第06章-時(shí)間同步

1、第六章 時(shí)間同步內(nèi)容提要時(shí)間同步概述 基本概念 傳統(tǒng)與挑戰(zhàn)2. 時(shí)間同步算法及比較 典型時(shí)間同步協(xié)議 新型同步機(jī)制內(nèi)容提要時(shí)間同步概述 基本概念 傳統(tǒng)與挑戰(zhàn)2. 時(shí)間同步算法及比較 典型時(shí)間同步協(xié)議 新型同步機(jī)制基本概念 WSN時(shí)間同步技術(shù)背景 時(shí)間同步技術(shù)的分類 時(shí)間同步技術(shù)的應(yīng)用場(chǎng)合 關(guān)鍵點(diǎn)：時(shí)鐘模型WSN時(shí)間同步技術(shù)背景 集中式系統(tǒng)與分布式系統(tǒng) 集中式：事件間有著明確的時(shí)間先后關(guān)系，不存在同步問題 分布式：同步是必需的，只是對(duì)同步的要求程度不同 無線傳感器網(wǎng)絡(luò)時(shí)間同步 典型的分布式系統(tǒng) 是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ) 需要解決的問題 同步精度 功耗 可擴(kuò)展性WSN時(shí)間同步機(jī)制的主要性能參數(shù)

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

3、件時(shí)鐘模型內(nèi)容提要時(shí)間同步概述 基本概念 傳統(tǒng)與挑戰(zhàn)2. 時(shí)間同步算法及比較 典型時(shí)間同步協(xié)議 新型同步機(jī)制傳統(tǒng)同步：NTP與GPS NTP：網(wǎng)絡(luò)時(shí)間協(xié)議 GPS：全球定位系統(tǒng)NTP（Network Time Protocol） 體系結(jié)構(gòu)（網(wǎng)絡(luò)）NTP（Network Time Protocol） 體系結(jié)構(gòu)（單機(jī)）NTP（Network Time Protocol） NTP不適合于WSN 體積、計(jì)算能力和存儲(chǔ)空間存在限制 傳輸方式不同：無線而非有線 目標(biāo)不同：局部最優(yōu)而非全局最優(yōu)GPS（Global Position System） 從根本上解決了人類在地球上的導(dǎo)航與定位問題。 每顆衛(wèi)星上配備

4、有高精度的銣、銫原子鐘，并不斷發(fā)射其時(shí)間信息 地面接收裝置同時(shí)接收4顆衛(wèi)星的時(shí)間信息，采用偽距測(cè)量定位方法可計(jì)算出時(shí)間和位置信息 缺點(diǎn)（室內(nèi)、功耗、安全性、分布式）傳感器網(wǎng)絡(luò)的挑戰(zhàn) 室內(nèi)、礦井、森林，有遮擋 低功耗、低成本和小體積 傳輸延遲的不確定性 可擴(kuò)展性、移動(dòng)性 健壯性、安全性 網(wǎng)絡(luò)規(guī)模大、多點(diǎn)協(xié)作傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver同步信息的時(shí)延包括以下幾部分同步信息的時(shí)延包括以下幾部分：發(fā)送時(shí)間、訪問時(shí)間、傳輸：發(fā)送時(shí)間、訪問時(shí)

5、間、傳輸時(shí)時(shí)延延、傳播時(shí)間、傳播時(shí)間、接收接收時(shí)延、時(shí)延、接收接收時(shí)間時(shí)間傳輸延遲的進(jìn)一步細(xì)化(在Mica2上)時(shí)間時(shí)間典型值典型值特性特性Send time & Receive time0100ms不確定，依賴處理器負(fù)載、操不確定，依賴處理器負(fù)載、操作系統(tǒng)系統(tǒng)調(diào)用開銷作系統(tǒng)系統(tǒng)調(diào)用開銷Access time10500ms不確定，依賴信道負(fù)載。不確定，依賴信道負(fù)載。Transmission time & Reception time1020ms確定，依賴報(bào)文長(zhǎng)度和發(fā)送速確定，依賴報(bào)文長(zhǎng)度和發(fā)送速率。率。Propagation time1s（距離（距離300米）米）確定，依賴收發(fā)

6、方物理距離和確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。傳播媒質(zhì)特性。Interrupt waiting time在大多數(shù)情況下在大多數(shù)情況下5s，在重，在重負(fù)載下，可達(dá)負(fù)載下，可達(dá)30s不確定，依賴處理器類型和處不確定，依賴處理器類型和處理器負(fù)載。理器負(fù)載。Encoding time & Decoding time100200s，2s的抖動(dòng)的抖動(dòng)確定，依賴射頻芯片的種類和確定，依賴射頻芯片的種類和設(shè)置。設(shè)置。Byte alignment time0400s確定，依賴發(fā)送速率和收發(fā)字確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。節(jié)偏移。低功耗、低成本和小體積 軟硬件都要受到該限制 存儲(chǔ)與計(jì)算能力均比較

7、小 加劇了電能供應(yīng)的緊張（電池體積） 網(wǎng)絡(luò)規(guī)模大、密度高 通信距離近 分布式、協(xié)作可擴(kuò)展性（Scalability） 在大規(guī)模網(wǎng)絡(luò)中尤為重要 是大規(guī)模無線傳感器網(wǎng)絡(luò)軟硬件設(shè)計(jì)中非常重要的問題 滿足不同的網(wǎng)絡(luò)類型、網(wǎng)絡(luò)規(guī)模 滿足不同的應(yīng)用需求健壯性 外部環(huán)境復(fù)雜，搞毀能力 需要應(yīng)對(duì)安全性挑戰(zhàn) 無線傳感器網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性較強(qiáng) 網(wǎng)絡(luò)規(guī)模變化、需求變化內(nèi)容提要時(shí)間同步概述 基本概念 傳統(tǒng)與挑戰(zhàn)2. 時(shí)間同步算法及比較 典型時(shí)間同步協(xié)議 新型同步機(jī)制時(shí)間同步 發(fā)送者接收者同步發(fā)送者接收者同步：發(fā)送者在報(bào)文中嵌入報(bào)發(fā)送者在報(bào)文中嵌入報(bào)文發(fā)送時(shí)間，而接收者在接收到報(bào)文后記錄下文發(fā)送時(shí)間，而接收者在接收到報(bào)文后

8、記錄下接收時(shí)間，并利用這些時(shí)間信息計(jì)算出收發(fā)雙接收時(shí)間，并利用這些時(shí)間信息計(jì)算出收發(fā)雙方的時(shí)鐘偏移，進(jìn)而達(dá)到收發(fā)雙方的時(shí)間同步。方的時(shí)鐘偏移，進(jìn)而達(dá)到收發(fā)雙方的時(shí)間同步。 接收者接收者同步接收者接收者同步：發(fā)送者發(fā)送一個(gè)同步報(bào)發(fā)送者發(fā)送一個(gè)同步報(bào)文到多個(gè)接收者，這些接收者通過對(duì)同一個(gè)報(bào)文到多個(gè)接收者，這些接收者通過對(duì)同一個(gè)報(bào)文時(shí)間的比較，計(jì)算出它們之間的時(shí)鐘偏移，文時(shí)間的比較，計(jì)算出它們之間的時(shí)鐘偏移，從而達(dá)到接收者一接收者同步。從而達(dá)到接收者一接收者同步。典型時(shí)間同步協(xié)議 NTP（Network Time Protocol） DMTS （Delay Measurement Time Sync

9、hronization） RBS （Reference Broadcast Synchronization） TPSN （Timing-sync Protocol for Sensor Networks） HRTS （Hierarchy Referencing Time Synchronization Protocol） FTSP （Flooding Time Synchronization Protocol） GCS （Global Clock Synchronization） 發(fā)送者接收者：DMTS 最簡(jiǎn)單直觀 單報(bào)文同步同步精度低 廣播方式同步能耗低發(fā)送者發(fā)送者接收者接收者發(fā)送前導(dǎo)碼發(fā)送

10、前導(dǎo)碼、同步字同步字 （nt）接收前導(dǎo)碼、接收前導(dǎo)碼、同步字同步字接收接收ACK接收接收數(shù)據(jù)數(shù)據(jù)發(fā)送發(fā)送ACK接收接收處理處理發(fā)送時(shí)間發(fā)送時(shí)間訪問時(shí)間訪問時(shí)間DMTS（Delay Measurement Time Synchronization） 基于同步消息在傳輸路徑上所有延遲的估計(jì)，實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步去除去除發(fā)送端的處理延遲發(fā)送端的處理延遲和和MAC層的訪問延遲層的訪問延遲t0+nt+(t2-t1)嵌入時(shí)嵌入時(shí)標(biāo)標(biāo)t0時(shí)標(biāo)時(shí)標(biāo)t1時(shí)標(biāo)時(shí)標(biāo)t2接收者接收者：RBS （Reference Broadcast SynchronizationReceiverNICSenderCritical P

11、athTimeNICSenderReceiver1Critical PathReceiver2通過廣播同步指示分組實(shí)現(xiàn)接收點(diǎn)間的相對(duì)時(shí)間同步RF信號(hào)的傳播時(shí)間差值非常小可以消除接收節(jié)點(diǎn)的接收協(xié)議處理、上下文切換、網(wǎng)絡(luò)接口向主機(jī)傳送影響RBS機(jī)制性能的因素：時(shí)鐘偏差、接收點(diǎn)不確定性因素以及接收點(diǎn)的個(gè)數(shù)RBS （Reference Broadcast Synchronization） 接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0單跳RBS 用最小二乘法估計(jì)clock skew提高同步精度多跳RBS 時(shí)間路由技術(shù)：基于最短路徑查找TPSN（Timing-sync Protocol for Se

12、nsor Networks） 否定：DMTSRBS 否定之否定：RBSTPSN TPSN：雙報(bào)文交換的發(fā)送者接收者同步節(jié)點(diǎn)節(jié)點(diǎn)A節(jié)點(diǎn)節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)2)()(3412TTTTTPSN（Timing-sync Protocol for Sensor Networks） ：脈沖的傳輸延時(shí)移：節(jié)點(diǎn)間的相對(duì)時(shí)鐘漂d-3412dTTdTT 對(duì)同步誤差的分析 很重要，是一種基本的分析方法 理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半 結(jié)合對(duì)lock skew的估計(jì)，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Ne

13、tworks） 多跳TPSN 全網(wǎng)周期性同步 “層發(fā)現(xiàn)”把網(wǎng)絡(luò)組織成最短生成樹 逐層在相鄰兩層節(jié)點(diǎn)間同步 網(wǎng)絡(luò)內(nèi)兩個(gè)節(jié)點(diǎn)的同步 “后同步”查找兩個(gè)節(jié)點(diǎn)間的路徑 在路徑的相鄰兩個(gè)節(jié)點(diǎn)間進(jìn)行TPSN同步HRTS（Hierarchy Referencing Time Synchronization Protocol） TPSN基于雙向報(bào)文交換，因此同步精度高 TPSN本質(zhì)上是對(duì)同步，因此全網(wǎng)同步的同步能耗高 由RBS發(fā)現(xiàn)，廣播能降低全網(wǎng)同步能耗 結(jié)合廣播和節(jié)點(diǎn)間的雙向報(bào)文交換同步HRTS協(xié)議 BS n1 n2 n3 (a) BS n1 n2 n3 (b) BS n1 n2 n3 (c) n4 BS

14、n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） 根節(jié)點(diǎn)和應(yīng)答者節(jié)點(diǎn)本質(zhì)上是采用TPSN同步 根節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是雙向報(bào)文交換同步（但非TPSN） 應(yīng)答者節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是接收者-接收者同步HRTS（Hierarchy Referencing Time Synchronization Protocol） FTSP（Flooding Time Synchronization Protocol） 同步精度高 工程實(shí)用性強(qiáng) 強(qiáng)調(diào)實(shí)現(xiàn)細(xì)節(jié) MAC層時(shí)間戳技術(shù) 和平臺(tái)直接相關(guān) 基本同步原理

15、發(fā)送者-接收者同步 單個(gè)報(bào)文中包括多個(gè)時(shí)間戳（在報(bào)文的不同位置） 根據(jù)單個(gè)報(bào)文中的多個(gè)時(shí)間戳，可對(duì)中斷等待時(shí)間進(jìn)行補(bǔ)償 對(duì)clock skew的補(bǔ)償仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） 多跳FTSP 洪泛方式廣播時(shí)間基準(zhǔn)節(jié)點(diǎn)的時(shí)間 協(xié)議健壯 實(shí)際做了工程化的實(shí)現(xiàn)GCS（Global Clock Synchronization） 節(jié)點(diǎn)遍歷模式 聚類分層模式 擴(kuò)散模式GCS：節(jié)點(diǎn)遍歷模式 游走階段：記錄游走的出發(fā)和到達(dá)時(shí)間 時(shí)間校正階段：根據(jù)節(jié)點(diǎn)在游走環(huán)的位置和游走時(shí)間對(duì)節(jié)點(diǎn)時(shí)間進(jìn)行校正 理論假設(shè)：每段游走的時(shí)間花費(fèi)相同GCS：聚

16、類分層模式 單純的節(jié)點(diǎn)遍歷方式導(dǎo)致遍歷環(huán)過長(zhǎng)，同步功耗大 通過分簇協(xié)議，把網(wǎng)絡(luò)組織成簇結(jié)構(gòu) 簇頭節(jié)點(diǎn)間以節(jié)點(diǎn)遍歷方式同步 簇內(nèi)節(jié)點(diǎn)可以節(jié)點(diǎn)遍歷或RBS等方式進(jìn)行同步GCS：擴(kuò)散模式 越簡(jiǎn)單的方法往往是越有效的 同步過程：對(duì)接收到的時(shí)間進(jìn)行平均操作，并對(duì)自己的時(shí)間進(jìn)行擴(kuò)散 理論證明：當(dāng)把所有節(jié)點(diǎn)的時(shí)間當(dāng)成一張快照時(shí)，經(jīng)過若干輪擴(kuò)散過程，所有節(jié)點(diǎn)時(shí)間最終將收斂到所有節(jié)點(diǎn)時(shí)間的平均值上內(nèi)容提要時(shí)間同步概述 基本概念 傳統(tǒng)與挑戰(zhàn)2. 時(shí)間同步算法及比較 典型時(shí)間同步協(xié)議 新型同步機(jī)制新型同步機(jī)制 基于報(bào)文交換的同步機(jī)制面臨著挑戰(zhàn) 同步精度問題 可擴(kuò)展性問題 新型同步機(jī)制 螢火蟲同步 協(xié)作同步 兩個(gè)概念

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

18、斂性 沒有證明多跳網(wǎng)絡(luò)的同步收斂性Ernst的研究 M&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時(shí)的情況 M&S模型只研究了正耦合的情況，Ernst還研究了負(fù)耦合的情況Ernst-正耦合（2個(gè)節(jié)點(diǎn)） 存在兩種情況 不可能達(dá)到完全同步 其實(shí)是M&S模型的擴(kuò)展Ernst-負(fù)耦合（2個(gè)節(jié)點(diǎn)） 存在三種情況 和Peskin的結(jié)論一致 結(jié)論：考慮固定耦合延遲的情況下，只有負(fù)耦合才可能取得同步收斂 負(fù)耦合下的全連接網(wǎng)絡(luò) 仿真研究方法 和兩個(gè)節(jié)點(diǎn)下的情況不同 出現(xiàn)分簇現(xiàn)象其他一些研究與結(jié)論 理論上沒有突破 單純的仿真方法意義有限 螢火蟲同步技術(shù)對(duì)耦合延遲、耦合強(qiáng)度、耦合性

19、質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾?。雖然在例如兩個(gè)振蕩器的同步收斂性研究上取得了一定的進(jìn)展，但無論是理論研究還是仿真研究，研究者在某些結(jié)論上還不能達(dá)成一致的認(rèn)識(shí)。但可以認(rèn)同的一點(diǎn)是：在實(shí)際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會(huì)取得在一定誤差范圍內(nèi)的同步。實(shí)踐：RFA算法RFA (Reachback Firefly Algorithm) 在24個(gè)Micaz節(jié)點(diǎn)組成的網(wǎng)絡(luò)上實(shí)現(xiàn) 同步誤差是存在的，和同步操作的頻率直接相關(guān) 核心思想：將某輪同步周期內(nèi)接收到的同步報(bào)文的影響推后到下一輪同步周期的起始時(shí)刻 總結(jié)：螢火蟲同步 同步可直接在物理層而不需要以報(bào)文的方式實(shí)現(xiàn)。直接用硬件實(shí)現(xiàn)，使得同步精度不會(huì)受到

20、MAC延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影響。 由于對(duì)任何同步信號(hào)的處理方式均相同，與同步信號(hào)的來源無關(guān)，因此可擴(kuò)展性以及適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)變化的能力很強(qiáng)。 機(jī)制非常簡(jiǎn)單，不需要對(duì)其它節(jié)點(diǎn)的時(shí)間信息進(jìn)行存儲(chǔ)。螢火蟲同步算法的一個(gè)限制是要求每個(gè)節(jié)點(diǎn)具有相似性，但這種機(jī)制在非相似節(jié)點(diǎn)所組成的網(wǎng)絡(luò)下能否起到同步的作用，目前還不清楚。 此外，由于螢火蟲同步的理論研究還遠(yuǎn)未結(jié)束，工程實(shí)用性還有待考察。協(xié)作同步 本質(zhì)：空間平均而非時(shí)間平均 實(shí)現(xiàn)上直接受限于信號(hào)處理技術(shù) 總結(jié) 在無線傳感器網(wǎng)絡(luò)中，時(shí)間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗、可擴(kuò)展性和健壯性需求 經(jīng)典的時(shí)間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用

21、時(shí)鐘漂移補(bǔ)償、MAC層時(shí)間戳技術(shù)以及雙向報(bào)文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性和捎帶技術(shù)來降低同步能耗 螢火蟲同步和協(xié)作同步則側(cè)重于提高可擴(kuò)展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡(luò)的應(yīng)用 主要參考文獻(xiàn)（詳見原著）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-

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

23、os 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 Syste