Connectivity of inhomogeneous random key graphs intersecting inhomogeneous Erdős-Rényi graphs
Rashad Eletreby, Osman Yağan · 2017
We study the connectivity of a random graph formed by the intersection of an inhomogeneous random key graph with an inhomogeneous Erdös-Rényi graph. The former graph is naturally induced by a heterogeneous random key predistribution scheme introduced for securing wireless sensor network communications. In this scheme, nodes are divided into r classes according to a probability distribution μ = {μ1,..., μr}, and a class-i sensor is assigned Ki cryptographic keys that are selected uniformly at random from a common pool of P keys. The latter graph represents a heterogeneous on/off channel model, where the wireless channel between a class-j node and a class-j node is on (resp. off) with probability αij(resp. 1 - αij) independently from others. We present conditions on how to scale the parameters of the intersection model so that it is connected with high probability as the number of nodes gets large. The result is given in the form of a zero-one law and is supported by a numerical study in the finite-node regime.