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

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

引 言

無線傳感器網(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)用前景，是近年來國內(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é)議 NTP［1］（Network Time Protocol）是傳統(tǒng)網(wǎng)絡(luò)的時(shí)間同步協(xié)議，最早由美國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ù)的課題，在國際上引發(fā)了廣泛的關(guān)注和思考，吸引了許多大學(xué)和研究機(jī)構(gòu)參與研究，已經(jīng)提出許多種不同的實(shí)現(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ù)的時(shí)間同步算法等。

1 概念與定義

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

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

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

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

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

式中aik、bik為相對(duì)漂移量和相對(duì)偏移量。

2 典型同步算法

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

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

TPSN算法是由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)同步的相同的辦法，使它們的鄰居節(jié)點(diǎn)也實(shí)現(xiàn)與其同步。

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

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

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

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

計(jì)算出時(shí)鐘漂移的最低邊界滿足f（D）＝Ω（d＋lgD／lg lgD），這也就是說節(jié)點(diǎn)之間的時(shí)鐘漂移不只與兩個(gè)節(jié)點(diǎn)間的距離有關(guān)，還與整個(gè)網(wǎng)絡(luò)的規(guī)模有關(guān)，越近的節(jié)點(diǎn)同步效果越好，反之越差。GTSP（Gradient Time Synchronization Protocol）協(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μs，整個(gè)網(wǎng)絡(luò)的平均同步精度達(dá)到14.0μs。傳到j(luò)的傳播時(shí)間為0到dij，dij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。D＝maxijdij，為網(wǎng)絡(luò)的直徑。GCS提出了兩要求：

4 分布式時(shí)隙同步算法

主從同步方法是網(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ì)有誤差的累積，因此更加適合于大型的多跳自組織的無線傳感器網(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)行。采用固定的時(shí)隙調(diào)整時(shí)，根據(jù)節(jié)點(diǎn)間時(shí)隙基準(zhǔn)是超前還是滯后來調(diào)整時(shí)隙基準(zhǔn)?；诜植际揭恢碌臒o線傳感器網(wǎng)絡(luò)的時(shí)間同步協(xié)議的收斂和加速問題研究中，將分布式一致的收斂和加速問題映射到馬爾科夫鏈的狀態(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í)隙差值為Δtij，可以算出所有鄰居節(jié)點(diǎn)的時(shí)隙偏差值的加權(quán)平均值為εi，時(shí)隙修正量ωij。節(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í)隙偏差 Δt53（n）、Δt56和 Δt59（n），從而計(jì)算出自己的時(shí)隙調(diào)整量：

式中ω55＋ω53＋ω56＋ω59＝1，然后計(jì)算出參考的時(shí)隙基準(zhǔ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，即，式中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ù)變少，因而收斂速度提高。算法平均迭代38次可以達(dá)到最大時(shí)隙偏差收斂到10－6以下。

5 總結(jié)及展望

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

①大規(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í)中，隨著傳感器節(jié)點(diǎn)的低成本、微型化，及實(shí)際中的應(yīng)用，大規(guī)模的多跳的無線自組網(wǎng)的傳感器網(wǎng)絡(luò)的研究將是今后研究的方向之一。

②魯棒性和容錯(cuò)性的研究?，F(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ò)是與實(shí)際應(yīng)用相關(guān)的，不同的應(yīng)用需要不同的時(shí)間同步精度和能耗要求，因此對(duì)時(shí)間同步的需求也是多種多樣的，應(yīng)該結(jié)合特定的實(shí)際應(yīng)用來研究和開發(fā)時(shí)間同步算法。

編者注：本文為期刊縮略版，全文見本刊網(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ò)時(shí)間同步算法［J］.計(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.