An Energy-Efficient Key Predistribution Scheme for Secure Wireless Sensor Networks Using Eigenvector

Abstract

Currently, sensor networks are widely used in various fields. Here secure operations are required for critical applications since the damages are significant if the network is compromised or disrupted. For the security of wireless sensor network, the earlier schemes typically employ asymmetric cryptography. These schemes are, however, often unsuitable for wireless sensor network due to the limited computational power and energy of the sensor nodes. To address this issue, various approaches have been developed, and the random key predistribution approach has been recognized as an effective approach. One shortcoming, however, is that a common key is not guaranteed to be found between any two nodes wanting to communicate. This paper proposes a new robust key predistribution scheme solving this problem, with which the security is not compromised even though the data exchanged between the nodes are tapped by an adversary. This is achieved by using the keys assigned based on the notion of eigenvalue and eigenvector of a square matrix of a pool of keys. Mathematical analysis and computer simulation reveal that the proposed scheme significantly reduces the overhead required for secure connectivity and energy consumption of sensor nodes compared to the existing approaches.

1. Introduction

Wide-spread deployment of sensor networks is quite practical these days. A network of thousands or more sensors allows an efficient solution to various challenging tasks: traffic monitoring, monitoring of building with respect to the structure, fire, and security, military sensing and tracking, distributed measurement of seismic activity, real-time pollution monitoring, wild life monitoring, wild fire tracking, and so forth [1–3]. Energy-aware distributed intelligent data gathering with wireless sensor networks is a hot issue lately due to the emerge of big data paradigm [4].

Wireless sensor networks (WSNs) share several common properties with the traditional wireless networks. Both of them include arrays of nodes that are battery powered, have limited computational capabilities and memory, and rely on intermittent wireless communication via radio frequency and, possibly, optical links. They also include data-collecting nodes which cache the sensed data and make them available to the processing components of the network and control nodes which monitor the status of the sensor nodes and broadcast simple commands to them. However, WSNs differ from the traditional wireless networks in several aspects; namely, the scale is a few orders of magnitude larger than that of wireless networks; they are dynamic in the sense that addition and removal of sensor nodes are allowed after the deployment to expand the network or replace failed or unreliable nodes without physical contact; and they may be deployed in hostile areas where the communication is monitored and the sensor nodes are subject to capture and manipulation by an adversary. These harsh operational conditions place very critical security constraints on the WSN design [5–9].

Numerous commercial and military applications require secure operation of sensor networks, and seriously detrimental outcomes might be caused if the network is compromised or disrupted. When the sensor networks are deployed in a hostile environment, security is extremely important as they are prone to different types of malicious attacks. For example, an enemy can easily tap the information, imitate one of the sensor nodes, or intentionally provide incorrect information to other nodes. The critical issue here is how to secure the communication between the sensor nodes; that is, how to set up a secret key between the communicating nodes. Most of the earlier schemes use asymmetric cryptography to solve this problem [10]. However, these schemes are often unsuitable to distributed sensor network due to limited computational power and energy of sensor nodes.

To address this issue a scheme has been proposed, which is based on random key pre-distribution. However, it has a shortcoming that a common key is not guaranteed to be found between any two nodes wanting to communicate, and there is also a high possibility of leakage of key information and breakdown of security. This is because the keys are distributed using an identifier, working as a key transport between the sensor nodes. This paper proposes a new key pre-distribution scheme solving this problem by assigning the keys based on the notion of eigenvalues and eigenvectors [11] of a square matrix of a pool of random keys. The main idea here is that there exists infinite combination of eigenvalues and eigenvectors building a matrix. As a result, one cannot ever conjecture the original matrix with only a portion of eigenvalues and eigenvectors of the sensor nodes, which corresponds to the shared key. It thus provides high security to wireless sensor networks of pre-distributed keys by not exposing any data on the key to other nodes. The main advantages and contributions are summarized as follows.

• (i)

A common key is guaranteed to be found between any two nodes wanting to communicate.

(ii)

The key cannot be leaked unless entire sensor nodes are compromised.

(iii)

It requires much smaller memory space to hold the pre-distributed keys.

(iv)

The energy efficiency is higher.

Analytical modeling and computer simulation reveal that the proposed scheme significantly reduces the overhead required for secure connectivity and energy consumption of the sensor nodes compared to the existing approach employing the random key pre-distribution scheme.

The rest of the paper is organized as follows. Section 2 discusses the existing key distribution approaches for sensor networks, and Section 3 presents the proposed scheme. Section 4 analyzes and compares the performance of the proposed scheme with those of the earlier schemes, and finally concluding remarks are given in Section 5.

2. Related Works

There exist a number of key pre-distribution schemes developed for wireless sensor network. A basic approach is to let all the nodes carry a master secret key, and any pair of nodes use the global master key for key agreement and creation of a new pairwise key. This approach does not exhibit sufficient network resilience such that if one node is compromised, the security of the entire sensor network is compromised. Some existing studies suggest storing the master key in tamper-resistant hardware to reduce the risk [12], but this increases the cost and energy consumption of each sensor node. Furthermore, tamper-resistant hardware might not always be safe. Liu and Ning [13] proposed another key pre-distribution scheme which substantially improves the resilience of the network compared to other schemes. This scheme exhibits a threshold property; when the number of compromised nodes is smaller than the threshold, the probability that other noncompromised nodes are affected is close to zero. This desired property lowers the initial payoff of small-scale network breaches to an adversary, and makes it necessary for the adversary to attack a significant portion of the network.

Blundo et al. [14] proposed several schemes which allow any group of some parties to compute a common key while being secure against collusion between some members of them. These schemes focus on saving communication cost while memory constraints are not placed on the group members. Perrig et al. [10] proposed SPINS, a security architecture specifically designed for sensor networks. In SPINS, each sensor node shares a secret key with the base station, and any pair of sensor nodes cannot directly establish a secret key. They use the base station as a trusted third party to set up a secret key.

Eschenauer and Gligor [15] proposed a random key pre-distribution scheme, which exploits the probabilistic characteristics of random graph. In this scheme the basestation first creates a large number of random keys and saves them in the key pool. Then, a group of keys are randomly selected from it to build a key ring, which is distributed to the sensor nodes. The sensor nodes find the shared keys among the neighboring nodes residing within the wireless communication radius by broadcasting the key ring and key information to the neighbor nodes. Any two nodes apart by two or more links or having no shared key have to create a path key in order to have a shared key. One of the two nodes selects a key from the key ring and transmits it to other nodes through the intermediate nodes in the key path until reaching the target node. The operation of this scheme consists of three phases as follows, which is illustrated in Figure 1.

Figure 1

The procedure of the Eschenauer and Gligor scheme.

2.1. Phase I (The Initialization)

The Eschenauer and Gligor (E-G) scheme randomly decides a pool of keys, P, out of the key space generated by random graph. In each node k keys are randomly selected from P and stored in the memory. This set of k keys is called the node's key ring. The number of keys in the key pool, $|P|$ , is chosen such that two random subsets of size m in P will share at least one key with some probability p.

2.2. Phase II (The Discovery of Shared Key)

The nodes perform key discovery to find out shared key from their neighbors. The key discovery is performed by assigning a short identifier to each key prior to deployment and having each node broadcast its set of identifiers. The nodes identifying that they contain a shared key in their key ring can then verify that their neighbor actually holds the key through a challenge response protocol. The shared key then becomes the key for that link.

2.3. Phase III (The Setup of Path Key)

The nodes can set up path key with the nodes in their vicinity when they cannot find shared keys from their key rings. If the network is connected, a path can be found from a source node to its neighbor. The source node then generates a path key and sends it securely via the path to the target node.

The key pre-distribution scheme proposed by Chan et al. [16] also employs the random graph approach like the scheme proposed in [15], but it uses q (≥1) shared keys instead of one. This scheme connects two nodes via multiple paths and creates the keys to fortify the security. As a result, even if a sensor node is damaged by the attacker, the security of the rest of the nodes can be preserved using the random/shared keys. This scheme decides a pool of keys of size of P from the key space and composes a key ring of k elements. For the communication of one node with the neighbor nodes, at least more than q keys need to be shared and security is provided by creating a new key $(\text{hash}(k_1|k_2|\cdots k_q))$ . This scheme focuses on the security fortification against small-scale attacks. One shortcoming here is that a shared key between any two nodes is not guaranteed to be found. Moreover, it does not support the mechanism for mutual authentication between the nodes.

Camtepe and Yener [17] and Lee and Stinson [18] applied combinatorial approaches to key pre-distribution. They presented two classes of combinatorial designs: symmetric balanced incomplete block designs and generalized quadrangles. The points and blocks in the combinatorial designs are associated with distinct key identifiers and nodes, respectively. Here even though the probability of key establishment has been increased, the network resiliency is still limited and node authentication is not ensured. Sánchez and Baldus [19] made use of combinatorial design theory for the pre-distribution of multiple bivariate polynomial shares based on [14]. Their approach enables direct pairwise key establishment for a large number of nodes, independently of the physical connectivity properties of WSNs. Chakrabarti et al. [20] also used the combinatorial designs for key pre-distribution in WSNs. Their method is to begin with a transversal design and then form the key rings by merging the blocks. Some performance metrics are improved at the cost of larger storage.

Liu et al. [21] proposed an asymmetric key pre-distribution scheme (AKPS). AKPS uses a trusted authority (TA) to distribute secret keys to each user and public keying material to keying material servers (KMSs). With the help of KMSs, two sensor nodes can establish a session key to encrypt messages. AKPS has an advantage over other schemes in that the compromise of KMSs does not disclose any information of the users' secret keys and the session keys. Nguyen et al. proposed a key management scheme considering the signal range in [22]. Each node is assigned with a subset of keys from the key pool by a key setup server. Two nodes residing in each other's communication range is assigned a subset of common keys. This scheme also includes shared key discovery and path key establishment phases. By using the location information of sensor nodes, it improves the connectivity and achieves better resilience than other schemes. However, this scheme depends on the information of sensor deployment.

Szczechowiak and Collier [23] proposed a key agreement scheme based on identity-based cryptograph (IBC) for wireless sensor networks. A trust authority is used to pre-distribute a secret key, a unique identity $\text{ID}x$ , a hashing function H, a mapping function, and a key derivation function (KDF) into the memory of each node. This scheme saves much key storage space and allows high resilience against node capture. However, the key agreement protocol employs pairing-based cryptography, which requires large computational and energy resource for each sensor node to compute the shared pairwise keys together with its neighboring nodes.

Some literatures focus on localizing the keys. In [24, 25] the authors presented RPKH and location-dependent key management (LDK) scheme to allow local key management. They utilize different nodes including the normal nodes and anchor nodes to generate the keys of different transmission ranges. The LDK scheme employs heterogeneous sensors to build a clustered sensor network; the higher-ability nodes (anchor nodes) take the management role and regular nodes. The anchor nodes use the location information of other nodes to generate sets of keys. The neighboring nodes establish secure communication link by determining common keys via exchanging the data of their key. LDK takes advantage of relative location of the nodes by utilizing the anchor nodes of different power level. According to the locations, the nodes receive different sets of keys from the anchor nodes, and the neighboring nodes can establish secure communication link through the common keys. LDK can increase the direct connectivity ratio among the nodes. However, the nodes need to transmit a message containing all the data of the key for determining common keys. This operation consumes lots of energy, and thus it is not appropriate for WSNs. Moreover, the adversary can eavesdrop on the exchanged key data, and the anchor nodes are difficult to deploy.

Recently, efficient and secure key management for wireless sensor networks attracted a number of researchers [26–28]. Bechkit et al. [29] and Gu et al. [30] focused on key pre-distribution approach for mainly scalability, and Kim et al. [31] applied the key distribution to the clustered WSN. A new polynomial-based rekeying scheme was also proposed by Guo and Qian [32], and an adaptive dynamic key management approach was proposed by Alcaraz et al. [33]. As a different approach, Yu and Wang [34] and Paterson and Stinson [35] suggested to use combinatorial design. Salam et al. [36] proposed public key cryptography for key pre-distribution. An asymmetric matrix and projective plane was used by Subash and Divya [37] and Mitra et al. [38], respectively. The distinctive features of the proposed scheme compared to these key pre-distribution approaches are that it takes advantages of the notion of eigenvectors of a symmetric matrix, which disallows reverse mapping (and thus compromise of security).

The two main issues in the random key pre-distribution approaches are guaranteeing to find a common key between any pair of nodes and the prevention of information leaks. We next present the proposed scheme effectively handling these issues.

3. The Proposed Scheme

In this section the proposed scheme is presented, deferring the analysis and performance evaluation on the security and energy efficiency to the next section. The proposed key pre-distribution scheme employs the random graph approach like Eschenauer's method [15]. However, it guarantees that any pair of nodes can find the shared key between them while preventing the leakage of key information.

3.1. Preliminaries

The proposed scheme is based on important properties of a matrix in designing the key pre-distribution scheme.

Definition 1 (eigenvalue and eigenvector).

Let A be an $n\times n$   matrix. A nonzero vector v is an eigenvector of A if (1) holds for some scalar λ. λ is called an eigenvalue of A corresponding to the eigenvector v. Eigenvalues are also known as characteristic, or proper, values or even as latent roots

$$\begin{array}{cc}& Av=\lambda v.\end{array}$$

(1)

Let us now discuss how to compute eigenvalues and eigenvectors in general. Because   $Av=\lambda v\Rightarrow Av=\lambda Iv,\Rightarrow Av-\lambda Iv=\mathrm{0}\Rightarrow (A-\lambda I)v=\mathrm{0}$ , we see that v is an eigenvector, if and only if it is a nontrivial solution of the homogeneous system $(A-\lambda I)v=\mathrm{0}$ . In this case, v is a nonzero vector of the null space of $A-\lambda I$ . The system has a nontrivial solution, if and only if the determinant of the coefficient matrix is zero. Thus, λ is an eigenvalue of A, if and only if $\det (A-\lambda I)=\mathrm{0}$ [39].

Definition 2 (α -secure).

As long as an adversary compromises less than or equal to α nodes, uncompromised nodes are perfectly secure.

The security of the proposed scheme is stronger than α–secure in the sense that the entire security is unbroken despite $(\alpha +1)$ nodes being exposed. The entire security could be broken only when the entire keys pre-distributed are leaked, which is virtually impossible.

3.2. The Proposed Key Distribution Scheme

The key pre-distribution scheme proposed in this section randomly selects k keys out of the key pool of p elements and then generates the index of these keys. A random function is used to generate node identifiers, and the keys generated in the key pool are used as session keys.

The session key is an encryption key used for only one communication session. In case a key is used for numerous encryption messages, the key could be extracted from the messages. This is prevented using a temporary session (i.e., one-time) key. The session key approach employed in the earlier schemes may cause key exposure when used repeatedly. This problem is solved by the proposed approach using the pre-distributed key combination (initial vector).

3.2.1. Setup of Initial Vector

The initial vector is set via four off-line steps: (i) generation of a large pool of keys (e.g., $2^{17}~2^{20}$   keys), (ii) formation of a square matrix using the pool of keys, (iii) derivation of eigenvalues and eigenvectors for the square matrix, (iv) and key pre-distribution to each sensor node.

Step 1 (generation of a large pool of keys).

The proposed key pre-distribution scheme is based on random keys. Therefore, a large pool of keys (e.g., $2^{17}~2^{20}$   keys) are generated in this step. Each sensor node receives a subset of keys from the pool before deployment. For the communication between two nodes, they need to find one common key to be used as a shared secret key.

Step 2 (forming a square matrix using the pool of keys).

Eschenauer's scheme uses just a pool of keys. However, the proposed scheme uses a pool of keys formed in a square matrix. The random keys are first laid out in the square matrix format before applying the proposed key pre-distribution scheme using eigenvalues and eigenvectors.

Step 3 (deriving eigenvalues and eigenvectors for the square matrix).

The eigenvalues and eigenvectors derived from the square matrix are stored as keys in each sensor node. It is to allow a common key between any two nodes and increase the security by providing node-to-node mutual authentication.

A general method for finding eigenvalues and eigenvectors shown in Definition 1 needs to be developed. It computes the dominant eigenvalue and eigenvector corresponding to the dominant eigenvalue. Without loss of generality, it is necessary to assume that square matrix, A, has the following two properties.

• (i)

There is a single eigenvalue of maximum modulus.

(ii)

There is a linearly independent set of n eigenvectors.

According to the first assumption, the eigenvalues can be labeled such that

$$\begin{array}{cc}& \left|{\lambda }_{\mathrm{1}}\right|>\left|{\lambda }_{\mathrm{2}}\right|\ge \left|{\lambda }_{\mathrm{3}}\right|\ge \cdots \ge \left|{\lambda }_n\right|.\end{array}$$

(2)

According to the second assumption, there is a basis $\{v^{(\mathrm{1})},v^{(\mathrm{2})},\dots ,v^{(n)}\}$ for $C^n$   such that

$$\begin{array}{cc}& A{v}^{\left(j\right)}={\lambda }_j{v}^{\left(j\right)}\hspace{1em}\left(\mathrm{1}\le j\le n\right).\end{array}$$

(3)

Let $x^{(\mathrm{0})}$ be an element of $C^n$ such that when $x^{(\mathrm{0})}$ is expressed as a linear combination of the basis elements $v^{(\mathrm{1})},v^{(\mathrm{2})},\dots ,v^{(n)}$ , the coefficient of $v^{(\mathrm{1})}$ is not 0. Thus,

$$\begin{array}{cc}& x^{\left(\mathrm{0}\right)}=a_{\mathrm{1}}{v}^{\left(\mathrm{1}\right)}+a_{\mathrm{2}}{v}^{\left(\mathrm{2}\right)}+\cdots +a_n{v}^{\left(n\right)}\hspace{1em}\left(a_{\mathrm{1}}\ne \mathrm{0}\right).\end{array}$$

(4)

We form then   $x^{(\mathrm{1})}=A{x}^{(\mathrm{0})},x^{(\mathrm{2})}=A{x}^{(\mathrm{1})},\dots ,x^{(k)}=A{x}^{(k-\mathrm{1})}$ to have

$$\begin{array}{cc}& x^{\left(k\right)}=A^k{x}^{\left(\mathrm{0}\right)}.\end{array}$$

(5)

In the following analysis there is no loss of generality in absorbing all the coefficients $a_j$ in the vectors $v^{(j)}$ . By (5), we have

$$\begin{array}{cc}& x^{\left(k\right)}=A^k{v}^{\left(\mathrm{1}\right)}+A^k{v}^{\left(\mathrm{2}\right)}+\cdots +A^k{v}^{\left(n\right)}.\end{array}$$

(6)

Using (3), we arrive at

$$\begin{array}{cc}& x^{\left(k\right)}={\lambda }_{\mathrm{1}}^k\left[v^{\left(\mathrm{1}\right)}+{\left(\frac{{\lambda }_2}{{\lambda }_1}\right)}^k{v}^{\left(\mathrm{2}\right)}+\cdots +{\left(\frac{{\lambda }_n}{{\lambda }_1}\right)}^k{v}^{\left(n\right)}\right].\end{array}$$

(7)

Since $|{\lambda }_{\mathrm{1}}|>|{\lambda }_j|$ for $\mathrm{2}\le j\le n$ , we see that the coefficients ${({\lambda }_j/{\lambda }_{\mathrm{1}})}^k$   tend to 0 and the vector within the brackets converges to $v^{(\mathrm{1})}$ as $k\to \infty$ .

To simplify the notation, we write $x^{(k)}$   in the form

$$\begin{array}{cc}& x^{\left(k\right)}={\lambda }_{\mathrm{1}}^k\left[v^{\left(\mathrm{1}\right)}+{\epsilon }^{\left(k\right)}\right]\hspace{1em}\text{where}\hspace{0.17em}\hspace{0.17em}{\epsilon }^{\left(k\right)}⟶\mathrm{0}\hspace{0.17em}\hspace{0.17em}\text{as}\hspace{0.17em}\hspace{0.17em}k⟶\infty .\end{array}$$

(8)

In order to be able to take ratios, let φ be any linear functional on $C^n$ for which $\phi (v^{(\mathrm{1})})\ne \mathrm{0}$ . Recall that a linear functional φ satisfies $\phi (\alpha x+\beta y)=\alpha \phi (x)+\beta \phi (y)$ , for scalars α and β and vectors x and y. (e.g., φ could simply evaluate the jth component of any given vector). Then

$$\begin{array}{cc}& \phi \left(x^{\left(k\right)}\right)={\lambda }_{\mathrm{1}}^k\left[\phi \left(v^{\left(\mathrm{1}\right)}\right)+\phi \left({\epsilon }^{\left(k\right)}\right)\right].\end{array}$$

(9)

Consequently, the following ratios converge to ${\lambda }_{\mathrm{1}}$ as $k\to \infty$ :

$$\begin{array}{cc}& r_k\equiv \frac{\phi \left(x^{\left(k+\mathrm{1}\right)}\right)}{\phi \left(x^{\left(k\right)}\right)}={\lambda }_{\mathrm{1}}\left[\frac{\phi \left(v^{\left(\mathrm{1}\right)}\right)+\phi \left({\epsilon }^{\left(k+\mathrm{1}\right)}\right)}{\phi \left(v^{\left(\mathrm{1}\right)}\right)+\phi \left({\epsilon }^{\left(k\right)}\right)}\right]⟶{\lambda }_{\mathrm{1}}.\end{array}$$

(10)

Since the direction of the vector $x^{(k)}$ aligns more and more with $v^{(\mathrm{1})}$ as $k\to \infty$ , this results in the eigenvector $v^{(\mathrm{1})}$ . If the eigenvectors found are

$$\begin{array}{l}{v}^{\left(\mathrm{1}\right)}=\left[\begin{array}{l}{s}_{\mathrm{1}}\hfill \\ ⋮\hfill \\ ⋮\hfill \\ s_n\hfill \end{array}\right]s_n\in R,\hspace{1em}\hspace{1em}{v}^{\left(\mathrm{2}\right)}=\left[\begin{array}{l}{t}_{\mathrm{1}}\hfill \\ ⋮\hfill \\ ⋮\hfill \\ t_n\hfill \end{array}\right]t_n\in R,\dots ,\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{v}^{\left(n\right)}=\left[\begin{array}{l}{z}_{\mathrm{1}}\hfill \\ ⋮\hfill \\ ⋮\hfill \\ z_n\hfill \end{array}\right]z_n\in R,\hfill \end{array}$$

(11)

$P\hspace{0.17em}\hspace{0.17em}(P=[v^{(\mathrm{1})}{v}^{(\mathrm{2})}\cdots v^{(n)}])$ is actually stored key and D matrix consisting of eigenvalues becomes the decryption key. An important property of the proposed scheme is that it allows both key pre-distribution and encryption of data at the same time. That is, one cannot extract the original data even though some elements of the P matrix stored in each sensor node are leaked. This is because deciding the original matrix using a small portion of P matrix is impossible. As a result, the proposed key pre-distribution scheme allows high security.

Step 4 (key pre-distribution).

In this step every node is assigned P matrix consisting of eigenvectors and D matrix consisting of eigenvalues. Note here that there exist infinite ways for forming P matrix by arbitrarily deciding the $s_n$ , $t_n$ , and $u_n$ values. In addition, only the diagonal elements (eigenvalues) from the D matrix are stored to minimize the required memory space.

3.2.2. Distribution of Session Key

The previous subsection explained how to generate the initial vector using pre-distributed key combinations. This subsection describes how to distribute the session keys from a source node to the destination node using the initial vector. It consists of four steps: (i) set the initial vector between two nodes, (ii) exchange messages for setting a session, (iii) set the session key, (iv) and update the initial vector.

Step 1 (set the initial vector between two nodes).

An initial vector needs to be set between two nodes for which a security session is to be set. This step needs Definition 3.

Definition 3 (eigenvalue and eigenvector).

Assume that an $n\hspace{0.17em}\times \hspace{0.17em}n$ matrix A can be converted to a diagonal matrix D, which is called diagonalizable. Then there exists an invertible $n\times n$ matrix P such that

$$\begin{array}{cc}& P^{-\mathrm{1}}AP=D.\end{array}$$

(12)

The process of finding matrices P and D is called diagonalization. First, it is worth noticing that if D is a diagonal matrix with diagonal entries ${\lambda }_{\mathrm{1}},\dots ,{\lambda }_n$ , then for $i=1,\dots ,n$

$$\begin{array}{cc}& D{e}_i=\lambda e_i.\end{array}$$

(13)

Hence, the standard basis vectors $e_{\mathrm{1}},\dots ,e_n$ are eigenvectors of D. In particular, the eigenvectors of D  are linearly independent. To find a common key A using Definition 3, the following theorem needs to be proved.

Theorem 4.

   One has the following.

• (i)

A is diagonalizable if and only if it has n linearly independent eigenvectors.

(ii)

If A is diagonalizable with $P^{-\mathrm{1}}AP=D$ , then the columns of P are eigenvectors of A and the diagonal entries of D are the corresponding eigenvalues.

(iii)

If    $\{v_{\mathrm{1}},\dots ,v_n\}$ are linearly independent eigenvectors of A with corresponding eigenvalues   ${\lambda }_{\mathrm{1}},\dots ,{\lambda }_n$ , then A can be diagonalized by

$$\begin{array}{cc}& P=\left[v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_n\right],\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}D=\left[\begin{array}{ccc}{\lambda }_{\mathrm{1}}& \cdots & \mathrm{0}\\ ⋮& \ddots & ⋮\\ \mathrm{0}& \cdots & {\lambda }_n\end{array}\right].\end{array}$$

(14)

Proof.

Let P be a matrix with columns of n-vectors $v_{\mathrm{1}},\dots ,v_n$ and let D be a diagonal matrix with diagonal elements, ${\lambda }_{\mathrm{1}},\dots ,{\lambda }_n$ , respectively. Then

$$\begin{array}{l}AP=A\left[v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_n\right]=\left[v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_n\right]\left[\begin{array}{lll}{\lambda }_{\mathrm{1}}\hfill & \cdots \hfill & \mathrm{0}\hfill \\ ⋮\hfill & \ddots \hfill & ⋮\hfill \\ \mathrm{0}\hfill & \cdots \hfill & {\lambda }_n\hfill \end{array}\right]\hfill \\ \begin{array}{l}\phantom{AP}=PD.\hfill \end{array}\hfill \end{array}$$

(15)

If A is diagonalizable, with $P^{-\mathrm{1}}AP=D$ , then $AP=PD$ . Hence, $A{v}_i={\lambda }_i{v}_i$ , $i=1,\dots ,n$ . So, the ${\lambda }_i\text{s}$ are eigenvalues and the $v_i\text{s}$ are corresponding eigenvectors.

Suppose that A has n linearly independent eigenvectors, say, $v_{\mathrm{1}}{v}_{\mathrm{2}}\cdots v_n$ (the columns of P). If ${\lambda }_{\mathrm{1}},\dots ,{\lambda }_n$ are the corresponding eigenvalues, then   $A{v}_i={\lambda }_i{v}_i,i=1,\dots ,n$ . If D is a diagonal matrix with diagonal entries   ${\lambda }_{\mathrm{1}},\dots ,{\lambda }_n$ , then $AP=PD$ by (15). Because P is a square matrix with linearly independent columns, it is invertible. Hence, $P^{-\mathrm{1}}AP=D$ , and A is diagonalizable [40].

If we multiply P and $P^{-1}$ matrix to both sides of (12), it becomes $P{P}^{-\mathrm{1}}AP{P}^{-\mathrm{1}}=PD{P}^{-\mathrm{1}}$ . Since $P{P}^{-\mathrm{1}}=I,\hspace{0.17em}\hspace{0.17em}{P}^{-\mathrm{1}}P=I$ (I: identity matrix),

$$\begin{array}{l}A=PD{P}^{-\mathrm{1}}\hfill \\ \phantom{A}=\left[v^{\left(\mathrm{1}\right)}\cdots v^{\left(n\right)}\right]\left[\begin{array}{llll}{\lambda }_{\mathrm{1}}\hfill & \cdots \hfill & \cdots \hfill & 0\hfill \\ 0\hfill & {\lambda }_{\mathrm{2}}\hfill & \cdots \hfill & 0\hfill \\ ⋮\hfill & & \ddots \hfill & ⋮\hfill \\ 0\hfill & \cdots \hfill & \cdots \hfill & {\lambda }_n\hfill \end{array}\right]{\left[v^{\left(\mathrm{1}\right)}\cdots v^{\left(n\right)}\right]}^{-1}.\hfill \end{array}$$

(16)

Therefore, the common key can be found from P and D matrix that was stored in the sensor nodes by   $A=PD{P}^{-\mathrm{1}}$ .

Assume that ${\text{node}}_x$ and ${\text{node}}_y$ contain ( $v_{\mathrm{1}}^{\mathrm{1}},v_{\mathrm{1}}^{\mathrm{2}}\dots ,v_{\mathrm{1}}^n$ ) and ( $v_{\mathrm{2}}^{\mathrm{1}},v_{\mathrm{2}}^{\mathrm{2}},\dots ,v_{\mathrm{2}}^n$ ), respectively. When ${\text{node}}_x$ and ${\text{node}}_y$ need to find the initial vector between them, they first exchange randomly selected vectors and then compute a vector product as follows;

•   ${\text{node}}_x$

: $[v_{\mathrm{1}}^{\mathrm{1}}\cdots v_{\mathrm{2}}^k\cdots v_{\mathrm{1}}^n][{\lambda }_{\mathrm{1}}\cdots {\lambda }_n]{[v_{\mathrm{1}}^{\mathrm{1}}\cdots v_{\mathrm{2}}^k\cdots v_{\mathrm{1}}^n]}^{-\mathrm{1}}$ ,

 

${\text{node}}_y$ : $[v_{\mathrm{2}}^{\mathrm{1}}\cdots v_{\mathrm{1}}^k\cdots v_{\mathrm{2}}^n][{\lambda }_{\mathrm{1}}\cdots {\lambda }_n]{[v_{\mathrm{2}}^{\mathrm{1}}\cdots v_{\mathrm{1}}^k\cdots v_{\mathrm{2}}^n]}^{-\mathrm{1}}$ .

Recall that A is diagonalizable, and thus A is used as an initial vector between ${\text{node}}_x$ and ${\text{node}}_y$ .

Step 2 (exchange messages for setting a session).

Using the pre-distributed key combinations as the initial vector, m keys from the k keys are selected at each node. Also, $T_{ck(i)}$ in the source node and $D_{ck(i)}$ in the destination node are generated by applying Exclusive-OR operation to the key selected. Using $T_{ck(i)},D_{ck(i)}$ , and the initial vector ${SD}_{\text{IV}(k)}$ , an encrypted message required for setting a session is exchanged between the nodes. They are $MS\hspace{0.17em}\hspace{0.17em}(={SD}_{\text{IV}(k)}\oplus T_{ck(i)})$ and $MD\hspace{0.17em}\hspace{0.17em}(={SD}_{\text{IV}(k)}\oplus D_{ck(i)})$ .

Step 3 (set the session key).

In this step, with the messages exchanged in Step 2 used to set a session at each node, the session key is generated. The message exchanged to set the session extracts $T_{ck(i)}$ and $D_{ck(i)}$ with the Exclusive-OR operation, and each node generates ${SD}_{sk(i)}=MS\oplus MD=T_{ck(i)}\oplus D_{ck(i)}$   as the session key.

Step 4 (update initial vector).

A secure communication is available at each node using the session key decided in Step 3. In this step the initial vector is updated to improve the security level at each node. The updated initial vector ${SD}_{\text{IV}(i+1)}$ is extracted by the messages setting the session, $MS$ and $MD$ , and the initial vector, ${SD}_{\text{IV}(i)}$ , as in the following expression:

$$\begin{array}{cc}& {SD}_{\text{IV}\left(k+\mathrm{1}\right)}=MS\oplus MD\oplus {SD}_{\text{IV}\left(k\right)}.\end{array}$$

(17)

The two nodes now share ${SD}_{sk(i)}$ as the session key. Figure 2 depicts the flow of message exchange between the two communicating nodes.

Figure 2

The flow of message exchange between the nodes.

3.3. Example

3.3.1. Setup of Initial Vector

Step 1 (generation of a large pool of keys).

 

Step 2 (forming a square matrix using the pool of keys).

We have

$$\begin{array}{cc}& \left[\begin{array}{ccc}\mathrm{3}& \mathrm{0}& \mathrm{0}\\ -\mathrm{4}& \mathrm{6}& \mathrm{2}\\ \mathrm{16}& -\mathrm{15}& -\mathrm{5}\end{array}\right].\end{array}$$

(18)

Step 3 (deriving eigenvalues and eigenvectors for the square matrix).

The eigenvalues obtained are ${\lambda }_1=0,{\lambda }_2=1$ , and ${\lambda }_3=3$ .

Eigenvectors corresponding to each λ become

$$\begin{array}{l}{v}^{\mathrm{1}}=\left[\begin{array}{l}\mathrm{0}\hfill \\ s\hfill \\ -\mathrm{3}s\hfill \end{array}\right],\hspace{1em}\hspace{1em}{v}^{\mathrm{2}}=\left[\begin{array}{l}\mathrm{0}\hfill \\ \mathrm{2}t\hfill \\ -\mathrm{5}t\hfill \end{array}\right],\hspace{1em}\hspace{1em}{v}^{\mathrm{3}}=\left[\begin{array}{l}u\hfill \\ \mathrm{0}\hfill \\ \mathrm{2}u\hfill \end{array}\right]\hfill \\ \hspace{1em}\hspace{1em}s,t,u\in R.\hfill \end{array}$$

(19)

Therefore, the actually stored key P and decryption key D are as follows:

$$\begin{array}{cc}& P=\left[v^{\mathrm{1}},v^{\mathrm{2}},v^{\mathrm{3}}\right],\hspace{1em}\hspace{1em}D=\left[\begin{array}{ccc}0& 1& 3\end{array}\right].\end{array}$$

(20)

Step 4 (key pre-distribution).

We have

$$\begin{array}{l}{\text{node}}_x:P=\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{1}\hfill \\ \mathrm{1}\hfill & \mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & -\mathrm{5}\hfill & \mathrm{2}\hfill \end{array}\right],\hspace{1em}\hspace{1em}D=\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{1}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{3}\hfill \end{array}\right],\hfill \\ s=t=u=\mathrm{1},\hfill \\ {\text{node}}_y:P=\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{2}\hfill \\ \mathrm{1}\hfill & -\mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & \mathrm{5}\hfill & \mathrm{4}\hfill \end{array}\right],\hspace{1em}\hspace{1em}D=\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{1}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{3}\hfill \end{array}\right],\hfill \\ s=1,t=-1,u=\mathrm{2}.\hfill \end{array}$$

(21)

3.3.2. Distribution of Session Key

Step 1 (set the initial vector between two nodes).

When ${\text{node}}_x$ and ${\text{node}}_y$ need to find the initial vector between them, they first exchange randomly selected vectors $v^3$ ( $v^3$ of the ${\text{node}}_x$ is $[\mathrm{1}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.17em}\hspace{0.17em}\mathrm{2}]$ , $v^3$ of the ${\text{node}}_y$ is $[\mathrm{2}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.17em}\hspace{0.17em}\mathrm{4}]$ ) and then compute a vector product as follows:

$$\begin{array}{l}{\text{node}}_x:\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{2}\hfill \\ \mathrm{1}\hfill & \mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & -\mathrm{5}\hfill & \mathrm{4}\hfill \end{array}\right]\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{1}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{3}\hfill \end{array}\right]{\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{2}\hfill \\ \mathrm{1}\hfill & \mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & -\mathrm{5}\hfill & \mathrm{4}\hfill \end{array}\right]}^{-\mathrm{1}}\hfill \\ \hfill \\ \phantom{{\text{node}}_x:}=\left[\begin{array}{lll}\mathrm{3}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ -\mathrm{4}\hfill & \mathrm{6}\hfill & \mathrm{2}\hfill \\ \mathrm{16}\hfill & -\mathrm{15}\hfill & -\mathrm{5}\hfill \end{array}\right]={SD}_{\text{IV}\left(\mathrm{1}\right)},\hfill \\ {\text{node}}_y:\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{1}\hfill \\ \mathrm{1}\hfill & -\mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & \mathrm{5}\hfill & \mathrm{2}\hfill \end{array}\right]\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{1}\hfill & \mathrm{0}\hfill \\ \mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{3}\hfill \end{array}\right]{\left[\begin{array}{lll}\mathrm{0}\hfill & \mathrm{0}\hfill & \mathrm{1}\hfill \\ \mathrm{1}\hfill & -\mathrm{2}\hfill & \mathrm{0}\hfill \\ -\mathrm{3}\hfill & \mathrm{5}\hfill & \mathrm{2}\hfill \end{array}\right]}^{-\mathrm{1}}\hfill \\ \hfill \\ \phantom{{\text{node}}_y:}=[\begin{array}{lll}\mathrm{3}\hfill & \mathrm{0}\hfill & \mathrm{0}\hfill \\ -\mathrm{4}\hfill & \mathrm{6}\hfill & \mathrm{2}\hfill \\ \mathrm{16}\hfill & -\mathrm{15}\hfill & -\mathrm{5}\hfill \end{array}]={SD}_{\text{IV}\left(\mathrm{1}\right)}.\hfill \end{array}$$

(22)

Step 2 (exchange message for setting a session).

We have

•  

$T_{ck(\mathrm{3})}=[\mathrm{1}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.17em}\hspace{0.17em}\mathrm{2}]$ (3rd column vector of the ${\text{node}}_x$ ), ${SD}_{\text{IV}(\mathrm{1})}=[-\mathrm{15}\hspace{0.17em}\hspace{0.17em}-\mathrm{5}\hspace{0.17em}\hspace{0.17em}-\mathrm{4}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{2}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{3}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{6}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{16}]$

 

$MS={SD}_{\text{IV}(\mathrm{1})}\oplus T_{ck(\mathrm{3})}=[-\mathrm{15}\hspace{0.5em}-\mathrm{5}\hspace{0.5em}-\mathrm{4}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{1}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{2}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{3}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{6}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{16}]$

 

$D_{ck(\mathrm{3})}=[\mathrm{2}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.17em}\hspace{0.17em}\mathrm{4}]$ (3rd cloumn vector of the ${\text{node}}_y$ ), ${SD}_{\text{IV}(\mathrm{1})}=[-\mathrm{15}\hspace{0.5em}-\mathrm{5}\hspace{0.5em}-\mathrm{4}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{2}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{3}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{6}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{16}]$

 

$MD={SD}_{\text{IV}(\mathrm{1})}\oplus D_{ck(\mathrm{3})}=\hspace{0.17em}\hspace{0.17em}[-\mathrm{15}\hspace{0.5em}-\mathrm{5}\hspace{0.5em}-\mathrm{4}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{2}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{3}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{4}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{6}\hspace{0.5em}\hspace{0.17em}\hspace{0.17em}\mathrm{16}]$ .

Step 3 (set the session key).

${SD}_{\text{IV}(\mathrm{1})}=MS\hspace{0.17em}\hspace{0.17em}\oplus \hspace{0.17em}\hspace{0.17em}MD\hspace{0.17em}\hspace{0.17em}=\hspace{0.17em}\hspace{0.17em}[-\mathrm{15}\hspace{0.5em}-\mathrm{5}\hspace{0.5em}-\mathrm{4}\hspace{0.17em}\hspace{0.17em}\mathrm{0}\hspace{0.17em}\hspace{0.17em}\mathrm{1}\hspace{0.17em}\hspace{0.17em}\mathrm{2}\hspace{0.17em}\hspace{0.17em}\mathrm{3}\hspace{0.17em}\hspace{0.17em}\mathrm{4}\hspace{0.17em}\hspace{0.17em}\mathrm{6}\hspace{0.17em}\hspace{0.17em}\mathrm{16}]$ .

Step 4 (update initial vector).

${SD}_{\text{IV}(\mathrm{2})}=MS\hspace{0.17em}\hspace{0.17em}\oplus \hspace{0.17em}\hspace{0.17em}MD\hspace{0.17em}\hspace{0.17em}\oplus \hspace{0.17em}\hspace{0.17em}{SD}_{\text{IV}(\mathrm{1})}=\hspace{0.17em}\hspace{0.17em}[-\mathrm{5}\hspace{0.5em}-\mathrm{5}\hspace{0.5em}-\mathrm{4}\hspace{0.5em}\mathrm{0}\hspace{0.5em}\mathrm{1}\hspace{0.5em}\mathrm{2}\hspace{0.5em}\mathrm{3}\hspace{0.5em}\mathrm{4}\hspace{0.5em}\mathrm{6}\hspace{0.5em}\mathrm{16}]$ .

4. Performance Evaluation

4.1. Analysis of Connectivity

A random graph $G(n,p)$ is a graph of n nodes for which the probability that a link exists between two nodes is p. When p is zero, the graph does not have any edge, whereas when p is one, the graph is fully connected. Spencer [41] and Erdős and Rényi [42] showed that, for monotone properties, there exists a value of p such that the property moves from “nonexistent” to “certainly true” in a very large random graph. The function defining p is called the threshold function of the property. Given a desired probability $P_c$ for graph connectivity, the threshold function p is defined by

$$\begin{array}{l}{P}_c=\underset{n\to \infty }{\lim }{P}_r\left[G\left(n,p\right)\text{is}\hspace{0.17em}\hspace{0.17em}\text{connected}\right]=e^{e^{-c}},\hfill \\ \text{where}\hspace{0.17em}\hspace{0.17em}p=\frac{\ln \left(n\right)-\ln \left(-\ln \left(P_c\right)\right)}{n}.\hfill \end{array}$$

(23)

Let p be the probability that a shared key exists between two sensor nodes, and let n be the number of nodes, and d be the expected degree as

$$\begin{array}{cc}& d=p\times \left(n-\mathrm{1}\right)=\frac{\left(n-\mathrm{1}\right)\left(\ln \left(n\right)-\ln \left(-\ln \left(P_c\right)\right)\right)}{n}.\end{array}$$

(24)

For the deployment of a sensor network, let N be the expected number of neighbors within the communication range of a node. Using the expected node degree discussed above, the required local connectivity, $P_{\text{required}}$ , can be estimated as follows:

$$\begin{array}{cc}& P_{\text{required}}=\frac{d}{N}=\frac{\left(n-\mathrm{1}\right)\left(\ln \left(n\right)-\ln \left(-\ln \left(P_c\right)\right)\right)}{nN}.\end{array}$$

(25)

After the required local connectivity is obtained, the value S (the size of the key pool) and k (the number of keys in each node) are decided. Note that S is not directly related to the sensor network, while k is related to the memory size of a sensor node. Therefore, k needs to be as small as possible. Denote $P_{\text{actual}}$ , the actual local connectivity, which is the probability of any two neighboring nodes to find a common key between themselves. The link availability of any two nodes of the existing schemes [15, 16] is obtained by $1-P_{\text{ns}}$ , where $P_{\text{ns}}$ is the probability that a pair of nodes do not share a common key. It can be found using $P_{\text{actual}}$ ,

$$\begin{array}{cc}& P_{\text{actual}}=\mathrm{1}-\frac{{}_S^{}{C}_k\times {}_{S-k}{C}_k}{{\left({}_S^{}{C}_k\right)}^{\mathrm{2}}}=\mathrm{1}-\frac{{\left(\left(S-k\right)!\right)}^{\mathrm{2}}}{S!\left(S-\mathrm{2}k\right)!}.\end{array}$$

(26)

$P_{\text{actual}}$ is then approximated as follows:

$$\begin{array}{cc}& P_{\text{actual}}=\mathrm{1}-\frac{{\left(S-k\right)}^{\mathrm{2}S-\mathrm{2}k+\mathrm{1}}}{{\left(S-\mathrm{2}k\right)}^{S-\mathrm{2}k+(\mathrm{1}/\mathrm{2})}}.\end{array}$$

(27)

Recall that the Eschenauer and Gligor (E-G) [15] and Chan et al. (C-P) [16] schemes are the two representative key pre-distributions employing the random graph approach like the proposed scheme. Therefore, the efficiency of the proposed scheme is compared with these two schemes. Figure 3 compares the actual local connectivity of the proposed scheme with them when the size of the key varies from 2 to 200 for the S value of 5000 and 10000. Observe from the figure that the local connectivity increases as the number of keys in a node increases for the existing scheme when the size of the pool of keys is fixed. Note that the proposed scheme always allows the connectivity regardless of the number of keys per node. Also, the superiority of the proposed scheme becomes more substantial when the memory size of a sensor node is small.

Figure 3

Comparison of connectivity of different schemes.

4.2. Security of Connection

When the sizes of the key pool and key ring are S and K, respectively, the probability of two key rings sharing at least one key is calculated by (27). The number of cases each of two nodes chooses k keys out of the entire key pool is estimated in (28)

$$\begin{array}{cc}& {\left(C\left(S,k\right)\right)}^{\mathrm{2}}={\left(\frac{S!}{k!\left(S-k\right)!}\right)}^{\mathrm{2}}.\end{array}$$

(28)

Equation (29) estimates the number of cases where i  shared keys are chosen from the entire key pool

$$\begin{array}{cc}& C\left(S,i\right)=\frac{S!}{\left(S-i\right)!i!}.\end{array}$$

(29)

The probability of two nodes sharing exactly i keys is calculated in (30)

$$\begin{array}{cc}& P\left(i\right)=\frac{C\left(S,i\right)C\left(S-i,\mathrm{2}\left(k-i\right)\right)C\left(\mathrm{2}\left(k-i\right),k-i\right)}{{\left(C\left(S,k\right)\right)}^{\mathrm{2}}}.\end{array}$$

(30)

If a node of a wireless sensor network is captured by an adversary, the key information kept in the node might be exposed. The degree that the sensor nodes can operate while maintaining a desired security level is defined as the resilience against node capture. The higher the resilience against node capture, the longer the security level can be maintained during the operation of wireless sensor network.

In the proposed scheme, the number of keys used for session key distribution is α, which is much larger than i, leading to a lower probability of a communication link being exposed, compared to the existing schemes. Equation (31) shows that the probability of the session key to be exposed leads to a large value when x number of nodes are captured with the proposed scheme

$$\begin{array}{cc}& {\left(\mathrm{1}-{\left(\mathrm{1}-\frac{k}{S}\right)}^x\right)}^{\alpha },\hspace{1em}i<\alpha \le k.\end{array}$$

(31)

The number of neighbor nodes sharing a key with the existing random graph based schemes is obtained by simulation to evaluate the security of the connection depending on the sizes of key rings. In the simulation the size of key rings is reduced in units of 100 each time, starting from 1,000 to 2,000, where the size of the key pool is 100,000. Then, the probability of establishing a secure connection between any source and destination node randomly selected is found by simulation. In addition, the hop count of the path required for secure connection is found to evaluate the efficiency of the scheme.

Figure 4 shows the average number of neighbor nodes as the size of key ring a node has changed, when the size of the key pool is 100,000 and 1,000 nodes deployed with a 50 m transmission zone in a $\mathrm{1,000}\times \mathrm{1,000}$ region. The number of neighbor nodes with the existing schemes represents the number of nodes sharing a key, whereas it does the ones which can communicate with each other with the proposed approach. Note that the proposed approach is not affected by the size of the key ring. Observe from the figure that a key is shared when the size of key ring exceeds 600 (E-G scheme) and 500 (C-P scheme), respectively. It is predicted that the security of the connection degrades as the size of the key ring becomes smaller, causing the number of neighbor nodes to decrease dramatically.

Figure 4

Comparison of the number of neighbor nodes sharing a key.

Figure 5 shows the result of the evaluation of secure connectivity as the size of the key ring varies. It tests if secure connection is allowed between two randomly selected nodes. The proposed scheme always guarantees secure connectivity regardless of the size of the key ring, while the previous schemes do it only when the size exceeds around 300. The probability of secure connectivity drops sharply when the size falls below 300, for which the number of neighbor nodes is small.

Figure 5

Comparison of the probability of secure connectivity depending on size of key ring.

Figure 6 shows the average length of the key path as the size of key ring varies. The length of the key path measures the distance from a node to the destination node where secure connection is allowed. When the size of a key ring is 100, the probability of secure connectivity is close to 0, and thus it is excluded from the test. The proposed scheme demonstrates consistent size of key path irrespective of the size of the key ring, whereas the existing schemes show similar performance to that of the proposed scheme when the size of the key ring exceeds 500. However, with the existing scheme, the lengths increase if the size of the key ring drops below 400.

Figure 6

Comparison of key path length depending on the size of key ring.

Figure 7 shows the number of neighbor nodes as the transmission range of a node changes. As the transmission range increases, the number of neighbor nodes important for secure connectivity rises. This indicates that probability of secure connectivity grows in proportion to the transmission range. Figure 8 shows the length of the key path as the transmission range of a node varies. Observe from the figure that the difference between the proposed scheme and the previous ones decreases as the transmission range increases. That is, the increased transmission range reduces the overhead of providing secure connectivity and the required key. However, increasing the transmission range significantly increases energy consumption.

Figure 7

The number of neighbor nodes versus transmission range.

Figure 8

Comparison of key path length versus transmission range.

The neighbor nodes of a node can include the ones of multiple hop away to improve the probability of secure connectivity. However, it may increase the energy overhead in setting the keys and the number of nodes involved in setting the path key, resulting in lower security.

4.3. Energy Efficiency

We evaluate the energy efficiency of the proposed scheme through computer simulation by applying it to the LEACH protocol [43], which is one of the representative routing protocols proposed for WSNs. The number of cluster heads in the simulation is about 5% of the total number of nodes. We consider a sensor network of 100 sensor nodes randomly arranged in a $100\hspace{0.17em}\times \hspace{0.17em}100$ region. A base station is located at (50, 50).

In the simulation $E_{\text{elec}}$ of the transmitter or receiver circuitry and ${\epsilon }_{\text{amp}}$ of the transmitter amplifier are set to 50 nJ/bit and 100 pJ/bit/m² [44–46], respectively, and initial residual energy of a sensor node is set to 25 J. The size of data packet is 3000 bits, the number of key rings of [15, 16] is 100, and key length is 32 bits. The energy consumption model [44, 46] is described as follows. For transmission, when a node transmits k-bit data to another node with distance d between them, the energy it consumes is

$$\begin{array}{cc}& E_{\text{Tx}}\left(k,d\right)=E_{\text{elec}}\times k+{\epsilon }_{\text{amp}}\times k\times d^{\mathrm{2}}.\end{array}$$

(32)

For receiving, when a node receives k-bit data, the energy it consumes is

$$\begin{array}{cc}& E_{\text{Rx}}\left(k\right)=E_{\text{elec}}\times k.\end{array}$$

(33)

The parameters used in the simulation are summarized in Table 1.

Table 1

The parameters used in the simulation.

Parameters	Value
Network size	$\mathit{100}\times \mathit{100}$
Location of base station	(50, 50)
Number of nodes	100
Initial energy of the node	25 J
$E_{\text{elec}}$	50 nJ/bit
${\epsilon }_{\text{amp}}$	100 pJ/bit/m2
Data size	3000 bits
Number of key rings	100
Key length	32 bits

In the existing schemes each sensor node finds the neighboring nodes having the shared key for which energy consumption is not large. However, the energy consumption increases with the broadcasting of the identifier of the destination node via neighbor nodes holding a shared key for searching the pass key. If a node creates a pass key once and the session key is used more than once, the energy consumption may not greatly increase.

Figure 9 compares the energy consumption when a node is randomly selected as the destination node out of some number of nodes (called destination group). Here only the energy used by the transceiver of a node taken for secure connection is considered. The energy consumed by the proposed scheme and previous schemes is low if the destination group is small. It gradually increases as the destination group increases. In the proposed scheme this is due to the increment of energy consumption taken to exchange the initial vector, while it owes to the energy consumed to set up the pass key in the previous scheme. The proposed scheme is affected by the size of destination group more significantly than the previous scheme, but it consumes less energy than the previous scheme in a typical environment where the size of destination group is usually small.

Figure 9

Comparison of the residual energy of the schemes.

Figure 10 evaluates the energy consumption as time varies when the size of destination group is set to 100. The entire energy consumption is affected by the energy used to distribute the session key and the efficiency of the distribution of the session key. The increment of the energy consumption owes to session key distribution via the pass key in case of the previous schemes. The session key distribution of the previous scheme consumes more energy than the proposed scheme because the path for the pass key is longer.

Figure 10

Comparison of the residual energy of the schemes as the key length varies.

5. Conclusion and Future Work

Most earlier schemes proposed for the security of wireless network used asymmetric cryptography such as the Diffie-Hellman key agreement or RSA. However, these schemes are inappropriate for wireless sensor networks due to the limited computation and energy resource of sensor nodes. In order to solve the problem the key distribution scheme using the trusted server was proposed based on asymmetric public key certification approach. Also, the key pre-distribution scheme that saves the key information before installing the sensor node was proposed, which is known to be very effective. The key pre-distribution scheme proposed by Eschenauer and Gligor creates various random keys in the base station, and the randomly selected keys are distributed to each sensor node. The sensor nodes having a common key between them use it as a mutual secret key. When they cannot create a path key, in other words when they cannot find a secret key, they cannot communicate with each other.

This paper has proposed a new key pre-distribution scheme guaranteeing that any pair of nodes can find a common secret key between themselves by using the keys assigned by eigenvalue and eigenvector of a square matrix of a pool of keys. Mathematical analysis and computer simulation revealed that the proposed scheme significantly reduces the overhead required for secure connectivity and energy consumption compared to the existing schemes. Analysis shows that the existing scheme requires a large number of keys in each sensor node to display a comparable connectivity as the proposed scheme. The probability of secure connectivity was evaluated by computer simulation for a randomly designated destination node, which reveals that the size of key ring of the existing schemes needs to be over 300 to be comparable with the proposed scheme. Also, the number of neighbor nodes having a shared key with the existing schemes needs to be over 600. The superiority of the proposed scheme is more substantial when the memory size of the sensor node is small.

When composing a network, the keys need to be pre-distributed as the nodes are deployed in the field. The effectiveness of the key pre-distribution scheme needs to be analyzed as new nodes are added. This is because the probability of secure connectivity may change as the network topology is varied. There is a need of application and performance analysis for the distributed sensor network model covering various conditions including the size of network. In order to raise the probability of secure connectivity, the transmission range of a node can be increased. However, the energy cost increases in proportion to the distance. A new approach considering the energy efficiency along with secure connectivity will also be investigated in the future. The proposed scheme capitalizes some important properties of matrix including eigenvalues and eigenvectors in generating a pool of random keys. It will be expanded to exploit some other properties which allow higher security at lower implementation and operation cost.