Surface Coverage in Sensor Networks
Linghe Kong, Member, IEEE, Mingchen Zhao, Xiao-Yang Liu, Jialiang Lu, Member, IEEE,
Yunhuai Liu, Member, IEEE ,Min-YouWu,Senior Member, IEEE, and
Wei Shu, Senior Member, IEEE
Abstract—Coverage is a fundamental problem in wireless sensor networks (WSNs). Conventional studies on this topic focus on 2D
ideal plane coverage and 3D full space coverage. The 3D surface of a field of interest (FoI) is complex in many real-world applications.
However, existing coverage studies do not produce practical results. In this paper, we propose a new coverage model called surface
coverage. In surface coverage, the field of interest is a complex surface in 3D space and sensors can be deployed only on the surface.
We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor
deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. Thus, we target two problems assuming
cases of surface coverage to be true. One, under stochastic deployment, what is the expected coverage ratio when a number of
sensors are adopted? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full
coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation
algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct extensive simulations to
evaluate the performance of the proposed algorithms.
Index Terms—Wireless sensor networks, surface coverage, expected coverage ratio, optimal coverage strategy
Ç
1INTRODUCTION
C
OVERAGE problem is fundamental in wireless sensor
networks (WSNs). Each sensor is deployed to sense a
section of a field of interest (FoI). An FoI is considered fully
covered if and only if every point on the surface is covered
by at least one sensor. The quintessence of the coverage
problem is to use the least number of sensors to satisfy
specific service requirements, for example, coverage ratio,
network connectivity, and robustness. Solutions to the
coverage problem have important applications in base
station deployment in cellular networks, coverage in
wireless mesh networks and so on.
Existing works on coverage issues focus mainly on 2D
plane coverage or 3D full space coverage. In 2D plane
coverage [16], [3], sensors are only allowed to be deployed
on an ideal plane. And, in 3D full space coverage [10], [26],
the FoI is assumed to be the 3D full space where sensors can
be positioned freely within the whole FoI.
In many real-world applications, however, the FoI is
neither a 2D ideal plane nor a 3D full space. Instead, they are
complex surfaces. For example, in the Tungurahua volcano
monitoring project [1] (see Fig. 1), sensors are deployed on
the volcano, which is a surface. Existing 2D plane coverage
solutions do not provide a workable strategy. If the 2D
uniform deployment is adopted, there will be some cover-
age dead zone on the complex surface as illustrated in Fig. 2
(we called coverage dead zone problem). Similarly, 3D full
space coverage solutions cannot be applied either, because
sensors in this case can only be deployed on the exposed
surface area, and not freely inside the volcano or in the air.
Three-dimensional full space coverage solutions are not
discussed in this paper because they differ fundamentally
from issues of complex surface coverage.
To address the coverage solution in the surface applica-
tions, we propose an innovative model called surface
coverage. The surface coverage in WSNs (complex surfaces)
is superior to solutions derived from conventional 2D
ideal plane and 3D full space coverage methodologies.
Nonetheless, the advantages of surface coverage come with
new challenges such as how to handle variations in the
shape of the surface. This paper studies two problems in
WSN surface co ver age. One , com puting the expected
coverage ratio when a give n number of sensors are
scattered under stochastic deployment. Two, finding the
optimal deployment strategy with guaranteed full coverage
and the least number of sensors when sensor deployment is
pre-determined. We prove that the optimum surface cover-
age problem is NP-complete when applied to complex
surface. Then, we propose three approximation algorithms
with a provable performance bound for co verage of
complex surfaces. The methodology used in this paper
can be extended to other issues in surface coverage, for
example, connectivity problems and mobility problems.
The main results and contributions are summarized as
follows:
. To our best knowledge, this is the first work to tackle
the surface coverage problem in WSNs. We propose
a new model for the coverage problem.
. We derive analytical expressions of the expected
coverage ratio on surface coverage for stochastic
deployment. Simulation experiments are conducted
to verify the results.
234 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 1, JANUAR Y 2014
. L. Kong, X.-Y. Liu, J. Lu, Y. Liu, M.-Y. Wu, and W. Shu are with the
Shanghai Jiao Tong University, Room 121, No 3, SEIEE Building, Dong
Chuan Road, Shanghai 200240, China. E-mail: linghe.kong@sjtu.edu.cn.
. M. Zhao is at Room 613, 3330 Walnut Street, Philadelphia, PA, 19104.
Manuscript received 23 May 2012; revised 23 Jan. 2013; accepted 26 Jan.
2013; published online 14 Feb. 2013.
Recommended for acceptance by X.-Y. Li.
For information on obtaining reprints of this article, please send e-mail to:
tpds@computer.org, and reference IEEECS Log Number TPDS-2012-05-0489.
Digital Object Identifier no. 10.1109/TPDS.2013.35.
1045-9219/14/$31.00 ß 2014 IEEE Published by the IEEE Computer Society