基于元启发式算法的VNF部署及其并行化

发布时间：2020-11-17 12:38

　　 传统网络中需部署特定物理设备来提供特制功能以满足用户的服务请求,这会造成网络固化,后期升级和维护将花费巨额成本。网络功能虚拟化(Network Functions Virtualization,NFV)通过软硬分离和虚拟化技术,实现了灵活动态的部署和迁移网络功能,很好的解决了上述问题。NFV体系实施过程中的一个关键问题是VNF部署问题,如何在满足各种资源约束和开销下,找出尽可能优的方案将VNF部署在底层硬件上,是本文研究的核心。本文以端到端时延最小化为优化目标,提出了三种改进的元启发式算法来解决,并探索利用Spark平台并行化算法来提升算法性能,具体内容如下:1)提出一种改进型鲸鱼算法。该算法受到遗传算法和果蝇优化算法启发,结合个体交叉操作和个体变异策略,并设计了一种基于概率浓度的最优个体引导策略来增强解质量,加快算法收敛。实验结果表明,相比于经典的遗传算法、粒子群算法等,该算法能获得更优的部署方案。2)提出一种改进型灰狼算法。该算法设计了一种个体角色自适应调整策略,通过个体适应度值把灰狼个体动态的划分为局部挖掘灰狼和全局搜索灰狼,全局搜索灰狼执行基于增量更新的全局搜索操作,增加多样性,局部挖掘灰狼执行基于蚁群寻路的局部挖掘策略,加强搜索结果。实验仿真表明,该算法在所有实现的算法中能获得最优的结果,且算法相对比较稳定。3)提出一种改进型布谷鸟算法。该算法受到粒子群算法启发,在每个个体内部存储了搜索至今的历史最优解,并引入全局因子和局部因子控制个体更新,设计了逻辑邻域搜索和物理邻域搜索两种方式来加强局部挖掘。结果表明,该算法相比于传统的元启发式算法能获得更优的解,且算法速度较快。4)提出了元启发式算法的两种并行化方式。针对基于种群搜索的这类元启发式算法簇,本文详细分析其特点,提出了并行化模型,并基于Spark平台实现了一种通用并行化方法,在通用并行化方法的基础上,针对其缺陷设计了一种定制化的改进型并行化方法。最终结果表明,改进型并行化方法拥有更好的求解效果,能增强算法稳定性,在大规模场景或问题下,能加快算法执行效率,提升运行速度。
【学位单位】：西南交通大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP393.01
【部分图文】：

图 3-2 服务路径示例图给定的个体编码1 2{ , ,..., }kX x x x，部署后产生对应的服务路径 Pa示， 从计算节点1x 出发，到计算节点kx 处终止，相邻两个链路集合形成子路径，子路径(1 2x ,x )，子路径(2 3x ,x )…子路径(1k x 成了 。个体适应度评估1 2{ , ,..., }KC f f f，个体编码体适应度 fitness,…,k](2-2)至(2-4)判断 VNFif 部署在ix 上是否满足资源约束，不满足则该个体非+= ( )PCSiD f,…,k-1]stra 算法找到子路径(1,i ix x )，该子路径的传输时延之和为1( , )sumi iD x x (2-5)判断该子路径是否满足链路上的带宽约束，不满足则该个体非法，返回

图 3-5 NSM 机制示意图是 NSM 示意图，图中有 4 个计算节点和 3 个 VNF，NSM 按公署在每个计算节点上的概率ufvP ，对1f 用轮盘赌选出其部署在点 v4，f3选中节点 v3。的伪代码如下：进型灰狼算法的基于寻路的局部挖掘策略exploitW 个体编码1 2{ , ,..., }kX x x x， 狼个体编码1 2{ , ,...,X x x 1 2{ , ,..., }kX x x x ， 狼个体编码1 2{ , ,..., }kX x x x 、w , k] rnd [0,1]a)arnd w w )

图 3-5 NSM 机制示意图是 NSM 示意图，图中有 4 个计算节点和 3 个 VNF，NSM 按公署在每个计算节点上的概率ufvP ，对1f 用轮盘赌选出其部署在点 v4，f3选中节点 v3。的伪代码如下：进型灰狼算法的基于寻路的局部挖掘策略exploitW 个体编码1 2{ , ,..., }kX x x x， 狼个体编码1 2{ , ,...,X x x 1 2{ , ,..., }kX x x x ， 狼个体编码1 2{ , ,..., }kX x x x 、w , k] rnd [0,1]a)arnd w w )
【相似文献】

相关期刊论文 前10条

1 蒋少丙;刘书刚;;面向过程的任务并行化设计方法[J];计算机系统应用;2015年09期

2 本刊编辑部;;“地理计算并行化”专辑征稿[J];地球信息科学学报;2014年06期

3 齐书阳;;迎接并行化的明天[J];软件世界;2009年06期

4 金国华，陈福接;并行化技术与工具[J];计算机研究与发展;1996年07期

5 杨桃栏;程序并行化的有力工具——介绍Kuck公司的KAP[J];计算机工程与科学;1989年04期

6 本刊编辑部;;“地理计算并行化”专辑导言[J];地球信息科学学报;2015年05期

7 张妮娜;窦衡;;并行化改进遗传算法的FPGA高速实现方法[J];信息与电子工程;2012年01期

8 蔡砥,滕丽,王铮;一种禁忌搜索算法在计算网格中的并行化策略[J];微电子学与计算机;2004年06期

9 陈水福,孙炳楠,唐锦春;建筑风压数值模拟的几种并行化策略[J];计算力学学报;1998年02期

10 曹琳,杨学军,金国华;两种并行化机制的分析[J];计算机研究与发展;1993年09期

相关博士学位论文 前10条

1 张平;并行化编译器中并行程序自动生成和性能优化技术研究[D];解放军信息工程大学;2006年

2 董春丽;并行化编译中数据和计算的自动划分及优化技术研究[D];解放军信息工程大学;2007年

3 程兴国;仿生算法的动态反馈机制及其并行化实现方法研究[D];华南理工大学;2013年

4 赵岩;复杂机电系统仿真的并行化方法研究[D];华中科技大学;2017年

5 傅游;稀薄气体Monte Carlo数值仿真并行化技术研究与实现[D];西北工业大学;2002年

6 耿光超;电力系统稳定约束最优潮流：模型、算法与并行化[D];浙江大学;2014年

7 丁晓宁;面向CFD的交互式并行化技术研究[D];西北工业大学;2002年

8 高放;面向片上异构多核系统的机器学习算法并行化技术研究[D];北京工业大学;2017年

9 周纯葆;基因岛预测与隔离迁移模型并行化[D];吉林大学;2012年

10 郭琦;异构多核可重构平台指令并行化关键问题研究[D];中国科学技术大学;2015年

相关硕士学位论文 前10条

1 徐熙豪;基于FUSE的MBR编码的并行化研究[D];华中科技大学;2019年

2 周芯宇;基于元启发式算法的VNF部署及其并行化[D];西南交通大学;2019年

3 刘琴;基于种子扩展的社区发现算法及其并行化[D];南京信息工程大学;2019年

4 刘振羽;基于Spark的基因组学数据比对算法的并行化研究与比对平台构建[D];内蒙古农业大学;2019年

5 倪宁;一种簇存储结构中GPU加速并行化R-tree的方法[D];上海交通大学;2017年

6 罗钰敏;事件知识图谱并行化研究及应用[D];电子科技大学;2019年

7 何宗浩;基于Spark的Top-k高效用项目集挖掘研究[D];重庆邮电大学;2019年

8 许德心;关联规则挖掘算法的并行化及应用研究[D];南京邮电大学;2019年

9 陆俊尧;协同过滤算法的设计及并行化实现与应用[D];南京邮电大学;2019年

10 陶飞;基于姿态的属性学习并行化方法在行人再识别中的研究[D];江苏大学;2019年

本文编号：2887509