International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
August 2017, pp.
ISSN: 2088-8708.
DOI: 10.
11591/ijece.
Energy-Efficient Hybrid K-Means Algorithm for Clustered Wireless Sensor Networks Aziz Mahboub1.
Mounir Arioua2.
El Mokhtar En-Naimi3 LIST Laboratory.
Department of Computer Science.
Faculty of Sciences and Techniques.
Tangier.
Morocco National School of Applied Sciences-Tetouan.
Abdelmalek Essaydi University.
Morocco
Article Info
ABSTRACT
Article history:
Energy efficiency is the most critical challenge in wireless sensor network.
The transmission energy is the most consuming task in sensor nodes, specifically in large distances.
Clustered routing techniques are efficient approaches used to lower the transmission energy and maximize the networkAos lifetime.
In this paper, a hybrid clustered routing approach is proposed for energy optimization in WSN.
This approach is based on KMeans clustering algorithm and LEACH protocol.
The simulation results using MATLAB tool have shown that the proposed hybrid approach outperforms LEACH protocol and optimizes the nodes energy and the network lifetime.
Received Dec 11, 2016 Revised Mar 10, 2017 Accepted Mar 24, 2017 Keyword:
Clustering Energy optimization K-means algorithm
LEACH
Wireless sensor network Copyright A 2017 Institute of Advanced Engineering and Science.
All rights reserved.
Corresponding Author:
Aziz MAHBOUB.
LIST Laboratory.
Department of Computer Science.
Faculty of Sciences and Techniques Abdelmalek Essaydi University.
Street of charf B.
P 410.
Tangier Ae Morocco.
Email: amahboub@uae.
INTRODUCTION
Wireless sensors network (WSN) is composed of group of wireless sensors deployed in field with a high density.
enables detection of physical phenomena such as thermal, optical, vibration and temperature or pressure .
, .
WSN are being increasingly used for several application areas, such as environmental monitoring, military target tracking, healthcare, seismic sensing, etc.
Each sensor node is assembled with a transducer, microcomputer, transceiver and power source.
These wireless nodes are usually powered by limited capacity batteries which replacement is delicate in hostile environment where hundreds of them are randomly deployed.
The major limitations encountered in WSN are energy resources and high cost of transmission .
, .
Therefore, energy limitation is the key challenges in wireless sensors network, since the batteries are not rechargeable usually which limits the network lifetime .
To extend the wireless network lifetime, the energy of sensor nodes should be efficiently used.
Energy required in communications is the important consuming part compared to processing process in sensor nodes .
A variety of techniques have been developed in order to reduce the communication energy consumption.
Optimized routing techniques such as clustering algorithms have been widely adopted in WSN due to their energy effectiveness.
This paper investigates the energy efficiency of clustering in routing protocol.
We propose a substantial K-Means clustering algorithm based on LEACH protocol which consists of using jointly KMeans and LEACH approaches.
The proposed hybrid algorithm is proved to be energy efficient than LEACH protocol and significantly extends the sensor network lifetime.
The remainder of this paper is organized as follows.
Section 2 discusses the outline of K-Means The improved K-Means algorithm is described in section 3.
Simulations and results are discussed in section 4.
The final section concludes the paper by setting the direction of future work.
Journal homepage: http://iaesjournal.
com/online/index.
php/IJECE IJECE
ISSN: 2088-8708
K-MEANS ALGORITHM
K-Means is one of the promising and effective clustering algorithms .
It consists of regrouping nodes in the network into several clusters, the foundation of clusters is based on two parameters.
the first parameter is the number of wish clusters, the second parameter is the Euclidean distance is used for locate the closest cluster for each node .
The selection of cluster heads for the k-Means clustering algorithm is based on two things.
the cluster heads position must be the cluster center, and the residual energy of the node.
In wireless sensor network, the k-Means clustering method is based on an iterative optimization of the distance between the nodes to classify.
The algorithm generates K clusters from a set of N nodes.
The objective function of K-Means algorithm is .
, .
Where Cr is the set of nodes that belong to cluster r.
The K-Means clustering uses the Euclidean Oo Therefore the K-Means algorithm only seeks to find the global minimum of chr.
Where xi is a node of a cluster, chr the cluster head .
Algorithmic Steps for k-Means Clustering The progress of the K-Means clustering algorithm is done in four phases, the first step is choosing the desired number of clusters to generate in wireless sensors network, then for each cluster on chosen the cluster head randomly ch.
After the attribute the closest cluster to each node using the Euclidean distance .
The .
1,x2,x3,A.
,x.
represented the wireless sensors deployed in field and .
h1,ch2,AA.
,ch.
is the clusters head chosen initially randomly.
Initialize the middle of the clusters randomly chr where: r = 1 ,.
,k and k < n Attribute the closest cluster to each data point using the Euclidean distance .
For all clusters k, the cluster middles chi are updated using:
ENERGY MODEL
A sensor uses its energy to carry out three main tasks: acquisition, data processing and However, the energy used for acquisition is not prominent as much as in the communication Likewise, the energy consumed in the data processing operation is less important than communication energy .
The proposed approach uses the first order model adopted by LEACH and SEP protocols, the radio model is shown in Figure 1.
Figure 1.
Energy model in wireless sensor network.
Energy-Efficient Hybrid K-Means Algorithm for Clustered Wireless Sensor Networks (Aziz Mahbou.
A ISSN: 2088-8708 However, the consumed energy in data processing operation is less important than the energy of communication .
nergy required to send or receive data to another node.
The distance between transmitter and receiver influences the quantity of the consumed energy to send data into destination.
To broadcast a K-bit for a distance d, the energy expend by the system can be calculated by the Equations .
The expended energy can be schematized as follows:
The energy expended in the transmit electronics for free space propagation ETx-fs is described by:
The energy expended in the transmit electronics for free multi-path propagation ETx-mp is given .
To receive a message of k bits, the energy consumed by the receiver is given by:
Where: ETx is the electrical energy required to transmit a K-bit message over a distance d.
Eelec corresponds to the energy per bit required in transmitting and receiving electronics to process the are constants corresponding to the energy per bit required in the transmission amplifier to transmit an L-bit message over a distance d2 and d4 for free space and multi-path propagation modes, respectively.
By equating formula .
, we determine the distance d=d0 when the propagation transitions from direct path to multi-path:
d0=Oo .
If the distance between the transmitter and the receiver is larger than the crossover distance d0, the multi-path model is employed.
Otherwise, the free space model is adopted to measure the energy dissipation.
HYBRID K-MEANS APPROACH
The proposed routing approach aims mainly to optimize the energy consumed in data Using K-means clustering algorithm along with LEACH protocol enable member nodes to be attached to the closest CH in the network.
By adopting the proposed scheme, the transmission energy is minimized and the network lifespan is improved.
By considering n nodes randomly generate in area with dimension M*M.
Our approach ,the kMeans clustering algorithm is used initially for classify the nodes in wireless sensors network in groups ,The classification takes place as follows: the initialization of k , take k number of groups , the chosen k centroids initially at random places of groups which will be constructed or k< n.
The next step consists of grouping the nodes into clusters using the Euclidean distance.
Each node is attached to the closest centroid in the network.
Then the recalculate the position of centroid in each group, if the position of the centroid is changed then returns to step the join of each node in the new nearest centroid.
If the position of the centroids does not change.
Secondly, the Leach protocol is used in each group for the selection of clusters head and their The optimal number of CHs is estimated to be 5% of the total number of nodes .
The node elects itself to become a cluster head by some probability and broadcasts its status to the group members.
A larger number of nodes may elect themselves as cluster heads than the desired number of cluster This decision is made by the node by choosing a random number between 0 and 1.
The node becomes a CH for the current round if the number is less than the threshold T.
, the node declares CH according to the Equation following threshold:
IJECE Vol.
No.
August 2017 : 2054 Ae 2060
IJECE
ISSN: 2088-8708
( ))
Where p is the desired percentage of CH nodes in the sensor population and r is the current round number, where Gk is the group of nodes that have not been CHs in the last 1/p rounds .
Figure 2.
Flowchart of the cluster formation process of proposed approach
RESULTS AND DISCUSSION
All simulations were perfomed using MATLAB.
We started by a series of simulations to ascertain the experimental optimal value of the number of claasified groups that can provide energy efficeiny in the sensor netwok.
We tested the perfomed network with different clusters number .
=2, k=3 , k=4 and k=.
We perfomed simulation for two algorithms (LEACH and proposed approac.
, we compare and discuss the obtained results.
The simulated network consists of 100 nodes distributed randomly in an area of 100 m y 100 m.
The base station is located at position .
m, -50.
Every node transmits a 4000-bit message per round to its cluster head.
The probability of being cluster head is set to 0.
05, about 5% of nodes per round become cluster head Figure 3 presents the number of live nodes versus transmission rounds for Hybrid Kmean approach for different classification number (K).
The best energy performance of the proposed approach was obtained when K=3.
The stability period was sufficiently extended and the network lifmetime was enormously lenghtenend.
In consequence, we choose to perofm the Hybrid K-Mean approach with the optimal value of classification (K=.
In order to evaluate the proposed approach performance, several plots were generated to characterize energy consumption and the distribution of live and dead nodes in the hybrid K-Means network.
calculate the total WSN energy, and distribution of alive nodes for each method (LEACH and Hybrid KMean.
on common plots to compare network performance.
The total system energy and number of nodes versus transmission round are shown in Figure 4 and Figure 5 respectively.
Simulation total energy of the network using LEACH protocol and the proposed Hybrid K-Means algorithm is carried out in order to evaluate the algorithms energy performance.
Table 1 show the simulation parameters used in this work.
The comparison we carry out in this work between the proposed approach and LEACH protocol is based on some key performance parameters of wireless sensors network: firstly, the network lifetime that describe the time interval between the start of the network operation and the death of the last sensor node.
The second parameter is the number of alive nodes which is the total number of the sensor nodes that have not yet depleted all of their energies.
The third parameter is the number of dead nodes which is the total number of sensor nodes that have consumed all of their energy and are not able to do any kind of Energy-Efficient Hybrid K-Means Algorithm for Clustered Wireless Sensor Networks (Aziz Mahbou.
A ISSN: 2088-8708 The obtained results have demonstrated that the proposed approach reduces the energy consumption by round, and extend the network lifetime.
According to Figure 4, the energy consumption rate of the proposed approach is less than the LEACH protocol.
At approximately round 2300 and 2400 for the LEACH protocol, there is no energy in the WSN.
On the other hand the exhaustion of system energy in proposed approach begins at 4000 rounds, therefore the proposed approach provided the longest lifetime of WSN due to the Leach protocol.
Table 1.
Simulation parameters Simulation Area BS Location 100 m * 100 m .
m , -100 .
Number of Nodes Transmission amplifier free space Afs 10 pJ/bit/m2 Transmission amplifier, multipath Amp 0013 pJ/bit/m4 Data Aggregation Energy 5 nJ/bit/msg Transmission Energy ETx 50 nJ Receiving Energy ERX 50 nJ Network Dimension 100m*100m Signal wavelenght Antenna gain factor Gt .
Gr Message size .
4000 bits Initial node energy Figure 3.
Nnumber of nodes alive versus transmission round for proposed approach In Figure 4.
Total system energy versus transmission round for LEACH and proposed approch Figure 5.
Nnumber of nodes alive versus transmission round for LEACH and proposed approach IJECE Vol.
No.
August 2017 : 2054 Ae 2060
IJECE
ISSN: 2088-8708
CONCLUSION
The main objective of this work is to propose a novel clustering routing approach based on k-Means algorithm and LEACH protocol applied for wireless sensor networks.
The proposed approach minimizes the energy consumption, extends the network lifetime of the sensor nodes.
The evolution and enhancement of the presented routing algorithm should be done in the future to support multipath and heterogeneous modes.
REFERENCES