改进的粒子群算法在虚拟网映射中的应用

J4 ›› 2014, Vol. 36 ›› Issue (11): 2169-2173.

改进的粒子群算法在虚拟网映射中的应用

胡颖，庄雷

（郑州大学信息工程学院，河南郑州 450000）

收稿日期:2014-07-08 修回日期:2014-09-10 出版日期:2014-11-25 发布日期:2014-11-25
基金资助:
国家973计划资助项目（2012CB315901）

Applying an improved particle swarm
optimization algorithm in virtual network mapping

HU Ying,ZHUANG Lei

(College of Information and Engineering,Zhengzhou University,Zhengzhou 450000,China)

Received:2014-07-08 Revised:2014-09-10 Online:2014-11-25 Published:2014-11-25

摘要/Abstract

摘要：

应用粒子群算法解决虚拟网映射问题，可以大大减少网络资源的消耗，却也容易出现早熟的现象。通过增加随机因素、沿原方向飞行操作和改变原历史因素对搜索过程的指导等方式，既保留了历史因素对搜索的指导，又在此基础上加大了搜索范围，一定程度上减少了早熟收敛带来的问题。最终实验结果表明，改进的粒子群算法能够应用于虚拟网映射，和原粒子群算法相比，能够更有效减少资源消耗。

关键词: 虚拟网映射, 早熟收敛, 粒子群算法

Abstract:

Using the Particle Swarm Optimization (PSO) algorithm to solve the problem of virtual network embedding can reduce the consumption of network resource, but it also brings premature convergence.An improved PSO algorithm is proposed,which adds random factors,operates along the original direction, and changes the introduction of history factors to the search process.The proposal not only keeps the instruction of history factors to the search process but also increases the search range,thus relieving, the premature convergence problems to a certain extent.The experimental results demonstrate that the improved PSO algorithm can be applied to virtual network mapping and effectively reduce resource consumption in comparison with the original PSO algorithm.

Key words: virtual network mapping;premature convergence;particle swarm optimization (PSO)

胡颖，庄雷. 改进的粒子群算法在虚拟网映射中的应用[J]. J4, 2014, 36(11): 2169-2173.

HU Ying,ZHUANG Lei. Applying an improved particle swarm
optimization algorithm in virtual network mapping [J]. J4, 2014, 36(11): 2169-2173.

参考文献［16］

［1］	Shenker S, Peterson L, Turner J. Overcoming the Internet impasse through virtualization［C］∥Proc of the 3rd ACM Workshop on Hot Topics in Networks, 2004:3441.
［2］	Turner J,Taylor D. Diversifying the Internet［C］∥Proc of IEEE GLOBECOM’05, 2005:755760.
［3］	Anderson T, Peterson L, Shenker S, et al. Overcoming the Internet impasse through virtualization［J］. IEEE Computer, 2005,38(4):3441.
［4］	Feamster N, Gao L, Rexford J. How to lease the Internet in your spare time［J］. ACM SIGCOMM Computer Communications Review, 2007,37(1):6164.
［5］	Chowdhury N K, Boutaba R. Network virtualization:State of the art and research challenges［J］. IEEE Communications Magazine, 2009, 47(7):2026.
［6］	Andersen D G. Theoretical approaches to node assignment［Z］.Pittsburgh:Carnegie Mellon University, 2002.
［7］	Yu M, Yi Y, Rexford J, et al. Rethinking virtual network embedding:Substrate support for path splitting and migration［J］. ACM SIGCOMM Computer Communication Review, 2008, 38(2):1729.
［8］	James K,Eberhart R.Particle swarm optimization［C］∥Proc of IEEE International Conference on Neural Networks, 1995:19421948.
［9］	Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topology awareness and optimization［J］. Computer Networks, 2012, 56(6):17971813.
［10］	Lu J, Turner J. Efficient mapping of virtual networks onto a shared substrate［R］. Technical Report WUCSE200635. Washington:Washington University, 2006.
［11］	Fan J, Ammar M H. Dynamic topology configuration in service overlay networks:A study of reconfiguration policies［C］∥Proc of INFOCOM’06, 2006:1.
［12］	Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection［C］∥Proc of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, 2009:8188.
［13］	Cheng X, Su S, Zhang Z, et al. Virtual network embedding through topologyaware node ranking［J］. ACM SIGCOMM Computer Communication Review, 2011, 41(2):3847.
［14］	Chowdhury N M M K, Rahman M R, Boutaba R. Virtual network embedding with coordinated node and link mapping［C］∥Proc of INFOCOM’09, 2009:783791.
［15］	Zhang Z, Cheng X, Su S, et al. A unified enhanced particle swarm optimizationbased virtual network embedding algorithm［J］. International Journal of Communication Systems, 2013, 26(8):10541073.
［16］	Zhu Qiang, Wang Huiqiang, Lü Hongwu, et al. VNEAFS:Virtual network embedding based on artificial fish swarm［J］. Journal on Communications, 2012,33(Z1):170177.
	附中文参考文献：
	朱强, 王慧强, 吕宏武, 等. VNEAFS:基于人工鱼群的网络虚拟化映射算法［J］. 通信学报, 2012,33(Z1):170177.

[1]	王翼虎, 王思明. 基于改进粒子群算法的无人机路径规划[J]. 计算机工程与科学, 2020, 42(09): 1690-1696.
[2]	王永琦, 江潇潇. 基于混合灰狼算法的机器人路径规划[J]. 计算机工程与科学, 2020, 42(07): 1294-1301.
[3]	闫盼盼，俞海珍，史旭华，万凯. 基于Pareto支配的MPRM电路面积与功耗优化[J]. 计算机工程与科学, 2020, 42(04): 596-602.
[4]	覃远年，梁仲华. 基于混合粒子群算法的运动估计研究[J]. 计算机工程与科学, 2019, 41(04): 758-764.
[5]	邱云飞，李智义. 改进人工鱼群算法在SVM参数优化中的应用[J]. 计算机工程与科学, 2018, 40(11): 2074-2079.
[6]	南敬昌，陆亚男，高明明. 基于改进混合算法优化RBF网络的滤波器建模[J]. 计算机工程与科学, 2018, 40(07): 1329-1336.
[7]	王英博1，王艺星2. 基于SQP局部搜索的多子群果蝇优化算法[J]. 计算机工程与科学, 2018, 40(05): 906-915.
[8]	赵婧1,魏彬2. 标签SNPs选择及重构算法研究[J]. 计算机工程与科学, 2016, 38(11): 2328-2334.
[9]	熊聪聪1，耿世洁1，董昊2. 基于混合算法的降水集成预报研究[J]. 计算机工程与科学, 2016, 38(10): 2147-2152.
[10]	余胜威，曹中清. 基于分数阶达尔文粒子群FODPSO算法的图像分割[J]. 计算机工程与科学, 2016, 38(09): 1836-1842.
[11]	李锋刚1,2，骆林1,2，陈亚波1,2,蒋祥飞1,2. 求解均值-CVaR投资组合模型的改进粒子群算法[J]. 计算机工程与科学, 2016, 38(09): 1870-1877.
[12]	赵平，吴昊. 差分进化混合粒子群算法求解装配式住宅项目进度优化问题[J]. 计算机工程与科学, 2016, 38(07): 1495-1501.
[13]	卢志刚，申康. 基于粒子群蚁群算法的供应链合作伙伴选择研究[J]. J4, 2016, 38(05): 946-953.
[14]	刘欢1，2,肖根福3，欧阳春娟1. 基于互学习的自适应PSO算法的亚像素定位研究[J]. J4, 2016, 38(04): 747-754.
[15]	米根锁,梁利,杨润霞. 灰色变异粒子群算法在公交客流量预测中的应用[J]. J4, 2015, 37(01): 104-110.