Approximation algorithms for longest-lived directional multicast communications in WANETs

ABSTRACT

Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.

REFERENCES

• 1: I. Kang and R. Poovendran, "On the Lifetime Extension of Energy-Efficient Multihop Broadcast Networks", World Congress on Computational Intelligence, Honolulu, 2002.
• 2: I. Kang and R. Poovendran, "Maximizing Static Network Lifetime of Wireless Broadcast Adhoc Networks", in Proc. IEEE ICC, Alaska, 2003, pp. 2256--2261.
• 3: A. K. Das, R. J. Marks II, et al, "MDLT: a polynomial time optimal algorithm for maximization of time-to-first-failure in energy-constrained broadcast wireless networks", IEEE Globecom, 2003, pp. 362 -- 366.
• 4: M. X. Cheng, J. Sun, and et al, "Energy-efficient Broadcast and Multicast Routing in Ad Hoc Wireless Networks", IEEE IPCCC, 2003, pp.87 -- 94.
• 5: B. Wang and S. K. S. Gupta, "On Maximizing Lifetime of Multicast Trees in Wireless Ad hoc Networks", ICPP, 2003, pp. 333 -- 340.
• 6: 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]
• 7: L. Georgiadis, "Bottleneck multicast trees in linear time", IEEE Communications Letters, 7(11), Nov. 2003, pp. 564 -- 566.
• 8: Song Guo , Victor Leung , Oliver Yang, A scalable distributed multicast algorithm for lifetime maximization in large-scale resource-limited multihop wireless networks, Proceedings of the 2006 international conference on Wireless communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada [doi>10.1145/1143549.1143633]
• 9: J. E. Wieselthier, G. D. Nguyen, et al, "Energy-Limited Wireless Networking with Directional Antennas: The Case of Session-Based Multicasting", IEEE INFOCOM, 2002, pp. 190--199.
• 10: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting, IEEE Transactions on Mobile Computing, v.1 n.3, p.176-191, July 2002 [doi>10.1109/TMC.2002.1081754]
• 11: 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.
• 12: S. Guo, V. Leung and O. Yang, "Distributed Multicast Algorithms for Lifetime Maximization in Wireless Ad Hoc Networks with Omni-directional and Directional Antennas", IEEE Globecom, 2006.
• 13: Y. Hou, Y. Shi, H. D. Sherali, and J. E. Wieselthier, "Online lifetime-centric multicast routing for ad hoc networks with directional antennas", IEEE INFOCOM, 2005, pp. 761 -- 772.
• 14: S. Guo and O. Yang, "Optimal Tree Construction for Maximum Lifetime Multicasting in Wireless Ad-hoc Networks with Adaptive Antennas", IEEE ICC, 2005, pp. 3370 -- 3374.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
approximation algorithm, directional antenna, maximum-lifetime routing, multicast tree, wireless ad hoc networks