  This paper considers a wireless link with randomly arriving data that is
queued and served over a time-varying channel. It is known that any algorithm
that comes within $\epsilon$ of the minimum average power required for queue
stability must incur average queue size at least $\Omega(\log(1/\epsilon))$.
However, the optimal convergence time is unknown, and prior algorithms give
convergence time bounds of $O(1/\epsilon^2)$. This paper develops a scheduling
algorithm that, for any $\epsilon>0$, achieves the optimal
$O(\log(1/\epsilon))$ average queue size tradeoff with an improved convergence
time of $O(\log(1/\epsilon)/\epsilon)$. This is shown to be within a
logarithmic factor of the best possible convergence time. The method uses the
simple drift-plus-penalty technique with an improved convergence time analysis.

Optimization and Control