鄧雪峰,孫瑞志,聶　娟,2,張永瀚

(1.中國農(nóng)業(yè)大學(xué) 農(nóng)業(yè)部農(nóng)業(yè)信息獲取技術(shù)重點實驗室,北京 100083;2.北京農(nóng)學(xué)院 計算機與信息工程學(xué)院,北京 102206)

?

一種多跳無線傳感器網(wǎng)絡(luò)時間同步方法

鄧雪峰1,孫瑞志1,聶娟1,2,張永瀚1

(1.中國農(nóng)業(yè)大學(xué) 農(nóng)業(yè)部農(nóng)業(yè)信息獲取技術(shù)重點實驗室,北京 100083;2.北京農(nóng)學(xué)院 計算機與信息工程學(xué)院,北京 102206)

摘要:針對無線傳感器網(wǎng)絡(luò)中時間同步技術(shù)，降低同步誤差的問題，通過優(yōu)化生成樹模型的結(jié)構(gòu)，利用協(xié)作同步時間同步技術(shù)與生成樹生成過程結(jié)合，降低生成樹的深度，解決同步中誤差累積，減少了時間同步誤差。通過模擬實驗證明，節(jié)點經(jīng)過優(yōu)化后的同步誤差累積低于未優(yōu)化節(jié)點。本方案適合對常用的時間同步算法的優(yōu)化。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);時間同步;協(xié)同;誤差;優(yōu)化

隨著無線通信技術(shù)、嵌入式技術(shù)的發(fā)展,無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)已經(jīng)廣泛的應(yīng)用于軍事、農(nóng)業(yè)、環(huán)保、醫(yī)療、建筑、制造等領(lǐng)域。

在互聯(lián)網(wǎng)(Internet)技術(shù)中,時間同步問題已經(jīng)有了成熟的協(xié)議,可以精確的實現(xiàn)當前互聯(lián)網(wǎng)中的時間同步問題。有代表性的有:NTP(Network Time Protocol)時間同步協(xié)議[1]。利用GPS(Global Position System)時間同步技術(shù)。

由于WSN自身的特點，其中的時間同步問題不能直接利用Internet中使用的技術(shù),如NTP時間同步協(xié)議并不適合網(wǎng)絡(luò)不穩(wěn)定、網(wǎng)絡(luò)拓撲結(jié)構(gòu)經(jīng)常改變的無線傳感器網(wǎng)絡(luò)。GPS需要專門的設(shè)備進行時間同步,而傳感器的功能受限、成本受限的環(huán)境往往不能單獨配備相關(guān)的設(shè)備。

針對WSN的特點,ELSON et al提出了無線傳感器網(wǎng)絡(luò)時間同步問題[2]。此后,學(xué)術(shù)界提出了多種WSN時間同步算法。而這幾種方式的解決方案中,單跳節(jié)點的WSN的時間同步技術(shù)基本可以用第一種方案滿足同步需求。而多跳WSN由于其拓撲結(jié)構(gòu)復(fù)雜,基本上可以把以上各種方案分為兩大類,一種是以時間同步根節(jié)點為中心,根據(jù)同步目標節(jié)點到時間同步的根節(jié)點的路徑上的跳數(shù)而分層同步的集中式時間同步模型,另一種是以相鄰節(jié)點先同步而最后達到整個網(wǎng)絡(luò)同步的分簇式的自組織時間同步模型。

在實際應(yīng)用中,集中式時間同步模型現(xiàn)在的應(yīng)用較為廣泛,而對于集中式時間同步模型中一個重要的步驟就是建立層次結(jié)構(gòu)。一般來說,在同步的初始過程中將首先建立一個生成樹。由于時間同步目標節(jié)點到生成樹根節(jié)點的跳數(shù)的增加也會帶來誤差的積累,目標節(jié)點到生成樹根節(jié)點的跳數(shù)與生成樹的深度成正比。因此,降低生成樹的深度會降低誤差的增加。

筆者在分析了當前多跳WSN時間同步主要技術(shù)的情況下,對于時間同步集中式時間同步模型進行進一步分析,結(jié)合協(xié)作時間同步技術(shù),利用部分節(jié)點的協(xié)作時間同步降低時間同步中生成樹的深度,從而降低時間同步過程中的誤差累積。

1相關(guān)研究

時間同步技術(shù)對于WSN是一個基礎(chǔ)問題,由于WSN的通信范圍、傳感器節(jié)點性能以及功能受限制等因素,不能將現(xiàn)在的Internet網(wǎng)絡(luò)中同步的協(xié)議直接應(yīng)用于WSN時間同步問題上。自從WSN時間同步問題被提出后,針對WSN不同屬性的多種相關(guān)算法被提出。

1.1常用的WSN同步算法

比較常見的多跳WSN時間同步算法有TPSN(Timing-sync Protocol for Sensor Networks)，RBS(reference broadcast synchronization)[4]，DMTS(Delay Measurement Time Synchronization)[5]，F(xiàn)TSP(Flooding Time Synchronization Protocol)[6]，LTS(Lightweight Time Synchronization)[7]，HRTS(hierarchy referencing time synchronization)[8]等算法。

1.2WSN時間同步其它解決方案

螢火蟲時間同步算法與協(xié)作同步技術(shù)的提出給WSN時間同步技術(shù)提供了新的思路。

在1990年,文獻[9]中提出M&S模型,該模型采用脈沖耦合振蕩器的原理,將目標同步節(jié)點抽象為振蕩器,通過同步信號達到各個節(jié)點共振,從而完成時間同步操作。因此,RFA(reachback firefly algorithm)[10]協(xié)議利用了螢火蟲同步算法的基本原理,并且降低了該模型的收斂時間。但是,脈沖耦合振蕩器的原理僅是螢火蟲同步模型在理論模型上模擬,還不能揭示其原理,并且實現(xiàn)這個模型受節(jié)點相似等條件約束。

協(xié)作同步機制是在文獻[11]中提出,在其后,文獻[12]中提出了空間平均的概念,協(xié)作同步機制的提出是以概率論為基礎(chǔ),利用同步節(jié)點相鄰的節(jié)點的共同作用,消除同步產(chǎn)生的誤差,理論上,當節(jié)點數(shù)越大時,同步產(chǎn)生的誤差越小,其同步結(jié)構(gòu)如圖1所示。

圖1　協(xié)作同步結(jié)構(gòu)圖Fig.1　Collaboration synchronization structure chart

協(xié)作同步過程由R0開始,首先也是建立整個網(wǎng)絡(luò)的層次結(jié)構(gòu),但是建立些分層結(jié)構(gòu)會記錄各層間所有的節(jié)點間的可通信的結(jié)構(gòu)。如,R0至R1層之間,時間同步根節(jié)點R0與R1層節(jié)點間的每個連通點只能與R0連接,此時只有一個路徑,而當同步信號由R1層向R2層節(jié)點傳播時,R1層可能有多個節(jié)點與R2層的目標節(jié)點有通路,在協(xié)作同步機制中,這樣的通路會被記錄,用來共同完成時間同步消息的傳播,由于各個節(jié)點的隨機誤差服從高斯分布,因此,可以利用平均的方案消除系統(tǒng)誤差,從而達到提升整個系統(tǒng)同步精度的目標。但是,協(xié)作同步機制中要求系統(tǒng)節(jié)點密度較高,才可以實現(xiàn)多個節(jié)點共同協(xié)作完成時間同步的目標,并且實際系統(tǒng)中現(xiàn)在應(yīng)用較少,還處于實驗階段。

綜上所述,在常用的WSN時間同步過程中,依層次對待同步的節(jié)點進行劃分,形成時間同步生成樹是時間同步的第一個步驟,不管用集中式同步還是分布式同步的方式。時間同步生成樹的深度在常用的WSN時間同步方案中起到了累積誤差的效果,因此降低生成樹的深度是對降低誤差是一個有效的途徑。在WSN的其它解決方案中,螢火蟲算法與協(xié)作同步算法在實際應(yīng)用中還是應(yīng)用較少,螢火蟲算法由于原理的模型至今依然是個可以探討的問題,協(xié)作同步的算法利用概率的方法可以降低系統(tǒng)的誤差,因此,本文將協(xié)作同步原理用于常用同步算法中的部分節(jié)點之中,從而降低生成樹的深度,在不改變網(wǎng)絡(luò)物理拓撲形式的基礎(chǔ)上,提升算法的精度。

2同步模型分析

WSN時間同步模型一般說來都以一個時間基準點開始。這個節(jié)點在同步過程中一般作為時間同步生成樹的根節(jié)點。同步的過程中一般是建立一個線性的時間同步模型,待同步的目標節(jié)點與同步基準節(jié)點間以消除節(jié)點間的時間差為目標進行通信。降低通信的誤差一直是WSN時間同步算法的一個改進目標。

2.1WSN時間同步拓撲結(jié)構(gòu)分析

Gwsn為一個WSN的拓撲結(jié)構(gòu)圖,設(shè)

式中：V為頂點集合；E為邊的集合，E=V×V.

不妨以圖1中的圖為例說明WSN的物理拓撲結(jié)構(gòu)。在時間同步協(xié)議中,設(shè)R0級的節(jié)點,即同步過程中的基準節(jié)點為v00；R1級的節(jié)點,分別設(shè)為v10,v11,v12，…；R2級的節(jié)點為v20,v21,v22，…；Rn級的節(jié)點為vn0,vn1,vn2，….則V={v00,v10,v11,v12，…,v20,v21,v22，…,vn0,vn1,vn2，…},E={e0010,e0011,e0012,…}.其中e0010代表v00至v10有一條消息通信路徑相連。

假設(shè)有如圖2所示的一個WSN拓撲結(jié)構(gòu),圖中虛線圓代表圓內(nèi)范圍內(nèi)節(jié)點可以通信,虛線箭頭代表節(jié)點間或以通信,但是在依照時間同步算法分層時,被生成樹忽略的通信路徑。因此

式中：V={v00,v10,v11,v20,v21,v22,v30,v31,v32}；E={e0010,e0011,e1020,e1021,e1121,e1122,e2030,e2031,e2131,e2232}.

圖2　WSN拓撲結(jié)構(gòu)Fig.2　WSN topology

2.2WSN時間同步生成樹

在進行時間同步時,第一個步驟就是生成一顆樹結(jié)構(gòu),從而對時間同步中的各個節(jié)點以時間同步基點為中心進行分層,并以此生成樹為基礎(chǔ)對各層的節(jié)點進行消息傳送。

Twsn為WSN時間同步的生成樹,滿足從根節(jié)點到任一節(jié)點必須有通路。Twsn中節(jié)點數(shù)與Gwsn中節(jié)點數(shù)相同,Twsn中的邊集是Gwsn中邊集的子集。

由以上條件,圖3中的生成樹為

式中：V={v00,v10,v11,v20,v21, v22,v30,v31,v32}；E={e0010,e0011,e1020,e1021,e1121,e2030,e2031, e2232}.即圖中實線邊組成的集合。

2.3WSN協(xié)作同步策略分析

文獻[12]中提出了利用空間同步消除誤差的WSN時間同步機制,由于WSN節(jié)點間的同步過程中,基準節(jié)點向其相鄰節(jié)點發(fā)送同步脈沖后,第i級節(jié)點與i+1級節(jié)點時間同步時,由于WSN拓撲結(jié)構(gòu)中,可能存在多個第i級節(jié)點可以與第i+1級節(jié)點中待同步節(jié)點具備通信能力,如圖3所示。

圖3　協(xié)作同步節(jié)點同步分析Fig.3　Synchronization analysis of collaboration syncnodes

其中不妨設(shè),第i層節(jié)點vij,vij+1，vij+2，vij+3，這些節(jié)點的下標表示的含義為第i層的第j個節(jié)點及j+1，j+2，j+3個節(jié)點，并都可以與第i+1層節(jié)點vi+1k(表示第i+1層第k個節(jié)點)通信。

由文獻[12]中,WSN時間同步節(jié)點滿足

式中：ci(t)為待同步的時鐘；i為偏移；αi為一個常量；Ψi(t)為一個隨機誤差,一般情況下服從N(0,σ2)的分布。

當多個第i層節(jié)點向第i+1層節(jié)點同時發(fā)送同步脈沖的時候,由于第i層節(jié)點服從均值為0的正態(tài)分布,因此第i層的誤差不會累積到第i+1層,從而達到了降低系統(tǒng)誤差的目標。如圖4所示的情況,第i+1層第k個節(jié)點同時接收到第i層節(jié)點j，j+1，j+2，j+3的同步脈沖,利用協(xié)作同步機制,第i+1層的節(jié)點k的時鐘應(yīng)該取第i層4個節(jié)點時鐘的平均值。

3部分節(jié)點協(xié)作時間同步策略

降低生成樹的深度可以提升時間同步算法的精度,即減少同步的誤差。一般來說,常用的同步算法生成樹的深度確定后,只能通過增加設(shè)備的精度等手段減少同步中產(chǎn)生的誤差,在2.3節(jié)中提出的協(xié)作同步算法是一個新的思路；但是算法要求WSN同步中節(jié)點密度要滿足要求,在現(xiàn)在使用的還較少,其利用多個節(jié)點協(xié)作降低系統(tǒng)誤差的方案可以應(yīng)用于其它同步算法中。本方案利用協(xié)作時間同步的方法,將生成樹中部分滿足協(xié)作同步的節(jié)點進行重新排列,生成一個虛擬的生成樹,從而總體上降低生成樹的深度,從而使常用的WSN時間同步算法得以改進,降低系統(tǒng)誤差。

3.1虛擬生成樹的生成

WSN中節(jié)點時間同步過程中,常用的時間同步算法一般只利用生成樹所生成的路徑進行時間同步。如圖2所示,生成樹為實線連接的網(wǎng)絡(luò)部分；虛線連接的網(wǎng)絡(luò)部分同樣可以用于通信,傳送同步信息,但不是每一個節(jié)點均有多個傳送信息路徑。由2.3節(jié)中理論分析,如果利用這些非實線的連接路徑傳送時間同步信息,節(jié)點間就可以滿足協(xié)作同步條件；因此,可以利用這些可協(xié)作同步的節(jié)點對生成樹進行改進,建立一虛擬生成樹,在保證同層結(jié)點誤差累積不變的情況下,擴大生成樹的寬度,降低生成樹的深度,從而減少生成樹中離根節(jié)點較遠節(jié)點的同步誤差累積。

如圖4中所示,虛擬生成樹產(chǎn)生的過程主要由以下幾步構(gòu)成。為了說明問題的簡化,不妨設(shè)如果有2個以上i層節(jié)點可以與生成樹中i+1層節(jié)點進行通信,即可認為第i+1層的這個節(jié)點滿足協(xié)作同步通信條件。一般應(yīng)用中,應(yīng)該取更多的節(jié)點作為參考才能更好的滿足消除誤差的要求。

圖4　虛擬生成樹產(chǎn)生過程Fig.4　Process of virtual spanning tree generation

圖4中實線連接的圖是由圖2中的拓撲結(jié)構(gòu)生成的生成樹,v21節(jié)點分別由上層節(jié)點v10和v11連接,在產(chǎn)生生成樹的過程中,v11到v21被忽略。本方案利用這個忽略的邊,把v21作為第2層可以進行協(xié)作同步的節(jié)點處理,由v00至v21產(chǎn)生一條虛擬路徑,從而將v21的位置提升至生成樹的第2層；處理完v21后繼續(xù)查找第2層中是否有其它節(jié)點滿足條件增加虛擬路徑。

將第2層處理完成后,生成樹第1層將轉(zhuǎn)換成一個有實路徑與虛擬路徑結(jié)合的結(jié)構(gòu)。在處理第3層的過程中,將通過實線連接的生成樹節(jié)點按上一步掃描,將可提升層次的節(jié)點列出,上一步中新增加的虛擬節(jié)點不參與掃描;實線列出的節(jié)點掃描完畢后,將所有虛擬到第1層的節(jié)點對其下層節(jié)點進行同實線連接節(jié)點一樣的掃描步驟。這兩部分完成后,將新發(fā)現(xiàn)的可以提升層次的節(jié)點提升層次。

3.2虛擬生成樹同層節(jié)點誤差說明

虛擬生成樹中的同層節(jié)點在同步時,有兩種節(jié)點,一種是原始生成樹中沒有優(yōu)化過的普通節(jié)點,這部分節(jié)點的誤差與節(jié)點所在的生成樹的層次成正比,層次越深的節(jié)點累積的誤差越多,第i層節(jié)點累積的誤差i的函數(shù)；而第i層的虛擬節(jié)點的累積誤差跟非虛擬節(jié)點應(yīng)該是相同的,以圖5中節(jié)點v21為例。v21節(jié)點在未經(jīng)優(yōu)化前處于生成樹的第2層,如果按照普通的同步方案,v21應(yīng)該在同步的第二跳獲得時間同步消息,因此,第1層節(jié)點v10的誤差將累積到v21上,但是采用了本文的方案,v21提升至生成樹的第1層后,根據(jù)協(xié)作同步方案的理論,由v10與v11共同產(chǎn)生同步信號,此時用平均的方法消除了系統(tǒng)誤差,節(jié)點v21相當直接與v00進行時間同步,從而使v21的誤差累積與v10，v11達到同一級別。

同樣的情況在第i層同樣適用,因此,通過此方案降低后的生成樹,在第i層得到的誤差將與原生成樹第i層的誤差是同一級別。

3.3虛擬生成樹時間同步

利用虛擬生成樹重新建立WSN時間同步生成樹,可以降低生成樹的深度的同時不增加相應(yīng)層次的誤差累積,有效的減少距離根結(jié)點較遠處的時間同步誤差累積,建立虛擬生成樹的步驟如下:

1) 以v00為根節(jié)點掃描Gwsn,產(chǎn)生只有第一跳節(jié)點虛擬生成樹Twsn,此時的葉子節(jié)點都是與v00相連的第一跳節(jié)點。

2) 從Twsn的葉子節(jié)點向第2層節(jié)點開始掃描Gwsn,設(shè)定可以協(xié)作同步的最少節(jié)點數(shù)為N,即當Twsn此時的某個葉子節(jié)點的下一跳節(jié)點在Gwsn的入度大于N時,該節(jié)點滿足提升層次的條件,即建立一條虛擬邊,連接該節(jié)點與其父節(jié)點的父節(jié)點。本次掃描結(jié)束后,第2層節(jié)點中有直接與根結(jié)點相連的一跳節(jié)點,也有通過N個第一跳節(jié)點,誤差理論上累積等同于第一跳節(jié)點的虛擬第2層節(jié)點,標記虛擬節(jié)點的實際跳數(shù)與所在的虛擬生成樹深度,并把虛擬節(jié)點實際跳數(shù)發(fā)布給所有本層節(jié)點。

3) 掃描虛擬生成樹Twsn此時的葉子節(jié)點,所有節(jié)點按第2層掃描的原則標記,再次進行類似第2步的掃描并標記節(jié)點的層次與跳數(shù),并把本層虛擬節(jié)點實際最大的跳數(shù)發(fā)布給本層所有節(jié)點。

4) 重復(fù)第3步,直到所有的節(jié)點都被插入到虛擬生成樹中。

虛擬生成樹生成后,本方案的時間同步步驟為:

1) 由虛擬生成樹的根節(jié)點發(fā)送時間同步消息及協(xié)作時間同步脈沖(同步脈沖形式如文獻[12]中提出的方案)。

2) 第i層節(jié)點接受到同步脈沖有兩種情況,由于第i層節(jié)點有真實第i跳節(jié)點也同時有跳數(shù)大于i的虛擬節(jié)點組成,第i層通過對同步脈沖的計算,可以計算出本層節(jié)點最大跳數(shù)脈沖到達時間,所有本層節(jié)點等待最大跳數(shù)脈沖到達后,向下層節(jié)點發(fā)送計算后的多個協(xié)作同步脈沖。

4方案證明與驗證

本方法對WSN時間同步算法給予優(yōu)化,主要利用部分節(jié)點的協(xié)作同步優(yōu)化了多跳WSN算法中由于跳數(shù)增加帶來的時間同步誤差累積。在最好的情況下,如果所有的虛擬生成樹除了第1層節(jié)點外,其它層次的節(jié)點均為虛擬節(jié)點的情況下,本方案退化成協(xié)作時間同步算法,系統(tǒng)誤差達到最小值;如果虛擬生成樹中無虛擬節(jié)點,系統(tǒng)沒有被優(yōu)化。

優(yōu)化過程中,最后的虛擬生成樹比不優(yōu)化的情況下會減少一層或同樣深度,但是,如果虛擬生成樹中有某層全部為虛擬節(jié)點,則系統(tǒng)誤差在該層以下各層中至少減少一個層次累積。因此,優(yōu)化后的虛擬生成樹中,各層節(jié)點的誤差累積小于等于不優(yōu)化的方案。

本方案采用文獻[13]中的誤差分布方案,各實驗節(jié)點的時鐘誤差假設(shè)服從正態(tài)分布(μ=0,σ=10μs),以圖4所示的WSN結(jié)構(gòu)為例,優(yōu)化算法以TPSN算法為待優(yōu)化的算法,節(jié)點可以協(xié)作同步的最少節(jié)點數(shù)設(shè)計為N=2.按照3.2節(jié)中的步驟生成的虛擬生成樹如圖5所示。

圖5　虛擬生成樹實驗Fig.5　Experiment of virtual spanning tree

由于N=2,所以,位于第2層的v21節(jié)點可以優(yōu)化提升層次至第1層,故算法掃描完第1層后,第1層的結(jié)點有v10，v11，v21,其中v21為虛擬節(jié)點,在掃描完第1層后,在第1層所有節(jié)點處標注第1層最大跳數(shù)為2,v21上標注實際跳數(shù)為2,同時標注自身所處于的層為1，完成了第1層的掃描,以第1層節(jié)點為葉子節(jié)點,掃描第2層節(jié)點,可以發(fā)現(xiàn)v31為入度為2的節(jié)點,故可以進行優(yōu)化提升層次,同樣,掃描后將v31標注實際跳數(shù)為3,同時標注自己所處扔層次為2,并在第2層所有節(jié)點標注第2層最大跳數(shù)為3 .

虛擬生成樹生成完畢后同步過程為,由根節(jié)點發(fā)布時間同步信號,如本例中,將發(fā)送TPSN同步消息,發(fā)送一個協(xié)作同步脈沖,按照協(xié)作同步的過程,發(fā)送m個協(xié)作同步脈沖,間隔為d.

虛擬生成樹的第1層節(jié)點如果自身標注跳數(shù)與自身所處層數(shù)相同的節(jié)點為非虛擬節(jié)點,如v10,v11,直接按照公式利用接收到的時間根節(jié)點發(fā)送的時間同步脈沖進行時間校正,而v21等m個協(xié)作同步脈沖結(jié)束后,接收由v10，v11轉(zhuǎn)發(fā)的同步脈沖,此時,第1層節(jié)點同步完成,同時,v10，v11由于已知本層最大的跳數(shù)為2,在等v21接收完m個同步脈沖后,與v21同時向虛擬生成樹第2層節(jié)點發(fā)送協(xié)作同步脈沖,v21由于是利用協(xié)作同步方式獲得的時鐘同步信息,雖然其跳數(shù)為2,但系統(tǒng)誤差與v10，v11一致。v31的時間同步過程為v31等待第2層傳送的時間同步脈沖,具體情況為等待2md個周期后,收到由v21傳送的時間同步消息,但是v31此時已經(jīng)成為虛擬生成樹的第2層節(jié)點,它僅接收上層節(jié)點的同步消息,因此v31接收虛擬節(jié)點v21發(fā)送的時間同步消息,誤差累積兩次,因此跟同層節(jié)點v20,v22誤差累積相當。

經(jīng)實驗,圖5中上半部分為未利用本方案前,下半部分為利用本方案后,圖中所有節(jié)點在經(jīng)過一次實時同步后,圖6為各節(jié)點的模擬實驗誤差圖,圖中取做7次模擬實驗的誤差數(shù)據(jù)。

圖6　模擬實驗誤差數(shù)據(jù)圖Fig.6　Experiment of virtual spaning tree

圖6中各個節(jié)點取7次實驗結(jié)果,每一個系列代表同一個節(jié)點在7個連續(xù)時間同步脈沖中的本身節(jié)點的誤差值。假設(shè)各個節(jié)點的誤差分布服務(wù)正態(tài)分布。

在經(jīng)本方案優(yōu)化后主要有兩個節(jié)點的時間同步誤差有所改變,如圖7所示。圖中各個節(jié)點未經(jīng)累積的曲線代表各個節(jié)點在沒有經(jīng)過誤差累積的誤差的均值,是圖6中7次實驗的誤差的均值。優(yōu)化方案的曲線代表經(jīng)本方案優(yōu)化后各個節(jié)點的累積誤差值,未經(jīng)優(yōu)化方案展示的是時間同步過程中一般方法所帶來的累積誤差,由圖中可以看出在本方案中,如圖5中的實例,v21與v31節(jié)點在優(yōu)化過程中降低了時間同步誤差。圖中標注節(jié)點順序(n)分別依次代表節(jié)點v00,v10,v11,v20,v21,v22,v30,v31,v32,同圖中變化趨勢可以看出在第5個節(jié)點和第8個節(jié)點的誤差明顯較示優(yōu)化方案有所降低,其中第5個節(jié)點對應(yīng)v21節(jié)點,第8個節(jié)點對應(yīng)v31節(jié)點。

圖7　時間同步分析圖Fig.7　Time synchronization analysis chart

分別對v21,v31的誤差優(yōu)化與未優(yōu)化狀態(tài)進行對比分析。顯然v21在未優(yōu)化前v21獲得時間同步信息路徑為v00→v10→v21,優(yōu)化后v00→(v10與v11協(xié)作)→v21.由于v10與v11協(xié)作完成了一跳的時間同步過程,因此這一跳時間同步過程沒有帶來系統(tǒng)誤差；同樣v31的同步誤差僅由v21帶來,在未優(yōu)化的情況下,其誤差由v10,v20經(jīng)過兩次傳遞時間同步消息,積累兩次系統(tǒng)誤差。

經(jīng)過以上過程的分析,可以說明,在利用WSN中部分節(jié)點間協(xié)作時間同步的方法,可以減少系統(tǒng)中部分節(jié)點的時間同步誤差。在節(jié)點密度較多的情況下,節(jié)點間通信更加密集,效果會更突出。

5總結(jié)

總結(jié)了WSN中時間同步算法,在常用的時間同步算法的設(shè)計中,生成樹的深度是影響系統(tǒng)誤差累積的主要因素,決定了離時間同步基準節(jié)點越遠的節(jié)點同步時產(chǎn)生的系統(tǒng)誤差越大。在引入了部分節(jié)點協(xié)作時間同步的方案后,可以降低系統(tǒng)中可以利用協(xié)作時間同步部分節(jié)點的系統(tǒng)誤差積累,利用本方案可以優(yōu)化常用的WSN時間同步算法。

參考文獻：

[1]MILLS D L.Internet time synchronization: the network time protocol[J].IEEE Transactions on Communications,1989,39(10):1482-1493.

[2]ELSON J,REMER K.Wireless sensor networks: a new regime for time synchronization[J].Proc of the First Workshop on Hot Topics in Networks,2003,33(1):149-154.

[3]GANERIWAL S,KUMAR R,SRIVASTAVA M B.Timing-sync protocol for sensor networks[C]∥Proceedings of the 1st international conference on Embedded networked sensor systems.ACM,2003:138-149.

[4]ElSON J,GIROD L,ESTRIN D.Fine-grained time synchronization using reference broadcasts[C]∥Proceedings of the Fifth Symposium on Operating Systems Design and Implementation(OSDI 2002),2002.

[5]SU P,SU P.Delay measurement time synchronization for wireless sensor networks[EB/OL].http:∥www.intel-reserch.net/Publications/Berkeley/08112003132T-127.Pdf,2003.

[7]GREUNEN J V,RABAEY J. Lightweight time synchronization for sensor networks[J].Workshop on Wireless Sensor Networks and Applications WSNA,2003:11-19.

[8]DAI H,HAN R.TSync:A lightweight bidirectional time synchronization service for wireless sensor networks[J].Acm Sigmobile Mobile Computing & Communications Review,1994,8(8):125-139.

[9]MIROLLO R E,STROGATZ S H.Synchronization of pulse-coupled biological oscillators[J].Siam Journal on Applied Mathematics,1990,50(6):1645-1662.

[10]WERNER-ALLEN G,TEWARI G,PATEL A,et al.Firefly-inspired sensor network synchronicity with realistic radio effects[C]∥Proc.of the Third Int’l Conf.on Embedded Networked Sensor Systems,2005:142-153.

[11]HU A S,SERVETTO S D.On the scalability of cooperative time synchronization in pulse-connected networks[J].IEEE Transactions on Information Theory,2006,14(6):2725-2748.

[12]HU A S,SERVETTO S D.A scalable protocol for cooperative time synchronization using spatial averaging[J].EprintArxiv:cs/0611003,2006.

[13]PALCHAUDHURI S,SAHA A K,JOHNSON D B.Adaptive clock synchronization in sensor networks[C]∥Proceedings of the 3rd international symposium on Information processing in sensor networks.ACM,2004:340-348.

(編輯：劉笑達)

A Time Synchronization Method of Multihop Wireless Sensor Network

DENG Xuefeng1,SUN Ruizhi1,NIE Juan1,2,ZHANG Yonghan1

(1.KeyLaboratoryofAgriculturalInformationAcquisitionTechnology(Beijing),MinistryofAgricultureP.R.China,ChinaAgriculturalUniversity,Beijing100083,China;2.CollegeofComputerandInformationEngineering，BeijingUniversityofAgriculture,Beijing102206，China)

Abstract:The way to reduce the time synchronization (TS) error between crunodes has been a hot issue in research of TS technology in wireless sensor network. In this research, we solve the problem of error accumulation when sending TS message by optimizing the structure of spanning tree established during TS. Combination of collaboration TS scheme and spanning tree(ST) can reduce the deepth of ST and decrease TS errors. Simulation experiments show that synchronization error accumulation of optimized node is less than that of non-optimized node.

Key words:wireless sensor network;time synchronization;cooperative;blunder;majorization

文章編號:1007-9432(2016)02-0183-07

*收稿日期：2015-05-28

基金項目：中央高校基本科研業(yè)務(wù)費專項基金資助項目:農(nóng)業(yè)大數(shù)據(jù)關(guān)鍵技術(shù)研究與應(yīng)用(2015XD001)

作者簡介：鄧雪峰(1975-),男，吉林白城人，博士生，主要從事移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)研究，(E-mail)dxf75@sohu.com 通訊作者：孫瑞志，教授，博士生導(dǎo)師，主要從事農(nóng)業(yè)信息化技術(shù)、計算機支持的協(xié)同工作的研究，(E-mail)sunruizhi@cau.edu.cn

中圖分類號:TP31,TP39

文獻標識碼:A

DOI：10.16355/j.cnki.issn1007-9432tyut.2016.02.012