無線傳感器網(wǎng)絡(luò)典型時間同步技術(shù)分析

楊 穎，劉 軍

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

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

1 時間同步模型及算法

1.1 時間同步模型

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

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

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

(3)精準(zhǔn)模型。特點(diǎn)在于它的惟一性，它要求全網(wǎng)所有節(jié)點(diǎn)都與基準(zhǔn)參考點(diǎn)保持同步，維持全網(wǎng)惟一的時間標(biāo)準(zhǔn)。

1.2 時間同步算法

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

1.2.1 RBS

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

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

1.2.2 TPSN

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

圖1 成對同步過程

節(jié)點(diǎn)i在本地時刻T1時向節(jié)點(diǎn)j發(fā)送同步請求，該請求中包含節(jié)點(diǎn)i的等級和T1，節(jié)點(diǎn)j在本地時刻T2時收到請求并在T3時回發(fā)同步應(yīng)答，該應(yīng)答包含T2和T3，節(jié)點(diǎn)i于本地時刻T4收到應(yīng)答信息，根據(jù)時間關(guān)系可列出方程

其中，d是消息傳輸遲延;Δ為時鐘偏差，經(jīng)過計算得節(jié)點(diǎn)i計算出時間偏差Δ，從而調(diào)整自己的時鐘，達(dá)到同步。

TPSN采用層次分級形成拓?fù)錁浣Y(jié)構(gòu)，從根節(jié)點(diǎn)開始完成了所有葉子節(jié)點(diǎn)與根節(jié)點(diǎn)的同步，在MAC層打時間戳，降低了發(fā)送端的不確定性，減少了傳送時延、傳播時延和接收時延。該算法中任意節(jié)點(diǎn)的同步誤差與其到根節(jié)點(diǎn)的跳數(shù)有關(guān)，跳數(shù)越多，誤差越大，而與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)無關(guān)，所以該算法具有較好的可擴(kuò)展性;但由于全網(wǎng)參考時間由根節(jié)點(diǎn)確定，一旦根節(jié)點(diǎn)失效，就要重新選取根節(jié)點(diǎn)進(jìn)行同步，其魯棒性不強(qiáng)，再同步還需要大量計算和能量開銷，增加整個網(wǎng)絡(luò)負(fù)荷。

1.2.3 DMTS

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

將DMTS應(yīng)用到多跳網(wǎng)絡(luò)中還采用與TPSN相同的分層方法進(jìn)行同步，只是將每一層看作一個單跳網(wǎng)絡(luò)，基準(zhǔn)節(jié)點(diǎn)依次定在0級，1級，2級，n級，逐步實現(xiàn)全網(wǎng)同步。為避免廣播消息回傳，每個節(jié)點(diǎn)只接收上一層等級比自己低的節(jié)點(diǎn)廣播。

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

1.2.4 FTSP

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

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

(2)類似于RBS，F(xiàn)TSP可通過發(fā)送多個信令包，接收節(jié)點(diǎn)通過最小方差線性擬合計算出發(fā)送者與接收者之間的初始相位差和頻率差。

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

(4)FTSP提出了一套較完整的針對節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入等引起的拓?fù)浣Y(jié)構(gòu)變化時根節(jié)點(diǎn)選舉策略，從而提高了系統(tǒng)的容錯性和健壯性。

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

1.2.5 LTS

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

LTS根據(jù)不同的應(yīng)用需求在可行的同步精度下降低了成本，簡化了計算復(fù)雜度，節(jié)省了系統(tǒng)能量。

1.2.6 Tiny－sync和Mini－sync

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

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

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

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

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

2.1 時間同步算法的性能評價指標(biāo)

根據(jù)無線傳感器網(wǎng)絡(luò)自身資源有限、節(jié)點(diǎn)成本低、功耗低、自組織網(wǎng)絡(luò)等特點(diǎn)，應(yīng)從以下幾點(diǎn)考慮無線傳感器網(wǎng)絡(luò)的時間同步算法［8］。

(1)能耗。由于無線傳感器網(wǎng)絡(luò)自身節(jié)點(diǎn)能量有限，其時間同步算法應(yīng)保證在精度有效的前提下實現(xiàn)低能耗。

(2)可擴(kuò)展性。在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)數(shù)目增減靈活，時間同步算法應(yīng)滿足節(jié)點(diǎn)數(shù)目增減和密度變化，具有較強(qiáng)的可擴(kuò)展性。

(3)魯棒性。由于環(huán)境、能量等其它因素容易導(dǎo)致無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)無法正常工作，退出網(wǎng)絡(luò)，所以時間同步算法應(yīng)具有較強(qiáng)魯棒性，保證通信暢通。

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

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

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

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

(8)同步范圍。分為全網(wǎng)同步和局部同步，全網(wǎng)同步難度大、費(fèi)用高;局部同步較易實現(xiàn)。權(quán)衡整個系統(tǒng)的功能應(yīng)用及能耗開支等因素才能選擇合適的同步范圍。

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

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

經(jīng)過在Mica2節(jié)點(diǎn)上的對比實驗，根據(jù)這些指標(biāo)對以上的時間同步算法進(jìn)行比較分析。具體性能比較如表1所示。

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

3 結(jié)束語

隨著大規(guī)模無線傳感器網(wǎng)絡(luò)的廣泛應(yīng)用，時間同步技術(shù)可以向以下幾方面發(fā)展:

(1)節(jié)點(diǎn)移動導(dǎo)致的拓?fù)浣Y(jié)構(gòu)可變。目前，大部分無線傳感器網(wǎng)絡(luò)都認(rèn)為拓?fù)浣Y(jié)構(gòu)固定，沒有考慮到節(jié)點(diǎn)的移動性，但節(jié)點(diǎn)自身移動也可以將時間信息帶到另一個地方。

(2)依賴于節(jié)點(diǎn)的硬件條件，時間同步算法應(yīng)在滿足應(yīng)用需求的條件下盡可能地減少能量消耗，達(dá)到最優(yōu)效率。

時間同步是無線傳感器網(wǎng)絡(luò)的一個重要支撐技術(shù)，仍需要研究人員的不斷探索和發(fā)現(xiàn)。

［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］周賢偉，韋煒，覃伯平.無線傳感器網(wǎng)絡(luò)的時間同步算法研究［J］.傳感技術(shù)學(xué)報，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］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報，2003，14(07):1282 －1291.

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

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

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

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

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

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

［19］程利娟.無線傳感器網(wǎng)絡(luò)時間同步算法研究［D］.西安:西北工業(yè)大學(xué)，2007.

［20］張坤.無線傳感器網(wǎng)絡(luò)時間同步技術(shù)的研究［D］.重慶:西南大學(xué)，2007.

［21］孫佳偉.無線傳感器網(wǎng)絡(luò)時間同步的研究［D］.鞍山:遼寧科技大學(xué)，2008.