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

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

1 ? ?時間同步技術簡介

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

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

2 ? ?算法分析

2.1 ?層次構造階段

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

2.2 ?時間同步階段

2.2.1 ?反饋節(jié)點的同步

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

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

2.2.2 普通節(jié)點同步

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

3 ? ?算法同步誤差分析

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

（3）

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

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

（4）

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

4 ?結語

本文提出了一種基于分簇的WSN時間同步算法，該算法建立在分簇網(wǎng)絡的基礎上，利用簇內(nèi)節(jié)點同步方式進行優(yōu)化，結合了SRS和ROS同步方法，有效保證了同步精度的同時，也降低了同步消息包的收發(fā)數(shù)量，從而大大降低了網(wǎng)絡能耗。

[參考文獻]

[1]張超.無線傳感器網(wǎng)絡時間同步技術進展[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