Dynamic coverage in ad-hoc sensor networks

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).

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Julien Basch , Leonidas J. Guibas, Kinetic data structures, 1999
• 3: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 5: {5} L.J. Guibas, J. Hershberger, S. Suri and L. Zhang, Kinetic connectivity for unit disks, Discrete Comput. Geom. 25 (2001) 591-610.
• 6: John Hershberger , Subhash Suri, An Optimal Algorithm for Euclidean Shortest Paths in the Plane, SIAM Journal on Computing, v.28 n.6, p.2215-2256, Dec. 1999 [doi>10.1137/S0097539795289604]
• 7: {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).
• 8: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
• 9: {9} X.-Y. Li, P.-J. Wan and O. Frieder, Coverage in wireless ad-hoc sensor networks, IEEE Trans. Comput. 52 (2003) 1-11.
• 10: {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.
• 11: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 12: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 13: {13} H. Zhang and J.C. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Technical Report UIUCDCS-R-2003-2351, UIUC (2003).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Keywords:
ad hoc sensor network, coverage, kinetic data structure