無線自組網的自適應同步技術研究

宋曉雪, 魏 路, 林水生

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

0 引 言

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

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

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

1 基本時間同步算法

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

1.1 基于發送者-接收者的同步算法

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

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

(1)

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

(2)

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

(3)

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

1.2 洪泛時間同步協議

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

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

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

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

(4)

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

2 局部加權洪泛時間同步算法

2.1 局部加權線性回歸

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

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

(5)

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

(6)

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

θ=(XTWX)-1XTWY

(7)

得到擬合參數值,其中

2.2 同步過程

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

圖3 同步過程Fig.3 Synchronization process

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

表1 節點動態時延關系

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

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

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

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

步驟4檢查所有節點的狀態是否都為已調整,是則結束本次同步,否則參考節點繼續廣播當前本地時間。

3 仿真驗證

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

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

表2 仿真參數

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

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

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

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

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

圖9 不同節點數目的同步誤差對比Fig.9 Comparison of synchronization errors for differentnumber of nodes

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

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

4 結 論

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