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

1、摘要：時(shí)間同步是無線傳感器網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)融介、tdma調(diào)度、定位等基本應(yīng)用的基礎(chǔ)。從時(shí)間同步的 概念和定義出發(fā)，首先對(duì)兒種經(jīng)腆的常川的時(shí)間同步算法及新型的螢火蟲同步和梯度同步算法進(jìn)行了介紹, 然后主耍分析分布式的時(shí)隙互同步算法，最后展里了未來時(shí)間同步算法的研究方向。引言無線傳感器網(wǎng)絡(luò)技術(shù)融合了傳感器、低功耗嵌入式計(jì)算器、無線網(wǎng)絡(luò)和通信、分布式信息處理等技術(shù)， 利用傳感節(jié)點(diǎn)通過自組網(wǎng)絡(luò)對(duì)監(jiān)測(cè)對(duì)象進(jìn)行實(shí)時(shí)監(jiān)測(cè)、感知和采集，在環(huán)境、資源、智能交通、礦井安全 等領(lǐng)域都有著良好的應(yīng)用前景,是近年來國(guó)內(nèi)外信息領(lǐng)域研究和競(jìng)爭(zhēng)的焦點(diǎn)。而時(shí)間同步技術(shù)是無線傳感 器網(wǎng)絡(luò)中一項(xiàng)非常關(guān)鍵的基礎(chǔ)技術(shù)。網(wǎng)絡(luò)時(shí)間協(xié)議ntp1

2、 (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ǎng)絡(luò)。另外，無線傳感器網(wǎng)絡(luò)時(shí)間同步算法還要考慮能量消耗、可拓展性、桔確度、魯棒性等問題，這 些都對(duì)無線傳感器網(wǎng)絡(luò)的時(shí)間同步算法提出了新的要求和挑戰(zhàn)。在2002年的hotnets上，j elson和kay romer首次提出并闡述了無線傳感器網(wǎng)絡(luò)時(shí)間同步技術(shù)的課 題，在國(guó)際上引發(fā)了廣泛的關(guān)注和思考，吸引了許多人學(xué)和研究機(jī)構(gòu)參與研究，

3、已經(jīng)提出許多種不同的實(shí) 現(xiàn)算法及改進(jìn)算法,典型的有rbs算法、tpsn算法、還有tdp4算法、ftsp算法、dmts|：6算法、 lts7算法、ts/mse8算法、1irts9算法、ofdc10算法、chts111算法、crit12算法以及最新的基于 螢火蟲技術(shù)和協(xié)作技術(shù)的時(shí)間同步算法等。1概念與定義在計(jì)算機(jī)體系結(jié)構(gòu)中，時(shí)鐘通常川晶體振蕩器脈沖來度量，即*1c(t) = k co(r)dr + c(tn)(1)j b式中c(t)為構(gòu)造的本地時(shí)鐘，t為其實(shí)時(shí)間變暈，k為依賴于晶振的物理特性常屋，3 ( t )為品振的 頻率，間隔c(t)-c(t0)被川來作為度量時(shí)間。對(duì)于理想的時(shí)鐘，r(t)=d

4、c(t)/dt=l,也就是說，理想時(shí) 鐘的變化速率:r(t)為1。但在工程實(shí)踐中，因?yàn)闇囟?、壓力、電源電壓等外界環(huán)境的變化，往往會(huì)導(dǎo)致晶 振頻率產(chǎn)生波動(dòng)。因此構(gòu)造理想時(shí)鐘比較閑難，但在一般情況下晶振頻率的波動(dòng)幅度并非任意的，而是局 限在一定范圍z內(nèi)。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。假定c(t)是一個(gè)理想的時(shí)鐘。如果在t時(shí)刻有c(t)=ci(t),則稱ci(t)在t時(shí)刻是準(zhǔn)確的;如果 de (t)/dt=dci (t)/dt,則稱時(shí)鐘ci (t)在t時(shí)刻是精確的;如果ci (t)=ck(t),則稱時(shí)鐘ci (t)在t時(shí)刻與 時(shí)鐘ck(t)是同步的。上述定義

5、表明，兩個(gè)同步時(shí)鐘不一定是準(zhǔn)確或精確的，時(shí)間同步與時(shí)間的準(zhǔn)確性和 精度沒冇必然的聯(lián)系。如果采用時(shí)鐘速率恒定模型,由式(1),時(shí)鐘ci(t)可以簡(jiǎn)化表示為:c.(t) = a. t 4- h.(2)由此可知，時(shí)鐘ci (t)和ck(t)之間應(yīng)該存在如下的線性關(guān)系:cj(t) = aik ck(t) + bik(3)式中aik、bik為相對(duì)漂移最和相對(duì)偏移最。2典型同步算法elson、girod和eslrin在參考文獻(xiàn)2中以“笫三節(jié)點(diǎn)”實(shí)現(xiàn)同步的思想提出了 rbs算法，這是-種 基于接收者接收者的時(shí)間同步協(xié)議。根節(jié)點(diǎn)周期性地向其廣播域中的子節(jié)點(diǎn)發(fā)送不包含時(shí)間戳的參照廣播 (references b

6、roadcast )消息。接收到廣播消息后,鄰居子節(jié)點(diǎn)用自己的本地時(shí)鐘記錄各自的接收時(shí)亥!) 作為參考比對(duì)時(shí)鐘，然后相互交換它們記錄的時(shí)間信息，這樣接收節(jié)點(diǎn)就能知道彼此z間的時(shí)鐘偏移量。 然后利用式(4)計(jì)算和對(duì)其他各個(gè)節(jié)點(diǎn)的時(shí)鐘偏移的平均值，并相應(yīng)進(jìn)行調(diào)整。當(dāng)所有節(jié)點(diǎn)都獲得札i對(duì)其 他節(jié)點(diǎn)的時(shí)鐘偏移量平均值時(shí)，所有接收同一參照廣播消息的接收節(jié)點(diǎn)便獲得了一個(gè)相對(duì)網(wǎng)絡(luò)時(shí)間，即：v i n*j e=丄 t“k)(4)式中：n為待同步節(jié)點(diǎn)數(shù)，m為參考廣播的次數(shù)，ti, k為第i個(gè)節(jié)點(diǎn)接收第k次參考廣播的本地時(shí)刻。 顯然，山offset(i,j)形成的矩陣為對(duì)稱矩陣，且對(duì)角線元素為0。tpsn算法是山

7、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é)議。協(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)同步的相同的

8、 辦法，使它們的鄰居節(jié)點(diǎn)也實(shí)現(xiàn)與其同步。無線傳感器網(wǎng)絡(luò)的最常見的兒種同步算法的性能比較如表1所列。名稱rbstpsnftspmini-sync./tiny-sy nclts測(cè)試平臺(tái)micamicamicaad hoc(802. 1lb>()mn】<?+ +分級(jí)結(jié)構(gòu)否是是是是冋步方式捲收-接收發(fā)送接收發(fā)送-接收發(fā)送-接收發(fā)送-搖收同步謀差29. 1316.91.4fft確度*能耗*變雜度k x4c應(yīng)用范圍*有效范圍*注：*表示算法在某個(gè)方面的件能.趣筍表示并法的性施越好。表1幾利嗓用時(shí)間同步算法的性能比較3螢火蟲同步算法和梯度同步算法前面的時(shí)間同步技術(shù)都是基于時(shí)間倍息交換的同步技術(shù)，

9、然而在大規(guī)模的無線傳感器網(wǎng)絡(luò)中，存在同 步誤差會(huì)隨著跳距而積累的問題和叮拓展性需求等問題。螢火蟲同步技術(shù)和協(xié)作同步技術(shù)是為了實(shí)現(xiàn)節(jié)點(diǎn) 的同步性，即使節(jié)點(diǎn)的某些周期性動(dòng)作具冇相同的周期和相位，例如使一群螢火蟲同步閃爍并h閃爍周期 相同。1990年，mirollo和strogatz在peskin模型的基礎(chǔ)上提出了更一般的脈沖耦合振蕩器模型(后簡(jiǎn) 稱為h&s模型)。在此模型中，振蕩器使用狀態(tài)變量x來描述，x的變化服從函數(shù)f ( e),其中f是一個(gè)0, 1 到0, 1的光滑單調(diào)遞增上凸函數(shù),4)是相位變量且滿足dd)dt=l/t(t是同步周期)。mirollo和strogatz 從理論上證明了

10、在m&s模型下，多個(gè)耦介振蕩器系統(tǒng)在幾乎所冇的初始情況下都能夠達(dá)到同步，并在無線 多跳網(wǎng)絡(luò)測(cè)試床gains ±實(shí)現(xiàn)了 m&s模型的螢火蟲同步算法。麻省理工學(xué)院的rui fan. nancy lynch兩位作者笫一次提出了 gcs梯度同步算法。在移動(dòng)自組織網(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)不是同一個(gè)父節(jié)點(diǎn)，可以 允許謀差人一些。作者就是根據(jù)這一特征提出了梯度同步算法。在通常的時(shí)間同步算法的基礎(chǔ)上，假設(shè)兩 任意節(jié)點(diǎn)i、j, f(dij)為

11、節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的最大時(shí)鐘差，時(shí)鐘記為lai (t)。信息從節(jié)點(diǎn)i傳到j(luò)的傳 播時(shí)間為0到dij, dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。d-maxijdij,為網(wǎng)絡(luò)的直徑。gcs提出了兩要求:(d vi v t v r>0,y<l：(t + r)-l；(t)tee vtvivj. l：(t)-i>；(i)kf(dlt)計(jì)算出時(shí)鐘漂移的最低邊界滿足f(d)-q (d+lgd/lg lgd),這也就是說節(jié)點(diǎn)之間的時(shí)鐘漂移不只與兩 個(gè)節(jié)點(diǎn)間的距離有關(guān)，還與整個(gè)網(wǎng)絡(luò)的規(guī)模有關(guān)，越近的節(jié)點(diǎn)同步效果越好，反之越差ogtsp(gradicnt time synchronization prot

12、ocol )協(xié)議中,每個(gè)節(jié)點(diǎn)通過接收鄰居節(jié)點(diǎn)的時(shí)間來修正自己的時(shí)鐘,整個(gè)網(wǎng)絡(luò)無 需建立一個(gè)拓?fù)錁浣Y(jié)構(gòu)，也無需參考節(jié)點(diǎn),主要是實(shí)現(xiàn)直接的鄰居節(jié)點(diǎn)間直接的高精度的同步，同時(shí)考慮 時(shí)間漂移和偏移補(bǔ)償，漂移補(bǔ)償采用式(5)。通過這種補(bǔ)償機(jī)制，所有節(jié)點(diǎn)的邏輯漂移將趨近值xss；時(shí) 鐘偏移補(bǔ)償采用式(6)。協(xié)議的作者在mica2節(jié)點(diǎn)上進(jìn)行了仿真，通過20個(gè)節(jié)點(diǎn)實(shí)驗(yàn)，采用mac層時(shí)間 戳技術(shù)，得出鄰居節(jié)點(diǎn)之間的平均同步精度達(dá)到4.0 us,整個(gè)網(wǎng)絡(luò)的平均同步耕度達(dá)到14.0 uso(£xj(g)+xmk) (工 li(tk)+l,(ih)0心屮)=0mj+ (6)4分布式吋隙同步算法主從同步方法是

13、網(wǎng)絡(luò)中所有的節(jié)點(diǎn)與參考節(jié)點(diǎn)保持時(shí)間同步，對(duì)參考節(jié)點(diǎn)依賴性高，且同步的誤差隨 著跳數(shù)而累積；分布式同步則利用網(wǎng)絡(luò)屮所有節(jié)點(diǎn)的彼此時(shí)間信息進(jìn)行調(diào)整，不依賴任何特殊的節(jié)點(diǎn)，且 不會(huì)冇誤差的累積，因此更加適合于大型的多跳h組織的無線傳感器網(wǎng)絡(luò)。分布式時(shí)隙同步算法利用了網(wǎng) 絡(luò)小鄰居節(jié)點(diǎn)的時(shí)隙偏旁值來計(jì)算時(shí)隙的調(diào)整量，實(shí)驗(yàn)證明該算法收斂速度快，平均每個(gè)節(jié)點(diǎn)的計(jì)算屋小， 非常適合于移動(dòng)口組網(wǎng)的無線傳感器網(wǎng)絡(luò)終端節(jié)點(diǎn)的運(yùn)行。采用網(wǎng)定的時(shí)隙調(diào)整時(shí)，根據(jù)節(jié)點(diǎn)間時(shí)隙皋準(zhǔn) 是超前還是滯后來調(diào)整時(shí)隙基準(zhǔn)?；?分布式一致的無線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議的收斂和加速問題研 究屮，將分布式一致的收斂和加速問題映射到馬爾科夫鏈

14、的狀態(tài)轉(zhuǎn)移過程，但是排除了連通度對(duì)收斂速度 的影響，得出收斂速度與節(jié)點(diǎn)鄰屈數(shù)和網(wǎng)絡(luò)規(guī)模有關(guān)的結(jié)論，并通過100個(gè)節(jié)點(diǎn)組網(wǎng)實(shí)驗(yàn)得出了可以降低 25%的迭代數(shù)的結(jié)論。假設(shè)網(wǎng)內(nèi)任意節(jié)點(diǎn)i,對(duì)應(yīng)其所有的鄰居節(jié)點(diǎn)的時(shí)隙差值為atij,可以算出所有鄰居節(jié)點(diǎn)的時(shí)隙偏差 值的加權(quán)平均值為£ i,時(shí)隙修正量3ij。節(jié)點(diǎn)互同步過程如圖1所示，假設(shè)節(jié)點(diǎn)5能感知其鄰居節(jié)點(diǎn)(節(jié) 點(diǎn)3、節(jié)點(diǎn)6、節(jié)點(diǎn)9)的參考時(shí)隙偏差at53(n). a 156和at59(n),從而計(jì)算出自己的時(shí)隙調(diào)整量:= x 0 + tns3 at53(n) + cijjg (n) + 弭仁9(n) (7)式中3 55+ 3 53+ 3 5

15、6+ 3 59=1,然后計(jì)算出參考的時(shí)隙基準(zhǔn):(8)t5 ( n + 1 ) = t5 ( n) ( n)即可根據(jù)和鄰居節(jié)點(diǎn)的時(shí)隙偏差，選擇合適的時(shí)隙修正量使全網(wǎng)時(shí)間同步。為了理論分析，可以認(rèn)為 時(shí)間基準(zhǔn)偏差£ i是該節(jié)點(diǎn)i與全網(wǎng)所有節(jié)點(diǎn)時(shí)隙偏差的加權(quán)平均值，不連通節(jié)點(diǎn)的權(quán)值為0,即£ i(n)二 enk=13katik(n),式屮n為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)。-種可行的權(quán)值選擇方法是采用鄰居節(jié)點(diǎn)的算術(shù)平均法，把 相鄰的節(jié)點(diǎn)的時(shí)隙偏差算術(shù)平均后作為時(shí)隙的修正量。對(duì)此算法的收斂性的仿真分析得出，隨著節(jié)點(diǎn)覆蓋 半徑的提高，每個(gè)節(jié)點(diǎn)的連通度增大，網(wǎng)絡(luò)的最大跳數(shù)變少，因而收斂速度提高。算法平均

16、迭代38次可以 達(dá)到最大時(shí)隙偏差收斂到10-6以下。5總結(jié)及展望本文從吋間同步的概念出發(fā)，首先簡(jiǎn)耍介紹了兒種典型的時(shí)間同步算法及分析了他們的優(yōu)缺點(diǎn)，并對(duì) 它們的時(shí)間同步算法的性能進(jìn)行了綜合比較，然后還介紹了與傳統(tǒng)基于時(shí)間信息交換的時(shí)間同步算法不同 的兩種新技術(shù)：螢火蟲同步技術(shù)和協(xié)作同步技術(shù)。址然h前對(duì)于無線傳感器網(wǎng)絡(luò)時(shí)間同步算法的研究已經(jīng) 取得了如此人的進(jìn)展，但是基于無線傳感器網(wǎng)絡(luò)的不同的應(yīng)用特征，還可以在以下兒個(gè)方面作進(jìn)一步的研 究和發(fā)展：圖1節(jié)點(diǎn)互同步過程 大規(guī)模無限傳感節(jié)點(diǎn)的時(shí)間同步研究?，F(xiàn)有的大部分時(shí)間同步算法都是在實(shí)驗(yàn)室平臺(tái)，是基于兒個(gè) 或小規(guī)模的單跳網(wǎng)絡(luò)節(jié)點(diǎn)的仿其和研究。而現(xiàn)實(shí)中，

17、隨著傳感器節(jié)點(diǎn)的低成本、微型化，及實(shí)際中的應(yīng)用， 人規(guī)模的多跳的無線向組網(wǎng)的傳感器網(wǎng)絡(luò)的研究將是今后研究的方向z_。 魯棒性和容錯(cuò)性的研究。現(xiàn)冇的時(shí)間同步算法基木上都是在實(shí)驗(yàn)室或較簡(jiǎn)單的室外環(huán)境下實(shí)現(xiàn)的, 和實(shí)際的不可預(yù)測(cè)的、惡劣的真實(shí)環(huán)境相比，存在更多的干擾因素，因此時(shí)間同步算法在現(xiàn)實(shí)中的魯棒性 和容錯(cuò)性的研究也將是今后的研究方向之一。 可拓展性的研究。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的生產(chǎn)商很多，網(wǎng)絡(luò)中一般會(huì)包含大量的不同類型的移動(dòng)傳 感器節(jié)點(diǎn)，時(shí)間同步算法要相互兼容就需要很好的可拓展性，因此時(shí)間同步算法的可拓展性也值得進(jìn)一步 研究。無線傳感器網(wǎng)絡(luò)是打?qū)嶋H應(yīng)川相關(guān)的，不同的應(yīng)川需耍不同的時(shí)間同步粘度和能

18、耗耍求，因此對(duì)時(shí)間 同步的需求也是多種多樣的，應(yīng)該結(jié)介特定的實(shí)際應(yīng)用來研究和開發(fā)時(shí)間同步算法。編者注：本文為期刊縮略版，全文見本刊網(wǎng)站vmv mesnet. com.空。參考文獻(xiàn)1 david l milis. rfc 1305nctwork time protocol (version 3)specification. implementation, 19922 j elson, l girod, d estrin. finegrained network time synchronization using reference brotidcastsc/f3ro 5th symp. op.

19、 sys. design and implementation. boston, ma, 2002.3 s ganeriwal, r kumar, m b srivastava .timingsync protocol for sensornetworksc/proceedings of the 1st international conferenee embedded networked sensorsystems(sensys s03). usa:acm press, 2003.4 wcilian su, ian f akyildiztimcdiffusion synchronizatio

20、n protocol for wireless sensor networksj. ieee/acm transactions on networking, 2005, 13(2).5 m maroti, b kusy, g simon, et al the flooding time synchronization protocol c/proceedings of the 2nd in ter nali onal confere nee o n embedded netwo 廣 ked se nsor systems (se nsys'04), usa, november, 200

21、4.6 intel research delay measurement time synchronization for wireless sensor networks, 2003.7 j v greunen, j rabaey. lightweight time synchronization for sensor networksc/the 2ndacm int 1 workshop on wireless sensor networks and applications, san diego, 20038 sichitiu m l, vecrarittiphan c. simple,

22、 accurate time synchronization for wireless sensor networks j 1 eee trans on wireless cominu nication and network in g, 2003(3)9 ii dai, r ilan. tsync:a lightweight bidirectional time synchronization service for wireless sensor networksc/acm sigmobile mobi1e computing and communications review, specia