Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks

ABSTRACT

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(ka) approximation where a is the best approximation factor for the related problem in wired networks (the best a so far is in O(log k).) Then, using a more complicated algorithm and careful analysis, we achieve O(k) approximation for general graphs. We then present simple and practical distributed approximation algorithms for the cases of 2- and 3-connectivity in geometric graphs. In addition, we demonstrate how we can generalize this algorithm for k-connectivity in geometric graphs. Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining k-edge connectivity with guaranteed approximation factors.

REFERENCES

• 1: E. Althaus, G. Calinescu, I. Mandoiu, S. Prasad, N. Tchervenski, and A. Zelikovsky. Power efficient range assignment in ad-hoc wireless networks. Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), 2003. To appear.
• 2: M Bahramgiri, M Hajiaghayi, and V.S. Mirrokni. Fault-tolerant and 3-dimensional distributed topology control algorithms wireless multi-hop networks. In Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (ICCCN), pages 392--398. 2002.
• 3: Mostafa A. Bassiouni , Chun-Chin Fang, Dynamic channel allocation for linear macrocellular topology, Proceedings of the 1999 ACM symposium on Applied computing, p.382-388, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298391]
• 4: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, On the Symmetric Range Assignment Problem in Wireless Ad Hoc Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.71-82, August 25-30, 2002
• 5: Gruia Calinescu , Ion I. Mandoiu , Alexander Zelikovsky, Symmetric Connectivity with Minimum Power Consumption in Radio Networks, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.119-130, August 25-30, 2002
• 6: Julien Cartigny, David Simplot, and Ivan Stojmenovic. Localized minimum-energy broadcasting in ad-hoc networks. In Proceedings of fiftieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). 2003. To appear.
• 7: Joseph Cheriyan , Santosh Vempala , Adrian Vetta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509955]
• 8: Andrea E. F. Clementi , Pierluigi Crescenzi , Paolo Penna , Gianluca Rossi , Paola Vocca, On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.121-131, February 15-17, 2001
• 9: Andrea E. F. Clementi , Afonso Ferreira , Paolo Penna , Stephane Perennes , Riccardo Silvestri, The Minimum Range Assignment Problem on Linear Radio Networks, Proceedings of the 8th Annual European Symposium on Algorithms, p.143-154, September 05-08, 2000
• 10: A.E.F. Clementi, G. Huiban, P. Penna, G. Rossi, and Y.C. Verhoeven. Some recent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. Proceedings of 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE), pages 23--38, 2002.
• 11: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.197-208, August 08-11, 1999
• 12: András Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Discrete Mathematics, v.5 n.1, p.25-53, Feb. 1992 [doi>10.1137/0405003]
• 13: Andras Frank and Eva Tardos. An application of submodular flows. Linear Algebra Appl., 114/115:329--348, 1989.
• 14: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 15: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 16: K. Jain. A factor 2 approximation for the generalized steiner network problem. Combinatorica, 21(1):39--60, 2001.
• 17: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052]
• 18: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power consumption in packet radio networks, Theoretical Computer Science, v.243 n.1-2, p.289-305, July 28, 2000 [doi>10.1016/S0304-3975(98)00223-0]
• 19: Guy Kortsarz , Zeev Nutov, Approximating node connectivity problems via set covers, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.194-205, September 05-08, 2000
• 20: 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]
• 21: Weifa Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513815]
• 22: Errol L. Lloyd , Rui Liu , Madhav V. Marathe , Ram Ramanathan , S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513816]
• 23: Rudolf Mathar , Jürgen Mattfeldt, Optimal transmission ranges for mobile communication in linear multihop packet radio networks, Wireless Networks, v.2 n.4, p.329-342, Dec. 1996 [doi>10.1007/BF01262051]
• 24: R. Ramanathan and R. Rosales-Hain. Topology control of multihop radio networks using transmit power adjustment. In Proceedings of ninetieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 404--413. March 2000.
• 25: Volkan Rodoplu and Teresa H. Meng. Minimum energy mobile wireless networks. IEEE J. Selected Areas in Communications, 17(8):1633--1639, 1999.
• 26: Mader W. Ecken vom grad n in minimalen k-fach zusammenhangenden Graphen. Arch. Math. (Basel), 23:219--224, 1972.
• 27: P. Wan, A. Calinescu, X. Li, and O. Frieder. Minimum energy broadcast routing in static ad hoc wireless networks. In Proceedings of twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 607--617. 2001.
• 28: R. Wattenhofer, L. Li, V. Bahl, and Y.M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proceedings of twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1388--1397. 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Design, Reliability, Theory

Keywords:
ad hoc network, approximation algorithm, graph model, graph property, power conservation, topology control