Opportunistic Scheduling as Restless Bandits

In this paper, we consider energy-efficient scheduling in a multiuser setting, where each user has a separate 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-like indexable. Based on this result, we propose an algorithm in which the Whittle-like 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.