Multicast capacity for large scale wireless ad hoc networks

ABSTRACT

In this paper, we study the capacity of a large-scale random wireless network for multicast.Assume that n wireless nodes are randomly deployed in a square region with side-length a and all nodes have the uniform transmission range r and uniform interference range R >r. We further assume that each wireless node can transmit/receive at W bits/second over a common wireless channel. For each node v_i, we randomly pick k-1 nodes from the other n-1 nodes as the receivers of the multicast session rooted at node v_i. The aggregated multicast capacity is defined as the total data rate of all multicast sessions in the network. In this paper we derive matching asymptotic upper bounds and lower bounds on multicast capacity of random wireless networks. We show that the total multicast capacity is Θ(√n over log n dot W over √ k) when k = Ω(n over log n); the total multicast capacity is Θ(W) when k =Θ(n over log n). Our bounds unify the previous capacity bounds on unicast (when k=2) by Gupta and Kumar [7]and the capacity bounds on broadcast (when k=n) in [11,20]. We also study the capacity of group-multicast for wireless networks where for each source node, we randomly select k-1 groups of nodes as receivers and the nodes in each group are within a constant hops from the group leader. The same asymptotic upper bounds and lower bounds still hold. For arbitrary networks, we provide a constructive lower bound Ω(√n over √k dot W) for aggregated multicast capacity when we can carefully place nodes and schedule node transmissions.

REFERENCES

• 1: Gahng-Seop Ahn , Se Gi Hong , Emiliano Miluzzo , Andrew T. Campbell , Francesca Cuomo, Funneling-MAC: a localized, sink-oriented MAC for boosting fidelity in sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182837]
• 2: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 3: Khaled Alzoubi , Xiang-Yang Li , Yu Wang , Peng-Jun Wan , Ophir Frieder, Geometric Spanners for Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.408-421, April 2003 [doi>10.1109/TPDS.2003.1195412]
• 4: DU, D.-Z., AND HWANG, F.-K. A Proof of the Gilbert-Pollak Conjecture on the Steiner Ratio Algorithmica, 7(2,3), pp. 121--135 (1992).
• 5: GASTPAR, M., AND VETTERLI, M. On the capacity of wireless networks: the relay case. In IEEE INFOCOM (2002).
• 6: GROSSGLAUSER, M., AND TSE, D. Mobility increases the capacity of ad-hoc wireless networks. In INFOCOMM (2001), vol. 3, pp. 1360--1369.
• 7: GUPTA, P., AND KUMAR, P. Capacity of wireless networks. IEEE Trans. on Information Theory, Volume 46, Issue 2, Mar 2000, Page(s):388--404.
• 8: GUPTA, P., AND KUMAR, P. R. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, W. M. McEneaney, G. Yin, and Q. Zhang (Eds.) (1998).
• 9: Philippe Jacquet , Georgios Rodolakis, Multicast Scaling Properties in Massively Dense Ad Hoc Networks, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops (ICPADS'05), p.93-99, July 20-22, 2005
• 10: KESHAVARZ-HADDAD, A. AND RIEDI R. On the Broadcast Capacity of Multihop Wireless Networks: Interplay of Power, Density and Interference, 4th IEEE SECON, June 2007.
• 11: Alireza Keshavarz-Haddad , Vinay Ribeiro , Rudolf Riedi, Broadcast capacity in multihop wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161117]
• 12: 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]
• 13: Pradeep Kyasanur , Nitin H. Vaidya, Capacity of multi-channel wireless networks: impact of number of channels and interfaces, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080835]
• 14: 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]
• 15: LIU, J. GOECKEL, D. TOWSLEY, D. Bounds on the Gain of Network Coding and Broadcasting in Wireless Networks IEEE INFOCOM 2007. May 2007, pages 724--732.
• 16: PENROSE, M. The longest edge of the random minimal spanning tree. Annals of Applied Probability 7 (1997), 340--361.
• 17: Paolo Santi , Douglas M. Blough, The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.2 n.1, p.25-39, January-March 2003 [doi>10.1109/TMC.2003.1195149]
• 18: Srinivas Shakkottai , Xin Liu , R. Srikant, The multicast capacity of large multihop wireless networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288141]
• 19: STEELE, J. M. Growth rates of Euclidean minimal spanning trees with power weighted edges. The Annals of Probability 16, 4 (Oct 1988), 1767--1787.
• 20: TAVLI, B. Broadcast capacity of wireless networks. IEEE Communication Letters 10, 2 (February 2006).
• 21: WAN, P.-J., ALZOUBI, K. M., AND FRIEDER, O. Distributed construction of connected dominating set in wireless ad hoc networks. In IEEE INFOCOM (2002).
• 22: WANG, Y., LI, X.-Y., AND FRIEDER O. Distributed Spanner with Bounded Degree for Wireless Ad Hoc Networks Int. Journal on Found. of Compt. Sci., Vol. 14, No. 2 (2003) Pages 183--200.
• 23: Weizhao Wang , Yu Wang , Xiang-Yang Li , Wen-Zhan Song , Ophir Frieder, Efficient interference-aware TDMA link scheduling for static wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161119]
• 24: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 25: ZHENG, R. Information dissemination in power-constrained wireless networks. In IEEE INFOCOM (2006).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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

General Terms:
Algorithms, Design, Theory

Keywords:
capacity, multicast, wireless ad hoc networks