摘要 從無線傳感器網絡特點出發(fā)，結合三種時間同步模型及已有的時間同步算法，根據(jù)評價時間同步算法性能的指標，對典型的時間同步算法性能進行了分析評估，為進一步改進時間同步算法的性能提供了幫助。
關鍵詞 無線傳感器網絡；時間同步；模型

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

1 時間同步模型及算法
1．1 時間同步模型
    隨著時間同步概念的提出，其根據(jù)應用需求經歷了3種模型的演變。
    (1)模糊模型。是指所謂的時間同步僅需知道事件發(fā)生的先后次序，無需了解事件發(fā)生的具體時間。它是將時間同步簡化為先來后到的問題，給人直觀的印象，無須將細節(jié)具體化。
    (2)相對模型。指在維持節(jié)點間的相對時間。在該模型中，節(jié)點間彼此獨立，不同步，每個節(jié)點都有自己的本地時鐘，且它知道與其他節(jié)點的時間偏移量。根據(jù)需要，每個節(jié)點可與其他節(jié)點保持相對同步。
    (3)精準模型。特點在于它的惟一性，它要求全網所有節(jié)點都與基準參考點保持同步，維持全網惟一的時間標準。
1．2 時間同步算法
    隨著應用需求的不斷提高，時間同步趨于第3種模型，而時間同步算法也逐步成熟，完成級間的跳躍。
1．2．1 RBS
    RBS(Reference Broadcast Synchronization)由J．Elson等人于2002年提出基于參考廣播接收者與接收者之間的局部時間同步。具體描述為：第三方節(jié)點定時發(fā)送參考廣播給相鄰節(jié)點，相鄰節(jié)點接收廣播并記錄到達時間，以此時間作為參考與本地時鐘比較。相鄰節(jié)點交換廣播到達時間利用最小方差線性擬合的方法，估算兩者的初始相位差和頻率差，以此調整本地時鐘，達到接收節(jié)點間的同步。為提高同步精度，可以增加參考廣播的個數(shù)，也可以多次廣播。
    RBS消除了發(fā)送節(jié)點的時延不確定性，誤差來源于傳輸和接收時延，同步精度較高；但由于多次廣播參考消息，能耗較大，隨著網絡規(guī)模及節(jié)點數(shù)目的增多，開銷也會越來越大，不適用于能量有限的無線傳感器網絡。
1．2．2 TPSN
    TPSN(Timing-sync Protocol for Sensor Networks)是由Saurabh Ganeriwal等人于2003年提出的基于成對雙向消息傳送的發(fā)送者與接收者之間的全網時間同步。具體描述如下：同步過程分為分層和同步兩個階段。分層階段是一個網絡拓撲的建立過程。首先確定根節(jié)點及等級，此節(jié)點是全網的時鐘參考節(jié)點，等級為0級，根節(jié)點廣播包含有自身等級信息的數(shù)據(jù)包，相鄰節(jié)點收到該數(shù)據(jù)包后，確定自身等級為1級，然后1級節(jié)點繼續(xù)廣播帶有自身等級信息的數(shù)據(jù)包，以此類推，i級節(jié)點廣播帶有自身等級信息的數(shù)據(jù)包，其相鄰節(jié)點收到后確定自身等級為i+1，直到網絡中所有節(jié)點都有自身的等級。一旦節(jié)點被定級，它將拒收分級數(shù)據(jù)包。同步階段從根節(jié)點開始，與其下一級節(jié)點進行成對同步，然后i級節(jié)點與i-1級節(jié)點同步，直到每個節(jié)點都與根節(jié)點同步。成對同步的過程如圖1所示。

    節(jié)點i在本地時刻T1時向節(jié)點j發(fā)送同步請求，該請求中包含節(jié)點i的等級和T1，節(jié)點j在本地時刻T2時收到請求并在T3時回發(fā)同步應答，該應答包含T2和T3，節(jié)點i于本地時刻T4收到應答信息，根據(jù)時間關系可列出方程
   
    節(jié)點i計算出時間偏差△，從而調整自己的時鐘，達到同步。
    TPSN采用層次分級形成拓撲樹結構，從根節(jié)點開始完成了所有葉子節(jié)點與根節(jié)點的同步，在MAC層打時間戳，降低了發(fā)送端的不確定性，減少了傳送時延、傳播時延和接收時延。該算法中任意節(jié)點的同步誤差與其到根節(jié)點的跳數(shù)有關，跳數(shù)越多，誤差越大，而與網絡節(jié)點總數(shù)無關，所以該算法具有較好的可擴展性；但由于全網參考時間由根節(jié)點確定，一旦根節(jié)點失效，就要重新選取根節(jié)點進行同步，其魯棒性不強，再同步還需要大量計算和能量開銷，增加整個網絡負荷。
1．2．3 DMTS
    DMTS(Delay Measurement Time Synchronization)是由Ping S于2003年提出的基于基準節(jié)點廣播的發(fā)送者與接收者之間的全網時間同步。具體描述為：選擇一個基準節(jié)點，廣播包含時間的同步消息，接收節(jié)點根據(jù)時間信息估算消息傳輸時延，調整自身本地時間為同步消息所帶時間加傳輸時延，消息傳輸時延td等于發(fā)射時延ts加接收處理時間tv，發(fā)射時延為發(fā)射前導碼和起始符所需的時間，等于發(fā)射位數(shù)n乘以發(fā)射一位所需的時間t，接收處理時間等于接收處理完成時間t2減消息到達時間t1，得出公式
    td=ts+tv=nt+(t2-t1)      (5)
    將DMTS應用到多跳網絡中還采用與TPSN相同的分層方法進行同步，只是將每一層看作一個單跳網絡，基準節(jié)點依次定在0級，1級，2級，n級，逐步實現(xiàn)全網同步。為避免廣播消息回傳，每個節(jié)點只接收上一層等級比自己低的節(jié)點廣播。
    DMTS以犧牲同步精度換取低能耗，結合使用在MAC層打時間戳和時延估計技術，消除了發(fā)送時延和接入時延，計算簡單，開銷??；但DMTS沒有估算時鐘頻偏，時鐘保持同步時間較短，時鐘計時精度仍然影響同步精度，致使精度不高難以用于定位等高精度的應用中。
1．2．4 FTSP
    FTSP(Flooding Time Synchronization Protocol)是由Branislav Kusy于2004年提出的基于單向廣播消息傳遞的發(fā)送者與接收者之間的全網時間同步。FFSP是對DMTS的改進，具體不同在于：
    (1)FTSP降低了時延的不確定性，將其分為發(fā)送中斷處理時延、編碼時延、傳播時延、解碼時延、字節(jié)對齊時延和接收中斷處理時延。
    (2)類似于RBS，F(xiàn)TSP可通過發(fā)送多個信令包，接收節(jié)點通過最小方差線性擬合計算出發(fā)送者與接收者之間的初始相位差和頻率差。
    (3)FTSP根據(jù)一定時間范圍內節(jié)點時鐘晶振頻率穩(wěn)定原則，得出各節(jié)點問時鐘偏移量與時間成線性關系，利用線性回歸的方法通過節(jié)點周期性發(fā)送同步廣播使得接收節(jié)點得到多個數(shù)據(jù)對構造回歸直線，而且在誤差允許的時間間隔內，節(jié)點可通過計算得出某一時間節(jié)點間時鐘偏移量，減少了同步廣播的次數(shù)，節(jié)省了能量。
    (4)FTSP提出了一套較完整的針對節(jié)點失效、新節(jié)點加入等引起的拓撲結構變化時根節(jié)點選舉策略，從而提高了系統(tǒng)的容錯性和健壯性。
FTSP通過在MAC層打時間戳和利用線性回歸的方法估計位偏移量，降低了時延的不確定性，提高了同步精度，適用于軍事等需要高同步精度的場合。
1．2．5 LTS
    LTS(Lightweight Time Synchronization)是由VanGreunen Jana和Rabaey Jan于2003年提出的基于成對機制的發(fā)送者與接收者之間的輕量級全網時間同步。
    該算法是在成對同步的基礎上進行了改進，具體包括兩種同步方式：第一種是集中式，首先構建一個低深度的生成樹，以根節(jié)點作為參考節(jié)點，為節(jié)省系統(tǒng)有限能量，按邊進行成對同步，根節(jié)點與其下一層的葉子節(jié)點成對同步，葉子節(jié)點再與其下一層的孩子節(jié)點成對同步，直到所有節(jié)點完成同步，因為同步時間和同步精度誤差與生成樹的深度有關，所以深度越小，同步時間越短，同步精度誤差越小；第二種是分布式，當節(jié)點i需要同步時，發(fā)送同步請求給最近的參考節(jié)點，此方式中沒有利用生成樹，按已有的路由機制尋找參考點。在節(jié)點i與參考節(jié)點路徑上的所有節(jié)點都被動地與參考節(jié)點同步，已同步節(jié)點不需要再發(fā)出同步請求，減少了同步請求的數(shù)量。為避免相鄰節(jié)點發(fā)出的同步請求重復，節(jié)點i在發(fā)送同步請求時詢問相鄰節(jié)點是否也需同步，將同步請求聚合，減少了同步請求的數(shù)目和不必要的重復。
    LTS根據(jù)不同的應用需求在可行的同步精度下降低了成本，簡化了計算復雜度，節(jié)省了系統(tǒng)能量。
1．2．6 Tiny-sync和Mini-sync
    Tiny-sync和Mini-sync是由Sichitiu和Veerarittipahan于2003年提出的基于雙向消息傳遞的發(fā)送者和接收者之間的輕量級時間同步。該算法的前提是假設每個時鐘可近似為一個頻率固定的晶振，則兩個時鐘C1(t)，C2(t)滿足如下線性關系
    C1(t)=a12C2(t)+b12      (6)
    其中，a12是兩時鐘的相對漂移；b12是兩時鐘的相對偏移。
    算法仍采用TPSN中的雙向信息傳遞，不同之處在于Tiny-sync和Mini-sync發(fā)送多次探測信息，探測信息與以往的同步請求不同，接收節(jié)點收到探測信息后立即返回消息，具體如下：節(jié)點i在本地時刻t0發(fā)送一個探測消息給節(jié)點j，節(jié)點j收到消息后記錄本地時間tb并立即返回消息，節(jié)點i接收到消息后記錄本地時間tr。(t0，tb，tr)叫做數(shù)據(jù)點，節(jié)點i多次發(fā)送探測消息，并根據(jù)式(6)用線性規(guī)劃的原則得到a12和b12的最優(yōu)估計，但用所有點計算運算量過大，Tiny-sync則是每次獲得新數(shù)據(jù)點后與先前的進行比較，誤差小于先前的誤差時才采用新數(shù)據(jù)點，否則拋棄。Mini-sync是Tiny-sync的優(yōu)化，修正了Tiny-sync可能拋棄有用點的缺憾，留下了可能在后面提供較好邊界條件的數(shù)據(jù)點。
    Tiny-sync和Mini-sync為滿足無線傳感器網絡低能耗的要求，交換少量信息，利用夾逼準則和線性規(guī)劃估算頻偏和相偏，提高了同步精度，降低了通信開銷。

2 時間同步算法性能對比分析
2．1 時間同步算法的性能評價指標
    根據(jù)無線傳感器網絡自身資源有限、節(jié)點成本低、功耗低、自組織網絡等特點，應從以下幾點考慮無線傳感器網絡的時間同步算法。
    (1)能耗。由于無線傳感器網絡自身節(jié)點能量有限，其時間同步算法應保證在精度有效的前提下實現(xiàn)低能耗。
    (2)可擴展性。在無線傳感器網絡中，節(jié)點數(shù)目增減靈活，時間同步算法應滿足節(jié)點數(shù)目增減和密度變化，具有較強的可擴展性。
    (3)魯棒性。由于環(huán)境、能量等其它因素容易導致無線傳感器網絡節(jié)點無法正常工作，退出網絡，所以時間同步算法應具有較強魯棒性，保證通信暢通。
    (4)同步壽命。是指節(jié)點間達到同步后一直保持同步的時間。同步壽命越短，節(jié)點就需要在較短時間內再同步，消耗的能量就越高。時間同步需要同步壽命較長的算法。
    (5)同步消耗時間。是指節(jié)點從開始同步到完成同步所需的同步。同步消耗時間越長，所需的通信量、計算量和網絡開銷就越大，能耗也越高。
    (6)同步間隔。是指節(jié)點同步壽命的結束到下一次同步開始所間隔的時間。同步間隔越長，同步開銷就越小，能耗越低。
    (7)同步精度。不同的應用要求不同數(shù)量級的同步精度，有的時間同步只需知道事件發(fā)生的先后順序而有些則需精確到μs級。
    (8)同步范圍。分為全網同步和局部同步，全網同步難度大、費用高；局部同步較易實現(xiàn)。權衡整個系統(tǒng)的功能應用及能耗開支等因素才能選擇合適的同步范圍。
    (9)硬件限制?？紤]傳感器節(jié)點的體積、大小、成本，時間同步算法會受到傳感器節(jié)點硬件的限制，只有依賴硬件的條件，才能設計出滿足應用需求的時間同步算法。
2．2 時間同步算法性能對比分析
   經過在Mica2節(jié)點上的對比實驗，根據(jù)這些指標對以上的時間同步算法進行比較分析。具體性能比較如表1所示。

3 結束語
    隨著大規(guī)模無線傳感器網絡的廣泛應用，時間同步技術可以向以下幾方面發(fā)展：
    (1)節(jié)點移動導致的拓撲結構可變。目前，大部分無線傳感器網絡都認為拓撲結構固定，沒有考慮到節(jié)點的移動性，但節(jié)點自身移動也可以將時間信息帶到另一個地方。
    (2)依賴于節(jié)點的硬件條件，時間同步算法應在滿足應用需求的條件下盡可能地減少能量消耗，達到最優(yōu)效率。
    時間同步是無線傳感器網絡的一個重要支撐技術，仍需要研究人員的不斷探索和發(fā)現(xiàn)。