Multicast time maximization in energy constrained wireless networks

ABSTRACT

We consider the problem of maximizing the lifetime of a given multicast connection in a wireless network of energy-constrained (e.g. battery-operated) nodes, by choosing ideal transmission power levels for the nodes relaying the connection. We distinguish between two basic operating modes: In a static assignment, the power levels of the nodes are set at the beginning and remain unchanged until the nodes are depleted of energy. In a dynamic assignment, the powers can be adjusted during operation.We show that lifetime-maximizing static power assignments can be found in polynomial time, whereas for dynamic assignments, a quantized-time version of the problem is NP-hard. We then study the approximability of the quantized dynamic case and conclude that no polynomial time approximation scheme (PTAS) exists for the problem unless Ptime = NP. Finally, by considering two approximation heuristics for the dynamic case, we show experimentally that the lifetime of a dynamically maintained multicast connection can be made several times longer than what can be achieved by the best possible static assignment.

REFERENCES

• 1: M. Adler and C. Scheideler, "Efficient communication strategies for ad hoc wireless networks." Theory Comput. Systems 33 (2000), 337--391.
• 2: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 3: D. Bienstock and A. Bley, Capacitated Network Design with Multicast Commodities. Technical Report ZIB-Report 00-14, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000.
• 4: B. Bollobás, Modern Graph Theory. Springer-Verlag, New York NY, 1998.
• 5: Mario Ζagalj , Jean-Pierre Hubaux , Christian Enz, Minimum-energy broadcast in all-wireless networks:: NP-completeness and distribution issues, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570667]
• 6: Ioannis Caragiannis , Christos Kaklamanis , Panagiotis Kanellopoulos, A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem, Information Processing Letters, v.86 n.3, p.149-154, 16 May 2003 [doi>10.1016/S0020-0190(02)00484-2]
• 7: J.-H. Chang and L. Tassiulas, "Energy conserving routing in wireless ad-hoc networks." Proc. INFOCOM'00, 22--31. IEEE, New York NY, 2000.
• 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: A. K. Das, R. J. Marks, M. El-Sharkawi, P. Arabshahi and A. Gray, "Minimum power broadcast trees for wireless networks: integer programming formulations." Proc. INFOCOM'03. IEEE, New York NY, 2003.
• 10: A. Ephremides, "Energy concerns in wireless networks." IEEE Wireless Communications, August 2002, 48--59.
• 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: IEEE Wireless Communications, Special issue on energy-aware ad hoc wireless networks, August 2002.
• 13: Kamal Jain , Mohammad Mahdian , Mohammad R. Salavatipour, Packing Steiner trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: 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]
• 15: Qun Li , Javed Aslam , Daniela Rus, Online power-aware routing in wireless Ad-hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.97-107, July 2001, Rome, Italy [doi>10.1145/381677.381687]
• 16: 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]
• 17: 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]
• 18: R. J. Marks II, A. K. Das, M. El-Sharkawi, P. Arabshahi and A. Gray, "Maximizing lifetime in an energy constrained wireless sensor array using team optimization of cooperating systems." Proc. IEEE World Conference on Computational Intelligence 2002. IEEE, New York NY, 2002.
• 19: R. J. Marks II, A. K. Das, M. El-Sharkawi, P. Arabshahi and A. Gray, "Minimum power broadcast trees for wireless networks: optimizing using the viability lemma." Proc. IEEE Int. Symp. in Circuits and Systems 2002, I:273--276. IEEE, New York NY, 2002.
• 20: I. Papadimitriou and L. Georgiadis, "Energy-aware broadcasting in wireless networks." Proc. WiOPT'03, 267--277. INRIA Sophia-Antipolis, 2003.
• 21: Charles E. Perkins, Ad hoc networking: an introduction, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 22: H. J. Prömel and A. Steger, The Steiner Tree Problem. Vieweg, Braunschweig, 2002.
• 23: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 24: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment." Proc. INFOCOM'00, 404--413.IEEE, New York NY, 2000.
• 25: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 26: V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless networks." IEEE J. Selected Areas in Communications 17 (1999), 1333--1344.
• 27: Suresh Singh , Mike Woo , C. S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.181-190, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288286]
• 28: P. J. Wan , G. Călinescu , X. Y. Li , O. Frieder, Minimum-energy broadcasting in static ad hoc wireless networks, Wireless Networks, v.8 n.6, p.607-617, November 2002 [doi>10.1023/A:1020381720601]
• 29: J. E. Wieselthier, G. D. Nguyen and A. Ephremides, "On the construction of energy-efficient broadcast and multicast trees in wireless networks." Proc. INFOCOM'00, 585--594. IEEE, New York NY, 2000.
• 30: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Algorithms for energy-efficient multicasting in static ad hoc wireless networks, Mobile Networks and Applications, v.6 n.3, p.251-263, June 2001 [doi>10.1023/A:1011478717164]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

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

General Terms:
Algorithms, Performance, Theory

Keywords:
Steiner tree packing, energy saving, multi-hop packet networks, multicasting, optimization, sensor networks, wireless networks