Exploiting Channel Memory for Joint Estimation and Scheduling in Downlink Networks -- A Whittle’s Indexability Analysis

We address the problem of opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario in which the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state information by exploiting the memory inherent in the Markov channels along with ARQ-styled feedback from the scheduled users. Opportunistic schedul-ing is optimized in two stages: (1) Channel estimation and rate adaptation to maximize the expected immediate successful transmission rate of the scheduled user; (2) User scheduling, based on the optimized immediate rate, to maximize the overall long term sum-throughput of the downlink. The scheduling problem is a partially observable Markov decision process with the classic ‘exploitation vs exploration’ trade-off that is difficult to quantify. We therefore study the problem in the framework of Restless Multi-armed Bandit Processes and perform a Whittle’s indexability analysis. Whittle’s indexability is traditionally known to be hard to establish and the index policy derived based on Whittle’s indexability is known to have optimality properties in various settings. We show that the problem of downlink scheduling under imperfect channel state information is Whittle indexable and derive the Whittle’s index policy in closed form. Via extensive numerical experiments, we show that the Whittle’s index policy has near-optimal performance and is robust against imperfections in channel state feedback. Our work reveals that, under incomplete channel state infor-mation, exploiting channel memory for opportunistic scheduling can result in significant performance gains and that almost all of these gains can be realized using the easy-to-implement Whittle’s index policy