On secure and reliable communications in wireless sensor networks: Towards k-connectivity under a random pairwise key predistribution scheme

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 Erdös-Rényi graph, we present scaling conditions (on the number of nodes, the scheme parameter K, and the probability of a wireless channel being on) such that the resulting graph contains no node with degree less than k with high probability, when the number of nodes gets large. Results are given in the form of a zero-one law and are shown to improve the previous results by Yağan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of k-connectivity; i.e., the property that graph remains connected despite the deletion of any k - 1 nodes or edges.