Distributed Approximation Algorithms for Maximum Link Scheduling and Local Broadcasting in the Physical Interference Model
In this paper, the authors develop the first rigorous distributed algorithm for link scheduling in the SINR model under any length-monotone sub-linear power assignments (including linear, square-root, uniform power assignments). Their algorithms give constant factor approximation guarantees, matching the bounds of the sequential algorithms for these problems, with provable bounds on the running time in terms of the graph topology. They also study a related and fundamental problem of local broadcasting for uniform power levels, and obtain similar bounds. These problems are much more challenging in the SINR model than in the more standard graph based interference models, because of the non-locality of the SINR model.