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. A. Agarwal and P. R. Kumar, "Capacity bounds for ad hoc and hybrid wireless networks," Computer Communication Review, vol. 34, no. 3, pp. 71--81, 2004.]]
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. S. Toumpis, "Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid," in MobiHoc. ACM Press, 2004, pp. 133--144.]]
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. P. Kyasanur and N. H. Vaidya, "Capacity of multi-channel wireless networks: impact of number of channels and interfaces," in MobiCom, 2005, pp. 43--57.]]
14. S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu, "The broadcast storm problem in a mobile ad hoc network," in MobiCom. ACM Press, 1999, pp. 151--162.]]
15. B. Williams and T. Camp, "Comparison of broadcasting techniques for mobile ad hoc networks," in MobiHoc. ACM Press, 2002, pp. 194--205.]]
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, and R. R. Müller, "On the transport capacity of gaussian multiple access and broadcast channels," in WiOpt, 2005, pp. 10--20.]]
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. S. Basagni, "Distributed clustering for ad hoc networks," in ISPAN. IEEE Computer Society, 1999, p. 310.]]
32. K. Alzoubi, P.-J. Wan, and O. Frieder, "Message-optimal connected dominating sets in mobile ad hoc networks," in MobiHoc. ACM Press, 2002, pp. 157--164.]]
33. W. Lou and J. Wu, "A cluster-based backbone infrastructure for broadcasting in manets," in IPDPS. IEEE Computer Society, 2003, p. 221.1.]]
34. P.-J. Wan, K. Alzoubi, and O. Frieder, "Distributed construction of connected dominating set in wireless ad hoc networks," Mob. Netw. Appl., vol. 9, no. 2, pp. 141--149, 2004.]]
35. J. Wu and F. Dai, "A distributed formation of a virtual backbone in manets using adjustable transmission ranges," in ICDCS. IEEE Computer Society, 2004, pp. 372--379.]]
36. G. Calinescu, I. I. Mandoiu, P.-J. Wan, and A. Z. Zelikovsky, "Selecting forwarding neighbors in wireless ad hoc networks," Mob. Netw. Appl., vol. 9, no. 2, pp. 101--111, 2004.]]
37. A. Keshavarz-Haddad, V. Ribeiro, and R. Riedi, "Color-based broadcasting for ad hoc networks," in WiOpt, 2006.]]

Index Terms

• Computer systems organization

• Security and privacy

  • Cryptography

    • Mathematical foundations of cryptography

• Theory of computation

  • Computational complexity and cryptography

    • Communication complexity