We consider the delay properties of max-weight opportunistic scheduling in a multi-user ON/OFF wireless system, such as a multi-user downlink or uplink. It is well known that max-weight scheduling stabilizes the network (and hence yields maximum throughput) whenever input rates are inside the network capacity region. We show that when arrival and channel processes are independent, average delay of the max-weight policy is order-optimal, in the sense that it does not grow with the number of network links. While recent queuegrouping algorithms are known to also yield order-optimal delay, this is the first such result for the simpler class of maxweight policies. We consider the delay properties of max-weight opportunistic scheduling in a multi-user wireless system. Specifically, we consider a system with N transmission links. Each link receives independent data that arrives randomly and must be queued for eventual transmission. Separate queues are maintained by each link i ∈ {1, . . . , N}, so that data arriving to queue i must be transmitted over link i. The system works in slotted time with normalized slots t ∈ {0, 1, 2, . . .}. The channel states of each link vary randomly from slot to slot, and every slot t the network controller observes the current queue backlogs and the current channel states, and selects a single link for wireless transmission. This is a classic opportunistic scheduling scenario, where the network scheduler can exploit knowledge of the current state of the time varying channels. It is well known that maxweight scheduling policies are throughput optimal in such systems, in the sense that they provably stabilize all queues whenever the input rate vector is inside the network capacity region. This stability result was first shown by Tassiulas and Ephremides in [2] for the special case of ON/OFF channels, and was later generalized to multi-rate transmission models and systems with power allocation [3] [4] [5] [6] . However, the delay properties of max-weight scheduling are less understood. An average delay bound that is linear in N is derived in [5] [6] . While this bound is tight in the case of correlated arrival and channel processes, it is widely believed to be loose for independent arrivals and channels. In this paper, we focus on the special case of ON/OFF channels, and show that the max-weight policy indeed yields average delay that is O(1) under independence assumptions. Thus, average delay does not grow with the network size Michael J. Neely is with the Electrical Engineering department at the
REF The queues are assumed to be initialized such that
Delay analysis for max weight opportunistic scheduling in wireless systems
2008 46th Annual Allerton Conference on Communication, Control, and Computing
2008 46th Annual Allerton Conference on Communication, Control, and Computing
Computer Science Mathematics