Scheduling Stochastic Traffic With End-to-End Deadlines in Multi-hop Wireless Networks

摘要

Scheduling deadline-constrained packets in multihop networks has received increased attention recently. However, there is very limited work on this problem for wireless networks where links are subject to interference. The existing algorithms either provide approximation ratio guarantees which diminish in quality as parameters of the network scale, or hold in an asymptotic regime when the time horizon, network bandwidth, and packet arrival rates are scaled to infinity, which limits their practicality. While attaining a constant approximation ratio has been shown to be impossible in the worst-case traffic setting, it is unclear if the same holds under stochastic traffic, in a non-asymptotic setting. In this work, we show that, in the stochastic traffic setting, constant approximation ratio or near-optimal algorithms can be achieved. Specifically, we propose algorithms that attain Ω((1 − ϵ)/β) or Ω(1 − ϵ) fraction of the optimal value, when the number of channels is ${\text{C}} = \Omega \left( {\frac{{\log (L/\varepsilon )}}{{{\varepsilon ^2}}}} \right)$ or ${\text{C}} = \Omega \left( {\frac{{{\chi ^ \star }\log (L/\varepsilon )}}{{{\varepsilon ^3}}}} \right)$respectively, where L is the maximum route length of packets, χ⋆is the fractional chromatic number of the network’s interference graph, and β is its interference degree. This marks the first near-optimal results under nontrivial traffic and bandwidth assumptions in a non-asymptotic regime.