DMTS與TPSN時間同步算法的融合設計

2010-03-20 02:31:48徐世武王平何花施文灶江華麗

單片機與嵌入式系統應用 2010年12期

徐世武,王平,何花,施文灶,江華麗

(福建師范大學物理與光電信息科技學院,福州350007)

引言

無線傳感器網絡集成了傳感器技術、計算機技術和通信技術,在軍事、環境、健康、家庭、商業等許多方面有著巨大的潛在應用前景[1]。功耗的高低是衡量一個無線傳感器網絡性能的主要標志之一,應該盡量讓沒有工作的節點處于休眠狀態,以節省節點的功耗。當然可以在MAC層采用時分多路復用技術,但這就要求節點通信雙方實現時間上的同步。

NTP協議是目前因特網上采用的時間同步協議標準。因無線傳感網絡具有體積、電能供應、存儲容量等的約束,以及采用的是無線傳輸方式,算法的局部性等,所以NTP協議不適合用于無線傳感網絡中。GPS系統也可以提供高精度的時間同步,但它的信號穿透性差,GPS天線必須安裝在空曠的地方,功耗也較大,所以不適合無線傳感器網絡。

1 節點硬件平臺

傳感器節點是構成無線傳感網絡的基本平臺,具有傳統網絡的終端和路由的雙重功能:一方面要實現數據的采集和處理;另一方面還要對其他節點轉發的數據進行存儲、管理和融合等處理。雖然其設計不一,但是基本結構相同。它一般由傳感器模塊、處理器模塊、無線通信模塊和能量供應模塊組成[2]。基本組成如圖1所示。

圖1 無線傳感器節點基本組成

2 時間同步

2.1 不確定性的影響因素

因受到各種器件、負載等因素的影響,傳輸延遲的不確定性主要的影響因素如圖2所示。

圖2 報文傳輸延遲

發送時間:發送方用于構造分組并將分組轉交給發送方的MAC層的時間。主要取決于時間同步程序的操作系統調用時間和處理器負載等。

訪問時間:分組到達MAC層后,獲取信道發送權的時間。主要取決于共享信道的競爭,當前的負載等。

傳送時間:發送分組的時間,主要取決于報文的長度等。

傳播時間:分組離開發送方后,并將分組傳輸到接收方之間的無線傳輸時間。主要取決于傳輸介質、傳輸距離等。

接收時間:接收端接收到分組,并將分組傳送到MAC層所需的時間。

接受時間:處理接收到分組的時間。主要受到操作系統的影響。

2.2 算法分類

在無線傳感器網絡中,目前時間同步協議比較成熟的協議中,根據同步節點間信息交互方式的不同,可以歸結為以下3類:

①基于發送者—接收者的雙向同步算法,比較典型的算法如TPSN(Timing-Sync Protocol for Sensor Networks)算法。

②基于發送者—接收者的單向時間同步算法,比較典型的算法如FTSP(Flooding Time Synchronization Protocol)算法,DM TS(Delay Measurement Time Synchronization)算法。

③基于接收者—接收者的同步算法,典型的有RBS(Reference Broadcast Synchronization)算法。

2.3 DMTS算法分析

DM TS(Delay Measurement Time Synchronization)算法[3],即延遲測量時間同步協議,是基于發送者—接收者的單向時間同步算法,該算法結構簡單,功耗較低,具有廣泛的運用,其算法原理圖如圖3所示。當發送節點在檢測到通道空閑時,給廣播分組加上時間戳t0,從而排除了發送節點的處理延遲與MAC層的訪問延遲。并假設發送報文的長度為NA個比特(包括前導碼與同步字),傳送每個比特的時間為t,而接收者在接收完同步字后,記錄下此時的本地時間為t1,并在調整自己的本地時間記錄之前記錄下此時的時刻t2,這時接收節點為了與發送節點達到時間上的同步,可以調整接收節點的時間改為t0+t?NA+(t2-t1)。

圖3 DMTS算法原理圖

2.4 TPSN算法分析

TPSN(Timing-Sync Protocol for Sensor Networks)算法[4],采用的是層次型的網絡結構,是基于發送者—接收者的雙向同步算法。分層兩個階段,第一階段為層次發現階段,第二階段為同步階段。其算法原理圖如圖4所示。在圖4中,T1、T4用來記錄同步節點的本地時間,T2、T3用來記錄參考

節點的本地時間。同步節點A在T1時刻向參考節點B發送一個同步請求報文,報文中包含了同步節點的級別和T1,當參考節點B收到報文后,記錄下接收時刻T2,并立即向同步節點A回復一個同步應答報文,該報文中包含了參考節點B的級別和T1、T2、回復時刻T3。同步節點A收到參考節點的回復后,記下時刻T4,假設來回報文的傳輸延遲相同都為d,且m為同步節點在T1時刻兩者之間的時偏,且設來回時偏相同,由則在T4時刻,若在同步節點A的本地時間增加修正量m,就能達到同步節點A與參考節點B之間的同步。

圖4 TPSN算法原理圖

2.5 兩種算法的融合設計

本文設計主要采用DM TS與TPSN兩種算法的融合運用,充分利用兩種算法的優點。本文主要分成兩條路徑,主路徑和次路徑。主路徑即圖5中的A、B、E三個路由節點形成的路徑,次路徑即路由節點B與兩個傳感節點(C、D)形成的一個子網絡1,還有路由節點E與兩個傳感節點(F、G)形成的一個子網絡2。在無線傳感網絡中大部分是由傳感節點組成的,用來采集數據,還有一部分是路由節點用來存儲和轉發數據,因主路徑中的路由節點跳數較多,為了提高網絡的精度,可以在路由節點與路由節點之間,即主路徑之間采用TPSN算法,而在子網內的傳感節點與該子網的路由節點之間采用DMTS算法,這樣既可以減少整個網絡算法的復雜度,也可以減少整個網絡的功耗。

主路徑上的時間同步:首先A節點通過使用NLDEDATA.request原語,并設置DstAdd r參數為0xffff(廣播網絡地址)廣播形式發送時間同步組包命令[5]。組包中包括了A節點的層次號0,A節點的ID號,并指定B節點為其下一跳同步節點。當B節點收到A節點發送的廣播組包后,記下自己的層次號為1,父節點的ID號為A,并與A節點進行時間同步。同樣,B節點也以廣播的方式發送同步組包,指定E節點為其下一跳同步節點。當C、D、E節點收到B節點的廣播同步包后,分別記下自己的層次號為2,但只有E節點才與A節點進行時間同步。

圖5 實驗節點組網圖

次路徑上的時間同步:在主路徑上時間同步完成后,這時就可以在次路徑上進行時間同步。對同步精度要求不是很高的情況下,次路徑可以選擇較長的周期進行同步,以減少網絡的功耗。在子網絡1中,B節點以廣播的方式發送同步信息包,當然與主路徑的同步包不同,這時B節點指定的下一跳節點為C、D兩個節點。但C、D兩個節點收到B節點的同步包后,修改自己的本地時間以達到以節點B的同步,子網2采用同樣的辦法進行同步。

2.6 算法誤差分析

主路徑誤差分析,根據圖2中的消息傳輸過程,可以得出以下各式:

在式(1)、(2)中,t1、t2是由標準時鐘所確定的,表示UTC時間。T1、T2分別是t1、t2所對應的本地節點所測出的本地時間。SA代表節點A的報文發送時間,AA是發送報文的訪問時間,TA→B是A節點按比特傳輸報文與B節點按比特接收報文所需要的時間,PA→B是節點A傳播到節點B的時間。RB是節點B的報文接收處理過程時間。NAt是傳輸NA個比特的總時間。Terror指傳輸比特的誤差,Rerror打時標過程存在的誤差。代表節點A與節點B在t1時刻的時偏。因為在實驗中我們采用了MAC層的打時標方法,這樣就可以消除了發送時間與訪問時間對誤差的影響。于是式(1)、(2)就可以簡寫為式(3)、(4)。

由以上各式可以得到時偏:

次路徑上的誤差分析,由圖1可以看出,發送節點A在T0時刻檢測到空閑,接收節點B在報文到達時刻給報文加上時間戳T1,并在調整自己的本地時間記錄之前記錄下此時的時刻為T2,在T3時間完成調整。則可以得到[6]:

式子TA→B+RB=nt+Terror+Rerror+(T2-T1)中,n是前導碼的長度,于是可以得到DMTS的時偏m:

從式(7)中可以看出TPSN的誤差較小,因為兩個傳感節點的距離較小,而電波的傳播速度快,所示PUC通常都在μs范圍之內,而兩個節點之間的來回時偏基本是不變的。所以TPSN誤差大部分是由兩個節點收、發報文的時間差。從式(10)中可以看出,DM TS是單播傳送報文,所示不能消除Terror和Rerror的影響。雖然TPSN算法精度較高,但同步一次,需要發送2個消息和接收2個消息,共4個消息的能量消耗。DM TS算法精度較差,但同步一次,只需要發送1個消息和接收1個消息,共2個消息的能量消耗。所以結合了兩者的優點,在無線傳感器網絡中不僅保證了網絡的精確度,也減少了整個網絡的功耗。