Distributed algorithms for spectrum allocation, power control, routing, and congestion control in wireless networks

ABSTRACT

We develop distributed algorithms to allocate resources in multi-hop wireless networks with the aim of minimizing the total cost. In order to observe the fundamental duplexing constraint that co-located transmitters and receivers cannot operate simultaneously on the same frequency band, we first devise a spectrum allocation scheme that divides the whole spectrum into multiple sub-bands and activates conflict-free links on each sub-band. We show that the minimum number of required sub-bands grows asymptotically at a logarithmic rate with the chromatic number of network connectivity graph. A simple distributed and asynchronous algorithm is developed to feasibly activate links on the available sub-bands. Given a feasible spectrum allocation, we then develop node-based distributed algorithms for optimally controlling the transmission powers on active links for each sub-band, jointly with traffic routes and user input rates in response to channel states and traffic demands. We show that under specified conditioans, the algorithms asymptotically converge to the optimal operating point.

REFERENCES

• 1: M. Johansson, L. Xiao, and S. Boyd, "Simultaneous routing and power allocation in CDMA wireless data networks," in Proceedings of IEEE International Conference on Communications, vol. 1, May 2003.
• 2: M. Chiang, "To layer or not to layer: Balancing transport and physical layers in wireless multihop networks," in Proceedings of IEEE INFOCOM 2004, vol. 4, Mar. 2004.
• 3: Y. Xi and E. M. Yeh, "Optimal distributed power control and routing in wireless networks," in Proceedings of the 2006 International Symposium on Information Theory, (Seattle, WA), July 2006.
• 4: Andrea Goldsmith, Wireless Communications, Cambridge University Press, New York, NY, 2005
• 5: L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, "Jointly optimal congestion control, routing, and scheduling for wireless ad hoc networks," in Proceedings of IEEE INFOCOM 2006, Apr. 2006.
• 6: L. Bui, A. Eryilmaz, R. Srikant, and X. Wu, "Joint asynchronous congestion control and distributed scheduling for multi-hop wireless networks," in Proceedings of IEEE INFOCOM 2006, Apr. 2006.
• 7: B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Transactions on Information Theory, vol. 34, pp. 910--917, Sept. 1988.
• 8: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 9: L. Tassiulas and A. Ephremides, "Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks," IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936--1948, 1992.
• 10: Y. Liu and E. Knightly, "Opportunistic fair scheduling over multiple wireless channels," in Proceedings of IEEE INFOCOM 2003, Apr. 2003.
• 11: T. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad-hoc networks," in Proceedings of IEEE INFOCOM 2002, pp. 976--984, June 2002.
• 12: E. Arikan, "Some complexity results about packet radio networks," IEEE Transactions on Information Theory, vol. 31, pp. 910--918, 1984.
• 13: X. Lin and N. Shroff, "The impact of imperfect scheduling on cross-layer rate control in wireless networks," in Proceedings of IEEE INFOCOM 2005, vol. 3, pp. 1804--1814, Mar. 2005.
• 14: W. K. Hale, "Frequency assignment: theory and applications," Proceedings of the IEEE, vol. 68, no. 12, pp. 1497--1514, 1980.
• 15: M. B. Cozzens and D.-I. Wang, "The general channel assignment problem," Congressus Numerantium, vol. 41, pp. 115--129, 1984.
• 16: Mansoor Alicherry , Randeep Bhatia , Li (Erran) Li, Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080836]
• 17: Murali Kodialam , Thyaga Nandagopal, Characterizing the capacity region in multi-radio multi-channel wireless mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080837]
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: E. Sperner, "Ein satz Äuber untermegen einer endlichen menge," Math. Zeitschr, vol. 27, pp. 544--548, 1928.
• 20: W. Feller, An Introduction to Probability Theory and Its Applications. Wiley, 3rd ed., 1968.
• 21: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 22: R. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Transactions on Communications, vol. 25, no. 1, pp. 73--85, 1977.
• 23: D. Bertsekas, E. Gafni, and R. Gallager, "Second derivative algorithm for minimum delay distributed routing in networks," IEEE Transactions on Communications, vol. 32, no. 8, pp. 911--919, 1984.
• 24: D. Bertsekas, Nonlinear Programming. Athena Scientific, second ed., 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory

Additional Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Algorithms, Design, Theory

Keywords:
cross-layer optimization, resource allocation, spectrum allocation, wireless networks