Predrag R. Jelenković
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.
- {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. Google Scholar
- {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.Google Scholar
- {3} A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Optimal throughput-delay scaling in wireless networks--Part I: The fluid model," IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2568-2592, Jun. 2006. Google Scholar
- {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. Google Scholar
- {5} M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "On the throughput capacity of random wireless networks." Preprint.Google Scholar
- {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. Google Scholar
- {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. Google Scholar
- {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. Google Scholar
- {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. Google Scholar
- {10} G. Barrenechea, B. Beferull-Lozano, and M. Vetterli, "Lattice sensor networks: Capacity limits, optimal routing and robustness to failures," in Proc. Conf. Information Processing In Sensor Networks (IPSN), Berkeley, CA, Apr. 2004. Google Scholar
- {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.Google Scholar
- {12} F. Kelly, Reversibility and Stochastic Networks. New York: Wiley, 1979.Google Scholar
- {13} D. Bertsekas and R. Gallager, Data Networks, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 1992. Google Scholar
- {14} P. Jelenković, P. Momčilović, and M. Squillante, "Buffer scalability of wireless networks," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.Google Scholar
- {15} T. Liggett, Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Berlin, Germany: Springer-Verlag, 1999.Google Scholar
- {16} M. Karol, S. J. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 923-934, Dec. 2003. Google Scholar
- {17} F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes. San Mateo, CA: Morgan Kaufmann, 1992. Google Scholar
- {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.Google Scholar
- {19} M. Grossglauser and D. Tse, "Mobility increases the capacity of ad hoc wireless networks," IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477-486, Aug. 2002. Google Scholar
- {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. Google Scholar
- {21} P. Robert, Stochastic Networks and Queues. Berlin, Germany: Springer, 2003.Google Scholar
- {22} X. Chao, M. Miyazawa, and M. Pinedo, Queueing Networks: Customers, Signals, and Product Form Solutions. Chichester, U.K.: Wiley, 1999.Google Scholar
Index Terms
- Scalability of wireless networks
Recommendations
Relay Node Placement in Wireless Sensor Networks
A wireless sensor network consists of many low-cost, low-power sensor nodes, which can perform sensing, simple computation, and transmission of sensed information. Long distance transmission by sensor nodes is not energy efficient since energy ...
Integrated Connectivity and Coverage Techniques for Wireless Sensor Networks
MobiWac '16: Proceedings of the 14th ACM International Symposium on Mobility Management and Wireless AccessA wireless sensor network (WSN) consists of a group of energy-constrained sensor nodes with the ability of both sensing and communication, which can be deployed in a field of interesting (FoI) for detecting or monitoring some special events and then ...
On the data gathering capacity and latency wireless sensor networks
Special issue on simple wireless sensor networking solutionsIn this paper, we investigate the fundamental properties of data gathering in wireless sensor networks, in terms of both capacity and latency. We consider a scenario in which s(n) out of n total network nodes have to deliver data to a set of d(n) sink ...
Comments