Wireless Network Algorithmics

Magnús M. Halldórsson, Roger WattenhoferComputing and Software Science 2019 · DOI · DBLP

Abstract

This paper provides a high-level synthesis of a decade's worth of algorithmic progress in wireless networking, moving from simplistic "binary" models to the more realistic physical Signal-to-Interference-plus-Noise Ratio (SINR) model. The authors demonstrate that despite the complexity of additive interference, constant-factor approximation algorithms can be designed for link scheduling and power control by utilizing a metric called "affectance."

Introduction: The Failure of Binary Models

In the early days of wireless research, models like the Radio Network Model (graph-based) or the Disk Model (geometric) were standard. These models are "binary": a node either receives a signal perfectly or experiences total interference.

However, physical reality is additive. Multiple weak signals from distant transmitters can sum up to drown out a nearby sender. Furthermore, signal strength decays gradually according to the path-loss exponent $\alpha$. The fundamental challenge is Link Scheduling: given a set of communication requests, how do we schedule as many as possible simultaneously while ensuring the SINR remains high enough for successful decoding?

Algorithmic Frameworks

The transition to the Physical Model (SINR) requires moving beyond simple greedy approaches that fail to account for cumulative interference.

Algorithm 1: A too-naïve greedy approach to link scheduling that fails to account for the additive nature of interference.

As shown in Algorithm 1, a basic greedy approach only checks for immediate feasibility. The paper introduces more sophisticated methods centered on the concept of Affectance.

The Affectance Metric

Affectance ($a_{l' \to l}$) is a normalized measure of the interference link $l'$ creates on link $l$, relative to $l$'s own signal strength. Because affectance is cumulative, the condition for a successful transmission becomes simple: the sum of affectances from all other active links must be $\le 1$.

Advanced Scheduling and Power Control

  • Algorithm 2 (One-Shot Scheduling): A refined greedy approach using a "bi-feasibility" criterion. It bounds both the interference a link receives and the interference it contributes to others.
  • Algorithm 3 (Power Control): A two-pass algorithm for arbitrary power control. It selects links based on a power-independent measure and then assigns transmission powers in decreasing order of link length to ensure every link overcomes the interference of longer ones.

Key Insights and Evaluation

The performance of these algorithms is evaluated using mathematical proofs and stress tests like the Exponential Chain (nodes at $2^0, 2^1, \dots, 2^n$).

  • Mean Power is the "Goldilocks" Zone: While uniform and linear power strategies fail on the exponential chain, mean power ($l^{\alpha/2}$) balances frugality with robustness against interference.
  • Independence from $\alpha$: In one-dimensional settings, the approximation ratio of the scheduling algorithm is independent of the path-loss exponent.
  • Scalability of $\beta$: Increasing the required signal quality (threshold $\beta$) only increases the schedule length by a constant factor, indicating no sudden "phase transition" in difficulty.

Results and Future Directions

The paper proves that "One-Shot" link scheduling can be solved within a constant factor of the optimum for both uniform and arbitrary power control. Furthermore, Theorem 3 demonstrates that using the right power assignment can provide a linear-factor improvement in throughput compared to uniform power.

Despite these advances, several challenges remain:

  1. The Scheduling Gap: Partitioning all links into the minimum number of slots still only has logarithmic approximations for uniform power.
  2. Distributed Realities: Most results assume a centralized "god's eye view" of the network; efficient distributed algorithms remain a challenge.
  3. Non-Geometric Propagation: Future models must move toward "facts-on-the-ground" signal measurements to account for obstacles and the stochastic nature of real-world wireless links.

Summary updated

BibTeX
@inproceedings{halldorsson2019wireless,
  author = {Magnús M. Halldórsson and Roger Wattenhofer and Magnús M. Halldórsson},
  title = {{Wireless Network Algorithmics}},
  booktitle = {Computing and Software Science},
  year = {2019},
  doi = {10.1007/978-3-319-91908-9\_9},
}
Figure