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

 引言

　　想要在無(wú)線傳感網(wǎng)絡(luò)中很好地保證數(shù)據(jù)傳輸?shù)目煽啃?，非常重要的一點(diǎn)就是保持節(jié)點(diǎn)之間時(shí)間上的同步。目前因特網(wǎng)上采用時(shí)間同步協(xié)議標(biāo)準(zhǔn)是NTP協(xié)議，采用有線傳輸，不適合用于功耗、成本受限制的無(wú)線傳感網(wǎng)絡(luò)中。GPS系統(tǒng)也可以提供高精度的時(shí)間同步，但它的信號(hào)穿透性差，GPS天線
天線

　　天線的基本功能是輻射和接收無(wú)線電波。發(fā)射時(shí)，把高頻電流轉(zhuǎn)換為電磁波；接收時(shí)，把電磁波轉(zhuǎn)換為高頻電流。天線的一般原理是：當(dāng)導(dǎo)體上通以高頻電流時(shí)，在其周圍空間會(huì)產(chǎn)生電場(chǎng)與磁場(chǎng)。按電磁場(chǎng)在空間的分布特性，可分為近區(qū)、中間區(qū)、遠(yuǎn)區(qū)。設(shè)R為空間一點(diǎn)到導(dǎo)體的距離，是高頻電流信號(hào)的波長(zhǎng)，在R＜λ／2π時(shí)的區(qū)域稱近區(qū)，在該區(qū)內(nèi)的電磁場(chǎng)與導(dǎo)體中電流、電壓有緊密的聯(lián)系；在R＞A／2π的區(qū)域稱為遠(yuǎn)區(qū)，在該區(qū)域內(nèi)電磁場(chǎng)能離開(kāi)導(dǎo)體向空間傳播，它的變化相對(duì)于導(dǎo)體上的電流、電壓就要滯后一段時(shí)間，此時(shí)傳播出去的電磁波已不與導(dǎo)線上的電流、電壓有直接的聯(lián)系了，這區(qū)域的電磁場(chǎng)稱為輻射場(chǎng)。 [全文]

必須安裝在空曠的地方，功耗也較大，所以不適合無(wú)線傳感網(wǎng)絡(luò)。

　　ElsON等人2002年首次提出無(wú)線傳感器
傳感器

　　凡是利用一定的物性（物理、化學(xué)、生物）法則、定理、定律、效應(yīng)等把物理量或化學(xué)量轉(zhuǎn)變成便于利用的電信號(hào)的器件。傳感器是測(cè)量系統(tǒng)中的一種前置部件，它將輸入變量轉(zhuǎn)換成可供測(cè)量的信號(hào)”。按照Gopel等的說(shuō)法是：“傳感器是包括承載體和電路連接的敏感元件”，而“傳感器系統(tǒng)則是組合有某種信息處理(模擬或數(shù)字)能力的系統(tǒng)”。傳感器是傳感系統(tǒng)的一個(gè)組成部分，它是被測(cè)量信號(hào)輸入的第一道關(guān)口。 [全文]

網(wǎng)絡(luò)時(shí)間同步的研究課題以來(lái)，已有相當(dāng)多的典型時(shí)間同步算法，主要可以分為以下幾類：基于發(fā)送者-接收者的雙向同步算法，典型算法如TPSN算法；基于發(fā)送者-接收者的單向時(shí)間同步算法，典型算法如FTSP算法、DMTS算法；基于接收者-接收者的同步算法，典型算法有RBS算法。

　　近年來(lái)根據(jù)以上幾種典型同步算法，還有人提出了分簇式的層次型拓?fù)浣Y(jié)構(gòu)算法，以及結(jié)合生成樹(shù)等來(lái)提高整個(gè)網(wǎng)絡(luò)的性能，如LTS算法、CHTS算法、CRIT算法、PBS算法、 HRTS 算法、BTS算法、ETSP算法等。

　　然而，無(wú)論以上同步算法怎樣發(fā)展，精度如何提高，整個(gè)網(wǎng)絡(luò)功耗怎樣降低，都是基于單跳時(shí)間同步機(jī)制。隨著無(wú)線傳感網(wǎng)絡(luò)的運(yùn)用與發(fā)展，傳感節(jié)點(diǎn)體積不斷縮小，單跳距離變小，整體網(wǎng)絡(luò)規(guī)模變大，同步誤差的累積現(xiàn)象必將越來(lái)越嚴(yán)重。目前也有比較新的同步算法，試圖盡量避開(kāi)單跳累加來(lái)解決這些問(wèn)題，如協(xié)作同步。

　　1  時(shí)間同步

　　1.1  時(shí)間同步不確定性的影響因素

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

圖1  報(bào)文傳輸延遲

　　發(fā)送時(shí)間：發(fā)送方用于構(gòu)造分組并將分組轉(zhuǎn)交給發(fā)送方的MAC層的時(shí)間。主要取決于時(shí)間同步程序的操作系統(tǒng)調(diào)用時(shí)間和處理器負(fù)載等。

　　訪問(wèn)時(shí)間：分組到達(dá)MAC層后，獲取信道發(fā)送權(quán)的時(shí)間。主要取決于共享信道的競(jìng)爭(zhēng)、當(dāng)前的負(fù)載等。

　　傳送時(shí)間：發(fā)送分組的時(shí)間，主要取決于報(bào)文的長(zhǎng)度等。

　　傳播時(shí)間：分組離開(kāi)發(fā)送方后，并將分組傳輸?shù)浇邮辗街g的無(wú)線傳輸時(shí)間。主要取決于傳輸介質(zhì)、傳輸距離等。

　　接收時(shí)間：接收端接收到分組，并將分組傳送到MAC層所需的時(shí)間。

　　接受時(shí)間：處理接收到分組的時(shí)間。主要受到操作系統(tǒng)的影響。

　　1.2  典型時(shí)間同步算法分析

　　1.2.1  TPSN算法分析

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

　　則在T4時(shí)刻，若在同步節(jié)點(diǎn)A的本地時(shí)間增加修正量m，就能達(dá)到同步節(jié)點(diǎn)A與參考節(jié)點(diǎn)B之間的同步。

　　1.2.2  RBS算法分析

　　RBS算法是基于接收者-接收者的同步算法。首先參考節(jié)點(diǎn)廣播一個(gè)參考分組，當(dāng)同步節(jié)點(diǎn)A收到這個(gè)分組，記下自己的本地時(shí)鐘為T(mén)21，當(dāng)同步節(jié)點(diǎn)B收到這個(gè)分組時(shí)，也記下自己的本地時(shí)鐘為T(mén)22，然后同步節(jié)點(diǎn)A與同步節(jié)點(diǎn)B交換本地時(shí)鐘T21與T22，這時(shí)其中一個(gè)節(jié)點(diǎn)只要根據(jù)時(shí)間差值m=T21-T22，修改自己的時(shí)鐘就能達(dá)到與另一個(gè)節(jié)點(diǎn)之間的同步。在多跳網(wǎng)絡(luò)中，RBS算法采用多次廣播同步消息，接收節(jié)點(diǎn)根據(jù)接收到同步消息的平均值，同時(shí)采用最小平方線性回歸方法進(jìn)行線性擬合以減小同步誤差。

　　1.2.3  DMTS算法分析

　　DMTS算法是基于發(fā)送者-接收者的單向時(shí)間同步算法。當(dāng)發(fā)送節(jié)點(diǎn)在檢測(cè)到通道空閑時(shí)，給廣播分組加上時(shí)間戳t0,從而排除了發(fā)送節(jié)點(diǎn)的處理延遲與MAC層的訪問(wèn)延遲。并假設(shè)發(fā)送報(bào)文的長(zhǎng)度為NA個(gè)比特（包括前導(dǎo)碼與同步字），傳送每個(gè)比特的時(shí)間為t，而接收者在接收完同步字后，記錄下此時(shí)的本地時(shí)間為t1,并在調(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+（t2-t1）。

　　可以看出，TPSN平均單跳誤差為17.61μs,DMTS平均單跳誤差為30μs,RBS平均單跳誤差為6.29μs, TPSN平均4跳誤差為21.43μs,DMTS平均單跳誤差為151μs,RBS平均4跳誤差為9.97μs。

　　1.2.4  其他算法分析

　　LTS協(xié)議是基于發(fā)送-接收同步機(jī)制發(fā)展而來(lái)，提出了集中式和分布式LTS多跳時(shí)間同步算法。LTS協(xié)議首先把網(wǎng)絡(luò)組成廣度優(yōu)先生成樹(shù)拓?fù)浣Y(jié)構(gòu)，并沿著樹(shù)的每條邊進(jìn)行單跳成對(duì)同步。參考節(jié)點(diǎn)的子節(jié)點(diǎn)同步完成后，又以該節(jié)點(diǎn)為參考節(jié)點(diǎn)，采用同樣方式繼續(xù)同步下去，直到同步完成。

　　單跳成對(duì)同步采用TPSN同步方法。成對(duì)同步的次數(shù)是邊數(shù)的線性函數(shù)。Hui Dui等人提出來(lái)的HRTS 利用了廣播的特性，只需要一次同步過(guò)程可以完成一個(gè)單跳組網(wǎng)所有節(jié)點(diǎn)的同步，進(jìn)一步降低了LTS協(xié)議的功耗。HRTS算法不再采用廣度優(yōu)先生成樹(shù)的邊，采用的是廣度優(yōu)先生成樹(shù)非葉子節(jié)點(diǎn)個(gè)數(shù)的線性函數(shù)。相較于LTS協(xié)議，HRTS算法以犧牲一定的精確來(lái)降低了整個(gè)網(wǎng)絡(luò)的功耗。

　　BTS同步方法類似于HRTS算法，也是先建立廣度優(yōu)先成生樹(shù)拓?fù)浣Y(jié)構(gòu)，只不過(guò)BTS采用的是時(shí)間轉(zhuǎn)換技術(shù)，以達(dá)到整個(gè)網(wǎng)絡(luò)的時(shí)間同步，而HRTS直接對(duì)同步節(jié)點(diǎn)的本地時(shí)間進(jìn)行修改，得到全網(wǎng)的同步，同步報(bào)文個(gè)數(shù)降為HRTS協(xié)議的2／3。

　　PBS同步算法的思想是參考節(jié)點(diǎn)與簇首節(jié)點(diǎn)之間采用雙向同步方法，與TPSN相似，其他節(jié)點(diǎn)（在兩個(gè)節(jié)點(diǎn)的通信范圍內(nèi)）可以偵聽(tīng)到同步消息，就可以根據(jù)接收者-接收者同步方法同步。類似于RBS同步，PBS同步的前提是每個(gè)同步節(jié)點(diǎn)必須在簇首節(jié)點(diǎn)的通信范圍之內(nèi)。

　　ETSP算法主要采用的是設(shè)置門(mén)檻值N來(lái)選擇同步算法，當(dāng)父節(jié)點(diǎn)的子節(jié)點(diǎn)小于或等于N時(shí)，采用接收-接收（RBS）同步模式，否則采用發(fā)送-接收（TPSN）同步模式。N值的選擇采用N2-3N-2m=0來(lái)計(jì)算，式中m=RxTx，Rx為節(jié)點(diǎn)的接收次數(shù)，Tx為傳播次數(shù)。

　　FTSP同步算法精度高的原因是，發(fā)送者在發(fā)送一個(gè)同步請(qǐng)求報(bào)文時(shí)連續(xù)標(biāo)記了多個(gè)時(shí)間戳，接收者可以根據(jù)這幾個(gè)中斷時(shí)間計(jì)算出更精確的時(shí)間偏差。

　　1.2.5  協(xié)作同步技術(shù)

　　以上同步機(jī)制，無(wú)論怎樣改進(jìn)都是基于單跳同步基制，最近有人提出了協(xié)作同步技術(shù)，不再單純地從單跳同步機(jī)制上進(jìn)行改進(jìn)，而是通過(guò)信號(hào)疊加原理，使同步基準(zhǔn)節(jié)點(diǎn)能夠把同步消息直接發(fā)送到遠(yuǎn)方待同步的節(jié)點(diǎn)，使遠(yuǎn)方節(jié)點(diǎn)直接與基準(zhǔn)節(jié)點(diǎn)同步，消除了同步誤差單跳累加的結(jié)果。Hu A等人針對(duì)節(jié)點(diǎn)密度較高的網(wǎng)絡(luò)提出了一種協(xié)作同步算法，基本思想是參考節(jié)點(diǎn)根據(jù)同步周期發(fā)出m個(gè)同步脈沖，其一跳鄰居節(jié)點(diǎn)收到這個(gè)消息后保存起來(lái)，并根據(jù)最近的m個(gè)脈沖的發(fā)送時(shí)刻計(jì)算出參考節(jié)點(diǎn)的第m+1個(gè)同步消息發(fā)出的時(shí)間，并在計(jì)算出來(lái)的時(shí)刻同步與參考節(jié)點(diǎn)同時(shí)發(fā)送第m+1個(gè)同步消息。由于信號(hào)疊加，因此同步脈沖可以發(fā)送到更遠(yuǎn)的節(jié)點(diǎn)，當(dāng)然前提是網(wǎng)絡(luò)中節(jié)點(diǎn)密度較高的情況。A.Krohn等人提出了在物理層
物理層

　　物理層是TCP/IP 網(wǎng)絡(luò)模型的第一層,它雖然處于最底層,卻是整個(gè)通信系統(tǒng)的基礎(chǔ), 正如高速公路和街道是汽車通行的基礎(chǔ)一樣。理層為設(shè)備之間的數(shù)據(jù)通信提供傳輸媒體及 互連設(shè)備,為數(shù)據(jù)傳輸提供可靠的環(huán)境。

上面實(shí)現(xiàn)協(xié)作同步，只需要本地消息，避免了額外的消息同步交換開(kāi)銷。因此節(jié)點(diǎn)密度越高同步誤差也會(huì)越小。

　　2  時(shí)間同步算法誤差分析與比較

　　根據(jù)節(jié)點(diǎn)消息傳輸過(guò)程可以得到式（1）與式（2）：

　　在式（1）、（2）中，t1、t2是由標(biāo)準(zhǔn)時(shí)鐘所確定的，表示UTC時(shí)間。T1、T2分別是t1、t2所對(duì)應(yīng)的本地節(jié)點(diǎn)所測(cè)出的本地時(shí)間。SA代表節(jié)點(diǎn)A的報(bào)文發(fā)送時(shí)間，AA是發(fā)送報(bào)文的訪問(wèn)時(shí)間，TA→B是A節(jié)點(diǎn)按比特傳輸報(bào)文與B節(jié)點(diǎn)按比特接收?qǐng)?bào)文所需要的時(shí)間，PA→B是節(jié)點(diǎn)A傳播到節(jié)點(diǎn)B的時(shí)間。RB是節(jié)點(diǎn)B的報(bào)文接收處理過(guò)程時(shí)間。TNA是傳輸NA個(gè)比特的總時(shí)間。terror指?jìng)鬏敱忍氐恼`差，Rerror打時(shí)標(biāo)過(guò)程存在的誤差。DA→Bt1代表節(jié)點(diǎn)A與節(jié)點(diǎn)B在t1時(shí)刻的時(shí)偏。

　　對(duì)于TPSN算法，因?yàn)樵贛AC采用了加時(shí)間戳方法，因此消除了發(fā)送時(shí)間與訪問(wèn)時(shí)間對(duì)誤差的影響。因此對(duì)TPSN算法式（1）、（2）就可以簡(jiǎn)寫(xiě)為式（3）、（4）：

　　式中DA→Bt1=DA→Bt4+RDA→Bt1→t4。

　　同理可以得到T4，如下所示：

　　由以上各式可以得到時(shí)偏：

　　RDA→Bt1→t4代表從t1到t4時(shí)段內(nèi)，節(jié)點(diǎn)A相對(duì)于節(jié)點(diǎn)B增加的時(shí)偏。DA→Bt4是t4時(shí)刻節(jié)點(diǎn)A與節(jié)點(diǎn)B之間的時(shí)偏。則可以算出TPSN的同步誤差：

　　式中SUC=SA-SB，PUC=PA→B-PB→A，RUC=RB-RA。

　　對(duì)于DMTS算法，發(fā)送節(jié)點(diǎn)A在T0時(shí)刻檢測(cè)到空閑，接收節(jié)點(diǎn)B在報(bào)文到達(dá)時(shí)刻給報(bào)文加上時(shí)間戳T1,并在調(diào)整自己的本地時(shí)間記錄之前記錄下此時(shí)的時(shí)刻為T(mén)2，在T3時(shí)間完成調(diào)整。則可以得到：

　　　式中DA→Bt0=DA→Bt3+RDA→Bt0→t3。

　　由TmA→B+RB=n·t+Terror+Rerror+（T2-T1），其中n是前導(dǎo)碼的長(zhǎng)度，可以得到DMTS的時(shí)偏：

　　DMTS的誤差為：

　　對(duì)于RBS同步算法，可以得到：

　　則由式（8）與式（9）可以得到節(jié)點(diǎn)B的時(shí)偏m1為：

　　則可以得到節(jié)點(diǎn)B的同步誤差為：

　　從式（7）中可以看出，TPSN同步精度高的原因是在MAC層采用打時(shí)標(biāo)方式消除了發(fā)送時(shí)間與訪問(wèn)時(shí)間的影響，并在消息雙方向交換時(shí)消除了傳播時(shí)間的影響。缺點(diǎn)是點(diǎn)到點(diǎn)之間的同步，每次只能一對(duì)節(jié)點(diǎn)進(jìn)行時(shí)間同步，同步一次需要發(fā)送2個(gè)消息，接收2個(gè)消息，功耗較大。從式（10）可以看出DMTS同步誤差較大的原因是單播傳播，沒(méi)辦法消除Terror 與Rerror的影響，但DMTS同步一次只要消耗1個(gè)發(fā)送消息，1個(gè)接收消息，功耗較低。至于FTSP同步算法比DMTS高的原因是，發(fā)送者在發(fā)送一個(gè)同步請(qǐng)求報(bào)文時(shí)連續(xù)標(biāo)記了多個(gè)時(shí)間戳，接收者可以根據(jù)這幾個(gè)中斷時(shí)間，計(jì)算出更精確的時(shí)間偏差?？梢钥闯觯琑BS完全消除了發(fā)送方的影響，只是同步一次消耗3個(gè)發(fā)送消息，4個(gè)接收消息，功耗較大。而對(duì)于HRTS與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)，都適合不同的無(wú)線傳感網(wǎng)絡(luò)。精度高，相對(duì)功耗也較大。對(duì)特定的無(wú)線傳感網(wǎng)絡(luò)，選擇同步算法時(shí)應(yīng)該折中考慮精度與功耗。從整體上看，近年來(lái)有關(guān)時(shí)間同步算法的研究，大部分都是基于以往典型的單跳同步算法原理，進(jìn)一步從整體網(wǎng)絡(luò)中考慮誤差與功耗，結(jié)合最優(yōu)生成樹(shù)、分簇路由算法等，以平均整個(gè)網(wǎng)絡(luò)的功耗，降低節(jié)點(diǎn)傳輸?shù)奶鴶?shù)，提高同步的精度。協(xié)作同步算法側(cè)重于提高整個(gè)網(wǎng)絡(luò)的可擴(kuò)展性與健壯性，但要求節(jié)點(diǎn)具有相同的同步脈沖，比較困難，目前還需要進(jìn)一步的發(fā)展驗(yàn)證，也是未來(lái)可能很好的發(fā)展方向。