Characterizing achievable multicast rates in multi-hop wireless networks

ABSTRACT

In this paper, we consider the multicast throughput optimization problem in multi-hop wireless networks. Given a source, and a set of receivers, we would like to find the set of multicast trees and a schedule such that the rate that the source can multicast to the receivers is maximized. We consider two transmission models: broadcast and unicast. In the broadcast model, a transmission is received by multiple downstream nodes in a multicast tree. In the unicast model, a separate transmission has to be sent to each downstream node. We consider the fundamental constraint that a node can not be involved in multiple communications at the same time. We consider two multicast models: a single multicast tree per session and multiple multicast tree per session. In the single multicast tree case, (1) for the unicast model, we show that the problem is NP-hard and it is not approximable to a factor better than 1.5; we then give a 1.5-approximation algorithm if all links have the same data rate, a 5-approximation algorithm if all nodes have the same transmission power and a 24-approximation algorithm for a realistic heterogeneous ad hoc network where nodes can have different transmission power. (2) for the broadcast model, we show that the problem is NP-hard and it is not approximable to a factor better than 2; we then give a simple 2-approximation algorithm to find the multicast tree and the transmission schedule. In the multiple multicast tree case, (1) for the unicast model, we show that the problem is APX-hard, and give a 1.5Ρ-approximation where Ρ is the best approximation ratio of the minimal cost Steiner tree problem; (2) for the broadcast model, our results indicate that the problem is hard, may not be approximable within a factor better than log(n) where n is the number of multicast receivers. Our evaluation shows that the throughput achieved by our algorithms is much better than both the throughput achieved by using pruned shortest path tree and by using optimal unicast.

REFERENCES

• 1: D. Baker, J. Wieselthier, and A. Ephremides. A distributed algorithm for scheduling the activation of links in a self-organizing mobile radio networks. In Proceedings of IEEE Int. Conference Communications, pages 2F6.1--2F6.5, 1982.
• 2: R. Bhatia and M. Kodialam. On power efficient communication over multi-hop wireless networks: Joint routing, scheduling and power control. In Proceeding of IEEE INFOCOM, 2004.
• 3: E. Bommaiah, M. Liu, A. McAuley, and R. Talpade. AMRoute: Ad hoc Multicast Routing protocol. Internet Draft, draft-talpade-manet-amroute-00.txt, 1998.
• 4: Robert Carr , Santosh Vempala, Randomized metarounding (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.58-62, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335312]
• 5: Miguel Castro , Peter Druschel , Anne-Marie Kermarrec , Animesh Nandi , Antony Rowstron , Atul Singh, SplitStream: high-bandwidth multicast in cooperative environments, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 6: Prasanna Chaporkar , Anita Bhat , Saswati Sarkar, An adaptive strategy for maximizing throughput in MAC layer wireless multicast, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989491]
• 7: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 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: M. Scott Corson , Stephen G. Batsell, A preservation-based multicast (RBM) routing protocol for mobile networks: initial route construction phase, Wireless Networks, v.1 n.4, p.427-450, 1995 [doi>10.1007/BF01985755]
• 10: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 11: T. ElBatt and A. Ephremides. Joint scheduling and power control for wireless ad-hoc networks. In Proceedings of IEEE INFOCOM, 2002.
• 12: Martin Fürer , Balaji Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, selected papers from the third annual ACM-SIAM symposium on Discrete algorithms, p.409-423, November 1994, Orlando, Florida, United States
• 13: J. J. Garcia-Luna-Aceves and E. L. Madruga. Multicast routing protocol for ad-hoc networks. In Proceedings of IEEE INFOCOM, 1999.
• 14: 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
• 15: N. Garg, R. Khandekar, K. Kunal, and V. Pandit. Bandwidth maximization in multicasting. In Proceedings of European Symposium on Algorithms (ESA), pages 242--253, 2003.
• 16: Z. Gaspar and T. Tarnai. Upper bound of density for packing of equal circles in special domains in the plane. Per. Pol. Civil Eng., 44(1):13--32, 2000.
• 17: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, IT-46(2):388--404, Mar. 2000.
• 18: B. Hajek and G. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory, 34(5):910--917, 1988.
• 19: A. Itai, C. H. Papadimitriou, and J. Szwarcfiter. Hamilton paths in grid graphs. SIAM J. Comput., 1(4):676--686, 1982.
• 20: 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
• 21: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 22: L. Khachian. A polynomial algorithm in linear programming. Soviet Math. Dokl., 20:191--194, 1979.
• 23: Murali Kodialam , Thyaga Nandagopal, Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938991]
• 24: D. Konig. Graphok es alkalmazasuk a determinansok es a halmazok elmeletere {hungarian}. Mathematikai es Termeszettudomanyi Ertesito, 34:104--119, 1916.
• 25: Sung Ju Lee , William Su , Mario Gerla, On-demand multicast routing protocol in multihop wireless mobile networks, Mobile Networks and Applications, v.7 n.6, p.441-453, December 2002 [doi>10.1023/A:1020756600187]
• 26: Jinyang Li , Charles Blake , Douglas S.J. De Couto , Hu Imm Lee , Robert Morris, Capacity of Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.61-69, July 2001, Rome, Italy [doi>10.1145/381677.381684]
• 27: 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]
• 28: C. L. Monma, M. Paterson, S. Suri, and F. F. Yao. Computing euclidean maximum spanning trees. Algorithmica, 5(3):407--419, 1990.
• 29: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 30: The 3rd Generation Partnership Project 2(3GPP2). roadcast/Multicast Services Stage 1 . 3GPP2 TS-3GB-S.R0030-0v1.0, 2003.
• 31: The 3rd Generation Partnership Project (3GPP). Multimedia Broadcast/Multicast Service (MBMS); Stage 2. 3GPP TR 23.846, 2003.
• 32: J. E. Wieselthier, G. D.Nguyen, and A. Ephremides. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. In Proceedings of IEEE INFOCOM, 2000.
• 33: 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]

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

General Terms:
Algorithms, Theory

Keywords:
combinatorics, graph theory, mathematical programming, optimization