Capacity Achieving Distributed Scheduling With Finite Buffers

In this paper, we propose a distributed cross-layer scheduling algorithm for wireless networks with single-hop transmissions that can guarantee finite buffer sizes and meet minimum utility requirements. The algorithm can achieve a utility arbitrarily close to the optimal value with a tradeoff in the...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2015-04, Vol.23 (2), p.519-532
Main Authors: Dongyue Xue, Murawski, Robert, Ekici, Eylem
Format: Article
Language:English
Subjects:
Congestion control
Delays
distributed implementations
finite buffers
Heuristic algorithms
network scheduling
Schedules
Scheduling algorithms
Throughput
Upper bound
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a distributed cross-layer scheduling algorithm for wireless networks with single-hop transmissions that can guarantee finite buffer sizes and meet minimum utility requirements. The algorithm can achieve a utility arbitrarily close to the optimal value with a tradeoff in the buffer sizes. The finite buffer property is not only important from an implementation perspective, but, along with the algorithm, also yields superior delay performance. In addition, another extended algorithm is provided to help construct the upper bounds of per-flow average packet delays. A novel structure of Lyapunov function is employed to prove the utility optimality of the algorithm with the introduction of novel virtual queue structures. Unlike traditional back-pressure-based optimal algorithms, our proposed algorithm does not need centralized computation and achieves fully local implementation without global message passing. Compared to other recent throughput/utility-optimal CSMA distributed algorithms, we illustrate through rigorous numerical and implementation results that our proposed algorithm achieves far better delay performance for comparable throughput/utility levels.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2014.2303093