Asymptotic Properties of Proportional-Fair Sharing Algorithms: Extensions of the Algorithm

摘要

We are concerned with the allocation of transmitter time and power for randomly time varying mobile data communications. Time is divided into small scheduling intervals, called slots, and information on the channel rates for the various users is available at the start of the slot, when the user selections are made. There is a conflict between selecting the user set that can get the most immediate data through and helping users with poor average rates. The Proportional Fair Sharing method (PFS) deals with such con icts. In 5, 6) the convergence and basic qualitative properties were analyzed. Stochastic approximation results were used to analyze the long term properties. The paths of the (suitably interpolated) throughputs converge to the solution of an ODE, akin to a mean flow. The ODE has a unique equilibrium point. It is asymptotically stable and optimal in that it is the maximizer of a concave utility function. There is a large family of such algorithms, each member corresponding to a concave utility function. The basic idea of PFS extends to many systems of current importance for which it was not originally intended, and a variety of such extensions are treated here to illustrate the possibilities. One might have minimal throughput constraints, nonlinear dependence of rate on allocated power, minimal SNR requirements, etc. In some recent applications, the number of slots in a scheduling intervals is random, and the length is not known when the selection is made. The form of the PFS rule is adapted to the application. Then the basic results continue to hold. The asymptotic properties of the ODE characterize the behavior of the algorithm.