Queue-Affectance-based Scheduling in Multi-hop Wireless Networks under SINR Interference Constraints

Most distributed wireless scheduling schemes that are provably efficient have been developed under the protocol model, which describes interference constraints in a binary form. However, the oversimplified interference model imposes fundamental limitations on the performance in practice. The signal-to-interference-plus-noise-ratio (SINR) based interference model is more accurate and realistic accounting for the cumulative nature of the interference signals, but its complex structure makes the design of scheduling schemes much more challenging. In this paper, we focus on the scheduling performance under the SINR model and develop random access scheduling schemes that are amenable to implement in a distributed fashion with only local information. We analytically show that they are provably efficient under the SINR model, and through simulations demonstrate that they empirically perform better than the theoretical performance bound.