MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略

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

通信学报 ›› 2020, Vol. 41 ›› Issue (4): 70-80.doi: 10.11959/j.issn.1000-436x.2020074

MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略

陈卓^1,²,冯钢²,刘怡静²,周杨³

¹ 重庆理工大学计算机科学与工程学院，重庆 200433
² 电子科技大学通信抗干扰技术国家级重点实验室，四川成都 710077
³ 奥本大学计算机科学与软件工程学院，奥本 36849

修回日期:2020-03-16 出版日期:2020-04-25 发布日期:2020-04-30
作者简介:陈卓（1980- ），男，重庆人，博士，重庆理工大学副教授、硕士生导师，主要研究方向为网络虚拟化、物联网应用及网络性能分析和评估|冯钢（1964- ），男，重庆人，博士，电子科技大学教授、博士生导师，主要研究方向为无线通信网络、网络虚拟化及网络资源分配|刘怡静（1994- ），女，四川成都人，电子科技大学硕士生，主要研究方向为无线电通信网络、网络虚拟化|周杨（1975- ），男，重庆人，博士，奥本大学助理教授、博士生导师，主要研究方向为最优算法、大数据技术
基金资助:
国家自然科学基金资助项目(61471089);国家自然科学基金资助项目(61401076);重庆市技术创新与应用发展基金资助项目(cstc2018jszx-cyztzx0088)

Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC

Zhuo CHEN^1,²,Gang FENG²,Yijing LIU²,Yang ZHOU³

¹ College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 200433,China
² National Key Laboratory of Science and Technology on Communications,University of Electronic Science and Technology of China,Chengdu 710077,China
³ Department of Computer Science and Software Engineering,Auburn University,Auburn 36849,USA

Revised:2020-03-16 Online:2020-04-25 Published:2020-04-30
Supported by:
The National Natural Science Foundation of China(61471089);The National Natural Science Foundation of China(61401076);The Technology Innovation and Application Development Project of Chongqing(cstc2018jszx-cyztzx0088)

摘要/Abstract

摘要：

为了有效改善多集群共存的移动边缘网络中业务流端到端服务时延，提出了一种基于改进遗传模拟退火算法的虚拟网络功能部署策略。通过开放 Jackson 排队网络对移动业务流的时延进行最优化建模，在证明其 NP性的基础上提出了将遗传算法与模拟退火算法相结合的求解策略，该策略通过对服务节点的提前映射机制避免了可能带来的网络拥塞，并通过个体的约束性判断和纠正遗传的方法避免了局部最优的出现。在不同的服务请求量、服务节点规模、集群数量及虚拟网络功能之间的逻辑连接关系等参数下的对比实验表明，该策略能提供更低时延的端到端服务，使时延敏感类移动业务获得更好体验。

关键词: 移动边缘计算, 虚拟网络功能, 服务时延, 遗传模拟退火算法

Abstract:

In order to effectively improve the end-to-end service delay of the flow in multi-clusters coexisting mobile edge computing (MEC) network,a virtual network function deployment strategy based on improved genetic simulated annealing algorithm was proposed.The delay of mobile service flow was mathematically modeled through the open Jackson queuing network.After proving the NP attribute of this problem,a solution combining genetic algorithm and simulated annealing algorithm was proposed.In this strategy,the advance mapping mechanism avoids the possibility of network congestion,and the occurrence of local optima was avoided through using the methods of individual judgment and corrective genetic.Extensive simulation was set up to evaluate the effectiveness of the proposed strategy under different parameter settings,such as different volume of requests,different scale of service nodes,different number of MEC clusters,and logical link relationships between virtual network functions.Results show that this strategy can provide lower end-to-end services delay and better service experience for latency-sensitive mobile application.

Key words: mobile edge computing, virtual network function, service delay, genetic simulated annealing algorithm

中图分类号:

TP393.0

陈卓,冯钢,刘怡静,周杨. MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略[J]. 通信学报, 2020, 41(4): 70-80.

Zhuo CHEN,Gang FENG,Yijing LIU,Yang ZHOU. Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC[J]. Journal on Communications, 2020, 41(4): 70-80.

图/表 8

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 26

[1]	LIU H , ELDARRAT F , ALQAHTANI H ,et al. Mobile edge cloud system:architectures,challenges,and approaches[J]. IEEE Systems Journal, 2018,12(3): 2495-2508.
[2]	ESSWIE A A , PEDERSEN K I . Opportunistic spatial preemptive scheduling for URLLC and eMBB coexistence in multi-user 5G networks[J]. IEEE Access, 2018(6): 38451-38463.
[3]	MACH P , BECVAR Z . Mobile edge computing:a survey on architecture and computation offloading[J]. IEEE Communications Surveys ＆Tutorials, 2017,19(3): 1628-1656.
[4]	CHATRAS B , OZOG F F . Network functions virtualization:the portability challenge[J]. IEEE Network, 2016,30(4): 4-8.
[5]	LEI L , XIONG X , HOU L ,et al. Collaborative edge caching through service function chaining:architecture and challenges[J]. IEEE Wireless Communications, 2018,25(3): 94-102.
[6]	HUANG H W , GUO S . Proactive failure recovery for NFV in distributed edge computing[J]. IEEE Communications Magazine, 2019,57(5): 131-137.
[7]	NAM Y , SONG S , CHUNG J M . Clustered NFV service chaining optimization in mobile edge clouds[J]. IEEE Communications Letters, 2017,21(2): 350-353.
[8]	GU S J , LI Z P , WU C ,et al. An efficient auction mechanism for service chains in the NFV market[C]// IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[9]	XU Z C , ZHANG X N , YU S ,et al. Energy-efficient virtual network function placement in telecom networks[C]// IEEE International Conference on Communications. Piscataway:IEEE Press, 2018: 1-7.
[10]	MA W , SANDOVAL O , BELTRAN J ,et al. Traffic aware placement of interdependent NFV middle-boxes[C]// IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2017: 1-9.
[11]	BHAMARE D , SAMAKA M , ERBAD A ,et al. Multi-objective scheduling of micro-services for optimal service function chains[C]// IEEE International Conference on Communications. Piscataway:IEEE Press, 2017: 1-6.
[12]	魏亮, 黄韬, 张娇 ,等. 基于强化学习的服务链映射算法[J]. 通信学报, 2018,39(1): 90-100.
	WEI L , HUANG T , ZHANG J ,et al. Service chain mapping algorithm based on reinforcement learning[J]. Journal on Communications, 2018,39(1): 90-100.
[13]	YOUSAF F Z , BREDEL M , SCHALLER S ,et al. NFV and SDN- key technology enablers for 5G networks[J]. IEEE Journal on Selected Areas in Communications, 2017,35(11): 2468-2478.
[14]	ZENG C , LIU F , CHEN S ,et al. Demystifying the performance interference of co-located virtual network functions[C]// IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2018: 765-773.
[15]	LIU Z , YANG M , DAI J . Performance improvement based on path delay analysis in WiMax mesh networks[C]// Proceedings of the Second International Conference on Communications and Networking in China. Piscataway:IEEE Press, 2007: 958-962.
[16]	KHINCHIN A Y , ANDREWS D M , QUENOUILLE M H . Mathematical methods in the theory of queuing[M]. North Chelmsford: Courier CorporationPress, 2013.
[17]	CHU P C , BEASLEY J E . A genetic algorithm for the multidimensional knapsack problem[J]. Journal of Heuristics, 1998,4(1): 63-86.
[18]	LIN C C , SHU L , DENG D J . Router node placement with service priority in wireless mesh networks using simulated annealing with momentum terms[J]. IEEE Systems Journal, 2016,10(4): 1402-1411.
[19]	HOU N , HE F Z , ZHOU Y ,et al. A parallel genetic algorithm with dispersion correction for HW/SW partitioning on multi-core CPU and many-core GPU[J]. IEEE Access, 2017(6): 883-898.
[20]	YANG L Y , DENG Y H , YANG L T ,et al. Reducing the cooling power of data centers by intelligently assigning tasks[J]. IEEE Transactions on Automation Science and Engineering, 2018,5(3): 1667-1678.
[21]	孟凡超, 初佃辉, 李克秋 ,等. 基于混合遗传模拟退火算法的SaaS构件优化放置[J]. 软件学报, 2016,27(4): 916-932.
	MENG F C , CHU D H , LI K Q ,et al. Solving SaaS components optimization placement problem with hybird genetic and simulated annealing algorithm[J]. Journal of Software, 2016,27(4): 916-932.
[22]	JIA Y , WU C , LI Z ,et al. Online scaling of NFV service chains across geo-distributed datacenters[J]. IEEE/ACM Transactions on Networking (TON), 2018,26(2): 699-710.
[23]	JIA Y , WU C , LI Z ,et al. Online scaling of NFV service chains across geo-distributed datacenters[J]. IEEE/ACM Transactions on Networking, 2018,26(2): 699-710.
[24]	LI X , QIAN C . Low-complexity multi-resource packet scheduling for network function virtualization[C]// IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2015: 1400-1408.
[25]	XIA M , SHIRAZIPOUR M , ZHANG Y ,et al. Network function placement for NFV chaining in packet/optical datacenters[J]. Journal of Lightwave Technology, 2015,33(8): 1565-1570.
[26]	SUN C , BI J , ZHENG Z L ,et al. NFP:enabling network function parallelism in NFV[C]// The Conference of the ACM Special Interest Group on Data Communication. New York :ACM Press, 2017: 43-56.

MEC中基于改进遗传模拟退火算法的虚拟网络功能部署策略

Virtual network function deployment strategy based on improved genetic simulated annealing algorithm in MEC

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 26

相关文章 15

Metrics

推荐阅读 0

[1]	苏新, 张桂福, 行鸿彦, Zenghui Wang. 基于平衡生成对抗网络的海洋气象传感网入侵检测研究[J]. 通信学报, 2023, 44(4): 124-136.
[2]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[3]	范伟, 彭诚, 朱大立, 王雨晴. 移动边缘计算网络下基于静态贝叶斯博弈的入侵响应策略研究[J]. 通信学报, 2023, 44(2): 70-81.
[4]	赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.
[5]	龙隆, 刘子辰, 陆在旺, 张玉成, 李蕾. 移动边缘网络下服务缓存与资源分配联合优化策略[J]. 通信学报, 2023, 44(1): 64-74.
[6]	徐泽汐, 庄雷, 张坤丽, 桂明宇. 基于知识图谱的服务功能链在线部署算法[J]. 通信学报, 2022, 43(8): 41-51.
[7]	兰巨龙, 朱棣, 李丹. 面向多模态网络业务切片的虚拟网络功能资源容量智能预测方法[J]. 通信学报, 2022, 43(6): 143-155.
[8]	邱航, 汤红波, 游伟, 赵宇, 柏溢. NFV中基于量子遗传算法的网络服务扩展算法[J]. 通信学报, 2022, 43(11): 44-52.
[9]	李斌, 刘文帅, 谢万城, 费泽松. 智能反射面赋能无人机边缘网络计算卸载方案[J]. 通信学报, 2022, 43(10): 223-233.
[10]	黄永明, 郑冲, 张征明, 尤肖虎. 大规模无线通信网络移动边缘计算和缓存研究[J]. 通信学报, 2021, 42(4): 44-61.
[11]	李方伟, 张海波, 王子心. 车联网中基于MEC的V2X协同缓存和资源分配[J]. 通信学报, 2021, 42(2): 26-36.
[12]	王娜,郑坤,付俊松,李剑. 基于分块的移动边缘计算密文检索方法[J]. 通信学报, 2020, 41(7): 95-102.
[13]	亓晋,孙海蓉,巩锟,许斌,张顺颐,孙雁飞. 移动边缘计算中基于信誉值的智能计算卸载模型研究[J]. 通信学报, 2020, 41(7): 141-151.
[14]	吴大鹏,吕吉,李职杜,王汝言. 移动性感知的边缘服务迁移策略[J]. 通信学报, 2020, 41(4): 1-13.
[15]	张海君,张资政,隆克平. 基于移动边缘计算的NOMA异构网络资源分配[J]. 通信学报, 2020, 41(4): 27-33.