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

摘要：

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

关键词：离线虚拟网映射、贪婪算法、禁忌遗传算法、NP难问题

所属期刊栏目：46

分类号：TP393(计算技术、计算机技术)

资助基金：浙江省自然科学基金资助项目LY14F020010;国家863高技术研究发展计划项目2015AA015602,2015AA016013

在线出版日期：2020-01-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：114-119