Wireless Scheduling Algorithms With O(1) Overhead for M-Hop Interference Model

The authors develop a family of distributed wireless scheduling algorithms that requires only O(1) complexity for M-hop interference model, for any finite M: the recent technology advances and heterogeneity in wireless networks lead to various interference patterns. Thus, a scheduling algorithm geared into a specific interference model (typically one-hop or two-hop in literature) may be limited in its applicability. In this paper, they tackle this problem, and develop a family of scheduling algorithms (which guarantees throughput and delay performance) for M-hop interference models. To achieve such a goal, they use the concept of vertex augmentation, and for a given M; the family of parameterized algorithms are proposed and the trade-offs among throughput, complexity, and delay are studied.