Coverage In Heterogeneous Sensor Networks

Loukas Lazos and Radha Poovendran

Network Security Laboratory (NSL), Department of Electrical Engineering,
University of Washington, Seattle, WA,
l lazos, radha@ee.washington.edu

Abstract— In this paper we study the problem of coverage in according to a distribution, and is relevant in applications
heterogeneous planar sensor networks. Coverage as a perfor- where the sensors’ positions cannot be selected a priori.
mance metric, quantifies the quality of monitoring provided by
In this paper, we analyze the following stochastic coverage
the sensor network. We formulate the problem of coverage as a
set intersection problem arising in Integral Geometry, and derive problem. Given a planar field of interest and N sensors
analytical expressions for stochastic coverage. Our formulation deployed according to a known distribution, compute the
allows us to consider a heterogeneous sensing model, where fraction of the field of interest that is covered by at least
sensors need not have an identical sensing capability. In addition, k sensors (k ≥ 1). The problem can also be rephrased as,
our approach is applicable to scenarios where the sensing area
given a field of interest and a sensor distribution, how many
of each sensor has arbitrary shape and sensors are deployed
according to any distribution. We present analytical expressions sensors must be deployed in order for every point in the field
only for convex sensing areas, however, our results can be of interest to be covered by at least k sensors with a probability
generalized to non-convex areas. The validity of our expressions p (k-coverage problem) [20].
is verified by extensive simulations. In this paper we make the following contributions. We
formulate the problem of coverage in sensor networks as
I. I NTRODUCTION
a set intersection problem. We use results from integral
Sensor networks are projected to have a significant impact geometry to derive analytical expressions quantifying the
into our everyday lives, with applications to environmental coverage achieved by stochastic deployment of sensors into
monitoring, home health care, disaster relief operations, and a planar field of interest. Compared to previous analytical
ambient monitoring [1]. One of the primary tasks of sensor results [8], [12], [20], our formulation allows us to consider
networks is the collective monitoring of a field of interest. a heterogeneous sensing model, where sensors need not have
Sensors may monitor physical properties such as temperature, an identical sensing capability. In addition, our approach is
humidity, air quality, or track the motion of objects moving applicable to scenarios where the sensing area of a sensor
within the field of interest. In order for the sensor network is not an ideal circle, but has any arbitrary shape. To the
to sufficiently monitor the entire field of interest, one needs best of our knowledge, only [15] considers a heterogeneous
to ensure that every point of the field is covered by at least sensing model, though only incorporating the mean value of
one sensor. Furthermore, to provide the desired accuracy and the sensing range in the coverage computation. In addition, the
robustness against node failures, many applications require formulation in [15] considers only uniformly deployed sensors.
that each point of the field of interest is sensed by more In our approach, sensors can be deployed according to any
than one sensor. Hence, the problem of node deployment for distribution. We provide formulas for k-coverage in the case
the purpose of sensing can be viewed as a coverage problem, of heterogeneous sensing areas, as well as the simplified forms
defined below. in the case of identical sensing areas, and give an example for
The coverage problem is to quantify how well is the field of the computation of the number of sensors required to cover
interest sensed by the deployment of the sensor network. The a field of interest with a pre-specified probability. Finally, we
coverage problem can be studied under different objectives and validate our theoretical expressions via simulations and show
constraints imposed by the applications such as, worst-case an exact match between simulation and theory.
coverage [10], deterministic coverage [10], [12] or stochastic The rest of the paper is organized as follows. In Section
coverage [8], [10], [12], [15], [20]. The worst-case coverage III we formulate the coverage problem as a set intersection
problem quantifies coverage based on the parts of the field of problem. In Section IV we derive analytical expressions for
interest that exhibit the lowest observability from the sensors coverage. In Section V, we validate our theoretical results via
[10], and is relevant in applications where a desired threshold simulation. Section VI presents our conclusions.
number of sensors need to observe the field of interest.
The deterministic coverage problem [10], [12] quantifies the II. R ELATED W ORK
coverage achieved by deploying sensors in a deterministic
way, and is relevant in applications where one can select In this section we describe related work to the coverage
the positions where the sensors are placed. The stochastic problem in wireless sensor networks. The coverage problem
coverage problem [8], [10], [12], [15], [20], on the other hand, can be classified under different objectives and metrics. The
quantifies the coverage achieved when sensors are deployed different approaches to the coverage problem are, deterministic
 Form Approved
Report Documentation Page OMB No. 0704-0188

Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and
maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information,
including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington
VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it
does not display a currently valid OMB control number.

1. REPORT DATE 3. DATES COVERED

2. REPORT TYPE
2006 00-00-2006 to 00-00-2006
4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER
Coverage in Heterogeneous Sensor Networks 5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

6. AUTHOR(S) 5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION

REPORT NUMBER
University of Washington,Department of Electrical
Engineering,Seattle,WA,98195
9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S)

11. SPONSOR/MONITOR’S REPORT

NUMBER(S)

12. DISTRIBUTION/AVAILABILITY STATEMENT

Approved for public release; distribution unlimited
13. SUPPLEMENTARY NOTES
The original document contains color images.
14. ABSTRACT

15. SUBJECT TERMS

16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF
ABSTRACT OF PAGES RESPONSIBLE PERSON
a. REPORT b. ABSTRACT c. THIS PAGE
10
unclassified unclassified unclassified

Standard Form 298 (Rev. 8-98)

Prescribed by ANSI Std Z39-18
or stochastic sensor deployment, homogeneous or hetero- area of each sensor is identical. Furthermore, the analysis in
geneous sensing area, additional design constraints such as [12] suffers from the border effects problem, illustrated in [2],
energy efficiency, minimum number of sensors that need to [3]. The results hold asymptotically under the assumption that
be deployed, or network connectivity. Based on the objective, the field of interest expands infinitely in the plane, while the
the coverage problem formulation varies to reflect the different density of the sensor deployment remains constant.
assumptions and objectives. In [15], the authors study the stochastic coverage problem
In [9], the authors study the problem of deterministic node in ad hoc networks in the presence of channel randomness. For
placement in order to achieve connected coverage, that is, a randomly deployed sensor network, the authors analyze the
sense the field of interest with the minimum number of sen- effects of shadowing and fading to the connectivity and cov-
sors, while keeping the sensor network connected. The authors erage. They show that the in the case of channel randomness,
assume that the sensing area of each sensor follows the unit the coverage problem can still be modeled after the Spatial
disk model and consider sensors with identical sensing areas. Poisson distribution, by using expected size of the sensing
The problem of connected coverage has also been recently area of sensors. While the results in [15] are applicable to
studied in [20]. The authors provide a geometric analysis heterogeneous sensor networks, they hold only for randomly
that relates coverage to connectivity and define the necessary deployed networks, and are impacted from the border effects
conditions for a network covering a field of interest to be problem [2], [3], as noted by the authors [15].
connected. The conditions for coverage and connectivity are Compared to previous work that derives analytical coverage
derived based on the assumptions that the sensing area of each expressions [12], [15], [16], our formulation allows us to
node is identical and circular, and the location of the nodes consider a network model where, (a) sensors can be deployed
is known. The authors extend their algorithms for the case of according to any distribution, (b) sensors can have a sensing
probabilistic deployment, and also relax their assumptions to area of any arbitrary shape, (c) sensors can have heterogeneous
non-unit disk sensing areas, by approximating the real sensing sensing areas.
area with the biggest possible circular area included in the real
sensing area. III. P ROBLEM FORMULATION & BACKGROUND
In [16] the authors study the problem of deterministic In this section, we formulate the problem of coverage in
coverage under the additional constraint that each sensor must heterogeneous sensor networks as a set intersection problem
have at least k neighbors. They propose a deployment strategy arising in Integral Geometry [7], [14], [17]–[19] and provide
that would maximize the coverage while the degree of each relevant background for the set intersection problem.
node is guaranteed to be at least k, under the assumption that
the sensing range of the sensors is isotropic. A. Problem Formulation
In [13], the authors study the problem of coverage, as a
path exposure problem. Using a generic sensing model and We formulate the problem of stochastic coverage as follows.
an arbitrary sensor distribution, they propose a systematic Let A0 denote the planar field of interest we want to monitor,
method for discovering the minimum exposure path, that is the with area F0 and perimeter L0 . Assume that N sensors with
path along which the network exhibits the minimum integral sensor si having a sensing area Ai , (i = 1 . . . N ), are
observability1 . Authors in [10], investigate the problem of deployed according to a distribution K(A0 ) and in such a way
best- and worst-case coverage. In their formulation of the that they sense some part of the field of interest2 . Let Fi , Li
coverage problem, given the location of the sensors and a denote the size and the perimeter of the sensing area Ai of
generic sensing model where the sensing ability of each each sensor si , respectively. We want to calculate the fraction
sensor diminishes with distance, the authors use Voronoi of A0 that is sensed by at least k sensors, i.e. the fraction that
diagrams and Delaunay triangulation to compute the path that is k-covered (k ≥ 1). This problem is equivalent to computing
maximizes the smallest observability (best coverage) and the the probability that a randomly selected point P ∈ A0 is
path that minimizes the observability by all sensors (worst sensed by at least k sensors. We map this coverage problem
coverage). In [11], the authors provide a decentralized and to the following set intersection problem. In our formulation,
localized algorithm for calculating the best coverage. a set S is defined as a collection of points in the plane, and
for the coverage problem the sets are closed regions.
Authors in [12], study the problem of stochastic coverage
in large scale sensor networks. For a randomly distributed Let S0 be a fixed closed set defined as a collection of
sensor network, the authors provide the fraction of the field points in the plane, and let F0 and L0 denote the area and
of interest covered by k sensors, the fraction of nodes that perimeter of S0 . Let N closed sets Si (i = 1 . . . N ) of size Fi
can be removed without reducing the covered area as well and perimeter Li be dropped in the plane of S0 according
as the ability of the network to detect moving objects. The to a distribution K(S0 ) and in such a way that every set Si
results presented in [12] hold only for randomly (uniformly) intersects with S0 . Compute the fraction of S0 where at least
deployed networks and under the assumption that the sensing 2 Note that for sensing, we do not require that sensors are located within
the field of interest. Instead, as shown in Figure 1(a), we require that they
1 The integral observability is defined as the aggregate of the time that a can monitor some part of the field of interest even if they are located outside
target was observable by sensors while traversing a sensor network. of it.
 y
A1
A01

x A0
O

Sensor field A0 Sensing area Ai

(a) (b) (c)

Fig. 1. (a) A heterogeneous sensor network with sensors covering the deployment region A0 . (b) A convex set A and the corresponding quantities that
define the kinematic density. (c) Two convex sets A0 , A1 intersecting, and the common area A0 .

k out of the N sets Si intersect. In figure 1(b), we show a set S, a randomly selected
reference point O ∈ S, and the axis of a coordinate system.
In the mapping of the stochastic coverage problem to the All rotations and translations for the set S are defined with
set intersection problem, the fixed closed set S0 corresponds to respect to the reference point O. Integrating the kinematic
the field of intersect A0 . The N closed sets dropped according density of a set A over a group of motions M in the plane,
to the distribution K(S0 ) correspond to the sensing areas of yields a measure for the set of motions M, which is called
the N sensors deployed according to the distribution K(A0 ). the kinematic measure [17], defined below.
By computing the fraction of the set S0 , where at least k out Definition 2: Kinematic measure–The kinematic measure
of N sets Si intersect, we equivalently compute the fraction m of a set of motions M in the plane is defined by the integral
of the field of interest that is k-covered3 . of the kinematic density dA over M :
The set intersection problem has been a topic of research of Z
Integral Geometry and Geometric Probability [7], [14], [17]– m= dA. (2)
M
[19]. Before we provide analytical coverage expressions based By measuring the motions of a set in the plane, we quantify
on our formulation, we present relevant background. the space of all possible positions of the set that correspond
to that motion. The quotient of the measure of any random
B. Background on Integral Geometry
motion path Z over the measure of all possible motions M in
In this section, we present relevant background on Integral the plane, yields the probability p(Z) for that random motion
Geometry that we use in Section IV for deriving analytical path Z to occur:
coverage expressions based on our formulation. Interested
reader is referred to [7], [14], [17]–[19], as reference to m(Z)
p(Z) = . (3)
Integral Geometry. m(M)
We first define the notion of the kinematic density for the The kinematic measure allows us to compute the geometric
group of motions of a set A in the plane, that is used to define probability for a specific set configuration to occur, as depicted
a measure that quantifies the possible positions of A, such that in (3). Equation (3), is used in our formulation to derive the
a specific event occurs [17]. The kinematic density expresses fraction of the field of interest covered by a sensor deployment,
the differential element of motion of a set in the plane and is as it is illustrated in the following section.
defined as follows.
Definition 1: Kinematic Density–Let M denote the group IV. C OVERAGE IN HETEROGENEOUS SENSOR NETWORKS
of motions of a set A in the plane. The kinematic density dA In this section, we derive analytical expressions for coverage
for the group of motions M in the plane for the set A, is by analyzing the coverage problem as a set intersection prob-
defined as the differential form: lem. We first illustrate the coverage computation when a single
sensor is randomly deployed to monitor the field of interest,
dA = dx ∧ dy ∧ dφ, (1) by studying the intersection of two sets in the plane. We then
where ∧ denotes the exterior product used in exterior calculus compute coverage when the sensor is deployed according to a
[5], [6], (x, y) denote the Cartesian coordinates, and φ denotes distribution K(A0 ). We extend our expressions to the general
the rotation angle of A with respect to the x axis of the case where N sensors are deployed at random. We compute
coordinate system4 [17]. the fraction of the field of interest covered by exactly k sensors
in the case of heterogeneous sensing areas and simplify the
3 Due to their equivalence, A and S as well as the terms sensing area
0 0 formula when the sensors have identical sensing areas. Finally,
and set are used interchangeably in the rest of the paper.
4 For every set A, one can randomly choose a reference point O, based on we compute the fraction of the field of interest covered by at
which all translations and rotation motions of A are defined. least k sensors.
 T
A. Coverage Achieved by Random Deployment of a Single A0 A1 6= 0 is:
Sensor Z
\
m(A1 : A0 A1 6= ∅) = T
dA1
Let us consider the simple case where a single sensor s1
ZA0 A1 6=∅
is randomly deployed in such a way that it monitors some
part of the field of interest. The achieved coverage can be = T
dx ∧ dy ∧ dφ
A0 A1 6=∅
computed by considering the intersection of two sets in the = 2π(F0 + F1 ) + L0 L1 . (6)
plane. Let A0 , A1 denote two sets in a plane with A0 being
fixed, while A1 can move freely. A0 represents the field of Due to the length and complexity, the proof of (6) is omitted.
interest, while A1 represents the sensing area of node s1 . The Interested reader is referred to [17], [18] for details.
average size of the common area A01 between sets A0 , A1 ,
By combining (5) and (6) we can compute the probability
when A1 is randomly dropped in the plane, defines the area
p(P ∈ A1 ) as:
of A0 , covered by A1 . Normalizing A01 over A0 we obtain
the fraction f r(A0 ) of A0 covered by A1 . In figure 1)(c), we T
m(A1 : P ∈ A0 A1 )
show two sets A0 , A1 and the common area between them. p(P ∈ A1 ) = T
m(A1 : A0 A1 6= ∅)
To compute f r(A0 ), we randomly select a point P of A0 , 2πF1
and find the set of all positions of A1 that include P. Dividing = . (7)
2π(F0 + F1 ) + L0 L1
the measure of all the positions of A1 that include T P over the
measure of all the positions of A1 such that A0 A1 6= ∅
yields the probability p(P ∈ A1 ) that the randomly selected Note that p(P ∈ A1 ) is only dependent on the area and the
point P is covered by A1 [17], [18]. Integrating p(P ∈ A1 ) perimeter of the convex sets that intersect and not on the shape
over all P ∈ A0 and normalizing over the size of A0 yields of those sets.
f r(A0 ). The following theorem holds only for convex sets,
though it can be extended in the case of non-convex sets by Lemma 1: The fraction f r(A0 ) of a fixed convex set A0 of
appropriate computation of the kinematic measures [17], [18]. area F0 and perimeter L0 that is covered by a convex set A1
of area F1 and perimeter L1 , when A1 is randomly dropped
in the plane in such a way that it intersects with A0 is given
Theorem 1: Let A0 be a fixed convex set of area F0 and by:
perimeter L0 , and let A1 be a convex set of area F1 and 2πF1
perimeter L1 , randomly dropped in the plane in such a way f r(A0 ) = . (8)
2π(F0 + F1 ) + L0 L1
that it intersects with A0 . The probability that a randomly
selected point P ∈ A0 is covered by A1 is given by:
Proof: Equation (7) expresses the probability that a
2πF1 randomly selected point P ∈ A0 is covered by A1 . Integrating
p(P ∈ A1 ) = . (4) (7) over all points P ∈ A0 provides the size F01 of the
2π(F0 + F1 ) + L0 L1
common area A01 between A0 and A1 :
Z
Proof: The probability that P is covered by A1 is equal F01 = p(P ∈ A1 )dP
P ∈A0
to the measure of the set of motions of A1 such that P ∈ A1 Z
= p(P ∈ A1 ) dP
T by the measure of the set of motions of A1 such that
divided
P ∈A0
A0 A1 6= ∅. We now compute the two measures.
= p(P ∈ A1 )F0
Z 2πF0 F1
\ (i) = . (9)
m(A1 : P ∈ A0 A1 ) = T
dA1 2π(F0 + F1 ) + L0 L1
ZP ∈A0 A1
(ii) Normalizing F01 by F0 yields:
= dA1
P ∈A1
Z Z F01
2π f r(A0 ) =
= dx ∧ dy dφ F0
P ∈A1 0 2πF0 F1 1
= 2πF1 , (5) =
2π(F0 + F1 ) + L0 L1 F0
2πF1
=
where in 5(i)Twe integrate dA1 over all motions of A1 such 2π(F0 + F1 ) + L0 L1
that P ∈ A0 A1 . Since by assumption P ∈ A0 and A0 is = p(P ∈ A1 ). (10)
fixed, in 5(ii) we integrate dA1 over all motions of A1 such
that P ∈ A1 . The measure of all motions of A1 such that
B. Coverage Achieved by Deployment of a Single Sensor exactly k sensors is equal to the probability ¡that
¢ P is covered
According to an Arbitrary Distribution by exactly k specific sets. Let T denote a kx Nk matrix where
In the case where the A1 is not randomly deployed in each row j is a k-permutation
¡ ¢ of the vector [1 . . . N ], and let
the plane, but it follows an arbitrary distribution K(A0 ), the G denote a (N −k+1)x Nk matrix where each row j contains
measures in (5), (6) are calculated as weighted functions of the elements of [1 . . . N ], that do not appear in the j th row
the probability density function k(x, y, φ) of A1 . of T. Consider for example, T (1) = [1 . . . k] and G(1) =
Z [k + 1 . . . N ]. The probability p(T (1)) that P is covered by
\
m(A1 : A0 A1 6= ∅) = kdx ∧ dy ∧ dφ, (11) exactly the sets with indexes in the first row of T is given by:
ZZ
\ p(T (1))
(i)
= p(P ∈ A1 , . . . , P ∈
/ Ak+1 , . . . , P ∈
/ AN )
m(A1 : P ∈ A0 A1 ) = kdx ∧ dy ∧ dφ,(12)
(ii)
P ∈A1 = p(P ∈ A1 ), . . . , (P ∈ Ak )
T
where Z = A0 A1 6= ∅. Depending on the distribution p(P ∈
/ Ak+1 ), . . . , p(P ∈/ AN )
K(A0 ), the measures in (11), (12) may have a closed form. (iii) 2πF1
When A∞ is deployed according to the distribution K(A0 ), =
2π(F0 + F1 ) + L0 L1
we can calculate the probability p(P ∈ A1 ), by substituting 2πFk
the measures in (11), (12) into (7). The p(P ∈ A1 ), is the ...
2π(F0 + Fk ) + L0 Lk
basic building block for deriving expressions for coverage in
2πF0 + L0 Lk+1
the general case where N sensors are deployed, as we show
in the following section. 2π(F0 + Fk+1 ) + L0 Lk+1
2πF0 + L0 LN
...
C. Coverage in the Case of Multiple Sensors 2π(F0 + FN ) + L0 LN
Qk QN
In this section, we compute the probability p(S = k) that j=1 (2πFj ) z=k+1 (2πF0 + L0 Lz )
a randomly selected point P ∈ A0 is covered by k sensors = QN
when N sensors are randomly deployed. Using p(S = k), we r=1 (2π(F0 + Fr ) + L0 Lr )
Qk ¡ ¢ QN −k ¡ ¢
compute the probability that P is covered by at least k sensors, j=1 2πFT1,j z=1 2πF0 + L0 LG1,z
= QN .
as well as the fraction of A0 covered by at least k sensors.
r=1 (2π(F0 + Fr ) + L0 Lr )
Theorem 2: Let A0 be the field of interest of size F0 and (15)
perimeter L0 , and let N sensors with sensing area Ai of size
In (i), we show which k sets include point P. Due to the
Fi and perimeter Li be deployed over A0 . The probability
independence in the set deployment, in (ii), the intersection of
p(S = k) that a randomly chosen point P of A0 is covered
the events in (i) becomes a product of the individual events. In
by exactly k sensors when k ≥ 1 is given by:
(iii), we substitute the individual probabilities from (7), (14).
P(Nk ) ³Qk QN −k ´
In the general case, the probability that the sets with indexes
i=1 j=1 (2πFTi,j ) z=1 J (i, z)
p(S = k) = , (13) of the ith row of T cover point P is given by:
QN
r=1 (2π(F0 + Fr ) + L0 Lr ) Qk ¡ ¢ QN −k
j=1 2πFTi,j z=1 J (i, z)
where J (i, j) = (2πF0 + L0 LGi,z ), T is a matrix in which p(T (i)) = QN . (16)
each row j is a k-permutation of [1 . . . N ], and G is a matrix r=1 (2π(F0 + Fr ) + L0 Lr )
in which each row j contains the elements of [1 . . . N ], that Since we are not interested in a specific set permutation to
do not appear in the j th row of T. cover point P, the probability that p(S = k) is a summation
Proof: In order to prove Theorem 2, we map the problem of p(T (i)) for all possible k-permutations. Summing p(T (i))
of coverage to the set intersection problem, as illustrated in our over all i yields (13):
problem formulation in Section III-A. When a single sensor si (Nk )
is deployed, the probability that it covers a randomly selected X
p(S = k) = p(T (i))
point P ∈ A0 is given by Theorem 1. Hence, the probability i=1
p(P ∈/ Ai ) can be computed as:
(Nk ) Ã Qk ¡
X
¢ QN −k !
j=1 2πFTi,j z=1 J (i, z)
p(P ∈
/ Ai ) = 1 − p(P ∈ Ai ) = QN
2πFi i=1 r=1 (2π(F0 + Fr ) + L0 Lr )
= 1−
2π(F0 + Fi ) + L0 Li
2πF0 + L0 Li
= . (14) According to Lemma 1, (13) also expresses the fraction of A0
2π(F0 + Fi ) + L0 Li
that is covered by exactly k sensors. Equation (13) is valid for
Given that fact that the N sensors are independently deployed k ≥ 1. The fraction of the A0 that is not covered by any
in the plane so that they cover some part of A0 , the probability sensor, is given by the following corollary.
p(S = k) that a randomly selected point P ∈ A0 is covered by
 Non−covered fraction of A0
1
Theoretical
Simulated
0.8

Fraction fr(A0)
0.6

0.4

0.2

0
0 100 200 300 400 500 600
Sensor deployed (N)

Fig. 2. Fraction f r(A0 ) of A0 , that remains non-covered as a function of the number of sensors N that are deployed to monitor the field of interest.

Corollary 1: The fraction of A0 that is not covered by any Theorem 3: Let A0 be the field of interest of size F0 and
sensor when N sensors are randomly deployed is given by, perimeter L0 , and let N sensors with sensing area Ai of size
N
Fi and perimeter Li be deployed over A0 . The probability
Y 2πF0 + L0 Li that a randomly selected point of A0 is covered by at least k
p(S = 0) = . (17)
i=1
2π(F 0 + F i ) + L0 Li sensors is given by:

Proof: Given that fact that the N sensors are indepen- k−1
X
dently deployed in the plane so that they cover some part of p(S ≥ k) = 1− p(S = h) (20)
A0 , the probability p(S = 0) that none of the Ai , i = 1 . . . N h=1

covers point P is: where

p(S = 0) = p(P ∈
/ A1 , . . . , P ∈
/ AN ) P(Nh ) ³Qh QN −h ´
i=1 j=1 (2πFTi,j ) z=1 J (i, z)
YN p(S = h) = .
(i) QN
= p(P ∈
/ Ai ) r=1 (2π(F0 + Fr ) + L0 Lr )
i=1
Proof: Theorem 3, holds by observing:
YN µ ¶
(ii) 2πF0 + L0 Li
= . (18) k−1
X
i=1
2π(F0 + Fi ) + L0 Li p(S ≥ k) = 1 − p(S < k) = 1 − p(S = h), (21)
h=1
Equality in (i) holds due to the independence in the deploy-
ment of the sensors si . In (ii), we substitute p(P ∈
/ Ai ) from and substituting (13) into (21).
(14).
In the case where the sensors have identical sensing area, that V. VALIDATION OF THE T HEORETICAL R ESULTS
is, Fi = F and Li = L then the following corollary holds. In this section, we validate our theoretical results derived in
Corollary 2: Let Fi = F and Li = L. The probability Section IV via simulation. We perform experiments for both
that a randomly selected point of A0 is covered by exactly k homogeneous and heterogeneous sensor networks and show
sensors is given by that the theoretical formulas match the simulations. We also
¡N ¢ provide an example for analytically computing the number of
(2πF )k (2πF0 + L0 L)N −k sensors that need to be deployed in order to achieve the desired
p(S = k) = k N
. (19)
(2π(F0 + F ) + L0 L) degree of coverage.

A. Coverage in Homogeneous Sensor Networks

Proof: Corollary 2 holds by substituting Fi = F and
In our first experiment, we randomly deployed a variable
Li = L, into (13).
number of sensors with identical sensing area in a disk of
Once we have computed the probability for a randomly radius R = 100m. All sensors had a circular sensing area of
selected point P of A0 to be covered by exactly k sensors, radius r = 10m. We repeated the experiments 100 times and
we can also compute the probability that a randomly selected averaged the results. We first compute the fraction f r(A0 ) of
point P is covered by at least k sensors. A0 , that remains non-covered as a function of the number of
sensors N that are deployed to monitor the field of interest.
 Probability density function p(S=k) for N=200 Fraction of A0 covered by at least k sensors for N=200

0.3 Theoretical 0.8

Theoretical
Simulated Simulated
0.25
0.6
Fraction fr(A )

Fraction fr(A )
0

0
0.2

0.15 0.4

0.1
0.2
0.05

0 0
0 5 10 0 2 4 6 8 10 12 14
k (sensors) k (sensors)
(a) (b)
Probability density function p(S=k) for N=600 Fraction of A0 covered by at least k sensors for N=600

Theoretical Theoretical
0.16 Simulated Simulated
0.14 0.8
Fraction fr(A )

0.12

Fraction fr(A )
0

0
0.6
0.1
0.08
0.4
0.06
0.04 0.2
0.02

0 5 10 0 2 4 6 8 10 12 14
k (sensors) k (sensors)
(c) (d)

(e) (f)

Fig. 3. (a) The pdf of the fraction f r(A0 ) covered by exactly k sensors when N = 300 sensors with identical sensing area are randomly deployed. (b)
The fraction f r(A0 ) covered by at least k sensors when N = 300 sensors with identical sensing area are randomly deployed. (c) The pdf of the fraction
f r(A0 ) covered by exactly k sensors when N = 500 sensors with identical sensing area are randomly deployed. (d) The fraction f r(A0 ) covered by at
least k sensors when N = 500 sensors with identical sensing area are randomly deployed. (a) The pdf of the fraction f r(A0 ) covered by exactly k sensors
when N = 1000 sensors with identical sensing area are randomly deployed. (f) The fraction f r(A0 ) covered by at least k sensors when N = 1000 sensors
with identical sensing area are randomly deployed.

The theoretical formula that computes f r(A0 ) is obtained the theoretical formula in (22) conforms with the simulation
from Corollary 1 and is equal to: results. Since our method does not suffer from the border effect
µ ¶N problem, (22) is accurate despite the bounded size of the field
2πF0 + L0 L of interest.
f r(A0 ) = p(S = 0) = , (22)
2π(F0 + F ) + L0 L
In figure 3(a), we show the pdf of the fraction f r(A0 )
where F0 = πR2 , L0 = 2πR, F = πr2 , L = 2πr. In figure covered by exactly k sensors when N = 200 sensors with
2(a), we show the fraction f r(A0 ) of A0 , that remains non- identical sensing area are randomly deployed. The equivalent
covered as a function of the number of sensors N that are sensor density is equal to ρ = 0.0063 sensors/m2 . The
deployed to monitor the field of interest. We observe that same graphs for N = 600, N = 1000 (densities ρ = 0.019
 Fig. 4. Fraction f r(A0 ) of A0 , that remains non-covered as a function of the number of sensors N that are deployed to monitor the field of interest.

sensors/m2 , ρ = 0.032 sensors/m2 ) are provided in figures sensor density is equal to ρ = 0.0095 sensors/m2 . The
3(c) and 3(e), respectively. The pdf of f r(A0 ) is equal to same graph for N = 500, N = 1000 (densities ρ = 0.019
the probability that a randomly selected point P is covered sensors/m2 , ρ = 0.032 sensors/m2 ) are provided in figures
by exactly k sensors. Our analytical derivation in Section IV, 5(c) and 5(e), respectively. The f r(A0 ) covered by exactly K
yields: sensors is equal to the pdf p(S = k) of the probability that
a randomly selected point P is covered by exactly k sensors.
f r(A0 ) = p(S = k)
¡N ¢ k N −k
Our analytical derivation in Section IV, yields:
k (2πF ) (2πF0 + L0 L)
= N
. (23) f r(A0 ) = p(S = k)
(2π(F0 + F ) + L0 L)
In figure 3(b), we show the fraction of A0 covered by For k = 0 :
N µ
Y ¶
at least k sensors when N = 200. The same graphs for 2πF0 + L0 Li
N = 600, N = 1000 are provided in figure 3(d) and f r(A0 ) = ,
i=1
2π(F0 + Fi ) + L0 Li
3(f), respectively. For both values of N we observe that our
theoretic formulas conform with the simulation results. For all while for k ≥ 1 :
graphs in figure 2, 3 we show the theoretical result according P(Nk ) ³Qk QN −k ´
to our expressions, and the simulation values. i=1 j=1 (2πFTi,j ) z=1 J (i, z)
f r(A0 ) = QN .
B. Coverage in Heterogeneous Sensor Networks r=1 (2π(F0 + Fr ) + L0 Lr )
In our second experiment, we considered a hierarchical In figure 5(b), we show the fraction of A0 covered by
(heterogeneous) sensor network, where two types of sensors at least k sensors when N = 300. The same graphs for
are deployed. Type A has a sensing area of disk shape with a N = 500, N = 1000 are provided in figures 5(d), and
sensing range rA = 10m, while type B has a sensing area of 5(f), respectively. We again verify that our theoretical formula
disk shape with a sensing range of rB = 15m. We randomly agrees with the simulation results.
deployed an equal number NA = NB = N2 of sensors of In the case of heterogeneous sensor networks where each
each type over a circular field of interest of size F0 = πR2 sensor has a different sensing area, the formula in (25)
where R = 100m. In figure 4, we show the fraction f r(A0 ) has an exponentially increasing computational cost, since an
of A0 , that remains non-covered as a function of the number exponentially increasing summation of terms must be com-
of sensors N that are deployed to monitor the field of interest. puted in order to derive the exact coverage achieved. Such a
The theoretical formula that compute that is equal to: computation may not be feasible for large networks. In such
a case, an approximation can be used for our formulas by
f r(A0 ) = p(S = 0) employing the expressions derived for a homogeneous sensor
YN
2πF0 + L0 Li network and substituting the size F and perimeter L of the
= , (24) sensing area of the sensors with the expected size E[F ] and
i=1
2π(F 0 + Fi ) + L0 Li
expected perimeter E[L]. The theoretical approximation for
where F0 = πR2 , L0 = 2πR, Fi = πri2 , L = 2πri . such a case is:
We observe that the simulation results verify the validity
f r(A0 ) = p(S = k)
of our theoretical expression. In figure 5(a), we show the pdf ¡N ¢ k N −k
of the fraction f r(A0 ) covered by exactly k sensors when k (2πE[F ]) (2πF0 + L0 E[L])
= N
.(25)
N = 300 sensors are randomly deployed. The equivalent (2π(F0 + E[F ]) + L0 E[L])
 (a) (b)

(c) (d)

(e) (f)

Fig. 5. Heterogeneous sensor network, with the field of interest being a disk of radius R = 100m. An equal number of two types of sensors are deployed;
Type A has a sensing area of a disk shape with radius rA = 10m, while type B has a sensing area of a disk shape with rB = 15m. (a) The pdf of the
fraction f r(A0 ) covered by exactly k sensors when N = 300 sensors. (b) The fraction f r(A0 ) covered by at least k sensors when N = 300 sensors. (c)
The pdf of the fraction f r(A0 ) covered by exactly k sensors when N = 500 sensors. (d) The fraction f r(A0 ) covered by at least k sensors when N = 500
sensors. (e) The pdf of the fraction f r(A0 ) covered by exactly k sensors when N = 1000 sensors. (f) The fraction f r(A0 ) covered by at least k sensors
when N = 1000 sensors.

In figure 6(a) we show the pdf obtained via simulation for C. An Example of Computing the Coverage in a Sample
our heterogeneous sensor network experiment, for N = 500 Network
sensors, the theoretical values based on the exact formula in
(25), and the approximation in (25). In figure 6(b), we show In this section, we provide an example of applying our
the fraction of A0 covered by at least k sensors. We observe results to a sample sensor network. Consider an F oI of size
that for the case of heterogeneous sensor networks where F0 = 106 m2 and perimeter L0 = 4, 000m where sensors of
each sensor has a different sensing area, (25) provides a good identical sensing area F = 100π and perimeter L = 20π
approximation of the coverage achieved, without incurring the are randomly deployed. We want to compute the number of
computational cost of (25). sensors needed in order for a randomly selected point of the
F oI to be covered by at least one sensor with a probability
 (a) (b)
Fig. 6. Heterogeneous sensor network, with the field of interest being a disk of radius R = 100m. An equal number of two types of sensors are deployed;
Type A has a sensing area of a disk shape with radius rA = 10m, while type B has a sensing area of a disk shape with rB = 15m. (a) The pdf of the
fraction f r(A0 ) covered by exactly k sensors when N = 500 sensors. (b) The fraction f r(A0 ) covered by at least k sensors when N = 500 sensors.

pC = 95%. Or alternatively, the number of sensors N needed, R EFERENCES

so that a fraction pC = 0.95 of the field of interest is covered [1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey
by at least one sensor. Corollary 1 yields: on Sensor Networks,” IEEE Communications Magazine, Vol. 40, No. 8,
pp. 102-116, 2002.
p(S ≥ 1) = 1 − p(S = 0) [2] C. Bettstetter, and J. Zangl, “How to Achieve a Connected Ad Hoc
YN µ ¶ Network with Homogeneous Range Assignment: An Analytical Study
2πF0 + L0 L with Consideration of Border Effects,” WCNC ’02, 2002, pp. 125-129.
= 1− [3] C. Bettstetter, and O. Krause, “On Border Effects in Modeling and
i=1
2π(F0 + F ) + L0 L Simulation of Wireless Ad Hoc Networks, in Proceedings of the IEEE
µ ¶N MWCN ’01, 2001.
2πF0 + L0 L
= 1− . [4] T. Bonnesen, and W Fenchel, “Theorie de Convexen Korper,” Ergeb.
2π(F0 + F ) + L0 L Math. Springer, Berlin, 1934.
[5] H. Flanders, Differential Forms with Applications to the Physical Sci-
We want to the probability of 1-coverage to be at least p(S ≥ ences, Academic Press, New York, 1963.
1) ≥ p. Hence, [6] H. Flanders, Differential Forms, Prentice Hall, New Jersey, 1967.
[7] D. Filipescu, “On some Integral Formulas Relative to Convex Figures in
µ ¶N the Euclidean Space E2 ,” Stud. Cerc, Mat., Vol. 23, 1971, pp. 693–709.
2πF0 + L0 L [8] C. Huang, and Y. Tseng, “The Coverage Problem in a Wireless Sensor
P (S ≥ 1) = 1 − ≥ pC ⇒
2π(F0 + F ) + L0 L Network,” in Proceedings of WSNA ’03, 2003 pp. 115-121.
[9] K. Kar, and S. Banerjee, “Node Placement for Connected Coverage in
log (1 − pC )
N ≥ ³ ´. Sensor Networks,” in Proceedings of WiOpt ’03, March 2003.
2πF0 +L0 L [10] F. Koushanfar, S. Meguerdichian, M. Potkonjak, and M. Srivastava, Cov-
log 2π(F 0 +F )+L0 L erage Problems in Wireless Ad-Hoc Sensor Networks, in Proceedings
of the IEEE INFOCOM 01, March 2001, pp. 1380–1387.
Substituting the values for pC , F0 , L0 , F, L yields N ≥ 9, 728 [11] X. Li, P. Wan, and O. Frieder, “Coverage in Wireless Ad Hoc Sensor
sensors. Networks,” IEEE Transactions on Computers, Vol. 52, No. 6, 2003, pp.
753–763.
[12] B. Liu, and D. Towsley, “A Study of the Coverage of Large-scale Sensor
VI. CONCLUSION Networks,” in Proceedings of MASS ’04, 2004.
We studied the problem of stochastic coverage in planar [13] S. Meguerdichian, F. Koushanfar, G. Qu, and M. Potkonjak, “Exposure
in Wireless Ad hoc Sensor Networks,” in Proceedings of MobiCom ’01,
heterogeneous sensor networks. We formulated the coverage July 2001, pp. 139–150.
problem as a set intersection problem and used results from [14] R. Miles, “The Assymptotic Values of Certain Coverage Probabilities,”
Integral Geometry to obtain analytical expressions for the Biometrika, Vol. 56, 1969, pp. 661–680.
[15] D. Miorandi, and E. Altman, “Coverage and Connectivity of Ad Hoc
coverage achieved by the deployment of N sensors. Our Networks in Presence of Channel Randomness,” in Proceedings of the
formulation generalizes to a heterogeneous sensing model IEEE INFOCOM 05, March 2005, pp. 491–502.
where each sensor has a different sensing area, while it [16] S. Poduri, and G. S. Sukhatme, “Constrained Coverage for Mobile
Sensor Networks,” in Proceedings of IEEE International Conference on
does not suffer from the border effects problem. Furthermore, Robotics and Automation ’04, May 2004, pp. 165–172.
our approach applies to sensor deployment according to any [17] L. Santalo, Integral Geometry and Geometric Probability, Addison-
distribution. To verify our results, we performed extensive Wesley Publishing Company, 1976.
[18] L. Santalo, “Geometrica Intregral 4: Sobre la Medida Cinematica en el
simulation and showed that the simulation conforms with our Plano,” Abh. Math. Sem. Univ. Hamburg, Vol. 11, 1936, pp. 222–236.
theoretic formulas. [19] M. Stoka, “Alcune Formule Integrali Concenernenti i Corpsi Convessi
dello Spazio Euclideo E3 ,” Rend. Sem. Mat. Torino, Vo. 28, 1969, pp.
ACKNOWLEDGEMENTS 95–108.
[20] G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless and C. Gill, “Integrated
This work was supported in part by the following grants: Coverage and Connectivity Configuration for Energy Conservation in
ONR award, N00014-04-1-0479; ARO grant, W911NF-05-1- Sensor Networks,” ACM Transactions on Sensor Networks, Vol. 1, No.
1, 2005, pp. 36–72.
0491.