LPKP: location-based probabilistic key pre-distribution scheme for large-scale wireless sensor networks using graph coloring

Communication security of wireless sensor networks is achieved using cryptographic keys assigned to the nodes. Due to resource constraints in such networks, random key pre-distribution schemes are of high interest. Although in most of these schemes no location information is considered, there are scenarios that location information can be obtained by nodes after their deployment. In this paper, we propose a novel probabilistic key pre-distribution scheme, for large-scale wireless sensor networks which utilizes location information in order to improve the performance of random key pre-distribution substantially. In order to apply the location information of the nodes in key distribution process, we partition the network into some regions and use graph coloring techniques to eciently assign the random keys. The proposed scheme has a superior scalability by supporting larger number of nodes and also increasing the probability of existence of a shared exclusive key among the nearby nodes, i.e., the probability of having an isolated node is signi cantly reduced in comparison with the existing random key pre-distribution schemes. Our simulation results verify these terms.