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

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

2、到環(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í)間同步情況。WSN時(shí)間同步概述時(shí)間同步算法的分類（1） （1）基于接收者接收者（Receiver-Receiver）的時(shí)間同步 基于接收者接收者的時(shí)間同步算法，主要利用了無(wú)線信道的廣播屬性。 主要原理是引入一個(gè)節(jié)點(diǎn)作為輔助節(jié)點(diǎn)，由該節(jié)點(diǎn)廣播一個(gè)參考分組，在廣播域內(nèi)的一組 接收節(jié)點(diǎn)接收到這個(gè)參考分組，通過(guò)比較各自接收到消息的的本地時(shí)間，實(shí)現(xiàn)

3、它們之間的 時(shí)間同步。 由于其他節(jié)點(diǎn)只需要監(jiān)聽(tīng)信息而不需要同步到參考節(jié)點(diǎn)，該類型算法的優(yōu)點(diǎn)在于可以避免 發(fā)送節(jié)點(diǎn)時(shí)延的影響，但缺點(diǎn)在于信息交換次數(shù)較多，能耗較大。 該種類型的代表性算法是 RBS 算法。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í)間，待 同步節(jié)點(diǎn)接收到反饋的信息后計(jì)算時(shí)間偏差并予以調(diào)整，完成時(shí)間同步。 該類型算法優(yōu)點(diǎn)在于同步的高精度

4、，而缺點(diǎn)就是節(jié)點(diǎn)分層的維護(hù)和多次兩點(diǎn)間信息交換， 大大增加了能耗。 該種類型的代表性算法是 TPSN 算法、LTS 算法。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ù)包延遲的各個(gè)組成部分， 得到時(shí)間差值的待同步節(jié)點(diǎn)將對(duì)這些時(shí)延進(jìn)行補(bǔ)償，并完成了自己向參考節(jié)點(diǎn)的同步。 該類型算法優(yōu)點(diǎn)

5、在于算法復(fù)雜度低、能耗小，缺點(diǎn)在于同步精度較低。 該種類型的代表性算法是 DMTS 算法和 FTSP 算法。02TPSN時(shí)間同步算法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)通信；主要思想TPSN時(shí)間同步算法層次發(fā)現(xiàn)階段01040203該階段主要工作是把整個(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ù)包

6、中包含著節(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ù)包。TPSN時(shí)間同步算法時(shí)間同步階段ddA：i 層節(jié)點(diǎn)B：i+1 層節(jié)點(diǎn)TPSN時(shí)間同步算法時(shí)間同步階段B 節(jié)點(diǎn)根據(jù)與 A 節(jié)點(diǎn)的時(shí)間偏差同步到 A 節(jié)點(diǎn)的時(shí)間結(jié)論：缺點(diǎn)缺點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn) 在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ò)散； 新

7、節(jié)點(diǎn)加入時(shí)，需初始化層次發(fā)現(xiàn)步驟，擴(kuò)展性差； 不適合移動(dòng)節(jié)點(diǎn)或多跳同步等情況。TPSN時(shí)間同步算法優(yōu)、缺點(diǎn)03一種基于優(yōu)化拓?fù)涞臅r(shí)間同步算法N-TPSNN-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í)間同步算法，也希望降低算法能量損耗降低在時(shí)間同步過(guò)程中的數(shù)據(jù)包交換次數(shù)。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í)間同步

8、請(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)密度增大后，某個(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)而同步到

9、參考節(jié)點(diǎn)。以此思路為基礎(chǔ)進(jìn)行單跳層次內(nèi)的算法優(yōu)化設(shè)計(jì)。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)，依此類推。TPSN 的分層思想是多跳無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法中比較科學(xué)、先進(jìn)的解決思想。TPSN 協(xié)議在多跳情況下，下層節(jié)點(diǎn)需要向鄰近的每個(gè)上層節(jié)點(diǎn)進(jìn)行時(shí)間同步請(qǐng)求。比如圖中的17號(hào)節(jié)點(diǎn)，需要向8號(hào)節(jié)點(diǎn)和9號(hào)節(jié)點(diǎn)分別進(jìn)行同步請(qǐng)求。但這兩個(gè)節(jié)點(diǎn)的反饋包被17號(hào)節(jié)點(diǎn)接受并進(jìn)行數(shù)據(jù)綜合處理后，并不能保證17號(hào)節(jié)點(diǎn)的同步精度比單獨(dú)與一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步精度更高。如果17

10、號(hào)節(jié)點(diǎn)只與9號(hào)節(jié)點(diǎn)同步，16號(hào)節(jié)點(diǎn)只與7號(hào)節(jié)點(diǎn)同步，8號(hào)節(jié)點(diǎn)便不需要進(jìn)行時(shí)間同步數(shù)據(jù)包的接收和回饋工作。以此進(jìn)行層次間的算法優(yōu)化。N-TPSN時(shí)間同步算法層次內(nèi)開(kāi)銷優(yōu)化設(shè)計(jì)（1）TPSN 算法的數(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)為例，N-TPSN

11、時(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)銷。N-TPSN時(shí)間同步算法層次間開(kāi)銷優(yōu)化設(shè)計(jì)（1）網(wǎng)絡(luò)拓?fù)浜?jiǎn)化，采用選擇最佳鄰居的拓?fù)鋬?yōu)化思路，該算法被命名為 best-Neighbor TPSN，即 N-TPSN。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