Broadcast capacity in multihop wireless networks

ABSTRACT

In this paper we study the broadcast capacity of multihop wireless networks which we define as the maximum rate at which broadcast packets can be generated in the network such that all nodes receive the packets successfully in a limited time. We employ the Protocol Model for successful packet reception usually adopted in network capacity studies and provide novel upper and lower bounds for the broadcast capacity for arbitrary connected networks. In a homogeneous dense network these bounds simplify to Θ(W/max(1,Δ^d)) where W is the wireless channel capacity, Δ the interference parameter, and d the number of dimensions of space in which the network lies. Interestingly, we show that the broadcast capacity does not change by more than a constant factor when we vary the number of nodes, the radio range, the area of the network, and even the node mobility. To address the achievability of capacity, we demonstrate that any broadcast scheme based on a backbone of size proportional to the Minimum Connected Dominating Set guarantees a throughput within a constant factor of the broadcast capacity. Finally, we demonstrate that broadcast capacity, in stark contrast to unicast capacity, does not depend on the choice of source nodes or the dimension of the network.

REFERENCES

• 1: X. Hong, K. Xu, and M. Gerla, "Scalable routing protocols for mobile ad hoc networks," IEEE Network, vol. 16, pp. 11--21, 2002.
• 2: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, 2000.
• 3: Ashish Agarwal , P. R. Kumar, Capacity bounds for ad hoc and hybrid wireless networks, ACM SIGCOMM Computer Communication Review, v.34 n.3, July 2004 [doi>10.1145/1031134.1031143]
• 4: M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "On the throughput capacity of random wireless networks," IEEE Transactions on Information Theory, 2004.
• 5: M. Grossglauser and D. N. C. Tse, "Mobility increases the capacity of ad-hoc wireless networks," in INFOCOM, 2001, pp. 1360--1369.
• 6: R. Negi and A. Rajeswaran, "Capacity of power constrained ad-hoc networks," in INFOCOM, 2004.
• 7: S. Toumpis and A. J. Goldsmith, "Large wireless networks under fading, mobility, and delay constraints," in INFOCOM, 2004.
• 8: B. Liu, Z. Liu, and D. F. Towsley, "On the capacity of hybrid wireless networks," in INFOCOM, 2003.
• 9: Stavros Toumpis, Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid, 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.989477]
• 10: R. Zheng, "Information dissemination in power-constrained wireless network," in INFOCOM, 2006.
• 11: P. Gupta and P. Kumar, "Internets in the sky: The capacity of three dimensional wireless networks," Communications in Information and Systems, vol. 1, no. 1, pp. 33--50, 2001.
• 12: S. R. Kulkarni and P. Viswanath, "A deterministic approach to throughput scaling in wireless networks," IEEE Transactions on Information Theory, vol. 50, no. 6, pp. 1041--1049, 2004.
• 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: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 15: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile 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.513825]
• 16: W. Lou and J. Wu, Localized Broadcasting in Mobile Ad Hoc Networks Using Neighbor Designation. in Mobile Computing Handbook, CRC Press, 2005, ch. 28.
• 17: I. Stojmenovic and J. Wu, Mobile Ad Hoc Networking. IEEE Press, 2004, ch. 7, pp. 20--230.
• 18: G. Grimmett, Percolation. Second edition, Springer Verlag, 1999.
• 19: G. Sharma, R. R. Mazumdar, and N. B. Shroff, "Delay and capacity trade-offs in mobile ad hoc networks: A global perspective," in INFOCOM, 2006.
• 20: M. J. Neely and E. Modiano, "Capacity and delay tradeoffs for ad hoc mobile networks," IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917--1937, 2005.
• 21: S. N. Diggavi, M. Grossglauser, and D. N. C. Tse, "Even one-dimensional mobility increases the capacity of wireless networks," IEEE Transactions on Information Theory, vol. 51, no. 11, pp. 3947--3954, 2005.
• 22: X. Lin and N. Shroff, "Towards achieving the maximum capacity in large mobile wireless networks. under delay constraints," Journal of Communications and Networks, vol. 6, no. 4, p. 352--361, 2004.
• 23: G. Sharma and R. Mazumdar, "On achievable delay/capacity trade-offs in mobile ad hoc networks," in WiOpt, 2004.
• 24: A. E. Gamal, J. P. Mammen, B. Prabhakar, and D. Shah, "Throughput-delay trade-off in wireless networks," in INFOCOM, 2004.
• 25: N. Bansal and Z. Liu, "Capacity, delay and mobility in wireless ad-hoc networks," in INFOCOM, 2003.
• 26: P. Gupta and P. R. Kumar, "Towards an information theory of large networks: an achievable rate region," IEEE Transactions on Information Theory, vol. 49, no. 8, pp. 1877--1894, 2003.
• 27: M. Gastpar and M. Vetterli, "On the capacity of wireless networks: The relay case," in INFOCOM, 2002.
• 28: G. A. Gupta , S. Toumpis , J. Sayir , R. R. Muller, On the Transport Capacity of Gaussian Multiple Access and Broadcast Channels, Proceedings of the Third International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, p.10-20, April 04-06, 2005 [doi>10.1109/WIOPT.2005.35]
• 29: R. B. Ellis, J. L. Martin, and C. Yan, "Random geometric graph diameter in the unit ball," to appear Algorithmica, 2005.
• 30: C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE Journal on Selected Areas in Communications, vol. 15, no. 7, pp. 1265--1275, 1997.
• 31: Stefano Basagni, Distributed Clustering for Ad Hoc Networks, Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), p.310, June 23-25, 1999
• 32: Khaled M. Alzoubi , Peng-Jun Wan , Ophir Frieder, Message-optimal connected dominating sets in mobile 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.513820]
• 33: Wei Lou , Jie Wu, A Cluster-Based Backbone Infrastructure for Broadcasting in MANETs, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.221.1, April 22-26, 2003
• 34: Peng-Jun Wan , Khaled M. Alzoubi , Ophir Frieder, Distributed construction of connected dominating set in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.141-149, April 2004 [doi>10.1023/B:MONE.0000013625.87793.13]
• 35: Jie Wu , Fei Dai, A Distributed Formation of a Virtual Backbone in MANETs Using Adjustable Transmission Ranges, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.372-379, March 24-26, 2004
• 36: Gruia Călinescu , Ion I. Mandoiu , Peng-Jun Wan , Alexander Z. Zelikovsky, Selecting forwarding neighbors in wireless ad hoc networks, Mobile Networks and Applications, v.9 n.2, p.101-111, April 2004 [doi>10.1023/B:MONE.0000013622.63511.57]
• 37: A. Keshavarz-Haddad, V. Ribeiro, and R. Riedi, "Color-based broadcasting for ad hoc networks," in WiOpt, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

General Terms:
Performance, Theory

Keywords:
ad hoc networks, broadcast capacity, broadcast scheme, multihop wireless networks, unicast capacity