边缘计算中多设备多任务的能耗均衡优化算法

doi:10.3778/j.issn.1673-9418.2009072

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (2): 480-488.DOI: 10.3778/j.issn.1673-9418.2009072

• 理论与算法 • 上一篇

边缘计算中多设备多任务的能耗均衡优化算法

庞源, 武继刚, 陈龙⁺(), 姚棉阳

广东工业大学计算机学院,广州 510006

收稿日期:2020-09-02 修回日期:2020-11-11 出版日期:2022-02-01 发布日期:2020-12-17
通讯作者: + E-mail: ustchenlong@gdut.edu.cn
作者简介:庞源（1994—）,男,广东湛江人,硕士研究生,主要研究方向为边缘计算、机器学习。
武继刚（1963—）,男,江苏沛县人,博士,广东工业大学百人计划特聘教授,CCF会员,主要研究方向为网络计算、云计算、机器智能、可重构架构。
陈龙（1988—）,男,安徽人,博士,副教授,硕士生导师,主要研究方向为移动云计算、车联网、认知无线电网络、网络经济学。
姚棉阳（1997—）,男,广东汕头人,硕士研究生,主要研究方向为移动边缘计算、分布式机器学习。
基金资助:
国家自然科学基金(62072118);国家自然科学基金(61702115);广东省科技计划重点领域研发项目(2019B010118001);广东省科技计划重点领域研发项目(2019B010121001)

Energy Balancing for Multiple Devices with Multiple Tasks in Mobile Edge Computing

PANG Yuan, WU Jigang, CHEN Long⁺(), YAO Mianyang

School of Computer, Guangdong University of Technology, Guangzhou 510006, China

Received:2020-09-02 Revised:2020-11-11 Online:2022-02-01 Published:2020-12-17
About author:PANG Yuan, born in 1994, M.S. candidate. His research interests include edge computing and machine learning.
WU Jigang, born in 1963, Ph.D., distinguished professor at Guangdong University of Techno-logy, member of CCF. His research interests include network computing, cloud computing, machine intelligence and reconfigurable architecture.
CHEN Long, born in 1988, Ph.D., associate professor, M.S. supervisor. His research interests include mobile cloud computing, Internet of vehicles, cognitive radio networks and network economics.
YAO Mianyang, born in 1997, M.S. candidate. His research interests include mobile edge com-puting and distributed machine learning.
Supported by:
National Natural Science Foundation of China(62072118);National Natural Science Foundation of China(61702115);Key-Area Research and Development Program of Guangdong Province(2019B010118001);Key-Area Research and Development Program of Guangdong Province(2019B010121001)

摘要/Abstract

摘要：

移动边缘计算技术随着科技的发展,面临着多设备多任务的能耗均衡的挑战。相关研究大多集中在如何利用边缘服务器的计算性能以减少移动设备在任务处理过程中的能耗和执行时间。但现有研究在多设备多任务的能耗均衡问题上还没有很好的解决方法。针对此类能耗均衡问题,改进了现有的边缘计算系统模型,并在此基础上,给出了多移动设备多任务的能耗均衡优化问题的计算模型,同时提出了一个贪心算法,并做出了相应的近似比分析。与总能耗优化算法以及随机算法进行对比,并进行了大量的仿真实验。实验结果证明,所提出的贪心算法的平均性能与随机算法相比在能耗均衡方面可进一步提升66.59%。通过与蛮力算法对比,在经典的任务拓扑下,当移动设备的最小传输功率分别为5 dBm和6 dBm时,贪心算法几乎获得最优解。

关键词: 移动边缘计算, 任务卸载, 能耗均衡, 贪心算法

Abstract:

With the development of technology, mobile edge computing is facing the challenge of energy balancing of multi-device and multi-task. Related research mostly focuses on how to utilize the computing performance of edge servers to reduce the energy consumption and execution time of mobile devices during task processing. However, the existing research has not yet a good solution to the problem of multi-device and multi-task energy balancing. Aiming at this kind of energy balancing problem, this paper improves the existing edge computing system model, and gives a calculation model for the energy balancing optimization problem of multi-device and multi-task. At the same time, a greedy algorithm is proposed and the corresponding approximate ratio analysis is made. In addition, this paper is compared with the total energy consumption minimization algorithm and the random algorithm, and a large number of simulation experiments are conducted. Experimental results reveal that the average performance of the proposed greedy algorithm can be further improved by 66.59% in terms of energy balancing than the random algorithm. Compared with the brute force algorithm, under the classic task topology, when the minimum transmission power of the mobile device is 5 dBm and 6 dBm respectively, the greedy algorithm almost obtains the optimal solution.

Key words: mobile edge computing, task offloading, energy balancing, greedy algorithm

中图分类号:

TP338

庞源, 武继刚, 陈龙, 姚棉阳. 边缘计算中多设备多任务的能耗均衡优化算法[J]. 计算机科学与探索, 2022, 16(2): 480-488.

PANG Yuan, WU Jigang, CHEN Long, YAO Mianyang. Energy Balancing for Multiple Devices with Multiple Tasks in Mobile Edge Computing[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 480-488.

图/表 6

表1 本文所用符号

Table 1 Notations of this paper

符号	含义
$M$	移动设备集
$N$	子任务集
$H$	中继设备集
$e$	边缘服务器
$W i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的工作量大小
$R i, k 、 R k'$	第 $i$ 个移动设备和第 $k$ 个中继设备之间的上行数据速率以及第 $k$ 个中继设备和边缘服务器之间的上行数据速率
$D i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的数据量大小
$t i, j local, E i, j local$	第 $i$ 个移动设备自身处理第 $j$ 个子任务的计算时间以及本地能耗
$t i, j, k sen d 1, E i, j, k sen d 1$	第 $j$ 个子任务从第 $i$ 个移动设备传输到第 $k$ 个中继设备的所需时间和能量消耗
$t i, j, k sen d 2, E i, j, k sen d 2$	第 $i$ 个移动设备的第 $j$ 个子任务从第 $k$ 个中继设备传输到边缘服务器的时间和能量消耗
$t i, j edge$	在 $e$ 上计算第 $i$ 个移动设备的第 $j$ 个子任务所需的时间
$E i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的总能耗
$t i, j f$	第 $i$ 个移动设备的第 $j$ 个子任务完成计算所需的时间
$T i$	第 $i$ 个移动设备所有子任务完成计算的时间
$E i$	第 $i$ 个移动设备所有子任务完成计算的能耗

表1 本文所用符号

Table 1 Notations of this paper

符号	含义
$M$	移动设备集
$N$	子任务集
$H$	中继设备集
$e$	边缘服务器
$W i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的工作量大小
$R i, k 、 R k'$	第 $i$ 个移动设备和第 $k$ 个中继设备之间的上行数据速率以及第 $k$ 个中继设备和边缘服务器之间的上行数据速率
$D i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的数据量大小
$t i, j local, E i, j local$	第 $i$ 个移动设备自身处理第 $j$ 个子任务的计算时间以及本地能耗
$t i, j, k sen d 1, E i, j, k sen d 1$	第 $j$ 个子任务从第 $i$ 个移动设备传输到第 $k$ 个中继设备的所需时间和能量消耗
$t i, j, k sen d 2, E i, j, k sen d 2$	第 $i$ 个移动设备的第 $j$ 个子任务从第 $k$ 个中继设备传输到边缘服务器的时间和能量消耗
$t i, j edge$	在 $e$ 上计算第 $i$ 个移动设备的第 $j$ 个子任务所需的时间
$E i, j$	第 $i$ 个移动设备的第 $j$ 个子任务的总能耗
$t i, j f$	第 $i$ 个移动设备的第 $j$ 个子任务完成计算所需的时间
$T i$	第 $i$ 个移动设备所有子任务完成计算的时间
$E i$	第 $i$ 个移动设备所有子任务完成计算的能耗

图1 系统模型

Fig.1 System model

表2 实验参数

Table 2 Experimental parameters

参数	数值	参数	数值
$α$	0.1	$B k' / MHz$	5
$B i, k / MHz$	5	$p k' / dBm$	5
$p i / dBm$	5	$f e / GHz$	4
$f i / GHz$	0.8	$σ' / dBm$	-70
$ρ i$	0.3×10^-27	$σ k / dBm$	-70

表2 实验参数

Table 2 Experimental parameters

参数	数值	参数	数值
$α$	0.1	$B k' / MHz$	5
$B i, k / MHz$	5	$p k' / dBm$	5
$p i / dBm$	5	$f e / GHz$	4
$f i / GHz$	0.8	$σ' / dBm$	-70
$ρ i$	0.3×10^-27	$σ k / dBm$	-70

图2 实验1

Fig.2 The first experiment

图3 实验2

Fig.3 The second experiment

图4 实验3

Fig.4 The third experiment

参考文献 32

[1]	CISCO. Global mobile data traffic forecast update, 2016—2021 white paper[M]. San Jose: Cisco, 2017: 11-19.
[2]	HU Y C, PATEL M, SABELLA D, et al. Mobile edge com-puting—a key technology towards 5G[J]. ETSI White Pa-per, 2015, 11(11):1-16.
[3]	MAO Y, YOU C, ZHANG J, et al. A survey on mobile edge computing: the communication perspective[J]. IEEE Com-munications Surveys and Tutorials, 2017, 19(4):2322-2358.
[4]	MACH P, BECVAR Z. Mobile edge computing: a survey on architecture and computation offloading[J]. IEEE Com-munications Surveys and Tutorials, 2017, 19(3):1628-1656.
[5]	LIU T, CHEN F, MA Y, et al. An energy-efficient task sche-duling for mobile devices based on cloud assistant[J]. Fu-ture Generation Computer Systems, 2016, 61:1-12.
[6]	LUAN T H, GAO L X, LI Z, et al. Fog computing: focu-sing on mobile users at the edge[J]. arXiv:1502.01815, 2015.
[7]	DINH H T, LEE C, NIYATO D, et al. A survey of mobile cloud computing: architecture, applications, and approaches[J]. Wireless Communications and Mobile Computing, 2013, 13(18):1587-1611. DOI URL
[8]	TAO X Y, OTA K, DONG M X, et al. Performance guaran-teed computation offloading for mobile-edge cloud compu-ting[J]. IEEE Wireless Communications Letters, 2017, 6(6):774-777. DOI URL
[9]	GEDAWY H, HABAK K, HARRAS K A, et al. Awakening the cloud within: energy-aware task scheduling on edge IoT devices[C]//Proceedings of the 2018 IEEE International Conference on Pervasive Computing and Communications Workshops, Athens, Mar 19-23, 2018. Washington: IEEE Computer Society, 2018: 191-196.
[10]	WANG Y T, SHENG M, WANG X J, et al. Mobile-edge computing: partial computation offloading using dynamic voltage scaling[J]. IEEE Transactions on Communications, 2016, 64(10):4268-4282.
[11]	JIA M, CAO J N, YANG L. Heuristic offloading of concur-rent tasks for computation-intensive applications in mobile cloud computing[C]//Proceedings of the 2014 IEEE Confe-rence on Computer Communications Workshops, Toronto, Apr 27-May 2, 2014. Piscataway: IEEE, 2014: 352-357.
[12]	LIU F G, HUANG Z X, WANG L M. Energy-efficient col-laborative task computation offloading in cloud-assisted edge computing for IoT sensors[J]. Sensors, 2019, 19(5):1105-1124. DOI URL
[13]	WU W, ZHOU F H, LI P, et al. Energy-efficient secure NOMA- enabled mobile edge computing networks[C]//Proceedings of the 2019 IEEE International Conference on Communica-tions, Shanghai, May 20-24, 2019. Piscataway: IEEE, 2019: 1-6.
[14]	MENG Z Y, XU H L, HUANG L S, et al. Achieving energy efficiency through dynamic computing offloading in mo-bile edge-clouds[C]//Proceedings of the 15th IEEE Interna-tional Conference on Mobile Ad Hoc and Sensor Systems, Chengdu, Oct 9-12, 2018. Washington: IEEE Computer So-ciety, 2018: 175-183.
[15]	CHEN M H, LIANG B, DONG M. Joint offloading deci-sion and resource allocation for multi-user multi-task mo-bile cloud[C]//Proceedings of the 2016 IEEE International Conference on Communications, Kuala Lumpur, May 22-27, 2016. Piscataway: IEEE, 2016: 1-6.
[16]	KAMOUN M, LABIDI W, SARKISS M. Joint resource al-location and offloading strategies in cloud enabled cellular networks[C]//Proceedings of the 2015 IEEE International Conference on Communications, London, Jun 8-12, 2015. Piscataway: IEEE, 2015: 5529-5534.
[17]	LONG X, WU J G, CHEN L. Energy-efficient offloading in mobile edge computing with edge-cloud collaboration[C]//LNCS 11336: Proceedings of the 18th International Con-ference on Algorithms and Architectures for Parallel Proces-sing, Guangzhou, Nov 15-17, 2018. Cham: Springer, 2018: 460-475.
[18]	YU S, LANGAR R, LI W Z, et al. Coalition-based energy efficient offloading strategy for immersive collaborative applications in Femto-Cloud[C]//Proceedings of the 2016 IEEE International Conference on Communications, Kuala Lumpur, May 22-27, 2016. Piscataway: IEEE, 2016: 1-6.
[19]	SUNDAR S, LIANG B. Offloading dependent tasks with communication delay and deadline constraint[C]//Procee-dings of the 2018 IEEE Conference on Computer Com-munications, Honolulu, Apr 16-19, 2018. Piscataway: IEEE, 2018: 37-45.
[20]	MAZOUZI H, ACHIR N, BOUSSETTA K, et al. Maximi-zing mobiles energy saving through tasks optimal offloa-ding placement in two-tier cloud[C]//Proceedings of the 21st ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal, Oct 28-Nov 2, 2018. New York: ACM, 2018: 137-145.
[21]	GUO S T, LIU J D, YANG Y Y, et al. Energy-efficient dynamic computation offloading and cooperative task sche-duling in mobile cloud computing[J]. IEEE Transactions on Mobile Computing, 2019, 18(2):319-333. DOI URL
[22]	LIU J, MAO Y Y, ZHANG J, et al. Delay-optimal compu-tation task scheduling for mobile-edge computing systems[C]//Proceedings of the 2016 IEEE International Sympo-sium on Information Theory, Barcelona, Jul 10-15, 2016. Piscataway: IEEE, 2016: 1451-1455.
[23]	CHEN W W, WANG D, LI K Q. Multi-user multi-task com-putation offloading in green mobile edge cloud computing[J]. IEEE Transactions on Services Computing, 2019, 12(5):726-738. DOI URL
[24]	CHEN L, WU J G, LONG X, et al. ENGINE: cost effective offloading in mobile edge computing with fog-cloud coo-peration[J]. arXiv:1711.01683, 2017.
[25]	YI C Y, CAI J, SU Z. A multi-user mobile computation offloading and transmission scheduling mechanism for delay-sensitive applications[J]. IEEE Transactions on Mobile Com-puting, 2020, 19(1):29-43.
[26]	CHEN X, JIAO L, LI W Z, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking, 2016, 24(5):2795-2808. DOI URL
[27]	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 Jour-nal of Electronics and Communications, 2020, 118:153134.
[28]	WANG J R, LIU K Y, PAN J P. Online UAV-mounted edge server dispatching for mobile-to-mobile edge computing[J]. IEEE Internet of Things Journal, 2020, 7(2):1375-1386. DOI URL
[29]	LUO J, DENG X H, ZHANG H G, et al. Ultra-low latency service provision in edge computing[C]//Proceedings of the 2018 IEEE International Conference on Communications, Kansas City, May 20-24, 2018. Piscataway: IEEE, 2018: 1-6.
[30]	QUEK T Q S, DE LA ROCHE D, GVEN I, et al. Small cell networks: deployment, PHY techniques, and resource mana-gement[M]. New York: Cambridge University Press, 2013.
[31]	CAO X W, WANG F, XU J, et al. Joint computation and communication cooperation for energy-efficient mobile edge computing[J]. IEEE Internet of Things Journal, 2019, 6(3):4188-4200. DOI URL
[32]	GUO H Z, LIU J J. Collaborative computation offloading for multiaccess edge computing over fiber-wireless net-works[J]. IEEE Transactions on Vehicular Technology, 2018, 67(5):4514-4526. DOI URL

边缘计算中多设备多任务的能耗均衡优化算法

Energy Balancing for Multiple Devices with Multiple Tasks in Mobile Edge Computing

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 32

相关文章 8

编辑推荐

Metrics

[1]	张子辰, 岳昆, 祁志卫, 段亮. 时序知识图谱的增量构建[J]. 计算机科学与探索, 2022, 16(3): 598-607.
[2]	刘荆欣, 王妍, 韩笑, 夏长清, 宋宝燕. 基于Stackelberg博弈的边缘云资源定价机制研究[J]. 计算机科学与探索, 2022, 16(1): 153-162.
[3]	曹义亲, 刘龙标, 何恬, 丁要男. 基于贪心选择及斜率探测扩充的轨面提取方法[J]. 计算机科学与探索, 2022, 16(1): 205-216.
[4]	刘继军, 邹山花, 卢先领. MEC中资源分配与卸载决策联合优化策略[J]. 计算机科学与探索, 2021, 15(5): 848-858.
[5]	李颖浩, 嵩天, 杨雅婷. 面向边缘计算的组合拍卖式任务卸载机制[J]. 计算机科学与探索, 2021, 15(1): 73-83.
[6]	叶继华, 肖波, 杨思渝, 刘凯, 江爱文. 结合相对熵和多跳转发路由的改进WSN节能策略[J]. 计算机科学与探索, 2021, 15(1): 119-131.
[7]	郑逢斌，朱东伟，臧文乾，杨劲林，朱光辉. 边缘计算：新型计算范式综述与应用研究[J]. 计算机科学与探索, 2020, 14(4): 541-553.
[8]	孙焕良，富珊珊，刘俊岭，于戈，许鸿斐. 社会网络中弱关系团队形成问题研究[J]. 计算机科学与探索, 2016, 10(6): 773-785.