Technical Program

Paper Detail

Paper IDG.1.5
Paper Title k-Connectivity in Random Graphs induced by Pairwise Key Predistribution Schemes
Authors Mansi Sood, Osman Yagan, Carnegie Mellon University Pittsburgh, United States
Session G.1: Graph Analytics
Presentation Lecture
Track Graphs, Games, Sparsity, and Signal Processing
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Random key predistribution schemes serve as a viable solution for facilitating secure communication in Wireless Sensor Networks (WSNs). We analyze \emph{reliable} connectivity of a {\em 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 $\mu$ (respectively, $1-\mu)$ where $0<\mu<1$. Each type-1 (respectively, type-2) node is {\em paired} with 1 (respectively, $K_n$) other node selected uniformly at random; each {\em 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 and heterogeneous WSNs is how should the parameters $n$, $\mu$, and $K_n$ be selected such that resulting network exhibits certain desirable properties with high probability. Of particular interest is the {\em strength} of connectivity often studied in terms of $k$-connectivity; i.e., with $k=1, 2, \ldots$, the property that the network remains connected despite the removal of any $k-1$ nodes or links.In this paper, we answer this question by analyzing the {\em inhomogeneous random K-out graph} model naturally induced under the heterogeneous pairwise scheme. It was recently established that this graph is 1-connected asymptotically almost surely (a.a.s.) if and only if $K_n=\omega(1)$. Here, we show that for $k=2, 3, \ldots$, we need to set $K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n + \omega(1))$ for the network to be $k$-connected a.a.s. The result is given in the form of a zero-one law indicating that the network is a.a.s. {\em not} $k$-connected when $K_n = \frac{1}{1-\mu}(\log n +(k-2)\log\log n - \omega(1))$. We present simulation results to demonstrate the usefulness of the results in the finite node regime.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!