2011/07/16 by Bo Li, Li, Bo, Cem Boyaci +3
Computer Science · Engineering · Mathematics · #Advanced MIMO Systems Optimization #Advanced Wireless Network Optimization #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1107.3199
27 pages, 7 figures
arxiv created 2011/07/16 · openalex publication_date 2011/07/16 · arxiv updated 2011/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, Λ, 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, σ^*(G) Λ, where σ^*(G) is the overall local pooling factor of the interference graph G and σ^*(G) ≤ 1. It has been shown later that LQF achieves a larger rate region, Σ^*(G) Λ, where Σ^ (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.