Hai Huang
Abstract
Ad-hoc networks of sensor nodes are in general semi-permanently deployed. However, the topology of such networks continuously changes over time, due to the power of some sensors wearing out, to new sensors being inserted into the network, or even due to designers moving sensors around during a network re-design phase (for example, in response to a change in the requirements of the network). In this paper, we address the problem of how to dynamically maintain two important measures on the quality of the coverage of a sensor network: the best-case coverage and worst-case coverage distances. We assume that the ratio between upper and lower transmission power of sensors is bounded by a polynomial of n, where n is the number of sensors, and that the motion of mobile sensors can be described as a low-degree polynomial function of time. We maintain a (1 + Ã)-approximation on the best-case coverage distance and a (ã2 + Ã)-approximation on the worst-case coverage distance of the network, for any fixed à > 0. Our algorithms have amortized or worst-case poly-logarithmic update costs. We are able to efficiently maintain the connectivity of the regions on the plane with respect to the sensor network, by extending the concatenable queue data structure to also serve as a priority queue. In addition, we present an algorithm that finds the shortest maximum support path in time O(n log n).
- {1} A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). Google Scholar
- {2} J. Basch, Kinetic data structures, Ph.D. dissertation, Stanford University (1999). Google Scholar
- {3} J. Basch, L.J. Guibas and J. Hershberger, Data structures for mobile data, in: Proc. of 8th ACM-SIAM Symposium on Discrete Algorithms (1997) pp. 747-756. Google Scholar
- {4} B.N. Clark and C.J. Colbourn, Unit disk graphs, Discrete Math. 86 (1990) 165-177. Google ScholarDigital Library
- {5} L.J. Guibas, J. Hershberger, S. Suri and L. Zhang, Kinetic connectivity for unit disks, Discrete Comput. Geom. 25 (2001) 591-610.Google ScholarDigital Library
- {6} J. Hershberger and S. Suri, An optimal algorithm for Euclidean shortest paths in the plane, SIAM J. Comput. 28(6) (1999) 2215-2256. Google ScholarDigital Library
- {7} J. Holm, K. de Lichtenberg and M. Thorup, Poly-logarithmic deterministic fully-dynamic graph algorithms I: Connectivity and minimum spanning tree, Technical Report DIKU-TR-97/17, Department of Computer Science, University of Copenhagen (1997).Google Scholar
- {8} C.-F. Huang and Y.-C. Tseng, The coverage problem in a wireless sensor networks, in: Proc. of the 2nd ACM Internat. Conf. on Wireless Sensor Networks and Applications (2003) pp. 115-121. Google Scholar
- {9} X.-Y. Li, P.-J. Wan and O. Frieder, Coverage in wireless ad-hoc sensor networks, IEEE Trans. Comput. 52 (2003) 1-11. Google Scholar
- {10} S. Meguerdichian, F. Koushanfar, M. Potkonjak and M.B. Srivastava, Coverage problems in wireless ad-hoc sensor networks, in: Proc. of the 20th IEEE INFOCOM (2001) pp. 1380-1387.Google Scholar
- {11} S. Meguerdichian, F. Koushanfar, G. Qu and M. Potkonjak, Exposure in wireless ad-hoc sensor networks, in: Proc. of the 7th ACM MOBICOM (2001) pp. 139-150. Google Scholar
- {12} X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless and C.D. Gill, Integrated coverage and connectivity configuration in wireless sensor networks, in: Proc. of the 1st ACM Conf. on Embedded Networked Sensor Systems (2003). Google ScholarDigital Library
- {13} H. Zhang and J.C. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Technical Report UIUCDCS-R-2003-2351, UIUC (2003).Google Scholar
Index Terms
- Dynamic coverage in ad-hoc sensor networks
Recommendations
Impact of Interference on Coverage in Wireless Sensor Networks
The quality of surveillance is dependent on the sensing coverage of a wireless sensor network. In the present paper, we examine how interference affects the coverage of a wireless sensor network. The coverage fraction and required number of sensors for ...
A Study of k-Coverage and Measures of Connectivity in 3D Wireless Sensor Networks
In a wireless sensor network (WSN), connectivity enables the sensors to communicate with each other, while sensing coverage reflects the quality of surveillance. Although the majority of studies on coverage and connectivity in WSNs consider 2D space, 3D ...
Coverage properties of clustered wireless sensor networks
This article studies clustered wireless sensor networks (WSNs), a realistic topology resulting from common deployment methods. We study coverage in naturally clustered networks of wireless sensor nodes, as opposed to WSNs where clustering is facilitated ...
Reviews
Ruay-Shiung Chang
Sensor networks have received a lot of research attention recently. A sensor can detect the environment around it. Assuming that a sensor's detecting ability is omni-directional, we can model the coverage of a sensor as a disk centered at the sensor. The radius of such a disk is determined by the energy level of the sensor. The coverage area of the sensor network is the union of all such disks. It is desirable that the coverage area be as thorough and complete as possible, such that an intruder is detected no matter where he or she hides. Given two locations S and T, two relevant types of trajectories on the sensor plane are proposed. A maximum breach path from S to T is a path from S to T in which the minimum distance from a point P in the path to the sensor network is maximized. This distance is called the worst-case coverage distance of the network. Similarly, a maximum support path from S to T is a path in which the maximum distance of a point P in the path to the sensor network is minimized. This distance is called the best-case coverage distance of the network. The best-case and worst-case coverage distances are two measures of the quality of the coverage of a sensor network. How to obtain these two measures in a dynamic sensor network, where old sensors may die, or new sensors may be added, is discussed first. The authors successfully transform these problems into graph connectivity problems. They present two algorithms to maintain low constant approximations on the best-case and worst-case coverage distances. Both algorithms have low update and query costs. The paper does not consider the actual implementation scenario, where sensors have to communicate by sending data to one another. Frequent transmitting will soon exhaust the energy. The authors' algorithm requires every sensor to send distance data to one sensor. This will lead to a large number of packets, and great system overhead.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments