Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks

Abstract

Efficient link scheduling in a wireless network is challenging. Typical optimal algorithms require solving an NP-hard sub-problem. To meet the challenge, one stream of research focuses on finding simpler sub-optimal algorithms that have low complexity but high efficiency in practice. In this paper, we study the performance guarantee of one such scheduling algorithm, the Longest-Queue-First (LQF) algorithm. It is known that the LQF algorithm achieves the full capacity region, $\Lambda$, when the interference graph satisfies the so-called local pooling condition. For a general graph $G$, LQF achieves (i.e., stabilizes) a part of the capacity region, ${\sigma }^{\ast }(G)\Lambda$, where ${\sigma }^{\ast }(G)$ is the overall local pooling factor of the interference graph $G$ and ${\sigma }^{\ast }(G)\le 1$. It has been shown later that LQF achieves a larger rate region, ${\Sigma }^{\ast }(G)\Lambda$, where ${\Sigma }^{(}G)$ is a diagonal matrix. The contribution of this paper is to describe three new achievable rate regions, which are larger than the previously-known regions. In particular, the new regions include all the extreme points of the capacity region and are not convex in general. We also discover a counter-intuitive phenomenon in which increasing the arrival rate may sometime help to stabilize the network. This phenomenon can be well explained using the theory developed in the paper.

27 pages, 7 figures