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 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 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 developed. 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: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 2: 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
• 3: 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
• 4: {4} G. Calinescu and P.-J. Wan, Symmetric high connectivity with minimum total power consumption in multihop packet radio networks, in: Proc. of the Internat. Conf. on Ad Hoc and Wireless Networks (ADHOC-NOW'03), eds. S. Pierre, M. Barbeau and E. Kranakis, Montreal, Canada (October 2003) Lecture Notes in Computer Science, Vol. 2865 (Springer, New York, 2003) pp. 235-246.
• 5: {5} W. Chen and N. Huang, The strongly connecting problem on multihop packet radio networks, IEEE Trans. Commun. 37(3) (1989) 293-295.
• 6: Xiuzhen Cheng , Bhagirath Narahari , Rahul Simha , Maggie Xiaoyan Cheng , Dan Liu, Strong Minimum Energy Topology in Wireless Sensor Networks: NP-Completeness and Heuristics, IEEE Transactions on Mobile Computing, v.2 n.3, p.248-256, March 2003 [doi>10.1109/TMC.2003.1233530]
• 7: 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
• 8: 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
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: {10} G.A. Dirac, Minimally 2-connected graphs, J. Reine Angewandte Math. 228 (1967) 204-216.
• 11: 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
• 12: 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]
• 13: {13} L. Hu, Topology control for multi-hop packet radio networks, IEEE Trans. Commun. 41(10) (1993) 1474-1481.
• 14: 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 ]
• 15: 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]
• 16: 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
• 17: {17} S.O. Krumke, R. Liu, E.L. Lloyd, M.V. Marathe, R. Ramanathan and S.S. Ravi, Topology control problems under symmetric and asymmetric power thresholds, in: Proc. of the Internat. Conf. on Ad Hoc and Wireless Networks (ADHOC-NOW'03), eds. S. Pierre, M. Barbeau and E. Kranakis, Montreal, Canada (October 2003), Lecture Notes in Computer Science, Vol. 2865 (Springer, New York, 2000) pp. 187-198.
• 18: {18} M. Kubisch, H. Karl, A. Wolisz, L. Zhong and J. Rabaey, Distributed algorithms for transmission power control in wireless sensor networks, in: Proc. of the IEEE Wireless Communications and Networking Conference (WCNC 2003), New Orleans, LA (March 2003) pp. 558-563.
• 19: {19} L. Li and J.Y. Halpern, Minimum energy mobile wireless networks revisited, in: Proc. of the IEEE Conf. on Communications (ICC'01) (June 2001) pp. 278-283.
• 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: {21} M.D. Plummer, On minimal blocks, Trans. AMS 134 (October-December 1968) 85-94.
• 22: {22} V. Radoplu and T.H. Meng, Minimum energy mobile wireless networks, IEEE J. Selected Areas Commun. 17(8) (1999) 1333-1344.
• 23: {23} R. Ramanathan and R. Rosales-Hain, Topology control of multihop wireless networks using transmit power adjustment, in: Proc. of the IEEE INFOCOM 2000, Tel Aviv, Israel (March 2000) pp. 404-413.
• 24: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 25: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 26: {26} E.M. Royer, P. Melliar-Smith and L. Moser, An analysis of the optimum node density for ad hoc mobile networks, in: Proc. of the IEEE Internat. Conf. on Communication (ICC'01), Helsinki, Finland (June 2001) pp. 857-861.
• 27: 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]
• 28: {28} H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Trans. Commun. 32(3) (1984) 246-257; also see in: Multiple Access Communications, Foundations for Emerging Technologies, ed. N. Abramson (IEEE Press, New York, 1992) pp. 342-353.
• 29: {29} TRANSIMS, http://transims.tsasa.lanl.gov/.
• 30: J. van Leeuwen, Graph algorithms, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 31: {31} R. Wattenhofer, L. Li, P. Bahl and Y. Wang, Distributed topology control for power efficient operation in multihop wireless ad hoc networks, in: Proc. of the IEEE INFOCOM 2001, Anchorage, Alaska (April 2001) pp. 1388-1397.
• 32: {32} D.B. West, Introduction to Graph Theory (Prentice-Hall, Englewood Cliffs, NJ, 1996).

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Adaptable architectures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance

Keywords:
approximation algorithms, power control, topology