TY - GEN
T1 - Delay and effective throughput of wireless scheduling in heavy traffic regimes
T2 - 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'09
AU - Yi, Yung
AU - Zhang, Junshan
AU - Chiang, Mung
PY - 2009
Y1 - 2009
N2 - Distributed scheduling algorithms for wireless ad hoc networks have received substantial attention over the last decade. The complexity levels of these algorithms span a wide spectrum, ranging from no message passing to constant/polynomial time complexity, or even exponential complexity. However, by and large it remains open to quantify the impact of message passing complexity on throughput and delay. In this paper, we study the effective throughput and delay performance in wireless scheduling by explicitly considering complexity through a vacation model, where signaling complexity is treated as "vacations" and data transmissions as "ser-vices,"with a focus on delay analysis in heavy traffic regimes. We analyze delay performance in two regimes of vacation models, depending on the relative lengths of data transmission and vacation periods. State space collapse properties proved here enable a significant dimensionality reduction in the challenging problem of delay characterization. We then explore engineering implications and quantify intuitions based on the heavy traffic analysis.
AB - Distributed scheduling algorithms for wireless ad hoc networks have received substantial attention over the last decade. The complexity levels of these algorithms span a wide spectrum, ranging from no message passing to constant/polynomial time complexity, or even exponential complexity. However, by and large it remains open to quantify the impact of message passing complexity on throughput and delay. In this paper, we study the effective throughput and delay performance in wireless scheduling by explicitly considering complexity through a vacation model, where signaling complexity is treated as "vacations" and data transmissions as "ser-vices,"with a focus on delay analysis in heavy traffic regimes. We analyze delay performance in two regimes of vacation models, depending on the relative lengths of data transmission and vacation periods. State space collapse properties proved here enable a significant dimensionality reduction in the challenging problem of delay characterization. We then explore engineering implications and quantify intuitions based on the heavy traffic analysis.
KW - Complexity
KW - Heavy-traffic
KW - Scheduling
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=70450186013&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70450186013&partnerID=8YFLogxK
U2 - 10.1145/1530748.1530757
DO - 10.1145/1530748.1530757
M3 - Conference contribution
AN - SCOPUS:70450186013
SN - 9781605585314
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 55
EP - 64
BT - MobiHoc'09 - Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing
Y2 - 18 May 2009 through 21 May 2009
ER -