Low-coordination topologies for redundancy in sensor networks

ABSTRACT

Tiny, low-cost sensor devices are expected to be failure-prone and hence in many realistic deployment scenarios for sensor networks these nodes are deployed in higher than necessary densities to meet operational goals. In this paper we address the question of how nodes should be managed in such dense sensor deployments so that the network topology formed by the active sensors is able to provide connected-coverage to the entire area of interest and at the same time increase the lifetime of the network. In particular, we propose and study distributed, low-coordination node wakeup schemes to efficiently construct multiple independent (node-disjoint) sensor network topologies to achieve good fault tolerance. We propose and evaluate different distributed, random and pattern-based wakeup policies for sensor nodes to construct connected-covered topologies. Through analysis and simulations we demonstrate that in dense sensor deployment scenarios, these policies can construct near-optimal topologies (within 2.7% of the optimal) with zero coordination between nodes, as long as location information is available at the individual sensor nodes.Based on these observations, we develop and evaluate a few simple distributed, wakeup based topology construction algorithms that can realize similar performance bounds in realistic sensor deployments, with varying node densities. These algorithms differ in terms of the required level of coordination and the use of sensor location information, and generate connected-covered topologies efficiently, with very low message-exchange overhead.

REFERENCES

• 1: L. Booth, J. Bruck, M. Franceschetti and R. Meester, "Covering Algorithms, Continuum Percolation, and the Geometry of Wireless Networks," Annals of Applied Probability, 13(2), May 2003.
• 2: S. Shakkottai, R. Srikant, N. Shroff,"Unreliable Sensor Grids: Coverage, Connectivity and Diameter," To appear in the Proc. IEEE Infocom, San Francisco, March 2003.
• 3: P. Gupta and P. R. Kumar, "Critical Power for Asymptotic Connectivity in Wireless Networks," pp. 547--566, in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming. Edited by W.M. McEneany, G. Yin, and Q. Zhang, Birkhauser, Boston, 1998.
• 4: R. Kershner, "The number of circles covering a set", American Journal of Mathematics, 61:665--671, 1939.
• 5: W. Kuperberg, "Packing and covering problems in two and three dimensions", Alabama Journal of Mathematics 20, 1996.
• 6: P. Hall, Introduction to the Theory of Coverage Processes, John Wiley & Sons, 1988.
• 7: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 8: J. Quintanilla, S. Torquato, and R. Ziff, "Efficient Measurement of the Percolation Threshold for Fully Penetrable Disks", Journal of Physics A: Mathematics and General, 33, L399-L407 (2000).
• 9: Himanshu Gupta , Samir R. Das , Quinyi Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778438]
• 10: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 11: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 12: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 13: Y. Xu, J. Heidemann, D. Estrin, "Adaptive Energy Conserving Routing for Multihop Ad Hoc Networks", Tech. Report. 527, USC/ISI, Oct. 2000.
• 14: Curt Schurgers , Vlasios Tsiatsis , Saurabh Ganeriwal , Mani Srivastava, Topology management for sensor networks: exploiting latency and density, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513817]
• 15: 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]
• 16: G. Calinescu, S. Kapoor, A. Olshevsky, A. Zelikovsky, "Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks", Proc. ESA, 2003.
• 17: Thomas Moscibroda , Roger Wattenhofer, Maximizing the Lifetime of Dominating Sets, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 12, p.242.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.276]
• 18: H. Zhang, J.C. Hou, "Maintaining Sensing Coverage and Connectivity in Large Sensor Networks", Technical Report UIUCDCS-R-2003-2351, June 2003.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
connectivity, coverage, reliability, sensor networks