Communications and Network, 2013, 5, 508-511
http://dx.doi.org/10.4236/cn.2013.53B2093 Published Online September 2013 (http://www.scirp.org/journal/cn)
Research on Dynamic Clustering Routing Considering
Node Load for Wireless Sensor Networks*
Yi Sun, Can Cui, Shanshan Ke, Jun Lu
School of Electrical and Electronic Engineering, North China Electric Power University, Beijing, China
Received May 2013
ABSTRACT
Aiming at the problem that node load is rarely considered in existing clustering routing algorithm for Wireless Sensor
Networks (WSNs), a dynamic clustering routing algorithm for WSN is presen ted in this paper called DCRCL (Dynamic
Clustering Routing Considering Load). This algorithm is comprised of three phases including cluster head (CH) selec-
tion, cluster setup and inter-cluster routing. First, the CHs are selected based on residual energy and node load. Then the
non-CH nodes choose a cluster by comparing the cost function of its neighbor CHs. At last, each CH communicates
with base station by u sing multi-hop communication. The simulation results show that comparing with the existing one,
the techniques life cycle and date volume of the network are increased by 30.7 percent and 29.8 percent respectively by
using the proposed algorithm DCRCL.
Keywords: Wireless Sensor Network; Dynamic Routing; Clustering Algorithm; Node Load
1. Introduction
As Wireless Sensor Network (WSN) is a kind of energy
constrained multi-hop self-organizing networks, how to
save energy and maximize life cycle is the core problem
of WSN [1-3]. In cluster based WSN, the network is di-
vided into distinct clusters with a single leader called
cluster head (CH). CHs are either selected among normal
senor nodes or in some case some high energy nodes
called gateways which are deployed as CHs [4]. CHs
transmit all the local data from normal nodes to base sta-
tion (BS), so that normal nodes use less energy while
CHs consume more. To prevent the death of CHs from
extra load, the CH rotation mechanism is used to equili-
brium energy consumption of the network by changing
CHs dynamically in existing algorithm called LEACH
[5]. However, the main disadvantage of LEACH is that a
sensor node with very low energy may be selected as a
CH and the CHs send the packet to BS directly in single
hop communication. Thus, this method increases the
energy consumption of the CHs and reduces the network
life cycle.
A large number of algorithms have been developed to
improve LEACH namely PEGASIS [6], HEED [7] etc.
Compared to LEACH, PEGASIS improves network life-
time, but its data delay is significantly high and it is un-
suitable for large-sized networks. The HEED periodically
selects CHs based on the node’s residual energy and prox-
imity measure of the neighbor nodes or node degree. In
MRPUC [8], the authors design multi-hop routing and
unequal clustering algorithm using residual energies of
all sensor nodes and distance between sensor nodes to the
BS to extend network lifetime. Although these algorithms
can improve the network life cycle, the load problem is
not considered. As a result all the data will be transmitted
to the BS, the nearer from the node to the BS, the higher
load it will have. Higher load means forwarding data
more frequently, and consuming more energy. What’s
more, unbalanced load also leads to unbalanced energy
consumption and the decrease of network life cycle.
In this paper, we propose a dynamic clustering routing
algorithm which considers the load problem. This algo-
rithm contains three phases namely CH selection, cluster
setup and inter-cluster routing . In Section 2, these phases
are introduced in detail. Simulation results are given in
Section 3 followed by the conclusion in Section 4.
2. DCRCL Algorithm D escrip tion
2.1. Cluster Head Selection
The general factors considered in CH selection are node
residual energy, distance from CH to BS, distribution of
CHs, communication cost within the cluster and so on. In
DCRCL, the threshold function is optimized by consi-
*The work was
supported by a grant from the National Science and
Technology M ajor Project of China (No.2010ZX03006-005-01).

Y. SUN ET AL.
509
dering residual energy and node load.
In CH selection phase, every sensor node is given a
random number from 0 to 1. The node will be candidate
CH if the random number is less than the threshold. The
optimized threshold function is shown as follow:
(1)
Where, p is the probability of a node chosen to be CH,
r is the present round, G is a gather of nodes which were
not chosen to be CH in the past 1/p round. Eres and Eini
mean the residual energy and initial energy of nodes, η is
load factor and k is normalization coefficient, λ1 and λ2
are weight coefficients.
The optimized function retains the advantage in LEACH
that CHs are rotated by increasing the probability of be-
ing candidate CH for unselected nodes. At the same time,
it balances energy and load to make the nodes with high-
er residual energy and lower load easier to be candidate
CH.
In the multi-hop network with a single BS, the load of
CH contains not only the communication with nodes in-
side, also the channel utilize when CH transmit data fro m
oth er CH s to BS [9 ,10]. The load considered in this paper
is the latter.
As shown in Figure 1, the load of node A is the data
comes from the nodes in dash area, indicated by η. In
other words
(2)
Where, n is the node number in dash area, q is the
probability that a node transmit data in every moment,
pk_size is the size of every packet which is a same value
for every node in the network. Suppose that nodes are
distributed uniform in the network, so
Figure 1. Node Load Model.
Where, N is total node number, S0 is the coverage of
the dash area and S is total coverage of the network.
On the base of the distance from A to BS namely di,
communication radius R and network range dm, we can
get
(3)
(4)
(5)
So
(6)
It is observed that node load is related to communica-
tion radius and the distance from node to BS.
2.2. Cluster Setup
In the cluster setup phase of DCRCL, CH competitive
mechanism is introduced to avoid the unbalanced distri-
bution of CHs in LEACH. After being a candidate CH, a
node competes with other candidates in its communica-
tion range R, the one who has most residual energy is the
winner. R is given as follow
(7)
where, di, dm, Eres, Eini are defined above. Rmin is the
min imum competition radius, α1 and α2 are weight coef-
ficients and α1 + α2=1.
Equation (7) shows that competition radius of CH and
nodes in the cluster will decrease when the CH is nearer
to BS and owns less residual energy. Considering that
further CHs need close ones to transmit their data, the
close CHs will have enough energy and free load to en-
sure the stability of the network in this way.
By Equation (7), it is known that .
So θ can be approximated to a fixed value. Fused with
Equation (5), we can see that
Then, the selected CHs broadcast cluster request signal
to the nodes in their communication range. Normal nodes
choose which cluster to join in by using energy cost
function shown as follow
(8)
where, d(i, j) is the distance from node i to CHj, dj is the
distance from CHj to BS, Ei and Ej mean the residual
energy of node i and CHj. β1 and β2 are weight coeffi-
cients and β1 + β2=1.

Y. SUN ET AL.
510
As the Equation (8) shows, normal nodes prefer to
cooperate with the CH which is closer to BS and owns
more residual energy. The choose process is shown in
Figure 2.
2.3. Inter-Cluster Routing
The model that data is transmitted directly from CHs to
BS, as known in LEACH, usually results in short life
cycles of CHs and the network. In the proposed algo-
rithm DCRCL, an energy balanced multi-hop communi-
cation model is established to use network energy more
efficiently. The attribute equilibrium function for inter-
cluster routing contains several factors namely residual
energy, CH load and inside node number. The specific
equation is as follows
where, NEi, NLi, NCi are uniformed CH residual energy,
CH load and inside node number. ω1, ω2 and ω3 are
weight coefficients and ω1 + ω2 + ω3 = 1.
CHs send routing r equest signal RR EQ to the n eighbor
CH which has higher attribute equilibrium value than the
average of all neighbors by computing the equilibrium
function. At the same time, the link infor mation in RREQ
is updated. The information will be used by the destina-
tion node to choose a best link and send routing reply
signal RREP, as shown in Figure 3.
Figure 2. Cluster Setup Process.
(a) (b)
Figure 3. (a) Routing Request; (b) Routing Reply. Inter-
cluster R ou t i ng Process.
When the in ter-cluster routing is established, CHs record
the link and compute the optimized transmission power
according to the distance to next hop. The link will be
used abidingly until next CH selection phase comes.
3. Experimental Results
Extensive experiments are performed for the proposed
algorithm on MATLAB7.0 with the following experi-
mental set up. All sensor nodes are distributed random in
a 200 m × 200 m area, all nodes are immobile with the
same initial energy 0.1J. Nodes in cluster use TDMA
mechanism on MAC layer and the communication mode
is two-way. Time cycle of simulation is 300 rounds. For
the sake of comparison, we also run the LEACH and
AODV.
In Figure 4, the node number is 200 and the size of
packet is 500 bit. We sampled the results every 15 rounds.
As shown in Figure 4(a) that in the case of DCRCL, all
nodes are inactive after 200 rounds, the network life
cycle is increased by 566.7 percent and 33.3 percent
compared with 30 rounds of AODV and 150 rounds of
LEACH. Figure 4(b) shows that the data received by BS
in DCRCL is 42.8 percent more than LEACH.
(a)
(b)
Figure 4. (a) Active Nodes; (b) Data Received by BS.

Y. SUN ET AL.
511
Considering the generalization, more experiments are
performed by using different number of nodes from 50 to
500. It is shown in Figure5 that the proposed algorithm
in this paper also performed well for large scale networks.
Figure 5(a) shows that average life cycle of DCRCL is
30.7 percent higher than LEACH and the curve is smoother
than LEACH which means our method works more stea-
dily. In Figure 5(b), the average data received by BS in
DCRCL is 29.8 percent higher than LEACH, and get to
the highest 47.6 percent when the node number is 450.
4. Conclusion
In this paper, a dynamic clustering routing algorithm con-
sidering node load for wireless sensor networks is pre-
sented. In which, CHs are selected by considering resi-
dual energy and node load, a cost function based on ener-
gy and distance is used to set up the cluster and CHs use
multi-hop inter-cluster routing model which is established
by the attribute equilibrium function. The experiment re-
sults show that the proposed algorithm is more efficient
with respect to network life cycle and network data than
LEACH and AODV.
(a)
(b)
Figure 5. (a) Life cycle; (b) Date Received by BS. Compari-
son between DCRCL, LEACH and AODV for different
node number.
REFERENCES
[1] T. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E.
Cayirci, “Wireless Sensor Networks: A Survey,” Com-
puter Networks, Vol. 38, No. 4, 2002, pp. 393-422.
[2] G. Gupta and M. Younis, “Load-Balanced Clustering of
Wireless Sensor Networks,” IEEE International Confe-
rence on Communications, Vol. 3, 2003, pp. 1848-1852.
[3] P. Kuila and P. K. Jana, “An Energy Balanced Distributed
Clustering and Routing Algorithm for Wireless Sensor
Networks,” IEEE International Conference on Parallel,
Distributed and Grid Computing, 2012, pp. 200-225.
[4] J. G. Yu, “A Cluster-Based Routing Protocol for Wireless
Sensor Networks with Non Uniform Node Distribution,”
Journal of Electronics and Communications, Vol. 66,
2012, pp. 54-61.
[5] W. B. Heinzelman, A. P. Chandrakasan and H. Bala-
krishnan, “An Application Specific Protocol Architecture
for Wireless Microsensor Networks,” IEEE Transactions
on Wireless Communications, Vol. 1, No. 4, 2002, pp.
660-670. http://dx.doi.org/10.1109/TWC.2002.804190
[6] S. Lindsey and C. S. Raghavendra, “PEGASIS: Power
Efficient Gathering in Sensor Information Systems,”
IEEE Transactions on Parallel and Distributed Systems,
Vol. 13, No. 9, 2002, pp. 924-930.
http://dx.doi.org/10.1109/TPDS.2002.1036066
[7] O. Younis and S. Fahmy, “HEED: A Hybrid, Ener-
gy-Efficient, Distributed Clustering Approach for Ad Hoc
Sensor Networks,” IEEE Transactions on Mobile Com-
puting, Vol. 3, 2004, pp. 366-379.
http://dx.doi.org/10.1109/TMC.2004.41
[8] B. C. Gong, L. Y. Li, S. R. Wang and X. J. Zhou, “Mul-
tihop Routing Protocol with Unequal Clustering for
Wireless Sensor Networks,” Colloquium on Computing,
Communication, Cont rol, and Management, Vol. 2, 2008,
pp. 552-556.
[9] P. Kuila and P. K. lana, “Improved Load Balanced Clus-
tering Algorithm for Wireless Sensor Networks,” Pro-
ceedings of the 2011 International Conference on Ad-
vanced Computing, Networking and Security, 2012, pp.
399-404.
[10] C. Petrioli, M. Nati, P. Casari, M. Zorzi and S. Basagni,
“ALBA-R: Load-Balancing Geographic Routing Around
Connectivity Holes in Wireless Sensor Networks,” IEEE
Transactions on Parallel and Distributed Systems, 2013,
pp. 1-11.