Performance of distributed algorithms for maximizing multicast lifetime in mobile ad hoc networks

ABSTRACT

We consider the problem of maximizing the lifetime of a given multicast connection in mobile ad hoc networks that use omni-directional antennas and have limited energy resources. We present two distributed multicast algorithms BEEM and DMLM for this problem. In our distributed algorithms, each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes. The extensive simulation results have shown that our DMLM algorithm is very efficient in terms of multicast lifetime.

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, March 2000, pp.585--594.
• 2: Song Guo and Oliver 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: P.-J. Wan, G. Calinsecu, X.-Y. Li, and O. Frieder, "Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless Networks", IEEE INFOCOM, April 2001, pp. 1162--1171.
• 7: 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]
• 8: 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]
• 9: 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]
• 10: Intae Kang and Radha Poovendran, "Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks", IEEE ICC, Alaska, May 2003, pp. 2256--2261.
• 11: 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.
• 12: Bin Wang and Sandeep 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.
• 13: 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]
• 14: 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.
• 15: Song Guo and Oliver Yang, "Multicast Lifetime Maximization for Energy-Constrained Wireless Ad-hoc Networks with Directional Antennas", IEEE Globecom, Dallas, USA, December 2004, pp. 4120--4124.
• 16: D.B. Johnson and D.A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," Mobile Computing, T. Imielinski and H. Korth, eds. Kluwer Academic, 1996, pp. 153--181.
• 17: Jungkeun Yoon, Mingyan Liu, and Brian Noble, "Random Waypoint Considered Harmful", IEEE INFOCOM 2003, pp. 1312--1321.

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 algorithms, maximum lifetime multicast, mobile ad hoc network