無線傳感網(wǎng)絡(luò)中時(shí)間同步技術(shù)綜述

1、無線傳感網(wǎng)絡(luò)中時(shí)間同步技術(shù)綜述Sami M. Lasassmeh and James M. ConradElectrical and Computer Engineering Department, University of North Carolina at Charlotte, NC, USA摘要：無線傳感網(wǎng)絡(luò)是由分散在全球各區(qū)域的小設(shè)備組成，這些小設(shè)備都具有感知，計(jì)算和通信功能，當(dāng)網(wǎng)絡(luò)中需要partial time sy和full time sy時(shí)，無線傳感網(wǎng)絡(luò)就會(huì)被應(yīng)用。時(shí)間同步技術(shù)的目的在于在必要的時(shí)候?qū)⑷W(wǎng)的所有節(jié)點(diǎn)與當(dāng)?shù)貢r(shí)間整合一致，因?yàn)闊o線傳感網(wǎng)絡(luò)在能源，計(jì)算容量，存儲(chǔ)量和帶

2、寬方面很有限，所以傳統(tǒng)的算法如NTP和GPS在同步全網(wǎng)的時(shí)候就顯得不實(shí)用。這篇文章將介紹無線傳感網(wǎng)絡(luò)中時(shí)間同步存在的問題以及在這一領(lǐng)域中提出的一些基本算法。5 / 51 引言無線網(wǎng)絡(luò)由空間上離散分布在不同地域的自動(dòng)裝置組成，這些裝置通常用來監(jiān)控溫度，聲音，振動(dòng)，壓力，運(yùn)動(dòng)和污染等數(shù)據(jù)2，10。這種裝置通常都有感應(yīng)部件，無線通信收發(fā)器，計(jì)算回路，數(shù)據(jù)網(wǎng)以及電源（通常是電池）4。傳感器網(wǎng)絡(luò)是一種特殊的ad-hoc網(wǎng)絡(luò)，在傳感器網(wǎng)絡(luò)中，無線設(shè)備（通常指的是網(wǎng)絡(luò)中的節(jié)點(diǎn)）可以在沒有基礎(chǔ)的網(wǎng)絡(luò)構(gòu)造的情況下自發(fā)地一起工作形成網(wǎng)絡(luò)12。節(jié)點(diǎn)可以收發(fā)數(shù)據(jù)，或者作為數(shù)據(jù)傳輸?shù)穆窂健＞W(wǎng)絡(luò)節(jié)點(diǎn)通常是靜態(tài)的，并且是資

3、源受限的，它們把數(shù)據(jù)搜集起來并且形成一個(gè)叫做sink的中心單元，用于后續(xù)運(yùn)算。整個(gè)傳感器網(wǎng)絡(luò)的運(yùn)行時(shí)間（常常通過耗盡電量的無線節(jié)點(diǎn)的百分比來定義，而不是指的一個(gè)設(shè)備的運(yùn)行時(shí)間）是評(píng)估網(wǎng)絡(luò)性能的主要參數(shù)之一。傳感器必須要設(shè)計(jì)的能夠經(jīng)得住惡劣的環(huán)境和地質(zhì)條件。通常配備多余的后備設(shè)備或者傳感器以應(yīng)對(duì)設(shè)備無法工作的情形（如硬件故障，電池電量耗盡等）。時(shí)間同步的目的是在網(wǎng)絡(luò)中建立一個(gè)時(shí)標(biāo)，它在很多應(yīng)用中都是必要的技術(shù)。介質(zhì)訪問控制技術(shù)，如TDMA就需要時(shí)間同步技術(shù)來實(shí)現(xiàn)精確的沒有沖突的介質(zhì)訪問的規(guī)劃。另外，無線傳感網(wǎng)絡(luò)的電源有限，因此為降低整個(gè)網(wǎng)絡(luò)的能耗就要用到節(jié)電技術(shù)。為了使節(jié)點(diǎn)能在準(zhǔn)確的時(shí)間開關(guān)收發(fā)

4、設(shè)備，就要用到網(wǎng)絡(luò)節(jié)點(diǎn)之間的精確的時(shí)間調(diào)整技術(shù)。在很多應(yīng)用中還引入了數(shù)據(jù)融合。在不同節(jié)點(diǎn)搜集的數(shù)據(jù)將被會(huì)聚然后發(fā)送到sink節(jié)點(diǎn)，以便做出決斷。這些節(jié)點(diǎn)相互之間合作協(xié)調(diào)來完成這一任務(wù)。項(xiàng)目表探測(cè)這樣的應(yīng)用技術(shù)，需要精確的時(shí)間整合來對(duì)事件進(jìn)行準(zhǔn)確的估計(jì)。在有線網(wǎng)絡(luò)中已經(jīng)得到應(yīng)用的傳統(tǒng)的時(shí)間同步技術(shù)并不適用于無線網(wǎng)絡(luò)。在互聯(lián)網(wǎng)中得到廣泛應(yīng)用的NTP技術(shù)8的開始過程過于復(fù)雜，并且能耗較大。另一方面，因?yàn)榘惭b在網(wǎng)絡(luò)節(jié)點(diǎn)上的設(shè)備過于龐大和接近所以GPS技術(shù)也不適，而且，因?yàn)閭鞲衅魍ǔ１话惭b在惡劣的環(huán)境下，GPS信號(hào)還常常無法到達(dá)。下面的論述將以如下方式展開：第二部分我們將論述計(jì)算機(jī)時(shí)鐘是如何工作的，并且

5、解釋時(shí)間同步的資源和需求，第三部分詳細(xì)介紹時(shí)間同步的方法，TTS,RBS,TPSN,Tiny-Sync,Mini-Sync,以及基于樹時(shí)間同步的算法。2 同步問題A.計(jì)算機(jī)時(shí)鐘計(jì)算機(jī)時(shí)鐘回路由振蕩器和計(jì)時(shí)器組成，計(jì)時(shí)器將基于為振蕩器的角頻率來增加代表當(dāng)?shù)貢r(shí)鐘的網(wǎng)絡(luò)節(jié)點(diǎn)的C（t）的數(shù)值。在理想情況下，角頻率是恒定的。因此時(shí)鐘的變化率A等于1.計(jì)算機(jī)時(shí)鐘隨諸如溫度，振動(dòng)，壓力和角頻率的變化而擺動(dòng)節(jié)點(diǎn)i的本地時(shí)鐘將隨實(shí)時(shí)數(shù)據(jù)t作如下變化： Cit=ait+bi (1)這里a表示時(shí)鐘的變化綠，b是關(guān)于節(jié)點(diǎn)i的時(shí)鐘的設(shè)定。變化率表示了時(shí)鐘頻率的變化比率，設(shè)定值表示了數(shù)值與實(shí)時(shí)數(shù)據(jù)的差異。從方程（1）我們

6、比較在一個(gè)網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)，可以向文獻(xiàn)11中稱它們?yōu)楣?jié)點(diǎn)1和節(jié)點(diǎn)2。 C1t=a12.C2t+b12 (2)我們稱a為節(jié)點(diǎn)1時(shí)鐘和節(jié)點(diǎn)2時(shí)鐘的相對(duì)漂移，b為節(jié)點(diǎn)1時(shí)鐘和節(jié)點(diǎn)2時(shí)鐘的相對(duì)設(shè)定。如果兩個(gè)始終能夠完全同步，那么它們的相對(duì)漂移就為1，表示這兩個(gè)時(shí)鐘擁有相同的變化率。它們的相對(duì)設(shè)定值為0，表示他們?cè)谶@一時(shí)刻具有相同的數(shù)值12?；谇懊娴牡仁?，網(wǎng)絡(luò)節(jié)點(diǎn)的時(shí)鐘變化率和始終設(shè)定可以用來調(diào)整當(dāng)?shù)貢r(shí)間，很多方案都設(shè)計(jì)成不斷重復(fù)調(diào)整節(jié)點(diǎn)設(shè)定值，或者是調(diào)整節(jié)點(diǎn)設(shè)定值和變化率到一個(gè)共同的時(shí)標(biāo)。B.同步錯(cuò)誤的原因信息交換在很多時(shí)間同步算法中都得到了應(yīng)用，如果一個(gè)節(jié)點(diǎn)發(fā)送了一個(gè)帶有時(shí)間戳的信息包，不確定的像

7、訪問或廣播時(shí)間這樣的延時(shí)接收節(jié)點(diǎn)很難與發(fā)送節(jié)點(diǎn)準(zhǔn)確地同步?？傮w上，產(chǎn)生同步錯(cuò)誤的因素主要包括:精確度：同步技術(shù)的準(zhǔn)確性高度依賴于設(shè)備魯棒性：網(wǎng)絡(luò)節(jié)點(diǎn)可能會(huì)被破壞或者退出運(yùn)行，因?yàn)樗鼈冞\(yùn)行的環(huán)境很惡劣。任何同步技術(shù)的設(shè)計(jì)都應(yīng)該適應(yīng)這種變化，并且能在各種情形下運(yùn)行?？蓴U(kuò)展性：很多實(shí)際應(yīng)用中，可能會(huì)有成千上萬的傳感器，任何同步技術(shù)都應(yīng)該保證無論多少節(jié)點(diǎn)，都能很好地運(yùn)行。壽命：假設(shè)同步可能是瞬間發(fā)生的，與具體應(yīng)用有關(guān)，比如確定的某事件發(fā)生時(shí)，或者一旦網(wǎng)絡(luò)開始運(yùn)行就同步。電源效率：網(wǎng)絡(luò)節(jié)點(diǎn)的能源有限，包括同步技術(shù)在內(nèi)的所有的網(wǎng)絡(luò)協(xié)議都要考慮到這一點(diǎn)。費(fèi)用：由于技術(shù)的進(jìn)步，網(wǎng)絡(luò)節(jié)點(diǎn)變得小而便宜，任何同步算

8、法都不能增加費(fèi)用或者增大網(wǎng)絡(luò)規(guī)模。范圍：時(shí)間同步算法為所有節(jié)點(diǎn)提供了一個(gè)共同的時(shí)間，但這種方法將耗費(fèi)更多的能源和時(shí)間，另一種方法是可以只為在空間上靠得近的節(jié)點(diǎn)提供共同的時(shí)間。延時(shí)：很多設(shè)備，像漏氣監(jiān)測(cè)，需要即時(shí)反應(yīng)。這樣的設(shè)備，同步所需的時(shí)間要盡量低。3 無線傳感網(wǎng)絡(luò)的同步方法同步任務(wù)的目的在于調(diào)整網(wǎng)絡(luò)中的所有節(jié)點(diǎn)的時(shí)間與參考值一致，最嚴(yán)格有力的同步方法要求所有節(jié)點(diǎn)在所有時(shí)間同步，而其它要求寬松一點(diǎn)的方法則要求某些節(jié)點(diǎn)一段時(shí)間同步。A.傳統(tǒng)的時(shí)間同步（TTS）傳統(tǒng)的網(wǎng)絡(luò)節(jié)點(diǎn)時(shí)間同步的方案（如網(wǎng)絡(luò)時(shí)間協(xié)議）是基于收發(fā)信息而實(shí)現(xiàn)的，最簡(jiǎn)單的形式就是發(fā)送方向接收方發(fā)送帶有實(shí)時(shí)當(dāng)?shù)貢r(shí)間的信息，然后接收

9、方根據(jù)收到的信息調(diào)整自己的時(shí)鐘。在相對(duì)于本地時(shí)間所要求的精度下收發(fā)信息的延時(shí)可以忽略不及的情況下，這種方案可以很好地實(shí)現(xiàn)同步，如果收發(fā)的延時(shí)很長(zhǎng)，發(fā)送方就要求接收方立即回復(fù)，節(jié)點(diǎn)就可以計(jì)算信息在一個(gè)來回所需的時(shí)間，并且將這一時(shí)間應(yīng)用在與其它節(jié)點(diǎn)同步的時(shí)候。B.廣播參考同步(RBS)在文獻(xiàn)1中，介紹了接收器與接收器而非接收器與發(fā)送器的同步，在這種情況下，介紹了RBS。節(jié)點(diǎn)通過廣播方式發(fā)送信標(biāo)，其他節(jié)點(diǎn)應(yīng)用這些到達(dá)的信標(biāo)作為參考來重新設(shè)定它們的時(shí)間。這一算法主要是去改變不確定的傳送來的時(shí)間。這一方案的主要誤差來源在于不確定的接受和發(fā)送的次數(shù)，如果假設(shè)射頻距離很短，并且是表示向所有的節(jié)點(diǎn)同時(shí)廣播，那

10、么發(fā)送誤差可以忽略。所以這一誤差的唯一來源就在與接收時(shí)間。典型的通信方案是一個(gè)節(jié)點(diǎn)向相鄰節(jié)點(diǎn)發(fā)送時(shí)標(biāo)，接收方通過自己的時(shí)間與時(shí)標(biāo)差異的交換尋找相關(guān)的時(shí)間設(shè)定，然后相互之間進(jìn)行時(shí)間同步。發(fā)送的時(shí)標(biāo)越多，同步就越精確。用這項(xiàng)技術(shù)可以達(dá)到微秒的精確度，在流行的平臺(tái)Berkley上可以達(dá)到11微秒的精確度。而這種算法也被應(yīng)用在Linux上來通過802.11協(xié)議通信，而精確度也能達(dá)到6.29±6.45微秒。 C.無線傳感網(wǎng)絡(luò)的時(shí)間同步協(xié)議（TPSN）TPSN在文獻(xiàn)6中被提出。這種同步技術(shù)有兩個(gè)階段，在發(fā)現(xiàn)階段（第一階段），每個(gè)節(jié)點(diǎn)都會(huì)被設(shè)定一個(gè)層次編號(hào)。只有一個(gè)節(jié)點(diǎn)被編號(hào)為0，稱為根節(jié)點(diǎn)。在第

11、二階段，層次編號(hào)為n的節(jié)點(diǎn)依次與層次編號(hào)為n-1的節(jié)點(diǎn)同步，這樣下去，最終整個(gè)網(wǎng)絡(luò)將達(dá)到同步。節(jié)點(diǎn)發(fā)現(xiàn)階段：這一階段的第一步是選根節(jié)點(diǎn)，網(wǎng)絡(luò)中的節(jié)點(diǎn)可以定期地選出一個(gè)節(jié)點(diǎn)，然后將層次編號(hào)為0.這一節(jié)點(diǎn)可以與外部的時(shí)間參考（如GPS）相連。然后向其它節(jié)點(diǎn)發(fā)送發(fā)現(xiàn)數(shù)據(jù)包，接收到數(shù)據(jù)包的節(jié)點(diǎn)將自己層次編號(hào)為1，然后再向剩下的節(jié)點(diǎn)發(fā)送包括它們層次編號(hào)的數(shù)據(jù)包，直到所有節(jié)點(diǎn)都完成層次編號(hào)。同步階段：根節(jié)點(diǎn)通過再一次發(fā)送時(shí)間同步數(shù)據(jù)包開始時(shí)間同步階段。層次編號(hào)為n的節(jié)點(diǎn)A通過雙向數(shù)據(jù)交換與層次編號(hào)為n-1的節(jié)點(diǎn)B完成同步。節(jié)點(diǎn)A發(fā)送一個(gè)帶有當(dāng)?shù)貢r(shí)間T1的數(shù)據(jù)包，節(jié)點(diǎn)B在時(shí)間T2收到這一數(shù)據(jù)包，T2可以通過

12、如下方式計(jì)算：T2=T1+Td+ (3)上式Td是廣播延時(shí)，是節(jié)點(diǎn)與假設(shè)恒定情況下信息交換的相關(guān)時(shí)鐘漂移。節(jié)點(diǎn)B在一個(gè)隨機(jī)時(shí)刻T3向節(jié)點(diǎn)A發(fā)送一個(gè)包含T1,T2,T3和它的層次編號(hào)的確認(rèn)數(shù)據(jù)包。節(jié)點(diǎn)A在時(shí)間T4收到數(shù)據(jù)包的時(shí)候，可以通過文獻(xiàn)6的方法計(jì)算計(jì)算和Td，然后與節(jié)點(diǎn)B同步。=T2-T1-T4-T32;Td=T2-T1+(T4-T3)2(4)這種在層次編號(hào)n的節(jié)點(diǎn)到層次編號(hào)n-1的節(jié)點(diǎn)之間的同步方法在每一個(gè)節(jié)點(diǎn)上持續(xù)進(jìn)行，整個(gè)網(wǎng)絡(luò)就會(huì)實(shí)現(xiàn)同步。將TPSN和RBS作比較，這兩種算法都應(yīng)用在Mica平臺(tái)。數(shù)據(jù)顯示在相同的實(shí)驗(yàn)設(shè)定下RBS達(dá)到了29.13微秒的精度，而TPSN達(dá)到了16.9微秒

13、的精度。這些結(jié)果顯示，利用MAC層面上的時(shí)間標(biāo)記（time stamp）傳統(tǒng)的發(fā)送方-接收方算法可以克服發(fā)送時(shí)間的誤差，并且精確度比接收方-接收方算法高。再電能方面，TPSN比RBS消耗得多。在發(fā)現(xiàn)階段用來選根節(jié)點(diǎn)的數(shù)據(jù)包就算是一種消耗，這種消耗有損于網(wǎng)絡(luò)的壽命，特別是當(dāng)根節(jié)點(diǎn)總是失效時(shí)，整個(gè)同步方法總是要被重復(fù)。D.小同步和迷你同步在文獻(xiàn)11中，作者提出了兩種用于一對(duì)無線節(jié)點(diǎn)的同步的算法，然后這些算法被擴(kuò)展到所有網(wǎng)絡(luò)節(jié)點(diǎn)的情形。傳統(tǒng)的雙向信息被用來收集數(shù)據(jù)點(diǎn)，這些數(shù)據(jù)點(diǎn)用來使兩個(gè)節(jié)點(diǎn)的相關(guān)漂移和相關(guān)設(shè)定更加緊密。用兩個(gè)節(jié)點(diǎn)創(chuàng)造數(shù)據(jù)點(diǎn),：1和2，節(jié)點(diǎn)1向節(jié)點(diǎn)2發(fā)送帶有時(shí)間標(biāo)記t的探索信息，節(jié)點(diǎn)

14、2再馬上或者在某一時(shí)刻（標(biāo)記為t），在這一信息上做上記號(hào)t，然后傳回節(jié)點(diǎn)1以作確認(rèn)。圖三就描述了上述順序?；谏鲜龅仁?并且考慮到信息發(fā)送的順序，可以得到下面的關(guān)系：t0t<a12tbt+b12 (5)trt>a12tbt+b12 (6)算法開始收集數(shù)據(jù)點(diǎn)，用線性程序估計(jì)a和b，然后使節(jié)點(diǎn)相互同步。當(dāng)網(wǎng)絡(luò)中的普通數(shù)據(jù)和確認(rèn)數(shù)據(jù)包能夠用來收集數(shù)據(jù)點(diǎn)的時(shí)候，這樣可以減小消耗，估計(jì)a和b所需要的大存儲(chǔ)量以及大的計(jì)算量。E基于樹的同步算法很多無線網(wǎng)絡(luò)傳感器都需要微秒級(jí)的精度，有的需要毫秒級(jí)精度。文獻(xiàn)7提出的算法，在假定需要達(dá)到的精度，以及基于這一給定數(shù)據(jù)得出的復(fù)雜程度和計(jì)算時(shí)間已知的情況下

15、，解決這一現(xiàn)實(shí)問題。第一個(gè)算法包括兩個(gè)階段，在第一階段線形成生成樹協(xié)議，然后在第二階段，在生成樹協(xié)議n-1邊一個(gè)發(fā)送方-接收方同步將會(huì)完成。在這種集中算法中，所有的節(jié)點(diǎn)的時(shí)間將會(huì)同步為一個(gè)中心點(diǎn)，稱作sink或者根節(jié)點(diǎn)。根節(jié)點(diǎn)的作用是在必要的時(shí)候重新開始同步。同樣，它也將網(wǎng)絡(luò)所有的節(jié)點(diǎn)都同步為一個(gè)時(shí)間。為了能夠進(jìn)行那些運(yùn)算和做出其它的決策，根據(jù)生成樹協(xié)議的深度不斷調(diào)整更新根節(jié)點(diǎn)是很有必要的。在第二種算法中，節(jié)點(diǎn)根據(jù)與參考節(jié)點(diǎn)的遠(yuǎn)近，時(shí)鐘漂移，以及所需的精度來決定什么時(shí)候同步。因此任何節(jié)點(diǎn)都能再有參考節(jié)點(diǎn)的時(shí)候開始同步階段，而通向參考節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)必須先被同步。因?yàn)椴⒎撬泄?jié)點(diǎn)都需要在所有

16、時(shí)間被同步，所以這種算法允許節(jié)點(diǎn)自己決定是否要同步，這樣就減少了消耗。同步要求的整合的應(yīng)用使得算法更有效，在節(jié)點(diǎn)發(fā)出同步請(qǐng)求時(shí)，會(huì)先看臨近節(jié)點(diǎn)是否還有沒有經(jīng)過處理的請(qǐng)求，如果有的話，就把自己的請(qǐng)求整合在上面，這樣就可以保證同步只有一次。在文獻(xiàn)11中，提出了將整個(gè)網(wǎng)絡(luò)分成子樹的方法。在每一個(gè)子樹上，子節(jié)點(diǎn)向它們的母節(jié)點(diǎn)或者根節(jié)點(diǎn)同步，然后所有的母節(jié)點(diǎn)同步。4 結(jié)論我們發(fā)現(xiàn)在精確度上TPSN和RBS做得很好。它們可以將精確度控制在微秒級(jí)。因?yàn)槭瞻l(fā)數(shù)據(jù)包是整個(gè)同步過程中耗能最大的過程，所以同步一對(duì)節(jié)點(diǎn)所需要的數(shù)據(jù)包數(shù)常被用來評(píng)估節(jié)能效率。RBS算法是一個(gè)接收方-接收方算法，在同步兩個(gè)節(jié)點(diǎn)時(shí)會(huì)發(fā)送4個(gè)

17、數(shù)據(jù)包，接收3數(shù)據(jù)包。在TPSN中，在同步兩個(gè)節(jié)點(diǎn)的時(shí)候會(huì)發(fā)送2個(gè)數(shù)據(jù)包，接收兩個(gè)數(shù)據(jù)包。盡管聽上去TPSN更加節(jié)能，但是事實(shí)上，TPSN需要額外發(fā)送數(shù)據(jù)包來進(jìn)行層次的編號(hào)，并且在RBS中一次脈沖不止同步一個(gè)接收點(diǎn)?；跇涞耐剿惴ǜ屿`活，并且根據(jù)給定的精度和復(fù)雜度耗能的高低可能不確定。根節(jié)點(diǎn)在這些算法中起到了很大的作用，并且還可以連上外部節(jié)點(diǎn)以獲得實(shí)時(shí)時(shí)間。參考文獻(xiàn)1 J. Elson, L. Girod, and D. Estrin, “Fine-Grained Time Synchronization using Reference Broadcasts," Proceedi

18、ngs of the Fifth Symposium on Operating Systems Design and Implementation (OSDI 2002), Boston, MA, December 2002. 2 T. Haenselmann. “Sensornetworks,” Wireless Sensor Network textbook, 2006. 3 L. He and G.S. Kuo, “A Novel Time Synchronization Scheme in Wireless Sensor Networks,” Vehicular Technology

19、Conference, 2006. VTC 2006-Spring. IEEE 63rd Volume 2, 7-10 May 2006 pps. 568 572. 4 J. Hill and D. Culler, “A Wireless Embedded Sensor Architecture for System-Level Optimization," Technical Report, U.C. Berkeley, 2001. 5B.Hofmann-Wellenhof,H. Lichtenegger, and J. Collins. “Global Positioning S

20、ystem: Theory and Practice,” Text Book, Fifth edition, 2001. 6S. Ganeriwal, R. Kumar, and M. Srivastava, “Timing Sync Protocol for Sensor Networks," ACM SenSys, Los Angeles, November 2003. 7 J.V. Greunen, and J. Rabaey, “Lightweight Time Synchronization for Sensor Networks," Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA), San Diego, CA, September 2003. 8 D. Mills, “Network Time Protocol (Version 3) Specification, Implementation and Analysis,” Technical Report, Universi