On throughput in linear wireless networks

ABSTRACT

This paper investigates fundamental properties of throughput and energy cost in large wireless linear networks with very limited local resources that do not grow with the size of the network. The maximum throughput of the network is derived and the arrival process that maximizes throughput, given a fixed arrival rate, is established. An asymptotically critical loading regime is identified such that the probability of an arbitrary packet being lost is strictly within (0, 1) as the network size increases. Such a regime delivers throughput comparable to the maximum at a reasonable energy cost.

The paper also establishes the asymptotic network energy cost under this critical loading. These results are then used to consider a performance-cost tradeoff within an optimization problem for which the unique equilibrium point that maximizes the difference between performance benefits and costs is derived. Finally, from a mathematical perspective, the paper furthers our understanding of large stochastic linear networks for which, in general, no explicit solutions have been previously available.

REFERENCES

• 1: D. Bailey. Counting arrangements of 1's and -1's. Math. Mag., 69(2):128--131, 1996.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin. Throughput analysis in multihop CSMA packet radio networks. IEEE Trans. Comm., 35(3):267--274, 1987.
• 4: O. Dousse. Revising buffering in multihop CSMA/CA wireless networks. In Proc. IEEE SECON, San Diego, CA, June 2007.
• 5: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000.
• 6: P. J. Hunt and F. P. Kelly. On critically loaded loss networks. Adv. Appl. Prob., 21(4):831--841, 1989.
• 7: Predrag R. Jelenković , Petar Momčilović , Mark S. Squillante, Scalability of wireless networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.295-308, April 2007 [doi>10.1109/TNET.2007.892846]
• 8: I. Karatzas and S. Shreve. Brownian Motion and Stochastic Calculus. Springer-Verlag, New York, 2nd edition, 1991.
• 9: T. Liggett. Interacting Particle Systems. Springer-Verlag, New York, 1985.
• 10: T. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Springer-Verlag, Berlin, 1999.
• 11: James B. Martin, Large Tandem Queueing Networks with Blocking, Queueing Systems: Theory and Applications, v.41 n.1-2, p.45-72, June 2002 [doi>10.1023/A:1015729701521]
• 12: A. Saleh and J. Simmons. Evolution toward the next-generation core optical network. J. Lightwave Tech., 24(9):3303--3321, 2006.
• 13: J. Silvester and L. Kleinrock. On the capacity of multihop slotted ALOHA networks with regular structure. IEEE Trans. Comm., 31(8):974--982, 1983.
• 14: W. Whitt. Stochastic-Process Limits. Springer, New York, 2002.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Packet-switching networks

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Performance, Theory

Keywords:
asymptotic properties, critical load, linear loss networks, throughput properties, wireless networks