無線傳感器網(wǎng)絡(luò)時鐘同步技術(shù),TimeSynchronizationinWirelessSensorNetworkSystem,提綱,一,三,概述,MAC層協(xié)議分類,二,MAC層避免信道沖突技術(shù),四,基于多信道的MAC層技術(shù),時間同步,由于物理上的分散性，網(wǎng)絡(luò)無法為彼此間相互獨立的節(jié)點提供一個統(tǒng)一的全局時鐘，每個節(jié)點各自維護(hù)它們的本地時鐘。由于這些本地時鐘的計時速率、運行環(huán)境存在不一致性，因此即使所有的本地時鐘在某一時刻都被校準(zhǔn)，一段時間后，這些本地時鐘間也會出現(xiàn)失步。為了讓這些本地時鐘再次達(dá)到相同的時間值，必須進(jìn)行時間同步操作。時間同步就是通過對本地時鐘的某些操作，達(dá)到為分布式系統(tǒng)提供一個統(tǒng)一時間標(biāo)度的過程。傳感器網(wǎng)絡(luò)自身協(xié)議的運行及基于其上的應(yīng)用，如標(biāo)記數(shù)據(jù)采集時間、時分多址接入、協(xié)同休眠、定位、數(shù)據(jù)融合等都需要網(wǎng)絡(luò)中節(jié)點的時鐘保持同步。時間同步算法設(shè)計必須考慮到兩方面的因素：1)減少時間同步自身帶來的能量消耗；2)提供較高時間同步精度以有效減少其它關(guān)鍵技術(shù)帶來的能量消耗。,WSN時間同步技術(shù)背景,集中式系統(tǒng)與分布式系統(tǒng)集中式：事件間有著明確的時間先后關(guān)系，不存在同步問題分布式：同步是必需的，只是對同步的要求程度不同無線傳感器網(wǎng)絡(luò)時間同步典型的分布式系統(tǒng)是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)同步協(xié)議需要解決的問題同步精度功耗可擴(kuò)展性,時間同步技術(shù)的分類,排序、相對同步與絕對同步遞進(jìn)關(guān)系排序只能區(qū)分事件發(fā)生的先后相對同步：維持本地時鐘的運行，定期獲取其他節(jié)點的時鐘偏移和飄移，經(jīng)過換算達(dá)到同步的目的。如RBS協(xié)議絕對同步：本地時鐘和參考時鐘保持一致，修改本地時鐘。如TPSN協(xié)議外同步與內(nèi)同步參考源不同，前者參考源為網(wǎng)絡(luò)外部，如GPS。后者參考源為網(wǎng)絡(luò)內(nèi)部某個節(jié)點的時鐘局部同步與全網(wǎng)同步同步對象的范圍不同,時間同步技術(shù)的應(yīng)用場合,多傳感器數(shù)據(jù)壓縮與融合鄰近傳感節(jié)點對相同事件的感知數(shù)據(jù)需要融合，基于時間戳判斷是否同一事件，需要時鐘同步低功耗MAC協(xié)議、路由協(xié)議不發(fā)送數(shù)據(jù)時，節(jié)點處于休眠狀態(tài)，網(wǎng)絡(luò)節(jié)點的同步休眠需要時鐘同步測距、定位（位置相關(guān)報務(wù)，LBS）距離測量和定位是基于無線電信號的傳輸時間，時間同步越準(zhǔn)確，距離測量也越準(zhǔn)確分布式系統(tǒng)的傳統(tǒng)要求分布式系統(tǒng)的數(shù)據(jù)庫查詢，狀態(tài)等一致性的要求協(xié)作傳輸、處理的要求協(xié)作傳輸是基于電磁波的能量累加效應(yīng)，多個節(jié)點以相同的調(diào)制解調(diào)方式同時發(fā)送信號，使得遠(yuǎn)處的匯集節(jié)點能接收到信號,硬件時鐘模型,基本名詞時間、晶振、時鐘（RTC）時鐘偏移（clockoffset）：是指兩個時鐘瞬時讀數(shù)的差。晶振計時的時刻與實際時刻的差值，反映計時的準(zhǔn)確性ClockSkew：是指兩個時鐘的頻率差。它可以看作是Clockoffset的一階導(dǎo)數(shù)。時間漂移(ClockDrift)：是指時鐘頻率的變化，反映晶振的穩(wěn)定性。實際晶振的頻率有可能隨著外界環(huán)境溫度、濕度的變化而有所改變。ClockDrift可以看作是Clockoffset的二階導(dǎo)數(shù)。速率恒定模型該模型認(rèn)為頻率保持恒定不變，最常用，但不適應(yīng)環(huán)境變化劇烈的場合飄移有界模型常用于確定同步誤差上下界，頻率穩(wěn)定度常用ppm（百萬分之一）飄移變化有界模型時鐘的漂移變化率是有限的。,軟件時鐘模型,軟件虛擬時鐘一般是個分段連續(xù)、嚴(yán)格單調(diào)的函,時間同步的不同目的,第一種是最簡單的一種，要求也最低，它只需要保證節(jié)點之間事件發(fā)生的相對順序，這樣就不需要節(jié)點具有相等的本地時間；第二種時鐘同步問題是保證節(jié)點之間的相對時鐘，在需要的時候，節(jié)點的本地時間可以與其他節(jié)點的本地時間相互轉(zhuǎn)換，目前大多數(shù)時鐘同步算法，都是針對該種同步問題；第三種即最高要求的同步就是全網(wǎng)同步，全網(wǎng)所有節(jié)點隨時都要與網(wǎng)絡(luò)中的一個參考時鐘同步，這就需要在網(wǎng)絡(luò)中傳播公共的時間標(biāo)記。,傳統(tǒng)同步：NTP與GPS,NTPNTP不適合于WSN體積、計算能力和存儲空間存在限制GPS每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時間信息地面接收裝置同時接收4顆衛(wèi)星的時間信息，采用偽距測量定位方法可計算出時間和位置信息缺點（室內(nèi)、功耗、安全性、分布式）,節(jié)點上的時鐘,hardwareclock振蕩器以固定頻率產(chǎn)生脈沖每隔一定脈沖后計數(shù)寄存器增加1OnlyregistercontentisavailabletosoftwareRegisterchangerategivesachievabletimeresolutionNodeisregistervalueatrealtimetisHi(t)Convention:smallletters(liket,t)denoterealphysicaltimes,capitallettersdenotetimestampsoranythingelsevisibletonodesA(node-local)softwareclockisusuallyderivedasfollows:Li(t)=qiHi(t)+fi(沒有考慮計數(shù)寄存器的益處)qiisthe(drift)rate,fithephaseshift時間同步就是要修正qi和fi,而不是計數(shù)寄存器,同步精確性,外部同步與外部的時間表（如UTC）同步Nodesi=1,.,nareaccurateattimetwithinbounddwhen|Li(t)t|<dforalli因此，至少有一個節(jié)點具有外部的時間表內(nèi)部同步無外部的時間表,所有節(jié)點具有公共時間表Nodesi=1,.,nagreeontimewithinbounddwhen|Li(t)Lj(t)|<dforalli,j,不精確的原因,Nodesareswitchedonatrandomtimes,phasesihencecanberandom隨機(jī)打開的節(jié)點的相位也是隨機(jī)的Actualoscillatorshaverandomdeviationsfromnominalfrequency(drift,skew)實際的振蕩器與標(biāo)準(zhǔn)的頻率之間有一定的隨機(jī)偏差Deviationsarespecifiedinppm(pulsespermillion),theppmvaluecountstheadditionalpulsesorlostpulsesoverthetimeofonemillionpulsesatnominalrateThecheapertheoscillators,thelargertheaveragedeviationForsensornodesvaluesbetween1ppm(onesecondevery11days)and100ppm(onesecondevery2.8hours)areassumed,Berkeleymoteshaveanaveragedriftof40ppmOscillatorfrequencydependsontime(oscillatoraging)andenvironment(temperature,pressure,supplyvoltage,.)振蕩器的頻率會隨著使用期限、溫度等因素而出現(xiàn)偏差Especiallythetime-dependentdriftratescallforfrequentre-synchronization,asone-timesynchronizationisnotsufficientHowever,stabilityovertensofminutesisoftenareasonableassumption,時間同步算法,Physicaltimevs.logicaltimeExternalvs.internalsynchronizationGlobalvs.localalgorithmsKeepallnodesofaWSNsynchronizedoronlyalocalneighbourhood?Absolutevs.relativetimeHardwarevs.software-basedmechanismsAGPSreceiverwouldbeahardwaresolution,butoftentooheavyweight/costly/energy-consuminginWSNnodes,andinadditionaline-of-sighttoatleastfoursatellitesisrequiredA-priorivs.a-posteriorisynchronizationIstimesynchronizationachievedbeforeorafteraninterestingevent?Post-factosynchronizationDeterministicvs.stochasticprecisionboundsLocalclockupdatedisciplineShouldbackwardjumpsoflocalclocksbeavoided?(Usersofmakesayyeshere.)Avoidsuddenjumps?,時間同步算法的性能和功能模塊,Metrics:性能度量Precision:maximumsynchronizationerrorfordeterministicalgorithms,errormean/stddev/quantilesforstochasticonesEnergycosts,e.g.#ofexchangedpackets,computationalcostsMemoryrequirementsFaulttolerance:whathappenswhennodesdie?Fundamentalbuildingblocksoftimesynchronizationalgorithms:Resynchronizationeventdetectionblock:whentotriggeratimesynchronizationround?Periodically?Afterexternalevent?Remoteclockestimationblock:figuringouttheothernodesclockswiththehelpofexchangingpacketsClockcorrectionblock:computeadjustmentsforownlocalclockbasedonestimatedclocksofothernodesSynchronizationmeshsetupblock:figureoutwhichnodesynchronizeswithwhichothernodes,WSNs中時間同步算法的限制,AnalgorithmshouldscaletolargenetworksofunreliablenodesQuitediverseprecisionrequirements,frommstotensofsecondsUseofextrahardware(likeGPSreceivers)ismostlynotanoptionlowmobilityOftentherearenofixedupperboundsonpacketdeliverytimes(duetoMACdelays,buffering,.)NegligiblepropagationdelaybetweenneighboringnodesManualnodeconfigurationisnotanoption,時間同步算法分類,基于Sender/Receiver的時間同步通信雙方中的發(fā)送節(jié)點需要記錄時間消息發(fā)送時刻的時間信標(biāo)，而接收節(jié)點則需要記錄時間消息接收時刻的時間信標(biāo)，同步過程中只需要一次通信。該模式的代表算法是洪泛廣播時間同步協(xié)議?；赗eceiver/Receiver的時間同步在實現(xiàn)時間同步的過程中，節(jié)點只需要在接收時間消息的時刻記錄時間信標(biāo)，而發(fā)送時刻不需要記錄時間信標(biāo)，節(jié)點只需要知道接收到時間消息的精確時刻。典型協(xié)議有RBS等。基于Pair-Wise的時間同步這種算法利用成對同步方法進(jìn)行發(fā)送節(jié)點和接收節(jié)點間的時間同步，然后擴(kuò)展到整個網(wǎng)絡(luò)形成網(wǎng)絡(luò)的時間同步。此類算法使得網(wǎng)絡(luò)的同步報文開銷較大，對于低開銷要求較高的工業(yè)無線網(wǎng)絡(luò)應(yīng)用有一定的局限性。而且同步階段所用時間隨節(jié)點數(shù)目的增加而線性增加,不適合對快速性要求較高的工業(yè)無線網(wǎng)絡(luò)。典型的算法主要有TPSN、LTS、Tiny-sync和Miny-Sync等。,1、基于接收者和接收者的時間同步機(jī)制基于接收者和接收者的時間同步機(jī)制充分利用了無線數(shù)據(jù)鏈路層的廣播信道特性，引入一個節(jié)點作為輔助節(jié)點，由該節(jié)點廣播一個參考分組，在廣播域內(nèi)的一組接收節(jié)點接收到這個參考分組，通過比較各自接收到消息的本地時間，實現(xiàn)它們之間的時間同步。2、基于發(fā)送者和接收者的雙向時間同步機(jī)制基于發(fā)送者和接收者的雙向時間同步機(jī)制類似于傳統(tǒng)網(wǎng)絡(luò)中的NTP協(xié)議，基于客戶機(jī)一服務(wù)器架構(gòu)。待同步節(jié)點向基準(zhǔn)節(jié)點發(fā)送同步請求包，基準(zhǔn)節(jié)點回饋包含當(dāng)前時間的同步包，待同步節(jié)點估算時延并校準(zhǔn)時鐘。3、基于發(fā)送者和接收者的單向時問同步機(jī)制為了避免往返傳輸時間(RTT：RoundtripTime)估計，減少交換消息的數(shù)量，同時兼顧可擴(kuò)展性、能量消耗和估算成本，、產(chǎn)生了基于發(fā)送者和接收者的單向時間同步機(jī)制。在基于發(fā)送者和接收者的單向時間同步機(jī)制中，基準(zhǔn)節(jié)點廣播含有節(jié)點時間的分組，待同步節(jié)點測量分組的傳輸延遲，并且將自己的本地時間設(shè)置為接收到的分組中包含的時間加上分組傳輸延遲，這樣所有廣播范圍內(nèi)的節(jié)點都可以與主節(jié)點進(jìn)行同步。,DMTS(DelayMeasurementTimeSynchronization),DMTS基于同步消息在傳輸路徑上所有延遲的估計，實現(xiàn)節(jié)點間的時間同步在DMTS機(jī)制中，選擇一個節(jié)點作為時間主(leader)節(jié)點廣播同步時間。所有接收節(jié)點測量這個時間廣播分組的延遲，設(shè)置它的時間為接收到分組攜帶的時間加上這個廣播分組的傳輸延遲，這樣所有接收到廣播分組的節(jié)點都與主節(jié)點進(jìn)行時間同步。時間同步的精度主要由延遲測量的精度所決定。主節(jié)點在檢測到信道空閑時，給廣播分組加上時間戳t0，用來去除發(fā)送端的處理延遲和MAC層的接入延遲。在發(fā)送廣播分組前，主節(jié)點需要發(fā)送前導(dǎo)碼和起始字符，以便接收節(jié)點進(jìn)行接收同步，根據(jù)發(fā)送的信息位個數(shù)n和發(fā)送每比特位需要的時間t，可以估計出前導(dǎo)碼和起始字符的發(fā)送時間位nt。接收節(jié)點在廣播分組到達(dá)時刻加上時間戳t1，并在調(diào)整自己的時鐘之前時刻再記錄時間t2，接收端的接收處理延遲就是(t2t1)。這樣，如果忽略無線信號的傳播延遲，接收節(jié)點從t0時刻到調(diào)整時鐘前的時間長度約為nt+(t2t1)。因此，接收節(jié)點為了與發(fā)送節(jié)點時鐘同步，調(diào)整其時鐘為t0+nt+(t2t1)。,發(fā)送者在信道空閑后或爭用到信道后才插入本地時間t0接收處理報文的時間：前導(dǎo)碼時間nt，報文處理時間t2-t1接收方的同步時刻為：t0+nt+t2-t1單報文同步同步精度低廣播方式同步能耗低最簡單直觀，未考慮傳播延遲和編解碼時間,DMTS機(jī)制通過使用單個廣播時間分組，能夠同步單跳廣播域內(nèi)的所有節(jié)點，同時無需復(fù)雜的運算和操作，是一種輕量的能量有效的時間同步機(jī)制。DMTS機(jī)制在多跳網(wǎng)絡(luò)中采用層次型分級結(jié)構(gòu)實現(xiàn)全網(wǎng)內(nèi)所有節(jié)點的時間步，為此定義了時間源級別的概念，時間源級別用來表示節(jié)點到時間主節(jié)點的跳數(shù)距離。每個節(jié)點都有一個時間源級別：時間主節(jié)點的級別是0；與時間主節(jié)點相鄰的節(jié)點，即時間主節(jié)點一跳范圍內(nèi)的節(jié)點屬于級別1；與級別i節(jié)點相鄰的節(jié)點，也就是到時間主節(jié)點的跳數(shù)為(i+1)的節(jié)點屬于級別(i+1)；以此類推每個節(jié)點的級別。時間主節(jié)點周期性廣播它的時間，與主節(jié)點直接或間接同步的節(jié)點在給定時間內(nèi)廣播且僅廣播一次它的時間。在一段時間間隔內(nèi)，節(jié)點收到時間廣播分組時，檢查發(fā)送該分組的節(jié)點級別是否低于自己的級別。如果是，就與這個廣播時間進(jìn)行同步，否則丟棄該分組。這樣，主節(jié)點的時間以最小跳數(shù)傳播到整個網(wǎng)絡(luò)內(nèi)的所有節(jié)點，并且全網(wǎng)內(nèi)時間廣播分組的總個數(shù)達(dá)到最少，等于網(wǎng)絡(luò)內(nèi)所有節(jié)點的個數(shù)之和，沒有任何冗余數(shù)據(jù)包傳輸。因此，在節(jié)點組大級別為N的傳感器網(wǎng)絡(luò)中，時間同步的最大誤差是單跳同步誤差的N倍。由于多跳網(wǎng)絡(luò)的每一跳誤差可能為正也可能為負(fù)，多跳同步誤差的總和可以抵消部分單跳誤差。,DMTS算法結(jié)合鏈路層標(biāo)記時間戳和時延估計等技術(shù)，消除了發(fā)送時間和訪問時間的影響，算法簡單，通信開銷小。DMTS單跳同步誤差受同步精度和計時精度影響。多跳精度隨跳數(shù)的增加而下降，由于誤差的正負(fù)相加抵消了一部分，兩跳的誤差約為單跳誤差的1.5倍。DMTS算法沒有估計時鐘的頻率偏差，時鐘保持同步的時間較短；也沒有消除時鐘計時對同步精度的影響，因而其精度不高，不適用于定位等要求高精度同步的應(yīng)用。,RBS(ReferenceBroadcastsynchronization),RBS協(xié)議不是去同步報文的收發(fā)雙方，而是去同步報文的多個接收者。如右圖所示：在由3個節(jié)點組成的單跳網(wǎng)絡(luò)中，參考節(jié)點每發(fā)出一個參考報文，其廣播域內(nèi)的其他接收者節(jié)點都將接收到該報文，并各自記錄下接收到該參考報文時的本地時刻。接收者相互交換它們記錄的時刻并計算差值，該差值就是接收者之間的時鐘偏移。,根據(jù)偏移信息可以實現(xiàn)發(fā)送者-接收者同步，若能精確地估計出報文傳輸延遲，這種方法將能夠取得很高的精度。然而僅根據(jù)單個報文的傳輸很難準(zhǔn)確地估計出傳輸延遲。左圖為發(fā)送者-接收者同步機(jī)制?？梢钥闯觯l(fā)送者-接收者同步機(jī)制的同步關(guān)鍵路徑為從發(fā)送方到接收方。關(guān)鍵路徑過長，導(dǎo)致傳輸延遲不確定性的增加，因此同步精度不可能很高。右圖則是接收者-接收者同步機(jī)制，其關(guān)鍵路徑大為縮短，完全排除了發(fā)送時間和訪問時間的影響。,RBS中是通過廣播同步信標(biāo)分組實現(xiàn)接收節(jié)點之間的相對時間同步，信標(biāo)分組本身并不需要攜帶任何時標(biāo)，不依賴于信標(biāo)的發(fā)送時間。由于無線信道的廣播特性，信標(biāo)分組相對所有接收節(jié)點而言同時發(fā)送到物理信道上，這樣就除去發(fā)送時間和訪問時間引入的時間同步誤差。對于傳播時間，RBS只關(guān)心各個接收節(jié)點之間消息傳播時間的差值。對于射頻信號來說，傳播時間差值非常小，RBS忽略了傳播時間帶來的時間偏差。,影響RBS機(jī)制性能的主要因素包括接收節(jié)點間的時間速率、接收節(jié)點非確定因素和接收節(jié)點的個數(shù)等。為提高時間同步精度，RBS機(jī)制采用了統(tǒng)計技術(shù)，通過發(fā)送節(jié)點發(fā)送多個消息，獲得接收節(jié)點之間時間差異的平均值。對于時間速率問題，采用最小方差線性擬合，直線斜率就是兩個節(jié)點的時間速率，直線上的點表示節(jié)點間的時間差異。RBS的缺點是對網(wǎng)絡(luò)有一定的要求，它不適合點對點通信的網(wǎng)絡(luò)，且要求網(wǎng)絡(luò)有物理廣播信道。擴(kuò)展性不好，因為節(jié)點間本地時間戳通信需要額外的消息交換開銷，不能很好地應(yīng)用到大規(guī)模的多跳網(wǎng)絡(luò)中。RBS有很大的交換次數(shù)，對于具有，2個節(jié)點的單跳網(wǎng)絡(luò)，需要O(n2)的消息交換，如果n很大時，消息交換開銷是相當(dāng)大的，導(dǎo)致節(jié)點的計算開銷也非常之大。RBS中接收節(jié)點之間進(jìn)行相互同步，但并不與發(fā)送節(jié)點同步；實際上，在WSN中發(fā)送節(jié)點很可能也是一個普通的網(wǎng)絡(luò)節(jié)點因而也需要同步，為使該節(jié)點和其它節(jié)點進(jìn)行同步，需要另外一個節(jié)點作為參照廣播發(fā)射節(jié)點，這導(dǎo)致了相當(dāng)高的能耗。,TPSN(Timing-syncProtocolforSensorNetworks),圖中的T1、T4用節(jié)點A的本地時間記錄，T2、T3用節(jié)點B的本地時間記錄。節(jié)點A向節(jié)點B發(fā)送一個同步請求報文。節(jié)點B在接收到該報文后，記錄下接收到時刻T2，并立即向節(jié)點A返回一個同步應(yīng)答報文，并把T2和該報文的發(fā)送時刻T3嵌入在報文中。當(dāng)節(jié)點A接收到該報文時，記錄下接收到時刻T4。令為當(dāng)節(jié)點A的本地時刻為T1時，節(jié)點A和B之間的時偏。報文的傳輸延遲均為d。,多跳TPSN,全網(wǎng)周期性同步“層發(fā)現(xiàn)”把網(wǎng)絡(luò)組織成最短生成樹逐層在相鄰兩層節(jié)點間同步網(wǎng)絡(luò)內(nèi)兩個節(jié)點的同步“后同步”查找兩個節(jié)點間的路徑在路徑的相鄰兩個節(jié)點間進(jìn)行TPSN同步,TPSN算法優(yōu)點：TPSN基于雙向報文交換，因此同步精度高。對任意節(jié)點其同步誤差取決于它距離根節(jié)點的跳數(shù)，而與網(wǎng)絡(luò)中節(jié)點總數(shù)無關(guān)，使TPSN同步精度不會隨節(jié)點數(shù)目增加而降級，從而使TPSN具有較好的擴(kuò)展性。TPSN算法的缺點：TPSN本質(zhì)上是對同步，因此全網(wǎng)同步的同步能耗高。一旦根節(jié)點失效，就要重新選擇根節(jié)點并重新進(jìn)行分級和同步階段的處理，增加了計算和能量開銷。另外，TPSN算法沒有對時鐘的頻差進(jìn)行估計，這使得它需要頻繁同步，開銷較大。,HRTS(HierarchyReferencingTimeSynchronizationProtocol),基于雙向報文交換的用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議具有同步精度高的優(yōu)點，但一次只能同步一對節(jié)點。n個節(jié)點的單跳網(wǎng)絡(luò)則需要n-1次同步操作，同步功耗較大。RBS只需要一次同步過程就可完成一個單跳網(wǎng)內(nèi)所有節(jié)點間的同步，同步功耗降低，當(dāng)然，同步精度也相對變差。HRTS是一種結(jié)合了RBS所使用的參考廣播同步技術(shù)和TPSN所使用的雙向報文交互同步技術(shù)，減少了同步所需的報文開銷。圖描述了層級時間同步的過程。假設(shè)單跳網(wǎng)絡(luò)有包含時間基準(zhǔn)節(jié)點在內(nèi)的3個節(jié)點BS、n1和n2。,步驟1：時間基準(zhǔn)節(jié)點BS發(fā)出一個同步請求報文，該報文隨機(jī)指定一個鄰居節(jié)點（例如n1）作為應(yīng)答者節(jié)點（即對應(yīng)于圖1中的B節(jié)點）。同時n2也記錄下該報文的接收到時刻，記為T2。步驟2：應(yīng)答者節(jié)點n1向BS節(jié)點發(fā)一個同步應(yīng)答報文，報文中包含了T2與T3。步驟3：現(xiàn)在BS節(jié)點已經(jīng)和n1節(jié)點進(jìn)行了一次雙向報文交換，BS節(jié)點計算出它與n1節(jié)點之間的時鐘偏移。步驟4：BS節(jié)點發(fā)送一個包含和T2信息的報文。步驟5：當(dāng)n1、n2節(jié)點接收到該報文，對于應(yīng)答者節(jié)點n1來說，只要將其本地時間減去就達(dá)到與BS節(jié)點的瞬時同步。對于其他節(jié)點來說，只要在其本地時間加上T2T2即可達(dá)到與BS節(jié)點間的瞬時同步,根節(jié)點和應(yīng)答者節(jié)點本質(zhì)上是采用TPSN同步。根節(jié)點和非應(yīng)答者節(jié)點本質(zhì)上是雙向報文交換同步（但非TPSN）。應(yīng)答者節(jié)點和非應(yīng)答者節(jié)點本質(zhì)上是接收者-接收者同步。HRTS協(xié)議充分利用了無線傳輸?shù)膹V播特性來進(jìn)一步降低LTS協(xié)議的同步功耗。,LTS(LightweightTree-basedsynchronization),LTS同步算法是一種與TPSN非常類似的算法。LTS側(cè)重于降低時間同步的復(fù)雜度，在有限的計算代價下獲得合理的同步精度。LTS有集中式和分布式兩個版本，在集中式版本中，首先以時間參考節(jié)點為根建立生成樹，然后從樹根開始逐級向葉子節(jié)點進(jìn)行同步：首先根節(jié)點同步其子節(jié)點，然后這些子節(jié)點再分別同步其子節(jié)點，如此繼續(xù)下去，直到全部節(jié)點都被同步。另外，為了達(dá)到最高的同步精度，要求生成樹的深度盡可能的小。在分布式版本中，任何節(jié)點都可以發(fā)起同步過程，不需要建立生成樹，但是每個節(jié)點都必須知道參考節(jié)點的位置，并且知道其到這些節(jié)點的路徑。節(jié)點根據(jù)自己的時鐘漂移確定需要同步的時間，需要同步時，節(jié)點選擇距離自己最近的一個參考節(jié)點，并向其發(fā)出同步請求，然后參考節(jié)點向該節(jié)點的路徑上的節(jié)點逐對進(jìn)行同步，直到該節(jié)點被同步。,在分布式同步算法中，由于節(jié)點有機(jī)會決定它自己的同步，這就節(jié)約了不必要的同步開銷。同時，通過融合同步請求，降低了相同路徑上請求的數(shù)目，節(jié)約了資源。在LTS算法中，網(wǎng)絡(luò)中的節(jié)點避免了TPSN中與多個上層節(jié)點同步，而只與其直接父節(jié)點同步，減少了消息交換數(shù)目和同步時間。該算法目的在于最小化復(fù)雜度以此降低能耗，精度一般。同步次數(shù)是節(jié)點距離根節(jié)點跳數(shù)的線性函數(shù)，降低了消息交換次數(shù)，同時也降低了同步精度。算法的運行時間與樹的深度成比例，因此具有最小深度的生成樹時，收斂時間最短，但構(gòu)造最小生成樹也需要一定的計算和通信開銷。算法依賴于節(jié)點和參考節(jié)點的信息可靠性，錯誤的消息導(dǎo)致同步失敗。,LTS算法與TPSN協(xié)議的區(qū)別在于，LTS算法中節(jié)點只與自己的父節(jié)點進(jìn)行同步，其同步次數(shù)是路徑長度的線性函數(shù)，同時精度也隨路徑的長度線性降低，即在降低計算代價的同時降低了同步精度。,基于receiver/receiver的時間同步,Inthisclassofschemesthereceiversofpacketssynchronizeamongeachother,notwiththetransmitterofthepacketRBS=ReferenceBroadcastSynchronization(Elsonetal)RBShastwocomponents:SynchronizereceiverswithinasinglebroadcastdomainAschemeforrelatingtimestampsbetweennodesindifferentdomainsRBSdoesnotmodifythelocalclocksofnodes,butcomputesatableofconversionparametersforeachpeerinabroadcastdomainRBSallowsforpost-factosynchronization,Tiny-Sync/Mini-Sync,該算法基于一個假設(shè)：傳感器網(wǎng)絡(luò)中的時鐘頻率恒定且線性相關(guān)。Tiny-sync算法的思想在每次獲得新的數(shù)據(jù)點時，首先與以前的數(shù)據(jù)點比較，如果新的數(shù)據(jù)點計算出的誤差大于以前數(shù)據(jù)點計算的誤差，則拋棄新的數(shù)據(jù)點；否則，采用新的數(shù)據(jù)點，拋棄舊的數(shù)據(jù)點。Tinysync算法僅需存儲三到四個數(shù)據(jù)點的信息。,節(jié)點i的硬件時鐘是時間t是一個單調(diào)非遞減的函數(shù)Ci(t)，在相當(dāng)長一段時間內(nèi)可以認(rèn)為保持不變。在一段時間內(nèi)節(jié)點間的時鐘頻偏或相偏的差值保持不變，根據(jù)節(jié)點之間的線性相關(guān)性可以得出：C1(t)=a12C2(t)+b12Tiny-Sync算法和MiniSync算法采用傳統(tǒng)的雙向消息設(shè)計來估計節(jié)點時鐘間的相對漂移和相對偏移。Sender-receiver雙向數(shù)據(jù)交換Node1sendsaprobemessagetonode2time-stampedwitht0Node2generatestimestamptbandrespondsimmediatelyNode1generatestimestamptr不等式:t0<a12tb+b12<tr其中a12和b12分別表示兩個時鐘之間的相對時鐘頻偏和相對時鐘相偏，相對時鐘頻偏表示兩者頻率之比，相對時鐘相偏表示兩者相位之差。如果兩個時鐘精確同步，相對時鐘頻偏等于1，而相對時鐘相偏等于零。三個時間戳(t0,tb,tr)叫做數(shù)據(jù)點，算法通過不斷地收集數(shù)據(jù)點來估計a12和b12，并且隨著數(shù)據(jù)點個數(shù)的增加，算法的精度不斷提高。,注意到a12、b12對應(yīng)的直線必定在所有的數(shù)據(jù)點對之間，因此圖中最陡的和最緩的兩條虛線給出了a12、b12的上下界。并且上下界的區(qū)間越小，精度越高。通過求解所有數(shù)據(jù)點約束下的線性規(guī)劃問題，別可以得到最優(yōu)解。但是，這種方法太過復(fù)雜，無法在計算資源有限的無線傳感器網(wǎng)絡(luò)中實現(xiàn)。,C2(t),數(shù)據(jù)點1,數(shù)據(jù)點3,t0,tr,C1(t)=a12H2(t)+b12,C1(t),Node1,Node2,t0,tr,tb,tb,a12,b12,參數(shù)估計,Relativedrifta12andoffsetb12Thetighterthebound,thehigherthesynchronizationprecisionRequireshighamountofdatapointsandquitecomplexAlgorithmsprecisionincreaseswiththeincreasednumberofdatapoints.,Tiny-Sync與Mini-Sync之間的不同,DifferentmethodsinselectingusefuldatapointsTiny-SyncKeeponlyfourconstrainsofalldatapointsDoesnoralwaysgivethebestsolutionfortheboundsMini-SyncisanextensionofTiny-SyncMoreoptimalsolutionwithincreasedcomplexityKeepsalsothedatapointswhichmaybeusefulbysomefuturedatapointstogivetighterboundsAdatapointisdiscardedonlyifitisdefinitelyuselessQuitecomplexselectioncriterion.,TS/MS算法是基于并非所有觀察的數(shù)據(jù)點都有效的思想。每個數(shù)據(jù)點有兩個限制漂移和偏移的元素組成，TS僅保持產(chǎn)生最佳邊界估計的四個約束。但算法可能會因為排除了一些當(dāng)時看來沒有而后來很可能提供最佳估計的數(shù)據(jù)點而導(dǎo)致算法效果并非一直是最佳。MS是TS算法的擴(kuò)展，以較小的計算代價獲得最優(yōu)解決方法。是為避TS算法排除將來可能有用的數(shù)據(jù)點而提出的，它通過定義一個標(biāo)準(zhǔn)來確保丟棄確實沒用的數(shù)據(jù)點。TS/MS通過多個數(shù)據(jù)點來提供具有確定誤差界限的偏移和估計，比一般簡單的雙程同步算法精度要高，且能夠容忍消息丟失，可以擴(kuò)展到任何允許雙向數(shù)據(jù)通信的網(wǎng)絡(luò)，適合與帶寬、存儲容量和計算能力非常有限的網(wǎng)絡(luò)。該算法的缺點：收斂時間比較長，同步開銷是一般成對同步算法的k倍。文獻(xiàn)中建議MS存儲40個三元組數(shù)據(jù)，存儲開銷較大。對于需要長期檢測的傳感器網(wǎng)絡(luò)應(yīng)用，傳感器節(jié)點低成本的晶體振蕩器很難保證時間速率和時間偏差的長時間穩(wěn)定性，因而影響估計結(jié)果。,FTSP(FloodingTimeSynchronizationProtocol),FTSP協(xié)議屬于發(fā)送者接收者協(xié)議。FTSP協(xié)議基于MAC層時間戳技術(shù)，發(fā)送者節(jié)點在報文中的多個位置嵌入不同的時間戳。發(fā)送節(jié)點在完成SYNC字節(jié)發(fā)送后在MAC層給以后發(fā)送的每個字節(jié)標(biāo)記時間戳，接收節(jié)點在接收完SYNC字節(jié)也做同樣的標(biāo)記，這樣在發(fā)送節(jié)點和接收節(jié)點處都獲得了多個時間戳，當(dāng)消息傳輸完后雙方分別對這些時間戳做同樣的處理。最后接收節(jié)點獲得(globaltime，localtime)時間對，因而得到相對于發(fā)送節(jié)點的偏移，調(diào)整本地鐘。FTSP算法對時鐘漂移進(jìn)行了線性回歸分析。FTSP算法考慮到在特定的時間范圍內(nèi)節(jié)點時鐘晶振頻率是穩(wěn)定的，因此節(jié)點間時鐘偏移量(時間速率)與時間成線性關(guān)系：通過發(fā)送節(jié)點周期性廣播時間同步消息，接收節(jié)點取得多個數(shù)據(jù)對(time，offset)，并構(gòu)造最佳擬合直線L(time)。通過回歸直線L(time)，在誤差允許的時間間隔內(nèi)，節(jié)點可直接通過L(time)計算某一時間點節(jié)點間的時鐘偏移量而不必發(fā)送時間同步消息進(jìn)行計算，從而減少了消息的發(fā)送次數(shù)并降低了系統(tǒng)的能量開銷。,FTSP也提供了多跳時間同步。多跳的FTSP協(xié)議采用洪泛(Flooding)的方法廣播時間基準(zhǔn)節(jié)點的時間。當(dāng)網(wǎng)絡(luò)中的時間基準(zhǔn)節(jié)點正常工作時，每個一段時間，它將廣播一個報文。廣播消息由三個域組成：時間戳(timestamp)，根節(jié)點工D號(rootID)和順序號(seqNum)。每次時間基準(zhǔn)節(jié)點發(fā)送一個新的報文指示變量的值就加1(可以理解為同步的輪數(shù))。當(dāng)接收到消息，節(jié)點計算它的全局時間和嵌入在消息中的發(fā)送節(jié)點的全局時間之間的偏移，更新自己的全局時間，并廣播自己的全局時間到鄰居節(jié)點。為避免在線性回歸中使用冗余信息，每個節(jié)點保留接收到的消息的最大序號和最后一次接收到的消息所使用的rootID。同步消息只有在seqNum大于目前接收到的最大序號且新消息的rootID小于或等于最后一次接收到的rootID時才用于回歸。另外，如果節(jié)點在ROOT_TIMEOUT時間內(nèi)沒有監(jiān)聽到同步消息，它就宣布自己為新的根節(jié)點。為確保網(wǎng)絡(luò)中僅有一個根節(jié)點，如果一個根節(jié)點聽到來自于節(jié)點號更低的節(jié)點的時間同步消息，就放棄自己的根節(jié)點狀態(tài)。,FTSP算法通過對收發(fā)過程的分析，把時延進(jìn)一步分為發(fā)送中斷處理時延、編碼時延、傳播時延、解碼時延、字節(jié)對齊時延、接收終端處理時延，進(jìn)一步降低了時延的不確定性。另外，通過發(fā)射多個信令包，使得接收節(jié)點可以利用最小方差線性擬合估算自己和發(fā)送節(jié)點的漂移和偏移差。通過良好的根節(jié)點選舉機(jī)制，針對根節(jié)點失效、新節(jié)點加入以及拓?fù)浣Y(jié)構(gòu)變化等情況進(jìn)行了優(yōu)化，使得算法的健壯性很好，適合于軍事等惡劣應(yīng)用情況。,FTSP是現(xiàn)有的典型時間同步協(xié)議中精度最高的同步協(xié)議，并且有良好的健壯性，不會因為個別節(jié)點的失效而收到影響。但FTSP基于MAC層時間戳技術(shù)的細(xì)節(jié)技術(shù)的實現(xiàn)來提高同步精度，使得FTSP協(xié)議的通用性不強(qiáng)。并且洪泛的方式使得能耗開銷巨大。用于ZigBee網(wǎng)絡(luò)的同步休眠與喚醒算法,同步算法總結(jié),通過分析發(fā)現(xiàn)，TPSN、LTS、和TSMS都用泛洪廣播的方式構(gòu)造層次樹，然后用雙程同步的方法進(jìn)行上下層節(jié)點間的時鐘同步。但它們都沒有有效地利用泛洪廣播的信息，致使同步階段消息丌銷較大。TPSN采用在MAC層做時間標(biāo)記達(dá)到了16.9us的同步精度，因此在設(shè)計算法時可以考慮采用MAC層標(biāo)記的方法提高同步精度。RBS算法在單跳內(nèi)有較好的同步精度，但不適合用來進(jìn)行多跳節(jié)點間的同步，對于分簇網(wǎng)絡(luò)可以考慮用這種方法同步簇內(nèi)節(jié)點。TSync用雙信道的方法，結(jié)合了廣播同步機(jī)制和雙程同步算法，消息開銷小。但它假定每個節(jié)點都知道它的下層鄰節(jié)點號，在真正進(jìn)行同步時這還是個需要解決的問題。對于一些對精度要求不高要求計算復(fù)雜度低的應(yīng)用，可以考慮用DMTS算法。對于一些剛加入網(wǎng)絡(luò)的節(jié)點可以用AD算法與其周圍節(jié)點進(jìn)行同步。根據(jù)不同的應(yīng)用環(huán)境，也可以用多種方法結(jié)合的方法進(jìn)行網(wǎng)絡(luò)同步。在多種條件衡量下，沒有一種是最優(yōu)的。對于不同的應(yīng)用要求可以從多方面權(quán)衡來選擇合適的算法。對于不同的設(shè)計目標(biāo)，每個算法都有優(yōu)于其他算法的地方，可以相互借鑒，來設(shè)計出更好的算法。,謝謝大家，歡迎提問！,