Low degree connectivity of ad-hoc networks via percolation

Emilio De Santis, Fabrizio Grandoni, Alessandro PanconesiAdvances 2010 · DOI

Introduction

In the design of wireless ad-hoc networks, a fundamental challenge is ensuring global connectivity while minimizing the local burden on individual devices. When $n$ devices are distributed uniformly at random in a region, they must autonomously determine their transmission radii to form a communication graph. A high transmission power ensures connectivity but leads to rapid battery depletion and high signal interference. Conversely, low power saves energy but risks fragmenting the network into isolated clusters.

The ideal solution is a network that is both connected and sparse. Specifically, we seek a graph where the average degree is constant ($O(1)$) and the maximum degree is minimized (ideally $O(\log n)$), all while being constructed via an efficient distributed protocol. This paper presents the first such protocols that achieve these bounds in poly-logarithmic time.

The Two-Phase Distributed Protocol

The authors propose a strategy divided into two distinct phases: the formation of a giant component and the integration of isolated "lakes."

Phase 1: The Local Connection Rule

Each node independently identifies and connects to its $K$ closest neighbors. This is a purely local operation. The core theoretical contribution of this work is the proof that there exists a universal constant $K$, independent of $n$, such that this simple rule results in a unique "giant component" containing $\Theta(n)$ nodes with high probability.

Phase 2: The Cleanup Phase

While the giant component covers the vast majority of the network, some nodes will inevitably remain in small, isolated components. The authors characterize these as "lakes." A critical insight is that these lakes are not arbitrarily large; their size is bounded by $O(\log^2 n)$.

To achieve full connectivity, nodes must determine if they are part of the giant component. The authors provide a distributed probabilistic test: if a node's connected component exceeds a specific logarithmic threshold, it is almost certainly part of the giant component. Nodes that fail this test (those in "lakes") gradually increase their transmission power until they encounter a node belonging to the giant component, thereby merging the fragments into a single connected graph.

Theoretical Framework: Percolation and Coupling

The success of these protocols is rooted in Percolation Theory. To analyze the random geometric graph, the authors map the continuous unit square onto a discrete grid. By demonstrating that the cells of this grid "percolate"—meaning they form a massive, connected structure—they can infer the existence of the giant component in the underlying device network.

A technical challenge in this analysis is the dependency between node locations. The authors utilize a "coupling" technique to relate the fixed $n$-point distribution to a Poisson point process, which is more mathematically tractable. This allows them to prove that the "lakes" are small and that the power required to bridge them does not violate the desired degree bounds.

Results and Performance

The paper evaluates two variations of the protocol:

  • Algorithm A: Prioritizes speed, terminating in $O(\log^2 n)$ rounds, resulting in a maximum degree of $O(\log^2 n)$.
  • Algorithm B: Prioritizes sparseness, terminating in $O(\log^3 n)$ rounds, but achieving a tighter maximum degree of $O(\log n)$.

Both algorithms maintain a constant average degree of $O(1)$. Furthermore, the total power consumption is shown to be near-optimal, scaling with the area of the deployment region.

Discussion and Limitations

While these protocols provide strong theoretical guarantees, several practical considerations remain. The algorithms currently require nodes to have a rough estimate of the total population $n$ to set appropriate thresholds. Additionally, the model assumes an idealized 2D environment. In real-world scenarios with 3D topologies or physical obstacles, the percolation thresholds ($K$) may vary.

Despite these abstractions, the work establishes a vital link between percolation theory and distributed computing, proving that global connectivity in ad-hoc networks can be achieved with remarkably low local connectivity.

Summary updated

Abstract

Consider the following classical problem in ad-hoc networks. Suppose that n devices are distributed uniformly at random in a given region. Each device is allowed to choose its own transmission radius, and two devices can communicate if and only if they are within the transmission radius of each other. The aim is to (quickly) establish a connected network of low average and maximum degree. In this paper we present the first efficient distributed protocols that, in poly-logarithmically many rounds and with high probability, set up a connected network with O (1) average degree and O (log n ) maximum degree. Our algorithms are based on the following result, which is a nontrivial consequence of classical percolation theory. Suppose that each device sets up its transmission radius in order to reach the K closest devices. There exists a universal constant K (independent of n ) such that, with high probability, there will be a unique giant component (i.e. a connected component of size Θ( n )). Furthermore, all remaining components will be of size O (log 2 n ). This leads to an efficient distributed probabilistic test for membership in the giant component, which can be used in a second phase to achieve full connectivity.
BibTeX
@inproceedings{santis2010low,
  author = {Emilio De Santis and Fabrizio Grandoni and Alessandro Panconesi},
  title = {{Low degree connectivity of ad-hoc networks via percolation}},
  booktitle = {Advances},
  year = {2010},
  doi = {10.1239/aap/1275055242},
}
Figure