TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol. 12, No. 10, Octobe
r 20
14, pp. 7509
~ 752
2
DOI: 10.115
9
1
/telkomni
ka.
v
12i8.575
9
7509
Re
cei
v
ed Fe
brua
ry 8, 201
4; Revi
se
d Ju
ly 26, 201
4; Accepted Aug
u
s
t 14, 2014
Issues t
o
wards Efficient Time Synchronization in
Wireless Sensor Networks
Abdul Wahe
ed Kha
n
, Ab
dul Hanan
Abdullah*, Ja
v
e
d
Iqbal Bangash
F
a
cult
y
of Com
putin
g, Univ
ersiti T
e
knologi
M
a
la
ysi
a
UT
M, Skuda
i, 813
10, Johor Ma
la
ysi
a
T
e
l.: +
607-553-
876
1; F
a
x: +
6
0
7
-55
3
-88
2
2
*Corres
p
o
ndi
n
g
author, em
ail
:
hanan
@utm.m
y
A
b
st
r
a
ct
W
i
reless sens
or netw
o
rk (W
SN) is consider
ed as th
e ena
bli
ng te
chno
logy to i
n
creas
e
coord
i
nati
on
b
e
tw
een the
ph
ysical a
nd v
i
rtual w
o
rl
ds.
A typical W
S
N
is
compos
ed of
a lar
ge n
u
m
b
e
r of
computi
ng devi
c
es
know
n as nod
es
w
h
ich ar
e
resp
onsi
b
l
e
for sens
ing
an
d
reporti
ng s
o
me ph
en
o
m
en
on
to
a sink or bas
e-
station w
here s
o
me usefu
l
con
c
lusio
n
s
are dr
aw
n from the r
eporte
d
data.
Most of the times,
the se
nsed
da
ta is of l
i
m
ite
d
usa
ge
if not
acco
mp
an
ied
w
i
th timesta
m
p
an
d p
o
siti
on i
n
for
m
ati
o
n
.
I
n
add
ition, sev
e
r
a
l oth
e
r bas
ic oper
ati
ons
in
W
S
Ns are ba
sed o
n
efficie
n
t time sy
nchr
oni
z
a
t
i
on s
u
ch
a
s
dup
licate
det
e
c
tion, d
a
ta a
ggre
gatio
n/fusi
on, e
nergy
ma
na
ge
me
nt, trans
missi
on
sched
ul
ing,
an
d
cryptogra
phy e
t
c; therefore time sy
nc
hro
n
i
z
ation
plays
a pi
votal rol
e
in
op
eratio
nal
activit
i
es of the n
e
tw
ork
.
In this
pa
per,
w
e
discuss
al
l
the re
late
d iss
ues
an
d ch
all
e
nges
that r
e
vol
v
e ar
oun
d ti
me
synchr
oni
z
a
t
i
o
n
i
n
W
S
Ns. Our purpos
e in w
r
iting this p
a
p
e
r
is to
provid
e an in-
d
e
p
th
understa
n
d
i
n
g
of the cloc
k
synchro
ni
z
a
ti
o
n
pr
obl
e
m
in
W
S
Ns so th
at the
ap
plic
atio
n d
e
sig
ners
c
an fi
ne
tun
e
t
heir
ap
plic
atio
ns i
n
accord
ance w
i
th the un
derl
i
ne
d constrai
nts and co
mp
lexiti
e
s
involv
ed.
Ke
y
w
ords
:
wireless sensor networks, tim
e
synchroni
z
a
tion,
synchroni
z
a
tion
issues, clock
drift
Co
p
y
rig
h
t
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
Wirel
e
ss
sen
s
or
network (WSN) is
con
s
ide
r
ed
as th
e enabli
ng te
chn
o
logy to i
n
crea
se
coo
r
din
a
tion
betwe
en the physi
cal and
virtual worl
ds. A
typical WSN is com
p
o
s
ed of a larg
e
numbe
r of co
mputing d
e
vice
s kn
own a
s
nod
es
em
b
odying limite
d
set of re
so
urces
su
ch a
s
a
microcontroll
er,
sho
r
t ra
n
ge radio
tra
n
sceiver,
an
d a l
ong
-la
s
ting b
a
ttery a
s
e
nergy su
pply
(typically AA battery). Th
ese
node
s a
r
e inte
rfac
ed
with se
nsors who
s
e job
is to se
nse
and
monitor the
surro
undi
ng environ
ment for variou
s p
henom
eno
n su
ch a
s
temperatu
r
e, so
u
nd,
pre
s
sure etc
and di
ssemin
ate their
se
nsed data to
so
me spe
c
ial
computing
dev
ice
s
called
si
nks
or ba
se
-statio
n
s in a coo
r
di
nated man
n
e
r
whe
r
e the
si
nk no
de
s furt
her p
r
o
c
e
ss a
nd analy
z
e th
e
repo
rted data
to draw con
c
lusio
n
s ab
out
the reporte
d
activity [1]. In fact, WSN is co
nsi
dered
as
a sp
eci
a
l cate
gory of a
d
-h
o
c
net
wo
rk
whi
c
h i
s
cha
r
a
c
terized by th
e
de-cent
rali
ze
d infra
s
tru
c
tu
re
-
free ope
ratin
g
mode wh
e
r
e nod
es
sel
f
-config
ure themselve
s
up
on deploym
e
nt and ca
rry
out
dual job
s
of sensi
ng an
d forwarding e
a
c
h othe
r’s
da
ta in a coo
r
di
nated man
n
e
r
thus formin
g a
multi-ho
p
co
mmuni
cation setup. Ho
wev
e
r,
nod
es
in
WSN
have th
eir o
w
n u
n
iqu
e
ch
ara
c
te
rist
ics
that disting
u
i
s
h the
m
from
ad-ho
c net
works. Ty
pi
cal cha
r
a
c
t
e
ri
st
ic
s
of
WSN are
limited
e
n
e
r
gy
resou
r
ce, large scal
e de
pl
oyment, che
a
per b
u
t
un
reli
able n
ode
s a
nd lon
g
op
erating/duty time.
WSNs have
got nume
r
o
u
s
ap
plication
s
an
d to nam
e a few th
ey have be
en v
e
ry su
cce
ssf
ul in
enemy intrusion dete
c
tion
, pre
c
isio
n a
g
riculture,
traffic co
ntrol,
infra
s
tru
c
ture and
ma
chi
ne
health monito
ring an
d patie
nt’s rem
o
te h
ealth monito
ri
ng. In short, they are
pa
rticularly useful in
situation
s
wh
ere te
rrai
n
, cl
imate, and ot
her e
n
vi
ron
m
ental co
nst
r
ai
nts hind
er in
the deploym
e
n
t
of traditional
wire
d networks [2].
The re
st of the pape
r is o
r
gani
zed a
s
fo
llows:
In se
ction 2, we di
scuss the impo
rtance of
time synch
r
o
n
izatio
n in sensor net
wo
rks and o
u
tline seve
ral
basi
c
op
erati
ons in
sen
s
or
netwo
rks whi
c
h
ne
ce
ssitat
e
a
commo
n
notion
of ti
m
e
am
ong
the
se
nsor no
de
s. To
cope
with
the time
syn
c
hroni
zation
probl
em, on
e
need
s to
un
derstand
first the cl
ockin
g
mechani
sm
in
comp
uting d
e
vice
s and h
o
w time in
co
nsi
s
ten
c
ie
s
o
v
er the network
ari
s
e wit
h
the passa
g
e
of
time, an overview is p
r
e
s
e
n
ted in se
ctio
n 3. Taki
n
g
into accou
n
t the low
co
st chara
c
te
risti
c
of
sen
s
o
r
n
ode
s in
WSN, th
e
only cost-effective soluti
on
to attain
clo
c
k
synchro
n
ization in
WS
N is
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
9
– 7522
7510
throug
h the e
x
chan
ge(s) of
time-syn
ch
messag
es
th
ereby e
nabli
n
g the no
de
s to get an
esti
mate
of the remote
clock’s readi
ng. However
variou
s com
p
onent
s cont
ri
bute to the non-d
e
termi
n
istic
comm
uni
cati
on laten
c
y, which p
o
tential
l
y degrad
es
t
he time synchroni
zatio
n
p
r
ocess an
d a
r
e
discu
s
sed i
n
se
ction
4.
Section
5
di
scusse
s th
e
thre
e diffe
rent me
ssag
e
disse
m
inati
o
n
approa
che
s
b
e
ing
a
dapte
d
for
time syn
c
hroni
zatio
n
in
se
nsor networks.
In se
cti
on
6, we outli
ne
the typical f
eature
s
th
at need to
be i
n
co
rpo
r
ate
d
i
n
a time
synch
r
oni
zatio
n
schem
e bei
ng
develop
ed fo
r WS
N. Vario
u
s i
s
sue
s
tha
t
arise i
n
pu
rsuit of ad
heri
ng to the vari
ous fe
ature
s
of
WSN are
bei
ng di
scu
s
sed
in
se
ction
7.
Sectio
n
8
di
scusse
s va
ri
ous sch
e
me
s that h
a
ve b
e
e
n
develop
ed to
co
pe
with
time syn
c
h
r
o
n
izatio
n i
s
su
es i
n
WSN.
Finally,
we
co
ncl
ude
o
u
r
discu
ssi
on wi
th some reco
mmend
ation
s
in sectio
n 9.
2. Importanc
e of Time Sy
nchroni
zatio
n
in Sensor Net
w
o
r
k
s
In WS
N, onl
y the sen
s
e
d
data
if not
acco
mpani
e
d
with
time
stamps an
d p
o
sition
s
(so
m
etime
s
),
is
of limited
usa
ge, the
r
ef
ore tim
e
synchroni
zatio
n
pl
ays a
pivotal
role to
a
c
hiev
e
the obje
c
tive(s) the
sen
s
o
r
node
s are d
eployed fo
r.
Several othe
r basi
c
ope
rati
ons in
WSN
are
also
ba
sed
o
n
efficient tim
e
syn
c
h
r
oni
zation. Ti
me o
r
cl
ock
synch
r
oni
zation i
s
a me
chani
sm
that
enabl
e the se
nso
r
nod
es in
a netwo
rk to
corre
s
po
nd to a con
s
i
s
ten
t
notion of time either lo
call
y
signifi
cant o
r
globally
(pro
vided if a gl
o
bal time/cl
o
ck refere
nce i
s
availa
ble).
In the follo
wi
ng
lines,
we b
r
i
e
fly describ
e
few such o
peratio
ns
wh
ere effici
ent
time synchronization is
of
imme
ns
e
impo
r
t
a
n
c
e
:
Duplica
t
e Detec
t
ion and
Data
Aggr
e
g
ation
:
No
d
e
s in sen
s
or network a
r
e
densely
deploye
d
an
d there is a
high proba
bil
i
ty that
the same event might be rep
o
rted by mul
t
iple
node
s o
p
e
r
ati
ng in
neig
h
b
o
rho
od. Sin
c
e computatio
n con
s
ume
s
very less
ene
rgy compa
r
e
d
to
comm
uni
cati
on a
nd the
r
efore to
avo
i
d du
plic
ate
deliverie
s of
an event, data
a
ggreg
ation
mech
ani
sm i
s
u
s
ed
wh
ere
throu
gh the
use
of func
tio
n
like
averag
e, max, or mi
n, tran
smissi
on
redu
nda
ncy
is eli
m
inated
f
r
om th
e
data
comin
g
fr
om
multiple
so
urce
s [5]. T
h
is requires a
c
curate
time-s
tamping.
Data Fusion
:
Senso
r
nod
es are expected to coordi
nate with ea
ch other to achieve a
compl
e
x sen
s
ing ta
sk. To
do so, data f
u
sio
n
mecha
n
ism i
s
empl
oyed to aggl
omerate ra
w
data
from nod
es i
n
to some m
e
aningful resul
t
forwarded
e
n
route to the
sin
k
[6]. As an example, in
a
mobile targ
et tracki
ng app
lication, different node
s re
port the time and locatio
n
of the target to
the sin
k
node
, from which the sin
k
estim
a
tes the lo
cation and velo
city of
the target. Therefore, if
the repo
rting
node
s are not
synch
r
oni
ze
d, it will re
sult
in an inaccu
rate estimate
by the sink.
Energ
y
Managemen
t
:
No
des
in se
nsor
network are
ba
ttery o
pera
t
ed an
d u
s
u
a
l
l
y there
is no battery repla
c
e
m
ent servi
c
e. The
r
efore to pr
ol
o
ng netwo
rk lifetime, all activities of sensor
node
s mu
st take into a
c
co
unt the energ
y
conse
r
vatio
n
goal. It has been well e
s
tabli
s
he
d that
comm
uni
cati
on m
odule
in
se
nsor no
de
is th
e m
a
in
con
s
um
er of
the availa
ble
energy resou
r
ce
and
con
s
u
m
es m
o
re
tha
n
2/3 of
ene
rgy re
sou
r
ce
[
2
]. Energy
conservation
schem
es stro
ngly
depe
nd o
n
time syn
c
h
r
oni
zation. T
o
av
oid idle
li
steni
ng, duty-cycl
es a
r
e emplo
y
ed
wh
ere no
des
perio
dically g
o
into
sle
ep
and
wa
ke
-up
mode
s
and
thus saves
huge
amo
unt
of en
ergy
b
y
spe
ndin
g
min
i
mal ene
rgy i
n
sle
ep m
o
d
e
. If these
sl
eep a
nd
wa
ke-up
time int
e
rvals amo
n
g
the
sensor nodes are not sync
hroni
zed, it
will result in slow
delivery
of sensed data because
the
neigh
bors m
i
ght be asle
ep and thu
s
unabl
e to relay the data. Hen
c
e
,
network-wi
de
synchro
n
ization is cruci
a
l for e
fficient du
ty-cycling tha
t
will ens
ure that although
some n
ode
s go
into sle
ep mo
de, others in
the neig
hbo
rhood
are
still
doing th
e sen
s
ing ta
sk an
d
thus
will ma
ke
an efficient ut
ilization of the
energy resou
r
ce.
Transmissio
n
Schedulin
g:
MAC layer sched
uling
schem
es such
time divisio
n
multiple
acce
ss (T
DM
A) requi
re
s ti
ght syn
c
h
r
o
n
i
zation
am
on
g the
sen
s
or nod
es othe
rwise
colli
sion
s
might o
c
cur i
f
two no
des try to tran
smit
usin
g
the sa
me
time slot due
to
thei
r unsyn
ch
roni
zed
clo
ck t
i
ming.
Cr
y
p
tograph
y
:
To ensure fre
s
h
n
e
s
s and
p
r
eve
n
t re
play at
tacks, a
u
the
n
tication
scheme
s
st
ro
ngly dictate the use of
syn
c
hroni
zed tim
e
among the
node
s.
Other tha
n
these, log
g
ing
and de
bug
gi
ng, lo
cali
zati
on and
coo
r
d
i
nated a
c
tuati
ons al
so
requi
re a
con
s
iste
nt notion
of time among the sen
s
o
r
node
s.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Issu
es to
wards Efficient Ti
m
e
Synchroni
za
tion in
Wire
less Sensor… (Abdul
Wa
heed Kha
n
)
7511
3. Clock Mo
del and Cloc
k Inaccura
cies
All computin
g
device
s
are equip
ped
with so
m
e
clo
cking me
chani
sm. A comput
er cl
ock
is comprised
of a hardwa
re oscillator (typically
quart
z
-oscillators) and a
counter that
decrem
e
nts
its value with
each o
scillati
on of the qu
a
r
tz crys
tal.
Wheneve
r
, the
cou
n
ter valu
e
gets to zero, an
interrupt
(
c
lo
ck t
i
ck
)
is g
enerated
whi
c
h
cau
s
e
s
the soft
ware
clock
(anot
her
cou
n
ter) to
increme
n
t its value. It is th
e softwa
r
e cl
ock that
is re
ad by applica
t
ions thro
ugh
the use of so
me
appli
c
ation
progra
mming
i
n
terfaces (A
PIs). A
software
cl
ock
directly corre
s
p
ond
s to
the
lo
c
a
l
time
of a se
nso
r
node,
a
nd i
s
rep
r
e
s
e
n
ted by
C(
t)
indicating
th
e
clo
c
k rea
d
in
g
at som
e
re
al
time
t
.
Next we pre
s
ent some te
rminol
ogie
s
relat
ed to clo
cki
ng that wil
l
help the re
aders to
unde
rsta
nd the inhe
rent p
r
oble
m
s in cl
ock hardw
are and will provide a better insig
h
t to cope
with these issues.
3.1. Clock Offse
t
Two
clocks
might not co
rre
sp
ond to the sam
e
time instant at the sam
e
time. Clock
offset is the differen
c
e be
tween the in
stantan
eou
s
absolute valu
es of the clo
c
ks i.e., if tw
o
node
s
A
&
B
have the ab
solute clo
c
k va
lues
C
A
(t)
and
C
B
(t
)
respe
c
tively at a particul
a
r in
sta
n
ce
of time t,
then clock offs
et can be re
presented by:
t
C
t
C
B
A
AB
(1)
For t
w
o p
e
rfe
c
tly syn
c
hroni
zed
clo
c
ks,
cl
ock offs
et is
equal to
zero
. However, it
is very
rare in WSN
either be
ca
use different initial ti
mes mig
h
t have been
set by the manufa
c
ture
rs or
the clock oscillation rate
might change with pass
age of time subject to
varying environmental
con
d
ition
s
su
ch a
s
tempe
r
ature, supplie
d voltage/pre
s
sure a
nd agi
ng effect.
3.2. Clock Fr
equen
c
y
/
Rate
It is the rate
at whi
c
h th
e
clo
ck
progresse
s. The f
r
eq
uen
cy of a n
o
de
A
at time t
is given
by:
t
d
t
C
d
t
C
A
A
(2)
Two no
de
s might be ope
rating on diff
erent fre
quen
cie
s
either b
e
ca
use different initial
freque
nci
e
s
might have b
een set by the manufa
c
turers
or the fre
quen
cie
s
mig
h
t chan
ge su
bject
to the varying
environ
ment
al co
ndition
s
stated a
bove.
Freq
uen
cy o
f
clock al
so
d
epen
ds
on type
of crystal
bei
ng u
s
e
d
whe
r
e
som
e
cry
s
tals a
r
e
mo
re
stabl
e
com
p
ared
to
others in
p
r
e
s
en
ce
of
varying
environmental con
d
itions.
3.3. Clock Ratio
It is the freq
uen
cy ratio b
e
twee
n clo
cks
of two no
d
e
s. The
ratio
of clock of
node
A
relative to node
B
at time t is
given by:
t
C
t
C
B
A
(
3
)
3.4. Clock Ske
w
It is the difference in frequ
enci
e
s of two
cl
ocks. Clo
c
k ske
w
is the
difference b
e
twee
n
the rates the
clocks run i
.
e., the rate
of chan
ge
of
offset. It is also d
e
fined
as the rate
of
deviation of a
node’
s clo
ck from true time. Mathemati
c
a
lly, it is the first orde
r de
rivative of clock
offset and is
repre
s
e
n
ted b
y
:
t
d
t
C
d
t
d
t
C
d
t
C
t
C
B
A
B
A
AB
(
4
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
9
– 7522
7512
If
two clo
c
ks are
pe
rfectly synchro
n
ized
,
then
clo
c
k ske
w
will
b
e
zero
be
ca
use
t
he sam
e
rate of ch
ang
e of frequen
ci
es at both no
des’
clo
c
ks wi
ll can
c
el out e
a
ch oth
e
r.
3.5. Clock Dr
ift
Two syn
c
hro
n
ize
d
cl
ocks have
a clo
ck
rate
dC
/d
t = 1
at all time
s but va
riou
s factors
affect the actual clo
ck
rat
e
su
ch a
s
te
mper
ature a
nd humidity
of the enviro
n
ment, su
ppl
ied
voltage, an
d
age
of the q
u
a
rtz. A
s
a
re
sult of this dev
iation, drift
rat
e
o
c
curs
whi
c
h is the
rate
b
y
whi
c
h
two cl
ocks can drif
t
apart
i.e.,
dC/dt – 1
. Thi
s
drift rate i
s
a variable
q
uantity and the
maximum
drif
t rate
of a cl
ock
(
ρ
)
fo
r q
uartz-b
ased clo
c
ks might take a
valu
e from
the
rang
e
1
part-per-million (ppm) to
100 ppm
where
1 ppm
= 10-6. The value of
ρ
i
s
usu
a
lly given
by
manufa
c
turer of the oscillat
o
r and it mu
st guara
n
tee th
e followin
g
rel
a
tionship:
1
1
dt
dC
(
5
)
Based
on the
variation
s
in
a clo
c
k’s
drif
t rate with
re
spe
c
t to real
clo
ck time,
we might
have fast, perfect, or slo
w
clocks a
s
sho
w
n in Figu
re
1.
Figure 1. Cla
ssifi
cation of
Clo
ck Ba
sed
on Drift Rate
Senso
r
s’ clo
c
ks mi
ght get
sync
hro
n
ized
at one in
stan
t of time but due to clo
c
k skew an
d
con
s
e
que
ntly due to th
e d
r
ift rate the
sensors’
clo
c
k rea
d
ing
s
mi
ght be
com
e
i
n
co
nsi
s
tent a
t
a
later sta
ge, makin
g
it ne
ce
ssary to re
peat
the syn
c
hroni
zation
pro
c
e
ss to a
c
hieve a
co
mmo
n
notion of tim
e
. Even in th
e ab
sen
c
e
of
clo
c
k ske
w
,
two no
de
s mi
ght not h
a
ve
con
s
i
s
tent time
notion p
o
ssib
ly due to
a
slightly differe
nt init
ial fre
q
uen
cy set
by the ma
nufa
c
ture
r.
No
w the
que
stion ari
s
es that ho
w long this
resy
nch
r
oni
zati
o
n
interval sho
u
l
d be? To find
out this interval,
con
s
id
er two
identical syn
c
hroni
ze
d clo
c
ks
whi
c
h ca
n
drift apart from each oth
e
r at a rate o
f
a
t
most 2
ρ
max
(if one
clo
ck drifts p
o
sitiv
e
ly and th
e
other
drifts
n
egatively), no
w to b
oun
d the
relative offset to
δ
se
co
nd
s
,
th
e r
e
s
y
n
c
hr
o
n
i
z
a
tion in
te
r
v
a
l
(
τ
sy
nc
)
mus
t
satisfy the follow
i
ng
requi
rem
ent:
max
2
sync
(6)
It is a norm to make
gradu
al clo
ck adj
ustm
e
n
ts, for example, usin
g
a linear
comp
en
satio
n
function th
at chan
ge
s the slo
pe
of the local tim
e
, otherwi
se
simply jump
ing
forwa
r
d o
r
ba
ckwa
rd would
result in mi
ss
ing or repe
ating the time-tri
ggered event
s [3].
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Issu
es to
wards Efficient Ti
m
e
Synchroni
za
tion in
Wire
less Sensor… (Abdul
Wa
heed Kha
n
)
7513
3.6. Clock’s
Precision and Stabilit
y
These are the two import
ant parameters of a
clock’
s oscillat
o
r in
a com
puting device.
Preci
s
io
n (a.k.a frequ
en
cy
error) i
s
the
d
i
ffer
ence
b
e
twee
n
theo
reti
cal and re
al
freque
nci
e
s of an
oscillator a
n
d
is usu
a
lly given by manufa
c
ture
r in t
he
units of ppm. Esse
ntially, it is the drift ra
te
of a nod
e’s cl
ock with
re
sp
ect to a
n
ide
a
l
and p
e
rf
e
c
t
clo
ck.
Clo
ck
stability is the
tenden
cy of t
he
clo
ck’
s oscill
ator not to deviate from the sam
e
freq
uen
cy over the time and is affected by
the
factors like te
mperature a
n
d
humidity, supp
lie
d voltages, pressu
re
s and mate
ria
l
aging.
3.7. Adjustin
g Drifted Clo
cks
Compli
catio
n
s
ari
s
e wh
e
n
the local clo
ck of a n
ode ru
ns faster than the
clock of
referen
c
e no
de. If
T
curr
repre
s
ent
s t
he
cur
r
e
n
t
local
clo
ck t
i
me a
n
d
T
ne
w
rep
r
e
s
ents the real
time
that the local
clo
ck h
a
s to b
e
update
d
to, then:
a) If
T
new
> T
cur
r
then the so
ftware time o
f
the node
is simply adva
n
ce
d to the
new
value Tne
w
.
b) If
T
new
<
T
curr
then
we
can
not di
re
ctly set ba
ck the
software
time
of the
nod
e t
o
the
new value
T
new
be
ca
use
doing
that
wi
ll re
sult i
n
fa
ulty timestam
ps
(some
ti
me-
trigge
red eve
n
ts will be re
peated
). To cop
e
with thi
s
issue, in
ste
ad of tuning
the
clo
ck b
a
ck, the clo
c
k is sl
owe
d
down by
the software that han
dl
es the cl
ock tick
interrupt until it gets to a desire
d
value p
r
ogre
s
sively.
3.8. Complications in Clo
ck Offse
t
an
d Clock Ske
w
E
s
timatio
n
The p
r
oble
m
of clock
syn
c
hroni
zation
requi
re
s a
c
curate e
s
timat
e
s of both th
e clo
c
k
offset and
cl
ock ske
w
(if any). Synch
r
onization
sc
hemes that correc
t
only the c
l
oc
k offs
et
[4],
requi
re
s freq
uent resyn
c
h
r
onization tha
n
those t
hat
corre
c
t both
the cl
ock off
s
et and
skew.
The
r
e
as
o
n
be
h
i
nd
th
is
fr
e
q
uen
t r
e
s
y
nc
hr
on
iz
a
t
ion
is
that clocks sta
r
t drifting ap
art in ca
se
of
uncompe
nsated cl
ock
ske
w
s.
T
herefore, joint cl
ock offset an
d ske
w
comp
en
sation
re
sult
s in
long term rel
i
ability of synch
r
oni
zatio
n
and thu
s
m
o
re e
n
e
r
gy conservation.
If clocks
of two
node
s a
r
e p
e
r
fectly syn
c
h
r
onized,
then
clo
ck
offset is ze
ro a
nd the
differen
c
e
be
tween th
e
Se
nd
Tim
e
stam
p
and
Re
cei
v
e Ti
m
e
st
am
p
will
give us the end-
to-end delay. In case
of
non-zero offset
but no clo
ck
skew, the en
d-to-end del
a
y
will be t
he
differen
c
e of the two timestamp plu
s
the
clo
ck offset. The situatio
n
gets compli
cated in ca
se
of non-ze
ro clock o
ffset an
d non-ze
ro
cl
ock
skew be
ca
use the
end
-to-
end
delay
mi
ght g
r
adu
ally incre
a
se
o
r
decrea
s
e
ove
r
time
su
bje
c
t to
wheth
e
r the sende
r clo
c
k runs
slo
w
er o
r
faster compa
r
ed to re
ceive
r
clo
ck.
4. Non-De
ter
m
inistic Co
mmunicatio
n
Laten
c
y
in Wireless
En
v
i
ronments
In orde
r to a
c
hieve a com
m
on an
d con
s
iste
nt notion
of time, the node
s ex
cha
nge thei
r
local
clo
ck
re
ading
s with e
a
ch oth
e
r to
estimate a
n
d
adjust thei
r
clo
ck p
a
rame
ters. Howeve
r,
variou
s facto
r
s affect the
message d
e
livery in a wirele
ss network an
d compli
cate t
he
synchronization process.
In fac
t, there is no guarantee that
each receiver will receive
t
h
e
transmitted signal at th
e
same
in
stant
. This va
riab
le co
mmuni
cation laten
c
y
cont
ribute
s
to
unpredi
ctable
delay
s. So
me of the
factors th
at
contribute
to
comm
uni
cati
on late
ncy
while
transmitting over a wirel
e
ss cha
nnel
are
Send
Tim
e
, Access Tim
e
, Transm
i
ssi
on Ti
m
e
,
Propa
gation
Tim
e
, Recept
ion Tim
e
, an
d
Re
cei
v
e
Tim
e
[7] an
d [4]
and th
e
comb
ined
effect of
all
these differe
nt kind
s of delays mu
st be less
than the re
q
u
ired tole
ran
c
e of the time
synchro
n
ization. In the followin
g lines, we provide a
brief descri
p
tion of the variou
s del
ays in
messag
e deli
v
ery:
Send Time:
The time to construct the
messag
e an
d
then pa
ss o
n
to MAC layer on the
transmitter si
de. It might inclu
de del
ays ca
used by
operating
system su
ch a
s
context switching,
system
-call o
v
erhea
d, and
the pr
o
c
e
s
sor’s
cu
rrent load. All thes
e com
pon
ent
s of delay
s a
r
e of
variable
len
g
t
h and
ca
nn
ot be p
r
e
c
i
s
ely pre
d
icte
d
.
Putting sim
p
ly, it is the
time requi
re
d to
transfe
r the
messag
e fro
m
applicatio
n layer to network
interfac
e.
Ho
wever, the
delay cau
s
e
d
by Send
-Ti
m
e
can b
e
el
iminated fro
m
the overall
end
-to-
end d
e
lay by
usin
g MAC la
yer time-stam
p
ing a
s
being
done
in TPS
N
[4], FTSP [14], DMTS [2
0]
etc.
Acc
ess Time
:
The time th
at a messag
e
must wait b
e
f
ore getting a
c
cess to the
wirel
e
ss
medium/
c
ha
n
nel. Sin
c
e
wirele
ss me
di
um i
s
a
sha
r
ed
medi
um
and if
multip
le no
de
s try
to
transmit at the same time,
collisi
o
ns are inevitabl
e. To avoid such scenarios, two categories of
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
9
– 7522
7514
MAC proto
c
o
l
s exist: Cont
ention-ba
sed
MAC pr
oto
c
ols an
d Sch
edule
-
ba
se
d MAC proto
c
o
l
s.
Conte
n
tion-b
a
se
d MAC p
r
otocols n
e
e
d
an ex
cha
n
ge of control
message
s Req
u
e
s
t-to-S
end
(RTS
) a
nd
Cl
ear-to-Se
nd
(CTS) to ma
ke sure
that
th
e medi
um i
s
free
before transmi
ssion.
In
ca
se of
unav
ailability, the
node
wait
s f
o
r a
ra
ndom
amou
nt of time. In sch
e
d
u
le-b
ased M
A
C
proto
c
ol
s su
ch as T
D
MA, every node i
s
assig
ned
a
time-slot wh
en it can get
access to the
medium
so t
he no
de
wait
s for it
s time-slot befo
r
e transmi
ssion.
The Acce
ss-Time is th
e l
east
determi
nisti
c
as it stron
g
ly depend
s on
the dens
ity of nodes a
n
d
the netwo
rk traffic. Simply
putting, it is the waitin
g time to access the
tran
smi
ssi
on ch
ann
el u
n
til the transmissi
on be
gin
s
.
Again, by usi
ng the MAC l
a
yer time-sta
mping,
the Acce
ss-Time
de
lay can b
e
eli
m
inated
from the end
-to-end d
e
lay as bei
ng do
n
e
in
TPSN [4], FTSP [14],
DMTS [20], etc.
Transmissio
n
Time:
The t
i
me that it takes for the
s
e
n
der to tra
n
smi
t
the messag
e once
it gets a
cce
ss to
the
wirel
e
ss m
edium.
It depen
ds o
n
the
length
of the m
e
ssa
ge a
nd th
e
speed
of the radio (t
he time that it takes to tra
n
s
mit one bit o
f
the messag
e).
This
comp
on
ent of delay is pa
rtly deterministic if the
lengt
h of the message i
s
kno
w
n in
advan
ce. In that ca
se, the Tran
smi
ssi
on
-Time i
s
simp
ly
nT
, where
n
is the num
ber of bits in t
he
messag
e and
T
is the time to transmit on
e bit of the messag
e.
Propaga
tion
Time:
Is the
actual
propa
gation time f
o
r a m
e
ssa
g
e thro
ugh th
e
wireless
medium
on
ce
it lefts th
e
se
nder.
Me
ssag
e in
a
wirele
ss
cha
nnel
tra
v
els
with
sp
e
ed of
light
an
d it
depe
nd
s on the dista
n
ce b
e
twee
n two n
ode
s.
In wirele
ss sensor net
wo
rks, del
ay ca
use
d
by Pro
pagatio
n-Tim
e
is usually negligibl
e
taking into
co
nsid
eratio
n that node
s are
only a few meters a
p
a
r
t.
Rec
e
ption
T
i
m
e
:
The
time re
quired fo
r the
re
ceive
r
to receive t
he me
ssag
e
at the
physi
cal layer. It is just like
Tran
smi
ssi
on
-Time an
d de
pend
s on len
g
th of messa
ge and
spee
d
of
the radio.
Rec
e
iv
e Time:
Is the tim
e
for the net
work inte
rface ca
rd to re
ceive, co
nst
r
uct the
messag
e at the re
ceive
r
a
nd not
ify the host of its arri
val.
Re
ceive-Tim
e
doe
s not
contribute
mu
ch to
en
d-to
-end del
ay of messag
e deli
v
ery and
can e
a
sily be
eliminated by
MAC layer time-stampin
g at the receiver end.
5. Time-Sy
n
chronization
Messag
e Di
sseminatio
n Appro
ach
es
There a
r
e typ
i
cally three a
ppro
a
che
s
fo
r exchan
ging
time-syn
ch
ro
nizatio
n
me
ssag
es to
achi
eve cl
ock syn
c
h
r
o
n
ization in
wireless
sen
s
o
r
netwo
rks: f
i
rst o
ne i
s
one-way tim
e
-
synchro
n
ization me
ssag
e
dissemin
ation
,
se
con
d
is two-way
message ex
cha
n
g
e
(a.
k
.a
sen
d
e
r-
receiver
syn
c
hroni
zation
) and finally
the re
ce
iver-receiver syn
c
hroni
zation [8].
To
achi
eve
netwo
rk-wide
synch
r
oni
zat
i
on, this pro
c
ess of
excha
nging timing
messag
es i
s
repe
ated am
ong
multiple nod
e
pairs
until all node
s in the netwo
rk
ad
just their lo
ca
l clocks. He
re, we provide a
critical analy
s
is of these m
e
ssag
e disse
m
inat
ion me
chani
sms to
wa
rds time
synchroni
zatio
n
.
5.1. One-Wa
y
Message Dissemination
This i
s
a
si
mple pai
rwi
s
e messa
ge
excha
nge in
whi
c
h two n
ode
s syn
c
h
r
onize their
clo
c
ks u
s
ing
only a single
messag
e. Lets clo
c
ks of two node
s
i
and
j
needs to be syn
c
hroni
zed
usin
g this ap
proa
ch. As ill
ustrate
d
in Fi
gure 2,
the
synchroni
zatio
n
pro
c
e
s
s be
gins
whe
n
no
de
i
sen
d
s a
syn
c
hroni
zatio
n
m
e
ssag
e to no
de
j
at time
t
1
and time-stamps th
at messag
e with
t
1
.
Upo
n
receivin
g this
me
ssa
ge, nod
e j tim
e
stamp
s
thi
s
messag
e
with
time
t
2
according to it
s loca
l
clo
ck readi
ng
and from the
difference of
these two timestam
ps, th
e clock offset
is
es
timated,
that is
:
1
2
t
t
(7)
Acco
rdi
ngly, node j adj
ust
s
its clo
c
k time by the following e
quatio
n:
D
t
t
1
2
(8)
Whe
r
e
D
i
s
t
he p
r
op
agati
on d
e
lay of t
he me
ssag
e
and
sin
c
e
no
des in
se
nso
r
network
are only a fe
w meters ap
a
r
t, so it is either igno
re
d or
is assum
ed to be a ce
rtain
con
s
tant value.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Issu
es to
wards Efficient Ti
m
e
Synchroni
za
tion in
Wire
less Sensor… (Abdul
Wa
heed Kha
n
)
7515
Figure 2. Clo
ck Syn
c
hroni
zation u
s
in
g One-way Me
ssage
Disse
m
ination
This a
pproa
ch is althou
gh
very simple b
u
t due to vari
ous d
e
lay co
mpone
nts me
ntioned
above espe
cially the
m
edia acce
ss d
e
lay
which is highly non
-dete
r
mini
stic (depe
nding
on
netwo
rk traffic)
and i
s
normally seve
ral
ord
e
r
hi
gh
er in mag
n
itud
e than th
e cl
ock pe
rio
d
, o
n
e
singl
e time transfe
r wo
uld
not be eno
ug
h to synch
r
o
n
i
ze the no
de
s. Another issue with on
e-way
messag
e dissemin
ation is that the sen
der
cl
ock
skew might
ch
ange after it
timestamp
s
a
nd
sen
d
s the
sy
nch
r
oni
zatio
n
me
ssage
to
the receiver.
The
re
ceive
r
has no
me
an
s to
lea
r
n
ab
out
this ch
ang
e in sen
der’
s
cl
ock ske
w
oth
e
r than if the sen
der
sen
d
s another m
e
ssag
e to recei
v
er
notifying abo
ut its cha
nge
of
the clo
ck
skew
whi
c
h
add
s to the communi
catio
n
overh
ead a
n
d
thus can pote
n
tially con
s
u
m
e more e
n
e
r
gy re
sou
r
ce.
5.2. T
w
o
-Wa
y
Message Exchan
ge
This
app
roa
c
h is also
kn
own
a
s
roun
d-trip
syn
c
h
r
onization a
n
d
is someh
o
w
mo
re
accurate
app
roa
c
h
a
s
sho
w
n i
n
Fi
gure
3. Using
thi
s
approa
ch,
no
de
i
firs
t times
t
amps
the time-
synch messa
ge with time t1, which is re
ceived a
nd re
corded by no
de
j
at time
t
2
.
In return, node
j
send
s a re
spo
n
se to no
de i timestam
ped with time
t
3
and also includi
ng
t
1
. Upon receiving this resp
on
se, no
de
i
time-sta
mps the me
ssage
with time
t
4
whi
c
h
is
comp
uted u
s
i
ng the followi
ng equ
ation:
D
t
T
3
4
(9)
If the commu
nicatio
n
laten
c
y is symmet
r
ic, then:
2
3
4
1
2
t
t
t
t
D
(10
)
And,
2
3
4
1
2
t
t
t
t
(11
)
Substituting values of
D
and
in E
quation
(9
),
node i
will
a
d
just its cl
ock timing
accordingly.
No
w if no
de
i
has to
notif
y to node
j
a
bout the
esti
mated offset, it can
do
so
by
transmitting a
third messa
g
e
to node
j
.
This ap
pro
a
ch works well
unde
r the assumptio
n
that clock offset is con
s
tant du
ring the
excha
nge
pro
c
e
ss
and
cl
o
c
ks d
o
n
o
t dri
ft much in
thi
s
enti
r
e ex
ch
ange
process whi
c
h m
a
y n
o
t
be true be
cause clo
c
k offset contin
uou
sly gro
w
s su
bje
c
t to different fre
quen
cie
s
of the
oscillators. A
nother
big assumption is t
hat t
he comm
unication latency is
symmetric and remai
n
s
con
s
tant.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
9
– 7522
7516
Figure 3. Clo
ck Syn
c
hroni
zation
u
s
in
g Two
-
way Message Exch
a
nge
5.3. Receiv
e
r-Re
ceiv
e
r Messag
e Exch
ange
Usi
ng thi
s
ap
proa
ch, a
group of n
ode
s re
ceive the
same
me
ssa
ge broad
ca
st
ed by a
reference
node and therefore, it
i
s
also known as
reference broadcasting.
As illustrated in
Figure 4, the broa
dcaste
d messag
e is n
o
t time st
amp
ed by the sen
der, rath
er up
on re
ceiving,
all
the re
ceiving
node
s timestamp it according to t
heir l
o
cal
clo
ck ti
mes a
nd the
n
excha
nge t
heir
arrival
times
to com
pute
a
n
offset
whi
c
h would
be t
he differen
c
e
in reception
times. In
ca
se if
there
are
onl
y two
re
ceive
r
s, th
en
a tot
a
l of th
ree
m
e
ssag
es wou
l
d be
requi
re
d to
syn
c
hro
n
ize
these two receive
r
s. Re
feren
c
e broa
dca
s
t
schem
e (RBS) [9], follows this appro
a
ch to
synchro
n
ize all the node
s
that are in
the
radio covera
ge of the sen
der.
Figure 4. Clo
ck Syn
c
hroni
zation u
s
in
g
Re
ceiver-receiver
Me
ssag
e Exchang
e
Offset
comp
utation u
s
in
g
this ap
pro
a
c
h, i
s
m
o
re
accu
rate
compa
r
ed
to
two-way
messag
e ex
chang
e
since
the b
r
oa
dca
s
ted m
e
ssa
g
e
do
es
not encounte
r
ra
ndom delay
s
a
t
sen
d
ing n
o
d
e
. Ho
wever, i
t
incurs
signif
i
cant
time u
n
c
ertai
n
ty because the me
ssage
re
cepti
on
take
s
some
time (e.g., su
bject to
re
cei
v
er’s
r
adi
o
speed,
pro
c
e
s
sor availa
bility etc) f
r
om
o
ne
node to an
other, hen
ce t
here mi
ght b
e
signifi
cant
differen
c
e in
the absol
ute values of the
relative offset
compute
d
a
t
any pair of receive
r
s. A
nother i
s
sue in this appro
a
ch is that the
sen
d
ing n
ode
remain
s un
synchroni
zed i
n
this pro
c
e
s
s.
6. Featur
es
of Time Sy
n
c
hronization
Schemes in Wireless Se
nsor Net
w
o
r
k
The
scarce
re
sou
r
ce
s
of nod
es in
WS
N ma
ke it very
d
i
fficult for
a
n
y time
synchro
n
ization sche
me to
attain an optimal sy
n
c
hron
ization
withou
t compromi
si
ng so
me of the
ideal
cha
r
a
c
teristics. Elson an
d Estrin [10
], hav
e identified
a set
of metrics for time
synchro
n
ization in
WSN th
at se
rv
es a
s
a ben
ch
mark
for any time
synchroni
zatio
n
sche
me b
e
i
ng
develop
ed for WSN. However, no
singl
e schem
e is
con
s
id
ere
d
o
p
timal alon
g
all the axes
a
nd
trade
-offs a
r
e
alway
s
bein
g
ob
serve
d
b
e
twee
n t
he variou
s m
e
trics (fo
r
exampl
e, an a
ccu
rat
e
time synch
r
o
n
izatio
n woul
d be attained
at t
he expense of mo
re energy con
s
umption
)
. In the
followin
g
line
s
, we
bri
e
fly describe th
ese fe
ature
s
that need t
o
be in
co
rpo
r
ated in
a ti
me
synchro
n
ization schem
e b
e
ing develo
p
ed for WS
N:
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
Issu
es to
wards Efficient Ti
m
e
Synchroni
za
tion in
Wire
less Sensor… (Abdul
Wa
heed Kha
n
)
7517
Energ
y
Constrain
t
s:
Ene
r
gy i
s
the
scarcest
re
so
urce
i
n
WSN, t
herefo
r
e
like
all othe
r
operation
s
in
WSN, th
e
synch
r
oni
zatio
n
schem
e
sho
u
ld ta
ke into
accou
n
t the li
mited availa
b
l
e
energy and
therefore should o
p
t for lea
s
t en
ergy co
nsu
m
ption. Some traditional
time
synchro
n
ization scheme
s
require
the
u
s
e of
sophi
sticated a
nd e
n
e
r
gy-h
ung
ry e
quipme
n
ts
(e.
g
.,
G
PS r
e
c
e
ivers
an
d a
t
o
m
ic
c
l
oc
ks
)
,
h
o
w
e
ve
r
th
e us
e
of
su
ch
e
quipm
ents i
n
WSNs is not
a viabl
e
option d
ue t
o
the en
erg
y
con
s
umpti
on an
d cost
issue
s
. Tim
e
syn
c
h
r
oni
zation in
WS
N is
achi
eved thro
ugh exchan
g
e
of time-syn
ch me
ssag
es
; therefore
an
efficient time synch
r
o
n
ization
scheme
shou
ld aim
for
achieving time
synchro
n
iz
ation at th
e exp
ense of
mini
mum n
u
mbe
r
of
comm
uni
cati
on me
ssage
s. Ho
weve
r, there i
s
a
trade
-off b
e
twee
n ene
rgy efficien
cy and
synchro
n
ization accu
ra
cy and limit
ing the messa
g
e
s
result in mo
re synchro
n
ization error.
Accu
racy
:
Accura
cy is a
measure of h
o
w
clo
s
e a
n
ode’
s time is
to the true ti
me. The
accuracy of
time synchro
n
izatio
n is hi
ghly appl
i
c
ati
on spe
c
ific.
In certai
n ap
plicatio
ns, th
e
synchro
n
ization a
c
cura
cy
might
be in t
he order
of a few
µsec
while in
others only a sim
p
le
orde
rin
g
of e
v
ents o
r
me
ssag
es
wo
uld
be sufficient.
High
accu
ra
cy can b
e
a
c
hi
eved thro
ugh
the
use of hig
h
freque
ncy o
scil
l
ator but at t
he expen
se of more e
nergy con
s
um
ption.
Computational Complexit
y
:
Nodes in
WSNs h
a
ve
limited hard
w
are ca
pabili
ties and
have severe
energy con
s
traints; th
eref
ore th
e
comp
lexity (run
-
time and
memo
ry requi
rem
e
n
t
s
etc.) of a tim
e
syn
c
hroni
zation pr
otocol
can m
a
ke a
proto
c
ol im
practical for m
a
ny appli
c
atio
ns if
its com
putational re
qui
rem
ents exceed t
he nod
e’s p
h
y
sical resou
r
ces.
Scalabilit
y
a
nd Mobilit
y
Support
: In
many ap
plica
t
ions of
WS
N, node
s a
r
e
d
eployed
on a la
rg
e scale. Furth
e
r
d
ue to mo
bility, freque
nt top
o
logi
cal
cha
n
ges
might h
a
ppen
and
sin
c
e
comm
uni
cati
on inte
rfere
n
c
e d
epe
nd
s
on de
nsity
o
f
netwo
rk, th
erefo
r
e the
synchro
n
ization
scheme
sh
o
u
ld be a
b
le
to accomm
o
date the
in
creasi
ng nu
mb
er of no
de
s
and
scale well
accordingly without degradi
ng syn
c
hroni
zation a
c
cura
cy.
Robu
stn
ess
:
Nod
e
s
bein
g
battery op
erated
might
deplete th
ei
r batteri
es
b
u
t the
synchro
n
ization schem
e should remain
function
al in case of the
s
e topolo
g
ical
ch
ange
s.
Cos
t
an
d Siz
e
:
Small
si
ze
and lo
w
co
st
are th
e mai
n
cha
r
a
c
teri
stics of
node
s i
n
WSNs
towards thei
r widespread adapt
ability. Nodes cannot
afford to have la
rge and expensive
hard
w
a
r
e (su
c
h a
s
GPS or tempe
r
atu
r
e compe
n
sa
ted clo
c
ks) a
ttached to th
em. Therefore,
lightwei
ght sy
nch
r
oni
zatio
n
schem
es sh
ould
be d
e
ve
loped
in a
c
co
rdan
ce
with
the limited
co
st
and sm
all si
ze of the sen
s
or nod
es.
7. Issues an
d Challenge
s to
w
a
r
d
s
Efficient Time
Sy
nchroniza
tion
In this
se
ctio
n, we
outline
the vario
u
s i
s
sue
s
b
e
ing fa
ced
whil
e ad
herin
g to
so
me of the
t
y
pical ch
ara
c
t
e
rist
ic
s of
W
S
N in
pursuit
of time synch
r
oni
zation.
7.1. Issues in Energ
y
Effi
cient Time Sy
nchroniza
tion
Energy effici
ent synchroni
zation
can
be
atta
ined by adhe
ring to t
w
o ba
si
c pri
n
ciple
s
in
clo
ck
synchro
n
izatio
n pro
c
ess [11]:
1.
Usi
ng Lo
w Freque
ncy Cl
ock
2. Infreque
nt
Co
mmuni
cation
Hen
n
e
ssy an
d Patterso
n
, have identifie
d the followin
g
relatio
n
ship
betwee
n
the
powe
r
and freq
uen
cy in [12] and is co
nsi
dered
as
rul
e
of thumb for embe
dded
system
s.
Powe
r = Cap
a
citative Loa
d(C) * Voltag
e^2 * Freq
ue
ncy Switch
ed
(
1
2
)
Therefore, lo
w-frequ
en
cy clo
c
ks a
r
e m
andato
r
y
to
minimize the
power di
ssipa
t
ion of the
oscillator,
dig
i
tal co
unter a
nd
clo
ckin
g
n
e
twor
k. Ho
wever,
a
l
o
w-freque
ncy clo
c
k comp
romi
ses
the time re
so
lution an
d fre
quen
cy erro
r
thereby
re
sult
ing in le
ss fin
e
r time
re
sol
u
tion an
d mo
re
freque
ncy
error, for exam
ple, an
8M
Hz
clo
c
k re
sul
t
s in frequ
en
cy erro
r
re
so
lution of 0.0
1
2
5
ppm, while a
32KHz clo
c
k results in 3.0
5ppm [11].
Comm
uni
cati
on modul
e on
the other ha
nd is co
nsi
d
e
r
ed a
s
the largest consum
er of th
e
node
ene
rgy
re
sou
r
ce, fo
r exampl
e: th
e ene
rgy req
u
ired
to tran
smit 1 bit ov
er 1
00m
can
be
used to execute 3 million i
n
structions [13]. Ther
efore,
an important
characteri
sti
c
bei
ng
sought
towards en
ergy con
s
e
r
vati
on is le
ss
co
mmuni
ca
tion overhe
ad during
syn
c
h
r
o
n
ization process.
Ho
wever, l
e
ss o
r
inf
r
eq
ue
nt co
mmuni
cation results
into large
r
synch
r
oni
zatio
n
interval
s
whi
c
h
comp
romi
se
s the a
c
cura
cy of time noti
on am
ong th
e nod
es in th
e network b
e
cau
s
e
ch
angi
ng
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 10, Octobe
r 2014: 750
9
– 7522
7518
the environm
ental temp
erature
s
o
r
exp
o
su
re to
hig
h
voltage
s wo
uld
cau
s
e
greater f
r
eq
uen
cy
error (clo
ck ske
w
) a
nd thu
s
high
drift rate
betwe
en the
re
synchronizati
on inte
rvals. Frequ
e
n
t
excha
nge of
synch me
ssa
ges
re
su
lts i
n
fast conve
r
gen
ce an
d in
cre
a
ses th
e accuracy at the
expen
se
of more po
wer con
s
um
ption
so
the
r
e
i
s
a trad
e-off b
e
twee
n en
ergy con
s
u
m
ption,
accuracy an
d conve
r
ge
n
c
e time [14] whereby
d
e
crea
sing th
e resyn
c
h
r
o
n
izatio
n interval
increa
se
s the
numbe
r of time-synch me
ssage
s sent in a cert
ain time peri
od.
7.2. Issues in Impro
v
ing
Accu
racy
of Time Sy
nchroniza
tion
As
s
t
a
t
ed
ear
lie
r
,
th
e ac
cu
r
a
c
y
o
f
time
s
y
n
c
h
r
oni
zation is hig
h
l
y
application
sp
ecific
whe
r
e som
e
appli
c
ation
s
might
re
quire
ac
curacy of
time synchro
n
izatio
n in
µsec
, others mi
ght
requi
re
a fe
w
msec
whil
e
in so
me a
pplication
s
si
mple ord
e
rin
g
of
eve
n
ts woul
d
d
o
the
job.
There is
a tra
de-off bet
wee
n
the a
c
cura
cy and ene
rgy
con
s
um
ption
whe
r
eby hi
g
her a
c
cu
ra
cy is
achi
eved at the expen
se
of more e
n
e
r
gy con
s
um
ption thereby a
c
hievin
g fast
er conve
r
gen
ce
throug
h freq
uent exch
an
ge of syn
c
h messa
g
e
s
[14]. To conserve e
n
e
r
gy duri
ng t
h
e
synchro
n
ization pr
ocess, an alternate
approa
ch is to
exchan
g
e
the time-synch me
ssa
ges
initially over some time inte
rval for estim
a
tion of clo
c
k offset and skew an
d on
ce
sufficie
n
t data
points a
r
e
co
llected the
n
use
statistica
l techniq
u
e
s
su
ch a
s
linea
r reg
r
e
s
sion t
o
predi
ct clo
c
k
offset usi
ng t
he best-fit line as
shown i
n
figure
5. If the oscilla
tor f
r
equencies of
WSN nodes
do
not fluctuate,
then a o
ne-ti
me estim
a
tio
n
of clo
c
k drif
t would
be
su
fficient to tran
sform th
e cl
o
ck
readi
ng of a
nother
nod
e. This a
ppro
a
ch h
e
lp
s
in
redu
cin
g
the excha
nge
of time-syn
ch
messag
es a
nd thu
s
co
nse
r
ving
en
ergy. However, the
s
e
st
atistical
tech
nique
s a
r
e
not
guarantee
d to come up
with the right es
timat
e
s of clo
c
k param
eters and thus
the
synchro
n
ization a
c
cura
cy
degrade
s
sig
n
ificantly esp
e
cially in
ca
se of unsta
ble
con
d
itions
such
as ambi
ent temperature va
riation
s
or
ch
angin
g
the su
pplied voltag
es where the
clock ske
w
will
drift far awa
y
than expected. The
r
ef
ore, in
ca
se
of changi
n
g
environ
me
ntal factors,
the
synchro
n
ization pro
c
e
d
u
r
e
need
s to be repeate
d
after some time.
Figure 5. Clo
ck Offset Pre
d
icatio
n usi
n
g
Best-Fit Line
7.3. Issues to
w
a
rd
s Scalable Time Sy
nchroni
zatio
n
An important
characte
ri
stic of WSN is
their self-organi
zation a
nd dynami
c
behavio
r
whi
c
h im
plie
s that th
ere
might be
top
o
logi
cal
cha
n
ges from
tim
e
to time
th
at nee
d to
be
accomm
odat
ed by the time synch
r
o
n
ization schem
e
s
. In esse
nce
,
if new node
s join the network
and th
e net
work si
ze
gro
w
s, th
e time
synchro
n
ization
scheme
should
ada
pt i
t
self a
c
cordi
n
gly
and provide
the synch
r
onization se
rvice
s
to
the newly joi
n
ing nod
es,
howeve
r
the
synchro
n
ization schem
e should o
p
t for less deg
ra
d
a
tion of accura
cy. In WSN, node
s can re
port
data to sinks either in a flat-ba
s
ed
(pe
e
r-to
-
pe
er) or hierarchi
c
al
fashio
n and
accordingly the
time synchro
n
izatio
n sche
mes
can
be
flat-bas
ed o
r
hie
r
archi
c
al
. Compa
r
e
d
to peer-to-pe
er
synchronization, scalabilit
y is eas
ily achieved with
less overhead
by hierarchical and clust
e
r
-
based time
synchroni
zatio
n
sche
me
s such
as T
D
P [15], FTSP [14], and TPS
N
[4, 16]
etc.
, as
they keep a
provisi
on for
topologi
cal chang
es an
d
offer the flexibility to adapt acco
rdin
gly. In
su
ch syn
c
h
r
o
n
izatio
n sche
mes, ne
w no
des mi
ght
joi
n
a network from two
different poi
nts: n
e
w
node
s ente
r
into the direct
covera
ge area of ri
ng/clu
s
ter lea
der;
node
s join th
e netwo
rk at
a
Evaluation Warning : The document was created with Spire.PDF for Python.