Wireless scheduling with hybrid ARQ

A model for downlink wireless scheduling is studied, which takes into account both user-channel conditions and retransmissions with packet combining hybrid [automatic repeat request (ARQ)]. Quality-of-service (QoS) requirements for each user are represented by a cost function, which is an increasing function of queue length. The objective is to find a scheduling rule that minimizes the average cost over time. We consider two scenarios: 1) the cost functions are linear, and packets arrive to the queues according to a Poisson process and 2) the cost functions are increasing, convex, and there are no new arrivals (draining problem). In each case, we transform the system model into a different model that fits into a framework for stochastic scheduling developed by Klimov. Applying Klimov's results, we show that the optimal schedulers for the transformed models in both scenarios are specified by fixed priority rules. Applying the inverse transformation in each case gives the optimal scheduling policy for the original problem. The priorities can be explicitly computed, and in the first scenario, are given by simple closed-form expressions. For the draining problem, we show that the optimal policy never interrupts the retransmissions of a packet. We also show that a simple myopic scheduling policy, called the U'R rule, performs very close to the optimal scheduling policy in specific cases. We present numerical examples, which compare the performance of the optimal scheduling rule with several heuristic rules.