Scalability of wireless networks

ABSTRACT

This paper investigates the existence of scalable protocols that can achieve the capacity limit of c/√N per source-destination pair in a large wireless network of N nodes when the buffer space of each node does not grow with the size of the network N. It is shown that there is no end-to-end protocol capable of carrying out the limiting throughput of c/√N with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of c/√N log N when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available.

REFERENCES

• 1: [1] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 2: [2] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Throughput-delay trade-off in wireless networks," in Proc. IEEE INFOCOM 2004, Hong Kong, Mar. 2004, pp. 464-475.
• 3: Abbas El Gamal , James Mammen , Balaji Prabhakar , Devavrat Shah, Optimal throughput-delay scaling in wireless networks: part I: the fluid model, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2568-2592, June 2006 [doi>10.1109/TIT.2006.874379]
• 4: [4] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Optimal throughput-delay scaling in wireless networks--Part II: Constant-size packets," IEEE Trans. Inf. Theory, vol. 52, no. 11, pp. 5111-5116, Nov. 2006.
• 5: [5] M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "On the throughput capacity of random wireless networks." Preprint.
• 6: [6] S. Kulkarni and P. Viswanath, "A deternimistic approach to throughput scaling in wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1041-1049, Jun. 2004.
• 7: [7] P. R. Kumar and L.-L. Xie, "A network information theory for wireless communications: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 748-767, May 2004.
• 8: [8] O. Leveque and E. Telatar, "Information theoretic upper bounds on the capacity of ad hoc networks," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 858-865, Mar. 2005.
• 9: [9] A. Jovičič, P. Viswanath, and S. Kulkarni, "Upper bounds to transport capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 11, pp. 2555-2565, Nov. 2004.
• 10: Guillermo Barrenechea , Baltasar Beferull-Lozano , Martin Vetterli, Lattice sensor networks: capacity limits, optimal routing and robustness to failures, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984650]
• 11: [11] R. M. Loynes, "The stability of a queue with non-independent inter-arrival and service times," Proc. Cambr. Phil., Soc., vol. 58, pp. 497-520, 1962.
• 12: [12] F. Kelly, Reversibility and Stochastic Networks. New York: Wiley, 1979.
• 13: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 14: [14] P. Jelenković, P. Momčilović, and M. Squillante, "Buffer scalability of wireless networks," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 15: [15] T. Liggett, Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Berlin, Germany: Springer-Verlag, 1999.
• 16: Mark Karol , S. Jamaloddin Golestani , David Lee, Prevention of deadlocks and livelocks in lossless backpressured packet networks, IEEE/ACM Transactions on Networking (TON), v.11 n.6, p.923-934, 01 December 2003 [doi>10.1109/TNET.2003.820434]
• 17: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 18: [18] J. Herdtner and E. Chong, "Throughput-storage tradeoff in ad hoc networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, vol. 4, pp. 2536-2542.
• 19: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 20: [20] M. Neely and E. Modiano, "Capacity and delay tradeoffs for ad hoc mobile networks," IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1917-1937, Jun. 2005.
• 21: [21] P. Robert, Stochastic Networks and Queues. Berlin, Germany: Springer, 2003.
• 22: [22] X. Chao, M. Miyazawa, and M. Pinedo, Queueing Networks: Customers, Signals, and Product Form Solutions. Chichester, U.K.: Wiley, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Management, Performance

Keywords:
ad hoc wireless networks, finite-buffer queueing networks, large-scale networks, local cooperation, scaling laws, wireless sensor networks