On connectivity thresholds in superposition of random key graphs on random geometric graphs
B. Santhana Krishnan, Ayalvadi J. Ganesh, Deepika Revankar Manjunath · 2013
In a random key graph (RKG) of n nodes each node is randomly assigned a key ring of Kncryptographic keys from a pool of Pnkeys. Two nodes can communicate directly if they have at least one common key in their key rings. We assume that the n nodes are distributed uniformly in [0, l]2. In addition to the common key requirement, we require two nodes to also be within rnof each other to be able to have a direct edge. Thus we have a random graph in which the RKG is superposed on the familiar random geometric graph (RGG). For such a random graph, we obtain tight bounds on the relation between Kn, Pnand rnfor the graph to be asymptotically almost surely connected.