On random graphs associated with a pairwise key distribution scheme for wireless sensor networks (Extended version)

Abstract

The pairwise key distribution scheme of Chan et al. was proposed as an alternative to the key distribution scheme of Eschenauer and Gligor (EG) to enable network security in wireless sensor networks. In this paper we consider the random graph induced by this pairwise scheme under the assumption of full visibility. We first establish a zero-one law for graph connectivity. Then, we discuss the number of keys needed in the memory of each sensor in order to achieve secure connectivity (with high probability). For a network of n sensors the required number of keys is shown to be on the order of log n, a key ring size comparable to that of the EG scheme (in realistic scenarios).