# An Energy-Balanced Mechanism for Hierarchical Routing in Wireless Sensor Networks

Authors: Zhenjiang Zhang; Yanan Wang; Fuxing Song; Wenyu Zhang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In wireless sensor networks (WSNs), energy-constrained sensor nodes are always deployed in hazardous and inaccessible environments, making energy management a key problem for network design. The mechanism of RNTA (redundant node transmission agents) lacks an updating mechanism for the redundant nodes, causing an unbalanced energy distribution among sensor nodes. This paper presents an energy-balanced mechanism for hierarchical routing (EBM-HR), in which the residual energy of redundant nodes is quantified and made hierarchic, so that the cluster head can dynamically select the redundant node with the highest residual energy grade as a relay to complete the information transmission to the sink node and achieve an intracluster energy balance. In addition, the network is divided into several layers according to the distances between cluster heads and the sink node. Based on the energy consumption of the cluster heads, the sink node will decide to recluster only in a certain layer so as to achieve an intercluster energy balance. Our approach is evaluated by a simulation comparing the LEACH algorithm to the HEED algorithm. The results demonstrate that the BEM-HR mechanism can significantly boost the performance of a network in terms of network lifetime, data transmission quality, and energy balance.


---

## Body

## 1. Introduction

The wireless sensor network (WSN) is a dynamic network that has properties of large-scale, self-organization, and strong concealment ability. It is widely used in many applications, such as temperature acquisition [1], volcanic earthquake detection [2], environmental monitoring [3], and military applications [4].A wireless sensor network (WSN) is composed of a large number of small-scale sensor nodes that have the abilities of perception, calculation, and wireless communication [5]. These battery-powered sensor nodes are randomly deployed across the monitoring area, so it is difficult to recharge the batteries with limited energy. In most cases, sensor nodes are employed in harsh environments where humans could not access them, so the replacement of batteries is very difficult to achieve.The energy consumption of sensor nodes is mainly for sensing data of physical phenomena, processing the information, and communicating with other nodes. In fact, more energy is required for the data communication than any other process. The energy cost for transmitting 1 Kb a distance of 100 meters (330 ft) is approximately the same as that used for the execution of 3 million instructions by a 100 million instructions per second/W processor [6]. Therefore, the prime goal is to minimize the energy consumption of the communication so as to prolong the lifetime of the entire network. The communication protocol is based on clustering and is a kind of energy-efficient routing protocol. The cluster heads are responsible for the information exchange between clusters and the sink node, thus effectively reducing the communication cost of cluster members.However, the communication protocol based on clustering, to a certain extent, accelerates energy consumption by the cluster heads. Given the situation that some redundant nodes are temporarily closed to be spare sensors when a large number of sensor nodes are deployed, our prior work [7] puts forward a transmission mechanism using redundant nodes, which realizes the information exchange between the clusters and base station, thus decreasing the energy consumption of the normal nodes and the cluster heads. Although this approach can significantly reduce the network energy consumption, it lacks an updating mechanism for the redundant nodes. Once the relay node is dead, the relay tree will also be destroyed, causing an unbalanced distribution of residual energy among the sensor nodes. Addressing the defects of RNTA, we propose an energy-balanced mechanism for hierarchical routing in which the residual energy of redundant nodes is quantified and hierarchic, so the cluster head can dynamically select the redundant node with the highest energy grade as a relay for completing the information transmission from clusters to the sink node. When the residual energy grade of the redundant node that is selected as a relay node drops, the cluster head will reselect a new redundant node as a relay to achieve an intracluster energy balance.Obviously, only realizing that the intracluster energy balance cannot guarantee the energy balance of the entire network, based on the literature survey, the lifetime of the entire network is related to the number of dead nodes. When the proportion of dead nodes exceeds a certain threshold, the network cannot operate normally. So, how to balance the energy of every sensor node efficiently enough to prolong the network lifetime, based on the premise of not affecting the function of WSN, becomes a prime target for the design of the network. In addition, the unbalanced energy consumption dramatically reduces the lifetime of the network. However, when the energy consumption of the whole network is balanced, the death time for some nodes is extended, and thus the lifetime of the whole network is extended.Applying the above theories, the network can be divided into several layers based on the distances between the cluster heads and the sink node. Then, according to the energy consumption of the cluster heads, the sink node will decide to recluster in a certain layer, thus avoiding the reclustering in the entire network and achieving an intercluster energy balance. Hence, the proposed mechanism can produce a suitable trade-off of energy balance between the intracluster and the intercluster and prolong the lifetime of the entire network.The remainder of this paper is organized as follows: Section2 reviews related work on hierarchical routing algorithms. Section 3 introduces the energy-balanced mechanism for hierarchical routing (EBM-HR) in detail. Section 4 provides simulations and results for EBM-HR, LEACH, and HEED. The conclusion for this paper is offered in Section 5.


## 2. Related Work

The hierarchical routing protocol based on clustering not only can effectively reduce the amount of energy consumption of nodes, but also can alleviate the impact on routing protocol due to topology changes, so the protocol has wider academic value. At present, the hierarchical routing protocol contains LEACH, PEGASIS, TEEN, HEED, and other algorithms.LEACH is the low power, adaptive clustering, hierarchical routing protocol of Heinzelman et al. [8] for the design of WSNs. It uses the concept of “round,” and each round contains two stages: the establishment of the cluster and steady work. LEACH randomly selects cluster heads, which address the average share of relay communication tasks. It also applies data fusion technology to the routing protocol, which reduces the amount of data transmitted from the cluster head to the sink node. Due to improvements in these two aspects, namely, the number of nodes directly communicating with the base station and the communication volume between nodes, the protocol can effectively reduce energy consumption and prolong the life of the network. However, it does contain some problems, such that the distribution of cluster heads is uneven and the cluster head communication consumes too much energy. Accordingly, they put forward the LEACH_C protocol (LEACH centralized) [9] which was an improvement on the LEACH protocol. It uses global information to select the cluster heads, according to the current energy needed to select the cluster head, thus no longer strictly based on equal probability. In this way, the nodes with higher energy will be more easily selected as the cluster head.Later, Lindsey and Raghavendra [10] proposed the PEGASIS protocol, which presents a greedy algorithm used to choose the nearest nodes to form a chain and select a certain node as the head node in the chain directly, thereby communicating with the sink node, so the data are transmitted from both ends of the chain. Because of the low power needed for the communication of the nearest nodes, this way reduces the communication traffic. Therefore, it can prolong the network lifetime more efficiently than LEACH. TEEN (threshold sensitive energy-efficient sensor network protocol) made two improvements using the LEACH protocol. The single level structure is improved to become a multilevel structure. That is to say, the cluster head generates the multilevel cluster structure according to the different distances to the sink node. The other uses the threshold decision to reduce the amount of data transmission for the network. Younis and Fahmy [11] put forward the hybrid energy-efficient distributed (HEED) clustering algorithm, which aimed at the uneven distribution of cluster heads. It regarded the average minimum reach ability power in the cluster as a measure of communication cost. During the selection process of the cluster head, it treated the residual energy of each node and the intracluster communication cost as the parameters of clustering, so that the cluster head selected using this approach is more suitable for affording the data transmission tasks and thus prolongs the lifetime of the entire network.The aforementioned approaches can prolong the network lifetime to different degrees, but they cannot realize the energy balance of all the nodes. When the energy consumption of the whole network is balanced, the death time of some nodes will be extended, and thus the lifetime of the whole network will be prolonged. This paper proposes an energy-balanced mechanism for hierarchical routing, which can realize an energy balance of all the nodes to prolong the lifetime of the network.


## 3. An Energy-Balanced Mechanism for Hierarchical Routing

This section puts forward the specific algorithm and realization steps for the energy-balanced mechanism. The objective of the scheme is to jointly realize the energy balance for both the intracluster and intercluster to minimize the overall energy consumption and thus prolong network lifetime.


### 3.1. Network Model

This paper assumes that the wireless sensor network contains one sink node andN ordinary nodes, which are randomly sprinkled in the monitoring field. Each node is assigned a node ID (identification number) which is convenient for distinguishing different nodes during the routing process. Moreover, we consider a WSN with the following properties.(1)
To guarantee the existence of enough redundant nodes, a large number of sensor nodes should be deployed in the monitoring area.
(2)
This WSN is a static network, which means all the sensor nodes are fixed in a two-dimensional field and cannot change position arbitrarily.
(3)
Sensor nodes are not location-aware; that is, the sink node will estimate the distribution of the whole network, depending on the transmission data packets. Each sensor node is characterized by a circular transmission range and a carrier-sensing range.
(4)
All nodes have the capacity for data fusion, since each node can be selected as the cluster head.
(5)
The energy of each node is limited, and the battery cannot be recharged. Each node is free to adjust the transmission power to save energy, according to the distance between itself and the receiver.
(6)
The clustering process is fully distributed, and each node can make decisions independently, but only based on its local information.


### 3.2. Establishment of the Cluster

#### 3.2.1. Selection of Cluster Heads

Since the LEACH algorithm is simple and efficient, but also suitable for our application scenario, we chose the LEACH protocol to use for selecting cluster heads. The cluster head selection algorithm in LEACH is described as follows. Each sensor node randomly generates a number between 0 and 1. If the random number of a sensor node is less than a thresholdT
(
n
), then the node will be selected as a cluster head in the current round. T
(
n
) can be expressed as(1)
T
n
=
p
1
-
p
×
r
mod
⁡
p
-
1
,
n
∈
G
0
,
n
∉
G
,where p denotes the probability of becoming the cluster head, r denotes the number of selection rounds, and G denotes the nodes’ set, which consists of the nodes that have not been selected as cluster heads in round r. r mod (1
/
p) denotes the number of nodes that have been selected as cluster heads in round r.In the following rounds, we introduce residual energy into the cluster head selection. Namely, the nodes with higher residual energy have a higher probability of being selected as cluster heads. The probability of a node becoming a cluster head is thus calculated according to the following formula:(2)
p
head
=
p
×
E
res
E
ave
,where p and p
head, respectively, denote the probabilities of becoming the cluster head before and after the merging of residual energy, E
res is the residual energy value of the current node, and E
ave is the average energy of the entire network. Therefore, nodes with higher residual energy have higher thresholds and are the most likely to be selected as cluster heads. Then, the elected node will broadcast an invitation message to notify other nodes that it will be a cluster head and want to recruit its neighbors. Upon receiving that invitation, the neighboring sensor nodes will join the nearest cluster and become members of that cluster, and thus the establishment of clusters is completed. In particular, in each round, if a node has been selected as a cluster head, its T
(
n
) is set to zero, so that this node will not be selected as a cluster head again.The establishment of the cluster is described as in Algorithm1.Algorithm 1
(1)Begin
/∗Select cluster heads∗/
(2)If (random(0.1) < T
(
n
))
(3)  node.state = head
(4)  Broadcast, Head_msg(ID)
(5)End if
(6)Node i receives Head_msg from cluster head j
1
,
j
2
…
(7)If distance(i
,
j
x) < min_distance and node.state = common
(8) .Min_distance = d
(
i
,
j
x
)
(9) .Node i.head = j
x
(10)Send(Join_msgID, node.head);
(11)  End if


#### 3.2.2. The Identification of Redundant Nodes and Relay Nodes

A wireless sensor network of random deployment usually contains a large number of sensor nodes; thus some nodes will monitor the same area, resulting in a redundancy of information. At the same time, these nodes that are transmitting similar information will cause unnecessary energy consumption. In addition, energy consumption in the wireless communication module then accounts for the largest proportion of the total energy consumption. Therefore, to reduce energy consumption and prolong network lifetime, it is necessary to discover and identify the redundant nodes and turn them off to save energy. However, identifying the redundant nodes is a key problem. Most of the algorithms utilize geographic and radio technology to identify which nodes may be the redundant nodes by obtaining useful location information. However, [12] introduces a cluster-based algorithm for redundant node discovery in dense sensor networks. The algorithm supports identifying redundant nodes without additional GPS and directional antennas. The definition of a redundant node is that it has several neighboring cluster head nodes in its sensing range.Since the residual energy of each node is quantified and hierarchical periodically, when the redundant nodes are identified by the previously mentioned algorithm, they will, respectively, send their energy grades to the corresponding cluster heads. Then, the cluster head will select the redundant node that has the highest residual energy grade as a relay node and then transmit the fused data packets to it, informing it to forward the data to the next hop cluster head. If there is no redundant node in the cluster, the ordinary node with the highest residual energy will be selected as a relay node.


### 3.3. The Intracluster Energy-Balanced Mechanism

The general clustering algorithm is described as follows. Ordinary nodes transmit the sensed data to the cluster head to which they belong. Then, the cluster head implements the local data fusion and sends the data packets directly to the sink node. If so, the cluster head is under too much pressure and accelerates the rate of energy consumption, resulting in an energy unbalance of the cluster. In addition, although in our prior work [1] we presented the mechanism of redundant node transmission agents, that process also results in an unbalanced distribution of intracluster residual energy. Therefore, we make a further effort to present an energy-balanced mechanism for hierarchical routing (EBM-HR), wherein the residual energy of the redundant nodes is quantified and hierarchical. At the same time, the cluster head dynamically selects the redundant node with the highest energy grade as a relay to complete the information transmission between cluster heads and the sink node to achieve intracluster energy balance.


#### 3.3.1. Power Control Model

In our previous work, we adopted the power model from the literature [13, 14] wherein the definition of the data transmitting power from node i to node k is as follows:(3)
p
t
i
,
k
=
α
+
β
d
i
k
m
·
f
i
k
,where f
i
k denotes the information rate from the node i to the node k, d
i
k denotes the distance between the node i and node k, α, β are distance parameters of energy when receiving the data, and m is the path loss parameter.However, we adopted a kind of power control model [15], thereby embedding the residual energy into the proposed mechanism. The data transmitting power is defined as(4)
p
i
∗
=
n
i
G
i
i
β
∗
W
/
R
-
N
-
1
β
∗
E
i
E
T
,where n
i denotes the power of Gauss white noise, G
i
i denotes the channel gain information of the receiver, β is a unique solution, R denotes the transmission rate, W denotes the bandwidth, N is the number of receiving terminals, E
T denotes the total energy, and E
i denotes the residual energy of the node. When the residual energy of a node is decreasing, the value of the ratio E
i
/
E
T is also decreasing, so that the node will transmit data using low power. In this way, we can achieve the purpose, which is using less transmitting power when the residual energy is decreasing. Therefore, as long as each node knows its residual energy and channel gain information, it can implement power control in a distributed way, thus reducing the rate of energy consumption.


#### 3.3.2. The Realization of Intracluster Energy Balance

In each cluster, there are three kinds of nodes: cluster head node, redundant node, and ordinary node. In the proposed approach, the energy consumption of these three nodes is completely different, so how to realize energy balance among them becomes a key problem. The various tasks of the different kinds of nodes are described as follows.(i)
Cluster head node: it receives information from neighboring nodes, implements data fusion, and transmits data packets to the redundant node, which is treated as a relay node.
(ii)
Redundant node: most of the redundant nodes are in a sleeping state, unless one node is selected as the relay node. The relay node receives data packets from the cluster head and then transmits them to the next hop.
(iii)
Ordinary node: it senses information in the monitoring field and transmits the collected data packets to their own cluster head.Research has shown that the ways of energy consumption are different for these kinds of nodes, even for the same kind of nodes. If we want to realize the network balance from energy consumption, the situation will be very complex. However, although the ways of energy consumption are various, the degree of residual energy can always be determined. Moreover, the node can adaptively adjust its transmitting power according to the residual energy, just like what we describe here in Section3.3.1. Thus, we can achieve the purpose of energy balance.The redundant node that is selected as a relay node will consume relatively more energy due to transmitting more data packets. In the wake of the continual reduction of energy, the sending power of each relay node will be smaller, which prolongs the lifetime of the node to a certain extent. However, the decline of power can also affect service quality. In addition, once the relay node is dead, the relay tree will be destroyed, causing an unbalanced distribution of residual energy among the sensor nodes.In view of these problems, the residual energy of redundant nodes can be periodically quantified and made hierarchical. The redundant nodes report their energy grades to the cluster head, and then the cluster head selects a redundant node with the highest energy grade as the relay used to transmit the data packets. Further, under the control of the cluster head, redundant nodes are dynamically selected as relays. Namely, when the energy grade of the relay node reduces by one level, the cluster head will reselect another redundant node with the highest energy grade as a new relay node. In this way, we can provide an updating mechanism for the redundant nodes and achieve dynamic balance energy in the whole cluster.Therefore, in order to control the average energy in the cluster, the cluster head needs to maintain an energy table on the residual energy grades of the redundant nodes. The content of energy table is configured as shown in Table1.Table 1
Node ID ofredundant node
Node’s state
Residual energy grade (1–5)
2
Agent transmission
5
5
Dormancy
4
8
Dormancy
4
⋯
⋯
⋯From the table, we can see that each node in the cluster is assigned its own ID in advance. The node ID is the communication address of the redundant node, which is convenient for the cluster head to use to master the identification information for each redundant node in the cluster. A node’s state refers to the two states of redundant nodes, that is, dormancy and agent transmission. Since number 2 node has the highest energy grade, it will be selected as a relay node. After the cluster head selects the redundant node with the highest energy as a transmission relay, other redundant nodes in the same cluster go into a sleeping state to conserve energy for the next round and its selection of a relay node. The residual energy is quantified into five grades. If the value of an energy grade declines by one level, the cluster head will reselect a new redundant node with the highest energy grade to replace the previous relay node.Further, in order to prevent the data loss of the main energy table resulting from the system failure, each cluster head will send a standby energy table to the nearest member node periodically. If the data of the main table is lost, the cluster head will send a standby table request to the member node. Once the member node receives that request, it will send the latest standby energy table to the cluster head. In this way, we can guarantee that the cluster head will in a timely fashion continue to select the redundant node with the highest energy grade as the relay node to use to complete the transmission.The realization of intracluster energy balance is shown in Algorithm2.Algorithm 2
(1) In a cluster, head sends ASK_msg to its nodes
(2) If node.state = redundancy
(3)Send Energy_msgresidual energy grade, ID, node → head
(4)If E
res ≥ max_E and node.status = dormancy
(5)Node.status = relay
(6)End if
(7) End if
(8) Relay node transmits data, it’s transmitting power was controlled.
(9) Detect periodically, whenE
res changes, reselect the relay node, turn to step (1)


### 3.4. An Intercluster Energy-Balanced Mechanism

In the previous section, the cluster head dynamically selects the redundant node as the relay to achieve intracluster energy balance. However, it cannot realize the intercluster energy balance. The cluster head close to the sink node will accelerate its rate of energy consumption due to always forwarding the data packets of remote relays. If the energy of a cluster head has been depleted, the entire network clustering again will consume a lot of unnecessary energy. Therefore, the proposed energy-balanced mechanism will divide the network into several layers based on the distances between the cluster heads and the sink node. The sink node will master a table on energy consumption of all the cluster heads. When the energy of a cluster head is too low in a certain layer, the sink node will decide to recluster in the corresponding layer, thereby bringing no influence to other layers. The simulation can prove that this mechanism can realize the intercluster energy balance.


#### 3.4.1. Hierarchical Routing Process of the Entire Network

(1
) Measure the Relative Distances between Cluster Heads and the Sink Node. After the selection of a cluster head, the sink node will send a broadcasted message to all the cluster heads. When the cluster head receives the broadcast signal, it will calculate the relatively approximate distance to the sink node based on the received signal strength. Then, it will send its ID number and the value of the approximate distance to the sink node. Therefore, the sink node can master a control table of distances to all the cluster heads and estimate the distribution of the clusters.(2
) Layer the Network. According to the control table, the entire network is divided into several layers by the sink node. The nearest clusters are divided in the first layer. Similarly, the distant clusters are divided in the second layer and so on. To alleviate the neighboring hot spot effects of the sink node, the node number of the first layer should be more than other layers, while the last layer has the fewest nodes. After layering, the sink node will broadcast a data table about the layer result to the entire network. It will consist of the ID numbers of all the cluster heads and the corresponding layers. Because each member node knows the ID number of its cluster head, it can check the data table and know which layer it belongs to. The number of layers is defined as follows:(5)
k
=
α
L
r
,where L is the largest coverage radius of the entire network, r is the coverage radius of each sensor node, and α is a parameter of the monitoring field.(3
) The Process of Routing. After layering, each layer contains one or more cluster heads. Then, the cluster head will find the nearest cluster head nodes from the upper and lower layers. The cluster heads from different layers communicate with each other, so the routing is formed. However, to reduce energy consumption, cluster heads only complete data fusion and transmit the data packet to the relay node in the same cluster. Then, the relay node sends them to the next hop, namely, the cluster head of the upper layer. That is to say, the data packets are transferred from the relay node for the lower layer to the cluster head for the upper layer.The hierarchical routing process is shown in Algorithm3.Algorithm 3
(1)Sink, broadcast, Sink_msg(ID)
(2)Head i, send, Res_msgID, d
i
s
t
a
n
c
e
→sink, i
=
1,2
,
3
,
…
,
n,  n is the total number of nodes.
(3)Sink node divides the network into k layers
(4)Sink, broadcast, Lay_msgID, j, j
=
1,2
,
3
,
…
,
k
(5)Node i.level = j
(6)Head i broadcasts Route_msg(ID, Node.level)
(7)If node j.level ≠ 1
(8) If node j.state = head and node i.level = node j.level − 1
(9)  Node i receives Route_msg from cluster head j
(10)  Node j.next_hop = Node i
(11)   End if
(12) else if nodej.level = 1
(13) Nodej.next_hop = sink;
(14) End if
(15) Cluster_head tell redundant node the next_hop


#### 3.4.2. The Realization of Intercluster Energy Balance

The cluster head can control the energy balance of the intracluster nodes. At the same time, it can monitor its residual energy, sending its ID number and the value of energy to the sink node through the data packet. Then, the sink node can master whether the energy is balanced or not balanced among all the clusters. When the sink node receives the value of all the cluster heads, it can calculate a ratio as follows:(6)
e
i
=
E
i
E
,
E
=
1
n
∑
i
=
1
n
E
i
,where E
i denotes the residual energy of the current cluster head and E denotes the average value of the residual energy of all the cluster heads. If the value of e
i is less than 1 that means that the energy consumption of the cluster head is unbalanced and needs a cluster again. However, the sink node only sends a message to the layer to which the current cluster head with the lowest energy belongs, thus indicating that all the nodes in the same layer need to dismiss their former clusters and cluster again. The layering mechanism of the network was introduced in the last section.Therefore, to control the average energy among all the clusters, the sink node needs to maintain an energy table for the residual energy of the cluster heads. Just like the energy table of the cluster head, the sink node will also send a standby energy table to the nearest node periodically.The content of energy table is configured as shown in Table2.Table 2
ID of cluster head
The layer clusterhead belongs to
The residualenergy E
i
e
i
12
1
0.1
0.33
25
2
0.3
1
32
2
0.5
1.67
⋯
⋯
⋯
⋯Among all the clusters, each cluster head has also its own ID number in advance. If only one layer’s cluster energy consumption is unbalanced and the cluster head consumes energy quickly (such as the emergency center), the sink node will reselect the cluster heads in only one layer and cluster again under certain conditions. In this way, we can avoid the result where the entire network clusters again and realize the energy balance of the entire network. The value of residual energy is a standard to measure whether the cluster head can continue to work or cannot. When the energy of the whole network reduces to a very small value, the network will enter the stage of establishing again, deploying new nodes, layering, implementing cluster reconstruction, and so on. Namely, it does that by repeating the above steps.The realization of intercluster energy balance is shown in Algorithm4.Algorithm 4
(1) Sink, receive head_residual energy
(2) Sink calculate average energy:E and ratio e
i
(3) If ratioe
i, less than 1, belong to layer j
(4)   Recluster in the certain layerj
(5)   Rerouting
(6) End if


## 3.1. Network Model

This paper assumes that the wireless sensor network contains one sink node andN ordinary nodes, which are randomly sprinkled in the monitoring field. Each node is assigned a node ID (identification number) which is convenient for distinguishing different nodes during the routing process. Moreover, we consider a WSN with the following properties.(1)
To guarantee the existence of enough redundant nodes, a large number of sensor nodes should be deployed in the monitoring area.
(2)
This WSN is a static network, which means all the sensor nodes are fixed in a two-dimensional field and cannot change position arbitrarily.
(3)
Sensor nodes are not location-aware; that is, the sink node will estimate the distribution of the whole network, depending on the transmission data packets. Each sensor node is characterized by a circular transmission range and a carrier-sensing range.
(4)
All nodes have the capacity for data fusion, since each node can be selected as the cluster head.
(5)
The energy of each node is limited, and the battery cannot be recharged. Each node is free to adjust the transmission power to save energy, according to the distance between itself and the receiver.
(6)
The clustering process is fully distributed, and each node can make decisions independently, but only based on its local information.


## 3.2. Establishment of the Cluster

### 3.2.1. Selection of Cluster Heads

Since the LEACH algorithm is simple and efficient, but also suitable for our application scenario, we chose the LEACH protocol to use for selecting cluster heads. The cluster head selection algorithm in LEACH is described as follows. Each sensor node randomly generates a number between 0 and 1. If the random number of a sensor node is less than a thresholdT
(
n
), then the node will be selected as a cluster head in the current round. T
(
n
) can be expressed as(1)
T
n
=
p
1
-
p
×
r
mod
⁡
p
-
1
,
n
∈
G
0
,
n
∉
G
,where p denotes the probability of becoming the cluster head, r denotes the number of selection rounds, and G denotes the nodes’ set, which consists of the nodes that have not been selected as cluster heads in round r. r mod (1
/
p) denotes the number of nodes that have been selected as cluster heads in round r.In the following rounds, we introduce residual energy into the cluster head selection. Namely, the nodes with higher residual energy have a higher probability of being selected as cluster heads. The probability of a node becoming a cluster head is thus calculated according to the following formula:(2)
p
head
=
p
×
E
res
E
ave
,where p and p
head, respectively, denote the probabilities of becoming the cluster head before and after the merging of residual energy, E
res is the residual energy value of the current node, and E
ave is the average energy of the entire network. Therefore, nodes with higher residual energy have higher thresholds and are the most likely to be selected as cluster heads. Then, the elected node will broadcast an invitation message to notify other nodes that it will be a cluster head and want to recruit its neighbors. Upon receiving that invitation, the neighboring sensor nodes will join the nearest cluster and become members of that cluster, and thus the establishment of clusters is completed. In particular, in each round, if a node has been selected as a cluster head, its T
(
n
) is set to zero, so that this node will not be selected as a cluster head again.The establishment of the cluster is described as in Algorithm1.Algorithm 1
(1)Begin
/∗Select cluster heads∗/
(2)If (random(0.1) < T
(
n
))
(3)  node.state = head
(4)  Broadcast, Head_msg(ID)
(5)End if
(6)Node i receives Head_msg from cluster head j
1
,
j
2
…
(7)If distance(i
,
j
x) < min_distance and node.state = common
(8) .Min_distance = d
(
i
,
j
x
)
(9) .Node i.head = j
x
(10)Send(Join_msgID, node.head);
(11)  End if


### 3.2.2. The Identification of Redundant Nodes and Relay Nodes

A wireless sensor network of random deployment usually contains a large number of sensor nodes; thus some nodes will monitor the same area, resulting in a redundancy of information. At the same time, these nodes that are transmitting similar information will cause unnecessary energy consumption. In addition, energy consumption in the wireless communication module then accounts for the largest proportion of the total energy consumption. Therefore, to reduce energy consumption and prolong network lifetime, it is necessary to discover and identify the redundant nodes and turn them off to save energy. However, identifying the redundant nodes is a key problem. Most of the algorithms utilize geographic and radio technology to identify which nodes may be the redundant nodes by obtaining useful location information. However, [12] introduces a cluster-based algorithm for redundant node discovery in dense sensor networks. The algorithm supports identifying redundant nodes without additional GPS and directional antennas. The definition of a redundant node is that it has several neighboring cluster head nodes in its sensing range.Since the residual energy of each node is quantified and hierarchical periodically, when the redundant nodes are identified by the previously mentioned algorithm, they will, respectively, send their energy grades to the corresponding cluster heads. Then, the cluster head will select the redundant node that has the highest residual energy grade as a relay node and then transmit the fused data packets to it, informing it to forward the data to the next hop cluster head. If there is no redundant node in the cluster, the ordinary node with the highest residual energy will be selected as a relay node.


## 3.2.1. Selection of Cluster Heads

Since the LEACH algorithm is simple and efficient, but also suitable for our application scenario, we chose the LEACH protocol to use for selecting cluster heads. The cluster head selection algorithm in LEACH is described as follows. Each sensor node randomly generates a number between 0 and 1. If the random number of a sensor node is less than a thresholdT
(
n
), then the node will be selected as a cluster head in the current round. T
(
n
) can be expressed as(1)
T
n
=
p
1
-
p
×
r
mod
⁡
p
-
1
,
n
∈
G
0
,
n
∉
G
,where p denotes the probability of becoming the cluster head, r denotes the number of selection rounds, and G denotes the nodes’ set, which consists of the nodes that have not been selected as cluster heads in round r. r mod (1
/
p) denotes the number of nodes that have been selected as cluster heads in round r.In the following rounds, we introduce residual energy into the cluster head selection. Namely, the nodes with higher residual energy have a higher probability of being selected as cluster heads. The probability of a node becoming a cluster head is thus calculated according to the following formula:(2)
p
head
=
p
×
E
res
E
ave
,where p and p
head, respectively, denote the probabilities of becoming the cluster head before and after the merging of residual energy, E
res is the residual energy value of the current node, and E
ave is the average energy of the entire network. Therefore, nodes with higher residual energy have higher thresholds and are the most likely to be selected as cluster heads. Then, the elected node will broadcast an invitation message to notify other nodes that it will be a cluster head and want to recruit its neighbors. Upon receiving that invitation, the neighboring sensor nodes will join the nearest cluster and become members of that cluster, and thus the establishment of clusters is completed. In particular, in each round, if a node has been selected as a cluster head, its T
(
n
) is set to zero, so that this node will not be selected as a cluster head again.The establishment of the cluster is described as in Algorithm1.Algorithm 1
(1)Begin
/∗Select cluster heads∗/
(2)If (random(0.1) < T
(
n
))
(3)  node.state = head
(4)  Broadcast, Head_msg(ID)
(5)End if
(6)Node i receives Head_msg from cluster head j
1
,
j
2
…
(7)If distance(i
,
j
x) < min_distance and node.state = common
(8) .Min_distance = d
(
i
,
j
x
)
(9) .Node i.head = j
x
(10)Send(Join_msgID, node.head);
(11)  End if


## 3.2.2. The Identification of Redundant Nodes and Relay Nodes

A wireless sensor network of random deployment usually contains a large number of sensor nodes; thus some nodes will monitor the same area, resulting in a redundancy of information. At the same time, these nodes that are transmitting similar information will cause unnecessary energy consumption. In addition, energy consumption in the wireless communication module then accounts for the largest proportion of the total energy consumption. Therefore, to reduce energy consumption and prolong network lifetime, it is necessary to discover and identify the redundant nodes and turn them off to save energy. However, identifying the redundant nodes is a key problem. Most of the algorithms utilize geographic and radio technology to identify which nodes may be the redundant nodes by obtaining useful location information. However, [12] introduces a cluster-based algorithm for redundant node discovery in dense sensor networks. The algorithm supports identifying redundant nodes without additional GPS and directional antennas. The definition of a redundant node is that it has several neighboring cluster head nodes in its sensing range.Since the residual energy of each node is quantified and hierarchical periodically, when the redundant nodes are identified by the previously mentioned algorithm, they will, respectively, send their energy grades to the corresponding cluster heads. Then, the cluster head will select the redundant node that has the highest residual energy grade as a relay node and then transmit the fused data packets to it, informing it to forward the data to the next hop cluster head. If there is no redundant node in the cluster, the ordinary node with the highest residual energy will be selected as a relay node.


## 3.3. The Intracluster Energy-Balanced Mechanism

The general clustering algorithm is described as follows. Ordinary nodes transmit the sensed data to the cluster head to which they belong. Then, the cluster head implements the local data fusion and sends the data packets directly to the sink node. If so, the cluster head is under too much pressure and accelerates the rate of energy consumption, resulting in an energy unbalance of the cluster. In addition, although in our prior work [1] we presented the mechanism of redundant node transmission agents, that process also results in an unbalanced distribution of intracluster residual energy. Therefore, we make a further effort to present an energy-balanced mechanism for hierarchical routing (EBM-HR), wherein the residual energy of the redundant nodes is quantified and hierarchical. At the same time, the cluster head dynamically selects the redundant node with the highest energy grade as a relay to complete the information transmission between cluster heads and the sink node to achieve intracluster energy balance.


### 3.3.1. Power Control Model

In our previous work, we adopted the power model from the literature [13, 14] wherein the definition of the data transmitting power from node i to node k is as follows:(3)
p
t
i
,
k
=
α
+
β
d
i
k
m
·
f
i
k
,where f
i
k denotes the information rate from the node i to the node k, d
i
k denotes the distance between the node i and node k, α, β are distance parameters of energy when receiving the data, and m is the path loss parameter.However, we adopted a kind of power control model [15], thereby embedding the residual energy into the proposed mechanism. The data transmitting power is defined as(4)
p
i
∗
=
n
i
G
i
i
β
∗
W
/
R
-
N
-
1
β
∗
E
i
E
T
,where n
i denotes the power of Gauss white noise, G
i
i denotes the channel gain information of the receiver, β is a unique solution, R denotes the transmission rate, W denotes the bandwidth, N is the number of receiving terminals, E
T denotes the total energy, and E
i denotes the residual energy of the node. When the residual energy of a node is decreasing, the value of the ratio E
i
/
E
T is also decreasing, so that the node will transmit data using low power. In this way, we can achieve the purpose, which is using less transmitting power when the residual energy is decreasing. Therefore, as long as each node knows its residual energy and channel gain information, it can implement power control in a distributed way, thus reducing the rate of energy consumption.


### 3.3.2. The Realization of Intracluster Energy Balance

In each cluster, there are three kinds of nodes: cluster head node, redundant node, and ordinary node. In the proposed approach, the energy consumption of these three nodes is completely different, so how to realize energy balance among them becomes a key problem. The various tasks of the different kinds of nodes are described as follows.(i)
Cluster head node: it receives information from neighboring nodes, implements data fusion, and transmits data packets to the redundant node, which is treated as a relay node.
(ii)
Redundant node: most of the redundant nodes are in a sleeping state, unless one node is selected as the relay node. The relay node receives data packets from the cluster head and then transmits them to the next hop.
(iii)
Ordinary node: it senses information in the monitoring field and transmits the collected data packets to their own cluster head.Research has shown that the ways of energy consumption are different for these kinds of nodes, even for the same kind of nodes. If we want to realize the network balance from energy consumption, the situation will be very complex. However, although the ways of energy consumption are various, the degree of residual energy can always be determined. Moreover, the node can adaptively adjust its transmitting power according to the residual energy, just like what we describe here in Section3.3.1. Thus, we can achieve the purpose of energy balance.The redundant node that is selected as a relay node will consume relatively more energy due to transmitting more data packets. In the wake of the continual reduction of energy, the sending power of each relay node will be smaller, which prolongs the lifetime of the node to a certain extent. However, the decline of power can also affect service quality. In addition, once the relay node is dead, the relay tree will be destroyed, causing an unbalanced distribution of residual energy among the sensor nodes.In view of these problems, the residual energy of redundant nodes can be periodically quantified and made hierarchical. The redundant nodes report their energy grades to the cluster head, and then the cluster head selects a redundant node with the highest energy grade as the relay used to transmit the data packets. Further, under the control of the cluster head, redundant nodes are dynamically selected as relays. Namely, when the energy grade of the relay node reduces by one level, the cluster head will reselect another redundant node with the highest energy grade as a new relay node. In this way, we can provide an updating mechanism for the redundant nodes and achieve dynamic balance energy in the whole cluster.Therefore, in order to control the average energy in the cluster, the cluster head needs to maintain an energy table on the residual energy grades of the redundant nodes. The content of energy table is configured as shown in Table1.Table 1
Node ID ofredundant node
Node’s state
Residual energy grade (1–5)
2
Agent transmission
5
5
Dormancy
4
8
Dormancy
4
⋯
⋯
⋯From the table, we can see that each node in the cluster is assigned its own ID in advance. The node ID is the communication address of the redundant node, which is convenient for the cluster head to use to master the identification information for each redundant node in the cluster. A node’s state refers to the two states of redundant nodes, that is, dormancy and agent transmission. Since number 2 node has the highest energy grade, it will be selected as a relay node. After the cluster head selects the redundant node with the highest energy as a transmission relay, other redundant nodes in the same cluster go into a sleeping state to conserve energy for the next round and its selection of a relay node. The residual energy is quantified into five grades. If the value of an energy grade declines by one level, the cluster head will reselect a new redundant node with the highest energy grade to replace the previous relay node.Further, in order to prevent the data loss of the main energy table resulting from the system failure, each cluster head will send a standby energy table to the nearest member node periodically. If the data of the main table is lost, the cluster head will send a standby table request to the member node. Once the member node receives that request, it will send the latest standby energy table to the cluster head. In this way, we can guarantee that the cluster head will in a timely fashion continue to select the redundant node with the highest energy grade as the relay node to use to complete the transmission.The realization of intracluster energy balance is shown in Algorithm2.Algorithm 2
(1) In a cluster, head sends ASK_msg to its nodes
(2) If node.state = redundancy
(3)Send Energy_msgresidual energy grade, ID, node → head
(4)If E
res ≥ max_E and node.status = dormancy
(5)Node.status = relay
(6)End if
(7) End if
(8) Relay node transmits data, it’s transmitting power was controlled.
(9) Detect periodically, whenE
res changes, reselect the relay node, turn to step (1)


## 3.3.1. Power Control Model

In our previous work, we adopted the power model from the literature [13, 14] wherein the definition of the data transmitting power from node i to node k is as follows:(3)
p
t
i
,
k
=
α
+
β
d
i
k
m
·
f
i
k
,where f
i
k denotes the information rate from the node i to the node k, d
i
k denotes the distance between the node i and node k, α, β are distance parameters of energy when receiving the data, and m is the path loss parameter.However, we adopted a kind of power control model [15], thereby embedding the residual energy into the proposed mechanism. The data transmitting power is defined as(4)
p
i
∗
=
n
i
G
i
i
β
∗
W
/
R
-
N
-
1
β
∗
E
i
E
T
,where n
i denotes the power of Gauss white noise, G
i
i denotes the channel gain information of the receiver, β is a unique solution, R denotes the transmission rate, W denotes the bandwidth, N is the number of receiving terminals, E
T denotes the total energy, and E
i denotes the residual energy of the node. When the residual energy of a node is decreasing, the value of the ratio E
i
/
E
T is also decreasing, so that the node will transmit data using low power. In this way, we can achieve the purpose, which is using less transmitting power when the residual energy is decreasing. Therefore, as long as each node knows its residual energy and channel gain information, it can implement power control in a distributed way, thus reducing the rate of energy consumption.


## 3.3.2. The Realization of Intracluster Energy Balance

In each cluster, there are three kinds of nodes: cluster head node, redundant node, and ordinary node. In the proposed approach, the energy consumption of these three nodes is completely different, so how to realize energy balance among them becomes a key problem. The various tasks of the different kinds of nodes are described as follows.(i)
Cluster head node: it receives information from neighboring nodes, implements data fusion, and transmits data packets to the redundant node, which is treated as a relay node.
(ii)
Redundant node: most of the redundant nodes are in a sleeping state, unless one node is selected as the relay node. The relay node receives data packets from the cluster head and then transmits them to the next hop.
(iii)
Ordinary node: it senses information in the monitoring field and transmits the collected data packets to their own cluster head.Research has shown that the ways of energy consumption are different for these kinds of nodes, even for the same kind of nodes. If we want to realize the network balance from energy consumption, the situation will be very complex. However, although the ways of energy consumption are various, the degree of residual energy can always be determined. Moreover, the node can adaptively adjust its transmitting power according to the residual energy, just like what we describe here in Section3.3.1. Thus, we can achieve the purpose of energy balance.The redundant node that is selected as a relay node will consume relatively more energy due to transmitting more data packets. In the wake of the continual reduction of energy, the sending power of each relay node will be smaller, which prolongs the lifetime of the node to a certain extent. However, the decline of power can also affect service quality. In addition, once the relay node is dead, the relay tree will be destroyed, causing an unbalanced distribution of residual energy among the sensor nodes.In view of these problems, the residual energy of redundant nodes can be periodically quantified and made hierarchical. The redundant nodes report their energy grades to the cluster head, and then the cluster head selects a redundant node with the highest energy grade as the relay used to transmit the data packets. Further, under the control of the cluster head, redundant nodes are dynamically selected as relays. Namely, when the energy grade of the relay node reduces by one level, the cluster head will reselect another redundant node with the highest energy grade as a new relay node. In this way, we can provide an updating mechanism for the redundant nodes and achieve dynamic balance energy in the whole cluster.Therefore, in order to control the average energy in the cluster, the cluster head needs to maintain an energy table on the residual energy grades of the redundant nodes. The content of energy table is configured as shown in Table1.Table 1
Node ID ofredundant node
Node’s state
Residual energy grade (1–5)
2
Agent transmission
5
5
Dormancy
4
8
Dormancy
4
⋯
⋯
⋯From the table, we can see that each node in the cluster is assigned its own ID in advance. The node ID is the communication address of the redundant node, which is convenient for the cluster head to use to master the identification information for each redundant node in the cluster. A node’s state refers to the two states of redundant nodes, that is, dormancy and agent transmission. Since number 2 node has the highest energy grade, it will be selected as a relay node. After the cluster head selects the redundant node with the highest energy as a transmission relay, other redundant nodes in the same cluster go into a sleeping state to conserve energy for the next round and its selection of a relay node. The residual energy is quantified into five grades. If the value of an energy grade declines by one level, the cluster head will reselect a new redundant node with the highest energy grade to replace the previous relay node.Further, in order to prevent the data loss of the main energy table resulting from the system failure, each cluster head will send a standby energy table to the nearest member node periodically. If the data of the main table is lost, the cluster head will send a standby table request to the member node. Once the member node receives that request, it will send the latest standby energy table to the cluster head. In this way, we can guarantee that the cluster head will in a timely fashion continue to select the redundant node with the highest energy grade as the relay node to use to complete the transmission.The realization of intracluster energy balance is shown in Algorithm2.Algorithm 2
(1) In a cluster, head sends ASK_msg to its nodes
(2) If node.state = redundancy
(3)Send Energy_msgresidual energy grade, ID, node → head
(4)If E
res ≥ max_E and node.status = dormancy
(5)Node.status = relay
(6)End if
(7) End if
(8) Relay node transmits data, it’s transmitting power was controlled.
(9) Detect periodically, whenE
res changes, reselect the relay node, turn to step (1)


## 3.4. An Intercluster Energy-Balanced Mechanism

In the previous section, the cluster head dynamically selects the redundant node as the relay to achieve intracluster energy balance. However, it cannot realize the intercluster energy balance. The cluster head close to the sink node will accelerate its rate of energy consumption due to always forwarding the data packets of remote relays. If the energy of a cluster head has been depleted, the entire network clustering again will consume a lot of unnecessary energy. Therefore, the proposed energy-balanced mechanism will divide the network into several layers based on the distances between the cluster heads and the sink node. The sink node will master a table on energy consumption of all the cluster heads. When the energy of a cluster head is too low in a certain layer, the sink node will decide to recluster in the corresponding layer, thereby bringing no influence to other layers. The simulation can prove that this mechanism can realize the intercluster energy balance.


### 3.4.1. Hierarchical Routing Process of the Entire Network

(1
) Measure the Relative Distances between Cluster Heads and the Sink Node. After the selection of a cluster head, the sink node will send a broadcasted message to all the cluster heads. When the cluster head receives the broadcast signal, it will calculate the relatively approximate distance to the sink node based on the received signal strength. Then, it will send its ID number and the value of the approximate distance to the sink node. Therefore, the sink node can master a control table of distances to all the cluster heads and estimate the distribution of the clusters.(2
) Layer the Network. According to the control table, the entire network is divided into several layers by the sink node. The nearest clusters are divided in the first layer. Similarly, the distant clusters are divided in the second layer and so on. To alleviate the neighboring hot spot effects of the sink node, the node number of the first layer should be more than other layers, while the last layer has the fewest nodes. After layering, the sink node will broadcast a data table about the layer result to the entire network. It will consist of the ID numbers of all the cluster heads and the corresponding layers. Because each member node knows the ID number of its cluster head, it can check the data table and know which layer it belongs to. The number of layers is defined as follows:(5)
k
=
α
L
r
,where L is the largest coverage radius of the entire network, r is the coverage radius of each sensor node, and α is a parameter of the monitoring field.(3
) The Process of Routing. After layering, each layer contains one or more cluster heads. Then, the cluster head will find the nearest cluster head nodes from the upper and lower layers. The cluster heads from different layers communicate with each other, so the routing is formed. However, to reduce energy consumption, cluster heads only complete data fusion and transmit the data packet to the relay node in the same cluster. Then, the relay node sends them to the next hop, namely, the cluster head of the upper layer. That is to say, the data packets are transferred from the relay node for the lower layer to the cluster head for the upper layer.The hierarchical routing process is shown in Algorithm3.Algorithm 3
(1)Sink, broadcast, Sink_msg(ID)
(2)Head i, send, Res_msgID, d
i
s
t
a
n
c
e
→sink, i
=
1,2
,
3
,
…
,
n,  n is the total number of nodes.
(3)Sink node divides the network into k layers
(4)Sink, broadcast, Lay_msgID, j, j
=
1,2
,
3
,
…
,
k
(5)Node i.level = j
(6)Head i broadcasts Route_msg(ID, Node.level)
(7)If node j.level ≠ 1
(8) If node j.state = head and node i.level = node j.level − 1
(9)  Node i receives Route_msg from cluster head j
(10)  Node j.next_hop = Node i
(11)   End if
(12) else if nodej.level = 1
(13) Nodej.next_hop = sink;
(14) End if
(15) Cluster_head tell redundant node the next_hop


### 3.4.2. The Realization of Intercluster Energy Balance

The cluster head can control the energy balance of the intracluster nodes. At the same time, it can monitor its residual energy, sending its ID number and the value of energy to the sink node through the data packet. Then, the sink node can master whether the energy is balanced or not balanced among all the clusters. When the sink node receives the value of all the cluster heads, it can calculate a ratio as follows:(6)
e
i
=
E
i
E
,
E
=
1
n
∑
i
=
1
n
E
i
,where E
i denotes the residual energy of the current cluster head and E denotes the average value of the residual energy of all the cluster heads. If the value of e
i is less than 1 that means that the energy consumption of the cluster head is unbalanced and needs a cluster again. However, the sink node only sends a message to the layer to which the current cluster head with the lowest energy belongs, thus indicating that all the nodes in the same layer need to dismiss their former clusters and cluster again. The layering mechanism of the network was introduced in the last section.Therefore, to control the average energy among all the clusters, the sink node needs to maintain an energy table for the residual energy of the cluster heads. Just like the energy table of the cluster head, the sink node will also send a standby energy table to the nearest node periodically.The content of energy table is configured as shown in Table2.Table 2
ID of cluster head
The layer clusterhead belongs to
The residualenergy E
i
e
i
12
1
0.1
0.33
25
2
0.3
1
32
2
0.5
1.67
⋯
⋯
⋯
⋯Among all the clusters, each cluster head has also its own ID number in advance. If only one layer’s cluster energy consumption is unbalanced and the cluster head consumes energy quickly (such as the emergency center), the sink node will reselect the cluster heads in only one layer and cluster again under certain conditions. In this way, we can avoid the result where the entire network clusters again and realize the energy balance of the entire network. The value of residual energy is a standard to measure whether the cluster head can continue to work or cannot. When the energy of the whole network reduces to a very small value, the network will enter the stage of establishing again, deploying new nodes, layering, implementing cluster reconstruction, and so on. Namely, it does that by repeating the above steps.The realization of intercluster energy balance is shown in Algorithm4.Algorithm 4
(1) Sink, receive head_residual energy
(2) Sink calculate average energy:E and ratio e
i
(3) If ratioe
i, less than 1, belong to layer j
(4)   Recluster in the certain layerj
(5)   Rerouting
(6) End if


## 3.4.1. Hierarchical Routing Process of the Entire Network

(1
) Measure the Relative Distances between Cluster Heads and the Sink Node. After the selection of a cluster head, the sink node will send a broadcasted message to all the cluster heads. When the cluster head receives the broadcast signal, it will calculate the relatively approximate distance to the sink node based on the received signal strength. Then, it will send its ID number and the value of the approximate distance to the sink node. Therefore, the sink node can master a control table of distances to all the cluster heads and estimate the distribution of the clusters.(2
) Layer the Network. According to the control table, the entire network is divided into several layers by the sink node. The nearest clusters are divided in the first layer. Similarly, the distant clusters are divided in the second layer and so on. To alleviate the neighboring hot spot effects of the sink node, the node number of the first layer should be more than other layers, while the last layer has the fewest nodes. After layering, the sink node will broadcast a data table about the layer result to the entire network. It will consist of the ID numbers of all the cluster heads and the corresponding layers. Because each member node knows the ID number of its cluster head, it can check the data table and know which layer it belongs to. The number of layers is defined as follows:(5)
k
=
α
L
r
,where L is the largest coverage radius of the entire network, r is the coverage radius of each sensor node, and α is a parameter of the monitoring field.(3
) The Process of Routing. After layering, each layer contains one or more cluster heads. Then, the cluster head will find the nearest cluster head nodes from the upper and lower layers. The cluster heads from different layers communicate with each other, so the routing is formed. However, to reduce energy consumption, cluster heads only complete data fusion and transmit the data packet to the relay node in the same cluster. Then, the relay node sends them to the next hop, namely, the cluster head of the upper layer. That is to say, the data packets are transferred from the relay node for the lower layer to the cluster head for the upper layer.The hierarchical routing process is shown in Algorithm3.Algorithm 3
(1)Sink, broadcast, Sink_msg(ID)
(2)Head i, send, Res_msgID, d
i
s
t
a
n
c
e
→sink, i
=
1,2
,
3
,
…
,
n,  n is the total number of nodes.
(3)Sink node divides the network into k layers
(4)Sink, broadcast, Lay_msgID, j, j
=
1,2
,
3
,
…
,
k
(5)Node i.level = j
(6)Head i broadcasts Route_msg(ID, Node.level)
(7)If node j.level ≠ 1
(8) If node j.state = head and node i.level = node j.level − 1
(9)  Node i receives Route_msg from cluster head j
(10)  Node j.next_hop = Node i
(11)   End if
(12) else if nodej.level = 1
(13) Nodej.next_hop = sink;
(14) End if
(15) Cluster_head tell redundant node the next_hop


## 3.4.2. The Realization of Intercluster Energy Balance

The cluster head can control the energy balance of the intracluster nodes. At the same time, it can monitor its residual energy, sending its ID number and the value of energy to the sink node through the data packet. Then, the sink node can master whether the energy is balanced or not balanced among all the clusters. When the sink node receives the value of all the cluster heads, it can calculate a ratio as follows:(6)
e
i
=
E
i
E
,
E
=
1
n
∑
i
=
1
n
E
i
,where E
i denotes the residual energy of the current cluster head and E denotes the average value of the residual energy of all the cluster heads. If the value of e
i is less than 1 that means that the energy consumption of the cluster head is unbalanced and needs a cluster again. However, the sink node only sends a message to the layer to which the current cluster head with the lowest energy belongs, thus indicating that all the nodes in the same layer need to dismiss their former clusters and cluster again. The layering mechanism of the network was introduced in the last section.Therefore, to control the average energy among all the clusters, the sink node needs to maintain an energy table for the residual energy of the cluster heads. Just like the energy table of the cluster head, the sink node will also send a standby energy table to the nearest node periodically.The content of energy table is configured as shown in Table2.Table 2
ID of cluster head
The layer clusterhead belongs to
The residualenergy E
i
e
i
12
1
0.1
0.33
25
2
0.3
1
32
2
0.5
1.67
⋯
⋯
⋯
⋯Among all the clusters, each cluster head has also its own ID number in advance. If only one layer’s cluster energy consumption is unbalanced and the cluster head consumes energy quickly (such as the emergency center), the sink node will reselect the cluster heads in only one layer and cluster again under certain conditions. In this way, we can avoid the result where the entire network clusters again and realize the energy balance of the entire network. The value of residual energy is a standard to measure whether the cluster head can continue to work or cannot. When the energy of the whole network reduces to a very small value, the network will enter the stage of establishing again, deploying new nodes, layering, implementing cluster reconstruction, and so on. Namely, it does that by repeating the above steps.The realization of intercluster energy balance is shown in Algorithm4.Algorithm 4
(1) Sink, receive head_residual energy
(2) Sink calculate average energy:E and ratio e
i
(3) If ratioe
i, less than 1, belong to layer j
(4)   Recluster in the certain layerj
(5)   Rerouting
(6) End if


## 4. Simulation Results

In this section, to evaluate and analyze the performance of the proposed mechanism EBM-HR, we compare its performance with the other routing algorithms, LEACH and HEED, using the simulation tool—MATLAB.For the two routing algorithms, LEACH is a low power, adaptive, clustering hierarchical routing protocol. It randomly selects the cluster heads and utilizes data fusion technology, which can effectively reduce energy consumption and prolong the life of the network; HEED is a hybrid energy-efficient distributed clustering algorithm, aimed at the uneven distribution of cluster heads. In the selection process for the cluster head, the residual energy of each node and the intracluster communication cost are the parameters of that clustering, so the cluster heads selected by HEED are more suitable to address the data transmission tasks and prolong the life of the entire network.


### 4.1. Simulation Environment

In our set-up, we assumed that the initial network contains 100 sensor nodes randomly generated. The software can distribute the node ID numbers to all these nodes according to the generated sequence. The network coverage area is a square region of 200 m × 200 m, while the coordinates of the sink node are (100, 250). The parameters of the wireless communication model and the required values of multihop routing are shown in Table3.Table 3
Parameters of the simulation.
Parameters
Values of the parameters
Coverage area
200 m × 200 m
The coordinate of sink node
(100, 250)
The initial energy of each node
0.5 J
R (the transmission rate)
0.01 kbps
W (the bandwidth)
100 Hz
n
i (the power of Gauss white noise)
5
×
10
-
15
β
∗
12.4


### 4.2. Network Topology Structure

When all the sensor nodes are deployed, the entire network starts to select the cluster heads and carry out clustering and layering. Then, the nodes begin to periodically collect data and transmit them to the sink node. With the change of time, the network topology structure is also changing. We extract four different periods from the network working process to observe the changes in the network topology structure. Figure1 describes the different network topology structures for the different time periods. The round circle, star, and round dot, respectively, represent the nodes’ belonging to different layers; the red dot represents the dead node. The blue connection line denotes the path of a single hop from member nodes to the cluster head. The green connection line denotes the routing path taken among the clusters by the relay nodes. The red connection line denotes the direct communication link with the sink node.Figure 1
Different network topology structures of different time.Then, we compare the proposed mechanism EBM-HR with the LEACH algorithm and the HEED algorithm. According to the earlier introduction, we assign the nodes identical power parameters, namely, initial power and initial energy in the same environment. Then, we obtain simulation results from three aspects: the lifetime of the entire network, the amount of transmitted data, and the energy consumption of all the nodes.


### 4.3. Lifetime of the Entire Network

We compare the network lifetime under various algorithms by counting the number of dead nodes. Figure2 summarizes the performance of the three algorithms and shows the number of dead nodes at different times. As we can see, in the wake of the processing time for the system network, the number of dead nodes is increasing. Obviously, at the same time unit, the number of dead nodes in our proposed EBM-HR is less than the LEACH algorithm and the HEED algorithm. In particular, because of the uneven distribution of cluster heads, the LEACH algorithm induces high energy consumption, resulting in the reduction of network lifetime. In addition, to analyze the trend of broken lines, the slope can approximately reflect the situation of energy consumption for all the nodes. The smaller slope shows that more nodes die at the same time, which means that the energy consumption for all the nodes is more balanced. As expected, the mechanism of EBM-HR performs well in prolonging the life and balancing the energy of the entire network.Figure 2
The total number of the dead nodes.


### 4.4. The Amount of Data Transmission

In this simulation, we compared the performance of data transmission quality of the three algorithms. The amount of data transmission in different time periods is shown in Figure3. From the figure, we can see that, in the wake of the processing time of system network, the amount of total data collected by the sink node increases. Obviously, for the same time period, the amount of data transmission in our proposed approach of EBM-HR is much more than that for the other two algorithms. The EBM-HR utilizes the redundant nodes instead of the cluster heads as relay nodes, reducing the burden of cluster heads. Moreover, dividing the network into different layers builds a hierarchical routing tree to reduce the loss of data packets. Therefore, we can conclude that using EBM-HR can gather much more data and thus obtain more accurate information.Figure 3
The amount of data transmission.


### 4.5. The Energy Consumption of All the Nodes

In Section4.3, we analyze whether the network energy is balanced based on the slope of the broken line. In this simulation, we detect the residual energy of each node at any moment and calculate the average energy of all the nodes. Figure 4 shows the average residual energy of all the nodes for different time units. Then, we use the variance formula to calculate the variance of residual energy of all the nodes to determine which algorithm is better at achieving energy balance for the entire network. Figure 5, respectively, represents the variances of all the nodes for the three algorithms. Obviously, the variances of the proposed mechanism of EBM-HR are much smaller than those of the LEACH and HEED algorithms. It vividly indicates that EBM-HR can reduce energy consumption and achieve energy balance of the entire network. Therefore, we can conclude that EBM-HR outperforms the other two algorithms in terms of effectively saving more energy while achieving an energy balance.Figure 4
The average residual energy of all the nodes.Figure 5
The variance of residual energy of all the nodes.


## 4.1. Simulation Environment

In our set-up, we assumed that the initial network contains 100 sensor nodes randomly generated. The software can distribute the node ID numbers to all these nodes according to the generated sequence. The network coverage area is a square region of 200 m × 200 m, while the coordinates of the sink node are (100, 250). The parameters of the wireless communication model and the required values of multihop routing are shown in Table3.Table 3
Parameters of the simulation.
Parameters
Values of the parameters
Coverage area
200 m × 200 m
The coordinate of sink node
(100, 250)
The initial energy of each node
0.5 J
R (the transmission rate)
0.01 kbps
W (the bandwidth)
100 Hz
n
i (the power of Gauss white noise)
5
×
10
-
15
β
∗
12.4


## 4.2. Network Topology Structure

When all the sensor nodes are deployed, the entire network starts to select the cluster heads and carry out clustering and layering. Then, the nodes begin to periodically collect data and transmit them to the sink node. With the change of time, the network topology structure is also changing. We extract four different periods from the network working process to observe the changes in the network topology structure. Figure1 describes the different network topology structures for the different time periods. The round circle, star, and round dot, respectively, represent the nodes’ belonging to different layers; the red dot represents the dead node. The blue connection line denotes the path of a single hop from member nodes to the cluster head. The green connection line denotes the routing path taken among the clusters by the relay nodes. The red connection line denotes the direct communication link with the sink node.Figure 1
Different network topology structures of different time.Then, we compare the proposed mechanism EBM-HR with the LEACH algorithm and the HEED algorithm. According to the earlier introduction, we assign the nodes identical power parameters, namely, initial power and initial energy in the same environment. Then, we obtain simulation results from three aspects: the lifetime of the entire network, the amount of transmitted data, and the energy consumption of all the nodes.


## 4.3. Lifetime of the Entire Network

We compare the network lifetime under various algorithms by counting the number of dead nodes. Figure2 summarizes the performance of the three algorithms and shows the number of dead nodes at different times. As we can see, in the wake of the processing time for the system network, the number of dead nodes is increasing. Obviously, at the same time unit, the number of dead nodes in our proposed EBM-HR is less than the LEACH algorithm and the HEED algorithm. In particular, because of the uneven distribution of cluster heads, the LEACH algorithm induces high energy consumption, resulting in the reduction of network lifetime. In addition, to analyze the trend of broken lines, the slope can approximately reflect the situation of energy consumption for all the nodes. The smaller slope shows that more nodes die at the same time, which means that the energy consumption for all the nodes is more balanced. As expected, the mechanism of EBM-HR performs well in prolonging the life and balancing the energy of the entire network.Figure 2
The total number of the dead nodes.


## 4.4. The Amount of Data Transmission

In this simulation, we compared the performance of data transmission quality of the three algorithms. The amount of data transmission in different time periods is shown in Figure3. From the figure, we can see that, in the wake of the processing time of system network, the amount of total data collected by the sink node increases. Obviously, for the same time period, the amount of data transmission in our proposed approach of EBM-HR is much more than that for the other two algorithms. The EBM-HR utilizes the redundant nodes instead of the cluster heads as relay nodes, reducing the burden of cluster heads. Moreover, dividing the network into different layers builds a hierarchical routing tree to reduce the loss of data packets. Therefore, we can conclude that using EBM-HR can gather much more data and thus obtain more accurate information.Figure 3
The amount of data transmission.


## 4.5. The Energy Consumption of All the Nodes

In Section4.3, we analyze whether the network energy is balanced based on the slope of the broken line. In this simulation, we detect the residual energy of each node at any moment and calculate the average energy of all the nodes. Figure 4 shows the average residual energy of all the nodes for different time units. Then, we use the variance formula to calculate the variance of residual energy of all the nodes to determine which algorithm is better at achieving energy balance for the entire network. Figure 5, respectively, represents the variances of all the nodes for the three algorithms. Obviously, the variances of the proposed mechanism of EBM-HR are much smaller than those of the LEACH and HEED algorithms. It vividly indicates that EBM-HR can reduce energy consumption and achieve energy balance of the entire network. Therefore, we can conclude that EBM-HR outperforms the other two algorithms in terms of effectively saving more energy while achieving an energy balance.Figure 4
The average residual energy of all the nodes.Figure 5
The variance of residual energy of all the nodes.


## 5. Conclusions

In this paper, we propose EBM-HR, an energy-balanced mechanism for hierarchical routing, for the wireless sensor networks. In the mechanism, the residual energy of the redundant nodes is quantified and hierarchical, so the cluster head can dynamically select redundant nodes as relay nodes to complete information transmission and realize an update of the redundant nodes. Moreover, the sink node can recluster in a certain layer based on the residual energy of the cluster heads. EBM-HR not only realizes the intracluster and the intercluster energy balance, but also effectively prolongs the lifetime of the entire network. We have compared the performance of EBM-HR to the LEACH algorithm and the HEED algorithm. Extensive experiments show that the proposed mechanism of EBM-HR achieves better performance than any other algorithm in terms of meeting data transmission quality, realizing the balance of energy consumption, and prolonging the lifetime of the entire network. Thus, it can significantly improve the performance of wireless sensor networks.However, the experiment was performed in a static network, so how to balance data transmission power when the mobile nodes actually exist in a network remains for further study. Moreover, we only used MATLAB as the simulation tool, so how to specifically apply this approach to real sensor nodes and compare those differences is also too difficult to do without further study. In addition, since wireless sensor networks are widely used in practice, the reliability and lifetime of these networks are becoming more and more important. Therefore, studying different network energy balance algorithms should be a major development direction for the future.



---

*Source: 123521-2015-10-20.xml*