DocumentCode :
1385275
Title :
Approaching Throughput-Optimality in Distributed CSMA Scheduling Algorithms With Collisions
Author :
Jiang, Libin ; Walrand, Jean
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Univ. of California, Berkeley, Berkeley, CA, USA
Volume :
19
Issue :
3
fYear :
2011
fDate :
6/1/2011 12:00:00 AM
Firstpage :
816
Lastpage :
829
Abstract :
It was shown recently that carrier sense multiple access (CSMA)-like distributed algorithms can achieve the maximal throughput in wireless networks (and task processing networks) under certain assumptions. One important but idealized assumption is that the sensing time is negligible, so that there is no collision. In this paper, we study more practical CSMA-based scheduling algorithms with collisions. First, we provide a Markov chain model and give an explicit throughput formula that takes into account the cost of collisions and overhead. The formula has a simple form since the Markov chain is “almost” time-reversible. Second, we propose transmission-length control algorithms to approach throughput-optimality in this case. Sufficient conditions are given to ensure the convergence and stability of the proposed algorithms. Finally, we characterize the relationship between the CSMA parameters (such as the maximum packet lengths) and the achievable capacity region.
Keywords :
Markov processes; carrier sense multiple access; convex programming; distributed algorithms; radio networks; scheduling; telecommunication congestion control; Markov chain model; carrier sense multiple access; collision; convex optimization; distributed CSMA scheduling algorithm; throughput-optimality; transmission-length control algorithm; wireless network; Algorithm design and analysis; Markov processes; Multiaccess communication; Payloads; Scheduling; Throughput; Wireless networks; Carrier sence multiple access (CSMA); Markov chain; convex optimization; distributed scheduling;
fLanguage :
English
Journal_Title :
Networking, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1063-6692
Type :
jour
DOI :
10.1109/TNET.2010.2089804
Filename :
5641633
Link To Document :
بازگشت