Maximal Scheduling in Wireless Ad Hoc Networks With Hypergraph Interference Models

This paper proposes a hypergraph interference model for the scheduling problem in wireless ad hoc networks. The proposed hypergraph model can take the sum interference into account and, therefore, is more accurate as compared with the traditional binary graph model. Further, different from the global signal-to-interference-plus-noise ratio (SINR) model, the hypergraph model preserves a localized graph-theoretic structure and, therefore, allows the existing graph-based efficient scheduling algorithms to be extended to the cumulative interference case. Finally, by adjusting certain parameters, the hypergraph can achieve a systematic tradeoff between the interference approximation accuracy and the user node coordination complexity during scheduling. As an application of the hypergraph model, we consider the performance of a simple distributed scheduling algorithm, i.e., maximal scheduling, in wireless networks. We propose a lower bound stability region for any maximal scheduler and show that it achieves a fixed fraction of the optimal stability region, which depends on the interference degree of the underlying hypergraph. We also demonstrate the interference approximation accuracy of hypergraphs in random networks and show that hypergraphs with small hyperedge sizes can model the interference quite accurately. Finally, the analytical performance is verified by simulation results.