# A New Key Predistribution Scheme for Multiphase Sensor Networks Using a New Deployment Model

Authors: Boqing Zhou; Jianxin Wang; Sujun Li; Weiping Wang
Journal: Journal of Sensors
 (2014)

---

## Abstract

During the lifecycle of sensor networks, making use of the existing key predistribution schemes using deployment knowledge for pairwise key establishment and authentication between nodes, a new challenge is elevated. Either the resilience against node capture attacks or the global connectivity will significantly decrease with time. In this paper, a new deployment model is developed for multiphase deployment sensor networks, and then a new key management scheme is further proposed. Compared with the existing schemes using deployment knowledge, our scheme has better performance in global connectivity, resilience against node capture attacks throughout their lifecycle.


---

## Body

## 1. Introduction

Due to limited energy capacity of batteries and the possibility of node capture, the functional lifetime of sensor networks (SNs) generally is longer than the operational lifetime of single node. To keep networks working efficiently, multiple deployments of nodes are needed. In the paper, multiphase SNs (MSNs) are studied, in which new nodes are periodically redeployed with certain intervals, called multiphase, to replace the dead or compromised nodes.When SNs are deployed in a hostile environment, security becomes extremely important as they are vulnerable to different types of malicious attacks [1–4]. Hence, it is important to protect communications among sensor nodes to maintain message confidentiality and integrity. As one of the most fundamental security services, pairwise key establishment enables sensor nodes to communicate securely with each other using cryptographic techniques.Public-key operations (both software and hardware implementations), albeit computationally feasible [5, 6], consume energy approximatelythree orders of magnitude higher than symmetric key encryption [7]. Therefore, in the last few years, different key distribution schemes using symmetric key algorithms have been developed for SNs [8–26].However, the security issue is still not solved for MSNs by using deployment knowledge. In the schemes [16, 17], a fraction of keys known by an attacker increases with the capture of nodes due to the repeated use of a fixed key pool. As a result, network security significantly declines with time. When a certain number of these nodes are captured, the adversary has enough keys to compromise a large number of links making the network ineffective. Addition of new nodes to the network with keys from the same key pool will not help because the keys in the new nodes are compromised. In [20], a multiphase key management scheme is proposed, in which a multiphase deployment model is used. However, it has the following shortcomings. (1) In a cell, only a few nodes which are not captured are working in a long time. (2) Nodes must know their location information. (3) The number of new nodes added to the network is fixed in every deployment, which will give rise to the number of nodes uncaptured in the network with time. Also, the key management scheme proposed based on the deployment model has the following shortcomings. (1) Nodes which reside in the same cell but are deployed in different phases cannot communicate with each other. As a result, the local connectivity is low. (2) Theglobal connectivity will significantly decrease with time.


### 1.1. Outline of Our Scheme

To sum up, the problem of authentication and pairwise key establishment between nodes is still not solved for MSNs. In this paper, the main focus is twofold. (1) A new multiphase deployment model is proposed for sensor networks. In the model, the deployment field is divided into hexagonal cells, each cell has a deployment point, and nodes which have the same point form a group. When the proportion of uncaptured nodes in a group is less than the thresholdρ
0, new nodes are needed to be added to the cell. (2) A new key management scheme is proposed based on the deployment model. In our scheme, network deployment includes n phases. For a cell, a disjoint and association n phases’ key pool is created, which is generated by two-dimension backward key chains [21]. Key pool of each phase is divided into 7 equal size subkey pools. And nodes deployed in the ith phase and deployed in a cell (
r
,
c
) pick keys from the ith-phase key pool of the cell (
r
,
c
) and key pools which are created by neighbors cells of the cell (
r
,
c
).


### 1.2. Main Contributions

The main contributions of this paper are summarized as follows.(1)
A multiphase deployment model is presented. The model has the following two main advantages: (1) the number of nodes which are not captured in a cell can be controlled by adjusting the parameterρ
0; (2) nodes do not need to know their location information.
(2)
A new method to construct key pools is proposed and a new key predistribution scheme is presented. The scheme can provide good performances in local connectivity, global connectivity, and resilience against node capture.


### 1.3. Organization

The remainder of the paper is organized as follows. The existing schemes are summarized in Section2. The model of deployment is introduced in Section 3. Our approach is proposed in Section 4 and the analysis and simulation results are provided in Section 5. Conclusion and future work are given in Section 6.


## 1.1. Outline of Our Scheme

To sum up, the problem of authentication and pairwise key establishment between nodes is still not solved for MSNs. In this paper, the main focus is twofold. (1) A new multiphase deployment model is proposed for sensor networks. In the model, the deployment field is divided into hexagonal cells, each cell has a deployment point, and nodes which have the same point form a group. When the proportion of uncaptured nodes in a group is less than the thresholdρ
0, new nodes are needed to be added to the cell. (2) A new key management scheme is proposed based on the deployment model. In our scheme, network deployment includes n phases. For a cell, a disjoint and association n phases’ key pool is created, which is generated by two-dimension backward key chains [21]. Key pool of each phase is divided into 7 equal size subkey pools. And nodes deployed in the ith phase and deployed in a cell (
r
,
c
) pick keys from the ith-phase key pool of the cell (
r
,
c
) and key pools which are created by neighbors cells of the cell (
r
,
c
).


## 1.2. Main Contributions

The main contributions of this paper are summarized as follows.(1)
A multiphase deployment model is presented. The model has the following two main advantages: (1) the number of nodes which are not captured in a cell can be controlled by adjusting the parameterρ
0; (2) nodes do not need to know their location information.
(2)
A new method to construct key pools is proposed and a new key predistribution scheme is presented. The scheme can provide good performances in local connectivity, global connectivity, and resilience against node capture.


## 1.3. Organization

The remainder of the paper is organized as follows. The existing schemes are summarized in Section2. The model of deployment is introduced in Section 3. Our approach is proposed in Section 4 and the analysis and simulation results are provided in Section 5. Conclusion and future work are given in Section 6.


## 2. Related Work

To improve the performance of key establishment, Du et al. [16] and Yu and Guan (YG scheme) [17] developed a scheme using predeployment knowledge, respectively. In [16], the network area is divided into a grid and information on the associated matrices is stored in the sensors based on deployment knowledge. In [17], the network area is divided into hexagonal cells. Compared with [16], the scheme achieves a higher connectivity with a much lower memory requirement and a shorter transmission range. In the two schemes, all nodes choose their keys from the same key pool. An attacker can easily obtain a large number of keys by capturing a small fraction of nodes, which can make SNs ineffective. The addition of new nodes to the network with keys from the same key pool will not help because the keys in the new nodes are already compromised. Therefore, for MSNs, the above two schemes are ineffective.For MSNs, in [20], a scheme (ESPK scheme) is proposed using deployment knowledge, in which a multiphase deployment model is presented. In the model, the deployment field is divided into a grid. Each cell has a deployment point. Nodes which have the same deployment point form a group. The number of nodes in a group is N. And it is supposed that a new group of nodes are needed to be added to a cell only when 90% of nodes in the cell are captured. The model has the following shortcomings. (1) To know the number of nodes in each cell, location information of nodes is needed. (2) If just 80% of nodes in a cell are captured, there are a few nodes in the cell that are working in a long time. (3) The number of new nodes added to the network is measured in a group, and the number of nodes in a group is fixed, which will give rise to the number of nodes in the network with time. On the other hand, the proposed key management scheme can provide good resilience against node capture by using disjoint key pools. However, nodes which come from different phases but are deployed in the same cell cannot establish shared keys. As a result, the local connectivity is low, and the global connectivity decreases significantly with time. So, the problem of secure is still not solved for MSNs using deployment knowledge.


## 3. Deployment Knowledge and Threat Models

### 3.1. Multiphase Deployment Knowledge Model

As shown in Figure1, a target field is partitioned into hexagon cells, and each cell has a deployment point that resides in the center of the cell. Node distribution follows two-dimensional Gaussian distributions [27] with the deployment point as center.Figure 1
A target field is partitioned into hexagon grids. ● represents a deployment point.Nodes which are deployed in the same cell form a group. And nodes deployed in the cell(
r
,
c
) are denoted by G
(
r
,
c
). The number of nodes in G
(
r
,
c
) is N. G
(
r
,
c
) is clustered into phases according to the deployment time. The i-phase subgroup of G
(
r
,
c
) is denoted by G
(
r
,
c
)
i. In our scheme, S
N
(
r
,
c
) represents the set of nodes whose deployment point locate in the cell (
r
,
c
) and that are not captured, and |
S
N
(
r
,
c
)
|
≤
N (several schemes have been proposed to identify the compromised sensors in prior studies, such as [28]). When ρ
(
r
,
c
) is less than the threshold ρ
0, we should add N
-S
N
(
r
,
c
) new nodes to the cell. The ρ
(
r
,
c
) can be calculated as follows:
(1)
ρ
(
r
,
c
)
=
|
S
N
(
r
,
c
)
|
N
.In a deployment phase, if no new nodes are needed to be added to a cell, then the number of deployment phase of the cell remains unchanged. For example, in the second deployment phase, no new nodes are needed to be added to the cell(
1,1
); the number of recent deployment phase of the cell is 1 not 2.


### 3.2. Threat Model

Due to the short time period of the direct key establishment phase, it is reasonable to believe that only a limited number of sensor nodes may be compromised by an attacker [2, 20–23]. We further assume that if an attacker captures a node, all the keying information it holds will also be compromised.In the scheme, the attack model is similar with [16], when an attacker locates in a cell, he can capture nodes around it.


## 3.1. Multiphase Deployment Knowledge Model

As shown in Figure1, a target field is partitioned into hexagon cells, and each cell has a deployment point that resides in the center of the cell. Node distribution follows two-dimensional Gaussian distributions [27] with the deployment point as center.Figure 1
A target field is partitioned into hexagon grids. ● represents a deployment point.Nodes which are deployed in the same cell form a group. And nodes deployed in the cell(
r
,
c
) are denoted by G
(
r
,
c
). The number of nodes in G
(
r
,
c
) is N. G
(
r
,
c
) is clustered into phases according to the deployment time. The i-phase subgroup of G
(
r
,
c
) is denoted by G
(
r
,
c
)
i. In our scheme, S
N
(
r
,
c
) represents the set of nodes whose deployment point locate in the cell (
r
,
c
) and that are not captured, and |
S
N
(
r
,
c
)
|
≤
N (several schemes have been proposed to identify the compromised sensors in prior studies, such as [28]). When ρ
(
r
,
c
) is less than the threshold ρ
0, we should add N
-S
N
(
r
,
c
) new nodes to the cell. The ρ
(
r
,
c
) can be calculated as follows:
(1)
ρ
(
r
,
c
)
=
|
S
N
(
r
,
c
)
|
N
.In a deployment phase, if no new nodes are needed to be added to a cell, then the number of deployment phase of the cell remains unchanged. For example, in the second deployment phase, no new nodes are needed to be added to the cell(
1,1
); the number of recent deployment phase of the cell is 1 not 2.


## 3.2. Threat Model

Due to the short time period of the direct key establishment phase, it is reasonable to believe that only a limited number of sensor nodes may be compromised by an attacker [2, 20–23]. We further assume that if an attacker captures a node, all the keying information it holds will also be compromised.In the scheme, the attack model is similar with [16], when an attacker locates in a cell, he can capture nodes around it.


## 4. Our Scheme

### 4.1. Two-Dimensional Backward Key Chain

In [21], a two-dimensional backward key chain is constructed (see Figure 2). For a two-dimensional backward key chain C
j, if the key k
j
i
1 is known, the key k
j
i
2 (i
2
≤
i
1), the generation key g
j
i
2, and the first key k
j
(
i
2
,
0
) of the second dimensional key chain can be calculated as follows, respectively: k
j
i
2
=
H
1
i
1
-
i
2
(
k
j
i
1
), g
j
i
2
=
H
2
(
k
j
i
2
,
0
), and k
j
(
i
2
,
0
)
=
H
2
(
k
j
i
2
,
1
), where H
1 and H
2 are two independent hash functions. So, the key k
j
(
i
2
,
l
2
)
(
l
2
≥
1
) can be computed as follows:
(2)
k
j
(
i
2
,
l
2
)
=
H
2
l
2
(
g
j
i
2
,
k
j
(
i
2
,
0
)
)
,
when
l
2
≥
1
.
If the keys k
j
i
1 and k
j
(
i
2
,
l
1
) are known, the key k
j
(
i
2
,
l
2
) (l
1
<
l
2) can be computed using the following equation:
(3)
k
j
(
i
2
,
l
2
)
=
H
2
l
2
-
l
1
(
g
j
i
2
,
k
j
(
i
2
,
l
1
)
)
,
when
l
2
>
l
1
.Figure 2
Two-dimensional key chain.


### 4.2. Key Pool

In our scheme, the key pool is made up by two-dimensional backward key chains [21]. The key pool of the cell (
r
,
c
), namely, P
(
r
,
c
), which consists of m two-dimensional backward hash key chains, is divided inton phases according to the generation of the keys. P
(
r
,
c
)
i represents the ith-phase key pool of the cell (
r
,
c
). P
(
r
,
c
)
i is divided into seven equal size subkey pools, and P
(
r
,
c
)
s
i represents the sth (
0
≤
s
≤
6
) pool (see Figure 3). P
(
r
,
c
)
s
i consists of the following two parts: one is a generation key pool P
g
(
r
,
c
)
s
i
=
{
k
j
i
,
j
∈
[
1
,
m
]
} and the other is an ordinary key pool P
c
(
r
,
c
)
s
i
=
{
k
j
(
i
,
l
)
,
j
∈
[
1
,
m
]
,
1
≤
l
≤
L
}.Figure 3
Subkey pools.


### 4.3. Our Scheme

Our scheme consists of three phases: key predistribution phase, shared-key discovery phase, and path-key establishment phase. Although path-key establishment phase is the same as, key predistribution phase and share-key discover phase are different in the previous schemes [16, 17, 20]. The details of our scheme are described below.


#### 4.3.1. Key Predistribution Phase

This phase is conducted offline before sensor nodes are deployed. A nodea
(
r
,
c
)
i deployed in theith deployment phase and its deployment point locates in the cell (
r
,
c
), is predistributed the following keys.Step
1. Select randomly and uniformly t
1 (t
1 is a system parameter) keys from P
c
(
r
,
c
)
s
i
(
1
≤
s
≤
6
). In this step, the total number of predistribution keys of the node is 6
×
t
1.Step
2. Select randomly and uniformly t
2 (t
2 is a system parameter) keys from P
c
(
r
,
c
)
0
i.Step
3. Select randomly and uniformly t
3 (t
3 is a system parameter) keys from P
g
(
r
,
c
)
0
i, and meet the following condition: the number of keys from a two-dimensional backward hash key chain is no more than 1. For example, it is supposed that k
j
(
i
,
l
1
) has been predistributed to a
(
r
,
c
)
i and k
j
i cannot be predistributed to a
(
r
,
c
)
i.Step
4. Select randomly and uniformly t
3 keys from P
g
(
r
′
,
c
′
)
s
′
i
′, where (
r
′
,
c
′
) is the neighbor cell of (
r
,
c
), P
g
(
r
′
,
c
′
)
s
′
i
′ represents the generation key pool of the cell (
r
′
,
c
′
), and i
′ denotes the recent deployment phase. For example, if the deployment phase of cells (
1,1
) and (
1,2
) is 2 and 3, respectively, and new nodes are needed to be added to cell (
1,2
), but no new nodes are needed to be added to cell (
1,1
); then a
(
1,2
)
4 should pick t
3 keys from P
g
(
1,1
)
1
2(see Figure 3). But if both cells (
1,1
) and (
1,2
) need to add new nodes, then a
(
1,2
)
4 and b
(
1,1
)
3 should pick t
3 keys from P
g
(
1,1
)
1
3 and P
g
(
1,2
)
4
4(see Figure 3), respectively.


#### 4.3.2. Shared-Key Discovery Phase

In our scheme, after shared key establishment, each node should save the hashed keys in its key ring. For example, it is supposed that an sensora
(
r
,
c
)
i is pre-distributed two keys k
j
1
i and k
j
2
(
i
,
l
). As soon as the shared keys establishment between a
(
r
,
c
)
i and other nodes is finished, a
(
r
,
c
)
i saves the two following hashed keys: H
2
(
k
j
1
i
,
I
D
a
(
r
,
c
)
i
) and H
2
(
k
j
2
(
i
,
l
)
,
I
D
a
(
r
,
c
)
i
), where I
D
a
(
r
,
c
)
iis the identity of node a
(
r
,
c
)
i.Next, we will describe the method for any two nodesa
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2 (in the following analysis, a and b are short for a
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2) to establish a shared key at length. Similarly, in the following analysis, it is supposed that T
a
≥
T
b, where T
a and T
b represent the deployment time of nodes a and b, respectively. And in our scheme, if nodes a and b are deployed in the same cell or the neighboring cells, then they can establish a pairwise key, otherwise, they cannot.Ifr
1
=
r
2 and c
1
=
c
2, when T
a
=
T
b, the values of i
1 and i
2 are equal. The pairwise key between them consists of the following three parts (see Figure 4(a)): (1)x
1 generation keys, k
j
1
i
1
,
…
,
k
j
x
1
i
1, which come from the generation key pools; (2)x
2 ordinary keys, k
j
1
′
(
i
1
,
l
1
)
,
…
,
k
j
x
2
′
(
i
1
,
l
x
2
), which come from the ordinary key pools P
c
(
r
1
,
c
1
)
s
i
1
(
0
≤
s
≤
6
); (3)x
3 ordinary keys, which come from the ordinary key pool P
c
(
r
1
,
c
1
)
0
i
1. For example, let keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1
,
k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) and k
j
1
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
)
,
k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2 be predistributed to nodes a and b, respectively. Nodes a and b can calculate the keys k
j
2
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
) and k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) by using the keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1 and k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2and the method described in Section 4.1. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), the pairwise key between them consists of the following two parts (see Figure 4(b)). (1)x
1 hashed generation keys, H
(
k
j
1
i
1
,
I
D
b
)
,
…
,
H
(
k
j
x
1
i
1
,
I
D
b
). Node a can calculate these keys by using the predistributed keys  k
j
1
i
2
,
…
,
k
j
x
1
i
2 and the method described in Section 4.1 and in Section 4.3.2. (2)x
3 hashed ordinary keys, H
(
k
j
1
′′
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
l
x
3
(
i
1
,
l
x
′
)
,
I
D
b
). Node a can calculate these keys by using the predistributed keys k
j
1
′′
i
2
,
…
,
k
j
x
1
′′
i
2 from the key pool P
g
(
r
1
,
c
1
)
0
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)If cells(
r
1
,
c
2
) and (
r
2
,
c
2
) are neighbor cells, the values of x
1 and x
2 are equal to 0. When T
a
=
T
b, shared keys between them include x
′ and x
′′
=
x
3
-
x
′ ordinary keys (see Figure 5(a)), k
j
1
(
i
1
,
l
1
)
,
…
,
k
j
x
′
(
i
1
,
l
x
′
) and k
j
1
′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
-
x
′
′
(
i
2
,
l
x
3
-
x
′
′
), which come from the ordinary key pool P
c
(
r
1
,
c
1
)
s
a
i
1 (s
a
∈
[
1,6
]) and P
c
(
r
2
,
c
2
)
s
b
i
2 (s
b
∈
[
1,6
]), respectively. Nodes b and a can calculate these keys by using these predistributed keys k
j
1
i
1
,
…
,
k
j
x
′
i
1 and k
j
1
′
i
2
,
…
,
k
j
x
3
-
x
′
′
i
2, respectively. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), common keys between them contain x
3
=
x
′ hashed ordinary keys (see Figure 5(b)), H
(
k
j
1
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
x
3
(
i
1
,
l
x
3
)
,
I
D
b
). Node a can calculate these keys by using the generation keys of these keys k
j
1
i
1
,
…
,
k
j
x
3
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)As a result, if the number of shared keys is larger than 0, that is,x
1
+
x
2
+
x
3
≥
1, the shared key between them is hashed by all common keys.


## 4.1. Two-Dimensional Backward Key Chain

In [21], a two-dimensional backward key chain is constructed (see Figure 2). For a two-dimensional backward key chain C
j, if the key k
j
i
1 is known, the key k
j
i
2 (i
2
≤
i
1), the generation key g
j
i
2, and the first key k
j
(
i
2
,
0
) of the second dimensional key chain can be calculated as follows, respectively: k
j
i
2
=
H
1
i
1
-
i
2
(
k
j
i
1
), g
j
i
2
=
H
2
(
k
j
i
2
,
0
), and k
j
(
i
2
,
0
)
=
H
2
(
k
j
i
2
,
1
), where H
1 and H
2 are two independent hash functions. So, the key k
j
(
i
2
,
l
2
)
(
l
2
≥
1
) can be computed as follows:
(2)
k
j
(
i
2
,
l
2
)
=
H
2
l
2
(
g
j
i
2
,
k
j
(
i
2
,
0
)
)
,
when
l
2
≥
1
.
If the keys k
j
i
1 and k
j
(
i
2
,
l
1
) are known, the key k
j
(
i
2
,
l
2
) (l
1
<
l
2) can be computed using the following equation:
(3)
k
j
(
i
2
,
l
2
)
=
H
2
l
2
-
l
1
(
g
j
i
2
,
k
j
(
i
2
,
l
1
)
)
,
when
l
2
>
l
1
.Figure 2
Two-dimensional key chain.


## 4.2. Key Pool

In our scheme, the key pool is made up by two-dimensional backward key chains [21]. The key pool of the cell (
r
,
c
), namely, P
(
r
,
c
), which consists of m two-dimensional backward hash key chains, is divided inton phases according to the generation of the keys. P
(
r
,
c
)
i represents the ith-phase key pool of the cell (
r
,
c
). P
(
r
,
c
)
i is divided into seven equal size subkey pools, and P
(
r
,
c
)
s
i represents the sth (
0
≤
s
≤
6
) pool (see Figure 3). P
(
r
,
c
)
s
i consists of the following two parts: one is a generation key pool P
g
(
r
,
c
)
s
i
=
{
k
j
i
,
j
∈
[
1
,
m
]
} and the other is an ordinary key pool P
c
(
r
,
c
)
s
i
=
{
k
j
(
i
,
l
)
,
j
∈
[
1
,
m
]
,
1
≤
l
≤
L
}.Figure 3
Subkey pools.


## 4.3. Our Scheme

Our scheme consists of three phases: key predistribution phase, shared-key discovery phase, and path-key establishment phase. Although path-key establishment phase is the same as, key predistribution phase and share-key discover phase are different in the previous schemes [16, 17, 20]. The details of our scheme are described below.


### 4.3.1. Key Predistribution Phase

This phase is conducted offline before sensor nodes are deployed. A nodea
(
r
,
c
)
i deployed in theith deployment phase and its deployment point locates in the cell (
r
,
c
), is predistributed the following keys.Step
1. Select randomly and uniformly t
1 (t
1 is a system parameter) keys from P
c
(
r
,
c
)
s
i
(
1
≤
s
≤
6
). In this step, the total number of predistribution keys of the node is 6
×
t
1.Step
2. Select randomly and uniformly t
2 (t
2 is a system parameter) keys from P
c
(
r
,
c
)
0
i.Step
3. Select randomly and uniformly t
3 (t
3 is a system parameter) keys from P
g
(
r
,
c
)
0
i, and meet the following condition: the number of keys from a two-dimensional backward hash key chain is no more than 1. For example, it is supposed that k
j
(
i
,
l
1
) has been predistributed to a
(
r
,
c
)
i and k
j
i cannot be predistributed to a
(
r
,
c
)
i.Step
4. Select randomly and uniformly t
3 keys from P
g
(
r
′
,
c
′
)
s
′
i
′, where (
r
′
,
c
′
) is the neighbor cell of (
r
,
c
), P
g
(
r
′
,
c
′
)
s
′
i
′ represents the generation key pool of the cell (
r
′
,
c
′
), and i
′ denotes the recent deployment phase. For example, if the deployment phase of cells (
1,1
) and (
1,2
) is 2 and 3, respectively, and new nodes are needed to be added to cell (
1,2
), but no new nodes are needed to be added to cell (
1,1
); then a
(
1,2
)
4 should pick t
3 keys from P
g
(
1,1
)
1
2(see Figure 3). But if both cells (
1,1
) and (
1,2
) need to add new nodes, then a
(
1,2
)
4 and b
(
1,1
)
3 should pick t
3 keys from P
g
(
1,1
)
1
3 and P
g
(
1,2
)
4
4(see Figure 3), respectively.


### 4.3.2. Shared-Key Discovery Phase

In our scheme, after shared key establishment, each node should save the hashed keys in its key ring. For example, it is supposed that an sensora
(
r
,
c
)
i is pre-distributed two keys k
j
1
i and k
j
2
(
i
,
l
). As soon as the shared keys establishment between a
(
r
,
c
)
i and other nodes is finished, a
(
r
,
c
)
i saves the two following hashed keys: H
2
(
k
j
1
i
,
I
D
a
(
r
,
c
)
i
) and H
2
(
k
j
2
(
i
,
l
)
,
I
D
a
(
r
,
c
)
i
), where I
D
a
(
r
,
c
)
iis the identity of node a
(
r
,
c
)
i.Next, we will describe the method for any two nodesa
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2 (in the following analysis, a and b are short for a
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2) to establish a shared key at length. Similarly, in the following analysis, it is supposed that T
a
≥
T
b, where T
a and T
b represent the deployment time of nodes a and b, respectively. And in our scheme, if nodes a and b are deployed in the same cell or the neighboring cells, then they can establish a pairwise key, otherwise, they cannot.Ifr
1
=
r
2 and c
1
=
c
2, when T
a
=
T
b, the values of i
1 and i
2 are equal. The pairwise key between them consists of the following three parts (see Figure 4(a)): (1)x
1 generation keys, k
j
1
i
1
,
…
,
k
j
x
1
i
1, which come from the generation key pools; (2)x
2 ordinary keys, k
j
1
′
(
i
1
,
l
1
)
,
…
,
k
j
x
2
′
(
i
1
,
l
x
2
), which come from the ordinary key pools P
c
(
r
1
,
c
1
)
s
i
1
(
0
≤
s
≤
6
); (3)x
3 ordinary keys, which come from the ordinary key pool P
c
(
r
1
,
c
1
)
0
i
1. For example, let keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1
,
k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) and k
j
1
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
)
,
k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2 be predistributed to nodes a and b, respectively. Nodes a and b can calculate the keys k
j
2
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
) and k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) by using the keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1 and k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2and the method described in Section 4.1. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), the pairwise key between them consists of the following two parts (see Figure 4(b)). (1)x
1 hashed generation keys, H
(
k
j
1
i
1
,
I
D
b
)
,
…
,
H
(
k
j
x
1
i
1
,
I
D
b
). Node a can calculate these keys by using the predistributed keys  k
j
1
i
2
,
…
,
k
j
x
1
i
2 and the method described in Section 4.1 and in Section 4.3.2. (2)x
3 hashed ordinary keys, H
(
k
j
1
′′
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
l
x
3
(
i
1
,
l
x
′
)
,
I
D
b
). Node a can calculate these keys by using the predistributed keys k
j
1
′′
i
2
,
…
,
k
j
x
1
′′
i
2 from the key pool P
g
(
r
1
,
c
1
)
0
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)If cells(
r
1
,
c
2
) and (
r
2
,
c
2
) are neighbor cells, the values of x
1 and x
2 are equal to 0. When T
a
=
T
b, shared keys between them include x
′ and x
′′
=
x
3
-
x
′ ordinary keys (see Figure 5(a)), k
j
1
(
i
1
,
l
1
)
,
…
,
k
j
x
′
(
i
1
,
l
x
′
) and k
j
1
′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
-
x
′
′
(
i
2
,
l
x
3
-
x
′
′
), which come from the ordinary key pool P
c
(
r
1
,
c
1
)
s
a
i
1 (s
a
∈
[
1,6
]) and P
c
(
r
2
,
c
2
)
s
b
i
2 (s
b
∈
[
1,6
]), respectively. Nodes b and a can calculate these keys by using these predistributed keys k
j
1
i
1
,
…
,
k
j
x
′
i
1 and k
j
1
′
i
2
,
…
,
k
j
x
3
-
x
′
′
i
2, respectively. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), common keys between them contain x
3
=
x
′ hashed ordinary keys (see Figure 5(b)), H
(
k
j
1
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
x
3
(
i
1
,
l
x
3
)
,
I
D
b
). Node a can calculate these keys by using the generation keys of these keys k
j
1
i
1
,
…
,
k
j
x
3
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)As a result, if the number of shared keys is larger than 0, that is,x
1
+
x
2
+
x
3
≥
1, the shared key between them is hashed by all common keys.


## 4.3.1. Key Predistribution Phase

This phase is conducted offline before sensor nodes are deployed. A nodea
(
r
,
c
)
i deployed in theith deployment phase and its deployment point locates in the cell (
r
,
c
), is predistributed the following keys.Step
1. Select randomly and uniformly t
1 (t
1 is a system parameter) keys from P
c
(
r
,
c
)
s
i
(
1
≤
s
≤
6
). In this step, the total number of predistribution keys of the node is 6
×
t
1.Step
2. Select randomly and uniformly t
2 (t
2 is a system parameter) keys from P
c
(
r
,
c
)
0
i.Step
3. Select randomly and uniformly t
3 (t
3 is a system parameter) keys from P
g
(
r
,
c
)
0
i, and meet the following condition: the number of keys from a two-dimensional backward hash key chain is no more than 1. For example, it is supposed that k
j
(
i
,
l
1
) has been predistributed to a
(
r
,
c
)
i and k
j
i cannot be predistributed to a
(
r
,
c
)
i.Step
4. Select randomly and uniformly t
3 keys from P
g
(
r
′
,
c
′
)
s
′
i
′, where (
r
′
,
c
′
) is the neighbor cell of (
r
,
c
), P
g
(
r
′
,
c
′
)
s
′
i
′ represents the generation key pool of the cell (
r
′
,
c
′
), and i
′ denotes the recent deployment phase. For example, if the deployment phase of cells (
1,1
) and (
1,2
) is 2 and 3, respectively, and new nodes are needed to be added to cell (
1,2
), but no new nodes are needed to be added to cell (
1,1
); then a
(
1,2
)
4 should pick t
3 keys from P
g
(
1,1
)
1
2(see Figure 3). But if both cells (
1,1
) and (
1,2
) need to add new nodes, then a
(
1,2
)
4 and b
(
1,1
)
3 should pick t
3 keys from P
g
(
1,1
)
1
3 and P
g
(
1,2
)
4
4(see Figure 3), respectively.


## 4.3.2. Shared-Key Discovery Phase

In our scheme, after shared key establishment, each node should save the hashed keys in its key ring. For example, it is supposed that an sensora
(
r
,
c
)
i is pre-distributed two keys k
j
1
i and k
j
2
(
i
,
l
). As soon as the shared keys establishment between a
(
r
,
c
)
i and other nodes is finished, a
(
r
,
c
)
i saves the two following hashed keys: H
2
(
k
j
1
i
,
I
D
a
(
r
,
c
)
i
) and H
2
(
k
j
2
(
i
,
l
)
,
I
D
a
(
r
,
c
)
i
), where I
D
a
(
r
,
c
)
iis the identity of node a
(
r
,
c
)
i.Next, we will describe the method for any two nodesa
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2 (in the following analysis, a and b are short for a
(
r
1
,
c
1
)
i
1 and b
(
r
2
,
c
2
)
i
2) to establish a shared key at length. Similarly, in the following analysis, it is supposed that T
a
≥
T
b, where T
a and T
b represent the deployment time of nodes a and b, respectively. And in our scheme, if nodes a and b are deployed in the same cell or the neighboring cells, then they can establish a pairwise key, otherwise, they cannot.Ifr
1
=
r
2 and c
1
=
c
2, when T
a
=
T
b, the values of i
1 and i
2 are equal. The pairwise key between them consists of the following three parts (see Figure 4(a)): (1)x
1 generation keys, k
j
1
i
1
,
…
,
k
j
x
1
i
1, which come from the generation key pools; (2)x
2 ordinary keys, k
j
1
′
(
i
1
,
l
1
)
,
…
,
k
j
x
2
′
(
i
1
,
l
x
2
), which come from the ordinary key pools P
c
(
r
1
,
c
1
)
s
i
1
(
0
≤
s
≤
6
); (3)x
3 ordinary keys, which come from the ordinary key pool P
c
(
r
1
,
c
1
)
0
i
1. For example, let keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1
,
k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) and k
j
1
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
)
,
k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2 be predistributed to nodes a and b, respectively. Nodes a and b can calculate the keys k
j
2
′′
(
i
1
,
l
1
)
,
…
,
k
j
l
x
′
′′
(
i
1
,
l
x
′
) and k
j
l
x
′
+
1
′′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
′′
(
i
2
,
l
x
3
-
l
x
′
′
) by using the keys k
j
1
′′
i
1
,
…
,
k
j
l
x
′
′′
i
1 and k
j
x
′
+
1
′′
i
2
,
…
,
k
j
x
3
′′
i
2and the method described in Section 4.1. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), the pairwise key between them consists of the following two parts (see Figure 4(b)). (1)x
1 hashed generation keys, H
(
k
j
1
i
1
,
I
D
b
)
,
…
,
H
(
k
j
x
1
i
1
,
I
D
b
). Node a can calculate these keys by using the predistributed keys  k
j
1
i
2
,
…
,
k
j
x
1
i
2 and the method described in Section 4.1 and in Section 4.3.2. (2)x
3 hashed ordinary keys, H
(
k
j
1
′′
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
l
x
3
(
i
1
,
l
x
′
)
,
I
D
b
). Node a can calculate these keys by using the predistributed keys k
j
1
′′
i
2
,
…
,
k
j
x
1
′′
i
2 from the key pool P
g
(
r
1
,
c
1
)
0
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)If cells(
r
1
,
c
2
) and (
r
2
,
c
2
) are neighbor cells, the values of x
1 and x
2 are equal to 0. When T
a
=
T
b, shared keys between them include x
′ and x
′′
=
x
3
-
x
′ ordinary keys (see Figure 5(a)), k
j
1
(
i
1
,
l
1
)
,
…
,
k
j
x
′
(
i
1
,
l
x
′
) and k
j
1
′
(
i
2
,
l
1
′
)
,
…
,
k
j
x
3
-
x
′
′
(
i
2
,
l
x
3
-
x
′
′
), which come from the ordinary key pool P
c
(
r
1
,
c
1
)
s
a
i
1 (s
a
∈
[
1,6
]) and P
c
(
r
2
,
c
2
)
s
b
i
2 (s
b
∈
[
1,6
]), respectively. Nodes b and a can calculate these keys by using these predistributed keys k
j
1
i
1
,
…
,
k
j
x
′
i
1 and k
j
1
′
i
2
,
…
,
k
j
x
3
-
x
′
′
i
2, respectively. When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), common keys between them contain x
3
=
x
′ hashed ordinary keys (see Figure 5(b)), H
(
k
j
1
(
i
1
,
l
1
)
,
I
D
b
)
,
…
,
H
(
k
j
x
3
(
i
1
,
l
x
3
)
,
I
D
b
). Node a can calculate these keys by using the generation keys of these keys k
j
1
i
1
,
…
,
k
j
x
3
i
1 and the same method as the previous.The common key between two sensors, wherei
1
>
i
2 in (b).
(a)
(b)As a result, if the number of shared keys is larger than 0, that is,x
1
+
x
2
+
x
3
≥
1, the shared key between them is hashed by all common keys.


## 5. Performance Analysis and Simulation

In this section, we will analyze and simulate the performances of our scheme, including deployment model, local connectivity, communication overhead, and network resilience against node capture.In the following experiments, the involved main parameters subsequent are defined as follows.(1)
We consider a SN deployed over fields of 475 m by 520 m.
(2)
The area is divided into a hexagon andlen is 50.
(3)
The center of each cell is the deployment point (see Figure1).
(4)
The number of nodes in aG
(
r
,
c
) is 50 (
N
=
50
).
(5)
The wireless communication range for a node is 40 m.
(6)
We assume that node deployment follows a two-dimensional Gaussian distribution [27], and its standard deviation is σ
=
40.
(7)
We assume that node deployment includes 5 phases. The value ofρ
0 is 0.7.
(8)
The number of key pool of a cell, namely,m, is 175, and the length of a forward key chain is 30 (
L
=
30
).


### 5.1.ρ
0

In the capture model, when an attacker locates in a cell, he can capture nodes around it. In this paper, it is supposed that compromised nodes can be identified by using schemes proposed by some scholars, such as [28]. But how can we determine the value of ρ
0 when we do not know nodes’ location information? The value of ρ
0 and the actual number of uncaptured nodes in a cell are closely related. For example, in the first phase, if nodes in cell (
0,0
) is 50, 50% of these nodes are captured, and the number of these captured nodes whose deployment points reside in cells (
0,0
), (
0,1
), (
1,0
), (
2,0
), (
1,1
), and (
0,2
) is 16, 3, 2, 2, 1, and 1, respectively. Here, it is supposed that these captured nodes can be identified. Therefore, ρ
(
0,0
), ρ
(
0,1
), ρ
(
1,0
), ρ
(
2,0
), ρ
(
1,1
), and ρ
(
0,2
) are equal to 0.68, 0.94, 0.96, 0.96, 0.98, and 0.98, respectively. When ρ
0
=
0.6, no new nodes are needed to be added to these cells, which will cause that only a few uncaptured nodes in cell (
0,0
) are working in a long time.Figure6 shows that the relation between the number of uncaptured nodes in a cell and the standard deviation of two-dimension normal distributions and ρ
0. In our simulations, the number of nodes in each cell is about 48, and if a cell is compromised, about 50% nodes in the cell are captured. When the ratio of nodes uncaptured in the set S
N
(
r
,
c
) is less than ρ
0, new nodes are needed to be added to cell (
r
,
c
). The larger the σ, the smaller the number of new nodes which actually reside in cell (
r
,
c
). Therefore, when σ increases, the number of nodes captured in cell (
r
,
c
) which come from G
(
r
,
c
) decreases. To ensure that nodes uncaptured in each cell are many, we must increase ρ
0. For example, after nodes are captured and new nodes are added to the network, to ensure that the average number of nodes in the captured cells is larger than 35, when σ
=
30 and σ
=
40, the value of ρ
0 should be set to 0.6 and 0.7, respectively. However, when σ
=
50, even if ρ
0 equals 0.8, the above goal cannot be achieved. In addition, the frequency of adding new nodes to the network increases with the increase of ρ
0. Therefore, the value of ρ
0 should be set in accordance with the specific condition. For example, when σ
=
30 and σ
=
40, we can set ρ
0 to 0.7.Figure 6
The average number of uncaptured nodes in a cell as a function of σ andρ
0.


### 5.2. Local Connectivity

For multiple deployment sensor networks, local connectivity is not only affected by the key predistribution method but also affected by the deployment model and the capture model. In this paper, only the analysis that local connectivity is affected by the key predistribution method is presented, that is, the probabilityP
(
a
,
b
) of shared key between nodes a and b.Ifr
1
=
r
2 and c
1
=
c
2, when T
b
=
T
a, the probability P
(
a
,
b
) can be calculated as follows: a and b have (
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2 different ways of picking their 6
t
1
+
t
2
+
7
t
3 keys from the ordinary key pools and the generation key pools. It is supposed that a and b have x two-dimensional backward key chains in common. The number of ways to pickx1 generation keys from generation key pools of neighbor cells and x
2 + x
3 ordinary keys from ordinary key pools P
c
(
r
1
,
c
1
)
s
i (see Section 4.3.2) can be calculated as follows:
(4)
P
x
=
∑
x
=
1
6
t
1
+
t
2
+
7
t
3
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
P
S
0
·
∏
i
=
1
6
(
m
7
y
i
)
·
(
m
7
-
y
i
2
(
t
3
-
y
i
)
)
∑
x
=
1
6
t
1
+
t
2
+
7
t
3
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
(
2
(
t
3
-
y
i
)
t
3
-
y
i
)
·
∏
i
=
1
6
∑
x
5
=
0
m
/
7
-
y
i
′
(
m
7
y
i
′
+
x
5
)
·
(
y
i
′
+
x
5
x
5
)
·
∏
i
=
1
6
∑
x
5
=
0
m
/
7
-
y
i
′
·
(
m
7
-
y
i
′
-
x
5
2
(
t
1
-
y
i
′
-
x
5
)
)
·
(
2
(
t
1
-
y
i
′
-
x
5
)
t
1
-
y
i
′
-
x
5
)
·
∏
i
=
1
6
∑
x
5
=
0
m
7
-
y
i
′
·
(
L
1
)
2
t
1
-
y
i
′
-
2
x
5
·
(
L
-
1
1
)
x
5
,
where P
S
0 can be calculated as
(5)
P
S
0
=
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
(
m
7
x
3
+
y
0
+
y
0
′
+
x
4
)
·
(
y
0
′
+
x
4
x
4
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
m
7
-
x
3
-
y
0
-
y
0
′
-
x
4
2
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
)
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
2
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
)
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
t
3
-
x
′
-
y
0
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
t
3
-
x
′′
-
y
0
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
L
1
)
2
t
2
-
y
0
′
-
2
x
4
·
(
L
-
1
1
)
x
4
.WhenT
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), x
′′
=
x
2
=
0. The number of ways to pickx1 generation keys from generation key pools of neighbor cells and thex3 ordinary keys from ordinary key pools P
c
(
r
1
,
c
1
)
s
i (see Section 4.3.2) can be calculated as follows:
(6)
P
x
′
=
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
P
S
0
′
·
∏
i
=
1
6
·
(
m
7
-
y
i
2
(
t
3
-
y
i
)
)
·
(
2
(
t
3
-
y
i
)
t
3
-
y
i
)
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
∏
i
=
1
6
(
m
7
y
i
′
)
·
(
m
7
-
y
i
′
2
(
t
1
-
y
i
′
)
)
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
∏
i
=
1
6
·
(
2
(
t
1
-
y
i
′
)
t
1
-
y
i
′
)
·
(
L
1
)
12
t
1
,
where P
S
0
′ can be calculated as
(7)
P
S
0
′
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
(
m
7
x
3
+
y
0
)
·
(
x
3
+
y
0
x
3
)
·
(
m
7
-
x
3
-
y
0
2
(
t
2
+
t
3
-
x
3
-
y
0
)
)
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
·
(
2
(
t
2
+
t
3
-
x
3
-
y
0
)
t
2
+
t
3
-
x
3
-
y
0
)
·
(
t
2
+
t
3
-
x
3
-
y
0
t
3
-
x
′
-
y
0
)
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
·
(
t
2
+
t
3
-
x
3
-
y
0
t
3
-
y
0
)
·
(
L
1
)
2
t
2
.Hence, ifr
1
=
r
2 and c
1
=
c
2, we have
(8)
P
(
a
,
b
)
=
{
P
x
(
(
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2
)
2
when
T
a
=
T
b
,
where
x
=
x
1
+
x
2
+
x
3
P
x
′
(
(
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2
)
2
when
T
a
≠
T
b
,
where
x
=
x
1
+
x
3
.If cells(
r
1
,
c
1
) and (
r
2
,
c
2
) are neighbor cells, x
1
=
x
2
=
0. When T
b
=
T
a, a and b have (
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1 different ways of picking t
1 ordinary keys from the ordinary key pool and t
3 ordinary keys from the generation key pool. The number of ways to pick the x
(
x
=
x
′
+
x
′′
) common keys can be calculated as follows:
(9)
P
1
x
=
(
m
7
t
1
)
·
(
m
7
t
1
)
·
(
L
1
)
2
t
1

·

∑
x
=
x
3
=
1
t
3
∑
x
′
+
x
′′
=
x
3
(
t
1
x
′
)

·

(
t
1
x
′′
)
·
(
m
7
-
t
1
t
3
-
x
′′
)
·
(
m
7
-
t
1
t
3
-
x
′
)
.
When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), x
1
=
x
2
=
x
′′
=
0. The number of ways to pick the x
(
x
=
x
′
) keys can be calculated as follows:
(10)
P
1
x
′
=
(
m
7
t
1
)
·
(
m
7
t
1
)
·
(
m
7
t
3
)
·
(
L
1
)
2
t
1
·
∑
x
3
=
1
t
3
(
t
1
x
3
)
·
(
m
7
-
t
1
t
3
-
x
3
)
.Hence, if cells(
r
1
,
c
1
) and (
r
2
,
c
2
) are neighbor cells, we have(11)
P
(
a
,
b
)
=
{
P
1
x
(
(
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1
)
2
=
∑
x
=
x
3
=
1
t
3
∑
x
′
+
x
′′
=
x
3
(
t
1
x
′
)
·
(
t
1
x
′′
)
·
(
m
/
7
-
t
1
t
3
-
x
′′
)
·
(
m
/
7
-
t
1
t
3
-
x
′
)
(
m
/
7
t
3
)
2
when
T
a
=
T
b
P
1
x
′
(
(
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1
)
2
=
∑
x
3
=
1
t
3
(
t
1
x
3
)
·
(
m
/
7
-
t
1
t
3
-
x
3
)
(
m
/
7
t
3
)
when
T
a
≠
T
b
.If cell(
r
1
,
c
1
) and cell (
r
2
,
c
2
) are not neighbor cells, the probability P
(
a
,
b
) is equal to 0.Figure7 shows that local connectivity of our scheme is high. For example, when t
1
=
10, t
2
=
20, and t
3
=
2, the local connectivity in the first phase is 0.936. And in this case, the number of keys predistributed to a node is 10
×
6
+
20
+
2
×
7
=
94 only. In addition, Figure 7 shows that the larger the value oft1 andt3, the higher the local connectivity. For example, the value of t
1 increases from 5 to 15 and t
3 increases from 1 to 3; local connectivity increases by 0.135 and 0.117, respectively. However, in this case, for a node, the storage overheads increase by 60 and 14, respectively. As a result, we can have a conclusion that the parameter t
3 has a great influence on local connectivity. The larger the value of t
3 is, the higher the local connectivity is. However, the larger the value of t
3, the more keys compromised when nodes are captured. If a node is captured, the number of keys compromised can be calculated by 6
×
t
1
+
t
2
+
7
×
t
3
×
i
a
×
L, where i
a represents the deployment phase of node a. When i
a and L are 5 and 30, respectively, t
3 increases from 1 to 3; the number of keys compromised increases by 7
×
2
×
5
×
30
=
2100
≫
6
×
10
=
60. Therefore, concerning safety, t
3 should be as small as possible. On the other hand, Figure 7 shows that the larger the number of deployment phases, the smaller the local connectivity. However, after multiple deployments, local connectivity can keep basically stable. For example, from the 4th phase to the 5th phase, local connectivity decreases by less than 0.01.Local connectivity as a function of various parameters.
(a)
t
2
=
20, t
3
=
2
(b)
t
1
=
10, t
3
=
2
(c)
t
1
=
10, t
2
=
20


### 5.3. Communication Overhead

If direct key establishment fails, two sensor nodes need to start on path-key establishment phase to establish a pairwise key with the help of other sensor nodes. To establish a pairwise key with nodeb, node a needs to find a sequence of nodes between itself and node b such that any two adjacent nodes in this sequence can establish a direct key. For the sake of presentation, we call such a sequence of nodes akey path.In this section, we investigate the number of hops required on this path for various parameters of our scheme. Let ph(h) be the probability that the smallest number of hops needed to connect two neighboring nodes is h. Obviously, ph
(
1
) is local connectivity.In our scheme, after the 5th deployment, the local connectivity keeps basically stable. So, we plot the values ofph
(
1
), ph
(
2
), ph
(
3
), and ph
(
4
) of the four phases (see Figure 8). From the figure, we can observe that ph
(
1
)
+
ph
(
2
)
≈
1 (i.e., the probability that at most 2 hops are required is essentially 1).Figure 8
Distribution of the number of hops required to connect neighbors.


### 5.4. Comparisons

In this section, performance and security between our scheme and YG scheme [17] and ESPK scheme [20], are compared. For the sake of fairness, in YG and ESPK, the method for processing keys is same as our scheme. In this simulation, t
1, t
2, and t
3 of our scheme is 10, 20, and 2, respectively. The predistribution keys of YG and ESPK scheme is same as our scheme. Other parameters are same as Section 5.


#### 5.4.1. Local Connectivity

With the same storage overhead, Figure9 shows that, in each deployment phase, local connectivity of our scheme is higher than YG scheme andESPK scheme. InESPK scheme, nodes which come from different deployment phase but reside in the same cell cannot communicate with each other. Its local connectivity is the lowest. Fox example, in the fifth phase, local connectivity of our scheme, YG scheme, and ESPK scheme is 0.88, 0.86, and 0.46, respectively.Figure 9
Comparing the local connectivity of our, YG, and ESPK scheme.


#### 5.4.2. Global Connectivity

If local connectivity is less than 1, nodes in SNs may be divided into one or more isolated components. Any two nodes in an isolated component can securely communicate with each other directly or indirectly (Figure10). Global connectivity refers to the ratio of the number of nodes in the largest isolated component to the size of the whole network. If the ratio equals 98%, it means that 98% of the sensor nodes are connected securely and the remaining 2% are unreachable from the largest isolated component. So, global connectivity metric indicates the percentage of nodes that are wasted because of their unreachability.Figure 10
Comparing the global connectivity of our, YG, and ESPK scheme.In this work, we use simulation to estimate it. InESPK scheme, nodes which reside in the same cell but are deployed in different deployment phases can establish shared keys only by using path keys. For a node, if it cannot find a path to establish shared key with neighbouring nodes, then it is an isolated node. Therefore, the global connectivity of the scheme is the lowest. Fox example, in the fifth phase, global connectivity of our scheme, YG scheme, and ESPK scheme is 0.99955, 0.99941, and 0.94499, respectively.


#### 5.4.3. Resilience

A scheme’s resilience toward node capture is evaluated by estimating the fraction of total network communications that are compromised by a capture ofx nodesnot includingthe communications in which the compromised nodes are directly involved.We conducted simulation tests on network resilience against node capture of the above three schemes. In our simulations, it is supposed that only a few nodes are compromised during the shared-key discovery phase. In ESPK scheme, the key pools of nodes from different deployment phase are different. Therefore, its network resilience against node capture is the best. In YG scheme, the key pool is fixed. Therefore, increases in the number of captured nodes will diminish network resilience. For example, whenC
C
=
30, Figure 11 shows the probability that a shared key is compromised in the first phase and the 5th phase is 0.04 and 0.31, respectively. In our scheme, the subkey pool of the ith phase and the i
′
th phase is disjoint, that is, P
(
r
,
c
)
i
∩
P
(
r
,
c
)
i
′
=
ϕ (i
≠
i
′). Therefore, compared with YG scheme, our scheme can improve the performance in network resilience against node capture attacks. For example, when C
C
=
30, in our scheme, the probability that shared keys are compromised in the 5th phase is 0.09.Figure 11
Comparing the resilience of our, YG, and ESPK scheme. WhereC
C is the number of nodes captured by an attacker during the period of the direct key establishment phase.


## 5.1.ρ
0

In the capture model, when an attacker locates in a cell, he can capture nodes around it. In this paper, it is supposed that compromised nodes can be identified by using schemes proposed by some scholars, such as [28]. But how can we determine the value of ρ
0 when we do not know nodes’ location information? The value of ρ
0 and the actual number of uncaptured nodes in a cell are closely related. For example, in the first phase, if nodes in cell (
0,0
) is 50, 50% of these nodes are captured, and the number of these captured nodes whose deployment points reside in cells (
0,0
), (
0,1
), (
1,0
), (
2,0
), (
1,1
), and (
0,2
) is 16, 3, 2, 2, 1, and 1, respectively. Here, it is supposed that these captured nodes can be identified. Therefore, ρ
(
0,0
), ρ
(
0,1
), ρ
(
1,0
), ρ
(
2,0
), ρ
(
1,1
), and ρ
(
0,2
) are equal to 0.68, 0.94, 0.96, 0.96, 0.98, and 0.98, respectively. When ρ
0
=
0.6, no new nodes are needed to be added to these cells, which will cause that only a few uncaptured nodes in cell (
0,0
) are working in a long time.Figure6 shows that the relation between the number of uncaptured nodes in a cell and the standard deviation of two-dimension normal distributions and ρ
0. In our simulations, the number of nodes in each cell is about 48, and if a cell is compromised, about 50% nodes in the cell are captured. When the ratio of nodes uncaptured in the set S
N
(
r
,
c
) is less than ρ
0, new nodes are needed to be added to cell (
r
,
c
). The larger the σ, the smaller the number of new nodes which actually reside in cell (
r
,
c
). Therefore, when σ increases, the number of nodes captured in cell (
r
,
c
) which come from G
(
r
,
c
) decreases. To ensure that nodes uncaptured in each cell are many, we must increase ρ
0. For example, after nodes are captured and new nodes are added to the network, to ensure that the average number of nodes in the captured cells is larger than 35, when σ
=
30 and σ
=
40, the value of ρ
0 should be set to 0.6 and 0.7, respectively. However, when σ
=
50, even if ρ
0 equals 0.8, the above goal cannot be achieved. In addition, the frequency of adding new nodes to the network increases with the increase of ρ
0. Therefore, the value of ρ
0 should be set in accordance with the specific condition. For example, when σ
=
30 and σ
=
40, we can set ρ
0 to 0.7.Figure 6
The average number of uncaptured nodes in a cell as a function of σ andρ
0.


## 5.2. Local Connectivity

For multiple deployment sensor networks, local connectivity is not only affected by the key predistribution method but also affected by the deployment model and the capture model. In this paper, only the analysis that local connectivity is affected by the key predistribution method is presented, that is, the probabilityP
(
a
,
b
) of shared key between nodes a and b.Ifr
1
=
r
2 and c
1
=
c
2, when T
b
=
T
a, the probability P
(
a
,
b
) can be calculated as follows: a and b have (
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2 different ways of picking their 6
t
1
+
t
2
+
7
t
3 keys from the ordinary key pools and the generation key pools. It is supposed that a and b have x two-dimensional backward key chains in common. The number of ways to pickx1 generation keys from generation key pools of neighbor cells and x
2 + x
3 ordinary keys from ordinary key pools P
c
(
r
1
,
c
1
)
s
i (see Section 4.3.2) can be calculated as follows:
(4)
P
x
=
∑
x
=
1
6
t
1
+
t
2
+
7
t
3
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
P
S
0
·
∏
i
=
1
6
(
m
7
y
i
)
·
(
m
7
-
y
i
2
(
t
3
-
y
i
)
)
∑
x
=
1
6
t
1
+
t
2
+
7
t
3
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
(
2
(
t
3
-
y
i
)
t
3
-
y
i
)
·
∏
i
=
1
6
∑
x
5
=
0
m
/
7
-
y
i
′
(
m
7
y
i
′
+
x
5
)
·
(
y
i
′
+
x
5
x
5
)
·
∏
i
=
1
6
∑
x
5
=
0
m
/
7
-
y
i
′
·
(
m
7
-
y
i
′
-
x
5
2
(
t
1
-
y
i
′
-
x
5
)
)
·
(
2
(
t
1
-
y
i
′
-
x
5
)
t
1
-
y
i
′
-
x
5
)
·
∏
i
=
1
6
∑
x
5
=
0
m
7
-
y
i
′
·
(
L
1
)
2
t
1
-
y
i
′
-
2
x
5
·
(
L
-
1
1
)
x
5
,
where P
S
0 can be calculated as
(5)
P
S
0
=
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
(
m
7
x
3
+
y
0
+
y
0
′
+
x
4
)
·
(
y
0
′
+
x
4
x
4
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
m
7
-
x
3
-
y
0
-
y
0
′
-
x
4
2
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
)
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
2
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
)
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
t
3
-
x
′
-
y
0
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
t
2
+
t
3
-
x
3
-
y
0
-
y
0
′
-
x
4
t
3
-
x
′′
-
y
0
)
∑
x
3
=
x
′
+
x
′′
=
1
t
3
-
y
0
∑
x
4
=
0
2
t
2
-
x
3
·
(
L
1
)
2
t
2
-
y
0
′
-
2
x
4
·
(
L
-
1
1
)
x
4
.WhenT
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), x
′′
=
x
2
=
0. The number of ways to pickx1 generation keys from generation key pools of neighbor cells and thex3 ordinary keys from ordinary key pools P
c
(
r
1
,
c
1
)
s
i (see Section 4.3.2) can be calculated as follows:
(6)
P
x
′
=
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
P
S
0
′
·
∏
i
=
1
6
·
(
m
7
-
y
i
2
(
t
3
-
y
i
)
)
·
(
2
(
t
3
-
y
i
)
t
3
-
y
i
)
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
∏
i
=
1
6
(
m
7
y
i
′
)
·
(
m
7
-
y
i
′
2
(
t
1
-
y
i
′
)
)
∑
x
=
1
6
t
1
+
t
2
∑
x
1
=
∑
i
=
0
6
y
i
,
x
2
=
∑
i
=
0
6
y
i
′
·
∏
i
=
1
6
·
(
2
(
t
1
-
y
i
′
)
t
1
-
y
i
′
)
·
(
L
1
)
12
t
1
,
where P
S
0
′ can be calculated as
(7)
P
S
0
′
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
(
m
7
x
3
+
y
0
)
·
(
x
3
+
y
0
x
3
)
·
(
m
7
-
x
3
-
y
0
2
(
t
2
+
t
3
-
x
3
-
y
0
)
)
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
·
(
2
(
t
2
+
t
3
-
x
3
-
y
0
)
t
2
+
t
3
-
x
3
-
y
0
)
·
(
t
2
+
t
3
-
x
3
-
y
0
t
3
-
x
′
-
y
0
)
=
∑
x
3
=
x
′
=
1
t
3
-
y
0
·
(
t
2
+
t
3
-
x
3
-
y
0
t
3
-
y
0
)
·
(
L
1
)
2
t
2
.Hence, ifr
1
=
r
2 and c
1
=
c
2, we have
(8)
P
(
a
,
b
)
=
{
P
x
(
(
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2
)
2
when
T
a
=
T
b
,
where
x
=
x
1
+
x
2
+
x
3
P
x
′
(
(
m
/
7
t
1
)
6
·
(
m
/
7
t
3
)
6
·
(
m
/
7
t
2
+
t
3
)
·
(
t
2
+
t
3
t
3
)
·
(
L
1
)
6
t
1
+
t
2
)
2
when
T
a
≠
T
b
,
where
x
=
x
1
+
x
3
.If cells(
r
1
,
c
1
) and (
r
2
,
c
2
) are neighbor cells, x
1
=
x
2
=
0. When T
b
=
T
a, a and b have (
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1 different ways of picking t
1 ordinary keys from the ordinary key pool and t
3 ordinary keys from the generation key pool. The number of ways to pick the x
(
x
=
x
′
+
x
′′
) common keys can be calculated as follows:
(9)
P
1
x
=
(
m
7
t
1
)
·
(
m
7
t
1
)
·
(
L
1
)
2
t
1

·

∑
x
=
x
3
=
1
t
3
∑
x
′
+
x
′′
=
x
3
(
t
1
x
′
)

·

(
t
1
x
′′
)
·
(
m
7
-
t
1
t
3
-
x
′′
)
·
(
m
7
-
t
1
t
3
-
x
′
)
.
When T
a
≠
T
b (without loss of generality, it is supposed that T
b
<
T
a), x
1
=
x
2
=
x
′′
=
0. The number of ways to pick the x
(
x
=
x
′
) keys can be calculated as follows:
(10)
P
1
x
′
=
(
m
7
t
1
)
·
(
m
7
t
1
)
·
(
m
7
t
3
)
·
(
L
1
)
2
t
1
·
∑
x
3
=
1
t
3
(
t
1
x
3
)
·
(
m
7
-
t
1
t
3
-
x
3
)
.Hence, if cells(
r
1
,
c
1
) and (
r
2
,
c
2
) are neighbor cells, we have(11)
P
(
a
,
b
)
=
{
P
1
x
(
(
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1
)
2
=
∑
x
=
x
3
=
1
t
3
∑
x
′
+
x
′′
=
x
3
(
t
1
x
′
)
·
(
t
1
x
′′
)
·
(
m
/
7
-
t
1
t
3
-
x
′′
)
·
(
m
/
7
-
t
1
t
3
-
x
′
)
(
m
/
7
t
3
)
2
when
T
a
=
T
b
P
1
x
′
(
(
m
/
7
t
1
)
·
(
m
/
7
t
3
)
·
(
L
1
)
t
1
)
2
=
∑
x
3
=
1
t
3
(
t
1
x
3
)
·
(
m
/
7
-
t
1
t
3
-
x
3
)
(
m
/
7
t
3
)
when
T
a
≠
T
b
.If cell(
r
1
,
c
1
) and cell (
r
2
,
c
2
) are not neighbor cells, the probability P
(
a
,
b
) is equal to 0.Figure7 shows that local connectivity of our scheme is high. For example, when t
1
=
10, t
2
=
20, and t
3
=
2, the local connectivity in the first phase is 0.936. And in this case, the number of keys predistributed to a node is 10
×
6
+
20
+
2
×
7
=
94 only. In addition, Figure 7 shows that the larger the value oft1 andt3, the higher the local connectivity. For example, the value of t
1 increases from 5 to 15 and t
3 increases from 1 to 3; local connectivity increases by 0.135 and 0.117, respectively. However, in this case, for a node, the storage overheads increase by 60 and 14, respectively. As a result, we can have a conclusion that the parameter t
3 has a great influence on local connectivity. The larger the value of t
3 is, the higher the local connectivity is. However, the larger the value of t
3, the more keys compromised when nodes are captured. If a node is captured, the number of keys compromised can be calculated by 6
×
t
1
+
t
2
+
7
×
t
3
×
i
a
×
L, where i
a represents the deployment phase of node a. When i
a and L are 5 and 30, respectively, t
3 increases from 1 to 3; the number of keys compromised increases by 7
×
2
×
5
×
30
=
2100
≫
6
×
10
=
60. Therefore, concerning safety, t
3 should be as small as possible. On the other hand, Figure 7 shows that the larger the number of deployment phases, the smaller the local connectivity. However, after multiple deployments, local connectivity can keep basically stable. For example, from the 4th phase to the 5th phase, local connectivity decreases by less than 0.01.Local connectivity as a function of various parameters.
(a)
t
2
=
20, t
3
=
2
(b)
t
1
=
10, t
3
=
2
(c)
t
1
=
10, t
2
=
20


## 5.3. Communication Overhead

If direct key establishment fails, two sensor nodes need to start on path-key establishment phase to establish a pairwise key with the help of other sensor nodes. To establish a pairwise key with nodeb, node a needs to find a sequence of nodes between itself and node b such that any two adjacent nodes in this sequence can establish a direct key. For the sake of presentation, we call such a sequence of nodes akey path.In this section, we investigate the number of hops required on this path for various parameters of our scheme. Let ph(h) be the probability that the smallest number of hops needed to connect two neighboring nodes is h. Obviously, ph
(
1
) is local connectivity.In our scheme, after the 5th deployment, the local connectivity keeps basically stable. So, we plot the values ofph
(
1
), ph
(
2
), ph
(
3
), and ph
(
4
) of the four phases (see Figure 8). From the figure, we can observe that ph
(
1
)
+
ph
(
2
)
≈
1 (i.e., the probability that at most 2 hops are required is essentially 1).Figure 8
Distribution of the number of hops required to connect neighbors.


## 5.4. Comparisons

In this section, performance and security between our scheme and YG scheme [17] and ESPK scheme [20], are compared. For the sake of fairness, in YG and ESPK, the method for processing keys is same as our scheme. In this simulation, t
1, t
2, and t
3 of our scheme is 10, 20, and 2, respectively. The predistribution keys of YG and ESPK scheme is same as our scheme. Other parameters are same as Section 5.


### 5.4.1. Local Connectivity

With the same storage overhead, Figure9 shows that, in each deployment phase, local connectivity of our scheme is higher than YG scheme andESPK scheme. InESPK scheme, nodes which come from different deployment phase but reside in the same cell cannot communicate with each other. Its local connectivity is the lowest. Fox example, in the fifth phase, local connectivity of our scheme, YG scheme, and ESPK scheme is 0.88, 0.86, and 0.46, respectively.Figure 9
Comparing the local connectivity of our, YG, and ESPK scheme.


### 5.4.2. Global Connectivity

If local connectivity is less than 1, nodes in SNs may be divided into one or more isolated components. Any two nodes in an isolated component can securely communicate with each other directly or indirectly (Figure10). Global connectivity refers to the ratio of the number of nodes in the largest isolated component to the size of the whole network. If the ratio equals 98%, it means that 98% of the sensor nodes are connected securely and the remaining 2% are unreachable from the largest isolated component. So, global connectivity metric indicates the percentage of nodes that are wasted because of their unreachability.Figure 10
Comparing the global connectivity of our, YG, and ESPK scheme.In this work, we use simulation to estimate it. InESPK scheme, nodes which reside in the same cell but are deployed in different deployment phases can establish shared keys only by using path keys. For a node, if it cannot find a path to establish shared key with neighbouring nodes, then it is an isolated node. Therefore, the global connectivity of the scheme is the lowest. Fox example, in the fifth phase, global connectivity of our scheme, YG scheme, and ESPK scheme is 0.99955, 0.99941, and 0.94499, respectively.


### 5.4.3. Resilience

A scheme’s resilience toward node capture is evaluated by estimating the fraction of total network communications that are compromised by a capture ofx nodesnot includingthe communications in which the compromised nodes are directly involved.We conducted simulation tests on network resilience against node capture of the above three schemes. In our simulations, it is supposed that only a few nodes are compromised during the shared-key discovery phase. In ESPK scheme, the key pools of nodes from different deployment phase are different. Therefore, its network resilience against node capture is the best. In YG scheme, the key pool is fixed. Therefore, increases in the number of captured nodes will diminish network resilience. For example, whenC
C
=
30, Figure 11 shows the probability that a shared key is compromised in the first phase and the 5th phase is 0.04 and 0.31, respectively. In our scheme, the subkey pool of the ith phase and the i
′
th phase is disjoint, that is, P
(
r
,
c
)
i
∩
P
(
r
,
c
)
i
′
=
ϕ (i
≠
i
′). Therefore, compared with YG scheme, our scheme can improve the performance in network resilience against node capture attacks. For example, when C
C
=
30, in our scheme, the probability that shared keys are compromised in the 5th phase is 0.09.Figure 11
Comparing the resilience of our, YG, and ESPK scheme. WhereC
C is the number of nodes captured by an attacker during the period of the direct key establishment phase.


## 5.4.1. Local Connectivity

With the same storage overhead, Figure9 shows that, in each deployment phase, local connectivity of our scheme is higher than YG scheme andESPK scheme. InESPK scheme, nodes which come from different deployment phase but reside in the same cell cannot communicate with each other. Its local connectivity is the lowest. Fox example, in the fifth phase, local connectivity of our scheme, YG scheme, and ESPK scheme is 0.88, 0.86, and 0.46, respectively.Figure 9
Comparing the local connectivity of our, YG, and ESPK scheme.


## 5.4.2. Global Connectivity

If local connectivity is less than 1, nodes in SNs may be divided into one or more isolated components. Any two nodes in an isolated component can securely communicate with each other directly or indirectly (Figure10). Global connectivity refers to the ratio of the number of nodes in the largest isolated component to the size of the whole network. If the ratio equals 98%, it means that 98% of the sensor nodes are connected securely and the remaining 2% are unreachable from the largest isolated component. So, global connectivity metric indicates the percentage of nodes that are wasted because of their unreachability.Figure 10
Comparing the global connectivity of our, YG, and ESPK scheme.In this work, we use simulation to estimate it. InESPK scheme, nodes which reside in the same cell but are deployed in different deployment phases can establish shared keys only by using path keys. For a node, if it cannot find a path to establish shared key with neighbouring nodes, then it is an isolated node. Therefore, the global connectivity of the scheme is the lowest. Fox example, in the fifth phase, global connectivity of our scheme, YG scheme, and ESPK scheme is 0.99955, 0.99941, and 0.94499, respectively.


## 5.4.3. Resilience

A scheme’s resilience toward node capture is evaluated by estimating the fraction of total network communications that are compromised by a capture ofx nodesnot includingthe communications in which the compromised nodes are directly involved.We conducted simulation tests on network resilience against node capture of the above three schemes. In our simulations, it is supposed that only a few nodes are compromised during the shared-key discovery phase. In ESPK scheme, the key pools of nodes from different deployment phase are different. Therefore, its network resilience against node capture is the best. In YG scheme, the key pool is fixed. Therefore, increases in the number of captured nodes will diminish network resilience. For example, whenC
C
=
30, Figure 11 shows the probability that a shared key is compromised in the first phase and the 5th phase is 0.04 and 0.31, respectively. In our scheme, the subkey pool of the ith phase and the i
′
th phase is disjoint, that is, P
(
r
,
c
)
i
∩
P
(
r
,
c
)
i
′
=
ϕ (i
≠
i
′). Therefore, compared with YG scheme, our scheme can improve the performance in network resilience against node capture attacks. For example, when C
C
=
30, in our scheme, the probability that shared keys are compromised in the 5th phase is 0.09.Figure 11
Comparing the resilience of our, YG, and ESPK scheme. WhereC
C is the number of nodes captured by an attacker during the period of the direct key establishment phase.


## 6. Conclusion and Future Work

In this paper, we proposed a new deployment model for multiple deployment sensor networks, based on which a new key management scheme is further presented. We conducted a comprehensive study on connectivity, network resilience of our scheme. The results showed that our scheme can significantly improve network resilience over the YG scheme [17]. Compared with the ESPK scheme [20], our scheme can significantly improve its local connectivity and global connectivity, although the resilience of our scheme is poorer than that of the scheme. We have presented both the analytical and numerical results. In our future work, we will study different attack models and the accuracy how attack model affects the results.



---

*Source: 573913-2014-06-15.xml*