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 andNusers, 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 withN. We then construct a dynamic queue-length aware algorithm that maximizes throughput and achieves an average delay that is independent ofN. This is the first order-optimal delay result for opportunistic scheduling with asymmetric links. The delay bounds are achieved via a technique ofqueuegrouping together with Lyapunov drift and statistical multiplexing concepts.