TY - GEN
T1 - On the limitations of randomization for Queue-Length-Based Scheduling in wireless networks
AU - Li, Bin
AU - Eryilmaz, Atilla
PY - 2011
Y1 - 2011
N2 - Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this work, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule non-conflicting transmissions. This framework not only models many existing schedulers operating under a time-scale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. Our main results are the identification of necessary and sufficient conditions on the network topology and on the functional forms used in the randomization for throughput-optimality. Our analysis reveals an exponential and a sub-exponential class of functions that exhibit differences in the throughput-optimality. Also, we observe the significance of the network's scheduling diversity for throughput-optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.
AB - Randomization is a powerful and pervasive strategy for developing efficient and practical transmission scheduling algorithms in interference-limited wireless networks. Yet, despite the presence of a variety of earlier works on the design and analysis of particular randomized schedulers, there does not exist an extensive study of the limitations of randomization on the efficient scheduling in wireless networks. In this work, we aim to fill this gap by proposing a common modeling framework and three functional forms of randomized schedulers that utilize queue-length information to probabilistically schedule non-conflicting transmissions. This framework not only models many existing schedulers operating under a time-scale separation assumption as special cases, but it also contains a much wider class of potential schedulers that have not been analyzed. Our main results are the identification of necessary and sufficient conditions on the network topology and on the functional forms used in the randomization for throughput-optimality. Our analysis reveals an exponential and a sub-exponential class of functions that exhibit differences in the throughput-optimality. Also, we observe the significance of the network's scheduling diversity for throughput-optimality as measured by the number of maximal schedules each link belongs to. We further validate our theoretical results through numerical studies.
UR - http://www.scopus.com/inward/record.url?scp=79960858430&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960858430&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2011.5935086
DO - 10.1109/INFCOM.2011.5935086
M3 - Conference contribution
AN - SCOPUS:79960858430
SN - 9781424499212
T3 - Proceedings - IEEE INFOCOM
SP - 2597
EP - 2605
BT - 2011 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2011
Y2 - 10 April 2011 through 15 April 2011
ER -