On the Network Reliability Problem of the Heterogeneous Key Predistribution Scheme

Abstract

We consider the network reliability problem in wireless sensor networks secured by the heterogeneous random key predistribution scheme. This scheme generalizes Eschenauer-Gligor scheme by considering the cases when the network comprises sensor nodes with varying level of resources; e.g., regular nodes vs. cluster heads. The scheme induces the inhomogeneous random key graph, denoted $\mathbb{G}(n;\mu ,K,P)$. We analyze the reliability of $\mathbb{G}(n;\mu ,K,P)$ against random link failures. Namely, we consider $\mathbb{G}(n;\mu ,K,P,\alpha )$ formed by deleting each edge of $\mathbb{G}(n;\mu ,K,P)$ independently with probability $1-\alpha$, and study the probability that the resulting graph i) has no isolated node; and ii) is connected. We present scaling conditions on $K$, $P$, and $\alpha$ such that both events take place with probability zero or one, respectively, as the number of nodes gets large. We present numerical results to support these in the finite-node regime.

In proceedings of the 55th IEEE Conference on Decision and Control (CDC 2016). arXiv admin note: substantial text overlap with arXiv:1604.00460, arXiv:1610.07576