基于分簇的多跳無線傳感網絡時間同步算法

摘 ? 要：針對典型的時間同步算法應用到多跳拓撲網絡時存在時間同步精確度差、收斂速度慢、功耗較大等問題，文章提出一種基于分簇的多跳無線傳感網絡時間同步算法。該算法結合了TPSN算法和RBS算法的同步思想，摒棄了TPSN算法同步周期長的缺點而保留了其同步精確度高的優點，也解決了RBS同步開銷大和難于應用到多跳網絡的問題。該算法具有相當高的同步精度，并有效降低了同步功耗，具有一定的實用性。

關鍵詞：無線傳感網絡;時間同步;分簇;多跳;同步能耗

1 ? ?時間同步技術簡介

時間同步技術是無線傳感器網絡（Wireless Sensor Network，WSN）中一項極為重要的技術，也是諸如節點定位、數據融合和休眠調度等許多關鍵技術的基礎。無線傳感器網絡相對于傳統有線網絡在規模上和組織方式上有明顯不同，因此，一些傳統網絡的時間同步協議無法適應無線傳感網絡的環境條件，必須設計適用于WSN的時間同步算法[1]。自WSN時間同步概念提出以來，國內外學者和科研機構也研究了多種類型的時間同步算法。目前存在的時間同步算法主要可分為3種類型：（1）基于僅接收端（Receive-Only Synchronization，ROS）的時間同步算法，屬于此類型的算法主要有DMTS[2]和FTSP[3]算法。（2）基于發送端-接收端（Sender-Receiver Synchronization，SRS）的時間同步算法，其中，典型的算法是TPSN算法[4]。（3）基于接收端-接收端（Receiver-Receiver Synchronization，RRS）同步算法，典型的算法是RBS算法[5]。

以上算法基本上都是基于單跳網絡提出的，但在現實環境中大部分網絡都是多跳網絡，所以有必要具體研究如何將適用于單跳網絡的時間同步算法應用到多跳的網絡環境中。本文在經典同步算法的基礎上提出一種基于分簇的多跳無線傳感器網絡時間同步（Cluster-Based Time Synchronization algorithm for multi-hop wireless sensor networks，CBTS）算法，該算法不僅確保了同步精度，而且有效保證了能量消耗。

2 ? ?算法分析

2.1 ?層次構造階段

層次構造過程在網絡初始化時執行，首先，為網絡中每個節點賦予一個唯一的ID號;其次，選取根節點指定其為第0層并廣播層次建立消息包level_constuct，接收到廣播消息的節點將自己本地的level值置為分層消息中包含的level值加1，同時，將該發送節點作為自身父節點，并向其發送level_response分組，該分組包含自己的ID號。已重置過level值的節點對其后收到的分層消息都不做處理。父節點收到level_response分組后保存分組中包含的ID，并將這些節點作為自己的子節點，通過變量（Child_count）統計子節點個數。重復以上過程直至所有節點都加入網絡，至此整個網絡建立完成。

2.2 ?時間同步階段

2.2.1 ?反饋節點的同步

假設P節點為簇首節點，A，B，C為簇內節點，B節點設為反饋節點。節點P在時間T1，i（P）時刻廣播包含時間戳T1，i（P）的報文，簇內節點A，B，C都接收到該報文并標記接收時刻T2，i（A），T2，i（B），T2，i（C），反饋節點B在T3，i（B）時刻發送反饋報文，節點P在T4，i（P）時刻接收到該報文。故可以得到如下公式：

其中，d（BP）和Xi（BP）分別表示信息從節點B傳輸到節點P的固定時延部分和隨機時延部分。定義上行鏈路延遲為，下行鏈路延遲為。由Shrestha等[6]的研究可知，利用最大似然估計可求得，其中，代表上行鏈路的測量延遲平均值，即，代表下行鏈路的測量延遲平均值，即。假使節點的頻偏在一定范圍內保持不變，一次繼續廣播一個包含φ（BP），d（BP）和T1，i（P）的三元分組數據包，簇內接收到數據包后便可求得與P節點的相位偏差，再用線性估計方法調整頻率偏差，并且在簇首節點設置一個同步精度，因此可以校正節點B，假設節點B同步后的時間為T（B）。CBTS單跳同步算法原理如圖1所示。

2.2.2 普通節點同步

節點P廣播同步消息后，A，B，C接收到數據包，因為在此過程中消除了接入延遲和發送延遲，這也是延遲中最不確定和影響最大的延遲，所以假設節點A，B，C同時受到節點P廣播的數據包，然后分別記錄下各自接收到數據包時刻的時間戳。記為T（A），T（B），T（C），因為B已完成了同步，所以A，C都根據B來調整自己的時間差，即，。于是就保證了該單跳區域內節點與節點P同步，這是單跳的情況，多跳也依此方式進行同步。由于每個節點都有子節點計數器，當子節點為0時，則無需廣播數據包，有效節省了能量。

3 ? ?算法同步誤差分析

本算法結合了SRS和ROS同步方式進行同步，在同步時報文的傳輸延遲主要分為：發送延遲、訪問延遲、傳輸延遲、傳播延遲、接收延遲和接收處理延遲。CBTS算法在同步的第一階段使用雙向信息交換的方式，在這個過程中，算法的同步誤差主要體現在不確定延遲的估計上，即Xi（BP）和Xi（PB）的值，節點B的同步誤差表達式為：

（3）

其中，Xi（BP）和Xi（PB）分別表示節點B到節點P和節點P到節點B的不確定延遲，表示節點B和節點P同步一輪的時鐘漂移。

在同步的第二階段，父節點廣播一個數據包，子節點接收該數據包并記錄其時間戳，這個過程中消除了發送端的發送延遲和訪問延遲兩大不確定延遲，因此能夠極大地提高同步精度，同步時誤差主要體現在節點的時鐘頻偏和同步過程中產生的時鐘漂移。節點A，C的同步誤差可表示為：

（4）

其中，表示其他節點分別與B節點在接收P廣播時的接收誤差。

4 ?結語

本文提出了一種基于分簇的WSN時間同步算法，該算法建立在分簇網絡的基礎上，利用簇內節點同步方式進行優化，結合了SRS和ROS同步方法，有效保證了同步精度的同時，也降低了同步消息包的收發數量，從而大大降低了網絡能耗。

[參考文獻]

[1]張超.無線傳感器網絡時間同步技術進展[J].重慶工商大學學報（自然科學版），2019（6）：88-94.

[2]PING S.Delay measurement time synchronization for wireless sensor networks[J].Intel Research Berkeley Lab，2003（6）：1-12.

[3]MAROTI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol[C].Hangzhou：International Conference on Embedded Networked Sensor Systems，2004.

[4]GANERIWAL S，KUMAR R，SRIVASTAVA M，et al.Timing-sync protocol for sensor networks[C].Beijing：International Conference on Embedded Networked Sensor Systems，200.

[5]ELSON J，GIROD L，ESTRIN D，et al.Fine-grained network time synchronization using reference broadcasts[C].Shanghai：Operating Systems Design and Implementation，2002.

[6]SHRESTHA D，PANG Z，DZUNG D.Precise clock synchronization in high performance wireless communication for time sensitive networking[J].IEEE Access，2018（9）：1.

Abstract：In this paper， a clustering-based time synchronization algorithm for multi-hop wireless sensor networks is proposed to solve the problems of poor time synchronization accuracy， slow convergence and high power consumption. The algorithm combines the idea of TPSN algorithm and RBS algorithm， but discards the disadvantage of long synchronization period of TPSN algorithm， and retains the advantage of high synchronization accuracy. It also solves the problem of RBS synchronization overhead and difficult to apply to multi-hop network. The algorithm has quite high synchronization accuracy， and effectively reduces the synchronization power consumption， and has certain practicability.

Key words：wireless sensor networks;time synchronization; clustering; multi-hop; synchronous energy consumption