We introduce a new random key predistribution scheme for securing heterogeneous wireless sensor networks. Each of the @math sensors in the network is classified into @math classes according to some probability distribution @math . Before deployment, a class- @math sensor is assigned @math cryptographic keys that are selected uniformly at random from a common pool of @math keys. Once deployed, a pair of sensors can communicate securely if and only if they have a key in common. We model the communication topology of this network by a newly defined inhomogeneous random key graph. We establish scaling conditions on the parameters @math and @math so that this graph: 1) has no isolated nodes and 2) is connected, both with high probability. The results are given in the form of zero-one laws with the number of sensors @math growing unboundedly large; critical scalings are identified and shown to coincide for both graph properties. Our results are shown to complement and improve those given by and for the same model, therein referred to as the general random intersection graph.
Distributed Sensor Networks (DSNs) are ad-hoc mobile networks that include sensor nodes with limited computation and communication capabilities. DSNs are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment to grow the network or replace failing and unreliable nodes. DSNs may be deployed in hostile areas where communication is monitored and nodes are subject to capture and surreptitious use by an adversary. Hence DSNs require cryptographic protection of communications, sensor-capture detection, key revocation and sensor disabling. In this paper, we present a key-management scheme designed to satisfy both operational and security requirements of DSNs. The scheme includes selective distribution and revocation of keys to sensor nodes as well as node re-keying without substantial computation and communication capabilities. It relies on probabilistic key sharing among the nodes of a random graph and uses simple protocols for shared-key discovery and path-key establishment, and for key revocation, re-keying, and incremental addition of nodes. The security and network connectivity characteristics supported by the key-management scheme are discussed and simulation experiments presented. We give, for the first time, a precise mathematical analysis of the connectivity and security properties of sensor networks that make use of the random predistribution of keys. We also show how to set the parameters---pool and key ring size---in such a way that the network is not only connected with high probability via secure links but also provably resilient, in the following sense: We formally show that any adversary that captures sensors at random with the aim of compromising a constant fraction of the secure links must capture at least a constant fraction of the nodes of the network. In the context of wireless sensor networks where random predistribution of keys is employed, we are the first to provide a mathematically precise proof, with a clear indication of parameter choice, that two crucial properties---connectivity via secure links and resilience against malicious attacks---can be obtained simultaneously. We also show in a mathematically rigorous way that the network enjoys another strong security property. The adversary cannot partition the network into two linear size components, compromising all the links between them, unless it captures linearly many nodes. This implies that the network is also fault tolerant with respect to node failures. Our theoretical results are complemented by extensive simulations that reinforce our main conclusions.