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

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

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

時(shí)間同步1、1

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

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

典型時(shí)間同步算法分析1、2、１

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

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

DＭTS算法分析DMTS算法就是基于發(fā)送者—接收者得單向時(shí)間同步算法。當(dāng)發(fā)送節(jié)點(diǎn)在檢測(cè)到通道空閑時(shí),給廣播分組加上時(shí)間戳t０,從而排除了發(fā)送節(jié)點(diǎn)得處理延遲與MAC層得訪問延遲.并假設(shè)發(fā)送報(bào)文得長度為NＡ個(gè)比特(包括前導(dǎo)碼與同步字)，傳送每個(gè)比特得時(shí)間為t,而接收者在接收完同步字后,記錄下此時(shí)得本地時(shí)間為ｔ１，并在調(diào)整自己得本地時(shí)間記錄之前記錄下此時(shí)得時(shí)刻t2,這時(shí)接收節(jié)點(diǎn)為了與發(fā)送節(jié)點(diǎn)達(dá)到時(shí)間上得同步，可以調(diào)整接收節(jié)點(diǎn)得時(shí)間改為t0＋t·NA＋（ｔ2-t1)。可以瞧出，TPSＮ平均單跳誤差為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ā)送－接收同步機(jī)制發(fā)展而來，提出了集中式與分布式LTS多跳時(shí)間同步算法。LTS協(xié)議首先把網(wǎng)絡(luò)組成廣度優(yōu)先生成樹拓?fù)浣Y(jié)構(gòu)，并沿著樹得每條邊進(jìn)行單跳成對(duì)同步.參考節(jié)點(diǎn)得子節(jié)點(diǎn)同步完成后，又以該節(jié)點(diǎn)為參考節(jié)點(diǎn)，采用同樣方式繼續(xù)同步下去,直到同步完成。單跳成對(duì)同步采用TPＳＮ同步方法。成對(duì)同步得次數(shù)就是邊數(shù)得線性函數(shù)。ＨuiＤｕi等人提出來得HＲTS利用了廣播得特性，只需要一次同步過程可以完成一個(gè)單跳組網(wǎng)所有節(jié)點(diǎn)得同步，進(jìn)一步降低了LTＳ協(xié)議得功耗。ＨRTS算法不再采用廣度優(yōu)先生成樹得邊，采用得就是廣度優(yōu)先生成樹非葉子節(jié)點(diǎn)個(gè)數(shù)得線性函數(shù)。相較于LTS協(xié)議，HRTS算法以犧牲一定得精確來降低了整個(gè)網(wǎng)絡(luò)得功耗。BTＳ同步方法類似于HRＴＳ算法，也就是先建立廣度優(yōu)先成生樹拓?fù)浣Y(jié)構(gòu)，只不過ＢTS采用得就是時(shí)間轉(zhuǎn)換技術(shù),以達(dá)到整個(gè)網(wǎng)絡(luò)得時(shí)間同步，而ＨＲTＳ直接對(duì)同步節(jié)點(diǎn)得本地時(shí)間進(jìn)行修改,得到全網(wǎng)得同步,同步報(bào)文個(gè)數(shù)降為HRＴS協(xié)議得2/3。ＰＢS同步算法得思想就是參考節(jié)點(diǎn)與簇首節(jié)點(diǎn)之間采用雙向同步方法，與ＴPSN相似，其她節(jié)點(diǎn)(在兩個(gè)節(jié)點(diǎn)得通信范圍內(nèi)）可以偵聽到同步消息，就可以根據(jù)接收者-接收者同步方法同步。類似于RBS同步，PＢS同步得前提就是每個(gè)同步節(jié)點(diǎn)必須在簇首節(jié)點(diǎn)得通信范圍之內(nèi)。ETＳＰ算法主要采用得就是設(shè)置門檻值Ｎ來選擇同步算法，當(dāng)父節(jié)點(diǎn)得子節(jié)點(diǎn)小于或等于N時(shí)，采用接收-接收（RBS）同步模式，否則采用發(fā)送－接收（TＰＳN)同步模式。N值得選擇采用Ｎ2－３N－２m=0來計(jì)算，式中m=RxTｘ，Rx為節(jié)點(diǎn)得接收次數(shù)，Tx為傳播次數(shù)。FＴSP同步算法精度高得原因就是，發(fā)送者在發(fā)送一個(gè)同步請(qǐng)求報(bào)文時(shí)連續(xù)標(biāo)記了多個(gè)時(shí)間戳,接收者可以根據(jù)這幾個(gè)中斷時(shí)間計(jì)算出更精確得時(shí)間偏差。1、2、5

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

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

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