$k$ -Connectivity of Inhomogeneous Random Key Graphs With Unreliable Links
Rashad Eletreby, Osman Yağan · IEEE Transactions on Information Theory · 2019
We consider secure and reliable connectivity in wireless sensor networks that utilize the heterogeneous random key predistribution scheme. We model the unreliability of wireless links by an on/off channel model that induces an Erdos-Rényi graph, while the heterogeneous scheme induces an inhomogeneous random key graph. The overall network can thus be modeled by the intersection of both graphs. We present conditions (in the form of zero-one laws) on how to scale the parameters of the intersection model, so that with high probability: i) all of its nodes are connected to at least k other nodes, i.e., the minimum node degree of the graph is no less than k, and ii) the graph is k-connected, i.e., the graph remains connected even if any k - 1 nodes leave the network. These results are shown to complement and generalize several previous results in the literature. We also present numerical results to support our findings in the finitenode regime. Finally, we demonstrate via simulations that our results are also useful when the on/off channel model is replaced with the more realistic disk communication model.