Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access

ABSTRACT

In this paper, we address the rate control problem in a multi-hop random access wireless network, with the objective of achieving proportional fairness amongst the end-to-end sessions. The problem is considered in the framework of nonlinear optimization. Compared to its counterpart in a wired network where link capacities are assumed to be fixed, rate control in a multi-hop random access network is much more complex and requires joint optimization at both the transport layer and the link layer. This is due to the fact that the attainable throughput on each link in the network is `elastic' and is typically a non-convex and non-separable function of the transmission attempt rates. Two cross-layer algorithms, a dual based algorithm and a primal based algorithm, are proposed in this paper to solve the rate control problem in a multi-hop random access network. Both algorithms can be implemented in a distributed manner, and work at the link layer to adjust link attempt probabilities and at the transport layer to adjust session rates. We prove rigorously that the two proposed algorithms converge to the globally optimal solutions. Simulation results are provided to support our conclusions.

REFERENCES

• 1: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 2: D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
• 3: N. Z. Shor , Krzysztof C. Kiwiel , Andrzej Ruszcayǹski, Minimization methods for non-differentiable functions, Springer-Verlag New York, Inc., New York, NY, 1985
• 4: F. P. Kelly, "Charging and Rate Control for Elastic Traffic", European Transactions on Telecommunications, vol. 8, no. 1, 1997, pp. 33--37.
• 5: F. Kelly, A. Maulloo, D. Tan, "Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability", Journal of Operations Research Society, vol. 49, no. 3, 1998, pp. 237--252.
• 6: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 7: Thyagarajan Nandagopal , Tae-Eun Kim , Xia Gao , Vaduvur Bharghavan, Achieving MAC layer fairness in wireless packet networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.87-98, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345925]
• 8: Timucin Ozugur , Mahmoud Naghshineh , Parviz Kermani , C. Michael Olsen , Babak Rezvani , John A. Copeland, Balanced media access methods for wireless networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.21-32, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288244]
• 9: L. Tassiulas, S. Sarkar, "Maxmin Fair Scheduling in Wireless Networks", in Proceedings of Infocom 2002, pp. 763--772, New York, USA, June 2002.
• 10: M. Johnasson, L. Xiao, "Cross-layer optimization of wireless networks using nonlinear column generation", accept by IEEE Transactions on Wireless Communications.
• 11: L. Xiao, M. Johnasson, S. Boyd, "Simultaneous Routing and Resource Allocation via Dual Decomposition", IEEE Transactions on Communications, Vol. 52, No. 7, pages 1136--1144, July 2004.
• 12: M. Chiang, "To Layer or Not To Layer: Balancing Transport and Physical Layers in Wireless Multihop Networks", in Proceedings of Infocom 2004, Hong Kong, China, March 2004.
• 13: K. Kar, S. Sarkar, L. Tassiulas, "Achieving Proportionally Fair Rates using Local Information in Multi-hop Aloha Networks", Proceedings of Annual Allerton Conference, Urbana-Champaign, USA, October 2003.
• 14: X. Wang, K. Kar, "Distributed Algorithms for Max-min Fair Rate Allocation in Aloha Networks", Proceedings of Annual Allerton Conference, Urbana-Champaign, USA, October 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms

Keywords:
ad-hoc network, cross-layer control, optimization, random access