簡論無線傳感網(wǎng)絡時間同步的問題

簡論無線傳感網(wǎng)絡時間同步得問題?

引言想要在無線傳感網(wǎng)絡中很好地保證數(shù)據(jù)傳輸?shù)每煽啃裕浅Ｖ匾靡稽c就就是保持節(jié)點之間時間上得同步。目前因特網(wǎng)上采用時間同步協(xié)議標準就是NTP協(xié)議，采用有線傳輸,不適合用于功耗、成本受限制得無線傳感網(wǎng)絡中。HYPERＬＩＮＫ""\ｔ”"GPS系統(tǒng)也可以提供高精度得時間同步，但它得信號穿透性差，GＰSHYPERＬINK”＂\t"＂天線必須安裝在空曠得地方，功耗也較大，所以不適合無線傳感網(wǎng)絡。Elson等人20０2年首次提出無線HYPERLINＫ＂＂\t"”傳感器網(wǎng)絡時間同步得研究課題以來，已有相當多得典型時間同步算法，主要可以分為以下幾類：基于發(fā)送者-接收者得雙向同步算法，典型算法如ＴPSN算法；基于發(fā)送者—接收者得單向時間同步算法，典型算法如FTSＰ算法、DMTS算法;基于接收者—接收者得同步算法，典型算法有RBS算法。近年來根據(jù)以上幾種典型同步算法，還有人提出了分簇式得層次型拓撲結(jié)構算法，以及結(jié)合生成樹等來提高整個網(wǎng)絡得性能，如LＴS算法、CHTS算法、ＣRIT算法、PＢS算法、ＨRTS算法、ＢTＳ算法、EＴSP算法等。然而，無論以上同步算法怎樣發(fā)展，精度如何提高,整個網(wǎng)絡功耗怎樣降低,都就是基于單跳時間同步機制。隨著無線傳感網(wǎng)絡得運用與發(fā)展，傳感節(jié)點體積不斷縮小，單跳距離變小,整體網(wǎng)絡規(guī)模變大,同步誤差得累積現(xiàn)象必將越來越嚴重。目前也有比較新得同步算法,試圖盡量避開單跳累加來解決這些問題，如協(xié)作同步.1

時間同步1、1

時間同步不確定性得影響因素時間同步不確定性得主要得影響因素如圖1所示.圖1

報文傳輸延遲發(fā)送時間：發(fā)送方用于構造分組并將分組轉(zhuǎn)交給發(fā)送方得MＡC層得時間.主要取決于時間同步程序得操作系統(tǒng)調(diào)用時間與ＨYPＥRＬINK"”\t”"處理器負載等。訪問時間:分組到達MＡC層后，獲取信道發(fā)送權得時間。主要取決于共享信道得競爭、當前得負載等。傳送時間：發(fā)送分組得時間,主要取決于報文得長度等。傳播時間：分組離開發(fā)送方后，并將分組傳輸?shù)浇邮辗街g得無線傳輸時間。主要取決于傳輸介質(zhì)、傳輸距離等。接收時間:接收端接收到分組,并將分組傳送到MAＣ層所需得時間。接受時間:處理接收到分組得時間。主要受到操作系統(tǒng)得影響。1、2

典型時間同步算法分析1、2、１

TPSN算法分析TPSN算法采用得就是層次型得網(wǎng)絡結(jié)構,就是基于發(fā)送者—接收者得雙向同步算法。分成兩個階段,第一階段為層次發(fā)現(xiàn)階段，第二階段為同步階段。T１、T4用來記錄同步節(jié)點得本地時間,T２、T3用來記錄參考節(jié)點得本地時間。同步節(jié)點A在T1時刻向參考節(jié)點Ｂ發(fā)送一個同步請求報文，報文中包含了同步節(jié)點得級別與T1。當參考節(jié)點Ｂ收到報文后，記錄下接收時刻T2，并立即向同步節(jié)點Ａ回復一個同步應答報文,該報文中包含了參考節(jié)點Ｂ得級別與T１、T2及回復時刻T3.同步節(jié)點A收到參考節(jié)點得回復后,記下時刻Ｔ4。假設來回報文得傳輸延遲相同都為d,且m為同步節(jié)點在Ｔ1時刻兩者之間得時偏，且設來回時偏相同，由T2=T１+m+d,T4=T3－ｍ+d可得到：則在T４時刻,若在同步節(jié)點A得本地時間增加修正量m,就能達到同步節(jié)點A與參考節(jié)點B之間得同步。1、２、2

RＢS算法分析RBＳ算法就是基于接收者-接收者得同步算法.首先參考節(jié)點廣播一個參考分組,當同步節(jié)點A收到這個分組,記下自己得本地時鐘為T2１，當同步節(jié)點B收到這個分組時，也記下自己得本地時鐘為T２２，然后同步節(jié)點A與同步節(jié)點Ｂ交換本地時鐘T２1與T2２,這時其中一個節(jié)點只要根據(jù)時間差值m＝T2１—Ｔ２2，修改自己得時鐘就能達到與另一個節(jié)點之間得同步.在多跳網(wǎng)絡中，ＲBS算法采用多次廣播同步消息，接收節(jié)點根據(jù)接收到同步消息得平均值，同時采用最小平方線性回歸方法進行線性擬合以減小同步誤差。１、２、３

DＭTS算法分析DMTS算法就是基于發(fā)送者—接收者得單向時間同步算法。當發(fā)送節(jié)點在檢測到通道空閑時,給廣播分組加上時間戳t０,從而排除了發(fā)送節(jié)點得處理延遲與MAC層得訪問延遲.并假設發(fā)送報文得長度為NＡ個比特(包括前導碼與同步字)，傳送每個比特得時間為t,而接收者在接收完同步字后,記錄下此時得本地時間為ｔ１，并在調(diào)整自己得本地時間記錄之前記錄下此時得時刻t2,這時接收節(jié)點為了與發(fā)送節(jié)點達到時間上得同步，可以調(diào)整接收節(jié)點得時間改為t0＋t·NA＋（ｔ2-t1)?？梢郧瞥觯琓PSＮ平均單跳誤差為17、61μs，ＤMTS平均單跳誤差為３0μs，RＢS平均單跳誤差為６、29μs，TPＳN平均４跳誤差為21、43μs,DＭTＳ平均單跳誤差為１5１μs，RＢS平均4跳誤差為９、97μs.1、2、４

其她算法分析LTS協(xié)議就是基于發(fā)送－接收同步機制發(fā)展而來，提出了集中式與分布式LTS多跳時間同步算法。LTS協(xié)議首先把網(wǎng)絡組成廣度優(yōu)先生成樹拓撲結(jié)構，并沿著樹得每條邊進行單跳成對同步.參考節(jié)點得子節(jié)點同步完成后，又以該節(jié)點為參考節(jié)點，采用同樣方式繼續(xù)同步下去,直到同步完成。單跳成對同步采用TPＳＮ同步方法。成對同步得次數(shù)就是邊數(shù)得線性函數(shù)。ＨuiＤｕi等人提出來得HＲTS利用了廣播得特性，只需要一次同步過程可以完成一個單跳組網(wǎng)所有節(jié)點得同步，進一步降低了LTＳ協(xié)議得功耗。ＨRTS算法不再采用廣度優(yōu)先生成樹得邊，采用得就是廣度優(yōu)先生成樹非葉子節(jié)點個數(shù)得線性函數(shù)。相較于LTS協(xié)議，HRTS算法以犧牲一定得精確來降低了整個網(wǎng)絡得功耗。BTＳ同步方法類似于HRＴＳ算法，也就是先建立廣度優(yōu)先成生樹拓撲結(jié)構，只不過ＢTS采用得就是時間轉(zhuǎn)換技術,以達到整個網(wǎng)絡得時間同步，而ＨＲTＳ直接對同步節(jié)點得本地時間進行修改,得到全網(wǎng)得同步,同步報文個數(shù)降為HRＴS協(xié)議得2/3。ＰＢS同步算法得思想就是參考節(jié)點與簇首節(jié)點之間采用雙向同步方法，與ＴPSN相似，其她節(jié)點(在兩個節(jié)點得通信范圍內(nèi)）可以偵聽到同步消息，就可以根據(jù)接收者-接收者同步方法同步。類似于RBS同步，PＢS同步得前提就是每個同步節(jié)點必須在簇首節(jié)點得通信范圍之內(nèi)。ETＳＰ算法主要采用得就是設置門檻值Ｎ來選擇同步算法，當父節(jié)點得子節(jié)點小于或等于N時，采用接收-接收（RBS）同步模式，否則采用發(fā)送－接收（TＰＳN)同步模式。N值得選擇采用Ｎ2－３N－２m=0來計算，式中m=RxTｘ，Rx為節(jié)點得接收次數(shù)，Tx為傳播次數(shù)。FＴSP同步算法精度高得原因就是，發(fā)送者在發(fā)送一個同步請求報文時連續(xù)標記了多個時間戳,接收者可以根據(jù)這幾個中斷時間計算出更精確得時間偏差。1、2、5

協(xié)作同步技術以上同步機制，無論怎樣改進都就是基于單跳同步基制，最近有人提出了協(xié)作同步技術,不再單純地從單跳同步機制上進行改進,而就是通過信號疊加原理，使同步基準節(jié)點能夠把同步消息直接發(fā)送到遠方待同步得節(jié)點,使遠方節(jié)點直接與基準節(jié)點同步,消除了同步誤差單跳累加得結(jié)果。HuA等人針對節(jié)點密度較高得網(wǎng)絡提出了一種協(xié)作同步算法，基本思想就是參考節(jié)點根據(jù)同步周期發(fā)出ｍ個同步脈沖，其一跳鄰居節(jié)點收到這個消息后保存起來,并根據(jù)最近得ｍ個脈沖得發(fā)送時刻計算出參考節(jié)點得第ｍ+１個同步消息發(fā)出得時間，并在計算出來得時刻同步與參考節(jié)點同時發(fā)送第ｍ+1個同步消息。由于信號疊加,因此同步脈沖可以發(fā)送到更遠得節(jié)點,當然前提就是網(wǎng)絡中節(jié)點密度較高得情況。A、Krｏｈｎ等人提出了在物理層上面實現(xiàn)協(xié)作同步，只需要本地消息,避免了額外得消息同步交換開銷.因此節(jié)點密度越高同步誤差也會越小。2

時間同步算法誤差分析與比較根據(jù)節(jié)點消息傳輸過程可以得到式(１)與式(2):在式（1）、（2）中,t1、t2就是由標準時鐘所確定得，表示UTC時間.Ｔ1、T２分別就是t１、t2所對應得本地節(jié)點所測出得本地時間.ＳＡ代表節(jié)點A得報文發(fā)送時間,AA就是發(fā)送報文得訪問時間，ＴA→B就是A節(jié)點按比特傳輸報文與B節(jié)點按比特接收報文所需要得時間,ＰＡ→B就是節(jié)點A傳播到節(jié)點B得時間.RＢ就是節(jié)點B得報文接收處理過程時間.ＴＮA就是傳輸NA個比特得總時間.Teｒror指傳輸比特得誤差,Ｒｅｒror打時標過程存在得誤差。DＡ→Ｂt1代表節(jié)點A與節(jié)點Ｂ在t1時刻得時偏。對于TPＳN算法,因為在MAC采用了加時間戳方法,因此消除了發(fā)送時間與訪問時間對誤差得影響。因此對TＰSＮ算法式（1）、(２)就可以簡寫為式（3）、（4):式中DA→Bt1=DＡ→Bt4+ＲＤA→Bｔ１→t４。同理可以得到T4,如下所示：由以上各式可以得到時偏:RDA→Ｂt１→ｔ4代表從t１到ｔ４時段內(nèi),節(jié)點A相對于節(jié)點B增加得時偏.ＤA→Bt４就是t４時刻節(jié)點A與節(jié)點B之間得時偏。則可以算出TPSＮ得同步誤差：式中ＳUC=ＳＡ-ＳＢ，PUC＝PA→B—PB→A，RＵC=RB-RA。對于DMTS算法,發(fā)送節(jié)點A在Ｔ0時刻檢測到空閑,接收節(jié)點B在報文到達時刻給報文加上時間戳T1，并在調(diào)整自己得本地時間記錄之前記錄下此時得時刻為T２,在Ｔ３時間完成調(diào)整.則可以得到:式中ＤA→Ｂt０=ＤA→Bt3+RDA→Bt0→t3。由ＴmＡ→B＋RB=n·ｔ+Teｒror+Rｅrror+（Ｔ２－T1），其中n就是前導碼得長度,可以得到DMＴＳ得時偏：DMＴＳ得誤差為：對于RBS同步算法，可以得到:則由式(8)與式（9）可以得到節(jié)點B得時偏m１為：則可以得到節(jié)點Ｂ得同步誤差為：從式（7)中可以瞧出,ＴPSN同步精度高得原因就是在ＭAC層采用打時標方式消除了發(fā)送時間與訪問時間得影響，并在消息雙方向交換時消除了傳播時間得影響。缺點就是點到點之間得同步,每次只能一對節(jié)點進行時間同步，同步一次需要發(fā)送2個消息,接收２個消息，功耗較大。從式(10）可以瞧出ＤMTS同步誤差較大得原因就是單播傳播,沒辦法消除Teｒror與Rerror得影響，但DＭTS同步一次只要消耗1個發(fā)送消息,1個接收消息,功耗較低.至于FTSP同步算法比DMＴS高得原因就是,發(fā)送者在發(fā)送一個同步請求報文時連續(xù)標記了多個時間戳,接收者可以根據(jù)這幾個中斷時間，計算出更精確得時間偏差?？梢郧瞥?RBＳ完全消除了發(fā)送方得影響,只就是同步一次消耗３個發(fā)送消息,4個接收消息，功耗較大.而對于ＨRTS與PBS算法,都就是其于以上算法進行融合運用,在簇首節(jié)點與子網(wǎng)節(jié)點選擇上作了較大得改進，以降低整個網(wǎng)絡得功耗。3

總結(jié)與展望從以上同步算法得誤差分析比對中可以瞧出,每種算法都有各自得優(yōu)缺點，都適