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

Document Type: ORIGINAL RESEARCH PAPER

Authors

School of Electrical and Computer Engineering, Shiraz University, Shiraz, Iran

Abstract

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 efficiently 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 significantly reduced in comparison with the existing random key pre-distribution schemes. Our simulation results verify these terms.

Keywords


 [1] M. Kubale, "Graph colorings," American Mathematical Society, ISBN 0-8218-3458-4, 2004.

[2] J. H. Van Lint, R. M. Wilson, "A course in combinatorics (2nd ed.)," Cambridge University Press, ISBN 0-521-80340-3, 2001.

[3] T. R. Jensen, B. Toft, "Graph coloring problems, "Wiley-Interscience, New York, ISBN 0-471-02865-7, 1995.

[4] L. Eschenauer and V. D. Gligor. "A key-management scheme for distributed sensor networks," In Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002.

[5] A. Ahadipour, A. Keshavarz-Haddad, "A novel location-based key distribution scheme for large-scale stationary wireless networks," IEEE 12th International Iranian Society of Cryptology Information Security and Cryptology (ISCISC), Rasht, Iran, 2015.

[6] W. Du, J. Deng, Y. S. Han, P. Varshney, "A pairwise key pre-distribution scheme for wireless sensor networks," In Proceedings of the Annual ACM Computer and Communications Security (CCS), 2003.

[7] D. Liu, P. Ning, "Establishing pairwise keys in distributed sensor networks," In Proceedings of the Annual ACM Computer and Communications Security (CCS), 2003.

[8] R. Blom, "An optimal class of symmetric key generation systems," In Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EURO-CRYPT), 1984.

[9] C. Blundo, A. D. Santis, A. Herzberg, S. Kutten, U. Vaccaro, M. Yung, "Perfectly-secure key distribution for dynamic conferences," In Proceedings of the 29th International Cryptology Conference (CRYPTO), 1993.

[10] H. Chan, A. Perrig, D. Song, "Random key pre-distribution schemes for sensor networks," In Proceedings of IEEE Symposium on Security and Privacy (SP), 2003.

[11] W. Du, J. Deng, Y. S. Han, Sh. Chen, and P. K. Varshney, "A key management scheme for wireless sensor networks using deployment knowledge," 23th Annual Joint Conference of the IEEE Computer and Communications Societies (INFO-COM), 2004.

[12] W. Du, J. Deng, Y. S. Han, and P. K. Varshney, "A key pre-distribution scheme for sensor networks using deployment knowledge," IEEE Transactions on Dependable and Secure Computing, vol. 3, pp. 62-77, 2006.

[13] B. Kong, H. Chen, X. Tang, K. Sezaki, "Key pre-distribution schemes for large-scale wireless sensor networks using hexagon partition," IEEE Wireless Communications and Networking Conference (WCNC), 2010.

[14] F. Anjum, "Location dependent key management using random key- predistribution in sensor networks," Proceedings of the 5th ACM workshop on Wireless security, pp. 21-30, 2006.

[15] M. Faghani and S. Motahari, "Sectorized location dependent key management," Proceedings of Wireless and Mobile Computing, Networking and Communications, pp. 388-393, 2009.

[16] F. Anjum, "Location dependent key management in sensor networks without using deployment knowledge," Wireless Networks, vol. 16, no. 6, pp. 1587-1600, 2010.

[17] A. Gaur, S. Toshniwal, A. Prakash, D. P. Agrawal, "Enhanced location based key pre-distribution scheme for secure communication in Wireless Sensor Network (WSN)," IEEE 7th International Conference on Mobile Adhoc and Sensor Systems (MASS), 2010.

[18] H. Fakhrey, S. Boussakta, R. Tiwari, Y. AlMathehaji, A. Bystrov, "Location-dependent key management protocol for a WSN with a random selected cell reporter," IEEE International Conference on Communications (ICC), 2015.

[19] R. Vaid, V. Katiyar, "VLKM: Virtual location- based key management scheme for Wireless Sensor Networks," International Conference on Parallel, Distributed and Grid Computing (PDGC), 2014.

[20] J. Choi, J. Bang, L. Kim, M. Ahn, T. Kwon, "Location-based key management strong against insider threats in wireless sensor networks," IEEE System Journal, pp. 1-9, Issue: 99, 2015.

[21] M. J. Duan, J. Xu, "An efficient location-based compromise-tolerant key management scheme for sensor networks," Information Processing Letters, pp.  503-507, 2011.

[22] C. Chen and H. Chao, "A survey of key distribution in wireless sensor networks," Security and Communication Networks, 7.12; pp. 24952508, 2014.

[23] Misra, Sudip and Zhang, Isaac and Misra, Subhas Chandra, "Guide to wireless Ad Hoc networks," Security in wireless Ad Hoc networks, p. 391-425, Springer London, 2009.

[24] S. H. Zanakis, A. Solomon, N. Wishart, S. Dublish, "Multi-attribute decision making: a simulation comparison of select methods," European Journal of Operational Research, vol. 107, no. 3, pp. 507529, 1998.

[25] C. Zopounidis, M. Doumpos, "Multicriteria classification and sorting methods: a literature review," European Journal of Operational Research, vol. 138, no. 2, pp. 229246, 2002.

[26] A. Jahan, F. Mustapha, M. Y. Ismail, S. M. Sapuan, M. Bahraminasab, "Acomprehensive VIKOR method for material selection," Materials and Design, vol. 32, no. 3, pp. 12151221, 2011.

[27] A. Chauhan, R. Vaish, "Pareto optimal microwave dielectric materials," Advanced Science, Engineering and Medicine, vol. 5, no. 2, pp. 149155, 2013.

[28] S. Marti, T. J. Giuli, K Lai, and M. Baker, "Mitigating routing misbehavior in mobile ad hoc networks," In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 255-265. ACM, 2000.

[29] G. Wang, W. Zhang, G. Cao, and T. La Porta, "On supporting distributed collaboration in sensor networks," In IEEE Military Communications Conference (MILCOM'03), vol. 2, pp. 752-757, 2003.

[30] A. Seshadri, A. Perrig, L. Van Doorn, and P. Khosla, "Swatt: Software-based attestation for embedded devices," In Proceedings of IEEE Symposium on Security and Privacy, pp. 272-282, 2004.

[31] P. Erdos, A. Renyi, "On random graphs I," in Publ. Math. Debrecen 6, p. 290297, 1959.

[32] J. Spencer, "The strange logic of random graphs," Algorithms and Combinatorics 22, Springer- Verlag ISBN 3-540-41654-4, 2000.