Graph-Based Block Design and Efficient Key Pre-distribution Schemes

With the development of wireless communication technologies which considerably contributed to the development of wireless sensor networks (WSNs), we have witnessed ever-increasing WSN-based applications which induced a host of research activities in both academia and industry. Since most of the target WSN applications are very sensitive, security issue is one of the major challenges in the deployment of WSN. One of the important building blocks in securing WSN is key management. Traditional key management solutions developed for other networks are not suitable for WSN, since WSN networks are resource (e.g., memory, computation, and energy) limited. 

Key pre-distribution algorithms have recently evolved as efficient alternatives of key management in these networks. Secure communication is achieved between a pair of nodes either by the existence of a key allowing for direct communication or by a chain of keys forming a key path between the pair. State-of-art Key pre-distribution schemes do not take into account prior knowledge such as mandatory network connectivity (for instance, the commander of the military in battlefield naturally needs more frequent and secure communications with his lower rank staff), physical restrictions (for instance, two sensor nodes can communicate with each other only in a certain distance referred to as the radio frequency range). 

Can we design more efficient and effective key pre-distribution schemes, given prior knowledge of network characteristics?

In this work, we consider prior knowledge of network characteristics and application constraints in terms of communication needs between sensor nodes, and we propose methods to design key pre-distribution schemes with better security and connectivity while requiring less resources. Our methods are based on casting the prior information as a graph. The task is then closely related to what we refer to as “graph-based block design”. To that end, we propose a class of quasi-symmetric designs referred here to as g-designs, and study some of their combinatorial properties. Our proposed key pre-distribution schemes significantly improve upon the existing constructions based on the unital design

Jie Ding, Abdelmadjid Bouabdallah, Vahid Tarokh, “Key Pre-Distributions From Graph-Based Block Designs”. pdf


Image sources: &