Nearly optimal bounds for distributed wireless scheduling in the SINR model

摘要

We study the wireless scheduling problem in the SINR model. More specifically, given a set of links, each a sender-receiver pair, we wish to partition (or schedule) the links into the minimum number of slots, each satisfying interference constraints allowing simultaneous transmission. In the basic problem, all senders transmit with the same uniform power. We analyze a randomized distributed scheduling algorithm proposed by Kesselheim and Vocking, and show that it achieves -approximation, an improvement of a logarithmic factor. This matches the best ratio known for centralized algorithms and holds in arbitrary metric space and for every length-monotone and sublinear power assignment. We also show that every distributed algorithm uses slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.