Resource-Redistributive Opportunistic Scheduling for Wireless Systems

Opportunistic scheduling algorithms must balance throughput improvement (multiuser diversity) with externally imposed constraints on delay and fairness. For K users each with a weighted fairness constraint, the optimum solution is typically infeasible due to interdependence in the achievable rates. The contribution of this paper is a novel algorithm for achieving resource-sharing constraints with low complexity. This technique, termed resource-redistributive opportunistic (RRO) scheduling, consists of an initial allocation and then a stochastic diversion of resources from surplus users to underserved users. This conceptually and numerically simple approach is shown to have some appealing properties. First, we derive the exact average. throughput of the RRO scheduler for non-identically distributed user channels, and show that RRO achieves 90-95% of the optimum weighted fairness capacity, which requires O(K-3) complexity conservatively. Second, extreme value theory is used to prove that for large K the throughput loss of the proposed scheduler is linear with the degree of weighted fairness, and the throughput loss rate is only a half of that of the redistribution strategy based on round-robin.