一種新的無線傳感器網(wǎng)絡時間同步算法

游繼安，李　哲

(湖北工程學院 新技術學院，湖北 孝感 432000)

一種新的無線傳感器網(wǎng)絡時間同步算法

游繼安，李哲

(湖北工程學院 新技術學院，湖北 孝感 432000)

摘要：在分析以往各種時間同步優(yōu)化算法的基礎上,提出一種改進的無線傳感器網(wǎng)絡時間同步算法。該算法主要分為三步：首先對節(jié)點進行篩選，排除通信有故障的節(jié)點，然后將全網(wǎng)節(jié)點進行分層以減少WSN網(wǎng)絡的復雜性，最后設計相應的傳輸協(xié)議，利用時間同步算法對分層后的節(jié)點進行時間同步。實驗結果表明，該算法不僅明顯提高了網(wǎng)絡同步時間的準確度，而且減少了計算時間開銷。

關鍵詞：無線傳感器網(wǎng)絡;時間同步;分層;傳輸協(xié)議

中圖分類號：TP393.1

文獻標志碼：碼：A

文章編號：號：2095-4824(2015)06-0059-07

收稿日期：2015-09-11

基金項目：湖北工程學院新技術學院科學研究項目(Hgxky12)

作者簡介：游繼安(1987-)，男，湖北孝感人，湖北工程學院新技術學院助教，碩士。

Abstract：Based on the analysis of the advantages and disadvantages of the previous various time synchronization algorithms, an improved WSN time synchronization algorithm is proposed. The newly proposed algorithm is divided into three steps. First, the fault nodes are excluded from the network. Second, the layering nodes in the whole network are conducted to reduce the complexity of the WSN. Finally the corresponding transmission protocol is designed for time synchronization of layered nodes. Experimental results showed that the proposed algorithm significantly improved the network synchronization time and reduced the computational cost at the same time.

無線傳感器網(wǎng)絡(Wireless Sensor Networks, WSN)的研究起源于越戰(zhàn)，主要應用于軍事領域，直到“911事件”后，才迎來了WSN的飛速發(fā)展。目前，無線傳感網(wǎng)絡已經(jīng)在環(huán)境監(jiān)測、工業(yè)、農業(yè)、醫(yī)療、太空探索以及軍事等諸多領域都有廣泛的應用[1-2]。

WSN主要包括傳感器，微控制器以及網(wǎng)絡通信三個部分。以上三部分中，傳感器與微控制器在市場上的應用相對來說比較成熟。只有網(wǎng)絡通信這一部分有較大的研究空間。確切地說，決定一個WSN系統(tǒng)的優(yōu)劣并不取決于WSN的硬件配置，而是網(wǎng)絡通信算法現(xiàn)階段。WSN通信主要存在能量受限、擴展性、魯棒性、精確性以及收斂性等問題，而在以上問題中，時間一致性是眾多問題中最基礎的問題之一。

常規(guī)的時間同步方法分為兩步。第一步是對每個網(wǎng)絡的中心節(jié)點的時間進行同步，該同步方法稱為時間比對。目前，常規(guī)的時間比對系統(tǒng)主要有以下六類：(1)GPS[3]；(2)GLONASS[4]；(3)中國北斗衛(wèi)星導航定位系統(tǒng)[5]；(4)電視時鐘系統(tǒng)[6]；(5)OMEGA系統(tǒng)[7]；(6)羅蘭——C導航系統(tǒng)和無線電報時系統(tǒng)[8-9]。在以上六種時間比對方法中，GPS系統(tǒng)與北斗系統(tǒng)應用最為廣泛。第二步是運用時間同步算法達到同步網(wǎng)絡中所有節(jié)點時間的目的。對于常規(guī)的時間同步算法，應用較為廣泛的有RBS、TPSN和FTSP等算法。

1常規(guī)的時間同步算法

1.1RBS-參考廣播時間同步協(xié)議

RBS算法是由加州大學Jeremy Elson等人于2002年提出的，是一種基于Receiver-Receiver架構的時間同步模式。該算法中，Sender利用廣播發(fā)送消息的方式將消息發(fā)出后，兩個不同Receiver接收消息后，記錄消息中的時間和記錄接收到消息的時間，然后兩個不同Receiver交換記錄接收到消息的時間，就知道兩個Receiver間的時鐘偏移量，其中一個Receiver根據(jù)這個時間偏移量來更改自己的時間值，另一個Receiver的時間值不變。RBS的時間同步方法如圖1所示。

1.2TPSN-傳感器網(wǎng)絡時間同步協(xié)議

TPSN算法是加州大學網(wǎng)Saurabh Ganeriwal 等人于2003年提出的，該協(xié)議采用雙向成對同步方法，這種方法主要由兩個階段組成：分層階段與同步階段。首先選取一個根節(jié)點，并由這個根節(jié)點把分層數(shù)據(jù)包廣播出去，收到數(shù)據(jù)包的節(jié)點確定自己的層次號后，將重新打包的數(shù)據(jù)包廣播出去，重復該過程，直到所有節(jié)點均已分層完畢，分層過程如圖2(a)中的第1步(虛線標識的動作)所示。

李哲(1986-)，男，湖北漢川人，湖北工程學院新技術學院講師，博士研究生。

圖1　RBS時間同步協(xié)議的基本原理

(a)

(b)

同步階段：該階段的基本模式如圖2(b)所示，該階段的核心點是節(jié)點間成對地交換帶有時間同步參數(shù)的消息，以達到時間同步的目的。該階段可以用以下公式進行計算：

(1)

(2)

上式中：δ為時間漂移，d為時間傳播延遲。

該同步方法不僅同步精度高(同步精度大約為RBS同步方法的兩倍)，而且在大型網(wǎng)絡中仍有較好的同步性能，該算法的同步誤差只取決于網(wǎng)絡中的同步跳數(shù)，與網(wǎng)絡中的總節(jié)點數(shù)無關，而且該算法也有較好的可擴展性。

1.3FTSP時間同步算法

FTSP算法是由美國田納西州范德堡大學的Branislav Kusy等人于2004年提出的，其主要思想是使用單雙向結合傳播消息的方法實現(xiàn)節(jié)點間的時間同步，廣播消息的形式如圖3所示。

圖3　FTSP的消息交換圖

FTSP主要的基本過程是：首先給每個節(jié)點規(guī)定一個全網(wǎng)唯一的ID標志號,通過根節(jié)點將時間同步包sync廣播出去，收到時間同步包的節(jié)點根據(jù)時間同步包來同步自身的時間，同步完成后，生成一個新的時間包，并廣播出去，達到同步全網(wǎng)節(jié)點時間的目的。同步過程如圖4所示。

圖4　FTSP中數(shù)據(jù)包經(jīng)過無線信道

如果為多跳網(wǎng)絡，則在廣播時間同步前，還需要對網(wǎng)絡上的節(jié)點進行分層，然后再對所有節(jié)點進行時間同步。

2系統(tǒng)設計

2.1改進的時間同步算法

2.1.1算法原理

總結現(xiàn)有WSN時間同步算法的特點可知，當WSN節(jié)點數(shù)量較少且分布集中時，采用簡單的算法就可以解決時間同步問題，如RBS算法。但當節(jié)點數(shù)量較多、網(wǎng)絡結構復雜，且網(wǎng)絡節(jié)點數(shù)目不確定時，就需要尋求更加有效的時間同步算法。復雜的網(wǎng)絡通常不能一次性使所有節(jié)點時間同步，因此，就必須對網(wǎng)絡進行分層，而分層較有效的一種方法是廣播消息分層法，當WSN所有節(jié)點分層完后，再對WSN的所有節(jié)點進行時間同步。本文提出的改進時間同步算法主要分為三個階段。

第一階段為節(jié)點的篩選階段。節(jié)點的篩選過程，主要有兩個核心點。第一是在制節(jié)點時，需要核對節(jié)點的傳輸時間，例如，核對節(jié)點規(guī)合時，規(guī)定節(jié)點的單次單向傳輸時間范圍在[t1，t2](t1

第二階段是對全網(wǎng)節(jié)點進行分層，給每個節(jié)點分配一個層次號。在該階段中，所采用的分層方法是洪泛廣播方法。首先需要選取根節(jié)點，并規(guī)定該節(jié)點的層次號為0，然后由該節(jié)點廣播消息包，消息包主要包括該節(jié)點的ID號與該節(jié)點的層次號，收到廣播消息的節(jié)點取出消息包中的節(jié)點層次號與自身的層次號進行對比，若是自身的層次號比該層次號小1，則將該節(jié)點加入下層節(jié)點的列表中，若自身層次號大于該層次號，則改變自身層次號令其等于該層次號加1，并記錄上層節(jié)點的ID。最后，將本節(jié)點的層次號與ID號進行打包，并利用洪泛廣播的方式發(fā)送出去，不斷重復以上過程，直到所有節(jié)點都分層完畢為止。

第三階段為時間同步階段。從節(jié)點層次號為0的節(jié)點開始，逐層同步網(wǎng)絡中的其他節(jié)點，同步方法由雙向時間同步法改進而來。首先，根節(jié)點從下層節(jié)點列表中選取一個節(jié)點作為響應節(jié)點，然后，將時間同步消息廣播出去，接收到廣播消息的節(jié)點利用本地時間記錄消息的接收時間，只有根節(jié)點指定的響應節(jié)點向根節(jié)點返回消息，根節(jié)點接收到消息后，用雙向成對時間同步方法來計算時間偏移值δ、傳播延遲值d以及響應節(jié)點接收到消息的時間T2。然后，由根節(jié)點將包含這三個參數(shù)的數(shù)據(jù)包廣播出去，響應節(jié)點根據(jù)數(shù)據(jù)包中的時間偏移值δ和傳播延遲值d來調整本地時間，廣播域內的其他節(jié)點接收到數(shù)據(jù)包后，記錄接收時間T2'，由此計算出

(3)

T=t+δ'

(4)

式中：t為葉子節(jié)點接收消息的時間。層次號為1的節(jié)點時間同步完成后，再由根節(jié)點選取第一層節(jié)點中的部分節(jié)點(節(jié)點數(shù)目的選取根據(jù)實際網(wǎng)絡布局決定)作為根節(jié)點，重復之前的動作，直到所有節(jié)點的時間同步完成為止。消息交換及時間標記過程如圖5所示。

2.1.2算法流程

按上述三階段的時間同步過程，第一階段的工作需要提前完成，在網(wǎng)絡布局完成之后，再分別進行第二階段與第三階段的工作。其工作流程圖如圖6所示。

2.1.3通信協(xié)議

根節(jié)點與葉子節(jié)點通過無線串口進行連接，采用高級數(shù)據(jù)鏈路控制(High Level Data Link Control，HDLC)協(xié)議進行串口通信。HDLC是一種數(shù)據(jù)鏈路層協(xié)議，確保傳送到下一層的數(shù)據(jù)在傳輸過程中能夠準確地被接收。一般來說，串口消息包括兩部分，即串口消息頭和有效載荷，沒有footer和metadata部分。完整的串口數(shù)據(jù)消息格式如圖7所示。

(c)

圖7　串口通信格式

在圖7所示的串口數(shù)據(jù)幀中，F(xiàn)占一個字節(jié)，表示幀定界符，標識幀的開始或者結束。HDLC規(guī)定每一個數(shù)據(jù)幀都必須以0x7E作為開始和結束標志。P占用一個字節(jié)，為TinyOS串口協(xié)議棧的協(xié)議字段(TinyOS是專門為WSN設計的操作系統(tǒng))，當該字段值等于0x44時，表示串口數(shù)據(jù)幀需要確認，接收端收到數(shù)據(jù)幀后需要返回確認幀。當該字段值等于0x45時，則不需要返回確認幀；S為序列號字段，占一個字節(jié)長度；D表示包格式類型，占一個字節(jié)格式，默認值為0。payload的內容即為串口消息，包括串口消息頭和有效載荷部分，串口消息頭格式如圖7所示，最大有效載荷仍然使用默認的28個字節(jié)。CRC為兩個字節(jié)的循環(huán)校驗碼，采用ITU-T標準CRC生成多項式。G_16(x) = x16+ x12+ x5+ 1，校驗范圍從P字段開始到payload結束。

(1)下行數(shù)據(jù)。當WSN根節(jié)點向葉子節(jié)點以洪泛廣播形式發(fā)送消息時，需要按照協(xié)議規(guī)定的格式封裝數(shù)據(jù)包，然后發(fā)送到串口。普通節(jié)點接收到串口數(shù)據(jù)后，按照協(xié)議進行解包，再根據(jù)命令類型封裝成不同的數(shù)據(jù)包，然后下發(fā)到網(wǎng)絡中。普通節(jié)點接收到根節(jié)點下發(fā)的命令后，需要記錄接收信息的時間T2，并從數(shù)據(jù)包中取出根節(jié)點所在的網(wǎng)絡號與自身的網(wǎng)絡號進行對比。當串口消息頭中的type字段值等于0x14時，表示是時間同步數(shù)據(jù)包，如果值等于0x15時，表示廣播分層數(shù)據(jù)包。串口消息頭的前兩個字節(jié)為根節(jié)點的ID號，串口消息頭的第三、第四字節(jié)分別為包類型與分發(fā)命令類型，第五、六個字節(jié)為δ，第七、八字節(jié)為d，第九字節(jié)為層次號，TinyOS規(guī)定下行數(shù)據(jù)必須有S字段。分發(fā)命令類型01表示下行數(shù)據(jù)，02表示上行數(shù)據(jù)。包類型分為廣播分層數(shù)據(jù)包01(如圖2(a)中的第1步)與廣播時間同步數(shù)據(jù)包02(如圖2(a)中的第3步)兩種。下行數(shù)據(jù)包格式如圖8所示。

圖8　下行廣播命令串口數(shù)據(jù)包示例

(2)上行數(shù)據(jù)。網(wǎng)絡中所有節(jié)點分層結束后，第一層節(jié)點開始向層次號為0的根節(jié)點發(fā)送消息，0號根節(jié)點接收到普通節(jié)點上傳的數(shù)據(jù)后，需要將數(shù)據(jù)進行解封，然后再封裝成串口消息包發(fā)送到根節(jié)點。上行數(shù)據(jù)不需要確認幀，因此P字段值為0x45。本文規(guī)定當串口消息頭中的type字段值等于0x35時，表示上傳時間同步數(shù)據(jù)，等于值0x36時表示上傳的傳感器數(shù)據(jù)，值等于0x37表示上傳的狀態(tài)數(shù)據(jù)，值等于0x38時表示上傳的拓撲數(shù)據(jù)。TinyOS規(guī)定上行數(shù)據(jù)沒有S字段。圖9為普通節(jié)點發(fā)送消息到WSN根節(jié)點的傳感器數(shù)據(jù)格式。

圖9　行串口數(shù)據(jù)包格式示例

需要指出的是，串口數(shù)據(jù)幀中CRC字段采用的是小端格式，即數(shù)據(jù)傳輸時先傳送低字節(jié)后再傳送高字節(jié)，其他數(shù)據(jù)采用的是大端格式，即數(shù)據(jù)傳輸時先傳送高字節(jié)后傳送低字節(jié)。狀態(tài)數(shù)據(jù)、拓撲數(shù)據(jù)格式和傳感器數(shù)據(jù)格式類似，僅僅是串口消息頭中的類型標識不同。

對RBS、TPSN、FTSP以及本文算法等4種算法的同步類型、同步方式、同步精度、算法復雜性以及算法收斂時間作比較，結果如表1所示。

表1　4種同步算法的比較

由以上分析得知，以上四種時間同步方法都采用了泛洪與廣播的方式。RBS對于節(jié)點較少且分布集中的網(wǎng)絡有較好的時間同步效果。TPSN算法采用雙向成對時間同步方法來同步節(jié)點時間，因此，該算法有較好的同步精度，但由于該算法對每個節(jié)點采用雙向成對同步方法，因此其收斂時間一般。FTSP算法采用單雙結合的方式對全網(wǎng)節(jié)點的時間進行同步，該算法的復雜度較高，同步精度也較高，但是其收斂時間較長。本文算法采用單向與雙向相結合的時間同步模式，因此算法復雜度較低，同度精度較高，收斂時間比較短。

3系統(tǒng)測試

利用軟件仿真方法來測試本文算法的性能，軟件仿真的具體步驟如下：

采用MATLAB對本文算法進行仿真，模擬出如下實驗環(huán)境：在面積為100 m×100 m的范圍內，網(wǎng)絡節(jié)點數(shù)為30，節(jié)點的通信半徑為10米。本文應用一個6×30的矩陣來表示無線網(wǎng)絡中的節(jié)點，每一列表示一個節(jié)點的相應信息，每個節(jié)點的第1行表示節(jié)點為的ID，第2、3行分別表示節(jié)點的橫坐標和縱坐標，第4行表示每個節(jié)點的初始時間，第5行表示每個節(jié)點所在的層次，第6行表示節(jié)點的剩余能量。

將表1中另外三種算法與本文算法進行比較，當某一普通節(jié)點失效時，上述四種同步算法分別按照各自的同步方法重新對所有網(wǎng)絡節(jié)點進行時間同步，圖10為某一節(jié)點失效后網(wǎng)絡中節(jié)點同步時間與誤差間的關系。

圖10　葉子節(jié)點失效后同步時間與誤差的關系

若某一普通節(jié)點失效或有新節(jié)點加入時，需要重新對網(wǎng)絡進行分層，并且重新配置網(wǎng)絡參數(shù)。本文改進的新型時間同步算法只需要通過鄰節(jié)點便可以計算出新加入節(jié)點的同步時間值。從圖11可以看出，本文算法明顯減少了節(jié)點的同步時間。

圖11　節(jié)點數(shù)與同步時間的關系

4結束語

本文提出了一種改進的時間同步算法，該算法極大地節(jié)省了節(jié)點的開銷，最大限度的減少了因節(jié)點缺失造成的損失。同時，該算法因為采用了單雙結合的時間同步方法，因此具有較好的時間同步精度與較高的時間同步效率。經(jīng)測試，本文提出的時間同步算法具有較高的魯棒性，時間精度較高，具有較好的實際應用價值，且擴展性較好。

[參考文獻]

[1]AN T R, Gao F, Zhang G, et al. Integration of IoT and DRAGON-lab in cloud environment[J].中國郵電高校學報:英文版, 2012(2):87-91

[2]Lai M, Zhou T, Liu Z. IOT technology application model research of transportation industry in China[J].中國工程科學:英文版, 2013, 11:90-96.

[3]Yi T H, Li H N, Gu M. Experimental assessment of high-rate GPS receivers for deformation monitoring of bridge[J].Measurement, 2013, 46(1):420-432.

[4]郭際明, 孟祥廣, 李宗華,等.GLONASS衛(wèi)星廣播星歷精度分析[J].大地測量與地球動力學, 2011, 1(1):68-71.

[5]胡志剛. 北斗衛(wèi)星導航系統(tǒng)性能評估理論與試驗驗證[D].武漢:武漢大學,2013.

[6]王冠凌,郎朗,王滿海,等.基于ZigBee和GPS廣播電視時鐘授時系統(tǒng)的研究[J].自動化與儀器儀表,2008(5):15-18.

[7]梁麗敏. 提高Omega系統(tǒng)疊前時間偏移處理質量的技術對策[C]//中國地球物理學會第22屆年會論文集, 2006.

[8]林雪原,何友. GPS/羅蘭C/SINS/AHRS組合導航系統(tǒng)及試驗[J].電子科技大學學報,2008,37(1):4-7.

[9]何松. 基于FPGA的羅蘭C路基導航系統(tǒng)RS編譯碼器的設計與實現(xiàn)[D].成都：西南交通大學,2014.

A Novel Time Synchronization Algorithm for Wireless Sensor Networks

You Ji’an, Li Zhe

(CollegeofTechnology,HubeiEngineeringUniversity,Xiaogan,Hubei432000,China)

Key Words：wireless sensor networks; time synchronization; layering; transmission protocol

(責任編輯：張凱兵)