張得生，李留青，陳萍

基于粒子群算法的計算機網(wǎng)絡路由優(yōu)化研究

張得生，李留青，陳萍

針對計算機網(wǎng)絡規(guī)模日益擴大所帶來的網(wǎng)絡路由優(yōu)化問題，將其數(shù)學本質規(guī)劃為NP問題，提出使用粒子群優(yōu)化算法求得路由優(yōu)化的近似最優(yōu)解。同時，為了提高粒子群算法的性能引入了變異機制，使粒子群算法的進化速度得到明顯提升。仿真實驗表明，提出的方法可以在較短時間內得到路由優(yōu)化的結果，具有較好的有效性和實用性。

網(wǎng)絡路由；粒子群算法；優(yōu)化

0 引言

隨著計算機技術、通信技術、微電子等技術的逐漸提高，以及互聯(lián)網(wǎng)的逐漸普及，人們日常的生活越來越離不開計算機網(wǎng)絡。在計算機網(wǎng)絡給人們生活帶來便利的同時，其優(yōu)化問題也越來越突出。理想的路由選擇策略能夠大大降低網(wǎng)絡的傳輸時延，提高傳輸?shù)膶崟r性，并降低網(wǎng)絡的運營費用，增強對網(wǎng)絡資源的合理有效利用。對于計算機網(wǎng)絡來說，優(yōu)化問題其實就是一類特殊的組合優(yōu)化問題。而計算機網(wǎng)絡的路由優(yōu)化正是屬于NP-hard組合優(yōu)化問題[1-2]。

NP-hard組合優(yōu)化問題是一類難以求解的組合最優(yōu)化問題，人們從開始研究直到現(xiàn)在，還沒有找到一個算法可以求得其最優(yōu)解。但是這類問題的實際應用背景很強，所以，為了解決這個問題，通常都是假設這一類難解的組合優(yōu)化問題不存在最優(yōu)解，然后，用一些算法求得滿足要求的次優(yōu)解[3]。

傳統(tǒng)的優(yōu)化算法存在較大的缺點，其要求被優(yōu)化對象的數(shù)學模型必須精確已知，這在實際應用中往往很難做到。而且，當模型較為復雜以及約束條件較多時，這些方法往往不能進行有效求解，或者即使能夠求解但是算法復雜度過高，當模型維數(shù)較大時，會出現(xiàn)“組合爆炸”現(xiàn)象。隨著NP-hard理論的建立和發(fā)展，人們開始嘗試使用一些新的算法來優(yōu)化計算機網(wǎng)絡路由，包括神經(jīng)網(wǎng)絡、遺傳算法等在內的一些方法都被使用[4-6]，取得了一定的效果。

根據(jù)現(xiàn)代計算機網(wǎng)絡的特點，以及路由優(yōu)化這個NP問題的特性，本文提出使用粒子群算法（Particle Swarm Optimization，PSO）來解決其優(yōu)化問題。文中詳細的給出了路由優(yōu)化的數(shù)學模型，同時，為了解決PSO算法的早熟收斂問題，引入了變異機制。仿真實驗表明，本文提出的優(yōu)化方法效果較好，具有一定的實用性。

1 路由優(yōu)化的數(shù)學模型

路由優(yōu)化模型是一個NP完全的組合優(yōu)化問題, 可以把它簡化為這樣一個問題：

已知條件：

① 網(wǎng)絡的拓撲結構、節(jié)點集合及鏈路集合；

② 分布于網(wǎng)絡中的每一個成對通信節(jié)點及其可能的路由集合；

③ 在傳輸過程中對于節(jié)點對的一些性能要求，同時要求鏈路容量已知。

問題是：每一個通信節(jié)點對都存在多個候選路由，而這些候選路由的性能對于網(wǎng)絡的整體性能影響較大，如何從這些備選集合中選取一條最優(yōu)路由，使得網(wǎng)絡的傳輸性能最佳的同時網(wǎng)絡平均時延最小。

中間節(jié)點位于分組交換網(wǎng)中，按照存儲轉發(fā)方式工作。其中，等待使用輸出鏈路的時延最長，結點處理時延和鏈路傳播時延較短，可以忽略不計。這種情況下，分組交換網(wǎng)就等同于一個M/M/1排隊模型，也就是說報文處理時間可以看作是一個具有連續(xù)時間變化的負指數(shù)變量，同時可以用泊松過程來描述單隊列情況下分組到達和發(fā)送的整個過程。因此，可以用式（1）來刻畫某條鏈路l的報文分組（PL）的平均時延為公式（1）：

整個網(wǎng)絡的平均時延是通過對所有鏈路時延進行加權求和得到，如公式（2）：

對于公式（2）需要考慮以下3個約束條件：

網(wǎng)絡路由優(yōu)化模型是一個多約束條件下的非線性0-1規(guī)劃問題。設置約束條件①是為了保證鏈路的數(shù)據(jù)傳輸速率不超過鏈路容量；而約束條件②表明任一個通信節(jié)點對都有且僅有一條路由存在，以保證其通信需求；最后，約束條件③規(guī)定了決策變量問題的核心，即在滿足上述條件下，使得目標函數(shù)值最小。

2 PSO算法及其改進

PSO算法是由J.Kennedy與R.Eberthart于1995年共同提出的一種仿生優(yōu)化計算方法，其思想來源于人工生命和演化計算理論，最初的原型是模仿鳥群的捕食行為。該算法的計算過程為：首先，初始化一群代表最優(yōu)解的粒子，但要注意由于其是潛在的解，因此，必須在可能求解的范圍內進行初始化。這些初始化的粒子具有3個性能指標，分別為位置、速度和適應度。其中，適應度的值直接反映粒子性能的好壞，所以，適應度函數(shù)的正確選取十分重要。求解的過程可看作是粒子的一個運動過程，每一個粒子個體的位置在求解過程中都要不斷更新，主要是依據(jù)個體極值Pbest和群體極值Gbest。粒子更新了一次位置以后，需要重新計算此時的適應度值，其目的是與Pbest和Gbest的適應度值進行比較，根據(jù)優(yōu)劣程度進行更新[8]。

粒子的速度和位置在每一次迭代過程中都需要不斷更新，更新公式為公式（3）、（4）：

容易早熟收斂是PSO算法存在的一個不可忽視的缺陷。針對這一問題，本文參考GE算法中的變異操作，在PSO算法中引入這種機制，即設定一個適合的概率，按照這個概率對某些變量重新初始化。在PSO算法中引入變異機制以后，可以有效的使種群搜索空間得到擴展，這樣粒子便不會僅局限于原來的最優(yōu)值位置，能夠搜索更大的潛在解空間，同時保持了種群多樣性。但是，本文引入的并不是普通的簡單變異算子，而是使用參考文獻[9]中的Sigmoid形式變異算子，具體形式如公式（5）：

3 利用PSO算法進行網(wǎng)絡路由優(yōu)化的實現(xiàn)步驟

首先，根據(jù)計算機網(wǎng)絡的規(guī)模和拓撲結構，確定網(wǎng)絡中變量的個數(shù)。然后，將這些變量設定為PSO算法所需要的粒子，同時，根據(jù)式(2)計算粒子適應度值，接下來進行個體和群體尋優(yōu)迭代。粒子速度和位置按照公式（3）和（4）進行更新，具體的算法實現(xiàn)流程如圖1所示：

圖1 算法流程圖

4 仿真實驗

本文所采用的實驗仿真對象是Matlab自帶數(shù)據(jù)集中的USA Network，其網(wǎng)絡拓撲結構如圖2所示：

圖2 USA Network 拓撲結構

該網(wǎng)絡具有10個結點，15條鏈路，每條鏈路上標有鏈路編號及鏈路容量(kbit/s)。用表示節(jié)點對之間的通信量，并且假定節(jié)點對與節(jié)點對之間的通信線路和鏈路容量完全相同。平均報文長度為優(yōu)化目標為：優(yōu)選出各節(jié)點對之間的最佳通信路由，使得網(wǎng)絡平均時延達到最小。

為了利用PSO算法優(yōu)選出最佳的路由方案，首先，分析圖2中的網(wǎng)絡結構，可以確定這是一個具有20個變量和25個約束條件的非線性0-1規(guī)劃問題。為了進一步計算，下面給出通信量和候選路由矩陣，如表1所示：

表1 通信量和候選路由矩陣

仿真時設定種群粒子數(shù)為20，每個粒子的維數(shù)為20，算法迭代進化次數(shù)為100。首先比較一下引入變異機制以后PSO算法性能的提升，如圖3所示：

圖3 最優(yōu)個體適應度值進化對比

可見改進后的PSO算法，其適應度的進化速度得到明顯提升。網(wǎng)絡路由的優(yōu)化結果為：通信路徑最優(yōu)解為即使用傳統(tǒng)PSO算法時，最小時延為0.089570s；改進PSO算法得到的為0.089269s。這個實驗結果表明，PSO算法可以比較有效的解決網(wǎng)絡路由優(yōu)化問題，具有較好的全局尋優(yōu)能力。

為了進一步全面比較本文提出的改進PSO算法與傳統(tǒng)PSO算法在處理網(wǎng)絡路由優(yōu)化問題時的性能，本文又選取了Matlab軟件標準網(wǎng)絡測試數(shù)據(jù)集中的共20個網(wǎng)絡，其中包括3個中型網(wǎng)絡，分別為NASA Network、Mini Pacific Ocean Network以及Central bank Network。在軟硬件環(huán)境和測試數(shù)據(jù)集都一致的情況下，兩種算法的平均最小時延如圖4所示：

圖4 傳統(tǒng)PSO算法與改進PSO算法性能對比

從圖4中可以明顯看出，改進后的PSO算法在處理網(wǎng)絡路由優(yōu)化問題時，明顯網(wǎng)絡平均時延要小于傳統(tǒng)PSO算法。尤其是在第4、10和17位置，分別是3個中型結構網(wǎng)絡，傳統(tǒng)PSO算法的時延分別為0.823，0.787，0.801，而改進后的PSO算法時延僅為0.694，0.547，0.673，工作效率明顯要更優(yōu)。而在可以得到同樣結果的情況下，工作效率的明顯提升具有非常重要的工程實踐意義。因此，本文提出的改進PSO算法不僅可以正確的得到網(wǎng)絡路由的最終優(yōu)化結果，而且可以獲得更為少的網(wǎng)絡時延。

5 總結

網(wǎng)絡路由優(yōu)化一直是計算機網(wǎng)絡管理中的一個重要問題。本文根據(jù)其數(shù)學模型的本質，將其作為NP規(guī)劃問題處理。采用PSO智能算法解決其路徑尋優(yōu)，并引入變異機制改善傳統(tǒng)PSO方法的不足。仿真實驗表明，本文提出的這種方案可以較好的解決基于時延的動態(tài)路由選擇問題，算法簡單，適時性高，能夠獲得全局近似最優(yōu)解，使得在網(wǎng)絡的管理過程中可以根據(jù)計算結果進行動態(tài)路由選擇和最佳流量分配，以達到控制網(wǎng)絡時延的目的。

[1] 寇增濤. 計算機網(wǎng)絡路由研究概述[J]. 計算機光盤軟件與應用, 2012, 10(10): 59-61.

[2] 馬偉. 計算機網(wǎng)絡路由探究綜述[J]. 電子測試, 2013, 13(7): 250-251.

[3] 王錫智. 計算機網(wǎng)絡路由技術研究綜述[J]. 煤炭技術, 2013, 32(7): 160-162.

[4] 孔玉靜, 侯鑫, 華爾天等. 基于BP神經(jīng)網(wǎng)絡的無線傳感器網(wǎng)絡路由協(xié)議的研究[J]. 傳感技術學報, 2013, 26(2): 246-250.

[5] 孫力娟, 吳新余. 應用遺傳算法求解計算機通信網(wǎng)的最佳路由: —種新的遍歷匹配選擇算法[J].南京郵電學院報, 1996, 16(2): 16-21.

[6] 李曉磊, 邵之江, 錢積新.一種基于動物自治體的尋優(yōu)模式: 魚群算法[J].系統(tǒng)工程理論與實踐, 2002.22(11): 32-28.

[7] 李祖鵬, 黃建華, 唐輝. 基于P2P計算模式的自組織網(wǎng)絡路由模型[J]. 軟件學報, 2005, 16(5): 916-931.

[8] 紀震, 廖惠連. 粒子群算法及應用[M].北京：科學出版社，2009.

[9] 吳浩揚, 朱長純, 常炳圍等. 基于種群過早收斂程度定量分析的改進自適應遺傳算法[J]. 西安交通大學學報, 1999, 33(11): 27-30.

Research on Optimization of Computer Network Routing Based on Particle Swarm Optimization Algorithm

Zhang Desheng, Li Liuqing, Chen Ping
(School of Information Engineering, Huanghuai University, Zhumadian 463000, China)

The network routing optimization problem is increasingly evident with the growing scale of computer network. In order to solve this problem, which the mathematical essence is the NP problem, the method of using particle swarm algorithm to obtain approximate optimal solution is proposed. Meanwhile, in order to improve the performance of PSO, mutation mechanism is introduced, so that the speed of evolution particle swarm algorithm has been significantly improved. Simulation results show that the proposed method can be obtain route optimization results in a relatively short period of time, and it has relatively effectiveness and practicality.

Network Routing; PSO Algorithm; Optimistic

TP393.02

A

1007-757X(2014)07-0022-04

2014.06.15）

河南省教育廳科技攻關項目（No.13A520786）；河南省科技攻關項目（No.122102210510）

張得生（1982-），男，黃淮學院，實驗師，碩士，研究方向：計算機應用，駐馬店 463000李留青（1981-），女，黃淮學院，講師，碩士，研究方向：計算機應用，駐馬店 463000陳 萍（1969-），女，黃淮學院，教授，碩士，研究方向：計算機網(wǎng)絡及信息安全，駐馬店 463000