Energy-Aware Wireless Scheduling with Near Optimal Backlog and Convergence Time Tradeoffs

Abstract

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.

14 pages. This material with be presented in part at the IEEE INFOCOM conference, Hong Kong, 2015

Cited by in corpus (1)

• A Simple Convergence Time Analysis of Drift-Plus-Penalty for Stochastic Optimization and Convex Programs