k-Connectivity in Random Key Graphs with Unreliable Links

Abstract

Random key graphs form a class of random intersection graphs and are naturally induced by the random key predistribution scheme of Eschenauer and Gligor for securing wireless sensor network (WSN) communications. Random key graphs have received much interest recently, owing in part to their wide applicability in various domains including recommender systems, social networks, secure sensor networks, clustering and classification analysis, and cryptanalysis to name a few. In this paper, we study connectivity properties of random key graphs in the presence of unreliable links. Unreliability of the edges are captured by independent Bernoulli random variables, rendering edges of the graph to be on or off independently from each other. The resulting model is an intersection of a random key graph and an Erdos-Renyi graph, and is expected to be useful in capturing various real-world networks; e.g., with secure WSN applications in mind, link unreliability can be attributed to harsh environmental conditions severely impairing transmissions. We present conditions on how to scale this model's parameters so that i) the minimum node degree in the graph is at least k, and ii) the graph is k-connected, both with high probability as the number of nodes becomes large. The results are given in the form of zeroone laws with critical thresholds identified and shown to coincide for both graph properties. These findings improve the previous results by Rybarczyk on the k-connectivity of random key graphs (with reliable links), as well as the zero-one laws by Yagan on the 1-connectivity of random key graphs with unreliable links.

Published in IEEE Transactions on Information Theory

References in corpus (5)

• Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel
• Assortativity and clustering of sparse random intersection graphs
• Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
• On the strengths of connectivity and robustness in general random intersection graphs
• The phase transition in inhomogeneous random intersection graphs

Cited by in corpus (11)

• On resilience and connectivity of secure wireless sensor networks under node capture attacks
• Topological properties of secure wireless sensor networks under the q-composite key predistribution scheme with unreliable links
• Zero-one laws for connectivity in inhomogeneous random key graphs
• On Connectivity and Robustness in Random Intersection Graphs
• Towards $k$-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links
• Probabilistic key predistribution in mobile networks resilient to node-capture attacks
• On secure communication in sensor networks under q-composite key predistribution with unreliable links
• Analyzing resilience of interest-based social networks against node and link failures
• Analyzing connectivity of heterogeneous secure sensor networks
• Transitional Behavior of q-Composite Random Key Graphs with Applications to Networked Control
• Secure Connectivity of Wireless Sensor Networks Under Key Predistribution with on/off Channels