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

2、 (network time protocol)是傳統網絡的時間 同步協議,最早由美國delaware大學的mill教授提出。然而ntp是應傳統網絡的能量效率、網絡動態、 基礎設施和系統而構建，因此并不適合低功耗、低成本、微型化、高集成、協作式多跳自組織的無線傳感 器網絡。另外，無線傳感器網絡時間同步算法還要考慮能量消耗、可拓展性、桔確度、魯棒性等問題，這 些都對無線傳感器網絡的時間同步算法提出了新的要求和挑戰。在2002年的hotnets上，j elson和kay romer首次提出并闡述了無線傳感器網絡時間同步技術的課 題，在國際上引發了廣泛的關注和思考，吸引了許多人學和研究機構參與研究，

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

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

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

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

7、ganeriwal等人提出的，是一種基于發送者和接收者的時間同步算法。采用層次型網絡 結構。算法分兩步：首先是層次發現階段，建立網絡拓撲結構；然后每個節點與上一級的一個節點進行時 間同步，最終實現所有節點都與根節點的時間同步。ftsp協議是一種單向廣播的發送者和接收者的時間同步協議。協議首先要網絡動態地選擇-個節點作 為網絡的根節點，其時間作為全網的參考時間，根節點把含冇當前木地時間的信息包發送給它單跳廣播域 內的鄰居節點；鄰居節點在收到信息后分別記錄相應的接收時間，采用參數擬介技術算出相對于根節點的 時間漂移和時間偏移；然后這些與根節點同步了的鄰屈節點也作為參考節點，采用與根節點同步的相同的

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

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

10、在m&s模型下，多個耦介振蕩器系統在幾乎所冇的初始情況下都能夠達到同步，并在無線 多跳網絡測試床gains ±實現了 m&s模型的螢火蟲同步算法。麻省理工學院的rui fan. nancy lynch兩位作者笫一次提出了 gcs梯度同步算法。在移動自組織網絡 中往往是鄰居節點聯系比較密切，而相距較遠的節點很少交換消息，因此相距較遠的節點可以允許較大謀 差。如數據融合中，具有相同父節點的子節點需要精確的同步，但是較遠的節點不是同一個父節點，可以 允許謀差人一些。作者就是根據這一特征提出了梯度同步算法。在通常的時間同步算法的基礎上，假設兩 任意節點i、j, f(dij)為

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

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

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

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

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

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

17、隨著傳感器節點的低成本、微型化，及實際中的應用， 人規模的多跳的無線向組網的傳感器網絡的研究將是今后研究的方向z_。 魯棒性和容錯性的研究。現冇的時間同步算法基木上都是在實驗室或較簡單的室外環境下實現的, 和實際的不可預測的、惡劣的真實環境相比，存在更多的干擾因素，因此時間同步算法在現實中的魯棒性 和容錯性的研究也將是今后的研究方向之一。 可拓展性的研究。無線傳感器網絡節點的生產商很多，網絡中一般會包含大量的不同類型的移動傳 感器節點，時間同步算法要相互兼容就需要很好的可拓展性，因此時間同步算法的可拓展性也值得進一步 研究。無線傳感器網絡是打實際應川相關的，不同的應川需耍不同的時間同步粘度和能

18、耗耍求，因此對時間 同步的需求也是多種多樣的，應該結介特定的實際應用來研究和開發時間同步算法。編者注：本文為期刊縮略版，全文見本刊網站vmv mesnet. com.空。參考文獻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