Optimal Energy and Delay Tradeoffs for Multiuser Wireless Downlinks

We consider the fundamental delay tradeoffs for minimizing energy expenditure in a multiuser wireless downlink with randomly varying channels. First, we extend the Berry-Gallager bound to a multiuser context, demonstrating that any algorithm that yields average power within O(1/V) of the minimum power required for network stability must also have an average queueing delay greater than or equal to Omega(radicV). We then develop a class of algorithms, parameterized by V, that come within a logarithmic factor of achieving this fundamental tradeoff. The algorithms overcome an exponential state-space explosion, and can be implemented in real time without a priori knowledge of traffic rates or channel statistics. Further, we discover a ldquosuperfastrdquo scheduling mode that beats the Berry-Gallager bound in the exceptional case when power functions are piecewise linear.