江家寶　鄭尚志

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

關鍵詞：PSO算法；OSPF；網(wǎng)絡路由器；多約束路由；QoS

DOIDOI：10.11907/rjdk.1431035

中圖分類號：TP311

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

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

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

0 引言

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

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

1 OSPF協(xié)議原理

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

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

2 QoS路由問題

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

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

3 QoS路由模型

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

5 OSPF路由選擇實現(xiàn)

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

5.1 PSO算法實現(xiàn)

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

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

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

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

5.2 遺傳算法實現(xiàn)

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

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

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

6.2 實驗結果

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

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

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

7 結語

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

參考文獻：

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

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

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

[4]李想，李勁.基于OSPF協(xié)議的光纜需求算法研究[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]張倩倩，秦瑩瑩.基于動態(tài)最短路徑策略的多QoS路由算法[J].軟件導刊，2011，10（6）：3436.

[8]王小明，盧俊嶺，李英姝，等.模糊隨機環(huán)境下的無線傳感器網(wǎng)絡多約束多路徑路由[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