On the Eschenauer-Gligor key predistribution scheme under on-off communication channels: The absence of isolated nodes (Extended version)

Armand M. Makowski, Osman YağanarXiv 2015 · DOI · arXiv

Abstract

We consider the Eschenauer-Gligor key predistribution scheme under the condition of partial visibility with i.i.d. on-off links between pairs of nodes. This situation is modeled as the intersection of two random graphs, namely a random key graph and an Erdős-Rényi (ER) graph. For this class of composite random graphs we give various improvements on a recent result by Yağan [IEEE Transactions on Information Theory, 58(6):3821-3835, 2012] concerning zero-one laws for the absence of isolated nodes.

Introduction

In Wireless Sensor Networks (WSNs), establishing secure communication is a fundamental challenge, often addressed through the Eschenauer-Gligor (EG) random key predistribution scheme. In this scheme, each of the $n$ nodes is assigned a random set of $K$ cryptographic keys from a large pool of size $P$. Two nodes can secure their communication if they share at least one key.

Early theoretical analyses of the EG scheme often assumed "full visibility," where any two nodes sharing a key could communicate regardless of physical distance or channel quality. However, real-world WSNs are constrained by physical obstacles and limited radio range. This paper provides a rigorous mathematical refinement of the connectivity properties of WSNs by modeling the network under "partial visibility" using unreliable on-off communication channels.

System Model: The Intersection of Random Graphs

To capture the dual requirements of cryptographic key sharing and physical link availability, the authors model the network as the intersection of two distinct random graphs:

  1. The Random Key Graph $\mathbb{K}(n; K, P)$: A graph where an edge exists between two nodes if they share at least one key from their respective "rings."
  2. The Erdős-Rényi Graph $\mathbb{G}(n; \alpha)$: A graph where an edge exists between two nodes with probability $\alpha$, representing the i.i.d. on-off nature of the wireless communication channel.

The resulting composite graph, denoted as $\mathbb{G} \cap \mathbb{K}$, represents the actual functional network: a link exists between two nodes if and only if they share a key and the physical channel between them is active.

Mathematical Framework and Innovation

The study focuses on the asymptotic behavior of the network as the number of nodes $n$ approaches infinity. The authors investigate the conditions under which the network contains no isolated nodes—a prerequisite for global connectivity.

Scaling and the Deviation Function

The probability of a link existing between two nodes in the composite graph is given by $p_n = \alpha_n (1 - q_n)$, where $(1 - q_n)$ is the probability that two nodes share at least one key. The authors define a scaling for $p_n$ using a deviation function $\gamma_n$:

$$ p_n = \frac{\log n + \gamma_n}{n} $$

Overcoming Previous Limitations

A significant contribution of this work is the removal of technical constraints found in previous literature. Earlier results by Yağan (2012) required the sequence $\alpha_n \log n$ to converge to a limit for the zero-one law to hold. By employing the Principle of Subsubsequences, Makowski and Yağan prove that the zero-one law holds regardless of such convergence, provided the overall scaling of $p_n$ is maintained. This provides a much more general and robust mathematical foundation for understanding WSN connectivity.

Key Results: The Very Strong Zero-One Law

The authors establish a sharp phase transition, known as a zero-one law, for the property that the graph contains no isolated nodes:

  1. The One-Law: If $\gamma_n \to \infty$ as $n \to \infty$, then the probability that the network has no isolated nodes approaches 1.
  2. The Zero-Law: If $\gamma_n \to -\infty$ as $n \to \infty$, then the probability that the network has no isolated nodes approaches 0.

This transition is driven by the "zero-infinity" behavior of the expected number of isolated nodes. When the parameters are above the threshold, the expected number of isolated nodes vanishes; below it, the number grows without bound. This result allows network designers to precisely calculate the required key ring size $K$ and pool size $P$ given a specific channel reliability $\alpha$ to ensure node connectivity.

Discussion and Limitations

While the absence of isolated nodes is a necessary condition for a fully connected network, it is not sufficient. A network could potentially consist of several large, internally connected components that are disconnected from each other. While the threshold for the absence of isolated nodes often coincides with the threshold for the existence of a "giant component" or full connectivity in random graphs, proving the latter for this specific composite model remains a more complex challenge.

Furthermore, the model assumes that channel states are independent and identically distributed (i.i.d.). In practice, wireless channels often exhibit spatial correlation (e.g., shadowing from the same physical obstacle affecting multiple links). Future research may look toward integrating more geographically realistic models into this random graph framework.

Conclusion

By refining the zero-one laws for the Eschenauer-Gligor scheme under partial visibility, this paper provides tighter bounds and removes unnecessary technical restrictions on WSN connectivity analysis. The results offer a clear mathematical guideline for parameter selection in secure sensor networks operating over unreliable communication channels.

Summary updated

Abstract

We consider the Eschenauer-Gligor key predistribution scheme under the condition of partial visibility with i.i.d. on-off links between pairs of nodes. This situation is modeled as the intersection of two random graphs, namely a random key graph and an Erdős-Rényi (ER) graph. For this class of composite random graphs we give various improvements on a recent result by Yağan [IEEE Transactions on Information Theory, 58(6):3821-3835, 2012] concerning zero-one laws for the absence of isolated nodes.
BibTeX
@misc{makowski2015eschenauer,
  author = {Armand M. Makowski and Osman Yağan},
  title = {{On the Eschenauer-Gligor key predistribution scheme under on-off communication channels: The absence of isolated nodes (Extended version)}},
  year = {2015},
  eprint = {1510.02939},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.02939},
}
Figure