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(root V). 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 "superfast" scheduling mode that beats the Berry-Gallager bound in the exceptional case when power functions are piecewise linear.