1、第七章 時(shí)間同步技術(shù) l 時(shí)間同步技術(shù)概述l 時(shí)間同步技術(shù)研究現(xiàn)狀與發(fā)展l 時(shí)間同步技術(shù)關(guān)鍵問題l 傳統(tǒng)時(shí)間同步技術(shù)l 新型時(shí)間同步技術(shù)第七章 時(shí)間同步技術(shù)時(shí)間同步時(shí)間同步：使網(wǎng)絡(luò)中所有節(jié)點(diǎn)的時(shí)間保持一致，按照網(wǎng)絡(luò)應(yīng)用的深度可以分為三種不同的情況：u第一種第一種：時(shí)序確定，判斷事件發(fā)生的先后順序，對(duì)本地時(shí)間的要求比較低，只需要知道本節(jié)點(diǎn)與其余節(jié)點(diǎn)的相對(duì)時(shí)間即可u第二種第二種：相對(duì)同步，節(jié)點(diǎn)維護(hù)自己的本地時(shí)鐘，周期性地獲取其鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的時(shí)鐘偏移，實(shí)現(xiàn)本節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的時(shí)間同步u第三種第三種：絕對(duì)同步，所有節(jié)點(diǎn)的本地時(shí)間嚴(yán)格同步，等同于標(biāo)準(zhǔn)時(shí)間，這種情況對(duì)節(jié)點(diǎn)的要求最高，因此實(shí)現(xiàn)也最為復(fù)雜時(shí)

2、間同步的參考時(shí)間來源也有兩種情況：u外同步外同步：標(biāo)準(zhǔn)參考時(shí)間來自于外部u內(nèi)同步內(nèi)同步：參考時(shí)間來自于網(wǎng)絡(luò)內(nèi)部某個(gè)節(jié)點(diǎn)的時(shí)間第七章 時(shí)間同步技術(shù)l 時(shí)間同步技術(shù)概述無線傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議必須要解決三個(gè)方面的問題：同步的誤差要盡可能地小，這樣才能保證整個(gè)網(wǎng)絡(luò)間節(jié)點(diǎn)應(yīng)用的正常進(jìn)行因?yàn)闊o線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的電池不可替換，因此協(xié)議要盡可能地簡單，功耗要低，以盡可能地延長網(wǎng)絡(luò)的生命周期具有可擴(kuò)展性，隨著無線傳感器網(wǎng)絡(luò)規(guī)模的擴(kuò)大，時(shí)間同步協(xié)議要同樣有效第七章 時(shí)間同步技術(shù)l 時(shí)間同步技術(shù)概述第七章 時(shí)間同步技術(shù)l 時(shí)間同步技術(shù)概述時(shí)間同步的兩個(gè)重要的時(shí)間參數(shù)：時(shí)鐘偏移時(shí)鐘偏移：在真實(shí)時(shí)刻t時(shí)定義時(shí)鐘偏移

3、為c(t)t，即本地時(shí)間與真實(shí)時(shí)間的差值。時(shí)鐘漂移時(shí)鐘漂移：在真實(shí)時(shí)刻t時(shí)定義時(shí)鐘漂移為(t)=r(t)1，即本地時(shí)間變化速率與1的差值。在節(jié)點(diǎn)的兩種時(shí)間計(jì)數(shù)方式：硬件計(jì)數(shù)硬件計(jì)數(shù)模式：模式：即利用晶振來實(shí)現(xiàn)時(shí)間的計(jì)數(shù)軟件時(shí)鐘軟件時(shí)鐘模式：模式：采用虛擬的軟件時(shí)鐘來實(shí)現(xiàn)時(shí)鐘的計(jì)數(shù)1硬件時(shí)鐘模硬件時(shí)鐘模式式在硬件系統(tǒng)的時(shí)鐘計(jì)數(shù)中，計(jì)算時(shí)間的一個(gè)重要的公式是：式中，w(t)是晶振的角頻率，k是依賴于晶體物理特性的常量，t是真實(shí)時(shí)間變量， c(t)是當(dāng)真實(shí)時(shí)間為t時(shí)節(jié)點(diǎn)的本地時(shí)間。2軟件時(shí)鐘軟件時(shí)鐘模式模式在軟件時(shí)鐘模型中，也存在一個(gè)用于記錄時(shí)鐘脈沖的計(jì)數(shù)器，軟件時(shí)鐘模型與硬件模型不同，它不直接修改

4、本地時(shí)鐘，而是根據(jù)本地時(shí)鐘h(t)與真實(shí)時(shí)間的關(guān)系來換算成真實(shí)時(shí)間的函數(shù)c(h(t)。c(h(t)=t0+h(t)h(t0)就是一個(gè)最簡單的虛擬軟件時(shí)鐘的例子，實(shí)際應(yīng)用中，軟件時(shí)鐘還要考慮到時(shí)鐘漂移對(duì)時(shí)鐘的影響，因此更加復(fù)雜。第七章 時(shí)間同步技術(shù)l 時(shí)間同步技術(shù)概述到目前為止，時(shí)間同步技術(shù)的研究已經(jīng)有了30年之久，最早的時(shí)間同步機(jī)制是美國一所大學(xué)提出的網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）。NTP協(xié)議的時(shí)間同步精度可以達(dá)到毫秒級(jí)，通過外界一個(gè)精準(zhǔn)的時(shí)間源接收機(jī)，頂層的時(shí)間服務(wù)器可以獲得高精度的參考時(shí)間，并向全網(wǎng)內(nèi)提供統(tǒng)一的時(shí)間服務(wù)。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)研究現(xiàn)狀與發(fā)展NTPNTP協(xié)議采用的是分層結(jié)

5、構(gòu)，拓?fù)浣Y(jié)構(gòu)如圖所示，整個(gè)NTP協(xié)議分為三層結(jié)構(gòu)，其中A1、A2、A3為頂層的時(shí)間服務(wù)器，B1、B2、B3為第二層時(shí)間服務(wù)器，其余均為客戶機(jī)。第一層時(shí)間服務(wù)器通過GPRS或者廣播網(wǎng)絡(luò)等方式來獲得標(biāo)準(zhǔn)的UTC時(shí)間，其他層的時(shí)間服務(wù)器或者客戶機(jī)選擇一個(gè)或者多個(gè)上一層的時(shí)間服務(wù)器來同步本地時(shí)間，從而使整個(gè)網(wǎng)絡(luò)所有服務(wù)器和客戶機(jī)時(shí)間同步。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)研究現(xiàn)狀與發(fā)展NTP通過上層服務(wù)器的標(biāo)準(zhǔn)參考時(shí)間，服務(wù)器利用一個(gè)閉環(huán)控制系統(tǒng)來調(diào)整自己的本地時(shí)間第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)研究現(xiàn)狀與發(fā)展NTP1973年，美國國防部為了實(shí)現(xiàn)軍事部門對(duì)海陸空設(shè)施進(jìn)行高精度導(dǎo)航和定位，建立了一種新

6、的網(wǎng)絡(luò)系統(tǒng)GPS網(wǎng)絡(luò)系統(tǒng)，該系統(tǒng)成為繼阿波羅登月計(jì)劃和航天飛機(jī)計(jì)劃之后的第三項(xiàng)龐大空間計(jì)劃，它從根本上解決了人類在地球上的導(dǎo)航和定位問題，在軍事和工農(nóng)業(yè)等領(lǐng)域得到了廣泛的應(yīng)用。GPS系統(tǒng)由三個(gè)部分組成：空間衛(wèi)星空間衛(wèi)星、地面監(jiān)控地面監(jiān)控和用戶終端用戶終端。由于GPS信號(hào)的穿透性比較差，為了接收到GPS的信號(hào)，GPS天線必須安裝在空曠的室外，并且要求沒有高大阻擋物體，加上接收機(jī)功耗比較大，因此不適宜在無線傳感器網(wǎng)絡(luò)中應(yīng)用。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)研究現(xiàn)狀與發(fā)展GPS在設(shè)計(jì)無線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議時(shí)，需要滿足以下幾點(diǎn)要求： 能量有限 可擴(kuò)展 穩(wěn)定性第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)關(guān)

7、鍵問題1、傳輸延遲不可預(yù)測(cè)傳輸延遲不可預(yù)測(cè)無線傳感器網(wǎng)絡(luò)中，時(shí)間同步技術(shù)的一個(gè)重要難題是報(bào)文傳輸延遲的不確定，由于處理器處理能力有限、網(wǎng)絡(luò)負(fù)載不確定等因素的影響，延遲不能夠被精確地計(jì)算出來；另外傳輸延遲比要求的時(shí)間同步的精度要大得多。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)關(guān)鍵問題影響時(shí)間同步的傳輸時(shí)延發(fā)送時(shí)間發(fā)送時(shí)間：發(fā)送方用于組裝并將報(bào)文換交給發(fā)送方MAC層的時(shí)間。訪問時(shí)間訪問時(shí)間：指在發(fā)送方MAC層從獲得報(bào)文后到獲取無線信道發(fā)送權(quán)的等待時(shí)間。傳送時(shí)間傳送時(shí)間：發(fā)送方發(fā)送報(bào)文的時(shí)間，即從報(bào)文的第一個(gè)字節(jié)開始發(fā)送到發(fā)送完最后一個(gè)字節(jié)的時(shí)間。傳播時(shí)間傳播時(shí)間：報(bào)文從發(fā)送方以電磁波的形式傳送到接收方所

8、花費(fèi)的時(shí)間。接收時(shí)間接收時(shí)間：接收方接收?qǐng)?bào)文的時(shí)間。它和傳送時(shí)間完全相同，具有確定性。接受時(shí)間接受時(shí)間：用于處理接收到的報(bào)文的時(shí)間。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)關(guān)鍵問題第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)關(guān)鍵問題2高能效高能效無線傳感器網(wǎng)絡(luò)的軟/硬件設(shè)施要求節(jié)點(diǎn)體積盡量小，盡量廉價(jià)，因此要求時(shí)間同步技術(shù)具有高能效的特點(diǎn)。3可擴(kuò)展、健壯可擴(kuò)展、健壯采用逐跳的時(shí)間同步機(jī)制，因此隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，時(shí)間同步技術(shù)必須保證網(wǎng)絡(luò)擴(kuò)展后同步誤差不會(huì)超過誤差界限，并且能夠穩(wěn)定工作。第七章 時(shí)間同步技術(shù)l時(shí)間同步技術(shù)關(guān)鍵問題發(fā)送者發(fā)送者-接收者同步模式接收者同步模式：發(fā)送者發(fā)送帶有時(shí)間戳的同步包給接收者，同

9、步接收者的時(shí)間，這種模式的缺陷是不能夠準(zhǔn)確地估計(jì)算出報(bào)文的傳輸延遲，精度不高，通過單個(gè)報(bào)文的傳輸不能夠準(zhǔn)確地估算傳輸延遲。主要代表協(xié)議為DTMS協(xié)議。接收者接收者-接收者同步模式接收者同步模式：多個(gè)接收者利用發(fā)送者發(fā)送的同步包在若干接收者之間進(jìn)行同步，接收者-接收者模式縮短了關(guān)鍵路徑，避免發(fā)送者到接收者的關(guān)鍵路徑過長而導(dǎo)致的不準(zhǔn)確的傳輸延遲估計(jì)，主要代表協(xié)議為RBS協(xié)議第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)同步機(jī)制第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)同步機(jī)制DMTS協(xié)議協(xié)議： 一種簡單的同步技術(shù)，發(fā)送者通過發(fā)送單個(gè)廣播報(bào)文，同步一跳內(nèi)的所有節(jié)點(diǎn)。該協(xié)議主要考慮報(bào)文的傳輸延遲，在設(shè)置本地時(shí)間時(shí)

10、，報(bào)文中嵌入的時(shí)間為發(fā)送時(shí)刻的本地時(shí)間加上傳輸延遲的時(shí)間。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)DMTSDTMS報(bào)文同步的傳輸過程：為了避免發(fā)送等待事件對(duì)本地時(shí)間的干擾，發(fā)為了避免發(fā)送等待事件對(duì)本地時(shí)間的干擾，發(fā)送方在檢測(cè)到信道空閑之后才在報(bào)文中嵌入發(fā)送時(shí)間送方在檢測(cè)到信道空閑之后才在報(bào)文中嵌入發(fā)送時(shí)間t0，根據(jù)無線傳感器通信協(xié)議規(guī)定，報(bào)文在發(fā)送之前需要先發(fā)送一定數(shù)量的前導(dǎo)碼和同步字，根據(jù)發(fā)送速率我們可以知道單個(gè)比特的發(fā)送時(shí)間為t。而接收者在同步字結(jié)束的時(shí)候后，記錄下此時(shí)的本地時(shí)間t1，并在即將調(diào)整自己的本地時(shí)間之前記錄下此時(shí)的時(shí)刻t2，由此我們知道接收方的報(bào)文處理延遲為t2t1。接收者將自己

11、的時(shí)間改為t0+nt+t2t1，以達(dá)到與發(fā)送者之間的時(shí)間同步。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)DMTSDMTS同步協(xié)議是一種簡單靈活的同步技術(shù)，該算法網(wǎng)絡(luò)流量非常小，能量消耗也非常少，但是沒有考慮傳播延遲、編/解碼的影響，對(duì)時(shí)鐘漂移也沒有考慮，同步的精度不是很高，還有待進(jìn)一步的改進(jìn)。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)DMTS第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)RBS根據(jù)無線信道的廣播特性，發(fā)送者發(fā)送的消息對(duì)所有接收節(jié)點(diǎn)而言是同一個(gè)發(fā)送節(jié)點(diǎn)發(fā)送的，RBS算法利用這個(gè)優(yōu)勢(shì)來消除發(fā)送時(shí)間和訪問時(shí)間所造成的傳輸時(shí)間誤差，從而提高時(shí)間的同步精度。RBS同步機(jī)制的工作流程如下：假設(shè)有N個(gè)節(jié)點(diǎn)組

12、成的單跳網(wǎng)絡(luò)，1個(gè)發(fā)送節(jié)點(diǎn)，N1個(gè)接收節(jié)點(diǎn)，發(fā)送節(jié)點(diǎn)周期性地向接收節(jié)點(diǎn)發(fā)送參考報(bào)文，廣播域內(nèi)的接收節(jié)點(diǎn)都將收到該參考報(bào)文，并各自記錄收到該報(bào)文的時(shí)刻。接收者們通過交換本地時(shí)間戳信息，這樣這一組節(jié)點(diǎn)就可以計(jì)算出它們之間的時(shí)鐘偏差。RBS算法中廣播的時(shí)間同步消息與真實(shí)的時(shí)間戳信息并無多大關(guān)系，它也不關(guān)心準(zhǔn)確的發(fā)送和接收時(shí)間，而只關(guān)心報(bào)文傳輸?shù)牟钪?，RBS同步算法完全排除了發(fā)送時(shí)間和接收時(shí)間的干擾。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)RBS在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í)刻記錄本地

13、時(shí)間有關(guān)，為了減小時(shí)間同步的誤差，RBS采用了統(tǒng)計(jì)技術(shù)，同時(shí)廣播多個(gè)時(shí)間同步消息，求相互之間消息到達(dá)的時(shí)間差的平均值，這樣就能在最大程度上消除非同時(shí)記錄的影響另外對(duì)于節(jié)點(diǎn)間的時(shí)鐘漂移情況，RBS采用最小平方誤差的線性回歸方法，對(duì)從某時(shí)刻開始的節(jié)點(diǎn)間的時(shí)鐘偏移數(shù)據(jù)進(jìn)行線性擬合。考慮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ù)雜

14、度為O(mn2)。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)RBS在圖示網(wǎng)絡(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í)間同步。 接收者-接收者同步模式雖然消除了發(fā)送方的不確定性，但由于需要在若干節(jié)點(diǎn)中交換信息，通信開銷較大。S.Ganeriwal從另外一個(gè)角度來考慮問題：傳統(tǒng)的發(fā)送者-接收者同步協(xié)議的精確度低的根本原因在于單向報(bào)文不能夠準(zhǔn)確地估算出報(bào)文傳播延遲，基于報(bào)文傳輸?shù)膶?duì)稱性，采用雙向報(bào)文就能夠解決這個(gè)問題，獲得較高的

15、精確度，因此他提出了一種雙向報(bào)文交換協(xié)議TPSN。TPSN可以分為層次發(fā)現(xiàn)階段層次發(fā)現(xiàn)階段和時(shí)間同步時(shí)間同步兩個(gè)階段。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)TPSN1層次發(fā)現(xiàn)階段層次發(fā)現(xiàn)階段在網(wǎng)絡(luò)部署后，根節(jié)點(diǎn)首先廣播以使發(fā)現(xiàn)分組，啟動(dòng)層次發(fā)現(xiàn)階段。級(jí)別發(fā)現(xiàn)分組包含發(fā)送節(jié)點(diǎn)的ID和級(jí)別。根節(jié)點(diǎn)是0級(jí)節(jié)點(diǎn)，在根節(jié)點(diǎn)廣播域內(nèi)的節(jié)點(diǎn)收到根節(jié)點(diǎn)發(fā)送的分組后，將自己的級(jí)別設(shè)置為分組中的級(jí)別加1，即為第1級(jí)，然后將自己的級(jí)別和ID作為新的發(fā)現(xiàn)分組廣播出去。當(dāng)一個(gè)節(jié)點(diǎn)收到第i級(jí)節(jié)點(diǎn)的廣播分組后，記錄發(fā)送這個(gè)廣播分組的節(jié)點(diǎn)的ID，設(shè)置自己的級(jí)別為i+1。這個(gè)過程持續(xù)下去，直到網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)都具有一個(gè)級(jí)別為止

16、。如果節(jié)點(diǎn)已經(jīng)建立自己的級(jí)別，就忽略其他的級(jí)別發(fā)現(xiàn)分組。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)TPSN2時(shí)間同步階段時(shí)間同步階段層次結(jié)構(gòu)建立以后，根節(jié)點(diǎn)就會(huì)廣播時(shí)間同步分組，啟動(dòng)時(shí)間同步階段。第1級(jí)節(jié)點(diǎn)收到這個(gè)分組后。在等待一段隨機(jī)時(shí)間后，向根節(jié)點(diǎn)發(fā)送時(shí)間同步請(qǐng)求消息包，進(jìn)行同步過程，與此同時(shí)第2級(jí)節(jié)點(diǎn)會(huì)偵聽到第1級(jí)節(jié)點(diǎn)發(fā)送的時(shí)間同步請(qǐng)求消息包，第2級(jí)節(jié)點(diǎn)也開始自己的同步過程。這樣，時(shí)間同步就由根節(jié)點(diǎn)擴(kuò)散到整個(gè)網(wǎng)絡(luò)，最終完成全網(wǎng)的時(shí)間同步。建立層次之后，相鄰層次之間的節(jié)點(diǎn)通過雙向報(bào)文機(jī)制來進(jìn)行時(shí)間同步，假設(shè)節(jié)點(diǎn)A是第i層的節(jié)點(diǎn)，節(jié)點(diǎn)B是第i1層的節(jié)點(diǎn)，根據(jù)TPSN報(bào)文交換協(xié)議，我們規(guī)定T1和T

17、4為節(jié)點(diǎn)A的時(shí)間，T2和T3為節(jié)點(diǎn)B的時(shí)間，節(jié)點(diǎn)A在T1向節(jié)點(diǎn)B發(fā)送一個(gè)同步報(bào)文，節(jié)點(diǎn)B在收到該報(bào)文后，記錄下接收到該報(bào)文的時(shí)刻T2，并立刻向節(jié)點(diǎn)A發(fā)回一個(gè)應(yīng)答報(bào)文，將時(shí)刻T2和該報(bào)文的發(fā)送時(shí)刻T3嵌入到應(yīng)答報(bào)文中。當(dāng)節(jié)點(diǎn)A收到該應(yīng)答報(bào)文后，記錄下此時(shí)刻T4。我們假設(shè)當(dāng)節(jié)點(diǎn)A在T1時(shí)刻，A和B的時(shí)間偏移為，因?yàn)門1到T4兩個(gè)報(bào)文發(fā)送的時(shí)間非常短，我們可以認(rèn)為沒有變化，假設(shè)報(bào)文的傳輸延遲都是相同且對(duì)稱的，均為d，那么有T2=T1+d T4=T3+d，第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)TPSN這兩個(gè)方程聯(lián)立可解得：=(T2T1)(T4T3)/2， d=(T2T1)+(T4T3)/2在T4時(shí)刻，

18、節(jié)點(diǎn)A在本地時(shí)間上面加上一個(gè)偏移量，A和B就達(dá)到了同步。從雙向同步協(xié)議的同步過程中可以看出，在TPSN協(xié)議中，當(dāng)雙向報(bào)文的傳輸完全對(duì)稱時(shí)其精確度最高，即同步誤差最小。另外TPSN的同步誤差與雙向報(bào)文的傳輸延遲有關(guān)，延遲越短，同步誤差越小。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)TPSNFTSP（泛洪時(shí)間同步協(xié)議）也采用單個(gè)廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時(shí)間同步，采用同步時(shí)間數(shù)據(jù)的線性回歸方法估計(jì)時(shí)鐘漂移和偏差。綜合考慮了能量感知、可擴(kuò)展性、魯棒性、穩(wěn)定性和收斂性等方面的要求。FTSP算法實(shí)現(xiàn)步驟如下：（1）FTSP算法在完成SYNC字節(jié)發(fā)射后給時(shí)間同步消息標(biāo)記時(shí)間戳并將其發(fā)射出去。（2）接

19、收節(jié)點(diǎn)記錄SYNC字節(jié)最后到達(dá)時(shí)間，并計(jì)算位偏移。在收到完整的消息后，接收節(jié)點(diǎn)計(jì)算位偏移產(chǎn)生的時(shí)間延遲，這可通過偏移位數(shù)與接收速率得出。（3）接收節(jié)點(diǎn)計(jì)算與發(fā)送節(jié)點(diǎn)問的時(shí)鐘偏移量，然后調(diào)整本地時(shí)鐘和發(fā)送節(jié)點(diǎn)時(shí)間同步。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)FTSP1精度方面精度方面RBS協(xié)議協(xié)議：因?yàn)闊o線信道的廣播特性，使得發(fā)送節(jié)點(diǎn)發(fā)出的消息相對(duì)所有節(jié)點(diǎn)而言是同時(shí)發(fā)送到物理信道上的，相當(dāng)于將消息傳遞過程中兩項(xiàng)最不確定的時(shí)延被去除了，所以能夠得到較高的同步精度。TPSN協(xié)議協(xié)議：在網(wǎng)絡(luò)傳輸?shù)臅r(shí)延中，訪問時(shí)延的不確定性是最高的。為了提高兩個(gè)節(jié)點(diǎn)之間的時(shí)間同步精度，TPSN協(xié)議直接在MAC層記錄時(shí)間信

20、標(biāo)，這樣可以有效地消除發(fā)送時(shí)延、訪問時(shí)延、接收處理時(shí)延所帶來的時(shí)間同步誤差。并利用雙向消息交換計(jì)算消息的平均延遲，提高了時(shí)間同步的精度。FTSP協(xié)議協(xié)議：采用在MAC層記錄時(shí)間信標(biāo)，細(xì)分消息傳輸中的時(shí)間延遲對(duì)這些延遲進(jìn)行補(bǔ)償，利用線性回歸估計(jì)時(shí)間漂移等措施來降低時(shí)間同步誤差。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)比較2收斂性方面收斂性方面RBS協(xié)議協(xié)議：發(fā)送參考廣播的節(jié)點(diǎn)是預(yù)先選定的，其他節(jié)點(diǎn)接收到參考廣播消息后，就開始同步的過程。考慮到通信沖突，在幾個(gè)同步周期后，全網(wǎng)就可以達(dá)到時(shí)間同步，收斂時(shí)間也比較短。TPSN協(xié)議協(xié)議：這種同步方法的消息傳遞機(jī)制分為兩個(gè)過程，包括分層階段和同步階段，因此其

21、收斂時(shí)間較長。FTSP協(xié)議協(xié)議：該協(xié)議的根節(jié)點(diǎn)選擇過程是伴隨時(shí)間同步一起進(jìn)行的，根節(jié)點(diǎn)的選擇不會(huì)對(duì)收斂性造成影響，在幾個(gè)同步周期后，全網(wǎng)就能達(dá)到時(shí)間同步，收斂時(shí)間也比較短。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)比較3擴(kuò)展性方面擴(kuò)展性方面RBS協(xié)議協(xié)議：在全網(wǎng)達(dá)到同步后，新節(jié)點(diǎn)的加入不會(huì)影響到參考廣播節(jié)點(diǎn)的地位，也就不會(huì)對(duì)全網(wǎng)的結(jié)構(gòu)造成影響。但是，加入新的參考廣播節(jié)點(diǎn)會(huì)使得情況變得復(fù)雜，必須考慮處于不同廣播域內(nèi)的節(jié)點(diǎn)達(dá)到同步的問題。對(duì)于多跳網(wǎng)絡(luò)的RBS協(xié)議需要依賴有效的分簇方法，保證簇之間具有共同的節(jié)點(diǎn)，以便簇間進(jìn)行時(shí)間同步。TPSN協(xié)議協(xié)議：從分層過程可以看出，新節(jié)點(diǎn)加入后會(huì)對(duì)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)造

22、成很大的影響，應(yīng)此，該協(xié)議的擴(kuò)展性很差，這也是這個(gè)協(xié)議最大的缺點(diǎn)之一。FTSP協(xié)議協(xié)議：如果加入的是ID號(hào)最小的節(jié)點(diǎn)，該節(jié)點(diǎn)首先使自己與網(wǎng)絡(luò)達(dá)到同步，然后再進(jìn)行根節(jié)點(diǎn)選擇，不會(huì)影響網(wǎng)絡(luò)時(shí)間同步。如果不是ID號(hào)最小的節(jié)點(diǎn)，該節(jié)點(diǎn)只需要進(jìn)行時(shí)間同步并廣播時(shí)間同步消息。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)比較4魯棒性方面魯棒性方面RBS協(xié)議協(xié)議：由RBS協(xié)議的同步原理可以看出，節(jié)點(diǎn)失效或網(wǎng)絡(luò)通信故障不會(huì)破壞整個(gè)拓?fù)浣Y(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都有大量的冗余消息來保證時(shí)間同步。但是參考節(jié)點(diǎn)失效就會(huì)影響到該節(jié)點(diǎn)廣播域內(nèi)所有節(jié)點(diǎn)的同步。該協(xié)議具有較好的魯棒性。TPSN協(xié)議協(xié)議：當(dāng)某個(gè)節(jié)點(diǎn)失效，該節(jié)點(diǎn)以下的節(jié)點(diǎn)就有可能

23、接收不到時(shí)間同步消息，這樣就會(huì)造成連鎖反應(yīng)，影響到該節(jié)點(diǎn)所有的后續(xù)節(jié)點(diǎn)的時(shí)間同步。全網(wǎng)的時(shí)間同步會(huì)受到個(gè)別節(jié)點(diǎn)的影響，魯棒性很差。FTSP協(xié)議協(xié)議：如果是根節(jié)點(diǎn)失效，那么其他節(jié)點(diǎn)就會(huì)開始根節(jié)點(diǎn)選擇的過程，重新選出一個(gè)根節(jié)點(diǎn)，這在段時(shí)期內(nèi)會(huì)破壞時(shí)間同步，但全網(wǎng)很快就能重新達(dá)到同步。如果是其他節(jié)點(diǎn)失效，由于大量冗余消息的存在，個(gè)別節(jié)點(diǎn)不會(huì)影響全網(wǎng)時(shí)間同步。FTSP協(xié)議也具有良好的魯棒性。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)比較5能耗方面能耗方面可以利用網(wǎng)絡(luò)中的節(jié)點(diǎn)在一次時(shí)間同步中平均接收和發(fā)送消息的次數(shù)來簡單的估計(jì)時(shí)間同步協(xié)議的能耗。RBS協(xié)議協(xié)議：要實(shí)現(xiàn)兩個(gè)節(jié)點(diǎn)之間的時(shí)間同步，節(jié)點(diǎn)需要接收一次

24、廣播消息，然后再交換一次時(shí)間同步消息，平均需要2次消息發(fā)送和3次消息接收。協(xié)議的能量消耗較大。TPSN協(xié)議協(xié)議：由于這個(gè)方法采用的是類客戶/服務(wù)器模式，所以實(shí)現(xiàn)一次時(shí)間同步，節(jié)點(diǎn)平均需要2次消息發(fā)送和2次消息接收，協(xié)議的能量消耗相對(duì)較小。FTSP協(xié)議協(xié)議：在該協(xié)議中，節(jié)點(diǎn)接收到時(shí)間同步消息后，使得節(jié)點(diǎn)本地時(shí)間與全局時(shí)間達(dá)到同步，然后形成新的時(shí)間同步消息并發(fā)送出去。每次同步，節(jié)點(diǎn)平均需要1次消息發(fā)送和1次消息接收，協(xié)議的能量消耗是最小的。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)比較傳統(tǒng)的無線傳感器網(wǎng)絡(luò)時(shí)間同步機(jī)制的研究已經(jīng)非常成熟，實(shí)用性也非常強(qiáng)，主要應(yīng)用在單跳網(wǎng)絡(luò)中，同步誤差在Mica2平臺(tái)上已

25、經(jīng)達(dá)到幾至十幾微秒的量級(jí)，同步功耗也較低，能夠滿足大多數(shù)應(yīng)用場(chǎng)合的需要。然而，當(dāng)這些時(shí)間同步協(xié)議被擴(kuò)展到多跳網(wǎng)絡(luò)時(shí)，目前普遍采取的方法是首先按照節(jié)點(diǎn)之間的通信連接關(guān)系建立起一定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，在該拓?fù)浣Y(jié)構(gòu)上，按照時(shí)間同步協(xié)議的約定，未同步節(jié)點(diǎn)和所選定的已同步節(jié)點(diǎn)之間通過交換含時(shí)間信息的同步報(bào)文，從而間接間接地實(shí)現(xiàn)與時(shí)間基準(zhǔn)節(jié)點(diǎn)之間的同步。這種同步機(jī)制的特點(diǎn)在于：除時(shí)間基準(zhǔn)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)外，其余節(jié)點(diǎn)并不能直接和時(shí)間基準(zhǔn)節(jié)點(diǎn)同步。鑒于它們與傳統(tǒng)的因特網(wǎng)時(shí)間同步協(xié)議（Network Time Protocol，NTP）在該特點(diǎn)上的相似性，故將它們稱為無線傳感器網(wǎng)絡(luò)的傳統(tǒng)時(shí)間同步協(xié)議。第七章 時(shí)間同步

26、技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)分析由于傳統(tǒng)時(shí)間同步協(xié)議在體系結(jié)構(gòu)上的限制，節(jié)點(diǎn)不能直接和時(shí)間基準(zhǔn)節(jié)點(diǎn)同步而只能和與時(shí)間基準(zhǔn)節(jié)點(diǎn)存在同步誤差的節(jié)點(diǎn)進(jìn)行同步，因此必將出現(xiàn)節(jié)點(diǎn)的同步誤差隨著其離時(shí)間基準(zhǔn)節(jié)點(diǎn)跳距（Hop Distance）的增加而增加的現(xiàn)象，即出現(xiàn)了同步誤差的累積同步誤差的累積。理論分析和一些實(shí)際實(shí)驗(yàn)表明，在這些傳統(tǒng)的時(shí)間同步協(xié)議下，即使在最好的情況下，節(jié)點(diǎn)的同步誤差至少與其跳距的平方根呈正比。隨著無線傳感器網(wǎng)絡(luò)的發(fā)展，同步誤差累積問題將越來越嚴(yán)重：u一方面由于傳感器節(jié)點(diǎn)體積的不斷減小，使得節(jié)點(diǎn)的單跳傳播距離減小u另一方面由于網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大使得網(wǎng)絡(luò)直徑不斷增加這兩個(gè)因素均會(huì)導(dǎo)致平均節(jié)點(diǎn)跳

27、距的增加，使得同步誤差的累積現(xiàn)象更加嚴(yán)重。這對(duì)大規(guī)模無線傳感器網(wǎng)絡(luò)的應(yīng)用提出了挑戰(zhàn)。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同步技術(shù)分析傳統(tǒng)無線傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議還面臨著可擴(kuò)展性問題可擴(kuò)展性問題的挑戰(zhàn)：u傳統(tǒng)的時(shí)間同步協(xié)議在同步之前總是力圖建立起網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而把網(wǎng)絡(luò)中的所有節(jié)點(diǎn)有機(jī)地組織起來，u當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，這是完全可行的，但當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，由于無線傳輸?shù)牟环€(wěn)定性以及節(jié)點(diǎn)工作的動(dòng)態(tài)性，只有頻繁地進(jìn)行拓?fù)涓虏拍芨櫷負(fù)涞淖兓這一方面對(duì)于本已非常有限的網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)電能供應(yīng)來說是不可想象的，另一方面把網(wǎng)絡(luò)拓?fù)渚S護(hù)的繁重工作交給時(shí)間同步協(xié)議來解決也并不合適。第七章 時(shí)間同步技術(shù)l傳統(tǒng)時(shí)間同

28、步技術(shù)分析兩個(gè)新的時(shí)間同步技術(shù)試圖解決傳統(tǒng)時(shí)間同步技術(shù)中的同步積累誤差和可擴(kuò)展性問題：u協(xié)作同步技術(shù)協(xié)作同步技術(shù)u螢火蟲同步技術(shù)螢火蟲同步技術(shù)盡管目前這兩種技術(shù)由于存在較多的假設(shè)，絕大多數(shù)實(shí)驗(yàn)還停留在仿真的階段，但它們確實(shí)不失為解決無線傳感器網(wǎng)絡(luò)時(shí)間同步的新穎方法，可能會(huì)把無線傳感器網(wǎng)絡(luò)時(shí)間同步推入一個(gè)新的研究階段。需要說明的是，傳統(tǒng)時(shí)間同步協(xié)議的目的為了實(shí)現(xiàn)節(jié)點(diǎn)時(shí)間的一致性，即達(dá)到同時(shí)性；而新型同步技術(shù)則是為了實(shí)現(xiàn)節(jié)點(diǎn)（或個(gè)體）之間的同步性（Synchrony），即使節(jié)點(diǎn)的某些周期性動(dòng)作具有相同的周期和相位。同時(shí)性和同步性在一定程度上可以看做兩個(gè)等價(jià)的概念，節(jié)點(diǎn)的時(shí)間完全一致，則它們自然可以

29、生成具有相同周期和相位的動(dòng)作；而節(jié)點(diǎn)的動(dòng)作具有同步性，若以同步周期為基本時(shí)間單位，也就達(dá)到了節(jié)點(diǎn)間的同時(shí)性。第七章 時(shí)間同步技術(shù)l新型時(shí)間同步技術(shù)協(xié)作同步的具體過程：時(shí)間基準(zhǔn)節(jié)點(diǎn)按照相等的時(shí)間間隔發(fā)出m個(gè)同步脈沖，這m個(gè)脈沖的發(fā)送時(shí)刻被其一跳鄰居節(jié)點(diǎn)接收并保存，隨后這些鄰居節(jié)點(diǎn)根據(jù)最近的m個(gè)脈沖的發(fā)送時(shí)刻估計(jì)估計(jì)出時(shí)間基準(zhǔn)節(jié)點(diǎn)的第m+1個(gè)同步脈沖的發(fā)送時(shí)刻，并在該時(shí)刻與時(shí)間基準(zhǔn)節(jié)點(diǎn)同時(shí)發(fā)出同步脈沖。由于信號(hào)的疊加，因此復(fù)合的同步脈沖復(fù)合的同步脈沖可以到達(dá)更遠(yuǎn)的范圍。如此重復(fù)下去，最終網(wǎng)內(nèi)所有節(jié)點(diǎn)都達(dá)到了同步，如圖所示：第七章 時(shí)間同步技術(shù)l新型時(shí)間同步技術(shù)協(xié)作同步螢火蟲同步算法是目前人們解決群同步問題的最新方法，其基本思想來源于仿生學(xué)中的螢火蟲同步發(fā)光現(xiàn)象。1