K-Means Efficient Energy Routing Protocol for Maximizing Vitality of WSNs

Abstract

The progress of wireless communication and microelectronics create wireless sensor network, which is a very important field of research, The utilization of Wireless Sensor Network is growing and have a diversity applications like Military applications, Agriculture, Health care, Medical monitoring. The main issue of WSN is energy consumption, where prolonged network lifetime, is important necessity. From the solution proposed the Clustering with k-means is a successful technique for achieving these goals. This work is adaptation of one of the most famous protocol in WSN witch is Low Energy Adaptive Clustering Hierarchy (LEACH) in the clustering phase where the choice of number of clusters and their CHs.sing the k-means method and the distance between nodes and residual energy. Clustering k-means given a best partition with cluster separation. This chapter regulated as below, in section two we discussed related work used k-means to improved vitality of WSN. In the next section, we introduce the proposed adaptation protocol. The simulation resultsusing MATLAB have shown that the proposed protocol outperforms LEACH protocol and optimizes the nodes energy and thenetwork lifetime.

1. Introduction

Wireless Sensors Network (WSN) is composed of vast number of sensor nodes for sensing data. Nodes are deployed densely either in (WSN) itself, or somewhere near to it [1]. Although the sensors nodes are low in cost, they have limited energy [2].

Figure 1 below displays Wireless Sensor Network architecture.

Figure 1.

A wireless sensors network architecture [3].

“Clustering” is technique very efficient to prolong lifetime of network, by reducing energy consumption. Clusters are easy to manage as compared to large whole network. In this chapter we propose a new routing protocol based of K-Means mechanisms in phase of clustering and used the same transmission principe of Low Energy Adaptive Clustering Hierarchy (LEACH) protocol in each cluster. Cluster Head (CH) is elected the node having the higher residual energy and minimum distances from k-means of each cluster.

2. Related work

2.1 The routing protocol low energy adaptive clustering hierarchy (LEACH)

Low Energy Adaptive Clustering Hierarchy LEACH is considered to be the first cluster-based hierarchical routing protocol proposed by Heinzelman et al. As one of the most popular hierarchical routing algorithms for wireless sensor networks [4]. The LEACH protocol assumes equal residual energy from the sensor when starting the network. The life of the network is then divided into towers by a choice of CH. However, each cycle consists of two phases: an initialization phase and a transmission phase (Figure 2 below displays LEACH cluster formation).

Figure 2.

LEACH cluster formation [5].

2.2 Clustering with K-means

We distinguish several types of clustering techniques: The most used are Partitioning, Hierarchical, Density and Grid based. These algorithms try to decompose the set of nodes into a number of disjoint clusters. The problem is how to select the Cluster Head (CH) and how to manage the clusters. There are many methods of partitioning clustering. The most famous ones are: Fuzzy C-Means, K-means, K-medoids and Partitioning Around Medoids (PAM). The authors [6] surveyed and summarized all the partitioned clustering protocols in WSNs. The next table (Table 1) examined a list of routing protocols in wireless sensor networks (WSNs) that uses partitioning clustering with the “K-MEANS” method.

Ref	Characteristics	Intra-cluster	inter–cluster	CH choice	Compared with	Advantages
[7]	k-means used to implement an optimal number of clusters.	One -hop	One -hop	Nœud près du centre de gravité	Clustering traditionnel	Evolving. Optimal number of clusters. Increased network life.
[8]	KPSO/KGA	One -hop	One -hop	K-means/Distance euclidienne	k-means	Reduces energy consumption. Optimal number of clusters. Increased network life.
[9]	Unique node IDrefers to the Euclidian distance between nodes and center of gravity.	One -hop	One -hop	Midpoint algorithm mathematical format	k-means	More efficient and correct than k-Means for large clusters.
[10]	Combined (K means, Davies Bouldin Index, Gaussian elimination)	multi -hop	One -hop	Euclidian distance residual energy	/	Better performance.
[11]	EBRP	One -hop	One -hop	K-means++ Euclidian Distance	k-means	Better than k-Means for large clusters.
[12]	Algorithm genetic	One -hop	One -hop	K-means/Euclidian Distance	GA	Optimal solution.

Table 1.

The different routing protocol uses k-means in WSNs [3].

The K-MEANS algorithm is presented as one of the simplest non-supervised learning algorithms that solve clustering problems, developed by J.B.Mac Queen in 1967. In this method we assign a point in each group where the center of this group is closest (centroids). The center is the average of all the points of the group and its coordinates are the arithmetic average of each dimension, together with all the points of the group, which means that each cluster is represented by its center of gravity. Figure 3 below shows the flowchart of K-means algorithm.

Figure 3.

Flowcharts of K-means algorithm.

3. Proposed system

Our protocol is an adaptation of Low Energy Adaptive Clustering Hierarchy (LEACH) protocol that offers an improvement in the clustering procedure.

In our adaptation the random clustering of LEACH will be changed with the K-means clustering algorithm. This adaptation have been improve the clustering allocation and cluster features and generate energy efficient clustering to increase the life of WSNs.

The use of the K-means algorithm as a clustering technique for cluster formation ensures perfect clustering and reduces overheads when the CHs reelection.

This section presents the configuration of the proposed LEACH protocol adaptation, which consists of two phases: the initialization phase and the transmission phase. Figure 4 illustrates the two phases of proposed adaptation.

1. The initialization phase: nodes are randomly distributed in the network area, after the clustering process with the K-means method begins, the choice of k-CH is made in this phase using the maximum energy and the minimum distance from k-means distance to choose the CH of each cluster.

2. The transmission phase: the nodes of each cluster begins sending collected data to their own cluster head CH, after some iteration, (if the CH energy of cluster <=Min Energy), a CH update procedure will begin among the alive nodes belongs to the cluster using the same parameters of choice new CH(Min distance and Max energy) as the beginning in the initialization phase.

Figure 4.

The two phases of the proposed adaptation.

Figure 5 below illustrates the flowchart of operation of the proposed adaptation.

Figure 5.

The proposed adaptation using clustering with k-means method.

4. Experiments and performance evaluation

4.1 Sensor nodes deployment

For example, 100 sensor nodes are randomly deployed over a 100 m² area of interest. The SB is positioned at the coordinates (50 m, 200 m). Initially, there is no CH, so the nodes are all normal type. The Table 2 shows simulation setting.

Parameter	Value
The size of the network.	10 m * 10 m
La localisation de la station de la base.	(50,200)
The number of nodes	100 N
The initial energy of the nodes	0.12 J
Le nombre de cluster à créer avec K-means	5

Table 2.

The simulation settings.

4.2 Simulation results

In this simulation our experimental model is established with 100 nodes randomly spread over a square surface of 100 m² and a base station situated in (50,200) coordinate: Figure 6 illustrates the simulation phase with k = 7.

Figure 6.

The phase of clustering with (k = 7).

After the simulation we compare the performance of the two protocols LEACH and LEACH improvement with K-means by certain metrics.

4.2.1 Residual energy

Figure 7 below represents the residual energy relative to the number of rounds for the two LEACH and K-LEACH protocols. Both protocols showed a gradual decrease in energy and the difference between the two protocols is acceptable. However, K-LEACH show good improvement in lifespan with the same measures.

Figure 7.

Residual energy versus rounds (LEACH and K-LEACH).

4.2.2 Lifetime comparison

Figure 8 shows the number of dead nodes in both protocols. In LEACH, there was a very rapid decrease in the number of dead nodes depending on the number of rounds The first dead node in round Number: 97 and the tenth dead node in round 120 and all nodes died Round 441. This is what causes a very short lifespan in LEACH. On the other hand in K-LEACH has a longer lifespan, with a slow decrease in the number of dead nodes according to the round or The first dead node in round Number: 235 and the tenth dead node in round 337 and all nodes died Round 689.

Figure 8.

Number of dead nodes “first, tenth, last” versus rounds.

4.2.3 Comparison of CH numbers

Figure 9 shows the number of CHs in both protocols. We find that in LEACH has a high number of CHs which implies high energy consumption on the other hand in K-LEACH a fixed number of CH k-10 will die slowly. K-LEACH ensures a good distribution of CH on the network. LEACH presents a huge variation in the number of CH per round this leads to poor network coverage, and affects the overall lifespan of the network.

Figure 9.

Number of CHs nodes versus round.

After comparing the performance of the two LEACH and K-LEACH protocols, we noticed that the our adaptation K-LEACH has several advantages such as: The decrease in energy consumption; A longer lifespan during the simulation with a good distribution of CH thanks to the k-means method.

5. Conclusions

In recent years, Wireless Sensor Networks have been among the most active research themes due to their applications. The main factor limiting a sensor node is energy consumption. The battery-powered sensor nodes must be able to operate at very low Energy consumption.

The cluster-based routing protocols group the sensor nodes to efficiently relay to transmit data to the Sink. Cluster Head CH aggregates the data and sends it to the Sink in the name of the nodes in its group.

The most interesting research problem is how to form the clusters and choose the CHs so that energy consumption and contemporary communication parameters such as latency are optimized. Factors that influence on cluster formation and selection of CHs remain open questions for research.

Simulation results show that adapting the LEACH protocol with the K-Means clustering method that can extend network life and improve energy efficiency, increasing node survival and performance exceeds LEACH’s in terms of the amount of data transmitted to the base station and network life.