




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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é)點被同
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 4.2實現(xiàn)中華民族偉大復興的中國夢 課件 統(tǒng)編版高中思想政治必修1中國特色社會主義
- 麻醉、第一類精神藥品臨床使用與規(guī)范化管理考核試題及答案
- 臨床路徑下單病種質控管理文檔
- 老板安全培訓課件
- 老式電話兒童課件
- 老年營養(yǎng)護理課件
- 電子商務園區(qū)場地租賃代理合同
- 船舶安全護衛(wèi)服務管理協(xié)議范本
- 財務合同部全面職責與風險防控協(xié)議
- 餐飲品牌加盟店選址與評估合同
- 開業(yè)美容項目活動方案
- 2025至2030高純氯化鉀行業(yè)產(chǎn)業(yè)運行態(tài)勢及投資規(guī)劃深度研究報告
- ××中學實驗室?;饭芾砑殑t
- 家政服務培訓 課件
- 醫(yī)學美容技術專業(yè)教學標準(高等職業(yè)教育專科)2025修訂
- 2025年婚姻家庭咨詢師職業(yè)資格考試試題及答案
- 2025年人教版小學五年級下冊數(shù)學期末重難點測評試題(含答案和解析)
- 2024年天津市應急管理局招聘行政執(zhí)法專職技術檢查員筆試真題
- 變電站創(chuàng)優(yōu)工程匯報
- 廣西壯族自治區(qū)欽州市2024-2025學年高二上學期期末檢測歷史試題(含答案)
- 項目部主要管理制度
評論
0/150
提交評論