A Credible Routing Based on a Novel Trust Mechanism in Ad Hoc Networks

Abstract

Many existing routing protocols in Mobile Ad hoc Networks (MANETs) focus on finding paths in dynamic networks without considering security. In this paper, we propose a trust model which evaluates neighbours' direct trust by factors of encounter time, mobility, and successful cooperation frequency. The revised D-S evidence theory is used to combine multiple recommended pieces of evidence and obtain the recommended trust value. Then based on the novel trust mechanism, we propose a trusted routing protocol named TDS-AODV protocol by extending the AODV protocol. In this protocol, a node makes a routing decision according to the trust values of its neighbour nodes. Finally, two routes are built: the main route with highest route trust value in the candidate routes and a backup route. Simulation results reveal that TDS-AODV can eliminate malicious nodes effectively when building the route; furthermore, it also achieves better performance than TAODV and AODV in terms of throughput, packet delivery ratio, and average end to end delay.

1. Introduction

The past decade has witnessed tremendous research efforts devoted to Mobile Ad hoc Networks (MANETs). MANETs are temporary autonomous systems with the special characteristics of dynamic network topology, limited computational abilities, and continuously changing scale. Due to its flexibility, a MANET is attractive for applications, such as disaster relief, military service, and robot networks [1]. However, this flexibility also causes security problems. Routing security is one of the challenging issues in current research.

Traditional MANET routing protocols, such as destination-sequenced distance vector routing (DSDV) [2], dynamic source routing (DSR) [3], and ad hoc on-demand distance vector routing (AODV) [4], assume that all nodes in the network work in a benevolent manner and no predefined trust exists between communication partners. However, the fact is that malicious behavior among nodes exists; for example, selfish nodes deny relaying the packets of other nodes, and malicious nodes perform impersonation, fabrication, or modification attacks against the network traffic [5]. Hence, it is necessary to incorporate security mechanisms into MANET routing protocols to mitigate the impairment from malicious nodes. However, the security mechanism basing on the traditional cryptosystem is used to resist external attacks, but it cannot effectively solve the internal attacks by malicious nodes [6]. Therefore, the trust mechanism which is considered to be an effective measure to solve those questions has recently been studied.

In our trust mechanism, the successful cooperation frequency factor is considered in direct trust evaluation to guarantee the security of network. It is calculated according to its accumulated observations using the Bayesian inference which adopts Beta distribution. Unlike most trust mechanisms [7–12] that focus on trust evaluation without considering performance of the network, we take other two factors (factors of encounter time and mobility) into account. A good network performance can help save nodes' limited resources and prolong the network lifetime, which is very important in MANET. The network topology in MANET is dynamic; hence, the next hop of a node may not be its next hop the next moment. To create a relatively stable network topology as much as possible, we propose two factors, nodes' average encounter time and mobility, when calculating nodes' direct trust value. The two factors make the trust mechanism more suitable for resource-restricted MANET. D-S evidence theory, which was first introduced by statistician of Dempster [13] and extended by Shafer [14], is used to calculate direct trust value, integrate indirect evidence, and obtain the overall trust value. We choose D-S evidence here because it does well in dealing with the uncertainty of trust value.

Based on the novel trust mechanism, we put forward a trusted routing protocol, by extending the AODV protocol in MANETs, TDS-AODV for short. In this protocol, a node evaluates its neighbours' trust value according to the trust model and selects reliable nodes as its next-hop nodes. A source can establish multiple reliable paths to a destination in one route discovery process. We consider the number of hops as well as the trust value of paths to the destination. A destination will respond with three shortest paths as candidates and the path trust will be calculated during the process of Route Reply ( $R R E P$ ) Message delivery. The one with maximum path trust will be selected as the forwarding route and the second reliable one will be regarded as the backup route. We perform some simulations to compare the performance of TAODV, AODV, and TDS-AODV on Matlab platform. Simulation results show that our method is practical to detect malicious nodes and outperform TAODV and AODV in throughput, packet delivery ratio, and average end to end delay.

The rest of this paper is organized as follows. Section 2 summarizes the related work on trust evaluation and trust-based routing protocols. Section 3 presents the novel trust evaluation mechanism. Section 4 describes TDS-AODV in detail. Section 5 provides the simulation studies. Finally, we conclude this paper in Section 6.

2. Related Works

Researchers are becoming more and more interested in integrating trust into a MANET and have proposed numerous works. In this section, we first focus our attention on trust evaluation models in MANETs and then discuss the trust based routing protocols in MANETs.

2.1. Trust Evaluation

Peng et al. [7] assessed the subjective trust of nodes through the Bayesian method, but they were not able to detect dishonest recommendations. Zouridaki et al. [8] chose to determine the node trustworthiness with respect to reliable packet forwarding by combining first-hand trust and second-hand trust information. However, the trust calculation in unsupervised ad hoc environment involved complex aspects such as availability and mobility. besides packet forwarding. Omar et al. [9] sought to establish a fully distributed trust model based on trust graphs and threshold cryptography.

At present, most of the trust evaluation literatures ignore the uncertainty of trust value. To deal with this problem, some researchers [10–12] resort to D-S evidence theory. D-S evidence theory has the capacity of expressing directly for “uncertain,” which makes it suitable to calculate the trust value in MANETs. Xie et al. [10] proposed a trust model for MANETs based on D-S evidence theory. The model can be a good solution for the combination of pieces of evidence, but it failed in addressing the issues concerning conflicting recommendation pieces of evidence. In this paper, we adopt the revised D-S combination rule which includes a consistent intensity to calculate nodes' trust value.

2.2. Trust-Based Routing Protocols

Wang and Wu [15] introduced the trust metric which depended on network traffic statistics to evaluate the trust and then loaded the trust model on the previously proposed distance-based location-aided routing ( $LAR$ ). The algorithm utilized direct trust and recommendation trust to prevent malicious nodes from joining the forwarding. Li et al. [16] built a simple trust model to evaluate neighbours' behaviours forwarding packets and proposed a trust-based reactive multipath routing protocol extending from AODV. Peng et al. [17] incorporated a new dynamic trust mechanism which was based on multiple constraints and collaborative filtering into the extending DSR. Narula et al. [18] selected soft encryption systems and implemented them in conjunction with a trust-based reputation system and a multipath routing to provide a secure routing scheme. The implementation of this trust-based approach using DSR was then discussed. Sirotheau and Sousa [19] proposed an evaluation mechanism that aimed to mitigate routing misbehavior and other network failures. Four attributes of the routes were considered: level of activity, trust, mobility, and number of hops.

When transmitting a packet to a given destination, a node may have two routes: one is short but incredible while the other is long but credible. One of our main aims is to design a rational strategy which involves both hop counts and trust values in making decisions. The detailed implementation of our scheme is a secure extension of the AODV. Because of its ability to cope with network dynamic changes and repair broken links in routes, AODV is one of the promising protocols for deployment in a MANET.

3. Trust Model Based on D-S Evidence Theory

Trust model essentially performs trust derivation, computation, and application [20]. Trust applications including trust-based route discovery and route selection will be discussed in the next section.

3.1. D-S Evidence Theory

D-S evidence theory is based on the identification frame Ω set comprised by basic propositions which are both exclusive and exhaustive. $2^{Ω}$ is the power set of Ω, that is, the set of all the possible propositions based on Ω. Here we define Ω as ${T, - T}$ , where T and $- T$ represent two trust states, namely, credible and incredible. $2^{Ω}$ is ${\emptyset, {T}, {- T}, {T, - T}}$ , in which ∅, ${T}$ , ${- T}$ , and ${T, - T}$ represent the empty set, the propositions of nodes' “Trust”, “Distrust”, and “Uncertain”, respectively. There are definitions of basic reliability function m on $2^{Ω}$ : $2^{Ω} \to [0,1]$ , Belief $Bel$ : $2^{Ω} \to [0,1]$ and Plausibility $Pl$ : $2^{Ω} \to [0,1]$ , satisfying the following equations:

\begin{array}{l} m (\emptyset) = 0, \\ \sum_{A \subseteq Ω} ‍ m (A) = 1, A \neq \emptyset, \\ Bel (A) = \sum_{B \subseteq A}^{} m (B), \forall A \subseteq Ω, \\ Pl (A) = 1 - Bel (\bar{A}), \forall A \subseteq Ω, \end{array}

(1)

where A is named focal element,

m (A) > 0

is the basic confidence level of A, representing how much the evidence supports A to happen.

The difference between Belief and Plausibility is referred to as Belief Interval. It is represented by the range of maximum uncertainty. The relationship of Belief and Plausibility is shown in Figure 1.

Figure 1

Belief (Bel) and Plausibility (Pl).

3.2. Trust Factors

The definition of “Trust” in this paper refers to the confidence that node i has on node j about the ability to forward packets successfully. Nodes tend to select the neighbour that has higher trust value as the intermediate node. In general, the trust between nodes only has some connection with malicious behaviors; however, we should consider more factors that depend on the interactions between neighbour nodes in a MANET due to its flexibility.

3.2.1. Factor of Average Encounter Time ${ACF}_{i, j}$

The concept of average encounter time does well in quantifying node's encounter history record. Encounter means that two nodes enter each other's wireless transmission range. The larger the ${ACF}_{i, j}$ is, the more possibly node i chooses node j as the next hop. The ${ACF}_{i, j}$ during period T is calculated by the following equation

\begin{matrix} {ACF}_{i, j} = \frac{\sum_{t = 0}^{t = T} δ_{i, j}}{T} . \end{matrix}

(2)

If two nodes enter each other's wireless transmission range

δ_{i, j} = 1

, else

δ_{i, j} = 0

. For example, in Figure 2, node i and node j encounter three times during period T; the AC

F_{i, j}

is:

\begin{matrix} {ACF}_{i, j} = \frac{\sum_{t = 0}^{t = T} δ_{i, j}}{T} = \frac{T_{2} - T_{1} + T_{4} - T_{3} + T_{6} - T_{5}}{T} . \end{matrix}

(3)

Figure 2

Average encounter time.

3.2.2. Factor of Mobility ${MOL}_{i, j}$

The topology of MANET is dynamic due to the node movement; hence, in order to establish a more stable routing, it is necessary to take the node mobility into account when a node selects its cooperative nodes. The factor ${MOL}_{i, j}$ is constructed as

\begin{array}{l} {MOL}_{i, j} = | \frac{d_{i, j} (t + T) - d_{i, j} (t)}{d_{i, j} (t + T) + d_{i, j} (t)} |, \\ d_{i, j} (t) = \sqrt{{(x_{i} (t) - x_{j} (t))}^{2} + {(y_{i} (t) - y_{j} (t))}^{2},} \end{array}

(4)

where

d_{i, j}

denotes the distance between node i and node j at time t,

(x_{i} (t), y_{i} (t))

and

(x_{j} (t), y_{j} (t))

are the coordinates of node i and node j at time t, respectively.

3.2.3. Factor of Successful Cooperation Frequency ${SCF}_{i, j}$

Node i has a detection mechanism to obtain its interaction results ${record}_{i, j} = (α_{i, j}, β_{i, j})$ with node j. $α_{i, j}$ and $β_{i, j}$ , respectively, denote the number of successful cooperation and unsuccessful cooperation about node j observed by node i. Suppose ${SCF}_{i, j}$ can be easily expressed by beta distribution, that is, ${SCF}_{i, j} ~ Beta (α_{i, j}, β_{i, j})$ . The factor ${SCF}_{i, j}$ is constructed as

\begin{matrix} {SCF}_{i, j} = \frac{α_{i, j}}{α_{i, j} + β_{i, j}} . \end{matrix}

(5)

Once node j behaves badly, $β_{i, j}$ will increase and ${SCF}_{i, j}$ will decrease, which leads to the decrease of the possibility that node i chooses node j as the next hop.

3.3. Direct Trust

Subject node i monitors the behaviors of object node j in one cycle and acquires the current trust value $CD T_{i, j} = (m_{i, j}^{C} ({T}), m_{i, j}^{C} ({T, - T}), m_{i, j}^{C} ({- T}))$ based on the following expression:

\begin{array}{l} m_{i, j}^{C} ({T}) \\ = \frac{(ω_{1} * {ACF}_{i, j} + ω_{2} * (1 - {MOL}_{i, j}) + ω_{3} * {SCF}_{i, j})}{(\sum_{k = 1}^{3} ω_{k})}, \\ m_{i, j}^{C} ({- T}) \\ = \frac{(ω_{1} * (1 - {ACF}_{i, j}) + ω_{2} * {MOL}_{i, j} + ω_{3} * (1 - {SCF}_{i, j}))}{(\sum_{k = 1}^{3} ω_{k})}, \\ m_{i, j}^{C} ({T, - T}) = 1 - m_{i, j}^{C} ({T}) - m_{i, j}^{C} ({- T}), \end{array}

(6)

where

0 < ω_{k} < 1, k = 1,2, 3

ω_{k}

are determined by specific application environment, usually

ω_{3} > ω_{1}

ω_{3} > ω_{2}

as security is more important.

Furthermore, the direct trust value is recalculated in accordance with history records. Assuming the direct trust value of latest cycle is ${HDT}_{i, j}$ , the update of direct trust value is calculated as follows:

\begin{matrix} {DT}_{i, j} = γ \times {HDT}_{i, j} + (1 - γ) \times {CDT}_{i, j}, \end{matrix}

(7)

where

{DT}_{i, j}

is the direct trust value of subject node i on object node j in current cycle, parameter γ is the adaptive time factor used to weigh history experience against current information. To keep γ preferably dynamic characteristic, it is satisfied as

\begin{matrix} γ = {\begin{cases} γ_{s}, & m_{i, j}^{H} ({T}) \geq m_{i, j}^{C} ({T}), \\ γ_{l}, & m_{i, j}^{H} ({T}) < m_{i, j}^{C} ({T}), \end{cases} \end{matrix}

(8)

where

0 < γ_{s} < γ_{l} < 1

, the parameter

m_{i, j}^{C} ({T})

and

m_{i, j}^{H} ({T})

represent the trust components of

{CDT}_{i, j}

and

{HDT}_{i, j}

, respectively.

3.4. Recommendation Trust Evaluation

3.4.1. Trust Transitivity

Suppose the recommended trust value of node i on node j can be obtained through s different paths, and the number of recommendation paths s depends on nodes' distribution and communication radius. In order to avoid trust recycle recursion and decrease network communication payload, the recommendation values are confined to direct trust value of the common neighbours owned by both node i and node j. As shown in Figure 3, node i can get the trust recommendation of node j from $k_{1}, k_{2}, k_{3}, \dots, k_{s}$ .

Figure 3

Recommendation relationship between subject node i and object node j.

${RT}_{i, j}^{1}$ denotes the recommended trust value of node i on node j through recommendation path $pt 1 = {k 1}$ . The vector forms of ${RT}_{i, j}^{1}$ , ${DT}_{i, k_{1}}$ , ${DT}_{k_{1}, j}$ are as follows:

\begin{array}{l} {RT}_{i, j}^{1} = (m_{i, j}^{1} ({T}), m_{i, j}^{1} ({T, - T}), m_{i, j}^{1} ({- T})), \\ {DT}_{i, k_{1}} = (m_{i, k_{1}}^{D} ({T}), m_{i, k_{1}}^{D} ({T, - T}), m_{i, k_{1}}^{D} ({- T})), \\ {DT}_{k_{1}, j} = (m_{k_{1}, j}^{D} ({T}), m_{k_{1}, j}^{D} ({T, - T}), m_{k_{1}, j}^{D} ({- T})) . \end{array}

(9)

Let us set $Θ = {{T}, {T, - T}, {- T}}$ , A, E and $F \subseteq Θ$ . Then, the ${RT}_{i, j}^{1}$ is calculated as follows:

\begin{matrix} m_{i, j}^{1} (A) = {\begin{cases} m_{i, k_{1}}^{D} (A) \times m_{k_{1}, j}^{D} (A), & A = {T}, \\ \sum_{E = A or F = A}^{} m_{i, k_{1}}^{D} (E) \times m_{k_{1}, j}^{D} (F), & A = {- T}, \\ 1 - m_{i, j}^{1} ({T}) - m_{i, j}^{1} ({- T}), & A = {T, - T} . \end{cases} \end{matrix}

(10)

Using the symbol ⊗ to denote this operation, we get

\begin{matrix} {RT}_{i, j}^{1} = {DT}_{i, k_{1}} \otimes {DT}_{k_{1}, j} . \end{matrix}

(11)

To vividly show the process of trust transitivity, we resort to Figure 4. It is obvious to see that as long as one of ${DT}_{i, k_{1}}$ and ${DT}_{k_{1}, j}$ is distrust, then ${RT}_{i, j}^{1}$ is distrust.

Figure 4

The process of trust transitivity.

Extending the above transitivity to multihop, we can get recommended trust through complex recommendation paths with many middle nodes

\begin{matrix} {RT}_{i, j}^{1} = {DT}_{i, •} \otimes \dots \otimes {DT}_{•, j}, \end{matrix}

(12)

where the symbol • indicates anonymous nodes in recommendation path.

3.4.2. Dynamic Aggregation of Recommended Trust

On the basis of trust transitivity, node i obtains recommended trust values on node j through s recommendation paths, namely,

\begin{array}{l} {RT}_{i, j}^{1} = (m_{i, j}^{1} ({T}), m_{i, j}^{1} ({T, - T}), m_{i, j}^{1} ({- T})) \\ {RT}_{i, j}^{2} = (m_{i, j}^{2} ({T}), m_{i, j}^{2} ({T, - T}), m_{i, j}^{2} ({- T})) \\ ⋮ \\ {RT}_{i, j}^{s} = (m_{i, j}^{s} ({T}), m_{i, j}^{s} ({T, - T}), m_{i, j}^{s} ({- T})) . \end{array}

(13)

Then, node i would aggregate these pieces of evidence to get a consensus on node j. Due to the existence of malicious nodes that may offer false recommendation, we introduce the revised D-S combination rule which adopts a consistent intensity to adjust weights of recommended trust values. The integration process is described in detail as follows.

Firstly, we compute the corresponding average weight denoted as $I_{u}$ . The consistent intensity between ${RT}_{i, j}^{u}$ and ${RT}_{i, j}^{v}$ is defined as follows [21]:

\begin{array}{l} I_{u, v} = 1 - \sqrt{\frac{1}{2} ({∥ {\vec{m}}_{i, j}^{v} ∥}^{2} + {∥ {\vec{m}}_{i, j}^{u} ∥}^{2} - 2 〈 {\vec{m}}_{i, j}^{v}, {\vec{m}}_{i, j}^{u} 〉)}, \\ v = 1,2, \dots, s; u = 1,2, \dots, s, \end{array}

(14)

where

{∥ {\vec{m}}_{i, j}^{v} ∥}^{2} = 〈 {\vec{m}}_{i, j}^{v}, {\vec{m}}_{i, j}^{v} 〉

{∥ {\vec{m}}_{i, j}^{u} ∥}^{2} = 〈 {\vec{m}}_{i, j}^{u}, {\vec{m}}_{i, j}^{u} 〉

〈 {\vec{m}}_{i, j}^{v}, {\vec{m}}_{i, j}^{u} 〉

is the inner product of

{\vec{m}}_{i, j}^{v}

and

{\vec{m}}_{i, j}^{u}

The difference between two pieces of recommended trust evidence increases with the reduction of consistent intensity. The lower the consistent intensity is, the more probably false trust recommendation may occur.

Furthermore, the matrix of consistent intensity composed of all the recommended trust values is defined as follows:

\begin{matrix} I_{s \times s} = [\begin{bmatrix} 1 & I_{1,2} & \dots & I_{1, s} \\ I_{2,1} & 1 & \dots & I_{2, s} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ I_{s, 1} & I_{s, 2} & \dots & 1 \end{bmatrix}] . \end{matrix}

(15)

Through summation in row and normalization, the totally consistent intensity of recommended trust ${RT}_{i, j}^{u}$ , which is equal to the average weight $I_{u}$ , is computed by

\begin{matrix} I_{u} = \frac{\sum_{v = 1, v \neq u}^{s} I_{u, v}}{\underset{1 \leq w \leq s}{Max (\sum_{v = 1, v \neq w}^{s} I_{w, v})}} . \end{matrix}

(16)

Then, the basic reliability function m of every recommended trust evidence is amended by $I_{u}$ as follows:

\begin{array}{l} {m_{i, j}^{u}}^{'} ({T}) = I_{u} \times m_{i, j}^{u} ({T}), \\ {m_{i, j}^{u}}^{'} ({- T}) = I_{u} \times m_{i, j}^{u} ({- T}), \\ {m_{i, j}^{u}}^{'} ({T, - T}) = 1 - {m_{i, j}^{u}}^{'} ({T}) - {m_{i, j}^{u}}^{'} ({- T}), \\ u = 1,2, \dots, s . \end{array}

(17)

Next, we apply the amended basic trust reliability function m to D-S combination rule. Assume that

Be l_{1}

and

Be l_{2}

are two trust degree functions that are on the same identification frame Ω; their basic reliability degree functions are

m_{1}

and

m_{2}

. And m, the basic trust reliability function of

Bel

, can be expressed as follows:

\begin{array}{l} m (A) = m_{1} (A) \oplus m_{2} (A) = \frac{\sum_{X \cap Y = A}^{} m_{1} (X) \times m_{2} (Y)}{1 - K}, \\ A \neq \emptyset, A \subseteq Ω, \\ m (\emptyset) = 0, \\ K = \sum_{X \cap Y = \emptyset} ‍ m_{1} (X) \times m_{2} (Y), \end{array}

(18)

where ⊕ is called “Direct Sum,” representing the combinatorial operation between pieces of evidence.

Extending to s independent pieces of evidence which belongs to the same identification frame Ω, we can get

\begin{array}{l} m (A) = ((m_{1} (A) \oplus m_{2} (A)) \oplus \dots) \oplus m_{s} (A), m (\emptyset) = 0, \\ A \neq \emptyset, A \subseteq Ω . \end{array}

(19)

At last, the consistent recommended trust ${RT}_{i, j}^{'}$ is obtained.

3.5. Overall Trust Value Synthesis

Through the observation and recommendation from neighbour nodes, subject node i computes ${DT}_{i, j} (t)$ and ${RT}_{i, j} (t)$ . The D-S evidence theory can combine conflicting and uncertain information to make a correct decision and accelerate converge rate of trust calculation. Consequently, it is used to synthesize ${DT}_{i, j} (t)$ and ${RT}_{i, j} (t)$ for the overall trust value ${OT}_{i, j} (t)$ :

\begin{array}{l} m_{i, j}^{O} (A) = m_{i, j}^{D} (A) \oplus m_{i, j}^{R} (A) \\ = \frac{1}{N} \sum_{E \cap F = A}^{} m_{i, j}^{D} (E) \times m_{i, j}^{R} (F), A \subseteq θ, \\ N = \sum_{E \cap F \neq \emptyset}^{} m_{i, j}^{D} (E) \times m_{i, j}^{R} (F) > 0 . \end{array}

(20)

Algorithm 1 shows the process that subject node i judges whether node j is “Trust”, “Distrust” or “Uncertain”. The threshold values η and ξ are determined by specific application environment; here, we define $η = 0.4$ and $ξ = 0.1$ . If the trust component is the biggest and the uncertain component is smaller than η, node i regards node j as “Trust.” If the distrust component is the biggest and the uncertain component is smaller than η, node i regards node j as “Distrust.” Otherwise, node i regards node j as “Uncertain”.

Algorithm 1: Process of judging node j's style.

(1) if $m_{i, j}^{o} ({T, - T}) > η$ then

(2) node i regard node j as “Uncertain”;

(3) else if $m_{i, j}^{o} ({T}) - m_{i, j}^{o} ({- T})$

$> ξ & & m_{i, j}^{o} ({T}) > m_{i, j}^{o} ({T, - T})$ then

(4) node i regard node j as “Trust”;

(5) else if $m_{i, j}^{o} ({- T}) - m_{i, j}^{o} ({T})$

$> ξ & & m_{i, j}^{o} ({- T}) > m_{i, j}^{o} ({T, - T})$ then

(6) node i regard node j as “Distrust”;

(7) else

(8) node i regard node j as “Uncertain”;

(9) end if

4. Trust-Based Routing Protocol

In this section, we extend the AODV protocol to which can establish trusted route with minimum hops and maximum path trust based on trust mechanism denoted by TDS-AODV. The differences between AODV and TDS-AODV are listed as follows. (1)

We append the model of trust computation and fields including ${ACF}_{i, j}$ , ${MOL}_{i, j}$ , ${SCF}_{i, j}$ , and ${OT}_{i, j}$ in the neighbour table of each node.

(2)

Every node maintains a local black list.

(3)

We append $T_{route}$ field in the route reply message and $T_{route}$ denotes the accumulated route trust.

(4)

We set backup route to avoid initiating the route discovery frequently.

4.1. Route Discovery

During the process of route discovery, when node i chooses another node j to forward a packet, node i may suffer some attacks from node j, such as black hole attack. Thus, it is important to choose a reliable next hop node. The process of judging whether node j can be the next hop of node i is as follows.

Step 1.

Node i checks whether it has the trust value of node j ( ${OT}_{i, j}$ ); if it has, turn to Step 5, else turn to Step 2.

Step 2.

Node i computes $D_{i, j}$ according to (6)–(8) and broadcasts a $R e c o m m e n d a t i o n_Q u e r y$ message to the common neighbours denoted as node k.

Step 3.

After receiving the $R e c o m m e n d a t i o n_Q u e r y$ message, node k sends $D_{k, j}$ to node i if $m_{k, j} ({T, - T}) < η$ .

Step 4.

Node i calculates $R T_{i, j}$ based on (13)–(18) and ${OT}_{i, j}$ based on (19).

Step 5.

Whether node j is reliable can be estimated using Algorithm 1. If node j is trusted, node i will update ${OT}_{i, j}$ and regards node j as its credible next hop node, else node i will not choose node j to transmit packets and move node j into its local black list as a malicious node.

Once a node is in a black list, it will neither receive packets from its neighbour nor have its packets forwarded. That is, a malicious node in a black list is excluded by its neighbours. When a node exists in the black lists of all its neighbours, it will be excluded from the local network.

Sending packets by the trusted route will decrease the probability of malicious attacks and improve the survivability of MANETs. We evaluate the trustworthiness of a route by the trust value of nodes along the route, denoted by $T_{route}$ [16]

\begin{array}{l} T_{route} = \prod m_{i, k} ({T}), \\ n_{i} \in route, n_{k} \in route, n_{i} \to n_{k}, n_{k} \neq n_{d}, \end{array}

(21)

where

n_{i}

and

n_{k}

are any two adjacent nodes among the route;

n_{d}

is the destination node in the route;

n_{i} \to n_{k}

means that

n_{k}

is the next hop node of

n_{i}

;

n_{k} \neq n_{d}

means that the destination node

n_{d}

should not forward the packets for itself and

m_{i, d} ({T})

is not used to calculate the path trust to node

n_{d}

As shown in Figure 5, the trust value of path $P (A, B, C, D)$ is equal to 0.68 (i.e. $T_{A, B, C, D} = m_{A, B} ({T}) \times m_{B, C} ({T}) = 0.85 \times 0.8 = 0.68$ ). Figure 6 shows an example of a multiple path. Among the three paths from A to H, path $P (A, F, G, H)$ is the most credible path.

Figure 5

Path trust computation of a single path.

Figure 6

Path trust computation of a multiple path.

In our trusted routing mechanism, the route discovery includes three processes: (i) Route Request ( $R R E Q$ ) Message Delivery; (ii) Route Reply ( $R R E P$ ) Message Delivery; and (iii) route selection.

4.1.1. $R R E Q$ Delivery

An $R R E Q$ packet contains the following fields: $〈 S o u r c e A d d r$ , $S o u r c e S e q u e n c e N o$ , $B r o a d c a s t I D$ , $D e s t A d d r$ , $D e s t S e q u e n c e N o$ , $H o p C o u n t e r 〉$ .

When the source node S needs to send data to the destination node D, it first checks whether there is a feasible path found between S and D. If so, S sends the data to D; otherwise, S will broadcast a $R R E Q$ to start a route discovery.

When any reliable intermediate node K whose authentication process was discussed before receives a $R R E Q$ packet from a neighbour J, it deals with the request according to the following steps.

Step 1.

It checks whether one copy of the same $R R E Q$ has been received according to the $B r o a d c a s t I D$ . If so and the later copy has greater $H o p C o u n t e r$ , the $R R E Q$ will be discarded and the procedure ends; otherwise, go to Step 2.

Step 2.

If node J is not the source, node K creates a reverse route to S using the previous hop (node J) of the $R R E Q$ as the next hop.

Step 3.

K checks whether there is a valid route to the destination. If so and the $D e s t S e q u e n c e N o$ of the route is greater than that in the $R R E Q$ , K unicasts a Route Replay ( $R R E P$ ) message to S via J through the reverse route; otherwise, go to Step 4.

Step 4.

K increases $H o p C o u n t e r$ by one and propagates the $R R E Q$ to all its neighbours.

The pseudocode of the $R R E Q$ is shown in Algorithm 2.

Algorithm 2: The $R R E Q$ delivery algorithm.

(1) To source node:

(2) if there is a feasible path found between S and D then

(3) S sends data to D;

(4) else

(5) broadcasts the $R R E Q$ to start a route discovery;

(6) end if

(7) To a reliable intermediate node:

(8) checks whether one copy of the same $R R E Q$ has

been received;

(9) if so and the later copy has greater $H o p C o u n t e r$ then

(10) discards $R R E Q$ and the procedure ends;

(11) else

(12) creates a reverse route to S using the previous hop

of the $R R E Q$ as the next hop;

checks whether there is a valid route to the

destination;

(13) if so and the $D e s t S e q u e n c e N o$ of the route is

greater than that in the $R R E Q$ then

(14) unicasts a Route Replay ( $R R E P$ ) message to S

via J through the reverse route;

(15) else

(16) increases $H o p C o u n t e r$ by one;

propagates the $R R E Q$ to all its neighbours;

(17) end if

(18) To destination node:

(19) calls the process of route reply;

(20) end if

4.1.2. $R R E P$ Delivery

An $R R E P$ packet contains the following information: $〈 S o u r c e A d d r$ , $S o u r c e S e q u e n c e N o$ , $D e s t A d d r$ , $D e s t S e q u e n c e N o$ , $H o p C o u n t e r$ , $L i f e T i m e$ , $P a t h T r u s t 〉$ . When D receives the $R R E Q$ packet, it deals with the request according to the following steps.

Step 1.

If it is the first time for D to receive a $R R E Q$ packet, then D sets a timer window $t_{D}$ and records the route of $R R E Q$ in its cache and go to Step 6, otherwise go to Step 2.

Step 2.

If $t_{D}$ expires, it discards the follow-up $R R E Q$ packets, otherwise go to Step 3.

Step 3.

If there are less than three routes in the cache of D, then add the new route in its cache and go to Step 6, otherwise go to Step 4.

Step 4.

D compares the hop count of the new route with that of the route which owns the maximum hop count in its cache (denoted as route X). If the former is more than or equal to the latter, D discards the new $R R E Q$ , otherwise turn to Step 5.

Step 5.

D uses the new route to substitute route X and then turns to Step 6.

Step 6.

D sets $T_{route}$ and then unicasts the $R R E P$ packets with $T_{route}$ to the intermediate node.

After receiving a $R R E P$ packet, the intermediate node computes $T_{route}$ according to (21) and updates the field of $T_{route}$ then it forwards the $R R E P$ packet with $T_{route}$ . The pseudo code of $R R E P$ delivery algorithm is shown in Algorithm 3.

Algorithm 3: The $R R E P$ delivery algorithm.

(1) To destination node:

(2) sets $T_{route} = 1$ ;

(3) if received the first $R R E Q$ packet then

(4) sets a timer window $t_{D}$ ;

increases the destination sequence number by $1$ ;

records the route of $R R E Q$ in its cache;

sends the $R R E P$ with $T_{route}$ along the path to the

intermediate node;

(5) else if $t_{D}$ expires then

(6) discards the follow-up $R R E Q$ packets;

(7) else if there are less than three routes in its cache then

(8) adds the new route in the cache;

sends the $R R E P$ with $T_{route}$ along the path to the

intermediate node;

(9) else if the hop count of the new route is more than

or equal to that of route X then

(10) discards the new $R R E Q$ ;

(11) else

(12) uses the new route to substitute route X;

sends the $R R E P$ with $T_{route}$ along the path to the

intermediate node;

(13) end if

(14) To a reliable intermediate node:

(15) updates $T_{route}$ according to (21);

forwards the $R R E P$ ;

(16) To source node:

(17) updates $T_{route}$ according to (21);

calls route selection;

4.1.3. Route Selection

When S receives the $R R E P$ packet, if the timer window $t_{D}$ does not expire, it needs to update the $T_{route}$ field of this message according to (21). Otherwise, S discards follow-up $R R E P$ packets and picks the one with largest $T_{route}$ as its main route. The route with second largest $T_{route}$ is regarded as backup route which aims at avoiding initiating the route discovery frequently. The pseudo code of route selection algorithm is shown in Algorithm 4.

Algorithm 4: The route selection algorithm.

(1) when source node receives the $R R E P$ , checks the $t_{s}$ ;

(2) if $t_{s}$ does not expire then

(3) updates the $T_{route}$

(4) else

(5) discards the follow-up $R R E P$ ;

selects the route with the largest as its main route;

picks the route with second largest $T_{route}$ as its

backup routes;

(6) end if

4.2. Route Maintenance

After each successful route discovery takes place, S can deliver its data to D through a route. However, the route may break at any time instant due to the mobility of nodes or attacks. In order to maintain a stable and secure network connection, route maintenance is necessary to ensure the system survivability. AODV protocol designed two types of route maintenance mode one is a local repair mechanism and the other is that S reestablishes the route. Detailed process is discussed as follows.

Once the route is found, each node along the route periodically sends $H E L L O$ messages to its neighbour node for link failure detection. Link failure occurs when the neighbour node does not reply to the $H E L L O$ messages after a period of time. When a node N detects a link failure, it first sends a Route Error ( $R E R R$ ) message to S. S checks whether there is a backup route; if a backup route is found, S replaces the failure route with the backup and sends a $F o u n d B a c k u p$ message to N. Otherwise S sends a $N o n B a c k u p$ message to N and then N starts a local repair mechanism. N broadcasts a $R R E Q$ message to find an alternative route between N and D. If no route is found, the system resorts back to another mechanism of sending a $R E R R$ message upstream to S, starting a new route discovery.

In TDS-AODV, besides link failure, if $T_{route} < T_{thr}$ , S will also perform route maintenance which works as follows. During the transmission, if S finds the trust of a route has decreased, it sends a route check message along the route to check the route status and sets a timeout period to wait for the route check message from D. When S receives the reply, it will update the $T_{route}$ and judge whether $T_{route}$ is larger than $T_{thr}$ . If $T_{route} < T_{thr}$ , S resorts to the backup route and updates the path trust of the backup route (denoted as $T_{rb}$ ). If $T_{rb} > T_{thr}$ , S discards the main route and uses the backup route to send packets. Otherwise, a new route discovery is triggered.

5. Simulation Studies

To evaluate the performance of TDS-AODV, we use the simulation tool MATLAB. In our simulation, fifty nodes at first are randomly placed in a specific field (100 m × 100 m) and move to another random position with a speed chosen between 0 to 30 m/s. The malicious nodes randomly drop data packets based on their trust value. The simulation parameters are listed in Table 1.

Table 1

Simulation parameters.

Parameters	Value
Simulation time	100 s
Number of nodes	50
Source node	Node 1
Destination node	Node 50
Area size	100 m × 100 m
Transmission radius	25 m
Max speed	0–30 m/s
Number of malicious node	0–20

5.1. Performance Metrics

To measure the performance of our proposed TDS-AODV, we identify three metrics: (i) throughput: the number of packets transmitted per unit time from the source node to the destination node; (ii) packet delivery ratio: the ratio of the number of packets received to the total number of packets; and (iii) average end to end delay: the average delay between the sending of the packets by the source node and its receipt at the destination node.

The network topology of TDS-AODV was compared with that of TAODV [22] and AODV in this paper. We also carried out three simulations in terms of the maximum node speed and the proportion of malicious nodes to compare the above three performances of two protocol.

5.2. Simulation Results and Analysis

Figures 7 and 8 are the network topology of TDS-AODV and AODV with 20% malicious nodes. It is obvious to see that our method can avoid malicious nodes becoming the next hop effectively while in AODV malicious nodes can be selected as the next hop. The reason is that TDS-AODV takes nodes' trust value into account.

Figure 7

Network topology of TDS-AODV.

Figure 8

Network topology of AODV.

Figure 9 shows the average routing hop of TDS-AODV and AODV with different numbers of malicious nodes. when the number of malicious nodes accounts for a certain proportion of the number of total nodes, the average route hop of TDS-AODV is a little higher than that of AODV, because nodes would rather choose a relative longer path than choose malicious nodes as the next hop nodes in TDS-AODV. Although the path of TDS-AODV may be a little longer, the performance of TDS-AODV is still better than that of AODV as it eliminates malicious nodes out of the routing paths, which will be proven by the following simulation experiments.

Figure 9

Everage route hop of TDS-AODV and AODV with different numbers of malicious nodes.

Figures 10 and 11 depict the throughput of TDS-AODV, TAODV, and AODV. The routing throughput of TDS-AODV is averagely 29.60% lower than that of AODV and 21.27% lower than that of TAODV in Figure 10. This is because that our method can detect malicious nodes effectively and thus prevent the channel congestion. The throughput changes little at different maximum speed which indicates our method has excellent dynamic. As shown in Figure 11, the throughput rises slowly with the increase in the number of malicious nodes. Besides, TDS-AODV rises more slowly than TAODV and AODV as it prevents the malicious nodes from becoming the next hop and affects less by malicious nodes.

Figure 10

Performance of network throughput at different maximum speed.

Figure 11

Performance of network throughput with different number of malicious nodes.

The packet delivery ratio of TDS-AODV, TAODV, and AODV is shown in Figures 12 and 13. It can be observed that TDS-AODV outperforms TAODV and AODV in the packet delivery ratio because of the fact that in TDS-AODV intermediate nodes make routing selection considering hop count and trust value. It shows the packet delivery ratio of TDS-AODV is averagely 46.24% higher than that of AODV and 17.18% higher than that of TAODV in Figure 12. Figure 13 indicates that TDS-AODV has better fault tolerance as its packet delivery ratio declines slowly with the increase in the number of malicious nodes.

Figure 12

Performance of packet delivery ratio at different maximum speed.

Figure 13

Performance of packet delivery ratio with different number of malicious nodes.

We give the average end to end delay comparisons of TDS-AODV, TAODV, and AODV in Figures 14 and 15. As shown in Figure 14, the average end-to-end delay of three schemes rises very slowly with the increase in the maximum speed. However, the average delay of AODV is 18.73% higher than that of TDS-AODV and the average delay of TAODV is 7.74% higher than that of TDS-AODV in Figure 14 due to the lack of consideration of dynamic topology. Figure 15 depicts the performance of average delay with different number of malicious nodes. The average end to end delay of TDS-AODV declines faster than AODV. Because when intermediate nodes choose the next hop they will not consider the malicious nodes and thus save the time.

Figure 14

Performance of average delay at different maximum speed.

Figure 15

Performance of average delay with different number of malicious nodes.

6. Conclusions

In this paper, we propose a novel trust mechanism after investigating on trust models of ad hoc networks and routing in current researches. In this trust mechanism, direct trust value on each neighbour node is calculated by using trust factors of average encounter time, mobility, and successful cooperation frequency, which are defined according to node behaviors. Meanwhile, the revised D-S evidence theory is used to combine multiple recommended pieces of evidence and obtain the recommended trust value. Then, a trusted routing protocol based on the novel trust mechanism, by extending the AODV protocol is presented. In this protocol, a source establishes a main path and a backup path which are evaluated by two aspects: hop counts and trust values. At last, we validate the correctness and effectiveness of TDS-AODV by comparing its performance with TAODV and AODV on Matlab platform. Simulation results show that TDS-AODV is able to eliminate malicious nodes effectively when building the route and achieves an improvement in throughput, packet delivery ratio, and average end-to-end delay.

In our future work, we will conduct extensively simulation and rigorous analysis to quantify and evaluate the tradeoff between the security and the nodes' energy consumption. In addition, a comprehensive performance evaluation will be conducted to compare TDS-AODV with other routing protocols (e.g., DSR).

Footnotes

Acknowledgments

The authors are grateful to the anonymous reviewers for their insightful comments. This work is supported by the National Natural Science Foundation of China under Grants no. 61201317 and no. 61001138.

References

Wang

Huang

C. H.

L. Y.

Yang

W. Z.

Trustbased trustbased minimum cost opportunistic routing for Ad Hoc networks

Journal of Systems and Software 2011 84 12 2107 2122

Perkins

C. E.

Highly

Dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers

Proceedings of the Conference on Communications Architectures, Protocols and Applications (SIGCOMM '94)

1994

234 244

Johnson

D. B.

Maltz

D. A.

Dynamic source routing in Ad Hoc wireless networks

Mobile Computing 1996 353 153 181

Perkins

C. E.

Royer

E. M.

Ad-Hoc on-demand distance vector routing

Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '99)

February 1999

New Orleans, LA, USA

90 100

2-s2.0-34347349933

10.1109/MCSA.1999.749281

Pirzada

A. A.

Datta

McDonald

C. S.

Trust-based routing for Ad-Hoc wireless networks

Proceedings of the 12th IEEE International Conference on Networks (ICON '04)

November 2004

326 330

2-s2.0-21644478586

Xia

Jia

Z. P.

Zhang

A subjective trust management model based on AHP for MANETs

Proceedings of the International Conference on Network Computing and Information Security (NCIS '11)

May 2011

Guilin, China

363 368

2-s2.0-79961145911

10.1109/NCIS.2011.80

Peng

S. C.

Jia

W. J.

Wang

G. J.

Voting-based clustering algorithm with subjective trust and stability in mobile Ad-Hoc networks

Proceedings of the 5th International Conference on Embedded and Ubiquitous Computing (EUC '08)

December 2008

Shanghai, China

3 9

2-s2.0-63149130883

10.1109/EUC.2008.93

Zouridaki

Mark

B. L.

Hejmo

Thomas

R. K.

E-hermes: a robust cooperative trust establishment scheme for mobile Ad Hoc networks

Ad Hoc Networks 2009 7 6 1156 1168

2-s2.0-64049107478

10.1016/j.adhoc.2008.10.003

Omar

Challal

Bouabdallah

Reliable and fully distributed trust model for mobile Ad Hoc networks

Computers and Security 2009 28 3-4 199 214

2-s2.0-63049099708

10.1016/j.cose.2008.11.009

10.

Xie

J. F.

Yang

Dong

X. W.

A trust method of MANETs based on D-S evidence theory

International Journal of Advancements in Computing Technology 2012 4 2 247 257

11.

Huang

L. D.

Xue

X. L.

Zhuang

H. L.

A trust model based on evidence theory for P2P systems

Applied Mechanics and Materials 2010 20 23 99 104

2-s2.0-76449102186

12.

Jiang

L. M.

Zhang

A new evidential trust model for open distributed systems

Expert Systems with Applications 2012 39 3 3772 3782

13.

Dempster

A. P.

Upper and lower probabilities induced by a multi-valued mapping

The Annals of Mathematical Statistics 1967 38 2 325 339

14.

Shafer

A Mathematical Theory of Evidence 1976

New Jersey, NJ, USA

Princeton University Press

15.

Wang

Improved secure trust-based location-aided routing model for MANETs

China Communications 2011 8 3 154 162

16.

Jia

Z. P.

Zhang

Wang

H. Y.

Trust-based on-demand multipath routing in mobile Ad Hoc networks

IET Information Security 2010 4 4 212 232

2-s2.0-78650394299

10.1049/iet-ifs.2009.0140

17.

Peng

S. C.

Jia

W. J.

Wang

G. J.

Guo

M. Y.

Trusted routing based on dynamic trust mechanism in mobile Ad-Hoc networks

IEICE Transactions on Information and Systems 2010 E93.D 3 510 517

2-s2.0-77950193796

10.1587/transinf.E93.D.510

18.

Narula

Dhurandher

S. K.

Misra

Woungang

Security in mobile Ad-Hoc networks using soft encryption and trust-based multi-path routing

Computer Communications 2008 31 4 760 769

2-s2.0-39049100803

10.1016/j.comcom.2007.10.021

19.

Sirotheau

S. L. F.

Sousa

R. T. D.

Evaluating trust in Ad Hoc network routing by induction of decision trees

IEEE Latin America Transactions 2012 10 1 1332 1343

20.

Pirzada

A. A.

McDonald

Datta

Performance comparison of trust-based reactive routing protocols

IEEE Transactions on Mobile Computing 2006 5 6 695 710

2-s2.0-33646410469

10.1109/TMC.2006.83

21.

Jousselme

A. L.

Grenier

Bosse

A new distance between two bodies of evidence

Information Fusion 2001 2 2 91 101

2-s2.0-0010623928

10.1016/S1566-2535(01)00026-4

22.

X. Q.

Lyu

M. R.

Liu

J. C.

A trust model based routing protocol for secure Ad Hoc networks

Proceedings of the IEEE Aerospace Conference Proceedings

March 2004

1286 1295

2-s2.0-11244296240

A Credible Routing Based on a Novel Trust Mechanism in Ad Hoc Networks

Abstract

1. Introduction

2. Related Works

2.1. Trust Evaluation

2.2. Trust-Based Routing Protocols

3. Trust Model Based on D-S Evidence Theory

3.1. D-S Evidence Theory

3.2. Trust Factors

3.2.1. Factor of Average Encounter Time ACF i , j

3.2.2. Factor of Mobility MOL i , j

3.2.3. Factor of Successful Cooperation Frequency SCF i , j

3.3. Direct Trust

3.4. Recommendation Trust Evaluation

3.4.1. Trust Transitivity

3.4.2. Dynamic Aggregation of Recommended Trust

3.5. Overall Trust Value Synthesis

Algorithm 1: Process of judging node j's style.

4. Trust-Based Routing Protocol

4.1. Route Discovery

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

4.1.1. R R E Q Delivery

Step 1.

Step 2.

Step 3.

Step 4.

Algorithm 2: The R R E Q delivery algorithm.

4.1.2. R R E P Delivery

Step 1.

Step 2.

Step 3.

Step 4.

Step 5.

Step 6.

Algorithm 3: The R R E P delivery algorithm.

4.1.3. Route Selection

Algorithm 4: The route selection algorithm.

4.2. Route Maintenance

5. Simulation Studies

5.1. Performance Metrics

5.2. Simulation Results and Analysis

6. Conclusions

Footnotes

Acknowledgments

References

3.2.1. Factor of Average Encounter Time ${ACF}_{i, j}$

3.2.2. Factor of Mobility ${MOL}_{i, j}$

3.2.3. Factor of Successful Cooperation Frequency ${SCF}_{i, j}$

4.1.1. $R R E Q$ Delivery

Algorithm 2: The $R R E Q$ delivery algorithm.

4.1.2. $R R E P$ Delivery

Algorithm 3: The $R R E P$ delivery algorithm.