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

關(guān)鍵詞：無(wú)線傳感網(wǎng)絡(luò);時(shí)間同步;分簇;多跳;同步能耗

1 ? ?時(shí)間同步技術(shù)簡(jiǎn)介

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

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

2 ? ?算法分析

2.1 ?層次構(gòu)造階段

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

2.2 ?時(shí)間同步階段

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

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

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

2.2.2 普通節(jié)點(diǎn)同步

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

3 ? ?算法同步誤差分析

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

（3）

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

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

（4）

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

4 ?結(jié)語(yǔ)

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

[參考文獻(xiàn)]

[1]張超.無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)進(jìn)展[J].重慶工商大學(xué)學(xué)報(bào)（自然科學(xué)版），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