Paper Menu >>
Journal Menu >>
![]() Wireless Sensor Network, 2009, 1, 417-424 doi:10.4236/wsn.2009.15050 Published Online December 2009 (http://www.scirp.org/journal/wsn). Copyright © 2009 SciRes. 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 Email: leejnjupt@126.com, {wangrc, hhp}@njupt.edu.cn 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. Copyright © 2009 SciRes. WSN ![]() 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 Copyright © 2009 SciRes. WSN ![]() 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 lland each literal ,11 , ,...,, j kNN lllll. 1, 2kgiven 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- Copyright © 2009 SciRes. WSN ![]() 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 Copyright © 2009 SciRes. WSN ![]() J. LI ET AL. Copyright © 2009 SciRes. WSN 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 Copyright © 2009 SciRes. WSN ![]() 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. Copyright © 2009 SciRes. WSN |