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

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

引 言

無(wú)線傳感器網(wǎng)絡(luò)集成了傳感器技術(shù)、計(jì)算機(jī)技術(shù)和通信技術(shù),在軍事、環(huán)境、健康、家庭、商業(yè)等許多方面有著巨大的潛在應(yīng)用前景[1]。功耗的高低是衡量一個(gè)無(wú)線傳感器網(wǎng)絡(luò)性能的主要標(biāo)志之一,應(yīng)該盡量讓沒(méi)有工作的節(jié)點(diǎn)處于休眠狀態(tài),以節(jié)省節(jié)點(diǎn)的功耗。當(dāng)然可以在MAC層采用時(shí)分多路復(fù)用技術(shù),但這就要求節(jié)點(diǎn)通信雙方實(shí)現(xiàn)時(shí)間上的同步。

NTP協(xié)議是目前因特網(wǎng)上采用的時(shí)間同步協(xié)議標(biāo)準(zhǔn)。因無(wú)線傳感網(wǎng)絡(luò)具有體積、電能供應(yīng)、存儲(chǔ)容量等的約束,以及采用的是無(wú)線傳輸方式,算法的局部性等,所以NTP協(xié)議不適合用于無(wú)線傳感網(wǎng)絡(luò)中。GPS系統(tǒng)也可以提供高精度的時(shí)間同步,但它的信號(hào)穿透性差,GPS天線必須安裝在空曠的地方,功耗也較大,所以不適合無(wú)線傳感器網(wǎng)絡(luò)。

1 節(jié)點(diǎn)硬件平臺(tái)

傳感器節(jié)點(diǎn)是構(gòu)成無(wú)線傳感網(wǎng)絡(luò)的基本平臺(tái),具有傳統(tǒng)網(wǎng)絡(luò)的終端和路由的雙重功能:一方面要實(shí)現(xiàn)數(shù)據(jù)的采集和處理;另一方面還要對(duì)其他節(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)進(jìn)行存儲(chǔ)、管理和融合等處理。雖然其設(shè)計(jì)不一,但是基本結(jié)構(gòu)相同。它一般由傳感器模塊、處理器模塊、無(wú)線通信模塊和能量供應(yīng)模塊組成[2]。基本組成如圖1所示。

圖1 無(wú)線傳感器節(jié)點(diǎn)基本組成

2 時(shí)間同步

2.1 不確定性的影響因素

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

圖2 報(bào)文傳輸延遲

發(fā)送時(shí)間:發(fā)送方用于構(gòu)造分組并將分組轉(zhuǎn)交給發(fā)送方的MAC層的時(shí)間。主要取決于時(shí)間同步程序的操作系統(tǒng)調(diào)用時(shí)間和處理器負(fù)載等。

訪問(wèn)時(shí)間:分組到達(dá)MAC層后,獲取信道發(fā)送權(quán)的時(shí)間。主要取決于共享信道的競(jìng)爭(zhēng),當(dāng)前的負(fù)載等。

傳送時(shí)間:發(fā)送分組的時(shí)間,主要取決于報(bào)文的長(zhǎng)度等。

傳播時(shí)間:分組離開(kāi)發(fā)送方后,并將分組傳輸?shù)浇邮辗街g的無(wú)線傳輸時(shí)間。主要取決于傳輸介質(zhì)、傳輸距離等。

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

接受時(shí)間:處理接收到分組的時(shí)間。主要受到操作系統(tǒng)的影響。

2.2 算法分類

在無(wú)線傳感器網(wǎng)絡(luò)中,目前時(shí)間同步協(xié)議比較成熟的協(xié)議中,根據(jù)同步節(jié)點(diǎn)間信息交互方式的不同,可以歸結(jié)為以下3類:

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

②基于發(fā)送者—接收者的單向時(shí)間同步算法,比較典型的算法如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],即延遲測(cè)量時(shí)間同步協(xié)議,是基于發(fā)送者—接收者的單向時(shí)間同步算法,該算法結(jié)構(gòu)簡(jiǎn)單,功耗較低,具有廣泛的運(yùn)用,其算法原理圖如圖3所示。當(dāng)發(fā)送節(jié)點(diǎn)在檢測(cè)到通道空閑時(shí),給廣播分組加上時(shí)間戳t0,從而排除了發(fā)送節(jié)點(diǎn)的處理延遲與MAC層的訪問(wèn)延遲。并假設(shè)發(fā)送報(bào)文的長(zhǎng)度為NA個(gè)比特(包括前導(dǎo)碼與同步字),傳送每個(gè)比特的時(shí)間為t,而接收者在接收完同步字后,記錄下此時(shí)的本地時(shí)間為t1,并在調(diào)整自己的本地時(shí)間記錄之前記錄下此時(shí)的時(shí)刻t2,這時(shí)接收節(jié)點(diǎn)為了與發(fā)送節(jié)點(diǎn)達(dá)到時(shí)間上的同步,可以調(diào)整接收節(jié)點(diǎn)的時(shí)間改為t0+t?NA+(t2-t1)。

圖3 DMTS算法原理圖

2.4 TPSN算法分析

TPSN(Timing-Sync Protocol for Sensor Networks)算法[4],采用的是層次型的網(wǎng)絡(luò)結(jié)構(gòu),是基于發(fā)送者—接收者的雙向同步算法。分層兩個(gè)階段,第一階段為層次發(fā)現(xiàn)階段,第二階段為同步階段。其算法原理圖如圖4所示。在圖4中,T1、T4用來(lái)記錄同步節(jié)點(diǎn)的本地時(shí)間,T2、T3用來(lái)記錄參考

節(jié)點(diǎn)的本地時(shí)間。同步節(jié)點(diǎn)A在T1時(shí)刻向參考節(jié)點(diǎn)B發(fā)送一個(gè)同步請(qǐng)求報(bào)文,報(bào)文中包含了同步節(jié)點(diǎn)的級(jí)別和T1,當(dāng)參考節(jié)點(diǎn)B收到報(bào)文后,記錄下接收時(shí)刻T2,并立即向同步節(jié)點(diǎn)A回復(fù)一個(gè)同步應(yīng)答報(bào)文,該報(bào)文中包含了參考節(jié)點(diǎn)B的級(jí)別和T1、T2、回復(fù)時(shí)刻T3。同步節(jié)點(diǎn)A收到參考節(jié)點(diǎn)的回復(fù)后,記下時(shí)刻T4,假設(shè)來(lái)回報(bào)文的傳輸延遲相同都為d,且m為同步節(jié)點(diǎn)在T1時(shí)刻兩者之間的時(shí)偏,且設(shè)來(lái)回時(shí)偏相同,由則在T4時(shí)刻,若在同步節(jié)點(diǎn)A的本地時(shí)間增加修正量m,就能達(dá)到同步節(jié)點(diǎn)A與參考節(jié)點(diǎn)B之間的同步。

圖4 TPSN算法原理圖

2.5 兩種算法的融合設(shè)計(jì)

本文設(shè)計(jì)主要采用DM TS與TPSN兩種算法的融合運(yùn)用,充分利用兩種算法的優(yōu)點(diǎn)。本文主要分成兩條路徑,主路徑和次路徑。主路徑即圖5中的A、B、E三個(gè)路由節(jié)點(diǎn)形成的路徑,次路徑即路由節(jié)點(diǎn)B與兩個(gè)傳感節(jié)點(diǎn)(C、D)形成的一個(gè)子網(wǎng)絡(luò)1,還有路由節(jié)點(diǎn)E與兩個(gè)傳感節(jié)點(diǎn)(F、G)形成的一個(gè)子網(wǎng)絡(luò)2。在無(wú)線傳感網(wǎng)絡(luò)中大部分是由傳感節(jié)點(diǎn)組成的,用來(lái)采集數(shù)據(jù),還有一部分是路由節(jié)點(diǎn)用來(lái)存儲(chǔ)和轉(zhuǎn)發(fā)數(shù)據(jù),因主路徑中的路由節(jié)點(diǎn)跳數(shù)較多,為了提高網(wǎng)絡(luò)的精度,可以在路由節(jié)點(diǎn)與路由節(jié)點(diǎn)之間,即主路徑之間采用TPSN算法,而在子網(wǎng)內(nèi)的傳感節(jié)點(diǎn)與該子網(wǎng)的路由節(jié)點(diǎn)之間采用DMTS算法,這樣既可以減少整個(gè)網(wǎng)絡(luò)算法的復(fù)雜度,也可以減少整個(gè)網(wǎng)絡(luò)的功耗。

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

圖5 實(shí)驗(yàn)節(jié)點(diǎn)組網(wǎng)圖

次路徑上的時(shí)間同步:在主路徑上時(shí)間同步完成后,這時(shí)就可以在次路徑上進(jìn)行時(shí)間同步。對(duì)同步精度要求不是很高的情況下,次路徑可以選擇較長(zhǎng)的周期進(jìn)行同步,以減少網(wǎng)絡(luò)的功耗。在子網(wǎng)絡(luò)1中,B節(jié)點(diǎn)以廣播的方式發(fā)送同步信息包,當(dāng)然與主路徑的同步包不同,這時(shí)B節(jié)點(diǎn)指定的下一跳節(jié)點(diǎn)為C、D兩個(gè)節(jié)點(diǎn)。但C、D兩個(gè)節(jié)點(diǎn)收到B節(jié)點(diǎn)的同步包后,修改自己的本地時(shí)間以達(dá)到以節(jié)點(diǎn)B的同步,子網(wǎng)2采用同樣的辦法進(jìn)行同步。

2.6 算法誤差分析

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

在式(1)、(2)中,t1、t2是由標(biāo)準(zhǔn)時(shí)鐘所確定的,表示UTC時(shí)間。T1、T2分別是t1、t2所對(duì)應(yīng)的本地節(jié)點(diǎn)所測(cè)出的本地時(shí)間。SA代表節(jié)點(diǎn)A的報(bào)文發(fā)送時(shí)間,AA是發(fā)送報(bào)文的訪問(wèn)時(shí)間,TA→B是A節(jié)點(diǎn)按比特傳輸報(bào)文與B節(jié)點(diǎn)按比特接收?qǐng)?bào)文所需要的時(shí)間,PA→B是節(jié)點(diǎn)A傳播到節(jié)點(diǎn)B的時(shí)間。RB是節(jié)點(diǎn)B的報(bào)文接收處理過(guò)程時(shí)間。NAt是傳輸NA個(gè)比特的總時(shí)間。Terror指?jìng)鬏敱忍氐恼`差,Rerror打時(shí)標(biāo)過(guò)程存在的誤差。代表節(jié)點(diǎn)A與節(jié)點(diǎn)B在t1時(shí)刻的時(shí)偏。因?yàn)樵趯?shí)驗(yàn)中我們采用了MAC層的打時(shí)標(biāo)方法,這樣就可以消除了發(fā)送時(shí)間與訪問(wèn)時(shí)間對(duì)誤差的影響。于是式(1)、(2)就可以簡(jiǎn)寫(xiě)為式(3)、(4)。

由以上各式可以得到時(shí)偏:

次路徑上的誤差分析,由圖1可以看出,發(fā)送節(jié)點(diǎn)A在T0時(shí)刻檢測(cè)到空閑,接收節(jié)點(diǎn)B在報(bào)文到達(dá)時(shí)刻給報(bào)文加上時(shí)間戳T1,并在調(diào)整自己的本地時(shí)間記錄之前記錄下此時(shí)的時(shí)刻為T(mén)2,在T3時(shí)間完成調(diào)整。則可以得到[6]:

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

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

2.7 算法程序流程

算法總體流程如圖6所示,主路徑程序流程如圖7所示,次路徑程序流程如圖8所示。22

圖6 算法總體流程

圖7 主路徑程序流程

圖8 次路徑程序流程

結(jié) 語(yǔ)

本文的創(chuàng)新在于融合了DM TS和TPSN兩種時(shí)間同步算法,網(wǎng)絡(luò)功耗和精度均介于兩者之間。雖然相較于TPSN算法,在同步精度上有所下降,但網(wǎng)絡(luò)節(jié)點(diǎn)功耗低于TPSN算法,特別適用于同步精度要求不是非常高的中小型無(wú)線傳感器網(wǎng)絡(luò)中。

[1]田賢忠,陳登,胡同森.無(wú)線傳感器網(wǎng)絡(luò)按需時(shí)間同步算法研究[J].傳感技術(shù)學(xué)報(bào),2008,21(11):1881-1886.

[2]宋文.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京:電子工業(yè)出版社,2007:128-144.

[3]Ping S.Delaymeasurement time synchronization for wireless sensor networks(IR-TR-2003-64).Intel Research Center,2003.

[4]MarotiM,Kusy B,Simon G.The Flooding time synchronization inw ireless sensor networks:ACM SenSys'04,November 2004,Baltinore[C].

[5]呂治安.ZigBee網(wǎng)絡(luò)原理與應(yīng)用開(kāi)發(fā)[M].北京:北京航空航天大學(xué)出版社,2008:120-140.

[6]封紅霞,周瑩.無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步算法誤差分析[J].儀器儀表標(biāo)準(zhǔn)化與計(jì)量,2006(6):30-33.