Percolation on the Information-Theoretically Secure Signal to Interference Ratio Graph

Rahul Vaze, Srikanth K. Iyer

Abstract

This paper investigates the conditions for global, secure connectivity in a wireless network subject to both mutual interference and potential eavesdropping. We model the network as a Secure Signal to Interference plus Noise Ratio (SINR) Graph (SSG) consisting of two independent Poisson point processes (PPPs) in $\mathbb{R}^2$: legitimate nodes with intensity $\lambda$ and eavesdropper nodes with intensity $\lambda_E$. A secure directed edge exists between two legitimate nodes if the signal strength at the intended receiver exceeds the signal strength at any eavesdropper, accounting for interference from other legitimate transmissions and an interference suppression parameter $\gamma$. We demonstrate a phase transition in this model: for any finite $\lambda_E$, there exists a critical intensity $\lambda_c$ such that for $\lambda > \lambda_c$, an infinite connected component (percolation) emerges for sufficiently small $\gamma$. Conversely, we identify a sub-critical regime where eavesdropper-based structures preclude such connectivity.

Introduction

In the design of wireless communication systems, two fundamental challenges often conflict: the need for reliable connectivity in the presence of interference and the requirement for information-theoretic security against eavesdroppers. Traditionally, these problems have been studied in isolation. SINR graphs typically focus on how the collective interference of simultaneous transmissions affects the ability of a network to form a "giant component" of connectivity. On the other hand, secrecy graphs focus on the spatial distribution of eavesdroppers, often assuming that legitimate nodes do not interfere with one another (e.g., by using orthogonal frequency channels).

In realistic, large-scale wireless environments, these phenomena are coupled. Legitimate users transmit simultaneously, creating a background of interference that impacts both intended receivers and unauthorized interceptors. This paper addresses the Secure SINR Graph (SSG), a model where a link is considered viable only if the SINR at the receiver is strictly superior to the SINR at any potential eavesdropper. Because this threshold depends on the relative locations of all nodes in the network, the connectivity of a single link becomes a complex random variable, necessitating a rigorous treatment via continuum percolation theory.

The Secure SINR Model

The network is modeled using two independent Poisson Point Processes (PPPs) in a two-dimensional plane:

  1. Legitimate Nodes ($\Phi$): Distributed with intensity $\lambda$.
  2. Eavesdropper Nodes ($\Phi_E$): Distributed with intensity $\lambda_E$.

A directed edge exists from node $A$ to node $B$ if the signal received at $B$ is "secure." This security is defined by an advantage in the signal-to-interference ratio. A key parameter in this model is $\gamma$, the interference suppression parameter (or processing gain). Legitimate receivers are assumed to have the capability to suppress interference from other legitimate nodes through coding or signal processing, whereas eavesdroppers—lacking the specific code—cannot. This asymmetry is the mathematical foundation that allows secure communication to persist even in high-interference environments.

Methodology and Analytical Framework

The authors employ stochastic geometry and continuum percolation to determine the conditions under which the network achieves global connectivity.

Super-critical Regime: Lattice Mapping

To prove that an infinite secure component can form, the authors utilize a mapping technique. The 2D plane is tiled into a square lattice, where an edge in the discrete lattice is defined as "open" if specific local conditions are met within the corresponding area of the continuous plane. These conditions include the presence of at least one legitimate node, the absence of eavesdroppers in a critical radius, and a bounded level of aggregate interference. By proving that this discrete lattice percolates, the authors establish that the underlying wireless SSG also percolates for sufficiently high $\lambda$ and low $\gamma$.

Sub-critical Regime: Dual Graph Blocking

To identify the limits of connectivity, the authors define a "blocking" graph. In the sub-critical regime, where the density of legitimate nodes $\lambda$ is too low relative to $\lambda_E$, the eavesdroppers effectively form a geometric barrier. By showing that a graph defined over eavesdropper connections can form an infinite structure that surrounds and isolates legitimate nodes, the authors prove that no infinite legitimate component can exist below a certain threshold $\lambda_0$.

Key Insights

  • The Security Advantage: The model highlights that coordination (interference suppression) is the primary advantage of legitimate users. Without the parameter $\gamma$ providing an asymmetry between the receiver and the eavesdropper, secure percolation would be significantly more difficult to achieve in dense networks.
  • Binary Phase Transitions: Connectivity in secure networks is not a linear progression. The research proves a "sharp" transition: once the density of legitimate users crosses a critical threshold $\lambda_c$, the network transforms from a collection of isolated clusters into a globally connected system.
  • Universal Lower Bound: The study shows that the case with zero interference ($\gamma = 0$) serves as a universal lower bound. If a network cannot achieve percolation in an interference-free environment, it is physically impossible to achieve it when interference is introduced.

Conclusion and Future Work

This work provides a theoretical foundation for understanding the scaling laws of secure wireless networks. It proves that for any finite density of eavesdroppers, global secure connectivity is possible provided the legitimate node density is sufficiently high and interference suppression techniques are employed.

However, several avenues for future research remain. The current model assumes static node positions; incorporating mobility would introduce temporal dynamics into the percolation thresholds. Additionally, the study focuses on "out-components" (one-way security). Future work could extend these results to bi-directional secure connectivity, which is essential for interactive protocols. Finally, while the path-loss models used are broad, further refinement for complex urban environments with heavy shadowing would enhance the practical application of these theoretical bounds.

Summary updated

Abstract

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes (PPPs) in $\bbR ^2$ of intensities $\lambda$ and $\lambda_E$ respectively. A directed edge from one legitimate node $A$ to another legitimate node $B$ exists provided the strength of the {\it signal} transmitted from node $A$ that is received at node $B$ is higher than that received at any eavesdropper node. The strength of the received signal at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter $\gamma$. The graph is said to percolate when there exists an infinite connected component. We show that for any finite intensity $\lambda_E$ of eavesdropper nodes, there exists a critical intensity $\lambda_c < \infty$ such that for all $\lambda > \lambda_c$ the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the sub-critical regime, we show that there exists a $\lambda_0$ such that for all $\lambda < \lambda_0 \leq \lambda_c$ a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.
BibTeX
@article{vaze2014percolation,
  author = {Rahul Vaze and Srikanth K. Iyer},
  title = {{Percolation on the Information-Theoretically Secure Signal to Interference Ratio Graph}},
  journal = {J. Appl. Probab.},
  year = {2014},
  url = {https://openreview.net/forum?id=ZRylrDLMGd},
}
Figure