| In a wireless network, the efficiency of scheduling algorithms over time-varying channels depends heavily on the accuracy of the Channel State Information (CSI), which is usually quite "costly" in terms of consuming network resources. In the meanwhile, communication channels in wireless systems typically fluctuate in a temporally-correlated manner. We hence consider scheduling in wireless networks with limited and imperfect channel state knowledge, where the scheduler can exploit the temporal-correlation inherent in channels with memory for better channel state knowledge. We consider the channel state acquisition mechanism with ARQ-styled feedback, whereby the channel states are revealed at the end of only scheduled users' transmissions. In the presence of temporally-correlated channel evolution, the desired scheduler must optimally balance the 'exploitation-exploration trade-off', whereby it schedules transmissions both to exploit those channels with up-to-date CSI and to explore the current state of those with outdated CSI.;We model the scheduling problems as Partially Observable Markov Decision Processes (POMDPs). POMDPs are known to be difficult to solve. We are able to analyze the problems in the framework of Restless Multi-armed Bandit Processes and utilize the Whittle's indexability analysis. Based on our analysis, we propose low-complexity scheduling algorithms that have optimality performance in different wireless networks. Our work reveals that, under limited and imperfect channel state information, exploiting channel memory and ARQ-styled feedback for scheduling can result in significant system-level performance gains and that the proposed polynomial-complexity algorithms have provably optimal performances in various settings. |
