第06章、時(shí)間同步技術(shù)要點(diǎn)

1、無線傳感器網(wǎng)絡(luò)Wireless Sensor Networks第五章、時(shí)間同步技術(shù)內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.總結(jié)內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.總結(jié)基本概念nWSN時(shí)間同步技術(shù)背景n時(shí)間同步技術(shù)的分類n時(shí)間同步技術(shù)的應(yīng)用場合n關(guān)鍵點(diǎn)：時(shí)鐘模型WSN時(shí)間同步技術(shù)背景n集中式系統(tǒng)與分布式系統(tǒng)n不同節(jié)點(diǎn)晶振不同，時(shí)間長了存在偏差n受電池能量，存儲空間，帶寬限制n集中式：事件間有著明確的時(shí)間先后關(guān)系，不存在同步問題n分布式：同步是必需的，只是對同步的要求程度不同n無線傳感器網(wǎng)絡(luò)時(shí)間同步n典型的分布式系統(tǒng)是無線傳感

2、器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)n需要解決的問題n同步精度n功耗n可擴(kuò)展性時(shí)間同步技術(shù)的分類排序、相對同步與絕對同步遞進(jìn)關(guān)系各自具有典型的協(xié)議代表外同步與內(nèi)同步參考源不同局部同步與全網(wǎng)同步同步對象的范圍不同時(shí)間同步技術(shù)的應(yīng)用場合n多傳感器數(shù)據(jù)壓縮與融合n低功耗MAC協(xié)議、路由協(xié)議n測距、定位（位置相關(guān)報(bào)務(wù)，LBS）n分布式系統(tǒng)的傳統(tǒng)要求n協(xié)作傳輸、處理的要求n. .時(shí)鐘模型n硬件時(shí)鐘模型n軟件時(shí)鐘模型硬件時(shí)鐘模型n基本名詞n時(shí)間、晶振、時(shí)鐘（RTC）n時(shí)鐘偏移（clock offset）n時(shí)鐘飄移（clock drift）n速率恒定模型n最常用，但不適應(yīng)環(huán)境變化劇烈的場合n飄移有界模型n常用于確定同步誤差上下

3、界n飄移變化有界模型軟件時(shí)鐘模型n軟件虛擬時(shí)鐘n一般是個(gè)分段連續(xù)、嚴(yán)格單調(diào)的函數(shù)內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.總結(jié)傳統(tǒng)與挑戰(zhàn)n傳統(tǒng)同步方法n傳感器網(wǎng)絡(luò)的挑戰(zhàn)傳統(tǒng)同步：NTP與GPSNTP：網(wǎng)絡(luò)時(shí)間協(xié)議GPS：全球定位系統(tǒng)NTP（Network Time Protocol） 體系結(jié)構(gòu)（網(wǎng)絡(luò)）NTP（Network Time Protocol）n體系結(jié)構(gòu)（單機(jī)）NTP（Network Time Protocol）nNTP不適合于WSNn體積、計(jì)算能力和存儲空間存在限制n傳輸方式不同：無線而非有線n目標(biāo)不同：局部最優(yōu)而非全局最優(yōu)GPS（Global Pos

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

5、進(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)文長度和發(fā)送速確定，依賴報(bào)文長度和發(fā)送速率。率。Propagation time1s（距離（距離300米）米）確定，依賴收發(fā)方物理距離和確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。傳播媒質(zhì)特性。Interrupt

6、 waiting time在大多數(shù)情況下在大多數(shù)情況下5s，在重，在重負(fù)載下，可達(dá)負(fù)載下，可達(dá)30s不確定，依賴處理器類型和處不確定，依賴處理器類型和處理器負(fù)載。理器負(fù)載。Encoding time & Decoding time100200s，2s的抖動的抖動確定，依賴射頻芯片的種類和確定，依賴射頻芯片的種類和設(shè)置。設(shè)置。Byte alignment time0400s確定，依賴發(fā)送速率和收發(fā)字確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。節(jié)偏移。低功耗、低成本和小體積n軟硬件都要受到該限制n存儲與計(jì)算能力均比較小n加劇了電能供應(yīng)的緊張（電池體積）n網(wǎng)絡(luò)規(guī)模大、密度高n通信距離近 分布式、協(xié)作可

7、擴(kuò)展性（Scalability）n在大規(guī)模網(wǎng)絡(luò)中尤為重要n是大規(guī)模無線傳感器網(wǎng)絡(luò)軟硬件設(shè)計(jì)中非常重要的問題n滿足不同的網(wǎng)絡(luò)類型、網(wǎng)絡(luò)規(guī)模n滿足不同的應(yīng)用需求健壯性n外部環(huán)境復(fù)雜，搞毀能力n需要應(yīng)對安全性挑戰(zhàn)n無線傳感器網(wǎng)絡(luò)拓?fù)鋭討B(tài)性較強(qiáng)n網(wǎng)絡(luò)規(guī)模變化、需求變化n影響：數(shù)據(jù)融合和休眠喚醒方式節(jié)能內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.總結(jié)典型時(shí)間同步協(xié)議nNTP（Network Time Protocol）nDMTS （Delay Measurement Time Synchronization） nRBS （Reference Broadcast Synchr

8、onization） nTPSN （Timing-sync Protocol for Sensor Networks） nHRTS （Hierarchy Referencing Time Synchronization Protocol） nFTSP （Flooding Time Synchronization Protocol） nGCS （Global Clock Synchronization） 發(fā)送者接收者：DMTS 最簡單直觀 單報(bào)文同步同步精度低 廣播方式同步能耗低發(fā)送者發(fā)送者接收者接收者發(fā)送前導(dǎo)碼發(fā)送前導(dǎo)碼、同步字同步字嵌 入 時(shí)嵌 入 時(shí)標(biāo)標(biāo)t0接收前導(dǎo)碼、接收前導(dǎo)碼、同步字同

9、步字接收接收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í)間訪問時(shí)間訪問時(shí)間DMTS（Delay Measurement Time Synchronization） 接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） RBS （Reference Broadcast Synchronization） n接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0單跳

10、RBSn用最小二乘法估計(jì)clock skew提高同步精度多跳RBS時(shí)間路由技術(shù)：基于最短路徑查找TPSN（Timing-sync Protocol for Sensor Networks） n否定：DMTSRBSn否定之否定：RBSTPSNnTPSN：雙報(bào)文交換的發(fā)送者接收者同步節(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） n對同步誤差的分析n很重要，是一種基本的分析方法n理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半n結(jié)合對clock skew的

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

12、 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） n根節(jié)點(diǎn)和應(yīng)答者節(jié)點(diǎn)本質(zhì)上是采用TPSN同步n根節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是雙向報(bào)文交換同步（但非TPSN）n應(yīng)答者節(jié)點(diǎn)和非應(yīng)答者節(jié)點(diǎn)本質(zhì)上是接收者-接收者同步HRTS（Hierarchy Referencing Time Synchronization Protocol） FTSP（Flooding Time Synchronization

13、 Protocol） n同步精度高n工程實(shí)用性強(qiáng)n強(qiáng)調(diào)實(shí)現(xiàn)細(xì)節(jié)nMAC層時(shí)間戳技術(shù)n和平臺直接相關(guān)，書中給出了在Mica2平臺下的實(shí)現(xiàn)n基本同步原理n發(fā)送者-接收者同步n單個(gè)報(bào)文中包括多個(gè)時(shí)間戳（在報(bào)文的不同位置）n根據(jù)單個(gè)報(bào)文中的多個(gè)時(shí)間戳，可對中斷等待時(shí)間進(jìn)行補(bǔ)償n對clock skew的補(bǔ)償仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） 多跳FTSPn洪泛方式廣播時(shí)間基準(zhǔn)節(jié)點(diǎn)的時(shí)間n協(xié)議健壯n實(shí)際做了工程化的實(shí)現(xiàn)內(nèi)容提要1.基本概念2.傳統(tǒng)與挑戰(zhàn)3.典型時(shí)間同步協(xié)議4.新型同步機(jī)制5.總結(jié)新型同步機(jī)制n基于報(bào)文交換的同步機(jī)制面臨著

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

15、小，最終達(dá)到完全相同,即同步狀態(tài) M&S模型n證明了全耦合系統(tǒng)的同步收斂性n沒有證明多跳網(wǎng)絡(luò)的同步收斂性Ernst的研究nM&S模型沒有考慮耦合延遲，Ernst研究了耦合延遲固定時(shí)的情況nM&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é)論n理論上沒有突破n單純的

16、仿真方法意義有限n螢火蟲同步技術(shù)對耦合延遲、耦合強(qiáng)度、耦合性質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾?。雖然在例如兩個(gè)振蕩器的同步收斂性研究上取得了一定的進(jìn)展，但無論是理論研究還是仿真研究，研究者在某些結(jié)論上還不能達(dá)成一致的認(rèn)識。但可以認(rèn)同的一點(diǎn)是：在實(shí)際系統(tǒng)中，基于螢火蟲同步策略的同步技術(shù)會取得在一定誤差范圍內(nèi)的同步。總結(jié)：螢火蟲同步n同步可直接在物理層而不需要以報(bào)文的方式實(shí)現(xiàn)。直接用硬件實(shí)現(xiàn)，使得同步精度不會受到MAC延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影響。n由于對任何同步信號的處理方式均相同，與同步信號的來源無關(guān)，因此可擴(kuò)展性以及適應(yīng)網(wǎng)絡(luò)動態(tài)變化的能力很強(qiáng)。n機(jī)制非常簡單，不需要對其它節(jié)點(diǎn)的時(shí)間信息進(jìn)

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

18、耗n螢火蟲同步和協(xié)作同步則側(cè)重于提高可擴(kuò)展性和健壯性。非常適合于大規(guī)模無線傳感器網(wǎng)絡(luò)的應(yīng)用 主要參考文獻(xiàn)（詳見原著）n1 Elson J., Rmer K. Wireless sensor networks: a new regime for time synchronization. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 149-154.n3 Elson J., Girod L., Estrin D. Fine-grained time synchronization using reference broadcast

19、s. In: Proc. 5th Symposium on Operation System Design and Implementation, Boston, 2002, 147-163.n4 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.n7 Mills D. L. Network time

20、 protocol (Version3) specification, implementation and analysis. University of Delaware, DARPA Network Working Group Report: RFC-1305, 1992. n13 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.n14 Su Ping, Delay measurement time synchronization for wireless sensor