FLSS: a fault-tolerant topology control algorithm for wireless networks

ABSTRACT

Topology control algorithms usually reduce the number of links in a wireless network, which in turn decreases the degree of connectivity. The resulting network topology is more susceptible to system faults such as node failures and departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized algorithm, Fault-tolerant Global Spanning Subgraph (FGSSk), which preserves k-vertex connectivity. FGSSk is min-max optimal, i.e., FGSSk minimizes the maximum transmission power used in the network, among all algorithms that preserve k-vertex connectivity. Based on FGSSk, we propose a localized algorithm, Fault-tolerant Local Spanning Subgraph (FLSSk). It is proved that FLSSk preserves k-vertex connectivity while maintaining bi-directionality of the network, and FLSSk is min-max optimal among all strictly localized algorithms. We then relax several widely used assumptions for topology control to enhance the practicality of FGSSk and FLSSk. Simulation results show that FLSSk is more power-efficient than other existing distributed/localized topology control algorithms.

REFERENCES

• 1: M. Bahramgiri, M. Hajiaghayi, and V. S. Mirrokni. Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks. In Proc. Eleventh International Conference on Computer Communications and Networks (ICCCN), pages 392--397, Oct. 2002.
• 2: G. D. Battista, R. Tamassia, and L. Vismara. Output-sensitive reporting of disjoint paths. Algorithmica, 23(4):302--340, 1999.
• 3: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 4: S. A. Borbash and E. H. Jennings. Distributed topology control algorithm for multihop wireless networks. In Proc. International Joint Conference on Neural Networks, (IJCNN '02), pages 355--360, Honolulu, HI, USA, May 2002.
• 5: S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal on Computing, 4:507--518, 1975.
• 6: MohammadTaghi Hajiaghayi , Nicole Immorlica , Vahab S. Mirrokni, Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939016]
• 7: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 8: V. Kawadia and P. Kumar. Power control and clustering in ad hoc networks. In Proc. IEEE INFOCOM 2003, volume~1, pages 459--469, San Francisco, CA, USA, Apr. 2003.
• 9: Samir Khuller, Approximation algorithms for finding highly connected subgraphs, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 10: J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48--50, 1956.
• 11: 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]
• 12: N. Li and J. C. Hou. Topology control in heterogeneous wireless networks: problems and solutions. In Proc. IEEE INFOCOM 2004, Hong Kong, China, Mar. 2004 (the version in the conference proceedings has a technical error, and an updated version of the paper appears as a technical report at Department of Computer Science, University of Illinois at Urbana Champaign, Technical Report No. UIUCDCS-R-2004-2412, Mar 2004).
• 13: N. Li, J. C. Hou, and L. Sha. Design and analysis of an MST-based topology control algorithm. In Proc. IEEE INFOCOM 2003, volume~3, pages 1702--1712, San Francisco, CA, USA, Apr. 2003.
• 14: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed construction of planar spanner and routing for ad hoc networks. In Proc. IEEE INFOCOM 2002, volume~3, pages 1268--1277, New York, NY, USA, June 2002.
• 15: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778431]
• 16: S. McCanne and S. Floyd. ns Network Simulator. http://www.isi.edu/nsnam/ns/.
• 17: S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar. Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol. In Proc. European Wireless 2002, Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, pages 156--162, Florence, Italy, Feb. 2002.
• 18: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 19: R. Ramanathan and R. Rosales-Hain. Topology control of multihop wireless networks using transmit power adjustment. In Proc. IEEE INFOCOM 2000, volume~2, pages 404--413, Tel Aviv, Israel, Mar. 2000.
• 20: V. Rodoplu and T. H. Meng. Minimum energy mobile wireless networks. IEEE J. Select. Areas Commun., 17(8):1333--1344, Aug. 1999.
• 21: Hung-Ying Tyan , Chao-Ju Jennifer Hou, Design, realization and evaluation of a component-based compositional software architecture for network simulation, 2002

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
      C.2.4 Distributed Systems
          Subjects: Distributed applications
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
connectivity, energy management, fault tolerance, k-vertex, topology control, wireless networks