# B-iTRS: A Bio-Inspired Trusted Routing Scheme for Wireless Sensor Networks

Authors: Mingchuan Zhang; Ruijuan Zheng; Qingtao Wu; Wangyang Wei; Xiuling Bai; Haixia Zhao
Journal: Journal of Sensors
 (2015)

---

## Abstract

In WSNs, routing algorithms need to handle dynamical changes of network topology, extra overhead, energy saving, and other requirements. Therefore, routing in WSNs is an extremely interesting and challenging issue. In this paper, we present a novel bio-inspired trusted routing scheme (B-iTRS) based on ant colony optimization (ACO) and Physarum autonomic optimization (PAO). For trust assessment, B-iTRS monitors neighbors’ behavior in real time, receives feedback from Sink, and then assesses neighbors’ trusts based on the acquired information. For routing scheme, each node finds routes to the Sink based on ACO and PAO. In the process of path finding, B-iTRS senses the load and trust value of each node and then calculates the link load and link trust of the found routes to support the route selection. Moreover, B-iTRS also assesses the route based on PAO to maintain the route table. Simulation results show how B-iTRS can achieve the effective performance compared to existing state-of-the-art algorithms.


---

## Body

## 1. Introduction

Mobile wireless sensor networks (WSNs) are autonomous wireless communication networks and ideal candidates for applications to report detected events of interest, such as military surveillance and forest fire [1, 2]. Because of the sensor nodes’ mobility and failures, limited bandwidth, and power energy, routing algorithms need to handle dynamical changes of network topology, extra overhead, energy saving, and other requirements. Therefore, routing in WSNs is an extremely interesting and challenging issue.Traditional WSNs routing protocols assume that all sensor nodes work in a benevolent manner, which may render the WSNs vulnerable to malicious attacks in case of the presence of selfish and malicious nodes. Routing protocols, data, battery power, and bandwidth are the common targets of these attacks. Scientific researches prove that selfish behavior will seriously affect the network performance [3]. Since the safety of multihop communication depends on the reliability of nodes on the route to destination primarily, it is important for routing protocols to know the reliability of the nodes forming the route. Moreover, how to guarantee the efficiency of the multihop route is important to prolong lifetime of WSNs. Therefore, security and efficiency are the significant features for routing in WSNs.Recently, many research results on the trust and efficiency of routing have been proposed. In order to solve the security of routing protocol, some techniques (e.g., trust value, detection, cryptography, and data hiding) are proposed based on different applications [1–5]. Bao et al. [4] propose a highly scalable trust-based geographic routing protocol (TGRP) for WSNs to effectively deal with selfish or malicious nodes. Zhan et al. [1] design and implement TARF, a robust trust-aware routing framework for dynamic WSNs. Some methods (e.g., location-aware method, energy-aware method, energy harvesting method, and their combination) are discussed [6–9]. Yang and Heinzelman [7] propose sleeping multipath routing, which selects the minimum number of disjoint paths to achieve the trade-off of given reliability requirement and energy efficiency. Trajcevski et al. [8] present heuristic approaches to relieve some of the routing load of the boundary nodes of energy holes in location-aware WSNs. Chen et al. [9] present a method to enhance the efficiency of gathering sensor data based on a quadrotor-based mobile Sink.Bio-inspired methods [10–15] are advantageous for solving the problems regardless of security and efficiency of routing protocols. Gunes et al. [10] present an on-demand routing algorithm ARA based on ant colony optimization (ACO) and AODV [16]. Di Caro et al. [11] propose the hybrid routing algorithm AntHocNet, where artificial ants reactively set up multiple routes on demand and proactively test existing paths and explore new paths during the course of communication session. Tero et al. [12] propose a mathematical model for the Physarum autonomic optimization (PAO). Li et al. [13] present a routing protocol for wireless sensor networks based on PAO. We study the foraging rule of Physarum and present a Physarum-inspired routing protocol for WSNs [14, 15].In addition, trust computation or management is important for assessing node’s reliability. Ren et al. [17] propose a trust management scheme for UWSNs to provide efficient and robust trust data storage and trust generation, where a geographic hash table is employed. Chen et al. [18] design and validate a dynamic trust management protocol for secure routing optimization in DTN environments in the presence of well-behaved, selfish, and malicious nodes. Priyanka et al. [19] present a malicious node detection scheme for wireless sensor networks, where the malicious nodes are detected by computing the average number of event cycles. Indhu Lekha and Kathiroli [20] propose a vector based trust mechanism which nominates a cluster head based on the higher trust value computation with the earliest bit vectors and enhanced certificate revocation scheme for discarding the authorization of the misbehaving nodes. Wang et al. [21] propose the framework ARTSense to solve the problem of “trust without identity” in mobile sensing, where contextual factors are employed to dynamically affect the trustworthiness of the sensing data as well as the mutual support and conflict among data from different sources.In this paper, we propose a novel bio-inspired trusted routing scheme (B-iTRS) in comprehensive thought of trust and load. B-iTRF consists of trust mechanism and routing scheme. For trust mechanism, B-iTRS assesses nodes’ trust value through monitoring nodes’ behavior in real time and receives feedback fromSink. For routing scheme, B-iTRS finds routes to the Sink based on ACO by introducing cross-layer [22] and assesses the discovered routes based on PAO.The rest of this paper is organized as follows. Section2 introduces the models used in B-iTRS. Section 3 details the proposed B-iTRS. Section 4 analyzes B-iTRS with mathematical method. Section 5 evaluates our models and algorithms with extensive simulations. Finally, the conclusion is presented in Section 6.


## 2. System Framework and Models

### 2.1. Typical WSNs Scenario

This paper considers large multihop WSNs whose nodes are distributed randomly in a two-dimensional space. We assume that (1) each node has a single channel, (2) the interference rangeR is equal to the transmission range, and (3) all communication links are bidirectional.Based on the assumptions, WSNs can be abstracted as a graphG
=
(
V
,
E
), where V is the set of all nodes and E is the set of all edges. Each edge e
(
i
,
j
)
∈
E denotes that the two nodes are located within each other’s transmission range.In some circumstances, theSink node moves along a certain orbit in the field and broadcasts periodically its current positions to improve the efficiency of collected data. An example of such WSNs’ topology is shown in Figure 1.Figure 1
An example of MWSNs’ topology.


### 2.2. The Framework of B-iTRS

Based on the above discussion, Figure2 illustrates the design of the proposed B-iTRS framework which consists of trust assessment and routing scheme.Figure 2
B-iTRS framework.For trust assessment, each node monitors its neighbors’ behavior in real time and receives the feedback from theSink node. Based on the neighbors’ behavior and feedback information, B-iTRS assesses trusts of neighbors; that is, the trust of corresponding neighbor is added by a different positive, negative, or zero value according to the behavior’s weight or Sink’s feedback. In most cases, the trust consists of two sections—direct trust and indirect trust. Because of considerable traffic load and computing cost, this paper only considers the direct trust.For routing scheme, perceptive ACO is used to find and assess routes. Each nodes sends perceptive forward-ants to find routes to the Sink, where the cross-layer perception [22] is introduced to support route selection. When an ant hops from node i to node j on the way to source, it firstly senses its own load and the trust with respect to node i. Then, B-iTRS assesses the trust, load, and availability of route j
,
i
,
…
,
Sink. If the availability value of the route is less than a specific threshold TH
A
,
Lower, B-iTRS kills the backward-ant and discards the route. Otherwise, the route is inserted in the proper position of the route table of node j according to the availability value. The process is repeated until the backward-ant reaches source. When route failures happen, route maintenance is triggered to recover the route rapidly.


### 2.3. Trust Assessment Model

In B-iTRS, each node monitors its neighbors’ behaviors in real time and then analyzes them to get their trust weight, since analyzing node’s behavior can show whether the node is selfish, is acting like a black hole, is carrying out a modification or fabrication attack, is inducing latency delays by delaying the retransmission of the packet [23], and so forth. In order to alleviate the calculating burden, we do not adjust the trust weight of behaviors automatically but adopt the prior trust weight which is determined by offline decision.If a new neighborj of node i arises, node i endows it with initial trust value TRUST
i
,
j, which is determined by(1)
TRUST
i
,
j
=
1
n
∑
k
=
1
n
trust
i
,
k
,
if
n
≥
1
trust
c
,
if
n
=
0
,where trust
i
,
k is the trust value of node i with respect to the kth neighbor, n is the number of neighbors, and trust
c is a constant.Once nodei obtains a specific behavior about neighbor j by monitoring it, node i analyzes the behavior based on prior knowledge to identify the behavior of neighbor j and get the trust weight of the behavior and then updates the trust value of node i with respect to neighbor j by(2)
trust
i
,
j
(
t
+
1
)
=
TRUST
i
,
j
+
weight
,
if
t
=
1
trust
i
,
j
(
t
)
+
weight
,
if
t
>
1
,where weight is the trust weight of the behavior identified, trust
i
,
j
(
t
) is the trust value after the tth updating, and trust
i
,
j
(
t
+
1
) is the trust value after the (
t
+
1
)th updating.Once nodei receives the feedback about its neighbors from the Sink node, node i analyzes feedback information to modify the trusts of its neighbors by(3)
trust
i
,
j
new
=
trust
i
,
j
old
+
weight
j
,where trust
i
,
j
(
new
) is the trust value after updating, trust
i
,
j
(
old
) is the trust value before updating, and weight
(
j
) is the trust weight of node j based on the feedback of Sink node, where weight
(
j
) is standardized to the same range of trust
i
,
j.


### 2.4. Perceptive ACO Path-Finding Model

We improve the traditional ants to perceptive ants based on ACO to obtain path-finding and path-assessment models by introducing cross-layer perception [22]. For MWSNs expressed by graph G
=
(
V
,
E
), each edge e
(
i
,
j
)
∈
E has a variable artificial pheromone τ
(
i
,
j
), which is an indication of usage of the edge and is modified by perceptive ants when they hop from node i to node j.A perceptive ant located in nodei uses τ
(
i
,
j
) of node j to compute the probability of node j as next hop:(4)
p
i
j
=
τ
(
i
,
j
)
∑
j
∈
N
i
‍
τ
(
i
,
j
)
,
j
∈
N
i
,where p
i
j satisfies ∑
j
∈
N
i
‍
p
i
j
=
1 and N
i is the set of one-hop neighbors of node i.Once the perceptive ant moves from nodei to node j, it senses two metrics L
j and trust
i
,
j to measure the link status, where L
j denotes the length of transmission waiting queue of node j and trust
i
,
j denotes the trust value of node i with respect to the j. If it is the (
t
+
1
)th time that perceptive ants pass by the edge e
(
i
,
j
), depositing pheromone on e
(
i
,
j
) and evaporating pheromone from e
(
k
,
j
), k
≠
i, respectively, are followed by(5)
τ
t
+
1
i
,
j
=
τ
t
(
i
,
j
)
+
L
0
·
trust
i
,
j
L
j
·
T
0
·
Δ
τ
,
if
L
0
·
trust
i
,
j
L
j
·
T
0
≤
K
0
τ
t
(
i
,
j
)
+
K
0
·
Δ
τ
,
otherwise
,
(6)
τ
t
+
1
k
,
j
=
(
1
-
L
j
·
T
0
L
0
·
trust
i
,
j
)
·
τ
t
(
k
,
j
)
,
L
j
·
T
0
L
0
·
trust
i
,
j
∈
[
0,1
]
(
1
-
U
0
)
·
τ
t
(
k
,
j
)
,
otherwise
,where L
0, T
0, K
0, Δ
τ, and U
0 are constants and U
0
∈
(
0,1
). τ
t
(
i
,
j
) denotes the pheromone on edge e
(
i
,
j
) after the tth depositing or evaporating. Equations (4), (5), and (6) are used to find routes in B-iTRS.When a backward perceptive ant moves from nodei to node j on the way to source, the link quality and link load are assessed with the metrics, respectively, following(7)
L
_
R
d
j
=
L
_
R
d
i
+
T
0
,
if
trust
i
j
>
T
0
L
_
R
d
i
+
T
1
,
if
trust
i
j
<
T
1
L
_
R
d
i
+
trust
i
j
,
otherwise
,
(8)
L
_
L
d
j
=
L
_
L
d
i
+
L
0
,
if
L
j
>
L
0
L
_
L
d
i
+
L
j
,
if
L
j
≤
L
0
,where T
0, T
1, and L
0 are constants and L
_
R
d
j and L
_
L
d
j denote the link reliability and link load from node d to node j, respectively. Equations (7) and (8) are used to assess the discovered routes in B-iTRS.


### 2.5.  PAO Path-Assessment Model

In this section, we improve PAO to acquire PAO path-assessment model. From [12–15], the flux through each plasmodial tube follows(9)
Q
i
j
=
C
i
j
(
P
i
-
P
j
)
D
i
j
=
C
i
j
·
Δ
P
i
j
D
i
j
,where Δ
P
i
j
=
P
i
-
P
j is the pressure difference of two ends of the tube, C
i
j is a measure of the conductivity of the tube, and D
i
j is the length of the tube. Physarum forages for distributed food sources through adapting its plasmodium to change the flux of each tube, which is described by(10)
d
d
t
C
i
j
=
φ
Q
i
j
-
δ
C
i
j
,where δ is a decay rate of the tube and φ
(
·
) is a monotonically increasing continuous function satisfying φ
(
0
)
=
0.Since PAO comes from fluid dynamics and cannot be directly used in MANETs, we replaceC
i
j with the link trust trust
i
j, D
i
j with H
i
j which denotes the hops from node i to node j, and Δ
P
i
j with Δ
L
i
j
=
L
i
-
L
j. Thus, we obtain(11)
Q
i
j
=
C
i
j
·
Δ
P
i
j
D
i
j
=
trust
i
j
·
Δ
L
i
j
H
i
j
,
(12)
d
d
t
Δ
trust
i
j
=
φ
Q
-
δ
Δ
trust
i
j
=
trust
i
j
·
Δ
L
i
j
H
i
j
μ
-
δ
Δ
trust
i
j
,where Q
i
j is the virtual flux of communication through the wireless link e
(
i
,
j
), δ is the rate of trust changing, and μ is a constant satisfying μ
>
0. Equation (12) is used to select the optimal route in B-iTRS.


## 2.1. Typical WSNs Scenario

This paper considers large multihop WSNs whose nodes are distributed randomly in a two-dimensional space. We assume that (1) each node has a single channel, (2) the interference rangeR is equal to the transmission range, and (3) all communication links are bidirectional.Based on the assumptions, WSNs can be abstracted as a graphG
=
(
V
,
E
), where V is the set of all nodes and E is the set of all edges. Each edge e
(
i
,
j
)
∈
E denotes that the two nodes are located within each other’s transmission range.In some circumstances, theSink node moves along a certain orbit in the field and broadcasts periodically its current positions to improve the efficiency of collected data. An example of such WSNs’ topology is shown in Figure 1.Figure 1
An example of MWSNs’ topology.


## 2.2. The Framework of B-iTRS

Based on the above discussion, Figure2 illustrates the design of the proposed B-iTRS framework which consists of trust assessment and routing scheme.Figure 2
B-iTRS framework.For trust assessment, each node monitors its neighbors’ behavior in real time and receives the feedback from theSink node. Based on the neighbors’ behavior and feedback information, B-iTRS assesses trusts of neighbors; that is, the trust of corresponding neighbor is added by a different positive, negative, or zero value according to the behavior’s weight or Sink’s feedback. In most cases, the trust consists of two sections—direct trust and indirect trust. Because of considerable traffic load and computing cost, this paper only considers the direct trust.For routing scheme, perceptive ACO is used to find and assess routes. Each nodes sends perceptive forward-ants to find routes to the Sink, where the cross-layer perception [22] is introduced to support route selection. When an ant hops from node i to node j on the way to source, it firstly senses its own load and the trust with respect to node i. Then, B-iTRS assesses the trust, load, and availability of route j
,
i
,
…
,
Sink. If the availability value of the route is less than a specific threshold TH
A
,
Lower, B-iTRS kills the backward-ant and discards the route. Otherwise, the route is inserted in the proper position of the route table of node j according to the availability value. The process is repeated until the backward-ant reaches source. When route failures happen, route maintenance is triggered to recover the route rapidly.


## 2.3. Trust Assessment Model

In B-iTRS, each node monitors its neighbors’ behaviors in real time and then analyzes them to get their trust weight, since analyzing node’s behavior can show whether the node is selfish, is acting like a black hole, is carrying out a modification or fabrication attack, is inducing latency delays by delaying the retransmission of the packet [23], and so forth. In order to alleviate the calculating burden, we do not adjust the trust weight of behaviors automatically but adopt the prior trust weight which is determined by offline decision.If a new neighborj of node i arises, node i endows it with initial trust value TRUST
i
,
j, which is determined by(1)
TRUST
i
,
j
=
1
n
∑
k
=
1
n
trust
i
,
k
,
if
n
≥
1
trust
c
,
if
n
=
0
,where trust
i
,
k is the trust value of node i with respect to the kth neighbor, n is the number of neighbors, and trust
c is a constant.Once nodei obtains a specific behavior about neighbor j by monitoring it, node i analyzes the behavior based on prior knowledge to identify the behavior of neighbor j and get the trust weight of the behavior and then updates the trust value of node i with respect to neighbor j by(2)
trust
i
,
j
(
t
+
1
)
=
TRUST
i
,
j
+
weight
,
if
t
=
1
trust
i
,
j
(
t
)
+
weight
,
if
t
>
1
,where weight is the trust weight of the behavior identified, trust
i
,
j
(
t
) is the trust value after the tth updating, and trust
i
,
j
(
t
+
1
) is the trust value after the (
t
+
1
)th updating.Once nodei receives the feedback about its neighbors from the Sink node, node i analyzes feedback information to modify the trusts of its neighbors by(3)
trust
i
,
j
new
=
trust
i
,
j
old
+
weight
j
,where trust
i
,
j
(
new
) is the trust value after updating, trust
i
,
j
(
old
) is the trust value before updating, and weight
(
j
) is the trust weight of node j based on the feedback of Sink node, where weight
(
j
) is standardized to the same range of trust
i
,
j.


## 2.4. Perceptive ACO Path-Finding Model

We improve the traditional ants to perceptive ants based on ACO to obtain path-finding and path-assessment models by introducing cross-layer perception [22]. For MWSNs expressed by graph G
=
(
V
,
E
), each edge e
(
i
,
j
)
∈
E has a variable artificial pheromone τ
(
i
,
j
), which is an indication of usage of the edge and is modified by perceptive ants when they hop from node i to node j.A perceptive ant located in nodei uses τ
(
i
,
j
) of node j to compute the probability of node j as next hop:(4)
p
i
j
=
τ
(
i
,
j
)
∑
j
∈
N
i
‍
τ
(
i
,
j
)
,
j
∈
N
i
,where p
i
j satisfies ∑
j
∈
N
i
‍
p
i
j
=
1 and N
i is the set of one-hop neighbors of node i.Once the perceptive ant moves from nodei to node j, it senses two metrics L
j and trust
i
,
j to measure the link status, where L
j denotes the length of transmission waiting queue of node j and trust
i
,
j denotes the trust value of node i with respect to the j. If it is the (
t
+
1
)th time that perceptive ants pass by the edge e
(
i
,
j
), depositing pheromone on e
(
i
,
j
) and evaporating pheromone from e
(
k
,
j
), k
≠
i, respectively, are followed by(5)
τ
t
+
1
i
,
j
=
τ
t
(
i
,
j
)
+
L
0
·
trust
i
,
j
L
j
·
T
0
·
Δ
τ
,
if
L
0
·
trust
i
,
j
L
j
·
T
0
≤
K
0
τ
t
(
i
,
j
)
+
K
0
·
Δ
τ
,
otherwise
,
(6)
τ
t
+
1
k
,
j
=
(
1
-
L
j
·
T
0
L
0
·
trust
i
,
j
)
·
τ
t
(
k
,
j
)
,
L
j
·
T
0
L
0
·
trust
i
,
j
∈
[
0,1
]
(
1
-
U
0
)
·
τ
t
(
k
,
j
)
,
otherwise
,where L
0, T
0, K
0, Δ
τ, and U
0 are constants and U
0
∈
(
0,1
). τ
t
(
i
,
j
) denotes the pheromone on edge e
(
i
,
j
) after the tth depositing or evaporating. Equations (4), (5), and (6) are used to find routes in B-iTRS.When a backward perceptive ant moves from nodei to node j on the way to source, the link quality and link load are assessed with the metrics, respectively, following(7)
L
_
R
d
j
=
L
_
R
d
i
+
T
0
,
if
trust
i
j
>
T
0
L
_
R
d
i
+
T
1
,
if
trust
i
j
<
T
1
L
_
R
d
i
+
trust
i
j
,
otherwise
,
(8)
L
_
L
d
j
=
L
_
L
d
i
+
L
0
,
if
L
j
>
L
0
L
_
L
d
i
+
L
j
,
if
L
j
≤
L
0
,where T
0, T
1, and L
0 are constants and L
_
R
d
j and L
_
L
d
j denote the link reliability and link load from node d to node j, respectively. Equations (7) and (8) are used to assess the discovered routes in B-iTRS.


## 2.5.  PAO Path-Assessment Model

In this section, we improve PAO to acquire PAO path-assessment model. From [12–15], the flux through each plasmodial tube follows(9)
Q
i
j
=
C
i
j
(
P
i
-
P
j
)
D
i
j
=
C
i
j
·
Δ
P
i
j
D
i
j
,where Δ
P
i
j
=
P
i
-
P
j is the pressure difference of two ends of the tube, C
i
j is a measure of the conductivity of the tube, and D
i
j is the length of the tube. Physarum forages for distributed food sources through adapting its plasmodium to change the flux of each tube, which is described by(10)
d
d
t
C
i
j
=
φ
Q
i
j
-
δ
C
i
j
,where δ is a decay rate of the tube and φ
(
·
) is a monotonically increasing continuous function satisfying φ
(
0
)
=
0.Since PAO comes from fluid dynamics and cannot be directly used in MANETs, we replaceC
i
j with the link trust trust
i
j, D
i
j with H
i
j which denotes the hops from node i to node j, and Δ
P
i
j with Δ
L
i
j
=
L
i
-
L
j. Thus, we obtain(11)
Q
i
j
=
C
i
j
·
Δ
P
i
j
D
i
j
=
trust
i
j
·
Δ
L
i
j
H
i
j
,
(12)
d
d
t
Δ
trust
i
j
=
φ
Q
-
δ
Δ
trust
i
j
=
trust
i
j
·
Δ
L
i
j
H
i
j
μ
-
δ
Δ
trust
i
j
,where Q
i
j is the virtual flux of communication through the wireless link e
(
i
,
j
), δ is the rate of trust changing, and μ is a constant satisfying μ
>
0. Equation (12) is used to select the optimal route in B-iTRS.


## 3. B-iTRS Protocol

The B-iTRS consists of trust assessment and routing scheme. The trust assessment is running in each node independently to acquire its neighbors’ trusts. The route scheme works based on PACO and PAO. The module structure is shown in Figure3.Figure 3
B-iTRS module structure.


### 3.1. Data Structures in B-iTRS

There are mainly three kinds of data structures in B-iTRS—perceptive ant structure, route table, and pheromone table. The structure of perceptive ant is seven-tupleSource
,
Sequence
_
No
,
Type
,
Hops
,
Path
,
Link
_
Reliability
,
Link
_
Load. Source field stores the source node address. Sequence
_
No field stores the sequence number tagged to each ant. Source and destination nodes incrementally generate a Sequence
_
No each time forward- or backward-ants are sent out. The pair Source
,
Sequence
_
No can uniquely identify the ants’ generation. Type field indicates the ants’ type. There are four types of ants: the first is perceptive forward-ant used for finding routes; the second is perceptive backward-ant used for returning routes to source; the third is notification ant used for sending notification to other nodes; and the last is error ant used for sending error to other nodes. For forward-ant, the Hops field indicates the maximum hops that one ant can move. For backward-ant, the Hops field stores the hops of a route.  Path field stores the sequence of nodes from source to destination. Link
_
Reliability and Link
_
Load measure the link reliability and link load of the discovered routes, respectively.Each node needs to maintain a route table whose structure is six-tupleSource
,
Hops
,
Link
_
Reliability
,
Link
_
Load
,
Path
,
Sequence
_
No. Hops field stores the hops from source to destination. The structure of pheromone table is triple i
,
j
,
Value which expresses the pheromone of link e
(
i
,
j
)   is Value.


### 3.2. Route Discovery

When a sources wishes to send data packet to Sink, it looks up its route table firstly. If only one route is found, the route discovery process is over. If multiple routes are found, the route selection is performed according to (12).If there is no route from sources to Sink in route table, the route discovery will be triggered. The node s sets a timeout T
0 and sends perceptive forward-ants to find new routes, where Hops fields are set to the allowable maximum value, which means each perceptive forward-ant will die only to find Sink, a node with a route to Sink, or move limited maximum hops.When a forward-ant reaches an intermediate node, it checks whether unexpired routes to destinationSink already exist in the route table firstly. If there are one or more unexpired routes, the optimal route to Sink is selected according to (9), and a corresponding perceptive backward-ant is generated and sent back to source along the discovered path. Otherwise, the transition probability, pheromone depositing, and evaporating are calculated following (4), (5), and (6), respectively. Once a perceptive forward-ant reaches Sink, a corresponding backward-ant is generated and sent back to source along the discovered path.When the perceptive backward-ant reaches each intermediate nodei on the way to source, B-iTRS will perform two operations. Firstly, the pheromone depositing, pheromone evaporating, link quality, and link load are calculated following (5), (6), (7), and (8), respectively. Secondly, the new route will be added to the route table of node i. After the perceptive backward-ant reaches source s, the new route will be added to route table.IfT
0 is time out and no route is found, the route discovery fails. If only one route is found, the route discovery process is over. If multiple routes are found, (9) is used to determine the optimal route.


### 3.3. Route Maintenance

Route maintenance handles routing failures especially caused by node mobility or breakdown which is very common in MWSNs. If the route failures happen, the upstream node of the broken link will trigger a repair procedure to find new routes toSink, which is similar to the route discovery. If an alternative route is found, the transmission is going on and a notification ant is sent to source to update route table of each node on the path. If no route is found, an error ant will be sent to source as well as updating route table of each node on the path. After receiving an error ant, if the source still needs to transmit the data packet, it can select the backup route or other unexpired routes found in route table and even initiate a new procedure of route discovery among zones.


## 3.1. Data Structures in B-iTRS

There are mainly three kinds of data structures in B-iTRS—perceptive ant structure, route table, and pheromone table. The structure of perceptive ant is seven-tupleSource
,
Sequence
_
No
,
Type
,
Hops
,
Path
,
Link
_
Reliability
,
Link
_
Load. Source field stores the source node address. Sequence
_
No field stores the sequence number tagged to each ant. Source and destination nodes incrementally generate a Sequence
_
No each time forward- or backward-ants are sent out. The pair Source
,
Sequence
_
No can uniquely identify the ants’ generation. Type field indicates the ants’ type. There are four types of ants: the first is perceptive forward-ant used for finding routes; the second is perceptive backward-ant used for returning routes to source; the third is notification ant used for sending notification to other nodes; and the last is error ant used for sending error to other nodes. For forward-ant, the Hops field indicates the maximum hops that one ant can move. For backward-ant, the Hops field stores the hops of a route.  Path field stores the sequence of nodes from source to destination. Link
_
Reliability and Link
_
Load measure the link reliability and link load of the discovered routes, respectively.Each node needs to maintain a route table whose structure is six-tupleSource
,
Hops
,
Link
_
Reliability
,
Link
_
Load
,
Path
,
Sequence
_
No. Hops field stores the hops from source to destination. The structure of pheromone table is triple i
,
j
,
Value which expresses the pheromone of link e
(
i
,
j
)   is Value.


## 3.2. Route Discovery

When a sources wishes to send data packet to Sink, it looks up its route table firstly. If only one route is found, the route discovery process is over. If multiple routes are found, the route selection is performed according to (12).If there is no route from sources to Sink in route table, the route discovery will be triggered. The node s sets a timeout T
0 and sends perceptive forward-ants to find new routes, where Hops fields are set to the allowable maximum value, which means each perceptive forward-ant will die only to find Sink, a node with a route to Sink, or move limited maximum hops.When a forward-ant reaches an intermediate node, it checks whether unexpired routes to destinationSink already exist in the route table firstly. If there are one or more unexpired routes, the optimal route to Sink is selected according to (9), and a corresponding perceptive backward-ant is generated and sent back to source along the discovered path. Otherwise, the transition probability, pheromone depositing, and evaporating are calculated following (4), (5), and (6), respectively. Once a perceptive forward-ant reaches Sink, a corresponding backward-ant is generated and sent back to source along the discovered path.When the perceptive backward-ant reaches each intermediate nodei on the way to source, B-iTRS will perform two operations. Firstly, the pheromone depositing, pheromone evaporating, link quality, and link load are calculated following (5), (6), (7), and (8), respectively. Secondly, the new route will be added to the route table of node i. After the perceptive backward-ant reaches source s, the new route will be added to route table.IfT
0 is time out and no route is found, the route discovery fails. If only one route is found, the route discovery process is over. If multiple routes are found, (9) is used to determine the optimal route.


## 3.3. Route Maintenance

Route maintenance handles routing failures especially caused by node mobility or breakdown which is very common in MWSNs. If the route failures happen, the upstream node of the broken link will trigger a repair procedure to find new routes toSink, which is similar to the route discovery. If an alternative route is found, the transmission is going on and a notification ant is sent to source to update route table of each node on the path. If no route is found, an error ant will be sent to source as well as updating route table of each node on the path. After receiving an error ant, if the source still needs to transmit the data packet, it can select the backup route or other unexpired routes found in route table and even initiate a new procedure of route discovery among zones.


## 4. B-iTRS Analysis

In this section, we analyze the feasibility of B-iTRS by mathematical theoretical analysis. We study the cases in which two nodes connected to the same node compete to be the next hop, as shown in Figure4.Figure 4
B-iTRS module structure.There are two nodesi and j
1. For simplicity, we hereafter replace D
i
j
1, D
i
j
2, Q
i
j
1, Q
i
j
2, Δ
P
i
j
1, and Δ
P
i
j
2 by D
1, D
2, Q
1, Q
2, Δ
P
1, and Δ
P
2, respectively. From (9) and (10), the virtual fluxes along each path are calculated as(13)
Q
1
=
Δ
P
1
/
D
1
Δ
P
1
/
D
1
+
Δ
P
2
/
D
2
,
Q
2
=
Δ
P
2
/
D
2
Δ
P
1
/
D
1
+
Δ
P
2
/
D
2
.SinceQ
1 and Q
2 are nonnegative, adaptation equation (9) becomes(14)
d
d
t
Δ
P
1
=
φ
Q
1
-
δ
·
Δ
P
1
,
d
d
t
Δ
P
2
=
φ
Q
2
-
δ
·
Δ
P
2
.Settingφ
Q
=
Q
μ, (
d
/
d
t
)
Δ
P
1
=
0, and (
d
/
d
t
)
Δ
P
2
=
0, we have(15)
Δ
P
1
/
D
1
Δ
P
1
/
D
1
+
Δ
P
2
/
D
2
μ
=
δ
·
Δ
P
1
,
Δ
P
2
/
D
2
Δ
P
1
/
D
1
+
Δ
P
2
/
D
2
μ
=
δ
·
Δ
P
2
.After some calculations, we obtain(16)
Δ
P
1
=
1
δ
1
1
+
D
1
/
D
2
1
/
1
-
μ
μ
,
Δ
P
2
=
1
δ
1
1
+
D
2
/
D
1
1
/
1
-
μ
μ
.From (10), if we suppose Δ
L
i
j is constant and use trust
i
j replacing C
i
j, H
i
j replacing D
i
j, and Δ
L
i
j replacing D
i
j, we obtain(17)
Δ
trust
1
=
1
δ
1
1
+
H
1
/
H
2
1
/
1
-
μ
μ
,
Δ
trust
2
=
1
δ
1
1
+
H
2
/
H
1
1
/
1
-
μ
μ
.Namely, if we supposeΔ
L
i
j is constant, there is an equilibrium point given by (
Δ
trust
1
,
Δ
trust
2
). If we suppose trust
i
j is constant, there is an equilibrium point given by (
Δ
L
1
,
Δ
L
2
). If both Δ
L
i
j and trust
i
j are not constants, there is a more complicated equilibrium point. Therefore, the B-iTRS is always convergent, which is very important for a routing protocol.


## 5. Simulation Results and Analysis

We analyze B-iTRS in Network Simulator ns-2 (version 2.34) and compare its simulation results with those of AODV, AntHocNet, and TGRP. In the base simulation scenario, theSink node is placed in the center of a rectangular area of 600 m × 600 m, and 100 nodes are uniformly placed in the area and move according to the random way mobility model (RWP) [24]. The Sink moves along an ellipse orbit in the center of the rectangular area. It broadcasts periodically its current positions, as shown in Figure 1. In the model, each node moves towards a random direction at a speed uniformly distributed [0, 10 m/s]. Once a node reaches a target position, it pauses for resting 2 s to send or transmit data packet and then moves forward in the same way. The data traffic is generated by 20 constant bit rate (CBR) sources with sending rates of single 64 bytes every 2 s. The radio propagation range and data rate are set to 50 m and 2 Mbit/s, respectively. The parameters are shown in Table 1.Table 1
Simulation parameters.
Parameters
Value
Simulation range
600 m × 600 m
Node’s number
100
Max speed
10 m/s
Min speed
0 m/s
Propagation range
50 m
Data rate
2 Mbit/s
Node moving time
3 s
Node rest time
2 s
Simulation time
600 sThe simulation is run for 600 s each time. We run each simulation scenario 10 times to acquire the average values of results and compare them. The results and analysis are shown as follows.Figure5 shows end-to-end delay versus number of nodes when the ratio of malicious nodes is 8%. Since AODV is on-demand protocol, its end-to-end delay is the worst of the four protocols. Because AntHocNet can proactively test existing paths and explore new ones during the course of communication session, its end-to-end delay is better than that of AODV. Since both B-iTRS and TGRP can deal with malicious nodes, their end-to-end delays are much better than those of AODV and AntHocNet.Figure 5
Delay versus number of nodes.Figure6 shows end-to-end delivery ratio versus number of nodes when the ratio of malicious nodes is 8%. In the first stage, each delivery ratio increases rapidly with the increase of the number of nodes. After the number of nodes reaches a specific value, the delivery ratio will keep a stable value approximately. Since B-iTRS and TGRP adopt security mechanism, their delivery ratios are similar and greater than those of AODV and AntHoc.Figure 6
Delivery ratio versus number of nodes.Figure7 shows overhead versus number of nodes when the ratio of malicious nodes is 8%. Since AODV is a purely reactive and AntHocNet is hybrid, their control overheads are the least and the second least in the four protocols, respectively. However, their control overheads increase rapidly with the increase of the number of nodes. Since B-iTRS needs to deal with neighbors’ trusts and Sink feedback, its control overhead is greater than that of TGRP which only needs to deal with trust.Figure 7
Overhead versus number of nodes.Figure8 shows end-to-end delay versus ratio of malicious nodes. Since AODV and AntHocNet cannot deal with attacks from malicious nodes, their end-to-end delay increases with the increase of malicious nodes, and the increment is larger and larger. Since both B-iTRS and TGRP can deal with malicious nodes, their end-to-end delays are similar.Figure 8
Delay versus ratio of malicious nodes.Figure9 shows delivery ratio versus ratio of malicious nodes. Each delivery ratio decreases gradually with the increase of the ratio of malicious nodes, and the decrement is greater and greater. In the first stage, each delivery ratio decreases little with the increase of the ratio of malicious nodes. After the ratio of malicious nodes reaches a specific value, the two delivery ratios will decrease rapidly. Since both B-iTRS and TGRP adopt security mechanism, their delivery ratios are similar and decrease slowly.Figure 9
Delivery ratio versus ratio of malicious nodes.


## 6. Conclusion and Future Work

In this paper, we present B-iTRS, a trusted routing scheme based on bio-inspired method. B-iTRS uses perceptive ants to reactively maintain the route table, where the link status metrics are sensed by perceptive ants to support path finding. Then, B-iTRS uses PAO to select the optimal route from multiple routes. In fact, B-iTRS is devoted to combining the advantages of both ACO and PAO to improve the effective performance, which is verified by simulation results. The proposed scheme can be used in both WSNs and MANETs scenario. In future work, we consider extending link status metrics (e.g., interference, energy) and introducing actual mobility model of nodes into B-iTRS to make it fit in with real WSNs environment.



---

*Source: 156843-2015-08-02.xml*