Avoidance of energy hole problem based on feedback mechanism for heterogeneous sensor networks

Abstract

The application-based wireless sensor networks have the energy hole problem when considered for performance measures in balancing the energy load. To avoid the energy hole problem for heterogeneous sensor networks, a feedback mechanism–based unequal clustering algorithm is proposed. In the initial stage of the network, this article divides the network into several layers with different layer heights by only considering the distance from nodes to the sink. Then, this article introduces a feedback mechanism and dynamically changes the size of each cluster according to the feedback value calculated by the sink. After the size of each cluster varies for several rounds, the energy consumption between each cluster will tend to be balanced. To save the energy consumption cost of receiving the sink feedback signal, this article proposes the termination condition for the feedback process. When the termination condition is satisfied, the feedback process finishes and the network turns into the stable clustering stage. The simulation results show that compared with the existing algorithms of data transmission, feedback mechanism–based unequal clustering algorithm can make better use of node energy and prolong the network lifetime.

Introduction

In recent years, wireless sensor networks (WSNs) assembled with a large number of small energy device nodes has become a hot topic ¹ WSN has been widely used in environmental monitoring, wildlife protection, military detection, and many other fields. In multi-hop networks, some nodes generate data and also forward them, and the nodes close to the sink have larger energy consumption because they are burdened with heavier relay traffic. These nodes tend to die early when they exhaust their energy, leading to what is called energy hole.^2–4 Part of data can be delivered to the sink when the energy hole appears, and a lot of energy resource in the networks is wasted. The results of Song et al. ⁵ show that when the network lifetime is over, up to 90% of the total initial energy is left unused. Thus, avoiding or delaying the emergence of energy hole is an effective way to extend the lifetime of the networks.

In real applications, sensor nodes can be divided into different types according to the object, sensing capability, computing capability, and communication capability. The networks composed of different types of sensor nodes are called heterogeneous sensor networks, while the networks composed of one type of sensor nodes are called homogeneous sensor networks. Typically, various types of sensor nodes are deployed in the same area in order to monitor different types of objects (such as using various types of nodes in the same forest area to monitor different objects, such as meteorological data, disaster warning, and wildlife). In order to build more low-cost monitoring networks, various types of sensor nodes can share the same sink to constitute a heterogeneous sensor network.^6,7

Currently, many researchers have done enormous work to avoid energy hole in homogeneous sensor networks. However, the nodes in heterogeneous networks have different initial energy, communication capability, and data size. Therefore, in such a complex network condition, the energy hole avoiding strategy based on homogeneous networks cannot effectively balance the energy consumption of each node. Thus, the load of nodes in each part of the network is still unbalanced, and the nodes with high energy consumption will die early, so it is hard to avoid the emergence of energy hole.

To avoid energy hole in heterogeneous sensor networks, this article proposes a feedback mechanism–based unequal clustering (FMUC) algorithm. The main contributions of this article are listed as follows:

1. To the best of our knowledge, this is the first work to study the energy hole problem in heterogeneous sensor networks.

2. In the initial stage of the network, this article introduces an unequal clustering algorithm, only considering the distance from nodes to the sink.

3. To achieve energy consumption balance among clusters, this article proposes a feedback mechanism. Cluster sizes can be changed by the feedback value generated by the sink.

4. Considering the cost of the feedback process, this article proposes the termination condition for the feedback process.

The rest of the article is organized as follows: section “Related works” reviews related works. Section “Network model” describes the network model and energy consumption model. Section “Algorithm description” proposes the FMUC algorithm. Then, in section “Simulation,” this article evaluates FMUC with simulations. Finally, section “Conclusion” concludes the article.

Related works

Currently, the energy hole phenomenon is a bottleneck problem for WSN and many researchers have conducted a lot of research. Li and Mohapatra ⁸ first proposed a mathematical model for the analysis of energy hole in WSNs. To avoid the energy hole problem, researchers have proposed many effective methods which can fall into the following categories:

1. Unequal clustering algorithm. It is different from the traditional uniform clustering algorithms such as low-energy adaptive clustering hierarchy (LEACH). ⁹ Most of the unequal clustering algorithms can balance energy consumption and prolong network lifetime. Chanak et al. ¹⁰ proposed a new cluster-based load management scheme which can balance energy consumption of the deployed sensor nodes and reduce energy holes from the network by balancing the communication load as equally as possible. Energy-efficient unequal clustering (EEUC) ¹¹ is the first unequal cluster-based routing protocol to mitigate the energy hole problem. EEUC is a self-organized competition-based algorithm, where cluster heads (CHs) are selected based on local information. Different from EEUC, Jiang et al. ¹² introduced a time-based competitive clustering algorithm distributed energy-balanced unequal clustering routing protocol (DEBUC). DEBUC partitions all nodes into clusters of unequal size. The radius of each cluster depends on broadcast time and the distance to the sink. The broadcast time is determined by the residual energy of the candidate CH and neighbor nodes.

2. Nodes deployment strategy. Liu et al. ¹³ put forward a scheme of nonuniform node distribution on the basis of the proportion of nodes’ energy consumption in each ring and change nodes’ active/hibernating states under density control mechanism. Wu et al. ¹⁴ proposed a nonuniform node distribution strategy to achieve nearly balanced energy depletion and investigated q-switch routing algorithm. Liu et al. ¹⁵ studied how to build a heterogeneous network to balance the energy consumption by deploying higher energy nodes in the area closer to the sink and deploying lower energy nodes in the area farther away from the sink. However, this article only uses two types of nodes to avoid energy hole, but it does not propose a method to avoid the energy hole in heterogeneous sensor networks consisting of multiple types of nodes. Similar studies can also be found in Halder and Bit ¹⁶ and Xue et al. ¹⁷

3. Transmitting data by different transmission power levels. Song et al. ⁵ proposed an improved corona model with levels for analyzing sensors with adjustable transmission ranges in a WSN to avoid energy hole. Liu and He ¹⁸ combined these two strategies and proposed a novel deployment approach, ACO (ant colony optimization)-Greedy, to settle the problem of grid-based coverage with low cost and connectivity guarantee. Liu ¹⁹ proposed a transmission range adjustment strategy to avoid energy hole. In this strategy, energy consumption minimization and energy consumption balancing are jointly considered and fully reflected.

4. In addition, there are some other ways to reduce the impact of energy hole. Ammari ²⁰ proposed a three-tier architecture to balance energy consumption of the sensors closer to the sink. The architecture has immobile source sensors, immobile sinks, and mobile proxy sinks. Abo-Zahhad et al. ²¹ also use a controlled mobile sink to solve the energy hole problem. Kleerekoper and Filer ²² proposed a novel routing tree construction algorithm degree constrained routing, which can achieve better energy consumption balance and longer lifetime. Ren et al. ³ proposed an analytic model to estimate the entire network lifetime from network initialization until it is completely disabled and determined the boundary of energy hole in a data-gathering WSN.

Network model

Network model

In this article, we assume that n sensor nodes are randomly distributed in a $M\times N$ rectangle area. Table 1 summarizes the notations used in this article. This article assumes the network model as follows:

1. The only sink is located at the edge of the network;

2. All sensor nodes are randomly deployed in the network, and all nodes are stationary after deployment;

3. The initial energy of heterogeneous nodes is randomly distributed in $[{\epsilon }_{\mathrm{init}}^{\min },{\epsilon }_{\mathrm{init}}^{\max }]$ . The average initial energy of all nodes is $\overline{{\epsilon }_{\mathrm{init}}}$ . For any node i, the initial energy is ${\epsilon }_{\mathrm{init}}^i$ and the current energy is ${\epsilon }_i$ ;

4. Nodes are organized in the form of clusters, and heterogeneous nodes monitor different objects. So, each node in one round obtains monitored data of varying sizes and the monitored data sizes are between $[l_{\min },l_{\max }]$ bits;

5. After clusters finish data collection, multi-hop communication among CHs is adopted to send data to the sink.

Table 1.

Notations.

Symbol	Definitions
M	Network width
N	Network length
$L_i$	$i\mathrm{th}$ layer
$C_{i,j}$	$j\mathrm{th}$ cluster in the $i\mathrm{th}$ layer
$\parallel C_{i,j}\parallel$	Area of the cluster $C_{i,j}$
$r(C_{i,j})$	Radius of the cluster $C_{i,j}$
$\rho$	Node’s density in the network
$k_{i,j}$	Number of nodes in the $C_{i,j}$
$E[d_{\mathrm{toCH}}]$	Average distance expectancy from all nodes in $C_{i,j}$ to the cluster center
$\tau$	Node’s sensing distance
$E_{C_{i,j}}$	Total energy consumption of $C_{i,j}$ in one clustering round
${\epsilon }_{\mathrm{init}}^{C_{i,j}}$	Initial energy of cluster $C_{i,j}$
$E_{C_{i,j}}^{\mathrm{in}}$	Energy consumption for $C_{i,j}$ to complete data processing within the cluster in one clustering round
$E_{C_{i,j}}^{\mathrm{it}}$	Energy consumption for $C_{i,j}$ to complete data processing between clusters in one clustering round

Energy model

This article applies a simple energy consumption model ²³ to calculate energy consumption in communication. In the process of transmitting l-bit message across distance d, the energy consumption of the sender is

$$E_{\mathrm{Tx}}(l,d)=(\begin{array}{c}l{E}_{\mathrm{elec}}+l{\epsilon }_{\mathrm{fs}}{d}^2,d<d_0\hfill \\ \multicolumn{1}{c}{l{E}_{\mathrm{elec}}+l{\epsilon }_{\mathrm{mp}}{d}^4,d\ge d_0}\end{array}$$

(1)

Receiver’s energy consumption is

$$E_{\mathrm{Rx}}(l,d)=l{E}_{\mathrm{elec}}$$

(2)

where $E_{\mathrm{elec}}$ is transmitting circuit loss and ${\epsilon }_{\mathrm{fs}}{d}^2$ and ${\epsilon }_{\mathrm{mp}}{d}^4$ are, respectively, the energy required by power amplifier to send 1-bit data.

Algorithm description

The unequal cluster in the initial stage of the network

For the heterogeneity and randomness of deployment of sensor nodes, none of the nodes knows the location, energy, and message sizes of the other nodes nearby. Thus, it is hard to achieve the actual energy consumption balance in the first round.

To organize the network into cluster, in this section, this article temporarily ignores the distribution of heterogeneous nodes in the network and only considers the distance between nodes and the sink in the initial stage of the network.

This article divides the network into k layers and assumes the cluster $C_{i,j}$ belongs to $L_i$ . We calculate the energy consumption of each cluster. Consequently, we get the size of each cluster according to the ratio of the energy consumption of each layer.

The network structure in the first clustering round is shown in Figure 1. The network is divided into k layers and we denote by $L_i$ the $i\mathrm{th}$ layer. In each layer $L_i$ , there are several clusters. For each cluster $C_{i,j}$ belonging to $L_i$ , we denote by $r(C_{i,j})$ the cluster radius. The total energy consumption of cluster $C_{i,j}$ in one clustering round is the sum of $E_{C_{i,j}}^{\mathrm{in}}$ and $E_{C_{i,j}}^{\mathrm{it}}$ .

Figure 1.

Network structure model in the first clustering round.

Theorem 1. The energy consumption $E_{C_{i,j}}^{\mathrm{in}}$ for cluster $C_{i,j}$ to complete inner-cluster data processing in one clustering round is $\pi (r(C_{i,j}){)}^2\rho l(2E_{\mathrm{elec}}+4/9·{\epsilon }_{\mathrm{fs}}(r(C_{i,j}){)}^2)$ .

Proof. The energy consumption for cluster $C_{i,j}$ to complete inner-cluster data processing includes two parts. The first is the energy consumption $E_i^{\mathrm{node}}$ for nodes in the cluster to send collected data to CH. The second is the energy consumption $E_i^{\mathrm{re}}$ for CH to receive these data. Thus, we have

$$E_{C_{i,j}}^{\mathrm{in}}=E_{C_i}^{\mathrm{node}}+E_{C_i}^{\mathrm{re}}$$

(3)

We denote $E[d_{\mathrm{toCH}}]$ by the average distance expectancy from all nodes within the cluster to cluster center. According to Peng et al., ²⁴ $E[d_{\mathrm{toCH}}]$ can be calculated as follows

$$E[d_{\mathrm{toCH}}]=\underset{0}{\overset{r(C_{i,j})}{\int }}x\frac{2x}{r{(C_{i,j})}^2}\mathrm{dx}=\frac{2}{3}r(C_{i,j}))$$

(4)

Ignore node heterogeneity and assume every node sends l-bit data to CH in one clustering round. The energy consumption for nodes to send collected data to CH in one round is

$$\begin{array}{c}{E}_{C_i}^{\mathrm{node}}=\parallel C_{i,j}\parallel \rho (l{E}_{\mathrm{elec}}+l{\epsilon }_{\mathrm{fs}}E{[d_{\mathrm{toCH}}]}^2)\hfill \\ \multicolumn{1}{c}{=\pi r{(C_{i,j})}^2\rho (l{E}_{\mathrm{elec}}+\frac{4}{9}l{\epsilon }_{\mathrm{fs}}r{(C_{i,j})}^2)}\end{array}$$

(5)

The energy consumption for CH to receive data sent by nodes in $C_{i,j}$ is

$$E_{C_i}^{\mathrm{re}}=\parallel C_{i,j}\parallel \rho l{E}_{\mathrm{elec}}=\pi r(C_{i,j}{)}^2\rho l{E}_{\mathrm{elec}}$$

(6)

Thus, we can obtain the energy consumption for all nodes in cluster $C_{i,j}$ to complete inner-cluster data processing in one clustering round

$$E_{C_i}^{\mathrm{in}}=\pi (r(C_{i,j}){)}^2\rho l(2E_{\mathrm{elec}}+\frac{4}{9}·{\epsilon }_{\mathrm{fs}}{(r(C_{i,j}))}^2)$$

(7)

Theorem 2. The energy consumption $E_{C_{i,j}}^{\mathrm{it}}$ for all nodes in cluster $C_{i,j}$ to complete inter-cluster data processing in one clustering round is given in equation (12).

Proof. For each layer $L_i(i<k)$ , the total amount of data produced by the outer layers is $\sum _{n=i+1}^{k}2r(C_{n,j})N\rho l$ ; therefore, the amount of data $l_{i,j}^{\mathrm{rec}}$ received by the cluster $C_{i,j}$ is

$$l_{C_{i,j}}^{\mathrm{rec}}=\{\begin{array}{c}\begin{array}{c}\left(\frac{2r(C_{i,j})}{M}\right)\sum _{n=i+1}^{k}2r(C_{n,j})N\rho l,i<k\hfill \\ \multicolumn{1}{c}{0,i=k}\end{array}\hfill \end{array}$$

(8)

Thus, the energy consumption of cluster $C_{i,j}$ to receive data sent from the outer layers is

$$\begin{array}{c}{E}_{C_{i,j}}^{\mathrm{rec}}=l_{C_{i,j}}^{\mathrm{rec}}{E}_{\mathrm{elec}}\hfill \\ \multicolumn{1}{c}{=\{\begin{array}{c}\begin{array}{c}\left(\frac{2r(C_{i,j})}{M}\right)\sum _{n=i+1}^{k}2r(C_{n,j})N\rho l{E}_{\mathrm{elec}},i<k\hfill \\ \multicolumn{1}{c}{0,i=k}\end{array}\hfill \end{array}}\end{array}$$

(9)

Including the data collected by nodes within the cluster, the total amount of data the cluster $C_{i,j}$ need to send to the inner layer is

$$\begin{array}{c}{l}_{C_{i,j}}^{\mathrm{send}}=\parallel C_{i,j}\parallel \rho l+l_{C_{i,j}}^{\mathrm{rec}}\hfill \\ =\{\begin{array}{c}\pi {(r(C_{i,j}))}^2\rho l+2r{C}_{n,j}N\rho l,i<k\hfill \\ \multicolumn{1}{c}{\pi {(r(C_{i,j}))}^2\rho l,i=k}\end{array}\hfill \end{array}$$

(10)

Therefore, the energy consumption for cluster $C_{i,j}$ to send data to the CH of the inner layer is

$$\begin{array}{c}{E}_{C_i}^{\mathrm{send}}=\{\begin{array}{c}\begin{array}{c}{l}_{C_{i,j}}^{\mathrm{send}}{E}_{\mathrm{elce}}+l_{C_{i,j}}^{\mathrm{send}}{\epsilon }_{\mathrm{fs}}(r(C_{i,j}){)}^2,i=1\hfill \\ \multicolumn{1}{c}{l_{C_{i,j}}^{\mathrm{send}}{E}_{\mathrm{elce}}+l_{C_{i,j}}^{\mathrm{send}}{\epsilon }_{\mathrm{fs}}(r(C_{i,j})+r(C_{i-1,j}){)}^2,i<i\le k}\end{array}\hfill \end{array}\hfill \end{array}$$

(11)

According to equations (9) and (11), we can obtain the energy consumption for cluster $C_{i,j}$ to complete inter-cluster data processing in one clustering round

$$E_{C_{i,j}}^{\mathrm{it}}=E_{C_{i,j}}^{\mathrm{send}}+E_{C_{i,j}}^{\mathrm{rec}}$$

(12)

There are $M/2r(C_{i,j})$ clusters in layer $L_i$ . Thus, the total energy consumption of $L_i$ is

$$E_{L_i}=\left(\frac{M}{2r(C_{i,j})}\right)(E_{C_{i,j}}^{\mathrm{in}}+E_{C_{i,j}}^{\mathrm{it}})$$

(13)

For $L_i$ , the total initial energy is ${\epsilon }_{\mathrm{init}}^{L_i}=2r_{i}M\rho \overline{{\epsilon }_{\mathrm{init}}}$ , where $\overline{{\epsilon }_{\mathrm{init}}}$ is the average initial energy of all the nodes. Temporarily ignore node heterogeneity; to avoid energy hole, the ratio of the energy consumption of each layer and the total initial energy of each layer should be equal. Therefore, in the first clustering round, the following should be satisfied

$$\{\begin{array}{c}\frac{E_{L_1}}{{\epsilon }_{\mathrm{init}}^{L_1}}=\frac{E_{L_2}}{{\epsilon }_{\mathrm{init}}^{L_2}}=\cdots =\frac{E_{L_k}}{{\epsilon }_{\mathrm{init}}^{L_k}}\hfill \\ \multicolumn{1}{c}{r(C_{1,j})+r(C_{2,j})+\cdots +r(C_{k,j})=\frac{M}{2}}\end{array}$$

(14)

Cluster selection and routing

In the initial stage of the network, all the nodes in the network use a certain signal strength to broadcast within node communication range. The sink also uses another signal strength to broadcast to the entire network. Thus, nodes can perceive their mutual distance and the distance to the sink according to attenuation of signal strength in the process of transmission. Doshi et al. ²³ give the calculation results of the mutual distance between the nodes through the relationship between the signal transmission strength and the signal reception strength

$$d_{i,j}=\sqrt[\alpha ]{\frac{{\mathrm{KE}}_i^{\mathrm{tran}}}{E_{j,i}^{\mathrm{rec}}}}$$

(15)

where $d_{i,j}$ is the distance between node i and node j, $E_i^{\mathrm{tran}}$ is the signal transmission strength of node i, $E_{j,i}^{\mathrm{rec}}$ is the strength of the received signals (reception energy) of node j, and K is a constant.

All nodes in the network can determine the layer to which they belong after obtaining the distance from the sink. Furthermore, each node broadcasts CH competition message containing the information of its current residual energy in the optimal cluster radius of its layer. If a node finds its current residual energy is greater than the residual energy broadcast from the other nodes, this node broadcasts the message to be the CH.

To balance the energy load, all nodes take turn to become the CH. After receiving the data from nodes in the cluster in each round, CH will add the head information including cluster ID, cluster radius, total residual energy of nodes in the cluster, and the distance from the CH to the sink. Then, CH transmits the data packet to the next-hop CH in the next layer. After the next-hop CH receives the data packet, it will add the information of the distance of two CHs (i.e. the data transmission distance) into the data packet and continues to transmit. When the sink receives the data packet transmitted from clusters of $L_1$ , it also adds the information of the distance from these head nodes to the sink.

Generating the feedback value

Since the distribution of heterogeneous nodes is temporarily ignored in the unequal clustering of the network initial stage, clusters in the same layer cannot achieve the balance of energy consumption. Thus, the sink should calculate the energy consumption rate of each cluster in every cluster round.

Definition 1. Energy consumption rate. For each cluster $C_{i,j}$ , the energy consumption rate $R_{i,j}$ is the ratio of $E_{C_{i,j}}$ and ${\epsilon }_{\mathrm{init}}^{C_{i,j}}$ . It indicates the energy load of the cluster in one clustering round.

Since the ID of each cluster is added to the data packet sent to the sink, the sink can calculate the amount of data sent from $C_{i,j}$ . The transmission distance of each cluster is added to the data packet too. Thus, after the sink receives all data packets, the energy consumption of each cluster in one clustering round can be calculated by Theorems 1 and 2.

Assume the average energy consumption rate of all clusters in this clustering round is $\overline{V}$ . For cluster $C_{i,j}$ , if $V_{i,j}>\overline{V}$ , it indicates the energy load of $C_{i,j}$ is greater than the average energy load. Thus, the cluster radius of $C_{i,j}$ should be reduced to decrease the energy load. If $V_{i,j}<\overline{V}$ , the cluster radius should be expanded to increase the energy load of cluster $C_{i,j}$ .

According to Theorems 1 and 2, the energy consumption of each cluster is related to the amount of transmission and forwarding data. The amount of transmission and forwarding data of each cluster is directly related to the area of the cluster. Then, the feedback value $r_{i,j}$ is as follows

$$r_{i,j}=\sqrt{1+\ln \sqrt{\frac{\overline{V}}{V_{i,j}}}}$$

(16)

After the sink obtains the feedback value of each cluster, it broadcasts the feedback value to all nodes in the network. When the nodes in $C_{i,j}$ receive the feedback value $r_{i,j}$ , they change their radius of the CH competition according to $r_{i,j}$ and re-clustering. The new CH competition radius is

$$r(C_{i,j})=r(C_{i,j})·r_{i,j}$$

(17)

To control the data transmission of nodes in the cluster, this article defines the maximum CH competition radius as 90 m. ¹¹

The termination condition for the feedback process

In heterogeneous networks, the sink is informed of neither the distribution of each heterogeneous node nor the amount of message produced by each node in a clustering round. Thus, after the cluster size is changed by the feedback value, the energy load imbalance of each cluster cannot be solved at a time.

As is shown in Figure 2, for cluster $C_{i,j}$ , more heterogeneous nodes located at the center of the cluster are nodes producing more data, and the current residual energy of nodes in $C_{i,j}$ is small. So, the energy consumption rate of $C_{i,j}$ is higher than the average value of clusters in the network. After the feedback, the cluster radius of $C_{i,j}$ will be reduced. However, nodes located at the edge of the cluster produce less data. Thus, although the size of $C_{i,j}$ is reduced, $C_{i,j}$ is also producing a large amount of data and the energy consumption rate is higher than other clusters.

Figure 2.

Cluster model.

Conversely, if nodes generating more data located at the edge of the cluster, after the cluster radius of $C_{i,j}$ is reduced, the energy consumption rate of cluster $C_{i,j}$ also will be lower than the average value. To solve this problem, after a new round, the sink will calculate the energy consumption rate of each cluster to generate a new feedback value, continue to change the size of each cluster, and balance the energy consumption.

When the feedback process continues, the difference in energy consumption rate between clusters will tend to reduce. We denote $l_b$ by the feedback message length broadcast by the sink. Thus, the energy consumption for each node to receive the feedback signal from the sink in one clustering round is $l_b{E}_{\mathrm{elec}}$ . If the feedback process continues under the condition that the difference of energy consumption rate in each cluster is small and it is hard to reduce, the energy of each node would be wasted by receiving the feedback signal. Therefore, to effectively use the limited energy resources in the network and prolong the network lifetime, this article should propose the termination condition.

The sink calculates the standard deviation of the energy consumption rate among clusters after it receives data from each cluster. For the $m\mathrm{th}$ round, there are N clusters in the network, and the standard deviation of the energy consumption rate among clusters is

$${\sigma }_m=\sqrt{\frac{\sum _{i=1}^k\sum _{j=1}^n{(V_{i,j}-\overline{V_m})}^2}{N}}$$

(18)

For the $m\mathrm{th}$ round, after sink calculates the standard deviation ${\sigma }_m$ , the sink will compare ${\sigma }_m$ , ${\sigma }_{m-1}$ , and ${\sigma }_{m-2}$ . If ${\sigma }_m<{\sigma }_{m-1}$ or ${\sigma }_m<{\sigma }_{m-2}$ , it indicates that the feedback process can effectively balance the energy consumption of each cluster. While ${\sigma }_m>{\sigma }_{m-1}$ and ${\sigma }_m>{\sigma }_{m-2}$ , it shows that the feedback process in ( $m-1$ )th round cannot balance the energy consumption of each cluster. If the feedback process continues, it is hard to further balance the energy consumption of every cluster and nodes’ energy will be wasted in receiving broadcast from the sink. So, the feedback process finishes, and the nodes in the network cluster according to the CH competition radius of the ( $m-1$ )th round. Then, the network turns into a stable clustering stage.

Figure 3 shows the network structure when the feedback process stops and the network turns into the stable clustering stage. It can be seen that the size of each cluster is no longer equal.

Figure 3.

Network structure model in the stable clustering stage.

Simulation

To evaluate the performance of the algorithm proposed in this article, we have made a simulation experiment on it with the help of MATLAB simulation software. We first give each layer’s optimal height under the default network environment; second, we will compare the algorithm performance between LEACH, EEUC, DEBUC, FMUC-wf (FMUC without feedback mechanism), and FMUC under the default network environment. The reason for selecting these algorithms is LEACH is a classical clustering algorithm and EEUC and DEBUC are typical unequal clustering algorithms. Furthermore, we will compare the performance of each algorithm under different parameters of the network.

In the simulation, the default size of the network is a rectangular area with $250\mathrm{m}\times 150\mathrm{m}$ , the only sink is located at the edge of the network, and the position is (250, 75). We assume that 400 sensors are randomly uniformly deployed in the network. By default, 50% nodes are heterogeneous and 50% nodes are homogeneous. The initial energy of heterogeneous nodes is a random value between 0.2 and 0.8 J, and the message size is a random value between 100 and 1900 bits. For homogeneous nodes, the initial energy is 0.5 J and the message size is 1000 bits. The parameters of the simulation are shown in Table 2. Figure 4 shows the distribution of the heterogeneous nodes in the simulation.

Table 2.

Simulation parameters.

Parameter	Default value
$W(m)$	150
$L(m)$	250
$L_i$	The $i\mathrm{th}$ layer
N	400
sink position	(250, 75)
Threshold distance $d_0(m)$	87
Initial energy of sensor (J)	0.2–0.8
Data message size (bit)	100–1900
$E_{\mathrm{elec}}$	50 nJ/bit
${\epsilon }_{\mathrm{fs}}$	10 pJ/bit/ ${\mathrm{m}}^2$
${\epsilon }_{\mathrm{mp}}$	0.0013 pJ/bit/ ${\mathrm{m}}^4$

Figure 4.

Distribution of the heterogeneous nodes in simulation.

Performance of the feedback mechanism

Table 3 shows the height of each layer obtained by equation (14) after the first round under the default network environment. From Table 3, the network is divided into four layers. The layer closer to the sink has smaller layer height, and the layer farther to the sink has larger layer height.

Table 3.

Layer height.

	$L_1$	$L_2$	$L_3$	$L_4$
Layer height (m)	32	47	73	98

Figure 5 shows the energy consumption of all clusters in the first round. It can be seen, for the type and the location of nodes is unknown and the distribution of heterogeneous nodes is temporarily ignored in the first round, there is a big difference in energy consumption between the clusters of each layer. Especially in $L_3$ , the energy consumption difference among the three clusters is great.

Figure 5.

Energy consumption of all clusters in the first round.

Figure 6 shows the standard deviation of the energy consumption rate of each cluster in the first round. Since the energy consumption of a cluster is significantly greater than the other two clusters in $L_3$ , the standard deviation of the energy consumption rate of each cluster in $L_3$ is very large.

Figure 6.

Standard deviation of the energy consumption rate of each cluster.

Figure 7 shows the standard deviation of the energy consumption changes from the beginning to the end of the feedback process. It can be seen that the standard deviation of the energy consumption rate in the first round is the largest. With the feedback process going on, the standard deviation decreases, which indicates the feedback mechanism can balance the energy consumption load of each cluster. In the sixth round, the standard deviation decreases to a minimum value at $1.114\times {10}^{-3}$ . In the seventh round, the standard deviation of the energy consumption slightly increases compared to the fifth and sixth rounds, reaching $1.246\times {10}^{-3}$ . This indicates that it is very hard for the feedback process to balance the energy consumption of each cluster by adjusting the cluster’s size after the sixth round finishes. Now, the termination condition is satisfied and the feedback process finishes. In the eighth round, all nodes begin clustering according to the CH competition radius of the sixth round. Then, the network turns into the stable clustering stage.

Figure 7.

Standard deviation of the energy consumption in different rounds.

Comparisons under the default network environment

In this section, we compare the performance of LEACH, EEUC, DEBUC, FMUC-wf, and FMUC in the aspects of network lifetime and node residual energy rate when the first node dies. The network lifetime is defined as the time when the first node dies.

First, we compare the network lifetime of five algorithms under the default network environment. From Figure 8, LEACH is a single-hop routing algorithm, and it has the shortest network lifetime of only 42 rounds. Since the EEUC and DEBUC are typical unequal clustering algorithms, the network lifetime is significantly improved compared with LEACH. DEBUC reduces the communication energy consumption in the stage of CH competition using timing broadcasts and optimizes the inter-cluster routing. The network lifetime is 432 rounds, larger than 380 rounds of EEUC. The network lifetime of FMUC-wf is lower than FMUC and similar to DEBUC. Finally, FMUC dynamically adjusts the size of each cluster by the feedback mechanism to adapt to the distribution of heterogeneous nodes, so the network lifetime reaches 533 rounds.

Figure 8.

Network lifetime comparison between different algorithms.

Figure 9 shows the average node residual energy rate of five algorithms when the first node dies. From Figure 9, LEACH makes bad use of nodes’ energy. When the first node dies, 87.38% of the initial energy is wasted. In the heterogeneous networks, for EEUC and DEBUC, more energy cannot be effectively used. When the network lifetime is over, the average node residual energy rate is 60.04% and 46.88%. As FMUC adopts feedback mechanism, the average node residual energy rate reduces from 36.26% to 28.52%. It indicates that the feedback mechanism can effectively balance the energy consumption of each node in the heterogeneous network and make better use of node energy.

Figure 9.

Average node residual energy rate comparison between different algorithms.

Performance comparisons of different algorithms

In the default network environment, we change the proportion of heterogeneous nodes and observe the network performance of each algorithm under different proportions of heterogeneous nodes. Figures 10 and 11 show the network lifetime and the average node residual energy rate of each algorithm when the proportion of heterogeneous nodes increases from 20% to 80%. It can be seen from Figure 10 that for LEACH, the network lifetime is significantly lower than other algorithms. When the proportion of heterogeneous nodes is small, for EEUC, DEBUC, FMUC-wf, and FMUC, the difference in network lifetime is not obvious. However, with an increase in the proportion of heterogeneous nodes, the network lifetime of EEUC, DEBUC, and FMUC-wf declines significantly. Since the feedback mechanism balances the energy load of each cluster effectively due to the node heterogeneity, the network lifetime of FMUC is better than the other algorithms, when the proportion of heterogeneous node is increased.

Figure 10.

Network lifetime under different proportions of heterogeneous node.

Figure 11.

Average node residual energy rate under different proportions of heterogeneous node.

From Figure 11, we can see that with an increase in the proportion of heterogeneous nodes, the average node residual energy rate of EEUC, DEBUC, and FMUC-wf increases too. It is shown that EEUC, DEBUC, and FMUC-wf cannot make good use of the nodes’ energy while most nodes are heterogeneous. In contrast to these algorithms, FMUC obtains the lowest average node residual energy rate. When most nodes are heterogeneous, FMUC can better balance the energy consumption load between nodes and make good use of the nodes’ energy. The average node residual energy rate of LEACH remains at about 90% under different proportions of heterogeneous node. This result is consistent with that of Song et al. ⁵

Furthermore, we compare the network lifetime when the node’s initial energy is changed. From Figure 12, it can be seen that with an increase in the node’s initial energy, the network lifetime of all algorithms increases. The performance of FMUC is the best in the condition of different node’s initial energy. The reason is that FMUC algorithm can balance the energy load of each node by dynamically changing the cluster size according to the feedback value, so the nodes’ energy is better utilized. Thus, FMUC has the best network lifetime when changing the average energy of sensor nodes.

Figure 12.

Network lifetime under different node’s initial energy.

Figure 13 shows the comparison of the average node residual energy rate when the first node dies under different node’s initial energy. It is shown that compared with other algorithms, FMUC can make better use of node’s energy under different node’s initial energy.

Figure 13.

Average node residual energy rate under different node’s initial energy.

Figure 14 shows the comparison of network lifetime when the average size of the data produced by node in one clustering round is changed. It can be seen that with an increase in the amount of data produced by nodes, the traffic load of each node is also growing and the network lifetime is decreasing. When the average size of data produced by one node is 600 bits, the network lifetime of FMUC is slightly lower than EEUC and DEBUC. The reason for this result is when the size of data becomes smaller, the phenomenon of the imbalance of energy consumption load is not serious. Now, the effect of the feedback mechanism is not obvious. However, with an increase in the size of the data, the network lifetime of FMUC is larger than other algorithms.

Figure 14.

Network lifetime under different average data size.

Figure 15 shows the comparison of the average node residual energy. With an increase in the amount of data produced by nodes, the average node residual energy rate of each algorithm increases significantly except LEACH. The proposed FMUC can better balance the energy consumption load between nodes by dynamically adjusting the cluster size. Then, the average node residual energy rate of FMUC is lower than other algorithms.

Figure 15.

Average node residual energy rate under different average data size.

Conclusion

In this article, we have studied the problem of energy hole in heterogeneous sensor networks. In contrast to existing solutions, the main innovative work of this article is summarized as follows:

1. In the initial stage of the network, we temporarily ignore the distribution of heterogeneous nodes and divide the network into several layers with different layer heights. Every cluster is limited in one layer, thus ensuring the balance of the energy consumption between clusters in the condition of homogeneous networks.

2. FMUC algorithm uses feedback mechanism to balance the energy load of each node. According to the energy consumption of each cluster, the sink calculates the feedback value which could change the CH competition radius of each node. Thus, the size of each cluster can be dynamically changed in a new round. To save the energy consumption of receiving the feedback value, this article proposes the termination condition for the feedback process. When it is hard for the feedback process to balance the energy consumption of each cluster, the feedback process stops and the network turns into the stable clustering stage.