關 閉

新聞中心

EEPW首頁 > 工控自動化 > 設計應用 > 無線傳感器網(wǎng)絡同步算法的研究與探討

無線傳感器網(wǎng)絡同步算法的研究與探討

作者: 時間:2012-05-15 來源:網(wǎng)絡 收藏

摘要:時間進行數(shù)據(jù)融合、TDMA調(diào)度、定位等基本應用的基礎。從時間的概念和定義出發(fā),首先對幾種經(jīng)典的常用的時間及新型的螢火蟲同步和梯度同步進行了介紹,然后主要分析分布式的時隙互同步,最后展望了未來時間同步算法的方向。
關鍵詞:;梯度同步;分布式時隙同步算法

引言
技術融合了傳感器、低功耗嵌入式計算器、無線網(wǎng)絡和通信、分布式信息處理等技術,利用傳感節(jié)點通過自組網(wǎng)絡對監(jiān)測對象進行實時監(jiān)測、感知和采集,在環(huán)境、資源、智能交通、礦井安全等領域都有著良好的應用前景,是近年來國內(nèi)外信息領域和競爭的焦點。而時間同步技術是無線傳感器網(wǎng)絡中一項非常關鍵的基礎技術。網(wǎng)絡時間協(xié)議NTP(Network Time Protocol)是傳統(tǒng)網(wǎng)絡的時間同步協(xié)議,最早由美國Delaware大學的Mill教授提出。然而NTP是應傳統(tǒng)網(wǎng)絡的能量效率、網(wǎng)絡動態(tài)、基礎設施和系統(tǒng)而構建,因此并不適合低功耗、低成本、微型化、高集成、協(xié)作式多跳自組織的無線傳感器網(wǎng)絡。另外,無線傳感器網(wǎng)絡時間同步算法還要考慮能量消耗、可拓展性、精確度、魯棒性等問題,這些都對無線傳感器網(wǎng)絡的時間同步算法提出了新的要求和挑戰(zhàn)。
在2002年的HotNets上,J Elson和Kay Romer首次提出并闡述了無線傳感器網(wǎng)絡時間同步技術的課題,在國際上引發(fā)了廣泛的關注和思考,吸引了許多大學和機構參與研究,已經(jīng)提出許多種不同的實現(xiàn)算法及改進算法,典型的有RBS算法、TPSN算法、還有TDP算法、FTSP算法、DMTS算法、LTS算法、TS/MS算法、HRTS算法、OFDC算法、CHTS算法、CRIT算法以及最新的基于螢火蟲技術和協(xié)作技術的時間同步算法等。

1 概念與定義
在計算機體系結構中,時鐘通常用品體振蕩器脈沖來度量,即
a.JPG
式中C(t)為構造的本地時鐘,t為真實時間變量,k為依賴于晶振的物理特性常量,ω(τ)為晶振的頻率,間隔c(t)-c(t0)被用來作為度量時間。對于理想的時鐘,有r(t)=dc(t)/dt=1,也就是說,理想時鐘的變化速率r(t)為1。但在工程實踐中,因為溫度、壓力、電源電壓等外界環(huán)境的變化,往往會導致晶振頻率產(chǎn)生波動。因此構造理想時鐘比較困難,但在一般情況下晶振頻率的波動幅度并非任意的,而是局限在一定范圍之內(nèi)。為了方便描述與分析,定義了速率恒定模型、漂移有界模型和漂移變化有界模型。
假定c(t)是一個理想的時鐘。如果在t時刻有c(t)=ci(t),則稱ci(t)在t時刻是準確的;如果dc(t)/dt=dci(t)/dt。則稱時鐘ci(t)在t時刻是精確的;如果ci(t)=ck(t),則稱時鐘ci(t)在t時刻與時鐘ck(t)是同步的。上述定義表明,兩個同步時鐘不一定是準確或精確的,時間同步與時間的準確性和精度沒有必然的聯(lián)系。
如果采用時鐘速率恒定模型,由式(1),時鐘ci(t)可以簡化表示為:
ci(t)=ai·t+bi (2)
由此可知,時鐘ci(t)和ck(t)之間應該存在如下的線性關系:
ci(t)=aik·ck(t)+bik (3)
式中aik、bik為相對漂移量和相對偏移量。

2 典型同步算法
Elson、Girod和Estrin在參考文獻中以“第三節(jié)點”實現(xiàn)同步的思想提出了RBS算法,這是一種基于接收者一接收者的時間同步協(xié)議。根節(jié)點周期性地向其廣播域中的子節(jié)點發(fā)送不包含時間戳的參照廣播(Referenccs Broadcast)消息。接收到廣播消息后,鄰居子節(jié)點用自已
的本地時鐘記錄各自的接收時刻作為參考比對時鐘,然后相互交換它們記錄的時間信息,這樣接收節(jié)點就能知道彼此之間的時鐘偏移量。然后利用式(4)計算相對其他各個節(jié)點的時鐘偏移的平均值,并相應進行調(diào)整。當所有節(jié)點都獲得相對其他節(jié)點的時鐘偏移量平均值時,所有接收同一參照廣播消息的接收節(jié)點便獲得了一個相對網(wǎng)絡時間,即:
d.JPG
式中:n為待同步節(jié)點數(shù),m為參考廣播的次數(shù),Ti,k為第i個節(jié)點接收第k次參考廣播的本地時刻。顯然,由offset(i,j)形成的矩陣為對稱矩陣,且對角線元素為0。
TPSN算法是由Ganeriwal等人提出的,是一種基于發(fā)送者和接收者的時間同步算法。采用層次型網(wǎng)絡結構。算法分兩步:首先是層次發(fā)現(xiàn)階段,建立網(wǎng)絡拓撲結構;然后每個節(jié)點與上一級的一個節(jié)點進行時間同步,最終實現(xiàn)所有節(jié)點都與根節(jié)點的時間同步。
FTSP協(xié)議是一種單向廣播的發(fā)送者和接收者的時間同步辦議。協(xié)議首先要網(wǎng)絡動態(tài)地選擇一個節(jié)點作為網(wǎng)絡的根節(jié)點,其時間作為全網(wǎng)的參考時間,根節(jié)點把含有當前本地時間的信息包發(fā)送給它單跳廣播域內(nèi)的鄰居節(jié)點;鄰居節(jié)點在收到信息后分別記錄相應的接收時間,采用參數(shù)擬合技術算出相對于根節(jié)點的時間漂移和時間偏移;然后這些與根節(jié)點同步了的鄰居節(jié)點也作為參考節(jié)點,采用與根節(jié)點同步的相同的辦法,使它們的鄰居節(jié)點也實現(xiàn)與其同步。


上一頁 1 2 3 下一頁

評論


相關推薦

技術專區(qū)

關閉