無線傳感器網(wǎng)絡(luò)時間同步方法研究

1、無線傳感器網(wǎng)絡(luò)時間同步方法研究趙玉葉梁葉 收稿日期2011-5-20（廣西大學(xué)電氣工程學(xué)院廣西南寧530004）摘要時間同步技術(shù)是研究無線傳感器網(wǎng)絡(luò)（WSN）許多關(guān)鍵技術(shù)實(shí)現(xiàn)的基礎(chǔ)。文章分析了時間同步方法的重要性和設(shè)計時間同步機(jī)制關(guān)注的性能指標(biāo)，總結(jié)了幾個具有代表性的時間同步技術(shù)方法，描述了各自的工作原理以及優(yōu)缺點(diǎn)。關(guān)鍵詞無線傳感器網(wǎng)絡(luò)；時間同步；算法中圖分類號O45文獻(xiàn)標(biāo)識碼A文章編號1088-7656（2011）03-0038-041 時間同步技術(shù)的重要性傳感器節(jié)點(diǎn)的時鐘并不完美，會在時間上發(fā)生漂移，所以觀察到的時間對于網(wǎng)絡(luò)中的節(jié)點(diǎn)來說是不同的。但很多網(wǎng)絡(luò)協(xié)議的應(yīng)用，都需要一個共同的時間以

2、使得網(wǎng)路中的節(jié)點(diǎn)全部或部分在瞬間是同步的。第一，傳感器節(jié)點(diǎn)需要彼此之間并行操作和協(xié)作去完成復(fù)雜的傳感任務(wù)。如果在收集信息過程中，傳感器節(jié)點(diǎn)缺乏統(tǒng)一的時間戳（即沒有同步），估計將是不準(zhǔn)確的。第二，許多節(jié)能方案是利用時間同步來實(shí)現(xiàn)的。例如，傳感器可以在適當(dāng)?shù)臅r候休眠（通過關(guān)閉傳感器和收發(fā)器進(jìn)入節(jié)能模式），在需要的時候再喚醒。在應(yīng)用這種節(jié)能模式的時候，節(jié)點(diǎn)應(yīng)該在同等的時間休眠和喚醒，也就是說當(dāng)數(shù)據(jù)到來時，節(jié)點(diǎn)的接收器可以接收，這個需要傳感器節(jié)點(diǎn)間精確的定時。2 時間同步技術(shù)所關(guān)注的主要性能參數(shù)時間同步技術(shù)的根本目的是為網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時鐘提供共同的時間戳。對無線傳感器網(wǎng)絡(luò)WSN（Wireless S

3、ensor Networks）1的時間同步應(yīng)主要應(yīng)考慮以下幾個方面的問題：(1)能量效率。同步的時間越長，消耗的能量越多，效率就越低。設(shè)計WSN的時間同步算法需以考慮傳感器節(jié)點(diǎn)有效的能量資源為前提。(2) 可擴(kuò)展性和健壯性。時間同步機(jī)制應(yīng)該支持網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目或者密度的有效擴(kuò)展，并保障一旦有節(jié)點(diǎn)失效時，余下網(wǎng)絡(luò)有效且功能健全。(3)精確度。針對不同的應(yīng)用和目的，精確度的需求有所不用。(4)同步期限。節(jié)點(diǎn)需要保持時間同步的時間長度可以是瞬時的，也可以和網(wǎng)絡(luò)的壽命一樣長。(5)有效同步范圍。可以給網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)提供時間，也可以給局部區(qū)域的節(jié)點(diǎn)提供時間。(6)成本和尺寸。同步可能需要特定的硬件，另外

4、，體積的大小也影響同步機(jī)制的實(shí)現(xiàn)。(7)最大誤差。一組傳感器節(jié)點(diǎn)之間的最大時間差，或相對外部標(biāo)準(zhǔn)時間的最大差。3 現(xiàn)有主要時間同步方法研究時間同步技術(shù)是研究WSN的重要問題，許多具體應(yīng)用都需要傳感器節(jié)點(diǎn)本地時鐘的同步，要求各種程度的同步精度。WSN具有自組織性、多跳性、動態(tài)拓?fù)湫院唾Y源受限性，尤其是節(jié)點(diǎn)的能量資源、計算能力、通信帶寬、存儲容量有限等特點(diǎn)，使時間同步方案有其特殊的需求，也使得傳統(tǒng)的時間同步算法不適合于這些網(wǎng)絡(luò)2。因此越來越多的研究集中在設(shè)計適合WSN的時間同步算法3。針對WSN，目前已經(jīng)從不同角度提出了許多新的時間同步算法4。3.1 成對(pair-wise)同步的雙向同步模式代

5、表算法是傳感器網(wǎng)絡(luò)時間同步協(xié)議TPSN（Timing-Sync Protocol for Sensor Networks）56。目的是提供WSN整個網(wǎng)絡(luò)范圍內(nèi)節(jié)點(diǎn)間的時間同步。該算法分兩步：分級和同步。第一步的目的是建立分級的拓?fù)渚W(wǎng)絡(luò)，每個節(jié)點(diǎn)有個級別。只有一個節(jié)點(diǎn)與外界通信獲取外界時間，將其定為零級，叫做根節(jié)點(diǎn)，作為整個網(wǎng)絡(luò)系統(tǒng)的時間源。在第二步，每個i級節(jié)點(diǎn)與i-1（上一級）級節(jié)點(diǎn)同步，最終所有的節(jié)點(diǎn)都與根節(jié)點(diǎn)同步，從而達(dá)到整個網(wǎng)絡(luò)的時間同步。詳細(xì)的時間同步過程如圖 1 所示。圖1 TPSN 同步過程設(shè)R為上層節(jié)點(diǎn)，S為下層節(jié)點(diǎn)，傳播時間為d，兩節(jié)點(diǎn)的時間偏差為。同步過程由節(jié)點(diǎn)R廣播開始同

6、步信息，節(jié)點(diǎn)S接收到信息以后，就開始準(zhǔn)備時間同步過程。在T1時刻，節(jié)點(diǎn)S發(fā)送同步信息包，包含信息(T1)，節(jié)點(diǎn)R在T2接收到同步信息，并記錄下接收時間T2，這里滿足關(guān)系：節(jié)點(diǎn)R在T3時刻發(fā)送回復(fù)信息包，包含信息(T1,T2,T3)。在T4時刻S接收到同步信息包，滿足關(guān)系：最后，節(jié)點(diǎn)S利用上述2個時間表達(dá)式可計算出的值：TPSN由于采用了在MAC層給同步包標(biāo)記時間戳的方式，降低了發(fā)送端的不確定性，消除了訪問時間帶來的時間同步誤差，使得同步效果更加有效。并且，TPSN算法對任意節(jié)點(diǎn)的同步誤差取決于它距離根節(jié)點(diǎn)的跳數(shù)，而與網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)無關(guān)，使TPSN同步精度不會隨節(jié)點(diǎn)數(shù)目增加而降級，從而使TPSN

7、具有較好的擴(kuò)展性。TPSN算法的缺點(diǎn)是一旦根節(jié)點(diǎn)失效，就要重新選擇根節(jié)點(diǎn)，并重新進(jìn)行分級和同步階段的處理，增加了計算和能量開銷，并隨著跳數(shù)的增加，同步誤差呈線性增長，準(zhǔn)確性較低。另外，TPSN算法沒有對時鐘的頻差進(jìn)行估計，這使得它需要頻繁同步，完成一次同步能量消耗較大。3.2 接收方-接收方（Receiver-Receiver）模式代表算法是參考廣播時間同步協(xié)議RBS（Reference Broadcast Synchronization）7。RBS是典型的基于接收方-接收方的同步算法，是Elson等人以“第三節(jié)點(diǎn)”實(shí)現(xiàn)同步的思想而提出的。該算法中，利用無線數(shù)據(jù)鏈路層的廣播信道特性，基本思想為

8、：節(jié)點(diǎn)(作為發(fā)送者)通過物理層廣播周期性地向其鄰居節(jié)點(diǎn)（作為接收者）發(fā)送信標(biāo)消息10，鄰居節(jié)點(diǎn)記錄下廣播信標(biāo)達(dá)到的時間，并把這個時間作為參考點(diǎn)與時鐘的讀數(shù)相比較。為了計算時鐘偏移，要交換對等鄰居節(jié)點(diǎn)間的時間戳，確定它們之間的時間偏移量，然后其中一個根據(jù)接收到的時間差值來修改其本地的時間，從而實(shí)現(xiàn)時間同步11。假如該算法在網(wǎng)絡(luò)中有n個接收節(jié)點(diǎn)m個參考廣播包，則任意一個節(jié)點(diǎn)接收到m個參考包后，會拿這些參考包到達(dá)的時間與其它n-1個接收節(jié)點(diǎn)接收到的參考包到達(dá)的時間進(jìn)行比較，然后進(jìn)行信息交換。圖2為RBS算法的關(guān)鍵路徑示意圖。圖2 RBS算法的關(guān)鍵路徑示意圖其計算公式如下：其中n表示接收者的數(shù)量，m表

9、示參考包的數(shù)量，表示接收節(jié)點(diǎn)r接收到參考包b時的時鐘。此算法并不是同步發(fā)送者和接收者，而是使接收者彼此同步，有效避免了發(fā)送訪問時間對同步的影響，將發(fā)送方延遲的不確定性從關(guān)鍵路徑中排除，誤差的來源主要是傳輸時間和接收時間的不確定性，從而獲得了比利用節(jié)點(diǎn)間雙向信息交換實(shí)現(xiàn)同步的方法更高的精確度。這種方法的最大弊端是信息的交換次數(shù)太多，發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間、接收節(jié)點(diǎn)彼此之間，都要經(jīng)過消息交換后才能達(dá)到同步。計算復(fù)雜度較高，網(wǎng)絡(luò)流量開銷和能耗太大，不適合能量供應(yīng)有限的場合。3.3 發(fā)送方-接收方(Sender-Receiver)模式基于發(fā)送方-接收方機(jī)制的時間同步算法的基本原理是：發(fā)送節(jié)點(diǎn)發(fā)送包含本

10、地時間戳的時間同步消息，接收節(jié)點(diǎn)記錄本地接收時間，并將其與同步消息中的時間戳進(jìn)行比較，調(diào)整本地時鐘?；谶@種方法提出的時間同步算法有以下兩種。3.3.1 FTSP 算法8泛洪時間同步協(xié)議FTSP（Flooding Time Synchronization Protocol）由Vanderbilt大學(xué)Branislav Kusy等提出，目標(biāo)是實(shí)現(xiàn)整個網(wǎng)絡(luò)的時間同步且誤差控制在微秒級。該算法用單個廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時間同步。其特點(diǎn)為：(1)通過對收發(fā)過程的分析，把時延細(xì)分為發(fā)送中斷處理時延、編碼時延、傳播時延、解碼時延、字節(jié)對齊時延、接收中斷處理時延，進(jìn)一步降低時延的不確定度；(

11、2)通過發(fā)射多個信令包，使得接收節(jié)點(diǎn)可以利用最小方差線性擬合技術(shù)估算自己和發(fā)送節(jié)點(diǎn)的頻率差和初相位差；(3)設(shè)計一套根節(jié)點(diǎn)選舉機(jī)制，針對節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入、拓?fù)渥兓惹闆r進(jìn)行優(yōu)化，適合于惡劣環(huán)境12。FTSP算法對時鐘漂移進(jìn)行了線性回歸分析。此算法考慮到在特定時間范圍內(nèi)節(jié)點(diǎn)時鐘晶振頻率是穩(wěn)定的，因此節(jié)點(diǎn)間時鐘偏移量與時間成線性關(guān)系，通過發(fā)送節(jié)點(diǎn)周期性廣播時間同步消息，接收節(jié)點(diǎn)取得多個數(shù)據(jù)對，構(gòu)造最佳擬合直線，通過回歸直線，在誤差允許的時間間隔內(nèi)，節(jié)點(diǎn)可直接通過它來計算某一時間節(jié)點(diǎn)間的時鐘偏移量而不必發(fā)送時間同步消息進(jìn)行計算，從而減少了消息的發(fā)送次數(shù)并降低了系統(tǒng)能量開銷。FTSP結(jié)合TPSN和

12、RBS的優(yōu)點(diǎn)，不僅排除了發(fā)送方延遲的影響，而且對報文傳輸中接收方的不確定延遲（如中斷處理時間、字節(jié)對齊時間、硬件編解碼時間等）做了有效的估計。多跳的FTSP協(xié)議采用層次結(jié)構(gòu)，根節(jié)點(diǎn)為同步源，可以適應(yīng)大量傳感器節(jié)點(diǎn)，對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和根節(jié)點(diǎn)的失效有健壯性，精確度較好。該算法通過采用MAC層時間戳和線性回歸偏差補(bǔ)償彌補(bǔ)相關(guān)的錯誤源，通過對一個數(shù)據(jù)包打多個時戳，進(jìn)而取平均和濾除抖動較大的時戳，大大降低了中斷和解碼時間的影響。FTSP 采用洪泛的方式向遠(yuǎn)方節(jié)點(diǎn)傳遞時間基準(zhǔn)節(jié)點(diǎn)的時間信息，洪泛的時間信息可由中轉(zhuǎn)節(jié)點(diǎn)生成，因此誤差累積不可避免。另外，F(xiàn)TSP的功耗和帶寬的開銷巨大。3.3.2 DMTS

13、 算法9延遲測量時間同步DMTS (delay measurement time synchronization) 算法的同步機(jī)制是基于發(fā)送方-接收方的同步機(jī)制。DMTS 算法的實(shí)現(xiàn)策略是犧牲部分時間同步精度換取較低的計算復(fù)雜度和能耗，是一種能量消耗輕的時間同步算法。DMTS算法的基本原理為：選擇一個節(jié)點(diǎn)作為時間主節(jié)點(diǎn)廣播同步時間，所有接收節(jié)點(diǎn)通過精確地測量從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)的單向時間廣播消息的延遲并結(jié)合發(fā)送節(jié)點(diǎn)時間戳，計算出時間調(diào)整值，接收節(jié)點(diǎn)設(shè)置它的時間為接收到消息攜帶的時間加上廣播消息的傳輸延遲，調(diào)整自己的邏輯時鐘值以和基準(zhǔn)點(diǎn)達(dá)成同步，這樣所有得到廣播消息的節(jié)點(diǎn)都與主節(jié)點(diǎn)進(jìn)行時間同步。

14、發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的時間延遲可由得出。其中，nt為發(fā)送前導(dǎo)碼和起始字符所需的時間，n為發(fā)送的信息位個數(shù)，t為發(fā)送一位所需時間；為接收節(jié)點(diǎn)在消息到達(dá)時的本地時間；為接收節(jié)點(diǎn)在調(diào)整自己的時鐘之前的那一時刻記錄的本地時間，是接收處理延遲。DMTS 算法的優(yōu)點(diǎn)是結(jié)合鏈路層打時間戳和時延估計等技術(shù)，消除了發(fā)送時延和訪問時延的影響，算法簡單，通信開銷小。但DMTS算法沒有估計時鐘的頻率偏差，時鐘保持同步的時間較短，沒有對位偏移產(chǎn)生的時間延遲進(jìn)行估計，也沒有消除時鐘計時精度對同步精度的影響，因此其同步精度比FTSP略有下降，不適用于定位等要求高精度同步的應(yīng)用?；诎l(fā)送方-接收方單向同步機(jī)制的算法在上述三類方

15、法中需要發(fā)送的時間同步消息數(shù)目最少。發(fā)送節(jié)點(diǎn)只要發(fā)送一次同步消息，因而具有較低的網(wǎng)絡(luò)流量開銷和復(fù)雜度，減少了系統(tǒng)能耗。4 結(jié)論文章介紹了WSN時間同步算法的類型以及各自具有代表性的算法，分析了各算法的設(shè)計原理和優(yōu)缺點(diǎn)。這些協(xié)議解決了WSN中時間同步所遇到的主要問題，但對于大型網(wǎng)絡(luò)，已有的方法或多或少存在著一些問題：擴(kuò)展性差、穩(wěn)定性不高、收斂速度變慢、網(wǎng)絡(luò)通信沖突、能耗增大。今后的研究熱點(diǎn)將集中在節(jié)能和時間同步的安全性方面。這將對算法的容錯性、有效范圍和可擴(kuò)展性提出更高的要求。參考文獻(xiàn)1I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,E.Cayirci,”A Survey on Sensor Networks,”IEEE Communications Magazine,vol.40,no.8,pp.102-114,2002.2 周賢偉，韋煒，覃伯平. 無線傳感器網(wǎng)絡(luò)的時間同步算法研究J. 傳感技術(shù)學(xué)報，2006（1）.3 趙建軍, 姜建國, 裴慶祺. 低開銷的無線