基于PSO算法的OSPF多約束路由策略

江家寶　鄭尚志

摘要：利用傳統SPF算法解決OSPF網絡路由難題時，由于沒有考慮多約束條件和有效利用次路徑，一旦最優路徑發生擁塞，網絡傳輸性能將急劇降低。將PSO算法應用于OSPF網絡路由規劃，利用多約束條件并結合OSPF網絡多種路由參數的特性，重點對有效改善網絡局部擁塞和快速求得全局最佳路由及若干次路由算法進行探究，并利用仿真數據對所提出的改進算法進行驗證。結果表明，在解決OSPF網絡路由規劃問題中，PSO算法較傳統遺傳算法和SPF算法能實現網路傳輸性能更優。

關鍵詞：PSO算法；OSPF；網絡路由器；多約束路由；QoS

DOIDOI：10.11907/rjdk.1431035

中圖分類號：TP311

文獻標識碼：A 文章編號：16727800（2015）006007604

基金項目基金項目：安徽省高等教育振興計劃項目（2013zytz063）

作者簡介作者簡介：江家寶（1968-），男，安徽無為人，碩士，巢湖學院信息工程學院講師，研究方向為模式識別與智能控制、嵌入式系統、計算機網絡；鄭尚志（1963-），男，安徽巢湖人，博士，巢湖學院信息工程學院教授，研究方向為操作系統理論、人工智能。

0 引言

隨著網絡通信要求的不斷提高和Internet的飛速發展，路由器成了網絡連接中最為關鍵的設備，路由器中運行的軟件對網絡連接性能和效率的影響越來越明顯。目前，國內外OSPF網絡路由器的主流產品仍然使用SPF算法解決路由問題。為緩解網絡路由擁塞等瓶頸問題，人們陸續提出了遺傳算法、模擬退火算法等多種方法實現OSPF協議。

本文在研究OSPF 協議原理及PSO（Particle Swarm Optimization）算法基本概念和實現方法[1] 的基礎上，詳細闡述了網絡路由選擇過程中必須滿足的QoS和實時性等多種要求，以及在目標函數值的引導下，如何實現PSO和遺傳算法對復雜的OSPF網絡路由解空間進行有效搜索[23]，以獲得最佳路由和多條次路由，并有效利用這些路由進行路由規劃。通過仿真實驗驗證了將PSO算法應用于OSPF網絡路由規劃中的有效性。

1 OSPF協議原理

路由指在網絡數據傳輸中采用某種策略為數據包從源點到達目的地點尋找一條理想路徑。基于全局最優思想，網絡設備為轉發的數據包選擇某種距離測度下的最優路徑，沿最優路徑發送數據包。支持OSPF協議的SPF算法在傳送業務服務模式的網絡中效果較好，但其無法滿足多媒體業務的QoS需求[45]，主要表現如下：①SPF采用與鏈路帶寬成反比的cost值度量距離來尋找最優路徑，沒有考慮其它約束條件，不能滿足日益復雜的網絡性能要求；②SPF忽略了次路由，一旦最優路徑發生擁塞，其它可用路徑被閑置，將大大降低網絡傳輸性能。

擁塞時，網絡時延和丟包率會劇增，若采用時延和丟包率來度量最優路徑，可將流量轉移到另一條路徑上，但這種轉移是全部轉移，新路徑又會由于負荷過重而擁塞，而原來的路徑又會空閑，這樣容易引起路由振蕩。因此，需要選取新的OSPF實現方法，使其能滿足日益復雜的QoS要求。

2 QoS路由問題

CCITT給出QoS的定義[67]為：“QoS是一個綜合指標，用于衡量使用一個服務的滿意度。”而現有的Internet都只是提供besteffort傳送，不能提供QoS保證。為了適應網絡的發展需求，Internet2工作組提出的新草案對QoS要求如下：①提供可計量的服務；②支持高級應用（如雙向交互音/視頻、遠程控制等）；③良好的可擴展性；④可管理性；⑤能與終端用戶操作系統和中間件協同工作等。要求QoS選路既要可行（即可達），又要有效（即最小化占用鏈路帶寬，最小化鏈路擁塞等）。因此，為了滿足QoS路由要求，路由規劃時首先考慮如何有效利用網絡資源，其次考慮如何減少路由計算的時間復雜性。

本文首次采用經過PSO算法修正的OSPF路由來解決上述問題。

3 QoS路由模型

網絡鏈路的雙向特征一般存在差異，網絡的拓撲結構可用有向圖G=（V，E）來描述（V為網絡節點集合，E為節點間鏈路集合）。鏈路（v，e）的特性可用鏈路的可用剩余帶寬band（v，e）、時延delay（v，e）（包含數據包在節點的處理時延、排隊時延和發送時延）、丟包率loss（v，e）、發送報文所需的代價cost（v，e）（鏈路費用和傳播時延的綜合評價）來表示。

5 OSPF路由選擇實現

采用十進制編碼方案。以路徑中節點的十進制標號序列作為路徑編碼值。比如，路徑編碼表示的路徑為。

5.1 PSO算法實現

算法每次迭代對所有粒子都依次進行“進化、評估、取代”操作。

（1）進化。它是算法的核心，對粒子j路徑上的每點進行如下操作：①利用式（4）計算并處理第k維飛行速度V[j][k]；②依據式（5）計算第k維位置，記x=（p[j].path[k]+V[j][k]），結果是浮點數，按0.5的概率向上/下取整后再對（N+1）取余；③這是進化的難點所在，假設路徑數組P[j].path[i]≠0， P[j].path[i+1，+2，….，k-1]均為0，則定義P[j].path[i]為P[j].path[k]的前驅節點。若x值非法（是負數、起點、終點、已經經歷過的節點），則從[0，N]中隨機選取一個合法值給x。若x=0或與P[j].path[i]前驅節點可達，p[j].path[i]=x；否則作如下修正，記p[j].path[i]前驅節點p[j].path[m]的直達節點集合為A，p[j].path[0：m-1]經歷過的節點集合為B，從集合A-B中隨機選取一點賦給p[j].path[i]。若集合A-B為空，則p[j].path[m]以0.5的概率賦值0，以0.5的概率作上述修正，處理完p[j].path[m]后再重新處理p[j].path[i]。以此類推，極端情況是向前遞推處理到p[j].path[1]，這時肯定能從起始位置的直達節點中找一個節點作為p[j].path[1]的值，否則起始節點就是孤立點（無解）；④若p[j].path[i]為終點，則p[j].path[i，i+1，..，N-2]=0，進化結束。若i=N-2，則檢查p[j].path[N-1]能否直達前驅節點，若直達則進化結束，否則用類似步驟3的方法處理其前驅節點。

（2）評估。計算粒子各路徑特征參數和目標函數值p[j].fit，如果是新路由，則插入按目標函數值降序排列的可達路由鏈表。

（3）取代。比較目標函數值，若p[j].p_fit

5.2 遺傳算法實現

遺傳算法[3，9]與PSO的初始化相同。利用錦標賽方法實現選擇算子。以概率Pc進行交叉操作，交叉方法是：①找出用于交叉的父代個體A和B路徑上的所有相同節點；②從相同節點中隨機選取兩個用于交叉，產生兩個新個體；③若新個體中有相同節點，則刪除相同節點間的鏈路（見圖1）。以概率Pm進行變異操作，變異方法是：先對路徑節點p[j].path[i]以概率p更新，再仿照PSO進化操作步驟C的方法進行相應處理。

目標函數常量a和b的設置主要看實際網絡注重時延和帶寬的程度，若側重于追求時延小，則設置a>b；當某段鏈路的時延大于Dmax時，罰函數Fd=λ的值設置越小，目標函數值也就越小，一般設置λ≤0.3；當某段鏈路的帶寬小于一定值時，罰函數Fs=μ的值設置越小，目標函數值也就越小，一般設置μ=0.5左右。本文側重于追求網絡時延小，故此目標函數常量設置為：a=0.6、b=0.4、λ=0.1、μ= 0.5。鏈路特征值的上下限設置取決于實際網絡的性能要求，本文設置為：帶寬下限Bmin=0.1Mbps、帶寬上限Bmax=10Mbps、花費下限Cmin=1、花費上限Cmax=200、時延上限Dmax=250ms、丟包率上限Lmax=0.001。

為便于對比分析，PSO算法和遺傳算法的網絡拓撲結構、網絡狀態數據初始化、群體大小（20）、主循環次數（500）都對應相同。遺傳算法的交叉概率Pc=0.4，變異概率Pm=0.06。PSO算法參數m按照迭代循環次數線性地從2.0遞減到0.01，參數C1取0.2，參數C2取3.0。

6.2 實驗結果

選取多對節點進行測試，表1列舉了具有代表性的6個節點的仿真結果，表2列舉了具有代表性的3對節點的測試結果。

表1的仿真結果表明，在相同時間內（112s），網絡主要節點發送和接收的平均速率PSO和遺傳算法都比SPF明顯提高，并且PSO算法高于遺傳算法。提高的主要原因是：SPF中的數據包在連續兩次運行SPF期間始終沿前一次求得的唯一最優路徑發送，由于網絡鏈路性能時刻在動態變化，重新運行SPF之前原最優路徑的性能很可能變得很差，很顯然這種做法不合理。PSO和遺傳算法能夠很好地解決SPF的這種不合理現象，解決方法是一次運行算法求得最優路徑和多條次優路徑，當前路徑性能一旦發生明顯惡化就立刻選取相對次優的路徑而不必等到下一次運行算法重新路由，這樣相對次優路徑上的網絡資源就得到了有效利用。這說明在性能參數動態變化的OSPF網絡中，為了滿足QoS要求，快速改變路徑是必要的。

表2的測試結果表明，PSO與遺傳算法相比，找到的最佳路由目標函數值大多數相同，少數較優，但次路由的目標函數值均值較大方差較小；最佳路由cost值比較接近SPF，而且次路由cost均值和方差都較小；滿足QoS要求的路徑數量明顯增多，運行時間明顯縮短；SPF只搜尋一條最佳路徑，計算時間顯然最短。這說明PSO算法的搜索能力較強、計算效率較高，比較適宜解決多約束OSPF網絡路由規劃問題。

7 結語

本文重點闡述了PSO算法在OSPF網絡路由選擇中的具體應用，同時比較了PSO算法、遺傳算法和SPF算法的運行結果，通過對比分析可以得出如下結論：在滿足QoS要求的多約束OSPF網絡路由選擇中，與SPF算法相比，PSO與遺傳算法能夠很好地利用相對次優路徑上的網絡資源，從而提高網絡性能；與遺傳算法相比，PSO算法具有搜索能力強、運行效率高等優點。研究表明，PSO算法在滿足QoS要求的OSPF網絡路由選擇領域中具有很好的應用前景，值得進一步研究。

參考文獻：

[1]曾建潮，介婧，崔志華.微粒群算法[M].第1版.北京：科學出版社，2004.

[2]魏娟.基于遺傳算法的OSPF路由研究[J].科技咨詢，2013（22）：3739.

[3]楊云，徐永紅，張千目.一種QoS路由多目標遺傳算法[J].通訊學報，2004（1）：4351.

[4]李想，李勁.基于OSPF協議的光纜需求算法研究[J].信息通訊，2012（2）：193194.

[5]ANTON RIEDL.Optimized routing adaptation in IP networks utilizing OSPF and MPIS[C].IEEE Xplore，2003：17541758.

[6]WANG XIAOMEI，ZHANG ZHENG，RAN CHONGSHEN.A rerouting strategy in lowearth orbit QoS sattllite networks[J].Journal of Beijing University of Postsand Telecommunication，2005，28（1）：3034.

[7]張倩倩，秦瑩瑩.基于動態最短路徑策略的多QoS路由算法[J].軟件導刊，2011，10（6）：3436.

[8]王小明，盧俊嶺，李英姝，等.模糊隨機環境下的無線傳感器網絡多約束多路徑路由[J].計算機學報，2011（5）：779791.

[9]SCHMITT， LOTHAR M.遺傳算法理論[J].Theoretical Computer Science，2004，310（2）：181231.

責任編輯（責任編輯：孫 娟）

英文摘要Abstract：The OSPF network routing problems were solved by the use of traditional SPF algorithm， due to not considering the multiconstraint conditions and the effective use of secondary path， once the optimal path occurs to congestion， the network transmission performance will be decreased dramatically. In this paper， the PSO algorithm was applied to the OSPF network routing planning， used by multiconstraint conditions and combined by the characteristics of OSPF network and a variety of routing parameters， which was effectively improved by the local network congestion and obtained the global optimum fast routing and routing algorithm， and verified the improved algorithm by using the simulation data. The results showed that the proposed algorithm gets better improvement than the genetic algorithm and the traditional SPF algorithm in the solution of route planning problem and the network transmission performance.

英文關鍵詞Key Words： PSO； IGP； Routing Tactics； QoS