Libin Jiang and Jean Walrand

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-37

March 6, 2009

http://www2.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},
    Year= {2009},
    Month= {Mar},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-37.html
%F Jiang:EECS-2009-37