# EE-MRP: Energy-Efficient Multistage Routing Protocol for Wireless Sensor Networks

Authors: Muhammad Kamran Khan; Muhammad Shiraz; Kayhan Zrar Ghafoor; Suleman Khan; Ali Safaa Sadiq; Ghufran Ahmed
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Wireless sensor networks (WSNs) have captivated substantial attention from both industrial and academic research in the last few years. The major factor behind the research efforts in that field is their vast range of applications which include surveillance systems, military operations, health care, environment event monitoring, and human safety. However, sensor nodes are low potential and energy constrained devices; therefore, energy-efficient routing protocol is the foremost concern. In this paper, an energy-efficient routing protocol for wireless sensor networks is proposed. Our protocol consists of a routing algorithm for the transmission of data, cluster head selection algorithm, and a scheme for the formation of clusters. On the basis of energy analysis of the existing routing protocols, a multistage data transmission mechanism is proposed. An efficient cluster head selection algorithm is adopted and unnecessary frequency of reclustering is exterminated. Static clustering is used for efficient selection of cluster heads. The performance and energy efficiency of our proposed routing protocol are assessed by the comparison of the existing routing protocols on a simulation platform. On the basis of simulation results, it is observed that our proposed routing protocol (EE-MRP) has performed well in terms of overall network lifetime, throughput, and energy efficiency.


---

## Body

## 1. Introduction

Wireless sensor network is comprised of a large number of tiny and small sensor nodes which are distributed over the physical environment to monitor security events, temperature, humidity, capture images, pressure, and so on [1–8]. Sensor nodes have limited energy capabilities and have individual resources (such as CPU and memory). These nodes are randomly located in the dynamically varying environment [9]. The life of the sensor node depends on the energy (battery) of the node, on which the lifespan of the network is dependent. The main problem faced in WSN is that the energy of sensor nodes dropped quickly and become lifeless [10]. It is observed that maximum energy is dissipated in the communication subsystem [11]. Therefore, in order to extend and maximize the lifetime of sensor nodes, designing energy-efficient algorithms is necessary [1, 11–13]. In order to increase the lifetime of WSN, it is needed to manage resources carefully.There are many issues in WSNs which have to be considered, such as overall lifetime, coverage, energy efficiency, and network security [14–17]. Apart from efficient and reliable communication, the major goal of a routing protocol is to maximize the lifetime of cluster heads and sensor nodes. The following issues should be considered while designing an energy-efficient clustering algorithm. Firstly, the routing protocol should be distributed because it works better for large-scale WSNs [18]. Secondly, cluster heads should be distributed evenly in the network field, so that all sensor nodes equally find cluster heads for the communication [19]. Thirdly, communication between cluster heads and base station should be minimized because maximum energy is utilized in the communication between cluster heads and base station [20]. Fourthly, in most of the hierarchical routing protocols, cluster heads selection technique is not efficient [21].The energy consumption in the gathering of information from sensor nodes varies among cluster heads because it depends on the number of members of cluster heads. The consumption of energy also differs in cluster members because it depends on the distance between member nodes and cluster heads. In most of the existing WSN routing protocols, it is noticed that if one issue is addressed then other issues are ignored, due to which the required energy efficiency is not achieved. All factors discussed above should be considered in the development of routing protocol to achieve maximum energy efficiency in combination with the target to achieve maximum network coverage and data throughput.The primary objective of this research is to address routing issues by adopting an efficient cluster head selection method and proposing an energy-efficient and reliable routing protocol for WSNs. A lot of cluster-based routing protocols have been proposed for WSNs, but these protocols have limitations due to challenges related to the determination of accurate radio model (communication model) for the sensor nodes and cluster heads in the network area. The other drawback which is also addressed in our research work is an uneven distribution of cluster heads in the network field, which results in disconnection of a portion of network area from the base station. Hierarchical routing protocols like LEACH [4] and its variants use the same amplification energy in the transmission of data from the source node to the destination regardless of the distance between transmitting and receiving nodes [4, 10, 22]. Energy can be preserved by using multiple energy levels for the transmission of data according to the distance between the receiver and the transmitter. Therefore, we need to propose an energy-efficient solution to maximize the overall lifetime of the network.The rest of the paper is organized as follows. Section2 presents related work. The proposed routing protocol is presented in Section 3. Section 4 presents performance evaluation in terms of energy efficiency, stability period, and throughput. Finally, Section 5 ends up with the conclusion.


## 2. Related Work

WSNs have massive complexity and applicability, because the complex nature of WSNs variety of issues has to be addressed by the scientists and engineers. Various energy-efficient routing protocols have been proposed in the last few years. In hierarchical cluster-based network, the network is divided into separate clusters, and hierarchy of different nodes is defined. Each cluster has its cluster head (CH). Sensor nodes in each cluster get the information and send it to CH. CHs collect the information from sensor nodes in its cluster region, aggregate the collected information, and send it directly to BS or next hop according to the predefined algorithm working in CH.Low energy adaptive clustering hierarchy (LEACH) protocol is a base for the development of many hierarchical routing protocols in WSN. It is adaptive clustering and self-organizing routing protocol [1]. LEACH distributes the deployed nodes area into number of clusters. In each cluster, one node act as a CH and remaining nodes in this cluster act as a member of the cluster. These member nodes only communicate with their CH and CHs communicate with sink node or base station (BS) [1, 23]. CH is used as an intermediate node for member nodes to reach BS. CH collects data from member nodes, aggregates it, and forwards compressed data to BS. Due to added tasks, CH consumes more energy as compared to the normal nodes. As in static clustering, CH remains permanently, which results in the quick death of CHs [1, 24].LEACH noticeably improves network lifetime and minimized energy dissipation as compared to other nonhierarchical routing protocols. But there are a lot of opportunities to enhance the capabilities of the LEACH protocol. LEACH is not suitable for large-scale networks, because of its single hop routing operation, irrespective of the distance; each CH has to communicate directly with the BS. At the time of selection of CHs, the residual energy of the node is not considered and it is the possibility that a node with less energy can be selected as CH; if that happened then it will become dead and consequently, that cluster becomes inaccessible. LEACH assumes even consumption of energy for every CH and does not guarantee proper CH distribution.MODLEACH [21] is a modified version of LEACH protocol. In MODLEACH an efficient CH replacement scheme has been introduced. A predetermined threshold level has been set for the replacement of CHs. If current CH has enough battery power, which is greater than the predetermined threshold level then it will continue to serve as CH for the next round. The CH does not change until its battery power becomes less than the threshold limit. By using this CHs selection technique, energy consumed in the routing of update packets for newer CHs has been saved. MODLEACHHT [21] and MODLEACHST [21] are extended versions of MODLEACH [21]. In these versions, the idea of the hard and soft threshold level is introduced [25]. The soft threshold level is a little variation in the value of a recognized attribute which elicits the node to turn on the aerial and pass on data. The hard threshold is the attribute outright value beyond which the node that recognized threshold value will activate its transmitter and connect to CH. MODLEACHST [21] and MODLEACHHT [21] adopted the reactive approach and produced comparatively better results than MODLEACH [21]. MODLEACH, MODLEACHST, and MODLEACHHT improve CH selection technique but still, there are weaknesses in routing technique. These routing protocols adopt single hop routing strategy and are not suitable for large-scale networks. MODLEACH works on the basis of the density of sensor nodes which can make it unstable during the setup phase.Multihop LEACH (MH-LEACH) routing protocol [20] adopts a multihopping strategy to send collected data to BS. In it every sensor node sends the collected data to the CH, CHs perform aggregation operation and forward data to next CH until it reached BS. An optimal path is adopted between the sensor node and BS. The major limitation in MH-LEACH is delay factor which is due to multihop during transmission of data. As a lot of hops are added to reach BS, a little bit energy efficiency is achieved, which can be improved by reduction of unnecessary hops involved in the communication process.Assisted LEACH (A-LEACH) [26] introduces additional node for load sharing of CHs, which is known as helper node. In every cluster along with CH, a helper node is also selected. A node which has sufficient remaining energy and is nearest to the BS is selected as helper node. Every CH receives the data sensed by the sensor node in each cluster. CHs forward the collected information to helper node after performing aggregation and removal of redundant data. The helper node performs routing tasks, which forwards the data to the nearest helper node. During routing phase, only helper nodes remain active and all other sensor nodes including CHs will go into sleeping mode and minimize energy dissipation.Advanced Zonal Rectangular LEACH (AZR-LEACH) [27] have enhanced CH selection technique and introduced static clustering technique. The network deployment area is distributed into three logical partitions, such as advanced clusters, rectangular clusters, and zones. The rectangular clusters are formed by dividing the entire network into fixed clusters. Normally BS is installed at the center of the network area. The clusters those are around BS are advanced clusters and nodes under advanced clusters are considered as advanced nodes. Advanced CHs receive data from their member nodes as well as from other CHs and forward it to the BS. As advanced clusters are closer to BS, they consume less transmission power in comparison to other CHs. The zone is formed by the group of rectangular clusters. It is necessary that every zone must contain minimum one advanced cluster. AZR-LEACH [27] adopts a different strategy for the selection of CHs as compared to LEACH routing protocol. The node with highest remaining energy in the rectangular cluster will be elected as the CH. All nodes in the cluster send their remaining energy information to the CH. The main advantage of AZR-LEACH [27] is that the whole network area equally distributed into subareas, which equalize the network traffic load.Centralized Low Energy Adaptive Clustering Hierarchy (LEACH-C) [2, 28] protocol introduces centralized cluster creation technique. Apart from CH’s selection, all other operations are similar to LEACH routing protocol. Steady-state phase is different from original LEACH and setup phase is similar to LEACH protocol. In LEACH-C, all nodes send their location information and remaining energy level to the BS. For location information, sensor nodes are equipped with GPS module or any other tracking system. This information is shared at the beginning of each round. When BS has all the required information of nodes in the network then BS determines the value of average energy of all the sensor nodes in the network. The nodes with more remaining energy than the calculated average energy will be marked as candidate nodes. From the group of nodes which are marked as a candidate, BS will select a group of CHs using the simulated annealing. After choosing the selected group of CHs, it will be broadcasted to the entire network. A deterministic threshold algorithm is used by LEACH-C to collect the information of remaining energy level in the sensor nodes and to keep a record of nodes, those were selected as CHs in the previous rounds. By keeping CH’s selection task centralized, this technique improves the energy efficiency and reduced the load on CHs but there is extra overhead on the BS. The performance of LEACH-C [28] diminishes when energy utilization for communication with BS increases, then the energy cost for cluster formation.In order to prolong the stability time period (the time period before the first sensor node becomes dead), a two-level heterogeneous routing protocol is introduced, which is called stable election protocol (SEP) [29]. SEP distributes sensor nodes into two categories: normal sensor nodes and advanced sensor nodes. Advance sensor nodes are special nodes which have more energy (battery power) than normal sensor nodes. Both normal and advanced sensor nodes use weighted probability for the selection of CHs. As compared to advance sensor nodes, normal sensor nodes have lesser chances to become CH. Stability period is critical for most of the applications where reliable feedback is required from the sensor network. SEP routing protocol has noticeably improved the stability period than LEACH routing protocol. The major shortcoming in SEP routing protocol is that effective client deployment of sensor nodes is not guaranteed.Enhanced stable election protocol (E-SEP) [30] has introduced three-level communication hierarchy. E-SEP distributes sensor nodes into three categories: normal sensor nodes, intermediate sensor nodes, and advanced sensor nodes, where intermediate sensor nodes have more energy (battery power) than normal sensor nodes and advance sensor nodes have more energy (battery power) than normal nodes and intermediate nodes. By using an extra level of heterogeneity as compared to SEP [29], up to some extent energy dissipation is reduced. Multihop routing with stable election protocol (MR-SEP) [31] enhances SEP routing protocol by dividing the network field into multiple layers of clusters. In each layer, CHs are selected and member sensor nodes join CHs in each layer according to their distance from CHs. For the transmission of data, CHs in each layer collect data from member nodes and collaborate with the CHs of adjacent layers. The CHs in upper layer perform as super CHs for the CHs of the lower layer. By adopting multiple layering approaches CHs are evenly distributed in the network field and multihoping strategy has increased the stability period but did not get any convincing improvement in the overall network lifetime.


## 3. Proposed Solution

In the development of routing protocol, the operating environment is provided by the network model, which consists ofN sensor nodes, forwarder node, and BS. Sensor nodes are deployed randomly in the network area, and forwarder node is deployed in the network area, where it may be maximum involved in the communication process and BS is located outside of the network area. The major properties of the network model are as follows:(i)
All sensor nodes are homogeneous, having similar communication, sensing, and processing capabilities.(ii)
The sensor nodes are energy constrained.(iii)
In order to vary the transmission power of the sensor nodes, these are equipped with power control capabilities. The transmission range can be varied on the basis of requirements.(iv)
The forwarder node has more power and its battery can also be replaced and recharged.


### 3.1. Energy Model

It is the fact that the energy available to the sensor nodes is not only limited that it may diminish very easily if it is not properly managed. The main reasons for the consumption of energy in wireless sensor networks are communication and processing, with communication being the main responsible for the consumption of energy. First-order radio model [1, 2] is used for the energy model of sensor nodes. As shown in Figure 1, energy model consists of three main modules: receiver, transmitter, and power amplifier. The receiver consumes energy to run the receiver circuitry at the time of reception of data, and the transmitter consumes energy to run the power amplifier circuitry and transmitter circuitry at the time of transmission of data. Energy dissipation for transmitter and receiver is represented by Eelec and energy dissipation for transmit amplifier is represented by Eamp.Figure 1
Radio communication model.There are two transmission models: transmission model for free space and two-ray ground [32, 33]. In free space transmission, there is a direct line of sight path between the transmitting and the receiving nodes. In two-ray ground transmission model, the transmission between transmitting and the receiving nodes is not direct and the electromagnetic wave reached at the receiver from different paths at different times. The energy consumed for the transmission of l bits data packet, with distance “d” and energy consumed for the reception of “l” bits data by the receiver nodes, is represented by (1)ETxl,d=Eelec×l+Eamp×l×d2ERxl=Eelec×l.Two different levels of power amplification for communication signals are introduced by MODLEACH [21], which is used on the basis of transmission nature. Equations (2) show the amplification levels for different communications on the basis of type and distance between communication devices. As compare to BS to cluster transmission, for intracluster transmission, lesser energy amplification level is used. Apart from energy saving benefits, collisions are reduced by the use of multiple power levels, and the number of packet drops and interference with other signals are also reduced.(2)Energy  Amplification  levelCH  to  BS/Forwarderd≥d0Eafs=10pJbit/m2Energy  Amplification  levelCH  to  BS/Forwarderd≤d0Eamp=0.0013pJbit/m2Energy  Amplification  levelIntra  Cluster  Com.d≥d1Eafs1=Eafs10Energy  Amplification  levelIntra  Cluster  Com.d≤d1Eamp1=Eamp10.Transmission within a cluster is called intracluster communication. In it, sensor nodes sense data from the environment and send the collected data to the CH. Minimum amplification energy is required for intracluster communication.


### 3.2. Design of Energy-Efficient Multistage Routing Protocol (EE-MRP)

The fundamental theme of our proposed routing protocol is the energy efficiency in larger network field of wireless sensor networks, where data is extremely interrelated and the requirement of end user is an only high-level function of data that contains a collection of events collected from the environment. The clustering hierarchical approach, efficient CH selection algorithm, and optimized routing algorithm are essential to design efficient solution for larger scale networks [33, 34]. The architectural design of our proposed routing protocol is shown in Figure 2. In our proposed routing protocol, homogeneous sensor nodes are randomly placed in the network field. Forwarder node is placed in the field where it may be maximum involved in the communication process. BS is placed outside of the network field.Figure 2
Basic architecture of EE-MRP.


#### 3.2.1. Setup Phase

In this phase, the network field is divided into three logical stages (S1, S2, and S3) on the basis of sensor nodes located in the network field. BS is responsible for the division of network field into three logical stages. S1 and S3 have clustered regions and S2 is nonclustered region. Sensor nodes in S1 send data to the CHs, aggregation is done by CHs, and then aggregated data is forwarded to BS. Sensor nodes in S2 send data to the forwarder node, which performs aggregation on the collected data and then aggregated data is forwarded to BS. The sensor nodes which belonged to S3 also sends collected data to CHs and after aggregation, and CHs send to the forwarder node. The forwarder node then sends the collected data to the BS. By adding the forwarder node in the communication infrastructure, the distance between communicating nodes becomes less and energy consumption becomes less as compared to direct communication between CHs and BS.


#### 3.2.2. Cluster Formation

In most of the cluster-based routing protocols, clusters are formed in the network field and CHs are randomly divided in the entire network field. In it, there are chances that CHs are not uniformly distributed in the network field. Some portion of the network may get more CHs and some portion may get lesser CHs. Due to this problem sensor nodes in that portion of network field may expire earlier and a part of the network becomes isolated. In EE-MRP initially, BS divides the network field into multiple logical segments. Then in each segment, CHs are selected. By using this mechanism CHs are evenly distributed in each segment of the network field. This cluster formation strategy increased the overall lifetime of the network. On the basis of location information, segment identification numbers are allotted to sensor nodes; therefore, sensor nodes can only join CHs located in their own segment. The cluster formation flow diagram is shown in Figure3. Once CHs are selected, then CHs broadcast the invitation message to normal nodes in its area to join CH and become member node. Normal sensor nodes wait for invitation message from CHs in their area, and sensor nodes send join message to the nearest CH, on the basis of distance information.Figure 3
Cluster formation flowchart.


#### 3.2.3. Cluster Head Selection

Later to cluster formation, each node takes a decision whether or not to serve as a CH for the existing round. Every sensor node elects itself as a CH on the basis of the desired ratio of CHs and the status of eligibility flag to become CH. For instance, noden chooses a random number ranging from 0 to 1. The node will become CH if the threshold T(n) is greater than a number. Following formula is used for the calculation of T(n) [1, 11, 21].(3)Tn=fx=P1-P∗rmod⁡1/P,ifn∈G,0,otherwise,wheren is total number of sensor nodes.P is preferred the percentage of CH.r is current round.G is set of sensor nodes eligible to become CH.Selected CHs broadcast their status to other nodes via MAC protocol, that is, Carrier Sense Multiple Access (CSMA). Member nodes compute Received Signal Strength Indication (RSSI) for the selection of CHs. Time Division Multiple Access (TDMA) schedules are formed by CH for accompanying member nodes in the cluster. Member nodes communicate with CH in the allotted time slots and remain in sleeping mode during unallocated time slots.


#### 3.2.4. Cluster Head Replacement Scheme

In most of the hierarchical routing protocols like LEACH, the cluster changes in every round, and once a sensor node is selected as CH, it will never get another chance to become CH in the upcoming 1/p rounds. In every round, CHs are selected and the process for the formation of the cluster is repeated. In EE-MRP an efficient CH replacement scheme is adopted. The flow diagram of CHs replacement scheme is shown in Figure 4. In it a threshold level is used for the replacement of CHs, if the energy level of existing CHs is more than the predefined threshold then existing CH will remain until it crosses the threshold limit. When CH energy becomes lower than the threshold limit, then the availability flag for that sensor node is set to “0,” which means that this sensor node is not available to be elected as CH; this ensures that any retired CH may not trigger the next round of CH change. The CH selection range is limited to the smallest range which applies to this very CH and its members. By using this efficient CHs replacement mechanism, unnecessary energy usage in the process of routing packets for new CHs and for cluster formation can be avoided.Figure 4
Cluster head replacement flowchart.


#### 3.2.5. Steady-State Phase

The communication paradigm is shown in Figure5. After selection of CHs and allocation of TDMA slots, the process of steady-state phase begins. On the basis of TDMA protocol, communication is started between the sensor node and their respective CH, in their predefined allocated time slots. During the unallocated time slots, sensor nodes remain in sleep mode. By using this approach, better energy efficiency is achieved. The CHs perform aggregation on the collected data and forward it to the forwarder node or BS according to its segment number. Forwarder node also performs aggregation on the collected data and then transmits to the BS. Figure 6 shows the flowchart of the routing algorithm.Figure 5
Communication paradigm.Figure 6
Flowchart of routing algorithm.The communication algorithm works on the basis of three stagesS1,S2andS3. The sensor nodes belong to stage S1 and send the collected data to the CHs and CHs perform aggregation on the collected data and then send it to the BS. The sensor nodes belong to stage S2 and send the collected data directly to forwarder node and after aggregation forwarder node send the collected data to the BS. The sensor nodes belong to stage S3 and send the collected data to CHs after aggregation CHs send collected data to forwarder node and after aggregation forwarder node sends the collected data to BS.


## 3.1. Energy Model

It is the fact that the energy available to the sensor nodes is not only limited that it may diminish very easily if it is not properly managed. The main reasons for the consumption of energy in wireless sensor networks are communication and processing, with communication being the main responsible for the consumption of energy. First-order radio model [1, 2] is used for the energy model of sensor nodes. As shown in Figure 1, energy model consists of three main modules: receiver, transmitter, and power amplifier. The receiver consumes energy to run the receiver circuitry at the time of reception of data, and the transmitter consumes energy to run the power amplifier circuitry and transmitter circuitry at the time of transmission of data. Energy dissipation for transmitter and receiver is represented by Eelec and energy dissipation for transmit amplifier is represented by Eamp.Figure 1
Radio communication model.There are two transmission models: transmission model for free space and two-ray ground [32, 33]. In free space transmission, there is a direct line of sight path between the transmitting and the receiving nodes. In two-ray ground transmission model, the transmission between transmitting and the receiving nodes is not direct and the electromagnetic wave reached at the receiver from different paths at different times. The energy consumed for the transmission of l bits data packet, with distance “d” and energy consumed for the reception of “l” bits data by the receiver nodes, is represented by (1)ETxl,d=Eelec×l+Eamp×l×d2ERxl=Eelec×l.Two different levels of power amplification for communication signals are introduced by MODLEACH [21], which is used on the basis of transmission nature. Equations (2) show the amplification levels for different communications on the basis of type and distance between communication devices. As compare to BS to cluster transmission, for intracluster transmission, lesser energy amplification level is used. Apart from energy saving benefits, collisions are reduced by the use of multiple power levels, and the number of packet drops and interference with other signals are also reduced.(2)Energy  Amplification  levelCH  to  BS/Forwarderd≥d0Eafs=10pJbit/m2Energy  Amplification  levelCH  to  BS/Forwarderd≤d0Eamp=0.0013pJbit/m2Energy  Amplification  levelIntra  Cluster  Com.d≥d1Eafs1=Eafs10Energy  Amplification  levelIntra  Cluster  Com.d≤d1Eamp1=Eamp10.Transmission within a cluster is called intracluster communication. In it, sensor nodes sense data from the environment and send the collected data to the CH. Minimum amplification energy is required for intracluster communication.


## 3.2. Design of Energy-Efficient Multistage Routing Protocol (EE-MRP)

The fundamental theme of our proposed routing protocol is the energy efficiency in larger network field of wireless sensor networks, where data is extremely interrelated and the requirement of end user is an only high-level function of data that contains a collection of events collected from the environment. The clustering hierarchical approach, efficient CH selection algorithm, and optimized routing algorithm are essential to design efficient solution for larger scale networks [33, 34]. The architectural design of our proposed routing protocol is shown in Figure 2. In our proposed routing protocol, homogeneous sensor nodes are randomly placed in the network field. Forwarder node is placed in the field where it may be maximum involved in the communication process. BS is placed outside of the network field.Figure 2
Basic architecture of EE-MRP.


### 3.2.1. Setup Phase

In this phase, the network field is divided into three logical stages (S1, S2, and S3) on the basis of sensor nodes located in the network field. BS is responsible for the division of network field into three logical stages. S1 and S3 have clustered regions and S2 is nonclustered region. Sensor nodes in S1 send data to the CHs, aggregation is done by CHs, and then aggregated data is forwarded to BS. Sensor nodes in S2 send data to the forwarder node, which performs aggregation on the collected data and then aggregated data is forwarded to BS. The sensor nodes which belonged to S3 also sends collected data to CHs and after aggregation, and CHs send to the forwarder node. The forwarder node then sends the collected data to the BS. By adding the forwarder node in the communication infrastructure, the distance between communicating nodes becomes less and energy consumption becomes less as compared to direct communication between CHs and BS.


### 3.2.2. Cluster Formation

In most of the cluster-based routing protocols, clusters are formed in the network field and CHs are randomly divided in the entire network field. In it, there are chances that CHs are not uniformly distributed in the network field. Some portion of the network may get more CHs and some portion may get lesser CHs. Due to this problem sensor nodes in that portion of network field may expire earlier and a part of the network becomes isolated. In EE-MRP initially, BS divides the network field into multiple logical segments. Then in each segment, CHs are selected. By using this mechanism CHs are evenly distributed in each segment of the network field. This cluster formation strategy increased the overall lifetime of the network. On the basis of location information, segment identification numbers are allotted to sensor nodes; therefore, sensor nodes can only join CHs located in their own segment. The cluster formation flow diagram is shown in Figure3. Once CHs are selected, then CHs broadcast the invitation message to normal nodes in its area to join CH and become member node. Normal sensor nodes wait for invitation message from CHs in their area, and sensor nodes send join message to the nearest CH, on the basis of distance information.Figure 3
Cluster formation flowchart.


### 3.2.3. Cluster Head Selection

Later to cluster formation, each node takes a decision whether or not to serve as a CH for the existing round. Every sensor node elects itself as a CH on the basis of the desired ratio of CHs and the status of eligibility flag to become CH. For instance, noden chooses a random number ranging from 0 to 1. The node will become CH if the threshold T(n) is greater than a number. Following formula is used for the calculation of T(n) [1, 11, 21].(3)Tn=fx=P1-P∗rmod⁡1/P,ifn∈G,0,otherwise,wheren is total number of sensor nodes.P is preferred the percentage of CH.r is current round.G is set of sensor nodes eligible to become CH.Selected CHs broadcast their status to other nodes via MAC protocol, that is, Carrier Sense Multiple Access (CSMA). Member nodes compute Received Signal Strength Indication (RSSI) for the selection of CHs. Time Division Multiple Access (TDMA) schedules are formed by CH for accompanying member nodes in the cluster. Member nodes communicate with CH in the allotted time slots and remain in sleeping mode during unallocated time slots.


### 3.2.4. Cluster Head Replacement Scheme

In most of the hierarchical routing protocols like LEACH, the cluster changes in every round, and once a sensor node is selected as CH, it will never get another chance to become CH in the upcoming 1/p rounds. In every round, CHs are selected and the process for the formation of the cluster is repeated. In EE-MRP an efficient CH replacement scheme is adopted. The flow diagram of CHs replacement scheme is shown in Figure 4. In it a threshold level is used for the replacement of CHs, if the energy level of existing CHs is more than the predefined threshold then existing CH will remain until it crosses the threshold limit. When CH energy becomes lower than the threshold limit, then the availability flag for that sensor node is set to “0,” which means that this sensor node is not available to be elected as CH; this ensures that any retired CH may not trigger the next round of CH change. The CH selection range is limited to the smallest range which applies to this very CH and its members. By using this efficient CHs replacement mechanism, unnecessary energy usage in the process of routing packets for new CHs and for cluster formation can be avoided.Figure 4
Cluster head replacement flowchart.


### 3.2.5. Steady-State Phase

The communication paradigm is shown in Figure5. After selection of CHs and allocation of TDMA slots, the process of steady-state phase begins. On the basis of TDMA protocol, communication is started between the sensor node and their respective CH, in their predefined allocated time slots. During the unallocated time slots, sensor nodes remain in sleep mode. By using this approach, better energy efficiency is achieved. The CHs perform aggregation on the collected data and forward it to the forwarder node or BS according to its segment number. Forwarder node also performs aggregation on the collected data and then transmits to the BS. Figure 6 shows the flowchart of the routing algorithm.Figure 5
Communication paradigm.Figure 6
Flowchart of routing algorithm.The communication algorithm works on the basis of three stagesS1,S2andS3. The sensor nodes belong to stage S1 and send the collected data to the CHs and CHs perform aggregation on the collected data and then send it to the BS. The sensor nodes belong to stage S2 and send the collected data directly to forwarder node and after aggregation forwarder node send the collected data to the BS. The sensor nodes belong to stage S3 and send the collected data to CHs after aggregation CHs send collected data to forwarder node and after aggregation forwarder node sends the collected data to BS.


## 3.2.1. Setup Phase

In this phase, the network field is divided into three logical stages (S1, S2, and S3) on the basis of sensor nodes located in the network field. BS is responsible for the division of network field into three logical stages. S1 and S3 have clustered regions and S2 is nonclustered region. Sensor nodes in S1 send data to the CHs, aggregation is done by CHs, and then aggregated data is forwarded to BS. Sensor nodes in S2 send data to the forwarder node, which performs aggregation on the collected data and then aggregated data is forwarded to BS. The sensor nodes which belonged to S3 also sends collected data to CHs and after aggregation, and CHs send to the forwarder node. The forwarder node then sends the collected data to the BS. By adding the forwarder node in the communication infrastructure, the distance between communicating nodes becomes less and energy consumption becomes less as compared to direct communication between CHs and BS.


## 3.2.2. Cluster Formation

In most of the cluster-based routing protocols, clusters are formed in the network field and CHs are randomly divided in the entire network field. In it, there are chances that CHs are not uniformly distributed in the network field. Some portion of the network may get more CHs and some portion may get lesser CHs. Due to this problem sensor nodes in that portion of network field may expire earlier and a part of the network becomes isolated. In EE-MRP initially, BS divides the network field into multiple logical segments. Then in each segment, CHs are selected. By using this mechanism CHs are evenly distributed in each segment of the network field. This cluster formation strategy increased the overall lifetime of the network. On the basis of location information, segment identification numbers are allotted to sensor nodes; therefore, sensor nodes can only join CHs located in their own segment. The cluster formation flow diagram is shown in Figure3. Once CHs are selected, then CHs broadcast the invitation message to normal nodes in its area to join CH and become member node. Normal sensor nodes wait for invitation message from CHs in their area, and sensor nodes send join message to the nearest CH, on the basis of distance information.Figure 3
Cluster formation flowchart.


## 3.2.3. Cluster Head Selection

Later to cluster formation, each node takes a decision whether or not to serve as a CH for the existing round. Every sensor node elects itself as a CH on the basis of the desired ratio of CHs and the status of eligibility flag to become CH. For instance, noden chooses a random number ranging from 0 to 1. The node will become CH if the threshold T(n) is greater than a number. Following formula is used for the calculation of T(n) [1, 11, 21].(3)Tn=fx=P1-P∗rmod⁡1/P,ifn∈G,0,otherwise,wheren is total number of sensor nodes.P is preferred the percentage of CH.r is current round.G is set of sensor nodes eligible to become CH.Selected CHs broadcast their status to other nodes via MAC protocol, that is, Carrier Sense Multiple Access (CSMA). Member nodes compute Received Signal Strength Indication (RSSI) for the selection of CHs. Time Division Multiple Access (TDMA) schedules are formed by CH for accompanying member nodes in the cluster. Member nodes communicate with CH in the allotted time slots and remain in sleeping mode during unallocated time slots.


## 3.2.4. Cluster Head Replacement Scheme

In most of the hierarchical routing protocols like LEACH, the cluster changes in every round, and once a sensor node is selected as CH, it will never get another chance to become CH in the upcoming 1/p rounds. In every round, CHs are selected and the process for the formation of the cluster is repeated. In EE-MRP an efficient CH replacement scheme is adopted. The flow diagram of CHs replacement scheme is shown in Figure 4. In it a threshold level is used for the replacement of CHs, if the energy level of existing CHs is more than the predefined threshold then existing CH will remain until it crosses the threshold limit. When CH energy becomes lower than the threshold limit, then the availability flag for that sensor node is set to “0,” which means that this sensor node is not available to be elected as CH; this ensures that any retired CH may not trigger the next round of CH change. The CH selection range is limited to the smallest range which applies to this very CH and its members. By using this efficient CHs replacement mechanism, unnecessary energy usage in the process of routing packets for new CHs and for cluster formation can be avoided.Figure 4
Cluster head replacement flowchart.


## 3.2.5. Steady-State Phase

The communication paradigm is shown in Figure5. After selection of CHs and allocation of TDMA slots, the process of steady-state phase begins. On the basis of TDMA protocol, communication is started between the sensor node and their respective CH, in their predefined allocated time slots. During the unallocated time slots, sensor nodes remain in sleep mode. By using this approach, better energy efficiency is achieved. The CHs perform aggregation on the collected data and forward it to the forwarder node or BS according to its segment number. Forwarder node also performs aggregation on the collected data and then transmits to the BS. Figure 6 shows the flowchart of the routing algorithm.Figure 5
Communication paradigm.Figure 6
Flowchart of routing algorithm.The communication algorithm works on the basis of three stagesS1,S2andS3. The sensor nodes belong to stage S1 and send the collected data to the CHs and CHs perform aggregation on the collected data and then send it to the BS. The sensor nodes belong to stage S2 and send the collected data directly to forwarder node and after aggregation forwarder node send the collected data to the BS. The sensor nodes belong to stage S3 and send the collected data to CHs after aggregation CHs send collected data to forwarder node and after aggregation forwarder node sends the collected data to BS.


## 4. Performance Evaluation

Simulations are done using MATLAB R2013b (8.2.0.701). MATLAB provides an interactive environment for the deployment of algorithms, virtualization of data, analysis of data, and numeric computation using a high-level technical computing language. In order to simulate our proposed routing protocol, homogeneous sensor nodes are randomly deployed. The wireless communication channel which is used between the sensor nodes deployed in the network depends on the transmission range and distance.


### 4.1. Network Scenario Assumptions and Parameters

It is assumed in the simulation that sensor nodes are densely and randomly scattered in a two-dimensional square field. Figure7 shows a sample of randomly deployed sensor nodes used in our experiments. Sensor nodes are randomly deployed in the area of 150 m × 150 m. BS and forwarder are located at (75,170) and (75,65), respectively. Different samples of randomly deployed sensor nodes are used for each simulation and the results discussed in the next sections are the average values of 25 simulations.Figure 7
Random deployment of sensor nodes.The following properties are applied on the WSN.(i)
Sensor nodes are energy constrained, that is, not rechargeable, and always contain data to send.(ii)
There is only one BS, which is deployed outside of the network field.(iii)
There is only one forwarder in the field, which has a longer lifetime than normal sensor nodes and whose battery can be replaced.(iv)
A sensor node is declared as a dead node when it is unable to transmit data.(v)
It is assumed that the probability of interference and signal collision is ignorable.The parameters utilized in the simulation are shown in Table1.Table 1
Network parameters.
Parameters
Value
Network area (meter)
150 × 150
Number of nodes (N)
100
BS location
(
75,170
)
Forwarder location
(
75,65
)
Initial energy (E0)
0.5 J
E
T
X
50 nJ
E
R
X
50 nJ
E
a
m
p  (cluster to BS/forwarder)
0.0013 pJ/bit/m4
E
f
s  (cluster to BS/forwarder)
10 pJ/bit/m2
E
a
m
p
1  (intracluster comm.)
Eamp/10
E
f
s
1  (intracluster comm.)
Efs/10
E
d
a
5 nJ/bit
Packet size
4000 bits
Number of rounds
3000


#### 4.1.1. Evaluation Parameters

The performance of hierarchical routing protocols for WSNs is evaluated on the basis of following terms.Stability Period. It is the time period until the first sensor node becomes dead in the network field. The time interval between the startup of the WSNs operation and the time slot when first sensor node becomes dead is called stability period.Instability Period. The time interval between time slot when first sensor node becomes dead and the time slot when last sensor node becomes dead is called instability period.A Number of Alive Nodes. These are the total number of sensor nodes, those have not yet exhausted all of their energy and have enough energy to continue communication operation.A Number of Dead Nodes. These are the total number of sensor nodes, those have exhausted all of their energy and did not have enough energy to continue communication operation.Throughput. The rate of data sent from sensor nodes to CHs, from sensor nodes to forwarder, from CHs to forwarder, from CHs to BS, and from forwarder to BS, is collectively known as throughput.Reliability. The comparison between stability period and instability period characterizes the strength of reliability. The longer stability period and shorter instability period show better reliability.Overall Network Lifetime. The time period from the start of the network operation up to the death of the last sensor node is called overall network lifetime.There is a trade-off between overall network lifetime and reliability. As overall network lifetime includes both stability period and instability period, therefore, WSN which has longer instability period is less stable but has longer overall network lifetime. On the other hand, WSN which has shorter instability period is more stable but has shorter overall network lifetime.


### 4.2. Simulation Results and Discussion

The simulation of our proposed routing protocol is done in comparison with LEACH [1] and MODLEACH [21], for the adherence of alive sensor nodes per round, dead sensor nodes per round, throughput, and overall network lifetime.Figure8 shows the number of alive nodes with respect to the number of rounds. It is shown that EE-MRP has comparatively more stability period than LEACH and MODLEACH. The first sensor node of EE-MRP becomes dead after approximately 1100 rounds while the first sensor node of LEACH and MODLEACH routing protocol becomes dead after approximately 580th round and 600th round, respectively. At 600th round, sensor nodes of both LEACH and MODLEACH routing protocol sharply start to become dead, and all sensor nodes of LEACH and MODLEACH become dead at 1300th round and 1500th round, respectively. The sensor nodes of EE-MRP start to become dead comparatively slowly after 1100th round and all sensor nodes become dead up to 2600th round.Figure 8
Total number of alive nodes in each round.The number of dead nodes with respect to the number of rounds is shown in Figure9. It is observed that LEACH routing protocol has the shortest stability period and also has shorter instability period than other two routing protocols. The instability period of EE-MRP is longer but has much longer overall network lifetime than LEACH and MODLEACH. As the instability period of EE-MRP is longer than both LEACH and MODLEACH therefore EE-MRP has comparatively less reliability.Figure 9
Total number of dead nodes in each round.The average residual energy of network with respect to a number of rounds is shown in Figure10. We have assumed that a sensor node has a maximum of 0.5-joule initial energy; therefore total energy for a network of 100 nodes is 50 joules. It is clearly observed in Figure 10 that energy dissipation of MODLEACH is less than LEACH. EE-MRP performs better in terms of energy dissipation per round and outperforms the LEACH and MODLEACH routing protocols.Figure 10
Analysis of remaining energy per round.Figure11 shows the number of packets received by BS with respect to the number of rounds. It shows that throughput of EE-MRP is significantly greater as compared to LEACH and MODLEACH. From the graph, it is depicted that EE-MRP has better throughput up to 580% as compared to LEACH routing protocol and up to 483% as compared to MODLEACH routing protocol.Figure 11
Comparative throughput.The proposed routing protocol performed better than competing protocols in terms of various evaluation parameters discussed in Section4.1.1. There are multiple reasons behind improved performance of proposed routing protocol. Firstly, efficient cluster head replacement mechanism avoids unnecessary repetition of CHs rotation. Secondly, use of forwarder node improves communication process. Thirdly, even distribution of CHs in the network field improves overall network lifetime and throughput. Fourthly, multistage transmission mechanism improves communication process and maximizes the stability period. All these factors contribute to the achievement of energy efficiency in our proposed routing protocol.


## 4.1. Network Scenario Assumptions and Parameters

It is assumed in the simulation that sensor nodes are densely and randomly scattered in a two-dimensional square field. Figure7 shows a sample of randomly deployed sensor nodes used in our experiments. Sensor nodes are randomly deployed in the area of 150 m × 150 m. BS and forwarder are located at (75,170) and (75,65), respectively. Different samples of randomly deployed sensor nodes are used for each simulation and the results discussed in the next sections are the average values of 25 simulations.Figure 7
Random deployment of sensor nodes.The following properties are applied on the WSN.(i)
Sensor nodes are energy constrained, that is, not rechargeable, and always contain data to send.(ii)
There is only one BS, which is deployed outside of the network field.(iii)
There is only one forwarder in the field, which has a longer lifetime than normal sensor nodes and whose battery can be replaced.(iv)
A sensor node is declared as a dead node when it is unable to transmit data.(v)
It is assumed that the probability of interference and signal collision is ignorable.The parameters utilized in the simulation are shown in Table1.Table 1
Network parameters.
Parameters
Value
Network area (meter)
150 × 150
Number of nodes (N)
100
BS location
(
75,170
)
Forwarder location
(
75,65
)
Initial energy (E0)
0.5 J
E
T
X
50 nJ
E
R
X
50 nJ
E
a
m
p  (cluster to BS/forwarder)
0.0013 pJ/bit/m4
E
f
s  (cluster to BS/forwarder)
10 pJ/bit/m2
E
a
m
p
1  (intracluster comm.)
Eamp/10
E
f
s
1  (intracluster comm.)
Efs/10
E
d
a
5 nJ/bit
Packet size
4000 bits
Number of rounds
3000


### 4.1.1. Evaluation Parameters

The performance of hierarchical routing protocols for WSNs is evaluated on the basis of following terms.Stability Period. It is the time period until the first sensor node becomes dead in the network field. The time interval between the startup of the WSNs operation and the time slot when first sensor node becomes dead is called stability period.Instability Period. The time interval between time slot when first sensor node becomes dead and the time slot when last sensor node becomes dead is called instability period.A Number of Alive Nodes. These are the total number of sensor nodes, those have not yet exhausted all of their energy and have enough energy to continue communication operation.A Number of Dead Nodes. These are the total number of sensor nodes, those have exhausted all of their energy and did not have enough energy to continue communication operation.Throughput. The rate of data sent from sensor nodes to CHs, from sensor nodes to forwarder, from CHs to forwarder, from CHs to BS, and from forwarder to BS, is collectively known as throughput.Reliability. The comparison between stability period and instability period characterizes the strength of reliability. The longer stability period and shorter instability period show better reliability.Overall Network Lifetime. The time period from the start of the network operation up to the death of the last sensor node is called overall network lifetime.There is a trade-off between overall network lifetime and reliability. As overall network lifetime includes both stability period and instability period, therefore, WSN which has longer instability period is less stable but has longer overall network lifetime. On the other hand, WSN which has shorter instability period is more stable but has shorter overall network lifetime.


## 4.1.1. Evaluation Parameters

The performance of hierarchical routing protocols for WSNs is evaluated on the basis of following terms.Stability Period. It is the time period until the first sensor node becomes dead in the network field. The time interval between the startup of the WSNs operation and the time slot when first sensor node becomes dead is called stability period.Instability Period. The time interval between time slot when first sensor node becomes dead and the time slot when last sensor node becomes dead is called instability period.A Number of Alive Nodes. These are the total number of sensor nodes, those have not yet exhausted all of their energy and have enough energy to continue communication operation.A Number of Dead Nodes. These are the total number of sensor nodes, those have exhausted all of their energy and did not have enough energy to continue communication operation.Throughput. The rate of data sent from sensor nodes to CHs, from sensor nodes to forwarder, from CHs to forwarder, from CHs to BS, and from forwarder to BS, is collectively known as throughput.Reliability. The comparison between stability period and instability period characterizes the strength of reliability. The longer stability period and shorter instability period show better reliability.Overall Network Lifetime. The time period from the start of the network operation up to the death of the last sensor node is called overall network lifetime.There is a trade-off between overall network lifetime and reliability. As overall network lifetime includes both stability period and instability period, therefore, WSN which has longer instability period is less stable but has longer overall network lifetime. On the other hand, WSN which has shorter instability period is more stable but has shorter overall network lifetime.


## 4.2. Simulation Results and Discussion

The simulation of our proposed routing protocol is done in comparison with LEACH [1] and MODLEACH [21], for the adherence of alive sensor nodes per round, dead sensor nodes per round, throughput, and overall network lifetime.Figure8 shows the number of alive nodes with respect to the number of rounds. It is shown that EE-MRP has comparatively more stability period than LEACH and MODLEACH. The first sensor node of EE-MRP becomes dead after approximately 1100 rounds while the first sensor node of LEACH and MODLEACH routing protocol becomes dead after approximately 580th round and 600th round, respectively. At 600th round, sensor nodes of both LEACH and MODLEACH routing protocol sharply start to become dead, and all sensor nodes of LEACH and MODLEACH become dead at 1300th round and 1500th round, respectively. The sensor nodes of EE-MRP start to become dead comparatively slowly after 1100th round and all sensor nodes become dead up to 2600th round.Figure 8
Total number of alive nodes in each round.The number of dead nodes with respect to the number of rounds is shown in Figure9. It is observed that LEACH routing protocol has the shortest stability period and also has shorter instability period than other two routing protocols. The instability period of EE-MRP is longer but has much longer overall network lifetime than LEACH and MODLEACH. As the instability period of EE-MRP is longer than both LEACH and MODLEACH therefore EE-MRP has comparatively less reliability.Figure 9
Total number of dead nodes in each round.The average residual energy of network with respect to a number of rounds is shown in Figure10. We have assumed that a sensor node has a maximum of 0.5-joule initial energy; therefore total energy for a network of 100 nodes is 50 joules. It is clearly observed in Figure 10 that energy dissipation of MODLEACH is less than LEACH. EE-MRP performs better in terms of energy dissipation per round and outperforms the LEACH and MODLEACH routing protocols.Figure 10
Analysis of remaining energy per round.Figure11 shows the number of packets received by BS with respect to the number of rounds. It shows that throughput of EE-MRP is significantly greater as compared to LEACH and MODLEACH. From the graph, it is depicted that EE-MRP has better throughput up to 580% as compared to LEACH routing protocol and up to 483% as compared to MODLEACH routing protocol.Figure 11
Comparative throughput.The proposed routing protocol performed better than competing protocols in terms of various evaluation parameters discussed in Section4.1.1. There are multiple reasons behind improved performance of proposed routing protocol. Firstly, efficient cluster head replacement mechanism avoids unnecessary repetition of CHs rotation. Secondly, use of forwarder node improves communication process. Thirdly, even distribution of CHs in the network field improves overall network lifetime and throughput. Fourthly, multistage transmission mechanism improves communication process and maximizes the stability period. All these factors contribute to the achievement of energy efficiency in our proposed routing protocol.


## 5. Conclusion and Future Work

The WSNs have many resource limitations; however, the energy limitation of the sensor nodes is one of the important characteristics among all due to its attachment to the life of the sensor nodes. Routing protocol plays an important role in optimizing energy consumption of the sensor nodes and in the maximization of the overall network lifetime. Therefore, efficient utilization of the available resources is the primary concern in the development of routing protocols for WSNs. We have developed an efficient clustering-based energy-efficient multistage routing protocol that meets the challenges of energy in WSNs. By dividing the network field into multiple stages, the CHs are evenly distributed which increases the throughput of the network and increases the overall lifetime of the network. Unnecessary rotation of CHs is avoided by adopting threshold based CHs selection mechanism. In order to minimize the distance between communicating nodes and CHs, the concept of forwarder node is introduced, which minimizes the routing distance between communicating nodes, CHs and BS. Multiple power amplification levels are used for intracluster communication and for communication between CHs and forwarder or BS. As less amplification power level is required for the intracluster transmission, by adopting multiple amplification power levels, unnecessary consumption of energy is avoided.The performance of EE-MRP is evaluated using MATLAB simulation tool. Energy efficiency, throughput, and network lifetime are described as the performance metrics, used for comparison between our proposed routing protocol (EE-MRP) and existing routing protocols (LEACH and MODLEACH). It is clearly shown in the simulation results that EE-MRP surpassed the existing routing protocols in most of the performance metrics. In addition, with the help of these results, it has been verified that EE-MRP have adopted efficient CHs selection scheme and by using forwarder based routing strategy, overall lifetime of WSN has been improved significantly. This research work has opened numerous exigent research directions, which can be further explored. The proposed solutions have mostly addressed the energy efficiency in routing protocol, which can be further extended for the improvement of energy efficiency in MAC layer. The energy efficiency of the routing protocol can be further increased by making it application-specific like temperature monitoring and using the threshold level for the transmission of data between sensor nodes and CHs, CHs to BS, and CHs to forwarder node, which minimizes the communication for data transmission, and energy consumption during communication can be saved. This research work may further be extended by modeling and implementation of QoS in WSNs [35, 36].



---

*Source: 6839671-2018-01-08.xml*