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

摘要：時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)融合、TDMA調(diào)度、定位等基本應(yīng)用的基礎(chǔ)。從時(shí)間同步的概念和定義出發(fā)，首先對(duì)幾種經(jīng)典的常用的時(shí)間同步算法及新型的螢火蟲(chóng)同步和梯度同步算法進(jìn)行了介紹，然后主要分析分布式的時(shí)隙互同步算法，最后展望了未來(lái)時(shí)間同步算法的研究方向。
關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；梯度同步；分布式時(shí)隙同步算法

引言
無(wú)線傳感器網(wǎng)絡(luò)技術(shù)融合了傳感器、低功耗嵌入式計(jì)算器、無(wú)線網(wǎng)絡(luò)和通信、分布式信息處理等技術(shù)，利用傳感節(jié)點(diǎn)通過(guò)自組網(wǎng)絡(luò)對(duì)監(jiān)測(cè)對(duì)象進(jìn)行實(shí)時(shí)監(jiān)測(cè)、感知和采集，在環(huán)境、資源、智能交通、礦井安全等領(lǐng)域都有著良好的應(yīng)用前景，是近年來(lái)國(guó)內(nèi)外信息領(lǐng)域研究和競(jìng)爭(zhēng)的焦點(diǎn)。而時(shí)間同步技術(shù)是無(wú)線傳感器網(wǎng)絡(luò)中一項(xiàng)非常關(guān)鍵的基礎(chǔ)技術(shù)。網(wǎng)絡(luò)時(shí)間協(xié)議NTP(Network Time Protocol)是傳統(tǒng)網(wǎng)絡(luò)的時(shí)間同步協(xié)議，最早由美國(guó)Delaware大學(xué)的Mill教授提出。然而NTP是應(yīng)傳統(tǒng)網(wǎng)絡(luò)的能量效率、網(wǎng)絡(luò)動(dòng)態(tài)、基礎(chǔ)設(shè)施和系統(tǒng)而構(gòu)建，因此并不適合低功耗、低成本、微型化、高集成、協(xié)作式多跳自組織的無(wú)線傳感器網(wǎng)絡(luò)。另外，無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步算法還要考慮能量消耗、可拓展性、精確度、魯棒性等問(wèn)題，這些都對(duì)無(wú)線傳感器網(wǎng)絡(luò)的時(shí)間同步算法提出了新的要求和挑戰(zhàn)。
在2002年的HotNets上，J Elson和Kay Romer首次提出并闡述了無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)的課題，在國(guó)際上引發(fā)了廣泛的關(guān)注和思考，吸引了許多大學(xué)和研究機(jī)構(gòu)參與研究，已經(jīng)提出許多種不同的實(shí)現(xiàn)算法及改進(jìn)算法，典型的有RBS算法、TPSN算法、還有TDP算法、FTSP算法、DMTS算法、LTS算法、TS／MS算法、HRTS算法、OFDC算法、CHTS算法、CRIT算法以及最新的基于螢火蟲(chóng)技術(shù)和協(xié)作技術(shù)的時(shí)間同步算法等。

1 概念與定義
在計(jì)算機(jī)體系結(jié)構(gòu)中，時(shí)鐘通常用品體振蕩器脈沖來(lái)度量，即

式中C(t)為構(gòu)造的本地時(shí)鐘，t為真實(shí)時(shí)間變量，k為依賴于晶振的物理特性常量，ω(τ)為晶振的頻率，間隔c(t)-c(t0)被用來(lái)作為度量時(shí)間。對(duì)于理想的時(shí)鐘，有r(t)=dc(t)／dt=1，也就是說(shuō)，理想時(shí)鐘的變化速率r(t)為1。但在工程實(shí)踐中，因?yàn)闇囟取毫?、電源電壓等外界環(huán)境的變化，往往會(huì)導(dǎo)致晶振頻率產(chǎn)生波動(dòng)。因此構(gòu)造理想時(shí)鐘比較困難，但在一般情況下晶振頻率的波動(dòng)幅度并非任意的，而是局限在一定范圍之內(nèi)。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。
假定c(t)是一個(gè)理想的時(shí)鐘。如果在t時(shí)刻有c(t)=ci(t)，則稱ci(t)在t時(shí)刻是準(zhǔn)確的；如果dc(t)／dt=dci(t)／dt。則稱時(shí)鐘ci(t)在t時(shí)刻是精確的；如果ci(t)=ck(t)，則稱時(shí)鐘ci(t)在t時(shí)刻與時(shí)鐘ck(t)是同步的。上述定義表明，兩個(gè)同步時(shí)鐘不一定是準(zhǔn)確或精確的，時(shí)間同步與時(shí)間的準(zhǔn)確性和精度沒(méi)有必然的聯(lián)系。
如果采用時(shí)鐘速率恒定模型，由式(1)，時(shí)鐘ci(t)可以簡(jiǎn)化表示為：
ci(t)=ai·t+bi (2)
由此可知，時(shí)鐘ci(t)和ck(t)之間應(yīng)該存在如下的線性關(guān)系：
ci(t)=aik·ck(t)+bik (3)
式中aik、bik為相對(duì)漂移量和相對(duì)偏移量。

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

式中：n為待同步節(jié)點(diǎn)數(shù)，m為參考廣播的次數(shù)，Ti,k為第i個(gè)節(jié)點(diǎn)接收第k次參考廣播的本地時(shí)刻。顯然，由offset(i，j)形成的矩陣為對(duì)稱矩陣，且對(duì)角線元素為0。
TPSN算法是由Ganeriwal等人提出的，是一種基于發(fā)送者和接收者的時(shí)間同步算法。采用層次型網(wǎng)絡(luò)結(jié)構(gòu)。算法分兩步：首先是層次發(fā)現(xiàn)階段，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；然后每個(gè)節(jié)點(diǎn)與上一級(jí)的一個(gè)節(jié)點(diǎn)進(jìn)行時(shí)間同步，最終實(shí)現(xiàn)所有節(jié)點(diǎn)都與根節(jié)點(diǎn)的時(shí)間同步。
FTSP協(xié)議是一種單向廣播的發(fā)送者和接收者的時(shí)間同步辦議。協(xié)議首先要網(wǎng)絡(luò)動(dòng)態(tài)地選擇一個(gè)節(jié)點(diǎn)作為網(wǎng)絡(luò)的根節(jié)點(diǎn)，其時(shí)間作為全網(wǎng)的參考時(shí)間，根節(jié)點(diǎn)把含有當(dāng)前本地時(shí)間的信息包發(fā)送給它單跳廣播域內(nèi)的鄰居節(jié)點(diǎn)；鄰居節(jié)點(diǎn)在收到信息后分別記錄相應(yīng)的接收時(shí)間，采用參數(shù)擬合技術(shù)算出相對(duì)于根節(jié)點(diǎn)的時(shí)間漂移和時(shí)間偏移；然后這些與根節(jié)點(diǎn)同步了的鄰居節(jié)點(diǎn)也作為參考節(jié)點(diǎn)，采用與根節(jié)點(diǎn)同步的相同的辦法，使它們的鄰居節(jié)點(diǎn)也實(shí)現(xiàn)與其同步。