An unequal clustering routing protocal for wireless sensor networks based on genetic algorithm

WANG Lei, HUO Jiuyuan,2,3, Al-Neshmi Hamzah Murad Mohammed

(1. School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China；2. Lanzhou Huahao Technology Co. Ltd, Lanzhou 730070, China；3. National Cryosphere Desert Data Center (NCDC), Lanzhou 730070, China)

Abstract： The imbalance of energy consumption in wireless sensor networks (WSNs) easily results in the “hot spot” problem that the sensor nodes in a particular area die due to fast energy consumption. In order to solve the “hot spot” problem in WSNs, we propose an unequal clustering routing algorithm based on genetic algorithm (UCR-GA). In the cluster head election phase, the fitness function is constructed based on the residual energy, density and distance between nodes and base station, and the appropriate node is selected as the cluster head. In the data transmission phase, the cluster head selects single-hop or multi-hop communication mode according to the distance to the base station. After we comprehensively consider the residual energy of the cluster head and its communication energy consumption with the base station, an appropriate relay node is selected. The designed protocal is simulated under energy homogeneous and energy heterogeneity conditions, and the results show that the proposed routing protocal can effectively balance energy consumption, prolong the life cycle of network, and is appicable to heterogeneous networks.

Key words： wireless sensor networks (WSNs)； genetic algorithm (GA)； unequal clustering； multi-hop； life cycle of network; energy consumption

0 Introduction

The technological advancement in the energy-efficient low-cost sensors, electronic circuits and radio frequency (RF) communication modules along with the internet of things (IoT) evolution have revived the interest in wireless sensor network (WSN) research and applications[1]. A WSN is a self-organized network composed of a large number of sensor nodes that collect, process and transmit information of the sensing area. It has been widely used in military, disaster risk reduction, environment, medicine and other scientific fields[2-4]. Since sensor nodes are generally deployed in the places where the environment is harsh and people cannot reach, once the nodes are deployed, it is difficult to carry out the follow-up maintenance of nodes. Therefore, it is crucial to design energy-efficient routing algorithms.

In traditional wireless sensor networks, each node has to communicate with the base station, which consumes much energy and makes the information received by the base station usually have serious redundancy. Clustering can reduce the number of nodes directly communicating with the base station, so as to save energy and prolong the life time of WSN. It is an effective measure to reduce the energy consumption of WSNs[5-6]. In the cluster routing algorithm, member nodes’ information is sent to base station through the cluster head, in this way, the energy consumption is lower than that of all nodes communicating directly with the base station. However, because the cluster head needs to receive the cluster member nodes’ information and send it to the base station after data fusion, its energy consumption is high, and improper clustering structure often leads to some cluster heads’ death due to excessive energy consumption. Therefore, in the used routing algorithm, reducing and balancing energy consumption has become a hot spot for researchers.

Low-energy adaptive clustering hierarchy (LEACH) algorithm[7]is the first low-power adaptive clustering routing algorithm. Each cluster is composed of cluster head nodes and member nodes. Cluster heads can communicate directly with base stations, and member nodes can only communicate with corresponding cluster heads. The network time is divided into multiple rounds. After the clustering structure is formed in each round, the member nodes transmit information to the cluster head, and then the data are fused by the cluster head and sent to the base station directly so as to reduce the energy consumption and reduce the base station’s data redundancy. Simultaneously, by rotating the cluster head role uniformly among all nodes, the network load can be distributed to each node. Scholars have done much research based on the LEACH algorithm to improve the network’s energy efficiency further. Power-efficient clustering routing protocol (PECRP)[8]modifies the threshold formula, which considers the distance between the node’s residual energy and the base station, and combines multi-hop routing to extend the network life cycle. Hybrid unequal clustering with layering protocol (HUCL) algorithm[9]is a hybrid of static and dynamic clustering approaches. The selection of cluster head is based on residual energy, the distance to the base station and the number of neighbor nodes. Once the cluster is formed, the same clustering structure will be maintained for several rounds until a cluster head’s energy is lower than the threshold value. The cluster head then selects a new cluster head according to the residual energy and the distance to itself. Stable election protocol (SEP)[10]is based on a second-level heterogeneous network. The nodes are divided into advanced nodes and ordinary nodes. The advanced nodes have higher initial energy than ordinary nodes, so the probability of an advanced node being selected as cluster head is higher than that of an ordinary node. Energy and coverage-aware distributed clustering protocol (ECDC)[11]defines the degree and coverage importance metrics of nodes. Cluster heads are generated by local competition. The node with more residual energy and more neighbor nodes is more likely to be selected as cluster head. This algorithm can construct a better clustering topology to reduce energy consumption. Energy-and-distance efficient clustering algorithm (EDECA)[12]comprehensively considers the influence of node residual energy and distance on selection of cluster head, optimizes the probability and threshold formula of node selecting cluster head, the node with higher residual energy is more likely to be selected as cluster head.

Some scholars have introduced intelligent optimization algorithms into the design of routing algorithms of WSNs. For example, the clustering routing protocol based on improved particle swarm optimization algorithm (GRIPSO)[13]uses the PSO algorithm to optimize clustering, and construct reasonable clustering topology by comprehensively considering node’s residual energy and position through fitness function. At the same time, the multi-hop data transmission path based on the minimum spanning tree is established to shorten the communication distance of nodes and make the energy consumption of nodes lower and more balanced. Energy-aware clustering for wireless sensor networks using particle swarm optimization (PSO-C) algorithm[14]uses the PSO algorithm to select cluster heads, optimize the cluster head’s energy and obtain reasonable clustering topology between a node and cluster head. Compared with the LEACH algorithm, this algorithm can prolong the lifetime of network. However, since the algorithm uses single-hop communication, the nodes far away from the base station will consume much energy and die prematurely. Routing using ant colony optimization (RACO) algorithm[15]uses the ant colony algorithm to optimize multi-hop routing, and builds the best path between the cluster head and base station to reduce energy consumption. LEACH-centralized (LEACH-C) algorithm[16]uses the simulated annealing algorithm to determine the number of cluster heads and selects cluster heads according to the residual energy and location information of nodes to avoid premature node death.

In equal clustering routing algorithms, multi-hop communication is often better than single-hop communication. However, in the multi-hop communication, the cluster head near the base station needs to forward the remote cluster head’s information, so that the cluster head near the base station dies due to premature exhaustion of its energy. Scholars call this a “hot spot” problem. In order to solve the “hot spot” problem, Soro[17]et al. proposed unequal clustering for the first time. The clusters with uneven sizes are constructed in the network. The clusters closer to base station have smaller sizes than those farther away from it. Thus cluster heads closer to the base station can preserve some energy for the inter-cluster data forwarding, so as to balance the energy consumption of the network. However, the algorithm is based on a heterogeneous network. The location of the cluster head is calculated in advance, and has more initial energy. Energy-efficient uneven clustering (EEUC) algorithm[18]is a distributed unequal clustering algorithm that elects cluster heads based on nodes’ residual energy. Furthermore, it uses uneven competition ranges to construct clusters with uneven sizes, the clusters closer to base station have smaller sizes, so that the cluster head can save energy to forward the information of other cluster heads and achieve the purpose of balancing energy consumption. Location-based unequal clustering algorithm (LUCA)[19]is similar to EEUC algorithm, which determines the cluster size according to the distance between cluster head and base station. The cluster far away from the base station has a larger cluster size. In addition, the optimal cluster size of the network is analyzed mathematically, and the core idea of unequal clustering is elaborated in detail. Energy driven unequal clustering protocol (EDUC)[20]is an unequal clustering algorithm based on heterogeneous network. Different from the previous unequal algorithms, in this algorithm, the cluster far away from base station has a smaller size than those close to base station. All cluster heads communicate with the base station directly to balance energy consumption. However, this algorithm is only applicable to small-scale networks due to single-hop communication. When the network scale increases, cluster heads’ energy consumption far away from base stations increases rapidly. Cluster head multi-hops routing algorithm improved based on LEACH algorithm (CMRAOL)[21]improves the LEACH algorithm based on the idea of unequal clustering. The cluster head is selected according to residual energy and the distance from base station. The node with greater energy and smaller the distance to base station has greater probability becoming cluster heads. Thus, the clusters close to the base station are smaller than clusters far from the base station.

Genetic algorithm (GA) is a random search algorithm simulating natural selection and genetics. In applying the GA to WSNs, scholars have done a lot of research work[22-25]. For example, the genetic algorithm-based energy-efficient clustering and routing approach (GECR)[26]uses the GA to optimize clustering and routing, combine the clustering and routing scheme into a single chromosome and calculate the total amount of energy consumed for clustering and routing together. It constructs fitness function according to energy consumption and load balance, which can effectively extend the life cycle of network. However, in this algorithm, cluster head is determined in advance, which can not be applied to other networks. Genetic algorithm based distance-aware routing protocol (GADA-LEACH)[27]uses GA to select the cluster head and the node with high residual energy and close to the base station is selected as the cluster head. Furthermore, it combines multi-hop routing to reduce energy consumption and prolong the life cycle of network. Genetic algorithm-based, self-organizing network clustering algorithm (GASONeC)[28]optimizes clustering by GA, and the fitness function considers the remaining energy of cluster head, the estimated energy consumption, the distance to base station and density. However, this algorithm uses single-hop communication, that it isnot applicable to large-scale networks. Genetic algorithm based method that optimizes heterogeneous sensor node clustering algorithm (GAHN)[29]is a routing algorithm for heterogeneous networks based on GA. It reduces energy consumption by minimizing the communication distance of the network. The fitness function considers the residual energy of nodes, the estimated energy consumption and the distance to base station, which can effectively balance energy consumption. GA-PSO-based clustering and routing algorithm[30]uses GA to optimize clustering to obtain a reasonable clustering structure, and uses PSO algorithm to optimize routing to reduce energy consumption. However, this algorithm does not consider the residual energy of nodes in the cluster head selection phase, which leads to early death of nodes.

In our work, we propose an unequal clustering routing algorithm based on the GA (UCR-GA) to solve the “hot spot” problem in WSNs. The algorithm adopts the communication mode of single-hop within-cluster and the combination of single-hop and multi-hops between clusters. Single-hop communication within-cluster is simple and easy to implement. Inter-cluster communication adopts the combination of single-hop and multi-hop, which helps to reduce and balance energy consumption. In the cluster head election phase, UCR-GA selects reasonable cluster head nodes based on residual energy, density and distance of nodes to construct optimal clustering. In addition, the multi-hop communication path between cluster head and base station is established to shorten the communication distance and avoid the energy waste caused by long-distance data transmission. The experimental results show that the UCR-GA algorithm can effectively prolong the life cycle of network, balance energy consumption and avoid the “hot spot” problem.

The main contributions of this study can be summarized as follows： (1) We propose a centralized algorithm based on unequal clustering to effectively solve the “hot spot” problem in WSNs. (2) We introduce a candidate cluster head mechanism to shorten the convergence time of the algorithm. (3) We construct fitness function based on energy factor, density factor and distance factor to optimize clustering structure. (4) We design a multi-hop path of energy balance for inter-cluster communication. (5) We simulate the algorithm in the case of energy heterogeneity and homogeneous to verify the performance of proposed algorithm.

1 System model

1.1 Network model

Considering that the WSN is composed of nodes distributed in a square field, to simplify the network model, we adopt a few reasonable assumptions as follows：

1) Sensor nodes are randomly distributed in a WSN. The energy is limited and can not be changed once the deployment is completed；

2) Base station is located outside the sensor field, it has sufficient energy and the location of the base station is always unchanged；

3) Each node has an identity (ID)；

4) Cluster heads can fuse data to reduce the amount of data transmitted；

5) The node can judge the distance from the sender according to the strength of the received signal, and can adjust their transmission power.

1.2 Energy consumption model

We adopt the same radio energy dissipation model similar to the LEACH algorithm, as shown in Fig.1.

Fig.1 Radio energy dissipation model

In this model, the energy consumed by a node sendingLbits of data at a distance ofdconsists of two parts： transmitting circuit loss and power amplification loss, which is expressed as

(1)

2 UCR-GA

UCR-GA algorithm is a centralized clustering algorithm. Network clustering and multi-hop path establishment are carried out in the base station with unlimited energy. Each round is divided into two stages: clusters construction and data transmission. In the cluster construction stage, the base station selects the appropriate node as the cluster head based on GA. After clustering, it enters the data transmission stage. The member nodes transmit data to the cluster head, then the data are fused by the cluster head and sent to the base station along the multi-hop path.

2.1 Election of cluster head

Cluster heads are selected based on GA. When selecting the cluster head, the base station needs to know the location, density and energy information of nodes. In the preparation stage before the first round, the node sends the location, density and initial energy information to the base station, which receives the information and then saves it. When the node sends its information in each subsequent round, it also sends its energy and other information to the cluster head.

2.1.1 Chromosome representation

In the UCR-GA algorithm, each gene value on a chromosome indicates the cluster head’s ID in the network, and the length of the chromosome is equal to the number of cluster heads. An example of a WSN clustering scheme is illustrated in Fig.2, where “°” represents the member node and “·” represents the cluster head node. There are ten cluster head nodes in Fig.2, and their ID numbers are {11,7,16,4,20,18,9,31,8,21}, which correspond to the values of the genes on the chromosomes, respectively.

Fig.2 Chromosome and network clustering construction

2.1.2 Population initialization

The initial population is composed of several randomly generated chromosomes. To reduce the search range and improve the efficiency of the algorithm, the cluster head election is not to search in all nodes, but to select the candidate cluster head first, and then to select the final cluster head from the proposed candidate cluster heads. When initializing the population,Kcluster heads are randomly selected from the set of candidate cluster heads, and the ID numbers of the selected cluster heads are assigned to the corresponding gene values on chromosomes.

2.1.3 Fitness function

In WSNs, the nodes are powered by batteries. When the network works, the member nodes transmit information to the cluster head, and then the cluster head carries out data fusion and sends it to the base station. Therefore, we can reduce and balance the energy consumption of network by selecting appropriate nodes as cluster heads. In this study, the energy, density and distance of cluster head are used as evaluation indexes to construct fitness function to evaluate each chromosome.

1) Energy factor

(2)

The set of neighbor nodes of nodeSiis defined as

N(i)={Sj|d(Si,Sj)≤Rmax},

(3)

whered(Si,Sj) is the distance between nodesSiandSj, andRmaxis the maximum competition radius.

2) Density factor

(4)

(5)

whered(CHi,BS) represents the distance between cluster headiand base station;dmaxanddminare the farthest distance and the nearest distance from the node to the base station, respectively;Rmaxis the maximum competition radius, here we take the maximum competition radiusRmax=80 m.

3) Distance factor

The distance factor is equal to the distance between the base station and the network center divided by the average distance between the cluster head and the base station. Tthe distance factorf3is calculated by

(6)

whered(BS,NC) is the distance from the base station to the network center, andd(CHi,BS) represents the distance between cluster headiand base station.

Based on the energy factor, density factor and distance factor, the calculation method ofthis paper’s fitness function calculated by

F=f1+f2+f3.

(7)

The fitness function can comprehensively evaluate the cluster head node set represented by each chromosome in the population. The larger the fitness function, the better the cluster head node set.

2.1.4 Crossover

Crossover operation is used to cross some genes of two individuals to generate two new child chromosome from two parent chromosome. It is the key to generate new individuals in GA, which ensures the diversity of population individuals to a certain extent. In this study, we employ a single-point crossover. When performing a crossover operation, we choose a random crossover point and two parent chromosomes to exchange gene values after that point. The crossover process is shown in Fig.3.

Fig.3 Crossover between two parent chromosomes

2.1.5 Mutation

Mutation operation is used to generate new chromosomes and maintain population diversity, which is an effective measure for GA to jump out of local optimum. In this study, we employ a single-point mutation. When performing a mutation operation, mutation points are randomly selected on the chromosome. Assuming that thekth gene needs to mutate, we randomly select a new cluster head that is not in the chromosome from the set of candidate cluster heads to replace the previouskth allele. The mutation process is shown in Fig.4.

Fig.4 Mutation of chromosome

So far, a detailed cluster head election algorithm is given, and the steps are as follows：

Step 1： Select the candidate cluster heads.

Calculate the average residual energy of the surviving nodes in the network. If the nodes’ residual energy is greater than or equal to the average residual energy of the nodes, it is elected as the candidate cluster heads.

Step 2： Initialize the population.

Step 3： Repeat the following steps until the fitness converges or the maximum number of generations is reached.

1) Calculate the fitness value of each chromosome in the population.

2) Use the roulette wheel algorithm to select the chromosomes with higher fitness value from the population.

3) Perform the crossover according to crossover probability.

4) Perform the mutation according to mutation probability.

Step 4： Select the chromosome with the highest fitness value to restructure nodes according to the clustering scheme represented by chromosomes.

2.2 Data transmission

The data transmission is divided into two stages： intra-cluster communication and inter-cluster communication. In intra-cluster communication, the member nodes send the information to the cluster head by direct communication, and the cluster head performs data fusion to reduce data redundancy. In inter-cluster communication, single-hop and multi-hop hybrid communication mode is adopted. Cluster head needs to select single-hop or multi-hop mode to transmit information according to its distance from the base station.

When the cluster head communicates with the base station, the cluster head far away from the base station (d>d0) uses multipath decay model, the cluster head close to the base station (d≤d0) uses free space model. Therefore, when the distance between the cluster head and the base station is less than or equal tod0, single-hop communication is adopted; otherwise, multi-hop communication is adopted. Once multi-hop communication is selected, the cluster head needs to select relay nodes from other cluster heads to forward its data. In Ref.[17], the energy consumption of two-hop communication is analyzed. It is found that when clusteritakes cluster headjas the relay node,d2(CHi,CHj)+d2(CHj,BS)determines the level of energy consumption. In order to select a suitable relay node, considering the residual energy and energy consumption of the relay node comprehensively, parameter weights are introduced as

(8)

The method for cluster headito select the relay node is as follows： Cluster headiselects the cluster head with the largestWjfrom the rest of the cluster heads as the relay node. If there are two equal weights, the cluster head with larger residual energy is selected as the relay node. After the multi-hop path is determined, the cluster head node forms a tree with the base station as the root node, and the data are transmitted along the direction of the base station on the side.

3 Simulation and discussion

Matlab was used to run the simulation experiments of the UCR-GA algorithm in this study. The performance of UCR-GA algorithm is verified under energy homogeneous and energy heterogeneous. The parameters of GA are shown in Table 1.

Table 1 Parameters of GA

3.1 Energy homogeneous

Under the condition of energy homogeneous, we compare the proposed UCR-GA algorithm with six clustering routing ： LEACH, PECRP, CMRAOL GADA-LEACH, EEUC and GA-PSO algorithms. The parameters of simulation are shown in Table 2.

Table 2 Parameters configuration in Matlab simulation

3.1.1 Distribution of the number of cluster heads

Cluster heads play an essential role in WSN communication. A stable clustering algorithm should generate a relatively consistent number of cluster heads. Moreover, the number of cluster heads that can be kept stable is an important criterion for measuring and evaluating the clustering algorithms. Fig.5 shows the distribution of the number of cluster heads of seven networks in the simulation process. It can be seen that LEACH, CMRAOL and PECRP algorithms are unstable in the number of cluster heads, and the number of cluster heads fluctuates severely because the cluster heads are selected according to the threshold. EEUC algorithm selects cluster heads through local competition, producing a relatively stable number of cluster heads. GADA-LEACH and GA-PSO algorithms use GA to select cluster heads while do not limit the number of cluster heads, so the number of cluster heads fluctuates slightly. In the UCR-GA algorithm, the number of cluster heads remains stable because it selects cluster heads based on GA, and determines the number of cluster heads by chromosome length. Compared with the other six algorithms, the UCR-GA algorithm can generate a stable number of clusters, which is conducive to network stability and prolonging network lifetime. Therefore, the algorithm has high stability and reliability.

(a) LEACH

(b) CMRAOL

(c) PECRP

(d) EEUC

(e) GADA-LEACH

(f) GA-PSO

(g) UCR-GAFig.5 Distribution of the number of cluster heads

3.1.2 Energy consumption

1) Life cycle of network

The life cycle of network is one of the critical indicators to evaluate the performance of cluster routing algorithms, which is defined as the time span from the moment the network first operates to the moment of the first node’s death. Fig.6 shows the number of the live nodes of the seven algorithms in the network . It can be seen from that the UCR-GA algorithm is better than the other six algorithms in terms of the time from the death of the first node to the death of the last node. The first node death time of the UCR-GA algorithm is 570 rounds, while the first node death times of the CMRAOL, GADA-LEACH, PECRP, EEUC, GA-PSO and LEACH algorithms are 467, 459, 380, 255, 252 and 95 rounds, respectively. It can be seen that the UCR-GA algorithm extends the first node death times of the other six algorithms by 22%, 24%, 50%, 124%, 127% and 500%, respectively.

Fig.6 Life cycle of network

The last node death time of the UCR-GA algorithm is 626 rounds, while the last node death time of the CMRAOL, GADA-LEACH, PECRP, EEUC, GA-PSO and LEACH algorithms are 578, 552, 471, 458, 574 and 492 rounds respectively. It can be seen that the UCR-GA algorithm extends the last node death time of the other six algorithms by 8%, 13%, 33%, 37%, 9% and 27%, respectively. The time span from the death of the first node to the death of the last node can reflect the nodes’ energy balance in the network. The shorter the span, the more balanced the energy consumption of the network. The time span of the UCR-GA algorithm is smaller than that of the other six algorithms, which means that the UCR-GA can effectively balance the energy consumption. This is because in the cluster head election stage, the cluster head distribution is reasonable by considering the energy, density and distance to the base station of nodes to reduce energy consumption and distribute the energy consumption evenly to all nodes, thus prolonging the network life cycle.

Fig.7 shows the time (round) of the first node death of the seven algorithms in the network in an area of 200 m×200 m as the numbers of nodes are 100, 200, 300, 400, and 500, respectively. It can be seen that the life cycle of the UCR-GA algorithm is always longer than those of the other six algorithms, which means that compared with other algorithms, the UCR-GA algorithm can effectively save energy consumption and prolong the life cycle of network.

Fig.7 Death time (rounds) of the first node as the number of nodes varies from 100 to 500

In addition, with the increase of node density, the life cycles of PECRP, GADA-LEACH, EEUC, GA-PSO and LEACH algorithm fluctuate in a small range, which indicates that the five algorithms are not sensitive to node density. Increasing or reducing node density cannot significantly improves their life cycle. The results of UCR-GA and CMRAOL algorithms have an upward trend with the increase in node density, and the uptrend of the UCR-GA algorithm is more obvious, which indicates that the UCR-GA algorithm is more suitable for the network with higher node density.

2) Energy consumption of network

The energy of WSN is limited.The routing algorithm needs to choose reasonable clustering structure and multi-hop path to complete the transmission of monitoring data, balance the energy consumption of network and prolong the life cycle of network as far as possible. Fig.8 shows the comparison results of resudial energies of the seven algorithms in the whole network. It can be seen that the residual energy of the UCR-GA algorithm is significantly higher than those of other six algorithms.

Fig.8 Comparison of resudial energies

Figs.9 and 10 show the total energy consumption of the cluster head and the total network energy consumptions of seven algorithms. Ten rounds are randomly selected in the network operation to calculate the total energy consumptions of the network and cluster head.

Fig.9 Total energy consumption of cluster heads

It can be seen from Fig.9 that the total energy consumption of cluster heads of the UCR-GA algorithm is significantly lower than those of the other six algorithms, and the fluctuation is small because it effectively reduces the of energy consumption of cluster heads by constructing reasonable multi-hop paths. Moreover, the number of cluster heads generated by the algorithm is stable, which can control the energy consumption of cluster heads’ at a reasonable level. in Fig.10, the total network energy consumption of the UCR-GA algorithm is significantly lower than those of the other six algorithms, which indicates that the UCR-GA algorithm can effectively reduce network energy consumption and has higher stability.

Fig.10 Total energy consumption of network

3) Balance of network energy consumption

Figs.11 and 12 show the comparison results of the seven algorithms in terms of energy consumption balance.

Fig.11 Comparison of variance of node residual energy

Fig.11 shows the variance of residual energy. The smaller the variance, the more balanced the residual energy. The variance of the UCR-GA algorithm is always smaller than those of the other six algorithms and the fluctuation is small, indicating that the UCR-GA algorithm can effectively balance the energy consumption of the network. Fig.12 shows the distribution of dead nodes of the seven algorithms.

(a) LEACH

(b) PECRP

(c) GA-PSO

(d) GADA-LEACH

(f) EEUC

(g) UCR-GAFig.12 Distribution of dead nodes(30% dead nodes, ” represents dead node, “°” represents survival node)

To avoid the “hot spot” problem, the dead nodes should be evenly distributed throughout the network. It can be seen that LEACH, PECRP, GA-PSO and GADA-LEACH algorithms have very concentrated distributions of dead nodes, causing a serious “hot spot” problem. This is because these four algorithms are equal clustering routing protocols. When single-hop routing is adopted, the nodes far away from the base station die first, while when multi-hop routing is adopted, the nodes close to the base station die first. CMRAOL and EEUC algorithms are the unequal clustering routing algorithm. Although energy consumption is balanced to a certain extent, there is still a small range of aggregation phenomena at the dead node. The UCR-GA algorithm has a more uniform distribution of death nodes than the other six algorithms, indicating that UCR-GA algorithm can better balance the energy consumption of nodes and effectively avoid the “hot spot” problem.

3.1.3 Number of packets received

Figs.13 and 14 show the numbers of packets received by the cluster head and the base station, respectively.

Fig.13 Number of packets received by cluster head

It can be seen from Fig.13 that the number of packets received by the cluster head of the UCR-GA algorithm is always higher than those of other six algorithms. When the cluster heads of the other algorithms stop receiving data, the cluster head of the UCR-GA algorithm can still receive monitoring data from cluster members, which indicates that the algorithm can extend the monitoring time of the network. Fig.14 shows the number of packets received by the base station of seven algorithms. The base stations of CMRAOL, GADA-LEACH, PECRP, GA-PSO and LEACH algorithms receive more packets than other algorithms. This is because a large number of cluster heads are selected for each round of these five algorithms. Although the base station receives a large number of packets, there is serious data redundancy. Moreover, excessive cluster heads lead to a significant increase in energy consumption, which affects the life cycle of the network. The number of packets received by the base station of the UCR-GA algorithm is greater than that of EEUC algorithm. When the other six algorithms stop receiving data, the UCR-GA algorithm can still receive data because it produces a stable number of cluster heads per round, and the data redundancy between cluster heads is limited. Although the number of packets received by the base station is less, it can extend the monitoring time of the network as much as possible under the premise that the network keeps working normally.

Fig.14 Number of packets received by base station

3.2 Energy heterogeneous

Under the condition of energy heterogeneous, we compare the proposed UCR-GA algorithm with five clustering routing algorithms： GADA-LEACH, EDECA, PECRP, GA-PSO and SEP algorithms.

The parameters of the simulation are shown in Table 3, in which the proportion of advanced nodes ism, and the initial energy of normal nodes before operating the network isE0, the initial energy of the advanced node is (1+a)E0,ais the ratio of the additional energy of the advanced node to the initial energy of the normal node.

Table 3 Parameters configuration in simulation experiments

3.2.1 Life cycle of network

Fig.15 shows the number of live nodes in heterogeneous network. The first node death times of the UCR-GA algorithm is 946 rounds, while the first node death time of the GADA-LEACH, EDECA, PECRP, GA-PSO and SEP algorithms are 555, 628, 564, 485 and 143 rounds, respectively. The UCR-GA algorithm extends the first node death times of the other five algorithms by 95%, 51%, 68%, 95% and 562%, respectively. The last node death time of the UCR-GA algorithm is 996 rounds, while the last node death times of GADA-LEACH, EDECA, PECRP, GA-PSO and SEP algorithms are 948, 828, 732, 967 and 895 rounds, respectively. The UCR-GA algorithm extends the last node death time of the other five algorithms by 5%, 20%, 36%, 2% and 11%, respectively. It can be clearly seen that the UCR-GA algorithm has significantly improved the node survival rate, and the number of death nodes with the same number of rounds in the UCR-GA algorithm is less than those of the other five algorithms, therefore, the network life cycle is extended.

Fig.15 Life cycle of network

3.2.2 Energy consumption analysis

In heterogeneous networks, the energy consumption of the UCR-GA algorithm is analyzed from the aspects of node residual energy, cluster head’s total energy consumption and network’s total energy consumption. Fig.16 shows the comparison results of the resudial energies of the six algorithms in the whole network.

Fig.16 Comparison of resudial energies

It can be seen that the energy consumption rate of the UCR-GA algorithm is significantly lower than those of other five algorithms. This is because in selecting cluster heads, the fitness function comprehensively considers node energy, density and distance from node to base station, which makes the clustering structure more reasonable, so as to reduce energy consumption and prolong the life cycle of the network.

Figs.17 and 18 compare the total energy consumption of cluster head and the total energy consumption of network, respectively.

Fig.17 Total energy consumption of cluster heads

Fig.18 Total energy consumption of network

From the beginning of operating network to the death the first node the cluster head and network, we randomly select ten rounds to calculate the total energy consumption. It can be seen that the total energy consumptions of the cluster head and network of the UCR-GA algorithm are lower than those of the other five algorithms, and the fluctuation is smaller, which means that the UCR-GA algorithm can effectively reduce energy consumption and has high stability.

3.2.3 Balance of network energy consumption

In heterogeneous networks, the balance of energy consumption is mainly manifested in balancing the energy consumption of advanced nodes and normal nodes. Fig.19 shows the death times of the advanced nodes and normal nodes of the six algorithms.

(b) GADA-LEACH

(c) GA-PSO

(d) SEP

(e) EDECA

(f) UCR-GAFig.19 Death time of advanced node and normal node

Among them, the PECRP, GADA-LEACH and GA-PSO algorithms are energy isomorphic routing algorithms, so normal nodes often die earlier than advanced nodes. The SEP is a routing algorithm designed for heterogeneous networks, and its normal nodes and advanced nodes almost start to die at the same time. Although the EDECA algorithm is also a routing algorithm for heterogeneous networks, it is different from SEP algorithm. In SEP, the probability of advanced nodes being selected as cluster heads is higher than that of ordinary nodes and the probability remains unchanged. Nevertheless, in each round of the EDECA, the probability of selecting a cluster head varies according to the residual energy. Therefore, although the algorithm prolongs the network life cycle, it is not as good as SEP in energy balance. The UCR-GA algorithm considers the nodes’ residual energy when selecting cluster heads, therefore, compared with the normal nodes, advanced nodes can be selected as cluster heads frequently to balance energy consumption. It can be seen from that the UCR-GA algorithm is similar to the SEP algorithm, and normal nodes and advanced nodes almost start to die at the same time, therefore, the balance of energy consumption of the algorithm is better.

4 Conclusions

This paper presents an unequal clustering routing algorithm based on GA to solve the “hot spot” problem. We construct fitness function based on the residual energy, density and distance to the base station of nodes, and select appropriate nodes as cluster heads to construct the optimal clustering, balance and reduce communication energy consumption. For the selection of relay nodes in multi-hop communication, the residual energy of cluster head and its communication energy consumption with base station are comprehensively considered to reduce energy consumption and prolong the life cycle of the network. Simulation results show that the proposed algorithm can efficiently improve network energy utilization, balance network load, and prolong the life cycle of network.

However, our work focuses on the design of energy-efficient and balanced clustering routing algorithm, and does not study the convergence of the whole algorithm in runtime. At the same time, a centralized clustering algorithm requires nodes to send their own information to the base station, which will cause additional energy consumption. These problems must be solved in practical applications in the future.