第07章、時間同步技術(shù)v11

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

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

3、單調(diào)的函數(shù)相關術(shù)語信標節(jié)點和未知節(jié)點鄰居節(jié)點跳數(shù)、跳段距離基礎設施到達時間、到達時間差接收信號強度指示到達角度視線關系、非視線關系內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時間同步協(xié)議4.新型同步機制5.總結(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體積、計算能力和存儲空間存在限制傳輸方式不同：無線而非有線目標不同：局部最優(yōu)

4、而非全局最優(yōu)GPS（GLOBAL POSITION SYSTEM） 從根本上解決了人類在地球上的導航與定位問題。每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時間信息地面接收裝置同時接收4顆衛(wèi)星的時間信息，采用偽距測量定位方法可計算出時間和位置信息缺點（室內(nèi)、功耗、安全性、分布式）傳感器網(wǎng)絡的挑戰(zhàn)室內(nèi)、礦井、森林，有遮擋低功耗、低成本和小體積傳輸延遲的不確定性可擴展性、移動性健壯性、安全性網(wǎng)絡規(guī)模大、多點協(xié)作傳輸延遲的不確定性發(fā)送時間：發(fā)送節(jié)點構(gòu)造和發(fā)送時間同步消息所用時間。e.g., 系統(tǒng)調(diào)用時間；內(nèi)核調(diào)度時間；消息從主機發(fā)送到網(wǎng)絡接口時間。訪問時間：發(fā)送節(jié)點等待訪問網(wǎng)絡傳輸信道的時間。

5、傳播延遲：發(fā)送節(jié)點傳輸?shù)浇邮展?jié)點所經(jīng)歷的時間。接收時間：從接收節(jié)點的網(wǎng)絡接口接收到消息到通知主機消息達到事件所經(jīng)歷的時間間隔。SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver傳輸延遲的進一步細化(在MICA2上)時間時間典型值典型值特性特性Send time & Receive time0100ms不確定，依賴處理器負載、操不確定，依賴處理器負載、操作系統(tǒng)系統(tǒng)調(diào)用開銷作系統(tǒng)系統(tǒng)調(diào)用開銷Access time10500ms不確定，依賴信道負載。不確定，依賴信道負

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

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

8、4.新型同步機制5.總結(jié)典型時間同步協(xié)議NTP（Network Time Protocol）DMTSDMTS （Delay Measurement Time Synchronization） RBSRBS （Reference Broadcast Synchronization） TPSNTPSN （Timing-sync Protocol for Sensor Networks） HRTSHRTS （Hierarchy Referencing Time Synchronization Protocol） FTSPFTSP （Flooding Time Synchronization Prot

9、ocol） GCSGCS （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 Synchronizati

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

11、接收者接收者同步的基本依據(jù)：接收者時間相移均值為0單跳RBS用最小二乘法估計clock skew提高同步精度多跳RBS 時間路由技術(shù)：基于最短路徑查找節(jié)點節(jié)點A節(jié)點節(jié)點BT1T4T2T3RequestReply同步點2) 34() 12(TTTTTPSN（TIMING-SYNC PROTOCOL FOR SENSOR NETWORKS） TPSN（TIMING-SYNC PROTOCOL FOR SENSOR NETWORKS） 對同步誤差的分析很重要，是一種基本的分析方法理論分析和實驗證明：TPSN同步誤差是RBS的一半結(jié)合對clock skew的估計，可以提高TPSN的精度多跳TPSN全網(wǎng)

12、周期性同步“層發(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)，廣播能降低全網(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（HIE

13、RARCHY REFERENCING TIME SYNCHRONIZATION PROTOCOL） HRTS（HIERARCHY REFERENCING TIME SYNCHRONIZATION PROTOCOL） 根節(jié)點和應答者節(jié)點本質(zhì)上是采用TPSN同步根節(jié)點和非應答者節(jié)點本質(zhì)上是雙向報文交換同步（但非TPSN）應答者節(jié)點和非應答者節(jié)點本質(zhì)上是接收者-接收者同步FTSP（FLOODING TIME SYNCHRONIZATION PROTOCOL） 同步精度高工程實用性強強調(diào)實現(xiàn)細節(jié)FTSP（FLOODING TIME SYNCHRONIZATION PROTOCOL） MAC層時間戳技術(shù)

14、和平臺直接相關，書中給出了在Mica2平臺下的實現(xiàn)基本同步原理發(fā)送者-接收者同步單個報文中包括多個時間戳（在報文的不同位置）根據(jù)單個報文中的多個時間戳，可對中斷等待時間進行補償對clock skew的補償仍采用最小二乘法多跳FTSP洪泛方式廣播時間基準節(jié)點的時間協(xié)議健壯實際做了工程化的實現(xiàn)GCS（GLOBAL CLOCK SYNCHRONIZATION） 節(jié)點遍歷模式聚類分層模式擴散模式GCS：節(jié)點遍歷模式游走階段：記錄游走的出發(fā)和到達時間時間校正階段：根據(jù)節(jié)點在游走環(huán)的位置和游走時間對節(jié)點時間進行校正理論假設：每段游走的時間花費相同GCS：聚類分層模式單純的節(jié)點遍歷方式導致遍歷環(huán)過長，同步功

15、耗大通過分簇協(xié)議，把網(wǎng)絡組織成簇結(jié)構(gòu)簇頭節(jié)點間以節(jié)點遍歷方式同步簇內(nèi)節(jié)點可以節(jié)點遍歷或RBS等方式進行同步GCS：擴散模式越簡單的方法往往是越有效的同步過程：對接收到的時間進行平均操作，并對自己的時間進行擴散理論證明：當把所有節(jié)點的時間當成一張快照時，經(jīng)過若干輪擴散過程，所有節(jié)點時間最終將收斂到所有節(jié)點時間的平均值上內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時間同步協(xié)議4.新型同步機制5.總結(jié)新型同步機制基于報文交換的同步機制面臨著挑戰(zhàn)同步精度問題可擴展性問題新型同步機制螢火蟲同步協(xié)作同步兩個概念同時性與同步性螢火蟲同步1935年，Science1975年, Peskin的RC模型1989年，

16、M&S模型（無延遲）1998年，Ernst（有延遲）結(jié)論2005年，真實地實現(xiàn)簡單，高效，可擴展性強M&S模型研究由初始不同步狀態(tài)如何達到同步狀態(tài)個體性質(zhì)相同,因此一旦達到同步則永遠同步螢火蟲之間的交互被建模成電量耦合耦合延遲規(guī)定為0最終結(jié)論為:系統(tǒng)的同步收斂性取決于個體在自由狀態(tài)下的動力學特性同步的實質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量 ,相位差通過同步過程不斷縮小，最終達到完全相同,即同步狀態(tài) M&S模型證明了全耦合系統(tǒng)的同步收斂性沒有證明多跳網(wǎng)絡的同步收斂性ERNST的研究M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時

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

18、者在某些結(jié)論上還不能達成一致的認識。但可以認同的一點是：在實際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會取得在一定誤差范圍內(nèi)的同步。實踐：RFA算法RFA (REACHBACK FIREFLY ALGORITHM) 在24個Micaz節(jié)點組成的網(wǎng)絡上實現(xiàn) 同步誤差是存在的，和同步操作的頻率直接相關 核心思想：將某輪同步周期內(nèi)接收到的同步報文的影響推后到下一輪同步周期的起始時刻 總結(jié)：螢火蟲同步同步可直接在物理層而不需要以報文的方式實現(xiàn)。直接用硬件實現(xiàn)，使得同步精度不會受到MAC延遲、協(xié)議處理與軟件實現(xiàn)等的影響。由于對任何同步信號的處理方式均相同，與同步信號的來源無關，因此可擴展性以及適應網(wǎng)絡動態(tài)變

19、化的能力很強。機制非常簡單，不需要對其它節(jié)點的時間信息進行存儲。螢火蟲同步算法的一個限制是要求每個節(jié)點具有相似性，但這種機制在非相似節(jié)點所組成的網(wǎng)絡下能否起到同步的作用，目前還不清楚。此外，由于螢火蟲同步的理論研究還遠未結(jié)束，工程實用性還有待考察。協(xié)作同步 本質(zhì)：空間平均而非時間平均 實現(xiàn)上直接受限于信號處理技術(shù) 內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時間同步協(xié)議4.新型同步機制5.總結(jié)總結(jié) 在無線傳感器網(wǎng)絡中，時間同步不僅要關注同步精度，還需要關注同步能耗、可擴展性和健壯性需求經(jīng)典的時間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時鐘飄移補償、MAC層時間戳技術(shù)以及雙向報文交換來提高同步

20、精度，充分利用無線傳輸?shù)膹V播特性和捎帶技術(shù)來降低同步能耗螢火蟲同步和協(xié)作同步則側(cè)重于提高可擴展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡的應用 主要參考文獻（詳見原著）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 synchronization u

21、sing 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, 2003, 138-149.7 Mi

22、lls 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