GS3: scalable self-configuration and self-healing in wireless networks

ABSTRACT

We present GS³, a distributed, scalable, self-configuration and self-healing algorithm for multi-hop wireless networks. The algorithm enables network nodes in a 2D plane to configure themselves into a cellular hexagonal structure such that cells have tightly bounded geographic radius and low overlap between neighboring cells. The structure is self-healing under various perturbations, such as node joins, leaves, deaths, movements, and state corruptions. For instance, it slides as a whole if nodes in many cells die at the same rate. Moreover, its configuration and healing are scalable in three respects: first, local knowledge enables each node to maintain only limited information with respect to a constant number of nearby nodes; second, local healing guarantees that all perturbations are contained within a tightly bounded region with respect to the perturbed area and dealt with in a one-way message diffusion time across the region; third, only local coordination is needed in both configuration and self-healing.

REFERENCES

• 1: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 2: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 3: Suman Banerjee, Samir Khuller, "A clustering scheme for hierarchical control in multi-hop wireless networks", IEEE INFOCOM, 2001.
• 4: Ting-chao Hou, Tzu-Jane Tsai, "An access-based clustering protocol for multihop wireless ad hoc networks", IEEE JSAC, July 2001.
• 5: National Research Council Staff, Embedded Everywhere: A Research Agenda for Networked Systems of Embedded Computers, National Academy Press, Washington, DC, 2001
• 6: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 7: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 8: Roger Wattenhofer, Li Li, Paramvir Bahl, Yi-Min Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks", IEEE INFOCOM 2001.
• 9: Volkan Rodoplu, Teresa H. Meng, "Minimum Energy Mobile Wireless Networks", IEEE JSAC, Aug. 1999.
• 10: V. H. Mac Donald, "Advanced mobile phone service: the cellular concept", The Bell System Technical Journal, 1979.
• 11: Shlomi Dolev , Evangelos Kranakis , Danny Krizanc , David Peleg, Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks, SIAM Journal on Computing, v.29 n.3, p.804-833, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797316610]
• 12: Theodoros Salonidis, Pravin Bhagwat, Leandros Tassiulas, Richard LaMaire, "Distributed topology construction of Bluetooth personal area networks", IEEE INFOCOM, 2001.
• 13: 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]
• 14: Hongwei Zhang, Anish Arora, "GS3: Scalable Self-configuration and Self-healing in Wireless Networks", OSU-CISRC-4/02-TR08, April 2002.
• 15: Simon R. Saunders , Saunders R Simon, Antennas and Propagation for Wireless Communication Systems, John Wiley & Sons, Inc., New York, NY, 1999
• 16: Jerry Zhao, Ramesh Govindan, Deborah Estrin, "Residual energy scans for monitoring wireless sensor networks", USC-CSD-TR-01-745, May 2001.
• 17: Mahesh Jayaram , George Varghese, Crash failures can drive protocols to arbitrary states, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.247-256, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248104]
• 18: W. Heinzelman, A. Chandrakasan, H. Balakrishnan, "An Application-Specific Protocol Architecture for Wireless Microsensor Networks", to appear in IEEE Transactions on Wireless Networking.
• 19: Shay Kutten , David Peleg, Fault-local distributed mending, Journal of Algorithms, v.30 n.1, p.144-165, Jan. 1999 [doi>10.1006/jagm.1998.0972 ]
• 20: A. Arora , M. Gouda, Distributed Reset, IEEE Transactions on Computers, v.43 n.9, p.1026-1038, September 1994 [doi>10.1109/12.312126 ]

INDEX TERMS

Keywords:
cellular hexagons, dynamics, geographyaware, locality, mobility, multi-hop wireless networks, scalability, self-configuration, self-healing, self-stabilization