摘要 從無(wú)線傳感器網(wǎng)絡(luò)特點(diǎn)出發(fā)，結(jié)合三種時(shí)間同步模型及已有的時(shí)間同步算法，根據(jù)評(píng)價(jià)時(shí)間同步算法性能的指標(biāo)，對(duì)典型的時(shí)間同步算法性能進(jìn)行了分析評(píng)估，為進(jìn)一步改進(jìn)時(shí)間同步算法的性能提供了幫助。
關(guān)鍵詞 無(wú)線傳感器網(wǎng)絡(luò)；時(shí)間同步；模型

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

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

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

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

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