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

Virtual Network Mapping Algorithm Based on Cellular Genetic Mechanism

作　　者：王明 庄雷[1] 王国卿[1] 张坤丽[1] WANG Ming;ZHUANG Lei;WANG Guo-qing;ZHANG Kun-li(School of Information Engineering,Zhengzhou University,Zhengzhou 450000,China)

机构地区：[1]郑州大学信息工程学院,郑州450000

出　　处：《计算机科学》2018年第12期66-70,103,共6页Computer Science

基　　金：国家973计划(2012CB315901);国家自然科学基金(61379079)资助

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]