Opportunistic Scheduling as Restless Bandits
For wireless network designers, this work provides a theoretically grounded scheduling policy that improves energy efficiency over existing heuristics.
This paper addresses energy-efficient scheduling in multiuser wireless systems with finite queues and delay costs, proving the problem is Whittle Indexable and proposing a Whittle index-based algorithm that achieves lower average cost than Maximum Weight Scheduling and Weighted Fair Scheduling in simulations.
In this paper we consider energy efficient scheduling in a multiuser setting where each user has a finite sized queue and there is a cost associated with holding packets (jobs) in each queue (modeling the delay constraints). The packets of each user need to be sent over a common channel. The channel qualities seen by the users are time-varying and differ across users; also, the cost incurred, i.e., energy consumed, in packet transmission is a function of the channel quality. We pose the problem as an average cost Markov Decision Problem, and prove that this problem is Whittle Indexable. Based on this result, we propose an algorithm in which the Whittle index of each user is computed and the user who has the lowest value is selected for transmission. We evaluate the performance of this algorithm via simulations and show that it achieves a lower average cost than the Maximum Weight Scheduling and Weighted Fair Scheduling strategies.