Clique Size in Sensor Networks with Key Pre-distribution Based on Transversal Design

Abstract

Key pre-distribution is an important area of research in Distributed Sensor Networks (DSN). Two sensor nodes are considered connected for secure communication if they share one or more common secret key(s). It is important to analyse the largest subset of nodes in a DSN where each node is connected to every other node in that subset (i.e., the largest clique). This parameter (largest clique size) is important in terms of resiliency and capability towards efficient distributed computing in a DSN. In this paper, we concentrate on the schemes where the key pre-distribution strategies are based on transversal design and study the largest clique sizes. We show that merging of blocks to construct a node provides larger clique sizes than considering a block itself as a node in a transversal design.

Keywords:

• Clique
• Combinatorial Design
• Distributed Sensor Networks
• Key Pre-distribution
• Random Merging
• Secured Communication

*This is an extended version of the conference paper accepted in 7th International Workshop on Distributed Computing, IWDC 2005 IIT Kharagpur, India, December 27-30, 2005. Proceedings to be published in Lecture Notes in Computer Science, Springer Verlag.

Notes

4. D. Chakrabarti, S. Maitra, and B. Roy, A hybrid design of key pre-distribution scheme for wireless sensor networks. To be presented at the The 1st International Conference on Information Systems Security, ICISS (Kolkata, India). December 2005. Proceeding to be published in Lecture Notes in Computer Science 3803, Springer–Verlag

7. J. Lee, and D. Stinson, Deterministic key predistribution schemes for distributed sensor networks. SAC, 2004