無線傳感器網絡時間同步方法研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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