Wireless Se nsor Network, 2011, 3, 295-299
doi:10.4236/wsn.2011.38030 Published Online August 2011 (http://www.SciRP.org/journal/wsn)
Copyright © 2011 SciRes. WSN
Sensor Scheduling Algorithm Target Tracking-Orien ted
Dong Mei Yan, Jin Kuan Wang
School of Information Science and EngineeringNortheastern University, ShenYang, Liaoning Province, China
E-mail: dmy_125@163.com
Received June 17, 2011; revised July 21, 2011; accepted July 31, 2011
Abstract
Target tracking is a challenging problem for wireless sensor networks because sensor nodes carry limited
power recourses. Thus, scheduling of sensor nodes must focus on power conservation. It is possible to extend
the lifetime of a network by dynamic clustering and duty cycling. Sensor Scheduling Algorithm Target
Tracking-oriented is proposed in this paper. When the target occurs in the sensing filed, cluster and duty
cycling algorithm is executed t o schedule sensor node to perform tracking ta sk. Wi th t he tar get movi ng, only
one cluster is active, the others are in sleep state, which is efficient for conserving sensor nodes’ limited
power. Using dynamic cluster and duty cycling technology can allocate efficiently sensor nodes’ limited
energy and perform tasks coordinately.
Keywords: Wireless Sensor Network, Sensor Scheduling, Target Tracking, Collaborative Signal Processing,
Dynamic Clustering
1. Introduction
Wire less sensors network is becoming an important topic
of research with development of digital circuitry, wire-
less communications and Micro Electro Mechanical Sys-
tems, whic h i s composed o f many tiny sensor nodes built
in one or more sensors, computation and communication
unit, and a power supply. Sensor nodes may be deployed
to perform measurements in environments including in-
strumentation of rotating machinery and so on or moni-
tor ing the movements of s mall animal [1].
Wire less sensor net work is a power-limited a nd multi-
user distributed s ystem, so it is neces sary to make sensor
nodes operate collaboratively. CSP (collaborative signal
processing) is a new research field in wireless sensor
networks aiming at developing new algorithms for
processing massive information sensed by sensor nodes.
It is critical for wireless sensor network using CSP to
dynamically allocate resources among sensor nodes [2].
A typical application in wireless sensor networks is
targe t trac king, such a s sec urit y survei llance a nd wildli fe
habitat monitoring. Target tracking contains a lot of col-
laboration between individual sensors to perform com-
plex signal processing algorithms such as Kalman filter-
ing, Bayesian data fusion and other optimal algorithm.
Thus, energy management is a key task during target
moving, which affects energy consumption and network
lifetime. Cooperative strategies for target tracking are
based on the follo wing idea: with target moving, a set o f
nodes are selected to perform task, and the other nodes
can be turned off for saving energy. The node selection is
based on special algorithm considering nodes’ residual
energy, distance form target and so on. Thus, considera-
ble energy can be potentially conserved [3,4].
Xu Y et al. proposed a geographical adaptive fidelity
(GAF) algorithm that keeps energy by identifying nodes
equivalent from a routing perspective. GAF can keep a
constant level of fidelity by turning off unnecessary
nodes. Simulation shows that network lifetime increases
proportionally to node density. GAF can be used for ex-
tending network lifetime by exploiting redundancy in
order to keep energy [5].
Jianyong Lin et al. presented an adaptive multisensor
scheduling scheme for target tracking in Wireless Sensor
Network, which is divided into three steps. First, the
sampling interval is set by a predetermined tracking ac-
curacy value. Then, some sensors are chosen to form a
cluster for performing task. Last, the cluster head is de-
termined based on the predicted energy consumption. A
Monte Carlo method is employed to predict approx-
imately the target state. The proposed scheme can not
only reduce the energy consumption and improves the
tracking reliability, but also resist the uncertainty of the
process noise form simulation results [6].
In this paper, we propose sensor scheduling algorithm
target tracking -oriented. Deployment of sensor nodes ad-
D. M. YAN ET AL.
Copyright © 2011 S ciRes. WSN
296
opts honeycomb structure to increase one-hop coverage
area. When the target occurs in the sensing filed, cluster
and duty cycling algorithm is executed to schedule sensor
node to perform tracking task. The Kalman filter is em-
ployed to estimate next possible location of target. With the
target moving, only one cluster is active, the other are in
sleep state, which is efficient for conserving sensor nodes’
limited power. Using dynamic cluster and duty cycling
technology can make good use of each sensor nodes’ li-
mited energy an d perfo rm task s coordinately.
2. Prolonging the Lifetime of Sensor
Network
2.1. Energy Consumption of Sensor Nodes
A sensor node consists of a sensing unit, a processing
unit, a transceiver unit and a power unit as shown in
Figure 1, which a limited energy (< 0.5 Ah, 1.2 V).
Moreover, sometimes it may be impossible to replace
power resources. So, sensor node lifetime is mainly de-
cided by battery lifetime. Power conservation and power
management of sensor nodes is a key problem for wire-
less se nsor network.
Energy consumption of node subsystems is shown in
Figure 2 [7]. There are four possible states for sensor
node’s radio to select: transmit, receive, idle, or sleep. It
is obtained that the: Energy Consumption of Sensor
Node’s radio component is:
TX RX IDLESL
EEEE≈ ≈>>
Thus, it is j udicious to c omplete ly shut do wn the rad io
when it is not transmitting or receiving data in order to
keep power.
2.2. Clustering of Sensor Nodes
Sensor nodes in WSN can be divided into some groups
called clusters to realize data gather with efficient net-
work o rganiza tion, i n which h as a cluste r head ( CH) and
a number of member nodes. Clustering produces a two-
layer hierarchy in WSN. Cluster heads (CHs) belong to
Sensor
ADC
Processing Unit
storage
Transceiver
Sensor Unit
Proc essor
Figure 1. The compone nts of a sens or node.
5
0
10
15
20
Power (mW)
Sens or
CPU
TX
RX
Idle
Sleep
Radio
Figure 2. Energy c o nsumption of sensor no de s.
the higher layer while member nodes the lower layer.
The members of a cluster can communicate with their
CH directly. A CH can forward the fused data to the cen-
tral base statio n through other CHs.
The member nodes send their data to the respective
CHs. Then t he CHs f use the d a ta and tr a ns mit te d t he m to
the base station through other CHs. CHs may lose more
energy because of transmitting data over longer dis-
tances.
2.3. Duty Cycling
Duty cycling is very important in wireless sensor for
conserving energy, which makes the radio transceiver be
in the sleep mode while communication is not required.
Thus, sensor nodes change be tween active and sleep state
based on net work activity, which is known as duty cycl-
ing. Duty is cycling defined as time slots that nodes are
active during their lifetime. Fo r target tracking, since
sensor nodes perform a task cooperatively, it is necessary
to coordinate their sleep/wakeup times. A sleep/wakeup
scheduling algorithm is employed to decide state trans-
formation (active to sleep and vice versa) of sensor nodes.
3. Deployment of Sensor Nodes
Different shapes to forming nod e into clusters have been
proposed for deploying nodes, such as circle, quadrila-
teral, and hexagon. The honeycomb is often used be-
cause it corresponds to the shape of the radio transmis-
sion range, which may result in overlapping between
clusters or uncovered areas. The hexagon is an ideal
shape for clustering a large area into adjacent, no over-
lapping areas, which can be proved as follows.
Quadrilateral structure for parting sensing region is
sho wn in Figure 3, in which no de s a re d ivided into small
cluster. The clusters are defined as that two neighboring
clusters A and B, where all nodes in A can communicate
with all nodes in B and vice versa.
Note that transmitting range is R, so the distance be-
tween two possible farthest nodes in any two neighbor-
ing clusters, for example node 1 in cluster A and node 2
in cluster B (Figure 3), must not be larger than R. Based
D. M. YAN ET AL.
Copyright © 2011 S ciRes. WSN
297
on mar ked va lue i n Figure 3, functions can be expressed
as follow:
( )
2
22
2a aR+≤
(1)
22
2ar=
(2)
5aR
(3)
Honeycomb structure for parting sensing region is
shown in Figure 4; functions can be expressed based on
marked value in Figure 4.
( )
2
22
23b bR+≤
(4)
13bR
(5)
Thus, area of quadrilateral and each honeycomb can
be expressed by:
22 2
5 0.2
q
SaR R= ==
(6)
2 22
33
3sin60 0.2
26
h
Sb RR= °=≈
(7)
Note that the one-hop coverage area of quadrilateral
structure is Sqc= 5Sq = R2 and the one-hop coverage area
of ho ne ycomb struct ur e fo r wa r d ing i s Shc = 7 Sh ≈ 1.4 R2,
so the one-hop coverage area of honeycomb structure is
about 40% larger than that of quadrilateral structure.
2
m
n
a
1
A
B
R
Figure 3. Quadrilateral structure.
R
b
B
A
Figure 4. Honeycomb structure.
4. Sensor Scheduling During Target Moving
4.1. Dynamic Clustering
Dynamic cluster architectures means that clusters will be
formed with certain events of interest coming, such as
target appear. If a sensor node with sufficient energy and
computational power detects signals of interest, it would
be selected as a CH (cluster head). Sensors near to the
active CH are invited to join the cluster and send their
information to the CH.
At any ti me instant only one cluster is active with tar-
get mov i ng, in whic h s e nso rs nod e s ar e in the ac ti ve st ate
and all other sensors are shut down (Figure 5) Sensor
scheduling mechanism properly adapt to a scalable and
dynamic network topology. The network activity can be
set in time slots. Then, active sensor nodes are selected at
the beginning of time slot corresponding to trajectory of
target. Active node selection is chosen according to the
conne ctivity, power effi ciency and so on.
Sensor scheduling problem is employed to select sen-
sors to form cluster dynamically in order to optimize the
tracking performance of the targets. The sensor nodes
being activated at time ti must be chosen at or before
time ti TK, where TK is the time needed to select and
activate a sensor cluster.
4.2. Maximum Entropy Clustering
The objective of a clustering algorithm is the assignment
of a set of M feature vectors xi X into k clusters,
which are represented by the prototypes cj C. The
certainty of the assignment of the feature vectors xi X
into various clusters is measured by the membership
functions uij [0, l], j = 1, 2, k, (1
i
ij
ij u=
).
For a given set of members hip function s, the distor tion
between the feature vectors xi X and the prototypes cj
C is measured by[13-15].
( )( )
11
1
,,
Mk
ijiiji j
ij
DuUcCudxc
M
= =
∈ ∈=∑∑
(8)
cluster
sensor node
moving target
active
Figure 5. Dynamic cluster with target movi ng .
D. M. YAN ET AL.
Copyright © 2011 S ciRes. WSN
298
where d (xi, cj) is a metric of the distance between the
feature vector xi X and the prototype cjC,
( )
2
ii ii
dxc xc−=−
(9)
In the maximum uncertainty or minimum selectivity
phase, the clustering process is based on the minimiza-
tion of the negative entropy, g iven by
( )
11
* log
Mk
ijij ij
ij
Eu Uuu
= =
∈=
∑∑
(10)
Assume that the sensor network including k numbers
of sensor nodes can be divided into M numbers of clus-
ters, and the matrix of cluster head is
{ }
12
HH ,H,,H
z
=
and uij is the degree of member-
ship of node xi in cluster j.
( )
2
11 11
1
, log
ij
Mk Mk
ijij ij
ij ij
I uHuduu
λ
= == =
= +
∑∑ ∑∑
(11)
( )
1
1
ij ij
c
dd
l
ij k
ue e
λλ
−−
+
=
=
(12)
( )( )( )
11 1
11
kk
ll l
iij jij
jj
Hux u
++ +
= =
=∑∑
(13)
The Cl ustering process i s descr i bed as fol l ows:
1) Initialization of cluster head is assu med a s
( )( )( )()
{ }
0 000
12
, ,,c
H HHH=
2) Defining convergence threshold ε
3) Updating uij and cluster head with expressions (12)
and (13) until
()( )
( )
1
max ll
ii
HH
ε
+−<
4.3. Predica tion o f Trajectory
Durin g the tar get tra ckin g, when to wakeup sensor nodes
to form cluster for performing tracking task is mainly
based on the location of target in next time slot. Thus, it
is necessary to estimate precisely the trajectory of targets.
In this paper, we use Kalman filter to predict the trajec-
tories of target. The Kalman filter is a set of mathemati-
cal equations that is efficient to estimate the state of a
process, because it supports estimations of past, present,
and even future states.
The Kalman filter estimates a process using feedback
control, so the equations for the Kalman filter include
time update equations and measurement update equa-
tions. The time update equations represent projecting
forward the current state and error covariance estimates
to achieve the a priori estimates for the next time step
[16].
The state vectors of all targets at time tk is expressed
by
12
,,,
n
k kkk
x xxx

=
, where
i
k
x
is the state vecto r of
target i and n represents the number of targets. The state
equation of the n targets is set by
11k kk
X AXW
−−
=⋅+
(14)
with a meas urement that is
k kk
Z HV= +
(15)
The random variables Wk and Vk represent the process
and measurement noise (respectively).They are assumed
to be independent (of each other), white, and with normal
probability distributions
Where A is a linear function, and Wk is independent
white noise. Five basic equations of Kalman filter (time
update equations, measurement update equations) is
given by [16]
( )()
( )
1 11XkkAXk kWk−=⋅− −+
(16)
( )( )
11)1 1
T
PkkAPkAPkkA Q−=⋅−=⋅−−+
(17)
( )()
( )( )
( )
( )
11
g
X kkX kkKkZkHXkk=−+− ⋅−
(18)
( )( )
( )
'
11
T
g
KPkkHH PkkHR=−⋅⋅− +
(19)
( )
( )
()
( )
1
g
PkkIKkHPkk=−⋅ −
(20)
The process is repeated with the previous a posteriori
estimates used to predict the new a priori estimates with
each time and measurement update.
4.4. Sensor Scheduling
When a target appears in the sensor network, it can be
sensed when sensor nodes’ detected signal strength
beyond a predefined value. Then, sensor nodes are se-
lected to form a cluster dynamically. There are a cluster
head and several member nodes in each cluster. The
sensor information is passed on to cluster heads where,
in turn, transmit infor matio n to the base station.
With the target moving, different sensor nodes are
chosen to form another cluster and the nodes in this
cluster are awakened while make other sensor nodes be
in sleep mode based on the prediction of trajectory of
target and node’ energy and location. Thus, it is possible
to save energy during tracking with duty cycling and
cluster technology.
5. Conclusions
In this paper, we propose sensor scheduling algorithm
target tracking-oriented. We try to solve the problem
how to scheduling sensor nodes to extend network life-
time during target tracking. We utilize dynamic cluster
and duty cycling technology in order to shedule sensors
D. M. YAN ET AL.
Copyright © 2011 S ciRes. WSN
299
that perform tasks be in the active state and all other
sensors are in the sleep state. In later research, we will
attempt to study follows problem: 1) how to determine
each node whether to enter sleep mode? 2) How long
should a sensor be in the sleep state?
6. Referen ces
[1] J. Kahn, R. H. Katz and K. Pester, “Next Century Chal-
lenges: Mobile Networking for Smart Dust,” ACM MO-
BICOM Co nference, 1999.
[2] F. Zhao, J. Liu , J . Liu, L. Guibas and J. Reich, “Co llabor-
ative Signal and Information Processing: An Informa-
tion-Directed Approach,” Proceedings of the IEEE,
2003. doi:10.1109/JPROC.2003.814921
[3] V. Raghunathan, C. Schurgers, S. Park and M. B. Srivast-
ava, “Energy-Aware Wireless Microsensor Networks,”
Signal Processing Magazine IEEE, Vol. 19, No. 2, 2002,
pp. 40-50. doi:10.1109/79.985679
[4] D. M. Blough and P. San ti, “Investigating Upper Bounds
on Network Lifetime Extension for Cell-Based Energy
Cons ervation Techn iques in Stationary ad hoc NetWork,”
Proceedi ng of 8th Annual International Conference on
Mobile Computing and Networking, GA, USA, ACM
Press, Atlanta, 2002 , pp. 183-192.
[5] Y. Xu, J. Heidemann and D. Estrin “Geograp h y-Informed
Energy Conservation for ad hoc Routing,” Proceedings
Annual International Conference Mobile Mobicom, 2001,
pp. 70-84.
[6] J. Y. Lin , W. D. Xiao, F. L. Le wis and L. H. Xie, “Ener-
gy-Efficient Distributed Adaptive Multisensor Schedul-
ing for Target Tracking in Wireless Sensor Networks,”
IEEE Transactions on Instrumentation and Measurement,
Vol. 58, No. 6, 2009, pp. 1886-1896.
doi:10.1109/TIM.2008.2005822
[7] D. Estrin, “Wireless Sensor Networks Tutorial Part Iv:
Sensor Network Protocols,” In Preceding Mobicom, US A,
pp. 23-28, 2002 .
[8] T. Ratnasingham, K. Thiagalingam, L. Marcel and Her-
nand ez, “Large-Scale Op timal Senso r Array Management
for Multitarget Tracking, IEEE Transactions on Systems,
Man and CyberneticsPart C: Application s a nd Reviews,
Vol. 37, N o. 5, 20 07 , pp. 803-814.
doi:10.1109/TSMCC.2007.901003
[9] M. Cardei, M. T. Thai and Y. S. Li, et al. “Energy-E f fici ent
Target Coverage in Wireless Sensor Networks,” Pro-
ceedin gs of IEEE INFOCOM, 2005, Vol. 42, No. 3, pp.
1976-1984. doi:10.1109/INFCOM.2005.1498475
[10] I. F. Akyildiz, W. S. Y. Sankarasubramaniam and E.
Cayirci, “Wireless Sensor Networks: a Survey,” Com-
put er Networks, Vol. 38, No. 4, 2002, pp. 393-422.
[11] A. Giuseppe, C. Marco, D. F. Mario and P. Andrea,
“Energy Conservation in Wireless Sensor Networks: A
Survey,” Ad Hoc Netwo r ks, 2009.
doi:10.1016/S1389-1286(01)00302-4
[12] Z. Wang and J. Zhang, “Energy Efficiency of Two Vir-
tual Infrastructures for MNAETs,” IPCCCC, Vol. 42, No.
3, 2006, pp. 54 7-552. doi:10.1109/PCCC.2005.1460632
[13] D. M. Yan, J. K. Wang, L. Liu, B. Wang and P. Xu,
“Topology Control Algorithm Target Track-
ing-Oriented,” The 5th International Conference on
Wireless Communications, Networking and Mobile
Computing, Vol. 4, 2009, pp. 1-4.
doi:10.1109/WICOM.2009.5304199
[14] N. B. Karayiannis, “MECA: Maximum Entropy Cluster-
ing Algorithm,” Proceedings of the Third IEEE Confe-
rence on Fuzzy Systems, IEEE World Congress on Com-
putational Intelligence, Vol. 1, 1994, pp. 630-635.
doi:10.1109/FUZZY.1994.343658
[15] X. Wang, S. Wang and A. Jiang, “A Novel Framework
for Clusterbased Sensor Fusion,” IMACS Multiconference
on Computational Engineering in Systems Applications,
Vol. 2, 2006, pp. 2033-2038.
doi:10.1109/CESA.2006.313648
[16] G. Welch and G. Bishop, “An Introduction to the Kalman
Filter,” TR 95-041, Department of Computer Science
University of North Carolina at Chapel Hill, Jacksonville.