TPSN時(shí)間同步算法研究PPT課件

1、.,1,TPSN時(shí)間同步算法研究,.,2,CONTENTS,目 錄,WSN時(shí)間同步概述,TPSN時(shí)間同步算法,一種基于優(yōu)化拓?fù)涞臅r(shí)間同步算法N-TPSN,.,3,01,WSN時(shí)間同步概述,.,4,WSN時(shí)間同步概述,概念： 各個(gè)節(jié)點(diǎn)定期或不定期與其他節(jié)點(diǎn)交換本地時(shí)鐘信息，并在協(xié)議或算法控制下調(diào)整本地時(shí)鐘，實(shí)現(xiàn)全局時(shí)間一致的過(guò)程。,WSN為何需要時(shí)間同步： 不同節(jié)點(diǎn)晶體振蕩不同，存在累計(jì)誤差； 受能量、存儲(chǔ)、帶寬限制； 分布式系統(tǒng)，要求節(jié)點(diǎn)必須實(shí)現(xiàn)同步，不同系統(tǒng)要求程度不同。,時(shí)間同步要解決的問(wèn)題： 保證同步的精度； 盡量小的功耗； 保證網(wǎng)絡(luò)的可擴(kuò)展性。,.,5,WSN時(shí)間同步概述,時(shí)間同步的誤

2、差來(lái)源,晶體振蕩 不同節(jié)點(diǎn)的晶體振蕩器間存在誤差，并且也會(huì)受到環(huán)境影響，這一誤差會(huì)隨時(shí)間累積。,成本、資源 由于WSN資源受限，通信信道質(zhì)量不佳時(shí)；節(jié)點(diǎn)密度大時(shí)，易造成延遲和出錯(cuò)，導(dǎo)致時(shí)間誤差。,同步協(xié)議 需在性能和開(kāi)銷間取得平衡，即用較小的通信代價(jià)取得較好的同步效果。,協(xié)議執(zhí)行 信道出錯(cuò)，導(dǎo)致部分節(jié)點(diǎn)不能被同步，影響網(wǎng)絡(luò)的整體時(shí)間同步情況。,.,6,WSN時(shí)間同步概述,時(shí)間同步算法的分類（1）,（1）基于接收者接收者（Receiver-Receiver）的時(shí)間同步,基于接收者接收者的時(shí)間同步算法，主要利用了無(wú)線信道的廣播屬性。 主要原理是引入一個(gè)節(jié)點(diǎn)作為輔助節(jié)點(diǎn)，由該節(jié)點(diǎn)廣播一個(gè)參考分組，在

3、廣播域內(nèi)的一組 接收節(jié)點(diǎn)接收到這個(gè)參考分組，通過(guò)比較各自接收到消息的的本地時(shí)間，實(shí)現(xiàn)它們之間的 時(shí)間同步。 由于其他節(jié)點(diǎn)只需要監(jiān)聽(tīng)信息而不需要同步到參考節(jié)點(diǎn)，該類型算法的優(yōu)點(diǎn)在于可以避免 發(fā)送節(jié)點(diǎn)時(shí)延的影響，但缺點(diǎn)在于信息交換次數(shù)較多，能耗較大。 該種類型的代表性算法是 RBS 算法。,.,7,WSN時(shí)間同步概述,時(shí)間同步算法的分類（2）,（2）基于發(fā)送者接收者（Sender-Receiver）的雙向時(shí)間同步,基于發(fā)送者接收者的雙向時(shí)間同步算法，類似于傳統(tǒng)Internet 中的 NTP協(xié)議，即基 于客戶機(jī)服務(wù)器架構(gòu)。 待同步節(jié)點(diǎn)發(fā)送時(shí)間同步請(qǐng)包，基準(zhǔn)節(jié)點(diǎn)接收到這一同步請(qǐng)求后反饋?zhàn)陨懋?dāng)前時(shí)間，待

4、 同步節(jié)點(diǎn)接收到反饋的信息后計(jì)算時(shí)間偏差并予以調(diào)整，完成時(shí)間同步。 該類型算法優(yōu)點(diǎn)在于同步的高精度，而缺點(diǎn)就是節(jié)點(diǎn)分層的維護(hù)和多次兩點(diǎn)間信息交換， 大大增加了能耗。 該種類型的代表性算法是 TPSN 算法、LTS 算法。,.,8,WSN時(shí)間同步概述,時(shí)間同步算法的分類（3）,（3）基于發(fā)送者接收者（Sender-Receiver）的單向時(shí)間同步,基于發(fā)送者接收者的單向時(shí)間同步算法，相對(duì)于雙向的時(shí)間同步算法，只需要基準(zhǔn) 節(jié)點(diǎn)向待同步節(jié)點(diǎn)進(jìn)行單向數(shù)據(jù)包傳遞。 主要原理是基準(zhǔn)節(jié)點(diǎn)廣播包含自己節(jié)點(diǎn)時(shí)間信息的時(shí)間同步數(shù)據(jù)包，待同步節(jié)點(diǎn)在接受到 這一數(shù)據(jù)包后，根據(jù)時(shí)間戳信息，開(kāi)始計(jì)算數(shù)據(jù)通信過(guò)程中數(shù)據(jù)包延

5、遲的各個(gè)組成部分， 得到時(shí)間差值的待同步節(jié)點(diǎn)將對(duì)這些時(shí)延進(jìn)行補(bǔ)償，并完成了自己向參考節(jié)點(diǎn)的同步。 該類型算法優(yōu)點(diǎn)在于算法復(fù)雜度低、能耗小，缺點(diǎn)在于同步精度較低。 該種類型的代表性算法是 DMTS 算法和 FTSP 算法。,.,9,02,TPSN時(shí)間同步算法,.,10,TPSN時(shí)間同步算法,主要思想,層次發(fā)現(xiàn),時(shí)間同步,采用層次型網(wǎng)絡(luò)結(jié)構(gòu)，分為層次發(fā)現(xiàn)和時(shí)間同步兩個(gè)階段。,實(shí)現(xiàn)所有樹(shù)節(jié)點(diǎn)的時(shí)間同步，第 i 層的節(jié)點(diǎn)與第(i-1)層的一個(gè)節(jié)點(diǎn)同步，最終所有節(jié)點(diǎn)都能在時(shí)間上與根節(jié)點(diǎn)同步，從而實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步。,每一個(gè)節(jié)點(diǎn)賦予一個(gè)層次，第 i 層的節(jié)點(diǎn)至少要能夠與第(i-1)層的節(jié)點(diǎn)通信；,主要

6、思想,.,11,TPSN時(shí)間同步算法,層次發(fā)現(xiàn)階段,該階段主要工作是把整個(gè)網(wǎng)絡(luò)進(jìn)行分層。,時(shí)鐘源節(jié)點(diǎn)作為根節(jié)點(diǎn)，廣播級(jí)別發(fā)現(xiàn)數(shù)據(jù)包來(lái)啟動(dòng)分層過(guò)程。數(shù)據(jù)包中包含著節(jié)點(diǎn)自身的 ID 和所屬層次。,每個(gè)初次接收到級(jí)別發(fā)現(xiàn)數(shù)據(jù)包的節(jié)點(diǎn)需要將層次加 1 并繼續(xù)廣播，直到完成整個(gè)網(wǎng)絡(luò)的分層工作。,當(dāng)根節(jié)點(diǎn)的鄰居收到這一數(shù)據(jù)包，便把自己的層次置為 1，并向下繼續(xù)廣播新的級(jí)別發(fā)現(xiàn)數(shù)據(jù)包。,.,12,TPSN時(shí)間同步算法,時(shí)間同步階段,d,d,A：i 層節(jié)點(diǎn),B：i+1 層節(jié)點(diǎn),.,13,TPSN時(shí)間同步算法,時(shí)間同步階段,B 節(jié)點(diǎn)根據(jù)與 A 節(jié)點(diǎn)的時(shí)間偏差同步到 A 節(jié)點(diǎn)的時(shí)間,結(jié)論：,.,14,缺點(diǎn),優(yōu)點(diǎn),

7、在MAC層消息開(kāi)始發(fā)送到無(wú)線信道時(shí)才添加時(shí)間信標(biāo)，消除了訪問(wèn)時(shí)間帶來(lái)的誤差； 利用雙向交換信息計(jì)算消息的平均時(shí)延，精度相對(duì)較高。,節(jié)點(diǎn)失效（尤其是靠近根節(jié)點(diǎn)的節(jié)點(diǎn)失效）會(huì)導(dǎo)致同步錯(cuò)誤，并在網(wǎng)絡(luò)擴(kuò)散； 新節(jié)點(diǎn)加入時(shí)，需初始化層次發(fā)現(xiàn)步驟，擴(kuò)展性差； 不適合移動(dòng)節(jié)點(diǎn)或多跳同步等情況。,TPSN時(shí)間同步算法,優(yōu)、缺點(diǎn),.,15,03,一種基于優(yōu)化拓?fù)涞臅r(shí)間同步算法N-TPSN,.,16,N-TPSN時(shí)間同步算法,問(wèn)題描述,無(wú)線傳感器網(wǎng)絡(luò)各項(xiàng)技術(shù)具有一項(xiàng)共同的性能指標(biāo)，即能量消耗。 傳感器節(jié)點(diǎn)除了待機(jī)耗能外，幾乎所有能量都用來(lái)通過(guò)無(wú)線信道發(fā)送和接收數(shù)據(jù)包。,問(wèn)題：,研究方向：,對(duì)于無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同

8、步算法，也希望降低算法能量損耗,降低在時(shí)間同步過(guò)程中的數(shù)據(jù)包交換次數(shù)。,.,17,N-TPSN時(shí)間同步算法,算法思想（1）,本次算法設(shè)計(jì)的應(yīng)用背景是大規(guī)模、多跳、弱動(dòng)態(tài)的無(wú)線傳感器網(wǎng)絡(luò)，其單跳拓?fù)鋱D如圖所示，其中，實(shí)線表示 1 跳節(jié)點(diǎn)向參考節(jié)點(diǎn)發(fā)送的時(shí)間同步請(qǐng)求，虛線表示參考節(jié)點(diǎn)回饋的數(shù)據(jù)包。,根據(jù) TPSN 算法流程，在網(wǎng)絡(luò)分層結(jié)束同步過(guò)程開(kāi)始后，每個(gè) 1 跳節(jié)點(diǎn)需要向參考節(jié)點(diǎn)發(fā)送同步請(qǐng)求數(shù)據(jù)包，等待參考節(jié)點(diǎn)回饋后完成時(shí)間差值計(jì)算，同步到參考節(jié)點(diǎn)；,隨著節(jié)點(diǎn)數(shù)量的增加，節(jié)點(diǎn)密度增大，單跳范圍內(nèi)節(jié)點(diǎn)數(shù)量變大到 n，在 TPSN 協(xié)議中，此單跳范圍內(nèi)的數(shù)據(jù)包交換次數(shù)為 2n。,由于節(jié)點(diǎn)密度增大后

9、，某個(gè) 1 跳節(jié)點(diǎn)（假設(shè)為 A 節(jié)點(diǎn)）和參考節(jié)點(diǎn)的通信范圍內(nèi)很可能覆蓋其他的 1 跳節(jié)點(diǎn)，由于無(wú)線信道廣播特性，A 節(jié)點(diǎn)和參考節(jié)點(diǎn)的數(shù)據(jù)包交換過(guò)程可以被其他被覆蓋的 1 跳節(jié)點(diǎn)監(jiān)聽(tīng)到。,利用這些信息，這些被覆蓋的 1 跳節(jié)點(diǎn)便能發(fā)現(xiàn)自己與參考節(jié)點(diǎn)的時(shí)間差值進(jìn)而同步到參考節(jié)點(diǎn)。以此思路為基礎(chǔ)進(jìn)行單跳層次內(nèi)的算法優(yōu)化設(shè)計(jì)。,.,18,N-TPSN時(shí)間同步算法,算法思想（2）,上圖示意了 2 跳內(nèi)的 TPSN 算法，節(jié)點(diǎn)的編號(hào) 0-1 表示該節(jié)點(diǎn)是第 0 層的 1 號(hào)節(jié)點(diǎn)，1-9 表示該節(jié)點(diǎn)是第 1 層的 9 號(hào)節(jié)點(diǎn)，依此類推。,.,19,N-TPSN時(shí)間同步算法,層次內(nèi)開(kāi)銷優(yōu)化設(shè)計(jì)（1）,TPSN

10、 算法的數(shù)據(jù)包交換流程如圖 3-4 所示，O 為上層節(jié)點(diǎn)，A、B、C 均為下層節(jié)點(diǎn)。圖中節(jié)點(diǎn)按 A、B、C 順序依次與 O 節(jié)點(diǎn)進(jìn)行時(shí)間同步，實(shí)現(xiàn)表示下層節(jié)點(diǎn)發(fā)送時(shí)間同步請(qǐng)求，虛線表示上層節(jié)點(diǎn)回饋。,N-TPSN算法數(shù)據(jù)包交換流程如圖3-5所示，B、C 節(jié)點(diǎn)均在 A 和 O 節(jié)點(diǎn)的單跳范圍內(nèi)，由于無(wú)線信道具有廣播特性，A 與 O 節(jié)點(diǎn)間的數(shù)據(jù)包交換可以被 B、C 兩個(gè)節(jié)點(diǎn)監(jiān)聽(tīng)到。,以單跳內(nèi)四個(gè)節(jié)點(diǎn)為例，,.,20,N-TPSN時(shí)間同步算法,層次內(nèi)開(kāi)銷優(yōu)化設(shè)計(jì)（2）,1.同步請(qǐng)求,2.上層回饋,3.偏差計(jì)算,4.時(shí)間修正,上圖可以完成1跳范圍內(nèi)某節(jié)點(diǎn)與上層節(jié)點(diǎn)通信范圍覆蓋的所有節(jié)點(diǎn)的時(shí)間同步工作，這些被覆蓋的節(jié)點(diǎn)只需要監(jiān)聽(tīng)無(wú)線信道并對(duì)接收到的數(shù)據(jù)包進(jìn)行分析計(jì)算即可，大大降低了 TPSN的算法開(kāi)銷。,.,21,N-TPSN時(shí)間同步算法,層次間開(kāi)銷優(yōu)化設(shè)計(jì)（1）,網(wǎng)絡(luò)拓?fù)浜?jiǎn)化，采用選擇最佳鄰居的拓?fù)鋬?yōu)化思路，該算法被命名為 best-Neighbor TPSN，即 N-TPSN。,.,22,N-TPSN時(shí)間同步算法,層次間開(kāi)銷優(yōu)化設(shè)計(jì)（2）,檢測(cè) 1 跳鄰居,計(jì)算 2 跳鄰居,計(jì)算最佳鄰居,保存選中名單,1 號(hào)節(jié)點(diǎn)的 1 跳節(jié)點(diǎn)中只有 2、4、6、8 號(hào)節(jié)點(diǎn)需要向1 號(hào)節(jié)點(diǎn)發(fā)送時(shí)間同步請(qǐng)求數(shù)據(jù)包，3、5、7、9 號(hào)節(jié)點(diǎn)只需要進(jìn)行無(wú)線信道的監(jiān)聽(tīng)。在 1 跳范圍內(nèi)的節(jié)點(diǎn)被同