Energy-Aware Clustering and Efficient Cluster Head Selection

One of the most significant functions of WSNs is gathering data from the environment for a long duration. The sensor nodes are randomly deployed in the monitoring area to measure physical quantities such as temperature, pressure and vibration. The captured information is transmitted to collection stations called base stations (BSs) (Agarwal et al., 2016). The energy required for communication in the networks is an important challenge because the sensor nodes are equipped with batteries that are not generally rechargeable, when the battery of node dies a node is no longer useful (Sheta and Solaiman, 2015). Implying a smart routing protocol to efficiently utilize the battery resource can contribute in prolong the network lifetime. This is the reason why researchers are now days developing new routing algorithms for WSNs to save energy and improve QoS parameters like network lifetime, delay, and throughput. Some of the protocols use a clustering approach, the technique of clustering enables to dividing the sensor nodes in the network into several clusters. After clustering nodes, the later receive information from the environment and sends it to one of the nodes in that cluster called cluster head (CH). After receiving the information of all nodes that are members of the cluster, CH aggregates and compress this information and sends it to the BS. The existence of a CH reduces the number of communications on the network, thus reducing power consumption, and extending the lifetime of the WSNs (Jafarizadeh et al., 2017). One of the most important problems in clustering is to improve cluster structure and optimize the selection of CHs. To solve this problem, several methods have been used among these methods that are interested in CH selection based on energy or distance to the BS regardless of the clustering method, and other methods its main purpose is to provide a clustering algorithm, but next to this clustering algorithm, a procedure is presented for election the CH which is not optimal in most cases. To solve the above problems, a Clustering technique namely EAC-ECHS (Energy-Aware Clustering and Efficient Cluster Head Selection) is proposed in this paper to obtain the best routing for improved network performance. EAC-ECHS is based on two steps: the first step of clustering, aiming to create homogeneous clusters by dividing the network into fixed Grids. each grid is a cluster, this technique minimizes the transmission distance between the source and destination and extend the period of stability. The second step is selecting the optimal CH for each cluster, indeed the distance to the BS, the residual energy of the node, and the distance to the neighbors are taken into consideration in our new technique which plays an important role in energy consumption. The following sections organize the remainder of this paper. Some routing protocols based on the clustering algorithms are described in the section “Literature Survey”. A new clustering based routing approach to improve the performances of WSNs in terms of energy and QoS metrics is described in “Motivations” section. Section “Proposed technique: EAC-ECHS” gives more details about the algorithm proposed for cluster formation, CH selection, and data transmission. Section “Experimental results” is assigned to the explanation of simulating the proposed method compared to other routing techniques in terms of the residual energy, network lifetime, and throughput. Finally, the conclusions and futures works are discussed.

The limitation in the energy resources of nodes is the main challenging issue in the process of developing routing protocols for the WSNs (Wang et al., 2018, 2019). Moreover, the WSNs are partitioned into homogeneous and heterogeneous networks. In the homogeneous networks, all nodes are initially supplied with the same energy levels. Whereas, in the heterogeneous networks, different residual energy is assigned to the nodes. Several hierarchical clustering routing protocols have been proposed to efficiently collect the data with less resource consumption, maximizing the network lifetime (Khan and Samad, 2017; Praveen Kumar et al., 2019) for homogeneous and heterogeneous networks. As mentioned in the previous section, the objective of the algorithms is clustering and select a CH node for each cluster. In this section, we present algorithms that have the same objective.

The most famous of these algorithms in the field is the LEACH (Low Energy Adaptive Clustering Hierarchy) (Heinzelman et al., 2002). It is a hierarchical routing protocol with two layers, CHs layer and member layer. This can be clearly illustrated in Figure 1 which shows the architecture of the standard LEACH Protocol.

Figure 1:

During the first setup phase, each node creates a random number between 0 and 1. If the random number is smaller than the threshold value, then the node becomes a CH for current round. Every node uses the stochastic algorithm to find out the CH. The threshold value is calculated based on the following equation: (1)T(n)={P1‒P×(rmod1p)sin∈G0sinonwhere r is the current round, p is the expected number of CHs which is described initially, G is the ensemble of nodes which are eligible for CHs selection, and mod(r,1p) presents the modulus after the division of r by 1p. The data forwarded to the BS by its CHs.

Singh et al. (2014) proposes a routing technique based on LEACH. The clusters are refreshed periodically based on the distance and residual energy. To improve the network lifetime the technique distributes the work between different nodes by rotating the CH. The sensor nodes remain in the active state during transmission; however, they intentionally remain dormant to save energy throughout the rest of the time.

Lu et al. (2014) proposes a heuristic algorithm to find the quasi-optimal solution in polynomial time to design a tree structure subject to multiple objectives, called Multi-Objective Steiner Tree Problem (MOSTP). The algorithm based on the optimization of swarms of jump particles with a special double layer coding scheme and other necessary components are used to develop the proposed method.

Lu et al. (2016) this document proposes an adaptive data aggregation protocol with probabilistic routing for the collection of periodic event data. The main idea is to encourage nodes to use an optimal routing structure for data aggregation with certain probabilities. The optimal routing structure is defined as a Multi-Objective Steiner Tree, which can be explored and exploited by the ant colony Optimization and Genetic Algorithm hybrid approach. The probabilistic routing decision guarantees the adaptability of some transformations of the topology. By using the prediction model based on the sliding window for future arriving packets, the adaptive timing policy can reduce the transmission delay and can enhance the aggregation probability. Therefore, the packet transmission converges from both spatial and temporal aspects for the data aggregation.

Latif et al. (2016) presented a new algorithm named DDR to minimize energy consumption in WSN based on static clustering. The technique divides the network area into different segments. Each segment as a cluster, the CH of the clusters is selected based on residual energy.

Alami and Najid (2017) presents a technique for hierarchical routing protocols to enhance energy efficiency in WSNs, namely LEACH-G5. This technique divides the network area into the inner Grid and clustered Grids. In an inner Grid, the nodes directly transmit the data to the BS; whereas, in the clustered Grid, the nodes are organized into micro-Grids and thus each node transmits the data to the BS through its respective CH.

El Alami and Najid (2019) proposes a new clustering hierarchy (ECH) approach to achieving energy efficiency in WSNs by using a sleeping-waking mechanism for overlapping and neighboring nodes. In this way, data redundancy is minimized, and network lifetime is maximized. In contrast to previous hierarchical routing protocols where all nodes are required for data collection and transmission, the proposed approach only requires the waking nodes to do these tasks, which are keys to energy consumption in WSNs.

Wang et al. (2019) the authors of this paper, present an affinity propagation-based self-adaptive (APSA) clustering method to achieve more reasonable clustering performance. The affinity propagation (AP) (Sohn et al., 2016) and the K-medoids are combined for better clustering. AP algorithm is commonly used to calculate the similarity between different nodes in this paper is used to calculate the initial cluster centers and the optimal number of clusters. Then K-medoids is adopted to form the final clustering results by iteration based on the initial cluster centers by considering the residual energy.

Jain and Mohapatra (2019a) this paper presents a routing algorithm which preserve coverage of the network as well reduce energy consumption that leads to increased network lifetime. Jain and Mohapatra (2019b) presented comparison study of the algorithms of Cluster Head selection.

The authors (Khushboo and Anoop, 2020) present an algorithm for the optimal selection of CH to improved network lifetime and achieve energy efficiency based on residual energy levels and distance. For initial CHs selection and Cluster formation, all SN will communicate with the BS. then the BS chooses the initial CH, which reduces the energy level in the network. when the residual energy of the present CH drops to 40% of its initial energy is not having sufficient energy to perform the work of the CH and an instantaneous switching requires extending the lifetime of WSNs.

These algorithms have many improvements in the efficiency of energy in a certain extent. Within the lifetime of networks, based on the shortcomings of LEACH.

Other distinctive routing protocols in WSNs include (Jain et al., 2018; Ray and De, 2016; Wang et al., 2018), uses energy for choosing the CH, the information about the nodes positions and energy are obtained by exchanging messages by every node among themselves. That each node is frequently repeated several times elected cluster-head and formed the cluster consumed some energy. Differently, another routing protocols using fuzzy logic for clustering and choosing the CH in each cluster (Alami and Najid, 2016; El Alami and Najid, 2015; Gharajeh and Khanmohammadi, 2016; Hassan El Alami and Najid, 2015; Logambigai and Kannan, 2016; Neamatollahi et al., 2017) but not taking into consideration all the parameters that influence energy consumption. The clustering algorithms described in the section consider many important parameters for clustering or for choosing the optimal CH like proximity among the sensors nodes (SNs), location of BS, residual energy of the sensor’s nodes, and type of SNs for the heterogeneous network. In this work, we have developed a technique to conceive a strong WSNs clustering algorithm that generates equitable, energy-aware, and stable clusters. Thus, this work represents an improvement of our previous contributions presented in (El Idrissi et al., 2020). The EAC-ECHS is a technique of clustering and then choosing the optimal CH selection which reduces energy consumption, and it is unnecessary to form the cluster after every round because that consumed some energy. The algorithm is simulated on MATLAB to validate the improvement in terms of energy, packet delivery ratio, and network lifetime.

Clustering techniques are widely applied to improve network performance during the routing phase for WSNs. The most important issues regarding clustering, in WSNs, are to improve cluster structure, optimize the CHs selection, and energy optimization for data transmission. As discussed in “Literature survey”, several routing techniques based on clustering are proposed. However, these protocols are not as energy efficient as needed. These techniques randomly select the CHs, based on a value that is generate randomly, which lead to not optimum in number of selected CHs and thus leading to quick energy consumption of the CHs belonging to the cluster with dense concentration of nodes as compared to that of the sparse ones. To overcome the drawbacks, we propose a new clustering based routing approach to improve the performances of WSNs in terms of energy and QoS metrics.

The objective of the proposed EAC-ECHS protocol is to reduce energy consumption and optimize the lifetime of the WSN by introducing low overhead, stability, and reliability. The operation of the proposed EAC-ECHS protocol consists of a set of rounds. Each round consists of a setup phase and a transmission phase. A setup phase is done once at the beginning of the first round, in this phase the network area is divided into g Grid G_i to create fixed clusters (Grids) as shown in Figure 2. There are two types of nodes. Member nodes monitor and collect data about their environment of interest and forward these collected data to corresponding CHs including energy levels. CHs node, the type of nodes are two roles, receive the data packages from their members, and conduct data fusion. The fused data is uploaded to the BS by the CHs. CHs nodes not only need to forward these collected data to the BS, but also need to determine the CH for next round based on energy, distance to the BS and proximity of the node. The information received by its members. The following assumption is made to conduct the simulation conveniently.

WSN has homogeneous nodes own the same initial energy and their batteries cannot be changed. Once they exhaust their energy, they will be useless.

Figure 2:

The various existing hierarchical routing protocols use an information aggregation mechanism in the CH to reduce the amount of data transmission. They divide the network into several clusters while the communication time is divided into rounds, each round starts with a set-up phase to organize the clusters and then followed by a longer steady-state phase to transfer the data to the BS as shown in Figure 3. In EAC-ECHS the transmission is repeated in series of rounds, each divided into setup phase (CHs selection) and steady-state phase when data are transmitted from the nodes to CHs and the BS, without repeating the formation of the clusters because the clusters are fixed into Grids. As clearly shown in Figure 4.

Figure 3:

Figure 4:

Grid (Cluster) formation

We consider a network N of 100 nodes are distributed randomly in an area of 100 m*100 m. The BS divides the network area into an inner grid in which the nodes send sensed data directly to the BS, and the cluster grids each grid is known as a cluster. In clustered grids, the nodes organize into grids, with one node is CH of the grid. The data received by the nodes is routed through their CHs to the BS. To find the optimal number of grids the BS made several successive divisions of the network for example in Figures 5, 6, 7.

Figure 5:

Figure 6:

Figure 7:

In Figure 5 the network area is divided into two grids (two clusters) which gives large clusters, so the distance between the nodes and their CH will be long, while the objective of clustering is to minimize the distance, so the area must divide again to have more clusters. Figure 6 shows the division into 4 clusters, and Figure 7 shows the division into 6 clusters, to find the optimal division of this network, we compare the network lifetime for each division. the result is shown in Figure 8.

Figure 8:

where R is the distance from the center of the network area to the boundary of an inner grid. It is the reference distance for forming the grids. the value of R is calculated as follows: (2)R=x4

The simulated results depicted in Figure 8 compare the network lifetime of the different subdivisions of the network by showing the number of dead nodes in the network for each division. when the network is divided into 6 grids, its lifetime is 4000 rounds, we increased the number of grids by dividing the network into 8 grids we notice that the lifetime of the network is decreased. the same thing when we divided the network into 16 grids. so, we stopped the division of network because there may be singleton clusters for example composed of a single node that is the CH. Singletons directly send their data to the BS which can quickly drain the battery.

From the experimental results, it proves that the optimal division of the network is EAC-ECHS-G6 with the surface of grids given as follows: (3)Ginner=4R2(4)Gj=2R2

with G_inner the internal Grid that contains the BS, and G_j a clustered grid.

So, the optimal number of grids is given by equation (5): (5)g=N‒Ginner2R2

with N the network area given as follows: (6)N=x2

The BS divides the network by applying equations (5), Next determining the coordinate of each Grid and broadcast them.

Each node knows its Grid by verification of position such as in equation (7). (7)pni(xni,yni)={xGj‒1<xni<xGj,∀niϵGj,∀i,jϵNyGj−1<yni<yGj,∀niϵGj,∀i,jϵN

with p_ni (x_ni, y_ni) is the position of node i and x_ni, y_ni the coordinates of G_j.

Each sensor node broadcasts its information like id, the id of its Grid, and its position to detect its neighbors in the same Grid, the first packet send by the node is shown in Figure 9. When the information exchange is finished, the nodes in the same Grid calculating the distance local between its neighbors. The node records the information of the neighbors in a table (id, position (x_i, y_i)).

Figure 9:

The pseudo-code of the EAC-ECHS is described as Algorithm 1.

Algorithm 1: Proposed algorithm for grid formation

Input

n_i ∈ N | i = 1,2. . . . n

G_j : Cluster Grid | j = 1,2. . . . g

G_inner: internal grid

BS : Base station

n_i. type = ‘0’

Main

The nodes are randomly distributed in the coverage field

BS broadcast the coordinate of clustered grid and inner grid (equation (3), (4), (5))

n_i received the coordinate of each Grid

for i = 1 to n

n_i check its position

n_i check its Grid

if n_i ∈ G_innerthen

n_i. type = InterNode // n_i marked as an internal node

else

n_i. type = ClusteredNode // n_i marked as a clustered node

end if

n_i broadcast its information (id, Grid id, (x_i, y_i)) to its neighbors

n_i record the information of the neighbors in a table

Output

Network divide into g Grids and internal Grid

Fin

CH selection

In any clustering protocol, selection of CHs is an important step, In EAC-ECHS one CH is selected in each clustered grid, where the nodes in the inner grid send sensed data directly to the BS. After the neighbor's information has been recorded by the nodes. Each sensor node use equation (8) to calculate their probability value to be the best CH just for round 0 and broadcast it with the others in the same grid. The node which has the highest value of chance has turned CH to round 0 and has broadcast a DATA-REQ Message to inform its neighbors to transmit the data and its energy level. Each node has transmitted its data and its energy level to its CH, the latter transmits the data to the BS and determines the CH for the next round by calculating the probability value of each sensor in the same grid used equation (8). Because it contains a table of information of each neighboring node and sends a message to the node that has the highest value to become a CH for the next round. (8)P(ni)=EifCH(ni)E(ni)

which: (9)EifCH(ni)={l⁎ERxTx+l⁎εfs⁎(d(ni))2,d(ni)<d0l⁎ERxTx+l⁎εmp⁎(d(ni))4,d(ni)≥d0(10)d(ni)=ds(ni)+dl(ni)(11)ds(ni)=(xni‒xBS)2+(yni‒yBS)2(12)dl(ni|niϵGk)=∑njϵGk(xni‒xnj)2+(yni‒ynj)2where E_ifCH(n_i) is the energy consumed in the cluster if the node n_i is choosing to be a CH, E(n_i) is the residual energy of node n_i, ds(n_i) and dl(n_i) are the distance to the BS and distance local from neighbors, respectively.

The most preferred CH now will be the node having the maximum residual energy and achieve the lowest energy consumption.

The flowchart of the EAC-ECHS Protocol is depicted in Figure 10.

Figure 10:

Energy dissipation mode

In this work, we use a simple radio model as discussed in (Thangaramya et al., 2019) as shown in Figure 11. Different characteristics of the radio provide different energy dissipation in the transmission and reception modes. The impact of the proposed protocol on this model is presented below.

Figure 11:

In this model, a radio dissipates to operate the transmitter or receiver circuits and for the transmitter amplifier. Radios have power control and can expend the minimum amount of energy necessary to reach the intended recipients. Radios can be turned off to avoid receiving unintentional transmissions. The equations used to calculate the costs of transmitting and receiving an l − bit message in a distance d are shown below: (13)ETx(l,d)={l⁎ERxTx+l⁎εfs⁎d2,d<d0l⁎ERxTx+l⁎εmp⁎d4,d≥d0(14)ERx(l)=l⁎EelecRx

In amplification of signal, energy dissipated is calculated by equation: (15)Eamp={εfs⁎d2,d<d0εmp⁎d4,d≥d0

The first-order radio model was used to model the energy dissipation between two devices. In this model, if the distance between the transmitter and receiver is less than a threshold value d₀, a free space model (d² power loss) is used. If this is not the case, a multipath fading channel model (d⁴ power loss) is adopted. The amount of energy dissipated for the transmission of l data bits at d distance and the reception of l data bits is referred to as (13) and (14) respectively. Moreover, εf_s and εm_p are signal amplification factors of the free space and multipath fading channel models, respectively. d₀ can be calculated by Formula: (16)d0=εfsεmp

In this section, we present the simulation results to evaluate the performance of the proposed approach. Here, the main question we are interested in is how to extend the network lifetime without touching the QoS of the network, using the clustering approach. Therefore, we use the MATLAB simulator to implement EAC-ECHS; and we compare the proposed technique with LEACH, Routing-Gi, OSCH-Gi in terms of remaining energy, network life, and Throughput. The simulation results indicated that our approach is more efficient.

Results and discussions

As shown in the Figure 12, by using our proposed algorithm EAC-ECHS, total energy gets consumed in round 2600. Whereas in LEACH, Routing-G5, and OSCH-G6 the total energy consumed in round 1300, round 2300, round 2300, respectively. The proposed EAC-ECHS approach saves up to 50%, 12% and 12% of energy compared to LEACH, Routing-G5, and OSCHG6, respectively. Indeed, the topology of EAC-ECHS is more stable because we used fixed cluster.

Figure 12:

From Figure 13, it can be observed that the LND of Routing-G5 found to be in round 2700 but the LND of EAC-ECHS found in round 2600 that do not mean than the Routing-G5 is the best because the EAC-ECHS algorithm takes more rounds for FND and HND compared to the LEACH, RoutingG5, and OSCH-G6 techniques.

Figure 13:

We find that EAC-ECHS is higher than the other throughout the operation of WSN. It is clear from Figure 14 that due to enhanced network lifetime. In EAC-ECHS approach the lifetime of the nodes is longer with respect to the protocols LEACH, Routing-G5, and OSCH-G6.

Figure 14:

To make the results clearer Figure 15 shows the percentage improvement of lifetime of the nodes according to FND, HND, and LND of the different algorithms compared to LEACH.

Figure 15:

The trend of number of packets received per round by the BS and the CHs shown in Figures 16 and 17 for different algorithms. From the simulated results we can observe that the proposed routing technique provides a higher rate than LEACH, Routing-G5, and OSCH-G6. This is basically due to the appropriate use of distance and residual energy by the CHs in the proposed protocol.

Figure 16:

Figure 17:

In this paper, a new routing approach, namely EAC ECHS, has been proposed for achieving better energy efficiency, network lifetime, and packets loss while considering the CHs selection process. EAC ECHS approach considered the minimal distance to BS, minimal distance local, and higher residual energy as parameters to select the CHs. Compared to existing approaches, EAC ECHS to further optimize the performances of WSNs. To compare our approach with some previous approaches, we carried out extensive simulations on the energy consumption and QoS of different procedures. The simulation results showed that EAC ECHS was more efficient than the previous approaches simulated in terms of energy consumption, network lifetime, and throughput. However, one limitation of proposed approach is that the number of grids is not optimal because of the division of network based on dimension geography.

Therefore, in our future work, we will use of new trust mechanisms such as machine learning algorithms for obtaining the number optimal of grids and then improving the performance of hierarchical routing protocol in WSNs.