傳感網(wǎng)原理及應(yīng)用—第5講(時間同步)

1、Institute of Software,Chinese Academy of Sciences朱紅松朱紅松中國科學(xué)院軟件研究所中國科學(xué)院軟件研究所Institute of Software,Chinese Academy of Sciencesz 同步與時間同步概念同步與時間同步概念z 經(jīng)典（網(wǎng)絡(luò)）時間同步方法經(jīng)典（網(wǎng)絡(luò)）時間同步方法z 傳感器網(wǎng)絡(luò)時間同步算法與協(xié)議傳感器網(wǎng)絡(luò)時間同步算法與協(xié)議z 傳感網(wǎng)時間同步研究趨勢和總結(jié)傳感網(wǎng)時間同步研究趨勢和總結(jié)同步與時間同步概念同步與時間同步概念I(lǐng)nstitute of Software,Chinese Academy of Sciencesz協(xié)調(diào)

2、自然走路協(xié)調(diào)自然走路z螢火蟲同步閃動螢火蟲同步閃動z蟬齊聲鳴叫蟬齊聲鳴叫z鼓掌的整齊劃一鼓掌的整齊劃一z鐘擺的步調(diào)一致地擺動鐘擺的步調(diào)一致地擺動想象一下，一棵想象一下，一棵10米至米至12米高的樹，每一片樹葉上都有一個米高的樹，每一片樹葉上都有一個螢火蟲，所有的螢火蟲大約都以每螢火蟲，所有的螢火蟲大約都以每2秒秒3次的頻率同步閃光，次的頻率同步閃光，這棵樹在兩次閃光之間漆黑一片。這棵樹在兩次閃光之間漆黑一片。 想象一下，在想象一下，在160米的河米的河岸兩旁是不間斷的芒果樹，每一片樹葉上的螢火蟲，以及樹岸兩旁是不間斷的芒果樹，每一片樹葉上的螢火蟲，以及樹列兩端之間所有樹上的螢火蟲完全一致同步閃

3、光。如果一個列兩端之間所有樹上的螢火蟲完全一致同步閃光。如果一個人有足夠豐富的想象力的話，那么他就會對這一驚人奇觀產(chǎn)人有足夠豐富的想象力的話，那么他就會對這一驚人奇觀產(chǎn)生某種想法。生某種想法?！睎|南亞1935年，Science雜志Institute of Software,Chinese Academy of Sciencesz步調(diào)一致步調(diào)一致v1665, letter of Huygens to his father, Sympathy of two clocks. Mutual synchronization.vSharing the common time, Occurring in t

4、he same timev局部空間中對象之間的相對同步z“絕對絕對”時間統(tǒng)一時間統(tǒng)一v建立統(tǒng)一的（“絕對”）時間基準(zhǔn)，標(biāo)記狀態(tài)變化先后順序v便于人們描述、理解、研究，乃至控制客觀的物理世界v“絕對” 時間基準(zhǔn)，建立全局的時序邏輯關(guān)系Institute of Software,Chinese Academy of Sciencesz能夠產(chǎn)生更強(qiáng)烈的效果（共振）能夠產(chǎn)生更強(qiáng)烈的效果（共振）z能夠給人以舒暢的感覺能夠給人以舒暢的感覺z能夠傳遞信息（能量）能夠傳遞信息（能量）z能夠提高資源的利用率能夠提高資源的利用率z保證邏輯的正確性和可預(yù)見性（避免因果倒置）保證邏輯的正確性和可預(yù)見性（避免因果倒置）

5、觀察同步觀察同步=追求同步追求同步Institute of Software,Chinese Academy of Sciencesz時間的表示時間的表示v年、月、日、時、分、秒、毫秒、微秒、納秒、皮秒、飛秒、渺秒（10-18，中性介子的壽命）z計時裝置計時裝置v具有周期物理特性的部件，振蕩器（太陽、月亮、鐘擺、晶振）z計時參數(shù)計時參數(shù)v周期（秒、毫秒、微秒、納秒，離散）v相位（連續(xù)，更精準(zhǔn)）Institute of Software,Chinese Academy of Sciencesz銫原子鐘銫原子鐘v頻率準(zhǔn)確度高，系統(tǒng)復(fù)雜，壽命短，成本高，一級時頻標(biāo)準(zhǔn)z氫原子鐘氫原子鐘v長短期穩(wěn)定性好

6、，壽命長，頻率準(zhǔn)確度不如銫鐘，體積大、成本高，二級時頻標(biāo)準(zhǔn)；z銣原子鐘銣原子鐘v性能比晶體鐘好得多，頻率沒有漂移，二級時頻標(biāo)準(zhǔn)z石英（晶體）鐘石英（晶體）鐘v小巧，便宜，短期穩(wěn)定性好，但漂移大，作為三級時頻標(biāo)準(zhǔn)z其他：全光學(xué)原子鐘其他：全光學(xué)原子鐘Institute of Software,Chinese Academy of Sciencesz世界時（世界時（UT）v以格林維治天文臺時間為參考點(diǎn)的、根據(jù)地球自轉(zhuǎn)周期確定時間尺度的時系；z國際原子時（國際原子時（TAI）v一種以銫原子秒為時間尺度、以1958年1月1日0時0分0秒為時間起點(diǎn)；z協(xié)調(diào)世界時（協(xié)調(diào)世界時（UTC）v一種以銫原子秒為時

7、間尺度、采用閏秒校正方法使其時刻與UT時刻相接近的時系；zGPS時時v以UTC/USNO為參考基準(zhǔn)而建立、以1980年1月5日為時間起點(diǎn)的、不做閏秒連續(xù)計數(shù)的時系，它和國際原子時相似，與UTC時間相差一個確定的整數(shù)秒；Institute of Software,Chinese Academy of Sciencesz絕對時間、本地時間、本地測量時間絕對時間、本地時間、本地測量時間z物理（硬件、振蕩器）時間模型物理（硬件、振蕩器）時間模型vt = a*c(t)+b+wFc(t)是當(dāng)真實(shí)時間為 t 時的測量對象本地（絕對）時間Fb是時鐘偏移（offset），邏輯偏差，原則上可完全消除Fa稱為時鐘漂

8、移（skew），出廠確定，隨時間、環(huán)境(溫度)變化Fw為頻率抖動（jitter），正態(tài)分布的隨機(jī)量，會隨時間、環(huán)境變化z本地時間本地時間h(t)與本地測量時間與本地測量時間c(t)F節(jié)點(diǎn)維護(hù)一個基于時鐘脈沖計數(shù)器的本地時鐘h(t)；F節(jié)點(diǎn)本地（絕對）時鐘c(t)是根據(jù)h(t)經(jīng)過線性變換得到的時間：c(t)=t0+h(t)-h(t0)；t0為從外部獲得的絕對時間基準(zhǔn)。Institute of Software,Chinese Academy of Sciencesz層次型同步模型層次型同步模型v頂層（0級）通過標(biāo)準(zhǔn)時鐘源和相互校準(zhǔn)來維護(hù)絕對時間v下層對象通過上層獲取時間基準(zhǔn)z特點(diǎn)特點(diǎn)v每升高一

9、個層次，誤差會累積，通過相關(guān)濾波優(yōu)化0級級1級級3級級K級級K+2級級Institute of Software,Chinese Academy of Sciencest = a*c(t)+b+wz設(shè)計對時協(xié)設(shè)計對時協(xié)議議，消除偏移，消除偏移bv關(guān)鍵是要估計消息傳輸路徑上的時間開銷，否則b的計算是不準(zhǔn)確的z估計估計時時間基準(zhǔn)之間的漂間基準(zhǔn)之間的漂移移a，拉長同步時間，拉長同步時間z估計估計時間隨機(jī)抖動特征，減小時間隨機(jī)抖動特征，減小wz優(yōu)化對時協(xié)議，減小逐級同步造優(yōu)化對時協(xié)議，減小逐級同步造成的誤差累成的誤差累計計Institute of Software,Chinese Academy of

10、 Sciencesz通信與網(wǎng)絡(luò)層需求通信與網(wǎng)絡(luò)層需求v物理信道的調(diào)度，Wifi的PCF模式、Zigbee長幀模式v鏈路訪問的回退控制v協(xié)作傳輸（MIMO，網(wǎng)絡(luò)編碼）z應(yīng)用層需求應(yīng)用層需求v節(jié)點(diǎn)間的信號同步采樣的任務(wù)調(diào)度和任務(wù)協(xié)同v確定事件發(fā)生的先后順序，用于與時序相關(guān)的數(shù)據(jù)處理v測量距離，信號（聲波、電磁波）飛行的時間v低功耗控制，同時喚醒、同時睡眠v抗重放攻擊的安全認(rèn)證等Institute of Software,Chinese Academy of Sciencesz 同步與時間同步概念同步與時間同步概念z 經(jīng)典（網(wǎng)絡(luò)）時間同步方法經(jīng)典（網(wǎng)絡(luò)）時間同步方法z 傳感器網(wǎng)絡(luò)時間同步算法與協(xié)議傳

11、感器網(wǎng)絡(luò)時間同步算法與協(xié)議z 傳感網(wǎng)時間同步研究趨勢和總結(jié)傳感網(wǎng)時間同步研究趨勢和總結(jié)經(jīng)典（網(wǎng)絡(luò)）時間同步方法經(jīng)典（網(wǎng)絡(luò)）時間同步方法Institute of Software,Chinese Academy of ScienceszGPS同步方法同步方法zNTP同步算法與協(xié)議同步算法與協(xié)議Institute of Software,Chinese Academy of Sciencesz(x1,y1,z1,v1,t1)(x2,y2,z2,v2,t2)(x3,y3,z3,v3,t3)(x4,y4,z4,v4,t4)(x,y,z,v,t)Institute of Software,Chinese

12、 Academy of Sciencesz精度：精度：100nsz差分校正差分校正v使用固定站（位置已知）測量得到的誤差修正流動站誤差v環(huán)境相近，誤差可抵消v條件：與基站靠近(x1,y1,z1,v1,t1)(x2,y2,z2,v2,t2)(x3,y3,z3,v3,t3)(x4,y4,z4,v4,t4)(x,y,z,v,t)(x0,y0,z0,v0,t0)Institute of Software,Chinese Academy of Sciencesz優(yōu)點(diǎn)優(yōu)點(diǎn)v直接與1級時鐘源同步，沒有所謂的累積誤差，精度高z缺點(diǎn)缺點(diǎn)vGPS定時準(zhǔn)確度取決于信號發(fā)射端、信號在傳輸過程中和接收端所引入的誤差：F

13、信號發(fā)射端：衛(wèi)星鐘誤差、衛(wèi)星星歷（位置）誤差； F信號傳輸過程：電離層誤差、對流層誤差、遮擋、多路徑、多普勒效應(yīng)； F接收端：接收機(jī)時延、接收機(jī)噪聲。 v信號穿透能力差，室內(nèi)無法使用v模塊成本較高v受美國人的制約Institute of Software,Chinese Academy of Sciencesz美國美國Delaware大學(xué)的大學(xué)的Mills教授發(fā)起教授發(fā)起z設(shè)計目的設(shè)計目的v在Internet上計算機(jī)的時間同步為統(tǒng)一的標(biāo)準(zhǔn)時間UTC；zNTP4.0v加強(qiáng)了安全特性v在5分鐘之內(nèi)偏移可降至1毫秒一下v精度在百微秒左右； z服務(wù)模型服務(wù)模型vC/S 時間服務(wù)器Institute o

14、f Software,Chinese Academy of SciencesnNTP協(xié)議的可靠性協(xié)議的可靠性依賴于時間服務(wù)器依賴于時間服務(wù)器的冗余性和獲取時的冗余性和獲取時間的多路徑特性。間的多路徑特性。Institute of Software,Chinese Academy of Sciencesz多個樹分層管理結(jié)構(gòu)多個樹分層管理結(jié)構(gòu) (節(jié)點(diǎn)分為時鐘源和客戶節(jié)點(diǎn)分為時鐘源和客戶)v第0層為官方時鐘所保留 ；v第一層為一級時鐘源一級時鐘源層，沒有客戶，只有主鐘源；（頂級服務(wù)器）通過廣播、衛(wèi)星等方式與UTC同步；v第二層及以下層除層數(shù)不同、時間質(zhì)量不一樣外，沒有本質(zhì)上的區(qū)別，第N層上時鐘源的時

15、間來自第N-1層或第N層，并向第N層上的時鐘源和第N+1層上的客戶提供校時服務(wù)。二二級服務(wù)器級服務(wù)器是處于第2層到第n層；v通常n不超過15；Institute of Software,Chinese Academy of Sciencesz閉環(huán)控制系統(tǒng)：類型閉環(huán)控制系統(tǒng)：類型II的鎖相環(huán)路的鎖相環(huán)路v往返時間()、離差()、偏移()的估計、聚類、選擇、組合Institute of Software,Chinese Academy of Sciences偏差偏差()和往返時間和往返時間()值只與值只與(T2 - T1)、(T3 - T4) 有關(guān)，有關(guān)，與時間服務(wù)器處理請求消息所需的時間（與時間

16、服務(wù)器處理請求消息所需的時間（T3-T2）無關(guān)）無關(guān)21432143()()2()()2TTTTTTTT122114322TTTTInstitute of Software,Chinese Academy of Sciencesz 同步與時間同步概念同步與時間同步概念z 經(jīng)典（網(wǎng)絡(luò)）時間同步方法經(jīng)典（網(wǎng)絡(luò)）時間同步方法z 傳感器網(wǎng)絡(luò)時間同步算法與協(xié)議傳感器網(wǎng)絡(luò)時間同步算法與協(xié)議z 傳感網(wǎng)時間同步研究趨勢和總結(jié)傳感網(wǎng)時間同步研究趨勢和總結(jié)傳感器網(wǎng)絡(luò)時間同步算法和協(xié)議傳感器網(wǎng)絡(luò)時間同步算法和協(xié)議Institute of Software,Chinese Academy of ScienceszWS

17、N時間同步概述時間同步概述z層次化時間同步方法層次化時間同步方法vDMTS，RBS，TPSN，HTRS，TINY/MINI-SYNCz全局周期時鐘源的時間同步方法全局周期時鐘源的時間同步方法vAC交流電信號同步z全分布式同步方法（略）全分布式同步方法（略）v基于振蕩器模型的同步方法Institute of Software,Chinese Academy of Sciencesz時間同步是時間同步是WSN的基本功能的基本功能vTDMA MAC協(xié)議調(diào)度v網(wǎng)絡(luò)節(jié)點(diǎn)自定位和移動目標(biāo)的跟蹤F波束陣列確定聲源位置F確定目標(biāo)方向和速度v休眠和喚醒調(diào)度v多傳感器的數(shù)據(jù)融合F時間序列分析和相關(guān)計算v事件發(fā)生時

18、間標(biāo)定（邏輯關(guān)系）Institute of Software,Chinese Academy of Sciences要求要求z擴(kuò)展性擴(kuò)展性z穩(wěn)定性（拓?fù)渥兓┓€(wěn)定性（拓?fù)渥兓?z魯棒性（節(jié)點(diǎn)失效）魯棒性（節(jié)點(diǎn)失效） z收斂性收斂性 z低能耗低能耗約束約束z處理資源有限處理資源有限z“額外部件額外部件” 體積要小體積要小z“額外部件額外部件” 能量有限能量有限Institute of Software,Chinese Academy of SciencesGPS系統(tǒng)的限制系統(tǒng)的限制z場合場合v室外z價格和體積價格和體積v300元，半個鼠標(biāo)z能量能量v90mA持續(xù)v可以休眠，但啟動一次的時間要幾

19、分鐘（包括初始化和搜星）z室外的錨節(jié)點(diǎn)可以采用室外的錨節(jié)點(diǎn)可以采用GPS做絕對坐標(biāo)定位做絕對坐標(biāo)定位NTPz協(xié)議使用條件協(xié)議使用條件v有線，誤碼率低v網(wǎng)絡(luò)穩(wěn)定，手工配置；z協(xié)議追求目標(biāo)協(xié)議追求目標(biāo)-高精度，通信高精度，通信和計算開銷大；和計算開銷大；z網(wǎng)關(guān)可以作為網(wǎng)關(guān)可以作為NTP終端與終端與UTC同步同步Institute of Software,Chinese Academy of Sciencesz精度精度v最大誤差 ，常規(guī)誤差z擴(kuò)展性擴(kuò)展性v誤差是否隨通信跳數(shù)累計，累計將限制網(wǎng)絡(luò)規(guī)模z同步周期同步周期 v盡量長，減小同步協(xié)議能量消耗z能量效率能量效率 v協(xié)議過程是否簡單有效Instit

20、ute of Software,Chinese Academy of Sciences一跳內(nèi)一跳內(nèi)同步同步全網(wǎng)絡(luò)全網(wǎng)絡(luò)同步同步點(diǎn)到點(diǎn)點(diǎn)到點(diǎn)同步同步點(diǎn)到多點(diǎn)點(diǎn)到多點(diǎn)廣播同步廣播同步核心：消除關(guān)鍵路徑核心：消除關(guān)鍵路徑引入的誤差引入的誤差構(gòu)建層次構(gòu)建層次逐跳同步逐跳同步各自同步各自同步協(xié)同優(yōu)化協(xié)同優(yōu)化核心：減小誤差（方核心：減小誤差（方差）累計差）累計Institute of Software,Chinese Academy of Sciencesz關(guān)鍵路徑分析是指節(jié)點(diǎn)與節(jié)點(diǎn)之間進(jìn)行同步報文交換過程關(guān)鍵路徑分析是指節(jié)點(diǎn)與節(jié)點(diǎn)之間進(jìn)行同步報文交換過程中，在各個環(huán)節(jié)的時間延遲（消耗）中，在各個環(huán)節(jié)的時

21、間延遲（消耗）發(fā)送者發(fā)送者接收者接收者協(xié)議處協(xié)議處理理+OS信道信道訪問訪問編碼編碼延遲延遲傳播傳播時延時延解碼解碼延遲延遲中斷中斷響應(yīng)響應(yīng)協(xié)議處協(xié)議處理理+OS不同協(xié)議打時標(biāo)的時機(jī)不同不同協(xié)議打時標(biāo)的時機(jī)不同時間同步算法實(shí)現(xiàn)的層次時間同步算法實(shí)現(xiàn)的層次時間時間流逝流逝發(fā)送發(fā)送延遲延遲接收接收延遲延遲NIC（基帶（基帶+射頻）射頻）NIC（基帶（基帶+射頻）射頻）t = a*c(t)+b+wInstitute of Software,Chinese Academy of Sciences延遲類型延遲類型典型值典型值特性特性協(xié)議處理協(xié)議處理+OS調(diào)度調(diào)度0100ms不確定，依賴處理器能力、負(fù)載，

22、以不確定，依賴處理器能力、負(fù)載，以及操作系統(tǒng)效率及操作系統(tǒng)效率信道訪問時間信道訪問時間10500ms不確定，依賴信道負(fù)載比率不確定，依賴信道負(fù)載比率發(fā)送接收時間發(fā)送接收時間1020ms確定，報文長度和射頻調(diào)制速率決定確定，報文長度和射頻調(diào)制速率決定傳播時間傳播時間1us(300米內(nèi)）米內(nèi)）基本確定，收發(fā)距離和傳播介質(zhì)特性基本確定，收發(fā)距離和傳播介質(zhì)特性（不均勻可能存在問題）（不均勻可能存在問題）中斷響應(yīng)時間中斷響應(yīng)時間一般小于一般小于5us，中斷頻繁約中斷頻繁約30us不確定，與任務(wù)負(fù)載、實(shí)現(xiàn)方法有關(guān)不確定，與任務(wù)負(fù)載、實(shí)現(xiàn)方法有關(guān)編解碼時間編解碼時間100200us,2us的抖動的抖動確定，

23、射頻芯片決定確定，射頻芯片決定字節(jié)對齊字節(jié)對齊0400uS確定，依賴收發(fā)速率和收發(fā)字節(jié)偏移確定，依賴收發(fā)速率和收發(fā)字節(jié)偏移Institute of Software,Chinese Academy of Sciencesz發(fā)送者僅在檢測到信道空閑后才加時間戳：發(fā)送和訪問發(fā)送者僅在檢測到信道空閑后才加時間戳：發(fā)送和訪問z提高精度：發(fā)送前導(dǎo)碼和同步碼的時間提高精度：發(fā)送前導(dǎo)碼和同步碼的時間 nz接收節(jié)點(diǎn)：調(diào)整其時鐘為：接收節(jié)點(diǎn)：調(diào)整其時鐘為：t0+n+(t2-t1)假設(shè)：發(fā)送者有精準(zhǔn)時假設(shè)：發(fā)送者有精準(zhǔn)時鐘，接收者向鐘，接收者向發(fā)送者同步發(fā)送者同步Institute of Software,Chi

24、nese Academy of Sciencesz優(yōu)點(diǎn)優(yōu)點(diǎn)v簡單開銷?。簡蝹€廣播時間分組同步廣播域內(nèi)所有節(jié)點(diǎn)z缺點(diǎn)缺點(diǎn)v精度不高：沒有考慮傳播延遲、沒有對時鐘漂移補(bǔ)償v同步方差隨網(wǎng)絡(luò)規(guī)模（跳數(shù)）增加而增加 實(shí)實(shí)現(xiàn)復(fù)雜度、能量高效與同步精度之現(xiàn)復(fù)雜度、能量高效與同步精度之間的折間的折中中Institute of Software,Chinese Academy of Sciencesz目標(biāo)目標(biāo)v實(shí)現(xiàn)接收者之間的同步，沒有絕對時間，只有相對同步z核心思想核心思想v通過在接收者之間交換信息，消除發(fā)送者在發(fā)送Beacon過程引入的誤差I(lǐng)nstitute of Software,Chinese Acad

25、emy of Sciencesz操作過程操作過程vR：發(fā)送者vi,j：接收者vi與j之間的時間差=傳播差值+接收處理差值v相當(dāng)于DMTS中，只測量（t2-t1）發(fā)送者發(fā)送者接收者接收者協(xié)議處協(xié)議處理理+OS信道信道訪問訪問編編碼碼延遲延遲傳播傳播時延時延解碼解碼延遲延遲中斷中斷響應(yīng)響應(yīng)協(xié)議處協(xié)議處理理+OS發(fā)送發(fā)送延遲延遲接收接收延遲延遲NIC（基帶（基帶+射頻）射頻）Institute of Software,Chinese Academy of Sciences背景：發(fā)生在節(jié)點(diǎn)背景：發(fā)生在節(jié)點(diǎn)1和節(jié)點(diǎn)和節(jié)點(diǎn)7附近的兩個事附近的兩個事件，分別記為件，分別記為E1和和E7問題：判斷問題：判斷E

26、1和和E7兩個事件的時間差值兩個事件的時間差值v假設(shè)節(jié)點(diǎn)A和節(jié)點(diǎn)B分別在Pa和Pb時間點(diǎn)發(fā)送beacon分組v節(jié)點(diǎn)1在收到節(jié)點(diǎn)A發(fā)送的分組后兩秒觀察到事件E1v節(jié)點(diǎn)7在觀察到事件E7后4秒才收到節(jié)點(diǎn)B發(fā)送的beacon分組。v節(jié)點(diǎn)4知道節(jié)點(diǎn)A發(fā)送分組比節(jié)點(diǎn)B晚10秒，PaPb10，由此推出：E1E716Institute of Software,Chinese Academy of Sciencesz優(yōu)點(diǎn)優(yōu)點(diǎn)v消除發(fā)送過程誤差，提高了精度，4MHz的Mica，29.13s v協(xié)議相對簡單z缺點(diǎn)缺點(diǎn)v僅作同步，不做對時，沒有絕對時間F可用于通信調(diào)度，確定事件發(fā)生的全局時間需要v三個節(jié)點(diǎn)一次同步需

27、要3個發(fā)送消息和4個接收消息，鄰居節(jié)點(diǎn)很多時，能耗很大。v瞬間同步；不適用于長距離或長時間同步Institute of Software,Chinese Academy of Sciencesz目標(biāo)：目標(biāo)：v提供全網(wǎng)范圍內(nèi)時間同步；z假設(shè)假設(shè)v每個傳感器節(jié)點(diǎn)都有唯一的標(biāo)識號ID；v節(jié)點(diǎn)間的無線通信鏈路是雙向的v根節(jié)點(diǎn)：與外界通信獲取外界時間的節(jié)點(diǎn)稱為根節(jié)點(diǎn)；z協(xié)議過程協(xié)議過程v層次發(fā)現(xiàn)階段/同步階段Institute of Software,Chinese Academy of Sciencesz目標(biāo)是形成一個層次型拓?fù)浣Y(jié)構(gòu)；目標(biāo)是形成一個層次型拓?fù)浣Y(jié)構(gòu)；z通過洪泛方式在網(wǎng)絡(luò)中廣播通過洪泛方式

28、在網(wǎng)絡(luò)中廣播“級級別發(fā)現(xiàn)別發(fā)現(xiàn)”分組，分組包含發(fā)送節(jié)分組，分組包含發(fā)送節(jié)點(diǎn)的點(diǎn)的ID和級別號；和級別號；z根節(jié)點(diǎn)發(fā)起，級別號為根節(jié)點(diǎn)發(fā)起，級別號為0；z每跳級別號加每跳級別號加1；z節(jié)點(diǎn)級別號確定以后，忽略其他節(jié)點(diǎn)級別號確定以后，忽略其他的分組；的分組；Institute of Software,Chinese Academy of Sciencesz根節(jié)點(diǎn)廣播時間同步分組根節(jié)點(diǎn)廣播時間同步分組z1級的節(jié)點(diǎn)隨機(jī)回退一段時間，通過與級的節(jié)點(diǎn)隨機(jī)回退一段時間，通過與根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)vNTP類似的算法，更準(zhǔn)確估計處理時間v假設(shè)傳輸過程相對確定，可準(zhǔn)確估計z2級的節(jié)

29、點(diǎn)偵聽到級的節(jié)點(diǎn)偵聽到1級節(jié)點(diǎn)同步消息，級節(jié)點(diǎn)同步消息，等待確定時間，并隨機(jī)回退一段時間，等待確定時間，并隨機(jī)回退一段時間，同步到同步到2級節(jié)點(diǎn)級節(jié)點(diǎn)v等待的目的是保證第2級節(jié)點(diǎn)在第1級節(jié)點(diǎn)時間同步完成后才啟動消息交換。z每個節(jié)點(diǎn)與上一級節(jié)點(diǎn)同步，最終所每個節(jié)點(diǎn)與上一級節(jié)點(diǎn)同步，最終所有節(jié)點(diǎn)都同步到根節(jié)點(diǎn)。有節(jié)點(diǎn)都同步到根節(jié)點(diǎn)。 23412TTTTd 23412TTTT消息交換過程消息交換過程Institute of Software,Chinese Academy of Sciencesz優(yōu)點(diǎn)優(yōu)點(diǎn)v不需要測量發(fā)送接收節(jié)點(diǎn)之間對稱時間部分，直接通過算法將中間部分消掉，從而大大降低了誤差。z缺點(diǎn)

30、缺點(diǎn)v會隨跳數(shù)增加而累積（層次型算法都有的問題）v每個節(jié)點(diǎn)需要收發(fā)兩個包實(shí)現(xiàn)同步，能耗O(n)，比較高思思想與想與NTP相似，相似，NTP中客戶端與服務(wù)器之間路徑很長，中中客戶端與服務(wù)器之間路徑很長，中間設(shè)備多，傳播路徑上的時間時變，并不容易估計間設(shè)備多，傳播路徑上的時間時變，并不容易估計發(fā)送者發(fā)送者接收者接收者協(xié)議處協(xié)議處理理+OS信道信道訪問訪問編編碼碼延遲延遲傳播傳播時延時延解碼解碼延遲延遲中斷中斷響應(yīng)響應(yīng)協(xié)議處協(xié)議處理理+OS發(fā)送發(fā)送延遲延遲接收接收延遲延遲NIC（基帶（基帶+射頻）射頻）NIC（基帶（基帶+射頻）射頻）NTP交換機(jī)交換機(jī)路由器路由器交換機(jī)交換機(jī)路由器路由器服務(wù)器服務(wù)器

31、TPSNInstitute of Software,Chinese Academy of Sciencesz協(xié)議過程協(xié)議過程v參考基站廣播同步分組，i,j記錄Li(t2)和Lj(t2)vi節(jié)點(diǎn)在t3返回數(shù)據(jù)包(Li(t2), Li(t3)，參考點(diǎn)記錄LR(t4)v參考基站計算偏差OR,i，廣播給所有鄰居(OR,i, Li(t2)vi接收到OR,i，其它鄰居（如j）通過下式計算OR,jOR,j = Lj(t2) LR(t2) = Lj(t2) (Li(t2) OR,i )v假設(shè)t2=t2LR(t1)表示表示t1時時刻刻R的本地時間，的本地時間，其他類推其他類推Institute of Softw

32、are,Chinese Academy of Sciencesz優(yōu)點(diǎn)優(yōu)點(diǎn)v3包完成一個廣播域中的同步，大大減少往返數(shù)據(jù)包，能量效率高z缺點(diǎn)缺點(diǎn)v假設(shè)t2=t2，略微增大時間誤差的，但只要時標(biāo)打得足夠靠近下層，誤差是微秒級Institute of Software,Chinese Academy of Sciencesz時鐘同步算法時鐘同步算法 z節(jié)點(diǎn)節(jié)點(diǎn)i時間可以表示：時間可以表示：vai為節(jié)點(diǎn)i的時鐘頻偏，bi為節(jié)點(diǎn)i的時鐘相偏。 z節(jié)點(diǎn)節(jié)點(diǎn)1和節(jié)點(diǎn)和節(jié)點(diǎn)2的時間的時間t1和和t2符合線性關(guān)系：符合線性關(guān)系： va12、b12:相對時鐘頻偏和相對時鐘相偏技術(shù)v如果兩個時鐘精確同步：相對時鐘頻

33、偏等于1，而相對時鐘相偏等于零 ( )iiit ta tb112 212( )( )t ta t tbInstitute of Software,Chinese Academy of Sciencesz三三個時標(biāo)（個時標(biāo)（to, tb, tr）形成一個數(shù)據(jù)點(diǎn)，兩個約）形成一個數(shù)據(jù)點(diǎn)，兩個約束：束：z目標(biāo)目標(biāo)v估計參數(shù)a12和b1201212( )( )bt ta t tb1212)(bttatbrInstitute of Software,Chinese Academy of Sciencesz傳統(tǒng)方法傳統(tǒng)方法v大量采集數(shù)據(jù)點(diǎn)、擬合處理；v缺點(diǎn)：通信量、存儲量和計算量；ztiny-sync算法

34、算法v在每次獲得新數(shù)據(jù)點(diǎn)時，首先與以前數(shù)據(jù)點(diǎn)比較，如果新數(shù)據(jù)點(diǎn)計算出的誤差大于以前數(shù)據(jù)點(diǎn)計算的誤差，則拋棄；否則，采用新數(shù)據(jù)點(diǎn)而拋棄舊的數(shù)據(jù)點(diǎn)。v結(jié)果：存儲34個數(shù)據(jù)點(diǎn)，可實(shí)現(xiàn)一定精度時間同步；Institute of Software,Chinese Academy of Sciencesz新數(shù)據(jù)點(diǎn)更新評估條件：新數(shù)據(jù)點(diǎn)更新評估條件：v對于新的數(shù)據(jù)點(diǎn)Aj（如A3），如果對于任何滿足關(guān)系1ijk的整數(shù)i和k都關(guān)系式 ：zTiny/mini-sync評價評價v優(yōu)點(diǎn)：輕量級算法少量消息計算上界，需要資源少；v缺點(diǎn)：假設(shè)節(jié)點(diǎn)時鐘的頻偏和相偏不變，很難保證；(,)(,)ijjkm A Bm A BIn

35、stitute of Software,Chinese Academy of ScienceszWSN時間同步概述時間同步概述z層次化時間同步方法層次化時間同步方法vDMTS，RBS，TPSN，HTRS，TINY/MINI-SYNCz全局周期時鐘源的時間同步方法全局周期時鐘源的時間同步方法vAC交流電線信號同步z全分布式同步方法（略）全分布式同步方法（略）v基于振蕩器模型的同步方法Institute of Software,Chinese Academy of Sciencesz使用家用交流電使用家用交流電220v的的50Hz正弦信號作為同步源正弦信號作為同步源v如果不過變壓器，50Hz信號是

36、沒有相位突變的，如果所有節(jié)點(diǎn)都與這個信號，就可以實(shí)現(xiàn)很好的同步效果；v最新的研究結(jié)果，通過天線耦合原理可以在動力線50米以內(nèi)接收到50Hz信號；A. Rowe, et al., Low-power clock synchronization using electromagnetic energy radiating from AC power lines, presented at the Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, Berkeley, California, 2009.Institute of Software,Chinese Academy of Sciencesz每個節(jié)點(diǎn)使用類似每個節(jié)點(diǎn)使用類似NTP的鎖相環(huán)原理完成與交的鎖相環(huán)原理完成與交流信號的同步流信號的同步z仍有三個問題需要處理仍有三個問題需要處理v確定時間起始點(diǎn)v確定鄰居節(jié)點(diǎn)之間的相位差v當(dāng)同步失敗的時候恢復(fù)機(jī)制通過時間同步協(xié)議通過時間同步協(xié)議來處理