Multi-user scheduling in wireless networks with QoS constraints

We consider a cellular network consisting of a base station and N receivers. The channel states of the receivers are assumed to be identical and independent of each other. The goal is to compare the throughput of two different scheduling policies (a queue-length-based policy and a greedy scheduling policy) given an upper bound on the queue overflow probability. We consider a multi-state channel model, where each channel is assumed to be in one of l. states. Given an upper bound on the queue overflow probability, we obtain a lower bound on the throughput of the queue-length-based policy. For sufficiently large N, the lower bound is shown to be tight, strictly increasing with N, and strictly larger than the throughput of the greedy policy.