蔡文哲，王斌君

(中國人民公安大學網(wǎng)絡(luò)安全保衛(wèi)學院，北京 102623)

0 引言

網(wǎng)絡(luò)路由問題的研究常常通過以下2 個途徑來提高服務(wù)質(zhì)量［1］(Quality of Service，QoS):1)網(wǎng)絡(luò)節(jié)點控制;2)全網(wǎng)或局域網(wǎng)絡(luò)控制。網(wǎng)絡(luò)節(jié)點控制針對單個節(jié)點或單鏈路，主要用于控制業(yè)務(wù)對單節(jié)點共享資源的占用;全網(wǎng)或局域網(wǎng)絡(luò)控制常常利用對路由的控制來實現(xiàn)對業(yè)務(wù)流的控制。因為路由直接關(guān)系到網(wǎng)絡(luò)性能，所以有效的QoS 路由［2］選擇方案成為解決QoS 問題的一個關(guān)鍵技術(shù)，在網(wǎng)絡(luò)技術(shù)領(lǐng)域內(nèi)也是一個研究熱點。

在實際網(wǎng)絡(luò)中選擇出一條合適的路徑，使它符合一定的網(wǎng)絡(luò)費用、網(wǎng)絡(luò)延遲、延遲抖動和網(wǎng)絡(luò)帶寬的限制是QoS 路由的一項根本任務(wù)。Wang Zheng 等［3］證明了如果QoS 路由至少包含2 個限制時，它是一個NP-C 問題［4］。傳統(tǒng)的路由算法［5］很難有效地解決NP-C 問題，但基于改進的自適應(yīng)蟻群算法［6］卻提出了一種行之有效的解決方案。

為了研究的方便，本文QoS 路由研究的對象設(shè)定為平面網(wǎng)絡(luò)路由［7］，即所有的網(wǎng)絡(luò)路由器都處于同一級之內(nèi)的網(wǎng)絡(luò)，一般稱之為平面網(wǎng)絡(luò)路由。

1 網(wǎng)絡(luò)路由問題描述

通常用有向圖G=(V，E)表示網(wǎng)絡(luò)模型［8］，有向圖中V 是指節(jié)點的集合，E 是指邊的集合，每條邊是相鄰2 節(jié)點間的信息交換路徑。一般情況下，假定任意2 相鄰節(jié)點間的邊數(shù)最多只有一條。此外，設(shè)B(l)是網(wǎng)絡(luò)鏈路的實際帶寬，針對某個網(wǎng)絡(luò)路由請求w，當能夠找出不止一條費用較小的路徑，而且滿足下面幾個條件時，就接受該網(wǎng)絡(luò)路由請求w。

對于網(wǎng)絡(luò)路由請求w，每條路徑l 的可用帶寬都被限制為:

B(l)≥Bw(1)

對于網(wǎng)絡(luò)路由請求w，點到點的網(wǎng)絡(luò)延遲被限制為:

對于網(wǎng)絡(luò)路由請求w，點到點的網(wǎng)絡(luò)丟失率被限制為:

在本文中，研究的對象是那些因為網(wǎng)絡(luò)節(jié)點緩存器溢出所導(dǎo)致的數(shù)據(jù)包丟失。

對于網(wǎng)絡(luò)中的目的節(jié)點，點到點的網(wǎng)絡(luò)延遲抖動被限制為:

在式(1)～式(4)中，Bw表示網(wǎng)絡(luò)帶寬限制;Dw表示網(wǎng)絡(luò)延遲限制;Lw表示網(wǎng)絡(luò)丟失率限制;Jw表示網(wǎng)絡(luò)延遲抖動限制;DN 表示網(wǎng)絡(luò)節(jié)點處理延遲，且DN:V→R+;DL 表示網(wǎng)絡(luò)鏈路延遲，且DL:E→R+;V1表示網(wǎng)絡(luò)路由請求w 的節(jié)點集合;E1表示網(wǎng)絡(luò)路由請求w 的路徑集合;LR 表示網(wǎng)絡(luò)節(jié)點丟失率，且LR:V→R+∪{ 0} ;DNV 表示網(wǎng)絡(luò)目的節(jié)點的延遲變化，且DNV:V→R+∪{ 0}，其中R+表示正實數(shù)集。

2 平面QoS 蟻群路由算法設(shè)計

自適應(yīng)蟻群算法的信息素更新策略對算法的整體性能有很重要的影響。K.C.Abbaspour［9］等曾提出，在蟻群算法實際運行之前進行一個預(yù)處理階段，該階段開始并不使用信息素，通過預(yù)處理找出一定數(shù)量的路徑，然后再從其中找出部分路徑，并在算法開始前對信息素進行初始化，這樣可以獲得比較好的效果。但是目前對該方面的研究相對比較少，所以信息素更新策略值得深入的研究。而本文就是通過對信息素更新策略的改進設(shè)計了一種平面QoS 蟻群路由算法。

假設(shè)在平面QoS 蟻群路由算法中螞蟻的個數(shù)是m，并且本算法采用的信息素更新策略［10］是全局和局部相結(jié)合的復(fù)合更新策略。另外，本算法采用以下的狀態(tài)轉(zhuǎn)移策略:

現(xiàn)假定第i 只螞蟻在節(jié)點r 上，那么它將根據(jù)以下策略來選擇下一個節(jié)點s:

當q ≤q0時，則:

否則:

采用以上狀態(tài)轉(zhuǎn)移策略，螞蟻找到的路徑常常是局部最優(yōu)路徑。

1)局部信息素更新策略。

如果螞蟻i 選擇的2 個節(jié)點(r，s)在它行走的路徑中是相鄰的，那么此時的信息素變?yōu)閜he(i，r，s)，見公式(7);如果2 個節(jié)點不相鄰，那么信息素就不用更新。

其中α0是一個常數(shù)。

如果信息素沒有得到局部的更新，那么所有螞蟻將根據(jù)歷史最優(yōu)路徑在其鄰近域內(nèi)進行下一步搜尋。

2)全局信息素更新策略。

如果螞蟻i 選擇的2 個節(jié)點(r，s)在它行走的路徑中是相鄰的，那么此時的信息素則根據(jù)式(8)進行更新;如果2 個節(jié)點不相鄰，那么信息素則根據(jù)式(9)進行更新。

其中α1是一個常數(shù)。

對公式(8)中的限制函數(shù)F 進行定義，當節(jié)點r位于螞蟻i 所選擇行走的路徑中時，，否則0;當邊(r，s)位于螞蟻i 所選擇行走的路徑中時，=1，否則;假定LBrs、LCrs和LDrs表示的含義分別是螞蟻行走路徑中邊(r，s)的可用帶寬、費用和網(wǎng)絡(luò)延遲，NDr表示節(jié)點r 的處理延遲，NLr表示節(jié)點r的網(wǎng)絡(luò)丟失率。此時，限制函數(shù)F 可以表示為:

在式(11)～式(16)中，V 是網(wǎng)絡(luò)節(jié)點的個數(shù);A是可用帶寬限制;B 是點到點的延遲限制;C 是點到點的網(wǎng)絡(luò)丟失率限制;F1是費用可用限制;F2是QoS限制，并且它們都是正實數(shù)。

根據(jù)以上對限制函數(shù)的定義可知，當螞蟻所選路徑的總體費用最小，且QoS 的延遲限制也符合相應(yīng)要求時，最優(yōu)路由中的各條路徑上的信息素的增加值會更大。由于本算法的收斂性還有待提高，所以筆者在這方面做了改進:

1)在迭代過程中，對網(wǎng)絡(luò)延遲抖動所帶來的影響不予考慮，并且在執(zhí)行算法之前對其做相應(yīng)預(yù)處理;

2)對實際網(wǎng)絡(luò)進行簡化處理，比如刪除部分帶寬比較小的鏈路，從而形成一個新的簡化網(wǎng)絡(luò)，所以令F 函數(shù)中的A=0。

該算法的詳細步驟如下:

1)當DNV(d)＞Jw時，算法結(jié)束;否則，轉(zhuǎn)執(zhí)行第2)步。

2)對實際網(wǎng)絡(luò)進行簡化處理，刪除部分帶寬比較小的鏈路，從而形成一個簡化網(wǎng)絡(luò)。

3)對網(wǎng)絡(luò)結(jié)構(gòu)中每一條鏈路邊的信息素進行初始化賦值。

4)起初安排一定數(shù)量的螞蟻去覓食，假設(shè)螞蟻初始數(shù)量為m。在首個單位時間內(nèi)，每一只螞蟻在網(wǎng)絡(luò)節(jié)點集合內(nèi)隨機挑選某個節(jié)點作為下一節(jié)點，然后每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移策略對自己的路徑進行選擇。在選擇路徑的過程中，當螞蟻在覓食途中死亡時，則用另外一只同樣類型的螞蟻來代替此螞蟻，并對從起始節(jié)點到目的節(jié)點的路徑重新進行選擇。如果某一只螞蟻挑選出一條到目的節(jié)點的完整路由，則根據(jù)局部信息素更新策略對此路由中的信息素進行相應(yīng)更新。

5)對第4)步執(zhí)行m 次，直到所有螞蟻都對各自信息素進行了相應(yīng)更新。

6)對所有螞蟻選擇出的m 個路由進行挑選，選擇出滿足QoS 限制而且費用最小的路由，然后根據(jù)全局信息素更新策略對該路由中所有路徑上的信息素進行相應(yīng)更新。

7)不斷對第4)～6)這3 步驟進行重復(fù)執(zhí)行，直到獲得滿足一定條件的路由方案。

根據(jù)以上設(shè)計的平面QoS 蟻群路由算法，本文設(shè)計了平面QoS 蟻群路由選擇系統(tǒng)。該系統(tǒng)的具體工作流程表述如下，根據(jù)不同的具體問題設(shè)置相應(yīng)的參數(shù)，并根據(jù)一定的初始化策略，確定螞蟻的初始位置。然后螞蟻可以不斷地利用狀態(tài)轉(zhuǎn)移策略，尋找新路徑。在尋找路徑的同時，螞蟻也通過局部信息素更新策略對已訪問路徑上的信息素濃度不斷地進行修改。當所有螞蟻都尋找到了它們的路徑，則找出這些路徑中的最優(yōu)路徑，并利用全局信息素更新策略再次修改該路徑上的信息素濃度。這些狀態(tài)轉(zhuǎn)移策略可以使螞蟻受信息素信息和啟發(fā)信息的指導(dǎo)，向著信息素濃度更高的路徑爬行。簡言之，這些策略可以使更多的螞蟻來選擇更好的路徑。平面QoS 蟻群路由選擇系統(tǒng)具體的設(shè)計流程如圖1 所示。

圖1 平面QoS 蟻群路由選擇系統(tǒng)設(shè)計流程圖

本文利用TSP 問題對平面QoS 蟻群路由選擇系統(tǒng)的性能進行了驗證，從平均迭代次數(shù)、平均運行時間、平均最優(yōu)解等幾個方面對基本自適應(yīng)蟻群算法、文獻［11］和文獻［12］的算法與本文改進后的平面QoS 蟻群算法進行比較。最后在MATLAB 進行仿真實驗，結(jié)果如表1 所示。

表1 TSP 問題各算法性能比較表

由表1 可知，改進后的平面QoS 蟻群算法的平均運行時間與其他算法相比明顯都要短，也就是說它具有很強的收斂性;另外，與基本的自適應(yīng)蟻群算法相比，改進后的平面QoS 蟻群算法的平均迭代次數(shù)有明顯減少。改進后的算法能夠在保持較低的平均迭代次數(shù)和較短的平均運行時間的同時，也可以得到和其他算法幾乎相同的平均最優(yōu)解。綜上可知，改進后的平面QoS 蟻群算法擁有比一般自適應(yīng)蟻群算法更好的實際運行性能。

3 路由性能分析

實際網(wǎng)絡(luò)拓撲［13］如圖2 所示，網(wǎng)絡(luò)節(jié)點用點〈ndl，lr，dv〉表示，ndl 代表節(jié)點網(wǎng)絡(luò)延遲，lr 代表節(jié)點丟失率，dv 代表節(jié)點延遲變化。網(wǎng)絡(luò)鏈路用邊〈cost，bw，ldl〉表示，cost 代表費用，bw 代表帶寬，ldl 代表鏈路延遲。

圖2 網(wǎng)絡(luò)的拓撲及其參數(shù)

假定有3 個單播路由請求［14］(1，6)、(2，6)和(3，8)，它們的Bw=70，要求是:Dw=8，Lw=10-5，現(xiàn)對圖2 中的實際網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行簡化處理，如圖3所示。

圖3 簡化網(wǎng)絡(luò)及其參數(shù)

設(shè)置m=20，?0=0.075，?1=0.085，cons=0.28，q0=0.92，A=0，B=15，C=30，信息素τ=150。在MATLAB 上對平面QoS 蟻群路由算法進行仿真實驗［15］，最終結(jié)果如表2 所示，本次實驗的平均迭代次數(shù)只有105 次。

表2 平面QoS 蟻群路由算法的仿真實驗結(jié)果

最后對表2 中的路由請求額外進行了1 000 次的實驗仿真，結(jié)果發(fā)現(xiàn)其中有913 次可以找到表2 相應(yīng)路由，87 次可以找到比較優(yōu)的路由，沒有找不到路由的情況。綜上可知，改進后的平面QoS 蟻群路由算法可以很好地完成路由尋優(yōu)任務(wù)。

4 結(jié)束語

本文在自適應(yīng)蟻群算法的基礎(chǔ)上，對信息素更新策略進行了改進，采用局部與全局信息素更新策略相結(jié)合的方法，形成平面QoS 蟻群路由算法。為了提高收斂性，還對該路由算法進行一定的改進，最后將其成功應(yīng)用于網(wǎng)絡(luò)路由問題，并通過仿真實驗驗證了它的性能。仿真實驗結(jié)果表明，改進后的平面QoS蟻群路由算法在求解比較復(fù)雜的網(wǎng)絡(luò)路由問題時具有很強的優(yōu)越性，不僅迭代次數(shù)少而且還具有較高的最優(yōu)解幾率?？梢院芎玫亟鉀Q平面QoS 網(wǎng)絡(luò)路由問題，是一種有效的快速路由選擇方案。

［1］孔宇彥，姚金濤，張明武.Ad Hoc 網(wǎng)絡(luò)基于壽命估算MMAS 的QoS 組播路由優(yōu)化算法［J］.小型微型計算機系統(tǒng)，2015，36(1):44-48.

［2］葛連升，江林，秦豐林.QoS 組播路由算法研究綜述［J］.山東大學學報(理學版)，2010，45(1):55-65.

［3］Wang Zheng，Crowcroft J.Quality-of-service routing for supporting multimedia applications［J］.IEEE Journal on Selected Areas in Communications，1996，14(7):1228-1234.

［4］張素兵，呂國英，劉澤民，等.基于螞蟻算法的QoS 路由調(diào)度方法［J］.電路與系統(tǒng)學報，2000，5(1):1-5.

［5］賈云富，秦勇，段富，等.蟻群算法及其在路由優(yōu)化中的應(yīng)用綜述［J］.計算機工程與設(shè)計，2009，30(19):4487-4491.

［6］鄭慧君，張巍，滕少華.基于改進蟻群的無線傳感器網(wǎng)絡(luò)路由［J］.計算機應(yīng)用研究，2010，27(1):99-100.

［7］王子君，趙衛(wèi)國，王利英，等.基于人工免疫-蟻群算法的平面QoS 路由模型［J］.河北工程大學學報(自然科學版)，2007，24(3):76-79.

［8］胡小兵，黃席樾，張著洪.一種新的自適應(yīng)蟻群算法及其應(yīng)用［J］.計算機仿真，2004，21(6):108-111.

［9］Abbaspour K C，Schulin R，Genuchten M T.Estimating unsaturated soil hydraulic parameters using ant colony optimization［J］.Advance in Water Resources，2001，24(8):827-841.

［10］顏晨陽，張友鵬，熊偉清.一種新的蟻群優(yōu)化算法信息素更新策略［J］.計算機應(yīng)用研究，2007，24(7):86-88.

［11］賴智銘，郭躬德.基于自適應(yīng)閾值蟻群算法的路徑規(guī)劃算法［J］.計算機系統(tǒng)應(yīng)用，2014，23(2):113-118.

［12］邵創(chuàng)創(chuàng)，董尚陽.一種自適應(yīng)蟻群算法的研究及仿真［J］.中國科技博覽，2013(28):488-488.

［13］顧軍華.基于螞蟻算法的QoS 組播路由問題求解［J］.河北工業(yè)大學學報，2002，31(4):19-24.

［14］向虹佼，呂光宏，明麗洪.基于蟻群系統(tǒng)的QoS 單播路由算法［J］.電子科技，2014，27(1):53-56.

［15］陳冰梅，樊曉平，周志明，等.求解旅行商問題的Matlab蟻群仿真研究［J］.計算機測量與控制，2011，19(4):990-992.