Date Added: May 2009
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, the authors 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 "Services," with a focus on delay analysis in heavy traffic regimes.