無線傳感器組網(wǎng)-時間同步技術

第七章、時間同步技術內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結基本概念時間同步的定義WSN時間同步技術背景時間同步技術的分類時間同步技術的應用場合關鍵問題：時鐘模型時間同步技術的定義無線傳感器網(wǎng)絡中每個節(jié)點都有自己的內(nèi)部時鐘，即本地時間。由于不同節(jié)點的晶體振蕩頻率存在偏差，再加上溫度的差異、電磁波干擾等，即使在某個時間點所有節(jié)點時鐘一致，一段時間后他們的時間也會再次出現(xiàn)偏差。無線傳感器網(wǎng)絡的時間同步是指各個獨立的節(jié)點通過不斷與其他節(jié)點交換本地時鐘信息，最終達到并且保持全局時間協(xié)調(diào)一致的過程。即以本地通信確保全局同步。思考為什么需要時間同步？時間同步能解決什么問題？根據(jù)CSMA/CA協(xié)議，當節(jié)點要傳輸一個分組時，它首先偵聽信道狀態(tài)。如果信道空閑，而且經(jīng)過一個幀間間隔時間DIFS后，信道仍然空閑，則站點立即開始發(fā)送信息。如果信道忙，則站點始終偵聽信道，直到信道的空閑時間超過DIFS。當信道最終空閑下來的時候，節(jié)點進一步使用二進制退避算法，進入退避狀態(tài)來避免發(fā)生碰撞。CSMA/CA協(xié)議需要嚴格的時間同步網(wǎng)絡節(jié)點在進入退避狀態(tài)時，啟動一個退避計時器，當計時達到退避時間后結束退避狀態(tài)。在退避狀態(tài)下，只有當檢測到信道空閑時才進行計時。如果信道忙，退避計時器中止計時，直到檢測到信道空閑時間大于DIFS后才繼續(xù)計時。當多個節(jié)點推遲且進入隨機退避時，利用隨機函數(shù)選擇最小退避時間的節(jié)點作為競爭優(yōu)勝者。偵聽偵聽睡眠睡眠●節(jié)點協(xié)同進行周期性偵聽和睡眠的狀態(tài)切換，確保節(jié)點能同步進行偵聽和睡眠調(diào)度?！裾{(diào)度周期：周期性偵聽和睡眠的時間之和為一個調(diào)度周期。S-MAC協(xié)議需要嚴格的時間同步S-MAC協(xié)議(SensorMAC)是在802.1lMAC協(xié)議的基礎上，針對傳感器網(wǎng)絡的節(jié)省能量需求而提出的。流量自適應偵聽機制的基本思想是在一次通信過程中，通信節(jié)點的鄰居在通信結束后不立即進入睡眠狀態(tài)，而是保持偵聽一段時間。如果節(jié)點在這段時間內(nèi)接收到RTS，則可以立刻接收數(shù)據(jù)，無須等到下一次調(diào)度偵聽周期，從而減少了數(shù)據(jù)分組的傳輸延遲。如果在這段時間內(nèi)沒有接收到RTS，則轉入睡眠狀態(tài)直到下一次調(diào)度偵聽周期。流量自適應偵聽機制需要時間同步RTSA數(shù)據(jù)1RTS數(shù)據(jù)2BCTSACK偵聽睡眠偵聽CTSACKBCTSACK偵聽偵聽CTSACKRTSA數(shù)據(jù)1RTS數(shù)據(jù)2偵聽睡眠WSN時間同步技術背景集中式系統(tǒng)與分布式系統(tǒng)集中式：在事件間有著明確的時間先后關系時，不存在同步問題；時間關系不明確時仍存在。分布式：同步是必需的，只是對同步的要求程度不同需要解決的問題同步精度功耗可擴展性WSN時間同步機制的主要性能參數(shù)最大誤差：一組傳感器節(jié)點之間的最大時間差或相對外部標準時間的最大差值。同步期限：節(jié)點保持時間同步的時間長度。同步范圍：節(jié)點保持時間同步的區(qū)域范圍?？捎眯裕悍秶采w的完整性。效率：達到同步精度所經(jīng)歷的時間以及消耗的能量。代價和體積：需要考慮節(jié)點的價格和體積。時間同步技術的分類根據(jù)同步的級別，可以分為排序、相對同步與絕對同步，其間為遞進關系。排序只能區(qū)分事件發(fā)生的先后相對同步：維持本地時鐘的運行，定期獲取其他節(jié)點的時鐘偏移和飄移，經(jīng)過換算達到同步的目的。如RBS協(xié)議絕對同步：本地時鐘和參考時鐘保持一致，修改本地時鐘。如TPSN協(xié)議根據(jù)參考源不同，可以分為外同步（與外部某時間同步，如GPS）與內(nèi)同步（網(wǎng)絡內(nèi)部某個節(jié)點的時鐘）。根據(jù)同步對象的范圍不同，可以分為局部同步與全網(wǎng)同步時間同步技術的應用場合多傳感器數(shù)據(jù)壓縮與融合鄰近傳感節(jié)點對相同事件的感知數(shù)據(jù)需要融合，基于時間戳判斷是否同一事件，需要時鐘同步低功耗MAC協(xié)議、路由協(xié)議不發(fā)送數(shù)據(jù)時，節(jié)點處于休眠狀態(tài)，網(wǎng)絡節(jié)點的同步休眠需要時鐘同步測距、定位距離測量和定位是基于無線電信號的傳輸時間，時間同步越準確，距離測量也越準確分布式系統(tǒng)的傳統(tǒng)要求分布式系統(tǒng)的數(shù)據(jù)庫查詢，狀態(tài)等一致性的要求協(xié)作傳輸、處理的要求協(xié)作傳輸是基于電磁波的能量累加效應，多個節(jié)點以相同的調(diào)制解調(diào)方式同時發(fā)送信號，使得遠處的匯集節(jié)點能接收到信號時間同步技術的重要性時間同步技術對無線傳感器網(wǎng)絡的節(jié)點定位、無線信道時分復用、低功耗睡眠、路由協(xié)議、數(shù)據(jù)融合、傳感事件排序等應用及服務，都會產(chǎn)生直接或間接地重要影響。時間同步機制幾乎滲透至每一個與數(shù)據(jù)相關的環(huán)節(jié)，其實現(xiàn)的好壞直接決定了以數(shù)據(jù)為中心的無線傳感器網(wǎng)絡整體系統(tǒng)性能的優(yōu)劣。關鍵問題：時鐘模型硬件時鐘模型軟件時鐘模型硬件時鐘模型基本名詞時間、晶振、時鐘（RTC）時鐘偏移（clockoffset）：是指兩個時鐘瞬時讀數(shù)的差。晶振計時的時刻與實際時刻的差值，反映計時的準確性時鐘率偏移（ClockSkew）：是指兩個時鐘的頻率差。它可以看作是Clockoffset的一階導數(shù)。時間漂移(ClockDrift)：是指時鐘頻率的變化，反映晶振的穩(wěn)定性。實際晶振的頻率有可能隨著外界環(huán)境溫度、濕度的變化而有所改變。ClockDrift可以看作是Clockoffset的二階導數(shù)。速率恒定模型該模型認為頻率保持恒定不變，最常用，但不適應環(huán)境變化劇烈的場合飄移有界模型常用于確定同步誤差上下界，頻率穩(wěn)定度常用ppm（百萬分之一）飄移變化有界模型時鐘的漂移變化率是有限的。軟件時鐘模型以軟件虛擬時鐘一般是個分段連續(xù)、嚴格單調(diào)的函數(shù)相關術語信標節(jié)點和未知節(jié)點鄰居節(jié)點跳數(shù)、跳段距離基礎設施到達時間、到達時間差接收信號強度指示到達角度視線關系、非視線關系內(nèi)容提要基本概念傳統(tǒng)方法與面臨的挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結傳統(tǒng)同步：NTP與GPSNTP：網(wǎng)絡時間協(xié)議GPS：全球定位系統(tǒng)NTP（NetworkTimeProtocol）體系結構NTP提供準確時間，首先要有準確的時間來源，這一時間應該是國際標準時間UTC。NTP獲得UTC的時間來源可以是原子鐘、天文臺、衛(wèi)星，也可以從Internet上獲取。這樣就有了準確而可靠的時間源。時間按NTP服務器的等級傳播。按照離外部UTC源的遠近將所有服務器歸入不同的Stratum（層）中。Stratum-1在頂層，有外部UTC接入，而Stratum-2則從Stratum-1獲取時間，Stratum-3從Stratum-2獲取時間，以此類推，但Stratum層的總數(shù)限制在15以內(nèi)。所有這些服務器在邏輯上形成階梯式的架構相互連接，而Stratum-1的時間服務器是整個系統(tǒng)的基礎。NTP（NetworkTimeProtocol）體系結構（單機）NTP的適用性NTP不適合于WSN：體積、計算能力和存儲空間存在限制傳輸方式不同：無線而非有線目標不同：WSN僅需局部最而非全局最優(yōu)GPS（GlobalPositionSystem）從根本上解決了人類在地球上的導航與定位問題。每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時間信息地面接收裝置同時接收4顆衛(wèi)星的時間信息，采用偽距測量定位方法可計算出時間和位置信息缺點（室內(nèi)、功耗、安全性、可靠性）時間同步協(xié)議應用于無線傳感器網(wǎng)絡

面臨的挑戰(zhàn)室內(nèi)、礦井、森林，有遮擋網(wǎng)絡規(guī)模大、多點協(xié)作傳輸延遲的不確定性低功耗、低成本和小體積可擴展性、移動性健壯性、安全性傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReceptiontimeReceivetimePropagationtimeSenderReceiver發(fā)送時間：發(fā)送節(jié)點構造和發(fā)送時間同步消息所用時間。e.g.,系統(tǒng)調(diào)用時間；內(nèi)核調(diào)度時間；消息從主機發(fā)送到網(wǎng)絡接口時間。訪問時間：發(fā)送節(jié)點等待訪問網(wǎng)絡傳輸信道的時間。傳輸延遲：發(fā)送節(jié)點傳輸?shù)浇邮展?jié)點所經(jīng)歷的時間。傳播時間（Transmissiontime）:發(fā)送節(jié)點發(fā)送數(shù)據(jù)所經(jīng)歷的時間接收時間：從接收節(jié)點的網(wǎng)絡接口接收到消息到消息接收結束收到時間（Receivetime）通知主機消息達到事件所經(jīng)歷的時間間隔。傳輸延遲的進一步細化時間典型值特性Sendtime&Receivetime0~100ms不確定，依賴處理器負載、操作系統(tǒng)系統(tǒng)調(diào)用開銷Accesstime10~500ms不確定，依賴信道負載。Transmissiontime&Receptiontime10~20ms確定，依賴報文長度和發(fā)送速率。Propagationtime<1μs（距離<300米）確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。Interruptwaitingtime在大多數(shù)情況下<5μs，在重負載下，可達30μs不確定，依賴處理器類型和處理器負載。Encodingtime&Decodingtime100~200μs，<2μs的抖動確定，依賴射頻芯片的種類和設置。Bytealignmenttime0~400μs確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。低功耗、低成本和小體積軟硬件都要受到該限制存儲與計算能力均比較小電能供應的緊張（電池體積有限）網(wǎng)絡規(guī)模大、密度高通信距離近分布式、協(xié)作可擴展性（Scalability）在大規(guī)模網(wǎng)絡中尤為重要滿足不同的網(wǎng)絡類型、網(wǎng)絡規(guī)模滿足不同的應用需求健壯性外部環(huán)境復雜，抗干擾能力要強需要應對安全性挑戰(zhàn)無線傳感器網(wǎng)絡拓撲動態(tài)性較強網(wǎng)絡規(guī)模變化、需求變化內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結典型時間同步協(xié)議NTP（NetworkTimeProtocol）DMTS

（DelayMeasurementTimeSynchronization）RBS

（ReferenceBroadcastSynchronization）TPSN

（Timing-syncProtocolforSensorNetworks）HRTS

（HierarchyReferencingTimeSynchronizationProtocol）FTSP

（FloodingTimeSynchronizationProtocol）DMTS(DelayMeasurementTimeSynchronization)DMTS基于同步消息在傳輸路徑上所有延遲的估計，實現(xiàn)節(jié)點間的時間同步在DMTS機制中，選擇一個節(jié)點作為時間主節(jié)點(leader)廣播同步時間。所有接收節(jié)點測量這個時間廣播分組（packet）的延遲，設置它的時間為接收到分組攜帶的時間加上這個廣播分組的傳輸延遲，這樣所有接收到廣播分組的節(jié)點都與主節(jié)點進行時間同步。時間同步的精度主要由延遲測量的精度所決定。主節(jié)點在檢測到信道空閑時，給廣播分組加上時間戳t0，用來去除發(fā)送端的處理延遲和MAC層的接入延遲。在發(fā)送廣播分組前，主節(jié)點需要發(fā)送前導碼和起始字符，以便接收節(jié)點進行接收同步，根據(jù)發(fā)送的信息位個數(shù)n和發(fā)送每比特位需要的時間t，可以估計出前導碼和起始字符的發(fā)送時間位nt。接收節(jié)點在廣播分組到達時刻加上時間戳t1，并在調(diào)整自己的時鐘之前時刻再記錄時間t2，接收端的接收處理延遲就是(t2-t1)。這樣，如果忽略無線信號的傳播延遲，接收節(jié)點從t0時刻到調(diào)整時鐘前的時間長度約為nt+(t2-t1)。因此，接收節(jié)點為了與發(fā)送節(jié)點時鐘同步，調(diào)整其時鐘為t0+nt+(t2-t1)。發(fā)送者接收者：DMTS

簡單直觀單報文同步同步精度低t0+nt+(t2-t1)

廣播方式同步能耗低發(fā)送者接收者發(fā)送前導碼、同步字（nt）嵌入時標t0：（回避發(fā)送端的處理延遲和MAC層的訪問延遲)接收前導碼、同步字接收ACK接收數(shù)據(jù)發(fā)送ACK接收處理時標t1時標t2發(fā)送時間訪問時間發(fā)送者在信道空閑后或爭用到信道后才插入本地時間t0；接收處理報文的時間：前導碼時間nt，報文處理時間t2-t1；接收方的同步時刻為：t0+nt+t2-t1DMTS的優(yōu)缺點DMTS算法結合鏈路層標記時間戳和時延估計等技術，消除了發(fā)送時間和訪問時間的影響，算法簡單，通信開銷小。DMTS單跳同步誤差受同步精度和計時精度影響。多跳精度隨跳數(shù)的增加而下降，由于誤差的正負相加抵消了一部分，兩跳的誤差約為單跳誤差的1.5倍。DMTS算法沒有估計時鐘的頻率偏差，時鐘保持同步的時間較短；也沒有消除時鐘計時對同步精度的影響，因而其精度不高，不適用于定位等要求高精度同步的應用。RBS(ReferenceBroadcastsynchronization)RBS協(xié)議不是去同步報文的收發(fā)雙方，而是去同步報文的多個接收者。如下圖所示：在由3個節(jié)點組成的單跳網(wǎng)絡中，參考節(jié)點每發(fā)出一個參考報文，其廣播域內(nèi)的其他接收者節(jié)點都將接收到該報文，并各自記錄下接收到該參考報文時的本地時刻。接收者相互交換它們記錄的時刻并計算差值，該差值就是接收者之間的時鐘偏移。但這有一個前提，就是接收者必須同時收到此消息，即接收者同步。假設是否成立？RBS接收節(jié)點時間相移接收者接收者同步的基本依據(jù)：接收者時間相移均值為0RBS性能的影響因素及改善技術影響RBS機制性能的主要因素包括時鐘偏差、接收節(jié)點間的時間速率、接收節(jié)點非確定因素和接收節(jié)點的個數(shù)等。為提高時間同步精度，RBS機制采用了統(tǒng)計技術，通過發(fā)送節(jié)點發(fā)送多個消息，獲得接收節(jié)點之間時間差異的平均值。RBS的優(yōu)點RBS中是通過廣播同步信標分組實現(xiàn)接收節(jié)點之間的相對時間同步，信標分組本身并不需要攜帶任何時標，不依賴于信標的發(fā)送時間。由于無線信道的廣播特性，信標分組相對所有接收節(jié)點而言同時發(fā)送到物理信道上，這樣就除去發(fā)送時間和訪問時間引入的時間同步誤差。對于傳播時間，RBS只關心各個接收節(jié)點之間消息傳播時間的差值。對于射頻信號來說，傳播時間差值非常小，RBS忽略了傳播時間帶來的時間偏差。RBS的不足RBS的缺點是對網(wǎng)絡有一定的要求，它不適合點對點通信的網(wǎng)絡，且要求網(wǎng)絡有物理廣播信道。擴展性不好，因為節(jié)點間本地時間戳通信需要額外的消息交換開銷，不能很好地應用到大規(guī)模的多跳網(wǎng)絡中。RBS有很大的交換次數(shù)，對于具有2個節(jié)點的單跳網(wǎng)絡，需要O(n2)的消息交換，如果n很大時，消息交換開銷是相當大的，導致節(jié)點的計算開銷也非常之大。RBS中接收節(jié)點之間進行相互同步，但并不與發(fā)送節(jié)點同步；實際上，在WSN中發(fā)送節(jié)點很可能也是一個普通的網(wǎng)絡節(jié)點因而也需要同步，為使該節(jié)點和其它節(jié)點進行同步，需要另外一個節(jié)點作為參照廣播發(fā)射節(jié)點，這導致了相當高的能耗。TPSN（Timing-syncProtocolforSensorNetworks）--傳感器網(wǎng)絡時間同步協(xié)議2003年11月，SaurabhGaneriwal提出了TPSN同步機制，目的是通過采用層次型網(wǎng)絡結構來提供全網(wǎng)范圍內(nèi)節(jié)點同步。該機制分為拓撲建立階段和同步建立階段，考慮了傳播時間和接收時間，利用雙向消息交換計算消息的平均延遲，提高了精度。TPSN時間同步協(xié)議思想Thursday,January12,20231、TPSN是類似于NTP（NetworkTimeProtocol）時間同步協(xié)議2、目的是提供傳感器網(wǎng)絡全網(wǎng)范圍內(nèi)節(jié)點間的時間同步3、節(jié)點結構中包含一個根節(jié)點，它與外界通信獲取外界時間，以此作為整個網(wǎng)絡系統(tǒng)的時鐘源4、將節(jié)點分級后（根節(jié)點是0級，累加），每個節(jié)點同上一級的一個節(jié)點進行時間同步，最終與根節(jié)點同步5、節(jié)點對之間的同步采用發(fā)送者-接收者同步機制每個傳感器節(jié)點都有唯一的標識號ID節(jié)點間的無線通信鏈路是雙向的，通過雙向消息交換實現(xiàn)節(jié)點間的時間同步整個網(wǎng)絡內(nèi)所有節(jié)點按層次結構管理，由TPSN協(xié)議生成和維護TPSN協(xié)議過程（1）協(xié)議準備階段Thursday,January12,2023目的：生成節(jié)點層次結構，每個節(jié)點被賦予一個級別，根節(jié)點為0級，第i級的節(jié)點至少能夠與一個第（i-1）級得節(jié)點通信網(wǎng)絡部署后，由根節(jié)點廣播級別發(fā)現(xiàn)分組來啟動層次發(fā)現(xiàn)階段，級別發(fā)現(xiàn)分組包含本節(jié)點的ID和級別鄰居節(jié)點收到分組后，將自己的級別設置為分組中的級別加1，然后廣播新的級別發(fā)現(xiàn)分組節(jié)點收到第i級節(jié)點的廣播分組后，記錄發(fā)送這個廣播分組的節(jié)點ID，設置自己的級別為（i+1），廣播級別為（i+1）的分組，這個過程持續(xù)到網(wǎng)絡內(nèi)每個節(jié)點都被賦予一個級別節(jié)點一旦建立自己的級別，就忽略任何其他級別發(fā)現(xiàn)分組，防止網(wǎng)絡產(chǎn)生洪泛擁塞第一階段層次發(fā)現(xiàn)階段（LevelDiscoveryPhase）Thursday,January12,2023TPSN協(xié)議過程（2）目的：實現(xiàn)所有樹節(jié)點的時間同步，第1級節(jié)點同步到根節(jié)點，第i級的節(jié)點同步到第（i-1）級的一個節(jié)點，最終所有節(jié)點同步到根節(jié)點，實現(xiàn)整個網(wǎng)絡的時間同步層次結構建立以后，根節(jié)點通過廣播時間同步分組啟動同步階段第1級節(jié)點收到分組后，各自分別等待一段隨機時間，再通過與根節(jié)點交換消息同步到根節(jié)點第2級節(jié)點偵聽到第1級節(jié)點的交換消息后，等待一段隨機時間，再與它記錄的上一級別的節(jié)點交換消息進行同步，網(wǎng)絡中的節(jié)點依次與上一級節(jié)點同步，最終都同步到根節(jié)點等待一段隨機時間是為了保證該級節(jié)點在上一級節(jié)點同步完成后才啟動消息交換第二階段同步階段（SynchronizationPhase）Thursday,January12,2023TPSN協(xié)議過程（3）節(jié)點A節(jié)點BT1T4T2T3RequestReply同步點TPSN原理--相鄰級別節(jié)點間的同步機制令Δ為當節(jié)點A的本地時刻為T1時，節(jié)點A和B之間的時偏。報文的傳輸延遲均為d。TPSN算法優(yōu)點與缺點TPSN算法優(yōu)點：TPSN基于雙向報文交換，因此同步精度高。對任意節(jié)點其同步誤差取決于它距離根節(jié)點的跳數(shù)，而與網(wǎng)絡中節(jié)點總數(shù)無關，使TPSN同步精度不會隨節(jié)點數(shù)目增加而降級，從而使TPSN具有較好的擴展性。TPSN算法的缺點：TPSN本質(zhì)上是對同步，因此全網(wǎng)同步的同步能耗高。一旦根節(jié)點失效，就要重新選擇根節(jié)點并重新進行分級和同步階段的處理，增加了計算和能量開銷。另外，TPSN算法沒有對時鐘的頻差進行估計，這使得它需要頻繁同步，開銷較大。理論分析和實驗證明：TPSN同步誤差是RBS的一半結合對clockskew的估計，可以提高TPSN的精度TPSN同步誤差的分析HRTS(HierarchyReferencingTimeSynchronizationProtocol)基于雙向報文交換（如TPSN）的傳感器網(wǎng)絡時間同步協(xié)議具有同步精度高的優(yōu)點，但一次只能同步一對節(jié)點。n個節(jié)點的單跳網(wǎng)絡則需要n-1次同步操作，同步功耗較大。RBS只需要一次同步過程就可完成一個單跳網(wǎng)內(nèi)所有節(jié)點間的同步，同步功耗低，當然同步精度也相對變差。HRTS是一種結合了RBS所使用的參考廣播同步技術和TPSN所使用的雙向報文交互同步技術的方法，減少了同步所需的報文開銷。圖描述了層級時間同步的過程。假設單跳網(wǎng)絡有包含時間基準節(jié)點在內(nèi)的3個節(jié)點BS、n1和n2。步驟1：時間基準節(jié)點BS發(fā)出一個同步請求報文，該報文隨機指定一個鄰居節(jié)點（例如n1）作為應答者節(jié)點（即對應于上圖中的B節(jié)點）。n1記錄報文到達時刻T2，同時n2也記錄下該報文的到達時刻，記為T2'

。步驟2：應答者節(jié)點n1向BS節(jié)點發(fā)一個同步應答報文，報文中包含了T2與T3。步驟3：現(xiàn)在BS節(jié)點已經(jīng)和n1節(jié)點進行了一次雙向報文交換，BS節(jié)點計算出它與n1節(jié)點之間的時鐘偏移Δ。步驟4：BS節(jié)點發(fā)送一個包含Δ和T2信息的報文。步驟5：當n1、n2節(jié)點接收到該報文，對于應答者節(jié)點n1來說，只要將其本地時間減去Δ就達到與BS節(jié)點的瞬時同步。對于其他節(jié)點來說，只要在其本地時間加上T2?T2'?Δ即可達到與BS節(jié)點間的瞬時同步HRTS同步過程

BS

n1

n2

n3

(a)

BS

n1

n2

n3

(b)

BS

n1

n2

n3

(c)

n4

BS

n1

n2

n3

(d)

n4

節(jié)點A節(jié)點BT1T4T2T3RequestReply同步點HRTS協(xié)議的特點根節(jié)點和應答者節(jié)點本質(zhì)上是采用TPSN同步。根節(jié)點和非應答者節(jié)點本質(zhì)上是雙向報文交換同步（但非TPSN）。應答者節(jié)點和非應答者節(jié)點本質(zhì)上是接收者--接收者同步。HRTS協(xié)議充分利用了無線傳輸?shù)膹V播特性（類似于DMTS）來進一步降低協(xié)議的同步功耗。FTSP（FloodingTimeSynchronizationProtocol）

泛洪時間同步協(xié)議（FloodingTimeSynchronizationProtocol）由Vanderbilt大學Miklos,Branislav等提出，目標是實現(xiàn)整個網(wǎng)絡的時間同步并且誤差控制在微秒級。該算法使用單個廣播消息實現(xiàn)發(fā)送節(jié)點與接收節(jié)點之間的時間同步。

多跳的FTSP協(xié)議采用層次結構，根節(jié)點為同步源，可以適應大量傳感器節(jié)點，對網(wǎng)絡拓撲結構的變化和根節(jié)點的失效有健壯性，精確度較好。該算法通過采用MAC層時間戳和線性回歸偏差補償彌補了相關的錯誤源。FTSP（FloodingTimeSynchronizationProtocol）FTSP協(xié)議的同步原理：在傳感網(wǎng)絡中每個節(jié)點有唯一的ID號，通過根節(jié)點的自動選擇算法選出ID號最小的節(jié)點為根節(jié)點，根節(jié)點就是選中的同步時間基準點。同步從根節(jié)點開始，時間同步信息分組采用廣播的方式發(fā)送。未同步節(jié)點接收到已同步節(jié)點廣播的時間信息分組后，從信息分組中估算本地時間與全局時間的時間漂移和時鐘偏移，調(diào)整自己的本地時間，使之與全局時間達成統(tǒng)一。在節(jié)點同步后，生成新的時間信息分組廣播到網(wǎng)絡中。重復這個過程，直到整個網(wǎng)絡每個節(jié)點都時間同步。FTSP協(xié)議主要采用下面機制來降低時間延遲對時間同步精度的影響：在MAC層記錄時間信標，細分消息傳輸中的時間延遲并對這些延遲進行補償，利用線性回歸算法估算時間漂移。FTSP的特點FTSP算法通過對收發(fā)過程的分析，把時延進一步分為發(fā)送中斷處理時延、編碼時延、傳播時延、解碼時延、字節(jié)對齊時延、接收終端處理時延，進一步降低了時延的不確定性。通過發(fā)射多個時間戳（單個報文中包括多個時間戳），使得接收節(jié)點可以利用最小方差線性擬合估算自己和發(fā)送節(jié)點的漂移和偏移差。通過良好的根節(jié)點選舉機制，針對根節(jié)點失效、新節(jié)點加入以及拓撲結構變化等情況進行了優(yōu)化，使得算法的健壯性很好，適合于軍事等惡劣應用情況。FTSP的特點與典型應用FTSP是現(xiàn)有的典型時間同步協(xié)議中精度最高的同步協(xié)議，并且有良好的健壯性，不會因為個別節(jié)點的失效而收到影響。但FTSP基于MAC層時間戳技術的細節(jié)技術的實現(xiàn)來提高同步精度，使得FTSP協(xié)議的通用性不強。并且洪泛的方式使得能耗開銷巨大。用于ZigBee網(wǎng)絡的同步休眠與喚醒算法內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結螢火蟲同步1935年，Science1975年,Peskin的RC模型1989年，M&S模型(未考慮延遲)1998年，Ernst（考慮有延遲）2005年，真實地實現(xiàn)簡單，高效，可擴展性強M&S模型研究由初始不同步狀態(tài)如何達到同步狀態(tài)個體性質(zhì)相同,因此一旦達到同步則永遠同步螢火蟲之間的交互被建模成電量耦合耦合延遲規(guī)定為0最終結論為:系統(tǒng)的同步收斂性取決于個體在自由狀態(tài)下的動力學特性同步的實質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量,相位差通過同步過程不斷縮小，最終達到完全相同,即同步狀態(tài)Ernst的研究M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時的情況M&S模型只研究了正耦合的情況，Ernst還研究了負耦合的情況螢火蟲同步的特點同步可直接在物理層而不需要以報文的方式實現(xiàn)。直接用硬件實現(xiàn)，使得同步精度不會受到MAC延遲、協(xié)議處理與軟件實現(xiàn)等的影響。由于對任何同步信號的處理方式均相同，與同步信號的來源無關，因此可擴展性以及適應網(wǎng)絡動態(tài)變化的能力很強。機制非常簡單，不需要對其它節(jié)點的時間信息進行存儲。螢火蟲同步算法的一個限制是要求每個節(jié)點具有相似性，但這種機制在非相似節(jié)點所組成的網(wǎng)絡下能否起到同步的作用，目前還不清楚。由于螢火蟲同步的理論研究還遠未結束，工程實用性還有待考察。螢火蟲同步技術的未來發(fā)展螢火蟲同步技術對耦合延遲、耦合強度、耦合性質(zhì)、初始相位、網(wǎng)絡拓撲等因素很敏感。雖然在如兩個振蕩器的同步收斂性等研究上取得了一定的進展，但無論是理論研究還是仿真研究，研究者在某些結論上還不能達成一致的認識。但可以認同的一點是：在實際系統(tǒng)中，基于螢火蟲同步策略的同步技術會取得在一定誤差范圍內(nèi)的同步。內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結總結在無線傳感器網(wǎng)絡中，時間同步不僅要關注同步精度，還需要關注同步能耗、可擴展性和健壯性需求經(jīng)典的時間同步協(xié)議側重于同步精度和同步能耗的需求，采用時鐘飄移補償、MAC層時間戳技術以及雙向報文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性來降低同步能耗螢火蟲同步側重于提高可擴展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡的應用時間同步算法分類基于Sender/Receiver的時間同步通信雙方中的發(fā)送節(jié)點需要記錄時間消息發(fā)送時刻的時間信標，而接收節(jié)點則需要記錄時間消息接收時刻的時間信標，同步過程中只需要一次通信。該模式的代表算法是FTSP，DMTS?；赗eceiver/Receiver的時間同步在實現(xiàn)時間同步的過程中，節(jié)點只需要在接收時間消息的時刻記錄時間信標，而發(fā)送時刻不需要記錄時間信標，節(jié)點只需要知道接收到時間消息的精確時刻。典型協(xié)議有RBS等。基于Pair-Wise（成對）的時間同步這種算法利用成對同步方法進行發(fā)送節(jié)點和接收節(jié)點間的時間同步，然后擴展到整個網(wǎng)絡形成網(wǎng)絡的時間同步。此類算法使得網(wǎng)絡的同步報文開銷較大，對于低開銷要求較高的工業(yè)無線網(wǎng)絡應用有一定的局限性。而且同步階段所用時間隨節(jié)點數(shù)目的增加而線性增加,不適合對快速性要求較高的工業(yè)無線網(wǎng)絡。典型的算法主要有TPSN等。主要參考文獻（詳見原著）[1]ElsonJ.,R?merK..Wirelesssensornetworks:anewregimefortimesynchronization.ACMSIGCOMMComputerCommunicationReview,2003,33(1):149-154.[3]ElsonJ.,GirodL.,EstrinD..Fine-grainedtimesynchronizationusingreferencebroadcasts.In:Proc.5thSymposiumonOperationSystemDesignandImplementation,Boston,2002,147-163.[4]GaneriwalS.,KumarR.,SrivastavaM..