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.
Introduction
In wireless networking, power control is a critical yet challenging optimization problem. Increasing a transmitter's power strengthens its own signal but simultaneously increases interference for neighboring links. Maximizing wireless capacity—the number of links that can operate concurrently—ideally requires a global optimization where every node's power is a function of every other node's state. However, such global control is computationally NP-complete and impractical for dynamic environments.
A more practical alternative is oblivious power control, where a link's power is determined solely by its own length ($\ell$). While simpler to implement, the theoretical "price" of this simplicity has been a subject of long-standing debate. Previous research suggested a significant capacity gap, often depending on the number of nodes ($n$) or growing linearly with the range of link lengths ($\Delta$). This paper provides a definitive bound, showing that non-uniform oblivious power schemes can achieve capacity within an $O(\log \log \Delta)$ factor of the absolute theoretical optimum—an exponential improvement over previous state-of-the-art bounds.
Theoretical Framework: Inductive Independence in SINR
The authors analyze wireless interference through the lens of weighted inductive independence within the Signal-to-Interference-plus-Noise Ratio (SINR) model. The SINR model provides a realistic physical representation of signal behavior, accounting for path loss and cumulative interference. As a theoretical study, the results are proven for general metric spaces, ensuring applicability to any physical arrangement of nodes that satisfies the triangle inequality.
The core of the structural analysis involves a specific class of power assignments: $P = \ell^{p \cdot \alpha}$, where $\alpha$ is the path-loss constant and $p \in [0, 1]$. This family includes the well-known "mean power" assignment ($p=0.5$). The authors prove two major theorems:
- For this class of power assignments, the interference measure is bounded by a constant ($O(1)$).
- The gap between these oblivious schemes and unrestricted optimal power control is at most $O(\log \log \Delta)$.
Algorithmic Approach
By demonstrating that SINR interference has low inductive independence, the authors show that complex wireless capacity problems share structural similarities with "easy" graph problems. This allows for the application of simple, efficient greedy strategies to solve what would otherwise be intractable interference problems.
As shown in Algorithm 1, a single-pass greedy approach that processes links in increasing order of length can achieve these near-optimal theoretical bounds. This algorithm provides a practical path toward maximizing capacity without the need for complex global coordination.
Key Results and Implications
The theoretical bounds established in this work lead to several significant algorithmic improvements across various networking domains:
- Capacity Approximation: An $O(\log \log \Delta)$-approximation algorithm for capacity maximization relative to the absolute best possible power control.
- Distributed Scheduling: A reduction in complexity for distributed scheduling, achieving an $O(\log n)$ approximation even when accounting for acknowledgment overhead.
- Spectrum Auctions: An $O(\log n)$ improvement in approximation ratios for secondary spectrum auctions.
- Connectivity: Strong connectivity for any set of links can be achieved in $O(\log n \cdot \log \log \Delta)$ time slots, a direct improvement over previous bounds.
Limitations and Future Directions
While these results provide a major leap in theoretical understanding, some constraints remain. The primary theorems assume "non-weak" links—those operating comfortably above the noise floor. While weak links can often be handled separately, the $O(1)$ interference bound does not apply to them directly. Additionally, while the SINR model is robust, it assumes a static environment. Future research could investigate how these bounds adapt to volatile channel conditions, mobility, or the integration of Rayleigh fading effects.
Summary updated