Optimal delay bound for maximum weight scheduling policy in wireless networks

Authors:
Publisher website
Google Scholar
Abstract
We provide an improved bound for the expectation of the stationary delay under the maximum weight scheduling (MWS) policy in one-hop wireless networks. In the model, the interference of the links is characterized by an interference graph G=(V, E). For a vector μ ϵ R |V| + , let χ f (G, μ) be the weighted fractional coloring number for the graph G under the weight vector μ. For an arrival rate vector λ in the capacity region, we define a quantity ε (λ) to be the unique value satisfying the condition χ f (G, λ+ε (λ) e) = 1, where e = (1, 1,..., 1) T . We show that the stationary delay is upper-bounded by B(2(Σ i=1 |V| λ i ) ε (λ) ), where B is a constant depending on the arrival process. We show that the new bound is the tightest single-parameter bound obtainable with an often-used analytical framework. Generalizing the above, we also provide the tightest bounds for all MWS-w policies.

This publication has 20 references indexed in Scilit: