Abstract
We present a comprehensive analysis on connectivity and resilience of secure sensor networks under the widely studied q-composite key predistribution scheme. For network connectivity, which ensures that any two sensors can find a path in between for secure communication, we derive the conditions to guarantee connectivity in consideration of: 1) node-capture attacks, where the adversary may capture a set of sensors and compromise keys in their memory; 2) sensor mobility, meaning that sensors can move around so that the network topology may change over time; 3) physical transmission constraints, under which two sensors have to be within each other's transmission range for communication; 4) the boundary effect of network fields; and 5) link unreliability, meaning that links are allowed to be unreliable. In contrast, many prior connectivity analyses of secure sensor networks often ignore the above issues. For resilience, although limited studies have presented formal analysis, it is often assumed that the adversary captures a random set of sensors, whereas this paper allows the adversary to capture an arbitrary set of sensors. We present conditions to ensure unassailability and unsplittability in secure sensor networks under the q-composite scheme. Unassailability ensures that an adversary capturing any set consisting of a negligible fraction of sensors can compromise only a negligible fraction of communication links although the adversary may compromise communications between non-captured nodes, which happen to use keys that are shared by captured nodes. Unsplittability means that when a negligible fraction of sensors are captured, almost all of the remaining nodes are still securely connected. Based on the results of connectivity, unassailability, and unsplittability, we provide useful guidelines for the design of secure sensor networks.
Introduction
This research provides a rigorous mathematical foundation for securing Wireless Sensor Networks (WSNs) that are constantly on the move and under threat of physical attack. By bridging the gap between abstract graph theory and real-world physical constraints, the paper establishes the precise conditions under which these networks remain both connected and resilient. It moves beyond idealized models to account for sensor mobility, physical transmission ranges, unreliable links, and adversaries who can strategically capture nodes to compromise the network.
The Challenge of Secure Sensor Networks
Wireless Sensor Networks often operate in hostile or remote environments where traditional security, such as public-key infrastructure, is too computationally expensive. Instead, they utilize "probabilistic key predistribution," where each sensor is loaded with a random ring of keys from a large pool. Two sensors can communicate securely only if they share at least $q$ keys.
While this field is well-studied, most prior research relied on "full visibility" models—assuming any two nodes can talk if they share keys, regardless of distance. Furthermore, many analyses assumed that if an attacker captures nodes, they do so randomly. In reality, sensors have limited radio ranges, move around, and attackers are often strategic. This paper addresses the lack of formal proofs for connectivity and resilience when all these real-world factors are combined.
Modeling Network Connectivity and Resilience
The author employs Random Graph Theory to model the network as an intersection of different random graph types: $q$-composite key graphs (key sharing probability), random geometric graphs (the physical disk model), and Erdős–Rényi graphs (link unreliability due to interference).
A technique called coupling is used to compare these complex models to simpler, well-understood random graphs. This allows for the derivation of "zero-one laws"—thresholds where a property like connectivity jumps from "almost never happening" to "almost certainly happening" as the network scales. These findings were validated through extensive computer simulations, generating 500 independent network samples for various scenarios to confirm the mathematical thresholds.
Key Insights and Ideas
- Arbitrary vs. Random Capture: Unlike literature assuming random capture, this paper proves "unassailability" against arbitrary node capture. Even a clever attacker picking specific nodes cannot easily collapse security unless they capture a significant fraction of the population.
- The Boundary Effect: Connectivity is harder to achieve in a bounded "unit square" than on a "unit torus" (a wrap-around map). Nodes near the edges have fewer potential neighbors, requiring denser key distribution or longer radio range.
- Mobility as a Temporal Constraint: For mobile networks, the paper derives the number of consecutive time slots a network remains securely linked under an i.i.d. mobility model.
- Resilience Metrics: The author formalizes Unassailability (capturing a small fraction of nodes only compromises a small fraction of remaining links) and Unsplittability (an attacker cannot partition safe nodes into large, isolated islands).
Connectivity Results
The paper provides a comprehensive set of connectivity results across nine different network settings, accounting for the disk model, unreliable links, and field geometry (torus vs. square).
For a standard static network on a torus, connectivity is guaranteed if: $$\frac{1}{q!} \cdot \frac{K_n^{2q}}{P_n^q} \cdot \pi r_n^2 \geq \frac{c \ln n}{n} \text{ for } c > 1$$
Additional results show that a network is unassailable if the ratio of the key pool size to the keys per node ($P_n/K_n$) scales linearly with the number of nodes ($n$). The paper also identifies the optimal $q$ to balance resilience against small-scale attacks versus large-scale node capture.
Limitations and Future Work
While comprehensive, the analysis uses an "i.i.d. mobility model" where nodes jump to new random locations, which does not capture "smooth" motion like the Random Waypoint model. The study is also limited to 2D planes; future work could extend these proofs to 3D environments or non-uniform node distributions. Finally, the resilience analysis focuses on passive key compromise rather than active Byzantine attacks where captured nodes inject false data.
Summary updated