Allerton 2015 Paper Abstract


Paper ThC4.2

Yagan, Osman (Carnegie Mellon University)

Absence of Isolated Nodes in Inhomogeneous Random Key Graphs

Scheduled for presentation during the Regular Session "Sensor Networks II" (ThC4), Thursday, October 1, 2015, 13:50−14:10, Pine

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on December 5, 2021

Keywords Sensor Networks in Communications, Information Theoretic Approaches in Wireless Communications, Reliable and Trustworthy Networks


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, for each i = 1,...,r. Once deployed, a pair of sensors can establish a secure communication channel if and only if they have a key in common. We model the topology of this network by an inhomogeneous random key graph. We establish scaling conditions on the parameters P and {K_1, . . . , K_r} so that the this graph has no isolated nodes with high probability. The result is given in the form of a zero-one law with the number of sensors n growing unboundedly large. An analogous result is also conjectured for the property of graph connectivity.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2021 PaperCept, Inc.
Page generated 2021-12-05  09:40:42 PST  Terms of use