Queue-proportional rate allocation with per-link information in multihop wireless networks

Bin Li () and R. Srikant ()
Additional contact information
Bin Li: University of Illinois at Urbana-Champaign
R. Srikant: University of Illinois at Urbana-Champaign

Queueing Systems: Theory and Applications, 2016, vol. 83, issue 3, No 6, 329-359

Abstract: Abstract 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.

Keywords: Resource allocation; Low-complexity algorithm design; Multihop networks; Maximum throughput; Lyapunov function; Fluid limit analysis; 68M20 (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-016-9490-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9490-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-016-9490-1

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().