基于次模优化的边云协同多用户计算任务迁移方法

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

通信学报 ›› 2020, Vol. 41 ›› Issue (10): 25-36.doi: 10.11959/j.issn.1000-436x.2020205

• 专题：面向万物互联的通信与计算融合 • 上一篇下一篇

基于次模优化的边云协同多用户计算任务迁移方法

梁冰^1,^2,³,纪雯^1,^3,⁴()

¹ 中国科学院计算技术研究所，北京 100190
² 中国科学院大学计算机科学与技术学院，北京 100190
³ 移动计算与新型终端北京市重点实验室，北京 100190
⁴ 鹏城实验室，广东深圳 518055

修回日期:2020-09-03 出版日期:2020-10-25 发布日期:2020-11-05
作者简介:梁冰（1992- ），男，河北保定人，中国科学院计算技术研究所博士生，主要研究方向为多媒体通信与网络、视频传输、边缘计算、机器学习等|纪雯（1976- ），女，陕西西安人，博士，中国科学院计算技术研究所研究员、博士生导师，主要研究方向为多媒体通信与网络，包括视频传输和编码、优化理论和信息论、边缘计算、多媒体经济学和智能计算等
基金资助:
国家重点研发计划基金资助项目(2017YFB1400100);国家自然科学基金资助项目(62072440);北京市自然科学基金资助项目(4202072)

Multiuser computation offloading for edge-cloud collaboration using submodular optimization

Bing LIANG^1,^2,³,Wen JI^1,^3,⁴()

¹ Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China
² School of Computer Science and Technology,University of Chinese Academy of Sciences,Beijing 100190,China
³ Beijing Key Laboratory of Mobile Computing and Pervasive Device,Beijing 100190,China
⁴ Peng Cheng Laboratory,Shenzhen 518055,China

Revised:2020-09-03 Online:2020-10-25 Published:2020-11-05
Supported by:
The National Key Research and Development Program of China(2017YFB1400100);The National Natural Science Foundation of China(62072440);The Beijing Natural Science Foundation(4202072)

摘要/Abstract

摘要：

为了提升多用户计算任务卸载时的系统效用，提出了一种基于边云联合计算的多用户任务卸载方案。该方案在提升系统效用的同时，考虑了边云资源的协同优化问题。针对计算任务卸载模式的选择及边云资源分配的问题，设计了一种基于次模理论的贪心算法并充分利用了云端以及边缘端的计算和通信资源。仿真结果表明，所提方案能够有效降低计算任务执行的时延和能耗，且当多用户卸载计算任务时，所提方案在资源受限的条件下仍然能够保持稳定的系统性能。

关键词: 云计算, 边缘计算, 多用户计算卸载, 次模优化, 边云联合计算

Abstract:

A computation offloading scheme based on edge-cloud computing was proposed to improve the system utility of multiuser computation offloading.This scheme improved the system utility while considering the optimization of edge-cloud resources.In order to tackle the problems of computation offloading mode selection and edge-cloud resource allocation,a greedy algorithm based on submodular theory was developed by fully exploiting the computing and communication resources of cloud and edge.The simulation results demonstrate that the proposed scheme effectively reduces the delay and energy consumption of computing tasks.Additionally,when computing tasks are offloaded to edge and cloud from devices,the proposed scheme still maintains stable system utilities under ultra-limited resources.

Key words: cloud computing, edge computing, multiuser computation offloading, submodular optimization, edge-cloud computing

中图分类号:

TN92

梁冰,纪雯. 基于次模优化的边云协同多用户计算任务迁移方法[J]. 通信学报, 2020, 41(10): 25-36.

Bing LIANG,Wen JI. Multiuser computation offloading for edge-cloud collaboration using submodular optimization[J]. Journal on Communications, 2020, 41(10): 25-36.

图/表 6

图1

表1

仿真参数设置"

参数名称	取值
系统带宽B/MHz	20
路径损失模型	128.1+37.5lg10(d)
背景噪声 $σ_{0}^{2} / d B m$	-100
对数正态阴影衰落标准差/dB	10
边缘计算资源 f^e/GHz	20
云端分配给用户的计算资源 $f_{u}^{c} / G H z$	5

表1

图2

图3

图4

图5

参考文献 45

[1]	SHI W , CAO J , ZHANG Q ,et al. Edge computing:vision and challenges[J]. IEEE Internet of Things Journal, 2016,3(5): 637-646.
[2]	Cisco. Cisco annual internet report(2018–2023)white paper[R].(2020-03-09)[2020-07-16].
[3]	PULIAFITO C , MINGOZZI E , LONGO F ,et al. Fog computing for the Internet of things:a survey[J]. ACM Transactions on Internet Technology, 2019,19(2): 1-41.
[4]	CHEN X , JIAO L , LI W ,et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking, 2016,24(5): 2795-2808.
[5]	CHEN W , WANG D , LI K . Multi-user multi-task computation offloading in green mobile edge cloud computing[J]. IEEE Transactions on Services Computing, 2018,12(5): 726-738.
[6]	PATEL M , NAUGHTON B , CHAN C ,et al. Mobile-edge computing introductory technical white paper[R]. Mobile-Edge Computing (MEC) Industry Initiative,(2018-09-14)[2020-07-16].
[7]	ETSI. ETSI first meeting of new standardization group on mobile-edge-computing[R].(2014)[ 2020-07-16].
[8]	PLACHY J , BECVAR Z , STRINATI E C . Dynamic resource allocation exploiting mobility prediction in mobile edge computing[C]// 2016 IEEE 27th Annual International Symposium on Personal,Indoor,and Mobile Radio Communications (PIMRC). Piscataway:IEEE Press, 2016: 1-6.
[9]	JI W , LIANG B , WANG Y ,et al. Crowd V-IoE:visual Internet of everything architecture in AI-driven fog computing[J]. IEEE Wireless Communications, 2020,27(2): 51-57.
[10]	ABBAS N , ZHANG Y , TAHERKORDI A ,et al. Mobile edge computing:a survey[J]. IEEE Internet of Things Journal, 2017,5(1): 450-465.
[11]	JI W , DUAN L Y , HUANG X ,et al. Astute video transmission for geographically dispersed devices in visual IoT systems[J]. IEEE Transactions on Mobile Computing,DOI:10.1109/TMC.2020.3009745, 2020
[12]	董思岐, 李海龙, 屈毓锛 ,等. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学, 2019,46(11): 32-40.
	DONG S Q , LI H L , QU Y B ,et al. Survey of research on computation unloading strategy in mobile edge computing[J]. Computer Science, 2019,46(11): 32-40.
[13]	吴大鹏, 吕吉, 李职杜 ,等. 移动性感知的边缘服务迁移策略[J]. 通信学报, 2020,41(4): 1-13.
	WU D P , LYU J , LI Z D ,et al. Mobility aware edge service migration strategy[J]. Journal on Communications, 2020,41(4): 1-13.
[14]	ZHANG J , HU X , NING Z ,et al. Joint resource allocation for latency-sensitive services over mobile edge computing networks with caching[J]. IEEE Internet of Things Journal, 2018,6(3): 4283-4294.
[15]	满君丰, 赵龙乾, 彭成 ,等. 云边协同计算架构下大规模工厂接入的任务调度方法[J]. 计算机集成制造系统,(2020-05-06)[2020-07-16].
	MAN J F , ZHAO L Q , PENG C ,et al. Task scheduling method for large-scale factory access in cloud and edge collaborative computing architecture[J]. Computer Integrated Manufacturing Systems,(2020-05-06)[2020-07-16].
[16]	汤闻达 . 支持云雾端应用集成的资源调度策略及其优化技术[D]. 南京:南京大学, 2019.
	TANG W D . Resource scheduling strategies and optimization techniques supporting cloud-fog-thing integration[D]. Nanjing:Nanjing University, 2019.
[17]	CUI Y , ZHANG D , ZHANG T ,et al. Novel method of mobile edge computation offloading based on evolutionary game strategy for IoT devices[J]. AEU-International Journal of Electronics and Communications, 2020:153134.
[18]	WANG Y , LANG P , TIAN D ,et al. A game-based computation offloading method in vehicular multi-access edge computing networks[J]. IEEE Internet of Things Journal, 2020,7(6): 4987-4996.
[19]	CARDELLINI V , PERSONé V D N , DI VALERIO V ,et al. A game-theoretic approach to computation offloading in mobile cloud computing[J]. Mathematical Programming, 2016,157(2): 421-449.
[20]	ZHENG J , CAI Y , WU Y ,et al. Dynamic computation offloading for mobile cloud computing:a stochastic game-theoretic approach[J]. IEEE Transactions on Mobile Computing, 2018,18(4): 771-786.
[21]	赵临东, 庄文芹, 陈建新 ,等. 异构蜂窝网络中分层任务卸载:建模与优化[J]. 通信学报, 2020,41(4): 34-44.
	ZHAO L D , ZHUANG W Q , CHEN J X ,et al. Hierarchical task offloading in heterogeneous cellular network:modeling and optimization[J]. Journal on Communications, 2020,41(4): 34-44.
[22]	YANG X , YU X , HUANG H ,et al. Energy efficiency based joint computation offloading and resource allocation in multi-access MEC systems[J]. IEEE Access, 2019,7: 117054-117062.
[23]	SALEEM U , LIU Y , JANGSHER S ,et al. Latency minimization for D2D-enabled partial computation offloading in mobile edge computing[J]. IEEE Transactions on Vehicular Technology, 2020,69(4): 4472-4486.
[24]	CHEN M H , LIANG B , DONG M . Joint offloading and resource allocation for computation and communication in mobile cloud with computing access point[C]// IEEE INFOCOM 2017-IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2017: 1-9.
[25]	LONG L , LIU Z , ZHOU Y ,et al. Delay optimized computation offloading and resource allocation for mobile edge computing[C]// 2019 IEEE 90th Vehicular Technology Conference. Piscataway:IEEE Press, 2019: 1-5.
[26]	CHEN S , ZHENG Y , WANG K ,et al. Delay guaranteed energy-efficient computation offloading for industrial IoT in fog computing[C]// 2019 IEEE International Conference on Communications. Piscataway:IEEE Press, 2019: 1-6.
[27]	ZHAO P , TIAN H , QIN C ,et al. Energy-saving offloading by jointly allocating radio and computational resources for mobile edge computing[J]. IEEE Access, 2017,5: 11255-11268.
[28]	ZHANG K , MAO Y , LENG S ,et al. Energy-efficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access, 2016,4: 5896-5907.
[29]	LYU X , TIAN H , SENGUL C ,et al. Multiuser joint task offloading and resource optimization in proximate clouds[J]. IEEE Transactions on Vehicular Technology, 2016,66(4): 3435-3447.
[30]	TRAN T X , POMPILI D . Joint task offloading and resource allocation for multi-server mobile-edge computing networks[J]. IEEE Transactions on Vehicular Technology, 2018,68(1): 856-868.
[31]	ZHANG J , XIA W , YAN F ,et al. Joint computation offloading and resource allocation optimization in heterogeneous networks with mobile edge computing[J]. IEEE Access, 2018,6: 19324-19337.
[32]	GENG Y , YANG Y , CAO G . Energy-efficient computation offloading for multicore-based mobile devices[C]// IEEE INFOCOM 2018-IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2018: 46-54.
[33]	CHEN X . Decentralized computation offloading game for mobile cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2014,26(4): 974-983.
[34]	GUO S , XIAO B , YANG Y ,et al. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing[C]// IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[35]	POCHET Y , WOLSEY L A . Production planning by mixed integer programming[M]. Berlin: Springer Science ＆ Business MediaPress, 2006.
[36]	TAMMER K . The application of parametric optimization and imbedding to the foundation and realization of a generalized primal decomposition approach[J]. Mathematical research, 1987,35: 376-386.
[37]	BOYD S , BOYD S P , VANDENBERGHE L . Convex optimization[M]. Cambridge: Cambridge University PressPress, 2004.
[38]	BEREANU B . Quasi-convexity,strictly quasi-convexity and pseudoconvexity of composite objective functions[J]. Revue Francaise D Automatique Informatique Recherche Operationnelle, 2009,6(R1): 15-26.
[39]	FUJISHIGE S . Submodular functions and optimization[M]. Amsterdam: ElsevierPress, 2005.
[40]	FEIGE U , MIRROKNI V S , VONDRáK J . Maximizing non-monotone submodular functions[J]. SIAM Journal on Computing, 2011,40(4): 1133-1153.
[41]	JI W , ZHU W . Profit maximization for sponsored data in wireless video transmission systems[J]. IEEE Transactions on Mobile Computing, 2020,19(8): 1928-1942.
[42]	KHULLER S , MOSS A , NAOR J S . The budgeted maximum coverage problem[J]. Information Processing Letters, 1999,70(1): 39-45.
[43]	ZHANG J , HU X , NING Z ,et al. Joint resource allocation for latency-sensitive services over mobile edge computing networks with caching[J]. IEEE Internet of Things Journal, 2018,6(3): 4283-4294.
[44]	SARDELLITTI S , SCUTARI G , BARBAROSSA S . Distributed joint optimization of radio and computational resources for mobile cloud computing[C]// 2014 IEEE 3rd International Conference on Cloud Networking. Piscataway:IEEE Press, 2014: 211-216.
[45]	SARDELLITTI S , SCUTARI G , BARBAROSSA S . Joint optimization of radio and computational resources for multicell mobile-edge computing[J]. IEEE Transactions on Signal and Information Processing over Networks, 2015,1(2): 89-103.

基于次模优化的边云协同多用户计算任务迁移方法

Multiuser computation offloading for edge-cloud collaboration using submodular optimization

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 45

相关文章 15

Metrics

推荐阅读 0

[1]	马玲, 樊漆亮, 许婷, 郭冠琛, 张圣林, 孙永谦, 张玉志. 基于强化学习的在线离线混部云环境下的调度框架[J]. 通信学报, 2023, 44(6): 90-102.
[2]	鲁蔚锋, 李宁, 徐佳, 徐力杰, 徐建. 多接入边缘计算中相关性任务的联合调度算法[J]. 通信学报, 2023, 44(4): 87-98.
[3]	苏新, 张桂福, 行鸿彦, Zenghui Wang. 基于平衡生成对抗网络的海洋气象传感网入侵检测研究[J]. 通信学报, 2023, 44(4): 124-136.
[4]	谢人超, 文雯, 唐琴琴, 刘云龙, 谢高畅, 黄韬. 轨道交通移动边缘计算网络安全综述[J]. 通信学报, 2023, 44(4): 201-215.
[5]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[6]	范伟, 彭诚, 朱大立, 王雨晴. 移动边缘计算网络下基于静态贝叶斯博弈的入侵响应策略研究[J]. 通信学报, 2023, 44(2): 70-81.
[7]	赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.
[8]	龙隆, 刘子辰, 陆在旺, 张玉成, 李蕾. 移动边缘网络下服务缓存与资源分配联合优化策略[J]. 通信学报, 2023, 44(1): 64-74.
[9]	张宇, 程旻. NDN中边缘计算与缓存的联合优化[J]. 通信学报, 2022, 43(8): 164-175.
[10]	王子园, 杜瑞忠. 边缘环境下基于无证书公钥密码的数据完整性审计方案[J]. 通信学报, 2022, 43(7): 62-72.
[11]	莫梓嘉, 高志鹏, 杨杨, 林怡静, 孙山, 赵晨. 面向车联网数据隐私保护的高效分布式模型共享策略[J]. 通信学报, 2022, 43(4): 83-94.
[12]	杨力, 潘成胜, 孔相广, 黄琦龙, 戚耀文. 5G融合卫星网络研究综述[J]. 通信学报, 2022, 43(4): 202-215.
[13]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[14]	曹敦, 张应宝, 邹电, 王进, 汤强, 冀保峰. V2X多节点协同分布式卸载策略[J]. 通信学报, 2022, 43(2): 185-195.
[15]	孙俨, 熊翱, 蒋承伶, 王威, 于东晓, 郭少勇. 基于区块链的计算与无线通信资源联合管理双向拍卖模型[J]. 通信学报, 2022, 43(11): 14-25.