自組織網(wǎng)絡(luò)數(shù)據(jù)傳輸最短路徑路由算法仿真

李小玲，沈文娟，周新衛(wèi)

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

1 引言

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

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

為解決上述數(shù)據(jù)低時延傳輸過程中存在的問題，提出自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸最短路徑路由算法。

2 時延補(bǔ)償

2.1 傳輸信道模型

在獲取自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸最短路徑前，需優(yōu)化控制網(wǎng)絡(luò)中的數(shù)據(jù)低延遲。

首先構(gòu)建自組織網(wǎng)絡(luò)的傳輸信道模型[6]，依據(jù)網(wǎng)絡(luò)中相鄰節(jié)點的信道寬度，將自組織網(wǎng)絡(luò)中的節(jié)點幀分成各自獨立的Nc個碼片，依據(jù)信道的均衡控制法，創(chuàng)建自組織網(wǎng)絡(luò)的數(shù)據(jù)低時延信道模型。當(dāng)傳輸過程中延遲時間能夠滿足cjTc

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

(1)

式中，網(wǎng)絡(luò)信道內(nèi)的衰減系數(shù)標(biāo)記為ρ，網(wǎng)絡(luò)的最少節(jié)點數(shù)量標(biāo)記為RMDMMA(k)形式，自組織網(wǎng)絡(luò)的覆蓋率η的變化特征標(biāo)記為z(k)，網(wǎng)絡(luò)的節(jié)點總量標(biāo)記為E，JMDMMA為擴(kuò)展函數(shù)。將N個節(jié)點隨機(jī)裝置在固定區(qū)域內(nèi)，利用誤差生成函數(shù)對網(wǎng)絡(luò)信道進(jìn)行適當(dāng)補(bǔ)償，從而降低數(shù)據(jù)傳輸時的誤差延遲[7]。

依據(jù)自組織網(wǎng)絡(luò)中節(jié)點數(shù)據(jù)與相鄰節(jié)點數(shù)據(jù)之間的關(guān)系，對網(wǎng)絡(luò)傳輸信道進(jìn)行補(bǔ)償。設(shè)定網(wǎng)絡(luò)相鄰節(jié)點的輸出特征為T，利用時滯的補(bǔ)償控制法，獲取自組織網(wǎng)絡(luò)信道控制的迭代次數(shù)，結(jié)果如下式所示

(2)

通過上述計算結(jié)果，對網(wǎng)絡(luò)節(jié)點的相鄰節(jié)點集進(jìn)行計算，獲取數(shù)據(jù)傳輸時的經(jīng)過通頻帶p(t)的帶寬，并利用空間調(diào)度法對網(wǎng)絡(luò)信道進(jìn)行分配[8]。分配結(jié)果如下式所示

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

(3)

式中，信道的沖擊響應(yīng)特征標(biāo)記為hi(t)，相關(guān)性特征標(biāo)記成p(t)，分配條件標(biāo)記為pri(t)，通頻帶寬為npi(t)?；谏鲜龇峙錀l件，創(chuàng)建網(wǎng)絡(luò)時空評估模型，對自組織網(wǎng)絡(luò)內(nèi)的信道進(jìn)行優(yōu)化配置。

2.2 碼間干擾抑制

基于創(chuàng)建的自組織網(wǎng)絡(luò)信道模型，利用干擾抑制方法控制數(shù)據(jù)低時延傳輸時存在的干擾。設(shè)定模型的輸出序列為xn，期望響應(yīng)為dn，網(wǎng)絡(luò)異常節(jié)點的響應(yīng)特征如下式所示

(4)

式中，異常節(jié)點響應(yīng)特征標(biāo)記為d(t)，節(jié)點特征為t，a和c分別為序列數(shù)量，gc為干擾系數(shù)，網(wǎng)絡(luò)序列總量標(biāo)記成n，網(wǎng)絡(luò)節(jié)點傳輸時延為Tc，網(wǎng)絡(luò)序列中第a個以及第c個序列標(biāo)記成an和cn形式。

通過上述獲取的網(wǎng)絡(luò)節(jié)點響應(yīng)特征，構(gòu)建節(jié)點的異常檢測模型，獲取數(shù)據(jù)低時延傳輸?shù)难舆t誤差，過程如下式所示

(5)

根據(jù)獲取的數(shù)據(jù)低時延傳輸?shù)难舆t誤差，通過網(wǎng)絡(luò)模型對數(shù)據(jù)傳輸時的碼間干擾進(jìn)行抑制，從而去除碼間噪聲，過程如下式所示

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 延遲控制

依據(jù)容積Kalman濾波補(bǔ)償數(shù)據(jù)低時延傳輸時時延，從而實現(xiàn)對自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸時的延遲控制[9]。設(shè)定網(wǎng)絡(luò)節(jié)點的自身采樣間隔為d，數(shù)據(jù)低時延傳輸時的鏈路均衡模型如下式所示

(7)

式中，均衡調(diào)節(jié)系數(shù)標(biāo)記為si(t)，信道分配特征在節(jié)點m處的時延特征標(biāo)記成xm(t)，節(jié)點總特征為nm(t)，網(wǎng)絡(luò)閾值為p，節(jié)點系數(shù)為e，j，φ，m，i皆為自組織網(wǎng)絡(luò)節(jié)點指數(shù)。

在上述計算結(jié)果中加入擴(kuò)展系數(shù)，獲取數(shù)據(jù)傳輸?shù)臑V波函數(shù)表達(dá)形式，結(jié)果如下式所示

(8)

式中，兩個網(wǎng)絡(luò)節(jié)點之間的距離為θi(t)，傳輸時延為T，擴(kuò)展系數(shù)為δ，網(wǎng)絡(luò)中第i個節(jié)點特征的延遲系數(shù)標(biāo)記為ai(t)，相鄰節(jié)點特征為Ts，濾波函數(shù)為h(t)。

依據(jù)上述擴(kuò)展函數(shù)，設(shè)定網(wǎng)絡(luò)節(jié)點總數(shù)為N，利用信道估計方法，完成對數(shù)據(jù)低時延傳輸時的優(yōu)化控制，過程如下式所示

(9)

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

利用上述計算結(jié)果，對網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸過程中的時延進(jìn)行補(bǔ)償，提高傳輸時的控制能力。

3 獲取最短路徑

基于上述數(shù)據(jù)低時延傳輸時的優(yōu)化控制，利用DSPR算法完成網(wǎng)絡(luò)的路由節(jié)點部署，獲取網(wǎng)絡(luò)數(shù)據(jù)傳輸時的最短路徑。

3.1 獲取同質(zhì)簇

3.1.1 選擇初始簇頭

選擇網(wǎng)絡(luò)內(nèi)節(jié)點初始簇時，需要利用分布方式對簇頭進(jìn)行選擇。設(shè)定P為候選節(jié)點的選中概率，獲取過程如下式所示

(10)

式中，網(wǎng)絡(luò)中的節(jié)點數(shù)量為N，選定為候選節(jié)點si的數(shù)量為k。

在數(shù)據(jù)傳輸?shù)某跏茧A段，設(shè)定一個網(wǎng)絡(luò)節(jié)點的閾值為ξ∈[0，1]，若選中概率P小于等于ξ，可直接將其作為候選節(jié)點si。

設(shè)定Eresidual(si)為候選節(jié)點的剩余能量，相鄰節(jié)點簇頭為Ne(si)，相鄰節(jié)點簇頭個數(shù)為|Ne(si)|?；趥鬏敊C(jī)制，候選節(jié)點之間會存在競爭關(guān)系，因此要引入逃避機(jī)制[10]。候選節(jié)點的逃避時間如下式所示

(11)

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

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

3.1.2 網(wǎng)關(guān)簇頭

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

×|Ne(si)|T

(12)

等到退避時間完成，對網(wǎng)絡(luò)節(jié)點周圍進(jìn)行檢測，若相鄰節(jié)點數(shù)量為0，說明網(wǎng)絡(luò)節(jié)點未被初始簇頭覆蓋，該節(jié)點可成為網(wǎng)關(guān)簇頭。若相鄰節(jié)點數(shù)量為1，說明該節(jié)點被一個初始簇頭覆蓋，若相鄰節(jié)點數(shù)量大于2時，說明網(wǎng)絡(luò)節(jié)點在多個初始簇頭的通信范圍內(nèi)，若周圍簇頭沒有發(fā)生連接，將其作為網(wǎng)關(guān)簇頭，幫助其連接。若周邊簇頭處于連接狀態(tài)，可使其節(jié)點加入其中一方。

若競爭時發(fā)現(xiàn)該節(jié)點已成為初始簇頭，該節(jié)點直接退出競爭?；谏鲜鲞x取的簇頭節(jié)點為基礎(chǔ)，完成自組織網(wǎng)絡(luò)路由的部署，實現(xiàn)網(wǎng)絡(luò)的路由優(yōu)化。

3.2 最短路徑選擇

對自組織網(wǎng)絡(luò)路由進(jìn)行優(yōu)化主要目的就是獲取網(wǎng)絡(luò)在數(shù)據(jù)低時延傳輸時的源節(jié)點最短路徑[12]。

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

(13)

基于上述計算結(jié)果，實現(xiàn)對自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸?shù)淖疃搪窂将@取，從而降低網(wǎng)絡(luò)能耗。

4 實驗

為驗證上述網(wǎng)絡(luò)數(shù)據(jù)傳輸最短路徑路由算法的 整體有效性，需要對此算法進(jìn)行測試。

分別采用本文提出的自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸最短路徑路由算法(算法1)、文獻(xiàn)[3]提出的基于運(yùn)動狀態(tài)感知的容遲網(wǎng)絡(luò)路由算法(算法2)、文獻(xiàn)[5]提出的基于能耗區(qū)域感知的無線傳感器網(wǎng)絡(luò)路由算法(算法3)進(jìn)行測試．

1)不同算法的網(wǎng)絡(luò)節(jié)點能量消耗測試

在自組織網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)低時延傳輸時，利用算法1、算法2以及算法3對選取最短路徑后的網(wǎng)絡(luò)節(jié)點能量消耗情況進(jìn)行測試，測試結(jié)果如圖1所示。

圖1 不同算法的網(wǎng)絡(luò)節(jié)點能量消耗測試

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

2)不同算法的網(wǎng)絡(luò)壽命測試

采用算法1、算法2以算法3進(jìn)行數(shù)據(jù)傳輸最短路徑獲取后，對多自組織網(wǎng)絡(luò)的網(wǎng)絡(luò)壽命進(jìn)行測試，測試結(jié)果如圖2所示。

圖2 不同算法的網(wǎng)絡(luò)壽命測試

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

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

數(shù)據(jù)在進(jìn)行低時延傳輸時，控制時間開銷的長短會直接反映出算法的優(yōu)劣，對算法1、算法2以及算法3在網(wǎng)絡(luò)數(shù)據(jù)傳輸時的時間開銷進(jìn)行測試，測試結(jié)果如圖3所示。

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

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

4)數(shù)據(jù)傳輸優(yōu)化控制前后輸出幅值測試

基于上述實驗結(jié)果，對數(shù)據(jù)低時延傳輸優(yōu)化控制前后的輸出幅值進(jìn)行測試，測試結(jié)果如4所示。

圖4 數(shù)據(jù)傳輸優(yōu)化控制前后輸出幅值測試

分析圖4可知，網(wǎng)絡(luò)在進(jìn)行數(shù)據(jù)傳輸時，輸出的幅值越高，傳輸時的數(shù)據(jù)質(zhì)量越低。該算法數(shù)據(jù)傳輸優(yōu)化控制后的輸出幅值要低于優(yōu)化控制前。

5 結(jié)束語

隨著網(wǎng)絡(luò)技術(shù)的不斷更新，自組織網(wǎng)絡(luò)的形式愈加復(fù)雜。如何在數(shù)據(jù)進(jìn)行低時延傳輸時利用最短的時間找出最短路徑，成為該領(lǐng)域不斷需要解決的問題。針對網(wǎng)絡(luò)數(shù)據(jù)傳輸過程最短路徑路由算法中存在的問題，提出自組織網(wǎng)絡(luò)數(shù)據(jù)低時延傳輸最短路徑路由算法。該算法首先對數(shù)據(jù)傳輸時的網(wǎng)絡(luò)時延進(jìn)行優(yōu)化控制；再利用DSPR算法完成網(wǎng)絡(luò)的路由節(jié)點部署；最后通過路由部署結(jié)果實現(xiàn)對網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)淖疃搪窂将@取。該算法由于在網(wǎng)絡(luò)節(jié)點部署過程中存在一定問題，今后會針對該缺陷繼續(xù)對該算法進(jìn)行必要的優(yōu)化處理。