Abstract
We investigate the connectivity of a wireless sensor network 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 $\mathbb{K}(n;\pmbμ,\pmb{K},P)$ and the on/off channel model induces an Erdős-Rényi graph, denoted by $\mathbb{H}(n,α)$. Hence, the overall random graph modeling the WSN is obtained by the intersection of $\mathbb{K}(n;\pmbμ,\pmb{K},P)$ and $\mathbb{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 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 wireless sensor networks so that they achieve secure connectivity with high probability; and ii) despite the simplicity of the on/off communication model, the probability of connectivity in the resulting wireless sensor network approximates very well the case where the disk model is used.
Introduction
Wireless Sensor Networks (WSNs) are frequently deployed in environments where physical access is restricted, making robust security essential. Due to the limited computational resources of sensor nodes, random key predistribution is often employed: nodes are assigned a random subset of keys from a pool, and a secure link is established only if two nodes share at least one key.
Existing mathematical models for these networks often rely on two simplifying assumptions: homogeneity (all nodes are identical) and full visibility (any two nodes with a shared key can communicate). This research addresses these limitations by analyzing heterogeneous networks—where different classes of nodes may hold different numbers of keys—under a more realistic "On/Off" channel model that accounts for physical communication constraints.
Methodology
The study utilizes Random Graph Theory to model the WSN as the intersection of two distinct graphs:
- Inhomogeneous Random Key Graph ($\mathbb{K}$): Represents the security layer, where nodes are divided into $r$ classes, each receiving $K_i$ keys.
- Erdős-Rényi Graph ($\mathbb{H}$): Represents the physical layer, where a link exists between any two nodes with probability $\alpha$.
The authors derive "Zero-One Laws," which identify the mathematical thresholds at which the probability of network connectivity transitions from 0 to 1 as the number of nodes ($n$) increases. These theoretical results were validated through synthetic simulations of a network with $n = 500$ nodes and a key pool of $P = 10,000$.
Key Insights and Results
A primary finding is the "weakest link" effect: the connectivity of the entire network is largely dictated by the nodes with the smallest number of keys. If these "class-1" nodes are isolated, the network fails to achieve full connectivity.
Furthermore, the research demonstrates a significant model equivalence. The simplified On/Off channel model serves as an excellent proxy for the more realistic Disk Model (where connectivity depends strictly on distance). By setting the link probability $\alpha = \pi\rho^2$, the connectivity results of the two models align almost perfectly.
The derived Zero-One laws prove to be highly accurate even for finite networks. As shown in the simulations, the theoretical critical thresholds (represented by vertical dashed lines) precisely predict the point where the network transitions to full connectivity.
Conclusion
This work provides a rigorous mathematical framework for designing secure and connected heterogeneous WSNs. By establishing precise scaling laws, engineers can determine the minimum number of keys required to guarantee connectivity. While the current model uses a simplified interference representation and assumes static nodes, it offers a foundational "intersecting graph" approach that could be extended to dynamic topologies or other fields like epidemic modeling.
Summary updated