Computer Science ›› 2018, Vol. 45 ›› Issue (12): 66-70.doi: 10.11896/j.issn.1002-137X.2018.12.009

• Network & Communication • Previous Articles     Next Articles

Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism

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

  1. (School of Information Engineering,Zhengzhou University,Zhengzhou 450000,China)
  • Received:2017-11-03 Online:2018-12-15 Published:2019-02-25

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

CLC Number: 

  • TP393
[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.
[1] YANG Hao-xiong, GAO Jing, SHAO En-lu. Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery [J]. Computer Science, 2022, 49(6A): 191-198.
[2] SHEN Biao, SHEN Li-wei, LI Yi. Dynamic Task Scheduling Method for Space Crowdsourcing [J]. Computer Science, 2022, 49(2): 231-240.
[3] WU Shan-jie, WANG Xin. Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks [J]. Computer Science, 2021, 48(7): 308-315.
[4] WANG Jin-heng, SHAN Zhi-long, TAN Han-song, WANG Yu-lin. Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network [J]. Computer Science, 2021, 48(6): 338-342.
[5] ZHENG Zeng-qian, WANG Kun, ZHAO Tao, JIANG Wei, MENG Li-min. Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster [J]. Computer Science, 2021, 48(6): 261-267.
[6] ZUO Jian-kai, WU Jie-hong, CHEN Jia-tong, LIU Ze-yuan, LI Zhong-zhi. Study on Heterogeneous UAV Formation Defense and Evaluation Strategy [J]. Computer Science, 2021, 48(2): 55-63.
[7] YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing. PSO-GA Based Approach to Multi-edge Load Balancing [J]. Computer Science, 2021, 48(11A): 456-463.
[8] GAO Shuai, XIA Liang-bin, SHENG Liang, DU Hong-liang, YUAN Yuan, HAN He-tong. Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm [J]. Computer Science, 2021, 48(11A): 166-169.
[9] GAO Ji-xu, WANG Jun. Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm [J]. Computer Science, 2021, 48(1): 72-80.
[10] JI Shun-hui, ZHANG Peng-cheng. Test Case Generation Approach for Data Flow Based on Dominance Relations [J]. Computer Science, 2020, 47(9): 40-46.
[11] DONG Ming-gang, HUANG Yu-yang, JING Chao. K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection [J]. Computer Science, 2020, 47(8): 178-184.
[12] LIANG Zheng-you, HE Jing-lin, SUN Yu. Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition [J]. Computer Science, 2020, 47(8): 227-232.
[13] YANG De-cheng, LI Feng-qi, WANG Yi, WANG Sheng-fa, YIN Hui-shu. Intelligent 3D Printing Path Planning Algorithm [J]. Computer Science, 2020, 47(8): 267-271.
[14] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[15] YAO Min. Multi-population Genetic Algorithm for Multi-skill Resource-constrained ProJect Scheduling Problem [J]. Computer Science, 2020, 47(6A): 124-129.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!