朱强，王慧强，吕宏武，王振东

（哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）

1 引言

云计算环境追求以较低的成本提供可伸缩的多样性服务，而网络虚拟化是目前实现该目标最有效的技术手段[1～3]。网络虚拟化允许在共享底层网络资源的基础之上建立多个独立、异构的虚拟网络，使服务提供商（SP, service provider）能够依据用户需求提供可定制的个性化服务。虚拟网络请求中节点和链路通常带有约束条件。依据基础设施提供商（InP, infrastructure provider）当前资源情况，通过映射算法在虚拟网络构建需求与底层网络资源之间进行匹配，为虚拟网络请求分配合理的底层节点和链路资源被称为虚拟网络映射，它是一个NP-hard问题[4]。虚拟网络映射问题通常采用基于启发式算法的方法求解，然而为了降低映射的难度和提高启发式算法的效率，已有的成果通常对映射问题的空间进行诸多限制：1）假设底层节点资源和链路资源是无限的[5,6]；2）底层网络需要支持路径分割[7]；3）映射算法评估指标不完善[8]；4）忽略虚拟网络节点对位置的需求[9,10]等。同时映射求解过程还存在过于复杂和开销大的问题。

针对上述问题，本文在底层网络资源有限和不支持路径分割的前提下，提出了一种基于人工鱼群的网络虚拟化映射算法，利用虚拟网络请求对底层网络节点和链路的约束关系建立二进制组合优化模型，并通过人工鱼群算法对底层网络资源进行近似最优化映射，有效地降低底层网络开销和求解时间，提高虚拟网络映射的成功率、平均收益和资源平均利用率。……