第四章_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í)間同步：使網(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ā)生的先后順序，對本判斷事件發(fā)生的先后順序，對本 地時(shí)間的要求比較低，只需要知道本節(jié)點(diǎn)與其余節(jié)點(diǎn)地時(shí)間的要求比較低

2、，只需要知道本節(jié)點(diǎn)與其余節(jié)點(diǎn) 的相對時(shí)間即可的相對時(shí)間即可 u第二種第二種：相對同步相對同步，節(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第三種第三種：絕對同步絕對同步，所有節(jié)點(diǎn)的本地時(shí)間嚴(yán)格同步，所有節(jié)點(diǎn)的本地時(shí)間嚴(yán)格同步， 等同于標(biāo)準(zhǔn)時(shí)間，這種情況對節(jié)點(diǎn)的要求最高，因此等同于標(biāo)準(zhǔn)時(shí)間，這種情況對節(jié)點(diǎn)的要求最高，因此 實(shí)現(xiàn)也最為復(fù)雜實(shí)現(xiàn)也最為復(fù)雜 估計(jì)目標(biāo)的運(yùn)行速度和方向估計(jì)目標(biāo)的運(yùn)行速度和方向 數(shù)據(jù)融合需要時(shí)間同步數(shù)據(jù)融合需要時(shí)間同步

3、 用戶交互性需要用戶交互性需要 參考時(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í)間為是當(dāng)真實(shí)時(shí)間為t時(shí)節(jié)點(diǎn)的本地時(shí)間。時(shí)節(jié)點(diǎn)的本地時(shí)間。 2軟件時(shí)鐘

4、軟件時(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)系來換算成真實(shí)時(shí)間的函數(shù)間的關(guān)系來換算成真實(shí)時(shí)間的函數(shù)c(h(t)。c(h(t)=t0+h(t)h(t0)就是一個(gè)最簡就是一個(gè)最簡 單的虛擬軟件時(shí)鐘的例子，實(shí)際應(yīng)用中，軟件時(shí)鐘還要考慮到時(shí)鐘漂移對時(shí)單的虛擬軟件時(shí)鐘的例子，實(shí)際應(yīng)用中，軟件時(shí)鐘還要考慮到時(shí)鐘漂移對時(shí) 鐘的影響，因此更加復(fù)雜。鐘的影響，因此更加

5、復(fù)雜。 到目前為止，時(shí)間同步技術(shù)的研究已經(jīng)有了到目前為止，時(shí)間同步技術(shù)的研究已經(jīng)有了30年之久，最早的時(shí)間同步年之久，最早的時(shí)間同步 機(jī)制是美國一所大學(xué)提出的網(wǎng)絡(luò)時(shí)間協(xié)議（機(jī)制是美國一所大學(xué)提出的網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）。）。NTP協(xié)議的時(shí)間同步協(xié)議的時(shí)間同步 精度可以達(dá)到毫秒級，通過外界一個(gè)精準(zhǔn)的時(shí)間源接收機(jī)，頂層的時(shí)間服精度可以達(dá)到毫秒級，通過外界一個(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í)間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTP NTP協(xié)議采用的是分層結(jié)構(gòu)，拓?fù)浣Y(jié)協(xié)議采

6、用的是分層結(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ù)器通過地球觀測衛(wèi)星地球觀測衛(wèi)星 或者或者位于科羅拉多的位于科羅拉多的WWV短波電臺短波電臺獲獲 得標(biāo)準(zhǔn)的得標(biāo)準(zhǔn)的UTC時(shí)間，其他層的時(shí)間服務(wù)時(shí)間，其他層的時(shí)間服務(wù) 器或者客戶機(jī)選擇一個(gè)或者多個(gè)上一層器或者客戶機(jī)選擇一個(gè)或者多個(gè)上一層 的時(shí)間服務(wù)器來同步本地時(shí)間，從而使的時(shí)間服務(wù)器來同步本地時(shí)間，從而使 整個(gè)

7、網(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ù)起源NTPNTP T1 T2 T3 T4 客戶端客戶端服務(wù)器服務(wù)器 1 2 21 112TT 234TT 21 2 )21()34(TTTT )34()12(TTTT 假定假定，可計(jì)算出：，可計(jì)算出： 假定客戶端時(shí)鐘比服務(wù)器時(shí)鐘快假定客戶端時(shí)鐘比服務(wù)器時(shí)鐘快 l時(shí)間同步技術(shù)起源時(shí)間同步技術(shù)起源N

8、TPNTP NTP協(xié)議 NTP協(xié)議層次型樹形結(jié)構(gòu)協(xié)議層次型樹形結(jié)構(gòu) UTC時(shí)間源 一級時(shí)間基準(zhǔn)服 務(wù)器 二級時(shí)間基準(zhǔn)服務(wù)器客戶端 一級時(shí)間基準(zhǔn)服 務(wù)器 二級時(shí)間基準(zhǔn)服務(wù)器二級時(shí)間基準(zhǔn)服務(wù)器 一級時(shí)間基準(zhǔn)服 務(wù)器 二級時(shí)間基準(zhǔn)服務(wù)器客戶端 NTPNTP不適合于不適合于WSNWSN 體積、計(jì)算能力和存儲空間存在限制體積、計(jì)算能力和存儲空間存在限制 目標(biāo)不同：局部最優(yōu)而非全局最優(yōu)目標(biāo)不同：局部最優(yōu)而非全局最優(yōu) l時(shí)間同步技術(shù)起源時(shí)間同步技術(shù)起源NTPNTP WSN同步算法與協(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) 廣播同步廣播同步 核心：

9、消除關(guān)鍵路徑引入核心：消除關(guān)鍵路徑引入 的誤差的誤差 構(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ù)測傳輸延遲不可預(yù)測 無線傳感器網(wǎng)絡(luò)中，時(shí)間同步技術(shù)的一個(gè)重要難題是報(bào)文傳無線傳感器網(wǎng)絡(luò)中，時(shí)間同步技術(shù)的一個(gè)重要難題是報(bào)文傳 輸延遲的不確定，由于處理器處理能力有限、網(wǎng)絡(luò)負(fù)載不確輸延遲的不

10、確定，由于處理器處理能力有限、網(wǎng)絡(luò)負(fù)載不確 定等因素的影響，延遲不能夠被精確地計(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ā)送

11、報(bào)文的時(shí)間，即從報(bào)文的第一個(gè)字節(jié)開：發(fā)送方發(fā)送報(bào)文的時(shí)間，即從報(bào)文的第一個(gè)字節(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í)間：接收方接收報(bào)文的時(shí)間。它和傳送時(shí)間完全相同，：接收方接收報(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è)施要求

12、節(jié)點(diǎn)體積盡量小，硬件設(shè)施要求節(jié)點(diǎn)體積盡量小， 盡量廉價(jià)，因此要求時(shí)間同步技術(shù)具有高能效的特點(diǎn)。盡量廉價(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ò)展后同步誤差不會超過誤時(shí)間同步技術(shù)必須保證網(wǎng)絡(luò)擴(kuò)展后同步誤差不會超過誤 差界限，并且能夠穩(wěn)定工作。差界限，并且能夠穩(wěn)定工作。 l時(shí)間同步技術(shù)關(guān)鍵問題時(shí)間同步技術(shù)關(guān)鍵問題 課程目錄課程目錄 4.2.14.2.1 4.2.24.2.2 時(shí)間同步模型時(shí)間同步模型 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 無線傳感器網(wǎng)絡(luò)時(shí)間同

13、步技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù) 4.24.2 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 發(fā)送者發(fā)送者-接收者同步模式：發(fā)送者發(fā)送帶有時(shí)間戳的同步包接收者同步模式

14、：發(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í)，忽略了無線信道的許多不確定因素的影響 。 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 4.2.14.2.1 時(shí)間同步模型時(shí)間同步模型 接收者接收者-接收者同步模式：多個(gè)接

15、收者利用發(fā)送者發(fā)送的同接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同 步包在若干接收者之間進(jìn)行同步，接收者步包在若干接收者之間進(jìn)行同步，接收者-接收者模式縮短了接收者模式縮短了 關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長而導(dǎo)致的不關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長而導(dǎo)致的不 準(zhǔn)確的傳輸延遲估計(jì)準(zhǔn)確的傳輸延遲估計(jì)。 課程目錄課程目錄 4.2.14.2.1 4.2.24.2.2 時(shí)間同步模型時(shí)間同步模型 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù) 4.24.2 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 2 2 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同

16、步協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 接收者接收者-接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同 步包在若干接收者之間進(jìn)行同步，接收者步包在若干接收者之間進(jìn)行同步，接收者-接收者模式縮短了接收者模式縮短了 關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長而導(dǎo)致的不關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長而導(dǎo)致的不 準(zhǔn)確的傳輸延遲估計(jì)準(zhǔn)確的傳輸延遲估計(jì)。 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步

17、協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 17/20 LTS機(jī)制 LTS應(yīng)用于多跳網(wǎng)絡(luò)應(yīng)用于多跳網(wǎng)絡(luò) 根根 節(jié)節(jié) 點(diǎn)點(diǎn) 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 集中式集中式 根根 節(jié)節(jié) 點(diǎn)點(diǎn) 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 分布式分布式 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 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í)間

18、 接收信標(biāo)分 組本地時(shí)間 調(diào)整 時(shí)間 接收者接收者：RBS Receiver NIC Sender Critical Path Time NIC Sender Receiver1 Critical Path Receiver2 RBS（Reference Broadcast Synchronization） 在RBS算法中，接收節(jié)點(diǎn)只需比較接收節(jié)點(diǎn)接收報(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í)間差的平 均值，這樣

19、就能在最大程度上消除非同時(shí)記錄的影響 RBS （Reference 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ò) A B 1 4 3 2 7 6 5 考慮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級，因此RBS算法的同步精度非常高，但RBS算法的

20、網(wǎng)絡(luò)開銷 比較大，對于單播域中的n個(gè)節(jié)點(diǎn)和m個(gè)參考廣播消息，RBS算法的復(fù)雜度為O(mn2)。 在圖示網(wǎng)絡(luò)中存在三個(gè)不同的單跳域A 、B和C，其中4號和7號節(jié)點(diǎn)處于兩個(gè)單 跳域的交界，4號節(jié)點(diǎn)可以同步A區(qū)域和 C區(qū)域的時(shí)間，7號節(jié)點(diǎn)可以同步B區(qū)域 和C區(qū)域的時(shí)間，根據(jù)這兩個(gè)節(jié)點(diǎn)我們 可以得到相鄰兩區(qū)域的時(shí)間轉(zhuǎn)換關(guān)系， 從而達(dá)到全網(wǎng)的時(shí)間同步。 9/20 RBS同步機(jī)制 RBS同步機(jī)制總結(jié)： RBS機(jī)制利用信道的廣播特性來同步接收節(jié)點(diǎn)時(shí)間，去 除了時(shí)間同步誤差中所有發(fā)送節(jié)點(diǎn)引入的部分。 通過多次廣播分組獲取平均值，能夠提高RBS的時(shí)間同 步精度。 對于單個(gè)廣播域內(nèi)的n個(gè)節(jié)點(diǎn)和m個(gè)廣播消息，RBS

21、機(jī) 制的復(fù)雜度為O（mn）。 用于多跳網(wǎng)絡(luò)的RBS機(jī)制需要依賴有效的分簇方法，保 證簇之間有共同節(jié)點(diǎn)以便進(jìn)行簇間時(shí)間同步 10/20 RBS同步機(jī)制 后同步思想：后同步思想： 通常情況下節(jié)點(diǎn)的時(shí)間不用同步，只有監(jiān)測到一個(gè)事件發(fā)通常情況下節(jié)點(diǎn)的時(shí)間不用同步，只有監(jiān)測到一個(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)，同步

22、它們監(jiān)測到的事件發(fā)生時(shí)間。瞬時(shí)的時(shí)間參考點(diǎn)，同步它們監(jiān)測到的事件發(fā)生時(shí)間。 后同步機(jī)制能夠?qū)崿F(xiàn)后同步機(jī)制能夠?qū)崿F(xiàn)瞬時(shí)的節(jié)點(diǎn)間時(shí)間同步瞬時(shí)的節(jié)點(diǎn)間時(shí)間同步，但是受限于，但是受限于 廣播信標(biāo)分組的傳輸范圍，它不適應(yīng)于長距離或長時(shí)間通廣播信標(biāo)分組的傳輸范圍，它不適應(yīng)于長距離或長時(shí)間通 信的時(shí)間同步。信的時(shí)間同步。 后同步機(jī)制能夠提供精確的局部空間范圍的時(shí)間同步。后同步機(jī)制能夠提供精確的局部空間范圍的時(shí)間同步。 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 TPSN （ Timing-sync Protocol for Sensor Networks ） TPSN時(shí)間同步協(xié)議思想 TPSN （ Ti

23、ming-sync Protocol for Sensor Networks ） Sunday, July 04, 2021 1、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)分級后（根節(jié)點(diǎn)是0級，累加），每個(gè)節(jié)點(diǎn)同上一 級的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終與根節(jié)點(diǎn)同步 5、節(jié)點(diǎn)對之間的同步采用發(fā)送者-接收者同步機(jī)制（RBS） 11/20 TPSN時(shí)間同步協(xié)議 根 節(jié) 點(diǎn) 1 1 2 1 2 1 2 2 2 2 2

24、 層次發(fā)現(xiàn)階段層次發(fā)現(xiàn)階段 （廣播級別發(fā)現(xiàn)分組）（廣播級別發(fā)現(xiàn)分組） 根 節(jié) 點(diǎn) 1 1 2 1 2 1 2 2 2 2 2 同步階段同步階段 （廣播時(shí)間同步分組）（廣播時(shí)間同步分組） 每個(gè)傳感器節(jié)點(diǎn)都有唯一的標(biā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è)級別，根節(jié)點(diǎn)為0級， 第i級的節(jié)點(diǎn)至少能夠與一個(gè)第（i-1）級得節(jié)點(diǎn)通信 網(wǎng)絡(luò)部署后，由根節(jié)點(diǎn)廣播級別發(fā)現(xiàn)分組來啟動層次發(fā)現(xiàn)階段，級別 發(fā)現(xiàn)分組包含節(jié)點(diǎn)的ID和級別 鄰

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

26、第（i-1）級的一個(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í)間同步分組啟動同步階段 第1級節(jié)點(diǎn)收到分組后，各自分別等待一段隨機(jī)時(shí)間，再通過與根節(jié) 點(diǎn)交換消息同步到根節(jié)點(diǎn) 第2級節(jié)點(diǎn)偵聽到第1級節(jié)點(diǎn)的交換消息后，等待一段隨機(jī)時(shí)間，再與 它記錄的上一級別的節(jié)點(diǎn)交換消息進(jìn)行同步，網(wǎng)絡(luò)中的節(jié)點(diǎn)依次與上 一級節(jié)點(diǎn)同步，最終都同步到根節(jié)點(diǎn) 等待一段隨機(jī)時(shí)間是為了保證該級節(jié)點(diǎn)在上一級節(jié)點(diǎn)同步完成后才啟 動消息交換 TPSN協(xié)議過程 第二階段第二階段 同步階段（同步階段（Synchronization PhaseSynchronization Phase）

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

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

29、單直觀 單報(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） 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)t

30、0 接收 前導(dǎo)碼 接收 數(shù)據(jù) 發(fā)送 ACK 接收 處理 時(shí)標(biāo)t1時(shí)標(biāo)t2 n=發(fā)送信息位個(gè)數(shù) t=發(fā)送每比特位需要的時(shí)間 前導(dǎo)碼和起始字符的發(fā)送時(shí)間=nt 接收處理延遲=t2-t1 忽略無線信號的傳播延遲 接收節(jié)點(diǎn)時(shí)鐘為t0+nt+（t2-t1） 15/20 DMTS同步機(jī)制 vDMTS機(jī)制在多跳網(wǎng)絡(luò)中采用機(jī)制在多跳網(wǎng)絡(luò)中采用層次型層次型分級結(jié)分級結(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ù)少

31、。 能夠與外部世界標(biāo)準(zhǔn)時(shí)間同步，但同步精度相對較低。 DMTS在實(shí)現(xiàn)復(fù)雜度、能量高效與同步精度之間進(jìn)行了折中，能夠應(yīng) 用在對時(shí)間同步要求不是非常高的網(wǎng)絡(luò)中。 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 MAC層時(shí)間戳技術(shù) 和平臺直接相關(guān)，書中給出了在Mica2平臺下的實(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） (

32、6) HRTS(6) HRTS（Hierarchy Referencing Time Hierarchy Referencing Time Synchronization ProtocolSynchronization Protocol） TPSN基于雙向報(bào)文交換，因此同步精度高 TPSN本質(zhì)上是對同步，因此全網(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 Re

33、ferencing 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ì)上是接收者- -接收者同步 HRTSHRTS（Hierarchy Referencing Time Hierarchy Referencing Time Synchronization ProtocolSynchronization Protocol） （7 7）GCSGCS（Global Clock SynchronizationGlobal Clock Synchroniza

34、tion） 節(jié)點(diǎn)遍歷模式 聚類分層模式 擴(kuò)散模式 GCS：節(jié)點(diǎn)遍歷模式 游走階段：記錄游走的出發(fā)和到達(dá)時(shí)間 時(shí)間校正階段：根據(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í)間的平均值上 4.2.24.2.2 時(shí)間同步協(xié)議時(shí)間同步協(xié)議 新型同步機(jī)制？新型同步機(jī)制？ 新型同步機(jī)制新型同步機(jī)制 基于報(bào)文交換的同步機(jī)制面臨著挑戰(zhàn) 同步精度問題 可擴(kuò)展性問題 新型同步機(jī)制 螢火蟲同步 協(xié)作同步 兩個(gè)概念 同時(shí)性與同步性