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

徐雄偉，王平，徐世武，黃晞

（福建師范大學 物理與光電信息科技學院，福州 350007）

引 言

無線傳感器網絡技術融合了傳感器、低功耗嵌入式計算器、無線網絡和通信、分布式信息處理等技術，利用傳感節點通過自組網絡對監測對象進行實時監測、感知和采集，在環境、資源、智能交通、礦井安全等領域都有著良好的應用前景，是近年來國內外信息領域研究和競爭的焦點。而時間同步技術是無線傳感器網絡中一項非常關鍵的基礎技術。網絡時間協議 NTP［1］（Network Time Protocol）是傳統網絡的時間同步協議，最早由美國Delaware大學的Mill教授提出。然而NTP是應傳統網絡的能量效率、網絡動態、基礎設施和系統而構建，因此并不適合低功耗、低成本、微型化、高集成、協作式多跳自組織的無線傳感器網絡。另外，無線傳感器網絡時間同步算法還要考慮能量消耗、可拓展性、精確度、魯棒性等問題，這些都對無線傳感器網絡的時間同步算法提出了新的要求和挑戰。

在2002年的HotNets上，J Elson和Kay Romer首次提出并闡述了無線傳感器網絡時間同步技術的課題，在國際上引發了廣泛的關注和思考，吸引了許多大學和研究機構參與研究，已經提出許多種不同的實現算法及改進算法，典型的有RBS［2］算法、TPSN［3］算法、還有TDP［4］算法、FTSP［5］算法、DMTS［6］算法、LTS［7］算法、TS／MS［8］算法、HRTS［9］算法、OFDC［10］算法、CHTS［11］算法、CRIT［12］算法以及最新的基于螢火蟲技術和協作技術的時間同步算法等。

1 概念與定義

在計算機體系結構中，時鐘通常用晶體振蕩器脈沖來度量，即

式中C（t）為構造的本地時鐘，t為真實時間變量，k為依賴于晶振的物理特性常量，ω（τ）為晶振的頻率，間隔c（t）－c（t0）被用來作為度量時間。對于理想的時鐘，有r（t）＝dc（t）／dt＝1，也就是說，理想時鐘的變化速率r（t）為1。但在工程實踐中，因為溫度、壓力、電源電壓等外界環境的變化，往往會導致晶振頻率產生波動。因此構造理想時鐘比較困難，但在一般情況下晶振頻率的波動幅度并非任意的，而是局限在一定范圍之內。為了方便描述與分析，定義了速率恒定模型、漂移有界模型和漂移變化有界模型。

假定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）和ck（t）之間應該存在如下的線性關系：

式中aik、bik為相對漂移量和相對偏移量。

2 典型同步算法

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

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

TPSN算法是由Ganeriwal等人提出的，是一種基于發送者和接收者的時間同步算法。采用層次型網絡結構。算法分兩步：首先是層次發現階段，建立網絡拓撲結構；然后每個節點與上一級的一個節點進行時間同步，最終實現所有節點都與根節點的時間同步。

FTSP協議是一種單向廣播的發送者和接收者的時間同步協議。協議首先要網絡動態地選擇一個節點作為網絡的根節點，其時間作為全網的參考時間，根節點把含有當前本地時間的信息包發送給它單跳廣播域內的鄰居節點；鄰居節點在收到信息后分別記錄相應的接收時間，采用參數擬合技術算出相對于根節點的時間漂移和時間偏移；然后這些與根節點同步了的鄰居節點也作為參考節點，采用與根節點同步的相同的辦法，使它們的鄰居節點也實現與其同步。

無線傳感器網絡的最常見的幾種同步算法的性能比較如表1所列。

表1 幾種常用時間同步算法的性能比較

3 螢火蟲同步算法和梯度同步算法

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

麻省理工學院的Rui Fan、Nancy Lynch兩位作者第一次提出了GCS梯度同步算法。在移動自組織網絡中往往是鄰居節點聯系比較密切，而相距較遠的節點很少交換消息，因此相距較遠的節點可以允許較大誤差。如數據融合中，具有相同父節點的子節點需要精確的同步，但是較遠的節點不是同一個父節點，可以允許誤差大一些。作者就是根據這一特征提出了梯度同步算法。在通常的時間同步算法的基礎上，假設兩任意節點i、j，f（dij）為節點i和節點j之間的最大時鐘差，時鐘記為Lai（t）。信息從節點i

計算出時鐘漂移的最低邊界滿足f（D）＝Ω（d＋lgD／lg lgD），這也就是說節點之間的時鐘漂移不只與兩個節點間的距離有關，還與整個網絡的規模有關，越近的節點同步效果越好，反之越差。GTSP（Gradient Time Synchronization Protocol）協議中，每個節點通過接收鄰居節點的時間來修正自己的時鐘，整個網絡無需建立一個拓撲樹結構，也無需參考節點，主要是實現直接的鄰居節點間直接的高精度的同步，同時考慮時間漂移和偏移補償，漂移補償采用式（5）。通過這種補償機制，所有節點的邏輯漂移將趨近值Xss；時鐘偏移補償采用式（6）。協議的作者在Mica2節點上進行了仿真，通過20個節點實驗，采用Mac層時間戳技術，得出鄰居節點之間的平均同步精度達到4.0μs，整個網絡的平均同步精度達到14.0μs。傳到j的傳播時間為0到dij，dij為節點i到節點j的距離。D＝maxijdij，為網絡的直徑。GCS提出了兩要求：

4 分布式時隙同步算法

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

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

式中ω55＋ω53＋ω56＋ω59＝1，然后計算出參考的時隙基準：

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

5 總結及展望

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

①大規模無限傳感節點的時間同步研究。現有的大部分時間同步算法都是在實驗室平臺，是基于幾個或小規模的單跳網絡節點的仿真和研究。而現實中，隨著傳感器節點的低成本、微型化，及實際中的應用，大規模的多跳的無線自組網的傳感器網絡的研究將是今后研究的方向之一。

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

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

無線傳感器網絡是與實際應用相關的，不同的應用需要不同的時間同步精度和能耗要求，因此對時間同步的需求也是多種多樣的，應該結合特定的實際應用來研究和開發時間同步算法。

編者注：本文為期刊縮略版，全文見本刊網站www.mesnet.com.cn。

［1］David L Mills.RFC 1305－Network Time Protocol（Version 3）Specification.Implementation，1992.

［2］J Elson，L Girod，D Estrin.Fine－Grained Network Time Synchronization using Reference Broadcasts［C］／／Pro.5th Symp.Op.Sys.Design and Implementation.Boston，MA，2002.

［3］S Ganeriwal，R Kumar，M B Srivastava.Timing－sync Protocol for Sensor Networks［C］／／Proceedings of the 1st International Conference Embedded Networked Sensor Systems（SenSys's03）.USA：ACM press，2003.

［4］Weilian Su，Ian F Akyildiz.Time－Diffusion Synchronization Protocol for Wireless Sensor Networks［J］.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 International Conference on Embedded Networked Sensor Systems（Sen－Sys’04），USA，November，2004.

［6］Intel Research.Delay measurement time synchronization for wireless sensor networks，2003.

［7］J V Greunen，J Rabaey.Lightweight time synchronization for sensor networks［C］／／The 2nd ACM Int'l Workshop on Wireless Sensor Networks and Applications，San Diego，2003.

［8］Sichitiu M L，Veerarittiphan C.Simple，accurate time synchronization for wireless sensor networks［J］.IEEE Trans.on wireless communication and networking，2003（3）.

［9］H Dai，R Han.TSync：A Lightweight Bidirectional Time Synchronization Service for Wireless Sensor Networks［C］／／ACM SIGMOBILE Mobile Computing and Communications Review，Special Issue on Wireless PAN ＆Sensor Networks，University of Colorado，January 2004.

［10］王世軍，徐朝農，徐勇軍，等.同步精度穩定的多跳無線傳感器網絡時間同步算法［J］.計算機應用，2007（27）.

［11］Hyunhak Kim，Daeyoung Kim，Seong－eun Yoo.Clusterbased hierarchical time synchronization for multi－hop wireless sensor networks［C］／／Advanced Information Networking and Applications，2006.AINA 2006.20th International Conference，April 2006，2：5.

［12］S.Kee－Young ，K.Y.Lee，K.Lee.CRIT：A Hierarchical Chained－Ripple Time Synchronization in Wireless Sensor Networks［C］／／Networking，Sensing and Control，2006.ICNSC 06.Proceedings of the 2006IEEE International Conference，April 2006：797－802.