TY - JOUR
T1 - Low-complexity distributed scheduling algorithms for wireless networks
AU - Gupta, Abhinav
AU - Lin, Xiaojun
AU - Srikant, R.
N1 - Funding Information:
Manuscript received July 10, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor S. Sarkar. First published July 21, 2009; current version published December 16, 2009. This work was supported in part by the NSF under Grants CNS-0626703, CNS-0721286, CNS-0721484, and CNS-0519691 and by a grant from the Purdue Research Foundation. An earlier version of this paper has appeared in the Proceedings of IEEE INFOCOM 2007.
PY - 2009/12
Y1 - 2009/12
N2 - We consider the problem of designing distributed scheduling algorithms for wireless networks. We present two algorithms, both of which achieve throughput arbitrarily close to that of maximal schedules, but whose complexity is low due to the fact that they do not necessarily attempt to find maximal schedules. The first algorithm requires each link to collect local queue-length information in its neighborhood, and its complexity is otherwise independent of the size and topology of the network. The second algorithm, presented for the node-exclusive interference model, does not require nodes to collect queue-length information even in their local neighborhoods, and its complexity depends only on the maximum node degree in the network.
AB - We consider the problem of designing distributed scheduling algorithms for wireless networks. We present two algorithms, both of which achieve throughput arbitrarily close to that of maximal schedules, but whose complexity is low due to the fact that they do not necessarily attempt to find maximal schedules. The first algorithm requires each link to collect local queue-length information in its neighborhood, and its complexity is otherwise independent of the size and topology of the network. The second algorithm, presented for the node-exclusive interference model, does not require nodes to collect queue-length information even in their local neighborhoods, and its complexity depends only on the maximum node degree in the network.
KW - Low-complexity and distributed algorithms
KW - Maximal scheduling
KW - Provable efficiency ratios
KW - Wireless scheduling algorithms
UR - http://www.scopus.com/inward/record.url?scp=72449209168&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=72449209168&partnerID=8YFLogxK
U2 - 10.1109/TNET.2009.2021609
DO - 10.1109/TNET.2009.2021609
M3 - Article
AN - SCOPUS:72449209168
SN - 1063-6692
VL - 17
SP - 1846
EP - 1859
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 6
M1 - 5169943
ER -