無線傳感器網(wǎng)絡 第06章 時間同步技術(shù)

1、無線傳感器網(wǎng)絡技術(shù)無線傳感器網(wǎng)絡技術(shù)講義講義第六章、時間同步技術(shù)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)基本概念 WSN時間同步技術(shù)背景 時間同步技術(shù)的分類 時間同步技術(shù)的應用場合 關(guān)鍵點：時鐘模型WSN時間同步技術(shù)背景 集中式系統(tǒng)與分布式系統(tǒng) 集中式：事件間有著明確的時間先后關(guān)系，不存在同步問題 分布式：同步是必需的，只是對同步的要求程度不同 無線傳感器網(wǎng)絡時間同步 典型的分布式系統(tǒng) 是無線傳感器網(wǎng)絡應用的基礎(chǔ) 需要解決的問題 同步精度 功耗 可擴展性WSN時間同步機制的主要性能參數(shù) 最大誤差：一組傳感器節(jié)點之間的最

2、大時間差或相對外部標準時間的最大差值。 同步期限：節(jié)點保持時間同步的時間長度。 同步范圍：節(jié)點保持時間同步的區(qū)域范圍。 可用性：范圍覆蓋的完整性。 效率：達到同步精度所經(jīng)歷的時間以及消耗的能量。 代價和體積：需要考慮節(jié)點的價格和體積。時間同步技術(shù)的分類 排序、相對同步與絕對同步 遞進關(guān)系 各自具有典型的協(xié)議代表 外同步與內(nèi)同步 參考源不同 局部同步與全網(wǎng)同步 同步對象的范圍不同時間同步技術(shù)的應用場合 多傳感器數(shù)據(jù)壓縮與融合 低功耗MAC協(xié)議、路由協(xié)議 測距、定位（位置相關(guān)報務，LBS） 分布式系統(tǒng)的傳統(tǒng)要求 協(xié)作傳輸、處理的要求 . .時鐘模型 硬件時鐘模型 軟件時鐘模型軟件時鐘模型 軟件虛擬

3、時鐘 一般是個分段連續(xù)、嚴格單調(diào)的函數(shù)相關(guān)術(shù)語 信標節(jié)點和未知節(jié)點 鄰居節(jié)點 跳數(shù)、跳段距離 基礎(chǔ)設(shè)施 到達時間、到達時間差 接收信號強度指示 到達角度 視線關(guān)系、非視線關(guān)系內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)傳統(tǒng)與挑戰(zhàn) 傳統(tǒng)同步方法 傳感器網(wǎng)絡的挑戰(zhàn)傳統(tǒng)同步：NTP與GPS NTP：網(wǎng)絡時間協(xié)議 GPS：全球定位系統(tǒng)NTP（Network Time Protocol） 體系結(jié)構(gòu)（網(wǎng)絡）NTP（Network Time Protocol） 體系結(jié)構(gòu)（單機）NTP（Network Time Protocol） NTP不適合于WSN 體積、計算能力和存儲空間存在限制 傳輸方式

4、不同：無線而非有線 目標不同：局部最優(yōu)而非全局最優(yōu)GPS（Global Position System） 從根本上解決了人類在地球上的導航與定位問題。 每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時間信息 地面接收裝置同時接收4顆衛(wèi)星的時間信息，采用偽距測量定位方法可計算出時間和位置信息 缺點（室內(nèi)、功耗、安全性、分布式）傳感器網(wǎng)絡的挑戰(zhàn) 室內(nèi)、礦井、森林，有遮擋 低功耗、低成本和小體積 傳輸延遲的不確定性 可擴展性、移動性 健壯性、安全性 網(wǎng)絡規(guī)模大、多點協(xié)作傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReception timeReceive

5、timePropagationtimeSenderReceiver發(fā)送時間：發(fā)送節(jié)點構(gòu)造和發(fā)送時間同步消息所用時間。e.g., 系統(tǒng)調(diào)用時間；內(nèi)核調(diào)度時間；消息從主機發(fā)送到網(wǎng)絡接口時間。訪問時間：發(fā)送節(jié)點等待訪問網(wǎng)絡傳輸信道的時間。傳播延遲：發(fā)送節(jié)點傳輸?shù)浇邮展?jié)點所經(jīng)歷的時間。接收時間：從接收節(jié)點的網(wǎng)絡接口接收到消息到通知主機消息達到事件所經(jīng)歷的時間間隔。傳輸延遲的進一步細化(在Mica2上)時間時間典型值典型值特性特性Send time & Receive time0100ms不確定，依賴處理器負載、操不確定，依賴處理器負載、操作系統(tǒng)系統(tǒng)調(diào)用開銷作系統(tǒng)系統(tǒng)調(diào)用開銷Access tim

6、e10500ms不確定，依賴信道負載。不確定，依賴信道負載。Transmission time & Reception time1020ms確定，依賴報文長度和發(fā)送速確定，依賴報文長度和發(fā)送速率。率。Propagation time1s（距離（距離300米）米）確定，依賴收發(fā)方物理距離和確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。傳播媒質(zhì)特性。Interrupt waiting time在大多數(shù)情況下在大多數(shù)情況下5s，在重，在重負載下，可達負載下，可達30s不確定，依賴處理器類型和處不確定，依賴處理器類型和處理器負載。理器負載。Encoding time & Decoding t

7、ime100200s，2s的抖動的抖動確定，依賴射頻芯片的種類和確定，依賴射頻芯片的種類和設(shè)置。設(shè)置。Byte alignment time0400s確定，依賴發(fā)送速率和收發(fā)字確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。節(jié)偏移。低功耗、低成本和小體積 軟硬件都要受到該限制 存儲與計算能力均比較小 加劇了電能供應的緊張（電池體積） 網(wǎng)絡規(guī)模大、密度高 通信距離近 分布式、協(xié)作可擴展性（Scalability） 在大規(guī)模網(wǎng)絡中尤為重要 是大規(guī)模無線傳感器網(wǎng)絡軟硬件設(shè)計中非常重要的問題 滿足不同的網(wǎng)絡類型、網(wǎng)絡規(guī)模 滿足不同的應用需求健壯性 外部環(huán)境復雜，搞毀能力 需要應對安全性挑戰(zhàn) 無線傳感器網(wǎng)絡拓撲動態(tài)性

8、較強 網(wǎng)絡規(guī)模變化、需求變化內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)典型時間同步協(xié)議 NTP（Network Time Protocol） DMTS （Delay Measurement Time Synchronization） RBS （Reference Broadcast Synchronization） TPSN （Timing-sync Protocol for Sensor Networks） HRTS （Hierarchy Referencing Time Synchronization Protocol） FTSP （Flooding Time Synchr

9、onization Protocol） GCS （Global Clock Synchronization） 發(fā)送者接收者：DMTS 最簡單直觀 單報文同步同步精度低 t0+nt+(t2-t1) 廣播方式同步能耗低發(fā)送者發(fā)送者接收者接收者發(fā)送前導碼發(fā)送前導碼、同步字同步字 （nt）嵌入時標嵌入時標t0：發(fā)送端的處發(fā)送端的處理 延 遲 和理 延 遲 和M AC層 的層 的訪問延遲訪問延遲接收前導碼、接收前導碼、同步字同步字接收接收ACK接收接收數(shù)據(jù)數(shù)據(jù)發(fā)送發(fā)送ACK接收接收處理處理時標時標t1時標時標t2發(fā)送時間發(fā)送時間訪問時間訪問時間DMTS（Delay Measurement Time Sy

10、nchronization） 基于同步消息在傳輸路徑上所有延遲的估計，實現(xiàn)節(jié)點間的時間同步接收者接收者：RBS （Reference Broadcast SynchronizationReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2通過廣播同步指示分組實現(xiàn)接收點間的相對時間同步RF信號的傳播時間差值非常小可以消除接收節(jié)點的接收協(xié)議處理、上下文切換、網(wǎng)絡接口向主機傳送影響RBS機制性能的因素：時鐘偏差、接收點飛確定性因素以及接收點的個數(shù)RBS （Reference Broadcast Synchr

11、onization） 接收者接收者同步的基本依據(jù)：接收者時間相移均值為0單跳RBS 用最小二乘法估計clock skew提高同步精度多跳RBS 時間路由技術(shù)：基于最短路徑查找TPSN（Timing-sync Protocol for Sensor Networks） 否定：DMTSRBS 否定之否定：RBSTPSN TPSN：雙報文交換的發(fā)送者接收者同步節(jié)點節(jié)點A節(jié)點節(jié)點BT1T4T2T3RequestReply同步點2) 34() 12(TTTTTPSN（Timing-sync Protocol for Sensor Networks） 對同步誤差的分析 很重要，是一種基本的分析方法 理論分

12、析和實驗證明：TPSN同步誤差是RBS的一半 結(jié)合對clock skew的估計，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Networks） 多跳TPSN 全網(wǎng)周期性同步 “層發(fā)現(xiàn)”把網(wǎng)絡組織成最短生成樹 逐層在相鄰兩層節(jié)點間同步 網(wǎng)絡內(nèi)兩個節(jié)點的同步 “后同步”查找兩個節(jié)點間的路徑 在路徑的相鄰兩個節(jié)點間進行TPSN同步HRTS（Hierarchy Referencing Time Synchronization Protocol） TPSN基于雙向報文交換，因此同步精度高 TPSN本質(zhì)上是對同步，因此全網(wǎng)同步的同步能耗高 由DMTS發(fā)現(xiàn)

13、，廣播能降低全網(wǎng)同步能耗 結(jié)合廣播和節(jié)點間的雙向報文交換同步HRTS協(xié)議 BS n1 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） 根節(jié)點和應答者節(jié)點本質(zhì)上是采用TPSN同步 根節(jié)點和非應答者節(jié)點本質(zhì)上是雙向報文交換同步（但非TPSN） 應答者節(jié)點和非應答者節(jié)點本質(zhì)上是接收者-接收者同步HRTS（Hierarchy Referencing Time Synchronization Protocol）

14、 FTSP（Flooding Time Synchronization Protocol） 同步精度高 工程實用性強 強調(diào)實現(xiàn)細節(jié) MAC層時間戳技術(shù) 和平臺直接相關(guān)，書中給出了在Mica2平臺下的實現(xiàn) 基本同步原理 發(fā)送者-接收者同步 單個報文中包括多個時間戳（在報文的不同位置） 根據(jù)單個報文中的多個時間戳，可對中斷等待時間進行補償 對clock skew的補償仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） 多跳FTSP 洪泛方式廣播時間基準節(jié)點的時間 協(xié)議健壯 實際做了工程化的實現(xiàn)GCS（Global Clock Synchroni

15、zation） 節(jié)點遍歷模式 聚類分層模式 擴散模式GCS：節(jié)點遍歷模式 游走階段：記錄游走的出發(fā)和到達時間 時間校正階段：根據(jù)節(jié)點在游走環(huán)的位置和游走時間對節(jié)點時間進行校正 理論假設(shè)：每段游走的時間花費相同GCS：聚類分層模式 單純的節(jié)點遍歷方式導致遍歷環(huán)過長，同步功耗大 通過分簇協(xié)議，把網(wǎng)絡組織成簇結(jié)構(gòu) 簇頭節(jié)點間以節(jié)點遍歷方式同步 簇內(nèi)節(jié)點可以節(jié)點遍歷或RBS等方式進行同步GCS：擴散模式 越簡單的方法往往是越有效的 同步過程：對接收到的時間進行平均操作，并對自己的時間進行擴散 理論證明：當把所有節(jié)點的時間當成一張快照時，經(jīng)過若干輪擴散過程，所有節(jié)點時間最終將收斂到所有節(jié)點時間的平均值上

16、內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)新型同步機制 基于報文交換的同步機制面臨著挑戰(zhàn) 同步精度問題 可擴展性問題 新型同步機制 螢火蟲同步 協(xié)作同步 兩個概念 同時性與同步性螢火蟲同步1935年，Science1975年, Peskin的RC模型1989年，M&S模型（無延遲）1998年，Ernst（有延遲）結(jié)論2005年，真實地實現(xiàn)簡單，高效，可擴展性強M&S模型 研究由初始不同步狀態(tài)如何達到同步狀態(tài) 個體性質(zhì)相同,因此一旦達到同步則永遠同步 螢火蟲之間的交互被建模成電量耦合 耦合延遲規(guī)定為0 最終結(jié)論為:系統(tǒng)的同步收斂性取決于個體在自由狀態(tài)下的動力學特性

17、 同步的實質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量 ,相位差通過同步過程不斷縮小，最終達到完全相同,即同步狀態(tài) M&S模型 證明了全耦合系統(tǒng)的同步收斂性 沒有證明多跳網(wǎng)絡的同步收斂性Ernst的研究 M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時的情況 M&S模型只研究了正耦合的情況，Ernst還研究了負耦合的情況Ernst-正耦合（2個節(jié)點） 存在兩種情況 不可能達到完全同步 其實是M&S模型的擴展Ernst-負耦合（2個節(jié)點） 存在三種情況 和Peskin的結(jié)論一致 結(jié)論：考慮固定耦合延遲的情況下，只有負耦合才可能取得同步收

18、斂 負耦合下的全連接網(wǎng)絡 仿真研究方法 和兩個節(jié)點下的情況不同 出現(xiàn)分簇現(xiàn)象其他一些研究與結(jié)論 理論上沒有突破 單純的仿真方法意義有限 螢火蟲同步技術(shù)對耦合延遲、耦合強度、耦合性質(zhì)、初始相位、網(wǎng)絡拓撲等因素很敏感。雖然在例如兩個振蕩器的同步收斂性研究上取得了一定的進展，但無論是理論研究還是仿真研究，研究者在某些結(jié)論上還不能達成一致的認識。但可以認同的一點是：在實際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會取得在一定誤差范圍內(nèi)的同步。實踐：RFA算法RFA (Reachback Firefly Algorithm) 在24個Micaz節(jié)點組成的網(wǎng)絡上實現(xiàn) 同步誤差是存在的，和同步操作的頻率直接相關(guān)

19、核心思想：將某輪同步周期內(nèi)接收到的同步報文的影響推后到下一輪同步周期的起始時刻 總結(jié)：螢火蟲同步 同步可直接在物理層而不需要以報文的方式實現(xiàn)。直接用硬件實現(xiàn)，使得同步精度不會受到MAC延遲、協(xié)議處理與軟件實現(xiàn)等的影響。 由于對任何同步信號的處理方式均相同，與同步信號的來源無關(guān)，因此可擴展性以及適應網(wǎng)絡動態(tài)變化的能力很強。 機制非常簡單，不需要對其它節(jié)點的時間信息進行存儲。螢火蟲同步算法的一個限制是要求每個節(jié)點具有相似性，但這種機制在非相似節(jié)點所組成的網(wǎng)絡下能否起到同步的作用，目前還不清楚。 此外，由于螢火蟲同步的理論研究還遠未結(jié)束，工程實用性還有待考察。協(xié)作同步 本質(zhì)：空間平均而非時間平均 實

20、現(xiàn)上直接受限于信號處理技術(shù) 內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時間同步協(xié)議新型同步機制總結(jié)總結(jié) 在無線傳感器網(wǎng)絡中，時間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗、可擴展性和健壯性需求 經(jīng)典的時間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時鐘飄移補償、MAC層時間戳技術(shù)以及雙向報文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性和捎帶技術(shù)來降低同步能耗 螢火蟲同步和協(xié)作同步則側(cè)重于提高可擴展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡的應用 主要參考文獻（詳見原著）1 Elson J., Rmer K. Wireless sensor networks: a new regime for time

21、synchronization. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 149-154.3 Elson J., Girod L., Estrin D. Fine-grained time synchronization using reference broadcasts. In: Proc. 5th Symposium on Operation System Design and Implementation, Boston, 2002, 147-163.4 Ganeriwal S., Kumar R., Srivas

22、tava M. Timing-sync protocol for sensor networks. In: Proc. 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, 2003, 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,