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

DOI10.1109/TIT.2012.2201691zbMATH Open1364.90126arXiv1107.3199OpenAlexW2007571354MaRDI QIDQ2989779FDOQ2989779

Authors:

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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, $sigm{a}^{*}(G)Lambda$, where $sigm{a}^{*}(G)$ is the overall local pooling factor of the interference graph $G$ and $sigm{a}^{*}(G)leq1$. It has been shown later that LQF achieves a larger rate region, $Sigm{a}^{*}(G)Lambda$, where $Sigm{a}^{(}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.

Full work available at URL: https://arxiv.org/abs/1107.3199

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Communication networks in operations research (90B18)

Cited In (3)

• Guaranteed quality-of-service wireless access by packet-by-packet generalized processor sharing algorithm
• Subdiffusive Load Balancing in Time-Varying Queueing Systems
• Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks

This page was built for publication: Performance Guarantee Under Longest-Queue-First Schedule in Wireless Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989779)