無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSN 第7章 時(shí)間同步

1、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)第七章 時(shí)間同步無(wú)線(xiàn)傳感器網(wǎng)絡(luò)內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.小結(jié)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSN時(shí)間同步技術(shù)背景 集中式系統(tǒng)與分布式系統(tǒng) 集中式：事件間有著明確的時(shí)間先后關(guān)系，不存在同步問(wèn)題 分布式：同步是必需的，只是對(duì)同步的要求程度不同 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)時(shí)間同步 典型的分布式系統(tǒng) 是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ) 需要解決的問(wèn)題 同步精度 功耗 可擴(kuò)展性無(wú)線(xiàn)傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)的分類(lèi)排序、相對(duì)同步與絕對(duì)同步遞進(jìn)關(guān)系各自具有典型的協(xié)議代表外同步與內(nèi)同步參考源不同局部同步與全網(wǎng)同步同步對(duì)象的范圍不同無(wú)線(xiàn)傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)的應(yīng)用場(chǎng)合 多傳感器數(shù)據(jù)壓縮與融

2、合 低功耗MAC協(xié)議、路由協(xié)議 測(cè)距、定位（位置相關(guān)報(bào)務(wù)，LBS） 分布式系統(tǒng)的傳統(tǒng)要求 協(xié)作傳輸、處理的要求 . .無(wú)線(xiàn)傳感器網(wǎng)絡(luò)時(shí)鐘模型 硬件時(shí)鐘模型 軟件時(shí)鐘模型無(wú)線(xiàn)傳感器網(wǎng)絡(luò)硬件時(shí)鐘模型 基本名詞時(shí)間、晶振、時(shí)鐘（RTC）時(shí)鐘偏移（clock offset）時(shí)鐘飄移（clock drift） 速率恒定模型最常用，但不適應(yīng)環(huán)境變化劇烈的場(chǎng)合 飄移有界模型常用于確定同步誤差上下界 飄移變化有界模型無(wú)線(xiàn)傳感器網(wǎng)絡(luò)軟件時(shí)鐘模型 軟件虛擬時(shí)鐘 一般是個(gè)分段連續(xù)、嚴(yán)格單調(diào)的函數(shù)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)傳統(tǒng)與挑戰(zhàn) 傳統(tǒng)同步方法 傳感器網(wǎng)絡(luò)的挑戰(zhàn)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)傳統(tǒng)同步：NTP與GPSNTP：網(wǎng)絡(luò)時(shí)間協(xié)議GPS：

3、全球定位系統(tǒng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)NTP（Network Time Protocol） 體系結(jié)構(gòu)（網(wǎng)絡(luò)）無(wú)線(xiàn)傳感器網(wǎng)絡(luò)NTP（Network Time Protocol） 體系結(jié)構(gòu)（單機(jī)）無(wú)線(xiàn)傳感器網(wǎng)絡(luò)NTP（Network Time Protocol） NTP不適合于WSN 體積、計(jì)算能力和存儲(chǔ)空間存在限制 傳輸方式不同：無(wú)線(xiàn)而非有線(xiàn) 目標(biāo)不同：局部最優(yōu)而非全局最優(yōu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)GPS（Global Position System） 從根本上解決了人類(lèi)在地球上的導(dǎo)航與定位問(wèn)題。 每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時(shí)間信息 地面接收裝置同時(shí)接收4顆衛(wèi)星的時(shí)間信息，采用偽距測(cè)量定位方法可

4、計(jì)算出時(shí)間和位置信息 缺點(diǎn)（室內(nèi)、功耗、安全性、分布式）無(wú)線(xiàn)傳感器網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)的挑戰(zhàn) 室內(nèi)、礦井、森林，有遮擋 低功耗、低成本和小體積 傳輸延遲的不確定性 可擴(kuò)展性、移動(dòng)性 健壯性、安全性 網(wǎng)絡(luò)規(guī)模大、多點(diǎn)協(xié)作無(wú)線(xiàn)傳感器網(wǎng)絡(luò)傳輸延遲的不確定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver無(wú)線(xiàn)傳感器網(wǎng)絡(luò)傳輸延遲的進(jìn)一步細(xì)化(在Mica2上)時(shí)間時(shí)間典型值典型值特性特性Send time & Receive time0100ms不確定，依賴(lài)處理器負(fù)載、操不確定

5、，依賴(lài)處理器負(fù)載、操作系統(tǒng)系統(tǒng)調(diào)用開(kāi)銷(xiāo)作系統(tǒng)系統(tǒng)調(diào)用開(kāi)銷(xiāo)Access time10500ms不確定，依賴(lài)信道負(fù)載。不確定，依賴(lài)信道負(fù)載。Transmission time & Reception time1020ms確定，依賴(lài)報(bào)文長(zhǎng)度和發(fā)送速確定，依賴(lài)報(bào)文長(zhǎng)度和發(fā)送速率。率。Propagation time1s（距離（距離300米）米）確定，依賴(lài)收發(fā)方物理距離和確定，依賴(lài)收發(fā)方物理距離和傳播媒質(zhì)特性。傳播媒質(zhì)特性。Interrupt waiting time在大多數(shù)情況下在大多數(shù)情況下5s，在重，在重負(fù)載下，可達(dá)負(fù)載下，可達(dá)30s不確定，依賴(lài)處理器類(lèi)型和處不確定，依賴(lài)處理器類(lèi)型和處理器

6、負(fù)載。理器負(fù)載。Encoding time & Decoding time100200s，2s的抖動(dòng)的抖動(dòng)確定，依賴(lài)射頻芯片的種類(lèi)和確定，依賴(lài)射頻芯片的種類(lèi)和設(shè)置。設(shè)置。Byte alignment time0400s確定，依賴(lài)發(fā)送速率和收發(fā)字確定，依賴(lài)發(fā)送速率和收發(fā)字節(jié)偏移。節(jié)偏移。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)低功耗、低成本和小體積 軟硬件都要受到該限制 存儲(chǔ)與計(jì)算能力均比較小 加劇了電能供應(yīng)的緊張（電池體積） 網(wǎng)絡(luò)規(guī)模大、密度高 通信距離近 分布式、協(xié)作無(wú)線(xiàn)傳感器網(wǎng)絡(luò)可擴(kuò)展性（Scalability） 在大規(guī)模網(wǎng)絡(luò)中尤為重要 是大規(guī)模無(wú)線(xiàn)傳感器網(wǎng)絡(luò)軟硬件設(shè)計(jì)中非常重要的問(wèn)題 滿(mǎn)足不同的網(wǎng)絡(luò)類(lèi)型、

7、網(wǎng)絡(luò)規(guī)模 滿(mǎn)足不同的應(yīng)用需求無(wú)線(xiàn)傳感器網(wǎng)絡(luò)健壯性 外部環(huán)境復(fù)雜，搞毀能力 需要應(yīng)對(duì)安全性挑戰(zhàn) 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)性較強(qiáng) 網(wǎng)絡(luò)規(guī)模變化、需求變化無(wú)線(xiàn)傳感器網(wǎng)絡(luò)典型時(shí)間同步協(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

8、 Protocol） FTSP （Flooding Time Synchronization Protocol） GCS （Global Clock Synchronization） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)發(fā)送者接收者：DMTS 最簡(jiǎn)單直觀(guān) 單報(bào)文同步同步精度低 廣播方式同步能耗低發(fā)送者發(fā)送者接收者接收者發(fā)送前導(dǎo)碼發(fā)送前導(dǎo)碼、同步字同步字嵌 入 時(shí)嵌 入 時(shí)標(biāo)標(biāo)t0接收前導(dǎo)碼、接收前導(dǎo)碼、同步字同步字接收接收ACK接收接收數(shù)據(jù)數(shù)據(jù)發(fā)送發(fā)送ACK接收接收處理處理時(shí)標(biāo)時(shí)標(biāo)t1時(shí)標(biāo)時(shí)標(biāo)t2發(fā)送時(shí)間發(fā)送時(shí)間訪(fǎng)問(wèn)時(shí)間訪(fǎng)問(wèn)時(shí)間DMTS（Delay Measurement Time Synchronization）

9、 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)RBS （Reference Broadcast Synchronization） 接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0無(wú)線(xiàn)傳感器網(wǎng)絡(luò)單跳RBS 用最小二乘法估計(jì)clock skew提高同步精度無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多跳RBS時(shí)間路由技術(shù)：基于最短路徑查找無(wú)線(xiàn)傳感器網(wǎng)絡(luò)TPSN（Timing-sync Proto

10、col for Sensor Networks） 否定：DMTSRBS 否定之否定：RBSTPSN TPSN：雙報(bào)文交換的發(fā)送者接收者同步無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)節(jié)點(diǎn)A節(jié)點(diǎn)節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)2) 34() 12(TTTTTPSN（Timing-sync Protocol for Sensor Networks） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò) 對(duì)同步誤差的分析很重要，是一種基本的分析方法理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半結(jié)合對(duì)clock skew的估計(jì)，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Networks）

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

12、n3 (c) n4 BS n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò) 根節(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） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)FTSP（Flooding Time Synchronization Protocol） 同步精度高 工程實(shí)用性強(qiáng) 強(qiáng)調(diào)實(shí)現(xiàn)

13、細(xì)節(jié)無(wú)線(xiàn)傳感器網(wǎng)絡(luò) MAC層時(shí)間戳技術(shù)和平臺(tái)直接相關(guān)，書(shū)中給出了在Mica2平臺(tái)下的實(shí)現(xiàn) 基本同步原理發(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） 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)多跳FTSP 洪泛方式廣播時(shí)間基準(zhǔn)節(jié)點(diǎn)的時(shí)間 協(xié)議健壯 實(shí)際做了工程化的實(shí)現(xiàn)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)GCS（Global Clock Synchronization） 節(jié)點(diǎn)遍歷模式 聚類(lèi)分層模式 擴(kuò)散模式無(wú)線(xiàn)傳感器網(wǎng)絡(luò)GCS：節(jié)點(diǎn)遍歷模式 游走階

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

15、臨著挑戰(zhàn)同步精度問(wèn)題可擴(kuò)展性問(wèn)題 新型同步機(jī)制螢火蟲(chóng)同步協(xié)作同步 兩個(gè)概念同時(shí)性與同步性無(wú)線(xiàn)傳感器網(wǎng)絡(luò)螢火蟲(chóng)同步1935年，Science1975年, Peskin的RC模型1989年，M&S模型（無(wú)延遲）1998年，Ernst（有延遲）結(jié)論2005年，真實(shí)地實(shí)現(xiàn)簡(jiǎn)單，高效，可擴(kuò)展性強(qiáng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)M&S模型 研究由初始不同步狀態(tài)如何達(dá)到同步狀態(tài) 個(gè)體性質(zhì)相同,因此一旦達(dá)到同步則永遠(yuǎn)同步 螢火蟲(chóng)之間的交互被建模成電量耦合 耦合延遲規(guī)定為0 最終結(jié)論為:系統(tǒng)的同步收斂性取決于個(gè)體在自由狀態(tài)下的動(dòng)力學(xué)特性 同步的實(shí)質(zhì)：不同步產(chǎn)生了耦合，耦合改變了狀態(tài)量，而狀態(tài)量又改變了相位量 ,相

16、位差通過(guò)同步過(guò)程不斷縮小，最終達(dá)到完全相同,即同步狀態(tài) 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)M&S模型 證明了全耦合系統(tǒng)的同步收斂性 沒(méi)有證明多跳網(wǎng)絡(luò)的同步收斂性無(wú)線(xiàn)傳感器網(wǎng)絡(luò)Ernst的研究 M&S模型沒(méi)有考慮耦合延遲，Ernst研究了耦合延遲固定時(shí)的情況 M&S模型只研究了正耦合的情況，Ernst還研究了負(fù)耦合的情況無(wú)線(xiàn)傳感器網(wǎng)絡(luò)Ernst-正耦合（2個(gè)節(jié)點(diǎn)）存在兩種情況不可能達(dá)到完全同步其實(shí)是M&S模型的擴(kuò)展無(wú)線(xiàn)傳感器網(wǎng)絡(luò)Ernst-負(fù)耦合（2個(gè)節(jié)點(diǎn)）存在三種情況和Peskin的結(jié)論一致結(jié)論：考慮固定耦合延遲的情況下，只有負(fù)耦合才可能取得同步收斂 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)負(fù)耦合下的全連接

17、網(wǎng)絡(luò)仿真研究方法和兩個(gè)節(jié)點(diǎn)下的情況不同出現(xiàn)分簇現(xiàn)象無(wú)線(xiàn)傳感器網(wǎng)絡(luò)其他一些研究與結(jié)論 理論上沒(méi)有突破 單純的仿真方法意義有限 螢火蟲(chóng)同步技術(shù)對(duì)耦合延遲、耦合強(qiáng)度、耦合性質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾小ｋm然在例如兩個(gè)振蕩器的同步收斂性研究上取得了一定的進(jìn)展，但無(wú)論是理論研究還是仿真研究，研究者在某些結(jié)論上還不能達(dá)成一致的認(rèn)識(shí)。但可以認(rèn)同的一點(diǎn)是：在實(shí)際系統(tǒng)中，基于螢火蟲(chóng)同步策略的同步技術(shù)會(huì)取得在一定誤差范圍內(nèi)的同步。無(wú)線(xiàn)傳感器網(wǎng)絡(luò)實(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í)刻 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)總結(jié)：螢火蟲(chóng)同步 同步可直接在物理層而不需要以報(bào)文的方式實(shí)現(xiàn)。直接用硬件實(shí)現(xiàn)，使得同步精度不會(huì)受到MAC延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影