Order Optimal Delay for Opportunistic Scheduling in Multi-User Wireless Uplinks and Downlinks

We consider a one-hop wireless network with independent time varying ON/OFF channels and N users, such as a multi-user uplink or downlink. We first show that general classes of scheduling algorithms that do not consider queue backlog must incur average delay that grows at least linearly with N . We then construct a dynamic queue-length aware algorithm that maximizes throughput and achieves an average delay that is independent of N. This is the first order-optimal delay result for opportunistic scheduling with asymmetric links. The delay bounds are achieved via a technique of queue grouping together with Lyapunov drift and statistical multiplexing concepts.