1、無線傳感器網絡技術講義第六章、時間同步技術2007年8月20日內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結基本概念WSN時間同步技術背景時間同步技術的分類時間同步技術的應用場合關鍵點：時鐘模型WSN時間同步技術背景集中式系統與分布式系統集中式：事件間有著明確的時間先后關系，不存在同步問題分布式：同步是必需的，只是對同步的要求程度不同無線傳感器網絡時間同步典型的分布式系統是無線傳感器網絡應用的基礎需要解決的問題同步精度功耗可擴展性時間同步技術的應用場合多傳感器數據壓縮與融合低功耗MAC協議、路由協議測距、定位（位置相關報務，

2、LBS）分布式系統的傳統要求協作傳輸、處理的要求. .時鐘模型硬件時鐘模型軟件時鐘模型軟件時鐘模型軟件虛擬時鐘一般是個分段連續、嚴格單調的函數內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結傳統與挑戰傳統同步方法傳感器網絡的挑戰NTP（Network Time Protocol） 體系結構（網絡）NTP（Network Time Protocol）體系結構（單機）GPS（Global Position System） 從根本上解決了人類在地球上的導航與定位問題。每顆衛星上配備有高精度的銣、銫原子鐘，并不斷發射其時間信息地面接收裝置同時接收4顆衛星的時間信息，采用偽距測量定位方法可計算

3、出時間和位置信息缺點（室內、功耗、安全性、分布式）傳感器網絡的挑戰室內、礦井、森林，有遮擋低功耗、低成本和小體積傳輸延遲的不確定性可擴展性、移動性健壯性、安全性網絡規模大、多點協作傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver傳輸延遲的進一步細化(在Mica2上)時間典型值特性Send time & Receive time0100ms不確定，依賴處理器負載、操作系統系統調用開銷Access time10500ms不確定，依賴信道負載。Transm

4、ission time & Reception time1020ms確定，依賴報文長度和發送速率。Propagation time1s（距離300米）確定，依賴收發方物理距離和傳播媒質特性。Interrupt waiting time在大多數情況下5s，在重負載下，可達30s不確定，依賴處理器類型和處理器負載。Encoding time & Decoding time100200s，2s的抖動確定，依賴射頻芯片的種類和設置。Byte alignment time0400s確定，依賴發送速率和收發字節偏移。低功耗、低成本和小體積軟硬件都要受到該限制存儲與計算能力均比較小加劇了電能供應的緊張（電池

5、體積）網絡規模大、密度高通信距離近 分布式、協作可擴展性（Scalability）在大規模網絡中尤為重要是大規模無線傳感器網絡軟硬件設計中非常重要的問題滿足不同的網絡類型、網絡規模滿足不同的應用需求內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結典型時間同步協議NTP（Network Time Protocol）DMTS （Delay Measurement Time Synchronization） RBS （Reference Broadcast Synchronization） TPSN （Timing-sync Protocol for Sensor Networks） HR

6、TS （Hierarchy Referencing Time Synchronization Protocol） FTSP （Flooding Time Synchronization Protocol） GCS （Global Clock Synchronization） 接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） RBS （Reference Broadcast Synchronizat

7、ion） 接收者接收者同步的基本依據：接收者時間相移均值為0單跳RBS用最小二乘法估計clock skew提高同步精度多跳RBS時間路由技術：基于最短路徑查找TPSN（Timing-sync Protocol for Sensor Networks） 否定：DMTSRBS否定之否定：RBSTPSNTPSN：雙報文交換的發送者接收者同步節點A節點BT1T4T2T3RequestReply同步點TPSN（Timing-sync Protocol for Sensor Networks） 對同步誤差的分析很重要，是一種基本的分析方法理論分析和實驗證明：TPSN同步誤差是RBS的一半結合對clock

8、skew的估計，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Networks） 多跳TPSN全網周期性同步“層發現”把網絡組織成最短生成樹逐層在相鄰兩層節點間同步網絡內兩個節點的同步“后同步”查找兩個節點間的路徑在路徑的相鄰兩個節點間進行TPSN同步HRTS（Hierarchy Referencing Time Synchronization Protocol） TPSN基于雙向報文交換，因此同步精度高TPSN本質上是對同步，因此全網同步的同步能耗高由DMTS發現，廣播能降低全網同步能耗結合廣播和節點間的雙向報文交換同步HRTS協議 BS n

9、1 n2 n3 (a) BS n1 n2 n3 (b) BS n1 n2 n3 (c) n4 BS n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） 根節點和應答者節點本質上是采用TPSN同步根節點和非應答者節點本質上是雙向報文交換同步（但非TPSN）應答者節點和非應答者節點本質上是接收者-接收者同步HRTS（Hierarchy Referencing Time Synchronization Protocol） FTSP（Flooding Time Synchronization Protoco

10、l） 同步精度高工程實用性強強調實現細節MAC層時間戳技術和平臺直接相關，書中給出了在Mica2平臺下的實現基本同步原理發送者-接收者同步單個報文中包括多個時間戳（在報文的不同位置）根據單個報文中的多個時間戳，可對中斷等待時間進行補償對clock skew的補償仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） 多跳FTSP洪泛方式廣播時間基準節點的時間協議健壯實際做了工程化的實現GCS（Global Clock Synchronization） 節點遍歷模式聚類分層模式擴散模式GCS：節點遍歷模式游走階段：記錄游走的出發和到達時間時間校正

11、階段：根據節點在游走環的位置和游走時間對節點時間進行校正理論假設：每段游走的時間花費相同GCS：聚類分層模式單純的節點遍歷方式導致遍歷環過長，同步功耗大通過分簇協議，把網絡組織成簇結構簇頭節點間以節點遍歷方式同步簇內節點可以節點遍歷或RBS等方式進行同步GCS：擴散模式越簡單的方法往往是越有效的同步過程：對接收到的時間進行平均操作，并對自己的時間進行擴散理論證明：當把所有節點的時間當成一張快照時，經過若干輪擴散過程，所有節點時間最終將收斂到所有節點時間的平均值上內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結新型同步機制基于報文交換的同步機制面臨著挑戰同步精度問題可擴展性問題新型同步

12、機制螢火蟲同步協作同步兩個概念同時性與同步性螢火蟲同步1935年，Science1975年, Peskin的RC模型1989年，M&S模型（無延遲）1998年，Ernst（有延遲）結論2005年，真實地實現簡單，高效，可擴展性強M&S模型研究由初始不同步狀態如何達到同步狀態個體性質相同,因此一旦達到同步則永遠同步螢火蟲之間的交互被建模成電量耦合耦合延遲規定為0最終結論為:系統的同步收斂性取決于個體在自由狀態下的動力學特性同步的實質：不同步產生了耦合，耦合改變了狀態量，而狀態量又改變了相位量 ,相位差通過同步過程不斷縮小，最終達到完全相同,即同步狀態 M&S模型證明了全耦合系統的同步收斂性沒有證

13、明多跳網絡的同步收斂性Ernst的研究M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時的情況M&S模型只研究了正耦合的情況，Ernst還研究了負耦合的情況Ernst-正耦合（2個節點）存在兩種情況不可能達到完全同步其實是M&S模型的擴展Ernst-負耦合（2個節點）存在三種情況和Peskin的結論一致結論：考慮固定耦合延遲的情況下，只有負耦合才可能取得同步收斂 負耦合下的全連接網絡仿真研究方法和兩個節點下的情況不同出現分簇現象其他一些研究與結論理論上沒有突破單純的仿真方法意義有限螢火蟲同步技術對耦合延遲、耦合強度、耦合性質、初始相位、網絡拓撲等因素很敏感。雖然在例如兩個振蕩器的同步收

14、斂性研究上取得了一定的進展，但無論是理論研究還是仿真研究，研究者在某些結論上還不能達成一致的認識。但可以認同的一點是：在實際系統中，基于螢火蟲同步策略的同步技術會取得在一定誤差范圍內的同步。實踐：RFA算法RFA (Reachback Firefly Algorithm) 在24個Micaz節點組成的網絡上實現同步誤差是存在的，和同步操作的頻率直接相關核心思想：將某輪同步周期內接收到的同步報文的影響推后到下一輪同步周期的起始時刻 總結：螢火蟲同步同步可直接在物理層而不需要以報文的方式實現。直接用硬件實現，使得同步精度不會受到MAC延遲、協議處理與軟件實現等的影響。由于對任何同步信號的處理方式均

15、相同，與同步信號的來源無關，因此可擴展性以及適應網絡動態變化的能力很強。機制非常簡單，不需要對其它節點的時間信息進行存儲。螢火蟲同步算法的一個限制是要求每個節點具有相似性，但這種機制在非相似節點所組成的網絡下能否起到同步的作用，目前還不清楚。此外，由于螢火蟲同步的理論研究還遠未結束，工程實用性還有待考察。協作同步本質：空間平均而非時間平均實現上直接受限于信號處理技術 內容提要基本概念傳統與挑戰典型時間同步協議新型同步機制總結總結 在無線傳感器網絡中，時間同步不僅要關注同步精度，還需要關注同步能耗、可擴展性和健壯性需求經典的時間同步協議側重于同步精度和同步能耗的需求，采用時鐘飄移補償、MAC層時

16、間戳技術以及雙向報文交換來提高同步精度，充分利用無線傳輸的廣播特性和捎帶技術來降低同步能耗螢火蟲同步和協作同步則側重于提高可擴展性和健壯性。非常適合于大規模無線傳感器網絡的應用 主要參考文獻（詳見原著）1 Elson J., Rmer K. Wireless sensor networks: a new regime for time synchronization. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 149-154.3 Elson J., Girod L., Estrin D. Fine-grained time

17、synchronization using reference broadcasts. In: Proc. 5th Symposium on Operation System Design and Implementation, Boston, 2002, 147-163.4 Ganeriwal S., Kumar R., Srivastava M. Timing-sync protocol for sensor networks. In: Proc. 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, 2

18、003, 138-149.7 Mills D. L. Network time protocol (Version3) specification, implementation and analysis. University of Delaware, DARPA Network Working Group Report: RFC-1305, 1992. 13 Miklos M., Branislav K., Gyula S., Akos L. The flooding time synchronization protocol. In: Proc. 2th ACM Conference on Embedded Networked Sensor Systems, Baltimore, 2004, 39-49.14 Su Ping, Delay measurement time synchronization for wireless sensor networks, Intel Research. Berkeley Lab, 2003.19 Dai H., Han R. TSy