Stability of longest-queue-first scheduling in linear wireless networks with multihop traffic and one-hop interference

摘要

We consider the stability of the longest-queue-first (LQF) scheduling policy in wireless networks with multihop traffic under the one-hop interference model. Although it is well known that the back-pressure algorithm achieves the maximal stability, its computational complexity is prohibitively high. In this paper, we consider LQF, a low-complexity scheduling algorithm, which has been shown to have near-optimal throughput performance in many networks with single-hop traffic flows. We are interested in the performance of LQF for multihop traffic flows. In this scenario, the coupling between queues due to multihop traffic flows makes the local-pooling-factor analysis difficult to perform. Using the fluid-limit techniques, we show that LQF achieves the maximal stability for linear networks with multihop traffic and a single destination on the boundary of the network under the one-hop interference model.