Multicast capacity for multi-hop multi-channel multi-radio wireless networks

ABSTRACT

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). Each node is equipped with Φ interfaces. There are C = ∅(min(nr²=a² log n)) channels of equal bandwidth W/C available. We consider a random (C g) channel assignment where each node may switch between a preassigned random subset of g channels (with g ≥ ∅Φ). In this paper, we study the multicast capacity of such a random wireless network, where 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. We derive matching asymptotic upper bounds and lower bounds on multicast capacity. We show that the per-flow multicast capacity is Θ(W√P_rnd/n log n ⋅ 1/√k) when k = ∅(P_rnd⋅n/log n), where P_rnd denotes the probability that two nodes share at least one channel. Our bounds unify the previous capacity bounds on unicast (when k = 2) by Bhandari and Vaidya [3] for multi-channel multi-radio networks.

REFERENCES

• 1: Alicherry, M., Bhatia, R., and Li, L. E. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In MobiCom '05 pp. 58--72.
• 2: Alzoubi, K., Li, X.-Y., Wang, Y., Wan, P.-J., and Frieder, O. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Processing 14, 4 (2003), 408--421.
• 3: Bhandari, V., and Vaidya, N. H. Capacity of multi-channel wireless networks with random (c, f) assignment. In MobiHoc '07 pp. 229--238.
• 4: Grossglauser, M., and Tse, D. Mobility increases the capacity of ad-hoc wireless networks. In IEEE INFOCOMM (2001), vol. 3, pp. 1360--1369.
• 5: Gupta, P., and Kumar, P. Capacity of wireless networks. IEEE Transactions on Information Theory , vol. IT-46, no.2, pp.388--404, March 2000
• 6: Jacquet, P., and Rodolakis, G. Multicast scaling properties in massively dense ad hoc networks. In ICPADS '05, pp. 93--99.
• 7: Keshavarz-Haddad, A., Ribeiro, V., and Riedi, R. Broadcast capacity in multihop wireless networks. In MobiCom '06, pp. 239--250.
• 8: Keshavarz-Haddad, A., and Riedi, R. On the broadcast capacity of multihop wireless networks: Interplay of power, density and interference. In IEEE SECON (2007).
• 9: Kodialam, M., and Nandagopal, T. Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem. In MobiCom '03, pp. 42--54.
• 10: Kyasanur, P., and Vaidya, N. H. Capacity of multi-channel wireless networks: impact of number of channels and interfaces. In MobiCom '05, pp. 43--57.
• 11: Li, J., Blake, C., Couto, D. S. J. D., Lee, H. I., and Morris, R. Capacity of ad hoc wireless networks. In ACM MobiCom (2001).
• 12: Li, X.-Y., Tang, S.-J., and Ophir, F. Multicast capacity for large scale wireless ad hoc networks. In ACM Mobicom (2007).
• 13: Shakkottai, S., Liu, X., and Srikant, R. The multicast capacity of ad hoc networks. In Proc. ACM Mobihoc (2007).
• 14: Steele, J. M. Growth rates of euclidean minimal spanning trees with power weighted edges. The Annals of Probability 16, 4 (Oct 1988), 1767--1787.
• 15: Tavli, B. Broadcast capacity of wireless networks. IEEE Communication Letters 10, 2 (February 2006).
• 16: X.-Y. Li. Multicast Capacity for Large Scale Wireless AdHoc Networks. In Technical Report.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

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

General Terms:
Algorithms, Design, Theory

Keywords:
capacity, multicast, multichannel, wireless ad hoc networks