Low-delay throughput-optimal max weight scheduling for real-time mobile applications

The goal of this study is to reduce the packet delays of real-time mobile applications in a multiuser environment where the users' channels are randomly varying. Some parsimonious schedulers of the “max weight” type are known to maximize the stability regions of such queuing systems with very low computational complexity. Most previous work generalized the weight functions while limiting their input queue state variables to backlog sizes. In this study, we first generalize their results to support more general queue state variables and weight functions with mixed orders and with discontinuities. Compared to previous schedulers using backlog sizes and head-of-the-line (HOL) packet delays, max weight schedulers using forecasted “future maximum delay” as queue state variable produce much lower packet delays when frame size variations are present. Recognizing that the key to produce packet delays is to suppress long packet delays while maximizing spectral efficiency, we then proceed to characterize the efficiency behaviors of max weight schedulers. We prove that fixed weight schedulers provide the best spectral efficiency no matter whether there is quantization. The condition for efficiency loss and the procedure to calculate efficiency loss are also given. A modified Gauss-Newton algorithm is proposed to quickly find the optimal fixed weight vector for given channel conditions and data rate requirements. The effects of different orders of weight functions are also investigated. These results lead to a simple procedure to determine the parameters and function forms of max weight schedulers in order to achieved the best tradeoff between packet delay and spectral efficiency. Lastly, the framework also enables us to quickly determine the maximum stability region of such a queuing system without Monte Carlo simulations.