TY - JOUR
T1 - Q-CSMA
T2 - Queue-length-based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks
AU - Ni, Jian
AU - Tan, Bo
AU - Srikant, R.
N1 - Funding Information:
Manuscript received November 25, 2009; revised April 05, 2011; accepted August 26, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor A. Proutiere. Date of publication December 08, 2011; date of current version June 12, 2012. This work was supported by the NSF under Grant 07-21286, the ARO MURI under Grants W911NF-07-1-0287 and W911NF-08-1-0233, the AFOSR under Grant FA-9550-08-1-0432, and the DTRA under Grant HDTRA1-08-1-0016. An earlier version of this paper was presented at the IEEE Conference on Computer Communications (INFOCOM), San Diego, CA, March 15–19, 2010.
PY - 2012/6
Y1 - 2012/6
N2 - Recently, it has been shown that carrier-sense multiple access (CSMA)-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, in general they may only achieve a fraction of the capacity region. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm that is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single timeslot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate heuristics that lead to very good delay performance while retaining the throughput-optimality property.
AB - Recently, it has been shown that carrier-sense multiple access (CSMA)-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, in general they may only achieve a fraction of the capacity region. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm that is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single timeslot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate heuristics that lead to very good delay performance while retaining the throughput-optimality property.
KW - Carrier-sense multiple access (CSMA)
KW - random access
KW - scheduling algorithms
KW - wireless networks
UR - http://www.scopus.com/inward/record.url?scp=84862566458&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862566458&partnerID=8YFLogxK
U2 - 10.1109/TNET.2011.2177101
DO - 10.1109/TNET.2011.2177101
M3 - Article
AN - SCOPUS:84862566458
SN - 1063-6692
VL - 20
SP - 825
EP - 836
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 3
M1 - 6009216
ER -