# ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol

Manali Chakraborty, Nabendu Chaki

► To cite this version:

Manali Chakraborty, Nabendu Chaki. ETSeM: A Energy-Aware, Trust-Based, Selective Multi-path Routing Protocol. 11th International Conference on Computer Information Systems and Industrial Management (CISIM), Sep 2012, Venice, Italy. pp.351-360, 10.1007/978-3-642-33260-9_30. hal-01551733

HAL Id: hal-01551733

https://inria.hal.science/hal-01551733

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ETSeM: A Energy-aware, Trust-based, Selective Multi-path Routing Protocol

Manali Chakraborty¹, Nabendu Chaki²

Department of Computer Science & Engineering, University of Calcutta, India
92 APC Road, Kolkata 700009, India

¹manali4mkolkata@gmail.com, ²nabendu@ieee.org

**Abstract.** Multi-path routing protocols are used for different types of wireless networks primarily to enhance reliability of packet delivery. The frequency of route discovery is also less for multi-path routing protocols as these are more fault-tolerant. However, the overhead of route discovery in terms of congestion and energy requirement is much higher for multi-path routing as compared to single-path routing. In this paper, a restricted multi-path routing algorithm has been proposed that dynamically selects the number of neighboring nodes through which packets would be transmitted. The selection and degree of multi-path depends on multiple factors like the remaining energy of the node, trust value of that node, number of already existing paths through that node etc. The protocol is designed in such a way, that the burden of routing is lower on the weaker nodes and the nodes with more resources will have to perform more tasks. Consequently, the lifetime of the network would be higher as compared to multi-path routing protocols. Besides, the data reception rate, defined as the ratio of the total number of packets received by the sink node and the total number of packets sent by the source node, is much higher for the proposed protocol than any single path routing. While the routing load is balanced among the nodes, the multiple routes also increase the reliability.

**Keywords:** Selective multi-path routing, back-up path, fault tolerance, trust

## 1 Introduction

The main objective of different types of wireless networks, such as Sensor networks, MANETs, Wireless Mesh Networks is to transfer data from one node to another. This communication must be reliable. In order to ensure reliability, multi-path routing protocols can be utilized [5]. Due to the unpredictability of the environment, and unreliability of wireless medium, a single path routing is more prone to failure in a wireless network. This makes the protocol unreliable [7]. On the other hand, Multi-path routing can easily recover path failure by utilizing alternative routes. The frequency of route discovery is also less in a network with multi-path routing, since the network can tolerate one or few link failures, and still continue working with alternative paths
[8]. It also provides the benefits of fault tolerance, load balancing and bandwidth ag-
gregation etc [7].

In spite of such benefits, the overhead of route discovery and maintenance is often
higher in multi-path routing than single-path routing. In this work, the proposed selec-
tive multipath routing protocol aims to combine the benefits of both the methods.
Besides, it is expected to offer more efficient load balancing. The word selective
means that every node has the capability to select a subset from its neighboring nodes
through which it can transmit. The selection is based on the remaining energy, and
trust value of that node as well as on issues like the number of existing paths through
the node, etc.

The novelty in route selection for the proposed protocol is that the source and the
intermediate nodes may choose zero, one or more nodes for the next hop transmission
dynamically depending on the current status. As for example, just like single-path
routing there could be only one selected node for the next hop, if the communication
is reliable, trusted and meets other criteria. An intermediate may not forward the
RREQ packet at all depending on the status of the factors mentioned. However, de-
pending on the status, an intermediate may decide to broadcast to its entire neighbor-
hood too. The selection is run-time and dynamic.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Selection of next-hop for Routing</figcaption></figure>

In figure 1, for example, source node S transmits to nodes A, C and not to B. Node A transmits to F only, while C transmits to all its neighbors A, B, E and F. It is assumed that initially all the nodes are connected through bi-directional channels as shown by dotted lines. The directed continual lines are the selected links that eventually sets up routes up to D. The routes that are set for the selection in figure 1 is shown in figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Multi-path Routing from S to D Routing</figcaption></figure>
In the example, there are two or more alternate paths from the start node S and each intermediate node to destination D, except node J. As evident from this example, all the routes from S to D must be routed through J. There are several alternate routes to reach J from S. However, there is only one selected path between nodes J and the next hop destination L. This is in spite of the fact that both K and L are neighbors of J in the direction of destination D. The proposed protocol permits this. This depends on the reliability of the link J-L and the trust values, energy level, etc. for the two nodes. The underlying premise is that multipath routing may not be needed at all the steps. Multiple next-hop nodes have been used for other intermediate nodes depending on the status. The path selection is dynamically decided in a reactive manner.

The rest of the paper is organized as follows: section 2 describes related works, section 3 describes the routing process, the performance analysis of this algorithm is presented in section 4, the simulation results are presented in section 5 and section 6 concludes this work, with acknowledgement in section 7.

## 2 State of the art Review

A brief review of existing Multi-path Routing algorithms in different Wireless Networks is presented in this section. The route discovery and selection of multiple routes is one of the fundamental issues in multi-path routing. Two broad approaches are suggested for this purpose; node-disjoint and link disjoint [7]. In different node-disjointed approaches, multiple routes are created with an assurance that no common node can exist between them. In the link-disjointed methodologies, common nodes may exist between several routes, but links between two nodes do not overlap [5].

Multi-path routing algorithm is of three types. In the first method a back up path is used only when the primary path between a pair of nodes is down. The back up path is set up simultaneously with the primary path. In the second method, multiple paths are used simultaneously to balance the load of the primary path. Initially the primary path is used for data transmission, but when it has heavy traffic, the other paths also participate in packet transmission to reduce the burden from that primary path. In the third method, every node disjoint path between a pair of nodes is used to increase the end to end performance by transmitting data among several paths [1].

A meshed multi-path routing M-MPR [2] was proposed to provide mesh connectivity among the nodes. It also uses selective forwarding of packets among multiple paths. The selection is based on the condition of downstream forwarding nodes. End to end forward error checking (FEC) is used to reduce the overhead of retransmitting the packets based on acknowledgement. Besides being energy efficient, higher throughput achievement has been claimed in [2] as compared to any other node disjoint multi-path routing protocol.

Another multi-path [1] routing for wireless networks combines the idea of clustering and multi-path routing together. Clustering is used to speed up the routing by structuring the network nodes hierarchically, and multi-path routing is used to provide better
end to end performance and throughput. The solution in [1], according to its authors, is less prone to interference, than conventional multi-path routing. It is also quite simple as each path in the CBMPR just passes through the heads of clusters, resulting in a simple cluster level hop-by-hop routing. A reliable and hybrid multi-path routing, RHMR for MANET was proposed in [5]. It uses a proactive-like routing for route discovery and reactive routing for route recovery and maintenance.

LIEMRO [6] is another node-disjoint multi-path routing based on event based sensor network to improve QoS in the terms of data reception rate, lifetime, and latency. The primary path from source node to sink node is consist of the nodes with minimum packet transmission cost at each step. Similarly, the second path is established using the second best nodes at each step. Extra routes are only established if they don't decrease data reception rate at the sink node.

MHRP [3] is a Hybrid Multi-path Routing protocol that was designed to properly exploit the inherent hybrid architecture of WMNs. It uses Proactive Routing protocol in mesh routers and reactive routing in mesh clients. By efficiently using the resource-ful router nodes in route discovery and security mechanism, it reduces overhead from client nodes, which are mobile and have fewer resources.

Another multi-path routing for WMNs was proposed in MRATP [4]. It uses a traffic prediction model based on wavelet-neural network. The main idea of this paper is to set up one primary and some backup paths between a pair of nodes. The primary path is used to transmit the data, until any node on that path generates a congestion signal. Then the back-up paths is used to balance the load in the network. It is claimed that [4] reduces end to end delay and balances the load of the whole network efficiently.

# 3 The Proposed Algorithm

Wireless Ad Hoc networks were developed for reliable data communication and load balancing. Multiple path communication is the basic need behind these two objectives. If these attributes of Wireless networks are not utilized properly; one cannot achieve the best out of this network paradigm. Moreover, multi-path routing assists in achieving security in routing protocols. Most of the proposed schemes are not able to minimize the overhead of storing extra routes, through the life time and the maintenance cost of those routes. These limitations urge a need of a routing protocol which can manipulate the degree of multi-paths according to the energy level, number of paths through a node and trust value of a node.

In this section, the working of the proposed algorithm has been described. There are mainly two parts, 1. Neighbor Discovery, and 2. Route Establishment. The working of this algorithm is based on the following principles:

* Every node has to maintain two arrays; HEALTH and TRUST and two variables; ENERGY and PATH.

* Every node maintains the health information about its 1 hop neighbors.
* HEALTH is a linear function of the remaining energy of that node, number of paths already exists through the node and trust value of the node.

* Every node has to send its energy and path metrics to its 1 hop neighbors.

## 3.1 Neighbor Discovery

At first every node obtains some information about its neighbors. Each node broadcasts a HELLO packet to identify its neighbors within one-hop distance. On receiving the HELLO packets, each node replies with an ACK packet, containing the remaining energy of that node, the value of a counter variable PATH, which denotes the number of paths already existing through that node and the trust value of that node, given by its neighbors. We assume that, every node send its information reliably. After that, every node calculates the value of the variable HEALTH of its neighbors in terms of their remaining energy, number of paths already passing through the node and the trust value of that node.

$$HEALTH=f(remaining\-energy, trust, PATH)$$

## 3.2 Route Establishment

<figure><img src="image_4.png" /><figcaption>Fig. 3. Selection of route depending on HEALTH</figcaption></figure>
Figure 3 shows the route establishment process for this algorithm. To establish a route between a source node and a sink node, the source node sends a ROUTE_REQUEST packet towards the sink node. Each node checks for the healthiest node among its neighbors. If the value of the variable HEALTH for the healthiest node is greater than 90%, then it forwards the ROUTE_REQUEST packet through that node only. If the value of HEALTH is in the range of 75% to 90%, then the sender forwards the ROUTE_REQUEST packet through two nodes, the healthiest one and the second healthiest one. If the value of HEALTH is in the range of 60% to 75%, then the ROUTE_REQUEST packet is forwarded through the first three healthiest nodes in the neighborhood. If the value of HEALTH is in the range of 45% to 60% then the ROUTE_REQUEST packet is forwarded through the first four healthiest nodes in the neighborhood. Otherwise, that is, when the value of HEALTH is below 45% for every node in the neighborhood, the sender broadcasts the ROUTE_REQUEST packet through all the neighbors.

Each node, after receiving the ROUTE_REQUEST packet, forwards it similarly, and they also keep the ID of the node from which this packet has been received and inserts its own ID in the packet, to prevent the looping error. A node can not forward the ROUTE_REQUEST packet to such a node, whose ID is already in the packet. When the ROUTE_REQUEST packet reaches to the sink node, sink node replies by transmitting a ROUTE REPLY packet to the node from which it receives the ROUTE_REQUEST packet. Every node along through the path from the sink node to the source node, increment the value of the counter variable PATH by one, every time when it receives a ROUTE REPLY packet. Thus the PATH variable denotes the number of path passes through this node.

Upon receiving the ROUTE REPLY packet, the source node confirms a path to the sink node, and uses this path to transmit data. Each node distributes the load equally through all the paths starting from that node towards the sink node. i.e. if some node have only one path towards the sink node, it transmits the data through that path only, and if some node have two or more paths towards the sink node, it divides the data equally, and transmit through each route. Every node gain some rewards from its neighbors, when it forwards the data packets successfully.

# 4 Performance Analysis

In traditional multi-path routing, one has to maintain all the routes, though it may be the case that, maximum of the routes will remain inactive through out the lifetime of the network. Thus, the maintenance and setup cost of multiple routes are become overhead. On the other hand, in this algorithm, the degree of multi-path depends on the health of the nodes of the network itself. The number of multi paths is also dynamically changes with the overall condition of the nodes in the network. A node only increases the number of routes towards the sink node, when it finds that the next hop nodes are not capable enough to carry the total load. Thus, it can be said that it is a much intelligent approach for multi-path routing. Due to this feature, the data reception rate, defined as the ratio of the total number of packets received by the sink node
and the total number of packets send by the source node, is much higher than any single path routing. Also the end to end delay is decreased in this algorithm, due to the reason that the number of routes will increase with the decreasing health of nodes. Thus the load is balanced among the nodes and the multiple routes also increase the reliability. The lifetime of the network also increases with this algorithm, as the nodes with less remaining energy are released from the burden of transmitting the total load. The burden of each node is decreased proportionally with its remaining energy.

# 5 Simulation Results

The proposed algorithm has been successfully simulated using the standard Network Simulator QualNet. The findings are based on simulation results. We have taken the results by varying the node density from 10 to 50 nodes with the fixed mobility 30 mps. The simulation scenario and settings are described as follows:

<table><caption>Table 1. Simulator parameter settings</caption><thead><tr><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>Terrain area</td><td>1500X1500 m2</td></tr><tr><td>Simulation time</td><td>100 sec</td></tr><tr><td>Mac Layer protocol</td><td>DCF of IEEE 802.11b stan-</td></tr><tr><td>Traffic Model</td><td>CBR</td></tr><tr><td>Number of CBR applications</td><td>10 % of the number of nodes</td></tr><tr><td>Mobility Model</td><td>Random Waypoint</td></tr><tr><td>Trust Value of normal nodes</td><td>0-10</td></tr><tr><td>Initial Energy Value of normal</td><td>5000</td></tr></tbody></table>

## 5.1 Packet Delivery Ratio

The Packet delivery ratio (PDR) is an important metric to analyze the performance of a routing protocol. PDR is defined as the ratio of the total number of packets send by the source node and the total number of packets received by the destination node

<figure><img src="image_5.png" /><figcaption>Fig. 4. Packet Delivery Ratio Vs Node Density</figcaption></figure>
As shown in fig. 4 the packet delivery ratio is almost 100% for less node density. But the packet delivery ratio decreases with increasing node density, because of the increasing congestion in the network. Still, with higher node density the packet delivery ratio is quite stable.

## 5.2 Throughput

The throughput is defined as the total number of bits received by the receiver per second. The size of each data packet is 512 bytes and one data packet is sent in every second by the sender.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Average Throughput Vs Node Density</figcaption></figure>

Fig. 5 shows that the average throughput of the nodes in different node density. The average throughput of nodes decreases as the node density increases. The rate of decrease in throughput is almost 2.5%-3% in average with 100% increment in the node density. However, it still gives a moderate result.

## 5.3 End to End delay

The end to end delay can be defined as the time that a data packet takes to traverse the distance between the sender and the receiver.

<figure><img src="image_7.png" /><figcaption>Fig. 6. Average End-to-end Delay Vs Node Density</figcaption></figure>
It can be seen from figure 6, that the average end to end delay is quite stable with the node density.

## 5.4 Jitter

Jitter is expressed as an average of the deviation from the network mean latency.

<figure><img src="image_8.png" /><figcaption>Fig. 7. Jitter Vs Node Density</figcaption></figure>

The jitter in the network is increasing quite linearly with the increment in node density. It can also be seen from figure 7, that the value of the jitter is much lower with our algorithm.

## 5.5 Average Energy Consumption

The average energy consumption of the network under various node densities is also simulated.

<figure><img src="image_9.png" /><figcaption>Fig. 8. Average Energy Consumption Vs Node Density</figcaption></figure>

The energy consumption of the network increases with the number of nodes, because, with the increasing number of nodes, every node has to broadcast more hello messages.
es and also has to calculate the health and trust of those nodes. However, the power
consumption is much lower than the other multi-path algorithms, as the proposed
algorithm tries to divide the load of the network equally among the nodes, so that no
node can be suffer.

6 Conclusion

In this paper, a new selective, multi-path routing for effective load balancing is pre-
sented. In this algorithm, every node selects its next hop forwarding nodes very intel-
ligently. The selection procedure helps to improve the lifetime of the whole network,
and as the selection is also based on trust values, the algorithm provides reliability.
Moreover, the multi-paths also increase the data delivery rate. The effectiveness of
this algorithm is validated through theoretical performance analysis as well as simula-
tion results using QualNet. The proposed methodology builds the foundation for sev-
eral meaningful extensions in future. The incorporation of different security mechan-
isms to this routing protocol is left as future work. In this paper, the evaluation of
health parameter of each node depends on three parameters: energy, path and trust.
However, the impact of other factors like interference, latency on the health of each
node could be an interesting extension of the proposed work.

7 Acknowledgement

We would like to thank the Advanced Technology Cell, DRDO Cell for approving
our work as a Defense - related project. The contingency and Fellowship provided by
the Advanced Technology Cell has played a vital role in the completion and publica-
tion of this work.

8 References

1. Jie Zhang, Choong Kyo Jeong, Goo Yeon Lee, Hwa Jong Kim, "Cluster-based Multi-path Routing Algorithm for Multi-hop Wireless Network", International Journal of Future Generation Communication and Networking (2009)

2. S. De, C. Qiao, H. Wu; "Meshed multipath routing with selective forwarding: an efficient strategy in wireless sensor networks", Computer Networks, 2003, pp.481-497.

3. Muhammad Shoaib Siddiqui, Syed Obaid Amin, Jin Ho Kim, Choong Seon Hong, "MHRP: A Secure Multi-path Hybrid Routing Protocol for Wireless Mesh Network," Military Communications Conference, MILCOM 2007, Orlando, FL, October 2007, pp. 105

4. Zhiyuan Li, Ruchuan Wang, "A Multipath Routing Algorithm Based on Traffic Prediction in Wireless Mesh Networks." Communications and Network 1(2) : pp. 82-90 (2009).

5. Sung-Won Lee, Ji Yong Choi, Keun Woo Lim, Young-Bae Ko, and Byeong-Hee Roh, “A Reliable and Hybrid Multi-path Routing Protocol for Multi-Interface Tactical Ad Hoc Networks”, The military communication conference, 2010, pp.1531-1536
6. Marjan Radi, Behnam Dezfouli, Shukor Abd Razak, Kamalrulnizam Abu Bakar, "LIEMRO: A Low-Interference Energy-Efficient Multipath Routing Protocol for Improving QoS in Event-Based Wireless Sensor Networks" Fourth International Conference on Sensor Technologies and Applications, SENSORCOMM, pp-551-557, 2010.

7. S. Mueller, R. P. Tsang, and D. Ghosal, "Multipath Routing in Mobile Ad Hoc Networks: Issue and Challenges", In Performance Tools and Applications to Networked Systems, volume 2965, LNCS, pp. 209-234

8. Yashar Ganjali, Abtin Keshavarzian "Load Balancing in Ad Hoc Networks: Single-path Routing vs. Multi-path Routing" Advance Computing Conference, 2009, IACC, IEEE International: 32-34.