基于边缘计算的多目标任务调度方法

摘要： 针对智能工厂中的边缘算力资源调度问题，提出基于边缘计算的多目标任务调度模型； 以最小化任务时延和任务能耗为目标函数，添加传输时延、 计算时延、 排队时延、 迁移时延、 传输能耗、 计算能耗、 迁移能耗等7项约束条件建模； 为了解决多目标调度求解问题，提出基于任务紧急度的资源调度与分配算法，并设置迁移判断中服务器选择和任务排序方法； 以占地面积为1.2×104 m2的智能工厂的边云设备为实验环境，对比基于任务紧急度的资源调度与分配算法与随机接入资源分配算法、 迭代资源分配算法的平均任务完成率。结果表明，基于任务紧急度的资源调度与分配算法的服务器任务完成率较其他2种算法分别提高48、 5个百分点，大多数服务器的任务丢弃率被降至2%～4%，并且对系统负载均衡等问题的处理效果显著。

关键词： 生产任务调度； 多目标优化； 边缘计算； 边云协同

中图分类号： TP301

文献标志码： A

开放科学识别码（OSID码）：

Multi-objective Task Scheduling Method Based on Edge Computing

XIE Yanyu CHEN Lansun2

（1. School of General Education， Minnan Science and Technology College， Quanzhou 362332， Fujian， China;

2. Academy of Mathematics and Systems Science， Chinese Academy of Sciences， Beijing 100190， China）

Abstract： Aiming at the scheduling problem of edge computing resources in industrial intelligent factories， a multi-objective task scheduling model based on edge computing was proposed. With the objective function of minimizing task delay and task energy consumption， seven constraints such as transmission delay， computing delay， queuing delay， migration delay， transmission energy consumption， computing energy consumption and migration energy consumption were added for modeling. In order to solve the multi-objective scheduling problem， a resource scheduling and allocation algorithm based on task urgency （RSA_TU） was proposed， and the methods of server selection and task sequencing in migration judgment were set. Taking the edge cloud equipment of a smart factory covering an area of 12 000 m2 as an experimental environment， RSA_TU algorithm was compared with the random-access resource allocation algorithm and iterative resource allocation algorithm based on greedy search in average mandate completion rate. The results show that the server task completion rate of RSA_TU algorithm is improved by 48 percentage points and 5 percentage points respectively compared with the other two algorithms， and the discard rate of most servers is reduced to 2% to 4%， which reflects the remarkable effect of the proposed algorithm on system load balancing and other issues.

Keywords： production task scheduling; multi-objective optimization; edge computing; edge-cloud collaboration

边缘化网络计算已成为网络计算架构的新趋势。在实际应用中，边缘节点的计算能力可能是有限的， 当大量移动设备将任务调度到同一边缘节点时， 可能导致任务处理延迟增加， 甚至导致任务被放弃。 为了解决该问题， 一些研究者考虑诸如任务传输速率、调度速率以及设备处理能力等因素， 利用凸优化方法求解最优的任务调度决策， 以最小化任务的计算延迟和边缘计算环境中的工作流调度问题。例如， Sun等^［1］将调度问题转变为整数规划问题， 并采用贪婪搜索策略和复合启发式算法确保解的质量。Meng等^［2］提出基于新的截止日期的贪婪调度算法。彭青蓝等^［3］以任务优先级加权的卸载响应时间为评价指标， 提出一种去中心化的在线任务调度与资源分配方法， 能够减少34.21%的加权任务卸载响应时间。 Han等^［4］综合考虑所有任务的计算时间对用户服务体验的影响， 提出一种任务调度方法， 旨在最小化所有任务的加权处理时间。 巨涛等^［5］在改进深度强化学习模型的基础上， 提出自适应边缘计算任务调度方法， 能充分利用边缘计算资源改善任务处理的实时性， 降低系统能耗。

在处理任务调度问题时，上述凸优化方法和启发式方法具有较高的计算效率和可解释性^［6-7］，但在面对复杂的边缘计算场景时，通常需要场景的全部信息，导致在处理复杂场景时变得困难，难以优化得出良好的调度策略。此外，在复杂的边缘计算场景中，任务之间的依赖关系和所需的计算资源通常难以精确建模，传统方法的准确性和可靠性受到挑战。本文中结合边云协同与算力组网的理念，建立基于边缘计算的多目标任务调度模型，考虑包含静态设备、 巡检机器人、 边缘服务器和边缘网络链路的智能工厂层次边缘网络，旨在最小化任务的总体时延和能耗。

1 边缘计算

随着物联网技术的飞速发展，移动边缘计算（MEC）^［8-9］作为一项减轻云端压力的解决方案，备受研究者的广泛关注。早期MEC的发展受益于内容分发网络技术（CDN）的兴起^［10］。随着时间推移，CDN提供的数据备份功能无法满足用户日益增长的任务处理需求，目前的边缘计算不再局限于内容分发和缓存管理，而是利用边缘服务器强大的计算能力为终端设备提供低延迟的计算服务，成为边缘计算的另一个重要功能^［11］。典型的3层边缘计算框架包括具有强大计算能力的云计算层、 距离终端设备较近的具有较强处理能力的边缘层以及终端设备层，如图1所示。

终端设备层由各式各样的物联网终端设备所组成，由于这些终端设备自身计算能力的限制，在大多数场景下无法满足产生的任务日益增长的时敏性需求^［12-13］，因此，在面对计算密集及延迟敏感型任务时，终端设备层通常将此类任务调度到边缘层处理或通过边缘层进一步传输到云计算层处理。边缘层是3层边缘计算框架的核心，主要由位于网络边缘位置的智能化基站、 边缘网关以及路由器等设备所组成^［14］。由于这些边缘层设备距离终端设备较近，因此可以将终端设备上的时敏性任务传输到边缘层处理，或者通过边缘层将任务传输至计算能力更强的云计算层处理，从而有效减少云计算层和核心网的负载。云计算层主要通过软件定义网络、 网络功能虚拟化等虚拟化技术，封装大规模集群式计算资源，根据实际动态的需求管理计算资源，为终端设备提供计算服务^［15-16］。

2 基于边缘计算的多目标任务调度模型

2.1 系统建模

本文中定义的智能工厂层次边缘网络协作架构为W=（M∪N∪E∪C， L）， 其中， M为静态设备， N为巡检机器人， E为边缘服务器， L为边缘网络链路。

以下逐一描述模型的7项约束条件。

2.1.1 传输时延

传输时延不仅包括数据在有线信道传输的时间，还包括数据在光纤中传递的时间。任务量AM，t为静态设备M在t时刻通过光纤连接到边缘服务器E的距离为SM，E，传输时延TtM，t的表达式为

TtM，t=AM，tvnet+SM，Evlig ，（1）

式中： vnet与vlig分别为网络和光信号在无线信道中的传输速度。

本文中使用时分复用的传输模式，以保证任务在无线信道上传输至边缘服务器时不会相互干扰。根据香农（Shannon）公式，计算得到t时刻巡检机器人N能够达到的最大传输速率vN，t为

vN，t=BN，tlog21+PN，tP′N，t

，（2）

式中： BN，t为巡检机器人N在t时刻上传处理任务时分配的上行信道带宽； PN，t与P′N，t分别为巡检机器人N在t时刻的上传功率和噪声功率。

信道增益GN，t的计算公式为

GN，t=λ4π（xE-xN，t）2+（yE-yN，t）2 ，（3）

式中：（xE， yE）为边缘服务器E的坐标； （xN，t， yN，t）为巡检机器人N在t时刻的实时坐标。

2.1.2 计算时延

将静态设备M和巡检机器人N统称为终端设备K， t时刻待处理任务量为AK，t，则本地终端设备K的计算时延TcK，t为

TcK，t=HE，tAK，tfE，t ，（4）

式中HE，t和fE，t分别为边缘服务器E在t时刻的中央处理器（CPU）的计算能力和频率。

2.1.3 排队时延

对本地层终端设备产生的待处理任务的紧急度记为δK，t，设ts为单位时隙，当t≥ts时，有UK，t=AM，t和δK，t=δK，t-ts，其中UK，t为t时刻终端设备K无法处理的任务量。本地终端设备K的排队时延TqK，t计算公式为

TqK，t=HE，tAE，tfE，t ，（5）

式中AE，t为边缘服务器E在t时刻的任务量。

2.1.4 迁移时延

设Tp（E，E′）表示任务从边缘服务器E迁移到边缘服务器E′所经过的路径上的时延，其中路径包括了起始点、 终止点以及中间经过的所有边缘服务器，则链路时延TlK，t计算公式为

TlK，t=σTp（E，E′） ，（6）

式中σ为固定的链路时延系数。

综合考虑传输、 计算、 等待时延以及路径时延，可以得到任务迁移总时延TmK，t为

TmK，t=TtM，t+TcK，t+TqK，t+TlK，t 。（7）

2.1.5 传输能耗

巡检机器人N与边缘服务器E之间天线连接的传输能耗RtN，t为

RtN，t=TtN，tPN，t ，（8）

式中TtN，t为巡检机器人N在t时刻的传输时延。

2.1.6 计算能耗

终端设备K在特定时刻产生的任务，经过直连边缘服务器进行处理时的计算能耗RcK，t为

RcK，t=αEHE，tAK，t f2E，t ，（9）

式中αE为边缘服务器E中芯片的有效电容系数。

2.1.7 迁移能耗

迁移能耗为边缘服务器E迁入到另一边缘服务器E′中产生的消耗，计算公式为

RmK，t=αE′HE′，tAK，t f2E′，t 。（10）

式中： αE′为边缘服务器E′中芯片的有效电容系数； HE′，t、 fE′，t分别为边缘服务器E′在t时刻的CPU的计算能力和频率。

2.2 问题描述

在多目标任务中，当迁移时延不为0时，须要应调整原计算和排队时延，总时延在系统中的计算表达为Tt=TtM，t+TqK，t。在原有模型基础上，引入不同任务紧急度作为系数，如果存在任务迁移，则系统在某一时刻产生的总能耗为计算能耗和迁移能耗的总和，即

Rt=RcN，t+RmK，t 。（11）

综上，任务紧急度已融入到时延中，则最小化总体时延和能耗的目标函数为

f=min（T+γR） ，（12）

式中： T为系统总时延； R为系统总能耗； γ为时延和能耗平衡系数。

2.3 基于边缘计算的多目标任务调度问题求解

为了求解上述多目标任务调度问题， 本文提出了一种基于任务紧急度感知的算力资源调度和分配（RSA_TU）算法， 其核心思想是对待处理任务排序， 并根据服务器的处理能力判断是否迁移任务。 设TmaxK，ts为单位时隙ts时本地终端设备K集合的最大排队时延。

RSA_TU算法的输入和输出分别为多目标任务调度模型和调度结果。首先，初始化时间变量t=0时； 然后进入一个循环结构， 条件是时间t小于总时间长度。 在这个循环中， 终端设备K集合根据设备坐标匹配服务器， 同时边缘服务器E集合根据名下所有待处理任务次序排列。 设边缘服务器E集合在单位时隙ts的最大排队时延为T^maxE，ts， 如果T^maxE，tsgt;T^maxK，ts， 则更新待处理任务矩阵信息； 否则， 更新不处理任务矩阵信息。记录不处理任务矩阵中的最大紧急度阈值Nmax， 如果当前设备的任务紧急度δM，t小于Nmax，则将其转移至不处理任务矩阵，并重新排序。

在任务处理过程中， 边缘服务器每个时隙都会更新任务排序， 确保新到达的任务被及时添加到处理队列中， 这意味着每个任务都必须在同一时隙内在某个边缘服务器上完成处理。 该处理机制确保了任务的有序执行， 同时避免了因大任务而导致的任务积压问题。 整个迁移判断和选择过程如图2所示。

在资源调度与分配过程中， 首先要识别和分类接收到的任务^［17-18］。 基于对边缘计算节点资源状态的实时监测， 包括CPU利用率、 内存利用率和网络带宽等信息， 将任务分为不同的优先级和处理要求。

在任务识别与资源监测的基础上， 系统自动评估每个任务的紧急度， 综合考虑任务的截止时间、 重要性等因素。 随后， 系统根据任务的紧急度和当前资源状态作出资源调度决策。 对于高紧急度的任务， 系统优先选择资源充足、 响应速度快的节点用于分配，以确保及时完成任务。 对于低紧急度的任务， 则选择资源利用率较低的节点， 实现资源的均衡利用。 一旦完成资源调度决策，系统就将任务分配给相应的边缘节点， 并启动执行。 在任务执行过程中， 系统持续监测资源利用情况和任务执行进度， 并根据需要动态调整。 这种动态调整与优化确保了系统在面对不同负载和任务情况时能够灵活适应， 提高了系统的性能和响应速度。

边缘算力资源调度任务处理和排序过程如图3所示。针对服务器的虚拟处理情况，根据任务排序，各服务器在同一时隙内处理任务，避免任务迁移。若每台服务器可完全处理自身任务，则考虑更新处理结果。当服务器算力不足时，系统根据紧急程度决定是否迁移任务，将低紧急度任务重新分配。

3 实验与结果分析

3.1 实验环境及设置

实验基于占地面积为1.2×104 m2的智能工厂，边缘服务器、 云中心、 分布式单元、 本地终端设备、 传感设备的数量分别设置为8、 2、 6、 400、 180。

设定边缘服务器CPU周期数为6×10^-6，数据加

密级别为AES-256， 单位时隙为1 ms。当任务因失效而被丢弃时，排队时长被统一设定为0.05 ms。采用泊松分布模拟终端设备的任务时间流，数据存储量为0～50 KiB。

3.2 仿真结果分析

为了评估本文RSA_TU算法的特性， 引入Chen等^［19］提出的基于预测的随机接入资源分配算法（PRARA）、 Fan等^［20］提出的基于贪婪搜索的迭代资源分配算法（IGS）作对比， 实验中不同边缘服务器的任务完成率如表1和图4所示。

PRARA算法—基于预测的随机接入资源分配算法； IGS算法—基于贪婪搜索的迭代资源分配算法；

RSA_TU算法—基于任务紧急度感知的算力资源调度和分配算法。

在PRARA算法应用中， 除5号服务器外， 其他服务器的任务完成率为19%～40%。 在IGS算法应用中， 各服务器的平均任务完成率相对平稳， 为61%～81%， 总平均完成率为72%。 本文提出的 RSA_TU算法在8个服务器中的平均任务完成率为66%～86%， 总平均任务完成率约为77%，较PRARA、 IGS算法分别提高了48、 5个百分点。

此外，针对因排队时间过长而被丢弃的任务，本文中采用任务丢弃率量化分析，图5为不同算法在不同边缘服务器的任务丢弃率雷达图。由图可知，在PRARA算法应用中，除3号服务器外，其他服务器的任务丢弃率普遍较高，达到12%～17%。IGS算法虽然在1、 2、 5、 7、 8号服务器的任务丢弃率降低，但其他服务器的改善有限，任务丢弃率仍为10%左右。本文中提出的RSA_TU算法显著降低任务丢弃率，大多数服务器的任务丢弃率降至2%～4%，多边形的面积差异也反映了该算法对系统负载均衡等问题的显著处理效果。

4 结语

针对智能工厂中的边缘算力资源受限的调度问题， 本文中建立了以最小化任务时延、 任务能耗为目标函数， 以7项不同时延、 能耗指标为约束条件的多目标调度模型。 为了求解此多目标调度模型， 本文中提出RSA_TU算法， 建立任务紧急度评价方法， 提出迁移判断中的服务器选择和任务排序方法。以智能工厂边缘云设备为实验环境， 对比实验结果显示， RSA_TU算法的服务器任务完成率较PRARA、 IGS算法分别提高48、 5个百分点， 且大多数服务器的任务丢弃率被降至2%～4%， 表明该算法在系统负载均衡等方面具有显著的优势。

参考文献：

［1］ SUN J， YIN L， ZOU M H， et al. Makespan-minimization workflow scheduling for complex networks with social groups in edge computing［J］. Journal of Systems Architecture， 2020， 108： 101799.

［2］ MENG J Y， TAN H S， LI X Y， et al. Online deadline-aware task dispatching and scheduling in edge computing［J］. IEEE Transactions on Parallel and Distributed Systems， 2019， 31（6）： 1271.

［3］ 彭青蓝， 夏云霓， 郑万波， 等. 一种去中心化的在线边缘任务调度与资源分配方法［J］. 计算机学报， 2022， 45（7）： 1464.

［4］ HAN Z H， TAN H S， LI X Y， et al. Ondisc： online latency-sensitive job dispatching and scheduling in heterogeneous edge-clouds［J］. IEEE/ACM Transactions on Networking， 2019， 27（6）： 2475.

［5］ 巨涛， 王志强， 刘帅， 等. D3DQN-CAA：一种基于DRL的自适应边缘计算任务调度方法［J］. 湖南大学学报（自然科学版）， 2024， 51（6）： 76.

［6］ LUO S Q， CHEN X， WU Q， et al. HFEL： joint edge association and resource allocation for cost-efficient hierarchical federated edge learning［J］. IEEE Transactions on Wireless Communications， 2020， 19（10）： 6535.

［7］ 肖烨. 面向智能工厂的边缘计算节点部署及节能技术研究［D］. 北京： 北京邮电大学， 2021： 37.

［8］ 狄筝， 曹一凡， 仇超， 等. 新型算力网络架构及其应用案例分析［J］. 计算机应用， 2022， 42（6）： 1656.

［9］ ZENG L， LIU Q， SHEN S G， et al. Improved double deep Q network-based task scheduling algorithm in edge computing for make-span optimization［J］. Tsinghua Science and Technology， 2023， 29（3）： 806.

［10］ 张依琳， 梁玉珠， 尹沐君， 等. 移动边缘计算中计算卸载方案研究综述［J］. 计算机学报， 202 44（12）： 2406.

［11］ FENG Y X， HONG Z X， LI Z W， et al. Integrated intelligent greenschedulingofsustainableflexibleworkshopwithedgecomputingconsideringuncertain machine state［J］. Journal of Cleaner Production， 2020， 246： 119070.

［12］ PAN Z Y， HOU X H， XU H， et al. A hybrid manufacturing scheduling optimization strategy in collaborative edge computing［J］. Evolutionary Intelligence， 2022， 17（2）： 1065.

［13］ 刘泽宁， 李凯， 吴连涛， 等. 多层次算力网络中代价感知任务调度算法［J］. 计算机研究与发展， 2020， 57（9）： 1810.

［14］ WANG X F， HAN Y W， LEUNG V C M， et al. Convergence of edge computing and deep learning： a comprehensive survey［J］. IEEE Communications Surveys amp; Tutorials， 2020， 22（2）： 869.

［15］ WANG J， LIU Y， REN S， et al. Edge computing-based real-time scheduling for digital twin flexible job shop with variable time window［J］. Robotics and Computer： Integrated Manufacturing， 2023， 79： 102435.

［16］ TANG M， WONG V W S. Deep reinforcement learning for task offloading in mobile edge computing systems［J］. IEEE Transactions on Mobile Computing， 2020， 21（6）： 1985.

［17］ YEGANEH S， SANGAR A B， AZIZI S. A novel Q-learning-based hybrid algorithm for the optimal offloading and scheduling in mobile edge computing environments［J］. Journal of Network and Computer Applications， 2023， 214： 103617.

［18］ ZHOUMT，RENTF，DAIZ M， et al. Task scheduling and resource balancing of fog computing in smart factory［J］. Mobile Networks and Applications， 2023， 28： 19.

［19］ CHEN Y W， YOU J Z. Effective radio resource allocation for IoT randomaccessbyusingreinforcementlearning［J］. Journal of Internet Technology， 2022， 23（5）： 1070-1071.

［20］ FAN Y Q， WANG L F， WU W L， et al. Cloud/edge computing resource allocation and pricing for mobile blockchain： an iterative greedy and search approach［J］. IEEE Transactions on Computational Social Systems， 202 8（2）： 461-462.

（责任编辑：刘 飚）