Toward $k$ -Connectivity of the Random Graph Induced by a Pairwise Key Predistribution Scheme With Unreliable Links
Faruk Yavuz, Jun Zhao, Osman Yağan, Virgil Gligor · IEEE Transactions on Information Theory · 2015
We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent ON/OFF channels. Modeling the network by an intersection of a random K-out graph and an Erdos-Rényi graph, we present scaling conditions (on the number of nodes n, the scheme parameter K, and the probability p of a wireless channel being on), such that the resulting graph contains no nodes with a degree less than k with high probability. Results are given in the form of zero-one laws with n getting large, and are shown to improve the previous results by Yagan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero) in the same model. Through simulations, the established zero-one laws are also shown to hold for the property of k-connectivity, i.e., the property that graph remains connected despite the deletion of any k - 1 nodes or edges.