Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks

Tomasz Jurdzinski, Dariusz R. Kowalski, Grzegorz Stachowiak

Broadcasting—the process of disseminating a message from a single source to all nodes in a network—is a fundamental primitive for ad hoc wireless systems like MANETs and VANETs. While many existing protocols rely on randomized heuristics to manage interference, these often lack the rigorous guarantees required for safety-critical applications. This paper provides the first provably efficient, deterministic solutions for broadcasting under the Signal-to-Interference-and-Noise-Ratio (SINR) model.

The Challenge of the SINR Model

Traditional wireless research often utilizes the simplified "Radio Network Model," where a transmission is successful if exactly one neighbor sends a message. However, the physical reality is better captured by the SINR model, where a signal is received only if its strength significantly exceeds the cumulative noise from all other simultaneous transmissions across the network. Deterministic broadcasting in this environment is difficult because interference is global, topology is initially unknown, and nodes must coordinate without the use of randomized back-off timers.

Methodology: Grid-Based Coordination

The authors propose a "divide and conquer" strategy centered on geometric grid partitioning. By dividing the 2D plane into square boxes, the algorithm can manage local and global interference more effectively.

Grid Partitioning and Neighborhoods

The size of the grid boxes is calibrated such that nodes within the same box are guaranteed to be within communication range. This spatial structure allows the algorithm to treat groups of nodes as single logical units during different phases of the broadcast.

Figure 1: Illustration of a grid cell C and its immediate neighboring cells C1 through C8, used to define local coordination areas.

Leader Election

A critical step in the protocol is electing a "leader" node within each box to coordinate transmissions. The paper introduces two versions of this process. If the network granularity $g$ (the ratio of maximum transmission range to minimum node distance) is known, a specialized algorithm is used to rapidly select leaders.

Figure 2: Pseudocode for the GranLeaderElection algorithm, which efficiently selects box leaders when network granularity is known.

Diluted Transmissions

To mitigate global interference, the authors employ a "dilution" technique. Only nodes in boxes separated by a specific distance $d$ are permitted to transmit at the same time. This ensures that the sum of interference from all active senders converges to a small constant, allowing the SINR threshold to be met at target receivers.

Key Results and Complexity

The paper establishes new deterministic upper bounds for broadcast time complexity:

  • General Networks: $O(D \log^2 n)$ rounds, where $D$ is the network diameter and $n$ is the number of nodes.
  • Known Granularity: When $g$ is known, the complexity improves to $O(D \log g)$ rounds.
  • Stochastic Disturbances: In models with random signal fluctuations, the algorithms remain robust, adding only a logarithmic factor to the time complexity ($O(D \log^3 n)$ or $O(D \log g \log n)$).

Conclusion

These results demonstrate that deterministic broadcasting is not only feasible under realistic physical interference models but also highly scalable. By replacing randomized "coin-flips" with geometric coordination and transmission dilution, the authors provide a framework for reliable communication in unpredictable wireless environments. Future work may extend these deterministic guarantees to networks with variable power control and non-Euclidean geometries.

Summary updated

BibTeX
@inproceedings{jurdzinski2013distributed,
  author = {Tomasz Jurdzinski and Dariusz R. Kowalski and Grzegorz Stachowiak},
  title = {{Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks}},
  booktitle = {FCT},
  year = {2013},
  doi = {10.1007/978-3-642-40164-0\_20},
}
Figure