Nearly optimal bounds for distributed wireless scheduling in the SINR model

DOI10.1007/978-3-642-22012-8_50zbMATH Open1357.68021arXiv1104.5200OpenAlexW2571153928MaRDI QIDQ287982FDOQ287982

Authors: Magnús M. Halldórsson, Pradipta Mitra 

Publication date: 23 May 2016

Published in: Distributed Computing, Automata, Languages and Programming (Search for Journal in Brave)

Abstract: We study the wireless scheduling problem in the SINR model. More specifically, given a set of $n$ links, each a sender-receiver pair, we wish to partition (or emph{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 give a distributed $O(logn)$-approximation algorithm for the scheduling problem, matching the best ratio known for centralized algorithms. It holds in arbitrary metric space and for every length-monotone and sublinear power assignment. It is based on an algorithm of Kesselheim and V"ocking, whose analysis we improve by a logarithmic factor. We show that every distributed algorithm uses $Omega(logn)$ slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.

Full work available at URL: https://arxiv.org/abs/1104.5200

Recommendations

• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Distributed wireless link scheduling in the SINR model
• Wireless Link Scheduling With Power Control and SINR Constraints
• Approximation for a scheduling problem with application in wireless networks
• A maximum clique based approximation algorithm for wireless link scheduling under SINR model
• SINR based maximum link scheduling in wireless mesh networks

zbMATH Keywords

schedulingwireless networksdistributed schedulingSINR modelwireless

Mathematics Subject Classification ID

Randomized algorithms (68W20) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Approximation algorithms for wireless link scheduling with flexible data rates
• Wireless scheduling with power control
• Distributed connectivity of wireless networks
• Algorithms for scheduling with power control in wireless networks
• Distributed contention resolution in wireless networks
• Wireless Communication Is in APX
• Title not available (Why is that?)
• The capacity of wireless networks
• Oblivious interference scheduling
• Connectivity and aggregation in multihop wireless networks
• Maximal independent sets in radio networks
• Improved Algorithms for Latency Minimization in Wireless Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Power of Non-Uniform Wireless Power

Cited In (20)

• Spanning Trees With Edge Conflicts and Wireless Connectivity
• Vertex coloring edge-weighted digraphs
• The Power of Oblivious Wireless Power
• Effective Wireless Scheduling via Hypergraph Sketches
• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Distributed wireless link scheduling in the SINR model
• Generalizing the Square Root Rule for Optimal Periodic Scheduling in Push-Based Wireless Environments
• Distributed \((\varDelta + 1)\)-coloring in the physical model
• Wireless capacity with arbitrary gain matrix
• Conflict graphs and the SINR-capacity of the mean power scheme
• Distributed multiple-message broadcast in wireless ad hoc networks under the SINR model
• Distributed contention resolution in wireless networks
• Token traversal in ad hoc wireless networks via implicit carrier sensing
• An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models
• Wireless Scheduling with Power Control
• A maximum clique based approximation algorithm for wireless link scheduling under SINR model
• Computing large independent sets in a single round
• Network design under general wireless interference
• Limitations of current wireless link scheduling algorithms
• Wireless Communication Is in APX

This page was built for publication: Nearly optimal bounds for distributed wireless scheduling in the SINR model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287982)