無線傳感器網(wǎng)絡(luò)的時(shí)間同步技術(shù)課件

1、無線傳感器網(wǎng)絡(luò)技術(shù)講義第六章、時(shí)間同步技術(shù)2007年8月20日內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)基本概念WSN時(shí)間同步技術(shù)背景時(shí)間同步技術(shù)的分類時(shí)間同步技術(shù)的應(yīng)用場合關(guān)鍵點(diǎn)：時(shí)鐘模型WSN時(shí)間同步技術(shù)背景集中式系統(tǒng)與分布式系統(tǒng)集中式：事件間有著明確的時(shí)間先后關(guān)系，不存在同步問題分布式：同步是必需的，只是對同步的要求程度不同無線傳感器網(wǎng)絡(luò)時(shí)間同步典型的分布式系統(tǒng)是無線傳感器網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)需要解決的問題同步精度功耗可擴(kuò)展性時(shí)間同步技術(shù)的應(yīng)用場合多傳感器數(shù)據(jù)壓縮與融合低功耗MAC協(xié)議、路由協(xié)議測距、定位（位置相關(guān)報(bào)務(wù)，

2、LBS）分布式系統(tǒng)的傳統(tǒng)要求協(xié)作傳輸、處理的要求. .時(shí)鐘模型硬件時(shí)鐘模型軟件時(shí)鐘模型軟件時(shí)鐘模型軟件虛擬時(shí)鐘一般是個(gè)分段連續(xù)、嚴(yán)格單調(diào)的函數(shù)內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)傳統(tǒng)與挑戰(zhàn)傳統(tǒng)同步方法傳感器網(wǎng)絡(luò)的挑戰(zhàn)NTP（Network Time Protocol） 體系結(jié)構(gòu)（網(wǎng)絡(luò)）NTP（Network Time Protocol）體系結(jié)構(gòu)（單機(jī)）GPS（Global Position System） 從根本上解決了人類在地球上的導(dǎo)航與定位問題。每顆衛(wèi)星上配備有高精度的銣、銫原子鐘，并不斷發(fā)射其時(shí)間信息地面接收裝置同時(shí)接收4顆衛(wèi)星的時(shí)間信息，采用偽距測量定位方法可計(jì)算

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

4、ission time & Reception time1020ms確定，依賴報(bào)文長度和發(fā)送速率。Propagation time1s（距離300米）確定，依賴收發(fā)方物理距離和傳播媒質(zhì)特性。Interrupt waiting time在大多數(shù)情況下5s，在重負(fù)載下，可達(dá)30s不確定，依賴處理器類型和處理器負(fù)載。Encoding time & Decoding time100200s，2s的抖動(dòng)確定，依賴射頻芯片的種類和設(shè)置。Byte alignment time0400s確定，依賴發(fā)送速率和收發(fā)字節(jié)偏移。低功耗、低成本和小體積軟硬件都要受到該限制存儲(chǔ)與計(jì)算能力均比較小加劇了電能供應(yīng)的緊張（電池

5、體積）網(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)用需求內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)典型時(shí)間同步協(xié)議NTP（Network Time Protocol）DMTS （Delay Measurement Time Synchronization） RBS （Reference Broadcast Synchronization） TPSN （Timing-sync Protocol for Sensor Networks） HR

6、TS （Hierarchy Referencing Time Synchronization Protocol） FTSP （Flooding Time Synchronization Protocol） GCS （Global Clock Synchronization） 接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） RBS （Reference Broadcast Synchronizat

7、ion） 接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0單跳RBS用最小二乘法估計(jì)clock skew提高同步精度多跳RBS時(shí)間路由技術(shù)：基于最短路徑查找TPSN（Timing-sync Protocol for Sensor Networks） 否定：DMTSRBS否定之否定：RBSTPSNTPSN：雙報(bào)文交換的發(fā)送者接收者同步節(jié)點(diǎn)A節(jié)點(diǎn)BT1T4T2T3RequestReply同步點(diǎn)TPSN（Timing-sync Protocol for Sensor Networks） 對同步誤差的分析很重要，是一種基本的分析方法理論分析和實(shí)驗(yàn)證明：TPSN同步誤差是RBS的一半結(jié)合對clock

8、skew的估計(jì)，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Networks） 多跳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ì)上是對同步，因此全網(wǎng)同步的同步能耗高由DMTS發(fā)現(xiàn)，廣播能降低全網(wǎng)同步能耗結(jié)合廣播和節(jié)點(diǎn)間的雙向報(bào)文交換同步HRTS協(xié)議 BS n

9、1 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é)點(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 Protoco

10、l） 同步精度高工程實(shí)用性強(qiáng)強(qiáng)調(diào)實(shí)現(xiàn)細(xì)節(jié)MAC層時(shí)間戳技術(shù)和平臺(tái)直接相關(guān)，書中給出了在Mica2平臺(tái)下的實(shí)現(xiàn)基本同步原理發(fā)送者-接收者同步單個(gè)報(bào)文中包括多個(gè)時(shí)間戳（在報(bào)文的不同位置）根據(jù)單個(gè)報(bào)文中的多個(gè)時(shí)間戳，可對中斷等待時(shí)間進(jìn)行補(bǔ)償對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í)間校正

11、階段：根據(jù)節(jié)點(diǎn)在游走環(huán)的位置和游走時(shí)間對節(jié)點(diǎn)時(shí)間進(jìn)行校正理論假設(shè)：每段游走的時(shí)間花費(fèi)相同GCS：聚類分層模式單純的節(jié)點(diǎn)遍歷方式導(dǎo)致遍歷環(huán)過長，同步功耗大通過分簇協(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ò)散模式越簡單的方法往往是越有效的同步過程：對接收到的時(shí)間進(jìn)行平均操作，并對自己的時(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)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)新型同步機(jī)制基于報(bào)文交換的同步機(jī)制面臨著挑戰(zhàn)同步精度問題可擴(kuò)展性問題新型同步

12、機(jī)制螢火蟲同步協(xié)作同步兩個(gè)概念同時(shí)性與同步性螢火蟲同步1935年，Science1975年, Peskin的RC模型1989年，M&S模型（無延遲）1998年，Ernst（有延遲）結(jié)論2005年，真實(shí)地實(shí)現(xià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)的同步收斂性沒有證

13、明多跳網(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ù)對耦合延遲、耦合強(qiáng)度、耦合性質(zhì)、初始相位、網(wǎng)絡(luò)拓?fù)涞纫蛩睾苊舾?。雖然在例如兩個(gè)振蕩器的同步收

14、斂性研究上取得了一定的進(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ì)受到MAC延遲、協(xié)議處理與軟件實(shí)現(xiàn)等的影響。由于對任何同步信號(hào)的處理方式均

15、相同，與同步信號(hào)的來源無關(guān)，因此可擴(kuò)展性以及適應(yīng)網(wǎng)絡(luò)動(dòng)態(tài)變化的能力很強(qiáng)。機(jī)制非常簡單，不需要對其它節(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ù) 內(nèi)容提要基本概念傳統(tǒng)與挑戰(zhàn)典型時(shí)間同步協(xié)議新型同步機(jī)制總結(jié)總結(jié) 在無線傳感器網(wǎng)絡(luò)中，時(shí)間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗、可擴(kuò)展性和健壯性需求經(jīng)典的時(shí)間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時(shí)鐘飄移補(bǔ)償、MAC層時(shí)

16、間戳技術(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-grained time

17、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, Los Angeles, 2

18、003, 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, Delay measurement time synchronization for wireless sensor networks, Intel Research. Berkeley Lab, 2003.19 Dai H., Han R. TSy