TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 9, September  2014, pp. 68 7 4  ~ 688 3   DOI: 10.115 9 1 /telkomni ka. v 12i9.499 0          6874     Re cei v ed O c t ober 2 9 , 201 3; Revi se d Ju ne 28, 201 4; Acce pted Jul y  21, 201 4   A Cooperative Time Synchronization Protocol for  Wireless Sensor Networks       Min Li* 1 , Gu oq iang  Z h eng 1 , J i s hun  Li 2 , Le i   Fu 1   1 School of Infor m ation En gi ne erin g, Hena n  U n iversit y  of Sci ence a nd T e chnol og y,   H e na n  Lu oy ang , C h i na  2 Hena n Ke y   La borator y for Ma chin er y   Desi gn  and T r ansmission S y stem,   Hen an Un ivers i t y  of Scie nce a nd T e chnol og y, Henan L u o y a ng, Chi n a   *Corres p o ndi n g  author, e-ma i l : limin0 9 1 9 @1 63.com       A b st r a ct   T he sync h ron o u s pr ecisi on  of  synchr oni z a t i o n  pr otocol  is  lo w  and th e sc al abil i ty is  li mit e d strictly   i n  la rg e sca le wi re l e ss se nso r   netw o rks  (W SNs).Consi deri ng th e iss ue, a  nov el  coop erative  ti me   synchro ni z a ti o n  protoco l  bas ed on p u lse-c o upl ed osci llator s  and distri but ed diffusi on (C T SP) is propos ed   in this  pap er. T he pr otocol w o rks in tw o phas es clock tick s y nchro n i z a t i on  phas e a nd ti me synchr oni z a t i o n   phas e In the  clock tick sy nc hroni z ation   ph ase, the  ph ase s  of the  pu lse- coup led  osci ll a t ors is ch an ge d b y   the puls e  cou p l ed sig nal of th e SINK node.  T he tick syn chroni z a t i on of al l nod es is achi e v ed by distri but ed   diffusio n . In time synchro ni z a ti on ph ase, the  avera ge ti me  of re fe re n c e  no de s i s  sp read to a lim i ted num ber  of hops bas e d  on tw o-w a y messa ge e xchan ge  mec han is m. More over, in ord e r  to achieve  the  synchro ni z a ti o n  of entire  net w o rk, it adopts the metho d  of mutu al d i ffu sion to fin i sh t he a pprox i m at ely   synchro ni z a ti o n  b e tw een th e  no de ti me  an d the  av erag e  time  of al l n o des. By c o mp arin g CT SP w i t h  TPSN, we show that, CTSP  can syn chr oni z e  the network quickly with  good prec ision  conver genc e speed  and sca la bility,  w h ich appro p ri ates for large-s c ale W S Ns .     Ke y w ords : w i reless se nsor n e tw orks, pulse -coup led osc ill ators, cooper ative synchr oni zation, distri but e d   diffusion     Copy right  ©  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 s s  s e n s or n e two r ks  (WSN s ) nor mally  con s ist  of a large numbe r of sensors  distrib u ted ov er a given  area.  The s e lo w-co st se nso r s h a ve limite d  com puting,  commu nication,  and  se nsi n g  ca pa city [1]. WSNs  ca n  be  used fo r monito ring  [2-3], obj ect  locali zatio n  a nd  tracking [4 -5] ,  etc. Most of these ap p licatio n s  re q u ire the op e r ation of dat a fusion, po wer   manag eme n t, and  tra n smi ssi on  sche du ling am ong  a  large  set  of  sen s o r   node s, whi c h, in  tu rn,  requi re all the  node s run n in g on a com m on time frame .   Ho wever,  every individ ual  se nsor i n  th e WS N h a s  i t s o w n  clo c k.  Dif f e re nt  cl o c k s   drif t   from ea ch other over tim e  due to many factors,  such a s  impe rfection of the oscillato rs and   environ menta l  cha nge s.  This ma kes  clo c k synchroni zatio n  bet ween  different  node s  indispen sabl e .  In ad dition,  sen s o r   node s in a   WSN are too  ene rgy  con s trai ned  a nd  com putati on  limited to use any compl e x synchro n i z ation  sc hem es. Due to al l aforem entio ned  chall eng es,   several time  synchro n ization sch e me s for WS Ns hav e bee n propo sed  sin c e El son an d Ro m e r  first di scusse d this p r obl e m  in 200 2 [6], incl udi ng  the refe ren c e b r oa dcast  synchro n iza t ion  (RBS) p r oto c ol [7], time s y nchroni zatio n  proto c ol fo r sen s o r  net works (TPSN) [8], the delay  measurement  time syn c hronization p r o t ocol  (DM T S) [9], the flooding time  synchroni zatio n   proto c ol  (FT SP) [10], etc. Most of th e pro p o s ed synchro n ization  metho d s just  focus on   the  minimizi ng of synch r oni za tion error an d energy  co nsum ption, ignori ng the  requi rem ent for  scalability. At present, the ti me synchronization protocol s for si ngle-hop net works are very  mature  an d t he  synchro n i z ation  erro r  can a c hi ev e a bout u p  to  a  dozen mi cro s eco n d s . Th e  co st  is lower  whi c h can  satisfy  most appli c ations. As  to  multi-hop  synch r oni zatio n ,  it results in  the   accumul a tion  of syn c hroni zation  error o v er ho p  di sta n ce i n  la rge - scale  WSNs.  The the o reti cal  analysi s  a n d  nume r ical e x perime n t sh ow th e syn c hroni zatio n  e rro rs a r e p r o portion al to t h e   distan ce  of  hop s b e twe e n  no de s a n d  refere nce  nod es [11].  So there must be so me   synchro n ization error a c cu mulation an d can not  satisf y synchroni zation accu ra cy in large-sca l e   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Coope rati ve Tim e  Synch r oni zation Protocol  for  Wireless Sen s o r  Networks  (Mi n  Li)  6875 WSNs. In addition, the compli cate d cal c ulat io n and frequ ent data pa cket s  exchang e will   gene rally b u rden fo r the  n o rmal  ru nnin g  of WS Ns. Fu rtherm o re, wit h  the  gra dual  increa se  of t he  netwo rk scal e and  the n e t work-ba s ed  appli c ation,  it  become s  m o re  and m o re time to a c h i eve  synchro n ization [12].  In this pape r,  a coop erativ e time synch r oni zation p r otocol (CTSP )  is propo se d  to dea l  with the issue of low precisi on and scalability in  sensor nodes.  Accordi ng to  the distri buti on  cha r a c teri stics and  ene rg y information  of node s,  maste r  nod e s  are sel e cte d . Based o n  the  partition, the  algorith m   works in t w o pha se s cl ock tick syn c hroni zation  pha se a nd t i me   synchro n ization ph ase Si mulation re sults sho w   th at  the  unifie d   clo c k-ti ck can ultimatel y   be  reali z ed for n e twork no de s. In addition,  a salient  feat ure of the propo sed meth od is that, in  the  regim e  of  a symptotically  den se  netwo rks,   it  can  m a intain  glob al  syn c h r oni zat i on in  the  se nse   that all multi-hop net wo rk node s  can su ccessfully  achi eve  co nv ersi on fro m   synchro n icity  to   synchro n ization. And  be si de that  it ca n ext end ed holdin g  synchroni zatio n   ti me  a nd ha s  the  higher robust ness and scal ability.  The remain d e r of this p a p e r is  org ani ze d as follo ws: The related  works are reviewe d  in  Section 2. Section 3 fo rmulates th e time-syn ch ro nizatio n  pro b l em co nsid ered in this pa per.   Section  4 p r opo se s a   coo perative time syn c hronization p r otocol to  a nalyze th e  time   synchro n ization i s sue s . Th e re sult s  of e x perime n ts   an d   s i mu la tions  ar e d i s c u sse d  in Se c t ion 5 ,   followe d by the con c lu sio n s of this paper  given in Secti on 6.      2. Related Works  In re cent  yea r s,  nume r ou s syn c hroni zat i on p r oto c ol s  have b een  propo sed, fo cu sing  on   different  asp e cts of th e  synchroni zatio n  p r oble m  in  WS Ns [13]   . For the  tra d itional p r oto c ols,  they nee d a  root no de a n d  are  tre e -b ased, an d they  are  not fully  distrib u ted,  which  mea n s that  they are fra g ile to link or  node failu re s. Thus,  these traditional  proto c ol s are  not optimal for  handli ng clo c k syn c hroni zation in rand om mobile  se nso r  network. Existing distributed protocols  [14-16], the s e proto c ol s a nd the a s soci ated theo reti cal results a r e obtaine d a s suming th at the  topology of t he net work i s  conn ecte d  or join t  con n e cted,  whi c h  hold s  no lo nger i n  rand om  mobile sen s o r  netwo rk. Th ese p r oto c ol s also have  slo w  co nverg e n c e spee d.  There are some wor ks  which investigate Pulse-Coupl ed  Oscillator (PCO) for sensor   netwo rks. Th e nonli nea r d y namics of l a rge  pop ulat i ons  of PCO  were stu d ied  to describe  the  synchro nou s  fireflies fla s hi ng, observed  in the s outh  east of Asia  sin c e the pa st two centu r ie s.  The PCO al gorithm [1 7] makes  mu ch m o re  lib eral  use of  the phy sical co mmuni cation  con s trai nts th at are a c kno w led ged  po ssible  in  t r aditi onal pa cket-switch ed point -to-p o int  n e twork  model s. Fro m  the the o re tical p o int of  view, t he protocol   [14]  i s   ba sed on g o ssip avera g i n g   algorith m s, a nd the proto c ols GTSP in [16]   and ATS in [15] are base d  on average co nsen sus  algorith m ,  wh ich have slo w  conve r ge n c e sp eed   a s  pointed   in  [1 8].  The study   of con s e n su s  fo r  spa r se, mobi le Ad Ho c n e tworks is  p r opo se d in[1 9]. Recent result s in [20 ]  sho w  that  the  approximate  model u s ed i n  [21] to prove conve r ge nce doe s not, in fact, warrant conve r ge nce for  all conn ecte d  networks. Note that the   convergi ng  sp eed  of the ti me  synchro n i z ation  is a  cri t ical  probl em in p r actice, while  most of existi ng co nsen su s ba sed p r ot ocol s, whi c h  aim to rea c h  an   averag e valu e within the network, are ti me-con su mi n g . And besid es the PCO  algorith m  is o n ly  provide s   a  unified ti cki n g  rhythm a c ro ss  se nso r  n ode s, n a m ely syn c h r onicity n o t the   synchro n ization of time. In orde r to real ize the  time  synchro n ization, the time of each  wirel e ss  sen s o r   nod es nee d to  be  synchroni zed.   Hen c e  it i s  of  great inte re st to devel op  a  protocol  whi c h  own s  mu ch faster  conve r g i ng time while  maintaining t he advanta g e s  of con s e n sus.       3. Summarize the Protoc ol Algorithm   The pe riodi ca l process of CTSP as sho w n in Figu re  1 is com p o s e d  of two majo r part s :  clo ck tick sy nch r oni zatio n  based o n  p u lse - coupl ed  oscillators an d time synch r oni zation. Each  cycle of syn c hron ou s execution pro c e ss is as follo ws:   1) Th e cl ock t i ck  syn c h r oni zation  ba sed  on pul se -cou pled o s cillators: Firstly, SINK node   emits  m   pulse s with  eq uidi stant zero-crossing.  T he surro undi ng node s re ceiv e  this pul se  seq uen ce, an d based on t he location s of the  obse r v ed ze ro -cro ssing s , the su rro undi ng no des  predi ct  when  the next pul se will  be  transmitted. Then, t hese nodes emit pul se at  their  predict ed  times a nd a n  agg regate  p u lse  se que nce is g ene ra te d. Although t he p r edi ction  at an individ ual  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 9, September 20 14:  68 74 – 688 3   6876 node may no t be perfect, unde r ce rtain  condition s o n  the pulse  and in asym ptotically den se   netwo rks [2 2-23], the zero -cro ssing s   of the ag gr e gate  wavefo rm  se quen ce  will b e  at the  sam e   positio ns  as t he zero -cro ssing s  of the  origin al wave form sequ en ce emitted  b y  the SINK node  due  to sp atia l  avera g ing. This agg reg a t e  pul se se q uen ce i s  h e a r d by th e no des lying fu rther  away from SI NK nod e and  these n ode s perform  pre d iction a s  de scribe d ab ove and emit th eir  pulses to  the i r predi cted ti me [3]. Perip heral   no des being add ed to  the  ra nks of  the  sendi n g   synchro n ization pul se by  outwa rd reca stion form ula.  After  m  pulse s, the new ag ent to join the   ran ks a nd th e more n ode s pul se can  gene rate sufficient en ergy  through  cou p ling. At last,  synchro n ization pul se s ar e sent by all  the node s i n  the net works  at the sa me time, na mely,  achi eving syn c hroni zation  state   [24-25].  2) The time  synchroni zatio n  pha se: Firstly,  with two-way message  excha nge mo dels, all   neigh bor  nod es time in th e maste r -nod e domai n is   obtaine d, and  the avera ge  time of node s i n   broa dcast d o m ain is  cal c ul ated. Seco ndl y, the ma ster-nod e is  synchroni ze d to the avera ge tim e   of all node s  in the ma ste r-n ode  bro a d c a s t domai n, and then  d e fines th e m a ster's time  as  referen c e time. The diffusi on-n ode s a r e  cho s en o n  the basi s  of averag e tran sm issi on del ay and   energy, which just begin s   from t he mast er-nod e and i t s spread to,   hop s distan ce node s from  maste r-n ode.  The  nod es within   hop s di stan ce f r om t he ma ste r  n o des will  re cei v e more  clo c k  synchro n ization informatio n from  the sa me maste r  n ode or differe nt master no des. By usin g of  the informatio n to update local  cycle th e clo ck an d o peratin g   cycl e according t o  the pro c e ss  of implement ation, the network will  com p le te synchronization process at a time.  A ssu me t hat   N  se nsor n ode s of la rg e-scal e  WSNs  have hi gh de nsity i n  the   recta ngul ar a r ea  of  W W  a c cording to  a  uni form p r o babil i ty distrib u tio n . In a ddition  to the   SINK, the hardwa r e facilitie s of  any other network no d e  are si milar  and the com m unication ra ng   o f  s e ns o r  no de s  is R . Using  straightforwa r d  broad ca sting  or  flooding, SINK can re a lize the initial  informatio n o f  startup  syn c hroni zation  and the  refe rence nod es  electio n  tran sfer ope ration  to  sensor nodes. The implem entation  of two stages will  be  described in the fo llowing discussi on.       1 T t     Figure 1. Cycle Implement ation of Synchroni zatio n  Protocol       4. The Coop erativ e Time  Sy nchroniza tion Protoc o l  Scheme  4.1. Clock Tick Sy nchronization  Ba s e d  on Pulse-Coupled Oscil l ators   In the phase, each n o d e  is co nsi d e r ed a s  a co ntrollabl e oscillator. Th e cou p ling   intera ction  be tween  nod es  in the n e two r k i s  mai n ly finish ed th rou gh tra n smitting and  receiving  the pe riodi c  narro w pul se  sign al, and  then real i z e s   the node  pha se synch r ono us.  In  t h is  scheme,  ea ch nod e (say  node i ) in  th e sensor net work i s   asso ciated with an  in crea sin g   monotoni c ph ase fun c tion  ) ( t i  taking valu es  from 0 to 1, defined a s :    ) 0 ( ) ( i i T t t                                                                             (1)    If a nod e i s  i s olated, the  st ate fun c tion  j x  in c r e a s e s  linea r l y fr om 0 to 1   s m oo th ly as  a   func tion of time as  follows:     N j f x j j j j ,..., 2 , 1 1 , 0 ) ( ， ，                                               (2)  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Coope rati ve Tim e  Synch r oni zation Protocol  for  Wireless Sen s o r  Networks  (Mi n  Li)  6877 ) ( t X j ) ( t X j re f ) ( t j 1 1 ) ( ) ( b t bx j e e t j X ) ( f X     Figure 2. Gen e ral Mo del of Pulse - Couple d  Upd a ting Dynamics      The no de em its a pul se wh en the state f unc tio n  achie v es the threshold value  ( 1 j x ). After the  pulse titillated, the node  will immediat ely reset its  state to ze ro  so that emi s sion pul se can  be   sent in the pe riodi c T . If a node is not isol ated, it can rece ive p u lse s  from other n ode s and the n   cha nge the st atus varia b le.  The phase functio n   ) ( t i  repla c e s  the state  function  j x  ch ange s   accordingly a s :    () () ( ( ) ) 1 () 1 j jj bx t j b xt B x t e t e                                                                             (3)    And  ） （ 1 ) 0 ( ) 1 0 ( 1 0 ) ( x x x x x B . This mean s that a node re ceivin g  a  pulse eithe r  emits the p u lse at  the same tim e  or sho r ten s  the waiting time for  the next cycle of e m issi on s. It can be sh own that  only when th e node s emit  the pulse si multaneo usly  will they be insen s itive to coupli ng, a n d   therefo r e a c hi eve syn c hron iz ation. If there is time  0 t  su ch that meet s  (4),  we  con s i der all  nod es  achi eve clo ck tick syn c h r on ization:     N n t t t t t t n i , ), ( ... ) ( ... ) ( ) ( 0 2 1                                                  (4)    It may trigge r infinity a n d  ci rculation  firing  problem,  be cau s e  of  cou p ling  dela y  is n o t   con s id ere d ,  namely infinite feedba ck [2 3].  Node  i   firing can result in node  j  and other no de s  firing,  cou p lin g data  pa cket  whi c h   sendi n g  ba ck from  j   and  othe r n o des firin g  ma y cau s e s  nod e   i   firing a gain.  If  i   firing breaks out in the network, a new   cycl e of the fi ring nodes will  be  happ en ag ai n and  cau s e  infinity and circulatio n firi ng. In ord e r t o  avoid infini te feedba ck, we  sup p o s ed th at after a no de fire s a pu lse, it ent ers a sho r t refra c tory pe riod,  durin g whi c h  no  sign al can b e  received from other no des. That  me ans the no de  cann ot resp onse to the new  firing sig nal. It can better  solve infinite feedba ck pro b l e m of node s.    4.2. The Time Sy nchronizatio n  Phase     The  pulse-co upled  algo rit h m  only p r ov ides a u n ifie d ticking  rhy t hm acro ss  sen s o r   node s, nam e l y synch r oni city not the synchroni zati o n  of time. In orde r to  re alize th e tim e   synchro n ization, ea ch  sen s or n ode  time ne ed s  to  b e  syn c h r o n ized. So  we  sh ould  ma ke  use of   the co ncept  of distri but ed  diffusin g   and e m pl oy  maste r-n ode s  and diffusi o n -no d e s  dyn a mic   electio n  me chani sm, the  maste r-n ode s  and diffu sio n -no d e s  a r e  ch osen o n   the ba sis of  the   energie s  an d  averag e tra n smi ssi on d e l ay. The net work time  sy nch r oni zatio n  is a c hieved  b y   usin g the inte r-diffu sion m e thod, the averag e time  of the master-n ode dom ain i s  diffuse d finite  hop s ba se d o n  the two-wa y messag e e x chan ge m e chani sm. Th e  entire  network n ode s time  ha s  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 9, September 20 14:  68 74 – 688 3   6878 been  app roxi mately synch r oni zed to  averag e time.  T he  ma ster-no des ele c tion must satisfy  the  following rules   Rule 1.  A s su me that ea ch  node  maintai n s th re shol d  value . During  the ele c tion  of the  maste r-n ode s, each n ode   gene rate s a   rand om  num ber , 1 , 0 .  r e pr es en ts  th e ra tio   o f   the current  resid ual  ene rgy and  the  first  maximum  ene rgy  of th e no de,   is  expre s sed  a s   follow:      1 -                                                                                   (5)    Provided  that    implie s th at the n ode  ca n be  de cla r e d  a s  a  ma ste r-n ode. In  (5 ),  the thresh old  value  of   de termine s  th e  numbe r  of n ode s all o ws  decl a rin g , th e ratio of th e  maste r-n ode s for netwo rk n ode s is 1 .  Rule 2.   All  node s, satisfying Rule  1, wait  ce rtai n time  and  sen d  a m a ster-n ode   statement  m e ssag e in it s bro a d c a s t d o main s  stoch a stic. If othe r node s  sati sfy Rule  1 in i t s   broa dcast  ra nge, the s e  n ode s  will exit  the  as  the m a ster-n ode s comp etit ive; If neigh bor n o des  receive different statement mess ages  or packet collisions in th e scope of their broadcasts  domain s , the s e no de s wi ll immediatel y send a  re spo nd for  conflicting inf o rmatio n. Up on  receiving the  resp on se m e ssag e, the node that st a t ements issu es pa cket  in accordan ce  with   prob ability 1/2 determi ne s whethe r to continue  se n d i ng the state m ent messa g e  as the p r im ary  node  until n o t  existing the  neigh bo r n o des ,whi ch  receive  de cla r ation p a cket s from  differe n t   node s in bro adcast s  dom ains of sendi ng nod e  stat ement me ssage; If its neighbo r nod es in   broa dcast ra nge re ceive only  the stat ement  m e ssage, the n  th e no de that  se nt statem ent  messag e  can  begin  to exe c ute  synchro n izatio n afte r waiting  for  a  ce rtain p e ri o d  of time. Th e   maste r-n ode s ele c tion i s   multi-cy cle; e a ch  second  will be re-electi on to the  mast er-nodes in  synchro nou s time .    4.2.1. The Av erage Time  of Nod e  in Maste r -Node  Broad cas t Domain  A ssu ming t h a t   S  nod es a r e  electe d to be  the maste r -n ode, and the  numbe r of no des in   each ma ster-node  bro a d c ast dom ain i s   ( 1 , 2 , ..., ) j nj s ,  ） （ l n l l l j j c c c c ,..., , 2 1  is the tim e  value   of   j n neighb or  node s i n  the   maste r-n ode   electio n  b r oa dca s t d o mai n  at time   l ,  ( 1 , 2 , ..., ) l kj ck n   is the   time v a lue of  nod e  at time  l  , where  l c 1  is th e ma ster-no de' s ti me value. T h e a c qui sition   pro c e ss of av erag e time in maste r-n ode  broa dcast do main as follo ws   1) T he m a ste r-n ode  broad ca sts  a  ch-qu e st p a ck et  (in c ludi ng the  sync-start  of st art time   synchro n ization, the  ma ster-no de ID, the local  time value )  to sta r t a  new cy cle  of  synchro n ization;  2) A c cordi n g  to the  ch -q u e st p a cket, t he n e igh bor  node s  se nd  ACK re sp on se pa cket  contai ning  a t i mestam p (i n c ludi ng the  lo cal time  value  wh en n ode  receivin g ch-q uest  pa cket, the   local time val ue wh en no d e  tran smitting  ACK packet, the neighb or node s ID) af ter ce rtain time  of rando m wa iting   3)  Whe n  re ceived t he  resp on se p a cket the  ma ster-n ode s  st art to  cal c ul ate the   prop agatio n  delay b e twe e n  no de s, an d  then  se nd   a  syn c -co n tinu e pa cket(i ncl uding  syn c -fl ag,  the delay  k d  between m a ste r -nod e an d re spo n sive n e i ghbo r no de  k , the node  k  ID and the  transmissio n time of the cu rre nt broa dca s t inform atio n )  to the neigh bor no de. After the neig h b o r   node k re ceivin g the syn c -continue p a cket, we ca n o b tain the del ay  k d ,and othe r neig hbo r  node s i s  n o t rep eated  inf o rmatio n ex chang e by  re ceiving  the  sync-contin ue  pa cket until  the   maste r-n ode  reissu e  a  syn c -contin ue   pa cket  an d the n  wait f o r  a m a ximum d e la y time  max D  but  failure to  re ce ive the timest amp info rmati on from   neig hbor  nod es.  All of which show th e ma ster- node o b tain s the time information of all the neig hbo r n ode s.  Figure 3 sh o w s the m a ste r-n ode A bro a d c asts  the start time  synchro n izatio n pa ckets at  time l , accordi ng to the describ ed ste p s t o  impl eme n t the inform atio n excha nge p r ocess.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Coope rati ve Tim e  Synch r oni zation Protocol  for  Wireless Sen s o r  Networks  (Mi n  Li)  6879     Figure 3. A Sende r A -re ceiv e r B Two-way Ti ming Excha n ge Model       k  and   k d  denote  the cl ock  drift and  propa ga tion del ay bet wee n  n ode k an d nei ghbo r  n ode s,  then  k  and  k d can  be expre s se d as:     21 kk tt d                                                                                          (6)    21 4 3 21 4 3 T- 2 T 2 k k TT T TT T d    （） （ ） （） （ ）                                                                      (7)    At time l , the maste r-n ode   clo c k time  1 1 T c l  was m a in time  of the n e igh bor  nod es which  can   be written a s :     1 ll kk cc                                                                                              (8)    4) From (7)  and (8), all n ode s averag e time  l j c  and  averag e p r op agation  delay   j d   within the ma ster-no de bro adcast dom ai n at time  l  tak e  the form:    1 11 1 / / jj j nn ll l jk j k j kk n jk j k cc n c n dd n                                                             (9)    4.2.2. The Selection of  Diffusion - No de s and the  Diffusion of  Av erage Time   Usi ng a  reference time of  the avera ge t i me  of the m a ster-n ode, t he con c rete  sele ction  rule s of diffusion-n ode s wh ich imple m en t the average  time diffusion  as follows   Rule 3.  After  receiving the ch-que st pa cket of  first-o r der ma ster-n ode or diffusi on-n ode,   node p r od uces ra ndom n u mbe r , where ） （ 1 , 0 . 1 -  is calculat ed acco rdin g  to   the method  of electio n  the  maste r-n ode  and n ode e n e r gy. If 1 , the node can b e  a d i ffusion- node,  otherwise  ca nnot  b e com e  the  d i ffusion-nod e. The  thre sh o l d value   1  determin e s the   numbe r  of el ection  diffusi on-n ode s  an d relates to  n ode  den sity, comm uni cati on  radiu s  an d so  on. Sin c e    is va riation  with e nergy, the th re sho l d value   must adj ust  according  to   1 1  after each  cycle of  syn c hroni zation,  whe r e   can  set  f o r any  small po sit i ve  according to  appli c ation.   Rule 4.  The node re ceive d   the ch -qu e s t  pa cket  fo r  the upp er ma ster-no de o r   diffusion - node, an d then if  L kj dd  (whe r e   j d  corre s po n d s to the av erag e sin g le -hop del ay, L   stand s for  h op co mmuni cation a nd  k d  denote s  the  messag e del ay betwee n   node a nd th e   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 9, September 20 14:  68 74 – 688 3   6880 maste r-n ode  or  th e  u ppe r diffusion -no d e .),  the nod e   ca n be diffusion -no de,  ot herwise can n o t  become the  diffusion -no d e . Time spre ads o u t fr om the maste r-n ode s and the  diffusion pro c e ss  of average ti me is a s  follows   0-Diffu sion: the maste r -no de se nd s synch r on ou s p a cket whi c h  contai ns the  followin g   informatio n: the ma ster-n ode ID; the  averag e time l j c ; the averag e time tran smissi on h o p   numbe r , each  diffusion time the value minus 1; the av erag e delay j d .  1-Diffu sion:  whe n  the  0-diffusion  carri e s  out, the  1 - diffusio n  n o des an d the   neigh bor  node s which  cann ot obtain avera g e  time info rm ation of the same ma st er-nod e nee d to   comm uni cate  informatio n i n  the b r o adcast d o main,  and the n   co mputes the  a v erage  si ngle - hop   delay  j d  for all  the neigh bor  node s an d the 1-diffu sion  node s up dat es the receiving ma ster- node  averag e time fo r:   0, ll jj k cc d  ,where  0, k d  sta n d s fo r info rm ation p r op ag ation d e lay  betwe en the  cu rrent dif f usion - no de  and it s ma ster-no de; t he receiving  avera ge ti me  transmissio n hop numb e r   in the  diffusi on p a cket mi nus 1; the  averag e d e lay  j d  betwe en   the  ma ster-n ode and neig hbor  no de s i s  repl aced  by  1 d ，k ,which i s  the  averag e d e la y betwe en   curre n t diffusi on-n ode  and  its neig hbo r  node s; the u pdated  diffusi on pa cket was b r o a d c ast  to   the next hop of the neighb or nod es.   f -Diffus i on: the f -Diffu sion proce s s  is simil a r  with  1-Diffusio n .The diff usio n process is  repe ated until    hop distan ces from the m a ster-n ode.   Whe r e   de pe nds on  the  preci s ion  and  t he  spe ed  of the  synchro n i z ation  an d m u st b e   able to su re t he adja c e n t maste r-n ode  obtain the  av erag e time in  two maste r -node d o main s at  least a nd is  use d  a s  a time refe ren c e  to synchro n i s tically u pdat e, so   sat i sf i e s f o llo wing   conditions:    22 ( ) 2 2 WR W R N SS W R                                                    (10)    The ma ster-node ID i s   set to avoid  repe atedly  receiving the  time synchronization  informatio n from the sam e  master-no d e  domai n. Du ring a ce rtain  diffusion no des p e rfo r mi ng  diffusion, the  neigh bor  no des  have received the av erag e time d i ffusion info rmation fro m   the  same  ma ste r -nod e,  which  ha s  wa s  be en  confi r med  ba sed  on  th e recordi ng t he m a ste r -no d e   numbe r, and  it is no longer involved  in t he diffusion node inf o rmatio n exchang e; If all the   neigh bor n o d e s of diffusi on-n ode s ha ve been al re ady re ceived  the averag e  time diffusion  in fo r m a t ion  fro m  th e sa me mas t e r - n od e, th e  d i ffus i on - n od e w ill en d  th e d i ffu s i o n  pr oc ess  afte r   having be en  waited o n  for a certai n time .  Acco rdi ng to the re ceived a v erage time d i ffusi on pa cke t s of the master-nod e in the each  cycle of syn c hroni zatio n  time, the node  cal c ulate s  the  new time new T     [( ) ] ( 1 ) n e w M k l oc al Tc l d L T L                                                      (11)    Whe r e  ) ( l c M  is th e avera ge ti me of ma ste r-n ode s d o m a in,  k d  is n ode  prop agatio n   delay b e twee n  k  node  and   the ma ster-n ode  and   L  is the received  synchro n ization diffu sio n   packet s  n u m ber which  mi nus 1. If  ne w l oca l TT , the  update  of n o d e  is such th at new T , otherwi se  to maintain local time  local T  at consta nt value .       5. Experiment and Simulation Results  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Coope rati ve Tim e  Synch r oni zation Protocol  for  Wireless Sen s o r  Networks  (Mi n  Li)  6881 In orde r to validate the synchrono us e ffect  of the propo se d syn c hroni zatio n  al gorithm  simulate s th e  experi m ent  on the  Mica  Z platform.  G i ving the  co rrelative pa ram e ter valu e fo r the  simulatio n : monitori ng area   is 2 m 500 500 , 1 000 n ode s are  ra nd omly depl o y ed ,  comm uni cati on ra diu s  of sen s o r  no de s are m R 10 , the cou p ling st rengt h  is 02 . 0 ,  cy cle  time is 10 Ts , the simulatio n  time is 50min , and each  experim ent is the mean  of 100  simulat i o n s.     5.1.   Analy s in g the Co nv er gence o f  CT SP  In the previo us  se ction,  we analy z ed  a  sy nchrono us versi on of  CTSP alg o rit h m an d   given its im p l ement p r o c e dure.  We  wil l  analyze  the  conve r g e n c e of CTSP i n  this  se ctio n.  Suppo se that  the deviation s for all th e n ode s time  an d stan dard time are unifo rm distri buted  in  [L t , Ht]  at time l , CTSP satisfi e s convergen ce theo rem a s  follow.   Theorem 1 .  For la rge - sca l e se nsor n e twork, CTSP can  be g r ad u a l co nverg e n c e in  C ,  whi c h eq uals  to the averag e clo ck of all the nod es in t he network.  Pro v e Assu ming that the  numbe r of main no des i s   S  ea ch sele cted roun d,  j t H and   j t L denote  the m a ximum a nd  minimum val ue of  devia ti ons for th e a v erage  time  of S ma ster- node s dom ai ns after  j  s e t;  ) ( l c j n  and  ) ( l c std  stand f o r the arbitra r y nodes time  and sta nda r d   time after  j  se t o f  s y nc hr on iz a t ion ,  then  after  synchronizi ng   set,  the arbitra r y node tim e   ) ( l c n  sat i sf ie s:     11 1 1 ... ( ) ( ) ... tt t t n s t d t t t t L LL L c l c l H H H H                   (12)    We kn ow j t H C  an d j t H  is  noni ncre asin g. Letting  the infimum  of the  seri e s j t H  be  M ,we have  li m j t t HM C  .Su ppo se M C We will derive a contradi ction.   Con s id er th e  function   1 () i i x nx . Ch oose  x su ch t h at   1 1 () 1 n n M xM x n C n  wh ere  n  is the  num b e r  of sen s o r s. For any  ( , 1 , ..., 1 ) nn de fin e 1 to be th e set of  se nsors  who s e value s  are gre a ter than  () M xn  and  2 to be the set of the re st of the nodes. Fo r x ,  there mu st ex ist a time  t  su ch t hat t HM x ; also, there mu st b e  som e  nod e  who s e valu e  is   less than  () CM x n   becau se  C  is th e averag e value. Starting from sets 1  and 2  at time   t , we have  2 1 n  . After the first  averag e op eration for  nod es that  are  in   1  and 2 , we have  2 1 2 n  . After the first averag e o p e ration  on  no des in  1 1 n  and 2 1 n , we  have 2 2 3 n  . So,  this contradicts that the in fimum of  j t H  is  M .Therefo r e, we  have li m j t t HC  . In the s a me  way,  we can  prove  t hat  li m j t t LC  .Combinin g  the s e t w o  re sult s, we  have th a t  all the val u e s  o n   the sen s o r s  converg e  to  C.   Provide a  sta t ement that what  i s  expe cted, a s  stat ed in t he  "Int rodu ction" ch apter can   ultimately result in "Results and  Discu s sion"  chapt e r , so there i s  comp atibility.  More over, it ca n   also  be  ad de d the  prospe ct of  the  devel opment  of re sea r ch  re sult s a nd  appli c a t ion p r o s pe cts of  further  studie s  into the nex t (base d  on result an d discussion ) .    5.2.   CTSP Versus TPSN  Assu ming th e average  synchroni za tio n  erro r of e a ch  hop i s , the time to realize  synchro n ization b e twe en  one  hop  neig hbors i s  alm o st  id entical results whi c h   are . In the  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 9, September 20 14:  68 74 – 688 3   6882 con d ition  of the  same  net work  pa ramet e r, the  syn c h r oni zation  e r ror of  CTSP  a nd TPS N   can  be   expre s sed a s :   2 2 CT S P TP SN nS S W S S R N WR                                                        (13)    From  comp arison, it ca n b e   found  that synchro nou s error  of  CTSP is greatly redu ced.  The  com pute r  si mulatio n  result s of th e  TPSN an d  CTSP algo rith m are give n f o r  com pari s o n , by  mean s of the  Figure 4  we  can find that,  with t he wire less hop s in crea sing, the  synchro n ization   conve r ge nt ra te incre a se a s  loga rithm m ode ap proxim ately.        Figure 4. Synchroni zation  Conve r ge nt Rate       The syn c h r o n izatio n pro p o rtion valve  and k eepi ng  the synchroni zation time o f  the two   algorith m s wi th  different  n e twork scale con d it ion s  are given in Fi gure  5 and F i gure  6 Thro ugh   the  contrast a nd com pari s o n   of  syn c hron ization  p r opo rtion valve  of  different network scale s ,  we  can fin d  the  CTSP algo rit h m always p r ovides  an  eff e ctive techni que to  synchronize for all  kinds  of network  u nder vari ou s scen ario s.  As  well  as the  synchro n i z ation  pe rformance of  T PSN   algorith m  is relatively high er by the infl uen ce  of the  variety of the netwo rk scale. Therefore,  CTSP algo rithm can a dapt  to the chang e of network  scale very we ll.          Figure 5. Synchroni zation  Propo rtion   Figur e 6. Hol d ing Synch r o n izatio n Time       6. Conclusio n   In this pap er,  a coo p e r ative  synch r o n izat ion protocol, named  CTSP, has b een p r o posed  to solve  the   probl em s a ssociate d   with l o w  accu ra cy and poo r sca l ability,  whi c h   wid e ly  exist  i n   mo s t   c l oc ks  in  W S N s . T he p u l se -c o u p l ed  is  us e d  for  clo ck ti ck  syn c hroni zing, a nd the n e two r k  node s at the  same tim e  wi th distrib u ted  coo per ation diffusion are pre s ente d .  And  be sid e s,  t h e   conve r ge nce  of algo rithm  i s  a nalyzed  in  theo reti cal, a nd the   synchronizati on  erro r exp r e ssi on  is  given. That   dire ctly proves  th e b e tter  synchro n ization e r ror  perfo rman ce  of CTSP. The   5 10 15 20 25 30 35 40 45 50 0 5 10 15 T he num ber  of  hop C o nv erg e n c e ra t e  of   s y nc hro n i z a t i o n     T PSN CT S P 2 4 6 8 10 12 14 16 18 20 30 40 50 60 70 80 90 10 0 L eng t h  o f   ed ges  f o r   gr i d  t o p o P e rc en t age  of  S y nc h r oni z a t i on(% )     TP S N CT S P 2 4 6 8 10 12 14 16 18 20 20 40 60 80 10 0 12 0 14 0 16 0 T h e  ne t w or k  di am et e r T i m e   t o  S y nc hr oni z a t i on(N u m ber of  P e ri ods )     TP S N CT S P Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     A Coope rati ve Tim e  Synch r oni zation Protocol  for  Wireless Sen s o r  Networks  (Mi n  Li)  6883 simulatio n  re sults  demo n strate the correctne ss of  theoreti c al a nal ysis an d CTSP can effe ctively  hold l ong er  synchro n ization time, im p r ove th e  rate   of conve r ge nce   of synch r oni zation, a nd  signifi cantly redu ce th e  synch r oni zatio n  error.  As  our  future  wo rk, i t  is inte re stin g to eval uate  the  perfo rman ce  of the propo sed CTSP in a  netwo rk-wi d e scena rio wit h  a dynamic t opolo g y       Referen ces   [1]  Daoj in g He,  Li n Cu i, Hej i a o  H uan g. Desi gn  a nd ver i ficatio n   of enh anc ed s e cure  loca liz ati on sch eme  in   w i reless sensor net w o rks.  IEEE Transactio n s on P a ral l el  and  Distrib uted  Systems.  20 0 9 ; 20(7): 1 050 - 105 8.  [2]  Yik-Chu ng W u , Qasim C h aud hari, Erc h i n  Serp ed in.  Clock s y n c hro n izati on  of  w i reless s ens or   net w o rks.  IEEE Signal Processing Maga z i n e .  2011; 2 8 (1): 124- 138.   [3]  Duzu n Do ng,  Xi an gke L i a o , Yunh ao  Liu. E dge s e lf-mon i torin g  for  w i r e le ss sensor  net w o rks [J]. IEEE   T r ansactio n  on  Parall el an d Di stribed Syste m s.  2012; 23( 3): 514- 527.   [4]  W a i-Le ong  Ye o w ,  C hen-K h o ng T ham, W a i- Cho ong  W o n g . Ener g y  effici e n t multi p le  targ et trackin g  i n   w i rel e ss sens o r  net w o rks . IEEE Transactions  on Vehic u lar Technology . 200 7; 56(2): 91 8–9 28.   [5]  Jiming  Che n , Keji e Cao, Ke yo ng L i . Distri buted s ens or activatio n   al go rithm  for target tracking  w i t h   bin a r y  s ensor  net w o rks.  Cl us ter Computi n g .  2011; 1 4 (1): 5 5 -64.   [6]  Jerem y  E l son,  Ka y  Romer.   W i reless s ens or n e t w orks:  A ne w   re gim e  for time  s y n c hron izatio n.   Co mp uter Co mmu n ic ation R e view . 2003; 33( 1): 149– 15 4.  [7]  Jerem y  E l son,  Le w i s Gir od,  De bora h  Est r in.  F i n e -gra in ed  netw o rk ti me  sync h ron i z a ti on  usi n g   referenc e bro a d casts. 5th Sy mp osi u m  on O perati ng Syste m s  Des i g n  an d  Impl e m entati o n.  200 2: 147- 163.   [8]  Saura bh Ga ne ri w a l,  Ram K u mar, Mani  B  Srivastava. T i ming-s y nc  pr o t ocol for s ens or net w o rks.   Procee din g  of F i rst Internatio nal C onfere n c e  on E m be dd e d  Netw orked S ensor Syste m s . 2003: 13 8- 149.   [9]  Ping S u . De la y m easur eme n t time s y nc hr oniz a tion  for  w i rel e ss se nso r  net w o rks.  Int e l R e searc h .  200 3.  [10]  Shib o H e , Jimi ng C h e n , Yo u x ian  Sun. On  o p tima l  inform ation c aptur e b y  en erg y -co n strain ed m obi l e   sensor.  IEEE Transactions on Vehic u lar Technology . 20 10; 59(5): 39 –4 9.  [11]  Hu An-S w o l,  Sergi o  D S e rv etto. On the s c ala b il it y   of co oper ative tim e  s y nchro n iz ati on i n  p u ls e- conn ected n e tw o r ks.  IEEE Tr ansactions on  Information Theory . 2006; 5 2 (6 ): 2725-2 7 4 8 .  [12]  B y o u n g -Ku g  Ki m, Sung- H w a   Hon g , K y e ong  Hur. E nerg y - e fficient a n d  rap i d tim e  s y nc hr oniz a tion  fo r   w i reless sens or net w o rks.  IEEE Transactions  on Cons um er  Electronics . 20 10; 56(4): 2 258 -226 6.  [13]  Ill-Keu n  Rh ee,  Jaeh an  Lee;  J angs ub Kim.  Clock s y nc hro n izati on i n   w i r e less s ensor  net w o rks:  A n   overvi e w .  Sens ors . 2009; 9( 1): 56–8 5.  [14]  Nicol as Mar e c hal, Je an-B e n o it Pierr o t, Jea n -Mari e  Gorce .  F i ne s y nc hro n izati on for  w i r e less s ens or   net w o rks usi n g  goss i p aver agi ng alg o rith ms.  EEE International Confer ence on Comm unication s.  200 8: 496 3– 49 67.   [15]  Luca Sc he nat o, F ederic o F i or e n tin. Aver age tim e s y nc h: a co nsens us-bas ed  prot ocol for tim e   s y nc hro n izati o n in  w i r e less s ensor n e t w orks .  Autom a tica.  2011; 47( 9): 187 8-18 86.   [16]  Phili pp S o mm er, Rog e r W a t t enhofer.  Gradient clock synchroni z a tion  i n  w i reless se ns or netw o rks .  Procee din g s of  IPSN. 2009: 3 7 -48.   [17]  Rob e rto Pagl ia ri, Anna Scag li one. Scal ab le  net w o rk s y nc h r oniz a tion  w i t h  pulse-c oup le d  oscillat o rs.  IEEE Transactions on Mobile  Com p uting . 2 0 11; 10(3): 3 92- 405.   [18]  He Ji an pin g , C hen g Pe ng, S h i Li ng, C h e n  Ji mi ng. T i me s y nchro n izati on  i n  W S Ns: A ma xim u m va lu e   base d  co nsen sus ap pro a ch.   Proceedings of  the  IEEE  Conference on De cision and Control . 20 11:   788 2– 788 7.  [19]  Aleke i sh Kh al ed, Ezhi lche lv an Pa ul. C o n s ensus  in Sp arse, Mob ile  Ad Hoc N e t w orks . IEEE  T r ansactio n s o n  Paral l el a nd  Distribut ed Sys t ems . 20 12; 23 (3): 467– 47 4.  [20]  F u mito Mori, T a kashi Odag aki. S y nchro n i z ati on of co u p le d oscil l ator s on small- w o rld net w o rks .   Physica D: No nlin ear Ph en o m e na.  20 09; 2 38(1 4 ): 118 0-1 185.   [21]  Lucar ell i  D e n n is, W ang  IJeng.  D e ce ntra li z e d  sync h ro ni z a ti on  proto c ols w i th n e a r est nei gh bo r   communic a tio n . Proc. Second  Int’l Conf. Embed de d Net w o r ked Se nsor S y stems (Se n S ys ’04). 20 04:   62-6 8 .  [22]  W u  Jiansh e , Jiao Lic h e ng, Di ng Ra nran. Av erag e ti me s y n c hron izatio n in  w i rel e ss sens o r  net w o rks b y   pair w i s e mess ages.  Co mpute r  Communic a ti ons . 201 2; 35( 2): 221– 23 3.  [23]  Xi ao Y W ang,  Raje ev K Dok a nia,  Al yssa Ap sel. PCO-base d  s y nchro n izati on for cog n itiv e dut y-c y cle d   impuls e  rad i o s ensor n e t w orks .  IEEE Sensors Journal.  201 1; 11(3): 555- 56 4.  [24]  Mengfa n  Ch e ng, Han p i ng  Hu. Impulsiv e  s y nc hr on izati on of cha o tic  s y stems  w i th  time-var yin g   param eters.  Journa l of Co mp utation a l Infor m ati on Syste m s.  2012; 8(1 1 ): 475 9-47 68.   [25]  Jiming  Ch en,  Qing Yu, Y a n Z han g. F e e dback- base d   clock s y nc hro n izati on i n   w i r e less s enso r   net w o rks: A control the o retic  appro a ch.  IEEE Transactions on Vehicular Technology.  2010; 59( 6):   296 3-29 73.   Evaluation Warning : The document was created with Spire.PDF for Python.