基于變長幀的無線傳感器網(wǎng)絡(luò)時間同步算法

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

(中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所物聯(lián)網(wǎng)系統(tǒng)技術(shù)實驗室，上海 201899)

1 概述

無線傳感器網(wǎng)絡(luò)作為構(gòu)建通信環(huán)境的基礎(chǔ)架構(gòu)，由大量隨機布設(shè)的傳感器節(jié)點組成，這類網(wǎng)絡(luò)具有資源受限、低功耗、多跳、自組織、應(yīng)用種類多等特點。時間同步是傳感器網(wǎng)絡(luò)的重要支撐技術(shù)，它服務(wù)于傳感網(wǎng)的多種應(yīng)用，如定位技術(shù)、睡眠機制、MAC層協(xié)議、調(diào)度機制等。因此，對無線傳感器網(wǎng)絡(luò)時間同步技術(shù)進行研究是十分必要的。

時間同步協(xié)議的一個研究重點是在保證同步精度的前提下，降低同步過程的通信開銷?，F(xiàn)有多數(shù)算法均強調(diào)單跳同步精度，未考慮同步開銷問題。而傳感器節(jié)點本身能量有限，節(jié)點無線收發(fā)會消耗大量能量。針對該問題，本文提出一種基于變長幀的傳感器網(wǎng)絡(luò)時間同步算法，同時對傳感器時間同步的收斂時間進行分析。

2 基本模型及典型算法

無線傳感器網(wǎng)絡(luò)時間同步算法包含以下3種基本模型：發(fā)送者-接收者模型，成對同步模型和接收者-接收者同步模型。

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

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

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

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

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

3 時間同步機制

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

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

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

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

傳感器節(jié)點同步數(shù)據(jù)幀包含父節(jié)點本地時間信息。該數(shù)據(jù)幀組成結(jié)構(gòu)如圖2所示，其中，幀頭代表父節(jié)點ID；長度控制標志便于節(jié)點獲取數(shù)據(jù)信息；同步幀數(shù)據(jù)區(qū)存儲發(fā)送節(jié)點本地時間。該基本幀格式，廣泛應(yīng)用于不同無線傳感器網(wǎng)絡(luò)，更完善的幀結(jié)構(gòu)定義可參考IEEE 802.15.4協(xié)議。

圖2 傳感器節(jié)點同步幀格式

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

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

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

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

因此，變長幀時間同步能夠減少全網(wǎng)時間同步的數(shù)據(jù)通信量。

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

接收節(jié)點B偽代碼如下：

5 收斂時間分析

對全網(wǎng)絡(luò)同步的收斂時間進行分析，可得到以下定理：

定理 變長幀時間同步能夠減少全網(wǎng)同步收斂時間。

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

6 同步維護

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

7 實驗與結(jié)果分析

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

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

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

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

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

圖3 基于變長幀的發(fā)送者-接收者同步單跳實驗結(jié)果

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

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

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

圖4 基于變長幀的發(fā)送者-接收者同步4跳實驗結(jié)果

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

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

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

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

從以上3個實驗可以看出，變長幀時間同步能夠應(yīng)用于當(dāng)前所有同步協(xié)議，因為其本質(zhì)為針對時間同步的特性來壓縮通信數(shù)據(jù)量。

8 結(jié)束語

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

[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]孫德云,沈 杰,劉海濤.基于擴散機制的無線傳感器網(wǎng)絡(luò)時間同步協(xié)議[J].通信學(xué)報,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]皇甫偉,周新運,陳燦峰.基于多層抽樣反饋的傳感器網(wǎng)絡(luò)時間同步算法[J].通信學(xué)報,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]王義君,錢志鴻,王桂琴,等.無線傳感器網(wǎng)絡(luò)能量有效時間同步算法研究[J].電子與信息學(xué)報,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.