Algorithmic aspects of topology control problems for ad hoc networks

ABSTRACT

Topology control problems are concerned with the assignment of power values to the nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. This paper considers such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. A general approach leading to a polynomial algorithm is presented for minimizing maximum power for a class of graph properties called textbf monotone properties. The difficulty of generalizing the approach to properties that are not monotone is discussed. Problems involving the minimization of total power are known to be bf NP -complete even for simple graph properties. A general approach that leads to an approximation algorithm for minimizing the total power for some monotone properties is presented. Using this approach, a new approximation algorithm for the problem of minimizing the total power for obtaining a 2-node-connected graph is obtained. It is shown that this algorithm provides a constant performance guarantee. Experimental results from an implementation of the approximation algorithm are also presented.

REFERENCES

• 1: W. Chen and N. Huang. "The Strongly Connecting Problem on Multihop Packet Radio Networks", IEEE Trans. Communication, Vol. 37, No. 3, Mar. 1989.
• 2: 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
• 3: Andrea E. F. Clementi , Paolo Penna , Riccardo Silvestri, The Power Range Assignment Problem in Radio Networks on the Plane, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.651-660, February 01, 2000
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: G. A. Dirac. "Minimally 2-Connected Graphs", J. für Reine und Angewandte Mathematik, Vol. 228, 1967, pp. 204--216.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: L. Hu. "Topology Control for Multi-hop Packet Radio Networks", IEEE. Trans. Communications, 41(10), 1993, pp. 1474--1481.
• 8: S. Khuller and B. Raghavachari. "Improved Approximation Algorithms for Uniform Connectivity
• 9: Samir Khuller , Uzi Vishkin, Biconnectivity approximations and graph carvings, Journal of the ACM (JACM), v.41 n.2, p.214-235, March 1994 [doi>10.1145/174652.174654]
• 10: Lefteris M. Kirousis , Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Power Consumption in Packet Radio Networks (Extended Abstract), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, p.363-374, February 27-March 01, 1997
• 11: L. Li and J. Y. Halpern, "Minimum Energy Mobile Wireless Networks Revisited", Proc. IEEE Conference on Communications (ICC'01), June 2001, pp. 278--283.
• 12: 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]
• 13: M. D. Plummer. "On Minimal Blocks", Trans. AMS, Vol. 134, Oct.-Dec. 1968, pp. 85--94.
• 14: V. Radoplu and T. H. Meng. "Minimum Energy Mobile Wireless Networks", IEEE J. Selected Areas in Communications, 17(8), Aug. 1999, pp. 1333--1344.
• 15: R. Ramanathan and R. Rosales-Hain. "Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment", Proc. IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000, pp. 404--413.
• 16: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 17: R. Ravi and D. P. Williamson, "An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems", Algorithmica, 18: 21--43, 1997.
• 18: E. M. Royer, P. Melliar-Smith and L. Moser, "An Analysis of the Optimum Node Density for Ad hoc Mobile Networks", Proc. IEEE Intl. Conf. on Communication (ICC'01), Helsinki, Finland, June 2001.
• 19: Elizabeth M. Belding-Royer , Charles E. Perkins, Transmission range effects on AODV multicast communication, Mobile Networks and Applications, v.7 n.6, p.455-470, December 2002 [doi>10.1023/A:1020708701096]
• 20: H. Takagi, and L. Kleinrock. "Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals", IEEE Transactions on Communications, Vol. COM-32, No. 3, pp. 246--257, March 1984. Also appears in Multiple Access Communications, Foundations for Emerging Technologies, Norman Abramson (Ed.), IEEE Press, pp.342--353, 1992.
• 21: J. van Leeuwen, Graph algorithms, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 22: R. Wattenhofer, L. Li, P. Bahl and Y. Wang. "Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks", Proc. IEEE INFOCOM 2001, Anchorage, Alaska, April 2001, pp. 1388--1397.
• 23: D. B. West. Introduction to Graph Theory , Prentice-Hall, Inc., Englewood Cliffs, NJ, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

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

General Terms:
Algorithms, Design, Experimentation

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