TPSN時間同步算法研究PPT課件

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

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

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

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

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

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

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

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

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

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