Zero-One Laws for Connectivity in Inhomogeneous Random Key Graphs

DOI10.1109/TIT.2016.2574742MaRDI QIDQ2976671zbMATH OpenFDO

Authors Osman Yaǧan

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.02407

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

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 {mu} = {{mu}_1 , . . . , {mu}_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.

Recommendations

• Zero–One Laws for Connectivity in Random Key Graphs
• Zero-one law for connectivity in superposition of random key graphs on random geometric graphs
• Zero-One Laws for Sparse Random Graphs
• Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\)
• Zero-one laws for random \(k\)-partite graphs
• The weak zero-one law for the random distance graphs
• The weak zero-one laws for the random distance graphs
• Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\)
• Connectivity of inhomogeneous random graphs
• Zero-one laws for random graphs with vertices in a Boolean cube

Cited in

(2)

• Phase transition in random intersection graphs with communities
• Connectivity threshold for superpositions of Bernoulli random graphs

This page was built for publication: Zero-One Laws for Connectivity in Inhomogeneous Random Key Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976671)