基于粒子群算法的計算機網絡路由優化研究

張得生，李留青，陳萍

基于粒子群算法的計算機網絡路由優化研究

張得生，李留青，陳萍

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

網絡路由；粒子群算法；優化

0 引言

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

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

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

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

1 路由優化的數學模型

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

已知條件：

① 網絡的拓撲結構、節點集合及鏈路集合；

② 分布于網絡中的每一個成對通信節點及其可能的路由集合；

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

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

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

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

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

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

2 PSO算法及其改進

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

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

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

3 利用PSO算法進行網絡路由優化的實現步驟

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

圖1 算法流程圖

4 仿真實驗

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

圖2 USA Network 拓撲結構

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

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

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

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

圖3 最優個體適應度值進化對比

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

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

圖4 傳統PSO算法與改進PSO算法性能對比

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

5 總結

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

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

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

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

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

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

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

[7] 李祖鵬, 黃建華, 唐輝. 基于P2P計算模式的自組織網絡路由模型[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-），女，黃淮學院，教授，碩士，研究方向：計算機網絡及信息安全，駐馬店 463000