無線傳感器網絡典型時間同步技術分析

楊 穎，劉 軍

(武警工程學院研究生管理大隊，陜西西安 710086)

無線傳感器網絡是集微機電系統、傳感器技術、嵌入式計算技術、信息處理技術、現代網絡、無線通信技術和數字電子學于一體的新一代面向任務的分布式網絡。它是由在物理空間上密集分布的大量各類集成化的傳感器節點，通過自組織方式構成網絡，借助節點中不同類型的微型傳感器實時監測、感知和采集各種環境或被監測對象信息，協作地進行處理，并以自組織多跳的方式將信息傳送到用戶終端，實現物理世界、計算機世界以及人類社會三元世界的連通［1］。無線傳感器網絡具有廣闊的應用前景，主要應用在工業控制、生態環境、農業、防災救災、醫療保健、軍事國防、智能家居、空間探索、物流等領域。時間同步是無線傳感器網絡支撐技術的重要組成部分。研究無線傳感器網絡中的時間同步首先要分析其應用需求，在無線傳感器網絡中，由于傳感器節點分布密度高，而且自身資源有限，因此傳統網絡中高精度、不計成本和能耗的時間同步技術就不再適用于無線傳感器網絡，例如NTP協議。因此，研究適合無線傳感器網絡的時間同步就成為個國內外熱點問題。

1 時間同步模型及算法

1.1 時間同步模型

隨著時間同步概念的提出，其根據應用需求經歷了3種模型的演變。

(1)模糊模型。是指所謂的時間同步僅需知道事件發生的先后次序，無需了解事件發生的具體時間。它是將時間同步簡化為先來后到的問題，給人直觀的印象，無須將細節具體化。

(2)相對模型。指在維持節點間的相對時間。在該模型中，節點間彼此獨立，不同步，每個節點都有自己的本地時鐘，且它知道與其他節點的時間偏移量。根據需要，每個節點可與其他節點保持相對同步。

(3)精準模型。特點在于它的惟一性，它要求全網所有節點都與基準參考點保持同步，維持全網惟一的時間標準。

1.2 時間同步算法

隨著應用需求的不斷提高，時間同步趨于第3種模型，而時間同步算法也逐步成熟，完成級間的跳躍。

1.2.1 RBS

RBS(Reference Broadcast Synchronization)［2］由J.Elson等人于2002年提出基于參考廣播接收者與接收者之間的局部時間同步。具體描述為:第三方節點定時發送參考廣播給相鄰節點，相鄰節點接收廣播并記錄到達時間，以此時間作為參考與本地時鐘比較。相鄰節點交換廣播到達時間利用最小方差線性擬合的方法，估算兩者的初始相位差和頻率差，以此調整本地時鐘，達到接收節點間的同步。為提高同步精度，可以增加參考廣播的個數，也可以多次廣播。

RBS消除了發送節點的時延不確定性，誤差來源于傳輸和接收時延，同步精度較高;但由于多次廣播參考消息，能耗較大，隨著網絡規模及節點數目的增多，開銷也會越來越大，不適用于能量有限的無線傳感器網絡。

1.2.2 TPSN

TPSN(Timing － sync Protocol for Sensor Networks)［3］是由Saurabh Ganeriwal等人于2003年提出的基于成對雙向消息傳送的發送者與接收者之間的全網時間同步。具體描述如下:同步過程分為分層和同步兩個階段。分層階段是一個網絡拓撲的建立過程。首先確定根節點及等級，此節點是全網的時鐘參考節點，等級為0級，根節點廣播包含有自身等級信息的數據包，相鄰節點收到該數據包后，確定自身等級為1級，然后1級節點繼續廣播帶有自身等級信息的數據包，以此類推，i級節點廣播帶有自身等級信息的數據包，其相鄰節點收到后確定自身等級為i+1，直到網絡中所有節點都有自身的等級。一旦節點被定級，它將拒收分級數據包。同步階段從根節點開始，與其下一級節點進行成對同步，然后i級節點與i－1級節點同步，直到每個節點都與根節點同步。成對同步的過程如圖1所示。

圖1 成對同步過程

節點i在本地時刻T1時向節點j發送同步請求，該請求中包含節點i的等級和T1，節點j在本地時刻T2時收到請求并在T3時回發同步應答，該應答包含T2和T3，節點i于本地時刻T4收到應答信息，根據時間關系可列出方程

其中，d是消息傳輸遲延;Δ為時鐘偏差，經過計算得節點i計算出時間偏差Δ，從而調整自己的時鐘，達到同步。

TPSN采用層次分級形成拓撲樹結構，從根節點開始完成了所有葉子節點與根節點的同步，在MAC層打時間戳，降低了發送端的不確定性，減少了傳送時延、傳播時延和接收時延。該算法中任意節點的同步誤差與其到根節點的跳數有關，跳數越多，誤差越大，而與網絡節點總數無關，所以該算法具有較好的可擴展性;但由于全網參考時間由根節點確定，一旦根節點失效，就要重新選取根節點進行同步，其魯棒性不強，再同步還需要大量計算和能量開銷，增加整個網絡負荷。

1.2.3 DMTS

DMTS(DelayMeasurementTimeSynchronization)［4］是由Ping S于2003年提出的基于基準節點廣播的發送者與接收者之間的全網時間同步。具體描述為:選擇一個基準節點，廣播包含時間的同步消息，接收節點根據時間信息估算消息傳輸時延，調整自身本地時間為同步消息所帶時間加傳輸時延，消息傳輸時延td等于發射時延ts加接收處理時間tv，發射時延為發射前導碼和起始符所需的時間，等于發射位數n乘以發射一位所需的時間t，接收處理時間等于接收處理完成時間t2減消息到達時間t1，得出公式

將DMTS應用到多跳網絡中還采用與TPSN相同的分層方法進行同步，只是將每一層看作一個單跳網絡，基準節點依次定在0級，1級，2級，n級，逐步實現全網同步。為避免廣播消息回傳，每個節點只接收上一層等級比自己低的節點廣播。

DMTS以犧牲同步精度換取低能耗，結合使用在MAC層打時間戳和時延估計技術，消除了發送時延和接入時延，計算簡單，開銷小;但DMTS沒有估算時鐘頻偏，時鐘保持同步時間較短，時鐘計時精度仍然影響同步精度，致使精度不高難以用于定位等高精度的應用中。

1.2.4 FTSP

FTSP(Flooding Time Synchronization Protocol)［5］是由Branislav Kusy于2004年提出的基于單向廣播消息傳遞的發送者與接收者之間的全網時間同步。FTSP是對DMTS的改進，具體不同在于:

(1)FTSP降低了時延的不確定性，將其分為發送中斷處理時延、編碼時延、傳播時延、解碼時延、字節對齊時延和接收中斷處理時延。

(2)類似于RBS，FTSP可通過發送多個信令包，接收節點通過最小方差線性擬合計算出發送者與接收者之間的初始相位差和頻率差。

(3)FTSP根據一定時間范圍內節點時鐘晶振頻率穩定原則，得出各節點間時鐘偏移量與時間成線性關系，利用線性回歸的方法通過節點周期性發送同步廣播使得接收節點得到多個數據對構造回歸直線，而且在誤差允許的時間間隔內，節點可通過計算得出某一時間節點間時鐘偏移量，減少了同步廣播的次數，節省了能量。

(4)FTSP提出了一套較完整的針對節點失效、新節點加入等引起的拓撲結構變化時根節點選舉策略，從而提高了系統的容錯性和健壯性。

FTSP通過在MAC層打時間戳和利用線性回歸的方法估計位偏移量，降低了時延的不確定性，提高了同步精度，適用于軍事等需要高同步精度的場合。

1.2.5 LTS

LTS(Lightweight Time Synchronization)［6］是由 Van Greunen Jana和Rabaey Jan于2003年提出的基于成對機制的發送者與接收者之間的輕量級全網時間同步。該算法是在成對同步的基礎上進行了改進，具體包括兩種同步方式:第一種是集中式，首先構建一個低深度的生成樹，以根節點作為參考節點，為節省系統有限能量，按邊進行成對同步，根節點與其下一層的葉子節點成對同步，葉子節點再與其下一層的孩子節點成對同步，直到所有節點完成同步，因為同步時間和同步精度誤差與生成樹的深度有關，所以深度越小，同步時間越短，同步精度誤差越小;第二種是分布式，當節點i需要同步時，發送同步請求給最近的參考節點，此方式中沒有利用生成樹，按已有的路由機制尋找參考點。在節點i與參考節點路徑上的所有節點都被動地與參考節點同步，已同步節點不需要再發出同步請求，減少了同步請求的數量。為避免相鄰節點發出的同步請求重復，節點i在發送同步請求時詢問相鄰節點是否也需同步，將同步請求聚合，減少了同步請求的數目和不必要的重復。

LTS根據不同的應用需求在可行的同步精度下降低了成本，簡化了計算復雜度，節省了系統能量。

1.2.6 Tiny－sync和Mini－sync

Tiny－ sync和 Mini－ sync［7］是 由 Sichitiu 和Veerarittipahan于2003年提出的基于雙向消息傳遞的發送者和接收者之間的輕量級時間同步。該算法的前提是假設每個時鐘可近似為一個頻率固定的晶振，則兩個時鐘C1(t)，C2(t)滿足如下線性關系

其中，a12是兩時鐘的相對漂移;b12是兩時鐘的相對偏移。

算法仍采用TPSN中的雙向信息傳遞，不同之處在于Tiny－sync和Mini－sync發送多次探測信息，探測信息與以往的同步請求不同，接收節點收到探測信息后立即返回消息，具體如下:節點i在本地時刻t0發送一個探測消息給節點j，節點j收到消息后記錄本地時間tb并立即返回消息，節點i接收到消息后記錄本地時間tr。(t0，tb，tr)叫做數據點，節點i多次發送探測消息，并根據式(6)用線性規劃的原則得到a12和b12的最優估計，但用所有點計算運算量過大，Tiny－sync則是每次獲得新數據點后與先前的進行比較，誤差小于先前的誤差時才采用新數據點，否則拋棄。Minisync是Tiny－sync的優化，修正了Tiny－sync可能拋棄有用點的缺憾，留下了可能在后面提供較好邊界條件的數據點。

Tiny－sync和Mini－sync為滿足無線傳感器網絡低能耗的要求，交換少量信息，利用夾逼準則和線性規劃估算頻偏和相偏，提高了同步精度，降低了通信開銷。

2 時間同步算法性能對比分析

2.1 時間同步算法的性能評價指標

根據無線傳感器網絡自身資源有限、節點成本低、功耗低、自組織網絡等特點，應從以下幾點考慮無線傳感器網絡的時間同步算法［8］。

(1)能耗。由于無線傳感器網絡自身節點能量有限，其時間同步算法應保證在精度有效的前提下實現低能耗。

(2)可擴展性。在無線傳感器網絡中，節點數目增減靈活，時間同步算法應滿足節點數目增減和密度變化，具有較強的可擴展性。

(3)魯棒性。由于環境、能量等其它因素容易導致無線傳感器網絡節點無法正常工作，退出網絡，所以時間同步算法應具有較強魯棒性，保證通信暢通。

(4)同步壽命。是指節點間達到同步后一直保持同步的時間。同步壽命越短，節點就需要在較短時間內再同步，消耗的能量就越高。時間同步需要同步壽命較長的算法。

(5)同步消耗時間。是指節點從開始同步到完成同步所需的同步。同步消耗時間越長，所需的通信量、計算量和網絡開銷就越大，能耗也越高。

(6)同步間隔。是指節點同步壽命的結束到下一次同步開始所間隔的時間。同步間隔越長，同步開銷就越小，能耗越低。

(7)同步精度。不同的應用要求不同數量級的同步精度，有的時間同步只需知道事件發生的先后順序而有些則需精確到μs級。

(8)同步范圍。分為全網同步和局部同步，全網同步難度大、費用高;局部同步較易實現。權衡整個系統的功能應用及能耗開支等因素才能選擇合適的同步范圍。

(9)硬件限制。考慮傳感器節點的體積、大小、成本，時間同步算法會受到傳感器節點硬件的限制，只有依賴硬件的條件，才能設計出滿足應用需求的時間同步算法。

2.2 時間同步算法性能對比分析

經過在Mica2節點上的對比實驗，根據這些指標對以上的時間同步算法進行比較分析。具體性能比較如表1所示。

表1 時間同步算法性能對比分析表

3 結束語

隨著大規模無線傳感器網絡的廣泛應用，時間同步技術可以向以下幾方面發展:

(1)節點移動導致的拓撲結構可變。目前，大部分無線傳感器網絡都認為拓撲結構固定，沒有考慮到節點的移動性，但節點自身移動也可以將時間信息帶到另一個地方。

(2)依賴于節點的硬件條件，時間同步算法應在滿足應用需求的條件下盡可能地減少能量消耗，達到最優效率。

時間同步是無線傳感器網絡的一個重要支撐技術，仍需要研究人員的不斷探索和發現。

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(4):393 －422.

［2］JEREMY E，LEWIS G，DEBORAH E.Fine－grained network time synchronization using reference broadcasts［C］.Boston，MA:Proceedings of the Fifth Symposium on Operating Systems Design and Implementation，2002:147 －163.

［3］GANERIWAL S，KUMAR R，SRIVASTAVA M.Timing － sync protocol for sensor networks［C］.Losangeles，CA:ACM Sen-Sys，2003.

［4］PING S.Delay measurement time synchronization for wireless sensor networks［EB/OL］.(2003－07－12)［2011－01－08］Http//www.intel_research.net/publication/Berkeley/081120031327_137.pdf.

［5］MAROTI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol［C］.Baltimore，Mariland:Proceedings of the 2ndACM Conference on Embedded Networked Sensor Systems(SenSys)，2004:39 －49.

［6］GREUNEN V J，RABAEY J.Lightweight time synchronization for sensor networks［C］.San Diego，CA:Proc.2nd ACM Int'l.Conf.Wireless Sensor Networks and Apps，2003:11－19.

［7］SICHITIU M L，VEERARITTIPAHAN C.Simple，accurate time synchronization for wireless sensor networks［C］.New Orleans，LA:Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC2003)，2003:1266－1273.

［8］周賢偉，韋煒，覃伯平.無線傳感器網絡的時間同步算法研究［J］.傳感技術學報，2006，19(1):1005 －9490.

［9］STOJMENOVIC'I.Handbook of sensor networks:algorithms and architectures［M］.New York:Wiley，2005.

［10］CHARLES S P.Mathematical aspects of heart physiology［M/OL］.(2009－08－11)［2011－03－12］http://www.math.nyu.eduPfaculty/peskin/heartnotes/index.html.

［11］HONG Y，SCAGLIONE A.A scalable synchronization protocol for large scale sensor networks and its applications［J］.IEEE Journal of Selected Areas in Communications，2005，23(5):1085－1099.

［12］任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14(07):1282 －1291.

［13］楊宗凱，趙大勝，王玉明，等.無線傳感器網絡時鐘同步算法綜述［J］.計算機應用，2005，25(5):1170 －1176.

［14］康冠林，王福豹，段渭軍.無線傳感器網絡時間同步綜述［J］.計算機測量與控制，2005，13(10):1021 －1023.

［15］謝潔銳，胡月明.無線傳感器網絡的時間同步技術［J］.計算機工程與設計，2007，28(1):76 －77.

［16］趙建軍，姜建國，裴慶祺.低開銷的無線傳感器網絡時間同步方法［J］.計算機工程，2007，33(21):113 －115.

［17］葉雪，孫燕.一種節能的無線傳感器網絡分簇時間同步算法［J］.計算機工程，2009，35(19):117 －119.

［18］張白樺.基于TPSN的時間同步改進算法［J］，計算機工程，2010，36(9):109 －110.

［19］程利娟.無線傳感器網絡時間同步算法研究［D］.西安:西北工業大學，2007.

［20］張坤.無線傳感器網絡時間同步技術的研究［D］.重慶:西南大學，2007.

［21］孫佳偉.無線傳感器網絡時間同步的研究［D］.鞍山:遼寧科技大學，2008.