面向移动感知的计算卸载及资源分配策略研究

doi:10.19678/j.issn.1000-3428.0066522

摘要/Abstract

摘要：

在移动边缘计算(MEC)中，用户设备将计算密集任务卸载至边缘服务器执行以降低执行时延与能耗，基于5G技术的新型应用要求计算过程支持设备的高速移动性，而目前计算卸载方案的研究大多集中于静态场景。为提高用户体验质量，在多设备与多MEC服务器场景下，对MEC中考虑设备移动轨迹的计算卸载方案进行研究。结合设备移动性、计算与通信资源、信道状态及任务需求等因素, 将场景下的计算卸载方案设计为混合整数非线性规划问题。为降低求解难度，将上述问题分解为卸载服务器选择问题和固定服务器选择方案下的计算资源分配与子信道选择问题，采用凸优化技术及改进的Kuhn-Munkres算法对子问题进行求解，并依据子问题的解设计启发式卸载服务器选择算法，基于多项式时间复杂度获得次优卸载方案。通过EdgeCloudSim工具对本文卸载策略进行仿真，并与常用的卸载算法进行对比，实验结果表明，该算法在满足任务的实时性要求下，与穷举算法的平均系统效用差距控制在2.3%以内。

关键词: 移动边缘计算, 移动感知, 计算卸载, 资源分配, 卸载算法

Abstract:

In Mobile Edge Computing(MEC), user equipment offloads computationally intensive tasks to edge servers for execution to reduce execution delay and energy consumption.This process requires 5G technology-based applications to support the high-speed movement of devices during computing.However, much of the current research on computational offload solutions is focused on static scenarios.To improve the quality of user experience, this study investigates a computational offloading scheme that considers device movement trajectories in MEC and thus more suitable multi-device and multi-MEC server scenarios.Because this scheme considers multiple factors such as device mobility, computing and communication resources, channel states, and mission requirements, it can be described as a mixed-integer nonlinear programming problem.To reduce the difficulties inherent in solving this problem, this study decomposes the problem into subproblems of offloading server selection, computing resource allocation, and subchannel selection under a fixed-server selection scheme.The convex optimization technique and improved Kuhn-Munkres algorithm are then used to solve the subproblems.This study also designs a heuristic offload server selection algorithm based on the solution to the subproblems and derives a suboptimal offload solution with polynomial time complexity.Simulations are conducted using the EdgeCloudSim tool, the results of which prove the effectiveness of the proposed algorithm as compared with five other commonly used offloading algorithms.The experimental results show that the average system utility gap between the algorithm and exhaustive algorithm can be controlled to within 2.3% when it meets the real-time requirements of a given task.

Key words: Mobile Edge Computing(MEC), mobility-aware, computation offloading, resource allocation, offloading algorithm

班玉琦, 段利国, 温昊宇, 李爱萍, 赵菊敏. 面向移动感知的计算卸载及资源分配策略研究[J]. 计算机工程, 2023, 49(8): 163-173.

Yuqi BAN, Liguo DUAN, Haoyu WEN, Aiping LI, Jumin ZHAO. Research on Mobility-Aware Computation Offloading and Resource Allocation Strategy[J]. Computer Engineering, 2023, 49(8): 163-173.

http://www.ecice06.com/CN/Y2023/V49/I8/163

图/表 10

图1 移动设备卸载场景示意图

Fig.1 Schematic diagram of the offloading scenario for mobile devices

图2 场景划分及传输速率近似

Fig.2 Scenario division and transmission rate approximation

图3 卸载方案的整体框架

Fig.3 Overall framework for offloading scheme

表1 任务类型及相关参数配置

Table 1 Task type and related parameters configuration

任务类型	上传数据大小/KB	所需计算量/GIPS	完成时间限制/s	设备移动速度/(m·s^-1)
AR	1 500	12	无	[0, 2]
健康医疗	1 100	3	2	[5, 10]
信息处理	200	6	3	[30, 40]

表2 各算法平均运行时间

Table 2 Average running time of each algorithms

算法	运行时间/ms
独立卸载	0.23±0.08
JTORA算法	35.44±0.81
本文卸载算法	39.80±1.22
静态穷举算法	3473±1.67
穷举算法	4236±1.93

表3 不同部署场景下本文算法平均运行时间

Table 3 The average running time of the proposed algorithm in different deployment scenarios

SBS数量/个	间隔/m	设备数量/个	运行时间/s
12	237	60	0.43±0.02
20	209	100	4.26±0.17
30	112	150	27.31±1.91

图4 不同设备数量下的平均系统效用

Fig.4 Average system utility with different numbers of devices

图5 不同设备数量下的平均卸载任务数

Fig.5 Average offloaded task numbers with different numbers of devices

图6 不同任务类型对平均系统效用的影响

Fig.6 The influence of different task types on average system utility

图7 近似区域对系统效用的影响

Fig.7 Influence of approximate region on system utility

参考文献 26

1	ABBAS N, ZHANG Y, TAHERKORDI A, et al. Mobile edge computing: a survey. IEEE Internet of Things Journal, 2018, 5(1): 450- 465. doi: 10.1109/JIOT.2017.2750180
2	张开元, 桂小林, 任德旺, 等. 移动边缘网络中计算迁移与内容缓存研究综述. 软件学报, 2019, 30(8): 2491- 2516. URL
	ZHANG K Y, GUI X L, REN D W, et al. Survey on computation offloading and content caching in mobile edge networks. Journal of Software, 2019, 30(8): 2491- 2516. URL
3	GIUST F, SCIANCALEPORE V, SABELLA D, et al. Multi-access edge computing: the driver behind the wheel of 5G-connected cars. IEEE Communications Standards Magazine, 2018, 2(3): 66- 73. doi: 10.1109/MCOMSTD.2018.1800013
4	WU Y, QIAN L P, NI K J, et al. Delay-minimization nonorthogonal multiple access enabled multi-user mobile edge computation offloading. IEEE Journal of Selected Topics in Signal Processing, 2019, 13(3): 392- 407. doi: 10.1109/JSTSP.2019.2893057
5	SHU C, ZHAO Z W, HAN Y P, et al. Multi-user offloading for edge computing networks: a dependency-aware and latency-optimal approach. IEEE Internet of Things Journal, 2020, 7(3): 1678- 1689. doi: 10.1109/JIOT.2019.2943373
6	WANG X J, WEI X, WANG L. A deep learning based energy-efficient computational offloading method in Internet of vehicles. China Communications, 2019, 16(3): 81- 91.
7	FU Y R, YANG X L, YANG P, et al. Energy-efficient offloading and resource allocation for mobile edge computing enabled mission-critical Internet-of-things systems. EURASIP Journal on Wireless Communications and Networking, 2021, 2021(1): 1- 16. doi: 10.1186/s13638-020-01861-8
8	TRAN T X, POMPILI D. Joint task offloading and resource allocation for multi-server mobile-edge computing networks. IEEE Transactions on Vehicular Technology, 2019, 68(1): 856- 868. doi: 10.1109/TVT.2018.2881191
9	ZHANG Q, GUI L, HOU F, et al. Dynamic task offloading and resource allocation for mobile-edge computing in dense cloud RAN. IEEE Internet of Things Journal, 2020, 7(4): 3282- 3299. doi: 10.1109/JIOT.2020.2967502
10	CAO H J, CAI J. Distributed multiuser computation offloading for cloudlet-based mobile cloud computing: a game-theoretic machine learning approach. IEEE Transactions on Vehicular Technology, 2018, 67(1): 752- 764. doi: 10.1109/TVT.2017.2740724
11	QI P, SHU H, ZHU Q. Reliability and mobility aware task offloading strategy and scheduling algorithm in wisdom medical scenario. Journal of Intelligent & Fuzzy Systems, 2021, 40(3): 5255- 5273.
12	CHEN S Y, CHEN H P, RUAN J T, et al. Context-aware online offloading strategy with mobility prediction for mobile edge computing[C]//Proceedings of International Conference on Computer Communications and Networks. Washington D. C., USA: IEEE Press, 2021: 1-9.
13	LU Y F, CHEN Z Z, GAO Q H, et al. A mobility-aware and sociality-associate computation offloading strategy for IoT. Wireless Communications and Mobile Computing, 2021, 26(3): 1- 12.
14	DAI B, NIU J W, REN T, et al. Toward mobility-aware computation offloading and resource allocation in end-edge-cloud orchestrated computing. IEEE Internet of Things Journal, 2022, 9(19): 19450- 19462. doi: 10.1109/JIOT.2022.3168036
15	ZHAN W H, LUO C B, MIN G Y, et al. Mobility-aware multi-user offloading optimization for mobile edge computing. IEEE Transactions on Vehicular Technology, 2020, 69(3): 3341- 3356. doi: 10.1109/TVT.2020.2966500
16	LIU Y Q, LIU C B, LIU J, et al. Mobility-aware and code-oriented partitioning computation offloading in multi-access edge computing. Journal of Grid Computing, 2022, 20(2): 11. doi: 10.1007/s10723-022-09599-x
17	XIE Y, SUN Y Y, XU F, et al. The offloading algorithm of mobile edge computing considering mobility in the intelligent inspection scenario. Transactions on Emerging Telecommunications Technologies, 2022, 33(7): 44- 57.
18	HU H, WANG Q, HU R Q, et al. Mobility-aware offloading and resource allocation in a MEC-enabled IoT network with energy harvesting. IEEE Internet of Things Journal, 2021, 24(8): 17541- 17556.
19	ZHAO H L, DENG S G, ZHANG C, et al. A mobility-aware cross-edge computation offloading framework for partitionable applications[C]//Proceedings of IEEE International Conference on Web Services. Washington D. C., USA: IEEE Press, 2019: 193-200.
20	LI C X, WANG H, SONG R F. Mobility-aware offloading and resource allocation in NOMA-MEC systems via DC. IEEE Communications Letters, 2022, 26(5): 1091- 1095. doi: 10.1109/LCOMM.2022.3154434
21	JAHANDAR S, KOUHALVANDI L, SHAYEA I, et al. Mobility-aware offloading decision for multi-access edge computing in 5G networks. Sensors, 2022, 22(7): 2692. doi: 10.3390/s22072692
22	刘明明, 崔春风, 童小娇, 等. 混合整数非线性规划的算法软件及最新进展. 中国科学: 数学, 2016, 46(1): 1- 20. URL
	LIU M M, CUI C F, TONG X J, et al. Algorithms, softwares and recent developments of mixed integer nonlinear programming. Scientia Sinica(Mathematica), 2016, 46(1): 1- 20. URL
23	BOYD S, VANDENBERGHE L, FAYBUSOVICH L. Convex optimization. IEEE Transactions on Automatic Control, 2006, 51(11): 1859. doi: 10.1109/TAC.2006.884922
24	YAO Y, QIN Y, FENG W, et al. KFTO: Kuhn-Munkres based fair task offloading in fog networks. Computer Networks, 2021, 195, 108131. doi: 10.1016/j.comnet.2021.108131
25	SONMEZ C, OZGOVDE A, ERSOY C. EdgeCloudSim: an environment for performance evaluation of edge computing systems. Transactions on Emerging Telecommunications Technologies, 2018, 29(11): 39- 44.
26	杨天, 杨军. 移动边缘计算中的卸载决策与资源分配策略. 计算机工程, 2021, 47(2): 19- 25. URL
	YANG T, YANG J. Offloading decision and resource allocation strategy in mobile edge computing. Computer Engineering, 2021, 47(2): 19- 25. URL

[1]	梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.
[2]	蔡星娟, 郭彦亨, 赵天浩, 张文生. 基于进化多任务的边缘计算服务部署和任务卸载[J]. 计算机工程, 2023, 49(7): 1-9.
[3]	李强, 仪晋辉, 杜婷婷, 王胜春. 移动边缘计算中基于A3C的依赖任务卸载与资源分配[J]. 计算机工程, 2023, 49(6): 42-52.
[4]	罗华峰, 沈奕菲, 阮黎翔, 杜奇伟, 郑翔, 陈智麒, 张胜. 边缘环境下面向实时目标检测的帧卸载调度算法[J]. 计算机工程, 2023, 49(5): 295-301,309.
[5]	郑丽萍, 赵玉娟, 费选. 基于改进MOEA/D的车联网通信资源分配算法[J]. 计算机工程, 2023, 49(5): 191-197.
[6]	杨立伟, 贾博宇, 王芳, 彭祥原. 可见光通信与WiFi异构网络资源管理算法[J]. 计算机工程, 2023, 49(3): 203-210,220.
[7]	谢娜, 谭文安, 曹彦, 赵璐. 移动边缘计算中安全信息流建模与分析[J]. 计算机工程, 2022, 48(5): 35-42,52.
[8]	张伟成, 卫红权, 刘树新, 王庚润. 面向5G MEC基于行为的用户异常检测方案[J]. 计算机工程, 2022, 48(5): 27-34.
[9]	郑振康, 周金和. 面向多租户网络资源分配的博弈优化策略[J]. 计算机工程, 2022, 48(5): 170-177.
[10]	宋勇春, 王茜竹, 高正念. 基于HAGA的D2D-NOMA资源分配优化算法[J]. 计算机工程, 2022, 48(2): 275-280,290.
[11]	刘振鹏, 郭超, 王仕磊, 陈杰, 李小菲. 基于博弈论和启发式算法的超密集网络边缘计算卸载[J]. 计算机工程, 2022, 48(12): 54-61,71.
[12]	于晶, 鲁凌云, 李翔. 车联网中基于DDQN的边云协作任务卸载机制[J]. 计算机工程, 2022, 48(12): 156-164.
[13]	姚政, 吴怀宇, 陈洋. 基于两阶段优化的并发流任务计算卸载策略[J]. 计算机工程, 2022, 48(12): 62-71.
[14]	曾蓉晖, 林兵, 王明芬, 林凯, 卢宇. 超密集边缘计算网络中面向能耗优化的任务卸载方法[J]. 计算机工程, 2022, 48(11): 39-48.
[15]	冯浩, 郭彩丽. 车联网中视频内容理解任务的计算卸载决策研究[J]. 计算机工程, 2022, 48(1): 135-141,148.

选择文件类型/文献管理软件名称

选择包含的内容