$k$ -Connectivity of Inhomogeneous Random Key Graphs With Unreliable Links

Rashad Eletreby, Osman YaganIEEE Trans. Information Theory 2019 · OpenReview

TL;DR

This paper provides crucial theoretical guarantees for the security and reliability of wireless sensor networks (WSNs) using heterogeneous key distribution. It establishes precise conditions under which these networks can maintain connectivity even when links are unreliable and nodes are removed, offering a robust framework for designing secure WSNs.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are increasingly used in critical applications, but their security and reliability are major concerns. A common approach to secure WSNs is random key predistribution, where nodes share keys before deployment. This paper focuses on a "heterogeneous" version of this scheme, where nodes can have different resource levels or roles. The challenge is to ensure that despite unreliable communication links (channels that are sometimes on, sometimes off) and potential node failures (due to battery depletion, capture, or mobility), the network remains connected and secure. Specifically, the authors aim to determine the exact conditions on network parameters (like key pool size, key ring sizes, and channel reliability) needed to guarantee that the network is not only connected but also k-connected – meaning it can withstand the removal of up to k-1 nodes or links.

Methods

The authors model the WSN as a random graph. The heterogeneous key predistribution scheme leads to an "inhomogeneous random key graph," while the unreliable links are modeled by an "Erdős-Rényi graph." The overall network topology is then represented by the intersection of these two graphs. The core of their methodology involves deriving "zero-one laws." These laws are powerful theoretical tools that precisely define the threshold at which a property (like k-connectivity) transitions from being highly unlikely to highly probable as the network size grows. They achieve this by analyzing the minimum node degree and the k-connectivity of the intersection graph, using techniques like the first and second moment methods from random graph theory.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations, not on training or evaluating on specific real-world datasets.

Key Insights and Ideas

  • Heterogeneity Matters: The paper explicitly accounts for variations in node capabilities and roles, which is crucial for realistic WSN deployments.
  • Intersection Model is Key: Modeling the WSN as the intersection of a heterogeneous key graph and an unreliable channel graph provides a more accurate representation of real-world security and connectivity challenges.
  • Zero-One Laws are Powerful: The derivation of precise zero-one laws offers sharp theoretical guarantees, pinpointing the exact scaling conditions for network properties.
  • k-Connectivity is Crucial for Resilience: Beyond simple connectivity, k-connectivity ensures the network can withstand significant node or link failures, a vital aspect for robust WSNs.
  • Minimum Key Ring Size is Critical: The analysis highlights that the size of the smallest key ring among nodes plays a disproportionately large role in determining network connectivity and resilience.

Key Results

The paper establishes two main theoretical results:

  1. Minimum Node Degree Guarantee: Conditions are provided for the minimum node degree in the network to be at least k with high probability.
  2. k-Connectivity Guarantee: Conditions are provided for the network to be k-connected with high probability.

These conditions are expressed as "zero-one laws," meaning that if the parameters are scaled slightly below the threshold, the desired property is highly unlikely, and if scaled slightly above, it is highly probable. The critical scaling factor is shown to be related to the average degree of the network, specifically involving terms like $\log n$ and $\log \log n$. Numerical simulations support these theoretical findings, demonstrating that the empirical probabilities of achieving the desired connectivity transition sharply around the predicted thresholds. The simulations also show that the minimum node degree and k-connectivity properties are closely aligned.

Limitations and Future Work

  • Technical Conditions: The authors note that some technical conditions (e.g., $\lambda_1(n) = o(1)$) are primarily for proof convenience and might be relaxed in future work.
  • Homogeneous vs. Heterogeneous: While the paper focuses on heterogeneous networks, it shows how its results generalize previous work on homogeneous networks.
  • Practical Implementation: The paper discusses the feasibility of the derived conditions for real-world WSNs, particularly concerning key ring sizes and key pool sizes.
  • Future Directions: The authors suggest that their results complement and generalize existing work, opening avenues for further research into more complex WSN scenarios. The numerical results also suggest that the theoretical findings hold even when the on/off channel model is replaced by a more realistic disk communication model, which could be a direction for future theoretical analysis.

Summary updated

Abstract

We consider secure and reliable connectivity in wireless sensor networks that utilize the heterogeneous random key predistribution scheme. We model the unreliability of wireless links by an on/off channel model that induces an Erdos-Rényi graph, while the heterogeneous scheme induces an inhomogeneous random key graph. The overall network can thus be modeled by the intersection of both graphs. We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model, so that with high probability: i) all of its nodes are connected to at least k other nodes, i.e., the minimum node degree of the graph is no less than k, and ii) the graph is k-connected, i.e., the graph remains connected even if any k - 1 nodes leave the network. These results are shown to complement and generalize several previous results in the literature. We also present numerical results to support our findings in the finitenode regime. Finally, we demonstrate via simulations that our results are also useful when the on/off channel model is replaced with the more realistic disk communication model.
BibTeX
@article{eletreby2019k,
  author = {Rashad Eletreby and Osman Yagan},
  title = {{$k$ -Connectivity of Inhomogeneous Random Key Graphs With Unreliable Links}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=iVGTadgzcB},
}
Figure