無線傳感器網絡同步算法的研究與探討

摘要：時間同步是無線傳感器網絡進行數據融合、TDMA調度、定位等基本應用的基礎。從時間同步的概念和定義出發(fā)，首先對幾種經典的常用的時間同步算法及新型的螢火蟲同步和梯度同步算法進行了介紹，然后主要分析分布式的時隙互同步算法，最后展望了未來時間同步算法的研究方向。
關鍵詞：無線傳感器網絡；梯度同步；分布式時隙同步算法

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

1 概念與定義
    在計算機體系結構中，時鐘通常用品體振蕩器脈沖來度量，即
   
    式中C(t)為構造的本地時鐘，t為真實時間變量，k為依賴于晶振的物理特性常量，ω(τ)為晶振的頻率，間隔c(t)-c(t0)被用來作為度量時間。對于理想的時鐘，有r(t)=dc(t)／dt=1，也就是說，理想時鐘的變化速率r(t)為1。但在工程實踐中，因為溫度、壓力、電源電壓等外界環(huán)境的變化，往往會導致晶振頻率產生波動。因此構造理想時鐘比較困難，但在一般情況下晶振頻率的波動幅度并非任意的，而是局限在一定范圍之內。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。
    假定c(t)是一個理想的時鐘。如果在t時刻有c(t)=ci(t)，則稱ci(t)在t時刻是準確的；如果dc(t)／dt=dci(t)／dt。則稱時鐘ci(t)在t時刻是精確的；如果ci(t)=ck(t)，則稱時鐘ci(t)在t時刻與時鐘ck(t)是同步的。上述定義表明，兩個同步時鐘不一定是準確或精確的，時間同步與時間的準確性和精度沒有必然的聯系。
    如果采用時鐘速率恒定模型，由式(1)，時鐘ci(t)可以簡化表示為：
    ci(t)=ai·t+bi     (2)
    由此可知，時鐘ci(t)和ck(t)之間應該存在如下的線性關系：
    ci(t)=aik·ck(t)+bik     (3)
    式中aik、bik為相對漂移量和相對偏移量。

2 典型同步算法
    Elson、Girod和Estrin在參考文獻中以“第三節(jié)點”實現同步的思想提出了RBS算法，這是一種基于接收者一接收者的時間同步協議。根節(jié)點周期性地向其廣播域中的子節(jié)點發(fā)送不包含時間戳的參照廣播(Referenccs Broadcast)消息。接收到廣播消息后，鄰居子節(jié)點用自已
的本地時鐘記錄各自的接收時刻作為參考比對時鐘，然后相互交換它們記錄的時間信息，這樣接收節(jié)點就能知道彼此之間的時鐘偏移量。然后利用式(4)計算相對其他各個節(jié)點的時鐘偏移的平均值，并相應進行調整。當所有節(jié)點都獲得相對其他節(jié)點的時鐘偏移量平均值時，所有接收同一參照廣播消息的接收節(jié)點便獲得了一個相對網絡時間，即：
   
    式中：n為待同步節(jié)點數，m為參考廣播的次數，Ti,k為第i個節(jié)點接收第k次參考廣播的本地時刻。顯然，由offset(i，j)形成的矩陣為對稱矩陣，且對角線元素為0。
    TPSN算法是由Ganeriwal等人提出的，是一種基于發(fā)送者和接收者的時間同步算法。采用層次型網絡結構。算法分兩步：首先是層次發(fā)現階段，建立網絡拓撲結構；然后每個節(jié)點與上一級的一個節(jié)點進行時間同步，最終實現所有節(jié)點都與根節(jié)點的時間同步。
    FTSP協議是一種單向廣播的發(fā)送者和接收者的時間同步辦議。協議首先要網絡動態(tài)地選擇一個節(jié)點作為網絡的根節(jié)點，其時間作為全網的參考時間，根節(jié)點把含有當前本地時間的信息包發(fā)送給它單跳廣播域內的鄰居節(jié)點；鄰居節(jié)點在收到信息后分別記錄相應的接收時間，采用參數擬合技術算出相對于根節(jié)點的時間漂移和時間偏移；然后這些與根節(jié)點同步了的鄰居節(jié)點也作為參考節(jié)點，采用與根節(jié)點同步的相同的辦法，使它們的鄰居節(jié)點也實現與其同步。
    無線傳感器網絡的最常見的幾種同步算法的性能比較如表1所列。

3 螢火蟲同步算法和梯度同步算法
    前面的時間同步技術都是基于時間信息交換的同步技術，然而在大規(guī)模的無線傳感器網絡中，存在同步誤差會隨著跳距而積累的問題和可拓展性需求等問題。螢火蟲同步技術和協作同步技術是為了實現節(jié)點的同步性，即使節(jié)點的某些周期性動作具有相同的周期和相位，例如使一群螢火蟲同步閃爍并且閃爍周期相同。1990年，Mirollo和Strogatz在Peskin模型的基礎上提出了更一般的脈沖耦合振蕩器模型(后簡稱為M＆S模型)。在此模型中，振蕩器使用狀態(tài)變量x來描述，x的變化服從函數f(φ)，其中f是一個[0，1]到[0，1]的光滑單淵遞增上凸函數，φ是相位變量且滿足(T是同步周期)。Mirollo和Strogatz從理論上證明了在M＆S模型下，多個耦合振蕩器系統(tǒng)在幾乎所有的初始情況下都能夠達到同步，并在無線多跳網絡測試床Gains上實現了M＆S模型的螢火蟲同步算法。
    麻省理工學院的Rui Fan、Nancy Lynch兩位作者第一次提出了GCS梯度同步算法。在移動自組織網絡中往往是鄰居節(jié)點聯系比較密切，而相距較遠的節(jié)點很少交換消息，因此相距較遠的節(jié)點可以允許較大誤差。如數據融合中，具有相同父節(jié)點的子節(jié)點需要精確的同步，但是較遠的節(jié)點不是同一個父節(jié)點，可以允許誤差大一些。作者就是根據這一特征提出了梯度同步算法。在通常的時間同步算法的基礎上，假設兩任意節(jié)點i、j，f(dij)為節(jié)點i和節(jié)點j之間的最大時鐘差，時鐘記為。信息從節(jié)點i傳到j的傳播時間為0到dij，dij為節(jié)點i到節(jié)點j的距離。D=maxijdij為網絡的直徑。GCS提出了兩要求：
   
    計算出時鐘漂移的最低邊界滿足f(D)=Ω(d+lgD／lg lgD)，這也就是說節(jié)點之間的時鐘漂移不只與兩個節(jié)點問的距離有關，還與整個網絡的規(guī)模有關，越近的節(jié)點同步效果越好，反之越差。GTSP(Gradient Time Synchronization Protocol)協議中，每個節(jié)點通過接收鄰居節(jié)點的時間來修正自己的時鐘，整個網絡無需建立一個拓撲樹結構，也無需參考節(jié)點，主要是實現直接的鄰居節(jié)點間直接的高精度的同步，同時考慮時間漂移和偏移補償，漂移補償采用式(5)。通過這種補償機制，所有節(jié)點的邏輯漂移將趨近值Xss；時鐘偏移補償采用式(6)。協議的作者在Mica2節(jié)點上進行了仿真，通過20個節(jié)點實驗，采用Mac層時間戳技術，得出鄰居節(jié)點之間的平均同步精度達到4．0μs，整個網絡的平均同步精度達到14．0μs。
   

4 分布式時隙同步算法
    主從同步方法是網絡中所有的節(jié)點與參考節(jié)點保持時間同步，對參考節(jié)點依賴性高，且同步的誤差隨著跳數而累積；分布式同步則利用網絡中所有節(jié)點的彼此時間信息進行調整，不依賴任何特殊的節(jié)點，且不會有誤差的累積，因此更加適合于大型的多跳自組織的無線傳感器網絡。分布式時隙同步算法利用了網絡中鄰居節(jié)點的時隙偏差值來計算時隙的調整量，實驗證明該算法收斂速度快，平均每個節(jié)點的計算量小，非常適合于移動自組網的無線傳感器網絡終端節(jié)點的運行。采用固定的時隙調整時，根據節(jié)點間時隙基準是超前還是滯后來調整時隙基準。基于分布式一致的無線傳感器網絡的時間同步協議的收斂和加速問題研究中，將分布式一致的收斂和加速問題映射到馬爾科夫鏈的狀態(tài)轉移過程，但是排除了連通度對收斂速度的影響，得出收斂速度與節(jié)點鄰居數和網絡規(guī)模有關的結論，并通過100個節(jié)點組網實驗得出了可以降低25％的迭代數的結論。
    假設網內任意節(jié)點i，對應其所有的鄰居節(jié)點的時隙差值為△tij，可以算出所有鄰居節(jié)點的時隙偏差值的加權平均值為εi，時隙修正量ωij。節(jié)點互同步過程如圖1所示，假設節(jié)點5能感知其鄰居節(jié)點(節(jié)點3、節(jié)點6、節(jié)點9)的參考時隙偏差△t53(n)、△t56和△t59(n)，從而計算出自己的時隙調整量：
    ε5=ω55×0+ω53△t53(n)+ω56△t56(n)+ω59△t59(n)     (7)
    式中ω55+ω53+ω56+ω59=1，然后計算出參考的時隙基準：
    t5(n+1)=t5(n)-ε5(n)      (8)

    即可根據和鄰居節(jié)點的時隙偏差，選擇合適的時隙修正量使全網時間同步。為了理論分析，可以認為時間基準偏差εi是該節(jié)點i與全網所有節(jié)點時隙偏差的加權平均值，不連通節(jié)點的權值為0，即，式中N為網絡的節(jié)點數。一種可行的權值選擇方法是采用鄰居節(jié)點的算術平均法，把相鄰的節(jié)點的時隙偏差算術平均后作為時隙的修正量。對此算法的收斂性的仿真分析得出，隨著節(jié)點覆蓋半徑的提高，每個節(jié)點的連通度增大，網絡的最大跳數變少，因而收斂速度提高。算法平均迭代38次可以達到最大時隙偏差收斂到10-5以下。

5 總結及展望
    本文從時間同步的概念出發(fā)，首先簡要介紹了幾種典型的時間同步算法及分析了他們的優(yōu)缺點，并對它們的時間同步算法的性能進行了綜合比較，然后還介紹了與傳統(tǒng)基于時間信息交換的時間同步算法不同的兩種新技術：螢火蟲同步技術和協作同步技術。雖然目前對于無線傳感器網絡時間同步算法的研究已經取得了如此大的進展，但是基于無線傳感器網絡的不同的應用特征，還可以在以下幾個方面作進一步的研究和發(fā)展：
    ①大規(guī)模無限傳感節(jié)點的時間同步研究?，F有的大部分時間同步算法都是在實驗室平臺，是基于幾個或小規(guī)模的單跳網絡節(jié)點的仿真和研究。而現實中，隨著傳感器節(jié)點的低成本、微型化，及實際中的應用，大規(guī)模的多跳的無線自組網的傳感器網絡的研究將是今后研究的方向之一。
    ②魯棒性和容錯性的研究?，F有的時間同步算法基本上都是在實驗室或較簡單的室外環(huán)境下實現的，和實際的不可預測的、惡劣的真實環(huán)境相比，存在更多的干擾因素，因此時間同步算法在現實中的魯棒性和容錯性的研究也將是今后的研究方向之一。
    ③可拓展性的研究。無線傳感器網絡節(jié)點的生產商很多，網絡中一般會包含大量的不同類型的移動傳感器節(jié)點，時間同步算法要相互兼容就需要很好的可拓展性，因此時間同步算法的可拓展性也值得進一步研究。
無線傳感器網絡是與實際應用相關的，不同的應用需要不同的時間同步精度和能耗要求，因此對時間同步的需求也是多種多樣的，應該結合特定的實際應用來研究和開發(fā)時間同步算法。