Delay-constrained scheduling: Power efficiency, filter design, and bounds

In this paper, packet scheduling with maximum delay constraints is considered with the objective to minimize average transmit power over Gaussian channels. The main emphasis is on deriving robust schedulers which do not rely on the knowledge of the source arrival process. Towards that end, we first show that all schedulers (robust or otherwise) which guarantee a maximum queuing delay for each packet are equivalent to a time-varying linear filter. Using the connection between filtering and scheduling, we study the design of optimal power minimizing robust schedulers. Two cases, motivated by filtering connection, are studied in detail. First, a time-invariant robust scheduler is presented and its performance is completely characterized. Second, we present the optimal time-varying robust scheduler, and show that it has a very intuitive time water-filling structure. We also present upper and lower bounds on the performance of power-minimizing schedulers as a function of delay constraints. The new results form an important step towards understanding of the packet time-scale interactions between physical layer metric of power and network layer metric of delay.