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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、性。同步誤差在Mica2平臺(tái)上已經(jīng)達(dá)到幾微秒至十幾微秒的量級(jí)，同步功耗也較低，能夠滿足大多數(shù)應(yīng)用場(chǎng)合的需要。然而，當(dāng)這些時(shí)間同步協(xié)議被擴(kuò)展到多跳網(wǎng)絡(luò)時(shí)，會(huì)出現(xiàn)累計(jì)誤差較大、擴(kuò)展性較差等問(wèn)題。時(shí)間同步是無(wú)線傳感器網(wǎng)絡(luò)的基礎(chǔ)性中間件，其特性直接決定或影響著其他中間件或應(yīng)用的質(zhì)量與特性。提高同步精度、降低同步能耗、提高可擴(kuò)展性及健壯性是無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步下一步的研究方向。參考文獻(xiàn)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