無線傳感器網絡IRBS時間同步優化算法

凌海波，陳 妤，周先存

(皖西學院，安徽 六安 237012)

引言

無線傳感器網絡是由部署在監測區域內大量廉價微型的傳感器節點組成，通過無線通信方式形成的一個多跳組織的網絡系統。時間同步作為無線傳感器網絡的核心支持技術之一，在多傳感器數據融合、測距定位、協同休眠等環節都起著關鍵作用［1］。

時間同步機制在傳感器網絡研究領域引起了廣泛關注，國內外學者都紛紛進行研究。從現有的同步算法來看，主要包括3種基本同步機制:(1)RBS(References Broadcast Ring Synchronization)算法機制，該算法是基于接收端–接收端的同步算法，網絡中的兩個節點參考廣播發送時間，分別采用各自的本地時鐘記錄參考到達時間，通過交換記錄時間確定時間偏移，實現同步該算法同步精度較高;(2)Tiny-sync算法機制，是簡單的輕量同步機制，其特點是假設節點時鐘漂移成線性變化，通過交換少量消息能夠提供確定誤差上界的頻偏和相偏估計，但只能實現相位偏差瞬間同步;(3)TPSN算法機制，基于發射者-接收者的節點對方式，每個節點與上一個節點進行同步，從而實現所有節點與根節點時間同步，該算法魯棒性差、能耗開銷比RBS算法大，不適應拓撲結構的變化［2］。

在對RBS算法研究中，針對RBS算法網絡開銷較大和難以實現全網的時間同步問題，提出一種改進的參考廣播同步算法IRBS(Improved References Broadcast Ring Synchronization)，該算法基于多個參考廣播消息條件下，通過對兩個不相鄰的接收節點的相位偏差求均值，利用最大后驗法估算相位偏差［3］，根據估算的相位偏差進行糾正，并采用最小二乘法擬合時鐘偏移［4］，實現同步過程。

1 RBS算法分析

RBS時間同步機制通過廣播同步提示分組實現接收節點的相對時間同步［5］。兩個接收節點接收到發送節點廣播的一個信標分組，每個接收節點根據自己本地的時間記錄接收到信標的時刻，由于兩個接收節點都使用自己的本地時間，所以存在接收時間差值，即為該兩個接收節點間的時間差。RBS算法根據這個時間差，其中一個接收節點調整自己本地時間，從而實現兩個接收節點的時間同步。

信號在空間中傳播時間延遲計算公式［6］為:

其中，De為信號傳播的時延，L為信號傳輸的信道長度，Ve為電磁波的傳播的速度。由于電磁波在自由空間的傳播速度近似于光速，因此對于傳播時間，RBS算法只關心各個接收節點之間消息傳播時間的差值，對于傳播時間延遲可以忽略。RBS算法是為了消除參考廣播信號從發送節點傳送到接收節點之間的關鍵路徑上發生的時間延遲以及訪問時間延遲，如圖1所示。

圖1 傳統同步系統和RSB算法傳輸延遲分析

Elson等人通過實驗證明了在接收到參考消息后，接收端任意兩個節點之間的本地時間差的相位偏差符合正態分布。在RBS算法過程中，對于單個廣播域內的n個節點和m個廣播消息，RBS的復雜度為O(mn)。對于多跳網絡的RBS的機制復雜度較高，也增加了網絡開銷，同時網絡中的誤差也隨跳數增加而增加［2］。

2 IRBS算法

針對RBS算法存在網絡開銷大和同步精度低等問題，根據RBS算法相位偏差符合正太分布，提出改進的同步算法IRBS(Improved References Broadcast Ring Synchronization)。RBS算法存在由消息傳送延遲帶來的非確定性相位偏差和由節點內部晶振帶來確定性頻率偏移。IRBS算法對此進行改進，主要分兩步實現網絡中所有節點的時間同步，首先是采用最大后驗法對相位偏差進行估計，通過該估計值調整所有節點的本地時間;然后估計頻率偏移，實現時鐘漂移估計［7］。

2.1 IRBS相位偏差估計

在RBS算法中，當發送節點發送參考消息時，RBS算法要求每個接收節點都與除自身之外的其他所有接收節點交換此消息的本地時間，計算出兩個節點的本地時間差。如圖2(a)顯示的是RBS算法下的相位偏差估計示意圖，圖中給出了6個節點，其中一個是發送節點，其他為接收節點。隨著節點數量的增加，RBS算法計算復雜度將會急劇增加，同時增加了網絡開銷。圖2(b)顯示的是IRBS算法下對相位偏差估計示意圖，在多個參考廣播消息條件下，每個接收節點只與不相鄰的接收節點進行參考消息交換，計算出兩個不相鄰的接收節點的相位偏差求均值，由此獲得網絡中任意兩個不相鄰接收節點之間的相位偏差。再利用貝葉斯最大后驗估計出所有相位偏差的估計值，最后所有節點根據該估計值調制本地時間，實現網絡接收節點時間同步。

圖2 RBS和IRBS算法相位偏差估計示意圖

RBS算法時間估計主要包括接收時間誤差和時鐘誤差，對于任意的節點，i∈n，j∈n，n為第n號節點，m為第m個消息。接收時間誤差和時鐘誤差分別為:

IRBS算法中，若網絡中存在n個接收節點，假設i、j分別表示兩個不相鄰的節點序號，即i∈n，j∈n，其中i-j≠±1;若Ts，k為接收節點s接收到參考消息包k時的本地時間，其中s∈n，若發送節點發送m個參考廣播消息，則兩個不相鄰節點交換m個參考消息的相位偏差φ為:

根據Elson等人通過實驗結論得出的每個接收節點間的相位偏差φ符合μ=0，σ=11.1的正態分布，因此采用最大后驗估計法對相位偏差進行估計［8-11］。

用φ為相位偏差測量值，根據Elson等人的實驗結論，假設相位服從均值為μ=0，方差為σ0的正太分布。從中抽取一個大小為 n的隨機樣本，記 φi=(φ1，φ2，...，φn)，則 φi在統計學條件概率密度為

相位偏差概率密度為

由統計學可知

根據貝葉斯后驗估計法，φ的后驗分布為

對式(8)取對數

將式(4)～式(6)帶入式(9)并對φ求偏導得

進一步可簡化得

求得相位偏差估計值為

2.2 時鐘漂移估計

節點i∈n，j∈n之間的本地時鐘關系為:

其中，aij是節點i相對于節點j之間的頻率偏差，bij為兩個節點的本地時鐘初始相位偏差，ε為節點i與節點j接收到同一消息時兩個節點的本地時間偏差。采用最小二乘法對頻率和時鐘進行擬合，得出

節點i根據式(13)調制本地時間，達到與節點j時間同步。

3 仿真測試與分析

采用Matlab，在同步精度、能量消耗以及同步開銷等方面驗證IRBS算法的有效性。在一個類似于算法的網絡仿真400 m×400 m的環境區域內隨機布置多個無線傳感網絡節點進行同步算法仿真實驗，其中有多個發送節點，其他的均為接收節點。節點的通信半徑為50 m，數據包傳輸速率為50 Kb/s，延時和誤差初始化為0。相關仿真條件如下:節點間的最大通信理論值為80 m。

為了驗證RBS和IRBS兩種算法的同步精度，通過仿真平臺分別在50個節點和100個節點情況下，利用IRBS和RBS算法補償節點間的同步時間。圖3為網絡存在50個節點和100個節點的情況下同步誤差隨時間的變化規律。由圖3可知，基于改進的IRBS算法的同步誤差明顯低于RBS算法的同步誤差。隨著節點數量增加，IRBS算法的同步誤差也較RBS算法有顯著改善，即IRBS的同步精度優于RBS算法。

對RBS、IRBS算法在廣播產生消息包數量及網絡同步開銷方面進行仿真實驗，如圖4所示。當網絡節點數量較少時，兩種算法同步開銷相差不大，但隨著節點數量的不斷增加，IRBS算法增加趨勢非常平緩，且明顯低于RBS算法，即改進的IRBS算法下的同步開銷比RBS同步開銷減少了很多。

圖5給出了兩種算法在不同節點數量下的能量消耗對比圖。由圖可知，隨著節點個數的增加，兩種算法下的能耗都在增加，IRBS相比于RBS算法能量消耗有了很大的改善。由此可知當兩種算法的同步精度要求一致的情況下，IRBS算法相比RBS算法能夠更好的延長節點的使用壽命。

圖3 同步誤差對比分析

圖4 同步開銷對比分析

圖5 算法能耗對比分析圖

4 結束語

本文在分析傳統RBS時間同步算法的基礎上，提出了一種改進的IRBS時間同步算法。該算法對不相鄰的兩個接收節點在不同的廣播消息下求平均相位偏差，采用最大后驗法估計節點相位偏差值，各接收節點根據相位偏差估計值對自身時間進行調節，實現對相位偏差的糾正。最小二乘法進行估計擬合時鐘偏移，完成整個同步過程。分別從同步精度、同步開銷、能量消耗三個方面對RBS和IRBS進行試驗分析，通過仿真表明，改進的IRBS算法同步精度和能耗開銷都優于RBS算法。

[1] 孫利民,李建中.無線傳感器網絡[M].北京:清華大學出版社,2005.

[2] Yang J,Rabaey J.Light weight Time Sychronization for Sensor Networks[C]//Proceeding of the Second ACM Workshop on WSNA,San Diego,California,September 19-22,2003:11-19.

[3] Gao R,Ye F,Wang T.Smartphone indoor location by Photo-taking of the environment[C]//Proceedings of the IEEE ICC,Sydney,Australia,June 10-14,2014:2599-2604.

[4] 孫德云,沈杰,劉海濤.基于擴散機制的無線傳感器網絡時間同步協議[J].通信學報,2008,29(11):40-49.

[5] 徐煥良,劉佼佼,王浩云,等.WSN/WSAN中的時間同步算法研究[J].計算機工程與應用,2012,48(31):56-60.

[6] Park S,Crespi N,Oh S,et al.Overlay Multicast Protocol with Proxy Districts for Dynamic Wireless Sensor Networks[C]//Proceeding of 2013 12th IEEE International Symposium on Network Computing and Applications(NCA),Cambridge,MA,August 22-24,2013:187-194.

[7] 王義君,錢志鴻,王桂琴,等.無線傳感器網絡能量有效時間同步算法研究[J].電子與信息學報,2012,34(9):2174-2179.

[8] Sichitiu M L,Veerarittiphan C.Simple,accurate time syn-chronization for wireless sensor networks[C]//Proceeding of the IEEE Wireless Communications and Networking(WCNC 2003),New Orleans,LA,March 20,2003:1266-1273.

[9] Zhou Q Y,Koltun V.Simultaneous localization and calibration:Self-Calibration of Consumer Depth Cameras[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition(CVPR),Columbus,OH,June 23-28,2014:454-460.

[10] 張瑞華,賈智平,程合友.基于非均勻分簇和最小能耗的無線傳感網絡路由算法[J].上海交通大學學報,2012,46(11):1774-1778.

[11] Zheng Y,Suginoyo S,Sato I,et al.A General and simple method for Camera Pose and FocalLength Determination[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition(CVPR),Columbus,OH,June 23-28,2014:430-437.