Secrecy Transfer for Sensor Networks: From Random Graphs to Secure Random Geometric Graphs

Suppose n nodes with n0 acquaintances per node are randomly deployed in a two-dimensional Euclidean space with the geographic restriction that each pair of nodes can exchange information between them directly only if the distance between them is at most r, the acquaintanceship between nodes form a random graph, while the physical communication links constitute a random geometric graph. To get a fully connected and secure graph, we introduce a secrecy transfer algorithm which combines the random graph and the random geometric graph via an introduction process to produce an acquaintanceship graph Gn,n0. We find that the maximum component of graph Gn,n0 transitions rapidly from small components to a giant component when n0 is larger than a threshold, the threshold is derived, and applications for sensor networks are presented.