Wireless Sensor Network, 2011, 3, 307-312
doi:10.4236/wsn.2011.39032 Published Online September 2011 (http://www.SciRP.org/journal/wsn)
ANCAEE: A Novel Clustering Algorithm for Energy
Efficiency in Wireless Sensor Networks
Ademola P. Abidoye1,3*, Nureni A. Azeez2,3, Ademola O. Adesina1,3, Kehinde K. Agbele1,3
1Wireless Sensor Networks & Natural Language Research Group, Cape Town, South Africa
2Grid Computing & Distributed Systems Laboratory, Cape Town, South Africa
3Department of Computer Science, University of the Western Cape,
Cape Town, South Africa
Received July 18, 201 1; revised August 19, 2011; accepted August 31, 2011
Abstract
One of the major constraints of wireless sensor networks is limited energy available to sensor nodes because
of the small size of the batteries they use as source of power. Clustering is one of the routing techniques that
have been using to minimize sensor nodes’ energy consumption during operation. In this paper, A Novel
Clustering Algorithm for Energy Efficiency in Wireless Sensor Networks (ANCAEE) has been proposed.
The algorithm achieves good performance in terms of minimizing energy consumption during data transmis-
sion and energy consumptions are distributed uniformly among all nodes. ANCAEE uses a new method of
clusters formation and election of cluster heads. The algorithm ensures that a node transmits its data to the
cluster head with a single hop transmission and cluster heads forward their data to the base station with
multi-hop transmissions. Simulation results show that our approach consumes less energy and effectively
extends network utilization.
Keywords: Sensor Nodes, Clusters, Cluster heads, Wireless Sensor Networks, Base Station, Clustering
Algorithms, Energy Efficiency
1. Introduction
Recent advances in communication technology have led
to the development of intelligent, lightweight, low cost
sensor nodes that cooperatively collect data from the
place of deployment [1]. These nodes have the capability
to communicate among themselves and with the base
station. A sensor node consists of sensing, processing,
communication, transceiver and power units [2]. These
are used to acquire interested data, process, and commu-
nicate to other sensors within the networks usually,
through radio frequency channel [3]. Wireless sensor
networks (WSNs) have been used in many applications
include home security, battle-field surveillance, moni-
toring movement of wild animals in the forest, earth
movement detection, healthcare applications [4]. They
can also be used in sensing ambient conditions such as
light, sound, and temperature. Depending on the area of
applicati ons, sensor net works can be ran domly distri buted,
for instance in military applications, sensor nodes can be
randomly dropped from war-plane into the battlefield to
monitor enemies’ movement or manually placed.
Medical sensors can be manually placed in the hospital
to monitor both the medical staff and patients inside the
hospitals [5]. One of the main benefits of WSNs is their
ability to operate autonomously in harsh environments
where it may be dangerous or infeasible for human being
to reach [6]. T he nodes in WSNs are powered by batte ries,
it is expected that these batteries lasted for years before
they can be replaced. Due to the c ost and small size of the
sensor nodes, they have been equipped with small bat-
teries with limited energy source [7]. This has been a
major constraint of wireless sensor nodes which limits
their lifetime and affects utilization of the wireless sens or
networks. To extend batteries’ lifetime and networks
utilization, constant chang ing the batteries when they run
out of energy may not be practical, since these nodes in
most cases are many (tens to thousands of sensor nodes) ,
recharging the weaken batteries at all time may not be
feasible. Therefore, there is a need to minimize energy
consumption in WSNs. In recent time, many clustering
algorithms have been proposed with different protocols

A. P. ABIDOYE ET AL. 308
by different researchers to prolong networks utilization.
There still need to look for other techniques in which
energy can be minimized in WSNs.
Clustering technique is one of the effective approaches
used to save energy in WSNs [8]. Clustering means or-
ganizing sens or nodes into different gr oups called cl usters.
In each cluster, sensor nodes are given different roles to
play, such as cluster head, ordinary member node, or gate
way node. A cluster head (CH) is a group leader in each
cluster that collects sensed data from member nodes,
aggregate, and transmits the aggregated data to the next
CH or to the base station [9,10]. The role of ordinary
member node is to sense data from the environment they
deployed.
Gate-way nodes are nodes belonging to more than one
clusters and their role is to transmit data between two
clusters.
Furthermore, many different traditional clustering al-
gorithms for wireless ad-hoc networks have been pro-
posed by [11-13]. These clustering algorithms are not
suitable for sensor networks because in ad-hoc networks,
the primary concern is quality of service (QoS) and en-
ergy efficiency is the secondary. But in WSNs, the pri-
mary concern is the energy efficiency in order to extend
the utility of the network [14].
However, Low Energy Adaptive Clustering Hierarchy
(LEACH) Protocol was propos ed by [15] . This prot ocol is
one of the most famous hierarchical routing algorithms
for energy efficiency in WSNs. Other algorithms devel-
oped thereafter were based on this algorithm.
The operation of LEACH protocol is divided into
rounds. Each round consists of set-up phase and steady-
state phase. During the set-up phase, sensor nodes are
organized into different clusters based on the received
signal strength and cluster heads are selected for each
cluster as routers to the base station.
This algorithm saves energy, since only CHs are al-
lowed to transmit data to the base station rather than all
nodes. It allows CHs to rotate randomly to balance energy
consumption of nodes in the networks. Basically, each
node elects itself to be a CH in a given round. This deci-
sion is m ade by s electing a ra ndom nu mber bet ween 0 an d
1. A node V becomes CH for the current round, if the
number selected is less than set threshold value. The
threshold formula is contained in [15]. LEACH achieves
reduction in energy consumption 7 times compared with
direct comm unication an d betw een 4 to 8 times com pared
with minimum transmission energy (MTE) routing pro-
tocol [16]. Despite these benefits, LEACH suffers several
shortcomings. CHs are not uniformly distributed in
LEACH, CHs may be chosen from one part of the net-
work. If this occurs, energy dissipation will be more than
conventional protocols [17].
Moreover, considering a single round of LEACH, CH
selection based on probability will no t automatically lead
to minimum energy consumption during the steady state
phase.
[26] proposed two-level LEACH (TL-LEACH) algo-
rithm protocol. It was enhanced to the LEACH algorithm.
They adopted the same method of cluster heads selection
and clusters formation. The algorithm elected two sensor
nodes in each cluster as cluster heads, one node as pri-
mary cluster head and the other as the secondary cluster
head. Both the primary and secondary cluster heads can
communicate with each other and secondary cluster
heads communicate with nodes in their sub-clusters.
Secondary cluster heads collect sensed data from the
other nodes, perform data fusion and transmit it to the
primary cluster heads. Primary cluster heads further per-
form data fusion on the received data and transmit it to
the base station. Th is technique greatly reduces the num-
ber of data sent to the base station. However, the algo-
rithm may not be energy efficient if the cluster heads are
at distance from the base station. Finally, there is high
probability of increase in overhead during the selection
of primary and secondary cluster heads which will result
to increase in energy consumption.
SEP is another clustering protocol, proposed by [18].
The main goal of the protocol is to use non-homogenous
sensor n odes to dist ribute ene rgy uniform ly in WSN s. The
protocol operation is similar to LEACH protocol, apart
from method of cluster head selection is based on two
different l e vel s of energy . A node wi t h the highe st weight
according to their different energy is elected as CH.
Subsequent CHs are elected using this process. This ap-
proach ensures that CHs are randomly selected and en-
ergy consumption is uniformly distributed among sensor
nodes. The main objective of our research work is to
develop an algorithm that will minimize communication
distance among sensor nodes and prolong network utility.
2. Clustering Algorithm
Clustering is a good method in wireless sensor networks
(WSNs) for effective data communication and towards
energy efficiency [19]. It involves grouping of sensor
nodes together, so that nodes communicate their sensed
data to the CHs. CHs collect, aggregate and transmit the
aggregated data to the processing centre called base sta-
tion for further analysis [20]. Clustering provides re-
source utilization and minimizes energy consumption in
WSNs by reducing the number of sensor nodes that take
part in long distance transmission [21,22]. Cluster based
operation consists of rounds. These involve cluster heads
selection, cluster formation, and transmission of data to
the base station. The operations are explained below.

A. P. ABIDOYE ET AL.309
2.1. Algorithm for Cluster Heads Selection
In order for a node to become cluster head in a cluster the
followi ng assumptions were made.
 All the nodes have the same initial energy.
 There are S nodes in the sensor field.
 The number of clusters is K.
Based on the above assumptions, the average number
of sensor nodes in each cluster is M where
s
Mk  (1)
After
M
rounds, each of the nodes must have been a
cluster head (CH) once .
We assigned each node a unique identifier i, Mi for all
0,1,2,3,4, 1iS
Variable i is used to test whether it is the turn of a node
to become a CH.
Originally, all nodes are the sa me, i.e. there is no CHs
in each cluster, j = 0 where j is CHs counter .
A node q is selected among all nodes and continuously
executes the following steps:
Firstly, q incre m ents i by 1 a nd c heck if i is even, if yes
that node is selected as the CH for that round and an-
nounces its new position to all member nodes in the
cluster.
Else if i is odd, it cannot be a CH for that round, it will
wait for the next round and be ready to receive adver-
tisement message from the new CH.
A predetermined value is set (threshold value) for the
new CH to transmit for that round.
When the valu e has reache d, j will be incremented by 1
and the process of selection of new CH begins. It tests if
the following two conditions hold.
 That a sensor n ode has not becom e cluster head f or the
past

11p rounds [25].
 That the residual energy of a node is more than the
average energy of all the sensor nodes in the cluster-
ing.
Thus, the probability of a node becoming new cluster
head is given as



*
*
rem
i
avg
EiK
PEiM  (2)
where rem is the remaining energy in node (i), is
the average energy of all the nodes in a cluster.
Eavg E
It continues until j = K. The algorithm stops when j = K.
The new CHs collect sensed data from member nodes,
aggregate them, and transmit the compressed data to the
next cluster head or base station.
2.2. Cluster Formation
The next step in the clustering phase is cluster formation
after CHs have been elected. Below gives the description
of new cluster formation.
Step 1: The new cluster heads elected above broadcast
advertisements (ADV) m essage to all non-cluster nodes in
the network using Carrier Se nse Multiple Access (CSMA)
MAC Protocol.
Step 2: Each sensor node determines which clusters it
will join, by choosing CH that requires minimum com-
munication energy.
Step 3: Each non-cluster node uses CSMA to send
message back to the CHs informing them about the cluster
it wants to belong.
Step 4: After CHs have received messages from all
nodes, Time Division Multiple Access (TDMA) sched-
uling table will be created and send it to all nodes. This
message contains time allocated to each node to tran smit
to the CH within each cluster.
Step 5: Each sensor node uses TDMA allocated to it to
transmit data to the CH with a single- hop transmission
and switch off its transceiver whenever the distance be-
tween the node and CH is more than on e hop to con serve
energy.
To avoid a single node transmitting data multiple times
in one round, we set a threshold value G. G is the total
time of all nodes in the cluster forwa rding their data t o the
CH in one round.
Step 6: CHs will issue new TDMA slots to all nodes in
their clusters when allocated time for G has elapsed, for
each node to know exact time it will transmit data to avoid
data collision during transmission that can increase en-
ergy consumption.
Step 7: CH transceiver is always turn-on to receive data
from each node in its cluster and prepare them for in-
ter-clusters transmission.
Inter-cluster transmission is of two types: single hop
and multi-hop [23,24]. We adopted multi-hop transmis-
sion in order to save more energy during inter-cluster
transmission.
2.3. Steady State Phase
After all data has been received, the CH performs data
fusion function by removing redundant data and com-
presses the data into a single packet. This packet is
transmitted to the base station via multi hops transmis-
sion. After a certain period which is calculated in ad-
vance, the next round starts with the election of new CHs
using our initial algorithm as described in Section 2.1
above and formation of new clusters as explained in Sec-
tion 2.2.
3. Simulation Results and Analysis
The main aim of this experiment is to extend the network

A. P. ABIDOYE ET AL. 310
lifetime by minimizing communication distance during
transmission. In order to evaluate the performance of our
new clustering algorithm (ANCAEE), we simulated
LEACH, TL-LEACH protocol and ANCAEE using
MATLAB. To see the level of energy saving our proto-
col can achieve, we used 100 sensor nodes randomly
distributed between (0, 0) and (100, 100) m with base
station set at a distance (x = 50, y = 350) m as shown in
Figure 1.
Simple Radio energy dissipation model used for the
experiment was adapted from [15].
From the radio model, the energy expended by the ra-
dio to transmit k bits of data to distance d is given by

20
40
,
where
txelec amp
elec fs
elec mp
Ekd EkEk
Ek dkdd
Ek dkdd




 
(3)
To receive k bits of data is given by

*
rx elec
Ek Ek (4)
elec is the energy expended per bit to run the trans-
mitter or receiver circuit as shown in Equations (3) and
(4).
E
Energy dissipation by transmitter amplifier depends on
distance d between sender and receiver. For this experi-
ment, both the Free State (d2 power loss) and the Multi-
path Fading (d4 power loss) Models were used.
We set threshold value d0 for the distance between
sender (sensor nodes) and the receiver (Cluster heads and
Base station).
If the distance d is less than d0, Free State model is
used to know energy dissipation by the transmitter elec-
tronics else, Multipath Fading model is used.
The parameters used for the test and the respective
values are given in Table 1.
Sensor field containing 100 nodes is partitioned into
five clusters; each cluster contains a cluster head and
member nodes. Red nodes represent cluster heads and
Figure 1. Sensor nodes randomly distr ibuted.
Table 1. Simulation parameters.
Parameters Values
Number of Sensor Nodes 100
Network Dimension 100 m × 100 m
Nodes initial energy (K) 0.5 J
Transmitter circuitry di ssipation (Eele) 50 nJ/bit
Amplifier dissipation multipath (εmp) 0.0015 pJ/bit/m4
Data packet size 100 bytes
Amplifier dissipation free state (εfs) 10 pJ/bit/m2
Broadcast size 25 bytes
Distance between sensor field and Base-station x = 50, y = 350
black nodes represent member nodes. Each of the nodes
is assigned with unique identifier (ID) as shown in
Figure 2.
We compared the performances of our algorithms with
LEACH and TL-LEACH algorithms. We are interested in
the number of rounds when the first node dies and time
when the last node dies.
From the simulation result shown in Figure 3, it was
observed that the first node dies in LEACH and TL-
LEACH after about 135 and 148 roun ds resp ectively and
while in ANCAEE first nod e d ies af ter ab ou t 185 round s.
Furthermore, the last dies in LEACH after about 640
rounds and 7 10 rounds in TL-LEACH while last node dies
after 800 rounds in ANCAEE.
This simulation result shows that ANCAEE algorithm
extends battery life time thus, prolongs sensor network
utilization.
Figure 4 shows num ber of sense d data received at base
station (BS) over transmission rounds. Our algorithm

Sensor Node
 Cluster head
Figure 2. Cluster formation.

A. P. ABIDOYE ET AL.311
Figure 3. Number of nodes still alive over no of rounds.
Figure 4. Number of data received at base station.
selects new cluster heads (CHs) based on remaining en-
ergy of each node. It ensures that nodes with high residua l
energy are selected as CHs within a set value. The algo-
rithm transmits more data to the base station com pare with
LEACH and TL-LEACH algorithms with minimum en-
ergy dissipation.
4. Conclusions
In this paper, we introduced new method of cluster heads
selection and clusters formation al gorithm. Our algorithm,
ANCAEE partitioned the sensor field into different clus-
ters and elects a node as the cluster head for each cluster.
Each node within the cluster sends its data to the cluster
head with single hop transmission and cluster heads re-
ceive, aggregate the data and transmit to the base station
via multi-hops transmission. This method conserves en-
ergy dissipation of sensor nodes in the clusters.
Simulation results show that using this technique,
ANCAEE saves more energy than LEACH and TL-
LEACH protocols d ue to short range data transm ission of
sensor nodes and election of cluster heads based on re-
sidual energy of each node. The objective of this algo-
rithm is achieved of consuming less energy, distributing
energy consumption equally among all nodes and finally,
extends the network lifetime.
5. References
[1] W. Wang, et al., “CEDCAP: Cluster-Based energy-Effi-
cient Data Collecting and Aggregation Protocol for
WSNs,” Journal of Information Technology Research,
Vol. 3, No. 2, 2011, pp. 93-103.
[2] D. Zhicheng, Z. Li, B. Wang and Q. Tang, “An En-
ergy-Aware Cluster-Based Routing Protocol for Wireless
Sensor and Actor Network,” Journal of Information
Technology, Vol. 8, No. 7, 2009, pp. 1044-1048.
doi:10.3923/itj.2009.1044.1048
[3] Azat Rozyyev, H. Hasbullah and F. SubhanIndoor, “In-
door Child Tracking in Wireless Sensor Network Using
Fuzzy Logic Technique,” Research Journal of Informa-
tion Technology, Vol. 3, No. 2, 2011, pp. 81-92.
doi:10.3923/rjit.2011.81.92
[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E.
Cayirci, “A Survey on Sensor Networks,” IEEE Commu-
nication Magazine, Vol. 40, No. 8, 2002, pp. 102-114.
[5] J. N. Al-Karaki and A. E. Kamal, “Routing Techniques in
Wireless Sensor Networks: A Survey,” IEEE Wireless
Communications, Vol. 11, No. 6, 2004, pp. 6-28.
doi:10.1109/MWC.2004.1368893
[6] K. Sohrabi, J. Gao, V. Ailawadhi and G. J. Potie, “Proto-
cols for Self-Organization of a Wireless Sensor Net-
work,” IEEE Personal Communications, Vol. 7, No. 5,
2000, pp. 16-27.
[7] A. Gao, W. Wei and X. Xiao, “Multiple Hash Sub-
Chains: Authentication for the Hierarchical Sensor Net-
works,” Information Technology Journal, Vol. 9, No. 4,
2010, pp. 740-748.
[8] X. Guan, W. H. Yang and D. G. Bi, “EEHCA: An En-
ergy-Efficient Hierarchical Clustering Algorithm for
Wireless Sensor Networks,” Information Technology
Journal, Vol. 7, No. 2, 2008, pp. 245-252.
[9] J. Yang and D. Zhang, “An Energy-Balancing Unequal
Clustering Protocol for Wireless Sensor Networks,” In-
formation Technology Journal, Vol. 8, No. 1, 2009, pp.
57-63. doi:10.3923/itj.2009.57.63
[10] D. Wei, S. Kaplan and H. A. Chan, “Energy Efficient
Clustering Algorithms for Wireless Sensor Networks,”
Proceeding of the IEEE International Conference on
Communications Workshops, 19-23 May 2008, Beijing,
pp. 236-240.
[11] Z. Li, R. Li, Y. Wei and T. Pei, “Survey of Localization
Techniques in Wireless Sensor Networks,” Information
Technology Journal, Vol. 9, No. 8, 2010, pp. 1754-1757.
[12] W. Wang, et al., “Cross Layer Design and Implementa-
tion for Balancing Energy Efficiency in Wireless Sensor
Networks,” Information Technology Journal, Vol. 6, No.

A. P. ABIDOYE ET AL. 312
2, 2007, pp. 648-655.
[13] Y. Xu, J. Heidemamij and D. Estrin, “Geogra-
phy-Informed Energy Conservation for Ad Hoc Routing,”
Proceedings of the ACM/IEEE 7th Annual International
Conference on Mobile Computing and Networking, Rome,
16-21 July 2001, pp. 70-84.
[14] J. Chen, J. Fan, X. Cao and Y. Sun, “GRFR: Greedy
Rumor Forwarding Routing for Wireless Sensor/Actor
Networks,” Information Technology Journal, Vol. 7, No.
4, 2008, pp. 661-666.
[15] W. B. Heinzelman, A. P. Chandrakasan and H. Balak-
rishnan, “An application-Specific Protocol Architecture
for Wireless Microsensor Networks,” IEEE Transactions
on Wireless Communications, Vol. 1, No. 4, 2002, pp.
660-670. doi:10.1109/TWC.2002.804190
[16] K. Akkaya and M. Younis, “A Survey on Routing Proto-
cols for Wireless Sensor Networks,” Ad Hoc Networks,
Vol. 3, No. 3, 2005, pp. 325-349.
doi:10.1016/j.adhoc.2003.09.010
[17] M. Ahmad, M. Habib, M. Z. Shah, F. Ullah and S. Hus-
sain, “Energy Aware Uniform Cluster-Head Distribution
Technique for Hierarchal Wireless Sensor Networks,”
International Journal of Computer Science and Network
Security, Vol. 10, No. 10, 2010, pp. 97-103.
[18] G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A
Stable Election Protocol for Clustered Heterogeneous
Wireless Sensor Networks,” 2nd International Workshop
on Sensor and Actor Network Protocols and Applications,
Boston, 22 August 2004, pp. 56-66.
[19] K. Zhou, L. Meng, Z. Xu, G. Li and J. Hua, “A Dynamic
Clustering-Based Routing Algorithm for Wireless Senor
Networks,” Information Technology Journal, Vol. 7, No.
4, 2008, pp. 694-697.
[20] A. D. Amis, R. Prakash, T. H. P. Vuong and D. T. Huynh,
“Max-Min D-Cluster Formation in Wireless Ad-Hoc
Networks,” Proceedings of the IEEE 9th Annual Joint
Conference of the IEEE Computer and Communications
Societies, Tel Aviv, 26-30 March 2000, pp. 32-41.
[21] Y. He, W. S. Yoon and J. H. Kim, “Multi-level Cluster-
ing Architecture for Wireless Sensor Networks,” Infor-
mation Technology Journal, Vol. 5, No. 1, 2006, pp.
188-191. doi:10.3923/itj.2006.188.191
[22] W. Liu and J. Yu, “E nergy Efficient Clustering and Rout-
ing Scheme for Wireless Sensor Networks,” Proceeding
of the IEEE International Conference on Intelligent Com-
puting and Intelligent Systems, Shanghai, 20-22 Novem-
ber 2009, pp. 612-616.
doi:10.1109/ICICISYS.2009.5358113
[23] X. Hong, G. Mario and C. C. Chiang, “A Group Mobility
Model for Ad Hoc Wireless Networks,” Proceedings of
the 2nd ACM International Workshop on Modeling
Analysis and Simulation of Wireless and Mobile Systems
Seattle, New York, 20 August 1999, pp. 53-60.
[24] G. Yan and J. Xu, “A Clustering Algorithm in Wireless
Networks,” Proceeding of the International Conference
on Multi Media and Information Technology, Three
Gorges, 30-31 December 2008, pp. 629-632.
[25] M. J. Handy, M. Haase and D. Timmermann, “Low En-
ergy Adaptive Clustering Hierarchy with Deterministic
Cluster-Head Selection,” 4th IEEE International Work-
shop on Mobile and Wireless Communications Network,
Stockholm, 9-11 September 2002, pp. 368-372.
[26] V. Loscri, G. Morabito and S. Marano, “A Two-Level
Hierarchy for Low-Energy Adaptive Clustering Hierar-
chy,” 62nd IEEE Vehicular Technology Conference, Vol.
3, No. 2, 2005, pp. 1809-1813.