無(wú)線傳感器網(wǎng)絡(luò)IRBS時(shí)間同步優(yōu)化算法

凌海波，陳 妤，周先存

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

引言

無(wú)線傳感器網(wǎng)絡(luò)是由部署在監(jiān)測(cè)區(qū)域內(nèi)大量廉價(jià)微型的傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成的一個(gè)多跳組織的網(wǎng)絡(luò)系統(tǒng)。時(shí)間同步作為無(wú)線傳感器網(wǎng)絡(luò)的核心支持技術(shù)之一，在多傳感器數(shù)據(jù)融合、測(cè)距定位、協(xié)同休眠等環(huán)節(jié)都起著關(guān)鍵作用［1］。

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

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

1 RBS算法分析

RBS時(shí)間同步機(jī)制通過(guò)廣播同步提示分組實(shí)現(xiàn)接收節(jié)點(diǎn)的相對(duì)時(shí)間同步［5］。兩個(gè)接收節(jié)點(diǎn)接收到發(fā)送節(jié)點(diǎn)廣播的一個(gè)信標(biāo)分組，每個(gè)接收節(jié)點(diǎn)根據(jù)自己本地的時(shí)間記錄接收到信標(biāo)的時(shí)刻，由于兩個(gè)接收節(jié)點(diǎn)都使用自己的本地時(shí)間，所以存在接收時(shí)間差值，即為該兩個(gè)接收節(jié)點(diǎn)間的時(shí)間差。RBS算法根據(jù)這個(gè)時(shí)間差，其中一個(gè)接收節(jié)點(diǎn)調(diào)整自己本地時(shí)間，從而實(shí)現(xiàn)兩個(gè)接收節(jié)點(diǎn)的時(shí)間同步。

信號(hào)在空間中傳播時(shí)間延遲計(jì)算公式［6］為:

其中，De為信號(hào)傳播的時(shí)延，L為信號(hào)傳輸?shù)男诺篱L(zhǎng)度，Ve為電磁波的傳播的速度。由于電磁波在自由空間的傳播速度近似于光速，因此對(duì)于傳播時(shí)間，RBS算法只關(guān)心各個(gè)接收節(jié)點(diǎn)之間消息傳播時(shí)間的差值，對(duì)于傳播時(shí)間延遲可以忽略。RBS算法是為了消除參考廣播信號(hào)從發(fā)送節(jié)點(diǎn)傳送到接收節(jié)點(diǎn)之間的關(guān)鍵路徑上發(fā)生的時(shí)間延遲以及訪問(wèn)時(shí)間延遲，如圖1所示。

圖1 傳統(tǒng)同步系統(tǒng)和RSB算法傳輸延遲分析

Elson等人通過(guò)實(shí)驗(yàn)證明了在接收到參考消息后，接收端任意兩個(gè)節(jié)點(diǎn)之間的本地時(shí)間差的相位偏差符合正態(tài)分布。在RBS算法過(guò)程中，對(duì)于單個(gè)廣播域內(nèi)的n個(gè)節(jié)點(diǎn)和m個(gè)廣播消息，RBS的復(fù)雜度為O(mn)。對(duì)于多跳網(wǎng)絡(luò)的RBS的機(jī)制復(fù)雜度較高，也增加了網(wǎng)絡(luò)開(kāi)銷，同時(shí)網(wǎng)絡(luò)中的誤差也隨跳數(shù)增加而增加［2］。

2 IRBS算法

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

2.1 IRBS相位偏差估計(jì)

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

圖2 RBS和IRBS算法相位偏差估計(jì)示意圖

RBS算法時(shí)間估計(jì)主要包括接收時(shí)間誤差和時(shí)鐘誤差，對(duì)于任意的節(jié)點(diǎn)，i∈n，j∈n，n為第n號(hào)節(jié)點(diǎn)，m為第m個(gè)消息。接收時(shí)間誤差和時(shí)鐘誤差分別為:

IRBS算法中，若網(wǎng)絡(luò)中存在n個(gè)接收節(jié)點(diǎn)，假設(shè)i、j分別表示兩個(gè)不相鄰的節(jié)點(diǎn)序號(hào)，即i∈n，j∈n，其中i-j≠±1;若Ts，k為接收節(jié)點(diǎn)s接收到參考消息包k時(shí)的本地時(shí)間，其中s∈n，若發(fā)送節(jié)點(diǎn)發(fā)送m個(gè)參考廣播消息，則兩個(gè)不相鄰節(jié)點(diǎn)交換m個(gè)參考消息的相位偏差φ為:

根據(jù)Elson等人通過(guò)實(shí)驗(yàn)結(jié)論得出的每個(gè)接收節(jié)點(diǎn)間的相位偏差φ符合μ=0，σ=11.1的正態(tài)分布，因此采用最大后驗(yàn)估計(jì)法對(duì)相位偏差進(jìn)行估計(jì)［8-11］。

用φ為相位偏差測(cè)量值，根據(jù)Elson等人的實(shí)驗(yàn)結(jié)論，假設(shè)相位服從均值為μ=0，方差為σ0的正太分布。從中抽取一個(gè)大小為 n的隨機(jī)樣本，記 φi=(φ1，φ2，...，φn)，則 φi在統(tǒng)計(jì)學(xué)條件概率密度為

相位偏差概率密度為

由統(tǒng)計(jì)學(xué)可知

根據(jù)貝葉斯后驗(yàn)估計(jì)法，φ的后驗(yàn)分布為

對(duì)式(8)取對(duì)數(shù)

將式(4)～式(6)帶入式(9)并對(duì)φ求偏導(dǎo)得

進(jìn)一步可簡(jiǎn)化得

求得相位偏差估計(jì)值為

2.2 時(shí)鐘漂移估計(jì)

節(jié)點(diǎn)i∈n，j∈n之間的本地時(shí)鐘關(guān)系為:

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

節(jié)點(diǎn)i根據(jù)式(13)調(diào)制本地時(shí)間，達(dá)到與節(jié)點(diǎn)j時(shí)間同步。

3 仿真測(cè)試與分析

采用Matlab，在同步精度、能量消耗以及同步開(kāi)銷等方面驗(yàn)證IRBS算法的有效性。在一個(gè)類似于算法的網(wǎng)絡(luò)仿真400 m×400 m的環(huán)境區(qū)域內(nèi)隨機(jī)布置多個(gè)無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行同步算法仿真實(shí)驗(yàn)，其中有多個(gè)發(fā)送節(jié)點(diǎn)，其他的均為接收節(jié)點(diǎn)。節(jié)點(diǎn)的通信半徑為50 m，數(shù)據(jù)包傳輸速率為50 Kb/s，延時(shí)和誤差初始化為0。相關(guān)仿真條件如下:節(jié)點(diǎn)間的最大通信理論值為80 m。

為了驗(yàn)證RBS和IRBS兩種算法的同步精度，通過(guò)仿真平臺(tái)分別在50個(gè)節(jié)點(diǎn)和100個(gè)節(jié)點(diǎn)情況下，利用IRBS和RBS算法補(bǔ)償節(jié)點(diǎn)間的同步時(shí)間。圖3為網(wǎng)絡(luò)存在50個(gè)節(jié)點(diǎn)和100個(gè)節(jié)點(diǎn)的情況下同步誤差隨時(shí)間的變化規(guī)律。由圖3可知，基于改進(jìn)的IRBS算法的同步誤差明顯低于RBS算法的同步誤差。隨著節(jié)點(diǎn)數(shù)量增加，IRBS算法的同步誤差也較RBS算法有顯著改善，即IRBS的同步精度優(yōu)于RBS算法。

對(duì)RBS、IRBS算法在廣播產(chǎn)生消息包數(shù)量及網(wǎng)絡(luò)同步開(kāi)銷方面進(jìn)行仿真實(shí)驗(yàn)，如圖4所示。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量較少時(shí)，兩種算法同步開(kāi)銷相差不大，但隨著節(jié)點(diǎn)數(shù)量的不斷增加，IRBS算法增加趨勢(shì)非常平緩，且明顯低于RBS算法，即改進(jìn)的IRBS算法下的同步開(kāi)銷比RBS同步開(kāi)銷減少了很多。

圖5給出了兩種算法在不同節(jié)點(diǎn)數(shù)量下的能量消耗對(duì)比圖。由圖可知，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，兩種算法下的能耗都在增加，IRBS相比于RBS算法能量消耗有了很大的改善。由此可知當(dāng)兩種算法的同步精度要求一致的情況下，IRBS算法相比RBS算法能夠更好的延長(zhǎng)節(jié)點(diǎn)的使用壽命。

圖3 同步誤差對(duì)比分析

圖4 同步開(kāi)銷對(duì)比分析

圖5 算法能耗對(duì)比分析圖

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

本文在分析傳統(tǒng)RBS時(shí)間同步算法的基礎(chǔ)上，提出了一種改進(jìn)的IRBS時(shí)間同步算法。該算法對(duì)不相鄰的兩個(gè)接收節(jié)點(diǎn)在不同的廣播消息下求平均相位偏差，采用最大后驗(yàn)法估計(jì)節(jié)點(diǎn)相位偏差值，各接收節(jié)點(diǎn)根據(jù)相位偏差估計(jì)值對(duì)自身時(shí)間進(jìn)行調(diào)節(jié)，實(shí)現(xiàn)對(duì)相位偏差的糾正。最小二乘法進(jìn)行估計(jì)擬合時(shí)鐘偏移，完成整個(gè)同步過(guò)程。分別從同步精度、同步開(kāi)銷、能量消耗三個(gè)方面對(duì)RBS和IRBS進(jìn)行試驗(yàn)分析，通過(guò)仿真表明，改進(jìn)的IRBS算法同步精度和能耗開(kāi)銷都優(yōu)于RBS算法。

[1] 孫利民,李建中.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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] 孫德云,沈杰,劉海濤.基于擴(kuò)散機(jī)制的無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議[J].通信學(xué)報(bào),2008,29(11):40-49.

[5] 徐煥良,劉佼佼,王浩云,等.WSN/WSAN中的時(shí)間同步算法研究[J].計(jì)算機(jī)工程與應(yīng)用,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] 王義君,錢(qián)志鴻,王桂琴,等.無(wú)線傳感器網(wǎng)絡(luò)能量有效時(shí)間同步算法研究[J].電子與信息學(xué)報(bào),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] 張瑞華,賈智平,程合友.基于非均勻分簇和最小能耗的無(wú)線傳感網(wǎng)絡(luò)路由算法[J].上海交通大學(xué)學(xué)報(bào),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.