Optimal delay bound for maximum weight scheduling policy in wireless networks

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.