International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

A Survey Paper on Various Energy Efficient Clustering Algorithms in

Wireless Sensor Networking
Sharvari Gaikwad1, Saurabh Ghewande2, Uday Kale3, Rushikesh Sumbe4
1,2,3,4 Student, Department of Computer Science and Engineering, PCCOE, Pune, India
---------------------------------------------------------------------***----------------------------------------------------------------------
Abstract - Wireless Sensor Network (WSN) is the next big
thing the world has to adapt. It is composed of finite set of
sensing devices, geographically distributed in a given indoor
or outdoor environment which aims to gather the
environmental data. Here sensed information is transmitted
via wireless media. Consisting of cluster heads, base station
and non-cluster heads. These sensors are battery driven and
hence subjected to power loss and energy drainage. Therefore,
energy saving' is the most important in task of WSN
operations. The sensor nodes are un-rechargeable, so it leads
to an issue regarding lifetime of the network. As per the
Communication Technology, most of the energy is consumed
by transmission of energy followed by processing and then
sensing. In this paper we have presented various Clustering
approaches and Routing protocols that can optimize the Fig-1: Basic architecture of WSN
wireless sensor network (WSN).
RELATED WORKS:
Key Words: Wireless sensor networking, cluster head,
clustering, energy Based on LEACH protocol called as LEACH-TLCH.
Due to randomness of the clusters forming the new
1. INTRODUCTION algorithm proposed. This algorithm based on LEACH,
where the process of cluster-head selection and cluster
Traditionally down the ages, energy 'Consumption vs formation is same as LEACH protocol. Selection of the
Conservation' has been a highly alarming issue. Recent cluster is based on the threshold value. A secondary
advances in wireless communications, networking, Cluster head (SCH) is elected in the same cluster.
electronics and microprocessors have enabled the Cluster divided into two categories cluster with
development of low-cost, low-power wireless-sensor secondary cluster head and cluster without secondary
nodes that are small in size and can communicate over cluster head. Path for data transmission: Receive Data
short distances. Each of the sensors in WSN contains a from Sensor node and pass to SCH -> Data Fusion->
Battery for power, Transmitter for transmitting the Send to CH-> Sent to BS by single-hop method.
information and Receiver for receiving the information. Effective lifecycle of the improved algorithm is 9%
Energy consumption can be reduced by using proper longer than LEACH. Stable period of lifecycle increases
cluster-management techniques and routing protocol. 15% than LEACH. The energy efficiency and the
Clustering techniques includes hierarchical clustering lifetime of network are better than LEACH protocol.
for heterogeneous nodes, maintaining cluster size, hot- EDCH(Effective Distance Cluster Heads)-a
spot problem elimination etc. while Routing deals with clustering algorithm which is described in the two
single hop, multi- hop network transmission, multi- phases-EDCH1 and EDCH2.
path selection, probabilistic approaches and inter-
clustering routing. LEACH (Low-Energy Adaptive EDCH1: Focused on the formation of clusters of
Clustering Hierarchy) and DSP (Dynamic Source equal size so that the energy not wasted. After election
Routing) protocols are widely used in Clustering and of first cluster head follows usual LEACH procedure.
routing respectively. Divides of the cluster into smaller cluster with each
small cluster having cluster head.

EDCH2: Derived a formula for selection of the

Cluster head. So that more number of sensor nodes

© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1183
 International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

having the probability to be CH. applied to a clustered WSN where each node belongs to
the closest cluster according to their distance to the
T’(n)=T(n)+(1-T(n)) x f , where 1. T’(n) is novel cluster center. Energy consumption is reduced using
threshold value 2. T(n) is basic formula in LEACH to this strategy for both methods of CH selection. This
calculate threshold value. 3. F is constant. This formula strategy increases the rate of saved energy. The new
is used to calculate threshold value in every round. The transmission strategy saves more energy than previous
result shows that using optimum value of f EDCH2 techniques (it can reach up to 90%).
shows the improvement to reduce energy utilization
and hence increase network lifetime. Compared with The main focus is on the two Parameters that are a.
LEACH, EDCH1 shows up to 5.6% development in Average communication distance and b. Lingering
saving energy and up to 7.25% in extend network life. energy. Average communication distance is the
Compared with LEACH, EDCH2 shows up to 13.01% distance from central to I th node. For selection of CH
development in saving energy and up to 30.01% in following formula is used:
extend network life.
ACD=sum of distance of ith node(Di)/n,
A two stage energy proficient balanced clustering where n is number of nodes
method. Here they consider parameters such as
residual energy, intra-cluster cost, inter cluster cost, In the above formula, Di is the distance to I th node and
communication distance. Protocol composed of two n is number of nodes. Another method is Lingering
stages: 1. Cluster formation : Cluster formation and CH energy which is also called as residual energy. On the
selection is done by k-means algorithm 2. Load basis of lingering energy, Cluster head is selected.
Balancing : phase inter and intra cluster cost and
communication distance is considered. Used Omnet++ Lingering Energy: Residual Energy
simulator for simulation. Offered good load balancing =Etx(k,d)=kEelec+k*epsilon*d^2
within the network. Network life time increases. Future
work: Network life time decreases as nodes increases. Here in this paper, there are two modes are applied in
the algorithm. If first mode is applied i.e. ACD, then ACD
A strategy for the data transmission to efficiently
is calculated according to formula. If ACD of node is less
extend the network life time using the same energy.
than other then it is considered as CH. Cluster is
a) Cluster selection methods: formed on the basis of distance from that CH.
Threshold Distance = under root of epsilon Fs / epsilon
 Method 1: We select the node that has the mp
minimum of means of distances to all other
nodes belongs to the cluster as cluster head. The FND (First Node Die) and LND (Last Node Die)
ratio is better than LEACH and SEECH. CUDP (Complete
 Method 2: We select the node that has the useful Data percentage) is higher LEACH and SEECH.
minimum of maximum distance from all nodes Time simulation is good.
as cluster head.
Heterogeneous network is considered. The parameters
b) Transmission Strategy : used are residual energy, transmission range, number
of transmission. In this method, first transmission
The transmission strategy is proceeds by the CH energy, Consumption rate, Delay is calculated.
election process and the classification of nodes into
active nodes and sleeping nodes. The transmission Delay= (E(i)-E(r)/E(i)+x)*RTD
strategy uses either cooperative or non-cooperative
scheme. The first step consists of calculating the From the above formula, delay of node is calculated.
necessary transmit power to transmit data via non- E(r) is the residual energy.
cooperative scheme. They apply the relay selection
algorithm based on Dijkstra’s algorithm to select the On the basis of delay, Node which has low delay is
set of relays that cooperate to retransmit data from the consider as CH. After that nodes which are closest to
source node to the CH node with the minimum CH, Cluster is formed of that nodes.
transmit power. Here they proposed new energy
saving algorithm using on Dijkstra’s algorithm. It is
© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1184
 International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

Energy Consumption Rate= E(i)-E(r)/CR-1 Threshold T(n)= P(opt)/1-P(opt)*(rMod1/P(opt))

Sending l-bit data packet:
Energy consumption rate over other protocol is
uniform. FND is more than LEACH. Uniform network. Energy consumption (l,d)
Time taken to reach the packet is less =E (tx) (elec)(l)+E (tx) amp (l,d)
=l*E (elec)+l*epsilon (fs) *d^2 d<d0
Two phases : Initial and Rescue phase. Distance =l*E (elec) +l *epsilon (amp)*d^4 d>=d0
parameter use for cluster formation. Th (cluster) is Epsilon (fs) and epsilon (amp) are consumption of
calculated by using formula=N/X, where N is active amplifying radio. ‘d’ is the propagation distance,
nodes and X is the number of CH nodes. Now in first E(elec) represents energy consumption, epsilon Fs and
phase i.e. in initial phase Th defines the number of epsilon(amp) represents the energy consumption of
member nodes in each cluster. In second phase i.e. in amplifying ratio. Residual energy and distance are
rescue phase nodes join the possible cluster. For this main factors of ICT2TSK protocols. Active nodes alive
Th formula is used. By using Th formula first limit is ratio is higher. More efficient than LEACH. Prolong
calculated and then cluster members are decided to lifetime of network.
follow the cluster. Nodes will join the nearest cluster
head if the rescue phase condition is not satisfied. Extended version of LEACH. Time management concept
is used. A particular area is taken and divide it. Suppose
Threshold T(n)= P(opt)/1-P(opt)*(rMod /P(opt))
area is 100*100, then area is divided into 10*10m.
General formula for calculating the nodes in cluster
Cluster is formed with equal residual energy. If area is
defined by formula N/X.
of size 10*10 then each cluster will contain 20 nodes
at-least. If any cluster contain less than 20 node then it
Total cluster Distance=Σ i=1 to x Σ j=1 to n Dist (j,i)
will request the other cluster which has more than 20
Number of active nodes are more. Improved lifetime of
nodes. Then it will share its member with other that
network. Balanced load over LEACH.
has less member. Now process flow is as:-Initially the
The technique uses, a particular message is sent to node with higher residual energy, consider as a cluster
nodes and according to that after getting message each head. After every 60sec new cluster head is selected.
node update its neighbouring table.(Update the On 50th sec CH check routing table and node which has
neighbour’s routing table with the help of message highest energy selected as CH. On 56th sec, new node
broadcasting). Various parameters like energy become CH. Cluster is formed according to size of area.
consumption, delay, transmission, etc. are stored in Energy consumption is uniform. No effect of
matrices. These metrics are then compared and the unbalanced cluster on consumption energy.
matrix which contains higher residual energy
TEEN is designed for applications where data is sent to
considered as a cluster head. The nearest members
the base station when a specific event occurs.
form particular cluster. First, message is sent by server
Advantages of this protocol are that Reducing the
to members. A CH is selected among them. By distance
number of transmissions to the BS(Base Station) so
parameter, a cluster is formed with their CH. If cluster
that the approach is more energy- efficient. Data-
head is selected, then INVITE message is sent to other
centric nature of TEEN makes it suitable for time-
members in cluster. After participating in cluster,
concerned applications in which a quick response from
members send ADHESION message to Cluster head.
the network is urgent for user. Disadvantages: Some
Means they are now members of that cluster head.
nodes may die while the user is not aware of their
More efficient than LEACH, CHEATS, EEUC. Reduce the
death because it does not receive feedback. Defining
energy consumption. Spend much lower energy in
the exact value of the thresholds according to the
every round as compared to other protocols. Threshold
application is not very easy. Not suitable for the
energy concept use for selecting cluster head and
applications in which a periodical feedback from the
Distance parameter used for cluster formation. Setup
region is needed, like the monitoring of a forest.
and steady phase are described. In Setup phase clusters
are formed. In steady phase, Cluster and members are
Uses a random method for CH selection, each node
selected. TDMA mechanism is used to communicate
produces a probability p, based on which announces
with nodes.
itself as a CH within its cluster range. This
announcement is forwarded to all the nodes within the

© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1185
 International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

range of k hops from the CH. Then each node sends a

request to all the CHs from which it has received the
announcement. KOCA, which tries to solve the
overlapping clustering problem.

Methodology used:
1. Calculating the number of neighbors Using P: probability of selecting advanced nodes
2. CH election and P-nrm : probability of selecting normal node as CH.
3. Cluster formation Here alpha is constant and m is related to round
4. Determining TDMA schedules number. In E-BEENISH algorithm they have added
more parameter i.e. distance.

In DEEC algorithm :

Fig -2: Clusters along Clusters table

while in E-BEENISH algorithm they have added more

parameters and one extra layer i.e. ultra-super CH
nodes.

Fig-3: Area of cluster w.r.t CH

Cluster head selection- hybrid combination of
residual energy (primary) and communication cost
(secondary) such as node proximity Number of rounds
of iterations taken into consideration. Tentative
CH(Cluster Heads) are formed. Final CH until
CHprob=1. Disadvantages: Repeated iterations,
Complex algorithm, Decrease of residual energy.
Smaller probability-number of iterations increased.

Updated form of SEP(stable election process) where Advancement of DEEC protocol where traffic factor
CH nodes are selected upon residual energy Er and is considered. When there is lot of traffic over a CH
distance parameter. They have formulated new node then there will be more energy drainage rate than
selection criterion on four layered energy model expected hence leading to dead link eventually failure
consisting normal cluster heads, advanced cluster of network hence in this protocol as DEEC they are
head, super cluster head and ultra-super cluster heads. using probabilistic approach to find threshold energy
In SEP they are: and comparing Eth with probabilistic values from path
of every NCH. Here considering nodes to be of

© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1186
 International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

heterogeneous energy levels and E0 be the lower An improved ant colony optimization algorithm,
bound and E0(1+alphathi) be the upper bound of i’th
node then total energy of network can be calculated by  Step 1: Divide the TSP problem into several
summing the every nodes value which is Etot . Eavg sub-problems, and each sub-problem
value is determined for every round. Probability of corresponds to one subpopulation.
NCH to become CH is determined by following
formulae:  Step 2: Initialize the parameters of the
ICMPACO algorithm. These parameters include
the number of ants (k), pheromone amount
(Q), the maximum number of iterations (T), the
parameter (α and β), volatility coefficient (ρ),
etc. with WSN parameters include energy of
path , energy drainage rate.

Routing protocol in which sensing node floods the  Step 3: Randomly select the initial position for
neighboring node with route request message (RREQ). each ant. i.e. that of sensed node.
Similarly neighboring node also floods it neighbors
with RREQ this process is followed till there is  Step 4: Each sub-population independently
destination is achieved or already RREQ is sent. This execute the search process. The transition
message is passed to one by one nodes. If node is probability of the next state is calculated
having sufficient energy then it adds its own id to data according.
packet and send to next node. Once the RREQ reaches
the destination, Destination selects the best path from  Step 5: Locally update the pheromone
given solutions and reply back with RREP message. IF concentration of the passed path of ants in each
there is any conflict between two path the average subpopulation.
energy of path is considered to select the path. If any
 Step 6: Locally update the pheromone
intermediate node is dead then RERR message is sent
concentration of the adjacent path according to
to source so that the node is avoided. This performs
the pheromone diffusion mechanism for each
good but transmission delay is more and can consume
subpopulation.
more energy in case of redundancy and dense network.
 Step 7: Globally update the pheromone
concentration for each passed path.

 Step 8: If each ant executes Step 4 - Step 7 in

this iteration, then continue to execute next
step, otherwise go to Step 4.

 Step 9: Determine whether the maximum

number of iterations (T) is achieved or the
obtained solution has met the requirement. If
Fig- 4: Find path to transfer data within cluster this end condition does not meet, then execute
Step 4 in order to start a new
It is similar to the FTEERP but here they evolution,otherwise go to Step10.
considering the energy level of intermediate path with
the distance from source to destination for example let  Step 10: After ten iterations are completed, the
P and Q are source and destination . If there exits to obtained solutions of all sub-populations are
solution for intermediate transmission path for packet exchanged in order to select better solutions.
transfer. Selection of solution is dependent on
E1D2=E2D1 where E1 is total energy of nodes in path CONCLUSIONS:
no 1and D1 is distance in path1, similarly for E2 and
D2. Regarding Clustering protocols, the data
transmission in the Dijkstra’s algorithm technique is
useful, saves the energy using shortest path method.
© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1187
 International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056
Volume: 07 Issue: 06 | June 2020 www.irjet.net p-ISSN: 2395-0072

The cluster head selection process using four [9]Said Harchi, Jean Philippe Georges “WS dynamic
parameters is quite different from other techniques clustering for oil slicks monitoring”, 2012, IEEE
and still gives better result compared to LEACH-C and
ECHS. Moving on to Routing protocols, Ant colony [10]Feng Zhang, Qi-Ye Zhang “ICT2TSK:An improved
optimization, Swarm optimization, these techniques clustering algorithm for WSN using a Type-2 Takagi
will reduce the network overhead, transmission delay Sugeno Kang Fuzzy Logic System ”,2013 IEEE
considerably as it is maintaining own state as well as
previous state so decision can be taken from table itself [11]Tan Xian, “A modified energy efficient backup
with observing energy drainage rate. The Wake-up hierarchical clustering algorithm for WSN”, 2015 IEEE
radio module can be added to improve sleep
scheduling and reducing further more energy. Water [12]Yin ghui Zhang, Xialou Zhang, Shuang Ning, Jing
ripple technique can be used in addition with sleep Gao, Yang Liu, “Energy-efficient Multilevel
scheduling to hibernate non-essential nodes to stop Heterogeneous Routing Protocol for Wireless sensor
working. Traffic aware routing should be applicable in networks”,2017, IEEE
probabilistic approach of E-BEENISH etc. Energy [13]Deepak sharma, Amol P Bhondekar,” Traffic and
drainage rate can be substitute the traffic congestion energy aware routing for heterogeneous wireless
in many protocol for every round. sensor networks”, 2018, IEEE

REFERENCES [14]Zhenfei wang, Liying, Zhiyun Zheng, Junfeng

Wang,” An optimized RPL protocol for wireless sensor
[1]Wang, Mingzu, “Clustering in wireless sensor networking”,2016, IEEE
networks”, 2017, IEEE
[15]Hassan el alami, Abdellah Najid,”ECH: An enhanced
[2]Chunyao FU1, Zhifang JIANG1, Wei WEI2and Ang Clustering Hierarchy approach to maximize lifetime of
WEI “An Energy Balanced Algorithm of LEACH Protocol wireless sensor networks”, 2019, IEEE
in WSN”, 2016, IEEE
[16]Wu deng, Junjie Xu, Huimin Zhao. “An improved
[3]Rajkumar and H. G. Chandrakanth “EDCH: A Novel Ant colony Optimization Algorithm based on hybrid
Clustering Algorithms for Wireless Sensors Network”, Strategies for Scheduling Problem”, 2019, IEEE
2019, EJERS

[4]Md. Nurul Islam Khan, Md. Saiful Islam “A New

Approach of Energy Efficient Load Balancing for
Wireless Sensor Networks” 2019, IEEE

[5]Maha Abderrahim1, Hela Hakim1, Hatem Boujemaa,

Farid Touati “Energy-Efficient Transmission Technique
based on Dijkstra Algorithm for decreasing energy
consumption in WSNs”, 2019, IEEE

[6]Yuvaraj Padmanaban, Manimozi Muthukumarasamy

“Energy-efficient clustering algorithm for structured
wireless sensor networks”, 2018 IET

[7]K. Johny Elma, Dr. S .Meeakshee “Ennergy Efficient

clustering for lifettime maximization and routing in
WSN”,2018, IEEE.

[8]Vipin Pal, Girdhari Singh, “Balanced cluster size

solution to extend lifetime of wireless sensor network”,
2015, IEEE

© 2020, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page 1188