On the Connectivity of Sensor Networks Under Random Pairwise Key Predistribution

We investigate the connectivity of wireless sensor networks under the random pairwise key predistribution scheme of Chan Under the assumption of full visibility, this reduces to studying the connectivity in the so-called random K-out graph H (n;K); here, n is the number of nodes and K <; n is an integer parameter affecting the number of keys stored at each node. We show that if K ≥ 2 (respectively, K=1), the probability that H (n;K) is a connected graph approaches 1 (respectively, 0) as n goes to infinity. For the one-law this is done by establishing an explicitly computable lower bound on the probability of connectivity. Using this bound, we see that with high probability, network connectivity can already be guaranteed (with K ≥ 2) by a relatively small number of sensors. This corrects earlier predictions made on the basis of a heuristic transfer of connectivity results available for Erdös-Rényi graphs.