主動隊列管理下大時滯網(wǎng)絡(luò)路徑擁塞控制算法

劉國芳，張 煒

(四川大學(xué)錦江學(xué)院，四川眉山 620860)

1 引言

無線通道交換網(wǎng)絡(luò)是設(shè)定在監(jiān)測區(qū)域中的一些小型路由節(jié)點，通過無線通信的方式衍生出的具有多跳性、自組織性的網(wǎng)絡(luò)系統(tǒng)[1]。大時滯條件下，無線通道交換網(wǎng)絡(luò)的計算、儲存以及網(wǎng)絡(luò)能量供應(yīng)過程都會存在一定延時[2]。無線通道交換網(wǎng)絡(luò)里一個或多個路由節(jié)點吞吐量飽滿后，難以同其它節(jié)點實現(xiàn)即時通信，便會使網(wǎng)絡(luò)路徑堵塞，造成網(wǎng)絡(luò)服務(wù)延遲，減少無線通道交換網(wǎng)絡(luò)的使用性能[3]。因此，大時滯下無線通道交換網(wǎng)絡(luò)路徑擁塞是無線通道交換網(wǎng)絡(luò)的核心研究方向。為此，提出一種主動隊列管理下大時滯網(wǎng)絡(luò)路徑擁塞控制算法，以期可以優(yōu)化無線通道交換網(wǎng)絡(luò)路徑、縮短傳輸時延。

2 無線通道交換網(wǎng)絡(luò)路徑優(yōu)化選取方法

2.1 相鄰路由節(jié)點網(wǎng)絡(luò)路徑擁塞情況預(yù)測

大時滯網(wǎng)絡(luò)路徑擁塞時，無線通道交換網(wǎng)絡(luò)路由節(jié)點能量消耗與擁塞狀態(tài)成正比。因此，通過對路由節(jié)點能量消耗的預(yù)測可以直接預(yù)測網(wǎng)絡(luò)路徑擁塞情況。無線通道交換網(wǎng)絡(luò)路由節(jié)點能量消耗狀態(tài)如圖1所示。

圖1 無線信道交換網(wǎng)絡(luò)節(jié)點的能耗情況

伴隨集成電路工藝的快速發(fā)展，無線通道交換網(wǎng)絡(luò)中傳感器模塊與處理器的功耗逐漸變小[4]。由圖1能夠看出，大量的無線通道交換網(wǎng)絡(luò)能耗均消耗于無線通信模塊中，但無線通信模塊具有發(fā)送、接收、空閑以及睡眠四類情況。圖1中，無線通道交換網(wǎng)絡(luò)在發(fā)送時消耗能量最高；空閑與接收時能耗類似，但小于發(fā)送時的能量耗損，睡眠時的能耗最小。所以解決無線通道交換網(wǎng)絡(luò)路徑擁塞可以通過路由節(jié)點工作的變換，讓路由節(jié)點在無線通道交換網(wǎng)絡(luò)高效運行時快速由睡眠狀態(tài)變?yōu)榘l(fā)送接收狀態(tài)，高效應(yīng)用無線通道交換網(wǎng)絡(luò)路徑[5]。

主動隊列管理是通過網(wǎng)絡(luò)中間節(jié)點分組丟棄減少無線通道交換網(wǎng)絡(luò)中路由節(jié)點的緩存，以實現(xiàn)縮短傳輸時延和較高的吞吐量。若掌握自身全部相鄰路由節(jié)點的剩余可使用隊列，繼而可以在符合查詢和傳輸條件的近鄰節(jié)點里，先選擇剩余隊列較多的路由節(jié)點作為下一條節(jié)點，路由節(jié)點選擇即為網(wǎng)絡(luò)路徑選取[6]。

為實現(xiàn)對相鄰路由節(jié)點網(wǎng)絡(luò)路徑擁塞情況的有效控制，本文在分析路由節(jié)點狀態(tài)與對相鄰路由節(jié)點的剩余隊列的基礎(chǔ)上，獲取無線通道交換網(wǎng)絡(luò)路由節(jié)點中相鄰路由節(jié)點的剩余隊列數(shù)據(jù)。該數(shù)據(jù)是無線通道交換網(wǎng)絡(luò)路徑選取的核心標準，能夠有效平衡無線通道交換網(wǎng)絡(luò)路徑吞吐量負載。

在預(yù)測機制里，使用馬爾可夫鏈對無線通道交換網(wǎng)絡(luò)路由節(jié)點實行分析，路由節(jié)點在差異化工作模式中對應(yīng)的馬爾科夫鏈也存在差異化狀態(tài)：若一個路由節(jié)點存在N種工作模式，那么能夠使用馬爾可夫的N種狀態(tài)實行分析。在此類模型中，無線通道交換網(wǎng)絡(luò)各個路由節(jié)點均存在一系列隨機數(shù)Y0；Y1；Y2；…，此類隨機數(shù)依次描述路由節(jié)點各個數(shù)據(jù)吞吐處理時間步長(time-step)各自的狀態(tài)。無線通道交換網(wǎng)絡(luò)各個time-step中路由節(jié)點僅存在一種狀態(tài)。若Y0=j，則第m個time-step屬于狀態(tài)j。此外，若路由節(jié)點某數(shù)據(jù)吞吐處理時間步長的狀態(tài)是j，則路由節(jié)點后續(xù)數(shù)據(jù)吞吐處理時間步長會在固定概率qij的約束下，將自身的狀態(tài)變成i。則采用式(1)描述路由節(jié)點狀態(tài)轉(zhuǎn)移概率

qij=q{Yn+1=i|Yn=j}

(1)

(2)

各個無線通道交換網(wǎng)絡(luò)路由節(jié)點隊列消耗率參數(shù)是

(3)

其中，ΔB描述后續(xù)A個time-step中平均各個time-step的節(jié)點隊列消耗。經(jīng)過相鄰路由節(jié)點ΔB的計算，便能夠預(yù)測出無線通道交換網(wǎng)絡(luò)路由節(jié)點中相鄰路由節(jié)點在后續(xù)A時間中所消耗的隊列信息，最終獲取相鄰路由節(jié)點的剩余隊列[8]。

2.2 改進WSN蟻群路由選取算法

無線通道交換網(wǎng)絡(luò)路徑的路由選取時，需要充分分析無線通道交換網(wǎng)絡(luò)路由節(jié)點的隊列有限性[9]。針對這個特征，本文在上小節(jié)分析的無線通道交換網(wǎng)絡(luò)隊列消耗和工作狀態(tài)后，顧及到后續(xù)節(jié)點隊列參數(shù)和實際工作中的傳輸速度等情況，采用改進WSN蟻群路由選取算法，優(yōu)化節(jié)點隊列、傳輸速度等方面，獲取最佳無線通道交換網(wǎng)絡(luò)路由隊列，同時在蟻群進行路由隊列的自動尋優(yōu)時，會存在隊列感知意識，大大增強了網(wǎng)絡(luò)隊列路由的動態(tài)優(yōu)化選取性能[10]。

2.2.1路徑概率選擇

基于路徑探索的角度分析，必須融合概率訪問附近節(jié)點：在路徑尋優(yōu)這個角度出發(fā)，為了克服進入局部最優(yōu)解，在訪問無線通道交換網(wǎng)絡(luò)節(jié)點中，若只憑借概率而獲取的最優(yōu)解并不是都是正確的。則考慮傳輸方向參數(shù)，獲取改進轉(zhuǎn)移概率為

(4)

2.2.2本地分組丟棄函數(shù)

螞蟻在無線通道交換網(wǎng)絡(luò)傳感器路由節(jié)點j轉(zhuǎn)移至相鄰路由節(jié)點i的期望水平用分組丟棄函數(shù)dij描述。無線通道交換網(wǎng)絡(luò)不僅需要分析路由距離因素，也需要分析節(jié)點、相鄰路由節(jié)點剩余隊列等有關(guān)數(shù)據(jù)[11]。所以，本文采用的分組丟棄函數(shù)是：

(5)

2.2.3吞吐量信息素更新

螞蟻選取下一個節(jié)點時，在走過的路徑上會釋放吞吐量信息素，進而變成引導(dǎo)后續(xù)螞蟻的吞吐量信息素濃度。則吞吐量信息素更新公式是

cij(a+1)=cij(a)+Δcij

(6)

(7)

式中，cij(a)與Δcij分別描述前一時刻吞吐量信息素濃度與當(dāng)下吞吐量信息素濃度；Hs表示螞蟻在源節(jié)點至目的節(jié)點走過的路徑長；θ表示全局設(shè)定常量；Bs-min、Bs-avg依次描述螞蟻走過路徑節(jié)點的最小隊列以及平均隊列。

2.2.4優(yōu)化選取實現(xiàn)

結(jié)合上述路徑擁塞情況預(yù)測和改進WSN的蟻群路由選取過程，實現(xiàn)路徑優(yōu)化選取，詳細的實現(xiàn)流程如下：

第一步：初始化。將螞蟻路徑、訪問標志恢復(fù)到原始狀態(tài)；在源節(jié)點處放n只螞蟻，并設(shè)定成已訪問，其是路線的第一個節(jié)點，其它每個節(jié)點的初始值都是常數(shù)，存在一樣的吞吐量信息素；信息素增量值是0；

第二步：設(shè)定到達目的節(jié)點的螞蟻數(shù)是0；

第三步：螞蟻數(shù)s的值是0；

第四步：經(jīng)過運算獲取路由節(jié)點間距；

第五步：運算路徑轉(zhuǎn)移概率，判定路由節(jié)點i，將螞蟻s轉(zhuǎn)移到i，并設(shè)定這個路由節(jié)點屬于已訪問；

第六步：采用式(5)分析是否存在路由節(jié)點隊列耗盡，若存在便直接跳轉(zhuǎn)到步驟八；

第七步：s′=s+1，將此值和n值相比，小于n跳至第五步；

第八步：運算螞蟻所走過的路徑總長度，對比獲取最短路徑；

第九步：若經(jīng)過運算后，若不存在路由節(jié)點耗盡隊列的情況，那么按照式(6)、式(7)實行吞吐量信息素的全局更新后跳轉(zhuǎn)至第二步，反之停止。

第十步：若上述循環(huán)停止，最后輸出最佳路由選取結(jié)果。

基于上述可知，改進WSN蟻群路由選取算法可在增加無線通道交換網(wǎng)絡(luò)應(yīng)用吞吐量的同時，將傳輸時延最小化，該算法通過路徑概率選取、分組丟棄函數(shù)、更新吞吐量信息素方面，從傳輸距離、節(jié)點隊列以及傳輸方向三個方面，優(yōu)化網(wǎng)絡(luò)路徑選取過程，得到縮短無線通道交換網(wǎng)絡(luò)傳輸時延的方法。

3 實驗分析

為了評估主動隊列管理下大時滯網(wǎng)絡(luò)路徑擁塞控制算法的實際應(yīng)用效果，建立大時滯無線通道交換網(wǎng)絡(luò)的模擬環(huán)境展開實驗驗證。顧及到實驗的復(fù)雜性，將螞蟻總數(shù)設(shè)成60只，則路由節(jié)點數(shù)量為60；無線通道交換網(wǎng)絡(luò)路由節(jié)點每次傳輸?shù)臄?shù)據(jù)包大小一樣，各個節(jié)點的初始隊列是200。網(wǎng)絡(luò)環(huán)境配置參數(shù)如表1所示。

表1 網(wǎng)絡(luò)環(huán)境配置參數(shù)

為避免實驗結(jié)果的單一性，采用本文算法、基于鏈路容量的多路徑擁塞控制算法、基于功率分配的網(wǎng)絡(luò)擁塞控制算法進行對比。對比指標為：無線通道交換網(wǎng)絡(luò)隊列消耗總量、死亡節(jié)點數(shù)、網(wǎng)絡(luò)丟包率、傳輸時延。

3.1 無線通道交換網(wǎng)絡(luò)隊列消耗總量

無線通道交換網(wǎng)絡(luò)隊列消耗總量通過節(jié)點隊列體現(xiàn)。節(jié)點隊列越多，能力消耗越大。設(shè)置實驗無線通道交換網(wǎng)絡(luò)存在60個節(jié)點，各個節(jié)點的初始隊列是200，則全網(wǎng)隊列總值是12000。圖2為三種算法的隊列消耗對比結(jié)果。

圖2 三種算法的能耗對比

分析圖2數(shù)據(jù)可知，本文算法在3000輪時的能耗僅為60kJ，其能耗曲線始終位于另外兩種算法能耗曲線之下，證明本文算法的節(jié)點隊列消耗更低，說明保證其在選取網(wǎng)路路徑路由時有效增大無線通道交換網(wǎng)絡(luò)的吞吐量。

3.2 死亡節(jié)點數(shù)

路由節(jié)點平均隊列消耗和死亡節(jié)點數(shù)不存在必然的關(guān)系，死亡節(jié)點數(shù)并不會隨著路由節(jié)點隊列增大而增大。假定只有少量路由節(jié)點消耗隊列，剩余節(jié)點沒有消耗或者基本未曾消耗隊列，此類狀況下死亡節(jié)點數(shù)較小，而不能忽略的是很有可能死亡節(jié)點都在關(guān)鍵路由上，便會導(dǎo)致全部網(wǎng)絡(luò)出現(xiàn)崩潰，相應(yīng)的網(wǎng)絡(luò)傳輸時延也會增多。假定無線通道交換網(wǎng)絡(luò)中是多數(shù)節(jié)點一起消耗節(jié)點隊列，便屬于平均消耗，即使無線通道交換網(wǎng)絡(luò)中會存在大量死亡節(jié)點，但也不會發(fā)生節(jié)點全部失效的情況，網(wǎng)絡(luò)崩潰的概率也較小，便可縮短網(wǎng)絡(luò)傳輸時間。圖3為三種算法的死亡節(jié)點數(shù)對比結(jié)果。

圖3 三種算法的死亡節(jié)點數(shù)對比

分析圖3數(shù)據(jù)可知，本文算法在第3000輪迭代時，死亡節(jié)點數(shù)量最高，但也處于20個以下；相比之下，基于鏈路容量和基于功率分配的擁塞控制算法的死亡節(jié)點數(shù)量均較高。由此可知，本文算法的節(jié)點死亡效率最慢，能夠達到預(yù)期效果。

3.3 網(wǎng)絡(luò)丟包率

設(shè)定不同長度數(shù)據(jù)包，測試應(yīng)用三種算法后的無線通道交換網(wǎng)絡(luò)的網(wǎng)絡(luò)丟包率，對比結(jié)果如圖4所示。

圖4 三種算法的無線信道交換網(wǎng)絡(luò)丟包率對比

分析圖4可知，在不同長度數(shù)據(jù)包的設(shè)定下，應(yīng)用本文算法后的無線通道交換網(wǎng)絡(luò)丟包率最大值為4.43%；而應(yīng)用基于鏈路容量的多路徑擁塞控制算法和基于功率分配的網(wǎng)絡(luò)擁塞控制算法后的無線通道交換網(wǎng)絡(luò)丟包率均大于本文算法。由此可說明本文算法在選取無線通道交換網(wǎng)絡(luò)路徑時，能夠有效保護數(shù)據(jù)安全性，對數(shù)據(jù)包不存在較大的損耗，也可保證了傳輸吞吐量。

3.4 傳輸時延

圖5為不同長度數(shù)據(jù)包的設(shè)定下，使用三種算法時無線通道交換網(wǎng)絡(luò)的傳輸時延對比結(jié)果。

圖5 三種算法的無線信道交換網(wǎng)絡(luò)傳輸時延

分析圖5可知，當(dāng)數(shù)據(jù)包長度值較小，三種算法的性能差異度較小；當(dāng)數(shù)據(jù)包長度增大至120字節(jié)時，使用本文算法時無線通道交換網(wǎng)絡(luò)的傳輸時延僅有29ms；使用基于鏈路容量的算法時無線通道交換網(wǎng)絡(luò)的傳輸時延為94ms；而使用基于功率分配的算法時，傳輸時延最大，其延遲接近150ms。由此可知，在不同數(shù)據(jù)包長度值的前提下，使用本文算法時無線通道交換網(wǎng)絡(luò)的傳輸時延最小，這是因為本文算法能夠有效選取最佳網(wǎng)絡(luò)路徑，可以保持較小的傳輸時延。

4 結(jié)束語

為了緩解大時滯下無線通道交換網(wǎng)絡(luò)路徑的擁塞情況，本文設(shè)計了基于主動隊列管理算法的大時滯網(wǎng)絡(luò)路徑擁塞控制算法。考慮到無線通道交換網(wǎng)絡(luò)中間節(jié)點隊列少，引入主動隊列管理算法，使用相鄰路由節(jié)點剩余隊列預(yù)測分析無線通道交換網(wǎng)絡(luò)路由節(jié)點的隊列消耗和工作狀態(tài)；在此基礎(chǔ)上，為了獲取最佳網(wǎng)絡(luò)路徑，考慮后續(xù)節(jié)點隊列參數(shù)和實際工作中的最佳傳輸距離以及傳輸方向等情況，則采用改進 WSN 蟻群路由選取算法進行路徑概率選取、分組丟棄函數(shù)、更新吞吐量信息素三方面優(yōu)化，從傳輸距離、節(jié)點隊列以及傳輸方向三個方面，優(yōu)化網(wǎng)絡(luò)路徑隊列選取過程，確保在增多無線通道交換網(wǎng)絡(luò)應(yīng)用吞吐量的同時，將傳輸時延最小化，最終獲取最佳網(wǎng)絡(luò)路徑。經(jīng)驗證得到，本文算法有效解決了無線通道交換網(wǎng)絡(luò)存在的傳輸時延長能耗大等問題，具有較高的實際應(yīng)用意義。