Wireless Sensor Network, 2010, 2, 777-783
doi:10.4236/wsn.2010.210093 October 2010 (http://www.SciRP.org/journal/wsn/).
Copyright © 2010 SciRes. WSN
Published Online
An Energy-Balanced Clustering Routing Algorithm for
Wireless Sensor Network
Fengjun Shang, Yang Lei
College of Computer Science and Technology, Chongqing University of Posts and Telecommunications,
Chongqing, China
Email: shangfj@cqupt.edu.cn
Received May 19, 2010; revised June 27, 2010; accepted August 4, 2010
Abstract
In this paper, we consider a network of energy constrained sensors deployed over a region. Each sensor node
in such a network is systematically gathering and transmitting sensed data to a base station (via cluster-
heads). This paper focuses on reducing the power consumption of wireless sensor networks. Firstly, we pro-
posed an Energy-balanced Clustering Routing Algorithm called LEACH-L, which is suitable for a large
scope wireless sensor network. Secondly, optimum hop-counts are deduced. Lastly, optimum position of
transmitting node is estimated. Simulation results show that our modified scheme can extend the network
lifetime by up to 80% before first node dies in the network. Through both theoretical analysis and numerical
simulations, it is shown that the proposed algorithm achieves higher performance than the existing clustering
algorithms such as LEACH, LEACH-M.
Keywords: Wireless Sensor Network, LEACH, Energy Efficient, Multiple-Hop
1. Introduction
Wireless Sensor Networks (WSNs) can collect reliable
and accurate information in distant and hazardous envi-
ronments, and can be used in National Defence, Military
Affairs, Industrial Control, Environmental Monitor, Traf-
fic Management, Medical Care, Smart Home, etc. The
sensor whose resources are limited is cheap, and depends
on battery to supply electricity, so it’s important for Rout-
ing to efficiently utilize its power.
In this paper, we propose an advanced multiple-hop
routing protocol named LEACH-L, whose features can
be described as follows: when the cluster-heads are close
to, they directly communicate with Base station (BS);
when they are far in distance, they telecommunicate by
multiple-hop way, and the shortest transmission distance
is limited. The sensors in different areas use different
frequencies and gaps to communicate with BS. In the last
part, the authors respectively simulate LEACH [1],
LEACH-M [2], and LEACH-L on the Matlab. The simu-
lation experiments indicate that: LEACH-L can prolong
the whole network lifetime.
2. Related Works
Various issues in the design of wireless sensor networks
such as the design of low-power signal processing archi-
tectures, low power sensing interfaces, energy efficient
wireless media access control and routing protocols, have
been areas of extensive research in recent years. LEACH
is one of the first hierarchical routing approaches for sen-
sors networks, which attempts to improve energy and
routing efficiency of such networks. The idea proposed
in LEACH has been an inspiration for many hierarchical
routing protocols, although some protocols have been
independently developed.
In [2], the author puts forward energy-LEACH and
multihop-LEACH protocols called LEACH-M. Energy-
LEACH protocol improves the choice method of the
cluster head, makes some nodes which have more resi-
dual energy as cluster heads in next round. Multihop-
LEACH protocol improves communication mode from
single hop to multi-hop between cluster head and sink.
Simulation results show that energy-LEACH and multi-
hop-LEACH protocols have better performance than
LEACH protocols.
In [3], a radio irregularity model is proposed aiming at
location and topology control. The simulated results show
that radio irregularity has a relatively larger impact on
the routing layer than the MAC layer. It also shows that
radio irregularity leads to larger localization errors and
F. J. SHANG ET AL.
Copyright © 2010 SciRes. WSN
778
makes it harder to maintain communication connectivity
in topology control.
In [4], author addresses the problem of clustering in
WSNs, subject to upper bounds on the maximum latency,
the energy consumed by intermediate nodes, and clusters
size. Those constraints are necessary for the reliability of
the system and for extending its lifetime.
In [5], author proposes a novel energy efficient clus-
tering scheme for single-hop wireless sensor networks. A
novel cost function is introduced to balance the load
among the cluster heads and prolongs the network life-
time significantly against the other clustering protocols
such as LEACH.
In [6], an Energy-Efficient Unequal Clustering is pro-
posed for multihop sensor network. Simulation results
show that the unequal clustering mechanism balances the
energy consumption well among all sensor nodes and
achieves an obvious improvement on the network life-
time.
In [7], a novel multicast protocol, uCast is proposed
for energy efficient content distribution in sensor net-
works. The uCast support a large number of multicast
sessions, especially when the number of destinations in a
session is small.
In [8], a novel energy-efficient protocol is proposed,
called Route Maintenance based-on Energy Threshold
and extends the lifetime of nodes and enhance the effi-
ciency of the entire network.
LEACH-C uses a centralized algorithm to form clus-
ters [9]. A non-autonomous cluster-head selection is again
the main disadvantage of this algorithm. Moreover, it re-
quires the location information of all nodes in the net-
work. However, location information in mobile wireless
networks is only available through GPS or a location-
sensing technique, such as triangulation which requires
additional communication among the nodes.
In [10], DCHS algorithm is proposed. In this algo-
rithm, in order to extend the lifetime, a parameter En_
current/En_max is introduced. Nevertheless, it has a cru-
cial disadvantage: After a certain number of rounds the
network is stuck, although there are still nodes available
with enough energy to transmit data to the base station,
so DCHS algorithm need be improved.
3. LEACH-L Algorithm
In order to explain our idea, we fist define some parame-
ters as follows.
The Eelect is consumed energy per bit.
The
f
s
and mp
are consumed energy per bit and
per area respectively.
The do is a distance, which decide the parameter value
both
f
s
and mp
.
The EDA is the energy required for data aggregation.
The is a cluster-head section probability, used dur-
ing cluster creation.
p
The round is the time, which all cluster members com-
municate with cluster heads and cluster heads communi-
cate with BS.
3.1. Problem Formulation
This paper proposes a modification of LEACH cluster-
head selection algorithm to reduce energy consumption.
For a microsensor network, we make the following as-
sumptions:
The base station (BS) is located among the sensors
and is stationary.
All nodes in the network are homogenous and en-
ergy-constrained.
All nodes are able to reach BS in one hop.
Nodes have location information.
Propagation channel is symmetric.
Cluster-heads perform data compression.
This paper presents an improvement to the LEACH’s
cluster-head selection algorithm by introducing distance-
based factor, called LACH-L. In LEACH-L, the clusters
are re-established in each round. Each of these rounds
consists of a set-up and a steady-state phase. New cluster
heads are elected in each round and as a result the load is
well distributed and balanced among the nodes in the
network. Moreover, each node transmits to the closest
cluster-head to split the communication cost to the sink.
Only the cluster head has to report to the sink and may
consume a large amount of energy, but this happens pe-
riodically for each node. During the set-up phase clus-
ter-heads are determined and the clusters are organized.
During the steady-state phase data transfers to the base
station occur.
We use a simplified model shown in Figure 1 for the
radio hardware energy dissipation. Both the free space
(power loss) and the multi-path fading (power loss)
channel models are used in the model, depending on the
distance between the transmitter and receiver. Transmis-
sion (Tx ) and receiving costs (
2
d4
d
E
R
x
E) are calculated as
follows [9]:
2
4
,
(, ),
elect fso
Tx
elect mpo
lEl dd d
Eld lEld dd


(1)
where d is the distance between the transmitter and the
receiver.
Where is:
0
f
s
mp
d
(2)
The following equation shows the amount of energy
required to receive each message.
F. J. SHANG ET AL.779
Figure 1. Radio energy dissipation model.
()
x elect
EL EL (3)
with L as the length of the message in bits, d as the dis-
tance between transmitter and receiver node. A sensor
node also consumes
D
A amount of energy for data
aggregation. We assumed that the sensed information is
highly correlated, thus the cluster-head can always ag-
gregate the data gathered from its members into a single
length-fixed packet.
E
3.2. Problem in Single-hop Routing
When the scope of WSN gets larger, the diversity of en-
ergy consumption among cluster-heads of LEACH as
well gets larger.
Let’s suppose that there are cluster-heads which
is r far from the BS and which is 3r far from the
BS.
()Si
()Sj
When , the energy consumption of is listed
as
0
rd()Si
4
(,)
Txelect mp
EkrkEk r

The energy consumption of S(j) is written as
4
(,) 81
Txelect mp
EkrkEk r

In the formula, when the circuit consumption is the
same, the energy consumed by transmit amplifier of S(i)
is 8l times as much as that of S(j) so WSNs in large
scope should adopt multiple-hop routing protocols.
3.3. Introducing Multiple-Hop Routing
The data collected by myriad sensors flow to a small
number of BS, which leads to the energy of sensors
which near to basic be used up quickly and leads to the
break of networks, so the question existing in many-to-
one networks is viewed as the hot spot [11]. Meanwhile,
only considering the shortest route will result in the geo-
graphic superiority of individual sensor embodied in the
multiple routes, and this is proved in LEACH-M. Be-
sides, multiple-hops routing cuts down the communica-
tion consumption, but increases the circuit energy con-
sumption. In order to go on the research, let’s suppose
that there is a linear network model, as shown in Figure 2.
The cluster-head which is nr far from the BS, if direct
communication protocol is adopted, so the total energy
consumed by network is:
(, )()(, )
directTxTx electTx amp
EEknrEkEkn

r

If multiple-hop transmission is adopted, the total en-
ergy consumed by network is:
() (1)()
multihopTxelectTx elect
EnEknE

k

+ (, )
Tx amp
nEk nr
(21)( , )
Tx electTxamp
nkEnE kr


This paper adopts the parameters of Table 1 in the fif-
th chapter. There are following conclusions:
When , so
0
rd
direct multihop
EE
44 4
2( 1)
mpelect mp
nrkn kEnrk
 
When 0
nr d
so
direct multihop
EE
22 2
2( 1)0
fselect fs
nrkn kEnrk


When 0
rd
,, so
0
nr d
direct multihop
EE
44 2
2( 1)0
mpelect fs
nrkn kEnrk


When
1
22
04
22
40000 (1)
()
4
ddnn
rnnd

, so
44 2
2( 1)0
mpelect fs
nrknkEnrk


When
1
22
04
22
40000 (1)
()
4
ddnn
rnnd

, so
44 2
2( 1)0
mpelect fs
nrknkEnrk


Therefore, when the nodes are close to the BS, directly
communicate routing can exhibition a good result; when
the transmission distance is long, under limiting each
transmitting distance the multiple-hop strategy can re-
duce the energy consumption of WSN.
3.4. Communication Conflicts
The communication between the cluster-heads and the BS
should adopt Collision Avoidance when the network be-
comes large and the number of sensors increase, or it will
give rise to the occurrence of conflicts when the clus-
ter-heads are sending data. Therefore, sensor networks in
large scope should adopt certain strategies to reduce the
Figure 2. Linear network model.
Copyright © 2010 SciRes. WSN
F. J. SHANG ET AL.
Copyright © 2010 SciRes. WSN
780
occurrence of conflicts.
3.5. Estimating Hop-Counts
CHs can send their data via just one (high-energy) trans-
mit of data to the base station or via a multi-hop scheme
where each data message must go through n (low energy)
transmits and n receives. Depending on the relative costs
of the transmit amplifier and the radio electronics, the
total energy expended in the system might actually be
greater using multi-hop routing than direct transmission
to the base station.
To illustrate this point, consider the linear network
shown in Figure 1, where the distance between the no-
des is r. If we consider the energy expended transmitting
a single l-bit message from a node located a distance nr
from the base station using the direct communication
approach via one hop and Equations (1) and (3), we have:
2
1
()
Tx fselect
n
El rlE

(4)
Where
is the number of hops. Thus, the total en-
ergy is:
TX RX
Etot EE

22
(1)
2elect fs
nr
lE l

 (5)
And the optimum number of hops is computed as be-
low:
2
2
20
tot
elect fs
opt
dE d
lE l
d
 
2 100
fs
opt
elect
d
dE
 
This shows that, when transmission energy is on the
same order as receive energy, which occurs when trans-
mission distance is short, direct transmission is more en-
ergy-efficient than multi-hop routing. Thus we use direct
transmission communication among CHs and the base
station.
3.6. Selecting Optimum Transmitting Node
To illustrate this point, consider the linear network shown
in Figure 3.
Where 0
is distance between BS and node 1,
02 0
is distance between node 2 and node 1,
is distance between BS and node 2. We select node 1 to
transmit data, when node 2 transmits data to BS. From
1
rd
2ddr r
Figure 3. Relay node network model.
Figure 2, we have
21
rrr
(6)
When node 2 transmits data to node 1, the energy con-
sumption is written as
2
11
node fselect
EkrkE

22
212
()2
node fselect
EkrrkE

The total energy consumption is as follows
22
12
2( )3
tot fselect
EkrrkE

(7)
We replace (6) into (7),
22
22
2(( ))3
tot fselect
EkrrrkE

And the optimum node position is computed as below:
2/2rr
In a similar way, when and
31 /3rr32 2/3rr
,
the energy consumption is minimum, etc.
According above computation, optimum transmitting
distance is
(1
opt opt
opt
d
d
)

Given coordinate of S(i) be (x, y), optimum node co-
ordinate is listed as
(1
(1
opt opt
opt
opt opt
opt
x
x
y
y
)
)


8
4. Simulation Results
This paper makes Matlab as experiment platform, and
goes on imitation in two scenes respectively. The para-
meters of imitation experiments see the following Table 1,
in which the first ten parameters are same to the docu-
ment.
Figure 4 and Figure 5 are the network’s life cycle in
two scenes. In the scene 1, the Fist Node Death time (FND)
of LEACH-L is 2.5 times more than that of LEACH, and
the Half Nodes Death (HND) time of LEACH-L is about
1.1 times more than that of LEACH. In the scene 2, LEA-
CH-L’s FND and HND are 12 times and 1.8 times as mu-
ch as that of LEACH. Besides, the last node dead time of
LEACH and LEACH-M are longer than that of LEACH-
L. The reason is that LEACH-L makes power equally
distribute among all sensors, therefore, in the pre-period,
the network’s activity nodes and cover areas of LEACH-L
are greatly larger than that of LEACH-M and LEACH.
Figure 6 and Figure 7 are the sum of data packets
which is the cluster-heads sending to the BS in two dif-
ferent scenes. In the scene 1, before HND, the sum of data
packets transmitted by LEACH-L is 1.3 times as much as
that of LEACH and 1.4 times as much as that of LEACH–
BS node 1node 2
r
1
r
2
F. J. SHANG ET AL.781
Table 1. Simulation parameters.
scene 1 scene 2
The scope
The number of sensors
The location of BS
300 × 300 m
900
(150,150)
500 × 500 m
2500
(250,250)
The initial energy
E
The length of packets
ETX
ERX
εfs
εmp
EDA
P
M
D
Restriction_distance
Max_distance
0.5 J
1 J
4000
5 × 10-8
5 × 10-8
10-11
1.3 × 10-15
5 × 10-9
0.1
0.1
70 m
30 m
87 m
0.5 J
1 J
4000
5 × 10-8
5 × 10-8
10-11
1.3 × 10-15
5 × 10-9
0.1
0.1
70 m
70 m
87 m
Figure 4. Dead nodes over rounds in 300 × 300 m.
Figure 5. Dead node over rounds in 500 × 500 m.
M. In the scene 2, before HND, the data transmitted by
LEACH-L is 2.4 times that of LEACH and 2.1 times that
of LEACH-M.
Figure 8 is relation between energy consumption and
round among LEACH, LEACH-M, LEACH-L in 300 ×
300 scene. From Figure 8, it is known that LEACH-L
can save energy consumption of network when LEACH-
L is compared with LEACH-M and LEACH. After a
while, it saves energy in LEACH and LEACH-M better
than LEACH-L. In about the 400th round, total energy
consumption of network in LEACH-L is more than LE-
ACH and LEACH-M, because some nodes in LEACH
and LEACH-M are dead with time going.
Figure 9 is relation between energy consumption and
round among LEACH, LEACH-M, LEACH-L in 500 ×
500 scene. From Figure 9, it is known that LEACH-L
can save 50% energy consumption of network in the 100th
round when LEACH-L is compared with LEACH-M and
LEACH. In about the 400th round, total energy consump-
tion of network in LEACH-L is more than LEACH and
Figure 6. Received packets over rounds in 300 × 300 m.
Figure 7. Received packets over rounds in 500 × 500 m.
Copyright © 2010 SciRes. WSN
F. J. SHANG ET AL.
Copyright © 2010 SciRes. WSN
782
Figure 8. 300 × 300 energy consumption among LEACH,
LEACH-M and LEACH-L.
Figure 9. 500 × 500 energy consumption among LEACH,
LEACH-M and LEACH-L.
Figure 10. 300 × 300 energy consumption of LEACH-L in
different areas.
Figure 11. 500 × 500 energy consumption of LEACH-L in
different areas.
LEACH-M, because some nodes in LEACH and LEA-
CH-M are dead with time going.
Figure 10 is relation between energy consumption and
rounds in different area in LEACH-L. It is obvious that
in two areas energy consumption is balancing in 300 ×
300 scene.
Figure 11 is relation between energy consumption and
rounds in different area in LEACH-L. It is obvious that
in two areas energy consumption is balancing in 500 ×
500 scene.
5. Conclusions
We have proposed a routing protocol named LEACH-L.
The experiments demonstrate that in the larger scope
sensor networks, Comparing with LEACH and LEACH-
M which is the multiple-hop protocol only considering
the distance, LEACH-L can balance network load, re-
duce the network’s energy consumption, enhance the net-
work’s data collecting precision and extend the net-
work’s life cycle, certainly, LEACH-L demands each sen-
sor node to record its own location information and the
information of candidate routing cluster-heads, increas-
ing the storage requirements of sensor nodes. But, com-
pared with balancing the nodes’ surplus energy and pro-
longing the life time of network, LEACH-L is valuable.
6. Acknowledgements
This work is supported by the Chongqing Natural Sci-
ence Foundation under Grant No. 2009BB2081. The Pro-
ject Sponsored by the Scientific Research Foundation for
the Returned Overseas Chinese Scholars, State Education
Ministry.
F. J. SHANG ET AL.
Copyright © 2010 SciRes. WSN
783
7
. References
[1] W. Heinzelman, A. Chandrakasan and H. Balakrishnan,
“Energy-Efficient Communication Protocol for Wireless
Microsensor Networks,” Proceedings of 33rd Interna-
tional Conference on System Sciences, Hawaii, 2000, p. 10.
[2] X. N. Fan and Y. L. Song, “Improvement on LEACH Pro-
tocol of Wireless Sensor Networks,” Proceedings of 2007
International Conference on Sensor Technologies and
Applications, Valencia, 2007, pp. 260-264.
[3] G. Zhou, T. He, S. Krishnamurthy and J. A. Stankovic,
“Models and Solutions for Radio Irregularity in Wireless
Sensor Networks,” ACM Transactions on Sensor Net-
works, Vol. 2, No. 2, 2006, pp. 221-262.
[4] B. Aoun and R. Boutaba, “Clustering in WSN with La-
tency and Energy Consumption Constraints,” Journal of
Network and Systems Management, Vol. 14, No. 3, 2006,
pp. 415-439.
[5] M. Ye, C. F. Li, G. Chen and J. Wu, “EECS: An Energy
Efficient Clustering Scheme,” 24th IEEE International
Performance, Computing, and Communications Confer-
ence, Phoenix, 2005, pp. 535-540.
[6] G. Chen, C. F. Li, M. Ye and J. Wu, “An Unequal Cluster-
Based Routing Strategy in Wireless Sensor Networks,”
Chinese Journal of Computers, Vol. 30, No. 1, 2007, pp.
27-36.
[7] Q. Cao, T. He and T. F. AbdelZaher, “uCast: Unified Con-
nectionless Multicast for Energy Efficient Content Dis-
tribution in Sensor Networks,” IEEE Transactions on
Parallel and Distributed Systems, Vol. 18, No. 2, 2007,
pp. 240-250.
[8] L. Hu, Y. Li and Q. B. Chen, “A New Energy-Aware
Routing Protocol for Wireless Sensor Networks,” Inter-
national Conference on Wireless Communications, Net-
working and Mobile Computing, Shanghai, 2007, pp.
2444-2447.
[9] W. Heinzelman, A. Chandrakasan and H. Balakrishnan,
“An Application-Specific Protocol Architecture for Wire-
less Microsensor Networks,” IEEE Transaction on Wire-
less Networking, Vol. 1, No. 4, 2002, pp. 660-670.
[10] M. J. Handy, M. Haase and D. Timmermann, “Low En-
ergy Adaptive Clustering Hierarchy with Deterministic
Cluster-Head Selection,” Proceeding of the 4th IEEE
Conference on Mobile and Wireless Communications
Networks, Stockholm, 2002, pp. 368-372.
[11] G. Smaragdakis, I. Matta and A. Bestavros, “SEP: A Sta-
ble Election Protocol for Clustered Heterogeneous Wire-
less Sensor Networks,” Proceeding of the International
Workshop on Sensor and Actor Network Protocols and
Applications, Boston, No. 4, 2004, pp. 660-670.