Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model

Date Added: Apr 2011
Format: PDF

The authors study the wireless scheduling problem in the physically realistic SINR model. More specifically: they are given a set of n links, each a sender-receiver pair. They would like to schedule the links using the minimum number of slots, using the SINR model of interference among simultaneously transmitting links. In the basic problem, all senders transmit with the same uniform power. In this paper, they provide a distributed O(log n)-approximation for the scheduling problem, matching the best ratio known for centralized algorithms. This is based on an algorithm studied by Kesselheim and Vocking, improving their analysis by a logarithmic factor. They show this to be best possible for any such distributed algorithm.