Distributed approximation algorithms for maximum link scheduling and local broadcasting in the physical interference model

In this paper, we develop the first rigorous distributed algorithm for link scheduling in the SINR model under any length-monotone sub-linear power assignments. Our 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. We 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. Our algorithms are randomized and crucially rely on physical carrier sensing for the distributed communication steps. We find that the specific wireless device capability of duplex/halfduplex communication significantly impacts the performance. Our main technique involves the distributed computation of affectance and a construct called a ruling, which are likely to be useful in other scheduling problems in the SINR model. We also study the empirical performance of our algorithms, and find that the performance depends on the topology, and the approximation ratio is very close to the best sequential algorithm.