基于接收者的無線傳感器網(wǎng)絡(luò)時(shí)間同步算法研究

谷呈星，趙訓(xùn)威，*，張春玲

（1.上海電力大學(xué)，上海 201306；2.國網(wǎng)信息通信產(chǎn)業(yè)集團(tuán)有限公司，北京 100032）

0 引言

隨著無線通信、微機(jī)電系統(tǒng)和信號處理技術(shù)的迅速發(fā)展，低成本的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN）［1］設(shè)備在軍事、農(nóng)業(yè)、醫(yī)療、航空航天、智能家居和環(huán)境監(jiān)測等領(lǐng)域有著廣泛應(yīng)用。時(shí)間同步技術(shù)作為無線傳感器網(wǎng)絡(luò)的底層支撐技術(shù)之一，是數(shù)據(jù)的可靠傳輸、節(jié)能監(jiān)測定位、目標(biāo)追蹤、休眠調(diào)度等功能實(shí)現(xiàn)的基礎(chǔ)，故研究WSN的時(shí)間同步具有重要意義［2］。

現(xiàn)有的多數(shù)同步算法是在MAC層時(shí)間戳可用的條件下才能實(shí)現(xiàn)高的同步精度。基于發(fā)送者-接收者的單向同步、基于發(fā)送者-接收者的雙向同步和基于接收者-接收者的同步是同步算法的3種同步方式。泛洪時(shí)間同步協(xié)議(Flooding Time Synchronization Protocol，F(xiàn)TSP）［3］、多跳平均共識時(shí)間同步［4］(Multihop Average Consensus time Synchronization，MACTS）等屬于發(fā)送者-接收者單向同步方式的算法。傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議(Timing sync-Protocol for Sensor Networks，TPSN）［5］、Mini-Sync協(xié)議和Tiny-Sync協(xié)議［6］等屬于發(fā)送者-接收者雙向同步方式的算法。上述發(fā)送者-接收者方式的算法用MAC層時(shí)間戳消除了發(fā)送時(shí)延和訪問時(shí)延，但忽視了不是所有無線芯片都支持MAC層時(shí)間戳這個(gè)問題。產(chǎn)生MAC層時(shí)間戳需要無線射頻模塊的支持，無線射頻模塊接收完一個(gè)數(shù)據(jù)包后會向微處理器(Micro Controller Unit，MCU）發(fā)送請求信號，MCU在收到請求信號時(shí)，會產(chǎn)生中斷并在傳輸中的數(shù)據(jù)包上打MAC層時(shí)間戳。但是現(xiàn)在很多Zigbee，WiFi和藍(lán)牙等無線射頻模塊在MCU收到請求信號時(shí)，需要立即安排下一個(gè)數(shù)據(jù)包，也就無法在傳輸中的數(shù)據(jù)包上打時(shí)間戳。當(dāng)MAC層時(shí)間戳不可用時(shí)，受訪問時(shí)延的影響，發(fā)送方-接收方算法的同步精度會大幅降低。參考廣播同步(Reference Broadcast Synchronization，RBS）［7］、參 考 廣 播 基 礎(chǔ) 同 步［8］(Reference Broadcast Infrastructure Synchronization，RBIS）等屬于接收者-接收者的同步方式。此方式的算法利用參考節(jié)點(diǎn)廣播的方式消除了發(fā)送方的時(shí)延，在無MAC層時(shí)間戳?xí)r也可以實(shí)現(xiàn)較高的同步精度，但是存在同步開銷大的缺點(diǎn)。

本文在RBS算法的基礎(chǔ)上，提出了一種基于接收者-接收者方式的時(shí)間同步算法(LPSN算法），利用廣播關(guān)鍵參數(shù)的方法減少了同步開銷，降低了能耗。在實(shí)驗(yàn)中本文算法沒有與對硬件和軟件有較高要求的同步算法作比較，比如PulseSync算法［9］，而是與適用性強(qiáng)，可以在任何硬件上實(shí)現(xiàn)的經(jīng)典算法相比較。實(shí)驗(yàn)結(jié)果證明算法無須MAC層時(shí)間戳也能實(shí)現(xiàn)較高同步精度。

1 模型及符號表示

在WSN中，節(jié)點(diǎn)的晶振頻率易受到溫度、濕度、電磁輻射等因素的影響，這將導(dǎo)致不同節(jié)點(diǎn)間的本地時(shí)鐘出現(xiàn)偏差。隨著時(shí)間的推移時(shí)鐘偏差會逐漸變大，最終影響WSN中節(jié)點(diǎn)的正常工作。時(shí)間的相對時(shí)鐘偏移和相對漂移是節(jié)點(diǎn)時(shí)鐘同步的重要參數(shù)，相對時(shí)鐘偏移和相對漂移分別指兩個(gè)時(shí)鐘之間的時(shí)間差和兩個(gè)時(shí)鐘頻率之間的差。

假設(shè)監(jiān)測區(qū)域內(nèi)有N個(gè)節(jié)點(diǎn)，任意一個(gè)節(jié)點(diǎn)i將本地時(shí)鐘建模為：

其中，t i是本地時(shí)鐘讀數(shù)，a i和b i是節(jié)點(diǎn)時(shí)鐘相對于標(biāo)準(zhǔn)時(shí)間t UTC的絕對時(shí)鐘漂移和偏移。

依據(jù)晶振頻率的特性，可以認(rèn)為a i和b i在一段時(shí)間內(nèi)為常數(shù)。因此，兩個(gè)傳感器節(jié)點(diǎn)的本地時(shí)鐘是線性相關(guān)的。任意兩個(gè)節(jié)點(diǎn)i和j的時(shí)間關(guān)系可以建模為：

其中，a i j和b i j是節(jié)點(diǎn)i的本地時(shí)鐘t i相對于節(jié)點(diǎn)j的本地時(shí)鐘t j的相對漂移和偏移。

將任意兩個(gè)節(jié)點(diǎn)i，j的本地時(shí)間與t UTC代入公式(1）可得到兩個(gè)等式。利用t UTC相同這一條件，進(jìn)行等式變形便可得出t i(t）與t i(t）之間的關(guān)系，a i j和b i j便可計(jì)算出來。

2 LPSN算法

2.1 算法實(shí)現(xiàn)

采用簇型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，按照地理位置選出合適節(jié)點(diǎn)作為參考節(jié)點(diǎn)。算法定義同步周期T=N T R，其中，N是參考節(jié)點(diǎn)廣播數(shù)據(jù)包的次數(shù)，T R是參考節(jié)點(diǎn)廣播的兩個(gè)連續(xù)數(shù)據(jù)包之間的時(shí)間間隔，同步周期T是廣播N次數(shù)據(jù)包所需要的時(shí)間。典型的單跳同步示例如圖1所示，設(shè)節(jié)點(diǎn)O為時(shí)間基準(zhǔn)點(diǎn)，節(jié)點(diǎn)R為參考節(jié)點(diǎn)，節(jié)點(diǎn)A為普通節(jié)點(diǎn)，A是希望與O同步的節(jié)點(diǎn)。

圖1 單跳同步示例

同步算法的過程可分為3個(gè)階段，過程如下：

2.1.1 參考節(jié)點(diǎn)廣播階段

在同步周期內(nèi)，R定時(shí)廣播信標(biāo)數(shù)據(jù)包，每個(gè)信標(biāo)包中含有節(jié)點(diǎn)的標(biāo)識ID、包的序號、周期號和一個(gè)時(shí)間戳，該時(shí)間戳記錄了應(yīng)用層生成包時(shí)R的本地時(shí)間。O和A在收到信標(biāo)包時(shí)將各自的本地時(shí)間作為接收時(shí)間，并將接收時(shí)間和信標(biāo)包中的時(shí)間成對地存儲在大小為N的循環(huán)緩沖區(qū)中。在無丟包的情況下，會形成N對時(shí)間標(biāo)(信標(biāo)包中的時(shí)間，接收時(shí)間）。當(dāng)循環(huán)緩沖區(qū)中有N對時(shí)間標(biāo)時(shí)就建立線性回歸方程，采用最小二乘法求解，見公式(3）和(4），便可計(jì)算出相對時(shí)鐘漂移和偏移。

2.1.2 參數(shù)傳遞階段

在同步周期結(jié)束時(shí)(周期號的增加代表了上一個(gè)周期的結(jié)束），O將構(gòu)建并廣播一次同步信息包，信息包中含有時(shí)間基準(zhǔn)點(diǎn)ID，參考節(jié)點(diǎn)參考節(jié)點(diǎn)收到信息包后會轉(zhuǎn)發(fā)此信息包。

2.1.3 普通節(jié)點(diǎn)與時(shí)間基準(zhǔn)點(diǎn)同步階段

2.2 誤差分析

發(fā)送方節(jié)點(diǎn)的應(yīng)用層時(shí)間戳到達(dá)接收方節(jié)點(diǎn)的過程中，會遇到多個(gè)時(shí)延，這些時(shí)延會降低同步精度。無線鏈路的時(shí)延組成如圖2所示。在WSN中無線消息傳播鏈路上的時(shí)延可以分為：發(fā)送時(shí)延、訪問時(shí)延、傳輸時(shí)延、傳播時(shí)延、接收時(shí)延和接收處理時(shí)延［10］。

圖2 無線鏈路的時(shí)延組成

其中訪問時(shí)延是影響同步精度的主要原因，采用MAC層時(shí)間戳的同步算法可以消除發(fā)送、訪問和接收處理時(shí)延。在MAC層時(shí)間戳不可用的條件下，需要MAC層時(shí)間戳的算法的同步精度會大幅降低。本文算法借鑒了RBS算法的思想，消除了發(fā)送方的時(shí)延，而傳播時(shí)延與節(jié)點(diǎn)間的距離有關(guān)，300 m內(nèi)的傳播時(shí)間小于1 us。與訪問時(shí)延相比，接收時(shí)延和接收處理時(shí)延對同步精度的影響較小。因此，在理論上本文算法可以實(shí)現(xiàn)較好的同步精度。

3 性能比較

3.1 同步開銷比較

在WSN的應(yīng)用中，傳感器節(jié)點(diǎn)的功耗是由通信主導(dǎo)而不是由計(jì)算主導(dǎo)［11］，節(jié)點(diǎn)的能量主要在發(fā)射、接收數(shù)據(jù)包的過程中消耗。Bae［12］中的能耗分析模型指出在確定了區(qū)域范圍和區(qū)域內(nèi)節(jié)點(diǎn)的數(shù)量后，可以用發(fā)送和接收報(bào)文的次數(shù)來衡量能耗的大小。

在靜態(tài)WSN中，因?yàn)榇_定層次結(jié)構(gòu)或者從屬關(guān)系的數(shù)據(jù)包只需要用一次，所以沒有考慮它們的開銷。為了便于比較，有頻率漂移和偏移估計(jì)的算法都用8對時(shí)間標(biāo)進(jìn)行估計(jì)，無頻率漂移和偏移估計(jì)的算法需交換8次信息。根據(jù)幾種算法各自的原理計(jì)算同步開銷，表1示出了幾種算法在一跳內(nèi)同步的開銷，n為需要同步的節(jié)點(diǎn)個(gè)數(shù)。

表1 不同算法開銷比較

從表1中可以看出，與同為接收者-接收者方式的RBS算法相比，本文算法大幅減少了開銷，具有很大優(yōu)勢。與發(fā)送者-接收者方式的TPSN算法和FTSP算法相比，本文算法優(yōu)于TPSN算法，劣于FTSP算法。

3.2 同步精度比較

通過實(shí)驗(yàn)比較了各個(gè)算法在沒有MAC層時(shí)間戳的情況下的同步精度。在實(shí)驗(yàn)環(huán)境中，采用外接32 kHz晶體振蕩器的CC1310物聯(lián)網(wǎng)射頻芯片來實(shí)現(xiàn)不同的算法。用公差為5～30 ppm的晶振作為內(nèi)部數(shù)字控制振蕩器的時(shí)鐘源。

本文算法用3個(gè)CC1310模塊按照圖1的拓?fù)浣Y(jié)構(gòu)進(jìn)行同步實(shí)驗(yàn)。參考節(jié)點(diǎn)每秒鐘廣播一次數(shù)據(jù)包。在普通節(jié)點(diǎn)與時(shí)間基準(zhǔn)點(diǎn)同步后，將普通節(jié)點(diǎn)估計(jì)出的時(shí)間與時(shí)間基準(zhǔn)點(diǎn)的實(shí)際時(shí)間的差作為同步誤差，時(shí)間基準(zhǔn)點(diǎn)的實(shí)際時(shí)間可以用指令在CC1310上查看。其余同步算法也通過CC1310實(shí)現(xiàn)，為了模擬傳感器節(jié)點(diǎn)的在線處理過程，在收到信標(biāo)后，接收節(jié)點(diǎn)會通過USB線將信標(biāo)包傳輸?shù)交??；臼占⒏檸r(shí)間戳的數(shù)據(jù)包。在實(shí)現(xiàn)TPSN和FTSP同步算法時(shí)，普通節(jié)點(diǎn)在接收到信標(biāo)包后立即將確認(rèn)消息發(fā)送回時(shí)間基準(zhǔn)點(diǎn)。每種算法統(tǒng)計(jì)了3個(gè)小時(shí)的實(shí)驗(yàn)數(shù)據(jù)并求出平均同步誤差。實(shí)驗(yàn)結(jié)果如圖3所示，顯示了廣播信標(biāo)包次數(shù)與平均同步誤差的關(guān)系。

圖3 無MAC層時(shí)間戳

實(shí)驗(yàn)結(jié)果表明隨著廣播包次數(shù)的增加，幾種算法的時(shí)間同步精度略有提高，在無MAC層時(shí)間戳的情況下，消除了發(fā)送方時(shí)延的RBS和本文算法的精度遠(yuǎn)大于未能消除訪問時(shí)延的FTSP與TPSN算法。N=10時(shí)，本文算法的同步精度約為7 us。實(shí)驗(yàn)結(jié)果證明在無MAC層時(shí)間戳的情況下，本文算法可以實(shí)現(xiàn)微秒級的同步精度。

4 結(jié)語

現(xiàn)有的多數(shù)同步算法要在MAC層時(shí)間戳可用這一條件下才能實(shí)現(xiàn)較高的同步精度，但是很多現(xiàn)代的無線射頻芯片不支持MAC層時(shí)間戳，這限制了設(shè)備選擇芯片類型的范圍。本文針對傳感器節(jié)點(diǎn)的射頻芯片不支持MAC層時(shí)間戳的情況，提出了基于接收者的時(shí)間同步算法。接收節(jié)點(diǎn)會在同步周期內(nèi)存儲時(shí)間戳并利用最小二乘法計(jì)算出相對時(shí)鐘漂移和偏移，時(shí)間基準(zhǔn)點(diǎn)在同步周期結(jié)束時(shí)會通過廣播參數(shù)的方法減少同步報(bào)文交換的次數(shù)，進(jìn)而降低能量消耗。在同步精度方面，通過與幾種經(jīng)典算法的對比可知，本文算法在芯片不支持MAC層時(shí)間戳的情況下也能實(shí)現(xiàn)較好的同步精度。在未來工作中，將完善算法在大規(guī)模高密集場景中的功能，提升算法的泛化能力。