Optimal Utility Based Multi-User Throughput Allocation subject to Throughput Constraints

We consider the problem of scheduling multiple users sharing a time-varying wireless channel. (As an example, this is a model of scheduling in 3G wireless technologies, such as CDMA2000 3G1xEV-DO downlink scheduling.) We introduce an algorithm which seeks to optimize a concave utility function sum_i H_i(R_i) of the user throughputs R_i, subject to certain lower and upper throughput bounds: R_i^min le R_i le R_i^max. The algorithm, which we call the Gradient algorithm with Minimum/Maximum Rate constraints (GMR) uses a token counter mechanism, which modifies an algorithm solving the corresponding unconstraine} problem, to produce the algorithm solving the problem with throughput constraints. Two important special cases of the utility functions are sum_i log(R_i) and sum_i R_i, corresponding to the common Proportional Fairness and Throughput Maximization objectives. We show asymptotic optimality of GMR in the sense that if, under an appropriate scaling, the throughput vector R(t) converges to a fixed vector R^* as time t goes to infinity, then R^*$is a solution to the optimization problem described above. We also present simulation results showing the algorithm performance. [This paper is a generalized and extended version of report ITD-02-43545G.]