無線自組網(wǎng)的自適應同步技術(shù)研究

宋曉雪, 魏 路, 林水生

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

0 引 言

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

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

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

1 基本時間同步算法

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

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

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

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

(1)

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

(2)

假設A到B,B到A的傳播延時相同,可計算出節(jié)點A和節(jié)點B之間的傳輸延時:

(3)

圖1 TPSN節(jié)點的報文交互過程Fig.1 Message exchange process for TPSN

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

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

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

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

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

(4)

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

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

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

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

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

(5)

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

(6)

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

θ=(XTWX)-1XTWY

(7)

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

2.2 同步過程

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

圖3 同步過程Fig.3 Synchronization process

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

表1 節(jié)點動態(tài)時延關(guān)系

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

步驟1各個節(jié)點發(fā)送同步請求包,接收來自一跳鄰居節(jié)點的同步應答包,并建立與一跳鄰居節(jié)點的時延表。在發(fā)送包的過程中,對每個發(fā)送包以及接受包的每個字節(jié)標記時間戳,為LWLR建立時間戳對。在這個過程中,若接受到的節(jié)點ID已經(jīng)存在于時延表中則丟棄該請求包或應答包。

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

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

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

3 仿真驗證

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

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

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

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

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

表2 仿真參數(shù)

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

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

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

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

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

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

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

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

4 結(jié) 論

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