Roberto Di Pietro
Luigi V. Mancini
Abstract
We give, for the first time, a precise mathematical analysis of the connectivity and security properties of sensor networks that make use of the random predistribution of keys. We also show how to set the parameters---pool and key ring size---in such a way that the network is not only connected with high probability via secure links but also provably resilient, in the following sense: We formally show that any adversary that captures sensors at random with the aim of compromising a constant fraction of the secure links must capture at least a constant fraction of the nodes of the network. In the context of wireless sensor networks where random predistribution of keys is employed, we are the first to provide a mathematically precise proof, with a clear indication of parameter choice, that two crucial properties---connectivity via secure links and resilience against malicious attacks---can be obtained simultaneously. We also show in a mathematically rigorous way that the network enjoys another strong security property. The adversary cannot partition the network into two linear size components, compromising all the links between them, unless it captures linearly many nodes. This implies that the network is also fault tolerant with respect to node failures. Our theoretical results are complemented by extensive simulations that reinforce our main conclusions.
- Akyildiz, I. F., Sankarasubramaniam, Y., Su, W., and Cayirci, E. 2002. Wireless sensor networks: A survey. Comput. Netw. 38, 393--422. Google Scholar
Digital Library
- Bettstetter, C. 2002. On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking and Computing (MobiHoc02). 80--91. Google ScholarDigital Library
- Blom, R. 1985. An optimal class of symmetric key generation systems. In Advances in Cryptology: Proceedings of the 1984 International Conference of the Theory and Applications of Cryptographic Techniques (EUROCRYPT'84), Lecture Notes in Computer Science, vol. 338. Google ScholarDigital Library
- Blundo, C., Santis, A. D., Herzberg, A., Kutten, S., Vaccaro, U., and Yung, M. 1993. Perfectly-secure key distribution for dynamic conferences. In Advances in Cryptology: Proceedings of the International Cryptology Conference (CRYPTO'92), Lecture Notes in Computer Science, vol. 740. Google ScholarDigital Library
- Bollobas, B. 1998. Modern Graph Theory. Springer.Google Scholar
- Chan, H., Perrig, A., and Song, D. 2003. Random key predistribution schemes for sensor networks. In Proceedings of the IEEE Symposium on Security and Privacy. Oakland, CA, 197--213. Google ScholarDigital Library
- Conti, M., Di Pietro, R., and Mancini, L. V. 2007. Ecce: Enhanced cooperative channel establishment for secure pairwise communication in wireless sensor networks. Ad Hoc Netw. 5, 1, 49--62.Google ScholarCross Ref
- Di Pietro, R., Mancini, L. V., and Mei, A. 2006. Energy efficient node-to-node authentication and communication confidentiality in wireless sensor networks. Wirel. Netw. 12, 6, 709--721. Google ScholarDigital Library
- Di Pietro, R., Mancini, L. V., Mei, A., Panconesi, A., and Radhakrishnan, J. 2004. Connectivity properties of secure wireless sensor networks. In Proceedings of the 2nd ACM Workshop on Security of ad hoc and Sensor Networks. ACM Press, New York, 53--58. Google ScholarDigital Library
- Du, W., Deng, J., Han, Y. S., and Varshney, P. K. 2003. A pairwise key pre-distribution scheme for wireless sensor networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS'03). ACM Press, New York, 42--51. Google ScholarDigital Library
- Erdös, P. and Rényi, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17--61.Google Scholar
- Eschenauer, L. and Gligor, V. D. 2002. A key-management scheme for distributed sensor networks. In Proceedings of the 9th ACM Conference on Computer and Communications Security (CCS). ACM Press, New York, 41--47. Google ScholarDigital Library
- Fill, J. A., Schenerman, E. R., and Singer-Cohen, K. B. 2000. Random intersection graphs when m = ω(n): An equivalence theorem relating the evolution of the g(n, m, p) and g(n, p) models. Random Struct. Algor. 16, 156--176. Google ScholarDigital Library
- Karoński, M., Sheinerman, E. R., and Singer-Cohen, K. B. 1999. On random intersection graphs: The subgraph problem. Combin. Probab. Comput. 8, 131--159. Google ScholarDigital Library
- Liu, D. and Ning, P. 2003. Establishing pairwise keys in distributed sensor networks. In Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS'03). ACM Press, New York, 52--61. Google ScholarDigital Library
- Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 167--256.Google ScholarDigital Library
- Penrose, M. D. 1999. On k-connectivity for a geometric random graph. Random Struct. Algor. 15, 2, 145--164. Google ScholarDigital Library
- Perrig, A., Szewczyk, R., Wen, V., Culler, D., and Tygar, J. 2001. SPINS: Security protocols for sensor networks. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom'01). ACM Press, New York, 189--199. Google ScholarDigital Library
- Singer-Cohen, K. B. 1995. Random intersection graphs. Ph.D. thesis, Department of Mathematical Sciences, The Johns Hopkins University.Google Scholar
- Stark, D. 2004. The vertex degree distribution of random intersection. Random Struct. Algor. 24, 249--258. Google ScholarDigital Library
- Watts, D. J., and Strogatz, S. H. 1998. Collective dynamics of “small world” networks. Nature 393, 440--442.Google ScholarCross Ref
Index Terms
- Redoubtable Sensor Networks
Recommendations
A key-management scheme for distributed sensor networks
CCS '02: Proceedings of the 9th ACM conference on Computer and communications securityDistributed Sensor Networks (DSNs) are ad-hoc mobile networks that include sensor nodes with limited computation and communication capabilities. DSNs are dynamic in the sense that they allow addition and deletion of sensor nodes after deployment to grow ...
Connectivity properties of secure wireless sensor networks
SASN '04: Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networksWe address the problem of connectivity in Secure Wireless Sensor Networks (SWSN) using random pre-distribution of keys. We propose a geometric random model for SWSNs. Under this new and realistic model, we describe how to design secure and connected ...
Energy conservation in wireless sensor networks and connectivity of graphs
In wireless sensor networks (WSNs), the energy source is usually a battery cell, which is impossible to recharge while WSNs are working. Therefore, one of the main issues in wireless sensor networks is how to prolong the network lifetime of WSNs with ...
Comments