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

作者：Kang Xiaohan^*; Jaramillo Juan Jose; Ying Lei

来源：Queueing Systems, 2015, 80(3): 273-291.

DOI：10.1007/s11134-015-9441-2

• Queueing networks
• Stability
• Longest-queue-first scheduling
• Linear networks
• Fluid limit
• Throughput optimality
• Multihop traffic

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.

• 出版日期2015-7