The Power of Oblivious Wireless Power
Magnús M. Halldórsson, Stephan Holzer, Pradipta Mitra, Roger P. Wattenhofer · SIAM Journal on Computing · 2017
We study a fundamental measure for wireless interference in the signal-to-interference noise ratio 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 capacity that is---due to existing lower bounds---asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems involving both oblivious power and arbitrary power control, including connectivity, secondary spectrum auctions, and dynamic packet scheduling. We also show that the price of oblivious power---the relative increase in capacity possible when using unconstrained power control---is only doubly logarithmic in the maximum link length.