Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model

Details Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model

2011-04-27

arxiv.org/abs/1104.5200v1

Computer Science

Data Structures and Algorithms

to appear in ICALP 2011 (Track C)

Scientific paper

We study the wireless scheduling problem in the physically realistic SINR model. More specifically: we are given a set of $n$ links, each a sender-receiver pair. We 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 work, we 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 V\"ocking, improving their analysis by a logarithmic factor. We show this to be best possible for any such distributed algorithm. Our analysis extends also to linear power assignments, and as well as for more general assignments, modulo assumptions about message acknowledgement mechanisms.

Affiliated with

Also associated with

No associations

Rating

Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-476254