The Strength of Connectivity of Random Graphs induced by Pairwise Key Predistribution Schemes: Implications on Security and Reliability of Heterogeneous Sensor Networks
share
Random key predistribution schemes have emerged as a widely adopted solution for facilitating secure communication in Wireless Sensor Networks (WSNs). Emerging real world networks increasingly rely on integrating information from sensor nodes with different resources and requirements. We analyze the strength of connectivity of a heterogeneous WSN under the random pairwise key predistribution scheme of Chan et al. According to this scheme, each of the n sensor nodes is classified as type-1 (respectively, type-2) with probability μ (respectively, 1-μ) where 0<μ<1. Each type-1 (respectively, type-2) node is paired with 1 (respectively, K_n) other node selected uniformly at random; each pair is then assigned a unique pairwise key so that they can securely communicate with each other. A main question in the design of secure networks is how should the parameters n, μ, and K_n be selected such that the resulting network exhibits certain desirable properties with high probability. It was recently established that achieving even 1-connectivity a.a.s. requires K_n=ω(1) for the inhomogeneous random K-out graph model naturally induced under the heterogeneous pairwise scheme. In this paper, we analyse k-connectivity, the property that the network remains connected despite the removal of any k-1 nodes or links. First, we establish a sharp zero-one law for k-connectivity, showing that for the network to be k-connected a.a.s., we need to set K_n = 1/1-μ(log n +(k-2)loglog n + ω(1)) for all k=2, 3, .... Despite such large scaling of K_n being required for k-connectivity, we also show that merely having K_n =3 ensures that all but finitely many nodes will form a connected sub-network a.a.s.. We provide comprehensive simulations to demonstrate the usefulness of our results in choosing network parameters in the finite node regime.
READ FULL TEXT