k -Connectivity in Random K -Out Graphs Intersecting Erdős-Rényi Graphs

摘要

We investigate k -connectivity in secure wireless sensor networks under the random pairwise key predistribution scheme with unreliable links. When wireless communication links are modeled as independent on-off channels, this amounts to analyzing a random graph model formed by intersecting a random K -out graph and an Erdős-Rényi graph. We present conditions on how to scale the parameters of this intersection model so that the resulting graph is k -connected with probability approaching to one (resp. zero) as the number of nodes gets large. The resulting zero-one law is shown to improve and sharpen the previous result on the 1-connectivity of the same model. We also provide numerical results to support our analysis.