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

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

2011-07-16

arxiv.org/abs/1107.3199v1

Computer Science

Information Theory

27 pages, 7 figures

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Performance Guarantee under Longest-Queue-First Schedule in Wireless Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-549900