宋曉雪, 魏 路, 林水生

(1. 電子科技大學(xué)通信與信息工程學(xué)院, 四川 成都 611731; 2. 通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點(diǎn)實(shí)驗(yàn)室, 河北 石家莊 050811)

0 引 言

無(wú)線自組網(wǎng)中節(jié)點(diǎn)的頻繁移動(dòng),網(wǎng)絡(luò)拓?fù)涞目焖僮兓?導(dǎo)致節(jié)點(diǎn)之間通信鏈路的不穩(wěn)定[1],使得同步過(guò)程中傳輸?shù)姆纸M碰撞率以及丟包率顯著增大,難以將成熟的時(shí)間同步算法應(yīng)用于動(dòng)態(tài)網(wǎng)絡(luò)中。而高效精確的時(shí)間同步是無(wú)線自組網(wǎng)的前提[2],確保正常的數(shù)據(jù)交互和時(shí)隙調(diào)度,所以時(shí)間同步技術(shù)是無(wú)線自組網(wǎng)的重要研究?jī)?nèi)容。

在時(shí)間同步方面,在給出時(shí)鐘同步模型的基礎(chǔ)上[3],對(duì)時(shí)鐘漂移在同步過(guò)程中的影響進(jìn)行了詳細(xì)的數(shù)值分析[4-5],以及對(duì)時(shí)鐘偏差進(jìn)行比較精確地估計(jì)[6-8]。而在無(wú)線自組網(wǎng)中,不同同步算法有不同的特性[9],以較高的同步精度為前提,減少同步過(guò)程所需的分組數(shù)量是至關(guān)重要的[10]。通過(guò)減少同步分組的傳輸量,減少了冗余分組[11],進(jìn)而提高了同步效率,使得全網(wǎng)同步具備了更快的收斂速度[12]。在動(dòng)態(tài)網(wǎng)絡(luò)的時(shí)間同步中,某一性能得到提升,但對(duì)同步分組的傳輸沒有很好地控制[13],也有為了均衡各個(gè)性能而只能在兩跳的范圍內(nèi)有效工作,網(wǎng)絡(luò)規(guī)模局限性比較大[14]。對(duì)網(wǎng)絡(luò)拓?fù)涞膬?yōu)化策略[15],以時(shí)延均衡拓?fù)涓拍顬榛A(chǔ)的時(shí)鐘同步協(xié)議,但算法較為復(fù)雜,以及基于接收者-接收者同步方案的能量高效率同步協(xié)議[16],可以顯著降低通信開銷以實(shí)現(xiàn)低功耗。以上研究都沒有考慮在動(dòng)態(tài)網(wǎng)絡(luò)中既保證適當(dāng)?shù)木扔质沟猛椒纸M傳輸數(shù)量減少。

本文基于動(dòng)態(tài)無(wú)線自組網(wǎng)的特性,通過(guò)雙向交互同步獲得節(jié)點(diǎn)間的時(shí)延,運(yùn)用局部加權(quán)線性回歸對(duì)時(shí)間戳進(jìn)行擬合,使得同步算法能夠自適應(yīng)于無(wú)線自組網(wǎng)的復(fù)雜環(huán)境。

1 基本時(shí)間同步算法

本文時(shí)間同步算法采用分布式與集中式相結(jié)合的同步方式[17]。在分布式同步中采用了發(fā)送-接收雙向交互同步算法[18],以及在集中式同步中采用了洪泛時(shí)間同步算法。

1.1 基于發(fā)送者-接收者的同步算法

傳感器網(wǎng)絡(luò)時(shí)間同步協(xié)議(timing-sync protocol for sensor network,TPSN)[19]是典型的基于發(fā)送者-接收者的雙向同步機(jī)制的同步算法。具體報(bào)文交互過(guò)程如圖1所示,節(jié)點(diǎn)A是待同步節(jié)點(diǎn),在T1時(shí)刻給節(jié)點(diǎn)B發(fā)送同步請(qǐng)求報(bào)文,并把時(shí)間戳作為報(bào)文消息也發(fā)送出去,隨后節(jié)點(diǎn)B在自己本地時(shí)間為T2時(shí)刻收到該報(bào)文,經(jīng)過(guò)一段時(shí)間的處理后,在T3時(shí)刻給節(jié)點(diǎn)A發(fā)送響應(yīng)報(bào)文,同樣T2和T3時(shí)間戳包含在報(bào)文中,在節(jié)點(diǎn)A的本地時(shí)間為T4時(shí)刻時(shí)收到響應(yīng)報(bào)文,因此節(jié)點(diǎn)A還有用于時(shí)間同步的4個(gè)時(shí)刻信息:

TA(t4)=TB(t3)-θA,B+delayB

(1)

TA(t4)=TB(t3)-θA,B+delayB

(2)

假設(shè)A到B,B到A的傳播延時(shí)相同,可計(jì)算出節(jié)點(diǎn)A和節(jié)點(diǎn)B之間的傳輸延時(shí):

(3)

圖1 TPSN節(jié)點(diǎn)的報(bào)文交互過(guò)程Fig.1 Message exchange process for TPSN

1.2 洪泛時(shí)間同步協(xié)議

洪泛時(shí)間同步協(xié)議(flooding time synchronization protocol,FTSP)[20]采用層次結(jié)構(gòu)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的時(shí)間同步。在層級(jí)結(jié)構(gòu)中采用分級(jí)的形式進(jìn)行逐級(jí)同步,根節(jié)點(diǎn)設(shè)置為0級(jí)節(jié)點(diǎn),在根節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)設(shè)置為1級(jí)節(jié)點(diǎn),一跳鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)設(shè)置為2級(jí)節(jié)點(diǎn),依次設(shè)置節(jié)點(diǎn)級(jí)別。同步時(shí),級(jí)別為i+1的節(jié)點(diǎn)與級(jí)別為i的節(jié)點(diǎn)進(jìn)行同步,在層級(jí)結(jié)構(gòu)網(wǎng)絡(luò)中的節(jié)點(diǎn)都會(huì)收到同步報(bào)文完成同步然后繼續(xù)廣播同步報(bào)文,以讓下一級(jí)節(jié)點(diǎn)完成同步。因此,同步過(guò)程可以看成是級(jí)別小的節(jié)點(diǎn)向級(jí)別大的節(jié)點(diǎn)逐層擴(kuò)散的同步方式,最終全網(wǎng)節(jié)點(diǎn)達(dá)成同步。

如圖2所示,節(jié)點(diǎn)0為根節(jié)點(diǎn),根節(jié)點(diǎn)向外廣播同步包,一層節(jié)點(diǎn)(1,2,3,4,5,6)收到同步包后根據(jù)回歸擬合方程進(jìn)行時(shí)間同步,然后通過(guò)隨機(jī)競(jìng)爭(zhēng)方式搶占信道,接著廣播本地同步之后的時(shí)間以便二層節(jié)點(diǎn)(7,8,9,10,11,12)進(jìn)行同步。本文算法使用FTSP的廣播信息功能以及利用局部加權(quán)線性回歸的思想,完成所有節(jié)點(diǎn)的同步過(guò)程。

圖2 洪泛時(shí)間同步模型Fig.2 Synchronization model for FTSP

在FTSP中[21],算法采用一元線性回歸對(duì)時(shí)間漂移率和偏移進(jìn)行估計(jì)和補(bǔ)償。在線性回歸中,對(duì)于給定節(jié)點(diǎn)的時(shí)間戳對(duì)(t2,t1),線性回歸算法通過(guò)選擇合適的參數(shù)向量θ以最小化flin(θ):

(4)

在一定的樣本集中,當(dāng)采用線性方式擬合數(shù)據(jù),若樣本集中的數(shù)據(jù)的自變量和應(yīng)變量有較好的線性模型時(shí),線性擬合能很好地體現(xiàn)這種關(guān)系,若兩變量沒有明顯的線性關(guān)系時(shí),線性擬合出的效果會(huì)明顯出現(xiàn)偏差,得出的結(jié)果與實(shí)際相差較大,將使得這種線性回歸出現(xiàn)嚴(yán)重的欠擬合。

2 局部加權(quán)洪泛時(shí)間同步算法

2.1 局部加權(quán)線性回歸

本文采用局部加權(quán)線性回歸(locally weighted linear regression,LWLR)[22]實(shí)現(xiàn)時(shí)間戳對(duì)的擬合。

LWLR的處理方式如下:選擇合適的參數(shù)向量θ最小化fLWLR(θ):

(5)

式中,w(i)是對(duì)局部數(shù)據(jù)選擇的一種參數(shù)[23]。w(i)的數(shù)學(xué)定義為

(6)

式中,t表示預(yù)測(cè)的值;t(i)是第i個(gè)時(shí)間戳樣本數(shù)據(jù);τ表示該權(quán)值代表的衰減程度,τ值越大,該權(quán)值衰減得越慢,否則越快,τ也是LWLR時(shí)間同步算法中需要考慮的重要參數(shù)。式(6)表明，隨著t(i)離t越遠(yuǎn),權(quán)值w(i)越小。

θ=(XTWX)-1XTWY

(7)

得到擬合參數(shù)值,其中

2.2 同步過(guò)程

本文同步算法采用分布式與集中式結(jié)合的同步方式,既避免了分布式同步的復(fù)雜,開銷較大,且收斂較慢,又克服了集中式同步過(guò)分依賴于參考節(jié)點(diǎn),并且交互包的數(shù)量較多,存在較大的碰撞率,具體同步過(guò)程如圖3所示。

圖3 同步過(guò)程Fig.3 Synchronization process

首先,在分布式階段運(yùn)用TPSN建立各個(gè)節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)的動(dòng)態(tài)時(shí)延表,每個(gè)節(jié)點(diǎn)會(huì)得到一跳鄰居節(jié)點(diǎn)的時(shí)延,具體時(shí)延表如表1所示。這個(gè)階段把網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行編號(hào),當(dāng)時(shí)延表中包含所有的節(jié)點(diǎn)編號(hào)時(shí),意味著時(shí)延表建立完成。此時(shí),根據(jù)每個(gè)節(jié)點(diǎn)的時(shí)延表中所包含的節(jié)點(diǎn)個(gè)數(shù)進(jìn)行參考節(jié)點(diǎn)的選取,把鄰居節(jié)點(diǎn)較多的節(jié)點(diǎn)設(shè)置為參考節(jié)點(diǎn),避免了始終使用同一個(gè)參考節(jié)點(diǎn),使得參考節(jié)點(diǎn)的選取引入了一定的隨機(jī)性。

表1 節(jié)點(diǎn)動(dòng)態(tài)時(shí)延關(guān)系

當(dāng)時(shí)延表建立完成并且參考節(jié)點(diǎn)確定后進(jìn)入集中式同步,在參考節(jié)點(diǎn)上利用FTSP廣播其本地時(shí)間,其他所有節(jié)點(diǎn)根據(jù)此時(shí)間以及本地的時(shí)延表更新它們的本地時(shí)間,并且把更新完成的時(shí)間廣播出去。如果節(jié)點(diǎn)已經(jīng)更新完成就丟棄收到的廣播報(bào)文,否則進(jìn)行更新,直到所有節(jié)點(diǎn)更新完成從而時(shí)間達(dá)到同步。具體同步過(guò)程如下。

步驟1各個(gè)節(jié)點(diǎn)發(fā)送同步請(qǐng)求包,接收來(lái)自一跳鄰居節(jié)點(diǎn)的同步應(yīng)答包,并建立與一跳鄰居節(jié)點(diǎn)的時(shí)延表。在發(fā)送包的過(guò)程中,對(duì)每個(gè)發(fā)送包以及接受包的每個(gè)字節(jié)標(biāo)記時(shí)間戳,為L(zhǎng)WLR建立時(shí)間戳對(duì)。在這個(gè)過(guò)程中,若接受到的節(jié)點(diǎn)ID已經(jīng)存在于時(shí)延表中則丟棄該請(qǐng)求包或應(yīng)答包。

步驟2檢查所有時(shí)延表中的節(jié)點(diǎn)ID是否達(dá)到系統(tǒng)中節(jié)點(diǎn)總數(shù)。若是,則計(jì)數(shù)各個(gè)節(jié)點(diǎn)時(shí)延表所包含的節(jié)點(diǎn)數(shù),把包含節(jié)點(diǎn)數(shù)最多的那個(gè)節(jié)點(diǎn)設(shè)置為參考節(jié)點(diǎn),并對(duì)各兩節(jié)點(diǎn)之間進(jìn)行LWLR擬合,得到擬合參數(shù),進(jìn)入第二階段同步;否則各個(gè)節(jié)點(diǎn)繼續(xù)發(fā)送同步請(qǐng)求包。

步驟3把參考節(jié)點(diǎn)設(shè)置為進(jìn)行FTSP源節(jié)點(diǎn),廣播自己的本地時(shí)間,收到該時(shí)間包的節(jié)點(diǎn)根據(jù)時(shí)延表查找到對(duì)應(yīng)的時(shí)延,并且根據(jù)相應(yīng)擬合曲線計(jì)算該節(jié)點(diǎn)的時(shí)間,從而得到與發(fā)送節(jié)點(diǎn)的擬合時(shí)延,該擬合時(shí)延與時(shí)延表中的時(shí)延進(jìn)行對(duì)比,從而進(jìn)行本地時(shí)間調(diào)整,并設(shè)置狀態(tài)為已調(diào)整,然后再把各自的本地時(shí)間廣播出去,以讓其鄰居節(jié)點(diǎn)進(jìn)行時(shí)間調(diào)整。若收到時(shí)間包的節(jié)點(diǎn)已調(diào)整好時(shí)間,則廣播自己的本地時(shí)間。

步驟4檢查所有節(jié)點(diǎn)的狀態(tài)是否都為已調(diào)整,是則結(jié)束本次同步,否則參考節(jié)點(diǎn)繼續(xù)廣播當(dāng)前本地時(shí)間。

3 仿真驗(yàn)證

對(duì)LWLR中的參數(shù)τ進(jìn)行選擇,測(cè)試環(huán)境為Python2.7,根據(jù)仿真表明,如圖4所示,當(dāng)τ=1.0時(shí)權(quán)重值很大,相當(dāng)于所有樣本點(diǎn)都是一樣的權(quán)重,擬合出的曲線與線性回歸是一樣的。如圖5所示,當(dāng)τ=0.01時(shí)得到非常好的效果,體現(xiàn)了樣本點(diǎn)間的特性。如圖6所示,當(dāng)τ=0.001時(shí)引入了太多的噪聲點(diǎn),出現(xiàn)了過(guò)擬合現(xiàn)象。所以,τ取0.01較為合適。

圖4 τ=1.0時(shí)的擬合曲線Fig.4 Fitting curve when τ=1.0

圖5 τ=0.01時(shí)的擬合曲線Fig.5 Fitting curve when τ=0.01

圖6 τ=0.001時(shí)的擬合曲線Fig.6 Fitting curve when τ=0.001

把得到的參數(shù)τ值運(yùn)用于LWLR中,對(duì)本文中的同步算法進(jìn)行仿真實(shí)驗(yàn),所使用的系統(tǒng)環(huán)境為Ubuntu-16.04,工具為ns-allinone-2.35[24]。仿真參數(shù)如表2所示,分別在不同節(jié)點(diǎn)數(shù)以及不同速度下對(duì)同步精度和分組數(shù)量進(jìn)行仿真。TF-LIN表示TPSN和線性回歸的FTSP,也就是基本的FTSP時(shí)間同步算法；TF-LWLR表示TPSN和LWLR的FTSP,即本文提出的對(duì)FTSP算法的改進(jìn)。

表2 仿真參數(shù)

圖7為不同算法完成同步過(guò)程發(fā)送同步分組數(shù)量的對(duì)比,可以看出,網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目越多,節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)也較多,完成同步所需的同步分組也增加。但TF-LIN和TF-LWLR要比單純的TPSN增長(zhǎng)緩慢且分組數(shù)量也比較少。由于TF-LIN和TF-LWLR只是對(duì)回歸方式進(jìn)行了優(yōu)化,并不影響兩者同步的分組數(shù)量,所以增長(zhǎng)趨勢(shì)大致相同。從圖7中可以看出,本文提出的算法TF-LWLR相比經(jīng)典TPSN在同步分組的傳輸數(shù)量方面平均降低了30%左右。

圖7 不同節(jié)點(diǎn)數(shù)目的同步分組數(shù)量對(duì)比Fig.7 Comparison of synchronized packets number fordifferent number of nodes

圖8為不同算法在不同速度下發(fā)送同步分組數(shù)量的對(duì)比,可以看出TF-LWLR隨著網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)速度的增加,所需的同步分組傳輸數(shù)量要少于TPSN,但也表現(xiàn)出緩慢的遞增趨勢(shì),因?yàn)楫?dāng)節(jié)點(diǎn)速度增加后,通信鏈路可能容易失效,使得部分?jǐn)?shù)據(jù)包丟失,從而出現(xiàn)比較多的冗余分組。而TF-LIN和TF-LWLR遞增趨勢(shì)幾乎重合,說(shuō)明TF-LWLR在同步分組數(shù)量上與基本的FTSP效果相似,但優(yōu)于TPSN。

圖8 不同速度的同步分組數(shù)量對(duì)比Fig.8 Comparison synchronized packets number at different speeds

為了對(duì)比各種算法在時(shí)間同步的精度方面的性能,本文用最大誤差來(lái)體現(xiàn),即同步完成后系統(tǒng)中選取某兩個(gè)節(jié)點(diǎn)的最大時(shí)間誤差的絕對(duì)值。由圖9可看出,利用LWLR的TF-LWLR算法的同步精度要比其他兩種算法要低,說(shuō)明其能更好地對(duì)同步時(shí)間進(jìn)行擬合。另外,網(wǎng)絡(luò)規(guī)模越大,同步誤差表現(xiàn)出越來(lái)越大的遞增趨勢(shì),但TF-LWLR的增長(zhǎng)趨勢(shì)沒有其他兩種快速,說(shuō)明其同步誤差性能表現(xiàn)的要好。本文的算法使節(jié)點(diǎn)的同步精度提高了26%左右,而隨著節(jié)點(diǎn)數(shù)目的增加,同步誤差相對(duì)比較穩(wěn)定、增長(zhǎng)較慢。其次,隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加,TF-LIN的同步誤差要優(yōu)于TPSN,說(shuō)明TF-LIN更適用于大規(guī)模網(wǎng)絡(luò)。

圖9 不同節(jié)點(diǎn)數(shù)目的同步誤差對(duì)比Fig.9 Comparison of synchronization errors for differentnumber of nodes

圖10為不同算法在不同速度下同步完成后最大誤差的對(duì)比,可以看出，TF-LWLR隨著網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)速度的增加,最大誤差也會(huì)呈現(xiàn)緩慢的遞增趨勢(shì),同步精度受節(jié)點(diǎn)移動(dòng)速度的影響較大。這是由于節(jié)點(diǎn)移動(dòng)速度增加后,由于數(shù)據(jù)包丟失的嚴(yán)重性,從而使得同步時(shí)間延長(zhǎng),導(dǎo)致時(shí)鐘漂移加重,進(jìn)而導(dǎo)致同步精度的下降。但TF-LWLR隨著節(jié)點(diǎn)速度的增加,同步誤差要優(yōu)于TPSN和TF-LIN,其更適用于動(dòng)態(tài)拓?fù)渚W(wǎng)絡(luò)。

圖10 不同速度的同步誤差對(duì)比Fig.10 Comparison of synchronization errors at different speeds

4 結(jié) 論

本文對(duì)動(dòng)態(tài)網(wǎng)絡(luò)的特性提出一種時(shí)間同步算法,具體分為TPSN的時(shí)延建立以及FTSP的時(shí)間LWLR,這種方式既保證了合適的同步精度,又減少了同步過(guò)程所需的分組傳輸數(shù)量,一定程度上降低了同步延時(shí)。通過(guò)理論分析和仿真實(shí)驗(yàn)表明,該算法在動(dòng)態(tài)網(wǎng)絡(luò)中取得了良好的效果,對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目變化具有魯棒性。