On the maximum stable throughput problem in random networks with directional antennas

ABSTRACT

We consider the problem of determining rates of growth for the maximum stable throughput achievable in dense wireless networks. We formulate this problem as one of finding maximum flows on random unit-disk graphs. Equipped with the max-flow/min-cut theorem as our basic analysis tool, we obtain rates of growth under three models of communication: (a) omnidirectional transmissions; (b) "simple" directional transmissions, in which sending nodes generate a single beam aimed at a particular receiver; and (c) "complex" directional transmissions, in which sending nodes generate multiple beams aimed at multiple receivers. Our main finding is that an increase of Θlog2n in maximum stable throughput is all that can be achieved by allowing arbitrarily complex signal processing (in the form of generation of directed beams) at the transmitters and receivers. We conclude therefore that neither directional antennas, nor the ability to communicate simultaneously with multiple nodes, can be expected in practice to effectively circumvent the constriction on capacity in dense networks that results from the geometric layout of nodes in space.

REFERENCES

• 1: S. Adireddy and L. Tong. Exploiting Decentralized Channel State Information for Random Access. Submitted for publication. Available from http://acsp.ece.cornell.edu/.
• 2: R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network Information Flow. IEEE Trans. Inform. Theory, 46(4):1204--1216, 2000.
• 3: Romit Roy Choudhury , Xue Yang , Nitin H. Vaidya , Ram Ramanathan, Using directional antennas for medium access control in ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570653]
• 4: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 5: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 6: L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• 7: S. Ghez, S. Verdú, and S. Schwartz. Optimal Decentralized Control in the Random Access Multipacket Channel. IEEE Trans. Autom. Control, 34(11):1153--1163, 1989.
• 8: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 9: 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]
• 10: M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer Verlag, 1988.
• 11: P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W. M. McEneany, G. Yin, and Q. Zhang, editors, Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Birkhauser, 1998.
• 12: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000.
• 13: M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Networks, 25:59--68, 1995.
• 14: G. Mergen and L. Tong. On the Capacity of Regular Wireless Networks with Transceiver Multipacket Communication. In Proc. IEEE Int. Symp. Inform. Theory (ISIT), Lausanne, Switzerland, 2002.
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984.
• 17: Anna Scaglione , Sergio D. Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570663]
• 18: S. D. Servetto. Quantization with Side Information: Lattice Codes, Asymptotics, and Applications in Wireless Networks. Submitted to the IEEE Trans. Inform. Theory. Available from http://people.ece.cornell.edu/servetto/.
• 19: L. Tong, Q. Zhao, and G. Mergen. Multipacket Reception in Random Access Wireless Networks: From Signal Processing to Optimal Medium Access Control. IEEE Communications Magazine, 39(11):108--112, 2001.
• 20: S. Toumpis and A. J. Goldsmith. Capacity Regions for Wireless Adhoc Networks. IEEE Trans. Wireless Comm., to appear. Available from http://wsl.stanford.edu/.
• 21: B. S. Tsybakov and V. A. Mikhailov. Ergodicity of a Slotted ALOHA System. Problemy Peredachi Informatsii, 15(4):301--312, 1979.
• 22: V. N. Vapnik and A. Ya. Chervonenkis. On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications, XVI(2):264--280, 1971.
• 23: D. West. Introduction to Graph Theory. Prentice Hall, 1996.
• 24: Jeffrey E. Wieselthier , Gam D. Nguyen , Anthony Ephremides, Energy-efficient broadcast and multicast trees in wireless networks, Mobile Networks and Applications, v.7 n.6, p.481-492, December 2002 [doi>10.1023/A:1020716919751]
• 25: L.-L. Xie and P. R. Kumar. A Network Information Theory for Wireless Communication: Scaling Laws and Optimal Operation. Submitted to the IEEE Trans. Inform. Theory, April 2002. Available from http://decision.csl.uiuc.edu/ prkumar/.
• 26: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
directional antennas, maximum stable throughput, multicommodity flow, network flow, random graphs, random networks, wireless networks