Constrained Coverage for Mobile Sensor Networks

Sameera Poduri and Gaurav S. Sukhatme

Robotic Embedded Systems Laboratory
Center for Robotics and Embedded Systems
Department of Computer Science
University of Southem California, Los Angeles, California, USA
(sameera,gaurav)@[Link]

AbsfmcI- We consider the problem of self-deployment of on node degree [3], a local constraint. This ability
a mobile sensor network. We are interested in a deployment to influence global network properties by manipulating
strategy that maximizes the area coverage of lbe network with lbe purely local ones is interesting.
constraint that each of lbe nodes has at least K neighbors, where
K is a user-specified parameter. We propose an algorithm based Pragmatically we are motivated by applications of network
on artificial potential fields which is distributed, scalable and does
not require a prior map of the environment. Simulationsestablish
_ _
deolovment where a global mar, of the environment is either
unavailable or of littie use because the environment is not
that the resulting networb have the required degree with a high static, we also that no global positioning system
probability, are well connected and achieve good coverage. We
= .
~ advlical
~ results
- ~ the ~
for ~ achievable by uniform
random and symmetrically tiled network configuratiork and use
(GPS) is available. An example is an urban search and rescue
operation where a building is on fire and first responders want
these to evaluate the performance of our algorithm. to gather information from inside the building. We would like
our mobile sensor network to deploy itself into the building,
I. INTRODUCTION
form a network with high sensor coverage and reliably transmit
There has been a growing interest to study and build systems required information to personnel outside,
of mobile sensor networks. It is envisaged that in the near Our approach the problem of coverage is
future, very large scale networks consisting of both mobile based on virtual potential fields. we treat each node in the
and static nodes will be deployed for applications ranging network as a virtual charged particle and &fine simple force
from environment monitoring to emergency search-and-rescue laws to the interaction neighboring
operations [I]. The mobile nodes in the network will enhance laws incorporate kinds of One is
its capabilities - they could be used to physically collect and a repulsive force that tries maximize coverage while the
transport data Or to recharge and repair the Static 'Odes in other is an attractive force that imposes the constraint of K -
network' A key step towards realizing such is [Link] a result of these forces, a group of nodes placed
to develop techniques for network nodes to self-deploy and close together spreads a network to maximize the
reconfigure. Further, for successful operation of the network, coverage while satisfying the of K-degree,
the deployment should result in configurations that not only
provide good 'sensor coverage' but also satisfy certain local
11. RELATED WORK
(e.g. node degree) and global (e.g. network connectivity)
constraints. Informally, Constrained Coverage is the problem In 1992, Gage inlroduced a taxonomy for coverage by multi-
of finding a deployment configuration which maximizes the robot systems [4]. He defined three kinds of coverage: blanket
collective sensor coverage of the nodes while satisfying one coverage, barrier coverage and sweep coverage. According to
or more constraints. this taxonomy our problem falls into the category of blanket
In this paper we consider constrained coverage for a network coverage problems where the main objective is to maximize
whose constituent nodes are all autonomous mobile robots. the total detection area.
The constraint we consider is node degree - the number of The problem of dispersing a large group of mobile robots
neighbors of each node in the network. More precisely, we into an unknown environment has received a lot of anen-
require each node to have a minimum degree K , where K tion. Arkin and Ali developed a behavior-based approach
is parameter of the deployment algorithm. Our interest in this for dispersion of robot-teams by using a random-wandering
particular constraint is twofold behavior coupled with obstacle and robot avoidance behaviors
1) In several applications of sensor networks, node degree [5]. More recently, Batalin and Sukhatme have addressed the
plays an imponant role. For instance, several localization problem of multi-robot area coverage [b].Their approach is
algorithms require a certain minimum degree for the based on using local dispersion of the robots to achieve good,
nodes [Z]. Sometimes a high degree is required for the global coverage. Pearce, et al. have developed a dispersion
sake of redundancy. behavior for a group of miniature robots inspired by insect
2) Evidence from the theory of random networks indicates colony coordination behaviors ['l].connectivity is a constraint
that global network connectivity is strongly dependent to task completion

07803-8232-3/04/$17.00 02004 IEEE 165

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 Potential Field techniques for robot applications were first IV. THE DEPLOYMENT
ALGORITHM
introduced by Khatib [SI and ever since have been used Potential field-based techniques have been used extensively
extensively to develop elegant solutions for path planning. to solve navigation problems in mobile robotics. In these
Recently, they have also been applied to multi-robot domains. methods, virtual potential fields are used to represent goals
Reif and Wang have used the idea of ‘social potentials’ where and constraints and the control law for the robot’s motion is
the potentials for a robot are conshcted with respect to the formulated such that it moves from a high potential state to
other robots 19). They describe heuristics to design social a low potential state similar to-the way in which a charged
potentials for achieving a variety of behaviors like clustering, panicle would move in an electrostatic field.
patrolling, etc. Balch and Hybinette have also developed a In our deployment algorithm, we construct virtual forces
method based on social potentials that allows teams of robots between nodes so that each node can attract or repel its
to autonomously arrange themselves into geometric patterns neighbors. The forces are of two kinds. The first, Fcover,
while navigating through an obstacle field [IO].These methods causes the nodes to repel each other to increase their coverage,
do not aim at maximizing the area coverage. Our algorithm and the second, Fdes,,, constrains the degree of nodes by
is most closely related to the potential field-based deployment making them attract each other when they are on the verge of
algorithm proposed by Howard, et al. [ 1 I] where coverage is being disconnected. By using a combination of these forces
achieved as an emergent property of the system. However. in each node maximizes its coverage while maintaining a degree
this case there is no constraint on the deployed network. of at least K.
To the best of our knowledge, the problem of coverage In OUT experiments, each [Link] with more than K
maximization in network deployment with an explicit node neighbors and repels all of them using Fcovertill it has only
degree constraint has not yet been addressed in the iiteraiure. K left. The resulting neighbors are called the node’s critical
111. PROBLEMFORMULATION
neighbors and the connections between them and the node are
called critical connections.
Problem: Given N mobile nodes with. isotropic radial The node now communicates to all its neighbors that its
sensors of range R, and isotropic radio communication of connection with them is critical and therefore should not be
.. range R,, how should they deploy themselves so rhat the broken. It then continues to repel all its neighbors using F,
resulting confrguration maximizes the net sensor coverage of but as the distance between the node and its critical neighbor
rhe network with the constraint that each node hns at leasr K increases. IIFcOverll decreases and [lFdegree/l increases. As
’’neighbors? a result, at some distance qRc, where 0 < q < 1, the net
Definition: Two nodes are considered neighbors if the
~

force IIFcOver + Fdesreell between the node and its neighbor

Euclidean distance between them is less than or equal to the is zero. At this distance, the node and its neighbor are in
communication range R,. equilibrium with respect to each other. We call f the safety
We make the following assumptions: factor because the larger its value, the smaller the probability
1) The nodes are capable of omni-directional motion, of critical neighbors losing connectivity.
2) Each node can sense the exact relative range and bearing The forces are constructed as inverse square law profiles -
of its neighbors, llFcowr1ltends to infinity when the distance between nodes is
. . 3) The quality of sensing (communication) is constant zero so that collisions are avoided. Similarly, llFdegreelltends
within R.(R,) and is zero outside the sensing (com- to infinity when the distance between the critical neighbors is
munication) range, i.e. it follows a binary model. R, so that loss of connectivity between them is prevented.
We impose certain desiderata on the problem solution. .The Figure 1 shows a node with > K and exactly K neighbors
deployment algorithm should: and Figure 2 shows the corresponding force profiles.
be distributed and scalable Mathematically, the forces can be expressed. as follows.
n
nodes 1 , 2 , 3 , .. .,TI at positions

-
.

’
.
not require a prior map or localization of nodes
adapt to changes in the environment and the network itself
We use the following [Link] evaluate the perfor-
Consider a .network of
xl, x2,. . . ,x,-respectively. Let Asij represent the Euclidean
distance between nodes i and.j, i.e. Az, = 11% - xjll
mince of the deployment algorithm.
F,,,,.and Fdegreearcdefined as follows.
1) the normalized per-node coverage. This is defined as:
(Net Area Covered by {he Nefwork)

[S::
Carerage =
NaR:
In the remainder of the paper, we use the term ‘coverage’
~ ~ j)
~ = ~
.;;;,..(=)
: ,%
~ ~ ( i
if critical connection;
:
to mean the normalized per-node coverage as defined otherwise.
above.
where K,,,,, and Kdegreeare the force constants.
2) the percentage of nodes in the network that have at least
The resultant force between the nodes 2 and 3 is
-
K neighbors.
.3) the average degree of the network. F(i,j)= Fcover(i:j) Fdegrdid +

166

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 .

(a) Node with >K neigh (b) N& with cxacUy K

bors (critical) neigh&

Fig. 1
ILLCSTRATION
OF THE ALGORITHM FOR K=3

Fig. 3
THEDEPLOYMENT ALGORITHM

(a) Non-Critical connection (b) critical connection

Fig. 2
FORCEPROF~LES

and node i will experience a net force of

Fi = W,j)
. q: A large q increases the probability of critical neighbors
getting disconnected while a small q results in lesser
all oeiphbonj
coverage. We used a value of 0.8 for q. This is a heuristic
The equation of motion for node a is formulated as:
. choice based on experimental experience.
U: We conducted a simple 'two-body' variant of our
scenario by implementing our algorithm on two nodes
to study the variation in their interaction for different
where v is a damping factor and m is the virtual mass of values of v. For these experiments we fixed the values of
the node which is assumed to be 1. K,,,,,, Kdegreeand q as explained above. We found that
Computational Details for small values of U the system oscillates. We picked the
smallest value of v that does not lead to oscillations. This
Having described the equation of motion for the node, we
discuss our choices of the four parameters K,,,.,, Kdeg... . value corresponds roughly to the critically dampedcase
for our system. In our experiments, we used U = 0.25.
U and q.
In the following two sections, we analyze the coverage
K,,,.,: Consider two nodes that are repelling each other.
achievable by uniform random and symmetrically tiled net-
As the distance d between them increases, the combined
work configurations that satisfy the constraint of K-degree.
coverage of the nodes increases, reaches a maximum of
These will serve as reference points to evaluate the perfor-
2rR: at d = 2R. and remains constant after that. This
mance of OUT algorithm.
implies that for d > 2R, repelling does not improve
coverage. We therefore pick a value for K,,,,, such that v. COVERAGE OF UNIFORM RANDOM NETWORKS
A uniform random network is one in which the nodes are
disuibuted randomly and with a uniform density. For such

167

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 -
networks. the nrobabilitv of findine i nodes in a snecified
domain depends only on the area of the domain and not on
VII. EXPERIMENTS
A N D RESULTS

This section presents a set of experiments designed to study

its shape or location. Given any area S, the probability that it
the performance of the proposed system for different values
will contain exactly i nodes is given by
of the innut oarameters. The simulations were conducted
1 .

using the Player/Stagel software platform which simulates the

P(i) o"e-ps
Z!
behavior of real sensors and actuators with a high degree of
where p is the density of node deployment [12]. fidelity [13]. Each of the nodes in our simulations is capable
The probability that a randomly chosen node will have a of omni-directional motion and sensing (using [Link] range
degree of at least K is the probability that there will be at finder). Further, each node has a retro-reflective beacon so that
least K nodes in the area rrR: around it. it can be distinguished from the obstacles in the environment.
In most of our simulations we used a 2-d obstacle-less
environment.
Figure 5 shows the initial and final network configuration
for a typical deployment. The circles in the figure represent the
As the density of deployment increases, the probability that coverage areas of individual nodes. The nodes start in a com-
each node will have a degree of at least K , increases but pact grid like configuration at the center of the environment
the per-node coverage of the network decreases. Therefore the and spread out to cover a large portion of the environment. In
best coverage achieved by a random network that satisfies the the particular instance shown, the sensing range of the nodes
constraint of K-degree with a high probability, say 0.95, will is equal to their communication range.
[Link] the smallest density for which P(i 2 K) 2 Figure 6 shows the variation of the coverage and average
0.95. Let this density be p'. degree of the network with time for different values of K.
The coverage of a uniform random network is.a function The coverage (average degree) increases (decreases) rapidly
of its density and R,. For a network with density p' the in the first 1-2 minutes and then saturates to a stable value
normalized per node coverage is: within 4-5 minutes. This is because, initially all the nodes have
more than K neighbors and so they spread out uninhibitedly to
improve the coverage until the degreeeconstraints activate and
restrict'their motion. Further, since these constraints activate
Note that this expression is independent of the number of at different stages for different values of K , the coverage
nodes in the network. (average degree) graphs for the different values of K, start
off. identically but branch off at different points and settle at
VI. COVERAGE [Link] TILEDNETWORKS different values of final coverage (degree).

-We define aSymmetricaNy liled Network as one in which

each node has exactly K neighbors
the distance between any two neighboring nodes is ex-
Figures 7 and.8 compare the performance of our algorithm
in terms of the coverage and average'node degree with the
uniform random and symmetrically tiled network configura-

... actly R,
a node's neighbors'are placed symmetrically around it
Figure 4 shows some network configurations thatsatisfy the
tions for three different regimes - R, > ZR,, R, = 2R, and
R, < 2R,. Clearly, the configurations we obtain outperform
the random network. Note that while computing the coverage
above properties. A striking feature of these configurations is of the symmetrically tiled configurations we assume that the
that the line; connecting neighboring nodes fo& regular poly- size of the network is infinite. The values thus-obtained are in
gons that tile the plane. For instance, in a network with K = 3 reality an upper bound on the coverage that can be achieved
the angle between twn neighbors of a node is = 120' and with finite networks because in the latter case, we will have
therefore configuration represents a hexagonal tiling. However, to take into accnunt the edge effects.
such configurations ye only. possible-for K = 0,' 1,2,3,4 and Our third petfnfiance metric (as discussed ,in section III)
6:For instance, if K =.5, then to form a symmetrically tiled is the percentage of the nodes in the network that have a
configuration, the corresponding regular polygon should have minimum degree of K. This we found was at least 95% in
an interior angle of = 72" which is not possible. - all the network configurations resulting form our deployment
Given a symmetrically tiled configuration, we can compute algorithm. This is also the case-with .the random networks.
the ' p r node coverage as a function of ~ R and, R,. If R, ,> Recall that while finding the density of deployment for the .
2R,, Cooerage = 1 because there will be no overlap between random network we explicitly imposd~theconstraint that each
the nodes. For [Link] when R, < 2R, and K = 1, node should have at least K neighbors with a probability
Coverage = (n-8/2+sin(e/2)) where 0 ~ o s - l ( ~ we
) ,
of at least 0.95. In the symmetrically tiled configurations
n however this probability is 1 since all the nodes have exactly
can derive similar exnressions-for the other values of K.
It is our conjecture that the coverage of these Symmetrically
'Player/Slage was d&eloped jointly a1 the USC Robotics Research hh
Tiled networks is an upper bound on the coverage achievable HRL Labs fm,y available the General
by networks given the constraint of Kdegree. . - ' from http:[Link]

168

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 (a) K=O (b) K=I (e) K=2

(d) K=3 (e) K=4

Fig. 4
THESYMMETRICALLY TILED NETWORK CONFTGURATIONS FOR Rs < % < 2Rs

K neighbors.
An appealing and unexpected result is that there is no
significant change in the per-node coverage obtained when
the size of the network N was varied from 49 to 81 (Figure
9). One would expect that for smaller values of N the edge
effects will be more significant and therefore as N increases
the per-node coverage will increase. We speculate that either
the edge effects do not vary significantly with the network size
or a 49 node network is large enough to make edge effects
negligible. In future, work we plan to fully characterize this
relationship.
VIII. CONCLUSIONS AND FUTURE WORK
We have presented a deployment algorithm for mobile
K
sensor networks that is designed to maximize the collective
sensor coverage while simultaneously constraining the degree Fin
..6 ,
(I

of the network nodes. The pair-wise interaction between nodes VARIATION OF COVERAGE WITH NETWORK SIZE (N) FOR Ra = 4 AND
is governed by two kinds of virtual forces - one causes the R, = 8 (AVERAGEDOVER IOTRIALS)
nodes to repel each other to improve their coverage and the
other is an attractive force that prevents the nodes from losing
connectivity. By using a combination of these two forces,
every node tries to maximize its coverage while maintaining
the required number of neighbors. and symmetrically tiled networks proves that the algorithm
We have tested the algorithm extensively in simulation. results in reasonably good coverage. We are working towards
Starting with configurations in which each node has a degree validating these results through experiments on real robots.
greater than the required degree K, the algorithm results Possible criticisms of the algorithm are the strong assump-
in networks in which more than 95% of the nodes have tions it makes on the capabilities of the nodes - in particular
a degree of at least K . Our analysis of uniform random the ability of each node to measure the exact range and bearing

169

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 L'
. ..
'(a) lnitial Configuration (b) Final Configuration

Fig. 5
TYPICAL
NETWORKCONFIGURATIONS FOR A 64 NODE DEPLOYMENT WITH K=2

, ,
, ,

-/----=-
, ,

4='1 " ' " ' - l

Re. 6
THETEMPORAL PERFORMANCE FOR h' = 64. & = 4 AND & = 8 (AVERAGED OVER 10 TRIALS)

of the neighboring nodes and obstacles. In future, we plan to ACKNOWLEDGMENTS .

~ . extend the algorithm to work with approximate estimates of The authors thank all the of the REsL lab for
.. .range and bearing readings. their valuable feedback. This work is funded in part by grants
CCR-0120778 and lIS-0133947 from the National Science
The resulting network will reconfigure on addition of nodes, Foundation.
We would like it to be able to reconfigure even when some
of the nodes cease to function (e.g. due to energy depletion) REFERENCES
or are removed (e.g. due to malicious intervention). A simple [I] D. Esuin, D. Culln, K F'isrer, and G. S . Suhhahne. 'Connecting the
solution could be that when a node has less than K neighbors, physical world wi!h pervasive networks:' IEEE Pervarive Compuring.
vol. 1. no. 1. pp. 5 9 6 9 , zw2.
I it moves towards its [Link] till it gets connected [21 K, K, chiafalapudi, A, Dhariwal R, o. S. sukhame.
., -
~

to some of the neighbor's neighbors. This might result in it "-

"Ad-hae localizatioo usine meine and sectorine.'' in IEEE hfocomrn.
k
I

having more than neighbors - at which point the repulsive 'O

[3] F. Xue and P. R. Kumar. 'The number of neighbors needed for
forces will cause the nodes to spread out again. We plan to eonnecrivim of wireless networks." Wrdesr Network. vol. IO. no. 2.

170

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.
 (a) R, = 10 ( R , > ZR,) (b) Q = 8 (& = 2R,) le) Rc = 6 (Q < ZR.)

Fig. 7
COVERAGE FOR N = 49 AND Ra = 4 FOR DIFFERENT VALUES OF Q (AVERAGED OVER 10 TRIALS)

..I

(b) Q = 8 (Q = 2R.)

Fig. 8
DEGREE FOR N = 49 AND R, = 4 FOR DIFFERENT VALUES OF & (AVERAGED OVER 10 TRIALS)
AVERAGE

[4] D. W. Gage. ‘Command control for my-robot systems,” in AUVS-

92, the Nineteenth A n n u l AUVS Teclmical Symposiwn, Hunuvillc,
Alabama, USA. lune 1992. pp. 22-24.
[5] R. Arkin and K Ali, “lnregration of reactive and telerobotic conml
in multi-agcnl robotic systems,” in 7’hid lnremationnl Conference on
Sirnulotion of Adaptive Behavior, (SAB94)lFmm Animals lo Animtsl, [I21 P Hall, lnrmducrion to the theory of Coverage Pmcessres. John Wiley
Blighton, England. August 1994. pp. 47-78, and Sons, Octobcr 1998.
(61 [Link]& and G . S. Sukhatme, “Spreading out: A laeal approach 10 [I31 E. P. C a w , R. T. Vaughvan, A. Howard. G. S. Sukhaune. and M.I.
multi-robot mveragc:’ in 6th Intemnrional Confc~nceon Distributed Malaric. “Most valuable playa: A robot dwicc server for distributed
Autonomous Robotic Systems (DSRS02). Fukuoka. Japan, 2002, pp. 373- conmy in I E E m S I Inremorioml Conference on brtelligent Robots
382. arid systems (IROSOI). Wail-, Hawk October ZW1,pp. 1?2&1?31.
171 I. L. Pearce, P. E. Ryhsld, S. A. Stacter, and N. Papanikolopoulous,
“Dispersion behaviors for a team of multiple miniature robots:’ in IEEE
Inremotional Conference on Robotics and Automation, Taipei, Taiwan,
September zw3, pp. 1158-1163.
[8] 0. Khatib, “Rcal-time obstacle avoidance for manipulators and mobile
robots,” l~ntemtionolJoumnl of Robotics Research, vol. 5. no. 1, pp.
W 9 8 . 1986.
[9] I. H. kif and H. Wang. “Soeial potential fields: A distrihuted behavioral
conml for autonomous mbots,” Robotic$ and Autonomous Systems.
vol. 27, pp, 171-194. 1999.
1101 T. Balch and M. Hyhinefte. “Social potentials for scalable multi-
robot formations,’’ in IEEE lntemntionol Conference on Robotics ond
Auromtion. vol. 1, San Franscisco. April 2 W , pp. 73-80.

171

Authorized licensed use limited to: University at Buffalo Libraries. Downloaded on April 07,2025 at [Link] UTC from IEEE Xplore. Restrictions apply.