1 Introduction

Wireless sensor networks (WSNs) consist of nodes with limited energy (Yin et al. 2022). The WSN is a new type of wireless network that gathers and processes data in the environment (Ramli et al. 2021). The nodes collect data from the surrounding environment and send them to the base station (BS) to be processed (Khalaf et al. 2022). The nodes have limited energy. Therefore, the initial energy of each node is drained with each data transmission. This problem is a risk for network lifetime (Wang et al. 2012a). One of the approaches for increasing the lifetime of WSN is routing (Zagrouba and Kardi 2021). Routing finds the best route between nodes that transfer data to the BS. There are many factors for finding the best route between nodes: the primary energy of nodes, node density in the environment, the distance between nodes and the BS, data aggregation, etc. (Khalil and Bara’a 2011). Generally, there are two methods to transfer data to the BS: multi-hop and single-hop transfer (Lin et al. 2012; Tam et al. 2021). In single-hop transfer, nodes send their data directly to the BS. In multi-hop transfer, nodes send their data to the BS via mediators such as other nodes or cluster heads (CHs). In both methods, the nodes' distribution environment is divided into sections called clusters. In each cluster, a node with better conditions is selected as the cluster head (CH) (Vazifehdan et al. 2012). Then all the nodes in clusters send their data to its CH. Finally, the CHs, depending on the transfer fashion (multi-hop or single-hop), send the collected data directly to the BS or a higher level (Bari et al. 2009). There are many methods for clustering and selecting the optimum route in WSN. One of these methods is the hierarchical approach (Shukla and Sengupta 2020). In this method, the environment of the nodes is divided into parts called clusters. Transferring between nodes is performed through the clusters. The other fashions of routing are flooding (Qazi et al. 2021), gossiping (Santhosh Kumar et al. 2021), and hybrid energy-efficient distributed (HEED) algorithms (Younis and Fahmy 2004). In these methods, there are problems such as collision and overlap.

In most of the proposed methods, the cluster head selection is random. In others, such as the LEACH algorithm (Yadav and Sunitha 2014) and LEACH-based approaches (Shi et al. 2012; Tong and Tang 2010; Braman and Umapathi 2014; Daanoune et al. 2021), nodes are selected as cluster head in the current round. Therefore, they have less priority in later rounds. Unselected nodes in the later rounds may be eligible for CH. Therefore, these methods do not guarantee the selection of the appropriate cluster head. To solve these problems, using metaheuristic algorithms is recommended. The genetic algorithm is one of the metaheuristic methods that provide a search technique to find proper solutions in an acceptable time (Ai et al. 2022; Kashyap et al. 2020; Roy and De 2022). Every time GA is handled, lower essential samples are also considered and used until the obtaining desired results. Therefore, the GA ensures that earlier and less important samples are applied. In this study, we present the routing algorithm based on three dimensions of node energy, distance, and density of nodes. This algorithm can improve the network lifetime by reducing the number of generations compared with previous similar methods. The main aims of this research are:

  • Increasing the network lifetime by selecting the appropriate CHs

  • Selecting the appropriate CH by genetic algorithm

  • Reducing the number of executable generations to select CH

  • Reducing energy consumption per node in each round

  • Improving the selection of proper CHs in high-density areas compared to low-density areas.

One of the main problems of older algorithms such as LEACH and C-LEACH is the selection of CH in the final rounds. In these algorithms, with each run, the energy of the nodes is gradually reduced. Moreover, in some environments, the distribution of the node may be random. For this reason, some areas may have more nodes. Therefore, more CHs should be selected in high-density regions to balance the network load. The protocol presented in this research considers these issues properly.

The rest of the article is organized as follows: We present a summary of the clustering algorithms in the next section. In Sect. 3, we review the genetic algorithm (GA) and network model. In Sect. 4, we go into details regarding our algorithm, and in Sect. 5, we present the results obtained from the simulation and compare them with similar studies. Finally, conclusions will be drawn.

2 Related Works

One of the clustering methods is LEACH (Bagci 2016). It is a self-manager protocol with constant clustering that uses a random approach to distribute energy between nodes. In the LEACH, nodes manage themselves into local groups, and one node plays the role of a local station. The operation rounds in the LEACH are repeated periodically. Each round is performed with the primary regulations. In the steady phase, data are sent to the base station. To minimize the information overhead, the duration of the steady stage must be more than the primary regulation stage. The LEACH algorithm consists of setup and steady stages. In the setup stage, clusters are formed. After forming the clusters, each node decides to be in the setup stage of the cluster head or not. This decision is directly related to the percentage advised for the number of cluster heads and must be determined in advance. Another proper aspect of this decision-making is the number of times in which a node has already been selected as a cluster head. For this decision-making, each node selects a random number between 0 and 1. If the selected number is less than the threshold Tr(n), it is chosen as the cluster head.

$$T_{r} \left( n \right) = \left\{ {\begin{array}{*{20}l} {\frac{e}{{1 - e\left( {r\,\bmod \,\frac{1}{e}} \right)}}\;if} \hfill & {n \in G} \hfill \\ 0 \hfill & {{\text{otherwise}}} \hfill \\ \end{array} } \right.$$
(1)

where

n: individual sensor node,

e: the desired percentage of cluster heads, and

G: the collection of nodes that are not selected as CH yet in recent r rounds.

In the first round, all the nodes that have the probability e can be a cluster head. After evolving the cluster head, each node cannot be a cluster head in the last 1/e rounds. In the next round, the probability of the unselected node as a cluster head is increased. So, in the round (1/e-1), \({T}_{r}(n)\) equals 1.

Data are transmitted in the steady phase. After forming clusters and their members, the data are transmitted. Common nodes can transmit the collected data to the cluster head during the allocated time. This connection needs the least amount of energy. Other methods for the improvement of energy consumption in WSN are EAERP (Khalil and Bara’a 2011), ALEACH (Ali et al. 2008), and LEACH-C (Heinzelman et al. 2002). These protocols are based on the residual energy of the nodes, the cost function, and intra-cluster connections. The simulation results show that the percentage of dead nodes in each round and the first node die (FND) have been improved. Another method proposed is routing based on the genetic algorithm presented by Bari et al. (Bari et al. 2009). This method is a two-tiered wireless sensor network and can improve network lifetime compared with previous methods.

Some researchers have presented methods based on the node density to reduce energy consumption in WSN. One of these methods is the CACP algorithm (Wang et al. 2012a). In this method, better CHs are selected in the high-density regions. The simulation results show a proper improvement in network lifetime compared with the previous similar methods.

Some researchers use combined parameters such as energy, distance, and density of nodes to reduce energy consumption. One of these methods is the EEDCA-MS algorithm (Meddah et al. 2017). It uses a genetic algorithm and re-clustering for decreasing energy consumption. The EEDCA-MS algorithm considers parameters such as energy and distance of the nodes. It can balance the number of clusters in different rounds and reduce the generation number for finding a CH. In the GFCM protocol (He et al. 2012), an energy-balanced clustering algorithm has been proposed. This method uses a GA and fuzzy logic for the formation of clusters. In this protocol, using fuzzy logic is solved the problems of the GA in the election of the best cluster head. In GADA-LEACH (Bhatia et al. 2016), a GA-based distance-aware routing protocol for WSNs has been proposed. In this method, the CH uses a genetic algorithm. This protocol reduces the energy consumption by the node relay and running GA. The DV-HOP algorithm (Peng and Li 2015) is another protocol that uses GA. The simulation results show that the DV-HOP protocol has better accuracy compared to previous methods. Song et al. (Song et al. 2015) proposed an energy-efficient algorithm called GAEMW using GA for multi-path routing. Simulation results show that this method has stability. One of the new methods proposed to optimize energy consumption in wireless sensor networks is metaheuristic algorithms (Abualigah et al. 2021a, b, 2022). Metaheuristic algorithms are widely used in optimization problems of various sciences, such as computer science, artificial intelligence, engineering, and management. One of the main applications of metaheuristic algorithms is combination optimization and NP-hard problems. One of the metaheuristic approaches is the distributed guidance anti-flocking algorithm (DGAA) (Wang et al. 2021). The DGAA improves the performance of mobile sensor nodes and guarantees maximum profit by imitating the behavior of predators. Another metaheuristic method is the algorithm proposed by Wang et al. They solved the problem of dynamic deployment in WSN using a binary detection model (Wang et al. 2012b).

In Sixu et al. (2022), the authors have presented a particle swarm optimization-based cluster routing algorithm. In this method, artificial bee colony algorithm-based traversal path algorithm is used to design the move path of the base station. In the E-FUCA protocol (Mehra 2022), an unequal clustering method based on fuzzy logic is provided where vital parameters are considered during CH candidate selection, and intelligent decision using fuzzy logic is taken by common nodes during the selection of their cluster head for the formation of clusters.

3 Genetic Algorithm and Network Model

Nowadays, genetic algorithms are popular. An proper application of the genetic algorithm is finding solutions for optimizing (Khalil and A. A. Bara’a, 2011; Meddah et al. 2017; Bhatia et al. 2016; Sabet and Naji 2015). Genetic algorithms work with a population of selected solutions instead of one solution. Each solution is shown with 0 and 1 (or binary values). Binary values describe problem characteristics (Khalil and Bara’a 2011; Bari et al. 2009). If the input of GA is correctly determined, then finding the answer will be very easy; otherwise, the solution will be a difficult process. Generally, the main idea of a genetic algorithm is to select the best routes and merge them in the best way to obtain optimal points. In the genetic algorithm, the function to maximize the process is called the fitness function (Haupt and Ellen Haupt 2004). The genetic algorithm encodes a set of input data and problem parameters in n-line strings. All the solution processes will proceed with these codes. The simplest kind of coding in the genetic algorithm is binary coding, in which strings are coded as 0 and 1. The combination of different solutions for a problem creates a population. Therefore, the population that has m unique features will have m-bit binary strings (or chromosomes) (Bari et al. 2009; Bhatia et al. 2016; Sabet and Naji 2015; Haupt and Ellen Haupt 2004). Chromosomes showed with 0 and 1 are genes. They belong to the fitness function and are defined as the collection of problem input variables. Genetic operators result in a change in the answers. Selection, combination, and mutation are the three main operators in genetic algorithms. The selection operator elects a pair of chromosomes with higher fitness in comparison with another chromosome. This work performs to produce new children. The selection process is random, because some selections may not be in an optimum generation, but in the next generations result in an optimum generation. The common methods of selection are as follows:

Roulette wheel selection, sequential selection, Boltzmann selection, comparative selection, brindle definitive selection, head selection, selection of steady state, selection of elite democracy, select to replace generation modified, competition selection, and selection random match.

The combination is a process in which the previous generations combine to create a new generation of the chromosome. In this stage, two chromosomes selected in the previous stage combine to produce new children. The most common methods of combination are single-point combination, two-point combination, n-point combination, uniform combination, account combination, discipline, cycle, convex, and section written.

Mutation causes search in untouched space of the problem. The mutation is for search in the untouched space of the problem. The most important part of mutation is not to obtain a local minimum (partial optimization). In GA after the creation of a member in the new collection, every gene mute with a probability of mutation (Pm). The probability Pm is used for mutation. It is determined by the user (Haupt and Ellen Haupt 2004; Yussof et al. 2009). The standard level of the Pm is usually low (between 0 and 1). If the amounts allocated to genes are less than their Pm, the genes are mutated. In mutation, a gene may be deleted or added from population genes. The mutation changes a gene. Different methods of mutation are used based on the type of coding. The different types of mutation are binary mutation, real mutation, bit inversion mutation, change of used mutation, inversion mutation, and change of value mutation. The following criteria are used to stop the genetic algorithm (Sabet and Naji 2015; Hussain et al. 2007):

• Fixed generations after a few rounds.

• The fitness value cannot improve after several generations.

• The highest degree of fitness be obtained for each child.

• A combination of the above-mentioned cases.

Code 1 shows the pseudo-code of genetic algorithm.

figure a

3.1 The Network Model

We consider some assumptions to simplify the network model:

  1. 1.

    Nodes are randomly distributed in a square n*n.

  2. 2.

    Nodes are aware of the BS and their position.

  3. 3.

    The initial energy of nodes is random.

  4. 4.

    All nodes have identification (ID) and the BS is outside of the nodes' distribution field.

  5. 5.

    Nodes cannot be deleted or added after the establishment.

  6. 6.

    Nodes need hardware like GPS or positioning algorithm to aware of the other positions.

We have also used the Heinzelman model for energy (Heinzelman et al. 2002). According to the model, to transmit an n-bit message over a distance d, energy consumption is defined as follows:

$$\begin{gathered} E_{1} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{fs} d^{2} } \right)\quad d < d_{c} \hfill \\ E_{2} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{mp} d^{4} } \right)\quad d \ge d_{c} \hfill \\ \end{gathered}$$
(2)

The necessary energy to receive m-bit message from distance d is defined as follows:

$$E_{3} \left( n \right) = mE_{{{\text{elect}}}}$$
(3)

where \(E_{{{\text{elect}}}}\), \(\varepsilon_{fs}\), and \(\varepsilon_{mp}\) are based on the physical distance between sender and receiver, the shape of noise, modulation and transfer manner (multi-hop or single-hop), multi-path fading, and free space propagation. \(d_{c}\) is crossover distance between sender and receiver. Crossover distance (\(d_{c}\)) is equal to:

$$d_{c} = \sqrt {\frac{{\varepsilon_{fs} }}{{\varepsilon_{mp} }}}$$
(4)

4 The NEECH Protocol

The NEECH algorithm consists of two stages. In the first stage, CHs are determined, and in the second stage, data are transmitted. In the following, we describe both steps in detail.

4.1 First Stage: Find the Best CH via GA

This stage is called setup in which nodes are divided into separate areas called the grid. Then the gravity center and the mass center are calculated for each grid. If the center of gravity is nearer to the BS, then the nearest node to the BS is selected as the probable CH. If the mass center is nearer to the BS, then the node with more energy is selected as the probable CH. Finally, selected nodes are used in GA for selecting the best CH.

One of the main bases of distributed powers is replacing these powers with a balanced power called F. This power is enforced to a single point. This point is often called the gravity center. For example, the gravity center on the symmetrical metal sheet differs from the asymmetrical. Generally, the gravity centers for the symmetrical geometrical shapes such as circles, rectangles, and triangles are different from asymmetrical. If in the process of calculating the gravity center, the mass of the point be considered and points do not have equal mass, a point called mass center is gained. This point will be near to a point with a higher mass or weight. In engineering, shapes without a uniform density are called lamina. We suppose these shapes are bounded by x = a, x = b, \(y=f\left(x\right),\) and \(y=g\left(x\right)\) with g(x) <  = f(x). If (\(\overline{x }\),\(\overline{y }\)) is the coordinates of mass center, then:

$$\begin{gathered} \overline{x} = \frac{{\mathop \smallint \nolimits_{a}^{b} x\left( {f\left( x \right) - g\left( x \right)} \right)dx}}{{\mathop \smallint \nolimits_{a}^{b} f\left( x \right) - g\left( x \right)}} \hfill \\ \overline{y} = \frac{1}{2}\frac{{\mathop \smallint \nolimits_{a}^{b} (f\left( x \right)^{2} - g\left( x \right)^{2} )dx}}{{\mathop \smallint \nolimits_{a}^{b} f\left( x \right) - g\left( x \right)}} \hfill \\ \end{gathered}$$
(5)

Therefore, on the level that has n nodes and the nodes have masses m1, m2… mi, the center of mass is defined as follows:

$$\left\{ {\begin{array}{*{20}c} { \left( { \mathop \sum \limits_{i = 1}^{n} m_{i} } \right)\overline{x} = \mathop \sum \limits_{i = 1}^{n} m_{i} \overline{{x_{i} }} } \\ {\left( {\mathop \sum \limits_{{{\text{i}} = 1}}^{{\text{n}}} {\text{m}}_{{\text{i}}} } \right){\overline{\text{y}}} = \mathop \sum \limits_{{{\text{i}} = 1}}^{{\text{n}}} {\text{m}}_{{\text{i}}} \overline{{{\text{y}}_{{\text{i}}} }} } \\ \end{array} } \right.$$
(6)

To calculate the center of mass or gravity center of non-uniform geometric shapes, we must arrange non-uniform geometric shapes based on uniform ones such as rectangle or triangle; i.e., we must first analyze non-uniform geometric shapes into uniform ones. Therefore, we divide the interval [a, b] into n subintervals:

$$a = x_{0} < x_{1} < \ldots < x_{n} = b$$
(7)

In the NEECH algorithm, the initial grids are rectangles. So, if f (xi*) is the upper corner coordinates and g(xi*) is the down corner coordinates of the rectangle (xi* is the central point of the rectangle), then the length and height of the rectangle are determined as follows:

$$\begin{gathered} \Delta x_{i} = x_{i} - x_{i - 1} \hfill \\ {\text{h}}\left( {{\text{x}}_{i}^{*} } \right) = {\text{f}}\left( {{\text{x}}_{i}^{*} } \right) - {\text{g}}\left( {{\text{x}}_{i}^{*} } \right) \hfill \\ \end{gathered}$$
(8)

where we assume that surface density is 1 because the nodes have a uniform distribution. Therefore, if we have n nodes with masses of mi, and (\(\overline{x }\) i,\(\overline{y }\) i) is the coordinates of mass centers, then:

$$m_{i} = (f\left( {x_{i}^{*} } \right) - \left( {g\left( {x_{i}^{*} } \right)} \right)\Delta x_{i}$$
(9)
$$\overline{x} = x_{i}^{*}$$
(10)
$$\overline{{y_{i} }} = \frac{1}{2}\left( {f\left( {x_{i}^{*} } \right) - g\left( {x_{i}^{*} } \right)} \right)$$
(11)
$$\mathop \sum \limits_{i = 1}^{n} m_{i} = \mathop \sum \limits_{i = 1}^{n} \left( {f\left( {x_{i}^{*} } \right) - g\left( {x_{i}^{*} } \right)} \right)\Delta x$$
(12)
$$\mathop \sum \limits_{i = 1}^{n} m_{i} \overline{{x_{i} }} = \mathop \sum \limits_{i = 1}^{n} x_{i}^{*} \left( {f\left( {x_{i}^{*} } \right) - g\left( {x_{i}^{*} } \right)} \right)\Delta x$$
(13)
$$\mathop \sum \limits_{i = 1}^{n} m_{i} \overline{{y_{i} }} = \mathop \sum \limits_{i = 1}^{n} 1/2\left( {f\left( {x_{i}^{*} } \right)} \right) + g\left( {x_{i}^{*} } \right)\left( {f\left( {x_{i}^{*} } \right) - g\left( {x_{i}^{*} } \right)} \right)\Delta x_{i}$$
(14)

For example, we assume the distribution of nodes in one grid to be as Fig. 1.

Fig. 1
figure 1

Random distribution of nodes in a grid and calculation of their centers of gravity and mass based on two-dimensional coordinates

Full size image

In Fig. 1, the coordinates of mass center are:

$$\overline{x}_{m} = \frac{{m_{1} \left( {X_{{x_{i}^{*} }} - x_{{m_{1} }} } \right) + m_{2} \left( {x_{{m_{2} }} - X_{{x_{i}^{*} }} } \right) + m_{3} \left( {X_{{x_{i}^{*} }} - x_{{m_{3} }} } \right) + m_{4} \left( {X_{{x_{i}^{*} }} - x_{{m_{4} }} } \right) + m_{5} \left( {x_{{m_{5} }} - X_{{x_{i}^{*} }} } \right)}}{{m_{1} + m_{2} + m_{3} + m_{4} + m_{5} }}$$
$$\overline{y}_{m} = \frac{{m_{1} \left( {y_{{m_{1} }} - y_{{x_{i}^{*} }} } \right) + m_{2} \left( {y_{{m_{2} }} - y_{{x_{i}^{*} }} } \right) + m_{3} \left( {y_{{x_{i}^{*} }} - x_{{m_{3} }} } \right) + m_{4} \left( {y_{{x_{i}^{*} }} - x_{{m_{4} }} } \right) + m_{5} \left( {y_{{m_{5} }} - y_{{x_{i}^{*} }} } \right)}}{{m_{1} + m_{2} + m_{3} + m_{4} + m_{5} }}$$

To calculate the coordinates of the gravity center, we consider the weight of all nodes equal to 1. Therefore:

$$m_{1} = m_{2} = m_{3} = m_{4} = m_{5} = 1$$

With this assumption, the coordinates of gravity center in the nodes of Fig. 1 are defined as follows:

$$\overline{x}_{g} = \frac{{\left( {X_{{x_{i}^{*} }} - x_{{m_{1} }} } \right) + \left( {x_{{m_{2} }} - X_{{x_{i}^{*} }} } \right) + m_{3} \left( {X_{{x_{i}^{*} }} - x_{{m_{3} }} } \right) + \left( {X_{{x_{i}^{*} }} - x_{{m_{4} }} } \right) + \left( {x_{{m_{5} }} - X_{{x_{i}^{*} }} } \right)}}{5}$$
$$\overline{y}_{g} = \frac{{\left( {y_{{m_{1} }} - y_{{x_{i}^{*} }} } \right) + \left( {y_{{m_{2} }} - y_{{x_{i}^{*} }} } \right) + \left( {y_{{x_{i}^{*} }} - x_{{m_{3} }} } \right) + \left( {y_{{x_{i}^{*} }} - x_{{m_{4} }} } \right) + \left( {y_{{m_{5} }} - y_{{x_{i}^{*} }} } \right)}}{5}$$

Generally, for an environment with n nodes, the coordinates of gravity center and mass center are defined as follows:

$$\overline{x}_{{{\text{mass}}}} = \frac{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} \left( {f\left( {x_{i} } \right) - g\left( {x_{i} } \right)} \right)}}{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} }}$$
(15)
$$\overline{y}_{{{\text{mass}}}} = \frac{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} \left( {f\left( {y_{i} } \right) - g\left( {y_{i} } \right)} \right)}}{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} }}$$
(16)
$$\overline{x}_{{{\text{gravity}}}} = \frac{{\mathop \sum \nolimits_{i = 1}^{n} \left( {f\left( {x_{i} } \right) - g\left( {x_{i} } \right)} \right)}}{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} }}$$
(17)
$$\overline{y}_{{{\text{gravity}}}} = \frac{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} \left( {f\left( {x_{i} } \right) - g\left( {y_{i} } \right)} \right)}}{{\mathop \sum \nolimits_{i = 1}^{n} m_{i} }}$$
(18)

Code 2 shows the pseudo-code of mass and gravity centers calculation in the NEECH.

figure b

Code 3 shows the pseudo-code of the NEECH for the selection of probable CHs. The selection process of probable CHs is calculated as code 3.

figure c

In each grid, the gravity center closer to the BS is selected as the probable CH; otherwise, the node with higher energy is selected as the probable CH.

4.2 Calculation and Selection of the Best CH via GA

After the selection of probable CHs, the genetic algorithm selects the best CH. We have used competition selection in the proposed method. The chromosomes are the probable CHs of the previous stage and coded as 0 and 1. For example, if we have 10 grids and two nodes can be selected from each grid as the gravity center and mass center, then the chromosomes of the GA will be twenty bits. The random selection method elects some members of the population randomly. It selects the best members as the parent. The stages of competition selection in GA are as follows:

  1. 1)

    Two members are selected randomly.

  2. 2)

    The amount of r is selected randomly between 0 and 1.

  3. 3)

    The parameter k \(\left( {0 \le K \le 1} \right)\) is determined by the user.

  4. 4)

    If \(k \le r\), the best member, and if K < r, the worst member is selected as parents.

  5. 5)

    The two selected members are sent to the end of the population. Finally, they compete and can take part in the competition process once again.

To combine the selected chromosomes and formed children, we use the uniform combination. In this method, each grid of the chromosome is selected separately. Each gene depending on its situation is selected from the parents randomly, for example, the first gene from the second parent, the second gene from the second parent, the second gene from the third parent, and so on.

We adopt the uniform combination because the new population formed from a uniform combination has more genetic diversity compared with a child produced from one-point and two-point combinations. Therefore, the combination is more effective in a population with a few members because may below the number of grids and chromosome bits. Figure 2 shows the uniform combination for 7-bit chromosomes.

Fig. 2
figure 2

Uniform combination in NEECH protocol. Parent and children show the initial state of the chromosome and their final state after the combination and formation of new children, respectively

Full size image

We have also used the inversion mutation. In this method, a bit that has mutation conditions is modified. In other words, if the bit value is equal to one, then it is converted to zero, and vice versa. Figure 3 shows the inversion mutation of the bit.

Fig. 3
figure 3

Inversion mutation in NEECH protocol

Full size image

After certain generations of GA are performed, the bits of the final chromosome are checked. If a bit equals 1, the corresponding node to its chromosome will be deterministic CH. Code 4 indicates the main pseudo-code of the proposed algorithm.

figure d

Finally, after the determination of cluster heads, the clustering process is performed by the C-means algorithm.

4.3 The Second Stage of the NEECH

This stage is called the steady phase. In the steady phase, data are transferred based on the selection of CHs in the previous phase. In the steady phase, two steps are depending on the type of transmission.

In the NEECH, the CH gathers data from its surrounding nodes and sends it to the BS directly. With each data transmission, the amount of energy is reduced. The energy of the common nodes is calculated according to the following equation:

$$E_{1} = {\text{Send\_Energy}} = \left\{ {\begin{array}{*{20}c} {E_{1} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{fs} d^{2}_{dis2CH} } \right)\quad d_{dis2CH} < d_{c} } \\ {or} \\ {E_{1} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{mp} d^{4}_{dis2CH} } \right)\quad d_{dis2CH} \ge d_{c} } \\ \end{array} } \right.$$
(19)

The energy required for common nodes to receive data is equal to:

$$E_{2} = E_{{\text{Receive - energy}}} = mE_{{{\text{elect}}}}$$
(20)

According to Eqs. (19) and (20), the total energy for common nodes is defined as follows:

$$E_{{\text{total - common - node}}} = E_{{\text{send - energy}}} + E_{{\text{Receive - energy}}} = E_{1} + E_{2}$$
(21)

Three energies including reception energy from common nodes, the transmission energy to the BS, and aggregation energy (Eqs. 22, 23, and 24) are calculated for cluster heads. Eventually, the sum of three energies (Eq. 25) is considered as the final energy of the CH.

$$E_{1} = {\text{Send\_Energy}} = \left\{ {\begin{array}{*{20}c} {E_{1} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{fs} d^{2}_{dis2CH} } \right)\quad d_{dis2CH} < d_{c} } \\ {or} \\ {E_{1} \left( {n,d} \right) = n\left( {E_{{{\text{elect}}}} + \varepsilon_{mp} d^{4}_{dis2CH} } \right)\quad d_{dis2CH} \ge d_{c} } \\ \end{array} } \right.$$
(22)
$$E_{{\text{Receive - energy}}} = m*E_{{{\text{elect}}}} = E_{2}$$
(23)
$${\text{Aggregation\_energy}} = m*E_{{{\text{aggregation}}}} *\left( {{\text{number}}\;{\text{of}}\;{\text{nodes}}} \right) = E_{3}$$
(24)
$$E_{{\text{total - cluster - head}}} = E_{1} + E_{2} + E_{3}$$
(25)

Code 5 shows the steady and setup phases for single-hop transmission in the NEECH.

In the NEECH when nodes are distributed in large-scale environments the multi-hop fashion is used. In multi-hop transmission, lower-level CHs send their data to higher-level CHs. In other words, two energies (reception and sending data) are calculated for common nodes. But for CHs, four energies are calculated and extracted (including the energy received from the common nodes, the aggregation energy, the energy of sending to the higher-level CH, and the energy of sending to the BS).

figure e

5 Simulation Results

In this section, we evaluate the performance of the protocol with MATLAB. Our analysis parameters are the initial energy of nodes, the number of nodes, the size of the environment, the number of generations, the number of grids, the primary population in the implementation of the GA, and the position of the base station (BS). Table 1 shows the simulation parameters.

Table 1 Simulation parameters
Full size table

To evaluate the performance of the proposed protocol, we compare it with the existing algorithms, namely LEACH, ALEACH, EAERP, LEACH-C, CACP, GADA-LEACH, EEDCA-MS, and GAEMW. Simulation cases are the same for all algorithms. The results are compared with existing protocols based on five metrics: the network lifetime, the first node die (FND) and the last node die (LND), the node density and the selection of probable CHs, the number of generations, the proper balance in choosing the final CHs, and energy consumption of each node.

5.1 Network Lifetime

As mentioned before, the reduction in the energy consumption increases the network lifetime. Figure 4 shows alive nodes after implementing 7000 rounds of the NEECH algorithm with 100 nodes. Also, Fig. 5 shows the previous similar methods with 100 nodes. As Figs. 4 and 5 show, the proposed method have improved network lifetime in comparison with the other methods. The main reason is the minimum energy consumption of the network that occurs in each cluster. In other words, the gravity of the center, the mass center, and the grid structure not only increase the network lifetime but also decrease energy consumption in each cluster head.

Fig. 4
figure 4

Network lifetime in NEECH based on rounds and number of alive nodes

Full size image
Fig. 5
figure 5

Network lifetime in EAERP, LEACH, ALEACH, LEACH-C, GFCM, PACMSD, and EFUCA protocols

Full size image

When the nodes lose their energy later, the network lifetime is longer. As Figs. 4 and 5 indicate, the death time of the first node (FND) has occurred in around 2000. This shows a proper improvement compared with the other methods. Figure 6 shows the FND and LND parameters in the NEECH protocol and the other methods. As Fig. 6 shows, the LND in the NEECH protocol is 68.8% better than LEACH, 81.7% better than ALEACH, 91.7% better than LEACH-C, 83.3% better than GFCM, 33.3% better than EAERP, 83.3% better than CASP, 65% better than GADA-LEACH, 16.7% better than EEDCA-MS, and 91.7% better than GAEMW. Moreover, the FND in the NEECH protocol is 90% better than LEACH, 50% better than ALEACH, 80% better than LEACH-C, 75% better than GFCM, 60% better than EAERP, 95% better than CASP, 10% better than GADA-LEACH, 75% better than EEDCA-MS, and 90% better than GAEMW.

Fig. 6
figure 6

FND and LND in NEECH and similar methods

Full size image

5.2 Node Density and the Selection of Probable CH

The high-density areas are regions in which the number of nodes is more than other regions of the network. The selection of probable CHs in these areas must be more than in other areas. This problem is more salient in uneven areas.

Figure 7 shows the random distribution of nodes in the network. As Fig. 7 shows, some areas have a higher density than other areas. Figures 8 and 9 show the formation of clusters and the selection of probable CHs in an environment with different nodes. As it is clear, the selection of probable CHs to participate in the GA is more in the high-density areas. The most important reason is that in high-density regions more probable CHs can be selected compared to low-density areas. Because of the selection of more CH in high-density areas, the inputs of the genetic algorithm will also be more in high-density areas. Therefore, the genetic algorithm in the NEECH protocol selects more deterministic CHs in high-density areas. As shown in Fig. 8, the probability of the CHs selection is more in high-density regions. This result is also shown in Fig. 9. Therefore, unlike the LEACH and the methods based on it, the NEECH protocol elects the previous nodes in each step of CH selection. The procedure leads to considering the previous CHs with better conditions to be re-selected. More nodes are located in high-density areas. Therefore, more CHs should be selected in high-density areas. The NEECH protocol selects more nodes in high-density areas to participate in the initial population using the metaheuristic approach. Therefore, more CHs are selected in high-density areas. Figures 7, 8, and 9 also prove this result.

Fig. 7
figure 7

Random distribution of nodes and high-density areas with 200 nodes

Full size image
Fig. 8
figure 8

Selection of probable CHs with genetic algorithm

Full size image
Fig. 9
figure 9

Selection of Final CHs in high-density areas

Full size image

5.3 Reduction in the Number of Generations

Reducing generations in the GA leads to a reduction in the operational overhead of the GA. If the number of generations in the GA for finding the best fitness value is low, then the cost of the algorithm is reduced. It means that if the best fitness value is achieved in n generations, there will be no need to run the algorithm again. Figure 10 illustrates the number of generations to find the best fitness value in 50 generations in the NEECH and GAEMW protocols. Figure 10 shows that the best fitness value has been obtained in the 35th generation.

Fig. 10
figure 10

Number of generations and the best fitness value in the NEECH and the GAEMW protocols

Full size image

Table 2 indicates the number of generations to obtain the best fitness value in the NEECH algorithm. As Table 2 shows, the fitness value in 50 generations does not differ from 35 generations. This causes to reduce the cost of the NEECH algorithm. Therefore, the NEECH protocol improves the number of executable generations by 30% compared to similar protocols.

Table 2 Comparison between number of generations and fitness
Full size table

5.4 The Proper Balance in Choosing the Final CHs

The selection of the cluster heads in wireless sensor network depends on factors such as data traffic in each node, residual energy of the node, energy of neighbor nodes, and the distance of nodes within their cluster and other clusters. If the factors are considered simultaneously in the election of the cluster heads, then the selection of the cluster heads will have a proper balance. In addition, the simultaneous consideration of the factors leads to the election of more suitable CHs in the environment. If the initial population in the GA is better, then the formation of the next population will be better. In the NEECH protocol, more nodes are elected to select CHs to form the initial population from high-density areas. Therefore, the proper population leads to the better selection of the final CHs in all areas of the network, especially in high-density areas.

Figure 11 shows the selection of CHs based on gravity and mass centers. As Fig. 11 shows, the selection of final CHs has a proper balance. Another reason for the proper balance in the CH selection is the use of centers of mass and gravity of the nodes. The use of the two parameters leads to the formation of balanced clusters in terms of intra-cluster and inter-cluster distances. By selecting more CHs in high-density areas, the NEECH protocol significantly improves the energy consumption and lifetime of CHs in each cluster. Therefore, the network lifetime is increased. Moreover, the number of executable generations to select CHs is reduced.

Fig. 11
figure 11

Selection of CHs based on gravity center and mass center before running the genetic algorithm

Full size image

5.5 Improving the Energy Consumption of Each Node

In WSN, improving the energy consumption of each node will improve the total energy consumption of the network. In other words, if the energy consumption of single nodes is low, then the total energy consumption of the network will be low. Figure 12 indicates the energy consumption of each node. As shown in Fig. 12, the maximum amount of energy consumption for each node is between 0.2 and 0.6 Jules. In other words, the consumption peak of energy in the cluster is between 0.3 and 0.4 Jules. In other words, the highest energy consumption is related to high-density areas where the number of nodes is high. In a large-scale network, it can be proper because increasing the number of nodes will increase the total energy in the initial setup of the network. Therefore, the low energy consumption per node results in a longer lifetime.

Fig. 12
figure 12

Energy consumption of each node

Full size image

5.6 Validation

The coefficient of determination indicates the correlation between two sets of data. It is compatible with current and past data and shows the power of predicting the dependent variable based on the independent variables. The value of the coefficient of determination is between 0 and 1, and the closer to one is more proper. Usually, a value greater than 0.6 indicates that the independent variables have been able to express the changes of the dependent variable to a large extent. Pearson's correlation coefficient is suitable for normal or high data distribution. Pearson's correlation coefficient is between − 1 and + 1. The value of one indicates a direct or positive relationship between independent and dependent variables and vice versa.

In this section, we evaluate the validity of the NEECH protocol based on the coefficient of determination, Pearson's correlation coefficient, and root mean square error (RMSE). RMSE is a proper tool for comparing prediction errors by a data set.

One of the main features of the NEECH protocol is the selection of more CHs in high-density areas. In addition, if the network size increases, more possible and final CHs will also be selected.

Table 3 shows the number of possible and final CHs in different scenarios. As it is known, as the network size increases, the number of CHs also increases. Figure 13 shows the regression equation with the coefficient of determination for probable and final CHs.

Table 3 Number of possible and final CHs with different network sizes and number of nodes
Full size table
Fig. 13
figure 13

Regression equation and coefficient of determination for probable and final CHs

Full size image

The Pearson coefficient between the number of probable and final CHs, probable CHs and network size, and final CHs and network size is 0.996185, 0.991107, and 0.995435, respectively. Therefore, the selection of final CHs based on probable CHs and the selection of more CHs in high-density areas has more accurate.

As shown in Fig. 13, there is a strong correlation between possible and final CHs. Therefore, the NEECH protocol guarantees that the CHs selected in the setup phase can be selected as the final cluster head with a high probability.

One of the important features of the NEECH protocol is the selection of more CHs in larger networks. Figure 14 shows the regression equation and the coefficient of determination between the number of final CHs selected and the size of the network. As Fig. 14 shows, there is a strong correlation between the number of final CHs selected and the size of the network. Therefore, according to the regression equation, the number of final CHs can be determined in advance. This is one of the most efficient features of the NEECH protocol because in most clustering methods, the number of clusters is manually and statically selected in advance, and then, clustering is performed based on that. In other words, in NEECH, unlike other clustering methods, the number of CHs is specified in advance and will not be by default and will change according to the size of the network.

Fig. 14
figure 14

Regression equation and coefficient of determination for number of final CHs and the size of the network

Full size image

Root mean square error (RMSE) measures how much error there is between two data sets. It compares a predicted value and an observed or known value. The RMSE is calculated as follows:

$${\text{RMSE}} = \sqrt {\frac{{\mathop \sum \nolimits_{i = 1}^{n} \left( {P_{i} - O_{i} } \right)^{2} }}{n}}$$
(26)

where

Pi = predicted value,

Oi = observed value, and

n: number of data set.

The closer RMSE is to 0, the model is more accurate. Based on the data in Table 3 and Eq. (26), the value of RMSE between probable and final CHs is 15.8682. On the other hand, the average number of probable and final CHs is equal to 139.9 and 126.7, respectively. Therefore, the RMSE value is low compared to the average values. Therefore, another reason to prove the accuracy of NEECH protocol in selecting CHs is the low value of RMSE.

Another advantage of the NEECH protocol compared to similar methods is the small number of execution generations for cluster head selection. The low number of generations has a significant effect on reducing overhead. Table 4 shows the number of execution generations to find probable CHs, and Fig. 15 shows the regression equation and the coefficient of determination based on the number of nodes, network size, and the number of execution generations to find probable CHs. As Fig. 15 shows, there is a high correlation between the number of generations of the GA, the size of the network, and the number of nodes.

Table 4 Number of possible CHs with different network sizes and generations
Full size table
Fig. 15
figure 15

Coefficient of determination and regression equations to find the probable CHs based on number of generations in genetic algorithm and network size

Full size image

According to Figs. 14 and 15, the best case of the algorithm execution is O(n) and the worst case is O(n2). Therefore, it can be claimed that the overhead of the NEECH protocol is O(n) in the best case (or linear overhead) and O(n2) in the worst case.

6 Conclusion and Future Works

So far, many metaheuristic methods have been used to optimize wireless sensor networks. The most important of approaches are monarch butterfly optimization (MBO), earthworm optimization algorithm (EWA), elephant herding optimization (EHO), moth search (MS) algorithm, slime mold algorithm (SMA), and Harris hawk’s optimization (HHO). Based on the same methods and metaheuristic approaches, we have proposed a clustering algorithm based on density by using the GA, namely the NEECH protocol. Our presented algorithm is based on the three criteria including residual energy, distance, and density of nodes. In the NEECH protocol, the probable CHs are detected by using gravity and mass centers. Then, deterministic CHs are determined by the genetic algorithm. The simulation results show that the proposed method can improve the network lifetime in comparison with the other methods. We have also shown that the proposed method can select better CHs in high-density areas by reducing the number of generations. In this research, the probable nodes with a higher chance of becoming CH are determined via gravity and mass centers. The selection of probable CHs using the GA reduces the number of generations. Therefore, the genetic algorithm used in the proposed protocol has less complexity compared to other methods. In addition, the selection of cluster centers based on the two factors of the center of gravity and center of mass leads to earlier optimization than similar methods such as MBO and EWA. Performing a fixed number of generations in the NEECH to find the proper population leads to better fitness at a lower cost. However, in similar heuristic methods, more generations must be performed to reach an optimal population.

One of the significant results of the research is improving the network lifetime by improving FND and LND parameters. Our analysis shows that the NEECH protocol has improved the FND parameter by up to 90% compared to LEACH. Furthermore, the LND parameter has improved by 68.8% compared to LEACH.

To validate the NEECH protocol, we have used Pearson's correlation coefficient, regression equations, coefficient of determination, and RMSE error. Our evaluations show that the overhead of the NEECH algorithm in the best case and the worst case is O(n) and O(n2), respectively.

Validation of the NEECH protocol shows that the relationship between the number of execution generations and the selection of probable CHs at the first phase is a second-degree equation. In addition, the selection of final CHs based on possible CHs, network size, and the number of nodes in the second phase is a linear equation. Therefore, by implementing the NEECH protocol in the clustering (or second phase), the overhead of the protocol is reduced.

In the future, in addition to wireless sensor networks, the NEECH protocol can also be used in classification and data mining. Combining the proposed protocol with another metaheuristic approach can reduce the NEECH overhead. In addition, the use of other clustering approaches such as fuzzy clustering with genetic algorithms can select better CHs in high-density areas. Selecting ideal CHs in high-density areas or using them alternately can also increase the lifetime of nodes. The approach leads to less complexity in CH selection and increases network life.