The power of oblivious wireless power

DOI10.1137/15M1023348zbMATH Open1371.68021arXiv1210.3371OpenAlexW2733091665MaRDI QIDQ5269826FDOQ5269826

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)

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.

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

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

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)

Cites Work

• Dynamic packet scheduling in wireless networks
• How well can graphs represent wireless interference?
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks
• Approximation algorithms for wireless link scheduling with flexible data rates
• Wireless scheduling with power control
• Distributed connectivity of wireless networks
• Distributed contention resolution in wireless networks
• Wireless Communication Is in APX
• The capacity of wireless networks
• Oblivious interference 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
• The power of non-uniform wireless power
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Vertex coloring edge-weighted digraphs
• (Incremental) priority algorithms
• The topology of wireless communication
• Broadcast in the Ad Hoc SINR Model
• Elimination graphs
• On some bounds on the optimum schedule length in the SINR model
• On the impact of geometry on ad hoc communication in wireless networks
• Jamming-resistant learning in wireless networks
• Beyond geometry
• The price of local power control in wireless scheduling
• Wireless connectivity and capacity

Cited In (5)

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

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)