Distributed Algorithms for Maximum Link Scheduling in the Physical Interference Model
A fundamental problem in wireless networks is the maximum link scheduling problem. Constant factor approximation algorithms have been developed for this problem, but low complexity distributed algorithms that give the same approximation guarantee in the SINR model are not known. Distributed algorithms are especially challenging in this model, because of its non-locality. In this paper, the authors develop a set of fast distributed algorithms in the SINR model, providing constant approximation for the maximum link scheduling problem under uniform power assignment.