# Tree-Based Multihop Routing Method for Energy Efficiency of Wireless Sensor Networks

Authors: Jin Yong; Zhou Lin; Wei Qian; Bai Ke; Wang Chen; Li Ji-fang
Journal: Journal of Sensors
 (2021)

---

## Abstract

In wireless sensor networks (WSNs), due to the limited energy of sensor nodes, how to design efficient hierarchical routing algorithms to balance network resources and extend network life is an important problem to be solved. Aiming at the problems such as random selection of cluster head, redundancy of working node, and construction of cluster head transmission path, which affect network energy consumption, this paper proposes a multihop routing algorithm based on path tree (MHRA-PT) to optimize the network energy. Firstly, some nodes are those close to the base station and have large remaining energy which are selected to construct a cluster head set. Then, after clustering, each cluster is divided into different regions, and in each region, nodes with residual energy greater than the average residual energy of the cluster are selected as a working node. Finally, the cluster heads are sorted according to their distance from base station, and the next hop node is selected for each cluster head in turn until a path tree rooted at base station is formed completely, leading to data transmission from working node to base station. Simulation results show that the proposed algorithm can effectively reduce network energy consumption, balance network resources, and prolong network life cycle.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have been widely used in many fields including environmental monitoring, smart space, military reconnaissance, and medical systems [1–4]. However, how to efficiently use energy of the network node is still a valuable problem to be studied in WSNs [5, 6]. Cluster routing algorithms are effective methods of energy management related to WSNs [7, 8], the most classic of which is the LEACH algorithm proposed by Daanoune et al. [9]. This algorithm divides nodes in the network into cluster heads and cluster members by clustering, which can fully use network node resources and effectively lengthen the life cycle of the network. In addition, algorithms such as PEGASIS [10] and TEEN [11] employed clustering idea to reduce the number of nodes those directly communicate with base station. By periodically changing cluster head, the energy consumption is balanced among nodes in the network; it is used to prolong the network life cycle.Although the LEACH algorithm has good energy saving effects, it still has some problems. For example, the LEACH algorithm completely relies on a random number to select cluster heads. As a result, some nodes with less residual energy may be selected as cluster heads for several times, resulting in the death of those nodes. In addition, cluster head or working node that has a long distance from the base station may consume a large amount of energy in transmitting.


## 2. Related Work

Many research works have been done to improve the LEACH algorithm. Using the isolated node method, Leu et al. proposed a clustering routing algorithm to prolong the network life cycle [12]. Leu et al.’s algorithm constructs a cluster head selection threshold according to the node’s own remaining energy and the average remaining energy of all nodes and assigns nodes with more energy as the cluster head preferentially, then uses distance between isolated nodes and base station to judge whether isolated nodes should directly communicate with the base station or else. Thus, premature death of cluster heads and isolated nodes due to excessive energy consumption may be avoided. Neamatollahi et al. developed a clustering routing algorithm using the mechanism of cluster head rotation [13]. The algorithm utilizes the current remaining energy of the cluster heads to determine whether to reselect the cluster head. It not only ensures that the cluster head has enough energy but also reduces the energy consumption caused by repeated clustering. However, in literatures [12, 13], the way in which the cluster head transmits data to the base station is single-hop transmission. If the distance between the cluster head and the base station is far, the cluster head will die prematurely because of large energy consumption corresponding to long distance transmission.To solve the problem of energy consumption caused by long distance communication between cluster head and base station, the literature [14] proposed an IMHT-LEACH algorithm by combining the LEACH algorithm with multihop strategy. This algorithm assigns the different level of cluster heads according to the distance between the cluster heads and the base station. The low-level cluster heads nearby the base station are selected as the relay nodes, and the network energy consumption is reduced by the multihop transmission method. However, this algorithm fastens the structure of WSNs and may reduce the diversity of cluster head alternative paths. Arora et al. proposed a distributed multihop routing approach (DMATEB) to tackle this problem [15]. The DMATEB algorithm marks the cluster head that is closer to the base station than the current cluster head as neighbor cluster heads and then selects the cluster head with the largest remaining energy in the neighbor cluster heads as the next hop, which effectively reduces the network energy consumption. However, Arora et al.’s algorithm does not consider the transmission energy consumption between cluster heads. If some cluster heads far from base station are selected as the relay, they will still consume a lot of energy too. In short, the existing algorithms are mainly focused on saving energy of WSNs, while balance energy consume of WSNs is rarely considered.


## 3. Contribution

In this paper, inspired by the idea of LEACH, this paper proposes a multihop routing algorithm using path tree (MHRA-PT) to optimize network energy. The MHRA-PT algorithm is composed of three stages such as the cluster heads selecting, working nodes assigning, and transmission paths generating. In WSNs, the proposed algorithm can reduce network energy consumption and balance energy consumption of different nodes, thus significantly improving the energy utilization rate and leading to life cycle extension of WSNs. Overall, the main contributions of this paper can be summarized as follows:(i)
A cluster head selection strategy with network energy balancing is developed. This strategy not only avoids the data inverse transmission caused by cluster heads far from the base station but also prevents cluster heads with less residual energy premature death caused by energy consumption in data transmitting. Thus, MHRA-PT effectively prolongs the network life cycle(ii)
A working node selection strategy based on cluster region division is developed to construct the set of working nodes. This strategy can dynamically wake up nodes with more residual energy to perform some tasks, thus avoiding network resource waste caused by using excessive node of WSNs. Thus, MHRA-PT can effectively save the energy of WSNs(iii)
In traditional data transmission, multiple cluster heads transmit data to the base station by forming a data link. Thus, faults of any cluster head in the data link may lead to data transmission failure. To improve the stability of data transmission, MHRA-PT assigns the path weight of the path tree according to the directivity of the cluster head data transmission, the residual energy of the cluster head, the data transmission energy consumption, and so onThe remainder of this work is organized as follows. Section4 introduces the system model and conventional method, including the network model, improved energy consumption model, and main steps of the LEACH algorithm. Section 5 describes the implementation process of the MHRA-PT algorithm in detail. To evaluate the proposed algorithm, some simulation results are presented in Section 6; besides, some analyses are done in this section. Section 7 summarizes all works of this paper.


## 4. System Model and Conventional Method

### 4.1. System Model

#### 4.1.1. Network Model

Assume thatN sensor nodes are randomly deployed in the M×M square area. Base station (BS) is located at the center of the square area. The network model is shown in Figure 1.Figure 1
Network model.Moreover, three assumptions related to the model of WSNs are as follows:(1)
Each sensor node has limited energy, and their initial energy is the same(2)
Each sensor node has its own ID, and their positions are fixed after deployment(3)
The location of the base station is fixed, its energy is unlimited, and its information processing and storage capabilities can always meet the network requirements


#### 4.1.2. Energy Consumption Model

The energy of sensor nodes is mainly used to transmit data, receive data, and process data [16]. Figure 2 shows the energy consumption model of sensor.Figure 2
Energy consumption model of sensor.LetETX and ERX denote the energy consumption of sensor related to transmitting data and receiving data, respectively. Similar to the model of sensor energy. Consumption described in [17], ETX can be defined as(1)ETXk,d=ETX‐eleck+ETX‐ampk,d=kEelec+kεfsd2,d≤d0,kEelec+kεmpd4,otherwise,(2)ERXk=ERX‐eleck=kEelec,where ETX‐elec, ERX‐elec, and ETX‐amp are the energy consumption of transmitter, energy consumption of receiver, and energy consumption of amplifier, respectively; εfs and εmp are coefficient amplify of free space and coefficient amplify of multipath, respectively; Eelec is the energy consumption of 1-bit data processing related to node, k is bits of data; d is the distance between the transmitter and receiver; and d0 is the critical communication distance.


### 4.2. LEACH Algorithm

The LEACH algorithm divides the working process into several rounds, and each round is composed of clustering stage and data transmission stage. Details of LEACH are described as follows.


#### 4.2.1. Clustering Stage

In the LEACH algorithm, whether or not, a nodeniinside a cluster to be assigned as cluster head is determined by cluster head selection thresholdTni described by equation (3). Namely, a node ni is assigned as a cluster head if Tni is greater than a uniformly distributed random number between 0 and 1.(3)Tni=p1−prmod1/p,ni∈G,0,otherwise,where p is the percentage of cluster head in the total number of nodes in the WSNs, r is the number of running rounds, and G is the noncluster head set in the cycle of 1/p.Once a node is assigned as a cluster head, it should broadcast signal, and each noncluster head according to the received signal strength joins in the nearest cluster.


#### 4.2.2. Data Transmission Stage

In the data transmission stage, each node within cluster sends monitoring data to the cluster head in sequence. After fusing the received data, the cluster head transmits data to the base station.


## 4.1. System Model

### 4.1.1. Network Model

Assume thatN sensor nodes are randomly deployed in the M×M square area. Base station (BS) is located at the center of the square area. The network model is shown in Figure 1.Figure 1
Network model.Moreover, three assumptions related to the model of WSNs are as follows:(1)
Each sensor node has limited energy, and their initial energy is the same(2)
Each sensor node has its own ID, and their positions are fixed after deployment(3)
The location of the base station is fixed, its energy is unlimited, and its information processing and storage capabilities can always meet the network requirements


### 4.1.2. Energy Consumption Model

The energy of sensor nodes is mainly used to transmit data, receive data, and process data [16]. Figure 2 shows the energy consumption model of sensor.Figure 2
Energy consumption model of sensor.LetETX and ERX denote the energy consumption of sensor related to transmitting data and receiving data, respectively. Similar to the model of sensor energy. Consumption described in [17], ETX can be defined as(1)ETXk,d=ETX‐eleck+ETX‐ampk,d=kEelec+kεfsd2,d≤d0,kEelec+kεmpd4,otherwise,(2)ERXk=ERX‐eleck=kEelec,where ETX‐elec, ERX‐elec, and ETX‐amp are the energy consumption of transmitter, energy consumption of receiver, and energy consumption of amplifier, respectively; εfs and εmp are coefficient amplify of free space and coefficient amplify of multipath, respectively; Eelec is the energy consumption of 1-bit data processing related to node, k is bits of data; d is the distance between the transmitter and receiver; and d0 is the critical communication distance.


## 4.1.1. Network Model

Assume thatN sensor nodes are randomly deployed in the M×M square area. Base station (BS) is located at the center of the square area. The network model is shown in Figure 1.Figure 1
Network model.Moreover, three assumptions related to the model of WSNs are as follows:(1)
Each sensor node has limited energy, and their initial energy is the same(2)
Each sensor node has its own ID, and their positions are fixed after deployment(3)
The location of the base station is fixed, its energy is unlimited, and its information processing and storage capabilities can always meet the network requirements


## 4.1.2. Energy Consumption Model

The energy of sensor nodes is mainly used to transmit data, receive data, and process data [16]. Figure 2 shows the energy consumption model of sensor.Figure 2
Energy consumption model of sensor.LetETX and ERX denote the energy consumption of sensor related to transmitting data and receiving data, respectively. Similar to the model of sensor energy. Consumption described in [17], ETX can be defined as(1)ETXk,d=ETX‐eleck+ETX‐ampk,d=kEelec+kεfsd2,d≤d0,kEelec+kεmpd4,otherwise,(2)ERXk=ERX‐eleck=kEelec,where ETX‐elec, ERX‐elec, and ETX‐amp are the energy consumption of transmitter, energy consumption of receiver, and energy consumption of amplifier, respectively; εfs and εmp are coefficient amplify of free space and coefficient amplify of multipath, respectively; Eelec is the energy consumption of 1-bit data processing related to node, k is bits of data; d is the distance between the transmitter and receiver; and d0 is the critical communication distance.


## 4.2. LEACH Algorithm

The LEACH algorithm divides the working process into several rounds, and each round is composed of clustering stage and data transmission stage. Details of LEACH are described as follows.


### 4.2.1. Clustering Stage

In the LEACH algorithm, whether or not, a nodeniinside a cluster to be assigned as cluster head is determined by cluster head selection thresholdTni described by equation (3). Namely, a node ni is assigned as a cluster head if Tni is greater than a uniformly distributed random number between 0 and 1.(3)Tni=p1−prmod1/p,ni∈G,0,otherwise,where p is the percentage of cluster head in the total number of nodes in the WSNs, r is the number of running rounds, and G is the noncluster head set in the cycle of 1/p.Once a node is assigned as a cluster head, it should broadcast signal, and each noncluster head according to the received signal strength joins in the nearest cluster.


### 4.2.2. Data Transmission Stage

In the data transmission stage, each node within cluster sends monitoring data to the cluster head in sequence. After fusing the received data, the cluster head transmits data to the base station.


## 4.2.1. Clustering Stage

In the LEACH algorithm, whether or not, a nodeniinside a cluster to be assigned as cluster head is determined by cluster head selection thresholdTni described by equation (3). Namely, a node ni is assigned as a cluster head if Tni is greater than a uniformly distributed random number between 0 and 1.(3)Tni=p1−prmod1/p,ni∈G,0,otherwise,where p is the percentage of cluster head in the total number of nodes in the WSNs, r is the number of running rounds, and G is the noncluster head set in the cycle of 1/p.Once a node is assigned as a cluster head, it should broadcast signal, and each noncluster head according to the received signal strength joins in the nearest cluster.


## 4.2.2. Data Transmission Stage

In the data transmission stage, each node within cluster sends monitoring data to the cluster head in sequence. After fusing the received data, the cluster head transmits data to the base station.


## 5. The Proposed MHRA-PT Algorithm

Using models described in Sections4, this paper proposes the MHRA-PT algorithm to optimize and balance energy consumption of WSNs. The overall framework of the MHRA-PT algorithm is shown in Figure 3.Figure 3
Overall framework of MHRA-PT algorithm.According to the overall framework of MHRA-PT algorithm, some details related to the cluster head selection are discussed, the working node selection and data transmission path selection in this section.


### 5.1. Strategy for Cluster Head Selection

Cluster head selection is performed in the cluster routing algorithm based on the cluster head selection threshold. SupposeN sensor nodes are randomly distributed in the square area of SM. The optimal number of cluster head Kopt [18] and the optimal percentage of cluster head to the total number of all nodes Popt are shown in the following:(4)Popt=KoptN,Kopt=20.765N/2π.In equation (5), the cluster head selection threshold Tmni is constructed by probability Pb [10], fdni factor relating to distance between ni and base station, and remaining energy factor feni.(5)Tmni=αPb+βfdni⋅feni,ni∈G′,0,otherwise,where(6)Pb=Popt1−Poptrmod1/Popt,(7)fdni=dnbmax−dnbnidnbmax−dnbmin,(8)feni=ErniE0ni,where α and β are weight parameters of Tmni and, at the same time, α+β=1; dnbni≜ni−B2, B is the coordinate of base station, ni is the coordinate of node ni, dnbmax≜maxdnbni, and dnbmin≜mindnbni; and Erni is the remaining energy of ni, and E0ni is the initial energy of ni. Besides, G′ is the node set that has not been selected as the cluster head in the cycle of 1/Popt.Observing equations (4)–(8), it is obvious that some nodes with properties such as being closer to base station and larger remaining energy have large cluster head selection threshold, thus having greater probability of being selected as the cluster head. In addition, nodes selected as the cluster head are added to the cluster head set C, and the nodes not selected as the cluster head are added to the noncluster head set N.


### 5.2. Strategy for Working Node Selection

It is obvious that using all nodes in WSNs to work may consume excess energy. Therefore, it should partition each cluster to reducing number of working nodes while guaranteeing network coverage.An example is used to describe in Figure4 to illustrate the details of partition. Assume that the farthest distance between cluster head CH and cluster member CM is r and the maximum sensing radius of node is r/2. Thus, the cluster’s coverage area is a circle with the position of cluster head as the center and a radius r. Z1 is defined as the circular area with the position of cluster head as the center and r/2 as the radius; Z2 is the ring area with the position of cluster head as the center r/2 and r as the inner radii and outer radii, respectively. It can be found that the area of cluster may be divided into eight parts which are marked as ①~⑧, respectively.Figure 4
Area division within cluster.In Figure4, it is clear that sensing range of nodes in each part of Z1 areas and nodes in each part of Z2 areas can cover the entire cluster since the maximum sensing radius of node is r/2.So, it should, respectively, choose working nodes in each part of the entire cluster to guarantee sensing range of nodes covering the entire cluster. In addition, it can compare the remaining energyErnj of node nj with the average remaining energy Eavg of all nodes described in equation (9) to determine whether or not assign nodenjis the working node.(9)Eavg=∑nk∈CuErnkm.In equation (9), Cu is the set of all nodes within the cluster, Ernk is the remaining energy of node nk, m is the cardinal of the Cu. Specifically, if Ernj≥Eavg, the node nj joins in the working node set W. On the contrary, the node nj joins in the sleep node set S. Assuming the remaining energy of each node in a part of cluster less than Eavg, it should assign the node with the largest remaining energy as the working node.


### 5.3. Strategy for Data Transmission Path Selection

In the data transmission phase, multihop transmission strategy can be used to reduce energy consumption caused by long distance single-hop data transmission. This paper constructs path tree which assigns cluster head as the branch node so that each cluster head can transmit data to the base station along its branch path. The path tree between the base station and cluster head is shown in Figure5.Figure 5
Path tree constructed by base station and cluster head.Models of path tree construction are described in the following:(10)C0=CHii=1,⋯,C,(11)CHi−B2≤CHj−B2,∀i<j,where C0 is a new cluster head set by sorting the elements in the cluster head set C, C is the cardinal of C, CHi is the ith cluster head, CHi is the coordinate corresponding to CHi, and B is the coordinate corresponding to base station. It can conclude the details of path tree construction as follows. Firstly, sorting cluster head according to the distance dtoBS between cluster head and base station, cluster head should choose the cluster head closer to the base station as parent node. Secondly, it successively assigns the parent node to each cluster head according to ascending order of the distance dtoBS between the cluster head and the base station. Now, taking as an example (Figure 6), it chooses the cluster head CH1, CH2, and CH3 in C0 to display the details related to path tree construction.(Step 1)
Add first branch nodeCH1 of path tree and record path information.Figure 6
The process of path tree construction.According to equations (10) and (11), cluster head CH1 closest to the base station, so as described in equation (12) can directly choose the base station as the parent node of itself (Figure 6(b)). Meanwhile, as described in equations (13), (14), and (15),CH1records path information itself.(12)PCH1=BS,(13)EcoCH1,PCH1=EtrCH1,PE+EreCH1,PCH1,where(14)EtrCH1,PCH1=kEelec+kεfsCH1−PCH122,CH1−PCH12≤d0,kEelec+kεmpCH1−PCH124,others,(15)EreCH1,PCH1=kEelec.(Step 2)
Add cluster headCHii≠1 other than CH1 to path tree, and record path information of themselves.Assuming that the cluster head of currently selected parent node isCHi (CHi∈C0 and i≠1), the set of all optional parent nodes of CHi is defined as CHJ=CHjj=1,⋯,i−1. Specifically, in Figure 6(c), CHi=CH2 and CHJ=CH1.Whether or not choosingCHj as the parent node of the CHi is determined by the path weight WCHiCHj described in(16)WCHiCHj=μECHiCHj+λ1−RCHiCHj,CHj∈CHJ,where(17)ECHiCHj=ErCHjErcCHJ,(18)ErcCHJ=∑CHk∈CHJErCHk,(19)RCHiCHj=EtrCHi,CHjEtcCHi,CHJ,(20)EtcCHi,CHJ=∑CHk∈CHJEtrCHi,CHk.Observing equations (16) to (20), it can be concluded that path weights WCHiCHj are positively correlated with the remaining energy of CHj and negatively correlated with the energy consumption of data transmission from CHi to CHj, respectively. Thus, it may choose the node with the largest path weight in the CHJ as the parent node of CHi and record path information related to CHi.(Step 3)
Determine whether or notCHi should be assigned children nodes of the base station.After selecting the parent node,CHi can obtain the total communication energy consumption EcoCHi,PCHi by searching its record information first. Then, total energy consumption EtrCHi,BS related to direct communication between CHi and base station can be obtained by equation (14). Therefore, it decided whether CHi should be assigned as children nodes of the base station by condition threshold TcCHi described in(21)TcCHi=1,EcoCHi,PCHi≥EtrCHi,BS,0,EcoCHi,PCHi<EtrCHi,BS.IfTcCHi=1, CHi should be assigned as children nodes of the base station and update its path information, else, not.(Step 4)
Determine whether or not path tree is constructed completely.If current cluster headCHi is the last element of C0, it means the path tree is completed; otherwise, it will go back step 2 to select the parent node of the next cluster head. As shown in Figure 6(d), sequentially execute step 2, step 3, and step 4 to select the parent node of cluster head CH3 and so on, until all cluster heads in C0 have been selected.In summary, the pseudocode related to path tree constructing is shown in Pseudocode1.Pseudocode 1: For Constructing Path Tree.
Steps to build path tree1. Initialization, getCHnum (Cluster head number), dtoBS (Distance between cluster head and base station)2. Sort cluster head according todtoBS, and get C03. fori=1:CHnum4. if (i==1)5.PCH1=BS6.  Record path information ofCH1 according to equ. (13)–(15)7. else8.  Determine setCHJ of optional parent nodes of cluster head CHi9.  Select parent node according to equ.(17)10.  Record path information ofCHi according to equ.(12)–(15)11.  ifEcoCHi,PCHi≥EtrCHi,BS12.PCHi=BS ，and re-record path information of CHi13.   end if14.  end if15. end forThe symbolic instructions in the path tree building steps above are shown in Table1.Table 1
Symbolic representation in the path tree building step.
SymbolDefinitionSymbolDefinitionPCH1Parent node of cluster headCH1RCHiCHijPath energy factor of optional parent nodeCHijEtrCH1,PCH1Energy consumption ofCH1 transmitting data to PCH1ErCHijRemaining energy of optional parent nodeCHijEreCH1,PCH1Energy consumption ofPCH1 receiving data to CH1ErcCHijSum of the remaining energy of all optional parent nodes in setCHijEcoCH1,PCH1Communication energy consumption betweenCH1 and PCH1EtrCHi,CHijEnergy consumption of data transmission fromCHi to CHijCH1,PCH1Coordinates ofCH1 and PCH1, respectivelyEtcCHi,CHijSum of the energy consumption of data transmission fromCHi to all optional parent nodes in set CHijCHijjth optional parent node of CHiμ,λPath weight parameters,μ+λ=1ECHiCHijRemaining energy factor of optional parent nodeCHij


### 5.4. MHRA-PT Algorithm

The MHRA-PT algorithm improves the traditional methods including cluster head selection, working node selection, and data transmission path selection. The flow chart of MHRA-PT algorithm is shown in Figure7.Figure 7
The flow chart of MHRA-PT algorithm.In order to clearly describe the MHRA-PT algorithm, some pseudocodes are shown in Pseudocode2.Pseudocode 2: For MHRA-PT Algorithm.
MHRA-PT algorithm1. Initialization, getM(Node set) and rmax(Maximum number of rounds of the algorithm)2.forr=1:rmaxdo3.for∀ni∈Mdo4.ifTmni≥Trnithen  //If the nodeniis selected as cluster head5.C←ni   //The nodenijoinsC(Cluster head set)6.else7.N←ni   //The nodenijoinsN(Non-cluster head set)8.endif9.endfor10.for∀nj∈Cudo   //Cuis any cluster set in the network11.ifTwnj=1then   //If the nodenjis selected as working node12.W←nj   //The nodenjjoinsW(working node set)13.else14.S←nj   //The nodenjjoinsS(Sleep node set)15.endif16.endfor17. Construct sorted cluster head setC0=CHi∣i=1,⋯,C //CHirepresents theithcluster head18.for∀CHi∈C0do19.ifCHi=CH1then   //IfCHiis the first cluster head of the setC020.PCH1←BS   //BSis regarded as the parent node ofCHi21.else   //IfCHiis not the first cluster head of the setC022.  Calculate weight of pathWCHiCHij  //CHijrepresents thejthoptional parent node ofCHi23.PCHi←CHij←maxWCHiCHijCHij∈CHij//CHijis regarded as the parent node ofCHi24.  Determine whetherCHi needs to replace the parent node according to equ.(21)25.endif26.endfor27. Perform data transfer28.endfor


## 5.1. Strategy for Cluster Head Selection

Cluster head selection is performed in the cluster routing algorithm based on the cluster head selection threshold. SupposeN sensor nodes are randomly distributed in the square area of SM. The optimal number of cluster head Kopt [18] and the optimal percentage of cluster head to the total number of all nodes Popt are shown in the following:(4)Popt=KoptN,Kopt=20.765N/2π.In equation (5), the cluster head selection threshold Tmni is constructed by probability Pb [10], fdni factor relating to distance between ni and base station, and remaining energy factor feni.(5)Tmni=αPb+βfdni⋅feni,ni∈G′,0,otherwise,where(6)Pb=Popt1−Poptrmod1/Popt,(7)fdni=dnbmax−dnbnidnbmax−dnbmin,(8)feni=ErniE0ni,where α and β are weight parameters of Tmni and, at the same time, α+β=1; dnbni≜ni−B2, B is the coordinate of base station, ni is the coordinate of node ni, dnbmax≜maxdnbni, and dnbmin≜mindnbni; and Erni is the remaining energy of ni, and E0ni is the initial energy of ni. Besides, G′ is the node set that has not been selected as the cluster head in the cycle of 1/Popt.Observing equations (4)–(8), it is obvious that some nodes with properties such as being closer to base station and larger remaining energy have large cluster head selection threshold, thus having greater probability of being selected as the cluster head. In addition, nodes selected as the cluster head are added to the cluster head set C, and the nodes not selected as the cluster head are added to the noncluster head set N.


## 5.2. Strategy for Working Node Selection

It is obvious that using all nodes in WSNs to work may consume excess energy. Therefore, it should partition each cluster to reducing number of working nodes while guaranteeing network coverage.An example is used to describe in Figure4 to illustrate the details of partition. Assume that the farthest distance between cluster head CH and cluster member CM is r and the maximum sensing radius of node is r/2. Thus, the cluster’s coverage area is a circle with the position of cluster head as the center and a radius r. Z1 is defined as the circular area with the position of cluster head as the center and r/2 as the radius; Z2 is the ring area with the position of cluster head as the center r/2 and r as the inner radii and outer radii, respectively. It can be found that the area of cluster may be divided into eight parts which are marked as ①~⑧, respectively.Figure 4
Area division within cluster.In Figure4, it is clear that sensing range of nodes in each part of Z1 areas and nodes in each part of Z2 areas can cover the entire cluster since the maximum sensing radius of node is r/2.So, it should, respectively, choose working nodes in each part of the entire cluster to guarantee sensing range of nodes covering the entire cluster. In addition, it can compare the remaining energyErnj of node nj with the average remaining energy Eavg of all nodes described in equation (9) to determine whether or not assign nodenjis the working node.(9)Eavg=∑nk∈CuErnkm.In equation (9), Cu is the set of all nodes within the cluster, Ernk is the remaining energy of node nk, m is the cardinal of the Cu. Specifically, if Ernj≥Eavg, the node nj joins in the working node set W. On the contrary, the node nj joins in the sleep node set S. Assuming the remaining energy of each node in a part of cluster less than Eavg, it should assign the node with the largest remaining energy as the working node.


## 5.3. Strategy for Data Transmission Path Selection

In the data transmission phase, multihop transmission strategy can be used to reduce energy consumption caused by long distance single-hop data transmission. This paper constructs path tree which assigns cluster head as the branch node so that each cluster head can transmit data to the base station along its branch path. The path tree between the base station and cluster head is shown in Figure5.Figure 5
Path tree constructed by base station and cluster head.Models of path tree construction are described in the following:(10)C0=CHii=1,⋯,C,(11)CHi−B2≤CHj−B2,∀i<j,where C0 is a new cluster head set by sorting the elements in the cluster head set C, C is the cardinal of C, CHi is the ith cluster head, CHi is the coordinate corresponding to CHi, and B is the coordinate corresponding to base station. It can conclude the details of path tree construction as follows. Firstly, sorting cluster head according to the distance dtoBS between cluster head and base station, cluster head should choose the cluster head closer to the base station as parent node. Secondly, it successively assigns the parent node to each cluster head according to ascending order of the distance dtoBS between the cluster head and the base station. Now, taking as an example (Figure 6), it chooses the cluster head CH1, CH2, and CH3 in C0 to display the details related to path tree construction.(Step 1)
Add first branch nodeCH1 of path tree and record path information.Figure 6
The process of path tree construction.According to equations (10) and (11), cluster head CH1 closest to the base station, so as described in equation (12) can directly choose the base station as the parent node of itself (Figure 6(b)). Meanwhile, as described in equations (13), (14), and (15),CH1records path information itself.(12)PCH1=BS,(13)EcoCH1,PCH1=EtrCH1,PE+EreCH1,PCH1,where(14)EtrCH1,PCH1=kEelec+kεfsCH1−PCH122,CH1−PCH12≤d0,kEelec+kεmpCH1−PCH124,others,(15)EreCH1,PCH1=kEelec.(Step 2)
Add cluster headCHii≠1 other than CH1 to path tree, and record path information of themselves.Assuming that the cluster head of currently selected parent node isCHi (CHi∈C0 and i≠1), the set of all optional parent nodes of CHi is defined as CHJ=CHjj=1,⋯,i−1. Specifically, in Figure 6(c), CHi=CH2 and CHJ=CH1.Whether or not choosingCHj as the parent node of the CHi is determined by the path weight WCHiCHj described in(16)WCHiCHj=μECHiCHj+λ1−RCHiCHj,CHj∈CHJ,where(17)ECHiCHj=ErCHjErcCHJ,(18)ErcCHJ=∑CHk∈CHJErCHk,(19)RCHiCHj=EtrCHi,CHjEtcCHi,CHJ,(20)EtcCHi,CHJ=∑CHk∈CHJEtrCHi,CHk.Observing equations (16) to (20), it can be concluded that path weights WCHiCHj are positively correlated with the remaining energy of CHj and negatively correlated with the energy consumption of data transmission from CHi to CHj, respectively. Thus, it may choose the node with the largest path weight in the CHJ as the parent node of CHi and record path information related to CHi.(Step 3)
Determine whether or notCHi should be assigned children nodes of the base station.After selecting the parent node,CHi can obtain the total communication energy consumption EcoCHi,PCHi by searching its record information first. Then, total energy consumption EtrCHi,BS related to direct communication between CHi and base station can be obtained by equation (14). Therefore, it decided whether CHi should be assigned as children nodes of the base station by condition threshold TcCHi described in(21)TcCHi=1,EcoCHi,PCHi≥EtrCHi,BS,0,EcoCHi,PCHi<EtrCHi,BS.IfTcCHi=1, CHi should be assigned as children nodes of the base station and update its path information, else, not.(Step 4)
Determine whether or not path tree is constructed completely.If current cluster headCHi is the last element of C0, it means the path tree is completed; otherwise, it will go back step 2 to select the parent node of the next cluster head. As shown in Figure 6(d), sequentially execute step 2, step 3, and step 4 to select the parent node of cluster head CH3 and so on, until all cluster heads in C0 have been selected.In summary, the pseudocode related to path tree constructing is shown in Pseudocode1.Pseudocode 1: For Constructing Path Tree.
Steps to build path tree1. Initialization, getCHnum (Cluster head number), dtoBS (Distance between cluster head and base station)2. Sort cluster head according todtoBS, and get C03. fori=1:CHnum4. if (i==1)5.PCH1=BS6.  Record path information ofCH1 according to equ. (13)–(15)7. else8.  Determine setCHJ of optional parent nodes of cluster head CHi9.  Select parent node according to equ.(17)10.  Record path information ofCHi according to equ.(12)–(15)11.  ifEcoCHi,PCHi≥EtrCHi,BS12.PCHi=BS ，and re-record path information of CHi13.   end if14.  end if15. end forThe symbolic instructions in the path tree building steps above are shown in Table1.Table 1
Symbolic representation in the path tree building step.
SymbolDefinitionSymbolDefinitionPCH1Parent node of cluster headCH1RCHiCHijPath energy factor of optional parent nodeCHijEtrCH1,PCH1Energy consumption ofCH1 transmitting data to PCH1ErCHijRemaining energy of optional parent nodeCHijEreCH1,PCH1Energy consumption ofPCH1 receiving data to CH1ErcCHijSum of the remaining energy of all optional parent nodes in setCHijEcoCH1,PCH1Communication energy consumption betweenCH1 and PCH1EtrCHi,CHijEnergy consumption of data transmission fromCHi to CHijCH1,PCH1Coordinates ofCH1 and PCH1, respectivelyEtcCHi,CHijSum of the energy consumption of data transmission fromCHi to all optional parent nodes in set CHijCHijjth optional parent node of CHiμ,λPath weight parameters,μ+λ=1ECHiCHijRemaining energy factor of optional parent nodeCHij


## 5.4. MHRA-PT Algorithm

The MHRA-PT algorithm improves the traditional methods including cluster head selection, working node selection, and data transmission path selection. The flow chart of MHRA-PT algorithm is shown in Figure7.Figure 7
The flow chart of MHRA-PT algorithm.In order to clearly describe the MHRA-PT algorithm, some pseudocodes are shown in Pseudocode2.Pseudocode 2: For MHRA-PT Algorithm.
MHRA-PT algorithm1. Initialization, getM(Node set) and rmax(Maximum number of rounds of the algorithm)2.forr=1:rmaxdo3.for∀ni∈Mdo4.ifTmni≥Trnithen  //If the nodeniis selected as cluster head5.C←ni   //The nodenijoinsC(Cluster head set)6.else7.N←ni   //The nodenijoinsN(Non-cluster head set)8.endif9.endfor10.for∀nj∈Cudo   //Cuis any cluster set in the network11.ifTwnj=1then   //If the nodenjis selected as working node12.W←nj   //The nodenjjoinsW(working node set)13.else14.S←nj   //The nodenjjoinsS(Sleep node set)15.endif16.endfor17. Construct sorted cluster head setC0=CHi∣i=1,⋯,C //CHirepresents theithcluster head18.for∀CHi∈C0do19.ifCHi=CH1then   //IfCHiis the first cluster head of the setC020.PCH1←BS   //BSis regarded as the parent node ofCHi21.else   //IfCHiis not the first cluster head of the setC022.  Calculate weight of pathWCHiCHij  //CHijrepresents thejthoptional parent node ofCHi23.PCHi←CHij←maxWCHiCHijCHij∈CHij//CHijis regarded as the parent node ofCHi24.  Determine whetherCHi needs to replace the parent node according to equ.(21)25.endif26.endfor27. Perform data transfer28.endfor


## 6. Simulation Results and Analysis

In this section, it uses the performance comparison of different approaches to demonstrate the advantages of the proposed MHRA-PT algorithm.


### 6.1. Experimental Parameters

In order to verify the feasibility and effectiveness of the proposed MHRA-PT algorithm, it is compared with three algorithms IMHT-LEACH [14], DMATEB [15], and CEED [19] in terms of cluster head energy consumption, network energy balance, and network node survival time through MATLAB simulation platform.Assume thatN sensor nodes are randomly deployed in a monitoring area with an area of SM, and base station is located at the center of the monitoring area (Figure 8).Figure 8
Distribution of wireless sensor network nodes.The parameters used in the simulation are given in Table2.Table 2
The parameters used in the experiment.
NameSymbolValueArea of monitorSM300m×300mNumber of sensor nodesN100The coordinate of the base stationxBS,yBS(150 m, 150 m)Initial energy of nodeE01 JCommunication energy consumptionETX/ERX50 nJ/bitEnergy consumption of signal amplification in free spaceεfs10 pJ/bit/m2Energy consumption of signal amplification in multipathεmp0.0013 pJ/bit/m4Energy consumption of data fusionEDA5 nJ/bit/packetLength of control signalk1100 bitLength of monitor datak24000 bitOptimum ratio of cluster headPopt10%Weight of cluster head thresholdα,βα=0.4,β=0.6Weight of pathμ,λμ=0.3,λ=0.7Maximum number of running roundsrmax1800


### 6.2. Cluster Head Energy Consumption

#### 6.2.1. Transmission Path of Cluster Head

When cluster head transmits data to base station, it will cause different energy consumptions due to different transmission paths. Taking the network running to the 500th round as an example, Figure9 shows the cluster head transmission paths in the CEED, DMATEB, IMHT-LEACH, and MHRA-PT.Figure 9
Transmission path of cluster head related to four algorithms.
(a)
CEED (500th round)(b)
DMATEB (500th round)(c)
IMHT-LEACH (500th round)(d)
MHRA-PT (500th round)Comparing the four subgraphs in Figure9, under the condition that cluster heads are located at the same position, the cluster head transmission path of the CEED algorithm adopts chain structure, so that the data transmission appears to be oriented away from the base station. However, the cluster head transmission paths of DMATEB, IMHT-LEACH, and MHRA-PT algorithms adopt tree structure to avoid the deviation and improve the stability of data transmission from cluster head to base station. However, the data transmission paths of cluster heads related to three algorithms are very different due to their different path selection strategies. The MHRA-PT algorithm takes the directivity and path weight of the data transmitted from the cluster head to the base station into full consideration to construct the path tree as the data transmission path of the cluster head. Comparisons of four algorithms demonstrate the effectiveness of the MHRA-PT algorithm.


#### 6.2.2. Energy Consumption of Cluster Head

Figure10 shows the curve of total energy consumption of cluster head. It describes the energy consumption of transmitting between the cluster head and the base station, over the number of the network running rounds.Figure 10
Total energy consumption of the cluster head.In this figure, the curves of four algorithms all show an upward trend, but they have different rates of rise. It is clear that when network runs to the 900th round, the rising rate of the corresponding curve of four algorithms decreases. The reason is that the number of selected cluster heads decreases due to the death of a large number of nodes in the network. It is clear that energy consumption of the MHRA-PT algorithm is always lower than that of the other three algorithms. Specifically, when the network runs to the 1100th round, the total energy consumption of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 15.2732 J, 10.5168 J, 9.3494 J, and 7.0444 J, respectively. Compared with the other algorithms, the MHRA-PT algorithm saves 53.9%, 33.1%, and 24.7% of energy, respectively. The above analysis shows that the MHRA-PT algorithm can effectively reduce cluster head energy consumption.


#### 6.2.3. Average Remaining Energy of Cluster Head

Figure11 shows the average remaining energy of cluster heads of CEED, DMATEB, IMHT-LEACH, and MHRA-PT at different times during the network operation.Figure 11
Average remaining energy of the cluster heads.As can be seen from this figure, the curves corresponding to the four algorithms keep decreasing; that is, the average residual energy of the cluster head keeps decreasing, but the curve corresponding to the MHRA-PT algorithm is always higher than curve corresponding to the other three algorithms. Specifically, when the network runs to the 1000th round, the average remaining energy of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 0.0343 J, 0.0599 J, 0.0604 J, and 0.1329 J, respectively. Compared with the other three algorithms, the average remaining energy of the cluster head of the MHRA-PT algorithm is 74.2%, 54.9%, and 54.6% higher, respectively. This shows that in the same running time, the MHRA-PT algorithm can effectively save the energy consumption of cluster head.


#### 6.2.4. Balance of Energy Consumption of Cluster Head

Meanwhile, in order to measure the balance of energy consumption of cluster head, the proximitiesΔPrmax and ΔPrmin of cluster head are introduced in equations (22) and (23), respectively.(22)ΔPrmax=Ermax−EravgEravg×100%,(23)ΔPrmin=Eravg−ErminEravg×100%.In equations (22) and (23), ΔPrmax and ΔPrmin are proximity of maximum remaining energy and minimum remaining energy to average remaining energy of cluster head, respectively, Eravg is the average remaining energy of all nodes, Ermax is the maximum remaining energy, and Ermin is the minimum remaining energy. The smaller ΔPrmax and ΔPrmin are (that is, Ermax and Ermin are closer to Eravg), the more balanced the cluster head energy consumption is. The parameter indexes of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms are shown in Table 3.Table 3
The parameter index of the cluster head.
Algorithm parameter valueCEEDDMATEBIMHT-LEACHMHRA-PTErmax0.4975 J0.5474 J0.5654 J0.6030 JErmin0.0654 J0.1330 J0.2066 J0.4455 JEravg0.2749 J0.4390 J0.4235 J0.5495 JΔPrmax80.98%24.67%33.50%9.74%ΔPrmin76.23%69.71%51.21%18.92%It can be seen from Table3 that maximum remaining energy Ermax, minimum remaining energy Ermin, and average remaining energy Eravg of the MHRA-PT algorithm are 0.6030 J, 0.4455 J, and 0.5495 J, respectively. Compared with the other three algorithms, the remaining energy of the cluster head of the MHRA-PT algorithm is the largest. In addition, ΔPrmax of the MHRA-PT algorithm is 9.74%, which is 71.24%, 14.93%, and 23.76% lower than those of the other three algorithms, indicating the maximum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. Similarly, ΔPrmin of the MHRA-PT algorithm is 18.92%, which is 57.3%, 50.79%, and 32.9% lower than those of the other three algorithms, indicating the minimum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. According to the above analysis, the MHRA-PT algorithm can effectively balance energy consumption.


### 6.3. Network Energy Balance

Network nodes are deployed at different locations in the monitoring area. The remaining energy of each node is different at each round. Taking the network running to the 500th round as an example, it can prove the validity of the MHRA-PT algorithm for balancing network energy consumption by comparing the residual energy of nodes in different locations in the CEED, DMATEB, IMHT-LEACH, and MHRA-PT.In Figure12, square box indicates the base station, which is located at the center of the monitoring area. The distribution of the remaining energy of nodes in Figures 12(a)–12(c) are approximately convex; i.e., the remaining energy of nodes located near the center of monitoring area is higher and far from the center of monitoring area is lower, and the difference of remaining energy between nodes is large. However, the distribution of remaining energy of nodes in Figure 12(d) is approximately horizontal, indicating that no matter whether it is a node in the center of monitoring area or a node far from the center of monitoring area, the difference of remaining energy between nodes is small. The above analysis shows that the MHRA-PT algorithm can effectively balance network energy. Meanwhile, in order to illustrate the change of total remaining energy of all nodes in the four algorithms, Figure 13 shows the trend of total remaining energy of all nodes in the network.Figure 12
Distribution of remaining energy of nodes (500th round).
(a)
Remaining energy of CEED(b)
Remaining energy of DMATEB(c)
Remaining energy of IMHT-LEACH(d)
Remaining energy of MHRA-PTFigure 13
The trend of total remaining energy of all nodes.It can be shown from Figure13 that the total remaining energy corresponding to four algorithms decreases as the network running time increases. During network operation, the total remaining energy corresponding to the MHRA-PT algorithm is always greater than the other three algorithms. When the total remaining energy of the network is 0, the round of running of CEED, DMATEB, IMHT-LEACH, and MHRA-PT is 1201, 1196, 1329, and 1577, respectively. This means that the total remaining energy of the MHRA-PT algorithm is reduced to 0 at the latest, which indicates that the MHRA-PT algorithm has the longest energy utilization time; i.e., the MHRA-PT algorithm can effectively reduce network energy consumption and prolong energy utilization time.


### 6.4. Network Node Survival Time

In the process of network operation, with the increase of node energy consumption, dead nodes will gradually appear in the network. The number of survival nodes of WSNs versus the number of round running relating to different algorithms is given in Figure14.Figure 14
Number of survival nodes of WSNs versus round running.It can be seen from Figure14 that with the operation of the network, the curves corresponding to four algorithms have a cliff-like downward trend. When the first dead node appears in the network, the round of running of CEED, DMATEB, IMHT-LEACH, and MHRA-PT is 410, 439, 617, and 864, respectively. Compared with the other algorithms, the MHRA-PT algorithm is the latest when the first dead node appears and prolongs the death time of the first node: 110.7%, 96.8%, and 40%, respectively. Besides, compared with the other algorithms, the MHRA-PT algorithm prolongs the death time of all nodes (31.3%, 31.9%, and 18.7%, respectively). This is because the MHRA-PT algorithm preferentially uses the working nodes with large residual energy in each round of operation and constructs the path tree for the cluster head when transmitting data, thereby effectively delaying death time of the node. According to the above analysis, the MHRA-PT algorithm can effectively prolong the life cycle of WSNs.


## 6.1. Experimental Parameters

In order to verify the feasibility and effectiveness of the proposed MHRA-PT algorithm, it is compared with three algorithms IMHT-LEACH [14], DMATEB [15], and CEED [19] in terms of cluster head energy consumption, network energy balance, and network node survival time through MATLAB simulation platform.Assume thatN sensor nodes are randomly deployed in a monitoring area with an area of SM, and base station is located at the center of the monitoring area (Figure 8).Figure 8
Distribution of wireless sensor network nodes.The parameters used in the simulation are given in Table2.Table 2
The parameters used in the experiment.
NameSymbolValueArea of monitorSM300m×300mNumber of sensor nodesN100The coordinate of the base stationxBS,yBS(150 m, 150 m)Initial energy of nodeE01 JCommunication energy consumptionETX/ERX50 nJ/bitEnergy consumption of signal amplification in free spaceεfs10 pJ/bit/m2Energy consumption of signal amplification in multipathεmp0.0013 pJ/bit/m4Energy consumption of data fusionEDA5 nJ/bit/packetLength of control signalk1100 bitLength of monitor datak24000 bitOptimum ratio of cluster headPopt10%Weight of cluster head thresholdα,βα=0.4,β=0.6Weight of pathμ,λμ=0.3,λ=0.7Maximum number of running roundsrmax1800


## 6.2. Cluster Head Energy Consumption

### 6.2.1. Transmission Path of Cluster Head

When cluster head transmits data to base station, it will cause different energy consumptions due to different transmission paths. Taking the network running to the 500th round as an example, Figure9 shows the cluster head transmission paths in the CEED, DMATEB, IMHT-LEACH, and MHRA-PT.Figure 9
Transmission path of cluster head related to four algorithms.
(a)
CEED (500th round)(b)
DMATEB (500th round)(c)
IMHT-LEACH (500th round)(d)
MHRA-PT (500th round)Comparing the four subgraphs in Figure9, under the condition that cluster heads are located at the same position, the cluster head transmission path of the CEED algorithm adopts chain structure, so that the data transmission appears to be oriented away from the base station. However, the cluster head transmission paths of DMATEB, IMHT-LEACH, and MHRA-PT algorithms adopt tree structure to avoid the deviation and improve the stability of data transmission from cluster head to base station. However, the data transmission paths of cluster heads related to three algorithms are very different due to their different path selection strategies. The MHRA-PT algorithm takes the directivity and path weight of the data transmitted from the cluster head to the base station into full consideration to construct the path tree as the data transmission path of the cluster head. Comparisons of four algorithms demonstrate the effectiveness of the MHRA-PT algorithm.


### 6.2.2. Energy Consumption of Cluster Head

Figure10 shows the curve of total energy consumption of cluster head. It describes the energy consumption of transmitting between the cluster head and the base station, over the number of the network running rounds.Figure 10
Total energy consumption of the cluster head.In this figure, the curves of four algorithms all show an upward trend, but they have different rates of rise. It is clear that when network runs to the 900th round, the rising rate of the corresponding curve of four algorithms decreases. The reason is that the number of selected cluster heads decreases due to the death of a large number of nodes in the network. It is clear that energy consumption of the MHRA-PT algorithm is always lower than that of the other three algorithms. Specifically, when the network runs to the 1100th round, the total energy consumption of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 15.2732 J, 10.5168 J, 9.3494 J, and 7.0444 J, respectively. Compared with the other algorithms, the MHRA-PT algorithm saves 53.9%, 33.1%, and 24.7% of energy, respectively. The above analysis shows that the MHRA-PT algorithm can effectively reduce cluster head energy consumption.


### 6.2.3. Average Remaining Energy of Cluster Head

Figure11 shows the average remaining energy of cluster heads of CEED, DMATEB, IMHT-LEACH, and MHRA-PT at different times during the network operation.Figure 11
Average remaining energy of the cluster heads.As can be seen from this figure, the curves corresponding to the four algorithms keep decreasing; that is, the average residual energy of the cluster head keeps decreasing, but the curve corresponding to the MHRA-PT algorithm is always higher than curve corresponding to the other three algorithms. Specifically, when the network runs to the 1000th round, the average remaining energy of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 0.0343 J, 0.0599 J, 0.0604 J, and 0.1329 J, respectively. Compared with the other three algorithms, the average remaining energy of the cluster head of the MHRA-PT algorithm is 74.2%, 54.9%, and 54.6% higher, respectively. This shows that in the same running time, the MHRA-PT algorithm can effectively save the energy consumption of cluster head.


### 6.2.4. Balance of Energy Consumption of Cluster Head

Meanwhile, in order to measure the balance of energy consumption of cluster head, the proximitiesΔPrmax and ΔPrmin of cluster head are introduced in equations (22) and (23), respectively.(22)ΔPrmax=Ermax−EravgEravg×100%,(23)ΔPrmin=Eravg−ErminEravg×100%.In equations (22) and (23), ΔPrmax and ΔPrmin are proximity of maximum remaining energy and minimum remaining energy to average remaining energy of cluster head, respectively, Eravg is the average remaining energy of all nodes, Ermax is the maximum remaining energy, and Ermin is the minimum remaining energy. The smaller ΔPrmax and ΔPrmin are (that is, Ermax and Ermin are closer to Eravg), the more balanced the cluster head energy consumption is. The parameter indexes of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms are shown in Table 3.Table 3
The parameter index of the cluster head.
Algorithm parameter valueCEEDDMATEBIMHT-LEACHMHRA-PTErmax0.4975 J0.5474 J0.5654 J0.6030 JErmin0.0654 J0.1330 J0.2066 J0.4455 JEravg0.2749 J0.4390 J0.4235 J0.5495 JΔPrmax80.98%24.67%33.50%9.74%ΔPrmin76.23%69.71%51.21%18.92%It can be seen from Table3 that maximum remaining energy Ermax, minimum remaining energy Ermin, and average remaining energy Eravg of the MHRA-PT algorithm are 0.6030 J, 0.4455 J, and 0.5495 J, respectively. Compared with the other three algorithms, the remaining energy of the cluster head of the MHRA-PT algorithm is the largest. In addition, ΔPrmax of the MHRA-PT algorithm is 9.74%, which is 71.24%, 14.93%, and 23.76% lower than those of the other three algorithms, indicating the maximum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. Similarly, ΔPrmin of the MHRA-PT algorithm is 18.92%, which is 57.3%, 50.79%, and 32.9% lower than those of the other three algorithms, indicating the minimum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. According to the above analysis, the MHRA-PT algorithm can effectively balance energy consumption.


## 6.2.1. Transmission Path of Cluster Head

When cluster head transmits data to base station, it will cause different energy consumptions due to different transmission paths. Taking the network running to the 500th round as an example, Figure9 shows the cluster head transmission paths in the CEED, DMATEB, IMHT-LEACH, and MHRA-PT.Figure 9
Transmission path of cluster head related to four algorithms.
(a)
CEED (500th round)(b)
DMATEB (500th round)(c)
IMHT-LEACH (500th round)(d)
MHRA-PT (500th round)Comparing the four subgraphs in Figure9, under the condition that cluster heads are located at the same position, the cluster head transmission path of the CEED algorithm adopts chain structure, so that the data transmission appears to be oriented away from the base station. However, the cluster head transmission paths of DMATEB, IMHT-LEACH, and MHRA-PT algorithms adopt tree structure to avoid the deviation and improve the stability of data transmission from cluster head to base station. However, the data transmission paths of cluster heads related to three algorithms are very different due to their different path selection strategies. The MHRA-PT algorithm takes the directivity and path weight of the data transmitted from the cluster head to the base station into full consideration to construct the path tree as the data transmission path of the cluster head. Comparisons of four algorithms demonstrate the effectiveness of the MHRA-PT algorithm.


## 6.2.2. Energy Consumption of Cluster Head

Figure10 shows the curve of total energy consumption of cluster head. It describes the energy consumption of transmitting between the cluster head and the base station, over the number of the network running rounds.Figure 10
Total energy consumption of the cluster head.In this figure, the curves of four algorithms all show an upward trend, but they have different rates of rise. It is clear that when network runs to the 900th round, the rising rate of the corresponding curve of four algorithms decreases. The reason is that the number of selected cluster heads decreases due to the death of a large number of nodes in the network. It is clear that energy consumption of the MHRA-PT algorithm is always lower than that of the other three algorithms. Specifically, when the network runs to the 1100th round, the total energy consumption of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 15.2732 J, 10.5168 J, 9.3494 J, and 7.0444 J, respectively. Compared with the other algorithms, the MHRA-PT algorithm saves 53.9%, 33.1%, and 24.7% of energy, respectively. The above analysis shows that the MHRA-PT algorithm can effectively reduce cluster head energy consumption.


## 6.2.3. Average Remaining Energy of Cluster Head

Figure11 shows the average remaining energy of cluster heads of CEED, DMATEB, IMHT-LEACH, and MHRA-PT at different times during the network operation.Figure 11
Average remaining energy of the cluster heads.As can be seen from this figure, the curves corresponding to the four algorithms keep decreasing; that is, the average residual energy of the cluster head keeps decreasing, but the curve corresponding to the MHRA-PT algorithm is always higher than curve corresponding to the other three algorithms. Specifically, when the network runs to the 1000th round, the average remaining energy of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms is 0.0343 J, 0.0599 J, 0.0604 J, and 0.1329 J, respectively. Compared with the other three algorithms, the average remaining energy of the cluster head of the MHRA-PT algorithm is 74.2%, 54.9%, and 54.6% higher, respectively. This shows that in the same running time, the MHRA-PT algorithm can effectively save the energy consumption of cluster head.


## 6.2.4. Balance of Energy Consumption of Cluster Head

Meanwhile, in order to measure the balance of energy consumption of cluster head, the proximitiesΔPrmax and ΔPrmin of cluster head are introduced in equations (22) and (23), respectively.(22)ΔPrmax=Ermax−EravgEravg×100%,(23)ΔPrmin=Eravg−ErminEravg×100%.In equations (22) and (23), ΔPrmax and ΔPrmin are proximity of maximum remaining energy and minimum remaining energy to average remaining energy of cluster head, respectively, Eravg is the average remaining energy of all nodes, Ermax is the maximum remaining energy, and Ermin is the minimum remaining energy. The smaller ΔPrmax and ΔPrmin are (that is, Ermax and Ermin are closer to Eravg), the more balanced the cluster head energy consumption is. The parameter indexes of the cluster head of CEED, DMATEB, IMHT-LEACH, and MHRA-PT algorithms are shown in Table 3.Table 3
The parameter index of the cluster head.
Algorithm parameter valueCEEDDMATEBIMHT-LEACHMHRA-PTErmax0.4975 J0.5474 J0.5654 J0.6030 JErmin0.0654 J0.1330 J0.2066 J0.4455 JEravg0.2749 J0.4390 J0.4235 J0.5495 JΔPrmax80.98%24.67%33.50%9.74%ΔPrmin76.23%69.71%51.21%18.92%It can be seen from Table3 that maximum remaining energy Ermax, minimum remaining energy Ermin, and average remaining energy Eravg of the MHRA-PT algorithm are 0.6030 J, 0.4455 J, and 0.5495 J, respectively. Compared with the other three algorithms, the remaining energy of the cluster head of the MHRA-PT algorithm is the largest. In addition, ΔPrmax of the MHRA-PT algorithm is 9.74%, which is 71.24%, 14.93%, and 23.76% lower than those of the other three algorithms, indicating the maximum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. Similarly, ΔPrmin of the MHRA-PT algorithm is 18.92%, which is 57.3%, 50.79%, and 32.9% lower than those of the other three algorithms, indicating the minimum remaining energy is the closest to the average remaining energy of the cluster head of the MHRA-PT algorithm. According to the above analysis, the MHRA-PT algorithm can effectively balance energy consumption.


## 6.3. Network Energy Balance

Network nodes are deployed at different locations in the monitoring area. The remaining energy of each node is different at each round. Taking the network running to the 500th round as an example, it can prove the validity of the MHRA-PT algorithm for balancing network energy consumption by comparing the residual energy of nodes in different locations in the CEED, DMATEB, IMHT-LEACH, and MHRA-PT.In Figure12, square box indicates the base station, which is located at the center of the monitoring area. The distribution of the remaining energy of nodes in Figures 12(a)–12(c) are approximately convex; i.e., the remaining energy of nodes located near the center of monitoring area is higher and far from the center of monitoring area is lower, and the difference of remaining energy between nodes is large. However, the distribution of remaining energy of nodes in Figure 12(d) is approximately horizontal, indicating that no matter whether it is a node in the center of monitoring area or a node far from the center of monitoring area, the difference of remaining energy between nodes is small. The above analysis shows that the MHRA-PT algorithm can effectively balance network energy. Meanwhile, in order to illustrate the change of total remaining energy of all nodes in the four algorithms, Figure 13 shows the trend of total remaining energy of all nodes in the network.Figure 12
Distribution of remaining energy of nodes (500th round).
(a)
Remaining energy of CEED(b)
Remaining energy of DMATEB(c)
Remaining energy of IMHT-LEACH(d)
Remaining energy of MHRA-PTFigure 13
The trend of total remaining energy of all nodes.It can be shown from Figure13 that the total remaining energy corresponding to four algorithms decreases as the network running time increases. During network operation, the total remaining energy corresponding to the MHRA-PT algorithm is always greater than the other three algorithms. When the total remaining energy of the network is 0, the round of running of CEED, DMATEB, IMHT-LEACH, and MHRA-PT is 1201, 1196, 1329, and 1577, respectively. This means that the total remaining energy of the MHRA-PT algorithm is reduced to 0 at the latest, which indicates that the MHRA-PT algorithm has the longest energy utilization time; i.e., the MHRA-PT algorithm can effectively reduce network energy consumption and prolong energy utilization time.


## 6.4. Network Node Survival Time

In the process of network operation, with the increase of node energy consumption, dead nodes will gradually appear in the network. The number of survival nodes of WSNs versus the number of round running relating to different algorithms is given in Figure14.Figure 14
Number of survival nodes of WSNs versus round running.It can be seen from Figure14 that with the operation of the network, the curves corresponding to four algorithms have a cliff-like downward trend. When the first dead node appears in the network, the round of running of CEED, DMATEB, IMHT-LEACH, and MHRA-PT is 410, 439, 617, and 864, respectively. Compared with the other algorithms, the MHRA-PT algorithm is the latest when the first dead node appears and prolongs the death time of the first node: 110.7%, 96.8%, and 40%, respectively. Besides, compared with the other algorithms, the MHRA-PT algorithm prolongs the death time of all nodes (31.3%, 31.9%, and 18.7%, respectively). This is because the MHRA-PT algorithm preferentially uses the working nodes with large residual energy in each round of operation and constructs the path tree for the cluster head when transmitting data, thereby effectively delaying death time of the node. According to the above analysis, the MHRA-PT algorithm can effectively prolong the life cycle of WSNs.


## 7. Conclusions

It is important to solve the problem of sensor node energy consumption in WSNs. Based on the LEACH algorithm, this paper comprehensively considers the impact of cluster head selection, working node selection, and data transmission path selection on network energy consumption, and the MHRA-PT algorithm based on path tree is proposed for network energy reduction and balance. This algorithm combines the probability of node being selected as cluster head, the distance factor between node and base station, and the node’s residual energy factor to improve cluster head selection threshold. Within each cluster, an eight-part region partition method is introduced to reduce the number of working nodes; besides, a path tree is constructed and the transmission path from the cluster head to the base station is optimized too. The proposed MHRA-PT algorithm can effectively reduce cluster head energy consumption, balance network energy consumption, and prolong the network life cycle.



---

*Source: 6671978-2021-04-28.xml*