无线传感器网络中时间同步技术的综述

32520115MICROCOMPUTERAPPLICATIONSVol32No5Apr2011*徐世武王平黄晞施文灶徐雄伟(350007):,,,,,,,,,,,,:TheReviewofTimeSynchronizationAlgorithmforWirelessSensorNetworksXUShiwu,WANGPing,HUANGXi,SHIWenzao,XUXiongwei(SchoolofPhysicsandOptoElectronicsTechnology,FujianNormalUniversity,Fuzhou,350007,China)Abstract:TimeSynchronizationisoneofimportantprotocolforWirelesssensornetwork,itistheprerequisiteforotherprotocolreliableoperation.TherehavealotofTimeSynchronizationalgorithmsbeenproposed,inthelarge-scalewirelesssensornetwork,researchanewtimesynchronizationmechanismhasalotofchallenge,suchas,theaccumulationofsingle-hoperror,thecompensationoftimeoffsetandtimedrift,topologicalpropertiesofSynchronizationmechanism,andSynchronizationconvergenceTraditionalcentralizedsynchronizationmechanismcannotmeettheperformancerequirementsforlarge-scalewirelesssensornetworkDistributedConsensusTimeSynchronization,cooperativesynchronization,andGradientClockSynchronizationpresentsomenewsolutiontotimesynchronizationforwirelesssensornetworkWedetailedanalysisthesetimesynchronizationmechanism,WealsoproposedthefutureresearchdirectionsKeyword:Wirelesssensornetwork,centralizedsynchrony,distributedconsensussynchrony,cooperativesynchrony,gradientclocksynchronization,,,,,,MAC,,,,,MACTDMA,,,,MAC[1,2]2011-04-08*:(2008J0211)(2007F5039)(JB09071)(JB09076)5:2002,ElsonHotNets,,,,,NTP,,,,,,,[2]GPS,,GPS,,,[3],,,,,,,,,,,,,,,,,111,11(1):MAC(2):MAC,,(3):,(4):,(5):,MAC(6):12,,c(t)=ktt0wtdt+ct0:w(t),k,t;c(t),c(t)-c(t0),(1),(2),,(3),CktCit=aikCkt+mik,aik,332011,mik,aik1,mik0,,,,,13TPSN[4],,,,,MAC,,Mica,TPSN1761us,TPSNRBS[5],,,,,RBS,,,RBS,,RBS629us,DMTS[6],,:,t0,MACNA(),,t,t1,t2,,t0+tNA+(t2-t1),DMTS151usLTS[7]-,LTS,,,,,,,HRTS[8],,LTS,HRTSBTS[9]HRTS,,BTS,,HRTS,HRTS2/314,,,,,,,HuA,m,,mm+1,m+1,,[10][11][12],15(DistributedConsensusTimeSynchronization:DCTS)[13],,:ij,iXtkPtk,Xtk,ijtk,jitk,jUtkPtk,ji,ijtkjitk345:Oijt,j,(1),(2)ijtk=mink-1l=-l-1-kUtl+1-Ut1-Xtl+1-Xtl2(1)Ojitk+1=Ojitk+tk+1-Usjitk-1jitk(2)jitk=ijtkjitk[13]MICA2,2us,6us,[13],,,vi(3),v1=0,Nii,[13](3),[14][1],V*[14],,(4),D0,k[14],,,[15],,,10025%|Ni|vi-jNivj=jNixij(3)nD0log1v0TA,v0n2k2log1v0(4)[16],,,[16]24,100us[16],MoteLab,,[17]ATS,MAC,,jjt1,i,it1,i(it1,jt1)i(it2,jt2)(5),0,1,+ijij,,,ijij=limkijtk,ij,,ii,,v,minii0vmaxii0,,,[17][17]TmoteSkynodesATS,4,,(90-150us)30+ij=ij+1-Tjt2-Tjt1Tit2-Tit1(5)352011(FO-DCTS),,[18](SO-DCTS),,(6)(6),ti(k)ik,Nii,,i,SO-DCTSFO-DCTS,,tik=tik-1+jNitjk-1-tik-1-jNitjk-2-tik-2(6)16(GradientClockSynchronization:GCS)RuiFan,NancyLynchGCS(GradientClockSynchronization)[19],,,,,,,,,,,:,ij,ij0dij,dijijD=maxijdij,1itHit=t0hirdr,hit,01i,t1-hit1+Lit,(CSA),GCSfdijij1:itr0:r2Lit+r-Lit2:tii:Lit-Ljtfdij,f(D)=(d+logD/loglogD),,,,[20]DOd+DGCS,[20]GCSA,it:LitALit,itmaxjNiLjt,it,,,[21],OlogDGCS,[22],[1-O,1+O],T,T,,,[22]log1D,[23]GCS,,On,log1D,,[24]GTSP(GradientTimeSynchronizationProtocol),,,,,,(7),xit,Nii,,xss(8),iLit365:[24]Mica2,20,MAC,40us,140usxitk+1=jNixjtk+xitk|Ni|+1(7)itk+1=itk+jNiLjtk-Litk|Ni|+1(8)2,,,,,,,,,,,,,,,,,,,,,,,,,MAC,,,,,[1]SurendraRahamatkar,DrAjayAgarwa,lNarendraKumarAnalysisandComparativeStudyofClockSynchronizationSchemesinWirelessSensorNetworksInternationalJournalonComputerScienceandEngineering2010,02(03):536-541[2],,[J]2010,47(4):638-644[3]CLenzen,PSommer,andRWattenhoferOptimalClockSynchronizationinNetworksInProc7thACMConferenceonEmbeddedNetworkedSensorSystems(SenSys),USA,2009[4]SGaneriwa,lRKumar,andMBSrivastavaTiming-syncProtocolforSensorNetworksinProceedingsofthe1stInternationalConferenceEmbeddedNetworkedSensorSystems(SenSyss03),ACMpress,USA,November,2003138-149[5]JElson,LGirodandDEstrin,Fine-grainedNetworkTimeSynchronizationusingReferenceBroadcastsinProceedingsofthe5thSymposiumonOperatingSystemsDesignandImplementation(OSDI02),USA,December2002147-163[6]SuPingDelaymeasurementtimesynchronizationforwirelesssensornetworks,IntelResearchBerkeleyLab,2003[7]JVGreunen,JRabaeyLightweighttimesynchronizationforsensornetworks[C]The2ndACMIntlWorkshoponWirelessSensorNetworksandApplications,SanDiego,2003[8]HDa,iRhanTSync:ALightweightBidirectionalTimeSynchronizationServiceforWirelessSensorNetworks[C]ACMSIGMOBILEMobileComputingandCommunicationsReview,SpecialIssueonWirelessPAN&SensorNetworks,UniversityofColorado,January2004125-139[9]XuCN,ZhaoL,XuYJ,LiXWBroadcasttimesynchronizationalgorithmforwirelesssensornetworksProceedingsofthe1thInternationalConferenceonSensingChina,2006:2366-2371[10]HuA,ServettoSDOnthescalabilityofcooperativetimesynchronizationinpulse-connectednetworksIEEETransactionsonInformationTheory,2006,52(6):2725-2748[11],,[J]200845(1):138-145[12]AHu,SDServettoAscalableprotocolforcooperativetimesynchronizationusingspatialaveraging[OL]IEEE/ACMTransac372011tionsonNetworking,October2006[13]RSolis,VBorkar,andPKumarAnewdistributedtimesynchronizationprotocolformultihopwirelessnetworksUniversityofIllinois,TechRep,April2005[14]GiridharAandKumarPRDistributedclocksynchronizationoverwirelessnetworks:algorithmsandanalysisProceedingsofthe45thIEEEConferenceonDecisionandContro,lSanDiego,USA,20064915-4920[15],,[J],2010,3