Wireless Sensor Network, 2009, 1, 417-424
doi:10.4236/wsn.2009.15050 Published Online December 2009 (http://www.scirp.org/journal/wsn).
417
Voronoi-Based Coverage Optimization for Directional
Sensor Networks
Jing LI1, Ruchuan WANG1,2,3, Haiping HUANG1, Lijuan SUN1,3
1College of Computer, Nanjing University of Posts and Telecommunications, Nanjing, China
2State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing, China
3Institute of Computer Technology, Nanjing University of Posts and Telecommunications, Nanjing, China
Received July 25, 2009; revised August 3, 2009; accepted August 4, 2009
Abstract
Sensing coverage is a fundamental problem in sensors networks. Different from traditional isotropic sensors
with sensing disk, directional sensors may have a limited angle of sensing range due to special applications.
In this paper, we study the coverage problem in directional sensor networks (DSNs) with the rotatable orien-
tation for each sensor. We propose the optimal coverage in directional sensor networks (OCDSN) problem to
cover maximal area while activating as few sensors as possible. Then we prove the OCDSN to be
NP-complete and propose the Voronoi-based centralized approximation (VCA) algorithm and the Vo-
ronoi-based distributed approximation (VDA) algorithm of the solution to the OCDSN problem. Finally, ex-
tensive simulation is executed to demonstrate the performance of the proposed algorithms.
Keywords: Directional Sensor Networks, Coverage, Deployment, Voronoi Diagram
1. Introduction
In recent years, wireless sensor networks (WSNs) have
attracted intense interests due to their wide applications
in military and civilian operations, such as environmental
monitoring, battlefield surveillance, and health care [1–3].
The conventional research of WSNs is always based on
isotropic sensors which can equally detect the environ-
ment in each orientation. However, sensors may have a
limited angle of sensing range due to special applications,
which are denoted as directional sensors. There are many
kinds of directional sensors, such as video sensors [4,5],
ultrasonic sensors [6] and infrared sensors [2]. The most
familiar directional sensors are the video sensors widely
used in wireless multimedia sensor networks (WMSNs).
Note that the directional characteristic we discuss in this
paper is from the point of view of the sensing, but not
from the communicating activity of sensors.
Sensing coverage is a fundamental issue in all sensor
networks, which has been studied by many works. Due
to the large variety of sensors and applications, coverage
is subject to a wide range of interpretations. In general,
coverage can be considered as the measure of quality of
service (QoS) in a sensor network. For example, the fa-
mous Art Gallery Problem [7] deals with determining the
number of observers necessary to cover an art gallery
room such that every point is detected by at least one
observer.
One approach to sensing coverage is the deployment
of sensors, which is a critical issue in existing works. A
well-planned deployment can help maximize the sensing
coverage while activating as few sensors as possible. A.
Ghosh [8] studies the problem of coverage holes under
random deployment. An algorithm is proposed to
achieve a tradeoff between the cost of deployment and
the percentage of area covered. In [9] and [10], two algo-
rithms are proposed to efficiently deploy sensors and to
maximize the coverage.
Different from traditional sensors, the coverage of a
directional sensor is determined by both its location and
orientation. Ma et al [11] provide a directional sensor
model where each sensor is fixed to one direction and
analyzes the probability of full area coverage. In [12,13],
Tao presents two coverage-enhancing algorithms to
minimize the overlapping sensing area of directional
sensors, according to the characteristic of adjustable ori-
entations of directional sensors. In [14–16], some algo-
rithms are proposed to cover maximal number of targets.
Unfortunately, they limit orientations of a directional
sensor, i.e. the sensor they assume cannot rotate its ori-
entation continuously. The previous works assume
commonly that after directional sensors are deployed
randomly, they adjust orientations to achieve efficient
coverage.
Given a directional sensor network, we are interested

J. LI ET AL. 418
in designing a deployment algorithm that is able to opti-
mize coverage. S. Megerian et al [17] present the
worst-case coverage in WSNs. They attempt quantifying
the QoS by finding areas of lower observability from
sensors and detecting breach regions, where breach is
defined as the minimum Euclidean distance from any
point on a path to any sensor. Due to find a path, where
minimize the probability of detecting the target moves
along this path, they define maximal breach path. Simi-
larly, J. Adriaens et al [18] put forward an optimal poly-
nomial time algorithm for computing the worst-case
coverage in DSNs. Both of them present centralized
methods using the Voronoi diagram to solve the worst-
coverage problem. The use of Voronoi diagram, effi-
ciently and without loss of optimality, transforms the
continuous geometric problem into a discrete graph
problem.
In this paper, we mainly address the problem of
maximal coverage while activating as few sensors as
possible, called optimal coverage in directional sensor
networks (OCDSN) problem. For the solution to this
problem, we will propose two optimizing coverage algo-
rithms based on the Voronoi diagram. Both of two algo-
rithms, called the Voronoi-based centralized approxima-
tion (VCA) algorithm and the Voronoi-based distributed
approximation (VDA) algorithm, contribute to making
edges of Voronoi cover as more as possible, which could
keep the worst-case coverage. Further, it is approxi-
mately considered that if most paths are covered, most
Voronoi polygons are covered, i.e. most of the given
monitoring area is covered.
From the perspective of directional sensors, the effect
of coverage has three parameters: the number of sensors,
sensing range and the field of view (FOV). As shown in
the following sections, we will discuss the impact of
these parameters on the coverage of a directional sensor
network.
The rest of this paper is organized as follows: We
formally establish a mathematical model for representing
the FOV in Section 2, and then define the OCDSN prob-
lem and prove that it is NP-complete in Section 3. Fur-
thermore, we propose VCA and VDA of solution to the
OCDSN in Section 4. Simulation results are presented to
show the effectiveness of the proposed algorithms in
Section 5. Finally, we conclude the paper in Section 6.
2. Preliminaries
2.1. Sensing model
A directional sensor has a finite angle of view. From the
concept of FOV, its sensing region can be viewed as a
sector in a two-dimensional plane denoted by 4-tuple
(,, ,)
S
LR

 as shown in Figure 1. The sensing model of
a directional sensor is defined as follows.
R
S


L
Figure 1. Sensing model of a directional sensor.
Definition 1 The directional sensing model: 4-tuple
(,, ,)
S
LR


 L: the location of the sensor.
 Rs: sensing range of the sensor.
  : the offset angle of FOV , which equals to the
half of the vertex angle of sensing sector.
 β: the horizontal angle to the midline of sensing
sector, 02



. This parameter defines the ori-
entation of the directional sensor.
2.2. Notations and Assumptions
We adopt the following notations throughout the paper.
 A: the given specified area to be covered.
 N: the number of sensors.
 Si: the ith sensor, 1iN

.
 S: the set of sensors.


12
,,..., N Sss s.
 ,i


: the coverage of Si whose orientation is β,
1iN

, 02



.
 Φ: the set of the coverage of all sensor.


,|1,2,..., 02 iiN 

  .
 ,i P



: the point P covered by Si, 1iN

,
02



.
A point P is said to be covered by sensor Si if and only
if the following conditions are satisfied:
1) (,)
i
dis LPRS

, where is the Euclidean
distance between the location Li of sensor Si and point P.
Since Si corresponds to Li, throughout the rest of the pa-
per, unless otherwise mentioned, means
.
(,)
i
dis LP
(,)
i
dis sP
(,)
iPdis L
2) The horizontal angle to i
L
P

is within [,
i



i



].
An area A is covered by sensor Si, if and only if for
any point


1,2,...,
j
PAj

 , Pj is covered by Si, i.e.
,
j
i
P



.
For simplicity and computability, we make assump-
tions as below, however some of them can be relaxed.

J. LI ET AL.419
fi-
mmunication range is at least twice as large
 Directional sensors are homogeneous. Speci
cally, all sensors have the same omnidirectional com-
munication range Rc and shape of sensing sectors (i.e.
Rs and α).
 The co
as the sensing range, i.e. 2
cs
R
R.
 Every directional sensor knows its exact location
ion of every sensor has a uniform sens-
.3. Geometry Notation
he Voronoi diagram is an important data structure in
as VP(S). Ac-
co

However, some the lines at the boundaries of the
V
information.
 Each direct
ing sector.
2
T
computational geometry, which is a fundamental con-
struct defined by a discrete set of sites [19]. In a two-
dimensional plane, the Voronoi diagram partitions the
plane into a set of convex polygons such that all points
inside a polygon are closest to only one site. This con-
struction effectively produces polygons with edges that
are equidistant from neighboring sites.
We define the Voronoi polygon of Si i
rding to the property of Voronoi diagram, if an arbi-
trary point ()
i
PVPs then (,)(, )
ij
dis P sdis P s, where
, 1,2,...,ij N Therefnot de-
omenon in its Voronoi polygon, no
other sensor can detect it (assume that the directional
sensor can adjust its orientation circularly). The Voronoi
diagram generated by the set of sensors S is defined as
() ()
i
sS
VD SVP s

.
of
and i j.
ected phen
ore, if a sensor can
tect the exp
i
oronoi diagram extend to infinity. In this paper, the
monitoring area with our supposal is finite, so we clip the
Voronoi diagram within the boundary polygons. To do
this, we introduce extra edges in the Voronoi diagram
corresponding to the boundary edges and discard any
line segments that lie outside the boundary of the field as
shown in Figure 2. Let BVD(S) be the graph by removing
Figure 2. Boundary Voronoi diagram.
all edges n area A, of VD(S) that no longer than the give
i.e. () ()BVD SVD SA

.
3. Problem Definition
Sensors are randomly deployed when we initialize the
nal sensor
ne
network, so the whole monitoring area is not always
covered by this initial deployment. Further, it is unnec-
essary that all sensors are active. Our goal is to schedule
the orientations in order to cover maximal area while
activating as few sensors as possible, called the optimal
coverage in directional sensor networks (OCDSN) prob-
lem. This problem can be defined as follows.
Definition 2 Optimal coverage in directio
tworks (OCDSN) problem: Given a specified area A, a
set of directional sensors S, and each sensor with four
parameters Li Rs, α and β, find a subset Z of Φ, with the
constraint that at most one φi,β can be chosen for the
same i (i.e. an active sensor has only one orientation), to
maximize the union of chosen ,i


 (i.e. the covered
area), while minimizing the card of Z={φi,β |(i, β)
is chosen} (i.e. the number of active directional sensors).
Definition 3 Decision version of OCDSN: Given a
inality
sp
e
O
DSN problem is NP-complete.
i-
ni
rithm can b
ove that the decision version of OCDSN
is
ecified area A, a set of directional sensors S, and each
sensor with four parameters Li Rs, α and β, determine if
there exists a subset Z of Φ with u0 elements of Φ, with
the constraint that at most one Li Rs, α and β, can be cho-
sen for the same i, covering at least p0 A, where u0 is a
given positive integer from 1 to N and p0 is a given posi-
tive pure decimal called the required ratio of coverage.
The following theorem shows the complexity of th
CDSN problem.
Theorem 1 The OC
Proof: We follow two steps to prove this theorem.
First, we prove that OCDSN∈NP. The non-determ
stic OCDSN algorithm is described as follows: Select
u0 elements of the set of directional sensors S and assign
a random orientation to each of these selected sensors, so
that 2-tuple (i, β) corresponds to φi,β. Then check that if
the union of chosen sensors covers at least p0 A, i.e.
,0ipA 
 
. It is easy to see this non-deterministic algo-
e verified in a polynomial time. Therefore,
OCDSN∈NP.
Second, to pr
NP-hard, we show a polynomial time reduction
3-CNF-SAT to OCDSN, i.e. 3-CNF-SAT∝OCDSN.
Before the proof, we suppose a special case where sen-
sors are isotropic (i.e.



) and it requires the whole
coverage (i.e. p
0 =1). ermore, a plane can be re-
garded as the set of infinite points, so we assume that our
goal to cover the area A is equivalent to covering infinite
points.
Furth

J. LI ET AL. 420
he 3-CNF-SAT problem, a Boolean formula F
co
For t
nsisting of infinite clauses and N variables is in
3-conjunctive normal form, i.e. 1
j
j
Fc

 , where each
clause ,1 ,2,3
j
jj j
cl lland each literal


,11
, ,...,,
j
kNN
lllll. 


1, 2kgiven formula F
s constructed as follows:


|1,2,...Acj .
, 3 From the , an instance of
OCDSN i



j

,0 | is a literal in ,1,2,... ijij
cl cj  .

,| is a literal in ,1,2,... ijij
cl cj

 .

is construction can be finisheolynomial
tim
we prove that F is satisfiable if and only if A is
co
Thd in a p
e.
Now
vered. If F is satisfiable, then there is a set of truth
values for ,1,2,...,
i
li N, such that each clause is true
with this assus, with this assignment at least
one literal is true in each clause. Since each literal corre-
sponds to a φi,0 or φi,π, picking these true literals yields a
subset Z of Φ, where the cardinality of Z is the number of
active sensors, i.e.
ignment. Th
0
uZ. Note that l
i and i
l cannot
both be true, so the onding φi,0 and φi,0 Φ can-
not both be chosen into Z. Therefore, A is covered by Z.
Conversely, if A is covered by a subset Z of Φ and we
corresp in
suppose that
Z
N, then we assign true to the literals
which elemen correspond to. Obviously, every
clause is true because at least one of its literals is true.
Therefore, F is satisfiable.
We conclude that 3-CNF-S
ts in Z
AT∝OCDSN. The 3-CNF-
SA
is NP and NP-hard, the
re
4. Solution
ince the OCDSN problem is NP-complete, we propose
4.1. Voronoi-Based Centralized Approximation
o solve the NP-complete OCDSN problem as well as
CA is based on the greedy princi-
pl
is shown be-
lo
A algorithm
eploy N sensors randomly in monitoring area
T problem is known to be NP-complete, so the
OCDSN problem is NP-hard.
Since the OCDSN problem
sult follows.
S
two algorithms, the centralized algorithm and the distrib-
uted algorithm based on Voronoi diagram, both of which
solve the OCDSN problem efficiently.
(VCA) Algorithm
T
possible, we present the VCA algorithm that needs the
global information.
The main idea of V
e and can be described as follows. Initially, we deploy
a set of directional sensors S randomly in the monitoring
area A, all of which are inactive (i.e. not active). Sec-
ondly generate BV D (S) and construct F={maxlen (Si),i
=1,2,…, N}, where maxlen (Si) is the maximal length of
uncovered edges of BV
D (S) which Si can be possible to
cover. VCA runs in loops. In each loop, calculate the
maximal element of F and let Sj, the corresponding sen-
sor, be active. Rotate the orientation of Sj to make it
cover the maximal length of uncovered edges, remove Sj
from F and update F. If there are no more edges of
BV D (S) to be covered or no more inactive directional
sensors remaining, i.e. F is empty, the algorithm termi-
nates; otherwise, directional sensors are activated itera-
tively according to the above greedy rule.
The pseudo-code of the VCA algorithm
w.
VC
D


location( ),
ii
ixy
state( )'inactiv'ie

// Initialize the network, and
let all sensors be inactive.
Generate BV
D (S)
Construct {(),1,2,...,}
i
F
maxlen siN


while F is not empty && there is one edge uncovered
Calculate the maximal element of F
arg max{()}
ji
s
maxlen s

state()'active 'j

Rotate Sj orientation to make it cover the maximal
length of uncovered edges
Remove Sj from F
Update F
end while
Given N sensors, the best known algorithms for the
generation of the Voronoi diagram have O(NlogN) com-
plexities. In 2D, Voronoi diagrams are essentially linear
complexity in terms of vertices and edges. For N sensors,
E (numbers of edges) in the Voronoi diagram is O(N),
constructing and updating F need O(N2). The best
order algorithms have O(NlogN) complexities, thus cal-
culating the maximal element needs O(NlogN). The
complexity of while loop is O(N (NlogN+ N2). Therefore,
the total time of the VCA algorithm is as follows:
22
O(log) O() O( (log))NN NNNNN 
so
4.2. Voronoi-Based Distributed Approximation
s above, we can achieve the solution to OCDSN prob-
2
O( (log))NNNN
(VDA) Algorithm
A
lem approximately in polynomial time. However, the
VCA algorithm needs the global information, which in-

J. LI ET AL.421
e set of neighbors of S:
curs high cost. Without global information available in a
centralized location, each sensor must make its decision
independently based only on local information gathered
from the neighbors. In this subsection, we present the
VDA algorithm.
Definition 5 Th i
(){|( ,)2,1,2,...,}
jijS
N
eighborisSdisssRj N.
Definition 6 The weight of S:
i
,
1, if 0,
0, otherwise
i
E

ij
j
i i
i
e
E wE








where ,ij e is the length of ei j and ei j is the jth uncov-
ge of
iagram of S:
where C(S) is the communication regi of S, i.e.
As shown in Figure 3, eacdirectional sensor can
ca
ered ed BV D (S) that Si has the capability of sensing,
and Ei is the set of all ei j. Indeed, wi represents the prior-
ity among neighbors of Si.
Definition 7 Local Voronoi di
() ()()
ii
LVDsCs BVDS,
i i
() {|(,)}
iiC
CsPA dissPR.
h
on
lculate its local Voronoi diagram by collecting loca-
tions of all sensors in its communication region. Note
that we assume 2
CS
R
R, so ,()
ii
Cs


. Therefore
we can discuss thge of in its local
Voronoi diagram respectively.
The VDA algorithm is simp
e covera each sensor
ly described as follows.
Figure 3. Local Voronoi diagram of Si.
Initially, estate and
eudo-code of the VDA algorithm is shown be-
lo
VDA algorithm
. Initialization phase (only performed once)
ach directional sensor is in the active
collects locations of all sensors in its communication
region. Then each sensor generates local Voronoi dia-
gram respectively, and calculates its weight. Each sensor
starts to collect the information of its neighbors, i.e.
weights, covered edges, and states. Upon receiving the
information and updating its weight, each sensor makes
its decision independently as follows. If its weight is
maximal, it chooses the orientation for the purpose of
covering the maximal edge and sends out a new message
to inform its neighbors. If its weight is zero, it triggers a
transition timer, with random duration Tr. The timer is
canceled if new information from the neighbors arrives
and changes the weight to a non-zero value. Note that the
purposes of setting the transition timer Tr. are 1) to pre-
vent a sensor finalizing its decision before its neighbors
with higher weight and 2) to transfer its state to inactive
in time.
The ps
w.
1
Deploy N sensors randomly in A


location( ),
ii
ixy
state( )'active'i

S collects locationnsors in C(S), and generates
Calculate
rmation message to neighbors
ge from neighbors
al among neighbors of S
vering the
maxi
formation message to neighbors
en
and transition timer of S is off
tion timer of Si remains on for longer than
i i
()
i
LVD s
w
s of se
i
Send the info
2. Decision phase
for receiving messa
Update wi
if wi is maximi
Rotate the orientation to make co
mal edge
Send the in
if transition timer of Si is on
turn the transition timer off
end if
continue
d if
if wi =0i
turn the transition timer on
end if
if transi
r
T
state()'inactive'i

return
end if
end for

J. LI ET AL. 422
Table 1. Parameters setting.
Parameter Default Variation
A Area 500*500 500*500
Se N 200 nsor number 70-1000
Sens S 50
Offset angle α
ing range R30-120
π/3 π/6–π
isrithm terminates in finite
5. Simulations
this section, we evaluate the performance of two algo-
It clear that the VDA algo
time when all edges are covered or all sensors make their
decisions. By analyzing the pseudo-code, the initializa-
tion phase has O(NlogN) complexities, while the time of
decision phase is O(N).
In
rithms by simulations executed in MATLAB 7.4.0. The
simulation parameters are summarized in Table 1.
We compare the performance of VCA and VDA with
the coverage-enhancing algorithm which Tao [13] pre-
sented and the random algorithm in which every sensor
separately selects its orientation randomly. For random
algorithm, we run it 100 times and get the average value.
First, we examine the effect of the number of sensors
N. As shown in Figure 4, with the increase of sensors
deployed, both the ratio of coverage and number of ac-
tive sensors for all three algorithms increase linearly un-
til N approaches 400; upon passing such a value, the
number of active sensors increases slowly or even de-
creases whereas the ratio of coverage continuously in-
creases and then becomes saturated when N is above 400
or so. To state the difference: for the ratio of coverage,
VCA always behaves better than VDA, obviously Tao’s
and random algorithm; for the number of active sensors,
VCA activates larger number of sensors than VDA, and
the gap between two algorithm is nearly unfluctuating till
N exceeds a value (≥400 in this simulation). The rea-
sons that incur the above difference, are that 1) VCA and
VDA decrease overlapped area in dense network by ro-
tating orientations of directional sensors, so both of them
work better than the random algorithm; and 2) VCA
knows global information, while in VDA every sensor
makes its decision independently based only on local
information, so VCA achieves higher ratio of coverage
with more sensors whereas VDA activates less sensors
with lower ratio of coverage.
Figure 5 and Figure 6 show the influence of the sens-
ing range and the offset angle on our two algorithms re-
spectively. Clearly with the increase of Rs or α, the ratio
of coverage increases for VCA, VDA and random algo-
rithm, while the number of active sensors decreases.
Also, for the ratio of coverage, VDA works better than
VCA, Tao’s and random algorithm, and VCA excels
VDA in the number of active sensors. The intuitive rea-
sons for results are similar to the effect of number of
sensors. Notice that when Rs or α passes such a great
value (Rs approaches 120 and α approaches π in simula-
tions), the number of active sensors of VDA is near to
that of VCA. This is because the ratio of coverage is
saturated till Rs or α approaches a great value, and both
of two algorithms need a certain number of sensors.
6. Conclusions and Future Work
Coverage is always an important issue for sensor net-
works. Different from many other papers designed for
isotropic sensor networks, this paper has studied the
problem of optimal coverage of directional sensor net
0100 200 300 400 500 600 700 800 900 1000
0. 4
0. 45
0. 5
0. 55
0. 6
0. 65
0. 7
0. 75
0. 8
0. 85
0. 9
0. 95
1
Number of sensors
Ratio of coverage
VCA
VDA
Tao's
Random
0100 200 300 400 500 600700800 900 1000
50
100
150
200
250
300
Number of sensors
N
um
b
er o
f
act
i
ve sensors
VCA
VDA
(a) Ratio of coverage vs. number of sensors (b) Number of active sensors vs. numbe r of sensor s
Figure 4. Effect of number of sensors with50, 3
S
R



.

J. LI ET AL.423
30 40 50 60 7080 90100110120
0. 5
0. 55
0. 6
0. 65
0. 7
0. 75
0. 8
0. 85
0. 9
0. 95
1
Sensin
g
ran
g
e
Ratio of coverage
VCA
VDA
Tao's
Random
30 40 50 60 7080 90100110120
50
75
100
125
150
175
200
Sensing range
Number of active sensors
VCA
VDA
(a) Ratio of coverage vs. sensing range (b) Number of active sensors vs. sensing range
Figutre 5. Effect of sensing range with200, 3N



.
pi/6 pi/4pi/3 pi/2 pi/1.5 pi
0. 6
0. 65
0. 7
0. 75
0. 8
0. 85
0. 9
0. 95
1
Offset an
g
le
Ratio of coverage
VCA
VDA
Tao's
Random
pi/6pi/4 pi/3 pi/2 pi/1.5 pi
60
80
100
120
140
160
180
200
Offset an
g
le
Number of active sensors
VCA
VDA
(a) Ratio of coverage vs. offset angle (b) Number of active sensors vs. offset angle
Figure 6. Effect of offset angle with200, 50
S
NR

.
works and proved this problem is NP-complete. After the
VCA and VDA respectively. As a future work, we plan
to design energy efficient algorithms to prolong the life-
e are grateful that the subject is sponsored by the Na-
ndation of P. R. China (No.
0773041), the Natural Science Foundation of Jiangsu
definition of sensing model and some assumptions, we
present a centralized approximation algorithm and a dis-
tributed approximation algorithm to solve the OCDSN
problem, based on the boundary Voronoi diagram. As
our algorithms finish, we can obtain the optimizing cov-
ered area. Finally, we systematically evaluate the per-
formance of two algorithms through extensive simula-
tions. The results show that VCA and VDA work better
than the coverage-enhancing algorithm which Tao pre-
sented and the random algorithm, and fewer sensors can
cover more area so that more sensors can be inactive.
Moreover, we analyze the advantage and disadvantage of
time of directional sensor networks.
7. Acknowledgments
W
tional Natural Science Fou
6
Province(BK2008451), National 863 High Technology
Research Program of P. R. China (No. 2006AA01Z219),
High Technology Research Program of Nanjing City (No.
2007RZ106, 2007RZ127), Foundation of National
Laboratory for Modern Communications (No. 9140C11-
05040805), Jiangsu Provincial Research Program on

J. LI ET AL. 424
m, and E.
Cayirci, “A survey on sensor networks,” ACM Trans. on
omputing, Communications and Applica-
o. 8, pp. 102–114, August 2002.
26,
, April, 2007.
Applications, Vol. 1, No. 2,
ernational Conference on, pp.
80, December 1996.
under imprecise detections,”
sensor
International Conference on Mobile
nhancing algorithm for directional sen-
s,” Stojmenovic I, Cao JN, eds.
,”
oceedings of the Future Gen-
n directional wireless sensor
coverage in sensor
-of-view sensor
g
Natural Science for Higher Education Institutions (No.
07KJB520083) and Special Fund for Software Technol-
ogy of Jiangsu Province. Postdoctoral Foundation of
Jiangsu Province(0801019C), Science & Technology
Innovation Fund for higher education institutions of Ji-
angsu Province(CX08B-085Z, CX08B-086Z ).
8. References
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramania
netw
Ad-h
Multimedia C
tions, Vol. 40, N
[2] R. Szewczyk, A. Mainwaring, J. Polastre, J. Anderson,
and D. Culler, “An analysis of a large scale habitat
monitoring application,” ACM Conference on Embed-
ded Networked Sensor Systems (SenSys), pp. 214–2
2004.
[3] M. Li and Y. Liu, “Underground structure monitoring
with wireless sensor networks,” Information Processing
in Sensor Networks, IPSN, 6th International Symposium
on, pp. 69–78
[4] M. Rahimi, R. Baer, O. I. Iroezi, J. C. Garcia, J. Warrior,
D. Estrin, and M. Srivastava, “Cyclops: In situ image
sensing and interpretation in wireless sensor networks,”
SenSys, pp. 192–204, 2005.
[5] W. Feng, E. Kaiser, W. C. Feng, and M. L. Baillif, “Pan-
optes: Scalable low-power video sensor networking
technologies,” ACM Transactions on Multimedia Com-
puting, Communications and
pp. 151–167, May 2005.
[6] J. Djugash, S. Singh, G. Kantor, and W. Zhang,
“Rangeonly slam for robots operating cooperatively with
sensor networks,” Robotics and Automation, ICRA, Pro-
ceedings 2006 IEEE Int
2078–2084, May 2006.
[7] M. Marengoni, B. A. Draper, A. Hanson, and R. A. Sita-
raman, “A System to Place Observers on a Polyhedral
Terrain in Polynomial Time,” Image and Vision Com-
puting, Vol. 18, pp. 773–
[8] A. Ghosh, “Estimating coverage holes and enhancing
coverage in mixed sensor networks,” Local Computer
Networks, 29th Annual IEEE International Conference on,
pp. 68–76, November 2004.
[9] S. S. Dhillon, K. Chakrabarty, and S. S. Iyengar, “Sensor
placement for grid coverage
Information Fusion, Proceedings of the Fifth International
Conference on, Vol. 2, pp. 1581–1587, July 2002.
[10] S. S. Dhillon and K. Chakrabarty, “Sensor placement for
effective coverage and surveillance in distributed
orks,” in Proceedings of IEEE WCNC, pp. 1609–
1614, March 2003.
[11] H. Ma and Y. Liu, “On coverage problems of directional
sensor networks,” in
oc and Sensor Networks (MSN), Vol. 3794, pp.
721–731, 2005.
[12] D. Tao, H. Ma, and L. Liu, “A virtual potential field
based coverage-e
sor networks,” Journal of Software, Vol. 18, No. 5, pp.
1152−1163, May 2007.
[13] D. Tao, H. Ma, “Coverage-enhancing algorithm for di-
rectional sensor network
Proceedings of the 2nd International Conference on Mo-
bile Ad-Hoc and Sensor Networks, pp. 256−267, 2006.
[14] J. Ai and A. A. Abouzeid, “Coverage by directional sen-
sors in randomly deployed wireless sensor networks
Journal of Combinatorial Optimization, Vol. 11, No. 1,
pp. 21–41, February 2006.
[15] Y. Cai, W. Lou, and M. Li, “Cover set problem in direc-
tional sensor networks,” Pr
eration Communication and Networking (FGCN 2007),
Vol. 01, pp. 274–278, 2007.
[16] J. Wen, L. Fang, J. Jiang, and W. Dou, “Coverage opti-
mizing and node scheduling i
networks,” Wireless Communications, Networking and
Mobile Computing, WiCOM’08, 4th International Con-
ference on, pp. 1–4, October 2008.
[17] S. Megerian, F. Koushanfar, M. Potkonjak, and M.
Srivastava, “Worst- and best-case
networks,” IEEE Transactions on Mobile Computing,
Vol. 4, No. 1, pp. 84–92, February 2005.
[18] J. Adriaens, S. Megerian, and M. Potkonjak, “Optimal
worst-case coverage of directional field
networks,” Sensor and Ad Hoc Communications and
Networks, SECON’06, 3rd Annual IEEE Communica-
tions Society on, Vol. 1, pp. 336–345, September 2006.
[19] F. Aurenhammer, “Voronoi diagrams-A survey of a fun-
damental geometric data structure,” ACM Computin
Surveys, Vol. 23, No. 3, pp. 345–405, September 1991.