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

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

引 言

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

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

1 概念與定義

在計算機(jī)體系結(jié)構(gòu)中，時鐘通常用晶體振蕩器脈沖來度量，即

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

假定c（t）是一個理想的時鐘。如果在t時刻有c（t）＝ci（t），則稱ci（t）在t時刻是準(zhǔn)確的；如果dc（t）／dt＝dci（t）／dt，則稱時鐘ci（t）在t時刻是精確的；如果ci（t）＝ck（t），則稱時鐘ci（t）在t時刻與時鐘ck（t）是同步的。上述定義表明，兩個同步時鐘不一定是準(zhǔn)確或精確的，時間同步與時間的準(zhǔn)確性和精度沒有必然的聯(lián)系。

如果采用時鐘速率恒定模型，由式（1），時鐘ci（t）可以簡化表示為：

由此可知，時鐘ci（t）和ck（t）之間應(yīng)該存在如下的線性關(guān)系：

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

2 典型同步算法

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

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

TPSN算法是由Ganeriwal等人提出的，是一種基于發(fā)送者和接收者的時間同步算法。采用層次型網(wǎng)絡(luò)結(jié)構(gòu)。算法分兩步：首先是層次發(fā)現(xiàn)階段，建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；然后每個節(jié)點與上一級的一個節(jié)點進(jìn)行時間同步，最終實現(xiàn)所有節(jié)點都與根節(jié)點的時間同步。

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

無線傳感器網(wǎng)絡(luò)的最常見的幾種同步算法的性能比較如表1所列。

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

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

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

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

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

4 分布式時隙同步算法

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

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

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

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

5 總結(jié)及展望

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

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

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

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

無線傳感器網(wǎng)絡(luò)是與實際應(yīng)用相關(guān)的，不同的應(yīng)用需要不同的時間同步精度和能耗要求，因此對時間同步的需求也是多種多樣的，應(yīng)該結(jié)合特定的實際應(yīng)用來研究和開發(fā)時間同步算法。

編者注：本文為期刊縮略版，全文見本刊網(wǎng)站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］王世軍，徐朝農(nóng)，徐勇軍，等.同步精度穩(wěn)定的多跳無線傳感器網(wǎng)絡(luò)時間同步算法［J］.計算機(jī)應(yīng)用，2007（27）.

［11］Hyunhak Kim，Daeyoung Kim，Seong－eun Yoo.Clusterbased hierarchical time synchronization for multi－h(huán)op 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.