The Coverage Problem in a Wireless Sensor Network
[attachment=17748]

ABSTRACT
One fundamental issue in sensor networks is the coverage problem,
which reflects how well a sensor network is monitored or tracked
by sensors. In this paper, we formulate this problem as a decision
problem, whose goal is to determine whether every point in
the service area of the sensor network is covered by at least k sensors,
where k is a predefined value. The sensing ranges of sensors
can be unit disks or non-unit disks. We present polynomial-time
algorithms, in terms of the number of sensors, that can be easily
translated to distributed protocols. The result is a generalization of
some earlier results where only k = 1 is assumed. Applications of
the result include: (i) positioning applications, (ii) situations which
require stronger environmental monitoring capability, and (iii) scenarios
which impose more stringent fault-tolerant capability.
Categories and Subject Descriptors

F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical
Algorithms and Problems—Geometrical problems and
computations, Routing and layout
General Terms
Algorithms, Measurement, Reliability, Performance, Theory
Keywords
ad hoc network, computer geometry, coverage problem, ubiquitous
computing, wireless network, sensor network

1. INTRODUCTION
The rapid progress of wireless communication and embedded
micro-sensing MEMS technologies has made wireless sensor networks
possible. Such environments may have many inexpensive
wireless nodes, each capable of collecting, storing, and processing
environmental information, and communicating with neighboring
nodes. In the past, sensors are connected by wire lines. Today, this
environment is combined with the novel ad hoc networking technology
to facilitate inter-sensor communication [4, 15].



THE PROPOSED SOLUTIONS
At the first glance, the coverage problem seems to be very difficult.
A naive solution is to find out all sub-regions divided by the
sensing regions of all n sensors (i.e., n circles), and then check if
each sub-region is k-covered or not, as shown in Fig. 1. Managing
all sub-regions is a difficult and computationally expensive job in
geometry because there could exist as many as O(n2) sub-regions
divided by the circles. Also, it may be difficult to calculate these
sub-regions.

3.1 The k-UC Problem
In the section, we propose a solution to the k-UC problem, which
has a cost of O(nd log d), where d is the maximum number of sensors
that may intersect a sensor. Instead of determining the coverage
of each sub-region, our approach tries to look at how the
perimeter of each sensor’s sensing range is covered. Specifically,
our algorithm tries to determine whether the perimeter of a sensor
under consideration is sufficiently covered. By collecting this
information from all sensors, a correct decision can be made.