具有容錯性的時間同步協議算法

董仕鵬， 陳 璇

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

?

具有容錯性的時間同步協議算法

董仕鵬， 陳 璇

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

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

無線傳感器網絡； 容錯性時間同步協議; 時鐘漂移

0 引 言

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

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

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

1 FTSP實現同步的過程

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

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

2 容錯性FTSP

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

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

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

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

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

3 FTSP的改進

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

n=8,m≥8

(1)

(2)

式中vi為加權因子

(3)

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

(4)

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

(5)

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

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

(6)

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

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

(7)

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

(8)

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

4 仿真分析

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

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

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

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

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

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

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

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

5 結 論

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

[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] 姜 帆,鄭 霖.無線傳感器網絡TPSN-RBS聯合時間同步算法[J].傳感器與微系統,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] 秦紹華，陳冬巖.具有容錯性的無線傳感器網絡時間同步協議[J].軟件學報，2012,23(1):126-133.

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

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

[11] 陳 瑩，唐加山.無線傳感器網絡中一種基于FTSP的時間同步協議的改進設計[J].內蒙古大學學報,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-)，男，碩士研究生，研究方向為無線傳感器網絡時間同步，E—mail：595935041@qq.com。