基于禁忌遗传优化的离线静态虚拟网映射算法

Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization

离线静态虚拟网映射问题是NP难问题,其任务是以物理网提供商收益最大化为目标,在物理网上完成虚拟网子集的映射。文中对离线静态虚拟网映射问题及其研究现状进行介绍,指出当前离线静态虚拟网映射算法仅适用于小规模问题或特殊问题的求解,进而提出了一种适用于中大规模的一般离线静态虚拟网映射问题的求解算法。首先,基于收益优先的虚拟网映射顺序策略、节点等级匹配的虚拟节点映射策略以及最小化资源消耗量的虚拟链路映射策略,提出离线静态虚拟网映射问题的贪婪算法;然后,基于遗传算法和禁忌搜索混合的优化策略,提出离线静态虚拟网映射问题的禁忌遗传算法。实验表明,所提出的禁忌遗传算法具有较高的虚拟网构建完成率和物理网提供商收益,虚拟网构建完成率和物理网提供商收益分别比基线算法提高了34%和42%。

The offline static virtual network mapping problem is an NP-hard problem.It is to map the subset of virtual networks onto the physical network aimed to maximize the profit of physical network provider.This paper reviewed the offline static virtual network mapping problem and the current research progress for this problem and pointed out that the current offline static virtual network mapping algorithm is only suitable for solving small-scale problems or special problems.Therefore,this paper proposed a general offline static virtual network mapping algorithm suitable for solving medium and large scale.The virtual network mapping order strategy based on revenue priority,the virtual node mapping strategy by node rank matching and the virtual link mapping strategy that minimizes resource consumption are used to complete the greedy algorithm design for offline static virtual network mapping problem.Then,the optimization strategy based on the hybrid algorithm of genetic algorithm and tabu search are used to complete the tabu search genetic algorithm design for offline static virtual network mapping problem.Experiments show that the proposed algorithm has higher virtual network construction completion rate and gets better physical network provider revenue,and the virtual network construction completion rate and physical network provider revenue are 34%and 42%higher than the baseline algorithm,respectively.