Node Based Distributed Channel Access With Enhanced Delay Characteristics in NS2

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 paper 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 Glauber 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 polynomially 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.