We study opportunistic multiuser scheduling in downlink networks with Markov-modeled outage channels. We consider the scenario that the scheduler does not have full knowledge of the channel state information, but instead estimates the channel state by exploiting the memory inherent in the Markov channels along with Automatic-Repeat-reQues-styled-styled feedback from the scheduled users. Opportunistic scheduling is optimized in two stages: 1) channel estimation and rate adaptation are performed to maximize the short-term throughput, i.e., the successful transmission rate of the scheduled user in the current slot and 2) user scheduling is performed, based on the short-term throughput, 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 versus exploration tradeoff that is difficult to quantify. We, therefore, study the problem in the framework of restless multiarmed 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. Through extensive numerical experiments, we show that the Whittle's index policy has near-optimal performance and is robust against various imperfections in channel state feedback. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant system-level performance gains and that almost all of these gains can be realized using the polynomial-complexity Whittle's index policy.

We consider a cognitive radio network with multiple primary users (PUs) and one secondary user (SU), where a spectrum server is utilized for scheduling the SU to transmit over one of the PU channels opportunistically. One practical yet challenging scenario is when both the PU occupancy and the channel fading vary over time and exhibit temporal correlations. Little work has been done for exploiting such temporal memory in the channel fading and the PU occupancy simultaneously for opportunistic spectrum scheduling. Further, the scenario where PU occupancy possesses a long temporal memory has been underexplored as well. By casting the problem as a partially observable Markov decision process, we aim to understand the intricate tradeoffs resulting from the interactions of the two sets of system states (i.e., channel fading and PU occupancy) and the impact of the associated temporal memory. We identify and illustrate a set of multi-tier tradeoffs that go beyond the classic “exploitation vs. exploration” tradeoff. For certain special cases, we establish the optimality of a simple greedy policy. To build a more comprehensive understanding, we then introduce a full-observation genie-aided system that helps in decomposing the tradeoffs in the original system into multiple layers, which we examine progressively. Numerical examples indicate that the optimal scheduler in the original system, with observation on the scheduled channel only, achieves a performance very close to the genie-aided system. In addition, the optimal policy in the original system significantly outperforms randomized scheduling, as well as a policy that explores memory in one system state only, pointing to the merit of jointly exploiting the temporal correlation structure in both channel fading and PU occupancy.

This paper focuses on the downlink of a cellular system and studies opportunistic multiuser scheduling under imperfect channel state information, by exploiting the memory inherent in the channel. The channel between the base station and each user is modeled by a two-state Markov chain and the scheduled user sends back an ARQ feedback that arrives at the scheduler with a random delay, i.i.d. across users and time. The scheduler indirectly estimates the channel via accumulated delayed-ARQ feedback and uses this information to make scheduling decisions. The throughput maximization problem is formulated as a partially observable Markov decision process (POMDP). For the case of two users in the system, it is shown that a greedy policy is sum throughput optimal for any distribution on the ARQ feedback delay. For the case of more than two users, the greedy policy is suboptimal and numerical studies demonstrate that it has near optimal performance. Also, the greedy policy can be implemented by a simple algorithm that does not require the statistics of the underlying Markov channel or the ARQ feedback delay, thus making it robust against errors in system parameter estimation. Establishing an equivalence between the two-user system and a genie-aided system, a simple closed form expression for the sum capacity of the downlink is obtained. Further, inner and outer bounds on the capacity region of the downlink are obtained.

In this study, downlink scheduling of multiuser traffic with hard deadlines and packet-level priorities is cast as a partially observable Markov decision process. User channels are modeled as Markovian and the base station can learn only the channel condition of the currently scheduled user. The optimization of joint channel learning and scheduling presents the combined challenges incurred by the strict deadline constraint of real-time traffic and the partial observability of multiuser channels. In particular, we show that idling adds a new dimension to the action space; and that, through a case study of heterogeneous multiuser networks, idling is indeed the optimal action under certain system states. This somewhat surprising result reveals the existence of the fundamental tradeoffs between exploitation and exploration/idling, going beyond the classic `exploitation vs exploration'. We find that, due to hard deadlines and packet priorities, idling is intimately related to the tradeoff between the successful transmission of backlogged packets and that of future arrivals. In contrast, for the special case with a symmetric two-user system, we show that the scheduling problem exhibits unique structures, rendering a non-idling greedy policy optimal.

Integrating volatile renewable energy resources into the bulk power grid is challenging, due to the reliability requirement that the load and generation in the system remain balanced all the time. In this study, we tackle this challenge for smart grid with integrated wind generation, by leveraging multi-timescale dispatch and scheduling. Specifically, we consider smart grids with two classes of energy users - traditional energy users and opportunistic energy users (e.g., smart meters or smart appliances), and investigate pricing and dispatch at two timescales, via day-ahead scheduling and real-time scheduling. In day-ahead scheduling, with the statistical information on wind generation and energy demands, we characterize the optimal procurement of the energy supply and the day-ahead retail price for the traditional energy users; in real-time scheduling, with the realization of wind generation and the load of traditional energy users, we optimize real-time prices to manage the opportunistic energy users so as to achieve system-wide reliability. More specifically, when the opportunistic users are non-persistent, we obtain closed-form solutions to the two-level scheduling problem. For the persistent case, we treat the scheduling problem as a multi-timescale Markov decision process. We show that it can be recast, explicitly, as a classic Markov decision process with continuous state and action spaces, the solution to which can be found via standard techniques.

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 scheduling is optimized in two stages: (1) Channel estimation and rate adaptation to maximize the expected immediate 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 (RMBP) 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 index policy has near-optimal performance. Our work reveals that, under incomplete channel state information, exploiting channel memory for opportunistic scheduling can result in significant performance gains and that almost all of these gains can be realized using an easy-to-implement index policy.

Channel state information (CSI) is important for achieving large rates in MIMO channels. However, in time-varying MIMO channels, there is a tradeoff between the time/energy spent acquiring channel state information (CSI) and the time/energy remaining for data transmission. This tradeoff is accentuated in the MIMO multiple access channel (MAC), since the number of channel vectors to be estimated increases with the number of users. Furthermore, the problem of acquiring CSI is tightly coupled with the problem of exploiting CSI through multiuser scheduling. This paper considers a block-fading MAC with coherence timeT, n uncoordinated users-each with one transmit antenna and the same average power constraint, and a base station withMreceive antennas and no a priori CSI. For this scenario, a training-based communication scheme is proposed and the training and multiuser-scheduling aspects of the scheme are jointly optimized. In the high-SNR regime, the sum capacity of the non-coherent SIMO MAC is characterized and used to establish the SNR-scaling-law optimality of the proposed scheme. In the low-SNR regime, the sum-rate of the proposed scheme is found to decay linearly with vanishing SNR when flash signaling is incorporated. Furthermore, this linear decay is shown to be order-optimal through comparison to the low-SNR sum capacity of the non-coherent SIMO MAC. A by product of these SNR-asymptotic analyses is the observation that non-trivial scheduling (i.e., scheduling a strict subset of trained users) is advantageous at low SNR, but not at high SNR. The sum-rate and per-user throughput are also explored in the large-nand large-Mregimes. Non-coherent capacity, training, multiple access channel, multiuser scheduling, opportunistic scheduling.