TY - JOUR
T1 - Queue-proportional rate allocation with per-link information in multihop wireless networks
AU - Li, Bin
AU - Srikant, R.
N1 - Funding Information:
We would like to thank the anonymous reviewers for their very helpful suggestions, and pointing out a minor error in the proof of Proposition 3 in the initial version of the paper. This work is supported in part by NSF grant CNS-1161404, ONR Grant N00014-13-1-003, and DTRA grants HDTRA1-13-1-0030 and HDTRA1-15-1-0003.
Publisher Copyright:
© 2016, Springer Science+Business Media New York.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here, we propose another algorithm, called Queue-Proportional Rate Allocation (QPRA), which also only uses per-link queues and allocates service rates to links in proportion to their queue lengths, and employs the Serve-In-Random-Order queueing discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA algorithm achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.
AB - The backpressure scheduling algorithm for multihop wireless networks is known to be throughput optimal, but it requires each node to maintain per-destination queues. Recently, a clever generalization of processor sharing has been proposed which is also throughput optimal, but which only uses per-link queues. Here, we propose another algorithm, called Queue-Proportional Rate Allocation (QPRA), which also only uses per-link queues and allocates service rates to links in proportion to their queue lengths, and employs the Serve-In-Random-Order queueing discipline within each link. Through fluid limit techniques and using a novel Lyapunov function, we show that the QPRA algorithm achieves the maximum throughput. We demonstrate an advantage of QPRA by showing that, for the so-called primary interference model, it is able to develop a low-complexity scheduling scheme which approximates QPRA and achieves a constant fraction of the maximum throughput region, independent of network size.
KW - Fluid limit analysis
KW - Low-complexity algorithm design
KW - Lyapunov function
KW - Maximum throughput
KW - Multihop networks
KW - Resource allocation
UR - http://www.scopus.com/inward/record.url?scp=84976484484&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976484484&partnerID=8YFLogxK
U2 - 10.1007/s11134-016-9490-1
DO - 10.1007/s11134-016-9490-1
M3 - Article
AN - SCOPUS:84976484484
SN - 0257-0130
VL - 83
SP - 329
EP - 359
JO - Queueing Systems
JF - Queueing Systems
IS - 3-4
ER -