边缘协作环境下最小化完工时间任务调度方法

doi:10.19665/j.issn1001-2400.20240308

Abstract

Abstract:

The uneven geographical distribution of users may lead to unbalanced load on edge servers,which makes it difficult to provide satisfactory service quality for users.In addition,the available resources of the edge server are limited,and some large tasks may be difficult to offload to the edge server.To solve the above problems,this paper proposes a task scheduling method to minimize the completion time in the edge collaboration environment by utilizing the collaboration among multiple edge servers and combining the task partial offloading technology.First,by combining the edge of horizontal collaboration and task partial offloading technology and considering the position relationship between users and edge servers in multi-user multi-edge server scenario,a task partial offloading and scheduling model is established to minimize the task completion time.Second,a task scheduling algorithm based on the Improved Group Teaching Optimization Algorithm(IGTOA) is proposed to jointly optimize the edge server computing resource allocation,user-edge server association decision,task offloading ratio and execution location decision.With minimizing the task completion time as the goal,efficient task scheduling is achieved under edge computing environment.Finally,the proposed task scheduling algorithm is compared with DTOSO,HJTORA and ACS algorithms under multiple indexes.Experimental results show that the proposed method can effectively reduce the task completion time.

Key words: edge collaboration, partial offloading, scheduling algorithm, group teaching optimization algorithm

CLC Number:

TP301.6

ZHANG Chao, ZHAO Hui, ZHANG Zhifeng, WANG Jing, WAN Bo, WANG Quan. Task scheduling method for minimizing completion time in edge collaborative environment[J].Journal of Xidian University, 2024, 51(4): 114-127.

Figures/Tables 5

References 22

[1]	LIANG Y, WANG W, ZHENG X, et al. Collaborative Edge Service Placement for Maximizing QoS with Distributed Data Cleaning[C]//2023 IEEE/ACM 31st International Symposium on Quality of Service(IWQoS).Piscataway:IEEE, 2023: 1-4.
[2]	宋宇波, 金星妤, 燕锋, 等. 车联网中移动边缘计算的安全高效节能卸载策略[J]. 清华大学学报(自然科学版), 2021, 61(11):1246-1253.
	SONG Yubo, JING Xingyu, YAN Feng, et al. Secure and Energy Efficient Offloading of Mobile Edge Computing in the Internet of Vehicles[J]. Journal of Tsinghua University(Science and Technology), 2021, 61(11):1246-1253.
[3]	YUAN H, ZHOU M C. Profit-Maximized Collaborative Computation Offloading and Resource Allocation in Distributed Cloud and Edge Computing Systems[J]. IEEE Transactions on Automation Science and Engineering, 2020, 18(3):1277-1287.
[4]	DING Y, LI K, LIU C, et al. A Potential Game Theoretic Approach to Computation Offloading Strategy Optimization in End-Edge-Cloud Computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 33(6):1503-1519.
[5]	ZHOU T, YUE Y, QIN D, et al. Joint Device Association,Resource Allocation,and Computation Offloading in Ultradense Multidevice and Multitask IoT Networks[J]. IEEE Internet of Things Journal, 2022, 9(19):18695-18709.
[6]	赵辉, 冯南之, 王泉, 等. 面向边缘计算平台的半线上任务动态调度方法[J]. 西安电子科技大学学报, 2021, 48(6):8-15.
	ZHAO Hui, FENG Nanzhi, WANG Quan, et al. Dynamic Semi-Online Task Scheduling Method for the Edge Computing Platform[J]. Journal of Xidian University, 2021, 48(6):8-15.
[7]	彭青蓝, 夏云霓, 郑万波, 等. 一种去中心化的在线边缘任务调度与资源分配方法[J]. 计算机学报, 2022, 45(7):1462-1477.
	PENG Qinglan, XIA Yunni, ZHENG Wanbo, et al. A Decentralized Approach to Online Edge Task Scheduling and Resource Allocation[J]. Journal of Computer Science, 2022, 45(7):1462-1477.
[8]	WANG K, CHEN W, LI J, et al. Joint Task Offloading and Caching for Massive MIMO-Aided Multi-Tier Computing Networks[J]. IEEE Transactions on Communications, 2022, 70(3):1820-1833.
[9]	邝祝芳, 陈清林, 李林峰, 等. 基于深度强化学习的多用户边缘计算任务卸载调度与资源分配算法[J]. 计算机学报, 2022, 45(4):812-824.
	KUANG Zhufang, CHEN Qinglin, LI Linfeng, et al. Task Offloading Scheduling and Resource Allocation Algorithm for Multi-User Edge Computing Based on Deep Reinforcement Learning[J]. Journal of Computer Science, 2022, 45(4):812-824.
[10]	NING Z, DONG P, WANG X, et al. Partial Computation Offloading and Adaptive Task Scheduling for 5G-Enabled Vehicular Networks[J]. IEEE Transactions on Mobile Computing, 2020, 21(4):1319-1333.
[11]	MALIK R, VU M. On-Request Wireless Charging and Partial Computation Offloading in Multi-Access Edge Computing Systems[J]. IEEE Transactions on Wireless Communications, 2021, 20(10):6665-6679.
[12]	ZHANG W, ZHANG Z, ZEADALLY S, et al. Energy-Efficient Workload Allocation and Computation Resource Configuration in Distributed Cloud/Edge Computing Systems with Stochastic Workloads[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(6):1118-1132.
[13]	HU S, LI G. Dynamic Request Scheduling Optimization in Mobile Edge Computing for IoT Applications[J]. IEEE Internet of Things Journal, 2020, 7(2):1426-1437.
[14]	ELGENDY I A, ZHANG W Z, HE H, et al. Joint Computation Offloading and Task Caching for Multi-User and Multi-Task MEC Systems:Reinforcement Learning-Based Algorithms[J]. Wireless Networks, 2021, 27(3):2023-2038.
[15]	LIU X, YU J, WANG J, et al. Resource Allocation with Edge Computing in IoT Networks via Machine Learning[J]. IEEE Internet of Things Journal, 2020, 7(4):3415-3426.
[16]	LIU X, ZHAO X, LIU G, et al. Collaborative Task Offloading and Service Caching Strategy for Mobile Edge Computing[J]. Sensors, 2022, 22(18):6760.
[17]	RAO H, JIA H, WU D, et al. A Modified Group Teaching Optimization Algorithm for Solving Constrained Engineering Optimization Problems[J]. Mathematics, 2022, 10(20):3765.
[18]	ZHANG Y, JIN Z. Group Teaching Optimization Algorithm:A Novel Metaheuristic Method for Solving Global Optimization Problems[J]. Expert Systems with Applications, 2020,148:113246-113264.
[19]	GUO F, ZHANG H, JI H, et al. An Efficient Computation Offloading Management Scheme in the Densely Deployed Small Cell Networks with Mobile Edge Computing[J]. IEEE/ACM Transactions on Networking, 2018, 26(6):2651-2664.
[20]	MAHMOOD A, HONG Y, EHSAN M K, et al. Optimal Resource Allocation and Task Segmentation in IoT Enabled Mobile Edge Cloud[J]. IEEE Transactions on Vehicular Technology, 2021, 70(12):13294-13303.
[21]	LIU Z, FAN J, GENG S, et al. Joint Optimization of Task Offloading and Computing Resource Allocation in MEC-D2D Network[C]//2022 IEEE 5th International Conference on Computer and Communication Engineering Technology(CCET).Piscataway:IEEE, 2022: 256-260.
[22]	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.

参数	值
用户数量	20~120
边缘服务器数量	9
路径损失因子	4
边缘服务器无线信号覆盖半径/m	200
信道背景噪声功率/dBm	-100
用户设备上传功率/mW	100
边缘服务器通信带宽/MHz	[10,50]
用户设备本地计算能力/GHz	1
边缘服务器计算能力/GHz	[20,60]
边缘服务器间有线链路带宽/(Mb·s^-1)	500
任务输入数据大小/MB	[0.5,50]
任务所需计算量大小/GHz	[1,10]

Task scheduling method for minimizing completion time in edge collaborative environment

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 22

Related Articles 5

Metrics

Comments

Recommended 0

[1]	ZHANG Yupeng,WU Zili,CHEN Ming,ZHANG Lulu. Optimization of task scheduling oriented to cross microservice chains [J]. Journal of Xidian University, 2021, 48(6): 32-39.
[2]	XU Lin;QU Shiru;YU Bin. Research on distributed resources scheduling strategy in the ITSGrid [J]. J4, 2014, 41(3): 203-208.
[3]	GAO Ya;QIU Zhiliang;ZHANG Maosen;LI Jun. Integrating unicast and multicast traffic scheduling in Clos-network switches [J]. J4, 2013, 40(1): 48-52.
[4]	SUN Peng-gang1;QUAN Yi-ning1;LIU Jun-ping2. Task scheduling based on trust mechanism of the L-fuzzy set in grid computing [J]. J4, 2008, 35(1): 110-115.
[5]	YANG Fan1;QIU Zhi-liang1;LIU Zeng-ji1;LIU Gu-qing2;YAN Jing1. A new Clos fabric with input memory and the study of its routing and scheduling algorithm [J]. J4, 2007, 34(1): 63-67.