Zero-one laws for connectivity in inhomogeneous random key graphs

Abstract

We introduce a new random key predistribution scheme for securing heterogeneous wireless sensor networks. Each of the n sensors in the network is classified into r classes according to some probability distribution μ = {μ_1 , . . . , μ_r }. Before deployment, a class-i sensor is assigned K_i cryptographic keys that are selected uniformly at random from a common pool of P 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 P and {K_1 , . . . , K_r } so that this graph i) has no isolated nodes; and ii) is connected, both with high probability. The results are given in the form of zero-one laws with the number of sensors n 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 Godehardt et al. and Zhao et al. for the same model, therein referred to as the general random intersection graph.

Paper submitted to IEEE Transactions on Information Theory

References in corpus (4)

• Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel
• k-Connectivity in Random Key Graphs with Unreliable Links
• Connectivity in Secure Wireless Sensor Networks under Transmission Constraints
• On the strengths of connectivity and robustness in general random intersection graphs

Cited by in corpus (7)

• On Connectivity and Robustness in Random Intersection Graphs
• On secure communication in sensor networks under q-composite key predistribution with unreliable links
• Counting triangles, tunable clustering and the small-world property in random key graphs (Extended version)
• Analyzing connectivity of heterogeneous secure sensor networks
• $k$-connectivity of inhomogeneous random key graphs with unreliable links
• On the Strength of Connectivity of Inhomogeneous Random K-out Graphs
• Secure Connectivity of Heterogeneous Wireless Sensor Networks Under a Heterogeneous On-Off Channel Model