OALibJ  Vol.7 No.11 , November 2020
Multi-Hop Routing Algorithm for Wireless Sensor Network
Abstract: The recent enhancement of sensor devices, such as the Micro-Electro Mechanical Devices (MEMs) used for information collection and dissemination, has led to the emergence of the Internet of Things (IoT), Internet of Vehicles (IoV). This new paradigm overlaps with many research areas such as the Wireless Sensor Networks (WSNs) where sensor nodes are deployed over an area to perform local computations based on information gathered from the surrounding. Virtual Backbone is a mechanism that aims at constructing a path with multi-hop from cluster-heads (CHs) to a Base Station (BS) via gateway nodes. This mechanism is efficient since it allows enhancing the reliability and prolonging the network lifetime. In this paper, we propose a new routing protocol, denoted Multi-Hop Routing (MHR), which uses a virtual backbone to improve the network lifetime and reduce the number of lost packets. The aim of our proposition is to find the best connection between the CHs to ensure a fast and efficient backbone construction while minimizing the energy consumption. MHR uses the number of Advertisement (ADV) messages, the residual energy and the distance to the BS in the choice of the backbone’s gateways. Our simulation results show that MHR outperforms EEUC and MH-LEACH in terms of packet delivery ratio and network lifetime.

1. Introduction

In nowadays, the Internet of Things (IoT) has emerged as one of the most revolutionary events of this decade. This novel trend can be generally described as an ecosystem where the Internet is connected to the physical world via ubiquitous sensors. The IoT can be also described as the union of many research fields such as Ad Hoc Networks, Wireless Sensor Networks (WSNs), VANETs and so on. However, the main general aspect remains the same: ensure efficient data collection and transmission to the base station while providing the best Quality of Service (QoS) and facing several constraints such as the high density and energy limitation. For this aim, several techniques are provided in the literature like the clustering to cope with the high-density feature of the networks. However, one of the main issues with this solution is how to ensure an efficient connection between the CHs to ensure the routing process toward the destination. In this paper, we propose a routing solution denoted Multi-Hop Energy Routing (MHR), which uses a virtual backbone to improve the network lifetime and reduce the number of lost packets. The aim of our proposition is to find the best connection between the CHs to ensure a fast and efficient backbone construction while minimizing the energy consumption. MHR uses the number of Advertisement (ADV) messages, the residual energy and the distance to the Base Station (BS) in the choice of the backbone’s gateways. The rest of the paper is organized as follows. Section 2 briefly reviews related works cross backbone techniques in WSNs. In Section 3, the proposed construction backbone approach based on hybrid metric referred to MHR is presented. Then, it is followed by the simulation results and performance evaluation presented in Section 4. The paper is concluded in Section 5.

2. Related Work

2.1. Low Energy Adaptive Clustering Hierarchy (LEACH)

In [1], Heinzelman et al. proposed a routing protocol, called Low Energy Adaptive Clustering Protocol (LEACH), which is based on the cluster-head election using the generation of a random number. It assigns this role to different nodes according to a Round-Robin policy to ensure fair energy dissipation between nodes. Every round has approximately the same time interval previously determined. In order to reduce the amount of data transmitted to the base station, the cluster head aggregates data captured by the member nodes that belong to its own cluster, and sends an aggregated packet to the base station. Some nodes could lose energy too quickly since they are selected as cluster heads many times. The main disadvantage of LEACH is that all clusterheads communicate directly with the sink. However, the energy consumed between cluster heads and the sink is greater than the energy consumed among cluster heads and the cluster members. Therefore, the cluster heads will exhaust energy rapidly. In order to improve the network performances, LEACH has been enhanced in TEEN [2], LEACH-C [3], ALEACH [4], APTEEN [5], PEGASIS [6], LEACH-G [7], and HEED [8].

2.2. Energy-Efficient Unequal Clustering (EEUC)

In [9], Li et al. introduce a distributed Energy-Efficient Unequal Clustering (EEUC) algorithm with the aim of balancing energy consumption and prolonging the network lifetime. In EEUC, the nodes and the BS are stationary and a node can compute the approximate distance to another node based on the RSSI value. The CH election is based on the residual energy of each node and the distance to the BS. The BS broadcasts a Hello message to all nodes and each node computes the distance to the BS using the RSSI value. In EEUC, the closer the cluster is to the BS, the smaller is its size (Figure 1). Therefore, CHs close to the BS can preserve energy for inter-cluster data forwarding. The distribution is made by using the competition radius presented in Equation (1). A multi-hop routing protocol was also proposed for the inter-cluster communication.

S i R c o m p = ( 1 c d max d ( s i , BS ) d max d i n ) R c o m p 0 (1)

In Equation (1), dmax and dmin are the distances of the furthest and the closest node to the BS respectively, d(Si, BS) is the distance between a node Si and the BS, is a constant coefficient between 0 1 and Rcomp is the radius of the biggest cluster. EEUC improves the network lifetime when compared with LEACH and HEED. However, in EEUC, a CH chooses a relay node from its adjacent CHs without considering the relay traffic balance. To enhance the performances and increase the network lifetime in EEUC, other protocols were proposed such as RHEED [10] and RUHEED [11]. In EEUC, the periodic cluster head rotation or election needs extra energy to rebuild clusters.

2.3. Multi-Hop Low Energy Adaptive Clustering Protocol (MH-LEACH)

Henrique et al. [12] proposed a Multi-Hop Low Energy Adaptive Clustering Protocol (MH-LEACH) that attempts to enhance LEACH’s performances. This protocol establishes a multi-hop communication between cluster heads and the BS in the network. In MH-LEACH, each cluster-head sends a packet to the nearest cluster-head which has enough energy and is turned towards the Base Station. Thus, if a cluster-head cannot send a message to another one, it will try to find another cluster-head based on the information contained in its routing table. The latter is constructed by the BS based on the signal strength level received (RSSI). If the node Y received a packet from the base station with a higher RSSI than node X, it means that node Y is closer to the base station than node X. To see whether a cluster-head can be in another cluster head route table, the base station executes the following algorithm.

if ( ( I noX EB ) < ( I noY EB ) ) then the node Y is a possible route to node X (2)


・ I − noX −EB is the intensity of a packet received by the node X from the base Station.

Figure 1. EEUC Topology.

・ I − noY − EB is the intensity of a packet received by the node Y from the base Station.

Contrary to LEACH, the communication between CH and the sink is not direct in the case where the CH is not in the transmission range of the sink. The disadvantage of MH-LEACH is the fact that the selection of the same CH such as intermediate nodes consumed a lot of energy. Therefore, the network lifetime is reduced.

2.4. Energy Efficient Hybrid Multi-Hop Clustering Scheme (EEHMCS)

Ananya et al. presented a multi-hop communication algorithm [13]. This protocol uses a number of CHs as intermediate relay nodes to transmit data to base station when BS is situated far away from the deployment region. In this proposition, the network is divided into two zones: near-zone and far-zone. In the first, CHs broadcast messages to all far-zone CHs and according to the received signal strength far-zone CHs select their closest relay nodes. The CHs of far-zone send their packets to CHs in the near-zone. Besides, CHs of the near-zone relay the packet to the BS. The major disadvantage of this protocol is that the near-zone sensors consume a lot of energy as they have to transmit their own data for the far-zone.

2.5. Energy-Aware Multilevel Cluster Tree (EAMCT)

Yan et al. proposed the Energy-Aware Multilevel Cluster Tree (EAMCT) algorithm in [14], where the cluster heads with high energy are chosen to act as relay nodes directly. Furthermore, when the clustering tree is being finned, the number of relay nodes is minimized by performing optimization rules in order to reduce the amount of data exchanged between the nodes and to minimize energy dissipation.

2.6. Energy-Aware Multilevel Cluster Tree with Gateway (EAMCT-G)

To improve EAMCT performances, An et al. proposed in [15] an Energy-Aware Multilevel Cluster Tree with Gateway (EAMCT-G) algorithm. The aim of EAMCT-G is to introduce some gateway nodes as relay transmission among cluster-heads. When a cluster head is chosen in EAMCT-G, it will send an invitation to the other cluster-heads, which have not been added to EAMCT-G, within three hops to let them join. This process will be repeated until all the cluster-heads have joined in EAMCT-G. Using the concept of rooted tree, the BS will first be added to the tree acting as the root, subsequently, all the CHs are added to the tree gradually through gateway nodes. The building of the clustering tree is divided into two rules including: 1) rule 1: handling Invite messages; and 2) rule 2: handling Child messages. In the last one, when a simple node V receives a Child message (U, V) from the node U, node V chooses itself as a gateway node, and the node that sent this message as its child. Then, node V sends a Child message back to its father. When the cluster-head node receives a Child message that is forwarded to it from a simple node, it will consider the simple node as its child.

2.7. Hybrid Weight Clustering Algorithm (HWCA)

In [16], we proposed (HWCA) in order to increase the network lifetime by using a hybrid metric composed of three parameters: the distance of the candidate node to the BS, its level of consumed energy and the number of neighbor nodes as calculated in Equation (3). A node with the smallest weight is selected as the CH.

m ( u ) = α 1 | N ( u ) | N + α 2 d i s t ( u , b ) L max + α 3 E c ( u ) E ( u ) (3)

Here, m(u) is the metric of node u, N(u) is the total number of one-hop neighbor nodes of u, dist(u, BS) is the Euclidean distance of node u from the BS and Ec(u) is the energy consumed by node u. The energy consumption is balanced across the cluster by rotating the role of CH within the cluster and the size of the cluster was not taken into account. The major disadvantage of EANOC is that all cluster-heads send their data directly to the base station.

3. Gateway Selection Technique

3.1. Problem Description

We will represent the wireless sensor networks using a connected, undirected graph G = ( V , E ) , where V = { 1 , 2 , , n } is a set of vertices, respectively represents each wireless sensor; E = { e 1 , , e m } is a set of edges, edge e i = { V j , V t } represents the two nodes Vj and Vt that are within the radio range of each other. Assuming that there is a n-node wireless sensor network, the objective of this work is, after clustering phase, to choose the best gateway nodes to transmit data to the base station. We define a node as a gateway when it can be selected to ensure communication between at least two CHs. MHR represents an extension of the EANOC protocol. It aims to improve the network lifetime and reduce the number of lost packets. The purpose of the protocol is to send data to the base station through the gateways nodes already selected. Like EANOC protocol, MHR uses the same mechanism for the election of clusters-head. Due to space restriction, we will focus in this paper on the gateway choice algorithm and we will not present the cluster-head selection algorithm. Based on EANOC protocol, we exploit the metric to obtain CH in order to have a hybrid metric to choose the gateway node. This method combines the formula (3) and other parameters.

m ( u ) = | N ( u ) | N + d i s t ( u , b ) L max + E r ( u ) E ( u ) (4)

3.2. Hybrid Metric

In this formula, we use:

・ N(u) as the number of nodes in the one-hop neighborhood of node.

・ dist(u, b) is the Euclidian distance from node to the base station.

・ Er(u) is the energy consumed by node u.

・ N is the maximum number of nodes that a cluster head can handle ideally. This is to ensure that a cluster-head is not over-loaded and the efficiency of the system is maintained at the expected level.

・ Lmax is the maximum distance between two nodes, which represents the diagonal of the area.

・ E(u) is the initial energy of node u.

For the gateway choice, we use a hybrid metric gw(u). It’s obtained using the following formula:

g w ( u ) = N_ADV N + d i s t ( u , b ) L max + E r u E ( u ) (5)

Using formula (4), we have:

g w ( u ) = m ( u ) + N_ADV N | N ( u ) | N (6)

And finally, we obtain:

g w ( u ) = m ( u ) + N_ADV | N ( u ) | N (7)

We denote N_ADV, as the number of ADVs (advertisements messages).

3.3. Algorithm Description

In this proposition, the network is already formed and the cluster-heads of each group are already chosen. The main objective of the algorithm is the establishment of the multi-hop communication between cluster-heads and the base station. In order to ensure this, we choose some gateway nodes that will act as intermediary nodes if the CH is not in the transmission range of the base station. This choice is based on a hybrid metric which combines the number of ADV messages received, the distance to the base station and the residual energy. Our proposition is detailed in the two following Algorithm 1 and Algorithm 2. In Algorithm 1, the nodes, which do not cluster heads, receive the ADV messages from the CH during the time interval Synchro_ADV. They use the RSSI from the ADV messages to announce themselves as gateways. However, if a node receives at least two Advertisement messages (ADVs), it sends a sendADV _GW packet to its CH which is containing its ID and its metric (formula 7). At the end of this algorithm, each node receiving more than two Advertisements (ADVs) must inform the CH that it is a gateway candidate.

Algorithm 1. Candidate gateway declaration algorithm.

Algorithm 2. Gateway selection algorithm in the CH.

In Algorithm 2, if a CH receives a received ADV_GW (v, metric) packet from a candidate gateway, it adds the ID of this candidate to the list L. After a synchronization period Synchro_ADV_GW, if it is a neighbor of the base station, it sends its packets directly to this base station. Otherwise, each CH chooses the best gateway among all the candidates present in the established list L. We note that if the CH is in the vicinity of the sink, so there is no need to designate a gateway.

The choice Best GW (L(u)) function in Algorithm 2 compares the metrics of the candidate gateways. It chooses the one that has the smallest metric value as the better candidate for gateway. After this choice, this node will be used when there is data to send to the base station.

3.4. An Illustrative Example

To better understand our proposition, we illustrate it with the example shown in Figure 2. After the clustering phase (not presented in this paper), all CHs start sending ADV messages in their neighborhood. These messages will be received and treated by the CHs’ neighbors.

In Figure 3, the potential gateways send their proposition to their cluster-heads to act as their first intermediary to the base station. In the sendADV _GW packet, every node sends its ID and its metric. For example, the CH with ID 20 received three sendADV _GW packets from the nodes 19 with 0.7 as metric, 21 with 0.43 as metric and 3 with 0.87 as metric.

Finally, Figure 4 shows how the gateways are selected and then the best path to the base station is built. In the same example, the CH with ID 20, selected the node with ID 21 as its gateway to the best station since its metric (0.43) is the lowest one between all declared candidate gateways.

4. Performance Evaluation

In this section, we evaluate the performance of MHR using Castalia-3.2 [17] running on top of OMNET++ [18]. Sensor nodes are randomly distributed in a variable region in the simulation. The number of nodes is varied from 100 to 300 nodes. A sensor node consumes 0.77 mW in the idle state, 35.46 mW in the reception state and 31.32 mW in the transmission state. In our experiments, the base station is kept fixed in the middle of the network. The size of the transmitted packets by the nodes to their CHs at each round is 200 bytes. The energy efficiency of our proposed mechanism is compared with MH-LEACH and EEUC. The used parameters’ values are summarized in Table 1. The networks lifetime is among the parameters studied in the WSN. We evaluate the network lifetime by running several simulations while varying the number of nodes (100 - 300). Generally, the network lifetime depends on WSN application requirements. Some of these applications require nodes to have a good coverage and thus their corresponding network lifetime metric is measured according to the lifetime of the shortest-living node. Other applications require only a specific percentage of nodes to remain alive to achieve the application requirements [19]. Therefore, we evaluate the network lifetime by using a specific metric Half Node Die (HND). It is defined as the time elapsed in rounds until half of the nodes have consumed all their available energy. In the first part of our experiment, we illustrate the results in terms of the number of alive nodes against the number of rounds for 100 nodes. As shown in Figure 5, MHR shows a 38% improvement in network lifetime compared to MH-LEACH and 22% compared to EEUC. This is due to the fact that MHR selected fewer cluster-heads than the other protocols. As a consequence, the energy consumed is less since the cluster-heads are the most energy-consuming.

Table 1. Parameter settings.

Figure 2. ADV messages reception.

Figure 3. Send message to become gateway.

Figure 4. Find best gateway.

Figure 5. Network lifetime for 100 nodes.

Figure 6 presents the network evolution using the Half Node Die (HND) metric, i.e. the number of rounds spent until half of the network is inactive. It demonstrates another time that MHR increases the network lifetime by more than 20% EEUC and 38% MH-LEACH. This confirms that the gateway choice algorithm is very energy efficient compared to these well-known protocols.

Figure 7 shows the total energy consumed in all hundreds of rounds. It demonstrates that the energy consumed using MHR is reduced significantly compared to MH-LEACH reaching 60% at 300 rounds, and relatively reduced compared to EEUC reaching 21% at 600 rounds. After 600 rounds, all the nodes in MH-LEACH died and the number of alive nodes in EEUC drastically reduced. Then, EEUC consumes naturally less energy than MH-LEACH which saves the energy of the nodes. This will be seen better when analyzing the network performances of our protocol MHR compared to EEUC and MHLEACH.

Another important network parameter is the Packet Delivery Ratio (PDR). The PDR is computed as the amount of data received by the base station divided by the amount of all sent data through the whole network. Figure 8 displays the delivery ratio of every algorithm while varying the number of nodes from 100 to 300 nodes. We observe, here, that MH-LEACH and EEUC lose more data than MHR algorithm. For example, with 100 nodes, MHR protocol delivers more than 35% of packets compared to MH-LEACH and 70% EEUC. This is principally due to the fact that our protocol uses the maximum of connectivity between nodes to increase packet delivery ratio.

From all these results, we can conclude that our routing protocol MHR outperforms EEUC and MHLEACH. In fact, it is based on a clustering and gateway selecting approach. Generally speaking, MHR is the most energy-efficient protocol from those compared followed by EEUC and MH-LEACH. However, for the network performances, MHR is the most powerful in terms of PDR from those compared followed by MHLEACH and EEUC for author/s of only one affiliation: To change the default, adjust the template as follows.

Figure 6. Network lifetime in terms of Half Node Die.

Figure 7. Network energy consumption for 100 nodes.

Figure 8. Packets delivery ratio.

5. Conclusion

In this paper, we proposed a new routing protocol based on a clustering mechanism using gateway nodes denoted MHR for Wireless Sensor Networks (WSN). MHR is an extension of EANOC. The main contribution of this proposition is the gateway selection algorithm. It aims to establish a multi-hop communication between the different cluster-heads and the base station. For this issue, we use a proposed hybrid metric in this choice. This metric is based on a combination of three important criterions: 1) the number of Advertisement (ADV) messages, 2) the residual energy and 3) the distance to the base station. After a clustering phase, the gateway that is common to at least two CHs proposes to act as gateways. Then, the CHs select their gateways based on the lowest received metric. The simulation results demonstrated that MHR is more efficient than EEUC and MH-LEACH in terms of network lifetime and packet delivery ratio. For our future works, we will better measure the behavior of MHR using other network performance indicators such as the end-to-end delay. We intend also to study more deeply other criterions, which will influence on the gateway selection algorithm in order to enhance the performances of our proposed routing protocol MHR.

Cite this paper: Cisse, C.S.M. (2020) Multi-Hop Routing Algorithm for Wireless Sensor Network. Open Access Library Journal, 7, 1-14. doi: 10.4236/oalib.1106955.

[1]   Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, 4-7 January 2000, 10.

[2]   Manjeshwar, A. and Agrawal, D.P. (2001) TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Parallel and Distributed Processing Symposium, International, Vol. 3, 30189a.

[3]   Heinzelman, W.B., Chandrakasan, A.P. and Balakrishnan, H. (2002) An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, 1, 660-670.

[4]   Ali, M.S., Dey, T. and Biswas, R. (2008) ALEACH: Advanced LEACH Routing Protocol for Wireless Microsensor Networks. IEEE International Conference on Electrical and Computer Engineering, Phuket, 20-22 December 2008, 909-914.

[5]   Manjeshwar, A. and Apteen, A.D. (2002) A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wireless Sensor Networks. Proceedings of the 2nd International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, Fort Lauderdale, FL, 15-19 April 2002, 195-202.

[6]   Lindsey, S. and Raghavendra, C.S. (2002) PEGASIS: Power Efficient Gathering in Sensor Information Systems. Aerospace Conference Proceedings, Vol. 3, 3-1125.

[7]   Chen, H., Zhang, C., Zong, X. and Wang, C. (2013) LEACH-G: An Optimal Cluster-Heads Selection Algorithm Based on LEACH. Journal of Software, 8, 2660-2667.

[8]   Younis, O. and Fahmy, S. (2004) HEED: A Hybrid, Energy Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks. IEEE Transactions on Mobile Computing, 3, 366-379.

[9]   Li, C., Ye, M., Chen, G. and Wu, J. (2005) An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Washington DC, 7-10 November 2005, 8.

[10]   Mardini, W., Yassein, M.B., Khamayseh, Y. and Ghaleb, B.A. (2014) Rotated Hybrid, Energy-Efficient and Distributed (RHEED) Clustering Protocol in WSN. WSEAS Transactions on Communications, 13, 275-290.

[11]   Aierken, N., Gagliardi, R., Mostarda, L. and Ullah, Z. (2015) RUHEED-Rotated Unequal Clustering Algorithm for Wireless Sensor Networks. IEEE 29th International Conference on Advanced Information Networking and Applications Workshops, Gwangiu, 24-27 March 2015, 170-174.

[12]   Neto, J.H.B., Rego, A., Cardoso, A.R. and Celestino Jr., J. (2014) MH-LEACH: A Distributed Algorithm for Multi-Hop Communication in Wireless Sensor Networks. ICN 2014, Nice, 23-27 February 2014, 55-61.

[13]   Patra, A. and Chouhan, S. (2013) Energy Efficient Hybrid Multihop Clustering Algorithm in Wireless Sensor Networks. 2013 IEEE International Conference on Communication, Networks and Satellite (COMNETSAT), Yogyakarta, 3-4 December 2013, 59-63.

[14]   Yan, X.F., Sun, Y.G. and Zhao, C.L. (2005) Energy-Aware Hierarchical Clustering Algorithm for Wireless Sensor Networks. Journal of Tianjin University, 12, 15.

[15]   An, N., Yan, X., Zhu, Y. and Duan, L. (2007) A Virtual Backbone Network Algorithm Based on the Multilevel Cluster Tree with Gateway for Wireless Sensor Networks.

[16]   Cisse, C.S.M., Ahmed, K., Sarr, C. and Gregory, M.A. (2016) Energy Efficient Hybrid Clustering Algorithm of Wireless Sensor Network. 2016 26th International Telecommunication Networks and Applications Conference (ITNAC), Dunedin, 7-9 December 2016, 38-43.

[17]   The Castalia Simulator for Wireless Sensor Network.

[18]   OMNeT++Community OMNET++.

[19]   Aierken, N., Gagliardi, R., Mostarda, L. and Ullah, Z. (2015) RUHEED-Rotated Unequal Clustering Algorithm for Wireless Sensor Networks. 2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops (WAINA), Gwangiu, 24-27 March 2015, 170, 174.