# Trusted Tree-Based Trust Management Scheme for Secure Routing in Wireless Sensor Networks

Authors: Zhi Hu; Yuxia Bie; Hong Zhao
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

The unique characteristics of wireless sensor networks make them susceptible to the attacks. The secure scheme is considered in designing the routing protocol and algorithm. The cryptography and authentication secure technology can defend the external attacks but have no way to protect the network when the internal attacks occur. However, the trust management scheme with attack-resistance and robustness can efficiently detect the internal attack. On the condition of defending the attacks, it is also an issue that the trust management scheme aids routing algorithm to improve the security and performance. In this paper, we proposed a Trusted Tree-based trust management for secure routing in wireless sensor networks. The common attacks are firstly analyzed. And then the dynamic time window is designed in the distributed trust model with the detection of direct trust and indirect trust. Based on the trusted nodes, Trusted Tree is constructed. And the path quality of nodes in Trusted Tree is used as the gradient for routing. Finally, we add Trusted Tree-based trust management into the QoS based routing protocol and algorithm. Experimental results show that the QoS based routing algorithm with Trusted Tree has better performance and security.


---

## Body

## 1. Introduction

Wireless sensor networks are the most important elements in Internet of Things [1–4] and playing more and more key role in a wide range of application domains, such as habitat monitoring, disaster prevention, automation control, and infrastructural security [5–7]. These network nodes are equipped with the sensor and collect the data from the monitored environments.Since the communication range and computing ability of node are limited, the ad hoc routing protocol is used in wireless sensor networks [8, 9]. The traditional network protocol is not suitable for wireless sensor networks, and their security protocol can not be directly used to defend against the attacks in wireless sensor networks [10–12]. Many routing protocols and algorithms are designed for the efficient transmission of data in wireless sensor networks. The network threat is considered, such as flooding attack and eavesdropping attack. These attacks are divided into two types: internal attacks and external attacks [13, 14]. The cryptography and authentication are usually applied to the routing protocols to defend the external attacks, because the malicious nodes have no right to access the network. When the nodes are compromised and launch the internal attacks, the secure techniques with cryptography and authentication fail to protect the network security. For the internal attacks, the trust management is the effective method. The trust management can identify the malicious node by monitoring and evaluating their behavior. However, the trust management is also vulnerable to the attack, and some intelligent behavior can trick the trust management schemes, such as on-off attack and bad-mouthing attack. Therefore, robustness issue is also considered in the trust management scheme. The distributed trust mode with direct trust and indirect trust is used to enhance the robustness in the trust management.The trust management scheme is usually seen as the service for the network routing protocol and algorithm. The trust evaluation in the trust management does not only detect the trust value of the nodes; but it is also one of the metrics in the routing algorithm. By accumulating the trust value in the routing path to evaluate the security of routing path, the secure route can be reasonably established. Therefore, based on distributed trust mode, how to design an efficient trust management scheme is a critical issue in enhancing the performance of secure routing.In this paper, we propose a Trusted Tree-based trust management scheme for routing in wireless sensor networks, which can implement the routing security and improve network performance. The attacks are firstly analyzed. And then the trust computing model and Trusted Tree are established and maintained. Furthermore, our scheme is applied to the QoS based secure routing protocols and algorithms and guides the process of the routing establishment. The major contributions of this paper are threefold which are listed as follows.(i)
Dynamic time window: the fixed size of sliding time window is changed into the dynamic size, so as to detect the malicious nodes with the low proportional bad behavior.
(ii)
Trusted Tree: based on the computed trust value of node, the Trusted Tree is established. The secure key of node is generated. The topology path quality in Trusted Tree is used as the gradient to guide the routing building.
(iii)
Aiding Routing: the QoS based routing protocol using Trusted Tree is implemented. The simulation results show that the QoS based routing protocol with Trust Tree can not only efficiently detect and exclude the malicious nodes, but also significantly enhance the network performance.The remainder of this paper is organized as follows: Section2 discusses the related works. The attacks, computing of trust value, and Trusted Tree are proposed in Section 3. The simulation results are presented in Section 4, and Section 5 concludes the paper.


## 2. Related Work

The trust management can ensure the security of data transmission in wireless sensor networks [15]. The trust management model in secure routing protocol and algorithms can be divided into the two classes: centralized trust model and distributed trust mode [16, 17].


### 2.1. Centralized Trust Model

The trust value of nodes is computed by the particular trusted centre or base station. CENTER [18] is a centralized trust based efficient routing protocol for wireless sensor networks. The base station is used to observe the behavior information from the nodes and deduce the global network view. The nodes’ trust value and the best routes are calculated for excluding the malicious nodes. Improving on the previous CENTER, CENTERA [19] includes an appropriate authentication scheme, and the base station gathers minimal neighbor trust information from the nodes. Although the base station can calculate and evaluate the trust value of the nodes by the global view of the network, the accuracy of trust metrics about the distributed nodes needs to be improved.TCFL [20] uses the nodes’ trust value to select the routing path with highest trust value. The fuzzy logical deduction is used to quantize the uncertain and imprecise data. The proper transmitting path can be established from the source to the destination. However, the high energy is consumed in the TCFL.


### 2.2. Distributed Trust Model

The sensor nodes calculate the trust value by themselves. TQOS [21] obtains the secure routing by combining the trustworthiness of the nodes and the QoS of the link along a route. Based on the trustworthiness-based QoS metrics, the secure routing is discovered and set up. The trust value of nodes is gained by computing the ratio of the number of messages verified and received, but this simple statistics model is vulnerable to attack. ReTrust [22] is an attack-resistant and lightweight trust management approach. The sliding time window is used to calculate the trust value of nodes. ReTrust is a typical instance that uses direct trust and indirect trust. But this fixed size of sliding time window makes it difficult to detect the malicious nodes with low proportional behavior.FTPR [23] proposes a fuzzy-based trust prediction model for routing. Based on the historical behavior and the fluctuations in trust value over a period of time, FTPR operates the trust prediction model to predict the future behavior of the neighbor nodes. However, the wireless link is unstable, and then the link temporary errors can result in the fluctuation of the trust value. For FTPR, it is difficult to discriminate them.PLUS [24] uses the personal reference information and recommendation information to build the reasonable trust relationship among the sensor nodes. The personal reference value is gained based on the ratio of correct packets, and the recommendation value is computed by the neighbor nodes’ trust value. The trust value of suspect node is decided by the integrity check of the packet. Consequently, the suspect node may get unfair penalty and be regarded as the malicious node. In [25], considering the vulnerability of trust establishment to different attacks and the unique features of sensor nodes, a lightweight and robust trust establishment scheme is proposed. The trust value of the nodes is computed based on the rate of misbehavior. Although the frequency of misbehavior is used to check the on-off attack, this method fails to detect the attack with the low percentage of bad behavior.Another interesting distributed trust model is proposed in ATSR [26]. ATSR also implements the trust mode by the direct and indirect trust information and adopts the location-based approach to reduce the routing protocol storage and cost. However, ATSR needs to rely on the location information. GTMS [27] is a group-based trust management scheme for clustered wireless sensor networks. GTMS has three levels: the node level, the cluster head level, and the base station level. Although the timing window mechanism is used to calculate the trust value of the node, GTMS is designed for the clustered network.The cryptography and authentication technology are also used in the centralized and distributed trust model [28, 29]. In centralized trust model, CENTERA uses RC5 and PBC. In distributed trust model, TQOS contains authentication between two nodes.By analyzing the above instances of trust management mode, it is found that the centralized trust mode has high energy consumption and low accuracy. The distributed trust mode is used in the massive routing protocol and much more suitable for wireless sensor networks.


## 2.1. Centralized Trust Model

The trust value of nodes is computed by the particular trusted centre or base station. CENTER [18] is a centralized trust based efficient routing protocol for wireless sensor networks. The base station is used to observe the behavior information from the nodes and deduce the global network view. The nodes’ trust value and the best routes are calculated for excluding the malicious nodes. Improving on the previous CENTER, CENTERA [19] includes an appropriate authentication scheme, and the base station gathers minimal neighbor trust information from the nodes. Although the base station can calculate and evaluate the trust value of the nodes by the global view of the network, the accuracy of trust metrics about the distributed nodes needs to be improved.TCFL [20] uses the nodes’ trust value to select the routing path with highest trust value. The fuzzy logical deduction is used to quantize the uncertain and imprecise data. The proper transmitting path can be established from the source to the destination. However, the high energy is consumed in the TCFL.


## 2.2. Distributed Trust Model

The sensor nodes calculate the trust value by themselves. TQOS [21] obtains the secure routing by combining the trustworthiness of the nodes and the QoS of the link along a route. Based on the trustworthiness-based QoS metrics, the secure routing is discovered and set up. The trust value of nodes is gained by computing the ratio of the number of messages verified and received, but this simple statistics model is vulnerable to attack. ReTrust [22] is an attack-resistant and lightweight trust management approach. The sliding time window is used to calculate the trust value of nodes. ReTrust is a typical instance that uses direct trust and indirect trust. But this fixed size of sliding time window makes it difficult to detect the malicious nodes with low proportional behavior.FTPR [23] proposes a fuzzy-based trust prediction model for routing. Based on the historical behavior and the fluctuations in trust value over a period of time, FTPR operates the trust prediction model to predict the future behavior of the neighbor nodes. However, the wireless link is unstable, and then the link temporary errors can result in the fluctuation of the trust value. For FTPR, it is difficult to discriminate them.PLUS [24] uses the personal reference information and recommendation information to build the reasonable trust relationship among the sensor nodes. The personal reference value is gained based on the ratio of correct packets, and the recommendation value is computed by the neighbor nodes’ trust value. The trust value of suspect node is decided by the integrity check of the packet. Consequently, the suspect node may get unfair penalty and be regarded as the malicious node. In [25], considering the vulnerability of trust establishment to different attacks and the unique features of sensor nodes, a lightweight and robust trust establishment scheme is proposed. The trust value of the nodes is computed based on the rate of misbehavior. Although the frequency of misbehavior is used to check the on-off attack, this method fails to detect the attack with the low percentage of bad behavior.Another interesting distributed trust model is proposed in ATSR [26]. ATSR also implements the trust mode by the direct and indirect trust information and adopts the location-based approach to reduce the routing protocol storage and cost. However, ATSR needs to rely on the location information. GTMS [27] is a group-based trust management scheme for clustered wireless sensor networks. GTMS has three levels: the node level, the cluster head level, and the base station level. Although the timing window mechanism is used to calculate the trust value of the node, GTMS is designed for the clustered network.The cryptography and authentication technology are also used in the centralized and distributed trust model [28, 29]. In centralized trust model, CENTERA uses RC5 and PBC. In distributed trust model, TQOS contains authentication between two nodes.By analyzing the above instances of trust management mode, it is found that the centralized trust mode has high energy consumption and low accuracy. The distributed trust mode is used in the massive routing protocol and much more suitable for wireless sensor networks.


## 3. Trusted Tree-Based Trust Management

In this section, the threats are firstly analyzed, and then the computing method of trust value and Trust Tree are designed. At last, the Trust Tree-based trust management is added into the QoS based routing protocol.


### 3.1. Threats Analysis

Two types of attacks could occur in wireless sensor networks. The first type is the external attack. Wireless sensor networks are generally deployed in the unattended environment. The malicious nodes make it easy to launch the external attacks, such as denial of service (DoS) attack, sniffing attack, and replay attack [30]. DoS attacker can flood the massive hello message or redundant information. The normal and legitimate communication between nodes is disrupted. Although the sniffing attacker has no key materials about communication, it can passively eavesdrop on the transmitted data between legitimate nodes. The replay attacker can simply retransmit the earlier packets to the neighbor nodes, since it can receive the packets by wireless link. These external attacks can be defended by some cryptographic algorithms and authentication mechanisms.However, the cryptography and authentication fail to defend the internal attacks. When the node is compromised to be the malicious node, it is changed to be the internal attacker. The second type is the internal attacks that the compromised nodes launch. These malicious nodes can participate in the routing or collude with other malicious nodes. Wireless sensor networks are more vulnerable to the internal attacks as compared to the external attacks. There are usually some internal attacks including Blackhole, Greyhole, Sinkhole, and Wormhole [31]. The Blackhole attacker drops all the messages when it receives them from the neighborhood nodes. The Greyhole attacker forwards a part of the received message or discards parts of them. The Sinkhole attacker likes the Blackhole attacker, but it deceives the nodes in its near area and disguises itself as the Sink node and then attracts all the data from this area. The two malicious nodes tunnel the messages and replay them from one part of network to another part. This attack is called Wormhole attack. The trust mechanism is a widely used technology in aiding the nodes to deal with the uncertainties and malfunctions of the internal attacker nodes. By observing the behavior of the nodes in the network for a certain period, the normal node calculates the trust value and then justifies if the observed node is trusted.Although the trust based security mechanism can continuously monitor nodes’ behavior to detect the malicious and compromised nodes, the trust mechanism itself is also easy to be attacked. Before the malicious and misbehaved nodes are not detected, they launch some attacks on the trust management system in the network, such as on-off attack and bad-mouthing attack. In the on-off attack, the malicious nodes avoid being found by alternatively good and bad behavior, hoping that they remain in the trusted nodes set. The bad-mouthing attacker forges the recommendation of nodes, in which they frame up the recommendation of normal nodes and boost the trust recommendation of malicious nodes. They impair the trust management system by this kind of different behavior. These malicious nodes trick and attack the trust management system by the intelligent misbehavior. When the proportion of malicious behavior is lower, the detection of malicious nodes is more difficult to achieve. The current trust mechanisms have seldom effective methods to detect the low proportional malicious behavior. In this paper, the dynamic sliding window is used to solve this issue.


### 3.2. Computing of Trust Value

By observing the weight of neighborhood nodes’ misbehavior, the node usually computes their trust value. The sliding time window is used to estimate the trust value of nodes. The time windowW
n contains the n time units, as is shown in Figure 1. The S
k and F
k are the numbers of successful and failed transactions for each observation time unit. After each unit of time, the window slides to the right, recording the new experience and dropping experience recorded earlier.Figure 1
Sliding time window.Based on the observed information in the time window, the direct trust value is estimated. The direct trust value of nodeB for node A is denoted by V
D
T
(
A
,
B
):(1)
V
D
T
A
,
B
=
λ
×
∑
k
=
0
n
-
1
α
k
P
k
A
,
B
∑
k
=
0
n
-
1
α
k
,
P
k
A
,
B
=
S
k
+
1
S
k
+
F
k
+
2
,where P
k is the trust value in each time unit; n is the number of units; λ scales the computed trust value. α
k is the aging factor parameter and is defined as α
k
=
μ
n
-
k, where 0
<
μ
<
1.The direct trust value is computed by the observed number of misbehavior. Since the on-off attacker behaves well and badly alternatively to get the high trust value, calculating the period of misbehavior is adopted to detect the on-off attack. Based on the units in sliding time window, the time interval of good and bad behavior is estimated. When the proportion of misbehavior is higher, the smaller size of sliding time window can detect the misbehavior. However, when the proportion of misbehavior is lower, the size of sliding time window needs to be enlarged to cover the enough observed behavior. The current sliding time window adopts the fixed size that is previously set, before the nodes are deployed. If the fixed size is larger, it is a waste of storage resource. On the other hand, if the fixed size is smaller, it is not effective for detecting the low proportion of misbehavior. Therefore, in this paper, the sliding time window is changed into a kind of dynamic sliding time window. When the trust evaluation value is lower than the trust threshold of behavior, this window unit is considered as an on attacking unit and is temporarily stored in time window by prolonging the size of sliding time window. The fourth on window unit is reserved, as shown in Figure2(a).Figure 2
Size of dynamic time window.
(a)
(b)In sliding time window, nodeA observes the behavior of node B and finds that P
k
(
A
,
B
) is lower than the trust threshold. So node A suspects that node B launches a four-good-one-bad on-off attack. And then node A prolongs the size of sliding time window to 8 as shown in Figure 2(b). The window monitoring value of node B for node A is denoted by V
S
W
(
A
,
B
):(2)
V
S
W
A
,
B
=
∑
U
n
i
t
s
o
n
∑
U
n
i
t
s
o
n
+
∑
U
n
i
t
s
o
f
f
.NodeA normally sets a reasonable and secure value low bang V
T
l
b and high bang V
T
h
b for the dynamic window. If V
S
W is larger than V
T
h
b, the size of sliding window is prolonged to observe more behavior of node in added window units. With the number of good behavior increasing, V
S
W is reduced. When V
S
W is lower than V
T
l
b, the number of window units is gradually decreased to the normal size.Recommendation consistency is used to estimate the recommendation trust. The outlier detection scheme is a tool for detecting recommendation consistency. After receiving the recommendations from the neighboring nodes, nodeA firstly computes the mean M
V
R and then deduces the variance σ
R. The recommendation is good as long as the variance of recommendation is lower than σ
R. Furthermore, the commendation trust value V
R
T is calculated by adopting previous method of computing direct trust. The bad recommendation can be detected and avoided. So the node defends the bad-mouthing attack based on it.The indirect trust is calculated by employing trust chain, on the condition of legitimate recommendation trust. NodeC
i is the neighborhood nodes of node A, and every node C
i has the trust value V
D
T
(
C
i
,
B
) for the observed node B. Indirect trust is computed by the trust propagation. With the recommendation trust from the trusted nodes, one way to calculate the indirect trust of node B for A is(3)
V
I
T
A
,
B
=
∑
i
=
1
m
V
R
T
A
,
C
i
×
V
D
T
A
,
C
i
×
V
D
T
C
i
,
B
m
,where m is the number of good commendations.The trust value of nodeB for node A is obtained according to the direct and indirect trust value:(4)
V
T
A
,
B
=
β
·
V
D
T
A
,
B
+
1
-
β
·
V
I
T
A
,
B
.The computing process of node trust value is detailed as follows.NodeA firstly broadcasts the Trust Computing Request (TCR) message to the neighbor nodes in the communication range. The TCR message contains the following fields: (5)
TCR  identifier
,
s
e
q
A
,
B
,where TCR identifier stands for the TCR message; s
e
q
A is the sequence number of TCR message that node A sends; B is the observed node. Node A sets the timer for the reply of neighbors and then waits for the recommendation messages from them.Upon receiving the TCR message, the neighbor nodeC
i takes V
D
T
(
C
i
,
B
) into the Trust Computing Reply (TRE) message and unicasts TCR message back to node A. The TCR message consists of the following fields: (6)
TRE  identifier
,
s
e
q
A
,
B
,
C
i
,
V
D
T
C
i
,
B
.After nodeA receives the recommendations, it can compute the trust value of nodeB and decide if node B is reserved in its trusted neighbors set.


### 3.3. Model of Trusted Tree

Each node sends or forwards the data to the Sink in wireless sensor networks. The communication link is wireless channel, which is easily influenced by the environment. The quality of wireless link is usually measured by the number of data packets transmitted successfully [32–34]. The wireless link is a bidirection channel with ACK message. By using EWMA method, the nodes set time interval to compute the success probability of packet acceptance in the wireless link. The ETX is used to calculate the link quality. d
f and d
r are, respectively, indicated as the packet reception successful rate of the forward and reverse link. The wireless link quality is denoted by E
T
X
l
i
n
k
=
1
/
(
d
f
×
d
r
). The smaller the ETX is, the better the data reception and link quality are. Suppose the ETX of Sink is 0; the path quality of the other node is equal to the accumulation of single hop link quality. Consider(7)
P
Q
A
=
min
⁡
P
Q
B
+
L
Q
A
,
B
∣
B
∈
N
S
A
,where L
Q
A
,
B stands for the link quality from node A to node B; P
Q
B represents the path quality of node B; the path quality P
Q
A of node A is the minimum value that the function min
⁡
{
∗
} returns; N
S
(
A
) is the neighbor set of node A.According to the accumulation process of path quality, the network topology can form a tree, and the root is Sink, as shown in Figure3. To some extent, the path quality in this tree reflects the distance to the Sink, which is seen as the gradient information for routing.Figure 3
Trusted Tree.


### 3.4. Establishment of Trusted Tree

Since the bilinear pairing technology has been implemented on the sensor node platform, identity-based cryptography is used in wireless sensor networks [35]. The public key is derived based on the public information, such as the ID of node. The steps of key distribution and authentication between nodes are decreased. The complexity of computing and communication load is effectively controlled. In recent years, there have been many solutions put in wireless sensor networks, such as TinyTate [36], TinyPBC [37], and TinyParing [38]. Based on cryptography technology and trust management, Trusted Tree is constructed.


#### 3.4.1. Key Predeployment

The data is forwarded to the Sink in wireless sensor networks. It is assumed that the Sink is secure and trusted, which is equipped with trusted computing module. Therefore, the Sink is trustworthy and unassailable and is seen as the trusted authority. All of the key materials are stored in the Sink. However, the normal nodes are not tamper-resistant and can be compromised easily. The key and data of node can be extracted, because the hardware of node is cost constraint.Before the network nodes are deployed, the initial key and the necessary part of key materials are stored in the normal nodes. The five steps are listed as follows:(i)
Each nodeA has a unique, integer-valued ID, denoted by I
D
A.
(ii)
Choose the hash functionH
:
0,1
∗
→
G
1, mapping arbitrary strings to the elements in G
1, and bilinear pairing e
l
:
G
1
×
G
1
→
G
2, and master secret k
∈
Z
q.
(iii)
Choose the hash functionh
:
0,1
∗
→
0,1
N, mapping arbitrary strings to the fixed length string.
(iv)
Set the path quality of nodeA to the initial value P
Q
i
n
i
t and compute its public key P
K
A
=
H
(
I
D
A
∥
P
Q
i
n
i
t
) and private key T
K
A
=
k
H
(
I
D
A
∥
P
Q
i
n
i
t
).
(v)
Store the relative parameter(
G
1
,
G
2
,
e
l
,
q
,
H
,
h
) and T
K
A in node A.Since the Discrete Logarithm Problem is too difficult to be solved, it is infeasible to deducek from the ID and public key. In other words, although some nodes are captured and compromised, and relative key materials are extracted from them, the adversaries have no way to compute the critical key of other nodes.


#### 3.4.2. Authentication between Neighborhood Nodes

The neighborhood authentication is the foundation of the data transmission between neighborhood nodes. When the legitimate node only forwards/receives data to/from the authenticated nodes, the bogus message is not injected into the network, and the secure data is not swindled by the external attackers. The detailed procedure of neighborhood authentication is the following.Before the node communicates with the neighbor, the nodes should firstly perform the mutual authentication. NodeA broadcasts the neighborhood authentication (NAU) message, which includes message identifier, I
D
A, current path quality C
P
Q
A, and a random nonce R
A. The NAU message comprises the following fields:(8)
NAU  identifier
,
I
D
A
,
C
P
Q
A
,
R
A
,where NAU identifier uniquely identifies the NAU message; I
D
A denotes that this NAU message is from node A; C
P
Q
A is used to negotiate the shared key between the neighborhood nodes; R
A is applied to calculate and compare the message integrity code.NodeB responds to this message, when it is within the transmission range of node A. Node B firstly calculates the shared key N
K
B
,
A based on I
D
A, C
P
Q
A, I
D
B, and C
P
Q
B. And then Node B computes the message integrity code h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
) by using parameters R
A and R
B. Node B responds to node A, after it generates the Neighbor Respond (NRE) message with h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
). The NRE message consists of the following fields:(9)
NRE  identifier
,
I
D
B
,
C
P
Q
B
,
R
B
,
h
N
K
B
,
A
R
A
∥
R
B
∥
1
,where NRE identifier presents the NRE message; the function of I
D
B, C
P
Q
B, and R
B is identical to the homologous fields in NAU message. Based on bilinear pairing formulation, N
K
B
,
A is computed by the private key T
K
B of node B and the public key P
K
A of node A. Although N
K
B
,
A is generated on node B, N
K
B
,
A is equal to N
K
A
,
B that is deduced by node A. The computing process is described as follows:(10)
N
K
B
,
A
=
e
l
T
K
B
,
P
K
A
=
e
l
T
K
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
k
H
I
D
B
∥
C
P
Q
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
k
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
T
K
A
=
e
l
T
K
A
,
H
I
D
B
∥
C
P
Q
B
=
e
l
T
K
A
,
P
K
B
=
N
K
A
,
B
.Based on the bilinearity and symmetry ofe
l, the above equation holds. Therefore, node A uses N
K
A
,
B to compute h
N
K
A
,
B
(
R
A
∥
R
B
∥
1
). If the result is equal to what node B sent, node A considers node B an authentic neighbor. After node A verifies the NRE message, it sends the Neighbor Confirmation (NCO) message to node B. The NCO message contains the following fields:(11)
NCO  identifier
,
h
N
K
A
,
B
R
A
∥
R
B
∥
2
,where NCO identifier denotes the NCO message. h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
) is used to verify node A, due to h
N
K
B
,
A
(
R
A
∥
R
B
∥
2
)
=
h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
).By the three-way handshaking above, nodeA can construct the set of its certificated neighborhood nodes, and the shared keys between them are generated at the same time.


#### 3.4.3. Construction Procedure

The Sink is secure and not compromised in wireless sensor networks; otherwise it is difficult to set up the trust management mechanism and secure protocol. Since the path quality of Sink is 0, each node can find a path to the Sink, by the relaying of other nodes. In the construction procedure, the Sink firstly establishes the one-hop trusted path with the neighboring nodes, and then other nodes are added into the Trusted Tree by the nodes that have joined the Trusted Tree. The detailed procedure of construction is represented as follows.The Sink periodically broadcasts the Trusted Tree (TTR) message, which contains the message identifier, a sequence numberN
S
i
n
k, and the message integrity code which affirms the Sink origin of it. The TTR message comprises the following fields:(12)
TTR  identifier
,
N
S
i
n
k
,
T
K
S
i
n
k
TTM  identifier
∥
N
S
i
n
k
,where TTR identifier stands for the TTR message; N
S
i
n
k is used to differentiate and compare the message; the private key T
K
S
i
n
k of Sink is applied to sign the message. After the nodes receive and verify the TTR message, they rebroadcast the message. By comparing the messages from the neighboring nodes, the receiving node calculates the trust value and then sets up the trust relationship with them. The authenticated result of message is used in computing the node’s trust value.NodeA receives the messages from the certificated neighboring nodes. If the current path quality of neighboring node is not the initial value P
Q
i
n
i
t, the neighboring node has been authenticated with the Sink and has joined the Trusted Tree. Based on (7), node A researches the parent node B from its neighbor nodes set and then invokes the computing process of node trust value in Section 3.2.If the trust value of parent nodeB is larger than the trusted threshold, node A sets up the Joining Tree (JTR) message by using I
D
A, current path quality C
P
Q
A, new calculating path quality N
P
Q
A, V
T
(
A
,
B
), and n
p
·
P
K
A
N
P
Q. n
p is a random number. P
K
A
N
P
Q is the public key that is generated by N
P
Q
A. And node A uses the current private T
K
A to sign it. The JTR message consists of the following fields:(13)
J
T
R
i
d
e
n
t
i
f
i
e
r
,
I
D
A
,
C
P
Q
A
,
N
P
Q
A
,
n
p
·
P
K
A
N
P
Q
,
V
T
A
,
B
,
T
K
A
I
D
A
∥
C
P
Q
A
∥
N
P
Q
A
∥
n
p
·
P
K
A
N
P
Q
,where JTR identifier represents the JTR message.NodeA sends the JTR message to the parent node B. Node A encrypts the JTR message by using the shared key with node B. If node B is not directly communicated with the Sink, it needs to forward JTR message to the relaying node D, and then node D forwards it to the Sink. In the forwarding process, the trust value of relaying nodes is added into the JTR message. Figure 4 shows the JTR message delivering.Figure 4
Message delivering.After the Sink receives the JTR message from nodeA, the Sink stores the path quality of node A and calculates the new private key according to T
K
A
N
P
Q
=
k
H
I
D
A
∥
N
P
Q
A. Then the Sink computes the trust value of topology path in Trusted Tree, which is denoted by V
T
T
(
A
). The Sink packets the encrypted T
K
A
N
P
Q and n
q
·
P
K
S
i
n
k into the Tree Confirmation (TCO) message. n
q is a random number and P
K
S
i
n
k is the public key of Sink. The TCO message contains the following fields:(14)
TCM  identifier
,
P
K
A
T
K
A
N
P
Q
,
n
q
·
P
K
S
i
n
k
,
T
K
S
i
n
k
P
K
A
T
K
A
n
e
w
∥
n
q
·
P
K
S
i
n
k
,where TCO identifier denotes the TCO message; the generated T
K
A
N
P
Q is securely transmitted back to node A by encryption. At last, the Sink signs this message. The Sink calculates the shared key with node A, by using(15)
S
K
S
i
n
k
↔
A
=
e
l
T
K
S
i
n
k
,
n
p
·
P
K
A
N
P
Q
+
n
q
·
P
K
A
N
P
Q
=
e
l
k
·
P
K
S
i
n
k
,
n
p
+
n
q
·
P
K
A
N
P
Q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
.Once nodeA receives the TCO message, it also computes the shared key as follows:(16)
S
K
A
↔
S
i
n
k
=
e
l
T
K
A
N
P
Q
,
n
p
·
P
K
S
i
n
k
+
n
q
·
P
K
S
i
n
k
=
e
l
k
H
I
D
A
∥
N
P
Q
A
,
n
p
+
n
q
P
K
S
i
n
k
=
e
l
P
K
A
N
P
Q
,
P
K
S
i
n
k
k
·
n
p
+
n
q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
=
S
K
S
i
n
k
↔
A
.After the shared key is set up and nodeA has joined the Trusted Tree, node A updates the information with its neighborhood nodes. And the neighbors, which are not added into the Trusted Tree, join the Trusted Tree by node A. In the processing of establishing the Trusted Tree, the Sink stores the secure information of nodes in network.These neighborhood authentication messages and Trusted Tree construction messages can be piggybacked in the routing protocol messages. So the communication overhead is further reduced.


### 3.5. Routing Algorithm

In the design of trust based routing, two aspects need to be considered. The first aspect implies checking the trust value of the nodes and path. Only the nodes and path, whose trust value is larger than the set trusted threshold, are placed into the candidate set of the routing decision. The second aspect tries to include the trust value metric and some kind of routing metric, such as hop counts and QoS parameter. In other words, on the basis of trusted nodes, the secure routing with QoS support is built. The routing decision is based on the combination value of the two metrics.The Trusted Tree-based trust management scheme can be applied in many routing protocols and algorithms. Taking the QoS based routing protocol as example, we add Trusted Tree-based trust management scheme into the TQOS, which implements TQOS using Trusted Tree (TT). Since both the trust and QoS requirement are considered, the cost that combines the trust and QoS requirement is designed as follows:(17)
C
A
P
=
∑
i
,
j
∈
P
α
·
Φ
i
,
j
·
1
-
V
T
i
,
j
,
(18)
Φ
i
,
j
=
β
·
L
Q
i
,
j
·
D
i
,
j
,where α is a coefficient that is used to scale the cost; Φ
(
i
,
j
) is a combined metric that contains the link quality L
Q
i
,
j and delay D
i
,
j over the link from i to j; β is a scaling factor that is used to scale the impact of delay on the total metric. The bigger value of C
A
(
P
) represents the higher cost of path P, which is due to lower path quality, or the less trust value of path, or both. The path that is less trusted and does not meet the QoS requirement cannot be selected. Therefore, the problem of routing decision can be described as researching the minimum cost of path to be selected as follows: (19)
min
⁡
C
A
P
,
P
∈
Ω
A
→
S
i
n
k
,where Ω
A
→
S
i
n
k is the set of routing paths that are from node A to the Sink.In order to implement the minimumC
A
(
P
), each relaying node needs to calculate an increase to the cost function C
A
(
P
) when it and next hop node are selected to join the path P.In the process of secure routing establishment, source nodeA broadcasts the route discovery packet (R
D
P
A) with its secure signature. If node B belongs to the trusted neighbors set of node A, and C
P
Q
B is lower than C
P
Q
A, node B adds its own information into the R
D
P
A and then rebroadcasts it. The smaller C
P
Q
B means node B is nearer to the Sink, because the path quality in Trusted Tree is a kind of gradient information for routing. If C
P
Q
B is higher than C
P
Q
A, the distance or hop number of node B to the Sink can be larger than node A. So node B can not be the next hop of node A and drops R
D
P
A. This process is repeated until it reaches the Sink. At the Sink, it firstly verifies R
D
P
A and then calculates the total cost of the routing path by using (17). After the Sink receives a few routing discovery packets from node A, it makes the routing decision by using (19). The path with the least cost is selected as the optimal path. And then the Sink sends the route reply packet (R
E
P
A) back to node A. After node A receives and verifies R
E
P
A, the secure route between node A and the Sink is established, and node A starts data transmission. The process of route establishment is implemented on the Trusted Tree. The steps are shown in Algorithm 1(a).Algorithm 1:The processing flow of algorithm.
(a) Algorithm for secure route establishment
(1)  Process Initialization;
(2)  Source node broadcasts RDP to its neighborhood nodes;
(3)while (verify(RDP) == TRUE AND Receiving Node ≠ Sink);
(4)if (C
P
Q
R
e
c
e
i
v
i
n
g
N
o
d
e < C
P
Q
S
e
n
d
i
n
g
N
o
d
e);
(5)      Receiving Node adds its own information and rebroadcasts RDP;
(6)else
(7)      Receiving Node drops RDP;
(8)end if
(9)end while
(10) By using (17), the Sink computes the cost for the current route of the RDP;
(11) Store the current RDP and its cost intoΩ
S
o
u
r
c
e
N
o
d
e
→
S
i
n
k;
(12)if  Ω
S
o
u
r
c
e
N
o
d
e
→
S
i
n
k is FULL;
(13)   By using (19), select the one with the least cost;
(14)   Sends the REP back to the Source Node over the selected route;
(15)end if
(16) Source node receives the REP;
(17)if (verify(REP) == TRUE)
(18)   Secure route is established, and start data transmission;
(19)end if
(20) End Process
(b) Algorithm for secure route maintenance
(1)  Process Initialization;
(2)if (The trust value of Monitored Node is lower than the trust threshold)
(3)    Generates the RER, and broadcasts the RER;
(4)if (Monitoring Node == Source Node AND Monitored Node == Next Hop)
(5)      Deletes the route, and invokes Algorithm1(a);
(6)else if (Monitored Node == Next Hop)
(7)      Deletes the route;
(8)end if;
(9)end if;
(10)while (Receiving Node ≠ Source Node)
(11)  if (Sending Node == Next Hop OR Monitored Node == Next Hop)
(12)     Deletes the route;
(13)end if;
(14)   Broadcast the RER;
(15)end while;
(16) Establish the new route by using Algorithm1(a);
(17) End ProcessThe nodes on the Trusted Tree monitor and observe the behavior of neighbor nodes. When the trust value of observed node is lower than the trust threshold, the route error (RER) message is generated to notify other nodes to change the route.For example, nodeE is compromised. When the malicious behavior of node E is detected by node D, it broadcasts R
E
R
D. If node E is next hop of node D, and node D is not the source node of route, it only deletes node E from its routing table and trusted neighbor set. If node D is the source node, it needs to reestablish the route to the Sink by using Algorithm 1(a). When the neighbor node C of node D receives R
E
R
D, and it finds that node E or node D is its next hop, it deletes this next hop from the routing table and broadcasts R
E
R
D. After it reaches the source node, the new route establishment is conducted. Algorithm 1(b) describes this process.


## 3.1. Threats Analysis

Two types of attacks could occur in wireless sensor networks. The first type is the external attack. Wireless sensor networks are generally deployed in the unattended environment. The malicious nodes make it easy to launch the external attacks, such as denial of service (DoS) attack, sniffing attack, and replay attack [30]. DoS attacker can flood the massive hello message or redundant information. The normal and legitimate communication between nodes is disrupted. Although the sniffing attacker has no key materials about communication, it can passively eavesdrop on the transmitted data between legitimate nodes. The replay attacker can simply retransmit the earlier packets to the neighbor nodes, since it can receive the packets by wireless link. These external attacks can be defended by some cryptographic algorithms and authentication mechanisms.However, the cryptography and authentication fail to defend the internal attacks. When the node is compromised to be the malicious node, it is changed to be the internal attacker. The second type is the internal attacks that the compromised nodes launch. These malicious nodes can participate in the routing or collude with other malicious nodes. Wireless sensor networks are more vulnerable to the internal attacks as compared to the external attacks. There are usually some internal attacks including Blackhole, Greyhole, Sinkhole, and Wormhole [31]. The Blackhole attacker drops all the messages when it receives them from the neighborhood nodes. The Greyhole attacker forwards a part of the received message or discards parts of them. The Sinkhole attacker likes the Blackhole attacker, but it deceives the nodes in its near area and disguises itself as the Sink node and then attracts all the data from this area. The two malicious nodes tunnel the messages and replay them from one part of network to another part. This attack is called Wormhole attack. The trust mechanism is a widely used technology in aiding the nodes to deal with the uncertainties and malfunctions of the internal attacker nodes. By observing the behavior of the nodes in the network for a certain period, the normal node calculates the trust value and then justifies if the observed node is trusted.Although the trust based security mechanism can continuously monitor nodes’ behavior to detect the malicious and compromised nodes, the trust mechanism itself is also easy to be attacked. Before the malicious and misbehaved nodes are not detected, they launch some attacks on the trust management system in the network, such as on-off attack and bad-mouthing attack. In the on-off attack, the malicious nodes avoid being found by alternatively good and bad behavior, hoping that they remain in the trusted nodes set. The bad-mouthing attacker forges the recommendation of nodes, in which they frame up the recommendation of normal nodes and boost the trust recommendation of malicious nodes. They impair the trust management system by this kind of different behavior. These malicious nodes trick and attack the trust management system by the intelligent misbehavior. When the proportion of malicious behavior is lower, the detection of malicious nodes is more difficult to achieve. The current trust mechanisms have seldom effective methods to detect the low proportional malicious behavior. In this paper, the dynamic sliding window is used to solve this issue.


## 3.2. Computing of Trust Value

By observing the weight of neighborhood nodes’ misbehavior, the node usually computes their trust value. The sliding time window is used to estimate the trust value of nodes. The time windowW
n contains the n time units, as is shown in Figure 1. The S
k and F
k are the numbers of successful and failed transactions for each observation time unit. After each unit of time, the window slides to the right, recording the new experience and dropping experience recorded earlier.Figure 1
Sliding time window.Based on the observed information in the time window, the direct trust value is estimated. The direct trust value of nodeB for node A is denoted by V
D
T
(
A
,
B
):(1)
V
D
T
A
,
B
=
λ
×
∑
k
=
0
n
-
1
α
k
P
k
A
,
B
∑
k
=
0
n
-
1
α
k
,
P
k
A
,
B
=
S
k
+
1
S
k
+
F
k
+
2
,where P
k is the trust value in each time unit; n is the number of units; λ scales the computed trust value. α
k is the aging factor parameter and is defined as α
k
=
μ
n
-
k, where 0
<
μ
<
1.The direct trust value is computed by the observed number of misbehavior. Since the on-off attacker behaves well and badly alternatively to get the high trust value, calculating the period of misbehavior is adopted to detect the on-off attack. Based on the units in sliding time window, the time interval of good and bad behavior is estimated. When the proportion of misbehavior is higher, the smaller size of sliding time window can detect the misbehavior. However, when the proportion of misbehavior is lower, the size of sliding time window needs to be enlarged to cover the enough observed behavior. The current sliding time window adopts the fixed size that is previously set, before the nodes are deployed. If the fixed size is larger, it is a waste of storage resource. On the other hand, if the fixed size is smaller, it is not effective for detecting the low proportion of misbehavior. Therefore, in this paper, the sliding time window is changed into a kind of dynamic sliding time window. When the trust evaluation value is lower than the trust threshold of behavior, this window unit is considered as an on attacking unit and is temporarily stored in time window by prolonging the size of sliding time window. The fourth on window unit is reserved, as shown in Figure2(a).Figure 2
Size of dynamic time window.
(a)
(b)In sliding time window, nodeA observes the behavior of node B and finds that P
k
(
A
,
B
) is lower than the trust threshold. So node A suspects that node B launches a four-good-one-bad on-off attack. And then node A prolongs the size of sliding time window to 8 as shown in Figure 2(b). The window monitoring value of node B for node A is denoted by V
S
W
(
A
,
B
):(2)
V
S
W
A
,
B
=
∑
U
n
i
t
s
o
n
∑
U
n
i
t
s
o
n
+
∑
U
n
i
t
s
o
f
f
.NodeA normally sets a reasonable and secure value low bang V
T
l
b and high bang V
T
h
b for the dynamic window. If V
S
W is larger than V
T
h
b, the size of sliding window is prolonged to observe more behavior of node in added window units. With the number of good behavior increasing, V
S
W is reduced. When V
S
W is lower than V
T
l
b, the number of window units is gradually decreased to the normal size.Recommendation consistency is used to estimate the recommendation trust. The outlier detection scheme is a tool for detecting recommendation consistency. After receiving the recommendations from the neighboring nodes, nodeA firstly computes the mean M
V
R and then deduces the variance σ
R. The recommendation is good as long as the variance of recommendation is lower than σ
R. Furthermore, the commendation trust value V
R
T is calculated by adopting previous method of computing direct trust. The bad recommendation can be detected and avoided. So the node defends the bad-mouthing attack based on it.The indirect trust is calculated by employing trust chain, on the condition of legitimate recommendation trust. NodeC
i is the neighborhood nodes of node A, and every node C
i has the trust value V
D
T
(
C
i
,
B
) for the observed node B. Indirect trust is computed by the trust propagation. With the recommendation trust from the trusted nodes, one way to calculate the indirect trust of node B for A is(3)
V
I
T
A
,
B
=
∑
i
=
1
m
V
R
T
A
,
C
i
×
V
D
T
A
,
C
i
×
V
D
T
C
i
,
B
m
,where m is the number of good commendations.The trust value of nodeB for node A is obtained according to the direct and indirect trust value:(4)
V
T
A
,
B
=
β
·
V
D
T
A
,
B
+
1
-
β
·
V
I
T
A
,
B
.The computing process of node trust value is detailed as follows.NodeA firstly broadcasts the Trust Computing Request (TCR) message to the neighbor nodes in the communication range. The TCR message contains the following fields: (5)
TCR  identifier
,
s
e
q
A
,
B
,where TCR identifier stands for the TCR message; s
e
q
A is the sequence number of TCR message that node A sends; B is the observed node. Node A sets the timer for the reply of neighbors and then waits for the recommendation messages from them.Upon receiving the TCR message, the neighbor nodeC
i takes V
D
T
(
C
i
,
B
) into the Trust Computing Reply (TRE) message and unicasts TCR message back to node A. The TCR message consists of the following fields: (6)
TRE  identifier
,
s
e
q
A
,
B
,
C
i
,
V
D
T
C
i
,
B
.After nodeA receives the recommendations, it can compute the trust value of nodeB and decide if node B is reserved in its trusted neighbors set.


## 3.3. Model of Trusted Tree

Each node sends or forwards the data to the Sink in wireless sensor networks. The communication link is wireless channel, which is easily influenced by the environment. The quality of wireless link is usually measured by the number of data packets transmitted successfully [32–34]. The wireless link is a bidirection channel with ACK message. By using EWMA method, the nodes set time interval to compute the success probability of packet acceptance in the wireless link. The ETX is used to calculate the link quality. d
f and d
r are, respectively, indicated as the packet reception successful rate of the forward and reverse link. The wireless link quality is denoted by E
T
X
l
i
n
k
=
1
/
(
d
f
×
d
r
). The smaller the ETX is, the better the data reception and link quality are. Suppose the ETX of Sink is 0; the path quality of the other node is equal to the accumulation of single hop link quality. Consider(7)
P
Q
A
=
min
⁡
P
Q
B
+
L
Q
A
,
B
∣
B
∈
N
S
A
,where L
Q
A
,
B stands for the link quality from node A to node B; P
Q
B represents the path quality of node B; the path quality P
Q
A of node A is the minimum value that the function min
⁡
{
∗
} returns; N
S
(
A
) is the neighbor set of node A.According to the accumulation process of path quality, the network topology can form a tree, and the root is Sink, as shown in Figure3. To some extent, the path quality in this tree reflects the distance to the Sink, which is seen as the gradient information for routing.Figure 3
Trusted Tree.


## 3.4. Establishment of Trusted Tree

Since the bilinear pairing technology has been implemented on the sensor node platform, identity-based cryptography is used in wireless sensor networks [35]. The public key is derived based on the public information, such as the ID of node. The steps of key distribution and authentication between nodes are decreased. The complexity of computing and communication load is effectively controlled. In recent years, there have been many solutions put in wireless sensor networks, such as TinyTate [36], TinyPBC [37], and TinyParing [38]. Based on cryptography technology and trust management, Trusted Tree is constructed.


### 3.4.1. Key Predeployment

The data is forwarded to the Sink in wireless sensor networks. It is assumed that the Sink is secure and trusted, which is equipped with trusted computing module. Therefore, the Sink is trustworthy and unassailable and is seen as the trusted authority. All of the key materials are stored in the Sink. However, the normal nodes are not tamper-resistant and can be compromised easily. The key and data of node can be extracted, because the hardware of node is cost constraint.Before the network nodes are deployed, the initial key and the necessary part of key materials are stored in the normal nodes. The five steps are listed as follows:(i)
Each nodeA has a unique, integer-valued ID, denoted by I
D
A.
(ii)
Choose the hash functionH
:
0,1
∗
→
G
1, mapping arbitrary strings to the elements in G
1, and bilinear pairing e
l
:
G
1
×
G
1
→
G
2, and master secret k
∈
Z
q.
(iii)
Choose the hash functionh
:
0,1
∗
→
0,1
N, mapping arbitrary strings to the fixed length string.
(iv)
Set the path quality of nodeA to the initial value P
Q
i
n
i
t and compute its public key P
K
A
=
H
(
I
D
A
∥
P
Q
i
n
i
t
) and private key T
K
A
=
k
H
(
I
D
A
∥
P
Q
i
n
i
t
).
(v)
Store the relative parameter(
G
1
,
G
2
,
e
l
,
q
,
H
,
h
) and T
K
A in node A.Since the Discrete Logarithm Problem is too difficult to be solved, it is infeasible to deducek from the ID and public key. In other words, although some nodes are captured and compromised, and relative key materials are extracted from them, the adversaries have no way to compute the critical key of other nodes.


### 3.4.2. Authentication between Neighborhood Nodes

The neighborhood authentication is the foundation of the data transmission between neighborhood nodes. When the legitimate node only forwards/receives data to/from the authenticated nodes, the bogus message is not injected into the network, and the secure data is not swindled by the external attackers. The detailed procedure of neighborhood authentication is the following.Before the node communicates with the neighbor, the nodes should firstly perform the mutual authentication. NodeA broadcasts the neighborhood authentication (NAU) message, which includes message identifier, I
D
A, current path quality C
P
Q
A, and a random nonce R
A. The NAU message comprises the following fields:(8)
NAU  identifier
,
I
D
A
,
C
P
Q
A
,
R
A
,where NAU identifier uniquely identifies the NAU message; I
D
A denotes that this NAU message is from node A; C
P
Q
A is used to negotiate the shared key between the neighborhood nodes; R
A is applied to calculate and compare the message integrity code.NodeB responds to this message, when it is within the transmission range of node A. Node B firstly calculates the shared key N
K
B
,
A based on I
D
A, C
P
Q
A, I
D
B, and C
P
Q
B. And then Node B computes the message integrity code h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
) by using parameters R
A and R
B. Node B responds to node A, after it generates the Neighbor Respond (NRE) message with h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
). The NRE message consists of the following fields:(9)
NRE  identifier
,
I
D
B
,
C
P
Q
B
,
R
B
,
h
N
K
B
,
A
R
A
∥
R
B
∥
1
,where NRE identifier presents the NRE message; the function of I
D
B, C
P
Q
B, and R
B is identical to the homologous fields in NAU message. Based on bilinear pairing formulation, N
K
B
,
A is computed by the private key T
K
B of node B and the public key P
K
A of node A. Although N
K
B
,
A is generated on node B, N
K
B
,
A is equal to N
K
A
,
B that is deduced by node A. The computing process is described as follows:(10)
N
K
B
,
A
=
e
l
T
K
B
,
P
K
A
=
e
l
T
K
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
k
H
I
D
B
∥
C
P
Q
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
k
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
T
K
A
=
e
l
T
K
A
,
H
I
D
B
∥
C
P
Q
B
=
e
l
T
K
A
,
P
K
B
=
N
K
A
,
B
.Based on the bilinearity and symmetry ofe
l, the above equation holds. Therefore, node A uses N
K
A
,
B to compute h
N
K
A
,
B
(
R
A
∥
R
B
∥
1
). If the result is equal to what node B sent, node A considers node B an authentic neighbor. After node A verifies the NRE message, it sends the Neighbor Confirmation (NCO) message to node B. The NCO message contains the following fields:(11)
NCO  identifier
,
h
N
K
A
,
B
R
A
∥
R
B
∥
2
,where NCO identifier denotes the NCO message. h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
) is used to verify node A, due to h
N
K
B
,
A
(
R
A
∥
R
B
∥
2
)
=
h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
).By the three-way handshaking above, nodeA can construct the set of its certificated neighborhood nodes, and the shared keys between them are generated at the same time.


### 3.4.3. Construction Procedure

The Sink is secure and not compromised in wireless sensor networks; otherwise it is difficult to set up the trust management mechanism and secure protocol. Since the path quality of Sink is 0, each node can find a path to the Sink, by the relaying of other nodes. In the construction procedure, the Sink firstly establishes the one-hop trusted path with the neighboring nodes, and then other nodes are added into the Trusted Tree by the nodes that have joined the Trusted Tree. The detailed procedure of construction is represented as follows.The Sink periodically broadcasts the Trusted Tree (TTR) message, which contains the message identifier, a sequence numberN
S
i
n
k, and the message integrity code which affirms the Sink origin of it. The TTR message comprises the following fields:(12)
TTR  identifier
,
N
S
i
n
k
,
T
K
S
i
n
k
TTM  identifier
∥
N
S
i
n
k
,where TTR identifier stands for the TTR message; N
S
i
n
k is used to differentiate and compare the message; the private key T
K
S
i
n
k of Sink is applied to sign the message. After the nodes receive and verify the TTR message, they rebroadcast the message. By comparing the messages from the neighboring nodes, the receiving node calculates the trust value and then sets up the trust relationship with them. The authenticated result of message is used in computing the node’s trust value.NodeA receives the messages from the certificated neighboring nodes. If the current path quality of neighboring node is not the initial value P
Q
i
n
i
t, the neighboring node has been authenticated with the Sink and has joined the Trusted Tree. Based on (7), node A researches the parent node B from its neighbor nodes set and then invokes the computing process of node trust value in Section 3.2.If the trust value of parent nodeB is larger than the trusted threshold, node A sets up the Joining Tree (JTR) message by using I
D
A, current path quality C
P
Q
A, new calculating path quality N
P
Q
A, V
T
(
A
,
B
), and n
p
·
P
K
A
N
P
Q. n
p is a random number. P
K
A
N
P
Q is the public key that is generated by N
P
Q
A. And node A uses the current private T
K
A to sign it. The JTR message consists of the following fields:(13)
J
T
R
i
d
e
n
t
i
f
i
e
r
,
I
D
A
,
C
P
Q
A
,
N
P
Q
A
,
n
p
·
P
K
A
N
P
Q
,
V
T
A
,
B
,
T
K
A
I
D
A
∥
C
P
Q
A
∥
N
P
Q
A
∥
n
p
·
P
K
A
N
P
Q
,where JTR identifier represents the JTR message.NodeA sends the JTR message to the parent node B. Node A encrypts the JTR message by using the shared key with node B. If node B is not directly communicated with the Sink, it needs to forward JTR message to the relaying node D, and then node D forwards it to the Sink. In the forwarding process, the trust value of relaying nodes is added into the JTR message. Figure 4 shows the JTR message delivering.Figure 4
Message delivering.After the Sink receives the JTR message from nodeA, the Sink stores the path quality of node A and calculates the new private key according to T
K
A
N
P
Q
=
k
H
I
D
A
∥
N
P
Q
A. Then the Sink computes the trust value of topology path in Trusted Tree, which is denoted by V
T
T
(
A
). The Sink packets the encrypted T
K
A
N
P
Q and n
q
·
P
K
S
i
n
k into the Tree Confirmation (TCO) message. n
q is a random number and P
K
S
i
n
k is the public key of Sink. The TCO message contains the following fields:(14)
TCM  identifier
,
P
K
A
T
K
A
N
P
Q
,
n
q
·
P
K
S
i
n
k
,
T
K
S
i
n
k
P
K
A
T
K
A
n
e
w
∥
n
q
·
P
K
S
i
n
k
,where TCO identifier denotes the TCO message; the generated T
K
A
N
P
Q is securely transmitted back to node A by encryption. At last, the Sink signs this message. The Sink calculates the shared key with node A, by using(15)
S
K
S
i
n
k
↔
A
=
e
l
T
K
S
i
n
k
,
n
p
·
P
K
A
N
P
Q
+
n
q
·
P
K
A
N
P
Q
=
e
l
k
·
P
K
S
i
n
k
,
n
p
+
n
q
·
P
K
A
N
P
Q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
.Once nodeA receives the TCO message, it also computes the shared key as follows:(16)
S
K
A
↔
S
i
n
k
=
e
l
T
K
A
N
P
Q
,
n
p
·
P
K
S
i
n
k
+
n
q
·
P
K
S
i
n
k
=
e
l
k
H
I
D
A
∥
N
P
Q
A
,
n
p
+
n
q
P
K
S
i
n
k
=
e
l
P
K
A
N
P
Q
,
P
K
S
i
n
k
k
·
n
p
+
n
q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
=
S
K
S
i
n
k
↔
A
.After the shared key is set up and nodeA has joined the Trusted Tree, node A updates the information with its neighborhood nodes. And the neighbors, which are not added into the Trusted Tree, join the Trusted Tree by node A. In the processing of establishing the Trusted Tree, the Sink stores the secure information of nodes in network.These neighborhood authentication messages and Trusted Tree construction messages can be piggybacked in the routing protocol messages. So the communication overhead is further reduced.


## 3.4.1. Key Predeployment

The data is forwarded to the Sink in wireless sensor networks. It is assumed that the Sink is secure and trusted, which is equipped with trusted computing module. Therefore, the Sink is trustworthy and unassailable and is seen as the trusted authority. All of the key materials are stored in the Sink. However, the normal nodes are not tamper-resistant and can be compromised easily. The key and data of node can be extracted, because the hardware of node is cost constraint.Before the network nodes are deployed, the initial key and the necessary part of key materials are stored in the normal nodes. The five steps are listed as follows:(i)
Each nodeA has a unique, integer-valued ID, denoted by I
D
A.
(ii)
Choose the hash functionH
:
0,1
∗
→
G
1, mapping arbitrary strings to the elements in G
1, and bilinear pairing e
l
:
G
1
×
G
1
→
G
2, and master secret k
∈
Z
q.
(iii)
Choose the hash functionh
:
0,1
∗
→
0,1
N, mapping arbitrary strings to the fixed length string.
(iv)
Set the path quality of nodeA to the initial value P
Q
i
n
i
t and compute its public key P
K
A
=
H
(
I
D
A
∥
P
Q
i
n
i
t
) and private key T
K
A
=
k
H
(
I
D
A
∥
P
Q
i
n
i
t
).
(v)
Store the relative parameter(
G
1
,
G
2
,
e
l
,
q
,
H
,
h
) and T
K
A in node A.Since the Discrete Logarithm Problem is too difficult to be solved, it is infeasible to deducek from the ID and public key. In other words, although some nodes are captured and compromised, and relative key materials are extracted from them, the adversaries have no way to compute the critical key of other nodes.


## 3.4.2. Authentication between Neighborhood Nodes

The neighborhood authentication is the foundation of the data transmission between neighborhood nodes. When the legitimate node only forwards/receives data to/from the authenticated nodes, the bogus message is not injected into the network, and the secure data is not swindled by the external attackers. The detailed procedure of neighborhood authentication is the following.Before the node communicates with the neighbor, the nodes should firstly perform the mutual authentication. NodeA broadcasts the neighborhood authentication (NAU) message, which includes message identifier, I
D
A, current path quality C
P
Q
A, and a random nonce R
A. The NAU message comprises the following fields:(8)
NAU  identifier
,
I
D
A
,
C
P
Q
A
,
R
A
,where NAU identifier uniquely identifies the NAU message; I
D
A denotes that this NAU message is from node A; C
P
Q
A is used to negotiate the shared key between the neighborhood nodes; R
A is applied to calculate and compare the message integrity code.NodeB responds to this message, when it is within the transmission range of node A. Node B firstly calculates the shared key N
K
B
,
A based on I
D
A, C
P
Q
A, I
D
B, and C
P
Q
B. And then Node B computes the message integrity code h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
) by using parameters R
A and R
B. Node B responds to node A, after it generates the Neighbor Respond (NRE) message with h
N
K
B
,
A
(
R
A
∥
R
B
∥
1
). The NRE message consists of the following fields:(9)
NRE  identifier
,
I
D
B
,
C
P
Q
B
,
R
B
,
h
N
K
B
,
A
R
A
∥
R
B
∥
1
,where NRE identifier presents the NRE message; the function of I
D
B, C
P
Q
B, and R
B is identical to the homologous fields in NAU message. Based on bilinear pairing formulation, N
K
B
,
A is computed by the private key T
K
B of node B and the public key P
K
A of node A. Although N
K
B
,
A is generated on node B, N
K
B
,
A is equal to N
K
A
,
B that is deduced by node A. The computing process is described as follows:(10)
N
K
B
,
A
=
e
l
T
K
B
,
P
K
A
=
e
l
T
K
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
k
H
I
D
B
∥
C
P
Q
B
,
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
k
H
I
D
A
∥
C
P
Q
A
=
e
l
H
I
D
B
∥
C
P
Q
B
,
T
K
A
=
e
l
T
K
A
,
H
I
D
B
∥
C
P
Q
B
=
e
l
T
K
A
,
P
K
B
=
N
K
A
,
B
.Based on the bilinearity and symmetry ofe
l, the above equation holds. Therefore, node A uses N
K
A
,
B to compute h
N
K
A
,
B
(
R
A
∥
R
B
∥
1
). If the result is equal to what node B sent, node A considers node B an authentic neighbor. After node A verifies the NRE message, it sends the Neighbor Confirmation (NCO) message to node B. The NCO message contains the following fields:(11)
NCO  identifier
,
h
N
K
A
,
B
R
A
∥
R
B
∥
2
,where NCO identifier denotes the NCO message. h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
) is used to verify node A, due to h
N
K
B
,
A
(
R
A
∥
R
B
∥
2
)
=
h
N
K
A
,
B
(
R
A
∥
R
B
∥
2
).By the three-way handshaking above, nodeA can construct the set of its certificated neighborhood nodes, and the shared keys between them are generated at the same time.


## 3.4.3. Construction Procedure

The Sink is secure and not compromised in wireless sensor networks; otherwise it is difficult to set up the trust management mechanism and secure protocol. Since the path quality of Sink is 0, each node can find a path to the Sink, by the relaying of other nodes. In the construction procedure, the Sink firstly establishes the one-hop trusted path with the neighboring nodes, and then other nodes are added into the Trusted Tree by the nodes that have joined the Trusted Tree. The detailed procedure of construction is represented as follows.The Sink periodically broadcasts the Trusted Tree (TTR) message, which contains the message identifier, a sequence numberN
S
i
n
k, and the message integrity code which affirms the Sink origin of it. The TTR message comprises the following fields:(12)
TTR  identifier
,
N
S
i
n
k
,
T
K
S
i
n
k
TTM  identifier
∥
N
S
i
n
k
,where TTR identifier stands for the TTR message; N
S
i
n
k is used to differentiate and compare the message; the private key T
K
S
i
n
k of Sink is applied to sign the message. After the nodes receive and verify the TTR message, they rebroadcast the message. By comparing the messages from the neighboring nodes, the receiving node calculates the trust value and then sets up the trust relationship with them. The authenticated result of message is used in computing the node’s trust value.NodeA receives the messages from the certificated neighboring nodes. If the current path quality of neighboring node is not the initial value P
Q
i
n
i
t, the neighboring node has been authenticated with the Sink and has joined the Trusted Tree. Based on (7), node A researches the parent node B from its neighbor nodes set and then invokes the computing process of node trust value in Section 3.2.If the trust value of parent nodeB is larger than the trusted threshold, node A sets up the Joining Tree (JTR) message by using I
D
A, current path quality C
P
Q
A, new calculating path quality N
P
Q
A, V
T
(
A
,
B
), and n
p
·
P
K
A
N
P
Q. n
p is a random number. P
K
A
N
P
Q is the public key that is generated by N
P
Q
A. And node A uses the current private T
K
A to sign it. The JTR message consists of the following fields:(13)
J
T
R
i
d
e
n
t
i
f
i
e
r
,
I
D
A
,
C
P
Q
A
,
N
P
Q
A
,
n
p
·
P
K
A
N
P
Q
,
V
T
A
,
B
,
T
K
A
I
D
A
∥
C
P
Q
A
∥
N
P
Q
A
∥
n
p
·
P
K
A
N
P
Q
,where JTR identifier represents the JTR message.NodeA sends the JTR message to the parent node B. Node A encrypts the JTR message by using the shared key with node B. If node B is not directly communicated with the Sink, it needs to forward JTR message to the relaying node D, and then node D forwards it to the Sink. In the forwarding process, the trust value of relaying nodes is added into the JTR message. Figure 4 shows the JTR message delivering.Figure 4
Message delivering.After the Sink receives the JTR message from nodeA, the Sink stores the path quality of node A and calculates the new private key according to T
K
A
N
P
Q
=
k
H
I
D
A
∥
N
P
Q
A. Then the Sink computes the trust value of topology path in Trusted Tree, which is denoted by V
T
T
(
A
). The Sink packets the encrypted T
K
A
N
P
Q and n
q
·
P
K
S
i
n
k into the Tree Confirmation (TCO) message. n
q is a random number and P
K
S
i
n
k is the public key of Sink. The TCO message contains the following fields:(14)
TCM  identifier
,
P
K
A
T
K
A
N
P
Q
,
n
q
·
P
K
S
i
n
k
,
T
K
S
i
n
k
P
K
A
T
K
A
n
e
w
∥
n
q
·
P
K
S
i
n
k
,where TCO identifier denotes the TCO message; the generated T
K
A
N
P
Q is securely transmitted back to node A by encryption. At last, the Sink signs this message. The Sink calculates the shared key with node A, by using(15)
S
K
S
i
n
k
↔
A
=
e
l
T
K
S
i
n
k
,
n
p
·
P
K
A
N
P
Q
+
n
q
·
P
K
A
N
P
Q
=
e
l
k
·
P
K
S
i
n
k
,
n
p
+
n
q
·
P
K
A
N
P
Q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
.Once nodeA receives the TCO message, it also computes the shared key as follows:(16)
S
K
A
↔
S
i
n
k
=
e
l
T
K
A
N
P
Q
,
n
p
·
P
K
S
i
n
k
+
n
q
·
P
K
S
i
n
k
=
e
l
k
H
I
D
A
∥
N
P
Q
A
,
n
p
+
n
q
P
K
S
i
n
k
=
e
l
P
K
A
N
P
Q
,
P
K
S
i
n
k
k
·
n
p
+
n
q
=
e
l
P
K
S
i
n
k
,
P
K
A
N
P
Q
k
·
n
p
+
n
q
=
S
K
S
i
n
k
↔
A
.After the shared key is set up and nodeA has joined the Trusted Tree, node A updates the information with its neighborhood nodes. And the neighbors, which are not added into the Trusted Tree, join the Trusted Tree by node A. In the processing of establishing the Trusted Tree, the Sink stores the secure information of nodes in network.These neighborhood authentication messages and Trusted Tree construction messages can be piggybacked in the routing protocol messages. So the communication overhead is further reduced.


## 3.5. Routing Algorithm

In the design of trust based routing, two aspects need to be considered. The first aspect implies checking the trust value of the nodes and path. Only the nodes and path, whose trust value is larger than the set trusted threshold, are placed into the candidate set of the routing decision. The second aspect tries to include the trust value metric and some kind of routing metric, such as hop counts and QoS parameter. In other words, on the basis of trusted nodes, the secure routing with QoS support is built. The routing decision is based on the combination value of the two metrics.The Trusted Tree-based trust management scheme can be applied in many routing protocols and algorithms. Taking the QoS based routing protocol as example, we add Trusted Tree-based trust management scheme into the TQOS, which implements TQOS using Trusted Tree (TT). Since both the trust and QoS requirement are considered, the cost that combines the trust and QoS requirement is designed as follows:(17)
C
A
P
=
∑
i
,
j
∈
P
α
·
Φ
i
,
j
·
1
-
V
T
i
,
j
,
(18)
Φ
i
,
j
=
β
·
L
Q
i
,
j
·
D
i
,
j
,where α is a coefficient that is used to scale the cost; Φ
(
i
,
j
) is a combined metric that contains the link quality L
Q
i
,
j and delay D
i
,
j over the link from i to j; β is a scaling factor that is used to scale the impact of delay on the total metric. The bigger value of C
A
(
P
) represents the higher cost of path P, which is due to lower path quality, or the less trust value of path, or both. The path that is less trusted and does not meet the QoS requirement cannot be selected. Therefore, the problem of routing decision can be described as researching the minimum cost of path to be selected as follows: (19)
min
⁡
C
A
P
,
P
∈
Ω
A
→
S
i
n
k
,where Ω
A
→
S
i
n
k is the set of routing paths that are from node A to the Sink.In order to implement the minimumC
A
(
P
), each relaying node needs to calculate an increase to the cost function C
A
(
P
) when it and next hop node are selected to join the path P.In the process of secure routing establishment, source nodeA broadcasts the route discovery packet (R
D
P
A) with its secure signature. If node B belongs to the trusted neighbors set of node A, and C
P
Q
B is lower than C
P
Q
A, node B adds its own information into the R
D
P
A and then rebroadcasts it. The smaller C
P
Q
B means node B is nearer to the Sink, because the path quality in Trusted Tree is a kind of gradient information for routing. If C
P
Q
B is higher than C
P
Q
A, the distance or hop number of node B to the Sink can be larger than node A. So node B can not be the next hop of node A and drops R
D
P
A. This process is repeated until it reaches the Sink. At the Sink, it firstly verifies R
D
P
A and then calculates the total cost of the routing path by using (17). After the Sink receives a few routing discovery packets from node A, it makes the routing decision by using (19). The path with the least cost is selected as the optimal path. And then the Sink sends the route reply packet (R
E
P
A) back to node A. After node A receives and verifies R
E
P
A, the secure route between node A and the Sink is established, and node A starts data transmission. The process of route establishment is implemented on the Trusted Tree. The steps are shown in Algorithm 1(a).Algorithm 1:The processing flow of algorithm.
(a) Algorithm for secure route establishment
(1)  Process Initialization;
(2)  Source node broadcasts RDP to its neighborhood nodes;
(3)while (verify(RDP) == TRUE AND Receiving Node ≠ Sink);
(4)if (C
P
Q
R
e
c
e
i
v
i
n
g
N
o
d
e < C
P
Q
S
e
n
d
i
n
g
N
o
d
e);
(5)      Receiving Node adds its own information and rebroadcasts RDP;
(6)else
(7)      Receiving Node drops RDP;
(8)end if
(9)end while
(10) By using (17), the Sink computes the cost for the current route of the RDP;
(11) Store the current RDP and its cost intoΩ
S
o
u
r
c
e
N
o
d
e
→
S
i
n
k;
(12)if  Ω
S
o
u
r
c
e
N
o
d
e
→
S
i
n
k is FULL;
(13)   By using (19), select the one with the least cost;
(14)   Sends the REP back to the Source Node over the selected route;
(15)end if
(16) Source node receives the REP;
(17)if (verify(REP) == TRUE)
(18)   Secure route is established, and start data transmission;
(19)end if
(20) End Process
(b) Algorithm for secure route maintenance
(1)  Process Initialization;
(2)if (The trust value of Monitored Node is lower than the trust threshold)
(3)    Generates the RER, and broadcasts the RER;
(4)if (Monitoring Node == Source Node AND Monitored Node == Next Hop)
(5)      Deletes the route, and invokes Algorithm1(a);
(6)else if (Monitored Node == Next Hop)
(7)      Deletes the route;
(8)end if;
(9)end if;
(10)while (Receiving Node ≠ Source Node)
(11)  if (Sending Node == Next Hop OR Monitored Node == Next Hop)
(12)     Deletes the route;
(13)end if;
(14)   Broadcast the RER;
(15)end while;
(16) Establish the new route by using Algorithm1(a);
(17) End ProcessThe nodes on the Trusted Tree monitor and observe the behavior of neighbor nodes. When the trust value of observed node is lower than the trust threshold, the route error (RER) message is generated to notify other nodes to change the route.For example, nodeE is compromised. When the malicious behavior of node E is detected by node D, it broadcasts R
E
R
D. If node E is next hop of node D, and node D is not the source node of route, it only deletes node E from its routing table and trusted neighbor set. If node D is the source node, it needs to reestablish the route to the Sink by using Algorithm 1(a). When the neighbor node C of node D receives R
E
R
D, and it finds that node E or node D is its next hop, it deletes this next hop from the routing table and broadcasts R
E
R
D. After it reaches the source node, the new route establishment is conducted. Algorithm 1(b) describes this process.


## 4. Performance Evaluation

All of the simulation experiments are run in the TOSSIM simulator [39]. TOSSIM inherits the implementation and design of TinyOS, which provides the tool to generate network topology and uses CPM algorithm to simulate noise. The scenario that is used in our experiments consists of a 100 m × 100 m square area. The Sink is placed at the edge of the experiment area. The nodes are uniformly randomly distributed, where the average node density is about 2 to 6 nodes in each 20 m × 20 m square subarea. And the distance between any two nodes is more than 7 meters. The ID of node is orderly numbered by their distance to the Sink from near to far. Among the total number of the nodes in the experiment, 10 percent nodes are selected as the malicious nodes. Other normal nodes generate the sensed data packets by the period of random time interval. Each node can have the difference task for monitoring the environment. The period of sensing data or event driven time is also different. The nodes send a packet at the random time interval, which is randomly set from 5 to 15 seconds. The simulation experiments are run for 6000 seconds. The main experimental parameters are listed in Table 1.Table 1
Simulation settings.
Parameter
Value
Terrain (m2)
100 × 100
Node number
100
Packet length (Byte)
110
MAC protocol
IEEE802.15.4 CSMA
Radio range (m)
40
Trust threshold
0.4We implement and compare TQOS, TQOS using ReTrust, and TQOS using TT (Trusted Tree). After the malicious and normal nodes are selected, each test is executed about 5 times, and then their average value is calculated.


### 4.1. The Security and Performance of Trusted Routing

The trust management scheme is the effective method to defend the attacks in the network routing. In the tampering attack, the malicious node forwards the messages in the routing path, after receiving and tampering the messages. So the trust management scheme needs to cooperate with the cryptographic technique to detect the malicious nodes. And then the trust management scheme recalculates the trust value of the nodes and path for the routing algorithm.As shown in Figure5, the average delivery ratio of the packet decreases significantly when the malicious nodes launch the attack, while the average delivery ratio increases after the malicious nodes are detected out. At the initial stage of network running, the average delivery ratio is close to 1. Since the tampered messages are dropped, the packet loss ratio increases and the average delivery ration suffers the degradation. Compared with TQOS, the TQOS using ReTrust and TQOS using TT can earlier detect the malicious nodes, because the direct trust and indirect trust are used in them. TQOS has only direct trust by observing the neighbor nodes, so the detection efficiency of TQOS is lower than them. However, the trust value node and path are computed in dynamic time window of TQOS using TT, and the path quality gradient of Trusted Tree can speed up the building process of secure routing path. Therefore, the average delivery ratio in the new path of TQOS using TT increases more than the TQOS using ReTrust.Figure 5
Average delivery ratio under tampering attack.Figure6 represents the average transmission latency of the 30 normal nodes, which are randomly selected among the source nodes. The transmission time of packet is the base for the data transmission. The statistics of latency is based on the transmission time of packet. According to the transmission time of each packet from the source node to the destination node, the latency is counted and calculated on the Sink. Based on the link quality of Trusted Tree and the routing discovery, the TQOS using TT can get higher performance and has the lower transmission delay. TQOS using ReTrust has more stable routing path than the TQOS. Since the direct trust and indirect trust are used, the trust value of path is faster calculated for the routing. So the performance is enhanced.Figure 6
End-to-end delay under tampering attack.In the TQOS using TT, the routing path is built on the Trusted Tree. The next hop node is the trusted neighbor node, which is from the authenticated neighbor nodes set. And the neighbor nodes, which take lower path quality as routing gradient, forward the routing discovery packet for route establishment. The massive flooding of routing message is avoided. So TQOS using TT has the lower route load as shown in Figure7. Due to the large number of broadcast and rebroadcast packets sent and forwarded, TQOS has much higher cost. Based on the scheme of TQOS, the direct trust and indirect trust communication of TQOS using ReTrust result in more load.Figure 7
Route load.


### 4.2. Detecting Malicious Behavior

The malicious node can continue to change between the good and bad behavior, so as to achieve the purpose of damaging the network and avoid being detected. Firstly, we execute the simulation, in which the malicious nodes launch the on-off attack with dropping 50% of packets. The attack effect is shown in Figure8. Compared with the tampering attack, the average delivery ratio decreases gently in the presence of the on-off attacking, but many packets are dropped. This is because the malicious nodes are difficult to be detected. The message authentication mechanism in TQOS is modified and replaced by the direct trust computing. The average delivery ratio is lower when only direct trust is used. But the malicious nodes are earlier detected out in the TQOS using ReTrust and TQOS using TT. And TQOS using TT has higher delivery ratio than TQOS using ReTrust, because of the dynamic time window and Trusted Tree.Figure 8
Average delivery ratio under on-off attack.In the presence of on-off attack, the average transmission latency of the 30 normal nodes is shown in Figure9. The transmission latency of data packet is computed. In TQOS, the instability of the trust value results in the fluctuation of the delay. TQOS using ReTrust can alleviate the instability of the trust value. By the dynamic time window and Trusted Tree, TQOS using TT can quicker find out the malicious node and enhance performance on the latency.Figure 9
End-to-end delay under on-off attack.When the malicious nodes launch the on-off attack with dropping 10% of packets, the attack effect is shown in Figure10. TQOS and TQOS using ReTrust are difficult to detect out the attack. However, TQOS using TT can prolong the size of dynamic sliding window to find out the malicious nodes and raise the average delivery ratio.Figure 10
The effect of lower probability on-off attack.When the bad-mouthing attack is launched, the malicious nodes detection performance is shown in Figure11. Let D denote the set of malicious nodes that are detected out. M represents the set of malicious nodes. The malicious nodes detection performance is defined as D
/
M, which is a real number in [
0,1
]. In order to avoid being detected, the malicious nodes do not launch bad-mouthing attack constantly. When the proportion of bad-mouthing behavior is 50% and 20%, the TQOS using ReTrust and TQOS using TT can find out the malicious nodes. But the TQOS using TT has the higher performance. While the proportion of bad-mouthing behavior drops down to 10%, the TQOS using TT can still detect the malicious node since the dynamic time window is introduced.Figure 11
Malicious node detection performance.


### 4.3. Residual Energy

After the simulation is completed, the residual energy of normal nodes is shown in Figure12. For TQOS using TT, the average value of residual energy is 0.679, and TQOS and TQOS using ReTrust are, respectively, 0.589 and 0.561. TQOS using TT does not use the message redundancy and route redundancy to build secure routing. So the number of messages is decreased. TQOS using TT has the higher residual energy. The building process of routing path is shortened by introducing Trusted Tree. The network lifetime is longer in TQOS using TT.Figure 12
Residual energy.


## 4.1. The Security and Performance of Trusted Routing

The trust management scheme is the effective method to defend the attacks in the network routing. In the tampering attack, the malicious node forwards the messages in the routing path, after receiving and tampering the messages. So the trust management scheme needs to cooperate with the cryptographic technique to detect the malicious nodes. And then the trust management scheme recalculates the trust value of the nodes and path for the routing algorithm.As shown in Figure5, the average delivery ratio of the packet decreases significantly when the malicious nodes launch the attack, while the average delivery ratio increases after the malicious nodes are detected out. At the initial stage of network running, the average delivery ratio is close to 1. Since the tampered messages are dropped, the packet loss ratio increases and the average delivery ration suffers the degradation. Compared with TQOS, the TQOS using ReTrust and TQOS using TT can earlier detect the malicious nodes, because the direct trust and indirect trust are used in them. TQOS has only direct trust by observing the neighbor nodes, so the detection efficiency of TQOS is lower than them. However, the trust value node and path are computed in dynamic time window of TQOS using TT, and the path quality gradient of Trusted Tree can speed up the building process of secure routing path. Therefore, the average delivery ratio in the new path of TQOS using TT increases more than the TQOS using ReTrust.Figure 5
Average delivery ratio under tampering attack.Figure6 represents the average transmission latency of the 30 normal nodes, which are randomly selected among the source nodes. The transmission time of packet is the base for the data transmission. The statistics of latency is based on the transmission time of packet. According to the transmission time of each packet from the source node to the destination node, the latency is counted and calculated on the Sink. Based on the link quality of Trusted Tree and the routing discovery, the TQOS using TT can get higher performance and has the lower transmission delay. TQOS using ReTrust has more stable routing path than the TQOS. Since the direct trust and indirect trust are used, the trust value of path is faster calculated for the routing. So the performance is enhanced.Figure 6
End-to-end delay under tampering attack.In the TQOS using TT, the routing path is built on the Trusted Tree. The next hop node is the trusted neighbor node, which is from the authenticated neighbor nodes set. And the neighbor nodes, which take lower path quality as routing gradient, forward the routing discovery packet for route establishment. The massive flooding of routing message is avoided. So TQOS using TT has the lower route load as shown in Figure7. Due to the large number of broadcast and rebroadcast packets sent and forwarded, TQOS has much higher cost. Based on the scheme of TQOS, the direct trust and indirect trust communication of TQOS using ReTrust result in more load.Figure 7
Route load.


## 4.2. Detecting Malicious Behavior

The malicious node can continue to change between the good and bad behavior, so as to achieve the purpose of damaging the network and avoid being detected. Firstly, we execute the simulation, in which the malicious nodes launch the on-off attack with dropping 50% of packets. The attack effect is shown in Figure8. Compared with the tampering attack, the average delivery ratio decreases gently in the presence of the on-off attacking, but many packets are dropped. This is because the malicious nodes are difficult to be detected. The message authentication mechanism in TQOS is modified and replaced by the direct trust computing. The average delivery ratio is lower when only direct trust is used. But the malicious nodes are earlier detected out in the TQOS using ReTrust and TQOS using TT. And TQOS using TT has higher delivery ratio than TQOS using ReTrust, because of the dynamic time window and Trusted Tree.Figure 8
Average delivery ratio under on-off attack.In the presence of on-off attack, the average transmission latency of the 30 normal nodes is shown in Figure9. The transmission latency of data packet is computed. In TQOS, the instability of the trust value results in the fluctuation of the delay. TQOS using ReTrust can alleviate the instability of the trust value. By the dynamic time window and Trusted Tree, TQOS using TT can quicker find out the malicious node and enhance performance on the latency.Figure 9
End-to-end delay under on-off attack.When the malicious nodes launch the on-off attack with dropping 10% of packets, the attack effect is shown in Figure10. TQOS and TQOS using ReTrust are difficult to detect out the attack. However, TQOS using TT can prolong the size of dynamic sliding window to find out the malicious nodes and raise the average delivery ratio.Figure 10
The effect of lower probability on-off attack.When the bad-mouthing attack is launched, the malicious nodes detection performance is shown in Figure11. Let D denote the set of malicious nodes that are detected out. M represents the set of malicious nodes. The malicious nodes detection performance is defined as D
/
M, which is a real number in [
0,1
]. In order to avoid being detected, the malicious nodes do not launch bad-mouthing attack constantly. When the proportion of bad-mouthing behavior is 50% and 20%, the TQOS using ReTrust and TQOS using TT can find out the malicious nodes. But the TQOS using TT has the higher performance. While the proportion of bad-mouthing behavior drops down to 10%, the TQOS using TT can still detect the malicious node since the dynamic time window is introduced.Figure 11
Malicious node detection performance.


## 4.3. Residual Energy

After the simulation is completed, the residual energy of normal nodes is shown in Figure12. For TQOS using TT, the average value of residual energy is 0.679, and TQOS and TQOS using ReTrust are, respectively, 0.589 and 0.561. TQOS using TT does not use the message redundancy and route redundancy to build secure routing. So the number of messages is decreased. TQOS using TT has the higher residual energy. The building process of routing path is shortened by introducing Trusted Tree. The network lifetime is longer in TQOS using TT.Figure 12
Residual energy.


## 5. Conclusions

In this paper, we proposed Trusted Tree-based trust management scheme for secure routing. The attacks in wireless sensor networks are firstly analyzed. Based on the distributed trust model with the detection of direct trust and indirect trust, the dynamic time window is used to compute the trust value of nodes. Then Trusted Tree is established on the trusted nodes. The node’s path quality in Trusted Tree can aid the routing discovery process to set up the routing path. Trusted Tree-based trust management scheme can be added to the many secure routing algorithms, such as the QoS based secure routing algorithm. Compared with some current algorithms with the trust management scheme, the routing algorithm with Trusted Tree shows better performance and security, according to results of the simulation experiments.In the future, we plan to use message type weight to develop the distributed trust mode, which can both improve the detection efficiency and enhance the network performance. We will add our proposed trust management into some actual network protocol, such as IETF RPL protocol.



---

*Source: 385849-2015-12-10.xml*