無線傳感器網(wǎng)絡(luò)時(shí)間同步方法研究

1、無線傳感器網(wǎng)絡(luò)時(shí)間同步方法研究趙玉葉梁葉 收稿日期2011-5-20（廣西大學(xué)電氣工程學(xué)院廣西南寧530004）摘要時(shí)間同步技術(shù)是研究無線傳感器網(wǎng)絡(luò)（WSN）許多關(guān)鍵技術(shù)實(shí)現(xiàn)的基礎(chǔ)。文章分析了時(shí)間同步方法的重要性和設(shè)計(jì)時(shí)間同步機(jī)制關(guān)注的性能指標(biāo)，總結(jié)了幾個(gè)具有代表性的時(shí)間同步技術(shù)方法，描述了各自的工作原理以及優(yōu)缺點(diǎn)。關(guān)鍵詞無線傳感器網(wǎng)絡(luò)；時(shí)間同步；算法中圖分類號(hào)O45文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1088-7656（2011）03-0038-041 時(shí)間同步技術(shù)的重要性傳感器節(jié)點(diǎn)的時(shí)鐘并不完美，會(huì)在時(shí)間上發(fā)生漂移，所以觀察到的時(shí)間對(duì)于網(wǎng)絡(luò)中的節(jié)點(diǎn)來說是不同的。但很多網(wǎng)絡(luò)協(xié)議的應(yīng)用，都需要一個(gè)共同的時(shí)間以

2、使得網(wǎng)路中的節(jié)點(diǎn)全部或部分在瞬間是同步的。第一，傳感器節(jié)點(diǎn)需要彼此之間并行操作和協(xié)作去完成復(fù)雜的傳感任務(wù)。如果在收集信息過程中，傳感器節(jié)點(diǎn)缺乏統(tǒng)一的時(shí)間戳（即沒有同步），估計(jì)將是不準(zhǔn)確的。第二，許多節(jié)能方案是利用時(shí)間同步來實(shí)現(xiàn)的。例如，傳感器可以在適當(dāng)?shù)臅r(shí)候休眠（通過關(guān)閉傳感器和收發(fā)器進(jìn)入節(jié)能模式），在需要的時(shí)候再喚醒。在應(yīng)用這種節(jié)能模式的時(shí)候，節(jié)點(diǎn)應(yīng)該在同等的時(shí)間休眠和喚醒，也就是說當(dāng)數(shù)據(jù)到來時(shí)，節(jié)點(diǎn)的接收器可以接收，這個(gè)需要傳感器節(jié)點(diǎn)間精確的定時(shí)。2 時(shí)間同步技術(shù)所關(guān)注的主要性能參數(shù)時(shí)間同步技術(shù)的根本目的是為網(wǎng)絡(luò)中節(jié)點(diǎn)的本地時(shí)鐘提供共同的時(shí)間戳。對(duì)無線傳感器網(wǎng)絡(luò)WSN（Wireless S

3、ensor Networks）1的時(shí)間同步應(yīng)主要應(yīng)考慮以下幾個(gè)方面的問題：(1)能量效率。同步的時(shí)間越長(zhǎng)，消耗的能量越多，效率就越低。設(shè)計(jì)WSN的時(shí)間同步算法需以考慮傳感器節(jié)點(diǎn)有效的能量資源為前提。(2) 可擴(kuò)展性和健壯性。時(shí)間同步機(jī)制應(yīng)該支持網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目或者密度的有效擴(kuò)展，并保障一旦有節(jié)點(diǎn)失效時(shí)，余下網(wǎng)絡(luò)有效且功能健全。(3)精確度。針對(duì)不同的應(yīng)用和目的，精確度的需求有所不用。(4)同步期限。節(jié)點(diǎn)需要保持時(shí)間同步的時(shí)間長(zhǎng)度可以是瞬時(shí)的，也可以和網(wǎng)絡(luò)的壽命一樣長(zhǎng)。(5)有效同步范圍?？梢越o網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)提供時(shí)間，也可以給局部區(qū)域的節(jié)點(diǎn)提供時(shí)間。(6)成本和尺寸。同步可能需要特定的硬件，另外

4、，體積的大小也影響同步機(jī)制的實(shí)現(xiàn)。(7)最大誤差。一組傳感器節(jié)點(diǎn)之間的最大時(shí)間差，或相對(duì)外部標(biāo)準(zhǔn)時(shí)間的最大差。3 現(xiàn)有主要時(shí)間同步方法研究時(shí)間同步技術(shù)是研究WSN的重要問題，許多具體應(yīng)用都需要傳感器節(jié)點(diǎn)本地時(shí)鐘的同步，要求各種程度的同步精度。WSN具有自組織性、多跳性、動(dòng)態(tài)拓?fù)湫院唾Y源受限性，尤其是節(jié)點(diǎn)的能量資源、計(jì)算能力、通信帶寬、存儲(chǔ)容量有限等特點(diǎn)，使時(shí)間同步方案有其特殊的需求，也使得傳統(tǒng)的時(shí)間同步算法不適合于這些網(wǎng)絡(luò)2。因此越來越多的研究集中在設(shè)計(jì)適合WSN的時(shí)間同步算法3。針對(duì)WSN，目前已經(jīng)從不同角度提出了許多新的時(shí)間同步算法4。3.1 成對(duì)(pair-wise)同步的雙向同步模式代

5、表算法是傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議TPSN（Timing-Sync Protocol for Sensor Networks）56。目的是提供WSN整個(gè)網(wǎng)絡(luò)范圍內(nèi)節(jié)點(diǎn)間的時(shí)間同步。該算法分兩步：分級(jí)和同步。第一步的目的是建立分級(jí)的拓?fù)渚W(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)有個(gè)級(jí)別。只有一個(gè)節(jié)點(diǎn)與外界通信獲取外界時(shí)間，將其定為零級(jí)，叫做根節(jié)點(diǎn)，作為整個(gè)網(wǎng)絡(luò)系統(tǒng)的時(shí)間源。在第二步，每個(gè)i級(jí)節(jié)點(diǎn)與i-1（上一級(jí)）級(jí)節(jié)點(diǎn)同步，最終所有的節(jié)點(diǎn)都與根節(jié)點(diǎn)同步，從而達(dá)到整個(gè)網(wǎng)絡(luò)的時(shí)間同步。詳細(xì)的時(shí)間同步過程如圖 1 所示。圖1 TPSN 同步過程設(shè)R為上層節(jié)點(diǎn)，S為下層節(jié)點(diǎn)，傳播時(shí)間為d，兩節(jié)點(diǎn)的時(shí)間偏差為。同步過程由節(jié)點(diǎn)R廣播開始同

6、步信息，節(jié)點(diǎn)S接收到信息以后，就開始準(zhǔn)備時(shí)間同步過程。在T1時(shí)刻，節(jié)點(diǎn)S發(fā)送同步信息包，包含信息(T1)，節(jié)點(diǎn)R在T2接收到同步信息，并記錄下接收時(shí)間T2，這里滿足關(guān)系：節(jié)點(diǎn)R在T3時(shí)刻發(fā)送回復(fù)信息包，包含信息(T1,T2,T3)。在T4時(shí)刻S接收到同步信息包，滿足關(guān)系：最后，節(jié)點(diǎn)S利用上述2個(gè)時(shí)間表達(dá)式可計(jì)算出的值：TPSN由于采用了在MAC層給同步包標(biāo)記時(shí)間戳的方式，降低了發(fā)送端的不確定性，消除了訪問時(shí)間帶來的時(shí)間同步誤差，使得同步效果更加有效。并且，TPSN算法對(duì)任意節(jié)點(diǎn)的同步誤差取決于它距離根節(jié)點(diǎn)的跳數(shù)，而與網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)無關(guān)，使TPSN同步精度不會(huì)隨節(jié)點(diǎn)數(shù)目增加而降級(jí)，從而使TPSN

7、具有較好的擴(kuò)展性。TPSN算法的缺點(diǎn)是一旦根節(jié)點(diǎn)失效，就要重新選擇根節(jié)點(diǎn)，并重新進(jìn)行分級(jí)和同步階段的處理，增加了計(jì)算和能量開銷，并隨著跳數(shù)的增加，同步誤差呈線性增長(zhǎng)，準(zhǔn)確性較低。另外，TPSN算法沒有對(duì)時(shí)鐘的頻差進(jìn)行估計(jì)，這使得它需要頻繁同步，完成一次同步能量消耗較大。3.2 接收方-接收方（Receiver-Receiver）模式代表算法是參考廣播時(shí)間同步協(xié)議RBS（Reference Broadcast Synchronization）7。RBS是典型的基于接收方-接收方的同步算法，是Elson等人以“第三節(jié)點(diǎn)”實(shí)現(xiàn)同步的思想而提出的。該算法中，利用無線數(shù)據(jù)鏈路層的廣播信道特性，基本思想為

8、：節(jié)點(diǎn)(作為發(fā)送者)通過物理層廣播周期性地向其鄰居節(jié)點(diǎn)（作為接收者）發(fā)送信標(biāo)消息10，鄰居節(jié)點(diǎn)記錄下廣播信標(biāo)達(dá)到的時(shí)間，并把這個(gè)時(shí)間作為參考點(diǎn)與時(shí)鐘的讀數(shù)相比較。為了計(jì)算時(shí)鐘偏移，要交換對(duì)等鄰居節(jié)點(diǎn)間的時(shí)間戳，確定它們之間的時(shí)間偏移量，然后其中一個(gè)根據(jù)接收到的時(shí)間差值來修改其本地的時(shí)間，從而實(shí)現(xiàn)時(shí)間同步11。假如該算法在網(wǎng)絡(luò)中有n個(gè)接收節(jié)點(diǎn)m個(gè)參考廣播包，則任意一個(gè)節(jié)點(diǎn)接收到m個(gè)參考包后，會(huì)拿這些參考包到達(dá)的時(shí)間與其它n-1個(gè)接收節(jié)點(diǎn)接收到的參考包到達(dá)的時(shí)間進(jìn)行比較，然后進(jìn)行信息交換。圖2為RBS算法的關(guān)鍵路徑示意圖。圖2 RBS算法的關(guān)鍵路徑示意圖其計(jì)算公式如下：其中n表示接收者的數(shù)量，m表

9、示參考包的數(shù)量，表示接收節(jié)點(diǎn)r接收到參考包b時(shí)的時(shí)鐘。此算法并不是同步發(fā)送者和接收者，而是使接收者彼此同步，有效避免了發(fā)送訪問時(shí)間對(duì)同步的影響，將發(fā)送方延遲的不確定性從關(guān)鍵路徑中排除，誤差的來源主要是傳輸時(shí)間和接收時(shí)間的不確定性，從而獲得了比利用節(jié)點(diǎn)間雙向信息交換實(shí)現(xiàn)同步的方法更高的精確度。這種方法的最大弊端是信息的交換次數(shù)太多，發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間、接收節(jié)點(diǎn)彼此之間，都要經(jīng)過消息交換后才能達(dá)到同步。計(jì)算復(fù)雜度較高，網(wǎng)絡(luò)流量開銷和能耗太大，不適合能量供應(yīng)有限的場(chǎng)合。3.3 發(fā)送方-接收方(Sender-Receiver)模式基于發(fā)送方-接收方機(jī)制的時(shí)間同步算法的基本原理是：發(fā)送節(jié)點(diǎn)發(fā)送包含本

10、地時(shí)間戳的時(shí)間同步消息，接收節(jié)點(diǎn)記錄本地接收時(shí)間，并將其與同步消息中的時(shí)間戳進(jìn)行比較，調(diào)整本地時(shí)鐘?；谶@種方法提出的時(shí)間同步算法有以下兩種。3.3.1 FTSP 算法8泛洪時(shí)間同步協(xié)議FTSP（Flooding Time Synchronization Protocol）由Vanderbilt大學(xué)Branislav Kusy等提出，目標(biāo)是實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步且誤差控制在微秒級(jí)。該算法用單個(gè)廣播消息實(shí)現(xiàn)發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的時(shí)間同步。其特點(diǎn)為：(1)通過對(duì)收發(fā)過程的分析，把時(shí)延細(xì)分為發(fā)送中斷處理時(shí)延、編碼時(shí)延、傳播時(shí)延、解碼時(shí)延、字節(jié)對(duì)齊時(shí)延、接收中斷處理時(shí)延，進(jìn)一步降低時(shí)延的不確定度；(

11、2)通過發(fā)射多個(gè)信令包，使得接收節(jié)點(diǎn)可以利用最小方差線性擬合技術(shù)估算自己和發(fā)送節(jié)點(diǎn)的頻率差和初相位差；(3)設(shè)計(jì)一套根節(jié)點(diǎn)選舉機(jī)制，針對(duì)節(jié)點(diǎn)失效、新節(jié)點(diǎn)加入、拓?fù)渥兓惹闆r進(jìn)行優(yōu)化，適合于惡劣環(huán)境12。FTSP算法對(duì)時(shí)鐘漂移進(jìn)行了線性回歸分析。此算法考慮到在特定時(shí)間范圍內(nèi)節(jié)點(diǎn)時(shí)鐘晶振頻率是穩(wěn)定的，因此節(jié)點(diǎn)間時(shí)鐘偏移量與時(shí)間成線性關(guān)系，通過發(fā)送節(jié)點(diǎn)周期性廣播時(shí)間同步消息，接收節(jié)點(diǎn)取得多個(gè)數(shù)據(jù)對(duì)，構(gòu)造最佳擬合直線，通過回歸直線，在誤差允許的時(shí)間間隔內(nèi)，節(jié)點(diǎn)可直接通過它來計(jì)算某一時(shí)間節(jié)點(diǎn)間的時(shí)鐘偏移量而不必發(fā)送時(shí)間同步消息進(jìn)行計(jì)算，從而減少了消息的發(fā)送次數(shù)并降低了系統(tǒng)能量開銷。FTSP結(jié)合TPSN和

12、RBS的優(yōu)點(diǎn)，不僅排除了發(fā)送方延遲的影響，而且對(duì)報(bào)文傳輸中接收方的不確定延遲（如中斷處理時(shí)間、字節(jié)對(duì)齊時(shí)間、硬件編解碼時(shí)間等）做了有效的估計(jì)。多跳的FTSP協(xié)議采用層次結(jié)構(gòu)，根節(jié)點(diǎn)為同步源，可以適應(yīng)大量傳感器節(jié)點(diǎn)，對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和根節(jié)點(diǎn)的失效有健壯性，精確度較好。該算法通過采用MAC層時(shí)間戳和線性回歸偏差補(bǔ)償彌補(bǔ)相關(guān)的錯(cuò)誤源，通過對(duì)一個(gè)數(shù)據(jù)包打多個(gè)時(shí)戳，進(jìn)而取平均和濾除抖動(dòng)較大的時(shí)戳，大大降低了中斷和解碼時(shí)間的影響。FTSP 采用洪泛的方式向遠(yuǎn)方節(jié)點(diǎn)傳遞時(shí)間基準(zhǔn)節(jié)點(diǎn)的時(shí)間信息，洪泛的時(shí)間信息可由中轉(zhuǎn)節(jié)點(diǎn)生成，因此誤差累積不可避免。另外，F(xiàn)TSP的功耗和帶寬的開銷巨大。3.3.2 DMTS

13、 算法9延遲測(cè)量時(shí)間同步DMTS (delay measurement time synchronization) 算法的同步機(jī)制是基于發(fā)送方-接收方的同步機(jī)制。DMTS 算法的實(shí)現(xiàn)策略是犧牲部分時(shí)間同步精度換取較低的計(jì)算復(fù)雜度和能耗，是一種能量消耗輕的時(shí)間同步算法。DMTS算法的基本原理為：選擇一個(gè)節(jié)點(diǎn)作為時(shí)間主節(jié)點(diǎn)廣播同步時(shí)間，所有接收節(jié)點(diǎn)通過精確地測(cè)量從發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)的單向時(shí)間廣播消息的延遲并結(jié)合發(fā)送節(jié)點(diǎn)時(shí)間戳，計(jì)算出時(shí)間調(diào)整值，接收節(jié)點(diǎn)設(shè)置它的時(shí)間為接收到消息攜帶的時(shí)間加上廣播消息的傳輸延遲，調(diào)整自己的邏輯時(shí)鐘值以和基準(zhǔn)點(diǎn)達(dá)成同步，這樣所有得到廣播消息的節(jié)點(diǎn)都與主節(jié)點(diǎn)進(jìn)行時(shí)間同步。

14、發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的時(shí)間延遲可由得出。其中，nt為發(fā)送前導(dǎo)碼和起始字符所需的時(shí)間，n為發(fā)送的信息位個(gè)數(shù)，t為發(fā)送一位所需時(shí)間；為接收節(jié)點(diǎn)在消息到達(dá)時(shí)的本地時(shí)間；為接收節(jié)點(diǎn)在調(diào)整自己的時(shí)鐘之前的那一時(shí)刻記錄的本地時(shí)間，是接收處理延遲。DMTS 算法的優(yōu)點(diǎn)是結(jié)合鏈路層打時(shí)間戳和時(shí)延估計(jì)等技術(shù)，消除了發(fā)送時(shí)延和訪問時(shí)延的影響，算法簡(jiǎn)單，通信開銷小。但DMTS算法沒有估計(jì)時(shí)鐘的頻率偏差，時(shí)鐘保持同步的時(shí)間較短，沒有對(duì)位偏移產(chǎn)生的時(shí)間延遲進(jìn)行估計(jì)，也沒有消除時(shí)鐘計(jì)時(shí)精度對(duì)同步精度的影響，因此其同步精度比FTSP略有下降，不適用于定位等要求高精度同步的應(yīng)用。基于發(fā)送方-接收方單向同步機(jī)制的算法在上述三類方

15、法中需要發(fā)送的時(shí)間同步消息數(shù)目最少。發(fā)送節(jié)點(diǎn)只要發(fā)送一次同步消息，因而具有較低的網(wǎng)絡(luò)流量開銷和復(fù)雜度，減少了系統(tǒng)能耗。4 結(jié)論文章介紹了WSN時(shí)間同步算法的類型以及各自具有代表性的算法，分析了各算法的設(shè)計(jì)原理和優(yōu)缺點(diǎn)。這些協(xié)議解決了WSN中時(shí)間同步所遇到的主要問題，但對(duì)于大型網(wǎng)絡(luò)，已有的方法或多或少存在著一些問題：擴(kuò)展性差、穩(wěn)定性不高、收斂速度變慢、網(wǎng)絡(luò)通信沖突、能耗增大。今后的研究熱點(diǎn)將集中在節(jié)能和時(shí)間同步的安全性方面。這將對(duì)算法的容錯(cuò)性、有效范圍和可擴(kuò)展性提出更高的要求。參考文獻(xiàn)1I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,E.Cayirci,”A Survey on Sensor Networks,”IEEE Communications Magazine,vol.40,no.8,pp.102-114,2002.2 周賢偉，韋煒，覃伯平. 無線傳感器網(wǎng)絡(luò)的時(shí)間同步算法研究J. 傳感技術(shù)學(xué)報(bào)，2006（1）.3 趙建軍, 姜建國(guó), 裴慶祺. 低開銷的無線