基于元胞遗传机制的虚拟网络映射算法

doi:10.11896／j.issn.1002-137X.2018.12.009

计算机科学 ›› 2018, Vol. 45 ›› Issue (12): 66-70.doi: 10.11896／j.issn.1002-137X.2018.12.009

基于元胞遗传机制的虚拟网络映射算法

王明, 庄雷, 王国卿, 张坤丽

(郑州大学信息工程学院郑州450000)

收稿日期:2017-11-03 出版日期:2018-12-15 发布日期:2019-02-25
作者简介:王明(1992－),男,硕士,主要研究方向为下一代互联网;庄雷(1963－),女,博士,教授,博士生导师,CCF高级会员,主要研究方向为形式语言与自动机理论、模型检测、下一代互联网,E-mail:ielzhuang@zzu.edu.cn(通信作者);王国卿(1989－),男,博士,主要研究方向为模型检测、虚拟网络映射;张坤丽(1977－),女,博士,讲师,主要研究方向为机器学习、自然语言处理。
基金资助:
本文受国家973计划(2012CB315901),国家自然科学基金(61379079)资助。

Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism

WANG Ming, ZHUANG Lei, WANG Guo-qing, ZHANG Kun-li

(School of Information Engineering,Zhengzhou University,Zhengzhou 450000,China)

Received:2017-11-03 Online:2018-12-15 Published:2019-02-25

摘要/Abstract

摘要： 满足节点和链路约束条件的虚拟网络请求最优映射问题是NP-难问题,粒子群算法和遗传算法等启发式算法是解决这类问题的主要手段。这类启发式算法从数学模型优化的角度来求解问题,但未考虑虚拟网络映射节点本身的变化对最优解的影响,存在收敛速度较慢和容易陷入局部最优解的问题。文中将元胞遗传机制引入虚拟网络映射问题中,提出了虚拟网络映射算法VNE-CGA。该算法利用元胞自动机对节点建模,使用“B4567/S1234”规则来替代传统遗传算法中的交叉操作;通过对邻居的学习来指导个体的寻优过程,弥补了传统遗传算法的固有缺陷,最终提高了虚拟网络请求的接受率以及底层物理网络的运营收益。

关键词: 虚拟网络映射, 遗传算法, 元胞遗传算法, 元胞自动机

Abstract: The optimal mapping problem of virtual network requests which satisfies the constraints of nodes and links is an NP-hard problem.Heuristic algorithms,such as particle swarm algorithm and genetic algorithm,can solve those problems.They solve the problem from the perspective of mathematical model optimization,but fail to consider the influence of the change of virtual network mapping node itself on the optimal solution,and they also have the problems of slow convergence speed and being easy to fall into local optimal solution.This paper introduced the cellular genetic mechanism into the problem of virtual network mapping,and proposed the virtual network mapping algorithm (VNE-CGA).This algorithm uses the cellular automata to model the nodes,and replaces the cross operator in the traditional genetic algorithm with the “B4567 / S1234” rule.Besides,the individual’s optimization process is guided through lear-ning from neighbors,making up for the inherent defects of traditional genetic algorithms.Finally it improves the request acceptance rate of virtual network and the operating income of underlying physical network.

Key words: Cellular automata, Cellular genetic algorithm, Genetic algorithm, Virtual network mapping

中图分类号:

TP393

王明, 庄雷, 王国卿, 张坤丽. 基于元胞遗传机制的虚拟网络映射算法[J]. 计算机科学, 2018, 45(12): 66-70. https://doi.org/10.11896／j.issn.1002-137X.2018.12.009

WANG Ming, ZHUANG Lei, WANG Guo-qing, ZHANG Kun-li. Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism[J]. Computer Science, 2018, 45(12): 66-70. https://doi.org/10.11896／j.issn.1002-137X.2018.12.009

参考文献

[1]INFÜHR J,RAIDL G.A memetic algorithm for the virtual network mapping problem[J].Journal of Heuristics,2016,22(4):475-505.
[2]FISCHER A,BOTERO J F,BECK M T,et al.Virtual network embedding:A survey[J].IEEE Communications Surveys & Tutorials,2013,15(4):1888-1906.
[3]CHOWDHURY N M M K,BOUTABA R.A survey of network virtualization[J].Computer Networks,2010,54(5):862-876.
[4]AMALDI E,CONIGLIO S,KOSTER A M C A,et al.On the computational complexity of the virtual network embedding problem[J].Electronic Notes in Discrete Mathematics,2016,52:213-220.
[5]HUANG B B,LIN R H,PENG K,et al.Load-balancing Basedon Particle Swarm Optimization in Virtual Network Mapping[J].Journal of Electronics & Information Technology,2013,35(7):1753-1759.(in Chinese)
黄彬彬,林荣恒,彭凯,等.基于粒子群优化的负载均衡的虚拟网络映射[J].电子与信息学报,2013,35(7):1753-1759.
[6]LIU X,ZHANG Z B,LI X M,et al.Optimal virtual network embedding based on artificial bee colony [J].Eurasip Journal on Wireless Communications & Networking,2016,2016(1):273.
[7]SUN G.Virtual network mapping technology research[D].Chengdu:University of Electronic Science and Technology,2012.(in Chinese)
孙罡.虚拟网络的映射技术研究[D].成都:电子科技大学,2012.
[8]WANG W Z,WANG B Q,WANG Z M,et al.Virtual network embedding algorithm based on a hybrid swarm intelligence optimization[J].Journal of Computer Applications,2014,34(4):930-934.(in Chinese)
王文钊,汪斌强,王志明,等.基于混合群智能优化的虚拟网络映射算法[J].计算机应用,2014,34(4):930-934.
[9]LIU J,SONG T,HU Y,et al.Research on Virtual NetworkMapping Based on Mixed Genetic Algorithm[J].Journal of Chinese Computer Systems,2016,37(4):773-777.(in Chinese)
刘佳,宋涛,胡颖,等.基于混合遗传算法的虚拟网络映射方法研究[J].小型微型计算机系统,2016,37(4):773-777.
[10]CISSÉ B,El YACOUBI S,GOURBIÉRE S.The basic reproduction number for Chagas disease transmission using cellular automata[C]∥International Conference on Cellular Automata.Springer,Cham,2014:278-287.
[11]BAKHSHANDEH A,ESLAMI Z.An authenticated image en-cryption scheme based on chaotic maps and memory cellular automata[J].Optics and Lasers in Engineering,2013,51(6):665-673.
[12]ZHENG B J,LI Y X,WU M C.A function optimization algorithm based on cellular automata[J].Computer Engineering,2003,29(19):66-67.(in Chinese)
郑波尽,李元香,吴漫川.细胞自动机函数优化算法[J].计算机工程,2003,29(19):66-67.
[13]WAS J,SIRAKOULIS G C.Special issue on Simulation with Cellular Automata[J].Simulation Transactions of the Society for Modeling & Simulation International,2016,92(2):99-100.
[14]ALBA E,DORONSORO B.The exploration/exploitation tra-deoff in dynamic cellular genetic algorithms[J].IEEE Transactions on Evolutionary Computation,2005,9(2):126-142.
[15]KARTHIKEYAN S,SARAVANAN M,RAJKUMAR M.Optimization of worker assignment in dynamic cellular manufactu-ring system using genetic algorithm[J].Journal of Advanced Manufacturing Systems,2016,15(1):35-42.
[16]KARI J.Cellular Automata and Discrete Complex System[J].Lecture Notes in Computer Science,2017,412(30):3798-3799.
[17]YU J J,WU C M.Randomized Algorithm for Virtual Network Mapping Problem Based on Load Balancing[J].Computer Scien-ce,2014,41(6):69-74.(in Chinese)
余建军,吴春明.基于负载均衡的虚拟网映射随机算法[J].计算机科学,2014,41(6):69-74.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[5]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[6]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[7]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[8]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[9]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[10]	朱国晖, 张茵, 刘秀霞, 孙天骜. 节点拓扑感知的高效节能虚拟网络映射算法 Energy Efficient Virtual Network Mapping Algorithms Based on Node Topology Awareness 计算机科学, 2020, 47(9): 270-274. https://doi.org/10.11896/jsjkx.190700162
[11]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[12]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[13]	梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[14]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[15]	史朝卫, 孟相如, 马志强, 韩晓阳. 拓扑综合评估与权值自适应的虚拟网络映射算法 Virtual Network Embedding Algorithm Based on Topology Comprehensive Evaluation and Weight Adaptation 计算机科学, 2020, 47(7): 236-242. https://doi.org/10.11896/jsjkx.190600022

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于元胞遗传机制的虚拟网络映射算法

Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0