安竹林無線傳感器網(wǎng)絡(luò)時間同步概述

1、無線傳感器網(wǎng)絡(luò)時間同步概述安竹林 朱冠男 徐勇軍摘要：時間同步服務(wù)是無線傳感器網(wǎng)絡(luò)要解決的一項關(guān)鍵問題。本文對時間同步技術(shù)進行了介紹，分析了無線傳感器網(wǎng)絡(luò)時間同步所具有的特點。文章還介紹了幾種典型的用于無線傳感網(wǎng)絡(luò)的時間同步協(xié)議并對其優(yōu)缺點做了簡單比較。最后，本文對時間同步目前的研究現(xiàn)狀進行了總結(jié)，并對今后的發(fā)展進行了展望。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；時間同步1 時間同步問題簡述時間同步是所有分布式系統(tǒng)都要解決的一個重要問題。在集中式系統(tǒng)中，由于任何進程或模塊都可以從系統(tǒng)唯一的全局時鐘中獲取時間，因此系統(tǒng)內(nèi)任何兩個事件都有著明確的先后關(guān)系。而在分布式系統(tǒng)中，由于物理上的分散性，系統(tǒng)無法為彼此間相互

2、獨立的模塊提供一個統(tǒng)一的全局時鐘，必須由各個進程或模塊各自維護它們的本地時鐘。由于這些本地時鐘的計時速率、運行環(huán)境存在不一致性，因此即使所有的本地時鐘在某一時刻都被校準，一段時間后，這些本地時鐘間也會出現(xiàn)失步。為了讓這些本地時鐘再次達到相同的時間值，必須進行時間同步操作。時間同步就是通過對本地時鐘的某些操作，達到為分布式系統(tǒng)提供一個統(tǒng)一時間標度的過程。無線傳感器網(wǎng)絡(luò)是聯(lián)系物理世界和計算機系統(tǒng)的橋梁，對物理世界的觀測必須建立在統(tǒng)一的時間標度上，因此相對于通常的分布式系統(tǒng)，無線傳感器網(wǎng)絡(luò)對時間同步的需求尤為重要，可以說時間同步是無線傳感器網(wǎng)絡(luò)的一項支撐技術(shù)。2 無線傳感器網(wǎng)絡(luò)時間同步問題特點時間同

3、步是所有分布式系統(tǒng)都需要解決的問題，因此對其研究已經(jīng)較為深入，有許多成熟的方法被成功地應(yīng)用于解決這一問題，有代表性的解決方法有NTP Network time protocol，網(wǎng)絡(luò)時間協(xié)議和GPS Global Positioning System，全球定位系統(tǒng)。NTP協(xié)議1是目前互聯(lián)網(wǎng)上時間同步協(xié)議的標準，用于把互聯(lián)網(wǎng)上計算機的時間同步于世界標準時間（UTC Coordinated Universal Time，又稱協(xié)調(diào)世界時）。NTP采用層狀結(jié)構(gòu)的同步拓撲，每一層均有若干時間服務(wù)器，如頂層時間服務(wù)器，第二層時間服務(wù)器等，其他均為客戶機。頂層時間服務(wù)器通過廣播、衛(wèi)星等方式與世界標準時間同步

4、；其他層的時間服務(wù)器可選擇若干個上一層時間服務(wù)器及本層時間服務(wù)器作為同步源來實現(xiàn)與世界標準時間的間接同步；客戶機則可通過指定一個或多個上一層時間服務(wù)器來實現(xiàn)與世界標準時間的同步?？梢钥闯觯篘TP協(xié)議的可靠性依賴于時間服務(wù)器的冗余性和時間獲取路徑的多樣性。GPS是由美國國防部為滿足軍事部門對海陸空設(shè)施進行高精度導(dǎo)航和定位的需要而建立的。它由三部分構(gòu)成，分別為空間星座部分、地面監(jiān)控部分和用戶設(shè)備部分。空間部分是由若干顆GPS 工作衛(wèi)星所組成的，每顆衛(wèi)星裝置有精密的銣、銫原子鐘，并由監(jiān)控站經(jīng)常進行校準，達到和世界標準時間的同步。每顆衛(wèi)星不斷發(fā)射包含其位置和精確到十億分之一秒的時間的數(shù)字無線電信號用于

5、接收設(shè)備的時間校準。GPS接收裝置接收到來自于四顆或四顆以上衛(wèi)星的信號，根據(jù)偽距測量定位方法不僅可以計算出其在地球上的位置，而且也可計算出GPS接收機時間與世界標準時間之偏差，并進行時間校準，達到與世界標準時間的同步。這種方法的同步精度可達100納秒。NTP和GPS盡管在技術(shù)上已經(jīng)很成熟，但是卻無法直接應(yīng)用于無線傳感器網(wǎng)絡(luò)的時間同步，這是由于無線傳感器網(wǎng)絡(luò)具有其自身的特點，必須考慮以下因素：(1). 傳輸延遲的不確定性報文傳輸延遲的不確定性是無線傳感器網(wǎng)絡(luò)時間同步的主要挑戰(zhàn)之一。一方面?zhèn)鬏斞舆t比要求的時間同步允許的誤差大得多，另一方面它極易受到處理器負載、網(wǎng)絡(luò)負載等因素的影響。通常，報文的傳輸

6、延遲可分為：發(fā)送前處理時間（Send time 發(fā)送前將數(shù)據(jù)流處理成適于發(fā)射的信號流（消息的碼流）所用的時間）、排隊時間（Access time 等候發(fā)射信道時間）、發(fā)送時間（Transmission time 信號流從頭至尾從發(fā)射機發(fā)射所占用的時間）、傳播時間（Propagation time 信號在介質(zhì)中從發(fā)射端傳播到接收端所用的時間）、接收時間（Reception time 信號流從頭至尾被接收占用的時間）、收到后處理時間（Received time 收到信號后將碼流處理成應(yīng)用程序所需數(shù)據(jù)流的時間）。傳輸延遲的不確定性嚴重影響了同步精度，因此需要對傳輸延遲仔細地測量、分析和補償才能設(shè)計出

7、高精度的時間同步協(xié)議。(2). 對低功耗、低成本與小體積的要求低功耗、低成本與小體積的要求對無線傳感器網(wǎng)絡(luò)軟硬件設(shè)計的各個方面均提出挑戰(zhàn)。無線傳感器網(wǎng)絡(luò)強調(diào)低功耗，在設(shè)計時間同步軟硬件時必須遵循該原則。例如：對用于時間同步的硬件來說，類似于GPS接收機這樣的高耗能、高成本設(shè)備是不合適的。對時間同步軟件來說，雖然提高同步操作的頻率能夠提高同步精度，但必然引起同步功耗的增加，因此完全依靠提高同步操作頻率來提高同步精度的方法也是不合適的。低成本和小體積更是加劇了電能供應(yīng)的緊張趨勢。(3). 對可擴展性的要求無線傳感器網(wǎng)絡(luò)時間同步協(xié)議會隨著網(wǎng)絡(luò)規(guī)模的擴大而出現(xiàn)同步精度劣化現(xiàn)象，即同步誤差隨著網(wǎng)絡(luò)規(guī)模的

8、擴大而增長，并最終導(dǎo)致同步誤差越界。網(wǎng)絡(luò)規(guī)模的擴大還會引起時間同步協(xié)議其他方面性能的下降，甚至不能正常工作。如何設(shè)計時間同步協(xié)議，使得其在大規(guī)模網(wǎng)絡(luò)中不僅能正常工作，而且能保持較好的性能，即具有強的可擴展性。這是大規(guī)模無線傳感器網(wǎng)絡(luò)時間同步需要考慮的主要問題之一。(4). 對健壯性的要求在互聯(lián)網(wǎng)環(huán)境下，盡管NTP協(xié)議有時會遇到短暫的鏈路失敗，但仍然能正常工作。這是因為NTP協(xié)議被手動配置了多個時間服務(wù)器，因此具有較強的健壯性。在無線傳感器網(wǎng)絡(luò)中，節(jié)點的移動、故障及外界環(huán)境的變化等多種因素都會導(dǎo)致無線傳感器網(wǎng)絡(luò)的高度動態(tài)性。靜態(tài)配置方案并不能應(yīng)對網(wǎng)絡(luò)的高度動態(tài)性。時間同步協(xié)議必須能夠?qū)@些情況進

9、行處理，以保證系統(tǒng)的健壯性。3 典型無線傳感器網(wǎng)絡(luò)時間同步算法3.1 用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議（TPSN） Timing-sync Protocol for Sensor Networks最易于想到的同步方法為：發(fā)送者在同步報文中嵌入其本地時間，在接收到該報文后，接收者立即把自己的本地時間設(shè)置為嵌在該報文中的時間。但這種方法沒有考慮到報文的傳輸延遲。而延遲測量時間同步協(xié)議（DMTS，Delay Measurement Time Synchronization）2在此方法的基礎(chǔ)上，進一步考慮了報文的傳輸延遲，接收者測量報文的傳輸延遲，并將本地時間設(shè)置為發(fā)送時刻加上報文傳輸延遲。延遲測量時間同

10、步協(xié)議簡單，但同步精度不高。美國加州大學(xué)洛杉磯分校（UCLA）聯(lián)網(wǎng)和嵌入式系統(tǒng)實驗室（NESL, Networked and Embedded Systems）的甘納瑞沃爾（S.Ganeriwal）指出3：傳統(tǒng)的發(fā)送者-接收者同步協(xié)議的同步精度較低的根源在于基于單向報文所估算出的報文傳播延遲不夠精確。如果采用雙向報文，基于報文傳輸?shù)膶ΨQ性，有可能精確地計算出報文的傳輸延遲，圖1 NTP協(xié)議的雙向報文交換因此能獲得更高的同步精度。為此，他引入了NTP協(xié)議中的雙向報文交換協(xié)議（如圖1所示），提出了用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議。圖中的T1、T4用節(jié)點A的本地時間記錄，T2、T3用節(jié)點B的本地時間記錄

11、。節(jié)點A向節(jié)點B發(fā)送一個同步請求報文。節(jié)點B在接收到該報文后，記錄下接收到時刻T2，并立即向節(jié)點A返回一個同步應(yīng)答報文，并把T2和該報文的發(fā)送時刻T3嵌入在報文中。當節(jié)點A接收到該報文時，記錄下接收到時刻T4。令為當節(jié)點A的本地時刻為T1時，節(jié)點A和B之間的時偏。由于T1T4時間比較短，可認為當節(jié)點A的本地時刻為T4時，其與節(jié)點B之間的時偏沒有變化。假設(shè)報文的傳輸延遲相同，均為d。由：，可得：，。因此在T4時刻，若在節(jié)點A的本地時間上增加修正量，就達到和節(jié)點B之間的瞬時的時間同步。用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議將NTP時間同步方法引入無線傳感器網(wǎng)絡(luò)，可以獲得比使用延遲測量時間同步協(xié)議更高的精度，

12、但是其計算較為復(fù)雜，功耗較大，并且同步精度受到報文的傳輸延遲的影響；同時如果報文的雙向傳輸不對稱，同步精度也會受到影響。3.2 輕量基于樹形分布的同步算法（LTS） Lightweight Tree-based SynchronizationLTS同步算法4是一種與TPSN非常類似的算法。無線傳感器網(wǎng)絡(luò)通常只具有非常有限的計算資源，但是其并不要求非常高的時間同步精度。針對無線傳感器網(wǎng)絡(luò)的這一特點，LTS側(cè)重于降低時間同步的復(fù)雜度，在有限的計算代價下獲得合理的同步精度。LTS有集中式和分布式兩個版本，在集中式版本中，首先以時間參考節(jié)點為根建立生成樹，然后從樹根開始逐級向葉子節(jié)點進行同步：首先根節(jié)

13、點同步其子節(jié)點，然后這些子節(jié)點再分別同步其子節(jié)點，如此繼續(xù)下去，直到全部節(jié)點都被同步。另外，為了達到最高的同步精度，要求生成樹的深度盡可能的小，文4給出了Distributed depth first search (DDFS)和Echo兩種生成樹算法。在分布式版本中，任何節(jié)點都可以發(fā)起同步過程，不需要建立生成樹，但是每個節(jié)點都必須知道參考節(jié)點的位置，并且知道其到這些節(jié)點的路徑。節(jié)點根據(jù)自己的時鐘漂移確定需要同步的時間，需要同步時，節(jié)點選擇距離自己最近的一個參考節(jié)點，并向其發(fā)出同步請求，然后參考節(jié)點向該節(jié)點的路徑上的節(jié)點逐對進行同步，直到該節(jié)點被同步。LTS算法與TPSN協(xié)議的區(qū)別在于，LTS

14、算法中節(jié)點只與自己的父節(jié)點進行同步，其同步次數(shù)是路徑長度的線性函數(shù)，同時精度也隨路徑的長度線性降低，即在降低計算代價的同時降低了同步精度。3.3 參考廣播時鐘同步協(xié)議（RBS） Reference Broadcast Synchronization用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議可以看作是NTP在無線傳感器網(wǎng)絡(luò)上的改進版本，而無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳播介質(zhì)是無線信道，能否利用無線信道的廣播特性設(shè)計相關(guān)的時間同步算法呢？參考廣播時鐘同步協(xié)議所依據(jù)的就是這樣的算法5。與用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議不同，參考廣播時鐘同步協(xié)議不是去同步報文的收發(fā)雙方，而是去同步報文的多個接收者。如圖2的右圖所示：在由3個節(jié)

15、點組成的單跳網(wǎng)絡(luò)中，參考節(jié)點每發(fā)出一個參考報文，其廣播域內(nèi)的其他接收者節(jié)點都將接收到該報文，并各自記錄下接收到該參考報文時的本地時刻。接收者們交換它們記錄的時刻并計算差值，該差值就是接收者之間的時鐘偏移。圖2 發(fā)送者-接收者同步機制與接收者-接收者同步機制根據(jù)偏移信息可以實現(xiàn)發(fā)送者-接收者同步，若能精確地估計出報文傳輸延遲，這種方法將能夠取得很高的精度。然而僅根據(jù)單個報文的傳輸很難準確地估計出傳輸延遲。圖2的左圖為發(fā)送者-接收者同步機制?？梢钥闯?，發(fā)送者-接收者同步機制的同步關(guān)鍵路徑為從發(fā)送方到接收方。關(guān)鍵路徑過長，導(dǎo)致傳輸延遲不確定性的增加，因此同步精度不可能很高。右圖則是接收者-接收者同步

16、機制，其關(guān)鍵路徑大為縮短，完全排除了發(fā)送時間和訪問時間的影響。3.4 層級時間同步協(xié)議（HRTS） Hierarchy Referencing Time Synchronization Protocol基于雙向報文交換的用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議具有同步精度高的優(yōu)點，但一次只能同步一對節(jié)點。n個節(jié)點的單跳網(wǎng)絡(luò)則需要n-1次同步操作，同步功耗較大。參考廣播時鐘同步協(xié)議只需要一次同步過程就可完成一個單跳網(wǎng)內(nèi)所有節(jié)點間的同步，同步功耗降低，當然，同步精度也相對變差。層級時間同步協(xié)議6是一種結(jié)合用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議和參考廣播時鐘同步協(xié)議思想的同步方法。圖3描述了層級時間同步的過程。假設(shè)單跳網(wǎng)

17、絡(luò)有包含時間基準節(jié)點在內(nèi)的3個節(jié)點BS、n1和n2。同步步驟如下：步驟1：參見圖3，時間基準節(jié)點BS相當前面圖1中的A節(jié)點，按照與用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議相同的同步方式，時間基準節(jié)點BS發(fā)出一個同步請求報文，該報文隨機指定一個鄰居節(jié)點（例如n1）作為應(yīng)答者節(jié)點（即對應(yīng)于圖1中的B節(jié)點）。同時n2也記錄下該報文的接收到時刻，記為。步驟2：與用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議對同步方式相同，應(yīng)答者節(jié)點n1向BS節(jié)點發(fā)一個同步應(yīng)答報文，報文中包含了與。步驟3：現(xiàn)在BS節(jié)點已經(jīng)和n1節(jié)點進行了一次雙向報文交換，按照用于傳感器網(wǎng)絡(luò)的時間同步協(xié)議，BS節(jié)點計算出它與n1節(jié)點之間的時鐘偏移。步驟4：BS節(jié)點發(fā)

18、送一個包含和信息的報文。步驟5：當n1、n2節(jié)點接收到該報文，對于應(yīng)答者節(jié)點n1來說，只要將其本地時間減去就達到與BS節(jié)點的瞬時同步。對于其他節(jié)點來說，只要在其本地時間加上即可達到與BS節(jié)點間的瞬時同步層級時間同步協(xié)議充分利用了無線傳輸?shù)膹V播特性來進一步降低LTS協(xié)議的同步功耗。和LTS協(xié)議不同，基本同步單元不再是廣度優(yōu)先生成樹的邊，而是廣度優(yōu)先生成樹 Breadth First Spanning Tree，亦有譯作“橫向擴張樹”的中非葉子節(jié)點的單跳廣播區(qū)域。同步次數(shù)是圖3 層級時間同步協(xié)議同步過程廣度優(yōu)先生成樹非葉子節(jié)點個數(shù)的線性函數(shù)，因此降低了同步功耗。但在同步精度上，層級時間同步協(xié)議略遜

19、于LTS協(xié)議。3.5 Tiny-Sync/Mini-SyncTiny-Sync和Mini-Sync7是兩種適用于無線傳感器網(wǎng)絡(luò)的輕量級時間同步算法。該算法基于一個假設(shè)：傳感器網(wǎng)絡(luò)中的時鐘頻率恒定且線性相關(guān)。即對于時鐘、有其中a12為相對時鐘漂移，b12為相對時鐘偏移。算法采用雙向報文交換來估計相對時鐘漂移和相對時鐘偏移，如圖4所示。首先節(jié)點1向節(jié)點2發(fā)送一個探測數(shù)據(jù)包，并加入發(fā)送時刻的本地時間；節(jié)點2收到該數(shù)據(jù)包后，立即返回給節(jié)點1一個數(shù)據(jù)包，其中包含收到探測數(shù)據(jù)包的本地時間圖4 Tiny-Sync和Mini-Sync的雙向報文交換；最后，當節(jié)點1收到節(jié)點2發(fā)回的數(shù)據(jù)包時記錄本地時間。通過這三

20、個時間戳的絕對位置，可以得到：三個時間戳組成的三元組(,)稱作一個數(shù)據(jù)點。算法通過不斷地收集這樣的數(shù)據(jù)點估計a12和b12，并且隨著數(shù)據(jù)點個數(shù)的增加，算法的精度不斷提高。如圖5所示，每個數(shù)據(jù)點對應(yīng)于兩個約束（,）和（,）。注意到a12、b12對應(yīng)的直線必定在所有的數(shù)據(jù)點對之間，因此圖中最陡的和最緩的兩條虛線給出了a12、b12的上下界。并且上下界的區(qū)間越小，精度越高。通過求解所有數(shù)據(jù)點約束下的線性規(guī)劃問題，別可以得到最優(yōu)解。但是，這種方法太過復(fù)雜，無法在計算資源有限的無線傳感器網(wǎng)絡(luò)中實現(xiàn)。通過觀察可以發(fā)現(xiàn)，計算上下界時并不需要所有數(shù)據(jù)點。如圖5所示，上下界其實只由第1、3個數(shù)據(jù)點確定。Tiny

21、-Sync算法就利用了這一點，而只保存確定最優(yōu)邊界的4個約束點，因此降低了計算復(fù)雜度。但是，這種方法并不能總是給出最優(yōu)的上下界，在某些情況下算法可能會丟棄一些給出最優(yōu)上下界的點。Mini-Sync是對Tiny-Sync的擴展，其思路是防止算法丟棄可能在未來能夠給出更小的上下界的數(shù)據(jù)點，作者給出了一個標準來判斷是否一個約束有可能會被用于計算最優(yōu)邊界，而只在確認某一個約束不會被用到的時候才將其丟棄。這樣圖5 Tiny-Sync/Mini-Sync算法中數(shù)據(jù)點對時鐘漂移和時鐘偏移的約束在提高了計算復(fù)雜度的情況下保證能夠找到最優(yōu)解。Tiny-Sync和Mini-Sync這兩個算法，非常符合無線傳感器網(wǎng)

22、絡(luò)的要求，即所需存儲空間和計算資源非常少，同時對帶寬的要求也很小。但這種算法的假設(shè)條件（傳感器網(wǎng)絡(luò)節(jié)點時鐘的漂移和偏移恒定）在低成本的傳感器網(wǎng)絡(luò)節(jié)點上是很難達到的。4 總結(jié)與展望本文介紹了無線傳感器網(wǎng)絡(luò)時間同步的特點以及一些時間同步算法。不同于其他網(wǎng)絡(luò)，在無線傳感器網(wǎng)絡(luò)中，時間同步不僅要關(guān)注同步精度，還需要關(guān)注同步能耗、可擴展性和健壯性需求。典型的時間同步協(xié)議側(cè)重于同步精度和同步能耗的需求，采用時鐘飄移補償、介質(zhì)訪問控制（MAC）層時間戳技術(shù)以及雙向報文交換來提高同步精度，充分利用無線傳輸?shù)膹V播特性和捎帶技術(shù)來降低同步能耗。本文介紹的這些算法很多都已經(jīng)很成熟，在單跳網(wǎng)絡(luò)中已經(jīng)具有很強的工程實用

23、性。同步誤差在Mica2平臺上已經(jīng)達到幾微秒至十幾微秒的量級，同步功耗也較低，能夠滿足大多數(shù)應(yīng)用場合的需要。然而，當這些時間同步協(xié)議被擴展到多跳網(wǎng)絡(luò)時，會出現(xiàn)累計誤差較大、擴展性較差等問題。時間同步是無線傳感器網(wǎng)絡(luò)的基礎(chǔ)性中間件，其特性直接決定或影響著其他中間件或應(yīng)用的質(zhì)量與特性。提高同步精度、降低同步能耗、提高可擴展性及健壯性是無線傳感器網(wǎng)絡(luò)時間同步下一步的研究方向。參考文獻1 L., M.D., Network time protocol (Version3) specification, implementation and analysis. 1992, University of Delaware, DARPA Network Working Group.2 Ping, S., Delay Measurement Time Synchronization for Wireless Sensor Networks. 2003, Intel Research.3 Saurabh, G., K. Ram, and B.S. Mani, Timing-sync protocol for sensor networks, in Proceedings of the 1st international confe