The Case for Addressing the Ordering Effect in Interference-Limited Wireless Scheduling

Scheduling channel access for interference control is a basic building block of wireless networking. Despite much work in this area, the existing algorithms did not explicitly address the impact of link ordering (i.e., the order in which links are added to the schedule of a time slot) on receiver-side interference accumulation and thus on optimal scheduling. Towards understanding the importance of considering the ordering effect, we formulate the concept of interference budget, and, by modeling the scheduling problem as a knapsack problem, we propose the scheduling algorithm iOrder that maximizes the schedulability of future channel access when scheduling concurrent transmissions. When selecting concurrent transmitters for a time slot, more specifically, iOrder tries to maximize the additional interference that can be tolerated by all the receivers while satisfying the application requirement on link reliability. We analyze the approximation ratio of iOrder, and, through extensive simulation and testbed-based measurement, we observe that addressing the ordering effect can improve the performance of existing algorithms by a significant margin in the case of both backlogged and online traffic, for instance, improving the throughput and reducing the latency of the well-known algorithm LQF by a factor up to 2 and 24, respectively. Thus our study demonstrates the importance of explicitly addressing the ordering effect in wireless scheduling, which opens up new avenues for future research and for optimizing wireless network performance.