一種QoS 平面蟻群路由算法的設計與實現

蔡文哲，王斌君

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

0 引言

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

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

為了研究的方便，本文QoS 路由研究的對象設定為平面網絡路由［7］，即所有的網絡路由器都處于同一級之內的網絡，一般稱之為平面網絡路由。

1 網絡路由問題描述

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

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

B(l)≥Bw(1)

對于網絡路由請求w，點到點的網絡延遲被限制為:

對于網絡路由請求w，點到點的網絡丟失率被限制為:

在本文中，研究的對象是那些因為網絡節(jié)點緩存器溢出所導致的數據包丟失。

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

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

2 平面QoS 蟻群路由算法設計

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

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

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

當q ≤q0時，則:

否則:

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

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

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

其中α0是一個常數。

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

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

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

其中α1是一個常數。

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

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

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

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

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

該算法的詳細步驟如下:

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

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

3)對網絡結構中每一條鏈路邊的信息素進行初始化賦值。

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

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

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

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

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

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

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

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

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

3 路由性能分析

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

圖2 網絡的拓撲及其參數

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

圖3 簡化網絡及其參數

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

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

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

4 結束語

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

［1］孔宇彥，姚金濤，張明武.Ad Hoc 網絡基于壽命估算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 路由調度方法［J］.電路與系統(tǒng)學報，2000，5(1):1-5.

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

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

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

［8］胡小兵，黃席樾，張著洪.一種新的自適應蟻群算法及其應用［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］.計算機應用研究，2007，24(7):86-88.

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

［12］邵創(chuàng)創(chuà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.