摘要：簡要闡述近年來傳感網(wǎng)絡(luò)" title="無線傳感網(wǎng)絡(luò)" target="_blank">無線傳感網(wǎng)絡(luò)時間同步算法的發(fā)展情況和影響無線傳感網(wǎng)絡(luò)時間同步的因素后，重點介紹了目前幾種比較典型的時間同步算法,，并對其精度,、功耗以及各自的優(yōu)缺點進行了較詳細的分析。在特定的網(wǎng)絡(luò)中,，應(yīng)該對精度與功耗進行折中考慮,。最后探討了未來可能的發(fā)展方向,。
關(guān)鍵詞：時間同步；典型時間同步算法,；誤差分析

引言
    保持節(jié)點之間時間上的同步在無線傳感器網(wǎng)絡(luò)中非常重要,，它是保證數(shù)據(jù)可靠傳輸?shù)那疤帷TP協(xié)議是目前因特網(wǎng)上采用的時間同步協(xié)議標(biāo)準,，功耗大,，采用有線傳輸，不適合用于功耗,、成本受限制的無線傳感網(wǎng)絡(luò)中,。GPS系統(tǒng)也可以提供高精度的時間同步，但它的信號穿透性差,，GPS天線必須安裝在空曠的地方,，功耗也較大，所以不適合無線傳感網(wǎng)絡(luò),。
    Elson等人2002年首次提出無線傳感器網(wǎng)絡(luò)時間同步的研究課題以來,，已有相當(dāng)多的典型時間同步算法，主要可以分為以下幾類：基于發(fā)送者一接收者的雙向同步算法,，典型算法如TPSN(Timing-Sync Protocol for Sensor Networks)算法,；基于發(fā)送者一接收者的單向時間同步算，典型算法如FTSP(Flooding Time Synclaronization Protocol)算法,、DMTS(Delay Measurement Time Synchronization)算法,；基于接收者一接收者的同步算法，典型算法有RBS(Reference Broadcast Synchronization)算法,。
    近年來根據(jù)以上幾種典型同步算法,，還有人提出了分簇式的層次型拓撲結(jié)構(gòu)算法，以及結(jié)合生成樹等來提高整個網(wǎng)絡(luò)的性能,，如LTS(Li-glatweight time synchronization)算法,、CHTS(Cluster-based Hierarehical Time Synchronization)算法,、CRIT(Chained-Ripple Time Synchronization)算法,、PBS(The Pairwise Broadcast Synchronization)算法、HRTS(Hierarchy ReferencingTime Synchronization Pro-toc01)算法,、BTS(Broadcasttime synchronization)算法,、ETSP(Energy-efficient Time Synchronization Protocol)算法等。
    然而,，無論以上同步算法怎樣發(fā)展,，精度如何提高，整個網(wǎng)絡(luò)功耗怎樣降低,，都是基于單跳時間同步機制,。隨著無線傳感網(wǎng)絡(luò)的運用與發(fā)展,，傳感節(jié)點體積不斷縮小，單跳距離變小,，整體網(wǎng)絡(luò)規(guī)模變大,，同步誤差的累積現(xiàn)象必將越來越嚴重，目前也有比較新的同步算法,，試圖盡量避開單跳累加來解決這些問題,，如協(xié)作同步。

1 時間同步
1．1 時間同步不確定性的影響因素
    時間同步不確定性的主要的影響因素如圖1所示,。

    發(fā)送時間：發(fā)送方用于構(gòu)造分組并將分組轉(zhuǎn)交給發(fā)送方的MAC層的時間,。主要取決于時間同步程序的操作系統(tǒng)調(diào)用時間和處理器負載等。
    訪問時間：分組到達MAC層后,，獲取信道發(fā)送權(quán)的時間,。主要取決于共享信道的競爭、當(dāng)前的負載等,。
    傳送時間：發(fā)送分組的時間,，主要取決于報文的長度等。
    傳播時間：分組離開發(fā)送方后,，并將分組傳輸?shù)浇邮辗街g的無線傳輸時間,。主要取決于傳輸介質(zhì)、傳輸距離等,。
    接收時間：接收端接收到分組,，并將分組傳送到MAC層所需的時間。接受時間：處理接收到分組的時間,。主要受到操作系統(tǒng)的影響,。
1．2 典型時間同步算法分析
1．2．1 TPSN算法分析
    TPSN算法采用的是層次型的網(wǎng)絡(luò)結(jié)構(gòu)，是基于發(fā)送者一接收者的雙向同步算法,。分成兩個階段,，第一階段為層次發(fā)現(xiàn)階段，第二階段為同步階段,。T1,、T4用來記錄同步節(jié)點的本地時間，T2,、T3用來記錄參考節(jié)點的本地時問,。同步節(jié)點A在T1時刻向參考節(jié)點B發(fā)送一個同步請求報文，報文中包含了同步節(jié)點的級別和T1,。當(dāng)參考節(jié)點B收到報文后,，記錄下接收時刻T2，并立即向同步節(jié)點A回復(fù)一個同步應(yīng)答報文,，該報文中包含了參考節(jié)點B的級別和T1,、T2及回復(fù)時刻T3,。同步節(jié)點A收到參考節(jié)點的回復(fù)后，記下時刻T4,。假設(shè)來回報文的傳輸延遲相同都為d,，且m為同步節(jié)點在T1時刻兩者之間的時偏，且設(shè)來回時偏相同,，由T2=T1+m+d,，T4=T3-m+d可得到：
   
    則在T4時刻，若在同步節(jié)點A的本地時間增加修正量m,，就能達到同步節(jié)點A與參考節(jié)點B之間的同步,。
1．2．2 RBS算法分析
    RBS算法是基于接收者一接收者的同步算法。首先參考節(jié)點廣播一個參考分組,，當(dāng)同步節(jié)點A收到這個分組,，記下自己的本地時鐘為T21，當(dāng)同步節(jié)點B收到這個分組時,，也記下自己的本地時鐘為T22,，然后同步節(jié)點A與同步節(jié)點B交換本地時鐘T21與T22，這時其中一個節(jié)點只要根據(jù)時間差值m=T21-T22,，修改自己的時鐘就能達到與另一個節(jié)點之間的同步,。在多跳網(wǎng)絡(luò)中，RBS算法采用多次廣播同步消息,，接收節(jié)點根據(jù)接收到同步消息的平均值,，同時采用最小平方線性回歸方法進行線性擬合以減小同步誤差。
1．2．3 DMTS算法分析
    DMTS算法是基于發(fā)送者一接收者的單向時間同步算法,。當(dāng)發(fā)送節(jié)點在檢測到通道空閑時,，給廣播分組加上時間戳t0，從而排除了發(fā)送節(jié)點的處理延遲與MAC層的訪問延遲,。并假設(shè)發(fā)送報文的長度為NA個比特(包括前導(dǎo)碼與同步字),，傳送每個比特的時間為t，而接收者在接收完同步字后,，記錄下此時的本地時間為t1,，并在調(diào)整自己的本地時間記錄之前記錄下此時的時刻t2，這時接收節(jié)點為了與發(fā)送節(jié)點達到時間上的同步,，可以調(diào)整接收節(jié)點的時間改為t0+t·NA+(t2-t1),。
    從參考文獻中，可以看出,，文章作者在加州大學(xué)伯克利分校的Mica節(jié)點上測試過，TPSN平均單跳誤差為17．61μs,，DMTS平均單跳誤差為30μs,，RBS平均單跳誤差為6．29μs,，TPSN平均4跳誤差為21．43μs，DMTS平均單跳誤差為151μs,，RBS平均4跳誤差為9．97μS,。
1．2．4 其他算法分析
    LTS協(xié)議是基于發(fā)送～接收同步機制發(fā)展而來，提出了集中式和分布式LTS多跳時間同步算法,。LTS協(xié)議首先把網(wǎng)絡(luò)組成廣度優(yōu)先生成樹拓撲結(jié)構(gòu),，并沿著樹的每條邊進行單跳成對同步。參考節(jié)點的子節(jié)點同步完成后,，又以該節(jié)點為參考節(jié)點,，采用同樣方式繼續(xù)同步下去，直到同步完成,。
    單跳成對同步采用TPSN同步方法,。成對同步的次數(shù)是邊數(shù)的線性函數(shù)。Hui Dui等人提出來的HRTS利用了廣播的特性,，只需要一次同步過程可以完成一個單跳組網(wǎng)所有節(jié)點的同步,，進一步降低了LTS協(xié)議的功耗。HRTS算法不再采用廣度優(yōu)先生成樹的邊,，采用的是廣度優(yōu)先生成樹非葉子節(jié)點個數(shù)的線性函數(shù),。相較于LTS協(xié)議，HRTS算法以犧牲一定的精確來降低了整個網(wǎng)絡(luò)的功耗,。
    BTS同步方法類似于HRTS算法,，也是先建立廣度優(yōu)先成生樹拓撲結(jié)構(gòu)，只不過BTS采用的是時間轉(zhuǎn)換技術(shù),，以達到整個網(wǎng)絡(luò)的時間同步,，而HRTS直接對同步節(jié)點的本地時間進行修改，得到全網(wǎng)的同步,，同步報文個數(shù)降為HRTS協(xié)議的2／3,。
    PBS同步算法的思想是參考節(jié)點與簇首節(jié)點之間采用雙向同步方法，與TPSN相似,，其他節(jié)點(在兩個節(jié)點的通信范圍內(nèi))可以偵聽到同步消息,，就可以根據(jù)接收者一接收者同步方法同步。類似于RBS同步,，PBS同步的前提是每個同步節(jié)點必須在簇首節(jié)點的通信范圍之內(nèi),。
    ETSP算法主要采用的是設(shè)置門檻值N來選擇同步算法，當(dāng)父節(jié)點的子節(jié)點小于或等于N時,，采用接收-接收(RBS)同步模式,，否則采用發(fā)送-接收(TPSN)同步模式。N值的選擇采用來計算,，式中m=Rx/Tx,，Rx為節(jié)點的接收次數(shù),，Tx為傳播次數(shù)。
    FTSP同步算法精度高的原因是,，發(fā)送者在發(fā)送一個同步請求報文時連續(xù)標(biāo)記了多個時間戳,，接收者可以根據(jù)這幾個中斷時間計算出更精確的時間偏差。
1．2．5 協(xié)作同步技術(shù)
    以上同步機制,，無論怎樣改進都是基于單跳同步基制,，最近有人提出了協(xié)作同步技術(shù)，不再單純地從單跳同步機制上進行改進,，而是通過信號疊加原理,，使同步基準節(jié)點能夠把同步消息直接發(fā)送到遠方待同步的節(jié)點，使遠方節(jié)點直接與基準節(jié)點同步,，消除了同步誤差單跳累加的結(jié)果,。Hu A等人針對節(jié)點密度較高的網(wǎng)絡(luò)提出了一種協(xié)作同步算法，基本思想是參考節(jié)點根據(jù)同步周期發(fā)出m個同步脈沖,，其一跳鄰居節(jié)點收到這個消息后保存起來,，并根據(jù)最近的m個脈沖的發(fā)送時刻計算出參考節(jié)點的第m+1個同步消息發(fā)出的時間，并在計算出來的時刻同步與參考節(jié)點同時發(fā)送第m+1個同步消息,。由于信號疊加,，因此同步脈沖可以發(fā)送到更遠的節(jié)點，當(dāng)然前提是網(wǎng)絡(luò)中節(jié)點密度較高的情況,。A．Kr-ohn等人提出了在物理層上面實現(xiàn)協(xié)作同步,，只需要本地消息，避免了額外的消息同步交換開銷,。參考文獻證實了協(xié)作同步誤差的方差與節(jié)點密度呈反比關(guān)系,。因此節(jié)點密度越高同步誤差也會越小。

2 時間同步算法誤差分析與比較
    根據(jù)節(jié)點消息傳輸過程可以得到式(1)與式(2)：
   
    在式(1),、(2)中,，t1、t2是由標(biāo)準時鐘所確定的,，表示UTC時間,。T1、T2分別是t1,、t2所對應(yīng)的本地節(jié)點所測出的本地時間,。SA代表節(jié)點A的報文發(fā)送時問，AA是發(fā)送報文的訪問時間,，TA→B是A節(jié)點按比特傳輸報文與B節(jié)點按比特接收報文所需要的時間,，PA→B是節(jié)點A傳播到節(jié)點B的時間。RB是節(jié)點B的報文接收處理過程時間。TN是傳輸NA個比特的總時間,。Terror指傳輸比特的誤差,，Rerror打時標(biāo)過程存在的誤差,。代表節(jié)點A與節(jié)點B在t1時刻的時偏,。
    對于TPSN算法，因為在MAC采用了加時間戳方法,，因此消除了發(fā)送時間與訪問時間對誤差的影響,。因此對TPSN算法式(1)、(2)就可以簡寫為式(3),、(4)：
         


    對于DMTS算法,，發(fā)送節(jié)點A在T0時刻檢測到空閑，接收節(jié)點B在報文到達時刻給報文加上時間戳T1,，并在調(diào)整自己的本地時間記錄之前記錄下此時的時刻為T2,，在T3時間完成調(diào)整。則可以得到：

    從式(7)中可以看出,，TPSN同步精度高的原因是在MAC層采用打時標(biāo)方式消除了發(fā)送時間與訪問時間的影響,，并在消息雙方向交換時消除了傳播時間的影響。缺點是點到點之間的同步,，每次只能一對節(jié)點進行時間同步,，同步一次需要發(fā)送2個消息，接收2個消息,，功耗較大,。從式(10)可以看出DMTS同步誤差較大的原因是單播傳播，沒辦法消除Terror與Rerror的影響,，但DMTS同步一次只要消耗1個發(fā)送消息,，1個接收消息，功耗較低,。至于FTSP同步算法比DMTS高的原因是,，發(fā)送者在發(fā)送一個同步請求報文時連續(xù)標(biāo)記了多個時間戳，接收者可以根據(jù)這幾個中斷時間,，計算出更精確的時間偏差,。可以看出,，RBS完全消除了發(fā)送方的影響,，只是同步一次消耗3個發(fā)送消息，4個接收消息,，功耗較大,。而對于HRTS與PBS算法，都是其于以上算法進行融合運用，在簇首節(jié)點與子網(wǎng)節(jié)點選擇上作了較大的改進,，以降低整個網(wǎng)絡(luò)的功耗,。

3 總結(jié)與展望
    從以上同步算法的誤差分析比對中可以看出，每種算法都有各自的優(yōu)缺點,，都適合不同的無線傳感網(wǎng)絡(luò),。精度高，相對功耗也較大,。對特定的無線傳感網(wǎng)絡(luò),，選擇同步算法時應(yīng)該折中考慮精度與功耗。從整體上看,，近年來有關(guān)時間同步算法的研究,，大部分都是基于以往典型的單跳同步算法原理，進一步從整體網(wǎng)絡(luò)中考慮誤差與功耗,，結(jié)合最優(yōu)生成樹,、分簇路由算法等，以平均整個網(wǎng)絡(luò)的功耗,，降低節(jié)點傳輸?shù)奶鴶?shù),，提高同步的精度。協(xié)作同步算法側(cè)重于提高整個網(wǎng)絡(luò)的可擴展性與健壯性,，但要求節(jié)點具有相同的同步脈沖,，比較困難，目前還需要進一步的發(fā)展驗證,，也是未來可能很好的發(fā)展方向,。