Asymptotic critical transmission radii in random geometry graphs over three-dimensional regions

Jie Ding, Shuai Ma, Xiang Wei, Xiaohua Xu, Xinshan ZhuarXiv 2025 · DOI · arXiv

Introduction

The deployment of autonomous swarms, such as unmanned aerial vehicles (UAVs) or underwater robots (UUVs), necessitates robust communication networks. These networks are often modeled as Random Geometric Graphs (RGGs), where nodes are distributed within a volume and links are established between any two nodes within a transmission radius $r_n$. Ensuring $k$-connectivity—the property that the network remains connected after the removal of any $k-1$ nodes—is a primary design objective. While well-studied in 2D, 3D environments introduce significant geometric complexities, particularly regarding boundary effects.

Methodology and Geometric Framework

The analysis employs a rigorous probabilistic framework based on Poissonization, treating node locations as a Poisson point process before extending results to a fixed number of nodes $n$ via de-Poissonization. A central challenge in 3D RGGs is the "clipping" of a node's transmission volume when it is located near the boundary $\partial \Omega$ of the region.

Clipping of a transmission sphere by a curved boundary surface.

To quantify these effects, the authors analyze the volume of spherical segments formed by the intersection of the transmission sphere and the region $\Omega$. This involves detailed geometric modeling of the boundary's local curvature and its impact on the available connectivity volume for peripheral nodes.

Geometric parameters for sphere segment volume calculation.

Key Insights: The Role of Surface Area

A pivotal finding of this research is the fundamental difference between 2D and 3D connectivity. In 2D RGGs, boundary effects are often negligible for the leading terms of the critical radius. However, in 3D, the surface area of $\partial \Omega$ directly influences the probability of isolated nodes or small disconnected components. The study proves that the radius required for every node to have at least $k$ neighbors (minimum degree $k$) is asymptotically identical to the radius required for the entire graph to be $k$-connected.

Asymptotic Results

The authors derive an explicit expression for the critical transmission radius $r_n$:

$$r_n = \left( \frac{\log n + (\frac{3k}{2} - 1) \log \log n + \xi}{\pi n} \right)^{1/3}$$

where $n$ is the number of nodes, $k$ is the desired connectivity level, and $\xi$ is a constant determined by the boundary's surface area and the target connectivity probability. The probability of $k$-connectivity follows a double exponential distribution, $P(\text{connected}) \to \exp(-e^{-c})$, providing a precise tool for engineering reliable swarm communications.

Conclusion

This work provides the first exact asymptotic formulas for $k$-connectivity in 3D RGGs over regions with smooth boundaries. By identifying the critical impact of surface area, it bridges the gap between theoretical 2D models and practical 3D deployments of robotic swarms. Future research may extend these results to non-uniform node distributions and dynamic, mobile networks.

Summary updated

Abstract

This article presents the precise asymptotical distribution of two types of critical transmission radii, defined in terms of k-connectivity and the minimum vertex degree, for random geometry graphs distributed over three-dimensional regions.
BibTeX
@misc{ding2025asymptotic,
  author = {Jie Ding and Shuai Ma and Xiang Wei and Xiaohua Xu and Xinshan Zhu},
  title = {{Asymptotic critical transmission radii in random geometry graphs over three-dimensional regions}},
  year = {2025},
  eprint = {2511.17046},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.17046},
}
Figure