Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (3): 755-759.DOI: 10.11772/j.issn.1001-9081.2017.03.755

Previous Articles     Next Articles

Virtual network embedding algorithm based on multi-objective particle swarm optimization

LI Zhen1,2, ZHENG Xiangwei1,2, ZHANG Hui1,2   

  1. 1. College of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250000, China;
    2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan Shandong 250014, China
  • Received:2016-08-31 Revised:2016-11-01 Online:2017-03-10 Published:2017-03-22
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61373149).

基于多目标粒子群优化的虚拟网络映射算法

李贞1,2, 郑向伟1,2, 张辉1,2   

  1. 1. 山东师范大学 信息科学与工程学院, 济南 250000;
    2. 山东省分布式计算机软件新技术重点实验室, 济南 250014
  • 通讯作者: 郑向伟
  • 作者简介:李贞(1991-),女,山东济南人,硕士研究生,CCF会员,主要研究方向:云计算、网络虚拟化;郑向伟(1971-),男,山东泰安人,教授,博士,CCF会员,主要研究方向:计算智能、云计算;张辉(1991-),男,山东潍坊人,硕士研究生,CCF会员,主要研究方向:云计算、网络虚拟化。
  • 基金资助:
    国家自然科学基金资助项目(61373149)。

Abstract: In virtual network mapping, most studies only consider one mapping object, which can not reflect the interests of many aspects. To solve this problem, a Virtual Network Embedding algorithm based on Multi-objective Particle Swarm Optimization (VNE-MOPSO) was proposed by combining multi-objective algorithm and Particle Swarm Optimization (PSO) algorithm. Firstly, the crossover operator was introduced into the basic PSO algorithm to expand the search space of population optimization. Secondly, the non-dominated sorting and crowding distance sorting were introduced into the multi-objective optimization algorithm, which can speed up the population convergence. Finally, by minimizing both the cost and the node load balance degree as the virtual network mapping objective function, a multi-objective PSO algorithm was proposed to solve the Virtual Network Mapping Problem (VNMP). The experimental results show that the proposed algorithm can solve the VNMP, which has advantages in network request acceptance rate, average cost, average node load balance degree, and infrastructure provider's profit.

Key words: virtual network mapping, multi-objective optimization algorithm, Particle Swarm Optimization (PSO) algorithm, non-dominated sorting, crowding distance sorting, crossover operator

摘要: 在虚拟网络映射中,多数研究只考虑一个映射目标,不能体现多方的利益。为此,将多目标算法和粒子群算法结合,提出了一种基于多目标粒子群优化(PSO)的虚拟网络映射算法(VNE-MOPSO)。首先,在基本的粒子群算法中引入交叉算子,扩大了种群优化的搜索空间;其次,在多目标优化算法中引入非支配排序、拥挤距离排序,从而加快种群的收敛;最后,以同时最小化成本和节点负载均衡度为虚拟网络映射目标函数,采用多目标粒子群优化算法求解虚拟网络映射问题(VNMP)。实验结果表明,采用该算法求解虚拟网络映射问题,在网络请求接受率、平均成本、平均节点负载均衡度、基础设施提供商的收益等方面具有优势。

关键词: 虚拟网络映射, 多目标优化算法, 粒子群优化算法, 非支配排序, 拥挤距离排序, 交叉算子

CLC Number: