Communications and Network, 2013, 5, 504-507
http://dx.doi.org/10.4236/cn.2013.53B2092 Published Online September 2013 (http://www.scirp.org/journal/cn)
A Chain Routing Algorithm Based on Traffic Prediction in
Wireless Sensor Networks
Yi Sun, Lei Xu, Xin Wu, Minxuan Shen
School of Electrical&Electronic Engineering, North China El ectric Power University, Beijing, China
Received May 2013
ABSTRACT
As a representative of chain-bas ed protocol in Wireless Sensor Networks (WSNs), EEPB is an elegant solution on
energy efficiency. However, in the latter part of the operation of the network, the re is still a big problem: reserving
energy of the node frequently presents the incapacity of directly communicating with the base station, at the same time
capacity of data acquisition and tr ansmission as normal nodes. If these nodes were selected as LEADER nodes, that will
accelerate the death process and unevenness of energy consumption distribution among nodes. This paper proposed a
chain routing algorithm based on traffic prediction model (CRTP). The novel algorithm designs a threshold judgment
method through introducing the traffic prediction model in the process of election of LEADER node. The process can
be dynamically adjusted according to the flow fore ca s ting. Therefore, this algorithm lets the energy consumption tend-
ing to keep at same level. Simulation results show that CRTP has superior performance over EEPB in terms of b alan ced
network energy consumption and the prolonged network life.
Keywords: Wireless Sensor Networks; A Chain Routing Algorithm; LEADER Node; Traffic Prediction Model
1. Introduction
Wireless Sensor Networks (WSNs) is a technology com-
bined with computer, micro sensors and wireless com-
munication [1]. The self organization characteristic, also
the reliability, dynamicity and anti-destroying ability, make
WSNs suitable for battlefield target positioning [2], phy-
siological data collection [3], intelligent transportatio n
system [4] and ocean exploration [5], etc. [6].
Energy problem is one of the key problems in WSNs
[7]. Because battery capacity is low and no t easy to
change, cognitive nodes should be scraped once energy
depleted. Therefo re, improving energy efficiency, balanc-
ing the node energy consumption and prolonging net-
work life time have become a judgment in WSNs routing
protocol [8].
Chain routing algorithms characterized by energy effi-
cient have been proposed in recent years. PEGAS IS [9]
uses the greedy algorithm to build the chain, as a typical
algorithm th a t shortens the commutation distance between
the nodes. However, PEGASIS has some inherent flaws:
there are large numbers of long chains between neighbor
nodes that increases the energy consumption in data trans-
mission. The method of rotating the LEADER of the
chain among the nodes will result in unbalanced energy
consumption of each node. In recent years, international
and domestic academics have put forward improved al-
gorithms from different angles to avoid long chains [10-
14]. When these algorithms select the LEADER of the
chain, they only consider the factor of the residual energy
or the same as PEGASIS, and still can’t avoid the prob-
lem of inconsistent energy consumption of the nodes. [15]
avoids long chains between neighbor nodes by employ-
ing a distance threshold; through comprehensively taking
into account of node residu al energy and the distance
between the nodes and base station, selecting the LEADER
of the chains. EEPB algori thm makes a better performance
in balancing of node energy consumption and prolonging
the network life cycle. However, after running a long
time, nodes in netw ork are not strong enough to send the
fusion of data to base station, but still can be used as data
acquisition or transmission nodes among chains. If these
nodes were chosen as the LEADER of the chain, it would
cause the waste of node energy, not only weaken the
network robustness but also shorten sur- vival time. This
situation is particularly s e r ious in the monitoring area far
away from base station.
This paper proposes a chain routing algorithm based
on traffic prediction, CRTP. This model was applied to
the selection of the LEADER, implementing replacement
of the LEADER through forecast. At the end of this pa-
per, simulation results show that, CRTP makes better per-
formance in terms of balanced network energy consump-

Y. SUN ET AL.
505
tion and prolonged the network life .
2. Traffic Prediction Model
The nodes in Wireless Senso r Networks periodically sen-
sor monitoring area and transmit the collected data to the
remote Sink. ARMA model can effectively analyze the
serial correlation of these stable data sequence, so the
ARMA prediction model is applied to forecast network
traffic in this paper.
Suppose that the raw data flow sequence is
'' ' '
01
,,,,,
in
XX X X
, taking the method of differencing
or logarithm, we get a smooth sequence
01
,,,,,
in
XX X X
. This algorithm uses ARMA (2, 1)
to predict the traffic. The model can be described as fol-
lows:
(1)
(2)
(3)
B
is backward shift operator,
i
a
is flat noise.
1
ϕ
,
2
ϕ
,
1
θ
,
2
a
σ
(flat noise variance) are the estimated pa-
rameters. Since the sensor node is limited by its compu-
ting power, we get the value of
1
ϕ
∧
,
2
ϕ
∧
,
1
θ
∧
,
2
a
σ
∧
through the method of least squares estimation. ARMA
fitting model is:
11 2211tttt t
X XXaa ϕϕ θ
∧∧ ∧
−− −
= ++−
(4)
Furthermore, we use inverse function to carry out
one-step prediction. The ARMA inverse function
12
,,,
n
II I
are:
1 11
22 11
31
( 3)
j
I
II
II j
ϕθ
ϕθ
θ
∧∧
∧∧
∧

= −


= −


=> 


(5)
One-step prediction model is:
1
1
(1) m
tjt j
j
X IX
∧
+−
=
=∑
(6)
Where m is m times before the
t
X
observations, it
can be decided in accordance with the requirements of
the prediction accuracy values. Multi-step predictive mod-
el is:
12
( )(1)(2)
tt t
Xl XlXl ϕϕ
∧∧∧∧ ∧
= −+−
(7)
We use Matlab 7.0 to simulate. Figure 1 show s a real
traffic flowing through a sensor node during the 150 s of
sensor network operation. Its fitting model is:
12 1
0.86579 0.073560.68954
tttt t
XXXa a
−− −
= −+−
(8)
Further, One-step prediction model is:
3
1
1
(1)
tjt j
j
X IX
+−
=
=
∑
(9)
Multi-step predictive model is:
()0.86579 (1)0.07356 (2)
tt t
Xl XlXl
∧∧ ∧
=−− −
(10)
Starting from any time in the 150 s ( round), its esti-
mated value can be calculated by the use of this model
every second, its chart of one-step prediction shows in
Figure 2. From above figure, o ne -step prediction curve
is similar with the raw data flow. This because the AR-
MA is a short model, its related structure appears expo-
nential decay and decay rate is faster than actual obser-
vation value. Therefore, one step prediction could have
better prediction accuracy.
3. CRTP Algorithm
Assume a random distrib u tion of sensor nodes in a square
Figure 1. Example of a real flowing.
Figure 2. One-step predicti on .
() ()
ii
BX Ba ϕθ =
2
12
() 1B BB ϕ ϕϕ =−−
1
() 1BB θθ = −

Y. SUN ET AL.
506
monitoring area, and this sensor networks have the nature
as follows:
• The location of the base station is fixed, which is far
from the monitoring area. The base station has a strong
computing and storage capability, and unlimited ener-
gy.
• All sensor nodes are immobile, homogeneous, the same
initial energy value.
• According to the receiver’s distance nodes can con-
trol the ir transmit power for different transmission
ranges.
• All nodes can be informed the coordinates of their
location.
3.1. Chain-Building Stage
Similar with EEPB chain-building method, CRTP also
starts a chain from the nodes which is the furthest from
the base station. In order to determine whether the chain
is long, we set a distance threshold, in terms of
threshold
d
.
If
i threshold
dd≤
, said that the chain between node
1i+
and node
i
is not a long chain. Then the node
1i+
join the chain by directly connected to the node
i
. If
i threshold
dd>
, said that the chain between node
1i+
and node
i
is a long chain. Here, node
1i+
can’t
directly connect with the node
i
, node
1i+
will find
the nearest node from the chain.
3.2. LEADER Node Selection Algorithm Based
on the ARMA Model
LEADER node selection in EEPB considers the residual
energy of nodes and the distance from nodes to the base
station. Under the condition that nodes’ residual energy
is equal, EEPB algorithm is priority to select nodes near
the base station as the LEADER node, in order to save
energy when transmitting data to the base station. Simi-
larly, under the condition that distances from nodes to the
base station are the same, EEPB algorithm is priority to
select nodes with more residual energy as the LEADER
node, in order to avoid nodes with less residual energy to
death.
In the LEADER node selection based on ARMA mod-
el, when the energy consumption exceeds the threshold,
the node broadcasts its withdrawing the competition of
LEADER node in this round to neighbors, neighbor
nodes updates its routing table after receiving the message.
The key issue is to design a judg mental forecasting method
based on threshold. Suppose the threshold is
Max
,the
probability that the prediction exceeds the threshold val-
ue in the L-step is
12
()( ()|,,,,)
tt tttm
Ply tMaxXXXX
−− −
= >
(11)
According to the Equation (8),
t
X
is conditioned by
t
a
, if
t
a
is normal distribution and so is
t
X
. Stan-
dardize the Equation (7), we get
() 1()
() 1
1 exp()
2 ()
2
t tl
xt
P lPXMax
MaxXl dx
l σ
π
+
∧
−∞
=−≤
−
=−−
∫
(12)
4. The Simulation and Analysis
In order to verify the proposed idea, we use MATLAB to
simulate and compare EEPB and the improved routing
algorithm CRTP. The wireless commucation energy cost
model is the Heinzelman model. Simulation environment
goes as follows (Table1).
First of all, let’s analyze the number of the survival
nodes: the number is an important indicator of the energy
efficiency. From Figure 3, we know that 1) the first dead
node emerges at the 900r in EEPB but at the 1600r in
CRTP, improve 77.8%; 2) attenuation curve in CRTP is
faster than EEPB; 3) the slope of CRTP’s curve is greater
than EEPB after 1900r. This is because as the network
round increases unceasingly, the LEADER selection ac-
cording to flow prediction is more reasonable.
Figure 4 is a comparison between our algorithm and
EEPB in average resi dual energy each round, we can get
Table 1. Table type styles (Table caption is indispensable).
Parameters Value
Network Field 100 m × 100 m
Nodes numbers 100
Sink coordinates (50,250)
Nodes Initial energy 1.0J
Eelec 50 nJ/bit
Efs 100 pJ/bit/m 2
Emp 0.0013 pJ/bit/m4
Packet length 3000 bit
α 1.2
Figure 3. Life time of the network.

Y. SUN ET AL.
507
Figure 4. Average residual energy of the network.
that the average residual energy in improved algorithm is
more than EEPB as network running, at the same time
the network energy cost is lower. That’s because we take
a more reasonable method to select the LEADER node in
a chain and take into account the energy balance when
we established routing link, so life cycle of the network
is extended.
5. Conclusion
This paper proposes a chain routing algorithm based on
ARMA traffic prediction for nodes’ premature “death”. It
introduces ARMA prediction model into the LEADER
node reelection in EEPB. Therefore it has not only avoided
LEADER premature “death” because of the used-up energy,
but also avoided the network topology reconstruction as
well as the short life of the death of LEADER. Experi-
mental results show that CRTP has a better performance
than EEPB on balancing energy consumption and pro-
longing lifetime of Wireless Sensor Networks (WSNs).
6. Acknowledgements
The work was supported by National Science and Tech-
nology Major Project of China (No. 2010ZX03006-005-01)
and the Fundamental Research F unds for the Central
Universities (12QX 12).
REFERENCES
[1] X.-L. Zhao, X.-L. Li and K.-Q. Li, “LEACH-Based Pro-
tocol Difference of Cluster-Based Routing Algorithm,”
Computer Engineering and Applications, 2012.
[2] F. Viani, P. Rocca, G. Oliveri, et al., “Localization,
Tracking, and Imaging of Targets in Wireless Sensor
Networks: An Invited Review,” Radio Science, Vol. 46,
No. 5, 2011. http://dx.doi.org/10.1029/2010RS004561
[3] E. E. Emeka and O. F. Abraham, “A Survey of System
Architecture Requirements for Health Care-Based Wire-
less Sensor Networks,” Sensors, Vol. 11, No. 5, 2011, pp.
4875-4898.
[4] L. Fernando, G. Antonio-Javier, G. Felipe, et al., “A
Comprehensive Approach to WSN-Based ITS Applica-
tions: A Survey,” Sensors, Vol. 11, No. 11, 2011, pp.
10220-10265.
[5] A. Cristina, S. Pedro, I. Andrés, et al., “Wireless Sensor
Networks for Oceanographic Monitoring: A Systematic
Review,” Sensors, Vol. 10, No. 7, 2010, pp. 6948-6968.
http://dx.doi.org/10.3390/s100706948
[6] Z.-H. Qian and Y.-J. Wang, “Internet of Things-Oriented
Wireless Sensor Networks Review,” Journal of Electron-
ics & Information Technology, Vol. 35, No. 1, 2013, pp.
215-227.
[7] J.-H. Han, X. Ding, L. Shi, D. Han and Z.-C. Wei, “Re-
search on the Time-Varying Charging and Dyna mic Data
Routing Strategy for Rechargeable Wireless Sensor Net-
works,” Journal on Communications, Vol. 33, No. 12,
2012, pp. 1-10.
[8] Y.-H. Luo, S.-Q. Chen and J.-X. Wang, “The Ener-
gy-Efficient Routing Algorithm in Mobile Ad-Hoc Net-
works,” Engineering and Application of Computer, 2004,
Vol. 36, pp. 15-21.
[9] S Lindsey and C. Raghavendra, “PEGASIS: Power-Effi-
cient Gathering in Sensor Information Systems,” Pro-
ceedings of IEEE Aerospace Conference, Big Sky, Mon-
tana, 2002, pp. 1125-1130.
[10] K.M. Du, J. Wu and D. Zhou, “Chain-Based Protocols for
Data Broadcasting and Gathering in the Sensor Networks,”
Proceedings of Parallel and Distributed Processing
Symposium, Nice, 2003, pp. 1926-1933.
[11] S. L. Hu, Y. Zhang, X. Y. Jin, et al., “Improvement of
PEGASIS Algorithm in Wireless Sensor Networks Using
GA,” Journal of Jiangnan University (Natural Science
Edition), Vol. 7, No. 4, 2008, pp. 0420-0424
[12] L. P. Wang and Z. Cai, “Improved Algorithm of PEGA-
SIS Protocol Introducing Double Cluster Heads in Wire-
less Sensor Network,” 2010 International Conference on
Computer, Mechatronics, Control and Electronic Engi-
neering (CMCE), Changchun, 2010, pp. 148-151.
[13] W.J. Guo, W. Zhang and G. Lu, “PEGASIS Protocol in
Wireless Sensor Network Based on an Improved Ant Co-
lony Algorithm,” The 2nd International Workshop on
Education Technology and Computer Science, Wuhan,
2010.
[14] Zhang Z., Yan L.-S., Pan W., et al., “Routing protocol
based on cluster-head-chaining incorporating LEACH
and PEGASIS,” Chinese Journal of Sensors and Actua-
tors, Vol. 23, No. 8, 2010, pp. 1173-1178.
[15] Y.-C. Yu and G. We i, “An Improved PEGASIS Algo-
rithm in Wireless Sensor Network,” ACTA Electronica
Sinica, Vol. 36, No. 7, 2008, pp. 1309-1313.