無線傳感器網(wǎng)絡(luò)同步算法的研究與探討

無線傳感器網(wǎng)絡(luò)同步算法的研究與探討引言

無線傳感器網(wǎng)絡(luò)技術(shù)融合了傳感器、低功耗嵌入式計(jì)算器、無線網(wǎng)絡(luò)和通信、分布式信息處理等技術(shù)，利用傳感節(jié)點(diǎn)通過自組網(wǎng)絡(luò)對監(jiān)測對象進(jìn)行實(shí)時監(jiān)測、感知和采集，在環(huán)境、資源、智能交通、礦井安全等領(lǐng)域都有著良好的應(yīng)用前景，是近年來國內(nèi)外信息領(lǐng)域研究和競爭的焦點(diǎn)。而時間同步技術(shù)是無線傳感器網(wǎng)絡(luò)中一項(xiàng)非常關(guān)鍵的基礎(chǔ)技術(shù)。網(wǎng)絡(luò)時間協(xié)議NTP[1]（NetworkTimeProtocol）是傳統(tǒng)網(wǎng)絡(luò)的時間同步協(xié)議，最早由美國Delaware大學(xué)的Mill教授提出。然而NTP是應(yīng)傳統(tǒng)網(wǎng)絡(luò)的能量效率、網(wǎng)絡(luò)動態(tài)、基礎(chǔ)設(shè)施和系統(tǒng)而構(gòu)建，因此并不適合低功耗、低成本、微型化、高集成、協(xié)作式多跳自組織的無線傳感器網(wǎng)絡(luò)。另外，無線傳感器網(wǎng)絡(luò)時間同步算法還要考慮能量消耗、可拓展性、精確度、魯棒性等問題，這些都對無線傳感器網(wǎng)絡(luò)的時間同步算法提出了新的要求和挑戰(zhàn)。

在2002年的HotNets上，JElson和KayRomer首次提出并闡述了無線傳感器網(wǎng)絡(luò)時間同步技術(shù)的課題，在國際上引發(fā)了廣泛的關(guān)注和思考，吸引了許多大學(xué)和研究機(jī)構(gòu)參與研究，已經(jīng)提出許多種不同的實(shí)現(xiàn)算法及改進(jìn)算法，典型的有RBS[2]算法、TPSN[3]算法、還有TDP[4]算法、FTSP[5]算法、DMTS[6]算法、LTS[7]算法、TS/MS[8]算法、HRTS[9]算法、OFDC[10]算法、CHTS[11]算法、CRIT[12]算法以及最新的基于螢火蟲技術(shù)和協(xié)作技術(shù)的時間同步算法等。

1概念與定義

在計(jì)算機(jī)體系結(jié)構(gòu)中，時鐘通常用晶體振蕩器脈沖來度量，即

式中C(t)為構(gòu)造的本地時鐘，t為真實(shí)時間變量，k為依賴于晶振的物理特性常量，ω(τ)為晶振的頻率，間隔c(t)-c(t0)被用來作為度量時間。對于理想的時鐘，有r(t)=dc(t)/dt=1，也就是說，理想時鐘的變化速率r(t)為1。但在工程實(shí)踐中，因?yàn)闇囟?、壓力、電源電壓等外界環(huán)境的變化，往往會導(dǎo)致晶振頻率產(chǎn)生波動。因此構(gòu)造理想時鐘比較困難，但在一般情況下晶振頻率的波動幅度并非任意的，而是局限在一定范圍之內(nèi)。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。

假定c(t)是一個理想的時鐘。如果在t時刻有c(t)=ci(t)，則稱ci(t)在t時刻是準(zhǔn)確的；如果dc(t)/dt=dci(t)/dt，則稱時鐘ci(t)在t時刻是精確的；如果ci(t)=ck(t)，則稱時鐘ci(t)在t時刻與時鐘ck(t)是同步的。上述定義表明，兩個同步時鐘不一定是準(zhǔn)確或精確的，時間同步與時間的準(zhǔn)確性和精度沒有必然的聯(lián)系。

如果采用時鐘速率恒定模型，由式（1），時鐘ci(t)可以簡化表示為：

由此可知，時鐘ci(t)和ck(t)之間應(yīng)該存在如下的線性關(guān)系：

式中aik、bik為相對漂移量和相對偏移量。2典型同步算法

Elson、Girod和Estrin在參考文獻(xiàn)[2]中以“第三節(jié)點(diǎn)”實(shí)現(xiàn)同步的思想提出了RBS算法，這是一種基于接收者接收者的時間同步協(xié)議。根節(jié)點(diǎn)周期性地向其廣播域中的子節(jié)點(diǎn)發(fā)送不包含時間戳的參照廣播（ReferencesBroadcast）消息。接收到廣播消息后，鄰居子節(jié)點(diǎn)用自己的本地時鐘記錄各自的接收時刻作為參考比對時鐘，然后相互交換它們記錄的時間信息，這樣接收節(jié)點(diǎn)就能知道彼此之間的時鐘偏移量。然后利用式（4）計(jì)算相對其他各個節(jié)點(diǎn)的時鐘偏移的平均值，并相應(yīng)進(jìn)行調(diào)整。當(dāng)所有節(jié)點(diǎn)都獲得相對其他節(jié)點(diǎn)的時鐘偏移量平均值時，所有接收同一參照廣播消息的接收節(jié)點(diǎn)便獲得了一個相對網(wǎng)絡(luò)時間，即：

式中：n為待同步節(jié)點(diǎn)數(shù)，m為參考廣播的次數(shù)，Ti,k為第i個節(jié)點(diǎn)接收第k次參考廣播的本地時刻。顯然，由offset(i,j)形成的矩陣為對稱矩陣，且對角線元素為0。

TPSN算法是由Ganeriwal等人提出的，是一種基于發(fā)送者和接收者的時間同步算法。采用層次型網(wǎng)絡(luò)結(jié)構(gòu)。算法分兩步：首先是層次發(fā)現(xiàn)階段，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；然后每個節(jié)點(diǎn)與上一級的一個節(jié)點(diǎn)進(jìn)行時間同步，最終實(shí)現(xiàn)所有節(jié)點(diǎn)都與根節(jié)點(diǎn)的時間同步。

FTSP協(xié)議是一種單向廣播的發(fā)送者和接收者的時間同步協(xié)議。協(xié)議首先要網(wǎng)絡(luò)動態(tài)地選擇一個節(jié)點(diǎn)作為網(wǎng)絡(luò)的根節(jié)點(diǎn)，其時間作為全網(wǎng)的參考時間，根節(jié)點(diǎn)把含有當(dāng)前本地時間的信息包發(fā)送給它單跳廣播域內(nèi)的鄰居節(jié)點(diǎn)；鄰居節(jié)點(diǎn)在收到信息后分別記錄相應(yīng)的接收時間，采用參數(shù)擬合技術(shù)算出相對于根節(jié)點(diǎn)的時間漂移和時間偏移；然后這些與根節(jié)點(diǎn)同步了的鄰居節(jié)點(diǎn)也作為參考節(jié)點(diǎn)，采用與根節(jié)點(diǎn)同步的相同的辦法，使它們的鄰居節(jié)點(diǎn)也實(shí)現(xiàn)與其同步。

無線傳感器網(wǎng)絡(luò)的最常見的幾種同步算法的性能比較如表1所列。3螢火蟲同步算法和梯度同步算法

前面的時間同步技術(shù)都是基于時間信息交換的同步技術(shù)，然而在大規(guī)模的無線傳感器網(wǎng)絡(luò)中，存在同步誤差會隨著跳距而積累的問題和可拓展性需求等問題。螢火蟲同步技術(shù)和協(xié)作同步技術(shù)是為了實(shí)現(xiàn)節(jié)點(diǎn)的同步性，即使節(jié)點(diǎn)的某些周期性動作具有相同的周期和相位，例如使一群螢火蟲同步閃爍并且閃爍周期相同。1990年，Mirollo和Strogatz在Peskin模型的基礎(chǔ)上提出了更一般的脈沖耦合振蕩器模型（后簡稱為M&S模型）。在此模型中，振蕩器使用狀態(tài)變量x來描述，x的變化服從函數(shù)f(φ)，其中f是一個[0,1]到[0，1]的光滑單調(diào)遞增上凸函數(shù)，φ是相位變量且滿足dφdt=1/T（T是同步周期）。Mirollo和Strogatz從理論上證明了在M&S模型下，多個耦合振蕩器系統(tǒng)在幾乎所有的初始情況下都能夠達(dá)到同步，并在無線多跳網(wǎng)絡(luò)測試床Gains上實(shí)現(xiàn)了M&S模型的螢火蟲同步算法。

麻省理工學(xué)院的RuiFan、NancyLynch兩位第一次提出了GCS梯度同步算法。在移動自組織網(wǎng)絡(luò)中往往是鄰居節(jié)點(diǎn)聯(lián)系比較密切，而相距較遠(yuǎn)的節(jié)點(diǎn)很少交換消息，因此相距較遠(yuǎn)的節(jié)點(diǎn)可以允許較大誤差。如數(shù)據(jù)融合中，具有相同父節(jié)點(diǎn)的子節(jié)點(diǎn)需要精確的同步，但是較遠(yuǎn)的節(jié)點(diǎn)不是同一個父節(jié)點(diǎn)，可以允許誤差大一些。就是根據(jù)這一特征提出了梯度同步算法。在通常的時間同步算法的基礎(chǔ)上，假設(shè)兩任意節(jié)點(diǎn)i、j，f(dij)為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最大時鐘差，時鐘記為Lai(t)。信息從節(jié)點(diǎn)i傳到j(luò)的傳播時間為0到dij，dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。D=maxijdij，為網(wǎng)絡(luò)的直徑。GCS提出了兩要求：

計(jì)算出時鐘漂移的最低邊界滿足f(D)=Ω(d+lgD/lglgD)，這也就是說節(jié)點(diǎn)之間的時鐘漂移不只與兩個節(jié)點(diǎn)間的距離有關(guān)，還與整個網(wǎng)絡(luò)的規(guī)模有關(guān)，越近的節(jié)點(diǎn)同步效果越好，反之越差。GTSP（GradientTimeSynchronizationProtocol）協(xié)議中，每個節(jié)點(diǎn)通過接收鄰居節(jié)點(diǎn)的時間來修正自己的時鐘，整個網(wǎng)絡(luò)無需建立一個拓?fù)錁浣Y(jié)構(gòu)，也無需參考節(jié)點(diǎn)，主要是實(shí)現(xiàn)直接的鄰居節(jié)點(diǎn)間直接的高精度的同步，同時考慮時間漂移和偏移補(bǔ)償，漂移補(bǔ)償采用式（5）。通過這種補(bǔ)償機(jī)制，所有節(jié)點(diǎn)的邏輯漂移將趨近值Xss；時鐘偏移補(bǔ)償采用式（6）。協(xié)議的在Mica2節(jié)點(diǎn)上進(jìn)行了仿真，通過20個節(jié)點(diǎn)實(shí)驗(yàn)，采用Mac層時間戳技術(shù)，得出鄰居節(jié)點(diǎn)之間的平均同步精度達(dá)到4.0μs，整個網(wǎng)絡(luò)的平均同步精度達(dá)到14.0μs。

4分布式時隙同步算法

主從同步方法是網(wǎng)絡(luò)中所有的節(jié)點(diǎn)與參考節(jié)點(diǎn)保持時間同步，對參考節(jié)點(diǎn)依賴性高，且同步的誤差隨著跳數(shù)而累積；分布式同步則利用網(wǎng)絡(luò)中所有節(jié)點(diǎn)的彼此時間信息進(jìn)行調(diào)整，不依賴任何特殊的節(jié)點(diǎn)，且不會有誤差的累積，因此更加適合于大型的多跳自組織的無線傳感器網(wǎng)絡(luò)。分布式時隙同步算法利用了網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的時隙偏差值來計(jì)算時隙的調(diào)整量，實(shí)驗(yàn)證明該算法收斂速度快，平均每個節(jié)點(diǎn)的計(jì)算量小，非常適合于移動自組網(wǎng)的無線傳感器網(wǎng)絡(luò)終端節(jié)點(diǎn)的運(yùn)行。采用固定的時隙調(diào)整時，根據(jù)節(jié)點(diǎn)間時隙基準(zhǔn)是超前還是滯后來調(diào)整時隙基準(zhǔn)?；诜植际揭恢碌臒o線傳感器網(wǎng)絡(luò)的時間同步協(xié)議的收斂和加速問題研究中，將分布式一致的收斂和加速問題映射到馬爾科夫鏈的狀態(tài)轉(zhuǎn)移過程，但是排除了連通度對收斂速度的影響，得出收斂速度與節(jié)點(diǎn)鄰居數(shù)和網(wǎng)絡(luò)規(guī)模有關(guān)的結(jié)論，并通過100個節(jié)點(diǎn)組網(wǎng)實(shí)驗(yàn)得出了可以降低25%的迭代數(shù)的結(jié)論。

假設(shè)網(wǎng)內(nèi)任意節(jié)點(diǎn)i，對應(yīng)其所有的鄰居節(jié)點(diǎn)的時隙差值為Δtij，可以算出所有鄰居節(jié)點(diǎn)的時隙偏差值的加權(quán)平均值為εi，時隙修正量ωij。節(jié)點(diǎn)互同步過程如圖1所示，假設(shè)節(jié)點(diǎn)5能感知其鄰居節(jié)點(diǎn)（節(jié)點(diǎn)3、節(jié)點(diǎn)6、節(jié)點(diǎn)9）的參考時隙偏差Δt53(n)、Δt56和Δt59(n)，從而計(jì)算出自己的時隙調(diào)整量：

式中ω55+ω53+ω56+ω59=1，然后計(jì)算出參考的時隙基準(zhǔn)：

即可根據(jù)和鄰居節(jié)點(diǎn)的時隙偏差，選擇合適的時隙修正量使全網(wǎng)時間同步。為了理論分析，可以認(rèn)為時間基準(zhǔn)偏差εi是該節(jié)點(diǎn)i與全網(wǎng)所有節(jié)點(diǎn)時隙偏差的加權(quán)平均值，不連通節(jié)點(diǎn)的權(quán)值為0，即εi(n)=∑Nk=1ωkΔtik(n)，式中N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。一種可行的權(quán)值選擇方法是采用鄰居節(jié)點(diǎn)的算術(shù)平均法，把相鄰的節(jié)點(diǎn)的時隙偏差算術(shù)平均后作為時隙的修正量。對此算法的收斂性的仿真分析得出，隨著節(jié)點(diǎn)覆蓋半徑的提高，每個節(jié)點(diǎn)的連通度增大，網(wǎng)絡(luò)的最大跳數(shù)變少，因而收斂速度提高。算法平均迭代38次可以達(dá)到最大時隙偏差收斂到10-6以下。5總結(jié)及展望

本文從時間同步的概念出發(fā)，首先簡要介紹了幾種典型的時間同步算法及分析了他們的優(yōu)缺點(diǎn)，并對它們的時間同步算法的性能進(jìn)行了綜合比較，然后還介紹了與傳統(tǒng)基于時間信息交換的時間同步算法不同的兩種新技術(shù)：螢火蟲同步技術(shù)和協(xié)作同步技術(shù)。雖然目前對于無線傳感器網(wǎng)絡(luò)時間同步算法的研究已經(jīng)取得了如此大的進(jìn)展，但是基于無線傳感器網(wǎng)絡(luò)的不同的應(yīng)用特征，還可以在以下幾個方面作進(jìn)一步的研究和發(fā)展：

①大規(guī)模無限傳感節(jié)點(diǎn)的時間同步研究?，F(xiàn)有的大部分時間同步算法都是在實(shí)驗(yàn)室平臺，是基于幾個或小規(guī)模的單跳網(wǎng)絡(luò)節(jié)點(diǎn)的仿真和研究。而現(xiàn)實(shí)中，隨著傳感器節(jié)點(diǎn)的低成本、微型化，及實(shí)際中的應(yīng)用，大規(guī)模的多跳的無線自組網(wǎng)的傳感器網(wǎng)絡(luò)的研究將是今后研究的方向之一。

②魯棒性和容錯性的研究?，F(xiàn)有的時間同步算法基本上都是在實(shí)驗(yàn)室或較簡單的室外環(huán)境下實(shí)現(xiàn)的，和實(shí)際的不可預(yù)測的、惡劣的真實(shí)環(huán)境相比，存在更多的干擾因素，因此時間同步算法在現(xiàn)實(shí)中的魯棒性和容錯性的研究也將是今后的研究方向之一。

③可拓展性的研究。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的生產(chǎn)商很多，網(wǎng)絡(luò)中一般會包含大量的不同類型的移動傳感器節(jié)點(diǎn)，時間同步算法要相互兼容就需要很好的可拓展性，因此時間同步算法的可拓展性也值得進(jìn)一步研究。

無線傳感器網(wǎng)絡(luò)是與實(shí)際應(yīng)用相關(guān)的，不同的應(yīng)用需要不同的時間同步精度和能耗要求，因此對時間同步的需求也是多種多樣的，應(yīng)該結(jié)合特定的實(shí)際應(yīng)用來研究和開發(fā)時間同步算法。參考文獻(xiàn)

[1]DavidLMills.RFC1305NetworkTimeProtocol(Version3)Specification.Implementation,1992.

[2]JElson,LGirod,DEstrin.FineGrainedNetworkTimeSynchronizationusingReferenceBroadcasts[C]//Pro.5thSymp.Op.Sys.DesignandImplementation.Boston,MA,2002.

[3]SGaneriwal,RKumar,MBSrivastava.TimingsyncProtocolforSensorNetworks[C]//Proceedingsofthe1stInternationalConferenceEmbeddedNetworkedSensorSystems(SenSyss03).USA:ACMpress,2003.

[4]WeilianSu,IanFAkyildiz.TimeDiffusionSynchronizationProtocolforWirelessSensorNetworks[J].IEEE/ACMTransactionsonnetworking,2005,13(2).

[5]MMaroti,BKusy,GSimon,etal.Thefloodingtimesynchronizationprotocol[C]//Proceedingsofthe2ndInternationalConferenceonEmbeddedNetworkedSensorSystems(SenSys’04),USA,November，2004.

[6]

IntelResearch.Delaymeasurementtimesynchronizationforwirelesssensornetworks,2003.

[7]

JVGreunen,JRabaey.Lightweighttimesynchronizationforsensornetworks[C]//The2ndACMIntlWorkshoponWirelessSensorNetworksandApplications,SanDiego,2003.

[8]

SichitiuML,VeerarittiphanC.Simple,accuratetimesynchronizationforwirelesssensornetworks[J].IEEETrans.onwirelesscommunicationandnetworking,2003(3).

[9]HDai,RHan.TSync:ALightweightBidirectionalTimeSynchronizationServiceforWirelessSensorNetworks[C]//ACMSIGMOBILEMobileComputingandCommunicationsReview,SpecialIssueonWirelessPAN&SensorNetworks,UniversityofColorado,Janu