基于變長幀的無線傳感器網絡時間同步算法

王 晶，張 帥，羅炬鋒，高 丹，王營冠

(中國科學院上海微系統與信息技術研究所物聯網系統技術實驗室，上海 201899)

1 概述

無線傳感器網絡作為構建通信環境的基礎架構，由大量隨機布設的傳感器節點組成，這類網絡具有資源受限、低功耗、多跳、自組織、應用種類多等特點。時間同步是傳感器網絡的重要支撐技術，它服務于傳感網的多種應用，如定位技術、睡眠機制、MAC層協議、調度機制等。因此，對無線傳感器網絡時間同步技術進行研究是十分必要的。

時間同步協議的一個研究重點是在保證同步精度的前提下，降低同步過程的通信開銷。現有多數算法均強調單跳同步精度，未考慮同步開銷問題。而傳感器節點本身能量有限，節點無線收發會消耗大量能量。針對該問題，本文提出一種基于變長幀的傳感器網絡時間同步算法，同時對傳感器時間同步的收斂時間進行分析。

2 基本模型及典型算法

無線傳感器網絡時間同步算法包含以下3種基本模型：發送者-接收者模型，成對同步模型和接收者-接收者同步模型。

(1)基于發送者-接收者模型的典型算法主要包括洪泛時間同步協議(Flooding Time Synchronization Protocol,FTSP)[1]和時延測量時間同步(Delay Measurement Time Synchronization,DMTS)[2]，該模型通過MAC層時間戳機制去除通信過程中的隨機時延。由于其簡單、可靠等特點，發送者-接收者同步可以很好地應用于各種傳感器網絡，是傳感網的事實同步算法。此外，基于擴散機制的傳感網同步協議[3]采用與洪泛時間同步協議相同的多跳方案，通過信息擴散實現全網絡時間同步。相對于發送者-接收者同步，成對同步模型具有更高的同步精度。

(2)基于成對同步模型的同步算法包括輕量型時間同步(Lightweight Time Synchronization,LTS)[4]、傳感網時間同步協議(Timing-sync Protocol for Sensor Networks,TPSN)[5]、極小同步和微型同步(Tiny-Sync And Mini-Sync,TS-MS)[6]和基于多層抽樣反饋的傳感網時間同步算法[7]。此類同步算法通過2個節點相互交換同步信息實現單跳同步，利用信息傳播過程的對等性降低通信時延引起的同步誤差。輕量型時間同步和傳感網時間同步協議采用生成樹機制實現全網時間同步，根節點的時間信息沿著生成樹經歷多跳傳遞給目的傳感器節點。極小同步和微型同步算法采用邊界估計方法代替線性回歸實現時鐘頻偏估計。基于多層抽樣反饋的傳感網時間同步算法通過在生成樹中進行鏈路抽樣反饋獲取網絡同步狀況。這類同步算法抗毀能力差，通信負載和能量開銷較大。

(3)基于接收者-接收者同步模型的經典算法為參考廣播同步(Reference Broadcast Synchronization,RBS)[8]和能量高效參考廣播同步[9]。參考廣播同步利用參考節點廣播參考信息，其廣播域內各節點記錄并交換接收時間信息，實現相互的同步。參考節點的引入能夠完全去除發送端時延，因此，接收者-接收者同步模型在3種同步模型中具有最高的同步精度，但其缺點在于參考節點未同步、通信開銷大以及多跳同步擴展復雜。

上述算法均強調單跳同步精度，沒有考慮同步開銷問題。而傳感器節點本身能量有限，節點無線收發需要消耗大量能量，因此，設計低功耗時間同步算法是十分必要的。當前同步算法多通過降低通信包數量來解決該問題。文獻[10]對參考廣播同步算法進行改進，利用參考節點收集并廣播各子節點同步時間信息，減少節點間同步信息交換。文獻[11-12]基于成對同步(Pair-wise Synchronization,PBS)[13]單跳模型實現多跳時間同步，利用貪婪算法和分布式同步策略來計算出實現全網同步所需的最少節點，從而達到減少同步數據包的目的。

本文提出的時間同步算法通過降低同步過程中的數據通信量來降低能量消耗。不同于傳統算法，其目標不是減少同步節點個數或降低同步通信包數量，而是降低同步幀本身開銷。

3 時間同步機制

發送者-接收者同步的信息傳輸模型如圖1所示。其中，節點P為具有準確時間的父節點；節點B為待同步節點。

圖1 發送者-接收者同步信息交互模型

不同于發送者-接收者同步模型，在接收者-接收者同步模型中參考節點廣播參考信息，收到該信息后P和B分別記錄自己的本地時間，然后通過式(1)、式(2)計算出B節點時鐘參數。該模型完全去除發送端時延，其同步誤差約為發送者-接收者同步模型的一半。

4 基于變長幀的時間同步算法

傳感器節點同步數據幀包含父節點本地時間信息。該數據幀組成結構如圖2所示，其中，幀頭代表父節點ID；長度控制標志便于節點獲取數據信息；同步幀數據區存儲發送節點本地時間。該基本幀格式，廣泛應用于不同無線傳感器網絡，更完善的幀結構定義可參考IEEE 802.15.4協議。

圖2 傳感器節點同步幀格式

同步幀數據區所代表的本地時間包含大量冗余字節。為保證節點時間在短時間內不重復，節點本地時間需要用多個字節表示。考慮傳感器節點采用16 MHz外部晶振，在不分頻的情況下，為保證節點時間在15 h內不重復，節點時間需要用4個字節的系統時間和2個字節的計數器信息組成。節點在一次同步過程后需要進行再同步。一方面是因為節點需要計算時鐘頻偏以提高同步精度。洪泛時間同步協議通過短時間內發送多次時間消息來提高同步精度并利用多個同步點來計算時鐘頻偏。在文獻[14]所進行的實驗中，這一再同步時間為10 ms，通常，這類時間為百毫秒級別。另一方面是因為節點在同步過程中會不可避免的引入同步誤差。由于傳感器網絡的無線鏈路不穩定性，傳感器節點計算得出的時鐘相偏和時鐘頻偏總是會有誤差。隨著時間的積累，時鐘頻偏誤差會導致時鐘相偏逐步遞增。相比于節點可代表的最大時間，傳感器再同步周期往往比較短。在2次同步過程中，系統時間的高位字節有極大概率保持不變，如果每次同步過程都發送完整的時間信息，就會造成數據的浪費。

變長幀時間同步的幀結構設計原則是減少同步幀數據通信量，在保證時間信息的完整性、準確性的前提下盡量減少冗余時間的發送。父節點發送同步幀之前首先對時間信息進行判斷，如果高位字節時間信息沒有發生改變，則只發送低位字節時間信息。時間同步幀可以分為完整同步幀和短同步幀。變長幀時間同步旨在找出合理的短同步幀字節數，在保證同步精度的前提下，降低時間同步開銷。

傳感器節點晶振為計數器和定時器提供服務，用參數f代表傳感器節點晶振頻率。假設定時器和計數器采用的是外部晶振N倍分頻，則定時器和計數器的一個計數代表時間N/f。用Ts代表節點的系統時間，則完整同步幀中數據區所需字節數為：

由式(3)計算得出短同步幀時間信息所需要的最少比特數bmin，則短同步幀時間信息所需字節數為：

因此，變長幀時間同步能夠減少全網時間同步的數據通信量。

假設父節點為P，子節點為B。完整同步幀數據區除去低LB字節外的高位字節用HB表示。變長幀時間同步過程如下：(1)P發送完整同步幀，并存儲HB；(2)B收到完整同步幀后存儲HB，并進行同步；(3)P判斷比較當前時間的高HB個字節和存儲時間信息。如果兩者相等，則P只發送LB段，反之，P執行步驟(1)；(4)若B只收到LB段，則認為HB段沒有改變。B利用存儲信息HB與接收到的LB組合成完整同步幀，并進行同步。

接收節點B偽代碼如下：

5 收斂時間分析

對全網絡同步的收斂時間進行分析，可得到以下定理：

定理 變長幀時間同步能夠減少全網同步收斂時間。

用C代表傳感器節點的信道容量，k代表節點對信道容量的利用率，該值與傳感器網絡采用的MAC層協議相關。進一步假設傳感器節點均勻分布，ρ代表網絡中節點分布的密度，R為節點通信半徑，則節點i的吞吐量可以表示為：，用N代表節點同步幀字節數，發送一個完整的同步幀的時間為Ti=N/Si。從root節點到普通節點的最大跳數為Hopmax，那么實現全網時間同步的收斂時間可以表示為：

6 同步維護

在同步過程中，完整幀是非常重要的。一個完整同步幀的丟失會對后續所有短同步幀的精度產生影響。針對這種特殊情況，需要進行同步維護。由上文分析可知，2個完整同步幀之間的短幀個數最少為16。由于時間的累加性，短同步幀所代表的的數值會不斷遞增。如果任一完整幀丟失，在信道條件不是特別差的前提下，其后續第一個短幀的數值必然小于完整幀之前的短幀數值。此時，被同步節點判斷異常，得知完整幀丟失。被同步節點發送完整同步幀請求。接收到該請求幀后，同步節點將完整時間同步幀重新發送給被同步節點。

7 實驗與結果分析

本文在傳感器節點上實現變長幀同步算法，并對其同步精度和數據通信量進行統計。傳感器節點主控芯片采用德州儀器公司處理器MSP430F5438，芯片計數器和定時器使用頻率16 MHz的外部晶振，最大時間精度為0.0625 μs；低功耗射頻芯片采用德州儀器公司CC1100E，節點通信頻率設定為470 MHz，通信速率設定為100 KBaud；為適應節點可移動性，傳感器的供電系統為4.5 V充電鋰電池。此外，傳感器節點可提供多種外部接口：RS232串口，JTAG仿真接口，LED燈等。

實驗在3種不同配置條件下完成。變長幀同步設計目標是對現有時間同步協議的同步幀進行壓縮。為驗證變長幀同步的數據通信量，實驗將變長幀時間同步與現有同步模型融合后進行測試。

(1)基于變長幀同步的發送者-接收者同步模型單跳實驗

實驗采用3個傳感器節點，分別為發送節點P、接收節點B和參考節點S。根據上文所述，為保證節點時間短時間內不發生重復，需要用6個字節代表系統時間。傳感器節點再同步時間設定為為7 s，由式(4)可知，短同步幀中代表系統時間的字節數為4。發送節點P向接收節點B發送同步信息，節點B收到該同步信息后對本地時間進行調整，參考節點S偵聽該同步過程并記錄同步幀長，偵聽到一次完整的同步過程后S發送查詢幀。節點P和節點B收到查詢幀后立即記錄各自本地時間，并依次向參考節點匯報該時間。參考節點通過RS232串口線將同步幀數量、同步幀長及接收到的時間信息傳送給PC。

實驗采集100個同步數據點，節點的同步誤差如圖3所示。其中，節點誤差的最大絕對值為0.9362μs，同步精度與發送者-接收者同步模型符合。100個同步數據點產生3個完整同步幀、97個短同步幀。由圖2可知完整同步幀長為9個字節，短同步幀包含7個字節。變長幀時間同步效率η≈ 0.2156。

圖3 基于變長幀的發送者-接收者同步單跳實驗結果

(2)基于變長幀同步的發送者-接收者同步模型4跳實驗

實驗采用6個節點實現，節點同步時間傳遞方向為P1->P2->P3->P4->P5，每個節點只能與其鄰居節點進行通信。P1為root節點具有準確的時間信息，P1采用變長幀時間同步結合發送者-接收者同步模型來同步節點P2，P2以相同方式同步節點P3，該過程持續直到P5被同步。實驗利用超級節點S來偵聽、統計所有節點的同步信息，S在偵聽到一個完整的同步過程后廣播查詢幀，偵聽到查詢幀后節點P1、P2、P3、P4、P5記錄本地時間并依次發送給節點S。S將同步幀數量、短同步幀數量、節點時間信息通過串口線傳遞給PC。

實驗采集200個同步數據點，從圖4可以看出變長幀同步能夠與發送者-接收者同步很好地結合。變長幀發送者-接收者同步精度與普通發送者-接收者同步模型相同，都表現出了節點精度隨同步跳數增加的特性。PC采集到的完整同步幀個數為796，短同步幀個數為772，變長幀節省的同步數據量比例為η ≈ 0.2155。可以看出變長幀時間同步在保證發送者-接收者同步多跳同步精度的前提下，降低了同步數據通信開銷。

圖4 基于變長幀的發送者-接收者同步4跳實驗結果

(3)基于變長幀同步的接收者-接收者同步模型8跳實驗

實驗采用10個節點實現，同步信息傳遞方向為P1->P2->P3->P4->P5->P6->P7->P8->P9。每一對節點的同步都需要超級節點S的輔助，S廣播參考信息，偵聽到該信息后節點P1、P2各自記錄本地時間，節點P1將本地時間記錄發送給節點P2，P2利用2個時間記錄實現與節點P1的同步，S再次發送參考信息，P2與P3以相同方式實現同步，該過程持續直到節點P9被同步。之后S廣播查詢幀，偵聽到該信息后節點P1、P3、P5、P7、P9記錄本地時間并發送給節點S。在整個同步過程中，節點S偵聽同步信息并統計幀大小，S將該信息和節點時間信息發送給PC。

基于變長幀的接收者-接收者同步8跳同步符合接收者-接收者同步模型同步特性。圖5顯示，雖然接收者-接收者同步的最大同步精度低于發送者-接收者同步模型，但是前者具有比后者更高的同步精度，接收者-接收者同步模型在置信度為0.9時同步精度為1.0417 μs，優于置信度為0.9時發送者-接收者同步模型的同步精度1.3815 μs，考慮到接收者-接收者同步模型同步跳數為8，可知該模型同步精度大于發送者-接收者同步模型。PC采集到同步幀個數為1600，短幀個數為1552，參考信息幀個數為1600。每次同步過程中都需要參考信息，參考信息不包含圖2中數據區部分，其幀長為3 Byte。在考慮參考信息的前提下，基于變長幀的接收者-接收者同步模型同步效率 η≈ 0.1617；如果只考慮包含時間信息的同步幀，則其同步效率為η≈ 0.2156。

圖5 基于變長幀的接收者-接收者同步8跳實驗結果

從以上3個實驗可以看出，變長幀時間同步能夠應用于當前所有同步協議，因為其本質為針對時間同步的特性來壓縮通信數據量。

8 結束語

本文提出適用于無線傳感器網絡的變長幀時間同步算法。分析研究表明，無線通信是傳感網能量開銷的主要部分，傳感網全網同步的收斂時間與同步負載大小成正比。變長幀時間同步協議采用存儲、壓縮技術，將無線通信負載壓縮并轉化為節點存儲問題，可有效減少平均同步幀長，為設計能量高效和快速收斂的傳感網提供幫助。發送者-接收者同步單跳、發送者-接收者同步4跳和接收者-接收者同步8跳實驗結果表明，該算法可有效減少同步幀平均負載，并很好的與現有協議融合，對協議精度和特性沒有影響。但本文提出的數據幀都是應用在自定義的傳感器網絡中，更進一步的研究需要結合Zigbee 802.15.4來開展。此外，當前變長幀時間同步也需要結合現有同步模型實現。因此，下一步工作是提出更符合變長幀同步算法的時間模型，在降低同步數據量的基礎上進一步提升同步精度。

[1]Maróti M,Kusy B,Simon G,et al.The Flooding Time Synchronization Protocol[C]//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.Baltimore,USA:ACM Press,2004:39-49.

[2]Ping S.Delay Measurement Time Synchronization for Wireless Sensor Networks[R].Berkeley,USA:Intel Research Berkeley Lab,Technical Report:IRB-TR-03-013,2003.

[3]孫德云,沈 杰,劉海濤.基于擴散機制的無線傳感器網絡時間同步協議[J].通信學報,2008,29(11):40-49.

[4]van Greunen J,Rabaey J.Lightweight Time Synchronization for Sensor Networks[C]//Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications.San Diego,USA:ACM Press,2003:11-19.

[5]Ganeriwal S,Kumar R,Srivastava M B.Timing-sync Protocol for Sensor Networks[C]//Proceedings of the 1st ACM Conference on Embedded Networked Sensor System.Los Angeles,USA:ACM Press,2003:138-149.

[6]Sichitiu M L,Veerarittiphan C.Simple,Accurate Time Synchronization for Wireless Sensor Networks[C]//Proceedings of Wireless Communications and Networking.Louisiana,USA:IEEE Press,2003:1266-1273.

[7]皇甫偉,周新運,陳燦峰.基于多層抽樣反饋的傳感器網絡時間同步算法[J].通信學報,2009,30(3):59-65.

[8]Elson J E,Girod L,Estrin D.Fine-grained Network Time Synchronization Using Reference Broadcasts[C]//Proceedings of the 5th Symposium on Operating Systems Design and Implementation.Boston,USA:USENIX,2002:147-163.

[9]王義君,錢志鴻,王桂琴,等.無線傳感器網絡能量有效時間同步算法研究[J].電子與信息學報,2012,34(9):2174-2179.

[10]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.Berkeley,USA:ACM Press,2004.

[11]Cheng King-Yip,Lui King-Shan,Wu Yik-Chung,et al.A Distributed Multihop Time Synchronization Protocol for Wireless Sensor Networks Using Pairwise Broadcast Synchronization[J].IEEE Transactions on Wireless Communications,2009,8(4):1764-1772.

[12]Noh K L,Wu Y C,Qaraqe K,et al.Extension of Pairwise Broadcasting Clock Synchronization for Multi-cluster Sensor Networks[J].Eurasip Journal on Advances in Signal Processing:Special Issue on Distributed Signal Processing Techniques for Wireless Sensor Networks,2008,1-10.

[13]Noh K L,Serpedin E,Qaraqe K A.A New Approach for Time Synchronization in Wireless Sensor Networks:Pairwise Broadcast Synchronization[J].IEEE Transactions on Wireless Communications,2008,7(9):3318-3322.

[14]Huang Paihan,Desai M,Qiu Xiaofan,et al.On the Multihop Performance of Synchronization Mechanisms in High Propagation Delay Networks[J].IEEE Transactions on Computers,2009,58(5):577-590.