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

劉國芳，張 煒

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

1 引言

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

2.2 改進(jìn)WSN蟻群路由選取算法

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

2.2.1路徑概率選擇

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

(4)

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

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

(5)

2.2.3吞吐量信息素更新

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

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

(6)

(7)

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

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

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

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

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

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

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

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

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

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

第八步：運(yùn)算螞蟻所走過的路徑總長度，對(duì)比獲取最短路徑；

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

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

圖2 三種算法的能耗對(duì)比

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

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

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

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

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

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

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

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

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

3.4 傳輸時(shí)延

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

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

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

4 結(jié)束語

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