第七章時間同步內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制小結WSN時間同步技術背景集中式系統與分布式系統集中式：事件間有著明確的時間先后關系，不存在同步問題分布式：同步是必需的，只是對同步的要求程度不同無線傳感器網絡時間同步典型的分布式系統是無線傳感器網絡應用的基礎需要解決的問題同步精度功耗可擴展性時間同步技術的分類排序、相對同步與絕對同步遞進關系各自具有典型的協議代表外同步與內同步參考源不同局部同步與全網同步同步對象的范圍不同時間同步技術的應用場合多傳感器數據壓縮與融合低功耗MAC協議、路由協議測距、定位（位置相關報務，LBS）分布式系統的傳統要求協作傳輸、處理的要求......時鐘模型硬件時鐘模型軟件時鐘模型硬件時鐘模型基本名詞時間、晶振、時鐘（RTC）時鐘偏移（clockoffset）時鐘飄移（clockdrift）速率恒定模型最常用，但不適應環境變化劇烈的場合飄移有界模型常用于確定同步誤差上下界飄移變化有界模型軟件時鐘模型軟件虛擬時鐘一般是個分段連續、嚴格單調的函數傳統與挑戰傳統同步方法傳感器網絡的挑戰傳統同步：NTP與GPSNTP：網絡時間協議GPS：全球定位系統NTP（NetworkTimeProtocol）體系結構（網絡）NTP（NetworkTimeProtocol）體系結構（單機）NTP（NetworkTimeProtocol）NTP不適合于WSN體積、計算能力和存儲空間存在限制傳輸方式不同：無線而非有線目標不同：局部最優而非全局最優GPS（GlobalPositionSystem）從根本上解決了人類在地球上的導航與定位問題。每顆衛星上配備有高精度的銣、銫原子鐘，并不斷發射其時間信息地面接收裝置同時接收4顆衛星的時間信息，采用偽距測量定位方法可計算出時間和位置信息缺點（室內、功耗、安全性、分布式）傳感器網絡的挑戰室內、礦井、森林，有遮擋低功耗、低成本和小體積傳輸延遲的不確定性可擴展性、移動性健壯性、安全性網絡規模大、多點協作傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReceptiontimeReceivetimePropagationtimeSenderReceiver傳輸延遲的進一步細化(在Mica2上)時間典型值特性Sendtime&Receivetime0~100ms不確定，依賴處理器負載、操作系統系統調用開銷Accesstime10~500ms不確定，依賴信道負載。Transmissiontime&Receptiontime10~20ms確定，依賴報文長度和發送速率。Propagationtime<1μs（距離<300米）確定，依賴收發方物理距離和傳播媒質特性。Interruptwaitingtime在大多數情況下<5μs，在重負載下，可達30μs不確定，依賴處理器類型和處理器負載。Encodingtime&Decodingtime100~200μs，<2μs的抖動確定，依賴射頻芯片的種類和設置。Bytealignmenttime0~400μs確定，依賴發送速率和收發字節偏移。低功耗、低成本和小體積軟硬件都要受到該限制存儲與計算能力均比較小加劇了電能供應的緊張（電池體積）網絡規模大、密度高通信距離近分布式、協作可擴展性（Scalability）在大規模網絡中尤為重要是大規模無線傳感器網絡軟硬件設計中非常重要的問題滿足不同的網絡類型、網絡規模滿足不同的應用需求健壯性外部環境復雜，搞毀能力需要應對安全性挑戰無線傳感器網絡拓撲動態性較強網絡規模變化、需求變化典型時間同步協議NTP（NetworkTimeProtocol）DMTS

（DelayMeasurementTimeSynchronization）RBS

（ReferenceBroadcastSynchronization）TPSN

（Timing-syncProtocolforSensorNetworks）HRTS

（HierarchyReferencingTimeSynchronizationProtocol）FTSP

（FloodingTimeSynchronizationProtocol）GCS

（GlobalClockSynchronization）發送者接收者：DMTS

最簡單直觀單報文同步同步精度低廣播方式同步能耗低發送者接收者發送前導碼、同步字嵌入時標t0接收前導碼、同步字接收ACK接收數據發送ACK接收處理時標t1時標t2發送時間訪問時間DMTS（DelayMeasurementTimeSynchronization）接收者接收者：RBSReceiverNICSenderCriticalPathTimeNICSenderReceiver1CriticalPathReceiver2RBS（ReferenceBroadcastSynchronization）RBS（ReferenceBroadcastSynchronization）接收者接收者同步的基本依據：接收者時間相移均值為0單跳RBS用最小二乘法估計clockskew提高同步精度多跳RBS時間路由技術：基于最短路徑查找TPSN（Timing-syncProtocolforSensorNetworks）否定：DMTSRBS否定之否定：RBSTPSNTPSN：雙報文交換的發送者接收者同步節點A節點BT1T4T2T3RequestReply同步點TPSN（Timing-syncProtocolforSensorNetworks）對同步誤差的分析很重要，是一種基本的分析方法理論分析和實驗證明：TPSN同步誤差是RBS的一半結合對clockskew的估計，可以提高TPSN的精度TPSN（Timing-syncProtocolforSensorNetworks）多跳TPSN全網周期性同步“層發現”把網絡組織成最短生成樹逐層在相鄰兩層節點間同步網絡內兩個節點的同步“后同步”查找兩個節點間的路徑在路徑的相鄰兩個節點間進行TPSN同步HRTS（HierarchyReferencingTimeSynchronizationProtocol）TPSN基于雙向報文交換，因此同步精度高TPSN本質上是對同步，因此全網同步的同步能耗高由DMTS發現，廣播能降低全網同步能耗結合廣播和節點間的雙向報文交換同步HRTS協議

BS

n1

n2

n3

(a)

BS

n1

n2

n3

(b)

BS

n1

n2

n3

(c)

n4

BS

n1

n2

n3

(d)

n4

HRTS（HierarchyReferencingTimeSynchronizationProtocol）根節點和應答者節點本質上是采用TPSN同步根節點和非應答者節點本質上是雙向報文交換同步（但非TPSN）應答者節點和非應答者節點本質上是接收者--接收者同步HRTS（HierarchyReferencingTimeSynchronizationProtocol）FTSP（FloodingTimeSynchronizationProtocol）同步精度高工程實用性強強調實現細節MAC層時間戳技術和平臺直接相關，書中給出了在Mica2平臺下的實現基本同步原理發送者--接收者同步單個報文中包括多個時間戳（在報文的不同位置）根據單個報文中的多個時間戳，可對中斷等待時間進行補償對clockskew的補償仍采用最小二乘法FTSP（FloodingTimeSynchronizationProtocol）多跳FTSP洪泛方式廣播時間基準節點的時間協議健壯實際做了工程化的實現GCS（GlobalClockSynchronization）節點遍歷模式聚類分層模式擴散模式GCS：節點遍歷模式游走階段：記錄游走的出發和到達時間時間校正階段：根據節點在游走環的位置和游走時間對節點時間進行校正理論假設：每段游走的時間花費相同GCS：聚類分層模式單純的節點遍歷方式導致遍歷環過長，同步功耗大通過分簇協議，把網絡組織成簇結構簇頭節點間以節點遍歷方式同步簇內節點可以節點遍歷或RBS等方式進行同步GCS：擴散模式越簡單的方法往往是越有效的同步過程：對接收到的時間進行平均操作，并對自己的時間進行擴散理論證明：當把所有節點的時間當成一張快照時，經過若干輪擴散過程，所有節點時間最終將收斂到所有節點時間的平均值上新型同步機制基于報文交換的同步機制面臨著挑戰同步精度問題可擴展性問題新型同步機制螢火蟲同步協作同步兩個概念同時性與同步性螢火蟲同步1935年，Science1975年,Peskin的RC模型1989年，M&S模型（無延遲）1998年，Ernst（有延遲）結論2005年，真實地實現簡單，高效，可擴展性強M&S模型研究由初始不同步狀態如何達到同步狀態個體性質相同,因此一旦達到同步則永遠同步螢火蟲之間的交互被建模成電量耦合耦合延遲規定為0最終結論為:系統的同步收斂性取決于個體在自由狀態下的動力學特性同步的實質：不同步產生了耦合，耦合改變了狀態量，而狀態量又改變了相位量,相位差通過同步過程不斷縮小，最終達到完全相同,即同步狀態M&S模型證明了全耦合系統的同步收斂性沒有證明多跳網絡的同步收斂性Ernst的研究M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時的情況M&S模型只研究了正耦合的情況，Ernst還研究了負耦合的情況Ernst--正耦合（2個節點）存在兩種情況不可能達到完全同步其實是M&S模型的擴展Ernst--負耦合（2個節點）存在三種情況和Peskin的結論一致結論：考慮固定耦合延遲的情況下，只有負耦合才可能取得同步收斂負耦合下的全連接網絡仿真研究方法和兩個節點下的情況不同出現分簇現象其他一些研究與結論理論上沒有突破單純的仿真方法意義有限螢火蟲同步技術對耦合延遲、耦合強度、耦合性質、初始相位、網絡拓撲等因素很敏感。雖然在例如兩個振蕩器的同步收斂性研究上取得了一定的進展，但無論是理論研究還是仿真研究，研究者在某些結論上還不能達成一致的認識。但可以認同的一點是：在實際系統中，基于螢火蟲同步策略的同步技術會取得在一定誤差范圍內的同步。實踐：RFA算法RFA(ReachbackFireflyAlgorithm)

在24個Micaz節點組成的網絡上實現同步誤差是存在的，和同步操作的頻率直接相關核心思想：將某輪同步周期內接收到的同步報文的影響推后到下一輪同步周期的起始時刻總結：螢火蟲同步同步可直接在物理層而不需要以報文的方式實現。直接用硬件實現，使得同步精度不會受到MAC延遲、協議處理與軟件實現等的影響。由于對任何同步信號的處理方式均相同