A scalable distributed multicast algorithm for lifetime maximization in large-scale resource-limited multihop wireless networks

ABSTRACT

We consider the problem of maximizing the multicast lifetime in multihop wireless networks in which each node is static and has limited energy, bandwidth, memory, and computation capabilities. Unlike most multicast algorithms that use centralized greedy algorithms, our algorithm can construct a global optimal maximum lifetime multicast tree in a distributed manner. It has a low complexity of O(λ_u) for both memory and computation requirements at each node u, where λ_u is the degree of node u. The simulation results have shown that it has an expected linear communication complexity under different network sizes and multicast group sizes. This means that our distributed algorithm is also scalable in terms of communication overhead and it is very useful for large-scale energy and bandwidth constrained multihop wireless networks like sensor networks.

REFERENCES

• 1: J. E. Wieselthier, G. D. Nguyen, et al, "On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks", IEEE INFOCOM, 2000, pp.585 -- 594.
• 2: S. Guo and O. Yang, "A Dynamic Multicast Tree Reconstruction Algorithm for Minimum-Energy Multicasting in Wireless Ad Hoc Networks", IEEE IPCCC, Phoenix, USA April 2004, pp. 637 -- 642.
• 3: Fulu Li , Ioanis Nikolaidis, On Minimum-Energy Broadcasting in All-Wireless Networks, Proceedings of the 26th Annual IEEE Conference on Local Computer Networks, p.193, November 14-16, 2001
• 4: J. Cartigny, D. Simplot, and I. Stojmenovic, "Localized minimum-energy broadcasting in ad-hoc networks", IEEE INFOCOM, April 2003, pp. 2210 -- 2217.
• 5: P. J. Wan, G. Calinescu, and et al, "Minimum-energy broadcast routing in static ad hoc wireless networks", IEEE INFOCOM, Anchorage, Alaska, April 2001, pp. 1162 -- 1171.
• 6: Peng-Jun Wan , Gruia Călinescu , Chih-Wei Yi, Minimum-power multicast routing in static ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.507-514, June 2004 [doi>10.1109/TNET.2004.828940]
• 7: 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]
• 8: 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]
• 9: I. Kang and R. Poovendran, "Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks", IEEE ICC, Alaska, May 2003, pp. 2256 -- 2261.
• 10: M. X. Cheng, J. Sun, and et al, "Energy-efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks", IEEE IPCCC, Phoenix, Arizona, April 2003, pp.87 -- 94.
• 11: B. Wang and S. K. S. Gupta, "On Maximizing Lifetime of Multicast Trees in Wireless Ad hoc Networks", International Conference on Parallel Processing, Kaohsiung, Taiwan, October 2003, pp. 333 -- 340.
• 12: Patrik Floréen , Petteri Kaski , Jukka Kohonen , Pekka Orponen, Multicast time maximization in energy constrained wireless networks, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.50-58, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941087]
• 13: A. K. Das, R. J. Marks II, M.A. El-Sharkawi, P. Arabshahi and A. Gray, "MDLT: a polynomial time optimal algorithm for maximization of time-to-first-failure in energy-constrained broadcast wireless networks", IEEE Globecom, San Francisco, CA, December 2003, pp. 362 -- 366.
• 14: S. Guo and O. Yang, "Multicast Lifetime Maximization for Energy-Constrained Wireless Ad-hoc Networks with Directional Antennas", IEEE Globecom, Dallas, USA, December 2004, pp. 4120 -- 4124.
• 15: L. Georgiadis, "Bottleneck multicast trees in linear time", IEEE Communications Letters, 7(11), Nov. 2003, pp. 564 -- 566.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
distributed algorithm, maximum lifetime multicast, multihop wireless networkoc