Extensions of Proportional-Fair Sharing Algorithms for Multi-Access Control of Mobile Communications: Constraints, Finite Queues and Bursty Data Processes

摘要

We are concerned with the scheduling decisions (allocation of transmitter time, bandwidth and power) for multi-access mobile communications for data communications when the channels are randomly time varying. 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 that can get the most immediate data through and helping users with poor average throughputs. The Proportional Fair Sharing method (PFS) deals with such conflicts. In (4), and (6) the convergence and basic qualitative properties were analyzed via stochastic approximation methods. The paths of the (suitably interpolated) throughputs converge to the solution of an ODE, akin to a mean flow. The behavior of the ODE completely describes the behavior of PFS. It has a unique equilibrium point that is asymptotically stable and optimal for PFS 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. Most past work assumed an in infinite backlog of data. In many applications, the data arrival process for some users is bursty and data is queued until transmission, there might be minimal throughput constraints, or a balance between queue length (or delay) and throughput sought. The fact that some queues might be empty at times raises new issues. Natural modifications of PFS for these cases are shown to have the same properties.