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

We 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, we 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, we use the concept of vertex augmentation, and for a given M, the family of parameterized algorithms are proposed and the tradeoffs among throughput, complexity, and delay are studied.