Wireless Scheduling with Power Control

DOI10.1007/978-3-642-04128-0_33MaRDI QIDQ3639259zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson

Publication date 29 October 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Abstract: We consider the scheduling of arbitrary wireless links in the physical model of interference to minimize the time for satisfying all requests. We study here the combined problem of scheduling and power control, where we seek both an assignment of power settings and a partition of the links so that each set satisfies the signal-to-interference-plus-noise (SINR) constraints. We give an algorithm that attains an approximation ratio of $O(logncdotloglogDelta)$, where $n$ is the number of links and $Delta$ is the ratio between the longest and the shortest link length. Under the natural assumption that lengths are represented in binary, this gives the first approximation ratio that is polylogarithmic in the size of the input. The algorithm has the desirable property of using an oblivious power assignment, where the power assigned to a sender depends only on the length of the link. We give evidence that this dependence on $Delta$ is unavoidable, showing that any reasonably-behaving oblivious power assignment results in a $Omega(loglogDelta)$-approximation. These results hold also for the (weighted) capacity problem of finding a maximum (weighted) subset of links that can be scheduled in a single time slot. In addition, we obtain improved approximation for a bidirectional variant of the scheduling problem, give partial answers to questions about the utility of graphs for modeling physical interference, and generalize the setting from the standard 2-dimensional Euclidean plane to doubling metrics. Finally, we explore the utility of graph models in capturing wireless interference.

Recommendations

• Wireless scheduling with power control
• The price of local power control in wireless scheduling
• Scheduling and power assignments in the physical model
• Algorithms for scheduling with power control in wireless networks

Cited in

(31)

• Limitations of current wireless link scheduling algorithms
• Constant-approximation for optimal data aggregation with physical interference
• A maximum clique based approximation algorithm for wireless link scheduling under SINR model
• Approximation algorithms for wireless link scheduling with flexible data rates
• Broadcast scheduling problem in SINR model
• Wireless scheduling with power control
• Algorithms for scheduling with power control in wireless networks
• Convergence time of power-control dynamics
• Efficiency of wireless networks: approximation algorithms for the physical interference model
• Distributed wireless link scheduling in the SINR model
• An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models
• Wireless Link Scheduling With Power Control and SINR Constraints
• Wireless Communication Is in APX
• Online capacity maximization in wireless networks
• When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Universal framework for wireless scheduling problems
• Oblivious interference scheduling
• The power of oblivious wireless power
• The price of local power control in wireless scheduling
• Improved Algorithms for Latency Minimization in Wireless Networks
• Wireless capacity with oblivious power in general metrics
• A constant-factor approximation for wireless capacity maximization with power control in the SINR model
• Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs
• Scheduling and power assignments in the physical model
• On some bounds on the optimum schedule length in the SINR model
• Approximation and Online Algorithms
• The power of non-uniform wireless power
• Multi-channel assignment and link scheduling for prioritized latency-sensitive applications
• A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model
• Wireless capacity with arbitrary gain matrix
• Comparative study of approximation algorithms and heuristics for SINR scheduling with power control

This page was built for publication: Wireless Scheduling with Power Control

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