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

Bin Li, R. Srikant

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)329-359
Number of pages31
JournalQueueing Systems
Volume83
Issue number3-4
DOIs
StatePublished - Aug 1 2016

    Fingerprint

Keywords

  • Fluid limit analysis
  • Low-complexity algorithm design
  • Lyapunov function
  • Maximum throughput
  • Multihop networks
  • Resource allocation

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Cite this