董仕鵬， 陳 璇

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

?

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

董仕鵬， 陳 璇

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

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

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

0 引 言

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

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

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

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

WSNs時間同步即對節(jié)點時鐘偏移和時鐘漂移率的補償。時鐘偏移指兩節(jié)點在同一時刻的時鐘偏差，時鐘漂移則是因為各節(jié)點的晶振頻率不同而引起的時鐘振蕩頻率的偏差[5]。FTSP算法利用線性回歸估計時鐘漂移率，進而利用時鐘漂移估算和調整全局時間。

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

2 容錯性FTSP

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

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

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

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

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

3 FTSP的改進

FTSP用線性回歸的方法計算時鐘漂移率，在一個周期中，當回歸表中收集到8個參考點后，便可計算漂移率[11]

n=8,m≥8

(1)

(2)

式中vi為加權因子

(3)

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

(4)

結合式(3)、式(4)，計算出加權修正后的時鐘漂移率

(5)

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

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

(6)

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

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

(7)

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

(8)

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

4 仿真分析

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

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

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

圖2 2種算法的時鐘漂移率

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

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

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

圖4 2種算法接收到錯誤信息的時鐘漂移率

5 結 論

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

[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ǎng)絡TPSN-RBS聯(lián)合時間同步算法[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容錯性時間同步算法的研究[J].解放軍理工大學學報，2015,16(5):418-425.

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

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

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

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

[12] 何曉群，劉文卿.應用回歸分析[M].北京:中國人民大學出版社,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-)，男，碩士研究生，研究方向為無線傳感器網(wǎng)絡時間同步，E—mail：595935041@qq.com。