第四章2無線傳感器網(wǎng)絡(luò)的支撐技術(shù)時(shí)間同步4學(xué)時(shí)

1、第四章第四章 無線傳感器網(wǎng)絡(luò)無線傳感器網(wǎng)絡(luò)的支撐的支撐技術(shù)技術(shù)課程目錄課程目錄4.14.1無線傳感器網(wǎng)絡(luò)定位技術(shù)無線傳感器網(wǎng)絡(luò)定位技術(shù)4.24.2無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)無線傳感器網(wǎng)絡(luò)無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合數(shù)據(jù)融合技術(shù)技術(shù)4.24.2 什么叫時(shí)間同步？什么叫時(shí)間同步？ 時(shí)間同步時(shí)間同步：使網(wǎng)絡(luò)中所有節(jié)點(diǎn)使網(wǎng)絡(luò)中所有節(jié)點(diǎn)的的時(shí)間保持一致，按照時(shí)間保持一致，按照網(wǎng)絡(luò)應(yīng)用的深度可以分為三種不同的情況網(wǎng)絡(luò)應(yīng)用的深度可以分為三種不同的情況：u第一種第一種：時(shí)序確定時(shí)序確定，判斷事件發(fā)生的先后順序，對(duì)本判斷事件發(fā)生的先后順序，對(duì)本地時(shí)間的要求比較低，只需要知道本節(jié)點(diǎn)與其余節(jié)點(diǎn)地

2、時(shí)間的要求比較低，只需要知道本節(jié)點(diǎn)與其余節(jié)點(diǎn)的相對(duì)時(shí)間即可的相對(duì)時(shí)間即可u第二種第二種：相對(duì)同步相對(duì)同步，節(jié)點(diǎn)維護(hù)自己的本地時(shí)鐘，周期，節(jié)點(diǎn)維護(hù)自己的本地時(shí)鐘，周期性地獲取其鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的時(shí)鐘偏移，實(shí)現(xiàn)本節(jié)性地獲取其鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的時(shí)鐘偏移，實(shí)現(xiàn)本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的時(shí)間同步點(diǎn)與鄰居節(jié)點(diǎn)的時(shí)間同步u第三種第三種：絕對(duì)同步絕對(duì)同步，所有節(jié)點(diǎn)的本地時(shí)間嚴(yán)格同步，所有節(jié)點(diǎn)的本地時(shí)間嚴(yán)格同步，等同于標(biāo)準(zhǔn)時(shí)間，這種情況對(duì)節(jié)點(diǎn)的要求最高，因此等同于標(biāo)準(zhǔn)時(shí)間，這種情況對(duì)節(jié)點(diǎn)的要求最高，因此實(shí)現(xiàn)也最為復(fù)雜實(shí)現(xiàn)也最為復(fù)雜 為什么要時(shí)間同步？為什么要時(shí)間同步？估計(jì)目標(biāo)的運(yùn)行速度和方向估計(jì)目標(biāo)的運(yùn)行速度和方向數(shù)據(jù)

3、融合需要時(shí)間同步數(shù)據(jù)融合需要時(shí)間同步用戶交互性需要用戶交互性需要 時(shí)間同步的參考時(shí)間來源？時(shí)間同步的參考時(shí)間來源？參考時(shí)間來源有兩種情況參考時(shí)間來源有兩種情況：u外同步外同步：標(biāo)準(zhǔn)參考時(shí)間來自于外部標(biāo)準(zhǔn)參考時(shí)間來自于外部u內(nèi)同步內(nèi)同步：參考時(shí)間來自于網(wǎng)絡(luò)內(nèi)部參考時(shí)間來自于網(wǎng)絡(luò)內(nèi)部某個(gè)節(jié)點(diǎn)的時(shí)間某個(gè)節(jié)點(diǎn)的時(shí)間1硬件時(shí)鐘模硬件時(shí)鐘模式式在硬件系統(tǒng)的時(shí)鐘計(jì)數(shù)中，計(jì)算時(shí)間的一個(gè)重要的公式是在硬件系統(tǒng)的時(shí)鐘計(jì)數(shù)中，計(jì)算時(shí)間的一個(gè)重要的公式是：式中，式中，w(t)是晶振的角頻率，是晶振的角頻率，k是依賴于晶體物理特性的常量，是依賴于晶體物理特性的常量，t是真實(shí)時(shí)間是真實(shí)時(shí)間變量，變量， c(t)是當(dāng)真實(shí)時(shí)

4、間為是當(dāng)真實(shí)時(shí)間為t時(shí)節(jié)點(diǎn)的本地時(shí)間。時(shí)節(jié)點(diǎn)的本地時(shí)間。2軟件時(shí)鐘軟件時(shí)鐘模式模式在軟件時(shí)鐘模型中，也存在一個(gè)用于記錄時(shí)鐘脈沖的計(jì)數(shù)器，軟件時(shí)鐘模型在軟件時(shí)鐘模型中，也存在一個(gè)用于記錄時(shí)鐘脈沖的計(jì)數(shù)器，軟件時(shí)鐘模型與硬件模型不同，它不直接修改本地時(shí)鐘，而是根據(jù)本地時(shí)鐘與硬件模型不同，它不直接修改本地時(shí)鐘，而是根據(jù)本地時(shí)鐘h(t)與真實(shí)時(shí)與真實(shí)時(shí)間的關(guān)系來?yè)Q算成真實(shí)時(shí)間的函數(shù)間的關(guān)系來?yè)Q算成真實(shí)時(shí)間的函數(shù)c(h(t)。c(h(t)=t0+h(t)h(t0)就是一個(gè)最簡(jiǎn)就是一個(gè)最簡(jiǎn)單的虛擬軟件時(shí)鐘的例子，實(shí)際應(yīng)用中，軟件時(shí)鐘還要考慮到時(shí)鐘漂移對(duì)時(shí)單的虛擬軟件時(shí)鐘的例子，實(shí)際應(yīng)用中，軟件時(shí)鐘還要考慮

5、到時(shí)鐘漂移對(duì)時(shí)鐘的影響，因此更加復(fù)雜。鐘的影響，因此更加復(fù)雜。 如何實(shí)現(xiàn)時(shí)間同步？如何實(shí)現(xiàn)時(shí)間同步？到目前為止，時(shí)間同步技術(shù)的研究已經(jīng)有了到目前為止，時(shí)間同步技術(shù)的研究已經(jīng)有了30年之久，最早的時(shí)間同步年之久，最早的時(shí)間同步機(jī)制是美國(guó)一所大學(xué)提出的網(wǎng)絡(luò)時(shí)間協(xié)議（機(jī)制是美國(guó)一所大學(xué)提出的網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）。）。NTP協(xié)議的時(shí)間同步協(xié)議的時(shí)間同步精度可以達(dá)到毫秒級(jí)，通過外界一個(gè)精準(zhǔn)的時(shí)間源接收機(jī)，頂層的時(shí)間服精度可以達(dá)到毫秒級(jí)，通過外界一個(gè)精準(zhǔn)的時(shí)間源接收機(jī)，頂層的時(shí)間服務(wù)器可以獲得高精度的參考時(shí)間，并向全網(wǎng)內(nèi)提供統(tǒng)一的時(shí)間服務(wù)。務(wù)器可以獲得高精度的參考時(shí)間，并向全網(wǎng)內(nèi)提供統(tǒng)一的時(shí)間服務(wù)。l時(shí)

6、間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTPNTP協(xié)議采用的是分層結(jié)構(gòu)，拓?fù)浣Y(jié)協(xié)議采用的是分層結(jié)構(gòu)，拓?fù)浣Y(jié)構(gòu)如圖所示，整個(gè)構(gòu)如圖所示，整個(gè)NTP協(xié)議分為三層結(jié)協(xié)議分為三層結(jié)構(gòu)，其中構(gòu)，其中A1、A2、A3為頂層的時(shí)間服為頂層的時(shí)間服務(wù)器，務(wù)器，B1、B2、B3為第二層時(shí)間服務(wù)為第二層時(shí)間服務(wù)器，其余均為客戶機(jī)。器，其余均為客戶機(jī)。第一層時(shí)間服務(wù)器通過第一層時(shí)間服務(wù)器通過地球觀測(cè)衛(wèi)星地球觀測(cè)衛(wèi)星或者或者位于科羅拉多的位于科羅拉多的WWV短波電臺(tái)短波電臺(tái)獲獲得標(biāo)準(zhǔn)的得標(biāo)準(zhǔn)的UTC時(shí)間，其他層的時(shí)間服務(wù)時(shí)間，其他層的時(shí)間服務(wù)器或者客戶機(jī)選擇一個(gè)或者多個(gè)上一層器或者客戶機(jī)選擇一個(gè)或者多個(gè)上一層的時(shí)間服務(wù)

7、器來同步本地時(shí)間，從而使的時(shí)間服務(wù)器來同步本地時(shí)間，從而使整個(gè)網(wǎng)絡(luò)所有服務(wù)器和客戶機(jī)時(shí)間同步。整個(gè)網(wǎng)絡(luò)所有服務(wù)器和客戶機(jī)時(shí)間同步。l時(shí)間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTP通過上層服務(wù)器的標(biāo)準(zhǔn)參考時(shí)間，服務(wù)器利用一個(gè)閉環(huán)通過上層服務(wù)器的標(biāo)準(zhǔn)參考時(shí)間，服務(wù)器利用一個(gè)閉環(huán)控制系統(tǒng)來調(diào)整自己的本地時(shí)間控制系統(tǒng)來調(diào)整自己的本地時(shí)間l時(shí)間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTPT1T2T3T4客戶端客戶端服務(wù)器服務(wù)器1221112TT234TT212)21()34(TTTT)34()12(TTTT假定假定，可計(jì)算出：，可計(jì)算出：假定客戶端時(shí)鐘比服務(wù)器時(shí)鐘快假定客戶端時(shí)鐘比服務(wù)器時(shí)鐘快l時(shí)間同步技術(shù)起

8、源時(shí)間同步技術(shù)起源NTPNTPNTP協(xié)議NTP協(xié)議層次型樹形結(jié)構(gòu)協(xié)議層次型樹形結(jié)構(gòu)UTC時(shí)間源一級(jí)時(shí)間基準(zhǔn)服務(wù)器二級(jí)時(shí)間基準(zhǔn)服務(wù)器客戶端一級(jí)時(shí)間基準(zhǔn)服務(wù)器二級(jí)時(shí)間基準(zhǔn)服務(wù)器二級(jí)時(shí)間基準(zhǔn)服務(wù)器一級(jí)時(shí)間基準(zhǔn)服務(wù)器二級(jí)時(shí)間基準(zhǔn)服務(wù)器客戶端 NTPNTP不適合于不適合于WSNWSN 體積、計(jì)算能力和存儲(chǔ)空間存在限制體積、計(jì)算能力和存儲(chǔ)空間存在限制 目目標(biāo)不同：局部最優(yōu)而非全局最優(yōu)標(biāo)不同：局部最優(yōu)而非全局最優(yōu)l時(shí)間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTPWSN同步算法與協(xié)議設(shè)計(jì)一跳一跳內(nèi)內(nèi)同步同步全網(wǎng)全網(wǎng)絡(luò)絡(luò)同步同步點(diǎn)到點(diǎn)點(diǎn)到點(diǎn)同步同步點(diǎn)到多點(diǎn)點(diǎn)到多點(diǎn)廣播同步廣播同步核心：消除關(guān)鍵路徑引入核心：消除關(guān)鍵

9、路徑引入的誤差的誤差構(gòu)建層次構(gòu)建層次逐跳同步逐跳同步各自同步各自同步協(xié)同優(yōu)化協(xié)同優(yōu)化核心：減小誤差（方差）核心：減小誤差（方差）累計(jì)累計(jì)在設(shè)計(jì)無線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議時(shí)，需要滿在設(shè)計(jì)無線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議時(shí)，需要滿足以下幾點(diǎn)要求足以下幾點(diǎn)要求： 能量有限能量有限 可擴(kuò)展可擴(kuò)展 穩(wěn)定性穩(wěn)定性l時(shí)間同步技術(shù)關(guān)鍵問題時(shí)間同步技術(shù)關(guān)鍵問題1、傳輸延遲不可預(yù)測(cè)傳輸延遲不可預(yù)測(cè)無線傳感器網(wǎng)絡(luò)中，時(shí)間同步技術(shù)的一個(gè)重要難題是報(bào)文傳無線傳感器網(wǎng)絡(luò)中，時(shí)間同步技術(shù)的一個(gè)重要難題是報(bào)文傳輸延遲的不確定，由于處理器處理能力有限、網(wǎng)絡(luò)負(fù)載不確輸延遲的不確定，由于處理器處理能力有限、網(wǎng)絡(luò)負(fù)載不確定等因素的影響

10、，延遲不能夠被精確地計(jì)算出來；另外傳輸定等因素的影響，延遲不能夠被精確地計(jì)算出來；另外傳輸延遲比要求的時(shí)間同步的精度要大得多延遲比要求的時(shí)間同步的精度要大得多。l時(shí)間同步技術(shù)關(guān)鍵問題時(shí)間同步技術(shù)關(guān)鍵問題影響時(shí)間同步的傳輸時(shí)延影響時(shí)間同步的傳輸時(shí)延發(fā)送時(shí)間發(fā)送時(shí)間：發(fā)送方用于組裝并將報(bào)文換交給發(fā)送方：發(fā)送方用于組裝并將報(bào)文換交給發(fā)送方MAC層的時(shí)層的時(shí)間。間。訪問時(shí)間訪問時(shí)間：指在發(fā)送方：指在發(fā)送方MAC層從獲得報(bào)文后到獲取無線信道發(fā)層從獲得報(bào)文后到獲取無線信道發(fā)送權(quán)的等待時(shí)間。送權(quán)的等待時(shí)間。傳送時(shí)間傳送時(shí)間：發(fā)送方發(fā)送報(bào)文的時(shí)間，即從報(bào)文的第一個(gè)字節(jié)開：發(fā)送方發(fā)送報(bào)文的時(shí)間，即從報(bào)文的第一個(gè)

11、字節(jié)開始發(fā)送到發(fā)送完最后一個(gè)字節(jié)的時(shí)間。始發(fā)送到發(fā)送完最后一個(gè)字節(jié)的時(shí)間。傳播時(shí)間傳播時(shí)間：報(bào)文從發(fā)送方以電磁波的形式傳送到接收方所花費(fèi)：報(bào)文從發(fā)送方以電磁波的形式傳送到接收方所花費(fèi)的時(shí)間的時(shí)間。接收時(shí)間接收時(shí)間：接收方接收?qǐng)?bào)文的時(shí)間。它和傳送時(shí)間完全相同，：接收方接收?qǐng)?bào)文的時(shí)間。它和傳送時(shí)間完全相同，具有確定性。具有確定性。接受時(shí)間接受時(shí)間：用于處理接收到的報(bào)文的時(shí)間：用于處理接收到的報(bào)文的時(shí)間。l時(shí)間同步技術(shù)關(guān)鍵問題時(shí)間同步技術(shù)關(guān)鍵問題2高能效高能效無線傳感器網(wǎng)絡(luò)的軟無線傳感器網(wǎng)絡(luò)的軟/硬件設(shè)施要求節(jié)點(diǎn)體積盡量小，硬件設(shè)施要求節(jié)點(diǎn)體積盡量小，盡量廉價(jià)，因此要求時(shí)間同步技術(shù)具有高能效的特點(diǎn)。

12、盡量廉價(jià)，因此要求時(shí)間同步技術(shù)具有高能效的特點(diǎn)。3可擴(kuò)展、健壯可擴(kuò)展、健壯采用逐跳的時(shí)間同步機(jī)制，因此隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，采用逐跳的時(shí)間同步機(jī)制，因此隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，時(shí)間同步技術(shù)必須保證網(wǎng)絡(luò)擴(kuò)展后同步誤差不會(huì)超過誤時(shí)間同步技術(shù)必須保證網(wǎng)絡(luò)擴(kuò)展后同步誤差不會(huì)超過誤差界限，并且能夠穩(wěn)定工作。差界限，并且能夠穩(wěn)定工作。l時(shí)間同步技術(shù)關(guān)鍵問題時(shí)間同步技術(shù)關(guān)鍵問題課程目錄課程目錄4.2.14.2.14.2.24.2.2時(shí)間同步模型時(shí)間同步模型時(shí)間同步協(xié)議時(shí)間同步協(xié)議無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)4.24.21時(shí)鐘模型時(shí)鐘模型2時(shí)間同步機(jī)制時(shí)間同步機(jī)制4.2.14.2.1時(shí)間同步

13、模型時(shí)間同步模型1時(shí)鐘模型時(shí)鐘模型傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時(shí)鐘依靠對(duì)自身傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時(shí)鐘依靠對(duì)自身晶晶振中斷計(jì)數(shù)實(shí)現(xiàn)振中斷計(jì)數(shù)實(shí)現(xiàn)。 晶振的頻率誤差和初始計(jì)時(shí)時(shí)刻不同，使得晶振的頻率誤差和初始計(jì)時(shí)時(shí)刻不同，使得節(jié)點(diǎn)之間本地時(shí)鐘不同步。節(jié)點(diǎn)之間本地時(shí)鐘不同步。 如果能估算出本地時(shí)鐘與物理時(shí)鐘的關(guān)系或如果能估算出本地時(shí)鐘與物理時(shí)鐘的關(guān)系或本地時(shí)鐘之間的關(guān)系，就可以構(gòu)造對(duì)應(yīng)的邏本地時(shí)鐘之間的關(guān)系，就可以構(gòu)造對(duì)應(yīng)的邏輯時(shí)鐘以達(dá)成同步。輯時(shí)鐘以達(dá)成同步。 目前的邏輯時(shí)鐘同步算法，同步精度已達(dá)到目前的邏輯時(shí)鐘同步算法，同步精度已達(dá)到1 s，可以滿足傳感器網(wǎng)絡(luò)中絕大部分應(yīng)用的，可以滿足傳感器網(wǎng)絡(luò)中絕

14、大部分應(yīng)用的需求。需求。4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（1）節(jié)點(diǎn)本地時(shí)鐘模型）節(jié)點(diǎn)本地時(shí)鐘模型在計(jì)算機(jī)系統(tǒng)中，時(shí)鐘通常用在計(jì)算機(jī)系統(tǒng)中，時(shí)鐘通常用晶體振蕩器脈沖晶體振蕩器脈沖來度量來度量:4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（1）節(jié)點(diǎn)本地時(shí)鐘模型）節(jié)點(diǎn)本地時(shí)鐘模型兩個(gè)主要參數(shù)：兩個(gè)主要參數(shù)：4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（1）節(jié)點(diǎn)本地時(shí)鐘模型）節(jié)點(diǎn)本地時(shí)鐘模型在工程實(shí)踐中，因?yàn)闇囟取毫?、電源電壓等外界環(huán)境的在工程實(shí)踐中，因?yàn)闇囟取毫?、電源電壓等外界環(huán)境的變化，往往會(huì)導(dǎo)致變化，往往會(huì)導(dǎo)致晶振頻率產(chǎn)生波動(dòng)晶振頻率產(chǎn)生波動(dòng)。因此，構(gòu)造理想時(shí)。因此，構(gòu)造理想時(shí)鐘

15、比較困難。鐘比較困難。在一般情況下，晶振頻率的波動(dòng)幅度并非是任意的，而是在一般情況下，晶振頻率的波動(dòng)幅度并非是任意的，而是局限在一定的范圍之內(nèi)，為了方便描述和分析，定義如下局限在一定的范圍之內(nèi)，為了方便描述和分析，定義如下3種時(shí)鐘模型種時(shí)鐘模型:4.2.14.2.1時(shí)間同步模型時(shí)間同步模型 速率恒定模型。速率恒定模型。速率恒定模型假定時(shí)鐘速率是恒定的，速率恒定模型假定時(shí)鐘速率是恒定的，即晶振頻率沒有波動(dòng)發(fā)生。當(dāng)要求的時(shí)鐘精度遠(yuǎn)低于頻率即晶振頻率沒有波動(dòng)發(fā)生。當(dāng)要求的時(shí)鐘精度遠(yuǎn)低于頻率波動(dòng)導(dǎo)致的偏差時(shí)，該模型的假定應(yīng)該是合理的。波動(dòng)導(dǎo)致的偏差時(shí)，該模型的假定應(yīng)該是合理的。 漂移有界模型。漂移有界

16、模型。定義時(shí)鐘速率定義時(shí)鐘速率 相對(duì)于理想速率相對(duì)于理想速率1的偏差的偏差為時(shí)鐘漂移為時(shí)鐘漂移(drift) ，即，即 。漂移有界模型在工程實(shí)踐中非常有用，常用來確定時(shí)鐘的漂移有界模型在工程實(shí)踐中非常有用，常用來確定時(shí)鐘的精度或誤差的上下界。精度或誤差的上下界。 漂移變化有界模型。漂移變化有界模型。該模型假定時(shí)鐘漂移的變化該模型假定時(shí)鐘漂移的變化 是有界的是有界的時(shí)鐘漂移的變化主要是溫度和電源電壓等因素發(fā)生變化所時(shí)鐘漂移的變化主要是溫度和電源電壓等因素發(fā)生變化所引起的，一般變化速率相對(duì)緩慢，可以通過適當(dāng)?shù)难a(bǔ)償算引起的，一般變化速率相對(duì)緩慢，可以通過適當(dāng)?shù)难a(bǔ)償算法加以修正。法加以修正。4.2.1

17、4.2.1時(shí)間同步模型時(shí)間同步模型（2）節(jié)點(diǎn)邏輯時(shí)鐘模型）節(jié)點(diǎn)邏輯時(shí)鐘模型任一節(jié)點(diǎn)任一節(jié)點(diǎn)i在物理時(shí)刻在物理時(shí)刻t的邏輯時(shí)鐘讀數(shù)可以表示為的邏輯時(shí)鐘讀數(shù)可以表示為其中，其中， 為當(dāng)前本地時(shí)鐘讀數(shù)，為當(dāng)前本地時(shí)鐘讀數(shù)， 為頻率修正系數(shù)，為頻率修正系數(shù)， 為初為初相位修正系數(shù)。采用邏輯時(shí)鐘的目的是對(duì)本地時(shí)鐘進(jìn)行一相位修正系數(shù)。采用邏輯時(shí)鐘的目的是對(duì)本地時(shí)鐘進(jìn)行一定的換算以達(dá)成同步。為了同步任意兩個(gè)節(jié)點(diǎn)定的換算以達(dá)成同步。為了同步任意兩個(gè)節(jié)點(diǎn)i和和j，構(gòu)造，構(gòu)造邏輯時(shí)鐘有兩種途徑：邏輯時(shí)鐘有兩種途徑： 根據(jù)本地時(shí)鐘與物理時(shí)鐘等全局事件基準(zhǔn)的關(guān)系進(jìn)行根據(jù)本地時(shí)鐘與物理時(shí)鐘等全局事件基準(zhǔn)的關(guān)系進(jìn)行變換變

18、換 根據(jù)兩個(gè)節(jié)點(diǎn)本地時(shí)鐘的關(guān)系進(jìn)行對(duì)應(yīng)換算。根據(jù)兩個(gè)節(jié)點(diǎn)本地時(shí)鐘的關(guān)系進(jìn)行對(duì)應(yīng)換算。兩種方法都估計(jì)了頻率修正系數(shù)和初相位修正系數(shù)，兩種方法都估計(jì)了頻率修正系數(shù)和初相位修正系數(shù)，精度較高。精度較高。4.2.14.2.1時(shí)間同步模型時(shí)間同步模型2同步機(jī)制同步機(jī)制節(jié)點(diǎn)時(shí)間校正技術(shù)是無線傳感器網(wǎng)絡(luò)時(shí)間同節(jié)點(diǎn)時(shí)間校正技術(shù)是無線傳感器網(wǎng)絡(luò)時(shí)間同步的核心和基礎(chǔ)。目前主要的時(shí)間校正技術(shù)有單步的核心和基礎(chǔ)。目前主要的時(shí)間校正技術(shù)有單向報(bào)文傳遞、雙向報(bào)文交換、廣播參考報(bào)文和參向報(bào)文傳遞、雙向報(bào)文交換、廣播參考報(bào)文和參數(shù)擬合技術(shù)數(shù)擬合技術(shù)。4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（1）單向報(bào)文傳遞）單向報(bào)文傳遞

19、類似于類似于發(fā)送者發(fā)送者-接收者同步模式接收者同步模式4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（1）單向報(bào)文傳遞）單向報(bào)文傳遞節(jié)點(diǎn)節(jié)點(diǎn)i在本地時(shí)間在本地時(shí)間 時(shí)刻向節(jié)點(diǎn)時(shí)刻向節(jié)點(diǎn)j發(fā)送一個(gè)報(bào)文，發(fā)送一個(gè)報(bào)文，包含時(shí)間戳包含時(shí)間戳 。假設(shè)節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)j在本地時(shí)間在本地時(shí)間 時(shí)刻收時(shí)刻收到上述報(bào)文。節(jié)點(diǎn)到上述報(bào)文。節(jié)點(diǎn)j不知道報(bào)文的傳遞時(shí)延不知道報(bào)文的傳遞時(shí)延d，所，所以只能對(duì)以只能對(duì)d進(jìn)行估計(jì)，如果知道進(jìn)行估計(jì)，如果知道d的上界和下界，的上界和下界，則可以得到則可以得到進(jìn)而估計(jì)節(jié)點(diǎn)進(jìn)而估計(jì)節(jié)點(diǎn)i和節(jié)點(diǎn)和節(jié)點(diǎn)j之間的時(shí)間偏差公式為之間的時(shí)間偏差公式為4.2.14.2.1時(shí)間同步模型時(shí)間同步模

20、型發(fā)送者發(fā)送者-接收者同步模式：發(fā)送者發(fā)送帶有時(shí)間戳的同步包接收者同步模式：發(fā)送者發(fā)送帶有時(shí)間戳的同步包給接收者，給接收者，以此來以此來同步接收者的時(shí)間。同步接收者的時(shí)間。這種模式的缺陷是不能夠準(zhǔn)確地估計(jì)算出報(bào)文的傳輸延遲，精度不高，通過這種模式的缺陷是不能夠準(zhǔn)確地估計(jì)算出報(bào)文的傳輸延遲，精度不高，通過單個(gè)報(bào)文的傳輸不能夠準(zhǔn)確地估算傳輸延遲單個(gè)報(bào)文的傳輸不能夠準(zhǔn)確地估算傳輸延遲，并且，并且假設(shè)報(bào)文傳遞過程中只有假設(shè)報(bào)文傳遞過程中只有傳播延時(shí)，忽略了無線信道的許多不確定因素的影響傳播延時(shí)，忽略了無線信道的許多不確定因素的影響 。（2）雙向報(bào)文交換）雙向報(bào)文交換雙向報(bào)文交換時(shí)間校正技術(shù)復(fù)雜雙向報(bào)文

21、交換時(shí)間校正技術(shù)復(fù)雜的的多。節(jié)點(diǎn)多。節(jié)點(diǎn)i在本地時(shí)在本地時(shí)鐘鐘 時(shí)刻向節(jié)點(diǎn)時(shí)刻向節(jié)點(diǎn)j發(fā)送同步報(bào)文，節(jié)點(diǎn)發(fā)送同步報(bào)文，節(jié)點(diǎn)j在本地時(shí)鐘時(shí)刻在本地時(shí)鐘時(shí)刻 接收到該報(bào)文，之后立即向節(jié)點(diǎn)接收到該報(bào)文，之后立即向節(jié)點(diǎn)i發(fā)送應(yīng)答報(bào)文，節(jié)點(diǎn)發(fā)送應(yīng)答報(bào)文，節(jié)點(diǎn)i在在本地時(shí)鐘時(shí)刻本地時(shí)鐘時(shí)刻 接收到該應(yīng)答報(bào)文。則報(bào)文的往返時(shí)間接收到該應(yīng)答報(bào)文。則報(bào)文的往返時(shí)間為為D，大小為，大小為 ，報(bào)文的傳遞時(shí)延，報(bào)文的傳遞時(shí)延d在在0D之間。如果之間。如果知道知道d的上界和下界，節(jié)點(diǎn)的上界和下界，節(jié)點(diǎn)j可以確定可以確定d在在 和和 之間。由此可以確定節(jié)點(diǎn)之間。由此可以確定節(jié)點(diǎn)i、j之間的時(shí)間之間的時(shí)間偏差為偏差為 假設(shè)

22、上行報(bào)文和下行報(bào)文的時(shí)間延遲相假設(shè)上行報(bào)文和下行報(bào)文的時(shí)間延遲相等，即等，即 雙向報(bào)文交換是應(yīng)用很廣泛的一種時(shí)間校正技術(shù)，精雙向報(bào)文交換是應(yīng)用很廣泛的一種時(shí)間校正技術(shù)，精度比較高。但是網(wǎng)絡(luò)負(fù)載比較大，耗能較高，而且需要周度比較高。但是網(wǎng)絡(luò)負(fù)載比較大，耗能較高，而且需要周期性地執(zhí)行同步過程。期性地執(zhí)行同步過程。4.2.14.2.1時(shí)間同步模型時(shí)間同步模型（3）廣播參考報(bào)文）廣播參考報(bào)文利用第三個(gè)節(jié)點(diǎn)利用第三個(gè)節(jié)點(diǎn)k作為參考節(jié)點(diǎn)，發(fā)送時(shí)間同步的參作為參考節(jié)點(diǎn)，發(fā)送時(shí)間同步的參考廣播報(bào)文給相鄰的節(jié)點(diǎn)考廣播報(bào)文給相鄰的節(jié)點(diǎn)i和節(jié)點(diǎn)和節(jié)點(diǎn)j。假設(shè)這個(gè)參考廣播報(bào)。假設(shè)這個(gè)參考廣播報(bào)文到達(dá)節(jié)點(diǎn)文到達(dá)節(jié)點(diǎn)i和

23、節(jié)點(diǎn)和節(jié)點(diǎn)j的時(shí)間延遲相等的時(shí)間延遲相等 。節(jié)點(diǎn)。節(jié)點(diǎn)j收到參收到參考廣播報(bào)文后，立即發(fā)送包含有考廣播報(bào)文后，立即發(fā)送包含有 信息的報(bào)文給節(jié)點(diǎn)信息的報(bào)文給節(jié)點(diǎn)i，于是節(jié)點(diǎn)于是節(jié)點(diǎn)i就可以計(jì)算收到兩條報(bào)文的時(shí)間間隔就可以計(jì)算收到兩條報(bào)文的時(shí)間間隔D為為廣播參考報(bào)文的方法只能使節(jié)點(diǎn)間的時(shí)鐘保持相對(duì)同步。廣播參考報(bào)文的方法只能使節(jié)點(diǎn)間的時(shí)鐘保持相對(duì)同步。4.2.14.2.1時(shí)間同步模型時(shí)間同步模型接收者接收者-接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同步包在若干接收者之間進(jìn)行同步，接收者步包在若干接收者之間進(jìn)行同步，接收者-接收者模式縮短了接收者模式縮短

24、了關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長(zhǎng)而導(dǎo)致的不關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長(zhǎng)而導(dǎo)致的不準(zhǔn)確的傳輸延遲估計(jì)準(zhǔn)確的傳輸延遲估計(jì)。課程目錄課程目錄4.2.14.2.14.2.24.2.2時(shí)間同步模型時(shí)間同步模型時(shí)間同步協(xié)議時(shí)間同步協(xié)議無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)4.24.21時(shí)間同步的類別時(shí)間同步的類別時(shí)間同步一般理解為使許多節(jié)點(diǎn)的時(shí)鐘顯示相同的時(shí)時(shí)間同步一般理解為使許多節(jié)點(diǎn)的時(shí)鐘顯示相同的時(shí)間，實(shí)際上有很多種不同類型的同步。間，實(shí)際上有很多種不同類型的同步。在為給定的應(yīng)用選擇同步算法時(shí)，要在最大程度滿足在為給定的應(yīng)用選擇同步算法時(shí)，要在最大程度滿足應(yīng)用的

25、同時(shí)盡可能將計(jì)算、存儲(chǔ)，尤其是能量開銷降到最應(yīng)用的同時(shí)盡可能將計(jì)算、存儲(chǔ)，尤其是能量開銷降到最低低。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（1）時(shí)鐘速率同步與偏移同步）時(shí)鐘速率同步與偏移同步速率同步是指各個(gè)傳感器節(jié)點(diǎn)測(cè)量所得的時(shí)間間隔相速率同步是指各個(gè)傳感器節(jié)點(diǎn)測(cè)量所得的時(shí)間間隔相等，在目標(biāo)跟蹤、定位等應(yīng)用中，節(jié)點(diǎn)時(shí)鐘速率同步是最等，在目標(biāo)跟蹤、定位等應(yīng)用中，節(jié)點(diǎn)時(shí)鐘速率同步是最低的同步要求。低的同步要求。偏移同步是指?jìng)鞲衅鞴?jié)點(diǎn)在當(dāng)前時(shí)刻偏移同步是指?jìng)鞲衅鞴?jié)點(diǎn)在當(dāng)前時(shí)刻t的時(shí)鐘時(shí)間顯的時(shí)鐘時(shí)間顯示相等，即在時(shí)刻示相等，即在時(shí)刻t傳感器節(jié)點(diǎn)的時(shí)鐘讀出時(shí)間同為傳感器節(jié)點(diǎn)的時(shí)鐘讀出時(shí)間同為T，

26、而，而不管時(shí)鐘速率是否同步不管時(shí)鐘速率是否同步，偏移同步對(duì)傳感器網(wǎng)絡(luò)中不同節(jié)偏移同步對(duì)傳感器網(wǎng)絡(luò)中不同節(jié)點(diǎn)間的時(shí)戳結(jié)合是必須的。點(diǎn)間的時(shí)戳結(jié)合是必須的。2 24.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（2）同步期限：長(zhǎng)期同步與按需同步）同步期限：長(zhǎng)期同步與按需同步時(shí)間同步的同步期限是指同步要保持的時(shí)間長(zhǎng)短。在時(shí)間同步的同步期限是指同步要保持的時(shí)間長(zhǎng)短。在長(zhǎng)期同步的情況下，維持同步的代價(jià)是很大的，隨著時(shí)間長(zhǎng)期同步的情況下，維持同步的代價(jià)是很大的，隨著時(shí)間的推移，節(jié)點(diǎn)間誤差逐漸增加，可能還需要周期性地再同的推移，節(jié)點(diǎn)間誤差逐漸增加，可能還需要周期性地再同步。步。按需同步是指?jìng)鞲衅鞴?jié)點(diǎn)的時(shí)間在相關(guān)

27、事件發(fā)生前后按需同步是指?jìng)鞲衅鞴?jié)點(diǎn)的時(shí)間在相關(guān)事件發(fā)生前后進(jìn)行同步，它不需要大量的維護(hù)同步的通信開銷，節(jié)省了進(jìn)行同步，它不需要大量的維護(hù)同步的通信開銷，節(jié)省了通信帶寬和節(jié)點(diǎn)能量。對(duì)一些傳感器網(wǎng)絡(luò)的應(yīng)用，按需同通信帶寬和節(jié)點(diǎn)能量。對(duì)一些傳感器網(wǎng)絡(luò)的應(yīng)用，按需同步效率更高。步效率更高。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（3）同步范圍：全網(wǎng)同步與局部同步）同步范圍：全網(wǎng)同步與局部同步同步范圍是定義網(wǎng)絡(luò)中哪些節(jié)點(diǎn)同步范圍是定義網(wǎng)絡(luò)中哪些節(jié)點(diǎn)是是需要同步的。在有需要同步的。在有些情況下，范圍可能純粹是地理上的距離。而在其他情況些情況下，范圍可能純粹是地理上的距離。而在其他情況下，邏輯距離更有用

28、，如網(wǎng)絡(luò)中的跳數(shù)。根據(jù)不同的應(yīng)用，下，邏輯距離更有用，如網(wǎng)絡(luò)中的跳數(shù)。根據(jù)不同的應(yīng)用，范圍可能是網(wǎng)絡(luò)中所有節(jié)點(diǎn)或者部分節(jié)點(diǎn)。范圍可能是網(wǎng)絡(luò)中所有節(jié)點(diǎn)或者部分節(jié)點(diǎn)。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（4）內(nèi)同步和外同步）內(nèi)同步和外同步一些應(yīng)用只需要記錄事件發(fā)生的先后順序以及時(shí)間間一些應(yīng)用只需要記錄事件發(fā)生的先后順序以及時(shí)間間隔，并不需要事件發(fā)生的絕對(duì)時(shí)間。這種情況下，只需要隔，并不需要事件發(fā)生的絕對(duì)時(shí)間。這種情況下，只需要內(nèi)同步（相對(duì)同步），網(wǎng)絡(luò)必須內(nèi)部一致，不需要它們與內(nèi)同步（相對(duì)同步），網(wǎng)絡(luò)必須內(nèi)部一致，不需要它們與外界標(biāo)準(zhǔn)時(shí)間保持一致性。外界標(biāo)準(zhǔn)時(shí)間保持一致性。另一類應(yīng)用要求外同

29、步（絕對(duì)同步），即每個(gè)節(jié)點(diǎn)都另一類應(yīng)用要求外同步（絕對(duì)同步），即每個(gè)節(jié)點(diǎn)都要與外部時(shí)間標(biāo)度（如要與外部時(shí)間標(biāo)度（如UTC）保持同步。通常的環(huán)境監(jiān)控）保持同步。通常的環(huán)境監(jiān)控或者需要數(shù)據(jù)存檔的應(yīng)用中，比較需要外同步，而且要求或者需要數(shù)據(jù)存檔的應(yīng)用中，比較需要外同步，而且要求的同步期限比較長(zhǎng)。的同步期限比較長(zhǎng)。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（5）發(fā)送者接收者同步與接收者接收者同步）發(fā)送者接收者同步與接收者接收者同步在進(jìn)行發(fā)送者接收者同步時(shí)，發(fā)送者在報(bào)文中嵌入在進(jìn)行發(fā)送者接收者同步時(shí)，發(fā)送者在報(bào)文中嵌入報(bào)文發(fā)送時(shí)間，而接收者在接收到報(bào)文后記錄下接收時(shí)間，報(bào)文發(fā)送時(shí)間，而接收者在接收到報(bào)

30、文后記錄下接收時(shí)間，并利用這些時(shí)間信息計(jì)算出收發(fā)雙方的時(shí)鐘偏移，進(jìn)而達(dá)并利用這些時(shí)間信息計(jì)算出收發(fā)雙方的時(shí)鐘偏移，進(jìn)而達(dá)到收發(fā)雙方的時(shí)間同步。到收發(fā)雙方的時(shí)間同步。接收者接收者同步時(shí)，發(fā)送者發(fā)送一個(gè)同步報(bào)文到接收者接收者同步時(shí)，發(fā)送者發(fā)送一個(gè)同步報(bào)文到多個(gè)接收者，這些接收者通過對(duì)同一個(gè)報(bào)文時(shí)間的比較，多個(gè)接收者，這些接收者通過對(duì)同一個(gè)報(bào)文時(shí)間的比較，計(jì)算出它們之間的時(shí)鐘偏移，從而達(dá)到接收者一接收者同計(jì)算出它們之間的時(shí)鐘偏移，從而達(dá)到接收者一接收者同步。步。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議接收者接收者-接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)

31、送的同步包在若干接收者之間進(jìn)行同步，接收者步包在若干接收者之間進(jìn)行同步，接收者-接收者模式縮短了接收者模式縮短了關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長(zhǎng)而導(dǎo)致的不關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長(zhǎng)而導(dǎo)致的不準(zhǔn)確的傳輸延遲估計(jì)準(zhǔn)確的傳輸延遲估計(jì)。2典型的時(shí)間同步協(xié)議典型的時(shí)間同步協(xié)議（1）LTS協(xié)議協(xié)議（2）RBS協(xié)議協(xié)議（3）TPSN協(xié)議協(xié)議（4）DMTS協(xié)議協(xié)議（5）FTSP協(xié)議協(xié)議（6）HRTS協(xié)議協(xié)議（7）GCS協(xié)議協(xié)議（8）幾種協(xié)議的比較）幾種協(xié)議的比較4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議（1）LTS協(xié)議（協(xié)議（Lightweight Tree-based Synch

32、ronization） LTS同步算法的設(shè)計(jì)目標(biāo)就是適用于低成本、同步算法的設(shè)計(jì)目標(biāo)就是適用于低成本、低復(fù)雜度的傳感器節(jié)點(diǎn)時(shí)間同步低復(fù)雜度的傳感器節(jié)點(diǎn)時(shí)間同步； 側(cè)重最小化同步的能量開銷，同時(shí)具有魯側(cè)重最小化同步的能量開銷，同時(shí)具有魯棒性和自配置的特點(diǎn)棒性和自配置的特點(diǎn)。 劃分為劃分為3個(gè)組成部件：個(gè)組成部件： 重同步監(jiān)測(cè)重同步監(jiān)測(cè) 遠(yuǎn)程時(shí)鐘估計(jì)遠(yuǎn)程時(shí)鐘估計(jì) 時(shí)鐘修正時(shí)鐘修正4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議17/20LTS機(jī)制LTS應(yīng)用于多跳網(wǎng)絡(luò)應(yīng)用于多跳網(wǎng)絡(luò)根根節(jié)節(jié)點(diǎn)點(diǎn)1211111122222222222集中式集中式根根節(jié)節(jié)點(diǎn)點(diǎn)1211111122222222222分布式分布式

33、（2）RBS協(xié)議（協(xié)議（Reference Broadcast Synchronization） 參考廣播時(shí)間同步協(xié)議參考廣播時(shí)間同步協(xié)議 利用無線數(shù)據(jù)鏈路層的廣播信道特性，一個(gè)利用無線數(shù)據(jù)鏈路層的廣播信道特性，一個(gè)節(jié)點(diǎn)發(fā)送廣播消息，接收到廣播消息的一組節(jié)點(diǎn)發(fā)送廣播消息，接收到廣播消息的一組節(jié)點(diǎn)通過比較各自接收到廣播消息的同步時(shí)節(jié)點(diǎn)通過比較各自接收到廣播消息的同步時(shí)刻，來實(shí)現(xiàn)它們之間的時(shí)間同步?？?，來實(shí)現(xiàn)它們之間的時(shí)間同步。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議工作原理：工作原理： RBS算法通過接收節(jié)點(diǎn)對(duì)時(shí)抵消發(fā)送時(shí)間和算法通過接收節(jié)點(diǎn)對(duì)時(shí)抵消發(fā)送時(shí)間和訪問時(shí)間，發(fā)送節(jié)點(diǎn)廣播一個(gè)信標(biāo)分

34、組，廣播域訪問時(shí)間，發(fā)送節(jié)點(diǎn)廣播一個(gè)信標(biāo)分組，廣播域中兩個(gè)節(jié)點(diǎn)都能接收到這個(gè)分組，交換接收時(shí)間，中兩個(gè)節(jié)點(diǎn)都能接收到這個(gè)分組，交換接收時(shí)間，兩個(gè)接收時(shí)間的差值相當(dāng)于兩個(gè)接收節(jié)點(diǎn)間的時(shí)兩個(gè)接收時(shí)間的差值相當(dāng)于兩個(gè)接收節(jié)點(diǎn)間的時(shí)間差值，其中一個(gè)節(jié)點(diǎn)可以根據(jù)這個(gè)時(shí)間差值更間差值，其中一個(gè)節(jié)點(diǎn)可以根據(jù)這個(gè)時(shí)間差值更改它的本地時(shí)間，從而實(shí)現(xiàn)兩個(gè)節(jié)點(diǎn)的時(shí)間同步改它的本地時(shí)間，從而實(shí)現(xiàn)兩個(gè)節(jié)點(diǎn)的時(shí)間同步。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議7/20 RBS同步機(jī)制RBS機(jī)制的基本原理機(jī)制的基本原理發(fā)送節(jié)點(diǎn)發(fā)送節(jié)點(diǎn)接收節(jié)點(diǎn)接收節(jié)點(diǎn)信標(biāo)分組信標(biāo)分組接收節(jié)點(diǎn)接收節(jié)點(diǎn)接收信標(biāo)分組本地時(shí)間接收信標(biāo)分組本地時(shí)間

35、調(diào)整時(shí)間接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） 在RBS算法中，接收節(jié)點(diǎn)只需比較接收節(jié)點(diǎn)接收?qǐng)?bào)文的時(shí)間之差，因此在發(fā)送節(jié)點(diǎn)發(fā)送的參考報(bào)文中無須攜帶發(fā)送節(jié)點(diǎn)的本地時(shí)間。同步誤差只與接收者們是否在同一時(shí)刻記錄本地時(shí)間有關(guān)，為了減小時(shí)間同步的誤差，RBS采用了統(tǒng)計(jì)技術(shù)，廣播多個(gè)時(shí)間同步消息，求相互之間消息到達(dá)的時(shí)間差的平均值，這樣就能在最大程度上消除非同時(shí)記錄的影響RBS （Reference

36、 Broadcast Synchronization） 接收者接收者同步的基本依據(jù)：接收者時(shí)間相移均值為0單跳RBS 用最小二乘法估計(jì)clock skew提高同步精度8/20 RBS同步機(jī)制RBS機(jī)制應(yīng)用于多跳網(wǎng)絡(luò)機(jī)制應(yīng)用于多跳網(wǎng)絡(luò)AB1432765考慮RBS協(xié)議應(yīng)用于多跳網(wǎng)絡(luò)情況：RBS能夠消除發(fā)送節(jié)點(diǎn)引起的同步誤差，在忽略傳播時(shí)間的情況下，主要的誤差來源就只剩下接收節(jié)點(diǎn)之間的處理時(shí)間差，以及發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)間的無線電同步誤差，這兩者都只有s級(jí)，因此RBS算法的同步精度非常高，但RBS算法的網(wǎng)絡(luò)開銷比較大，對(duì)于單播域中的n個(gè)節(jié)點(diǎn)和m個(gè)參考廣播消息，RBS算法的復(fù)雜度為O(mn2)。在圖示網(wǎng)

37、絡(luò)中存在三個(gè)不同的單跳域A、B和C，其中4號(hào)和7號(hào)節(jié)點(diǎn)處于兩個(gè)單跳域的交界，4號(hào)節(jié)點(diǎn)可以同步A區(qū)域和C區(qū)域的時(shí)間，7號(hào)節(jié)點(diǎn)可以同步B區(qū)域和C區(qū)域的時(shí)間，根據(jù)這兩個(gè)節(jié)點(diǎn)我們可以得到相鄰兩區(qū)域的時(shí)間轉(zhuǎn)換關(guān)系，從而達(dá)到全網(wǎng)的時(shí)間同步。 9/20RBS同步機(jī)制 RBS同步機(jī)制總結(jié)：RBS機(jī)制利用信道的廣播特性來同步接收節(jié)點(diǎn)時(shí)間，去除了時(shí)間同步誤差中所有發(fā)送節(jié)點(diǎn)引入的部分。通過多次廣播分組獲取平均值，能夠提高RBS的時(shí)間同步精度。對(duì)于單個(gè)廣播域內(nèi)的n個(gè)節(jié)點(diǎn)和m個(gè)廣播消息，RBS機(jī)制的復(fù)雜度為O（mn）。用于多跳網(wǎng)絡(luò)的RBS機(jī)制需要依賴有效的分簇方法，保證簇之間有共同節(jié)點(diǎn)以便進(jìn)行簇間時(shí)間同步10/20RB

38、S同步機(jī)制 后同步思想：后同步思想：通常情況下節(jié)點(diǎn)的時(shí)間不用同步，只有監(jiān)測(cè)到一個(gè)事件發(fā)通常情況下節(jié)點(diǎn)的時(shí)間不用同步，只有監(jiān)測(cè)到一個(gè)事件發(fā)生時(shí)，節(jié)點(diǎn)才首先用它的本地時(shí)間記錄事件發(fā)生的時(shí)間，生時(shí)，節(jié)點(diǎn)才首先用它的本地時(shí)間記錄事件發(fā)生的時(shí)間，然后采用然后采用RBS機(jī)制，一個(gè)機(jī)制，一個(gè)“第三方第三方”節(jié)點(diǎn)廣播信標(biāo)消息給節(jié)點(diǎn)廣播信標(biāo)消息給區(qū)域內(nèi)的所有節(jié)點(diǎn)，接收節(jié)點(diǎn)利用這個(gè)同步消息作為一個(gè)區(qū)域內(nèi)的所有節(jié)點(diǎn)，接收節(jié)點(diǎn)利用這個(gè)同步消息作為一個(gè)瞬時(shí)的時(shí)間參考點(diǎn)，同步它們監(jiān)測(cè)到的事件發(fā)生時(shí)間。瞬時(shí)的時(shí)間參考點(diǎn)，同步它們監(jiān)測(cè)到的事件發(fā)生時(shí)間。后同步機(jī)制能夠?qū)崿F(xiàn)后同步機(jī)制能夠?qū)崿F(xiàn)瞬時(shí)的節(jié)點(diǎn)間時(shí)間同步瞬時(shí)的節(jié)點(diǎn)間時(shí)間同

39、步，但是受限于，但是受限于廣播信標(biāo)分組的傳輸范圍，它不適應(yīng)于長(zhǎng)距離或長(zhǎng)時(shí)間通廣播信標(biāo)分組的傳輸范圍，它不適應(yīng)于長(zhǎng)距離或長(zhǎng)時(shí)間通信的時(shí)間同步。信的時(shí)間同步。后同步機(jī)制能夠提供精確的局部空間范圍的時(shí)間同步。后同步機(jī)制能夠提供精確的局部空間范圍的時(shí)間同步。（3）TPSN協(xié)議協(xié)議 通過采用層次型網(wǎng)絡(luò)結(jié)構(gòu)來提供全網(wǎng)范圍內(nèi)通過采用層次型網(wǎng)絡(luò)結(jié)構(gòu)來提供全網(wǎng)范圍內(nèi)節(jié)點(diǎn)同步。節(jié)點(diǎn)同步。 該機(jī)制分為拓?fù)浣㈦A段和同步建立階段，該機(jī)制分為拓?fù)浣㈦A段和同步建立階段，考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息交換計(jì)算消息的平均延遲，提高了精度。交換計(jì)算消息的平均延遲，提高了精度。4.

40、2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議TPSN （ Timing-sync Protocol for Sensor Networks ）TPSN時(shí)間同步協(xié)議思想TPSN （ Timing-sync Protocol for Sensor Networks ）Thursday, July 07, 20221、TPSN是類似于NTP（Network Time Protocol）時(shí)間同步協(xié)議2、目的是提供傳感器網(wǎng)絡(luò)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步3、節(jié)點(diǎn)結(jié)構(gòu)中包含一個(gè)根節(jié)點(diǎn)，它與外界通信獲取外界時(shí)間，以此作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)鐘源4、將節(jié)點(diǎn)分級(jí)后（根節(jié)點(diǎn)是0級(jí)，累加），每個(gè)節(jié)點(diǎn)同上一級(jí)的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同

41、步，最終與根節(jié)點(diǎn)同步5、節(jié)點(diǎn)對(duì)之間的同步采用發(fā)送者-接收者同步機(jī)制（RBS）11/20TPSN時(shí)間同步協(xié)議根節(jié)點(diǎn)11212122222層次發(fā)現(xiàn)階段層次發(fā)現(xiàn)階段（廣播級(jí)別發(fā)現(xiàn)分組）（廣播級(jí)別發(fā)現(xiàn)分組）根節(jié)點(diǎn)11212122222同步階段同步階段（廣播時(shí)間同步分組）（廣播時(shí)間同步分組）每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biāo)識(shí)號(hào)ID節(jié)點(diǎn)間的無線通信鏈路是雙向的，通過雙向消息交換實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步整個(gè)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)按層次結(jié)構(gòu)管理，由TPSN協(xié)議生成和維護(hù)TPSN協(xié)議過程協(xié)議準(zhǔn)備協(xié)議準(zhǔn)備目的：生成節(jié)點(diǎn)層次結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)被賦予一個(gè)級(jí)別，根節(jié)點(diǎn)為0級(jí)，第i級(jí)的節(jié)點(diǎn)至少能夠與一個(gè)第（i-1）級(jí)得節(jié)點(diǎn)通信網(wǎng)絡(luò)部署后，由根

42、節(jié)點(diǎn)廣播級(jí)別發(fā)現(xiàn)分組來啟動(dòng)層次發(fā)現(xiàn)階段，級(jí)別發(fā)現(xiàn)分組包含節(jié)點(diǎn)的ID和級(jí)別鄰居節(jié)點(diǎn)收到分組后，將自己的級(jí)別設(shè)置為分組中的級(jí)別加1，然后廣播新的級(jí)別發(fā)現(xiàn)分組節(jié)點(diǎn)收到第i級(jí)節(jié)點(diǎn)的廣播分組后，記錄發(fā)送這個(gè)廣播分組的節(jié)點(diǎn)ID，設(shè)置自己的級(jí)別為（i+1），廣播級(jí)別為（i+1）的分組，這個(gè)過程持續(xù)到網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)都被賦予一個(gè)級(jí)別節(jié)點(diǎn)一旦建立自己的級(jí)別，就忽略任何其他級(jí)別發(fā)現(xiàn)分組，防止網(wǎng)絡(luò)產(chǎn)生洪泛擁塞TPSN協(xié)議過程第一階段第一階段 層次發(fā)現(xiàn)階段（層次發(fā)現(xiàn)階段（Level Discovery PhaseLevel Discovery Phase）Thursday, July 07, 2022目的：實(shí)現(xiàn)所有樹節(jié)

43、點(diǎn)的時(shí)間同步，第1級(jí)節(jié)點(diǎn)同步到根節(jié)點(diǎn)，第i級(jí)的節(jié)點(diǎn)同步到第（i-1）級(jí)的一個(gè)節(jié)點(diǎn)，最終所有節(jié)點(diǎn)同步到根節(jié)點(diǎn)，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步層次結(jié)構(gòu)建立以后，根節(jié)點(diǎn)通過廣播時(shí)間同步分組啟動(dòng)同步階段第1級(jí)節(jié)點(diǎn)收到分組后，各自分別等待一段隨機(jī)時(shí)間，再通過與根節(jié)點(diǎn)交換消息同步到根節(jié)點(diǎn)第2級(jí)節(jié)點(diǎn)偵聽到第1級(jí)節(jié)點(diǎn)的交換消息后，等待一段隨機(jī)時(shí)間，再與它記錄的上一級(jí)別的節(jié)點(diǎn)交換消息進(jìn)行同步，網(wǎng)絡(luò)中的節(jié)點(diǎn)依次與上一級(jí)節(jié)點(diǎn)同步，最終都同步到根節(jié)點(diǎn)等待一段隨機(jī)時(shí)間是為了保證該級(jí)節(jié)點(diǎn)在上一級(jí)節(jié)點(diǎn)同步完成后才啟動(dòng)消息交換TPSN協(xié)議過程第二階段第二階段 同步階段（同步階段（Synchronization PhaseSynchr

44、onization Phase）Thursday, July 07, 2022TPSN協(xié)議過程相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制Thursday, July 07, 2022i-1級(jí)級(jí)i級(jí)級(jí)消息傳播消息傳播時(shí)延時(shí)延兩節(jié)點(diǎn)間的兩節(jié)點(diǎn)間的時(shí)間偏差時(shí)間偏差TPSN協(xié)議過程相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制相鄰級(jí)別節(jié)點(diǎn)間的同步機(jī)制結(jié)論結(jié)論Thursday, July 07, 2022優(yōu)點(diǎn)減少同步誤差減少同步誤差TPSN同步協(xié)議在MAC層消息開始發(fā)送到無線信道是才給消息添加時(shí)標(biāo)，消除了訪問時(shí)間帶來的時(shí)間同步誤差提高同步精度提高同步精度考慮了傳播時(shí)間和接收時(shí)間，利用雙向消息交換計(jì)算消息的平均延遲，提高

45、了時(shí)間同步的精度Thursday, July 07, 2022缺點(diǎn)Thursday, July 07, 2022沒有考慮根節(jié)點(diǎn)失效問題新的節(jié)點(diǎn)加入時(shí)，需要初始化層次發(fā)現(xiàn)階段，級(jí)別的靜態(tài)特性減少了算法的魯棒性使用范圍Thursday, July 07, 2022TPSN能夠?qū)崿F(xiàn)全網(wǎng)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步，同步誤差與跳數(shù)距離成正比適合實(shí)現(xiàn)短期間的全網(wǎng)節(jié)點(diǎn)時(shí)間同步，若要長(zhǎng)時(shí)間的全網(wǎng)節(jié)點(diǎn)時(shí)間同步，需要周期的執(zhí)行TPSN協(xié)議進(jìn)行同步，間隔時(shí)間根據(jù)具體情況決定考慮能耗問題，TPSN可以與后同步策略結(jié)合使用（4）DMTS協(xié)議（協(xié)議（Delay Measurement Time Synchronization

46、） 延遲測(cè)量時(shí)間同步通過對(duì)同步報(bào)文在傳輸路徑上所有延遲測(cè)量時(shí)間同步通過對(duì)同步報(bào)文在傳輸路徑上所有的延遲進(jìn)行估計(jì)來實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。的延遲進(jìn)行估計(jì)來實(shí)現(xiàn)節(jié)點(diǎn)間的時(shí)間同步。 其基本原理為：其基本原理為： 選擇一個(gè)節(jié)點(diǎn)作為時(shí)間主節(jié)點(diǎn)（選擇一個(gè)節(jié)點(diǎn)作為時(shí)間主節(jié)點(diǎn)（Leader）廣播同步）廣播同步報(bào)文，同步報(bào)文中嵌入其本地時(shí)間。報(bào)文，同步報(bào)文中嵌入其本地時(shí)間。 所有的接收節(jié)點(diǎn)測(cè)量這個(gè)時(shí)間廣播報(bào)文的延遲，設(shè)所有的接收節(jié)點(diǎn)測(cè)量這個(gè)時(shí)間廣播報(bào)文的延遲，設(shè)置其時(shí)間為接收到分組攜帶的時(shí)間加上報(bào)文的傳輸置其時(shí)間為接收到分組攜帶的時(shí)間加上報(bào)文的傳輸延遲時(shí)間。延遲時(shí)間。 時(shí)間同步精度主要由測(cè)量延遲的精度所決定。時(shí)間

47、同步精度主要由測(cè)量延遲的精度所決定。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議發(fā)送者接收者：DMTS 最簡(jiǎ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í)間訪問時(shí)間訪問時(shí)間DMTS（Delay Measurement Time Synchronization） DMTS機(jī)制的同步報(bào)文傳輸過程如機(jī)制的同步報(bào)文傳輸過程如下下圖所示。主節(jié)點(diǎn)圖所示。主節(jié)點(diǎn)在檢測(cè)到信道空閑時(shí)，排除同步

48、報(bào)文發(fā)送的處理延遲和在檢測(cè)到信道空閑時(shí)，排除同步報(bào)文發(fā)送的處理延遲和MAC層的訪問延遲的影響，再在廣播報(bào)文嵌入時(shí)間戳層的訪問延遲的影響，再在廣播報(bào)文嵌入時(shí)間戳t0。由于通信機(jī)制的要求，報(bào)文在發(fā)送前主節(jié)點(diǎn)必須先發(fā)送一由于通信機(jī)制的要求，報(bào)文在發(fā)送前主節(jié)點(diǎn)必須先發(fā)送一定數(shù)量的前導(dǎo)碼（定數(shù)量的前導(dǎo)碼（Premble）和同步字（）和同步字（Sync Word），以），以便同步節(jié)點(diǎn)進(jìn)行接收同步報(bào)文。便同步節(jié)點(diǎn)進(jìn)行接收同步報(bào)文。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議14/20 DMTS同步機(jī)制發(fā)送者：接收者：同步消息MAC延遲發(fā)送前導(dǎo)碼起始字符發(fā)送數(shù)據(jù)接收ACK加上時(shí)標(biāo)t0接收前導(dǎo)碼接收數(shù)據(jù)發(fā)送AC

49、K接收處理時(shí)標(biāo)t1時(shí)標(biāo)t2n=發(fā)送信息位個(gè)數(shù)t=發(fā)送每比特位需要的時(shí)間前導(dǎo)碼和起始字符的發(fā)送時(shí)間=nt接收處理延遲=t2-t1忽略無線信號(hào)的傳播延遲接收節(jié)點(diǎn)時(shí)鐘為t0+nt+（t2-t1）15/20 DMTS同步機(jī)制vDMTS機(jī)制在多跳網(wǎng)絡(luò)中采用機(jī)制在多跳網(wǎng)絡(luò)中采用層次型層次型分級(jí)結(jié)分級(jí)結(jié)構(gòu)實(shí)現(xiàn)全網(wǎng)內(nèi)所有節(jié)點(diǎn)的時(shí)間同步構(gòu)實(shí)現(xiàn)全網(wǎng)內(nèi)所有節(jié)點(diǎn)的時(shí)間同步vDMTS同步機(jī)制總結(jié)：同步機(jī)制總結(jié)： DMTS是一種靈活的、輕量的和能量高效的能夠?qū)崿F(xiàn)全部網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)間同步的機(jī)制。 與RBS機(jī)制相比，DMTS機(jī)制的計(jì)算開銷小，需要傳輸?shù)南l數(shù)少。 能夠與外部世界標(biāo)準(zhǔn)時(shí)間同步，但同步精度相對(duì)較低。 DMTS在實(shí)現(xiàn)

50、復(fù)雜度、能量高效與同步精度之間進(jìn)行了折中，能夠應(yīng)用在對(duì)時(shí)間同步要求不是非常高的網(wǎng)絡(luò)中。 （5）FTSP協(xié)議（協(xié)議（Flooding Time Synchronization Protocol） 使用單個(gè)廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時(shí)使用單個(gè)廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時(shí)間同步間同步 算法的具體實(shí)現(xiàn)與算法的具體實(shí)現(xiàn)與DMTS有所不同有所不同 FTSP算法實(shí)現(xiàn)步驟如下算法實(shí)現(xiàn)步驟如下： FTSP算法在完成算法在完成SYNC字節(jié)發(fā)射后給時(shí)間同步消息標(biāo)字節(jié)發(fā)射后給時(shí)間同步消息標(biāo)記時(shí)間戳記時(shí)間戳t并并發(fā)送發(fā)送；SYNC字節(jié)類似字節(jié)類似DMTS算法中的算法中的Start Symbols；

51、時(shí)間戳?xí)r間戳t為當(dāng)前時(shí)間減去包含時(shí)間戳為當(dāng)前時(shí)間減去包含時(shí)間戳t的消息數(shù)據(jù)部的消息數(shù)據(jù)部分的發(fā)射時(shí)間分的發(fā)射時(shí)間； 消息數(shù)據(jù)部分的發(fā)射時(shí)間可通過數(shù)據(jù)長(zhǎng)度和發(fā)射速消息數(shù)據(jù)部分的發(fā)射時(shí)間可通過數(shù)據(jù)長(zhǎng)度和發(fā)射速率得出。率得出。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議 接收節(jié)點(diǎn)記錄接收節(jié)點(diǎn)記錄SYNC字節(jié)最后到達(dá)時(shí)間字節(jié)最后到達(dá)時(shí)間t，并計(jì)算位偏移，并計(jì)算位偏移（bit offset）。在收到完整消息后，接收節(jié)點(diǎn)計(jì)算位偏移）。在收到完整消息后，接收節(jié)點(diǎn)計(jì)算位偏移產(chǎn)生的時(shí)間延遲產(chǎn)生的時(shí)間延遲tb，這通過偏移位數(shù)與接收速率得出。，這通過偏移位數(shù)與接收速率得出。 接收節(jié)點(diǎn)計(jì)算與發(fā)送節(jié)點(diǎn)間的時(shí)鐘偏移量接收

52、節(jié)點(diǎn)計(jì)算與發(fā)送節(jié)點(diǎn)間的時(shí)鐘偏移量， 然后調(diào)整然后調(diào)整本地時(shí)鐘和發(fā)送節(jié)點(diǎn)時(shí)鐘同步。本地時(shí)鐘和發(fā)送節(jié)點(diǎn)時(shí)鐘同步。4.2.24.2.2時(shí)間同步協(xié)議時(shí)間同步協(xié)議 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í)間戳，可對(duì)中斷等待時(shí)間進(jìn)行補(bǔ)償 對(duì)clock skew的補(bǔ)償仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） (6) HRTS(6) HRTS（Hierarchy Referencing Time Hierarchy Referencing Time Synchronization ProtocolSynchronization Protocol） TPSN基于雙向報(bào)文交換，因此同步精度高 TPSN本質(zhì)上是對(duì)同步，因此全網(wǎng)同步的同步能耗高。 由DMTS發(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 n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） 根節(jié)