A unified approach to combinatorial key predistribution schemes for sensor networks

• Published in: Designs, codes, and cryptography codes, and cryptography, 2014-06, Vol.71 (3), p.433-457
• Main Authors: Paterson, Maura B., Stinson, Douglas R.
• Format: Article
• Language: English
• Subjects: Applied sciences; Circuits; Coding and Information Theory; Combinatorics; Combinatorics. Ordered structures; Computer Science; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Cryptography; Cryptology; Data Structures and Information Theory; Designs and configurations; Discrete Mathematics in Computer Science; Exact sciences and technology; Information and Communication; Information, signal and communications theory; Mathematics; Radiocommunications; Sciences and techniques of general use; Signal and communications theory; Software; Telecommunications; Telecommunications and information theory
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-012-9749-4

There have been numerous recent proposals for key predistribution schemes for wireless sensor networks based on various types of combinatorial structures such as designs and codes. Many of these schemes have very similar properties and are analysed in a similar manner. We seek to provide a unified framework to study these kinds of schemes. To do so, we define a new, general class of designs, termed “partially balanced t -designs”, that is sufficiently general that it encompasses almost all of the designs that have been proposed for combinatorial key predistribution schemes. However, this new class of designs still has sufficient structure that we are able to derive general formulas for the metrics of the resulting key predistribution schemes. These metrics can be evaluated for a particular scheme simply by substituting appropriate parameters of the underlying combinatorial structure into our general formulas. We also compare various classes of schemes based on different designs, and point out that some existing proposed schemes are in fact identical, even though their descriptions may seem different. We believe that our general framework should facilitate the analysis of proposals for combinatorial key predistribution schemes and their comparison with existing schemes, and also allow researchers to easily evaluate which scheme or schemes present the best combination of performance metrics for a given application scenario.