Distributed utility-optimal scheduling with finite buffers

In this paper, we propose a distributed cross-layer scheduling algorithm for 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 s...

Full description

Saved in:
Bibliographic Details
Main Authors: Xue, Dongyue, Murawski, Robert, Ekici, Eylem
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Delay
Schedules
Scheduling algorithms
Stability analysis
Throughput
Wireless networks
Online Access:Request 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 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. 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.