基于粒子群算法的计算机网络路由优化研究.docxVIP

文章编号：1007-757X(2014)07-0022-04基于粒子群算法的计算机网络路由优化研究张得生，李留青，陈萍摘要：针对计算机网络规模日益扩大所带来的网络路由优化问题，将其数学本质规划为NP问题，提出使用粒子群优化算法求得路由优化的近似最优解。同时，为了提高粒子群算法的性能引入了变异机制，使粒子群算法的进化速度得到明显提升。仿真实验表明，提出的方法可以在较短时间内得到路由优化的结果，具有较好的有效性和实用性。关键词：网络路由；粒子群算法；优化中图分类号：TP393.02文献标志码：AResearchonOptimizationofComputerNetworkRoutingBasedonParticleSwarmOptimizationAlgorithmZhangDesheng,LiLiuqing,ChenPing(SchoolofInformationEngineering,HuanghuaiUniversity,Zhumadian463000,China)Abstract:Thenetworkroutingoptimizationproblemisincreasinglyevidentwiththegrowingscaleofcomputernetwork.Inordertosolvethisproblem,whichthemathematicalessenceistheNPproblem,themethodofusingparticleswarmalgorithmtoobtainap-proximateoptimalsolutionisproposed.Meanwhile,inordertoimprovetheperformanceofPSO,mutationmechanismisintroduced,sothatthespeedofevolutionparticleswarmalgorithmhasbeensignificantlyimproved.Simulationresultsshowthattheproposedmethodcanbeobtainrouteoptimizationresultsinarelativelyshortperiodoftime,andithasrelativelyeffectivenessandpracticality.Keywords:NetworkRouting;PSOAlgorithm;Optimistic0引言随着计算机技术、通信技术、微电子等技术的逐渐提高，以及互联网的逐渐普及，人们日常的生活越来越离不开计算机网络。在计算机网络给人们生活带来便利的同时，其优化问题也越来越突出。理想的路由选择策略能够大大降低网络的传输时延，提高传输的实时性，并降低网络的运营费用，增强对网络资源的合理有效利用。对于计算机网络来说，优化问题其实就是一类特殊的组合优化问题。而计算机网络的路由优化正是属于NP-hard组合优化问题[1-2]。NP-hard组合优化问题是一类难以求解的组合最优化问题，人们从开始研究直到现在，还没有找到一个算法可以求得其最优解。但是这类问题的实际应用背景很强，所以，为了解决这个问题，通常都是假设这一类难解的组合优化问题不存在最优解，然后，用一些算法求得满足要求的次优解[3]。传统的优化算法存在较大的缺点，其要求被优化对象的数学模型必须精确已知，这在实际应用中往往很难做到。而且，当模型较为复杂以及约束条件较多时，这些方法往往不能进行有效求解，或者即使能够求解但是算法复杂度过高，当模型维数较大时，会出现“组合爆炸”现象。随着NP-hard理论的建立和发展，人们开始尝试使用一些新的算法来优化计算机网络路由，包括神经网络、遗传算法等在内的一些方法都被使用[4-6]，取得了一定的效果。根据现代计算机网络的特点，以及路由优化这个NP问——————————————题的特性，本文提出使用粒子群算法（ParticleSwarmOp-timization，PSO）来解决其优化问题。文中详细的给出了路由优化的数学模型，同时，为了解决PSO算法的早熟收敛问题，引入了变异机制。仿真实验表明，本文提出的优化方法效果较好，具有一定的实用性。1路由优化的数学模型[7]路由优化模型是一个NP完全的组合优化问题,可以把它简化为这样一个问题：已知条件：①网络的拓扑结构、节点集合及链路集合；②分布于网络中的每一个成对通信节点及其可能的路由集合；③在传输过程中对于节点对的一些性能要求，同时要求链路容量已知。问题是：每一个通信节点对都存在多个候选路由，而这些候选路由的性能对于网络的整体性能影响较大，如何从这些备选集合中选取一条最优路由，使得网络的传输性能最佳的同时网络平均时延最小。中间节点位于分组交换网中，