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 ε of the minimum average power required for queue stability must incur average queue size at least Ω(log(l/ε)). However, the optimal convergence time is unknown, and prior algorithms give convergence time bounds of O(l/ε2). This paper shows that it is possible to achieve the optimal O(log(l/ε)) average queue size tradeoff with an improved convergence time of O(log(l/ε)/ε). Further, 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.