Int. J. Communications, Network and System Sciences, 2011, 4, 562-567
doi:10.4236/ijcns.2011.49067 Published Online September 2011 (http://www.SciRP.org/journal/ijcns)
Copyright © 2011 SciRes. IJCNS
A LEACH-Head Expected Frequency
Appraisal Algorithm for Water -Environment
Monitoring Networks*
Chenmin Li1,2, Guoping Tan1,2, Jingyu Wu1, Zhen Zhang1, Lizhong Xu1,2#
1College of Computer and Information Engineering, Hohai University, Nanjing, China
2Institute of Communication and Information System, Hohai University, Nanjing, China
E-mail: #lzhxu@hhu.edu.cn, zz_hhuc@163.com
Received July 18, 2011; revised August 12, 2011; accepted August 27, 2011
Abstract
Water-environment monitoring network (WMN) is a wireless sensor network based real-time system, which
collects, transmits, analyzes and processes water-environment parameters in large area. Both cluster selection
mechanisms and energy saving strategies play an important role on designing network routing protocols for
the WMN. Since those existing routing algorithms can not be used directly in the WMN, we thus propose an
improved version of LEACH, a LEACH-Head Expected Frequency Appraisal (LEACH-HEFA) algorithm,
for the WMN in this paper. Simulation results show that the LEACH-HEFA can balance the energy con-
sumption of nodes, rationalize the clustering process and prolong the network lifetime significantly in the
WMN. It indicates that the LEACH-HEFA is suitable to the WMN.
Keywords: WSN, LEACH Protocol, Cluster-Head Selection, Water-Environment Monitoring
1. Introduction
The wireless sensor network (WSN) located in the moni-
toring area is comprised of the sensor nodes with the
capability of sensing, storage, correspondence and com-
putation [1,2]. Since the influence of terrain, climate and
flow, the regional hydrologic information has intense
mutability. They can not be real-time monitored syn-
thetically [3,4]. It is necessary to introduce the newly
arisen technique for the area monitoring system, and con-
structed the WSN based regional water-environment
monitoring network. The advantages of WMN are more
obvious in harsh environment and the area which human
could not access [5].
At present, there are many routing protocols of WSN
[6,7], such as SPIN (Sensor Protocols for Information via
Negotiation), MTE (Minimum Transmission Energy),
DD (Directed Diffusion) and LEACH (Low-Energy
Adaptive Clustering Hierarchy) protocols etc. Based on
the main network structure, the routing protocol of WSN
could be divided into plane routing protocol and cluster
routing protocol [8]. Plane routing protocol needs to
maintain a large routing table and take up numerous sto-
rage spaces. It thus is not suitable to be applied in the
WMN. This problem would be solved by the cluster
routing protocol to some extent. Clustering is an impor-
tant energy-saving method in WSN [9].
The cluster-head selection mechanism directly affects
the energy consumption and network lifetime in WSN
based water-environment monitoring systems. Thus, the
cluster-head selection mechanism and the energy saving
strategy would be considered as the important aspects in
the design of network routing protocols. However, the
present routing protocols usually have problems such as
previously selected cluster-head, unbalancing energy loads
and short lifetime. It can not be applied to the real-time
WMN with large area. In this paper, the classic cluster-
ing routing algorithm LEACH and LEACH-C were ana-
lyzed. Based on the idea of cluster-head expected fre-
quency appraisal, LEACH-HEFA (LEACH- Head Ex-
pected Frequency Appraisal) algorithm is proposed. De-
pending on cluster-head selection and energy balance,
the algorithm can prolong the lifetime of network.
*This paper is supported by the National Natural Science Foundation o
f
China (No.61001068), the Special Funds for Scientific Research on
Public Causes (No. 201201118) and the “948” Project (No. 201025) o
f
the Ministry of Water Resources of the People’s Republic of China. The rest of the paper is organized as follows. The first
C. M. LI ET AL.
563
section presents the theory and cluster-head selection
mechanism of LEACH and LEACH-C algorithms, and
the problems existed in the two algorithms. The second
section proposes a LEACH-HEFA algorithm based on
the idea of cluster-head expected frequency appraisal,
and then describes the realization procedure in detail.
The simulation results are shown in the third section. The
final section gives the conclusions.
2. Analysis of Classical Algorithms
In water-environment monitoring system, to monitor a
large range with WSN, the paper designs the clustering
routing algorithm based on LEACH. The reasons are as
follows: 1) based on a clustering routing protocol,
LEACH can satisfy the requirement of real-time trans-
mits, analyze and process the water-environment pa-
rameters better than the traditional plane routing protocol.
2) Because of using local control technology and MAC
protocol with low energy consumption, LEACH protocol
is further satisfy the demand on the node energy control
and network throughput. Because of the features above,
the LEACH routing protocol based on the hierarchic
structure can be more suitable to be applied in the large
range WMN than other routing protocols.
2.1. Description of Classic LEACH Algorithm
As clustering routing algorithms proposed in WSN,
LEACH (Low energy adaptive clustering hierarchy) have
received lots of researchers’ attention. Its thought of
clusters has far-reaching influences on many important
clustering routing algorithms suggested later [10]. The
basic principle is that it assigns overall energy consump-
tion of the network uniformly to each sensor node
through periodically selecting different nodes as clus-
ter-head. This makes the survival time of nodes close to
the lifetime of network. Thus, the energy consumption
can be reduced and the lifetime of the entire network can
be prolonged [11].
The operation of LEACH is divided into several
rounds. Each round begins with a set-up phase when the
clusters are organized, followed by a steady-state phase,
as shown in Figure 1.
In the set-up state when the clusters are organized, the
LEACH sets a threshold value first, and then sen-
sor node generates a random number between 0 and 1
automatically by distributed computing. If the random
number <, the node will become the cluster-head of
the current round r, and common nodes join in the near-
est cluster. After a period of data transmission, the net-
work starts cluster reconstruction of the new round. And
the circular processes like that.
()Tn
i
()Tn
Set upSteady-state Round
Time
Figure 1. Time-line in LEACH operation.
The threshold value [12] is:
 
,
1mod1
0, otherwise
pnG
pr p
Tn
 

(1)
where p is the probability of the nodded being selected as
a cluster-head node; r is the number of rounds passed,
and G is the collection of ordinary nodes; mod denotes
modulo operator. The value of p is the expected number
of cluster-head nodes. In the LEACH algorithm, all
nodes in the cluster take it turns to act as the head node,
to achieve the purpose of balancing node energy con-
sumption. Therefore, only the nodes that have not al-
ready been cluster-heads recently and have more energy
available may become cluster-heads at round r + 1.
Once the cluster-head is selected, all nodes join the
corresponding cluster according to the broadcast signal
intensity of the cluster-head node. Then, the cluster
set-up phase of this round is completed. When the clus-
ter-head assigns time slots for its members using TDMA
mode, the network will enter the steady-state. In this
phase, after all member nodes sent monitoring data in-
formation, the head node will process data fusion, and
then send data information to the base station. After this
round, it turns to the next round, and starts cluster recon-
struction of the new round [13].
2.2. Description of LEACH-C Algorithm
Among many improved LEACH algorithms, LEACH-C
(LEACH-Centralized) is the most representative algo-
rithm [14]. In the LEACH-C algorithm, the base station
is responsible for the selection of cluster-heads. It is a
centralized cluster-heads algorithm [15]. After each node
reports its location and current energy, the base station
will select cluster-heads. According to the information of
all the nodes sending, the base station will select the
cluster-heads set based on appropriate number and loca-
tion. Then, according to the smallest square of the dis-
tance principle between all member nodes to the clus-
ter-head node, the base station broadcasts the clus-
ter-head set and cluster structure.
2.3. Existing Problems
Although LEACH-C solves the problem of uncertainty
Copyright © 2011 SciRes. IJCNS
564
t
C. M. LI ET AL.
on the number of cluster-head at each round in LEACH,
it still has problems such as pre-selection cluster-head,
equal opportunities for cluster-head selection mechanism,
and the unbalancing energy loads. This phenomenon
means that nodes with less energy remaining may be also
become cluster-heads. However, once these nodes be-
come cluster-head, their energy will soon exhaust. In the
later periods of the network, even the phenomenon of the
cluster-head is dead where it have not energy to forward
the information may occurred. Therefore, the selection
mechanism of cluster-head affects the performance and
lifetime of the entire network. Besides, through the anal-
ysis of the node residual energy distribution, the network
lifetime has direct relation to whether the energy utiliza-
tion is balanced.
3. Improved LEACH with HEFA
In order to solve above mentioned problems, an im-
proved LEACH algorithm, LEACH-HEFA (LEACH-
Header Expect Frequency Appraisal) algorithm is pro-
posed based on the idea of cluster-head expected fre-
quency appraisal. The algorithm use the cluster-head
expect frequency appraisal function as a parameter in the
mechanism of the cluster-head selection, and add up the
optimum solution of cluster-head number. If the node has
higher residual energy, it will have more probability to
be selected as cluster-head, which balances node energy
efficacious. The algorithm also uses the concept of
rounds. Each round of the cluster is also composed of
set-up phases and steady-state phases. The following is
the procedure of the LEACH-HEFA.
3.1. Set-up Phase
Now let N denotes the number of nodes in the network,
and R denotes the number of rounds of the network until
now, denotes the time spent per round, H denotes
the number of cluster-head. Each member node sends a
Join-REQ message to cluster-head, which consist of it-
self ID and the current residual energy. The following is
the realization procedure of set-up phase.
t
At time of , the average energy consumption of
the single cluster-head node is computed by:
t
  
__
1
H
i currenti current
i
head
EtEtt
Ett
H



 
t)tt
(2)
where, _ and _ are the current
residual energy of node i at time of t and , respec-
tively.
()
i current
E(
i current
Et t
Then, the average energy consumption of the single
member node is given by:
  
__
1
NH
j currentj current
j
common
EtEt
Ett NH
t

 
(3)
The maximum expected rounds of network operation
can be calculated as:

 
_
1
N
k current
k
expect head common
Ett
REttE tt

 
(4)
The expected frequency appraisal factors of node i
becoming cluster-head satisfy the following formula:

 
__
_
i expectheadexpecti expect
commoni current
KEttRK
EttE t

t
  (5)
From (5), we have:

 
_
_
i currentcommon
i expecthead common
EttEt
KEttE tt
t
 
  (6)
In the time of 2tt
, , , repeat the
above steps, update the
3tt 4tt
(2)t
head
Et , (2
on
Et)t
comm
,
and at the new round.
expect
R_i expect
It is shown that, through repeat the above steps, the
expected frequency appraisal factors of node i becoming
cluster-head changes dynamicly. As the network energy
consumption, _iexpect decreases gradually. Evidently,
of the second round is the maximum, presume
as _(max)i expect. If _iexpect close to _(max)i expect, it
shows that the node has higher residual energy and more
probability to be elected as cluster-head. Otherwise, if
_iexpect close to 0, the node has little residual energy
and less probability to be elected as cluster-head. There-
fore, use the number of cluster-head node appraisal func-
tion
K
K
K
_i expect
KK
K
K
_i expect as a parameter in the cluster-head
selection mechanism. The function value is between (0,
1), which could optimize the cluster-head selection more
effectively. Figure 2 shows the general curve of cluster-
head expected frequency appraisal function
K
.
_i expect
K
o
1
_i expect
K
_i expect
K

_maxi expect
K
Figure 2. The curve of cluster-head expected frequency ap-
praisal function
i_expect
ΨK.
Copyright © 2011 SciRes. IJCNS
C. M. LI ET AL.
565
Clearly, the average energy consumption of the clus-
ter-head node and common member nodes are different.
In addition, with the network and iteration process, clus-
ter-head expected frequency appraisal function
_i expect
K is a nonlinear function. Thus, the general
linear function such as

_
_
_(max)
i expect
i expectiexpect
K
K
k
K
 b
can not meet the curve. Through experiments, the ex-
pressions of non-linear appraisal function is as follows:

__
_(max)
1ππ1
sin
2
i expecti expect
i expect
KK
K
 
2
2
(7)
In this way, the threshold formula can be improved as:
 


_
_
_(max)
1mod1
1mod1
1ππ1
sin
2
i expect
i expect
i expect
p
Tn K
pr p
p
pr p
K
K

 

 


2
2
(8)
The optimal numbers of cluster-head nodes of this ar-
ticle use the method of literature [16], as shown in (9).

1
2
2
2π
fs
opt elec
mp toBS
NM
kEpJbit
d
 
2
mm
(9)
where opt denotes the optimal numbers of cluster-head
nodes, N denotes the total sensor nodes, M denotes the
side of the node distribution area and toBS denotes the
distance from the node to the base station.
k
d
When the distribution of the energy of sensor node
was extremely unbalanced, the modified threshold for-
mula (8) can avoid the tiny alteration of T(n). Since the
nodes with high energy would have more probability to
become the cluster-heads than the one with low energy,
it also reduces the randomness of cluster selection in
network. The mechanism can balance the energy con-
sumption among the nodes and prolong the lifetime of
the whole network. When the energy of cluster-heads is
well-balanced, the value of cluster-head node expected
frequency appraisal function is equal to one approxi-
mately.
3.2. Steady-State Phase
In the steady-state phase, each node sends the collected
information during its own TDMA time slot [17]. After
receiving information of all the cluster-heads, the base
station analysis the datum and transfer those to the top
man-machine communication interface. According to the
ID and information intensity of node sending, the clus-
ter-heads broadcast the information to the network, and
prepare for the next round.
So far, this round is complete. Figure 3 is a flowchart
of the improved algorithm.
4. Simulation Results
In this section, we mainly use simulations to analyze and
evaluate the performance of the algorithm. This paper
uses the network simulator, NS2 [18], which developed
by UC Berkeley, to simulate the method. Then, to verify
the improved algorithm proposed in this paper, we will
compare the results with LEACH and LEACH-C.
4.1. Simulation Setup
As shown in Figure 4, 100 sensor nodes were arranged
randomly in the field of 100 × 100 square meters. The
sink nodes were also arranged. The nodes have no
movement capability, and they can correspond with the
sink nodes directly. The initial energy of a sensor node is
2J and the energy of a sink node is infinite. The data in-
formation of the next round can not be sent until the end
of the former transmitted. It is assumed that the con-
sumption of the energy can be ignored in the execution.
The settings of other parameters of the network envi-
ronment were displayed in Table 1.
_
,,,
headcommonexpectiexpect
EttEttR K 
_i expect
K
Figure 3. Flowchart of LEACH-HEFA.
Copyright © 2011 SciRes. IJCNS
566 C. M. LI ET AL.
Figure 4. Random deployment of sensor node s in the field.
Table 1. Simulation parameters.
Parameters Value
Number of nodes 100
Network size 100 × 100 m2
Distance of node transmission 20 m
Initial energy 2J
1
elec
EnJbit
50

1
2
fs pJbit m
 10

1
2
mp pJbit m
 0.0013
Expected number of cluster-head per round 5
4.2. Simulations and Analysis
Figure 5 shows the number of nodes alive over time of
the three algorithms. As shown in this figure, compared
with the LEACH and LEACH-C algorithms, the lifetime
of the sensor node was prolonged after the improvement.
The LEACH-HEFA algorithms optimized the cluster-
head selection mechanism by proposing the cluster-head
node expected frequency appraisal function. Thus it
makes the node premature deceasing because of the ex-
cessive energy consumption, and then can prolong the
network lifetime.
Figure 6 shows the curve of the total energy con-
sumption of the network node varied with the time. The
top curve presents the energy consumption in LEACH
algorithms. The lifetime of the whole network is short
because of the frequent cluster-head selection without
considering the balance of energy. After the improve-
ment of the cluster-head selection mechanism, the nodes
with lower energy become the cluster-head with fewer
probabilities, and the cluster-head would not vary fre-
quently. Compared with the LEACH and LEACH_C
algorithms under the same runtime, the energy consump-
tion of the whole network would decrease remarkably.
As shown in Figure 7, the network operated regularly
to 200 rounds, all of the water-environment sensor nodes
can transmit the data normally. The first node is already
dead when the runtime of network operate to 200 and
240 rounds in the LEACH and LEACH_C algorithms
respectively. However, after the improvement, the first
node would not die until the 290 round because of the
energy consumption. The runtime of the last node is
prolonged significantly. Compared with the LEACH and
LEACH-C algorithms, the results show that the network
lifetime of the improvement algorithm can be prolonged
by 23% and 18%, respectively.
5. Conclusions
The cluster-head selection mechanism and energy saving
strategy play an important role in the design of network
routing protocol. However, the current routing protocols
usually have problems such as previously selected clus-
ter-head, unbalancing energy loads and short lifetime of
200 400 600 800 1000 1200 1400 1600
0
20
40
60
80
100
Time(s)
Number of nodes alive
LEACH
LEACH-C
improved LEACH
Figure 5. Number of nodes alive over time.
0100 200 300400 500 600 700800
0
50
100
150
200
Time(s)
Total Energy Consumption
LEACH
LEACH-C
improved LEACH
Figure 6. Total energy consumption versus time.
Copyright © 2011 SciRes. IJCNS
C. M. LI ET AL.
Copyright © 2011 SciRes. IJCNS
567
123 25 100
0
50
100
150
200
250
300
350
400
Number of Dead Nodes
Number of Rounds
LEACH
LEACH- C
improved LEACH
[6] X. F. Li, L. Z. Xu and H. B. Wang, “A Differential Evo-
lution-Based Routing Algorithm for Environmental Moni-
toring Wireless Sensor Networks,” Sensors, Vol. 10, No.
6, 2010, pp. 5425-5442.
[7] H. B. Wang, Y. L. Zhong, J. H. Zhang, X. J. Yan, L. Z.
Xu, “Based on Sleep Scheduling for Wireless Sensor
Networks Clustering Protocol,” Microelectronics & Com-
puter, Vol. 27, No. 8, 2010, pp. 226-229.
[8] O. Younis and S. Fahmy, “HEED: A Hybrid, Energy
Efficient, Distributed Clustering Approach for Ad-Hoc
Sensor Networks,” IEEE Transactions on Mobile Com-
puting, Vol. 3, No. 4, 2004, pp. 660-669.
doi:10.1109/TMC.2004.41
[9] A. B. M. A. Al Islam, C. S. Hyder, H. Kabir and M.
Naznin, “Finding the Optimal Percentage of Cluster Heads
from a New and Complete Mathematical Model on
LEACH,” Wireless Sensor Network, Vol. 2, No. 2, 2010,
pp. 129-140.
Figure 7. The number of rounds and dead nodes of three
algorithms. [10] J. Zhu, J. Li and H. Gao, “Tasks Allocation for Real-
Time Applications in Heterogeneous Sensor Networks
for Energy Minimization,” 8th ACIS International Con-
ference on Software Engineering, Artificial Intelligence,
Networking, and Parallel/Distributed Computing (SNPD
2007), Qingdao, 30 July-1 August 2007, pp. 20-25.
network. Therefore, it can not be applied to the water-
environment monitoring network, which is real-time sys-
tem with a large range to collect, transmit, analyze and
process water-environment parameters. In this paper, an
improved LEACH algorithm, LEACH-HEFA (LEACH-
Head Expected Frequency Appraisal) algorithm is pro-
posed based on the idea of cluster-head expected fre-
quency appraisal. If the node has higher residual energy,
it will have more probability to be selected as cluster-
head, which balances node energy effectively. Simula-
tion results show that LEACH-HEFA algorithm is suit-
able to the WMN. It also can equalize the energy con-
sumption of the nodes in the network and prolong the
network lifetime significantly.
[11] G. Anastasi, M. Conti, M. Di Francesco and A. Passarella,
“Energy Conservation in Wireless Sensor Networks,” A
Survey, Ad Hoc Networks, Vol. 7, No. 3, 2009, pp. 537-
568. doi:10.1016/j.adhoc.2008.06.003
[12] P. Tillapart, T. Thumthawatworn and P. Pakdeepinit,
“Method for Cluster Heads Select Ion in Wireless Sensor
Network,” Proceedings of the 2004 IEEE Aerospace
Conference, IEEE, Piscataway, 6-13 March 2004, pp.
3615-3623.
[13] B. Nazir and H. Hasbullah, “Energy Balanced Clustering
in Wireless Sensor Network,” 4th International Sympo-
sium on Information Technology 2010 (ITSim’10), Kuala
Lumpur, 15-17 June 2010.
6. References
[14] N. M. A. Latiff, C. Tsimenidis and B. S. Sharif, “Per-
formance Comparison of Optimization Algorithms for
Clustering in Wireless Sensor Networks,” MASS, Pisa,
8-11 October 2007, pp. 1-4.
[1] L. Fl, “Wireless Sensor Networks,” Smart Environments:
Technologies, Protocols, and Applications, Vol. 21, No. 2,
2004, pp. 1-18.
[2] P. Corke and T. Wark, “Environmental Wireless Sensor
Networks,” Proceedings of the IEEE, Vol. 98, No. 11,
2010, pp. 1903-1917. doi:10.1109/JPROC.2010.2068530
[15] A. Manjeshwar and D. P. Grawal, “TEEN: A Protocol for
Enhanced Efficiency in Wireless Sensor Networks,”
Proceedings of the 15th Parallel and Distributed Proc-
essing Symposium, IEEE Computer Society, San Fran-
cisco, 23-27 April 2001.
[3] X
. J. Yan, L. M. Lu and L. Z. Xu, “The Application of
Wireless Sensor Network in the Irrigation Area Auto-
matic System,” International Conference on Networks
Security, Wireless Communications and Trusted Com-
puting, Vol. 2, 25-26 April 2009, pp. 21-24.
[16] Y. Tao and Y. L. Zheng, “The Combination of the Opti-
mal Number of Cluster-Heads and Energy Adaptive
Cluster-Head Selection Algorithm in Wireless Sensor
Networks,” WiCOM, International Conference, Wuhan,
23-25 September 2011, pp. 1-4.
[4] T. H. Fan, L. Z. Xu, X. W. Zhang and H. B. Wang, “Re-
search and Design of a Node of Wireless Multimedia
Sensor Network,” Proceedings of the 5th International
Conference on Wireless Communications, Networking
and Mobile Computing, Piscataway, 24-26 September
2009.
[17] E. W. Heinz, “Application Specific Protocol Architec-
tures for Wireless Networks,” Massachusetts Institute of
Technology, Boston, 2000.
[18] T. Issariyakul and E. Hossain, “Introduction to Network
Simulator NS2,” Springer, Berlin, 2008.
[5] S. Guo, H. Zhang and H. Chen, “A Reservoir Flood Fore-
casting and Control System for China,” Hydrological Sci-
ences Journal, Vol. 49, No. 6, 2006, pp. 959-972.