Academic
Publications
A refined performance characterization of longest-queue-first policy in wireless networks

A refined performance characterization of longest-queue-first policy in wireless networks,10.1145/1530748.1530758,Bo Li,Cem Boyaci,Ye Xia

A refined performance characterization of longest-queue-first policy in wireless networks   (Citations: 10)
BibTex | RIS | RefWorks Download
One of the major challenges in wireless networking is how to optimize the link scheduling decisions under interference constraints. Recently, a few algorithms have been introduced to address the problem. However, solving the problem to optimality for general wireless interference models is known to be NP-hard. The research community is currently focusing on finding simpler, sub-optimal scheduling algorithms and on characterizing the algorithm performance. In this paper, we address the performance of a specific scheduling policy called Longest Queue First (LQF), which has gained significant recognition lately due to its simplicity and high efficiency in empirical studies. There has been a sequence of studies characterizing the guaranteed performance of the LQF schedule, culminating at the construction of the σ-local pooling concept by Joo et al. [10]. In this paper, we refine the notion of σ-local pooling and use the refinement to capture a larger region of guaranteed performance.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In [17], the authors extended -local pooling to link -local pooling, which provides a refined throughput characterization of GMS...

    Mathieu Leconteet al. Improved Bounds on the Throughput Efficiency of Greedy Maximal Schedul...

    • ...Sparked by the works in [5], Leconte el al. [6] and Li el al. [7] presented some properties of LPF...
    • ...Li el al. [7] gave an alternative definition of LPF and also introduced a refined notion of LPF...
    • ...As the result, the bounding techniques developed in the early works [5] [6] [7] can hardly be employed to derive any tight lower bounds on LPFs under these general interference models...
    • ...This second lower bound has a very short purely graph-theoretic proof, and yet it can imply the lower bound on LPF provided in [5] which has a queuing-theoretic proof in [5] or an alternate proof based on the duality theory of linear programming in [7]...

    Peng-Jun Wanet al. Local pooling factor of multihop wireless networks

    • ...The LoP conditions were recently generalized to provide the σ-Local Pooling (σ-LoP) conditions under which GMS achieves σ% throughput [16], [17] (the conditions were reformulated in [20])...
    • ...Definition 2.4 (σ-SLoP - Xi et. al. [20]): A network graph G satisfies σ-SLoP, if and only if there exists a vector α ∈ [0, 1]|E| such that...
    • ...This definition can also be expressed as a Linear Program [20]...

    Berk Birandet al. Analyzing the Performance of Greedy Maximal Scheduling via Local Pooli...

    • ...There are several recent works that investigate the performance of LQF scheduling under different binary interference models [5,7,12]...
    • ...� We use the �-local pooling notion developed in [7,12] to show that LQF scheduling achieves zero throughput in the worst case...
    • ...We investigate the performance of LQF scheduling under the SINR interference model using the �-local pooling technique [7,12]...
    • ...A set local pooling factor can be calculated by a primal or dual formulation of a special optimization problem [12]...
    • ...It can be observed that the set local pooling factor represents the scaling factor between the most compact timesharing and the least compact time-sharing of maximal schedules [12]...
    • ...Then, we have the following lower bound for a local pooling factor of set L [12]...

    Long Bao Leet al. Longest-queue-first scheduling under SINR interference model

    • ...Using Lemma 5 and Lemma 11 in [3], one can rewrite it as a solution to the following dual problem...
    • ...Lemma 14 in [3] applied to the linear program in (9) gives the following relation for σLMW :...

    Arun Sridharanet al. A Greedy Link Scheduler for Wireless Networks with Gaussian Multiple A...

Sort by: