The power of oblivious wireless power

DOI10.1137/15M1023348MaRDI QIDQ5269826zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, Roger Wattenhofer

Publication date 28 June 2017

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsSINR modelpower controlwireless communicationinductive independencewireless capacityoblivious power

Mathematics Subject Classification ID

Randomized algorithms (68W20) Communication theory (94A05) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Abstract: We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the effectiveness of using oblivious power --- when the power used by a transmitter only depends on the distance to the receiver --- as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves --- due to existing lower bounds --- capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

Recommendations

• The power of non-uniform wireless power
• Wireless capacity with oblivious power in general metrics
• The price of local power control in wireless scheduling
• Wireless Scheduling with Power Control
• Wireless scheduling with power control

Cites work

• (Incremental) priority algorithms
• A constant-factor approximation for wireless capacity maximization with power control in the SINR model
• Approximation algorithms for wireless link scheduling with flexible data rates
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Beyond geometry: towards fully realistic wireless models
• Broadcast in the Ad Hoc SINR Model
• Distributed connectivity of wireless networks
• Distributed contention resolution in wireless networks
• Dynamic packet scheduling in wireless networks
• Elimination graphs
• How well can graphs represent wireless interference?
• Improved Algorithms for Latency Minimization in Wireless Networks
• Jamming-resistant learning in wireless networks
• Oblivious interference scheduling
• On some bounds on the optimum schedule length in the SINR model
• On the impact of geometry on ad hoc communication in wireless networks
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• The capacity of wireless networks
• The power of non-uniform wireless power
• The price of local power control in wireless scheduling
• The topology of wireless communication
• Vertex coloring edge-weighted digraphs
• Wireless Communication Is in APX
• Wireless capacity with oblivious power in general metrics
• Wireless connectivity and capacity
• Wireless scheduling with power control

Cited in

(5)

• The power of non-uniform wireless power
• Network design under general wireless interference
• Spanning trees with edge conflicts and wireless connectivity
• Effective Wireless Scheduling via Hypergraph Sketches
• Wireless capacity with oblivious power in general metrics

This page was built for publication: The power of oblivious wireless power

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