Due to the random distribution of sensor nodes in the WSN especially in the uncontrolled environment make it impossible to distribute the pairwise keys to these sensor nodes before their deployment, so they need a key management scheme to establish secret keys after the deployment, this problem called the key agreement problem (Du et al., 2003). Several key management schemes have been used to solve this problem taking into account the nature of the wireless communication in the WSN and the limited power of the sensor nodes (Divya et al., 2014).
The recent schemes that have been used to solve the key agreement problem classified into several types, some of these types are the Probabilistic Techniques (Random techniques), the Deterministic Techniques, the Polynomial–Based Techniques and the Matrix–Based Techniques.
1.1 Probabilistic Key Pre-Distribution Scheme
The main reason for the probabilistic approaches is to solve the resilience problem of the Single Master Key pre-distribution scheme and the storage problem of the pair-wise key pre-distribution scheme (Yum and Lee, 2012). It is also called the Random a Techniques because the keys are distributed randomly to the sensor nodes. The first random approach refers to Eschenauer and Gligor in (Eschenauer and Gligor, 2002) which the keys are distributed randomly to the sensor nodes from a common space called key pool, where each one of these sensor nodes receives a certain number of keys called key-chain to use later for communication. Any pair of nodes wants to communicate they use their own key-chains provided they have at least one common key. This scheme is called the Basic scheme.
The problem with the basic scheme is that the same key may be used by several pairs of node, so it has a low resilience. The q-composite approach that is presented in (Chan, Perrig and Song, 2003) added two new mechanisms on the Base scheme to increase its security: the Q-composite random key pre-distribution scheme, where the neighboring nodes can communicate if and only if they have keys in common. The second mechanism is the multi-path key reinforcement scheme to help the adjacent nodes that do not have common keys to communicate by finding another path through other nodes, but every node exists in this path must have common keys with the neighboring nodes. Although this scheme enhanced the resilience of the Basic scheme, where the adversary needs to compromise more than one key to break a secure link but it has a low network connectivity.
The enhanced random scheme that is proposed in (Du et al., 2003) merged the Basic scheme with the Blom’s scheme that is presented in (Blom, 1985) to solve the resilience problem of Basic Scheme and network connectivity of it. Each sensor node receives (?) key information selected randomly from (?) key spaces and any neighboring nodes use the same space can communicate, otherwise, they can communicate by finding another path which is called key path through other nodes. The main result of enhanced approach is the threshold value of the number of sensor nodes the adversary needs to break the entire network.
The proposed approach in (Zhu et al., 2016) use the q-composite scheme to improve the resilience of the Base scheme and the other random techniques, where any pair of nodes want to communicate must have at least common keys, but first the key pool are divided into groups and the sensor nodes are divided into groups according to their expected location with the same size, each group of sensor nodes receives a set of keys from the corresponding key pool.
All the previous random schemes suffer from the resilience problem, where the same key may be used by more than one pair of nodes, and the network connectivity in which the neighboring nodes might not be able to find a shared key due to the random distribution of the keys. In addition to that these approaches require a large memory to store a larger number of keys in order to increase the network connectivity and reduce the ability to duplicate the shared keys.
Table 1: Summary Table For Literature Review Of The Probabilistic Key Pre-Distribution Schemes
Author Name & Year Of Publication
The Technique Name
(Eschenauer and Gligor, 2002)
The Basic Scheme (E-G Scheme )
Solve the memory overhead problem of the pair-wise scheme and the resilience problem of the Single Master key pre-distribution scheme.
– Increased the resilience of the Single Master key pre-distribution.
– Decreased the memory overhead of the Pair-wise schemes.
(Chan, Perrig and Song, 2003)
Solve the resilience problems of the Base scheme.
– Increased the resilience of the Base scheme.
(Du et al., 2003)
Enhanced Random Scheme
Solve the network connectivity problem and the resilience problem of the Base scheme.
– Depends on the prior deployment knowledge.
(Zhu et al., 2016)
Improved Random Key Pre-Distribution Technique
Solve the resilience problem of the random techniques.
– Increased the resilience of the random schemes.
– Increased the network connectivity of the random schemes.
1.2 Deterministic Key Pre-Distribution Scheme
The Deterministic Key Pre-Distribution scheme proposed to solve the network connectivity problem of the random approaches. Çamtepe and Yener in (Çamtepe and Yener, 2004) proposed the first deterministic approach which aims to increase the random techniques connectivity without increase the size of the key pool and the key chain. They used two classes of the combinatorial design; the symmetric balanced design, in particular, the finite projective plane of order where is a prime power to generate a symmetric design. The second class is Generalized Quadrangles (GO) design to represent the WSN, where the points represent the keys and the blocks represent the sensor node, the keys are distributed depending on the Block designs.
Sanchez and Baldus in (Sanchez and Baldus, 2005) proposed another approach to enhance the scalability and the resilience of the previous approach, where they used the combinatorial theory to pre-distribute the shared polynomials to the sensor nodes. Any node that wants to communicate with the neighboring nodes must evaluate its shared polynomial using a specific index according to its block and the other node’s ID. While the authors in (Khandke et al., 2013) used asymmetric matrices to increase the resilience. The base station generates a positive integer and a base of form then it generates a set of keys from the key pool to build a secret information and distribute the information and the base to each sensor node. Each one of these sensor nodes has two keys, so each pair of nodes will have two separate links to communicate. In this case, if the adversary compromises one of these links there will be another secure link.
Other deterministic approaches focused on enhancing the resilience of the polynomial –Based key pre-distribution schemes that use the polynomial pool rather than the key pool such as the proposed approach in (Anzani, Javadi and Moeni, 2016). In this approach, the authors based on multivariate polynomials and the combinatorial design. The multivariate polynomials are distributed to the sensor nodes before their deployment based on the IDs of these sensor nodes and the combinatorial design. The problem with this approach is that the resilience is constant and cannot be increased, where it requires increasing in the number of the independent key path to establish an indirect key to increase the security level which may increase the communication overhead.
Table 2: Summary Table For Literature Review Of The Deterministic Key Pre-Distribution Schemes
Author Name & Year Of Publication
The Technique Name
(Camtepe and Yener, 2005)
– Solve the connectivity problem of the random approaches.
– Increased the network connectivity without increasing the size of the key pool and the key-chain.
(Sanchez and Baldus, 2005)
A Deterministic Pairwise Key Pre-distribution Scheme
– Solve the existence and the authentication problems of Ç-Y scheme .
– Solve the scalability problem of the C-Y scheme and the Blundo’s protocol.
– Increased the scalability of the C-Y Scheme.
– Solved the existence problem of the C-Y Scheme.
– Solved the mutual authentication of the Deterministic techniques.
(Khandke et al., 2013)
A Novel Deterministic Key Pre Distribution Scheme
– Increase the security level of the WSN.
– Enhanced the performance and energy efficiency of the sensor nodes.
(Anzani, Javadi and Moeni, 2016)
Deterministic Key Pre-Distribution Method Based On Hypercube Multivariate Scheme.
– Increase the resilience of the Polynomial–Based and the Matrix–Based schemes.
– Increased the resilience of the polynomial pool–based key pre-distribution scheme.
1.3 Polynomial-Based Key Pre-Distribution Scheme
The polynomial-based schemes were proposed to increase the resilience of the WSN. Banaie et al in (Banaie et al., 2014) proposed polynomial-based approach be merging the Polynomial–Based key pre-distribution scheme with the Matrix-Based key pre-distribution scheme. In this approach, the base station generates a set of polynomials from a polynomial pool to construct symmetric matrices and each sensor node receives random elements from these matrices. This approach increased the resilience of the WSN without increasing the communication overhead or the memory overhead.
In (Mahmood, Ning and Ghafoor, 2017), the authors used the polynomial-Based key pre-distribution scheme to reduce the computational cost as a result of regenerate the polynomials in every time a new sensor node joins or leaves the WSN. They used two symmetric polynomials; one for each group of the sensor nodes and the other one is used between the groups.
Table 3: Summary Table For Literature Review Of The Polynomial-Based Key Pre-Distribution Schemes
Author Name Year Of Publication
The Technique Name
(Banaie et al., 2015)
A Polynomial-Based Pairwise Key Pre-distribution protocol
– Increase the resilience of the WSN.
– Enhance the storage usage of the sensor nodes.
– Decreased the memory overhead.
– Increased the resilience of the WSN.
(Mahmood, Ning and Ghafoor, 2017)
A Polynomial Subset-Based Multi-Party System
– Decrease the computational cost of the Polynomial-Based schemes.
– Increased the lifetime of the network.
– Decreased the communication cost and memory overhead.
1.4 Matrix-Based key Pre-distribution Schemes
The Matrix–Based schemes always guarantee that any pair of nodes can communicate and find a common key due to the symmetric matrices that are used (Dai and Xu, 2010). Several algorithms in the encryption field in the WSN depend upon the LU-matrices to help the sensor nodes to build secure links. The authors in (Dai and Xu, 2010) used the Polynomial based key pre-distribution scheme and the Matrix -Based to increase the efficiency of the LU matrix algorithms and the resilience of the WSN. In this approach, the base station generates a set of polynomials randomly from a polynomial pool to establish the matrix (L) and uses this matric to construct the (U) matrix and the original matrix, then it distributes the (L) and (U) elements to the sensor nodes to establish a secure communication.
Another approach which applied the polynomial-Based on the Matrix-Based that is presented in (Banaie et al., 2014), where the base station generates random prime numbers and a set of polynomials to build symmetric matrices. Each sensor node receives one row from each matrix based on its ID, then the sensor nodes use this information to establish a communication with the neighboring nodes.
There other approaches focused on the network connectivity problem more than the resilience problem such as the approach that is presented in (Choi, Kim and Youn, 2013). In this approach, the authors used the eigenvalues and eigenvectors of a square matrix to distribute the keys to the sensor nodes, then construct the matrix using random keys. After that, the base station derives the eigenvalues and eigenvectors of this matrix and distributes them as keys for the sensor nodes to ensure that any pair of sensors can find a common key.
Table 4: Summary Table For Literature Review Of The Matrix-Based Key Pre-Distribution Schemes
Author Name Year Of Publication
The Technique Name
(Dai and Xu, 2010)
Matrix-Based key pre-distribution scheme
– Increase the resilience of the WSN by increasing the Blundo’s protocol threshold.
– Enhanced the performance of the LU-Matrix algorithms.
(Banaie et al., 2014)
A Matrix-Based Pairwise Key Management Scheme
– Provide a secure link to the sensors to communicate.
– Increased the storage efficiency.
– Increased the resilience of the sensor network by using the polynomials.
– Achieved a high network connectivity with a low memory overhead.
(Choi, Kim and Youn, 2013)
An Efficient Key Pre-distribution Scheme
– Increase the network connectivity.
– Enhance the security of the network by Providing a mutual authentication.
Over the years the authors tried to find efficient algorithms that can be used to protect the sensor nodes and the transmitted data between them. Some of these solutions appeared to solve specific problems that found in older solutions. The following table shows the main weakness and strengths that exist in each of the schemes that were presented in the literature review.
Table 5: Comparison Between The Different Types Of The Pre-Distribution Schemes
The Pre-Distribution Type
Its Main Reason
The Probabilistic Key Pre-Distribution Scheme
( Random Approaches )
– To solve the scalability, the network connectivity, and the storage space problems of the traditional approaches.
– Allows network
– Has a Low resilience.
– Has a poor network connectivity.
– May require a large space.
– Cannot provide the desired authentication where more than a pair of nodes may use the same key.
Deterministic Key Pre-Distribution Scheme
– To solve the network connectivity of the random approaches.
– Has a good network connectivity.
– Has a good network resilience.
– Has a low computation overhead.
– Has a low communication overhead.
– The hybrid design may decrease the network connectivity.
– Has limited scalability
– Has a poor authenticity.
Polynomial-Based Key Pre-Distribution Schemes
– To increase the resilience of the network.
– To reduce the communication overhead.
– Has a high resilience
– low communication overhead.
– Has a Low network connectivity.
– Required a Large storage space.
– t-security property.
Matrix-Based key Pre-distribution Schemes
– To increase the network connectivity.
– Has a high network connectivity.
– Has a low resilience.
The proposed approach merged the Matrix–Based algorithm with the Polynomial-Based algorithm, in particular, the Polynomial pool-Based key pre-distribution scheme to provide a mutual authentication between the sensor nodes in the WSN. The mutual authentication means that both communicated nodes know each other and each sensor node can validate the other sensor node. In addition to that, this merging aims to provide a high resilience through using the Polynomial-Based and a high connectivity through using the Matrix-Based.