2013/01/28 by Krishnan, B. Santhana, Ganesh, Ayalvadi, Manjunath, D.
#Combinatorics (math.CO) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #G.2.3 #Information Theory (cs.IT) #Probability (math.PR)
paper · doi:10.48550/arxiv.1301.6422
In a random key graph (RKG) of n nodes each node is randomly assigned a key ring of Kn cryptographic keys from a pool of Pn keys. 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,1]2. In addition to the common key requirement, we require two nodes to also be within rn of 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, Pn and rn for the graph to be asymptotically almost surely connected.