# Approaching Throughput-optimality in a Distributed CSMA Algorithm with Contention Resolution

### Libin Jiang and Jean Walrand

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2009-37

March 6, 2009

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-37.pdf

It was shown recently that CSMA (Carrier Sense Multiple Access)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One key assumption is that the sensing time is negligible, so that there is no collision. In this paper, we remove this idealized assumption by studying CSMA-based scheduling algorithms with collisions. First, we provide a model and give an explicit throughput formula which takes into account the cost of contention resolution. The formula has a simple form due to the quasi-reversibility structure of the model. Second, we show that the algorithms in [Allerton'08] can be extended to approach throughput optimality in this case. Finally, sufficient conditions are given to ensure the convergence and stability of the proposed algorithms.

BibTeX citation:

@techreport{Jiang:EECS-2009-37, Author = {Jiang, Libin and Walrand, Jean}, Title = {Approaching Throughput-optimality in a Distributed CSMA Algorithm with Contention Resolution}, Institution = {EECS Department, University of California, Berkeley}, Year = {2009}, Month = {Mar}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-37.html}, Number = {UCB/EECS-2009-37}, Abstract = {It was shown recently that CSMA (Carrier Sense Multiple Access)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One key assumption is that the sensing time is negligible, so that there is no collision. In this paper, we remove this idealized assumption by studying CSMA-based scheduling algorithms with collisions. First, we provide a model and give an explicit throughput formula which takes into account the cost of contention resolution. The formula has a simple form due to the quasi-reversibility structure of the model. Second, we show that the algorithms in [Allerton'08] can be extended to approach throughput optimality in this case. Finally, sufficient conditions are given to ensure the convergence and stability of the proposed algorithms.} }

EndNote citation:

%0 Report %A Jiang, Libin %A Walrand, Jean %T Approaching Throughput-optimality in a Distributed CSMA Algorithm with Contention Resolution %I EECS Department, University of California, Berkeley %D 2009 %8 March 6 %@ UCB/EECS-2009-37 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-37.html %F Jiang:EECS-2009-37