Optimal throughput-delay scaling in wireless networks: part I: the fluid model

ABSTRACT

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Θ (1/√n log n). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n) = Θ (nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Θ(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Θ(n log n). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of O (1/√n log n), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n) = Θ (nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Θ (n log n), which is the delay for throughput of Θ(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.

REFERENCES

• 1: [1] D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graph. [Online]. Available: http://www.stat.berkeley.edu/users/aldous/RWG/book.html
• 2: [2] N. Bansal and Z. Liu, "Capacity, mobility and delay in wireless ad hoc networks," in Proc. IEEE INFOCOM, Apr. 2003.
• 3: [3] A. F. Dana and B. Hassibi, "On the power efficiency of sensory and ad-hoc wireless networks," in Proc. IEEE Int. Symp. Information Theory, Yokohama, Japan, Jun./Jul. 2003, p. 412.
• 4: [4] A. Dembo, Y. Peres, L. Rosen, and O. Zeitouni, "Cover times for Brownian motion and random walks in two dimensions," Ann. Math., vol. 160, no. 2, pp. 433-464, 2004.
• 5: [5] S. N. Diggavi, M. Grossglauser, and D. N. C. Tse, "Even one-dimensional mobility increases ad hoc wireless capacity," in Proc. IEEE Int. Symp. Information Theory, Laussane, Switzerland, Jun./Jul. 2002, p. 352.
• 6: [6] A. El Gamal and J. Mammen, "Optimal hopping in ad hoc wireless networks," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 7: [7] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Throughput-delay tradeoff in wireless networks," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 8: [8] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Optimal throughput-delay tradeoff in energy constrained wireless networks," in Proc. IEEE Int. Symp. Information Theory, Chicago, IL, Jun./Jul. 2004, p. 439.
• 9: [9] A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, Optimal throughput-delay scaling in wireless networks--Part II: Constant-size packets. [Online]. Available: http://www.stanford. edu/~mammen/papers/it-TDpkt.pdf
• 10: [10] M. Grossglauser and D. N. C. Tse, "Mobility increases the capacity of ad-hoc wireless networks," in Proc. IEEE INFOCOM, Anchorage, AK, Apr. 2001, pp. 1360-1369.
• 11: [11] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 12: [12] A. Jovicic, P. Viswanath, and S. R. Kulkarni, "Upper bounds to transport capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 11, pp. 2555-2565, Nov. 2004.
• 13: [13] S. R. Kulkarni and P. Viswanath, "A deterministic approach to throughput scaling in wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1041-1049, Jun. 2004.
• 14: [14] O. Leveque and I. E. Telatar, "Information-theoretic upper bounds on the capacity of large extended ad hoc wireless networks," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 858-865, Mar. 2005.
• 15: [15] X. Lin, G. Sharma, R. R. Mazumdar, and N. B. Shroff. Degenerate Delay-Capacity Trade-Offs in Ad Hoc Networks With Brownian Mobility. [Online]. Available: http://min.ecn.purdue.edu/~inx/paper/it05. pdf
• 16: [16] R. Loynes, "Stability of queue with nonindependent arrival and service times," Proc. Camb. Philos. Soc., vol. 58, pp. 497-520, 1962.
• 17: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 18: [18] M. J. 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.
• 19: [19] R. W. Wolff, Stochastic Modeling and the Theory of Queues. New York: Prentice-Hall, 1989.
• 20: [20] L. Xie and P. R. Kumar, "A network information theory for wireless communication: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 748-767, May 2004.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Modeling techniques; Performance attributes

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Design, Performance

Keywords:
queueing theory, random walks, scaling laws, throughput scaling, throughput-delay tradeoff, wireless networks.