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 (SIRO) discipline within each link. Through uid limit techniques and using a novel Lyapunov function, we show that the QPRA 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 language | English (US) |
---|---|
Pages (from-to) | 97-108 |
Number of pages | 12 |
Journal | Performance Evaluation Review |
Volume | 43 |
Issue number | 1 |
DOIs | |
State | Published - Jun 24 2015 |
Event | ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2015 - Portland, United States Duration: Jun 15 2015 → Jun 19 2015 |
Keywords
- Fluid limit analysis
- Low-complexity scheduler design
- Lyapunov functions
- Maximum throughput
- Multihop wireless networks
- Resource allocation
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications