具有容錯(cuò)性的時(shí)間同步協(xié)議算法

董仕鵬， 陳 璇

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

?

具有容錯(cuò)性的時(shí)間同步協(xié)議算法

董仕鵬， 陳 璇

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

在無(wú)線傳感器網(wǎng)絡(luò)的許多時(shí)間同步協(xié)議中，算法的精確性、高效性以及簡(jiǎn)潔性總被優(yōu)先考慮。此外，容錯(cuò)性時(shí)間同步協(xié)議也逐漸受到越來(lái)越多的關(guān)注，鑒于經(jīng)典算法浮動(dòng)時(shí)間同步協(xié)議(FTSP)較為全面地考慮了時(shí)間同步的能耗、同步精度、可擴(kuò)展性等要求，提出了一種基于FTSP具有容錯(cuò)性的時(shí)間同步協(xié)議，算法通過對(duì)歷史所測(cè)的有限個(gè)時(shí)鐘漂移率進(jìn)行加權(quán)平均計(jì)算新的漂移率，其中算法的加權(quán)系數(shù)根據(jù)歷史測(cè)量值的方差動(dòng)態(tài)確定。通過Matalab對(duì)新算法的時(shí)鐘漂移率和在接收到錯(cuò)誤信息情況下漂移率的變化進(jìn)行仿真分析，結(jié)果表明：改進(jìn)后的算法具有較強(qiáng)的容錯(cuò)性。

無(wú)線傳感器網(wǎng)絡(luò)； 容錯(cuò)性時(shí)間同步協(xié)議; 時(shí)鐘漂移

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)融合了無(wú)線通信技術(shù)、傳感器技術(shù)以及分布式計(jì)算機(jī)技術(shù)等多種技術(shù)，它是由部署在監(jiān)控區(qū)域里大量廉價(jià)的、具有存儲(chǔ)、感知、通信能力的微型傳感器節(jié)點(diǎn)組成的自組織網(wǎng)絡(luò)。WSNs中分布存在的節(jié)點(diǎn)能將監(jiān)控區(qū)域內(nèi)采集到的數(shù)據(jù)以多跳的方式傳遞給匯聚節(jié)點(diǎn)，匯聚節(jié)點(diǎn)轉(zhuǎn)送給中央控制器，從而實(shí)現(xiàn)對(duì)整個(gè)區(qū)域的監(jiān)控。WSNs的應(yīng)用前景十分廣闊，它在軍事國(guó)防、環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生、科學(xué)研究等領(lǐng)域均發(fā)揮著非常重要的作用[1]。

網(wǎng)絡(luò)時(shí)間同步協(xié)議(network time protocal，NTP)是計(jì)算機(jī)網(wǎng)絡(luò)上應(yīng)用最普遍的協(xié)議。此外，全球定位系統(tǒng)(global positioning system，GPS)也被用來(lái)實(shí)現(xiàn)時(shí)間同步。由于NTP和GPS功耗較高，成本較大，所以不適合WSNs。比較經(jīng)典的時(shí)間同步算法分別參考廣播同步(reference broadcast synchronization,RBS)[2]，傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議(timing synchronization protocol for sensor networks,TPSN)[3]，容錯(cuò)時(shí)間同步協(xié)議(foult-tolerant time synchronization protocol,FTSP)[4]等。RBS是一種系統(tǒng)的WSNs時(shí)間同步算法，同步精度較高，但能耗較大，不適合大型多跳網(wǎng)絡(luò)。TPSN可實(shí)現(xiàn)全網(wǎng)同步，精度高，然而網(wǎng)絡(luò)擴(kuò)展性較差。FTSP是目前最為有效的算法，較為全面地兼顧了時(shí)間同步的能耗、精度、可擴(kuò)展性、魯棒性等要求。

比較幾種經(jīng)典算法發(fā)現(xiàn)，算法均較為全面地考慮了同步精度、能耗等問題，但未考慮同步的容錯(cuò)性。由于WSNs分布在比較惡劣的環(huán)境中，節(jié)點(diǎn)會(huì)因?yàn)橥饨缫蛩氐母蓴_或系統(tǒng)軟硬件的缺陷產(chǎn)生同步數(shù)據(jù)誤差，如果誤差未及時(shí)修正，將影響整個(gè)網(wǎng)絡(luò)的時(shí)間同步精度，導(dǎo)致無(wú)法提供可靠的應(yīng)用[4]。

1 FTSP實(shí)現(xiàn)同步的過程

WSNs時(shí)間同步即對(duì)節(jié)點(diǎn)時(shí)鐘偏移和時(shí)鐘漂移率的補(bǔ)償。時(shí)鐘偏移指兩節(jié)點(diǎn)在同一時(shí)刻的時(shí)鐘偏差，時(shí)鐘漂移則是因?yàn)楦鞴?jié)點(diǎn)的晶振頻率不同而引起的時(shí)鐘振蕩頻率的偏差[5]。FTSP算法利用線性回歸估計(jì)時(shí)鐘漂移率，進(jìn)而利用時(shí)鐘漂移估算和調(diào)整全局時(shí)間。

FTSP會(huì)給每個(gè)節(jié)點(diǎn)分配一個(gè)具有標(biāo)識(shí)作用的ID號(hào)。算法執(zhí)行時(shí)，根據(jù)ID號(hào)動(dòng)態(tài)選取出一個(gè)節(jié)點(diǎn)作為參考節(jié)點(diǎn)。參考節(jié)點(diǎn)會(huì)定期廣播其本地時(shí)間，收到廣播消息的節(jié)點(diǎn)記錄下廣播時(shí)間標(biāo)和接收廣播時(shí)的本地時(shí)間標(biāo)。因此，當(dāng)一個(gè)節(jié)點(diǎn)接收到參考節(jié)點(diǎn)的廣播消息后會(huì)收集到兩個(gè)時(shí)間標(biāo)，一個(gè)本地時(shí)間標(biāo)和一個(gè)參考節(jié)點(diǎn)廣播的時(shí)間標(biāo)。將本地時(shí)間和其與廣播消息的差值作為一個(gè)時(shí)間標(biāo)對(duì)，即參考點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)積累了至少8個(gè)參考點(diǎn)后，即可應(yīng)用線性回歸估算時(shí)鐘漂移率。通過時(shí)鐘漂移率估算全局時(shí)間偏差，從而與參考節(jié)點(diǎn)同步。

2 容錯(cuò)性FTSP

由于時(shí)間同步對(duì)WSNs的各種應(yīng)用至關(guān)重要，因此,在惡劣環(huán)境下，如何提高WSNs節(jié)點(diǎn)時(shí)間同步的精度以及節(jié)點(diǎn)受到惡意攻擊后，如何保證節(jié)點(diǎn)的抗攻擊性已成為近些年的研究熱點(diǎn)。

文獻(xiàn)[6]提出了一種全新的時(shí)間同步協(xié)議實(shí)時(shí)流傳輸協(xié)議(real-time streaming protocol,RTSP)，采用了新的圖形理論方法，能夠在消息層面上檢測(cè)異常數(shù)據(jù)。這種細(xì)粒度的檢測(cè)能力使RTSP可以較好地抵抗女巫攻擊。但協(xié)議的可操作性較差，未充分考慮無(wú)線傳感器的功耗問題。

文獻(xiàn)[7]采用動(dòng)態(tài)選舉時(shí)間基準(zhǔn)節(jié)點(diǎn)來(lái)避免重復(fù)發(fā)送的策略，算法增強(qiáng)了網(wǎng)絡(luò)的可擴(kuò)展性，對(duì)于新加入的節(jié)點(diǎn)可以迅速收斂，同時(shí)利用殘差分析進(jìn)行差錯(cuò)判斷。雖然算法整體上提高了時(shí)間同步的容錯(cuò)性，但是通信量較大。

文獻(xiàn)[8]提出了一種容錯(cuò)協(xié)議，采用分布式算法，由攻擊檢測(cè)模塊、本地時(shí)間校準(zhǔn)模塊、加權(quán)系數(shù)生成模塊組成，能夠有效地消除同步過程中產(chǎn)生的誤差，提高了時(shí)間同步的精度，保證了多通道通信的穩(wěn)定性，但協(xié)議結(jié)構(gòu)復(fù)雜，不容易實(shí)現(xiàn)。

本文在經(jīng)典算法FTSP的基礎(chǔ)上，針對(duì)算法線性回歸易受異常數(shù)據(jù)和其他環(huán)境因素影響的缺陷，提出了一種新的容錯(cuò)算法，對(duì)所測(cè)的有限個(gè)歷史時(shí)鐘漂移率進(jìn)行加權(quán)平均增加時(shí)鐘漂移率的精確性，其中，加權(quán)系數(shù)根據(jù)歷史測(cè)量值的方差動(dòng)態(tài)確定。相比文獻(xiàn)[9,10],系數(shù)確定更加合理科學(xué)，避免了因?yàn)橐揽拷?jīng)驗(yàn)值產(chǎn)生的不確定因素。

3 FTSP的改進(jìn)

FTSP用線性回歸的方法計(jì)算時(shí)鐘漂移率，在一個(gè)周期中，當(dāng)回歸表中收集到8個(gè)參考點(diǎn)后，便可計(jì)算漂移率[11]

n=8,m≥8

(1)

(2)

式中vi為加權(quán)因子

(3)

可以得出，同步周期中測(cè)量值的方差越大，其加權(quán)系數(shù)越小，進(jìn)而在求解漂移率時(shí)比重越小。將式(2)中x和xi用skew′和skewi代替，可得

(4)

結(jié)合式(3)、式(4)，計(jì)算出加權(quán)修正后的時(shí)鐘漂移率

(5)

式中除過方差σ外，其他均為已知量。對(duì)于σ計(jì)算,從文獻(xiàn)[12]可以推斷出，在一定時(shí)間范圍內(nèi)，節(jié)點(diǎn)間的時(shí)鐘偏差和本地時(shí)間具有線性關(guān)系

Toffseti=Toffset0+skew×ti+εi,i=1,2,…,N

(6)

式中Toffset0為初始時(shí)間節(jié)點(diǎn)的時(shí)間偏差；ε為隨機(jī)誤差，服從均值為0，方差為σ′2的正態(tài)分布。即

εi～N(Toffset0+skewi×ti,σ′2)

(7)

根據(jù)式(7),則第m個(gè)周期時(shí)鐘漂移率的方差為

(8)

求出σ后，根據(jù)式(5)計(jì)算出加權(quán)后的時(shí)鐘漂移率。經(jīng)過加權(quán)后的時(shí)鐘漂移率穩(wěn)定性更好，很好地補(bǔ)償了FTSP算法線性回歸易受異常數(shù)據(jù)影響而不穩(wěn)定的缺陷。

4 仿真分析

使用Matlab進(jìn)行仿真分析，仿真參數(shù)為：同步周期30 s;回歸表中存放參考點(diǎn)個(gè)數(shù)為n=8;存放歷史時(shí)鐘漂移率個(gè)數(shù)N=5。在相同條件下，改進(jìn)的FTSP算法同原FTSP算法進(jìn)行比較，主要從同步誤差以及時(shí)鐘漂移率2個(gè)參數(shù)的仿真分布變化情況來(lái)分析改進(jìn)算法的效果。

由圖1可知，原FTSP算法平均同步誤差大約為1.48 μs，改進(jìn)的FTSP算法同步誤差大約為0.98 μs，相比原FTSP算法，改進(jìn)的FTSP算法同步誤差較小。圖2為2種算法時(shí)鐘漂移率的變化情況，由仿真圖可知：原FTSP算法時(shí)鐘漂移率的波動(dòng)較大，改進(jìn)后的算法相對(duì)比較平穩(wěn)。

圖1 2種算法的平均同步誤差

圖2 2種算法的時(shí)鐘漂移率

為了驗(yàn)證容錯(cuò)性，在同步周期的第10次和第20次時(shí)，構(gòu)建一定的偏差信息。具體方法為使節(jié)點(diǎn)接收到的時(shí)間信息發(fā)生一定的偏差，然后分析仿真。

由圖3可知，當(dāng)接收到含有偏差的錯(cuò)誤信息后，在第10次和第20次原FTSP算法的平均同步誤差產(chǎn)生了一定的偏差。最大偏差增加到2.9 μs。相比之下，改進(jìn)的FTSP算法幾乎未受到影響。對(duì)于圖4的時(shí)鐘漂移率，原FTSP算法在接收到錯(cuò)誤信息后，時(shí)鐘漂移率會(huì)產(chǎn)生較大的波動(dòng)，由于改進(jìn)的算法應(yīng)用加權(quán)平均，時(shí)鐘漂移率相對(duì)比較穩(wěn)定。由此證明，改進(jìn)的算法具有較強(qiáng)的容錯(cuò)性。

圖3 2種算法接收到錯(cuò)誤信息的平均同步誤差

圖4 2種算法接收到錯(cuò)誤信息的時(shí)鐘漂移率

5 結(jié) 論

對(duì)FTSP進(jìn)行了改進(jìn)，應(yīng)用隨機(jī)加權(quán)平均算法對(duì)節(jié)點(diǎn)的歷史漂移率的值進(jìn)行加權(quán)平均，加權(quán)平均值增強(qiáng)了FTSP線性回歸求解漂移率的容錯(cuò)性。仿真結(jié)果表明：改進(jìn)后的算法不管是從漂移率的穩(wěn)定程度上還是系統(tǒng)的平均誤差方面均有較明顯改進(jìn)。

[1] Mitehel W M,Petter F. Ten emerging technologies that will change the world[J].Technology Review,2003,106(1):33-49.

[2] Elson J E,Estrin D,Girod L.Fine-grained network time synchronization using reference broadcasts[C]∥The Fifth Sympositum on Operating Systems Design and Implementation,2002:147-163.

[3] Ganeriwal S,Kumar R,Srivastava M B.Time-sync protocol for sensor networked[C]∥Proc of 1st International Conference on Embedded Networked Sensor Systems,2003:138-149.

[4] Kusy B,Ledeczi A,Maroti M,et al.The flooding time synchronization protocol[C]∥Proc of 2nd International Conference on Embedded Networked Sensor System,2004:39-49.

[5] 姜 帆,鄭 霖.無(wú)線傳感器網(wǎng)絡(luò)TPSN-RBS聯(lián)合時(shí)間同步算法[J].傳感器與微系統(tǒng),2016,35(1):149-152.

[6] Dong Wei,Liu Xiaojin.Robust and secure time synchronization aginst sybil attacks for sensor for sensor networks[J].IEEE Journals & Magazines,2015,11(6):1482-1491.

[7] 崔麗珍，園曼曼，李 璋.礦井下WSNs容錯(cuò)性時(shí)間同步算法的研究[J].解放軍理工大學(xué)學(xué)報(bào)，2015,16(5):418-425.

[8] 秦紹華，陳冬巖.具有容錯(cuò)性的無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議[J].軟件學(xué)報(bào)，2012,23(1):126-133.

[9] 李秋靈，白 焰，王仁書.具有容錯(cuò)性的泛洪時(shí)間同步算法研究[J].計(jì)算機(jī)仿真，2013,30(12):257-260.

[10] 楊 朔，李長(zhǎng)庚.無(wú)線傳感器網(wǎng)絡(luò)泛洪時(shí)間同步協(xié)議安全算法[J].傳感器與微系統(tǒng),2014,33(1):137-140.

[11] 陳 瑩，唐加山.無(wú)線傳感器網(wǎng)絡(luò)中一種基于FTSP的時(shí)間同步協(xié)議的改進(jìn)設(shè)計(jì)[J].內(nèi)蒙古大學(xué)學(xué)報(bào),2012,43(4):409-413.

[12] 何曉群，劉文卿.應(yīng)用回歸分析[M].北京:中國(guó)人民大學(xué)出版社,2011:18-54.

Algorithm of fault-tolerant time synchronization protocol

DONG Shi-peng， CHEN Xuan

(College of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China )

In many time synchronization protocols of wireless sensor networks(WSNs),accuracy,high efficiency and simplicity of the algorithm always be given priority.Besides,fault-tolerant time synchronization algorithm is also paid more attention.In view of classical algorithm floating time synchronization protocol(FTSP),it comprehensively considerates the energy consumption,synchronization precision,scalability and and other aspects that may be requested.propose a fault-tolerant time synchronization algorithm that based on FTSP,the algorithm calculate new clock drift rate through measured historical finite clock drift rate weighted average.The weighting coefficienty is dynamically determined according to variance of historical measurements value.Finally,simulation analysis is carried out on clock drift rate of new algorithm and change of error message

clock drift rate by Matalab.The results show that the improved algorithm has strong fault tolerance.

wireless sensor networks(WSNs); fault-tolerant time synchronization protocol(FTSP); clock drift

10.13873/J.1000—9787(2017)08—0149—03

2016—08—29

TP 393

A

1000—9787(2017)08—0149—03

董仕鵬(1989-)，男，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步，E—mail：595935041@qq.com。