Node-Based Distributed Channel Access With Enhanced Delay Characteristics

Recent studies in wireless scheduling have shown that carrier-sense multiple access (CSMA) can be made throughput optimal by optimizing over activation rates. However, those throughput optimal CSMA algorithms were found to suffer from poor delay performance, especially at high throughputs where the delay can potentially grow exponentially in the size of the network. Motivated by these shortcomings, in this project we propose a node-based version of the throughput optimal CSMA (NB-CSMA) as opposed to traditional link-based CSMA algorithms, where links were treated as separate entities. Our algorithm is fully distributed and corresponds to glibber dynamics with “Block updates”. 

We show analytically and via simulations that NB-CSMA outperforms conventional link-based CSMA in terms of delay for any fixed-size network. We also characterize the fraction of the capacity region for which the average queue lengths (and the average delay) grow polynomial in the size of the network, for networks with bounded-degree conflict graphs. 

This fraction is no smaller than the fraction known for link-based CSMA, and is significantly larger for many instances of practical wireless ad-hoc networks. Finally, we restrict our focus to the special case of collocated networks, analyze the mean starvation time using a Markov chain with rewards framework and use the results to quantitatively demonstrate the improvement of NB-CSMA over the baseline link-based algorithm.

Keywords: Wireless Networking, Carrier-Sense Multiple Access (CSMA), Scheduling, Starvation, Delay Performance.