基于动态服务缓存辅助的任务卸载方法

doi:10.11772/j.issn.1001-9081.2023050831

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1493-1500.DOI: 10.11772/j.issn.1001-9081.2023050831

• 第十九届中国机器学习会议(CCML 2023) • 上一篇

基于动态服务缓存辅助的任务卸载方法

张俊娜, 王欣新(), 李天泽, 赵晓焱, 袁培燕

河南师范大学计算机与信息工程学院，河南新乡 453007

收稿日期:2023-06-27 修回日期:2023-07-22 接受日期:2023-07-24 发布日期:2023-08-03 出版日期:2024-05-10
通讯作者: 王欣新
作者简介:张俊娜（1979—），女，河南扶沟人，副教授，博士，CCF会员，主要研究方向：边缘计算、服务计算
李天泽（1997—），男，河南周口人，硕士研究生，主要研究方向：边缘计算、机器学习
赵晓焱（1981—），女，河南许昌人，副教授，博士，CCF会员，主要研究方向：边缘计算、D2D通信
袁培燕（1978—），男，河南邓州人，教授，博士，CCF会员，主要研究方向：边缘计算、群智感知。
第一联系人：王欣新（1997—），女，河南驻马店人，硕士研究生，主要研究方向：边缘计算、服务计算
基金资助:
国家自然科学基金资助项目(62072159);河南省科技攻关项目(232102211061)

Task offloading method based on dynamic service cache assistance

Junna ZHANG, Xinxin WANG(), Tianze LI, Xiaoyan ZHAO, Peiyan YUAN

College of Computer and Information Engineering，Henan Normal University，Xinxiang Henan 453007，China

Received:2023-06-27 Revised:2023-07-22 Accepted:2023-07-24 Online:2023-08-03 Published:2024-05-10
Contact: Xinxin WANG
About author:ZHANG Junna， born in 1979， Ph. D.， associate professor. Her research interests include edge computing， service computing.
LI Tianze， born in 1997， M. S. candidate. His research interests include edge computing， machine learning.
ZHAO Xiaoyan， born in 1981， Ph. D.， associate professor. Her research interests include edge computing， D2D communication.
YUAN Peiyan， born in 1978， Ph. D.， professor. His research interests include edge computing， crowd sensing.
Supported by:
National Natural Science Foundation of China(62072159);Science and Technology Research Project of Henan Province(232102211061)

摘要/Abstract

摘要：

针对服务缓存和任务卸载联合优化中，由于缺乏对用户服务请求多样性和动态性的综合考虑而导致的用户体验质量降低问题，提出一种基于动态服务缓存辅助的任务卸载方法。首先，针对边缘服务器执行缓存服务动作空间较大的问题，重新定义了动作，并筛选出最优的动作集合以提高算法训练的效率；其次，设计一种改进的多智能体Q-Learning算法学习最优的服务缓存策略；再次，将任务卸载问题转换为凸优化问题，利用凸优化工具获得最优解；最后，利用拉格朗日对偶法求得最优的计算资源分配策略。为了验证所提方法的有效性，基于真实数据集进行了充分的实验。实验结果表明，对比Q-Learning、双层深度Q网络（D2QN）以及多智能体深度确定性策略梯度（MADDPG）方法，所提方法的响应时间分别降低了8.5%、11.8%和12.6%，平均体验质量分别提高了1.5%、2.7%和4.3%。

关键词: 边缘计算, 动态服务缓存, 任务卸载, 计算资源分配, 服务多样性

Abstract:

Aiming at the problem of user experience quality degradation due to the lack of comprehensive consideration of the diversity and dynamics of user service requests in the joint optimization of service caching and task offloading， a task offloading method based on dynamic service cache assistance was proposed. Firstly， to address the problem of the large action spaces for edge servers performing caching service， the actions were redefined and the optimal set of actions was selected to improve the efficiency of algorithm training. Secondly， an improved multi-agent Q-Learning algorithm was designed to learn an optimal service caching policy. Thirdly， the task offloading problem was converted into a convex optimization problem， and the optimal solution was obtained using a convex optimization tool. Finally， the optimal computational resource allocation policy was found using the Lagrangian dual method. To verify the effectiveness of the proposed method， extensive experiments were conducted based on a real dataset. Experimental results show that the response time of the proposed method is reduced by 8.5%， 11.8% and 12.6%， respectively， and the average quality of experience is improved by 1.5%， 2.7% and 4.3%， respectively， compared with Q-Learning， Double Deep Q Network （D2QN） and Multi-Agent Deep Deterministic Policy Gradient （MADDPG） method.

Key words: edge computing, dynamic service cache, task offloading, computing resource allocation, service diversity

中图分类号:

TP393

张俊娜, 王欣新, 李天泽, 赵晓焱, 袁培燕. 基于动态服务缓存辅助的任务卸载方法[J]. 计算机应用, 2024, 44(5): 1493-1500.

Junna ZHANG, Xinxin WANG, Tianze LI, Xiaoyan ZHAO, Peiyan YUAN. Task offloading method based on dynamic service cache assistance[J]. Journal of Computer Applications, 2024, 44(5): 1493-1500.

图/表 10

图1 网络模型

Fig. 1 Network model

表1 变量符号表

Tab. 1 Variable symbol table

符号	描述
E	边缘服务器集合
S	服务集合
$T$	时隙集合
U	用户设备集合
$F m$	边缘服务器 $e m$ 的最大计算能力
$C m$	边缘服务器 $e m$ 的最大存储能力
$c k$	服务 $s k$ 所需的存储大小
$D n i$	任务 $A n i$ 的输入数据大小
$W n i$	任务 $A n i$ 的计算工作负载
$T n m a x$	用户设备 $u n$ 的延迟阈值
$M n i$	为任务 $A n i$ 提供所需服务的边缘服务器集合
$I m e x e$	边缘服务器 $e m$ 需要执行的任务集合
$T e t r a n (t)$	在时隙 $T t$ ，任务 $A n i$ 卸载到边缘服务器的传输时延
$T c t r a n (t)$	在时隙 $T t$ ，任务 $A n i$ 卸载到云服务器的传输时延
$T n i e x e (t)$	在时隙 $T t$ ，任务 $A n i$ 的计算时间
$E T n i (t)$	在时隙 $T t$ ，任务 $A n i$ 的完成时间
$E T n (t)$	在时隙 $T t$ ，用户设备 $u n$ 的完成时间
$x m k (t)$	在时隙 $T t$ ，边缘服务器 $m$ 是否缓存服务 $k$
$y n m i (t)$	在时隙 $T t$ ，任务 $A n i$ 是否被卸载至边缘服务器 $m$
$f m n i (t)$	在时隙 $T t$ ，边缘服务器 $m$ 为任务 $A n i$ 分配计算资源

表1 变量符号表

Tab. 1 Variable symbol table

符号	描述
E	边缘服务器集合
S	服务集合
$T$	时隙集合
U	用户设备集合
$F m$	边缘服务器 $e m$ 的最大计算能力
$C m$	边缘服务器 $e m$ 的最大存储能力
$c k$	服务 $s k$ 所需的存储大小
$D n i$	任务 $A n i$ 的输入数据大小
$W n i$	任务 $A n i$ 的计算工作负载
$T n m a x$	用户设备 $u n$ 的延迟阈值
$M n i$	为任务 $A n i$ 提供所需服务的边缘服务器集合
$I m e x e$	边缘服务器 $e m$ 需要执行的任务集合
$T e t r a n (t)$	在时隙 $T t$ ，任务 $A n i$ 卸载到边缘服务器的传输时延
$T c t r a n (t)$	在时隙 $T t$ ，任务 $A n i$ 卸载到云服务器的传输时延
$T n i e x e (t)$	在时隙 $T t$ ，任务 $A n i$ 的计算时间
$E T n i (t)$	在时隙 $T t$ ，任务 $A n i$ 的完成时间
$E T n (t)$	在时隙 $T t$ ，用户设备 $u n$ 的完成时间
$x m k (t)$	在时隙 $T t$ ，边缘服务器 $m$ 是否缓存服务 $k$
$y n m i (t)$	在时隙 $T t$ ，任务 $A n i$ 是否被卸载至边缘服务器 $m$
$f m n i (t)$	在时隙 $T t$ ，边缘服务器 $m$ 为任务 $A n i$ 分配计算资源

图2 改进的多智能体Q-Learning算法框架

Fig. 2 Framework of improved multi-agent Q-Learning algorithm

表2 边缘服务器em的动作空间

Tab. 2 Action space of edge server em

服务子集	存储大小	动作	服务子集	存储大小	动作
$[s 1, s 2, s 3]$	1+2+3=6	［1，1，1，0，0］	$[s 1, s 3, s 5]$	1+3+4=8	［1，0，1，0，1］
$[s 1, s 2, s 4]$	1+2+3=6	［1，1，0，1，0］	$[s 1, s 4, s 5]$	1+3+4=8	［1，0，0，1，1］
$[s 1, s 2, s 5]$	1+2+4=7	［1，1，0，0，1］	$[s 2, s 3, s 4]$	2+3+3=8	［0，1，1，1，0］
$[s 1, s 3, s 4]$	1+3+3=7	［1，0，1，1，0］

表2 边缘服务器em的动作空间

Tab. 2 Action space of edge server em

服务子集	存储大小	动作	服务子集	存储大小	动作
$[s 1, s 2, s 3]$	1+2+3=6	［1，1，1，0，0］	$[s 1, s 3, s 5]$	1+3+4=8	［1，0，1，0，1］
$[s 1, s 2, s 4]$	1+2+3=6	［1，1，0，1，0］	$[s 1, s 4, s 5]$	1+3+4=8	［1，0，0，1，1］
$[s 1, s 2, s 5]$	1+2+4=7	［1，1，0，0，1］	$[s 2, s 3, s 4]$	2+3+3=8	［0，1，1，1，0］
$[s 1, s 3, s 4]$	1+3+3=7	［1，0，1，1，0］

表3 Q表的创建和初始化结果

Tab. 3 Results of Q table creation and initialization

边缘

服务器

动作索引

边缘

服务器

动作索引

e 1

-1

e 3

e 2

表3 Q表的创建和初始化结果

Tab. 3 Results of Q table creation and initialization

边缘

服务器

动作索引

边缘

服务器

动作索引

e 1

-1

e 3

e 2

表4 实验参数

Tab. 4 Experimental parameters

参数	数值	参数	数值
$D n i$	［0.2， 1］ Mb	$p n m$	1.5 W
$W n i$	［0.1， 0.5］ GHz	$σ 2$	100 dBm
$F m$	10 GHz	$T e t r (t)$	0.2 s
$C m$	10 Mb	$T c o r e (t)$	1.5 s
$c k$	［1， 5］ Mb	$T n m a x$	［0.5， 3］ s
B	20 MHz	EPISODE	20 000

表4 实验参数

Tab. 4 Experimental parameters

参数	数值	参数	数值
$D n i$	［0.2， 1］ Mb	$p n m$	1.5 W
$W n i$	［0.1， 0.5］ GHz	$σ 2$	100 dBm
$F m$	10 GHz	$T e t r (t)$	0.2 s
$C m$	10 Mb	$T c o r e (t)$	1.5 s
$c k$	［1， 5］ Mb	$T n m a x$	［0.5， 3］ s
B	20 MHz	EPISODE	20 000

图3 迭代轮数对平均奖励值、响应时间和体验质量的影响

Fig. 3 Impact of iteration rounds on average reward， response time and quality of experience

图4 边缘服务器数对平均响应时间和体验质量的影响

Fig. 4 Impact of number of edge servers on average response time and quality of experience

图5 用户数对平均响应时间和体验质量的影响

Fig. 5 Impact of number of users on average response time and quality of experience

图6 边缘服务器存储容量对平均响应时间和体验质量的影响

Fig. 6 Impact of storage capacities of edge servers on average response time and quality of experience

参考文献 22

1	CHEN J， YANG Y， WANG C， et al. Multitask offloading strategy optimization based on directed acyclic graphs for edge computing ［J］. IEEE Internet of Things Journal， 2022， 9（12）： 9367-9378. 10.1109/jiot.2021.3110412
2	YANG G， HOU L， HE X， et al. Offloading time optimization via markov decision process in mobile-edge computing ［J］. IEEE Internet of Things Journal， 2021， 8（4）： 2483-2493. 10.1109/jiot.2020.3033285
3	张秋平，孙胜，刘敏，等.面向多边缘设备协作的任务卸载和服务缓存在线联合优化机制［J］.计算机研究与发展，2021，58（6）：1318-1339. 10.7544/issn1000-1239.2021.20201088
	ZHANG Q P， SUN S， LIU M， et al. Online joint optimization mechanism of task offloading and service caching for multi-edge device collaboration ［J］. Journal of Computer Research and Development， 2021， 58（6）： 1318-1339. 10.7544/issn1000-1239.2021.20201088
4	ZHENG G， XU C， LONG H， et al. Service caching based task offloading and resource allocation in multi-UAV assisted MEC networks ［C］// Proceedings of the 2021 IEEE/CIC International Conference on Communications in China. Piscataway： IEEE， 2021： 1024-1029. 10.1109/iccc52777.2021.9580248
5	ZHAO G， XU H， ZHAO Y， et al. Offloading dependent tasks in mobile edge computing with service caching ［C］// Proceedings of the 2020 IEEE Conference on Computer Communications. Piscataway： IEEE， 2020： 1997-2006. 10.1109/infocom41043.2020.9155396
6	BI S， HUANG L， ZHANG Y-J A. Joint optimization of service caching placement and computation offloading in mobile edge computing systems ［J］. IEEE Transactions on Wireless Communications， 2020， 19（7）： 4947-4963. 10.1109/twc.2020.2988386
7	HUANG M， LIU W， WANG T， et al. A cloud-MEC collaborative task offloading scheme with service orchestration ［J］. IEEE Internet of Things Journal， 2020， 7（7）： 5792-5805. 10.1109/jiot.2019.2952767
8	FENG H， GUO S， YANG L， et al. Collaborative data caching and computation offloading for multi-service mobile edge computing ［J］. IEEE Transactions on Vehicular Technology， 2021， 70（9）： 9408-9422. 10.1109/tvt.2021.3099303
9	MA X， ZHOU A， ZHANG S， et al. Cooperative service caching and workload scheduling in mobile edge computing ［C］// Proceedings of the 2020 IEEE Conference on Computer Communications. Piscataway： IEEE， 2020： 2076-2085. 10.1109/infocom41043.2020.9155455
10	POULARAKIS K， LLORCA J， TULINO A， et al. Service placement and request routing in MEC networks with storage， computation， and communication constraints ［J］. IEEE/ACM Transactions on Networking， 2020， 28（3）： 1047-1060. 10.1109/tnet.2020.2980175
11	XU Z， ZHOU L， C-K CHAU S， et al. Near-optimal and collaborative service caching in mobile edge clouds ［J］. IEEE Transactions on Mobile Computing， 2023， 22（7）： 4070-4085. 10.1109/tmc.2022.3144175
12	XU J， CHEN L， ZHOU P. Joint service caching and task offloading for mobile edge computing in dense networks ［C］// Proceedings of the 2018 IEEE Conference on Computer Communications. Piscataway： IEEE， 2018： 207-215. 10.1109/infocom.2018.8485977
13	HAO Y， CHEN M， GHARAVI H， et al. Deep reinforcement learning for edge service placement in softwarized industrial cyber-physical system［J］. IEEE Transactions on Industrial Informatics， 2021， 17（8）： 5552-5561. 10.1109/tii.2020.3041713
14	ZHANG G， ZHANG S， ZHANG W， et al. Joint service caching， computation offloading and resource allocation in mobile edge computing systems ［J］. IEEE Transactions on Wireless Communications， 2021， 20（8）： 5288-5300. 10.1109/twc.2021.3066650
15	CHEN S， RUI L， GAO Z， et al. Cache-assisted collaborative task offloading and resource allocation strategy： a meta-reinforcement learning approach ［J］. IEEE Internet of Things Journal， 2022， 9（20）： 19823-19842. 10.1109/jiot.2022.3168885
16	PENG K， NIE J， KUMAR N， et al. Joint optimization of service chain caching and task offloading in mobile edge computing ［J］. Applied Soft Computing， 2021， 103： 107142. 10.1016/j.asoc.2021.107142
17	CHEN Y， ZHANG S， JIN Y， et al. LOCUS： user-perceived delay-aware service placement and user allocation in MEC environment ［J］. IEEE Transactions on Parallel and Distributed Systems， 2022， 33（7）： 1581-1592. 10.1109/tpds.2021.3119948
18	HE W， GAO L， LUO J. A multi-layer offloading framework for dependency-aware tasks in MEC ［C］// Proceedings of the 2021 IEEE International Conference on Communications. Piscataway： IEEE， 2021： 1-6. 10.1109/icc42927.2021.9500790
19	张俊娜，鲍想，陈家伟，等.一种联合时延和能耗的依赖性任务卸载方法［J］.计算机研究与发展，2023， 60（12）： 2770-2782. 10.11896/jsjkx.220900185
	ZHANG J N， BAO X， CHEN J W， et al. A dependent task offloading method for joint time delay and energy consumption ［J］. Journal of Computer Research and Development， 2023， 60（12）： 2770-2782. 10.11896/jsjkx.220900185
20	LAI P， HE Q， ABDELRAZEK M， et al. Optimal edge user allocation in edge computing with variable sized vector bin packing ［C］// Proceedings of the 2018 International Conference on Service-Oriented Computing. Cham： Springer， 2018： 230-245. 10.1007/978-3-030-03596-9_15
21	ZHONG S， GUO S， YU H， et al. Cooperative service caching and computation offloading in multi-access edge computing ［J］. Computer Networks， 2021， 189： 107916. 10.1016/j.comnet.2021.107916
22	HOU W， WEN H， SONG H， et al. Multiagent deep reinforcement learning for task offloading and resource allocation in cybertwin-based networks ［J］. IEEE Internet of Things Journal， 2021， 8（22）： 16256-16268. 10.1109/jiot.2021.3095677

[1]	赵徐炎, 崔允贺, 蒋朝惠, 钱清, 申国伟, 郭春, 李显超. CHAIN：基于重合支配的边缘计算节点放置算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2812-2818.
[2]	陈宛桢, 张恩, 秦磊勇, 洪双喜. 边缘计算下基于区块链的隐私保护联邦学习算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2209-2216.
[3]	李校林, 江雨桑. 无人机辅助移动边缘计算中的任务卸载算法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1893-1899.
[4]	曹腾飞, 刘延亮, 王晓英. 基于改进深度强化学习的边缘计算服务卸载算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1543-1550.
[5]	王哲, 王启名, 李陶深, 葛丽娜. 基于深度强化学习的SWIPT边缘网络联合优化方法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3540-3550.
[6]	王界钦, 林士飏, 彭世明, 贾硕, 杨苗会. 协同移动边缘计算分层资源配置机制[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2501-2510.
[7]	刘炎培, 陈宁宁, 朱运静, 王丽萍. 面向5G/Beyond 5G的移动边缘缓存优化技术综述[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2487-2500.
[8]	夏慧雯, 赵中雨, 王卓尔, 张清勇, 彭峰. 基于边缘计算的公共交通工具疫情监测系统[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2132-2138.
[9]	张杰, 许姗姗, 袁凌云. 基于区块链与边缘计算的物联网访问控制模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2104-2111.
[10]	邓世权, 叶绪国. 基于深度Q网络的多目标任务卸载算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1668-1674.
[11]	袁景凌, 毛慧华, 王娜娜, 向尧. 移动边缘计算中资源受限的动态服务部署策略[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1662-1667.
[12]	李余, 何希平, 唐亮贵. 基于终端直通通信的多用户计算卸载资源优化决策[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1538-1546.
[13]	曾续玲, 李陶深, 巩健, 杜利俊. 无线供能移动边缘计算系统的安全卸载优化[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1216-1224.
[14]	王亚丽, 陈家超, 张俊娜. 移动边缘计算中收益最大化的缓存协作策略[J]. 《计算机应用》唯一官方网站, 2022, 42(11): 3479-3485.
[15]	李智, 薛建彬. C‑V2X车联网中基于模拟退火算法的任务卸载与资源分配[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3140-3147.

基于动态服务缓存辅助的任务卸载方法

Task offloading method based on dynamic service cache assistance

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 22

相关文章 15

编辑推荐

Metrics