多接入边缘计算中相关性任务的联合调度算法

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

通信学报 ›› 2023, Vol. 44 ›› Issue (4): 87-98.doi: 10.11959/j.issn.1000-436x.2023047

多接入边缘计算中相关性任务的联合调度算法

鲁蔚锋¹^,², 李宁¹^,², 徐佳¹^,², 徐力杰¹^,², 徐建³

¹ 南京邮电大学计算机学院、软件学院、网络空间安全学院，江苏南京 210023
² 南京邮电大学江苏省大数据安全与智能处理重点实验室，江苏南京 210023
³ 南京理工大学计算机科学与工程学院，江苏南京 210094

修回日期:2023-01-10 出版日期:2023-04-25 发布日期:2023-04-01
作者简介:鲁蔚锋（1979- ），男，安徽马鞍山人，博士，南京邮电大学副教授、硕士生导师，主要研究方向为边缘计算、网络安全、区块链等
李宁（1994- ），男，江苏徐州人，南京邮电大学硕士生，主要研究方向为边缘计算等
徐佳（1980- ），男，江苏常州人，博士，南京邮电大学教授、博士生导师，主要研究方向为群智感知、边缘计算、无线充电、区块链等
徐力杰（1983- ），男，江苏盐城人，博士，南京邮电大学副教授、硕士生导师，主要研究方向为传感网/物联网、无线充电网络、边缘计算、移动与分布式计算等
徐建（1979- ），男，江苏江阴人，博士，南京理工大学教授、博士生导师，主要研究方向为智能运维、网络安全等
基金资助:
国家自然科学基金资助项目(61872193);国家自然科学基金资助项目(61971235);国家自然科学基金资助项目(62072254)

Joint scheduling algorithm for correlative tasks in multi-access edge computing

Weifeng LU¹^,², Ning LI¹^,², Jia XU¹^,², Lijie XU¹^,², Jian XU³

¹ School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
² Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
³ School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China

Revised:2023-01-10 Online:2023-04-25 Published:2023-04-01
Supported by:
The National Natural Science Foundation of China(61872193);The National Natural Science Foundation of China(61971235);The National Natural Science Foundation of China(62072254)

摘要/Abstract

摘要：

多接入边缘计算已经成为资源密集型应用程序的有前途的计算范式。不过，先前大部分研究工作没有考虑到任务的相关性，这可能导致不可行的调度决策。考虑应用程序上有些任务必须要在本地完成，研究了相关性任务在本地和边缘侧的联合调度方法，并考虑了多接入边缘计算卸载场景下的另一个不可忽视的能耗问题。将问题形式化为在满足应用程序的完成截止时间约束的条件下最小化系统中的能耗，并提出联合调度（JS）算法解决该问题。最后通过仿真实验分析JS算法在应用程序的完成率和系统能耗两方面的性能。仿真结果表明，JS算法在应用程序的完成率上优于其他对比算法并且至少可以节省43%的系统能耗。

Abstract:

Multi-access edge computing (MEC) has emerged as a promising computing paradigm for resource-intensive applications.However, most of the previous research work has not considered correlative tasks, which may lead to infeasible scheduling decisions.Considering that some tasks on the application must be completed locally and another non-negligible energy consumption problem in the multi-access edge computing offloading scenario, the joint scheduling algorithm of correlative tasks on the local and edge sides was studied.The problem was formalized as minimizing the energy consumption in the system while satisfying the application’s completion deadline constraints, and the joint scheduling (JS) algorithm was proposed to solve the problem.Finally, the performance of the JS algorithm in the application completion rate and system energy consumption were analyzed through simulation experiments.The simulation results show that the JS algorithm is superior to other comparison algorithms in the application completion rate and can save at least 43% of the system energy consumption.

Key words: multi-access edge computing, correlative task, energy consumption, task scheduling, joint scheduling algo-rithm

中图分类号:

TN92

鲁蔚锋, 李宁, 徐佳, 徐力杰, 徐建. 多接入边缘计算中相关性任务的联合调度算法[J]. 通信学报, 2023, 44(4): 87-98.

Weifeng LU, Ning LI, Jia XU, Lijie XU, Jian XU. Joint scheduling algorithm for correlative tasks in multi-access edge computing[J]. Journal on Communications, 2023, 44(4): 87-98.

图/表 8

图1

表1

参数设置"

参数	随机生成DAG	分子动力学代码DAG
B_i/GB	[0.1, 0.2]	[0.1, 0.2]
V /个	450	41
$\| N \|$	10	3
D_i/KB	[100, 300]	[100, 300]
u_i,j/KB	[20, 60]	[20, 60]
$ξ_{k k'}$ /(ms·KB^-1)	[2, 5]	[2, 5]
K	40	4
f_k /GHz	[0.1, 1]	[0.1, 1]
$W_{N_{i}, k}$ /MHz	5	5
$P_{N_{i}}$ /mW	100	100
$l_{N_{i}, k}$ /m	[3, 15]	[3, 15]
β/dB	11	11
$σ^{2}$ /mW	10^-10	10^-10
直接后继的数量	[1, 4]	—

表1

图2

图3

图4

图5

图6

图7

参考文献 23

[1]	MACH P , BECVAR Z . Mobile edge computing:a survey on architecture and computation offloading[J]. IEEE Communications Surveys ＆Tutorials, 2017,19(3): 1628-1656.
[2]	XU J , CHEN L X , ZHOU P . Joint service caching and task offloading for mobile edge computing in dense networks[C]// Proceedings of IEEE INFOCOM 2018 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2018: 207-215.
[3]	SHI W S , CAO J , ZHANG Q ,et al. Edge computing:vision and challenges[J]. IEEE Internet of Things Journal, 2016,3(5): 637-646.
[4]	CHEN M , HAO Y X . Task offloading for mobile edge computing in software defined ultra-dense network[J]. IEEE Journal on Selected Areas in Communications, 2018,36(3): 587-597.
[5]	ABBAS N , ZHANG Y , TAHERKORDI A ,et al. Mobile edge computing:a survey[J]. IEEE Internet of Things Journal, 2018,5(1): 450-465.
[6]	SATYANARAYANAN M , BAHL P , CACERES R ,et al. The case for VM-based cloudlets in mobile computing[J]. IEEE Pervasive Computing, 2009,8(4): 14-23.
[7]	LI Y Q , WANG X , GAN X Y ,et al. Learning-aided computation offloading for trusted collaborative mobile edge computing[J]. IEEE Transactions on Mobile Computing, 2020,19(12): 2833-2849.
[8]	ESHRAGHI N , LIANG B . Joint offloading decision and resource allocation with uncertain task computing requirement[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2019: 1414-1422.
[9]	TONG L , LI Y , GAO W . A hierarchical edge cloud architecture for mobile computing[C]// Proceedings of IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[10]	ZHAO G M , XU H L , ZHAO Y M ,et al. Offloading dependent tasks in mobile edge computing with service caching[C]// Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2020: 1997-2006.
[11]	HE K , MENG X Z , PAN Z Z ,et al. A novel task-duplication based clustering algorithm for heterogeneous computing environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2019,30(1): 2-14.
[12]	JIA M K , CAO J N , YANG L . Heuristic offloading of concurrent tasks for computation-intensive applications in mobile cloud computing[C]// Proceedings of 2014 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway:IEEE Press, 2014: 352-357.
[13]	GUO S T , XIAO B , YANG Y Y ,et al. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing[C]// Proceedings of IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications. Piscataway:IEEE Press, 2016: 1-9.
[14]	SUNDAR S , LIANG B . Communication augmented latest possible scheduling for cloud computing with delay constraint and task dependency[C]// Proceedings of 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Piscataway:IEEE Press, 2016: 1009-1014.
[15]	LIU Y J , WANG S G , ZHAO Q L ,et al. Dependency-aware task scheduling in vehicular edge computing[J]. IEEE Internet of Things Journal, 2020,7(6): 4961-4971.
[16]	KAO Y H , KRISHNAMACHARI B , RA M R ,et al. Hermes:Latency optimal task assignment for resource-constrained mobile computing[C]// Proceedings of 2015 IEEE Conference on Computer Communications (INFOCOM). Piscataway:IEEE Press, 2015: 1894-1902.
[17]	CHUDAK F A , SHMOYS D B . Approximation algorithms for precedence-constrained scheduling problems on parallel machines that Run at different speeds[J]. Journal of Algorithms, 1999,30(2): 323-343.
[18]	HWANG J J , CHOW Y C , ANGER F D ,et al. Scheduling precedence graphs in systems with interprocessor communication times[J]. SIAM Journal on Computing, 1989,18(2): 244-257.
[19]	TOPCUOGLU H , HARIRI S , WU M Y . Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3): 260-274.
[20]	TONG Z , DENG X M , CHEN H J ,et al. QL-HEFT:a novel machine learning scheduling scheme base on cloud computing environment[J]. Neural Computing and Applications, 2020,32(10): 5553-5570.
[21]	AHMAD S G , MUNIR E U , NISAR W . A segmented approach for DAG scheduling in heterogeneous environment[C]// Proceedings of the 2011 12th International Conference on Parallel and Distributed Computing,Applications and Technologies. New York:ACM Press, 2011: 362-367.
[22]	SCHWIEBERT L , JAYASIMHA D N . Mapping to reduce contention in multiprocessor architectures[C]// Proceedings of Seventh International Parallel Processing Symposium. Piscataway:IEEE Press, 1993: 248-253.
[23]	WANG F , XU J , WANG X ,et al. Joint offloading and computing optimization in wireless powered mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2017,17(3): 1784-1797.

多接入边缘计算中相关性任务的联合调度算法

Joint scheduling algorithm for correlative tasks in multi-access edge computing

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 15

Metrics

推荐阅读 0

[1]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[2]	李翠然, 王雪洁, 谢健骊, 吕安琪. 基于改进PSO的铁路监测线性无线传感器网络路由算法[J]. 通信学报, 2022, 43(5): 155-165.
[3]	杨力, 潘成胜, 孔相广, 黄琦龙, 戚耀文. 5G融合卫星网络研究综述[J]. 通信学报, 2022, 43(4): 202-215.
[4]	苏新, 薛淏阳, 周一青, 朱金秀. 面向海洋观监测传感网的计算卸载方法研究[J]. 通信学报, 2021, 42(5): 149-163.
[5]	唐琴琴,谢人超,刘旭,张亚生,何辞,李诚成,黄韬. 融合MEC的星地协同网络：架构、关键技术与挑战[J]. 通信学报, 2020, 41(4): 162-181.
[6]	任品毅,许茜. 基于移动边缘计算的时延能耗最小化安全传输[J]. 通信学报, 2020, 41(11): 52-63.
[7]	李罡,吴志军. 基于多QoS约束条件的广域信息管理系统任务调度算法[J]. 通信学报, 2019, 40(7): 27-37.
[8]	蒲勇霖,于炯,鲁亮,李梓杨,卞琛,廖彬. 基于Storm平台的数据迁移合并节能策略[J]. 通信学报, 2019, 40(12): 68-85.
[9]	刘伟,熊曙,杜薇,王伟. 移动云环境中数据流应用的Cloudlet选择策略研究[J]. 通信学报, 2019, 40(1): 87-101.
[10]	毛艳艳,程大鹏,冯烟利,窦全胜,李大社. C3S：基于相长干涉的智能传感系统并发传输策略研究[J]. 通信学报, 2019, 40(1): 180-194.
[11]	梁俊斌,周翔,李陶深. 移动低占空比无线传感网中低能耗的主动邻居发现算法[J]. 通信学报, 2018, 39(4): 45-55.
[12]	蒲勇霖,于炯,鲁亮,卞琛,廖彬,李梓杨. storm平台下工作节点的内存电压调控节能策略[J]. 通信学报, 2018, 39(10): 97-117.
[13]	何灏,陈永锐,易卫东,李鸣. 无线可充电传感器网络中固定充电器的部署策略[J]. 通信学报, 2017, 38(Z1): 156-164.
[14]	黄焱,王鹏,谢高辉. 基于PE方法的数据中心需量费用优化算法[J]. 通信学报, 2016, 37(3): 90-97.
[15]	廖彬,张陶,于炯,刘继,尹路通,郭刚. 温度感知的MapReduce节能任务调度策略[J]. 通信学报, 2016, 37(1): 61-75.