基于接收者的無線傳感器網絡時間同步算法研究

谷呈星，趙訓威，*，張春玲

（1.上海電力大學，上海 201306；2.國網信息通信產業集團有限公司，北京 100032）

0 引言

隨著無線通信、微機電系統和信號處理技術的迅速發展，低成本的無線傳感器網絡(Wireless Sensor Network，WSN）［1］設備在軍事、農業、醫療、航空航天、智能家居和環境監測等領域有著廣泛應用。時間同步技術作為無線傳感器網絡的底層支撐技術之一，是數據的可靠傳輸、節能監測定位、目標追蹤、休眠調度等功能實現的基礎，故研究WSN的時間同步具有重要意義［2］。

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

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

1 模型及符號表示

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

假設監測區域內有N個節點，任意一個節點i將本地時鐘建模為：

其中，t i是本地時鐘讀數，a i和b i是節點時鐘相對于標準時間t UTC的絕對時鐘漂移和偏移。

依據晶振頻率的特性，可以認為a i和b i在一段時間內為常數。因此，兩個傳感器節點的本地時鐘是線性相關的。任意兩個節點i和j的時間關系可以建模為：

其中，a i j和b i j是節點i的本地時鐘t i相對于節點j的本地時鐘t j的相對漂移和偏移。

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

2 LPSN算法

2.1 算法實現

采用簇型網絡拓撲結構，按照地理位置選出合適節點作為參考節點。算法定義同步周期T=N T R，其中，N是參考節點廣播數據包的次數，T R是參考節點廣播的兩個連續數據包之間的時間間隔，同步周期T是廣播N次數據包所需要的時間。典型的單跳同步示例如圖1所示，設節點O為時間基準點，節點R為參考節點，節點A為普通節點，A是希望與O同步的節點。

圖1 單跳同步示例

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

2.1.1 參考節點廣播階段

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

2.1.2 參數傳遞階段

在同步周期結束時(周期號的增加代表了上一個周期的結束），O將構建并廣播一次同步信息包，信息包中含有時間基準點ID，參考節點參考節點收到信息包后會轉發此信息包。

2.1.3 普通節點與時間基準點同步階段

2.2 誤差分析

發送方節點的應用層時間戳到達接收方節點的過程中，會遇到多個時延，這些時延會降低同步精度。無線鏈路的時延組成如圖2所示。在WSN中無線消息傳播鏈路上的時延可以分為：發送時延、訪問時延、傳輸時延、傳播時延、接收時延和接收處理時延［10］。

圖2 無線鏈路的時延組成

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

3 性能比較

3.1 同步開銷比較

在WSN的應用中，傳感器節點的功耗是由通信主導而不是由計算主導［11］，節點的能量主要在發射、接收數據包的過程中消耗。Bae［12］中的能耗分析模型指出在確定了區域范圍和區域內節點的數量后，可以用發送和接收報文的次數來衡量能耗的大小。

在靜態WSN中，因為確定層次結構或者從屬關系的數據包只需要用一次，所以沒有考慮它們的開銷。為了便于比較，有頻率漂移和偏移估計的算法都用8對時間標進行估計，無頻率漂移和偏移估計的算法需交換8次信息。根據幾種算法各自的原理計算同步開銷，表1示出了幾種算法在一跳內同步的開銷，n為需要同步的節點個數。

表1 不同算法開銷比較

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

3.2 同步精度比較

通過實驗比較了各個算法在沒有MAC層時間戳的情況下的同步精度。在實驗環境中，采用外接32 kHz晶體振蕩器的CC1310物聯網射頻芯片來實現不同的算法。用公差為5～30 ppm的晶振作為內部數字控制振蕩器的時鐘源。

本文算法用3個CC1310模塊按照圖1的拓撲結構進行同步實驗。參考節點每秒鐘廣播一次數據包。在普通節點與時間基準點同步后，將普通節點估計出的時間與時間基準點的實際時間的差作為同步誤差，時間基準點的實際時間可以用指令在CC1310上查看。其余同步算法也通過CC1310實現，為了模擬傳感器節點的在線處理過程，在收到信標后，接收節點會通過USB線將信標包傳輸到基站。基站收集并跟蹤帶時間戳的數據包。在實現TPSN和FTSP同步算法時，普通節點在接收到信標包后立即將確認消息發送回時間基準點。每種算法統計了3個小時的實驗數據并求出平均同步誤差。實驗結果如圖3所示，顯示了廣播信標包次數與平均同步誤差的關系。

圖3 無MAC層時間戳

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

4 結語

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