Connectivity of Wireless Sensor Networks Secured by Heterogeneous Key Predistribution Under an On/Off Channel Model

Rashad Eletreby, Osman Yagan

TL;DR

This paper provides the mathematical "recipe" for ensuring a heterogeneous wireless sensor network (WSN) remains both secure and connected. By modeling the network as the intersection of a security layer (who has which keys) and a physical layer (who can hear whom), the authors derive precise scaling laws that tell engineers how many keys to distribute to guarantee a fully connected network as it grows in size.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are often deployed in harsh or unreachable environments, making security a top priority. Because these sensors have limited battery and memory, they use "random key predistribution"—nodes are given a random set of keys from a large pool, and two nodes can talk securely only if they share at least one key.

However, most existing mathematical models make two unrealistic assumptions:

  1. Homogeneity: They assume all sensors are identical. In reality, "cluster heads" or more powerful nodes might need more keys than simple leaf sensors.
  2. Full Visibility: They assume any two nodes can communicate if they have a key. In the real world, physical distance and channel interference (the "On/Off" nature of wireless links) prevent many nodes from connecting.

This paper tackles these gaps by analyzing heterogeneous networks under a realistic On/Off channel model.

Methods

The authors use the framework of Random Graph Theory. They model the WSN as the intersection of two distinct random graphs:

  • The Inhomogeneous Random Key Graph $\mathbb{K}$: This represents the security layer. Nodes are divided into $r$ classes, each receiving a different number of keys ($K_i$).
  • The Erdős-Rényi Graph $\mathbb{H}$: This represents the physical communication layer, where a link between any two nodes exists with a probability $\alpha$.

The core of the paper is the derivation of Zero-One Laws. These are mathematical thresholds that show exactly when the probability of the network being connected jumps from 0 (disconnected) to 1 (fully connected) as the number of nodes ($n$) becomes very large. They also use simulations to compare their simplified "On/Off" model against the more complex "Disk Model" (where connectivity is strictly distance-based).

Datasets

As a theoretical paper in communication theory, it does not use external empirical datasets. Instead, the authors validated their mathematical proofs using synthetic simulations:

  • Network Size: $n = 500$ nodes.
  • Key Pool Size: $P = 10,000$ keys.
  • Evaluation: They generated 800 independent samples for various parameter settings to calculate the empirical probability of connectivity.

Key Insights and Ideas

  • The "Weakest Link" Impact: Connectivity is primarily driven by the nodes with the smallest number of keys (the "class-1" nodes). If these nodes are isolated, the whole network fails to achieve full connectivity.
  • The Power of Minimums: The authors show that the minimum key ring size in the network has a much more significant impact on connectivity than the average key ring size.
  • Model Equivalence: A major "aha moment" is the demonstration that the simple On/Off channel model is an excellent proxy for the more realistic Disk Model. By matching the link probability ($\alpha = \pi\rho^2$), the connectivity results of the simpler model align almost perfectly with the complex one.
  • Asymptotic Accuracy: While the math relies on the network size $n$ approaching infinity, the simulations prove these results are highly accurate for practical, finite networks (like those with only 500 nodes).

Key Results

  • Connectivity Threshold: The paper establishes that for the network to be connected with high probability, the parameters must scale such that the mean degree of the "weakest" nodes is at least $(1 + \epsilon)\log n$.
  • Zero-One Law: If the scaling factor $c$ is less than 1, the network will almost certainly have isolated nodes. If $c > 1$, the network is almost certainly connected.
  • Simulation Match: Figures in the paper show that the theoretical "critical threshold" (the vertical dashed line) perfectly predicts the point where the simulated networks transition from 0% to 100% connectivity.

Limitations and Future Work

  • Simplified Interference: The On/Off model, while better than "full visibility," still doesn't account for complex wireless phenomena like multi-user interference or fading in high detail.
  • Static Topology: The model assumes nodes are stationary. Future work could explore how node mobility affects these connectivity thresholds.
  • Broader Applications: The authors suggest that this "intersecting graph" approach could be applied to other fields, such as modeling the spread of epidemics or information diffusion in social networks where "links" depend on both a physical meeting and a shared interest.

Summary updated

Abstract

We investigate the connectivity of a wireless sensor network (WSN) secured by the heterogeneous key predistribution scheme under an independent on/off channel model. The heterogeneous scheme induces an inhomogeneous random key graph, denoted by H(n; μ, K, P ) and the on/off channel model induces an Erdos-Rényi graph, denoted by H(n, α). Hence, the overall random graph modeling the WSN is obtained by the intersection of H(n; μ, K, P ) and H(n, α). We present conditions on how to scale the parameters of the intersecting graph with respect to the network size n such that the graph i) has no isolated nodes and ii) is connected, both with high probability (whp) as the number of nodes gets large. Our results are supported by a simulation study demonstrating that i) despite their asymptotic nature, our results can in fact be useful in designing finite-node WSNs so that they achieve secure connectivity whp; and ii) despite the simplicity of the on/off communication model, the probability of connectivity in the resulting WSN approximates very well the case where the disk model is used.
BibTeX
@article{eletreby2019connectivity,
  author = {Rashad Eletreby and Osman Yagan},
  title = {{Connectivity of Wireless Sensor Networks Secured by Heterogeneous Key Predistribution Under an On/Off Channel Model}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2019},
  url = {https://openreview.net/forum?id=29LAEUxlKv},
}

Loading related content...

Figure