Abstract
We investigate the secure connectivity of wireless sensor networks (WSNs) under the random key distribution scheme of Eschenauer and Gligor (EG). Unlike previous research conducted under the assumption of full visibility, this study assumes a communication model where unreliable wireless links are represented as ON/OFF channels. We present scaling conditions for model parameters to ensure that the network has no isolated nodes and is securely connected with high probability as the number of nodes becomes large. These results are presented as full zero-one laws, providing the first complete analysis of the EG scheme under non-full visibility. Simulations demonstrate that these laws remain valid under the more realistic disk model, supporting conjectures regarding the connectivity of geometric random graphs with randomly deleted edges.
Introduction
Wireless Sensor Networks (WSNs) are frequently deployed in hostile or inaccessible environments, necessitating robust encrypted communications. However, the severe memory and power constraints of sensor nodes preclude the use of traditional public-key cryptography. The Eschenauer-Gligor (EG) scheme addresses this by assigning each node a random subset of keys (a "key ring") from a large global pool. Secure communication between two nodes is possible only if they are within physical transmission range and share at least one common key.
Historically, mathematical analyses of the EG scheme assumed "full visibility," where every node is within range of every other node. In practice, wireless links are limited by distance and environmental factors. If network parameters are dimensioned based on full-visibility assumptions, the resulting network may suffer from significant connectivity gaps. This paper bridges this gap by analyzing the EG scheme under an ON/OFF channel model, where physical links exist probabilistically, providing a more realistic baseline for network design.
Theoretical Framework
The network is modeled as the intersection of two distinct random graphs:
- The Random Key Graph: Represents the EG scheme, where an edge exists if two nodes share at least one key.
- The Erdős-Rényi (ER) Graph: Represents the ON/OFF physical channel, where an edge exists independently between any two nodes with a probability $\alpha$.
Using the method of first and second moments from random graph theory, the study establishes asymptotic zero-one laws. These laws identify sharp phase transitions where the probability of a network property (such as being fully connected) jumps from 0 to 1 as the number of nodes $n$ increases. A critical insight is that the threshold for full connectivity coincides with the threshold for the absence of isolated nodes, meaning that preventing isolation is the primary bottleneck for global connectivity.
Results and Validation
The research establishes a precise scaling law: if the product of the physical link probability $\alpha_n$ and the key-sharing probability $\beta_n$ scales as $\alpha_n \beta_n = c \frac{\log n}{n}$, the network is securely connected with probability 1 if $c > 1$, and disconnected with probability 0 if $c < 1$. This provides a sharp dimensioning guideline ($c=1$) for network engineers, avoiding the over-provisioning of keys which can compromise overall security.
As shown in Figure 1, simulations with $n=500$ nodes and a key pool of $P=10,000$ validate these asymptotic results. The empirical probability of connectivity exhibits a sharp jump exactly at the predicted theoretical thresholds for various values of $\alpha$.
Discussion: The ON/OFF Model as a Proxy
While the ON/OFF model assumes independent link failures, real-world wireless networks are spatial, often modeled by "disk models" where nodes connect if they are within a specific radius $\rho$. A significant finding of this work is that the connectivity behavior of the mathematically tractable ON/OFF model is asymptotically equivalent to the more complex disk model, provided the average number of physical neighbors is matched.
Figure 2 illustrates that the disk model follows the same sharp transition patterns as the ON/OFF model. This empirical evidence supports the long-standing Gupta and Kumar conjecture regarding the connectivity of geometric random graphs with random edge deletions. Future work will focus on providing rigorous mathematical proofs for these zero-one laws specifically within geometric settings.
Summary updated