14-11-2012, 02:07 PM
Coverage Problems in Wireless Ad-hoc Sensor Networks
1Coverage Problems.pdf (Size: 105.38 KB / Downloads: 20)
Abstract
Wireless ad-hoc sensor networks have recently
emerged as a premier research topic. They have great longterm
economic potential, ability to transform our lives, and
pose many new system-building challenges. Sensor networks
also pose a number of new conceptual and optimization problems.
Some, such as location, deployment, and tracking, are
fundamental issues, in that many applications rely on them
for needed information.
In this paper, we address one of the fundamental problems,
namely coverage. Coverage in general, answers the questions
about quality of service (surveillance) that can be provided by
a particular sensor network. We first define the coverage
problem from several points of view including deterministic,
statistical, worst and best case, and present examples in each
domain. By combining computational geometry and graph
theoretic techniques, specifically the Voronoi diagram and
graph search algorithms, we establish the main highlight of
the paper - optimal polynomial time worst and average case
algorithm for coverage calculation. We also present comprehensive
experimental results and discuss future research directions
related to coverage in sensor networks.
INTRODUCTION
As our personal computing era evolves into a ubiquitous
computing one, there is a need for a world of fully connected
devices with inexpensive wireless networks. Improvements
in wireless network technology interfacing
with emerging micro-sensor based on MEMs technology
[2], is allowing sophisticated inexpensive sensing, storage,
processing, and communication capabilities to be unobtrusively
embedded into our everyday physical world. Moreover,
embedded web servers [1, 3] can be used to connect
the physical world of sensors and actuators to the virtual
world of information utilities and services.
Consequently, a flurry of research activity has recently
commenced in the sensor network domain, especially in
wireless ad-hoc sensor networks. Although many of the
sensor technologies are not new, there are certain physical
laws governing the energy requirements of performing
wireless communications that have limited the feasibility of
such devices in the past.
Paper Organization
The reminder of the paper is organized as follows: In the
next section we summarize the related work. In section III,
we survey several key technologies that are fundamental to
our study of coverage. Section IV contains a brief overview
of deterministic sensor deployment and coverage. In section
V, we present a formal definition of the worst (breach)
and best (support) coverage and propose optimal polynomial-
time algorithms for solving each case. Section VI contains
a wide array of experimental results followed by a
brief discussion of our future research directions and the
conclusion.
RELATED WORK
The increasing trend in research efforts in the areas referred
to as Smart Spaces or Pervasive Computing are directly
related to many problems in sensor networks. Although
many researchers in the sensor network area have mentioned
the critical notion of coverage in the network, to our
knowledge this is the first time that an algorithmic approach
combined with computational geometry constructs
was adopted in ad-hoc sensor networks. Also, to our
knowledge, [18] was the first to identify the importance of
computational geometry and Voronoi Diagrams in sensor
network coverage. Reference [11] describes a general systematic
method for developing an advanced sensor network
for monitoring complex systems such as those found in
nuclear power plants but does not present any general coverage
algorithms. The Art Gallery Problem [12] deals with
determining the number of observers necessary to cover an
art gallery room such that every point is seen by at least
one observer. It has found several applications in many
domains such as the optimal antenna placement problems
for wireless communication. The Art Gallery problem was
solved optimally in 2D and was shown to be NP-hard in the
3D case. Reference [12] proposes heuristics for solving the
3D case using Delaunay triangulation. Sensor coverage for
detecting global ocean color where sensors observe the
distribution and abundance of oceanic phytoplankton [7] is
approached by assembling and merging data from satellites
at different orbits.
DETERMINISTIC COVERAGE
In order to achieve deterministic coverage, a static network
must be deployed according to a predefined shape. The
predefined locations of the sensors can be uniform in different
areas of the sensor field or can be weighted to compensate
for the more critically monitored areas. An example
of a uniform deterministic coverage is the grid-based
sensor deployment where nodes are located on the intersection
points of a grid. In this case, the problem of coverage
of the sensor field reduces to the problem of coverage of
one cell and its neighborhood due to the symmetric and
periodic deployment scheme.
An example of weighted predefined deployment is the security
sensor systems used in museums. The more valuable
exhibit items are equipped with more sensors to maximize
the coverage of the monitoring scheme. Another deterministic
deployment scheme can be found in the 3D Art Gallery
Problem heuristics solutions discussed in [12]. Our
proposed coverage algorithm can be used in all predefined
(deterministic) deployment schemes to determine the coverage
in the sensor field.
CONCLUSION
Several interpretations and formulations of coverage in
wireless ad-hoc sensor networks were presented. An optimal
polynomial time algorithm that uses graph theoretic
and computational geometry constructs was proposed for
solving for best and worst case coverages. Experimental
results show several applications of the theoretic coverage
formulations and algorithms specifically for solving for
Maximal Breach Path, Maximal Support Path, additional
sensor deployment heuristics to improve coverage, and
stochastic field coverage.