Topological Properties of Secure Wireless Sensor Networks Under the q-Composite Key Predistribution Scheme With Unreliable Links

Jun Zhao

Abstract

Security is a critical requirement for Wireless Sensor Networks (WSNs) deployed in hostile environments. While the $q$-composite key predistribution scheme is a widely recognized method for securing these networks, rigorous analysis of its topological properties has been historically difficult due to the interdependence of network links. This paper addresses this gap by investigating node degree properties in WSNs where communication links are subject to unreliability, modeled as independent ON/OFF channels. By deriving the asymptotically exact probability for the minimum degree being at least $k$ and demonstrating that node degree distribution follows a Poisson random variable, this research provides essential theoretical foundations and design guidelines for building resilient and secure sensor networks.

Introduction

Wireless Sensor Networks (WSNs) are often the backbone of data collection in "hostile" or unpredictable environments, such as battlefields, disaster zones, or remote industrial sites. In these settings, security and connectivity are paramount. To secure communications, sensors are pre-loaded with a set of cryptographic keys from a larger pool. Under the $q$-composite key predistribution scheme, two sensors can only establish a secure link if they share at least $q$ common keys.

However, cryptographic compatibility is only half of the equation. In practice, physical barriers, electromagnetic interference, or harsh environmental conditions can cause communication links to fail, rendering them "OFF" even if the sensors share the required keys. Analyzing the resulting network topology is mathematically challenging because the links between nodes are not independent—a shared key between two nodes affects the probability of links with other nodes. This paper provides the first rigorous mathematical analysis of WSNs operating under both the $q$-composite scheme and unreliable physical links.

Methodology and Modeling

The research models the WSN as an intersection of two distinct types of random graphs:

  1. A $q$-composite key graph: Where edges exist between nodes that share $q$ or more keys.
  2. An Erdős-Rényi graph: Representing the physical communication layer where links are independently ON or OFF.

The core of the study involves complex asymptotic analysis, examining the network's behavior as the number of nodes ($n$) approaches infinity. The author utilizes the Method of Moments to prove that the number of nodes with a specific degree $h$ is asymptotically equivalent to a Poisson random variable. This allows for the derivation of "Zero-One Laws"—mathematical thresholds that identify the exact point at which a network property (such as every node having at least $k$ neighbors) transitions from being almost impossible to almost certain.

Key Theoretical Insights

The Poisson Equivalence

A significant contribution of this work is the discovery that, despite the inherent dependencies between links in the $q$-composite scheme, the distribution of nodes with a fixed degree remains Poisson in the limit. This finding significantly simplifies the mathematical framework required for future WSN research, as it allows complex dependencies to be treated with more manageable statistical tools.

Minimum Degree and Connectivity

The paper establishes the asymptotically exact probability that the minimum degree of the network is at least $k$. In network science, having a minimum degree of $k$ is a necessary condition for $k$-connectivity (the ability of a network to remain functional even if $k-1$ nodes fail). By solving for the minimum degree, the author provides a foundation for ensuring overall network resilience against both node failure and physical link degradation.

Practical Design Guidelines

The theoretical findings are translated into practical design inequalities. These formulas allow network engineers to determine the optimal parameters for a deployment, specifically:

  • The number of keys to load onto each sensor ($K_n$).
  • The size of the total key pool ($P_n$).
  • The required physical link reliability ($p$).

By following these guidelines, engineers can guarantee a specific level of network reliability and security before the sensors are even deployed. The paper validates these formulas through extensive computer simulations involving networks of 2,000 to 3,000 nodes, showing that the analytical curves perfectly match experimental results even in finite, real-world scenarios.

Limitations and Future Directions

While the paper provides a rigorous foundation, it acknowledges certain modeling simplifications:

  • Independent Link Model: The current model assumes link failures are independent. In reality, physical obstructions might cause spatial correlation, where multiple nearby links fail simultaneously.
  • Static Topology: The analysis assumes sensors are stationary. Future work could extend these findings to mobile WSNs where the topology is constantly shifting.
  • Advanced Communication Models: The author suggests exploring more complex models, such as the "disk model" (distance-based constraints) or models accounting for "shadow fading" in radio signals, to further refine the accuracy of these topological predictions.

Summary updated

Abstract

Security is an important issue in wireless sensor networks (WSNs), which are often deployed in hostile environments. The q-composite key predistribution scheme has been recognized as a suitable approach to secure WSNs. Although the q-composite scheme has received much attention in the literature, there is still a lack of rigorous analysis for secure WSNs operating under the q-composite scheme in consideration of the unreliability of links. One main difficulty lies in analyzing the network topology, whose links are not independent. Wireless links can be unreliable in practice due to the presence of physical barriers between sensors or because of harsh environmental conditions severely impairing communications. In this paper, we resolve the difficult challenge and investigate topological properties related to node degree in WSNs operating under the q-composite scheme with unreliable communication links modeled as independent ON/OFF channels. Specifically, we derive the asymptotically exact probability for the property of minimum degree being at least k, present the asymptotic probability distribution for the minimum degree, and demonstrate that the number of nodes with a fixed degree is in distribution asymptotically equivalent to a Poisson random variable. We further use the theoretical results to provide useful design guidelines for secure WSNs. Experimental results also confirm the validity of our analytical findings.
BibTeX
@article{zhao2017topological,
  author = {Jun Zhao},
  title = {{Topological Properties of Secure Wireless Sensor Networks Under the q-Composite Key Predistribution Scheme With Unreliable Links}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2017},
  url = {https://openreview.net/forum?id=qqVe9dn8zd},
}
Figure