Convergence of proportional-fair sharing algorithms under general conditions

• Published in: IEEE transactions on wireless communications 2004-07, Vol.3 (4), p.1250-1259
• Main Authors: Kushner, H.J., Whiting, P.A.
• Format: Article
• Language: English
• Subjects: Access methods and protocols, osi model; Algorithm design and analysis; Algorithms; Applied sciences; Approximation; Base stations; Convergence; Differential equations; Equipments and installations; Exact sciences and technology; Information analysis; Intervals; Mathematical analysis; Mobile communication; Mobile radiocommunication systems; Radiocommunications; Scheduling algorithm; Stochastic processes; Stochasticity; Studies; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Teleprocessing networks. Isdn; Throughput; Transmission and modulation (techniques and equipments); Transmitters; Utilities
• ISSN: 1536-1276; 1558-2248
• DOI: 10.1109/TWC.2004.830826

We are concerned with the allocation of the base station transmitter time in time-varying mobile communications with many users who are transmitting data. Time is divided into small scheduling intervals, and the channel rates for the various users are available at the start of the intervals. Since the rates vary randomly, in selecting the current user there is a conflict between full use (by selecting the user with the highest current rate) and fairness (which entails consideration for users with poor throughput to date). The proportional fair scheduler of the Qualcomm High Data Rate system and related algorithms are designed to deal with such conflicts. The aim here is to put such algorithms on a sure mathematical footing and analyze their behavior. The available analysis, while obtaining interesting information, does not address the actual convergence for arbitrarily many users under general conditions. Such algorithms are of the stochastic approximation type and results of stochastic approximation are used to analyze the long-term properties. It is shown that the limiting behavior of the sample paths of the throughputs converges to the solution of an intuitively reasonable ordinary differential equation, which is akin to a mean flow. We show that the ordinary differential equation (ODE) has a unique equilibrium and that it is characterized as optimizing a concave utility function, which shows that PFS is not ad-hoc, but actually corresponds to a reasonable maximization problem. These results may be used to analyze the performance of PFS. The results depend on the fact that the mean ODE has a special form that arises in problems with certain types of competitive behavior. There is a large set of such algorithms, each one corresponding to a concave utility function. This set allows a choice of tradeoffs between the current rate and throughout. Extensions to multiple antenna and frequency systems are given. Finally, the infinite backlog assumption is dropped and the data is allowed to arrive at random. This complicates the analysis, but the same results hold.