基于离散粒子群优化的多目标服务路径构建算法

doi:10.11959/j.issn.1000-436x.2017032

通信学报 ›› 2017, Vol. 38 ›› Issue (2): 94-105.doi: 10.11959/j.issn.1000-436x.2017032

基于离散粒子群优化的多目标服务路径构建算法

马丁^1,²,庄雷¹,兰巨龙³

¹ 郑州大学信息工程学院，河南郑州 450001
² 河南工业大学信息科学与工程学院，河南郑州 450001
³ 国家数字交换系统工程技术研究中心，河南郑州 450002

修回日期:2016-12-23 出版日期:2017-02-01 发布日期:2017-07-20
作者简介:马丁（1978-），男，回族，河南夏邑人，郑州大学博士生，主要研究方向为新型网络体系结构、路由与交换技术等。|庄雷（1963-），女，山东日照人，郑州大学教授、博士生导师，主要研究方向为未来互联网体系结构、网络虚拟化等。|兰巨龙（1962-），男，河北张北人，国家数字交换系统工程技术研究中心总工程师、教授、博士生导师，主要研究方向为新一代信息网络关键理论与技术。
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目(2012CB315901);国家自然科学基金资助项目(61379079);河南省国际合作基金资助项目(152102410021)

Discrete particle swarm optimization based multi-objective service path constructing algorithm

Ding MA^1,²,Lei ZHUANG¹,Ju-long LAN³

¹ School of Information and Engineering,Zhengzhou University,Zhengzhou 450001,China
² College of Information Science and Engineering,Henan University of Technology,Zhengzhou 450001,China
³ China National Digital Switching System Engineering ＆Technological Research Center,Zhengzhou 450002,China

Revised:2016-12-23 Online:2017-02-01 Published:2017-07-20
Supported by:
The National Basic Research Program of China (973 Program)(2012CB315901);The National Natural Science Foundation of China(61379079);The International Cooperation Program of Henan(152102410021)

摘要/Abstract

摘要：

针对当前关于服务路径构建问题的研究主要围绕单一优化目标，构建时延最小、开销最低或负载均衡的服务路径，忽略了服务路径的综合质量，提出了一种基于离散粒子群优化的多目标服务路径构建算法(MOPSO)。为了提高收敛速度，优化算法的性能，进一步研究了候选节点和路径的评价标准，提出一种粒子位置初始化和更新策略(PIFC)。仿真实验表明，与已有算法相比，所提出的算法有效地优化了服务路径的质量，提高了服务路径的构建成功率和长期平均收益。

关键词: 网络功能虚拟化, 服务链, 服务路径, 多目标, 粒子群优化

Abstract:

Aiming at previous research primarily focused on constructing service paths with a single objective,for exam-ple,latency minimization,cost minimization or load balance,which ignored the overall performance of constructed ser-vice paths,a multi-objective service path constructing algorithm based on discrete particle swarm optimization (MOPSO) was proposed.To promote the convergence rate and improve constructing performance,the criterions for selecting can-didate physical nodes and paths were explored,and a particle position initialization and update strategy (PIFC) was de-signed.Simulation experiments show that the proposed algorithms can improve the overall quality of service paths and increase the success rate and long-term average revenue.

Key words: network function virtualization, service chain, service path, multi-objective, particle swarm optimization

中图分类号:

TP393

马丁,庄雷,兰巨龙. 基于离散粒子群优化的多目标服务路径构建算法[J]. 通信学报, 2017, 38(2): 94-105.

Ding MA,Lei ZHUANG,Ju-long LAN. Discrete particle swarm optimization based multi-objective service path constructing algorithm[J]. Journal on Communications, 2017, 38(2): 94-105.

图/表 13

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

参考文献 24

[1]	CHIOSI M , DON C , PETER W ,et al. Network functions virtualisation:an introduction,benefits,enablers,challenges and call for action[C]// SDN and OpenFlow World Congress Darmstadt,Germany:ESTI, 2012: 22-24.
[2]	MCKEOWN N , ANDERSON T , BALAKRISHNAN H ,et al. OpenFlow:enabling innovation in campus networks[J]. ACM Sigcomm Computer Communication Review, 2008,38(2): 69-74.
[3]	XIA W , WEN Y , FOH C H ,et al. A survey on software-defined networking[J]. IEEE Communications Surveys ＆ Tutorials, 2015,17(1): 27-51.
[4]	SAHHAF S , TAVERNIER W , COLLE D ,et al. Network service chaining with efficient network function mapping based on service decompositions[C]// 2015 1st IEEE Conference on Network Softwarization (NetSoft 2015). 2015: 1-5.
[5]	SAHHAF S , TAVERNIER W , ROST M ,et al. Network service chaining with optimized network function embedding supporting service decompositions[J]. Computer Networks, 2015,93(P3): 492-505.
[6]	HUANG X , GANAPATHY S , WOLF T . Evaluating algorithms for composable service placement in computer networks[C]// International Conference on Communications (ICCC 2009). 2009: 1-6.
[7]	CHOI S , TURNER J , WOLF T . Configuring sessions in programmable networks[J]. Computer Networks, 2003,41(2): 269-284.
[8]	RAMAN B , KATZ R H . Load balancing and stability issues in algorithms for service composition[C]// 22nd Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003). 2003: 1477-1487.
[9]	BARI M F , CHOWDHURY S R , AHMED R ,et al. On orchestrating virtual network functions[C]// 11th International Conference on Network and Service Management (CNSM 2015). 2015: 50-56.
[10]	DIETRICH D , ABUJODA A , PAPADIMITRIOU P . Network service embedding across multiple providers with nestor[C]// IFIP Networking Conference (Network-ing 2015). 2015: 1-9.
[11]	段通, 兰巨龙, 程国振 ,等. 基于元能力的 SDN 功能组合机制[J]. 通信学报, 2015,36(5): 156-166.
	DUAN T , LAN J L , CHENG G Z ,et al. Functional composition in software-defined network based on atomic capacity[J]. Journal on Communications, 2015,36(5): 156-166.
[12]	HU Y X , LI Y F , XING C Q ,et al. Providing customized security based on network function composition and reconfiguration[J]. China Communications, 2016,13(z1): 177-189.
[13]	YU M L , YI Y , REXFORD J ,et al. Rethinking virtual network embedding:substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2): 17-29.
[14]	CHOWDHURY N M K , RAHMAN M R , BOUTABA R . Vineyard:virtual network embedding algorithms with coordinated node and link mapping[J]. IEEE/ACM Transactions on Networking, 2012,20(1): 206-219.
[15]	CHENG X , SU S , ZHANG Z ,et al. Virtual network embedding through topology awareness and optimization[J]. Computer Networks, 2012,56(6): 1797-1813.
[16]	FISCHER A , BOTERO J F , BECK M T ,et al. Virtual network embedding:a survey[J]. IEEE Communications Surveys ＆ Tutorials, 2013,15(4): 1888-1906.
[17]	YANG Y , CHANG X L , LIU J ,et al. Towards robust green virtual cloud data center provisioning[J]. IEEE Transactions on Cloud Computing, 2015: 1-14.
[18]	BARI M F , BOUTABA R , ESTEVES R ,et al. Data center network virtualization:a survey[J]. IEEE Communications Surveys ＆ Tutorials, 2013,15(2): 909-928.
[19]	KENNEDY J , EBERHART R C . Particle swarm optimization[C]// International Conference on Neural Networks. 1995: 1942-1948.
[20]	EBERHART R C , SHI Y . Particle swarm optimization:Development,applications and resources[C]// The 2001 Congress on Evolutionary Computation. 2001: 81-86.
[21]	TAO F , ZHAO D , HU Y ,et al. Resource service composition and its optimal-selection based on particle swarm optimization in manufacturing grid system[J]. IEEE Transactions on Industrial Informatics, 2008,4(4): 315-327.
[22]	ZHAO X , SONG B , HUANG P ,et al. An improved discrete immune optimization algorithm based on PSO for QoS-driven web service composition[J]. Applied Soft Computing, 2012,12(8): 2208-2216.
[23]	ZEGURA E W , KENNETH L C , SAMRAT B . How to model an internetwork[C]// 15th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 1996). 1996: 594-602.
[24]	DOBRESCU M , ARGYRAKI K , RATNASAMY S . Toward predictable performance in software packet-processing platforms[C]// USENIX Symposium on Networked Systems Design and Implementation (NSDI 2012). 2012: 141-154.

基于离散粒子群优化的多目标服务路径构建算法

Discrete particle swarm optimization based multi-objective service path constructing algorithm

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 24

相关文章 15

Metrics

推荐阅读 0

[1]	赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.
[2]	陈浩, 杨芫, 徐明伟, 裴丹, 尤艺霖. 支持多模态网络的可扩展异构服务功能链并行编排部署系统[J]. 通信学报, 2022, 43(9): 1-11.
[3]	徐泽汐, 庄雷, 张坤丽, 桂明宇. 基于知识图谱的服务功能链在线部署算法[J]. 通信学报, 2022, 43(8): 41-51.
[4]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.
[5]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[6]	杨力, 潘成胜, 孔相广, 黄琦龙, 戚耀文. 5G融合卫星网络研究综述[J]. 通信学报, 2022, 43(4): 202-215.
[7]	曹阳, 钟烨, 彭醇陵, 彭小峰. 基于混合供能和能量协作的异构网络能量效率优化算法[J]. 通信学报, 2022, 43(3): 135-147.
[8]	毛伊敏, 甘德瑾, 廖列法, 陈志刚. 基于Spark框架和ASPSO的并行划分聚类算法[J]. 通信学报, 2022, 43(3): 148-163.
[9]	邱航, 汤红波, 游伟, 赵宇, 柏溢. NFV中基于量子遗传算法的网络服务扩展算法[J]. 通信学报, 2022, 43(11): 44-52.
[10]	苏新, 薛淏阳, 周一青, 朱金秀. 面向海洋观监测传感网的计算卸载方法研究[J]. 通信学报, 2021, 42(5): 149-163.
[11]	孙爱晶, 李世昌, 张艺才. 基于PSO优化模糊C均值的WSN分簇路由算法[J]. 通信学报, 2021, 42(3): 91-99.
[12]	黄小红, 张勇, 闪德胜, 钱叶魁, 韩璐, 李丹丹, 丛群. 基于多目标效用优化的分布式数据交易算法[J]. 通信学报, 2021, 42(2): 52-63.
[13]	王泽南, 张娇, 汪硕, 黄韬, F.RichardYu. 端到端时延上限确定的服务链部署算法[J]. 通信学报, 2021, 42(11): 66-78.
[14]	诸天逸,李凤华,金伟,郭云川,房梁,成林. 互操作性与自治性平衡的跨域访问控制策略映射[J]. 通信学报, 2020, 41(9): 29-48.
[15]	张沛,刘帅军,马治国,王晓晖,宋俊德. 基于深度增强学习和多目标优化改进的卫星资源分配算法[J]. 通信学报, 2020, 41(6): 51-60.