路由器技術(shù)在現(xiàn)在應(yīng)用也是非常廣泛的，很多路由器的功能不僅僅是分散網(wǎng)絡(luò)信號(hào)了。路由器也是網(wǎng)絡(luò)連接中最關(guān)鍵的一個(gè)設(shè)備。本文是一篇電子技術(shù)論文發(fā)表范文，主要論述了基于PSO算法的OSPF多約束路由策略。
　　摘要：利用傳統(tǒng)SPF算法解決OSPF網(wǎng)絡(luò)路由難題時(shí)，由于沒有考慮多約束條件和有效利用次路徑，一旦最優(yōu)路徑發(fā)生擁塞，網(wǎng)絡(luò)傳輸性能將急劇降低。將PSO算法應(yīng)用于OSPF網(wǎng)絡(luò)路由規(guī)劃，利用多約束條件并結(jié)合OSPF網(wǎng)絡(luò)多種路由參數(shù)的特性，重點(diǎn)對(duì)有效改善網(wǎng)絡(luò)局部擁塞和快速求得全局最佳路由及若干次路由算法進(jìn)行探究，并利用仿真數(shù)據(jù)對(duì)所提出的改進(jìn)算法進(jìn)行驗(yàn)證。結(jié)果表明，在解決OSPF網(wǎng)絡(luò)路由規(guī)劃問題中，PSO算法較傳統(tǒng)遺傳算法和SPF算法能實(shí)現(xiàn)網(wǎng)路傳輸性能更優(yōu)。

　　關(guān)鍵詞：PSO算法,OSPF,網(wǎng)絡(luò)路由器,多約束路由,QoS

　　作者簡(jiǎn)介作者簡(jiǎn)介：江家寶(1968-)，男，安徽無為人，碩士，巢湖學(xué)院信息工程學(xué)院講師，研究方向?yàn)槟Ｊ阶R(shí)別與智能控制、嵌入式系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò);鄭尚志(1963-)，男，安徽巢湖人，博士，巢湖學(xué)院信息工程學(xué)院教授，研究方向?yàn)椴僮飨到y(tǒng)理論、人工智能。

　　0 引言

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

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

　　1 OSPF協(xié)議原理

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

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

　　2 QoS路由問題

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

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

　　3 QoS路由模型

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

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

　　采用十進(jìn)制編碼方案。以路徑中節(jié)點(diǎn)的十進(jìn)制標(biāo)號(hào)序列作為路徑編碼值。比如，路徑編碼表示的路徑為。

　　5.1 PSO算法實(shí)現(xiàn)

　　算法每次迭代對(duì)所有粒子都依次進(jìn)行“進(jìn)化、評(píng)估、取代”操作。

　　(1)進(jìn)化。它是算法的核心，對(duì)粒子j路徑上的每點(diǎn)進(jìn)行如下操作：①利用式(4)計(jì)算并處理第k維飛行速度V[j][k];②依據(jù)式(5)計(jì)算第k維位置，記x=(p[j].path[k]+V[j][k])，結(jié)果是浮點(diǎn)數(shù)，按0.5的概率向上/下取整后再對(duì)(N+1)取余;③這是進(jìn)化的難點(diǎn)所在，假設(shè)路徑數(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é)點(diǎn)。若x值非法(是負(fù)數(shù)、起點(diǎn)、終點(diǎn)、已經(jīng)經(jīng)歷過的節(jié)點(diǎn))，則從[0，N]中隨機(jī)選取一個(gè)合法值給x。若x=0或與P[j].path[i]前驅(qū)節(jié)點(diǎn)可達(dá)，p[j].path[i]=x;否則作如下修正，記p[j].path[i]前驅(qū)節(jié)點(diǎn)p[j].path[m]的直達(dá)節(jié)點(diǎn)集合為A，p[j].path[0：m-1]經(jīng)歷過的節(jié)點(diǎn)集合為B，從集合A-B中隨機(jī)選取一點(diǎn)賦給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]，這時(shí)肯定能從起始位置的直達(dá)節(jié)點(diǎn)中找一個(gè)節(jié)點(diǎn)作為p[j].path[1]的值，否則起始節(jié)點(diǎn)就是孤立點(diǎn)(無解);④若p[j].path[i]為終點(diǎn)，則p[j].path[i，i+1，..，N-2]=0，進(jìn)化結(jié)束。若i=N-2，則檢查p[j].path[N-1]能否直達(dá)前驅(qū)節(jié)點(diǎn)，若直達(dá)則進(jìn)化結(jié)束，否則用類似步驟3的方法處理其前驅(qū)節(jié)點(diǎn)。 　　(2)評(píng)估。計(jì)算粒子各路徑特征參數(shù)和目標(biāo)函數(shù)值p[j].fit，如果是新路由，則插入按目標(biāo)函數(shù)值降序排列的可達(dá)路由鏈表。

　　(3)取代。比較目標(biāo)函數(shù)值，若p[j].p_fit　　5.2 遺傳算法實(shí)現(xiàn)

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

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

　　為便于對(duì)比分析，PSO算法和遺傳算法的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)狀態(tài)數(shù)據(jù)初始化、群體大小(20)、主循環(huán)次數(shù)(500)都對(duì)應(yīng)相同。遺傳算法的交叉概率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 實(shí)驗(yàn)結(jié)果

　　選取多對(duì)節(jié)點(diǎn)進(jìn)行測(cè)試，表1列舉了具有代表性的6個(gè)節(jié)點(diǎn)的仿真結(jié)果，表2列舉了具有代表性的3對(duì)節(jié)點(diǎn)的測(cè)試結(jié)果。

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

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

　　7 結(jié)語

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

　　參考文獻(xiàn)：

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

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

　　[3]楊云，徐永紅，張千目.一種QoS路由多目標(biāo)遺傳算法[J].通訊學(xué)報(bào)，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]張倩倩，秦瑩瑩.基于動(dòng)態(tài)最短路徑策略的多QoS路由算法[J].軟件導(dǎo)刊，2011，10(6)：3436.

　　[8]王小明，盧俊嶺，李英姝，等.模糊隨機(jī)環(huán)境下的無線傳感器網(wǎng)絡(luò)多約束多路徑路由[J].計(jì)算機(jī)學(xué)報(bào)，2011(5)：779791.
　　電子技術(shù)論文發(fā)表期刊推薦《計(jì)算機(jī)與現(xiàn)代化》雜志成為“中國科技核心期刊”、“中國科技論文統(tǒng)計(jì)源期刊”! 《計(jì)算機(jī)與現(xiàn)代化》系《中國學(xué)術(shù)期刊綜合評(píng)價(jià)數(shù)據(jù)庫來源期刊》;《中國學(xué)術(shù)期刊(光盤版)》、《中國期刊網(wǎng)》、《中國數(shù)字化期刊群》、《中國核心期刊(遴選)數(shù)據(jù)庫》全文引用期刊。

---

轉(zhuǎn)載請(qǐng)注明來自：http://www.jinnzone.com/dianzijishulw/53231.html