自組織網絡數據傳輸最短路徑路由算法仿真

李小玲，沈文娟，周新衛

(南昌大學共青學院，江西 共青城 332020)

1 引言

自組織網絡作為移動計算機網絡中的一種，具有隨意移動特性[1]。在計算機網絡中，路由始終處于重要位置。路由不僅能夠影響網絡的性能還會對自組織網絡本身帶來安全威脅。所謂的傳輸最短路徑，就是在知曉目標給定源以及目標節點的情況下，找出一條函數值最小的可行性路徑。最短路徑路由作為組合優化問題，在自組織網絡進行低時延傳輸時依然要對其進行綜合考慮，從而降低傳輸風險[2]。為此，相關學著針對網絡數據低時延傳輸最短路徑路由相關問題展開研究。

文獻[3]提出基于運動狀態感知的容遲網絡路由算法。該算法首先利用運動感知對路由進行噴射搜索，并進一步對搜索結果進行闡述；再基于DTN算法對網絡中各項參數的性能差異進行計算，獲取路由的參數繪圖；最后基于VANET環境實現對路由的最短路徑計算。該方法由于未能依據容積Kalman濾波對數據低時延傳輸時的時延進行補償，導致該算法獲取傳輸最小路徑時的網絡節點能量消耗高。文獻[4]提出基于SDN的衛星網絡多QoS目標優化路由算法。該算法首先創建軟件衛星網絡，并提出多種約束條件構建路由的優化模型；利用拉格朗日松弛算法松弛優化模型；最后采用梯度算法對模型進行迭代計算，通過計算結果獲取網絡路由的帶寬時延，從而實現最短路徑的獲取。該算法由于在孤立點降維時存在一定偏差，所以該算法的時間開銷大。文獻[5]提出基于能耗區域感知的無線傳感器網絡路由算法。該算法首先對網絡節點影響進行消除，構造簇頭節點候選集；再根據節點集的位置和方向，利用預感知區域理論，構建網絡節點評價指標，選擇附屬簇頭；最后通過選擇的簇頭信息實現數據的低時延傳輸。該算法由于在獲取評價指標時存在一定問題，所以該方法的輸出幅值高。

為解決上述數據低時延傳輸過程中存在的問題，提出自組織網絡數據低時延傳輸最短路徑路由算法。

2 時延補償

2.1 傳輸信道模型

在獲取自組織網絡數據低時延傳輸最短路徑前，需優化控制網絡中的數據低延遲。

首先構建自組織網絡的傳輸信道模型[6]，依據網絡中相鄰節點的信道寬度，將自組織網絡中的節點幀分成各自獨立的Nc個碼片，依據信道的均衡控制法，創建自組織網絡的數據低時延信道模型。當傳輸過程中延遲時間能夠滿足cjTc

JMDMMA=ρ·E[(|z(k)|2-RMDMMA(k)2)]

(1)

式中，網絡信道內的衰減系數標記為ρ，網絡的最少節點數量標記為RMDMMA(k)形式，自組織網絡的覆蓋率η的變化特征標記為z(k)，網絡的節點總量標記為E，JMDMMA為擴展函數。將N個節點隨機裝置在固定區域內，利用誤差生成函數對網絡信道進行適當補償，從而降低數據傳輸時的誤差延遲[7]。

依據自組織網絡中節點數據與相鄰節點數據之間的關系，對網絡傳輸信道進行補償。設定網絡相鄰節點的輸出特征為T，利用時滯的補償控制法，獲取自組織網絡信道控制的迭代次數，結果如下式所示

(2)

通過上述計算結果，對網絡節點的相鄰節點集進行計算，獲取數據傳輸時的經過通頻帶p(t)的帶寬，并利用空間調度法對網絡信道進行分配[8]。分配結果如下式所示

pri(t)=p(t)*hi(t)+npi(t)

(3)

式中，信道的沖擊響應特征標記為hi(t)，相關性特征標記成p(t)，分配條件標記為pri(t)，通頻帶寬為npi(t)。基于上述分配條件，創建網絡時空評估模型，對自組織網絡內的信道進行優化配置。

2.2 碼間干擾抑制

基于創建的自組織網絡信道模型，利用干擾抑制方法控制數據低時延傳輸時存在的干擾。設定模型的輸出序列為xn，期望響應為dn，網絡異常節點的響應特征如下式所示

(4)

式中，異常節點響應特征標記為d(t)，節點特征為t，a和c分別為序列數量，gc為干擾系數，網絡序列總量標記成n，網絡節點傳輸時延為Tc，網絡序列中第a個以及第c個序列標記成an和cn形式。

通過上述獲取的網絡節點響應特征，構建節點的異常檢測模型，獲取數據低時延傳輸的延遲誤差，過程如下式所示

(5)

根據獲取的數據低時延傳輸的延遲誤差，通過網絡模型對數據傳輸時的碼間干擾進行抑制，從而去除碼間噪聲，過程如下式所示

fF(k+1)=fF(k)-μ·?fF(k)JMMDMMA=

fF(k)-μF[ρ(k)(eMMDMMA(k)+jeMMDMMA-I(k))+

(1-ρ(k))(eR(k)+jeI(k))]y*

(6)

式中，碼間的抑制效果fF(k)。

2.3 延遲控制

依據容積Kalman濾波補償數據低時延傳輸時時延，從而實現對自組織網絡數據低時延傳輸時的延遲控制[9]。設定網絡節點的自身采樣間隔為d，數據低時延傳輸時的鏈路均衡模型如下式所示

(7)

式中，均衡調節系數標記為si(t)，信道分配特征在節點m處的時延特征標記成xm(t)，節點總特征為nm(t)，網絡閾值為p，節點系數為e，j，φ，m，i皆為自組織網絡節點指數。

在上述計算結果中加入擴展系數，獲取數據傳輸的濾波函數表達形式，結果如下式所示

(8)

式中，兩個網絡節點之間的距離為θi(t)，傳輸時延為T，擴展系數為δ，網絡中第i個節點特征的延遲系數標記為ai(t)，相鄰節點特征為Ts，濾波函數為h(t)。

依據上述擴展函數，設定網絡節點總數為N，利用信道估計方法，完成對數據低時延傳輸時的優化控制，過程如下式所示

(9)

式中，自組織網絡中第n條路徑的網絡延時系數為an(t)，時延控制值為c(τ，t)，擴展函數為δ，網絡節點半徑為π，頻率為f，采樣速率為τ，各個節點特征為t。

利用上述計算結果，對網絡數據低時延傳輸過程中的時延進行補償，提高傳輸時的控制能力。

3 獲取最短路徑

基于上述數據低時延傳輸時的優化控制，利用DSPR算法完成網絡的路由節點部署，獲取網絡數據傳輸時的最短路徑。

3.1 獲取同質簇

3.1.1 選擇初始簇頭

選擇網絡內節點初始簇時，需要利用分布方式對簇頭進行選擇。設定P為候選節點的選中概率，獲取過程如下式所示

(10)

式中，網絡中的節點數量為N，選定為候選節點si的數量為k。

在數據傳輸的初始階段，設定一個網絡節點的閾值為ξ∈[0，1]，若選中概率P小于等于ξ，可直接將其作為候選節點si。

設定Eresidual(si)為候選節點的剩余能量，相鄰節點簇頭為Ne(si)，相鄰節點簇頭個數為|Ne(si)|。基于傳輸機制，候選節點之間會存在競爭關系，因此要引入逃避機制[10]。候選節點的逃避時間如下式所示

(11)

式中，候選節點si的延時時間標記為T，相鄰節點簇頭標記成Ne(si)，剩余能量標記成Eresidual(si)，初始能量標記成Einit(si)。

逃避結束后，若沒有撞到其網絡節點說明節點逃避時間短，該節點可退出競爭直接作為本幀初始簇頭CH。

3.1.2 網關簇頭

為連接自組織網絡，需選擇出更多的簇頭。當簇頭之間無法連接時，要在網絡節點中選擇更多節點，作為轉發節點幫助初始簇頭進行連接，這些轉發節點作為網絡的網絡簇頭[11]。在初始簇頭競爭過后，落選的網絡節點可進行二次競爭。該次競爭會偏重節點的剩余能量以及相鄰的簇頭數量，從而保證初始簇頭的連接。節點競爭時依然要對退避時間進行規劃，過程如下式所示

×|Ne(si)|T

(12)

等到退避時間完成，對網絡節點周圍進行檢測，若相鄰節點數量為0，說明網絡節點未被初始簇頭覆蓋，該節點可成為網關簇頭。若相鄰節點數量為1，說明該節點被一個初始簇頭覆蓋，若相鄰節點數量大于2時，說明網絡節點在多個初始簇頭的通信范圍內，若周圍簇頭沒有發生連接，將其作為網關簇頭，幫助其連接。若周邊簇頭處于連接狀態，可使其節點加入其中一方。

若競爭時發現該節點已成為初始簇頭，該節點直接退出競爭。基于上述選取的簇頭節點為基礎，完成自組織網絡路由的部署，實現網絡的路由優化。

3.2 最短路徑選擇

對自組織網絡路由進行優化主要目的就是獲取網絡在數據低時延傳輸時的源節點最短路徑[12]。

由于障礙物的影響，獲取的最短路徑可能會產生路徑偏離，因此要利用貪婪的周邊無狀態路由對情況進行具體分析。設定源簇頭與傳輸目的地之間的距離為d+b，障礙物長為l、寬為b，基于ROT策略，可獲取最短路徑的路徑長度，過程如下式所示

(13)

基于上述計算結果，實現對自組織網絡數據低時延傳輸的最短路徑獲取，從而降低網絡能耗。

4 實驗

為驗證上述網絡數據傳輸最短路徑路由算法的 整體有效性，需要對此算法進行測試。

分別采用本文提出的自組織網絡數據低時延傳輸最短路徑路由算法(算法1)、文獻[3]提出的基于運動狀態感知的容遲網絡路由算法(算法2)、文獻[5]提出的基于能耗區域感知的無線傳感器網絡路由算法(算法3)進行測試．

1)不同算法的網絡節點能量消耗測試

在自組織網絡進行數據低時延傳輸時，利用算法1、算法2以及算法3對選取最短路徑后的網絡節點能量消耗情況進行測試，測試結果如圖1所示。

圖1 不同算法的網絡節點能量消耗測試

分析圖1可知，隨著數據傳輸時間的不斷增加，網絡節點的能量消耗呈不同程度的上升趨勢。算法2在測試初期的節點消耗與算法1相接近，但是隨著傳輸時間的增加，該算法下的網絡節點能量消耗呈急速上升趨勢，算法3所檢測出的網絡節點能量消耗是三種算法中最大的。綜上所述。方法1在進行數據低時延傳輸時，網絡節點的能量消耗小。

2)不同算法的網絡壽命測試

采用算法1、算法2以算法3進行數據傳輸最短路徑獲取后，對多自組織網絡的網絡壽命進行測試，測試結果如圖2所示。

圖2 不同算法的網絡壽命測試

分析圖2所示，隨著網絡內障礙物的增加，三種算法下的網絡壽命提升百分比呈現不同程度的下降趨勢。當網絡中障礙物較少時，算法3與算法1測試出的網絡壽命提升百分比相同，且二者高于算法2，但是隨著網絡中障礙物的不斷增加，算法2的網絡壽命提升百分比逐漸高于算法3。方法1所檢測出的網絡壽命提升百分比要高于其兩種算法。

3)不同算法的時間開銷測試

數據在進行低時延傳輸時，控制時間開銷的長短會直接反映出算法的優劣，對算法1、算法2以及算法3在網絡數據傳輸時的時間開銷進行測試，測試結果如圖3所示。

圖3 不同算法的時間開銷對比

分析圖3可知，時間開銷少，算法性能越好。隨著網絡節點的不斷增加，三種算法的控制時間開銷呈上升趨勢。算法2與算法3在測試初期的控制時間開銷相一致，但是隨著網絡節點數量的增加，算法3的時間開銷逐漸高于算法2。算法1所檢測出的時間開銷要低于算法2以及算法3，這主要是因為算法1依據容積Kalman濾波對數據低時延傳輸時的時延進行補償，從而實現對自組織網絡數據低時延傳輸時的延遲控制。所以方法1在進行數據低時延傳輸時的控制時間開銷小。

4)數據傳輸優化控制前后輸出幅值測試

基于上述實驗結果，對數據低時延傳輸優化控制前后的輸出幅值進行測試，測試結果如4所示。

圖4 數據傳輸優化控制前后輸出幅值測試

分析圖4可知，網絡在進行數據傳輸時，輸出的幅值越高，傳輸時的數據質量越低。該算法數據傳輸優化控制后的輸出幅值要低于優化控制前。

5 結束語

隨著網絡技術的不斷更新，自組織網絡的形式愈加復雜。如何在數據進行低時延傳輸時利用最短的時間找出最短路徑，成為該領域不斷需要解決的問題。針對網絡數據傳輸過程最短路徑路由算法中存在的問題，提出自組織網絡數據低時延傳輸最短路徑路由算法。該算法首先對數據傳輸時的網絡時延進行優化控制；再利用DSPR算法完成網絡的路由節點部署；最后通過路由部署結果實現對網絡數據傳輸的最短路徑獲取。該算法由于在網絡節點部署過程中存在一定問題，今后會針對該缺陷繼續對該算法進行必要的優化處理。