Potential Game Based Workflow Task Offloading Optimization Mechanism in Computing Power Network
-
摘要:
边缘计算虽然部分解决了任务上云导致的时延过长的问题,但由于通常只考虑端边云间的垂直协同,不可避免出现了“算力孤岛”效用,因而仍然难以满足工作流任务的低延迟执行需求.为了高效协同利用广域网上的算力资源,降低工作流任务的执行时间,亟需对算力网络中的工作流任务卸载和资源分配问题进行研究.首先描述了算力网络环境下面向多用户的工作流任务执行场景,并对该场景下的网络环境、工作流任务及其执行流程进行建模.其次根据优化目标建立工作流执行时延模型,以构建面向算力网络环境的多用户工作流任务卸载与资源分配问题.最后根据工作流应用的特点,针对链式工作流提出了一种基于势博弈的分布式工作流卸载算法. 针对复杂DAG工作流提出一种基于动态资源权重的启发式工作流卸载算法.仿真实验表明,与其他算法相比,所提算法均能够协同广域网上的算力与网络资源,降低工作流任务的平均完成时间,从而有效提高了算力网络环境中的工作流任务的执行效率.
Abstract:Although edge computing partially solves the problem of excessive latency caused by the tasks offloading to the cloud, it inevitably has the effect of “island of computing power” because of taking only vertical collaboration among the device, edge and cloud into consideration. Thus, it is difficult to meet the low-latency execution requirements of the workflow tasks. To efficiently and collaboratively utilize computing resources on the wide area network (WAN) to reduce the completion time of workflow tasks, it is urgent to study the offloading of workflow tasks and resource allocation problem in computing power network(CPN). Firstly, the multi-user-oriented workflow tasks’ execution scenario in computing power network environment is described. Secondly, the network environment, workflow tasks and their execution procedures in this scenario are modeled. Thirdly, according to the optimization goal, a latency model is built to construct the multi-user-oriented workflow tasks’ offloading and resource allocation problem. Finally, according to the characteristics of workflow application, a decentralized workload offloading algorighm based on potential game for chain workflow and a heuristic workload offloading algorithm based on dynamic resource weight for complex direct acyclic graph (DAG) workflow is proposed. Simulation results show that, compared with the other algorithms, the proposed algorithm can collaborate the computing resource and network resource in WAN, effectively reduce the average completion time of workflow tasks, thus effectively improving the execution efficiency of workflow tasks in computing power network environment.
-
Keywords:
- edge computing /
- computing power network /
- workflow task /
- task offloading /
- potential game
-
随着人工智能与移动互联网的不断发展,远程智能监控[1]、自动驾驶[2]等为代表的新型业务应用大量涌现,这些应用通常需要消耗大量的计算资源[3]. 同时,随着应用越来越复杂,通常以微服务[4]的形式进行开发部署,此时一个应用往往可拆分成多个具有数据依赖与时序依赖关系的子任务集合,通常可表示为工作流结构[5]. 图1展示了2种典型的工作流结构:链式工作流应用和有向无环图(directed acyclic graph,DAG)式工作流应用. 链式工作流应用为一系列顺序执行的子任务,如:采用深度神经网络(deep neural network,DNN)模型(如VGG[6])对图像进行识别,其神经网络模型可表示为若干顺序执行的不同模型层次(如卷积层、池化层、全连接层等)[6-8],并可按层进行任务划分与卸载;而DAG式工作流[5,9-10]则通常由多个分支与汇聚结构组成,比如:智能道路监控需要并行执行多项子任务,可以用DAG图来描述.
目前终端设备由于计算能力有限,难以支撑工作流应用的执行[11],而云服务器虽然具有丰富的计算资源,但端云间较大的网络通信延迟[9]将极大降低工作流应用的执行性能. 边缘计算[12]通过将边缘服务器部署在靠近用户的网络边缘侧为用户提供计算资源,一方面补齐了终端算力不足的短板,另一方面降低了任务上云所带来的通信开销. 近年来已有不少相关工作[1,6-7,12-16]关注边缘计算场景下的任务卸载与执行优化问题,然而这种端边云之间的垂直协同模式通常仅考虑终端和相邻边缘计算资源的协同与卸载,无法有效融合广域范围内的算力资源,因此仍然难以满足复杂工作流的高效能、低延迟需求.
近年来,边缘服务器在网络中的广泛部署,使得算力从集中走向分布,计算从“点”到“网”逐渐成为网络基础设施的重要组成部分. 算力网络[17]通过无处不在的网络感知并连接分布式的算力节点,基于软件定义网络(software defined network,SDN)[18]的思想将路由层分为控制面和转发面,综合考虑网络和计算资源状况,将业务调度到合适的计算资源节点上.
然而,面对算力网络中网络环境高复杂强动态、算力资源高异构泛分布的特点,实现广域算网融合环境下的资源高效融合和协同是一项挑战. 具体表现在2个方面:
1)计算模式方面. 许多新兴应用其源与目的不一定相同[8],如图1中的智能道路监控,橙色实线表示数据的传输路径,道路图像由路边的摄像头采集(源),而分析的结果需要传到监控中心(目的). 若采用传统侧重于靠近终端用户的边缘计算模式,将会在源端附近完成所有计算,然后再通过广域网络进行远距离传输. 由于无法有效融合广域范围内的算力与网络资源,将导致较差的任务执行性能. 因此算力网络环境中的工作流调度需要同时考虑任务在多边缘节点间的计算与传输开销的协同分配模式,实现边传边算,传算协同.
2)问题求解方面. 广域算力网络环境和传统边缘计算环境相比,具有算力资源高异构、泛分布的特点,因此相较传统端边云间的任务卸载问题,算力网络下的任务卸载问题具有更高的复杂性(不仅需要考虑任务的卸载还要决策数据的传输路径). 除此之外,应用的复杂性和环境的动态性将进一步增加任务卸载与资源分配的求解难度.
目前针对算力网络环境下的复杂工作流任务,协同优化的工作还很少,而传统边缘计算环境下的工作流卸载的工作[9-10,19-20]无法直接适用. 为此,本文研究了算力网络环境下工作流任务的卸载与资源分配优化问题,主要贡献有3个方面:
1)分析了算力网络下的工作流任务卸载与执行模式,并提出了算力网络环境下工作流任务卸载与资源分配问题. 综合考虑了算力网络中的网络环境、计算资源以及工作流任务的拓扑信息,建立时延模型,为工作流任务卸载与资源分配问题提供优化目标.
2)针对链式工作流任务,设计并实现了一种基于势博弈[21]的分布式工作流卸载(decentralized workload offloading,DWO)算法. 首先根据卸载决策通过凸优化[22]方法得到最优资源分配方案;然后将卸载决策建模为一个加权拥塞博弈问题,并证明了该博弈是一种势博弈(至少存在一个纳什均衡解)和无政府代价[21](price of anarchy,PoA)值. 另外,针对DAG工作流任务,设计并实现了一种基于动态资源权重的启发式工作流卸载(heuristic workflow offloading, Heu-WO)算法. 该算法将每个资源的占有情况记作资源权重,每个子任务基于资源权重选择完成时间最少的节点进行卸载,并动态更新资源权重.
3)针对算力网络环境下工作流任务卸载和资源分配问题,为了验证本文所提算法的有效性,设计并实现了仿真实验. 相比较最优解,本文所提算法DWO降低了一个维度(用户维度)的时间复杂度,解的近似比高达94.6%,相比其他算法可以获得最高3.2x的加速比;本文所提算法Heu-WO的时间复杂度为多项式级别,相比其他算法可以获得最高2.8x的加速比. 从而验证了本文所提算法的有效性.
1. 相关工作
为了解决终端计算能力的限制,文献[6, 13-15]从模型切分和卸载的角度出发,研究了将任务部分卸载到边缘服务器上处理来降低任务的计算时延. 其中LEIME[6]提出了一种基于多出口DNN的低延迟边缘智能方案来解决传统多出口DNN无法提供快速且一致的推理. 首先它在模型级别,提出了一种提前退出算法,以自动构建具有较低时间复杂度的最优 ME-DNN;在计算层面,提出了一种分布式卸载机制,在运行时微调任务调度,以维持动态环境中的高性能,具有接近最优性能保证的特性. Neurosurgeon[13]所考虑的计算任务是基于AlexNet,VGG这样的链式深度神经网络模型,并按照层来考虑切分点位置,综合网络环境和终端设备算力及边缘服务器的算力,找到一个最佳的切分位置使得总体的计算时延最低或者能量开销最低. 文献[14]提出了一种将 DNN 划分为多个分区的技术,这些分区可以在本地处理或卸载到一个或多个强大的节点. 通过设计自适应 DNN 分区方案和基于匹配游戏方法卸载计算的分布式算法来加快推理速度. 文献[15]在基于正交频分多址(orthogonal frequency division multiple access,OFDMA)的协同边缘计算场景下考虑了卸载决策、协作决策、计算资源分配和通信资源分配问题. 用户的延迟敏感任务可以在本地计算,或卸载到协作设备、MEC服务器. 目标是在延迟约束下最小化所有移动用户的总能量消耗,并提出了一种两级交替方法来解决公式化的混合整数非线性规划(mixed-integer nonlinear programming,MINLP)问题. 在上层,使用启发式算法来处理初始设置下的协作决策和卸载决策;在下层,基于当前卸载决策,通过深度强化学习更新功率、子载波和计算资源的分配. 但是由于启发式算法和深度强化学习的联合算法的算法复杂度会比较高,上述工作[6,13-15]基于传统深度学习模型具有链式的特点,在研究模型切分时对于链式任务的切分难以表达现在复杂工作流任务,呈现DAG的依赖关系.
针对日益复杂的应用,文献[9-10, 19-20]研究了工作流任务的卸载问题. 其中,文献[9]研究了具有预算约束下最小化工作流任务完成时间问题,即每个移动设备的预算都是有限的,并且必须确定哪些子任务应该在本地计算或者应该发送到边缘服务器或云服务器,针对2种合作模式(单边缘服务器与云服务器协同和多边缘服务器协同),分别设计了基于贪心策略的任务卸载算法. 文献[10]研究了MEC 在依赖和服务缓存约束下的任务卸载问题,提出了一种基于表的启发式任务卸载算法,该算法能够预测卸载决策的影响. 通过使用时间消耗表来预测卸载某个子任务的影响力,从而做出卸载决策. 文献[19]研究了具有通信延迟和应用程序完成截止日期的异构处理器上的工作流任务调度,提出了一种启发式算法ITAGS,首先通过松弛原问题中的二元约束,转化成凸问题,并获得原问题最优目标的下界;然后为每个单独子任务分配截止时间;最后贪婪地优化每一子任务调度. 文献[20]提出了一种联合工作流任务卸载和流调度的启发式算法,利用每个任务图的知识和流程的开始时间来做出任务卸载决策. 文献[9-10, 19-20] 工作默认卸载是单跳的,没有考虑到算力网络环境中任务可以通过多跳的方式卸载到原本访问不到的算力节点上,即算力路由问题,难以有效利用网络中的算力资源.
为了有效利用网络中的算力资源,文献[8, 23-25]研究了任务在多跳网络环境下的卸载问题. 其中,文献[8]介绍了一种低延迟自适应工作负载分配框架,首先通过一种自适应任务划分和放置算法来利用计算网络资源. 其次,为了解决复杂的 DAG 拓扑,设计了一种分区和放置的最优寻路算法用于联合优化计算寻路和工作负载分配. 文献[23]研究了工业物联网场景下多跳计算卸载中的计算卸载和通信路由问题,以最小化每个任务的计算时间和能量消耗为目标,将联合优化问题制定成一个势博弈问题;通过一种自由约束机制来确保有限的改进路径可以达到纳什均衡,提出了一种多跳协作消息传递机制并开发了2种可以实现纳什均衡的服务质量(quality of service,QoS)感知分布式算法. 文献[24]研究了联合多任务部分计算卸载和网络流调度问题,目标是最小化所有任务的平均完成时间,提出了一种联合部分卸载和流调度的启发式算法,通过考虑设备的等待时间和网络流的开始时间来决定部分卸载率;同时使用McCormick包络将公式化的MINLP问题松弛成线性规划(linear programming,LP)问题,以提供下界. 文献[25]提出了一种避免分割网络的启发式方法和一种可以优化多跳协作网络中计算任务分配的迭代任务分配算法,来评估多跳网络中计算卸载的效果. 上述工作[8, 23-25]聚焦卸载问题,没有考虑资源分配的问题,而是事先声明一个子任务需要多少的计算资源或者考虑排队、均匀分配资源,然而对于不同任务,适当的资源分配算法对满足延迟要求是至关重要的.
综上,现有的研究工作难以适用于算力网络环境下的工作流卸载问题,因此本文以最小化平均工作流任务完成时间为目标,研究了算力网络环境下工作流任务卸载与资源分配问题.
2. 问题定义和建模
2.1 问题分析
本文旨在研究一种算力网络环境下的通用工作流任务的执行优化机制,对于许多新兴业务应用其源与目的不一定相同[8],例如:智能安防、远程控制、增强现实应用等. 图2展示了算力网络环境下算力节点协作处理工作流任务的场景. 在这一场景中,算力节点高效协同,为低延时的工作流任务提供更好的性能保障. 如图2中任务执行路径所示,数据在终端设备(摄像头)上产生,需要经过多个算力节点协同分析处理,最终将数据的识别结果发送至远端的智能监控中心. 在这种执行模式下,数据源和目的之间的路径选择、工作流任务的卸载位置以及算力节点的资源分配情况都将影响应用的执行性能. 因此,本文研究的问题是在算力网络环境下联合任务卸载和资源分配优化问题,以最小化工作流任务的端到端延迟.
2.2 问题建模
1)系统建模. 我们把算力网络建模成一个有向无环图[5](DAG):
GE=(M,ER) ,其中M 表示算力节点的集合,ER 表示算力节点之间物理链路的集合. 我们用Fm 表示算力节点m∈M 的计算能力(以FLOPS来衡量);Bm,n 表示算力节点m 到算力节点n 之间的带宽.2)任务建模.
U 表示用户的集合,由于工作流任务由多个具有依赖关系的子任务构成,将任务建模成一个有向无环图:GT=(S,SR) ,其中S 表示工作流任务中子任务的集合,SR 表示子任务之间依赖关系集合.cu,s 表示用户u 中子任务s 所需的计算量,du,s 表示子任务s 的中间数据/输出结果所需的数据传输量. 本文中主要符号及含义如表1所示.表 1 主要符号的含义Table 1. Meaning of the Main Symbols符号 含义 Fm 算力节点m的算力 Bm,n 算力节点m和n之间的带宽 cu,s 用户u的子任务s的计算量 du,s 用户u的子任务s的数据量 Au,s 用户u的子任务s的卸载位置 Au,t 用户u的子任务t的卸载位置 Pu,s 分配给用户u的子任务s的算力比例 Qu,s,t 分配给用户u的子任务s到子任务t的带宽比例 基于上述问题建模,本文研究的问题包含二维影响工作流任务执行性能的决策变量:卸载决策和资源分配决策. 卸载决策决定将工作流任务中的子任务提交到哪个算力节点
Au,s 上进行执行;资源分配决策决定工作流任务中提交的子任务分配计算资源的比例Pu,s ,以及分配的带宽资源的比例Qu,s,t .2.3 问题定义
工作流任务的处理延迟包括计算延时和中间数据/结果的传输时延2部分. 对于任意用户
u 的子任务s ,其计算延时Tcompu,s 可以通过其计算量和所分配的计算资源FAu,s×Pu,s 表示:Tcompu,s=cu,sFAu,s×Pu,s. (1) 本文用
K 表示子任务间的传输路径集合,Ku,s,t 则表示用户u 的子任务s 到子任务t 的传输路径,由卸载决策A 决定,如式(2)所示:Ku,s,t=(Au,s,Au,t), (2) 则子任务
s 到子任务t 的传输时延Tcommu,s,t 如式(3)所示,其中ds 表示子任务BKu,s,t×Qu,s,t 的中间数据量/输出结果数据量,BKu,s,t×Qu,s,t 表示所分配的带宽资源.Tcommu,s,t=dsBKu,s,t×Qu,s,t. (3) 结合式(1)和式(3)可以得出工作流任务的子任务
s 的完成时间为:Tu,s=max (4) 其中,
s. pre 表示子任务s 的前驱子任务集合.因此,工作流任务的完成时间即为最后一个子任务
(s\_last) 的完成时间:{T_u} = {T_{u,s\_last}}. (5) 本文的研究问题,即联合优化工作流任务的卸载决策、资源分配决策来最小化所有用户的平均完成时间,该问题
P 可以表示的数学模型为:目标函数:
\mathop {\min }\limits_{{{A,P,Q}}} \frac{1}{{\left| U \right|}}\sum_{u \in U} {{T_u}} . (6) 约束条件:
{P_{u,s}} \geqslant 0,\forall u \in U,\forall s \in {S_u}, (7) {Q_{u,s,t}} \geqslant 0,\forall u \in U,\forall (s,t) \in S {R_u} , (8) \sum_{u \in U,s \in {S_u}} {{P_{u,s}}} I(m = {A_{u,s}}) \leqslant 1,\forall m \in M , (9) \sum_{u \in U,(s,t) \in S {R_u}} { {Q_{u,s,t}}I((m,n) = {K_{u,s,t}})} \leqslant 1,\forall m \in M,\forall n \in M , (10) {A_{u,s}} \in \left\{ {1,2,… ,\left| M \right|} \right\},\forall u \in U,\forall s \in {S_u} . (11) 其中,
A,P,Q 分别表示卸载位置决策、算力比例决策和带宽比例决策.I( · ) 表示指示函数,当括号里等式成立时值为1,反之则为0. 约束式(7)和式(8)分别保证分配给用户的算力资源和带宽资源大于0,是连续性变量;约束式(9)(10)保证分配的资源比例之和小于或等于1;约束式(11)表示卸载位置变量的取值范围,是离散型变量. 在有M个算力节点、N个用户,每个用户的工作流应用含有S个子任务的场景下,卸载决策的空间为{M^{NS}} ,因此,该问题是一个混合整数非线性规划问题,同时也是一个NP难问题.3. 工作流卸载算法
本文研究了2种典型的工作流结构:链式工作流任务和DAG式工作流任务. 针对链式工作流任务,本文提出了一种基于势博弈的分布式工作流卸载算法DWO来最小化工作流任务的完成时间;针对DAG式的工作流任务,本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO来减小工作流任务的完成时间.
3.1 链式工作流卸载算法
通过对链式工作流结构进行分析,可以将原问题
P 分解成2个子问题:子问题P1 根据卸载策略和路径选择策略决定最优的资源分配方案;子问题P2 根据最优分配策略决定卸载位置和传输路径,该问题基于势博弈进行求解.3.1.1 最优资源分配策略
子问题
P1 目标是在给定卸载策略和路径选择策略的前提下,决定最优的资源分配策略使得工作流任务完成时间最小.目标函数:
\mathop {\min }\limits_{{\{P,Q\}}} C(A,P,Q) = \sum_{u \in U} {\left(\sum_{s \in {S_u}} {T_{u,s}^{{\rm{comp}}}} + \sum_{(s,t) \in S{R_u}} {T_{u,s,t}^{{\rm{comm}}}} \right)}. (12) 约束条件:
{P_{u,s}} \geqslant 0,\forall u \in U,\forall s \in {S_u} , (13) {Q_{u,s,t}} \geqslant 0,\forall u \in U,\forall s,t \in S {R_u}, (14) \sum_{u \in U,s \in {S_u}} {{P_{u,s}}} I(m = {A_{u,s}}) \leqslant 1,\forall m \in M, (15) \sum_{u \in U,(s,t) \in S {R_u}} {{Q_{u,s,t}}I((m,n) = {K_{u,s,t}})} \leqslant 1,\forall m \in M,\forall n \in M . (16) 在
P1 中,式(12)表示的目标函数是凸函数,式(13)和式(14)表示的定义域为凸集,式(15)和式(16)表示的也是凸函数,因此P1 是一个凸优化问题,且最优解满足KKT(Karush-Kuhn-Tucker)条件. 首先给出P1 的拉格朗日函数:\begin{aligned} &L(A,P,Q,\alpha ,\beta ) = C(A,P,Q) +\\ &\displaystyle\sum_{u \in U} \left(\displaystyle\sum_{s \in {S_u}} {{\alpha _{u,s}}{P_{u,s}}} + \displaystyle\sum_{(s,t) \in S{R_u}} {{\beta _{u,s,t}}{Q_{u,s,t}}} \right)\end{aligned}, 其中,
\alpha 和\beta 分别表示2个约束项的参数. 从而获得拉格朗日对偶问题和KKT条件,通过求解KKT条件,得到最优的资源分配策略,资源分配的表达式为P_{u,s}^*(A) = \dfrac{{\sqrt {{c_{u,s}}} }}{{\displaystyle\sum_{(v,t) \in {D_{u,s}}(A)} {\sqrt {{c_{v,t}}} } }} , (17) Q_{u,s,t}^*(A) = \dfrac{{\sqrt {{d_{u,s}}} }}{{\displaystyle\sum_{(v,p,q) \in {R_{u,s,t}}(A)} {\sqrt {{d_{v,p}}} } }} , (18) 其中,
{D_{u,s}}(A) 表示卸载决策A 中与用户u 的子任务卸载到同一节点的用户和子任务集合,{R_{u,s,t}}(A) 表示卸载决策A 中与用户u 的子任务s 到子任务t 占有相同链路的用户和子任务集合. 根据最优资源分配策略,将式(17)中的P_{u,s}^*(A) 和式(18)中的Q_{u,s,t}^*(A) 代入到式(12)中,可以获得在卸载策略A 下的各个用户的工作流任务完成时间{\bar C_u} .因此,原问题
P 可以表示为P2 问题:目标函数:
\mathop {\min }\limits_A \bar C(A) = \displaystyle\sum_{u \in U} {{{\bar C}_u}(A)}, (19) 约束条件:
{A_{u,s}} \in \left\{ {1,2,… ,\left| M \right|} \right\},\forall u \in U,\forall s \in {S_u} . (20) 子问题
P2 的2种变量均为离散型,本文考虑工作流子任务的个数为S ,故可行的解空间大小为{\left| M \right|^{\left| U \right|S}} . 解空间是指数级的. 本文采用基于势博弈的方法来解决子问题P2 .3.1.2 多用户卸载博弈(multi-user offloading game,MOG)
基于3.1.1节的分析,本文设计了一种基于势博弈的方法来解决工作流卸载问题. 首先将子问题
P2 建模为一个多用户卸载博弈G = \{ U,{A_u},{V_u}\} ,其中U 表示用户集合,{A_u} 表示用户u 的卸载决策,{V_u} 表示用户u 的效用函数.定理1. 在最优资源分配条件下,用户间的相互作用可以被建模为一个资源依赖加权的拥塞博弈,每个用户的代价函数为
{\bar C_u}(A) = \displaystyle\sum_{s \in {S_u}} {w_{u,s}^x({A_u})} {w_x}(A) + \displaystyle\sum_{(s,t) \in S{R_u}} {w_{u,s,t}^y({A_u}){w_y}(A)}. (21) 证明. 用
x 表示用户u 的子任务s 的卸载位置{A_{u,s}} ,y 表示用户u 的子任务s 到子任务t 的传输路径{K_{u,s,t}} . 首先定义w_{u,s}^x({A_u}) = \sqrt {\dfrac{{{c_{u,s}}}}{{{F_x}}}} 表示用户u 的子任务s 在算力节点x 上处理,w_{u,s}^y({A_u}) = \sqrt {\dfrac{{{d_{u,s}}}}{{{B_y}}}} 表示用户u 的子任务s 到子任务t 的中间数据在路径y 上传输. 那么{w_x}(A) = \displaystyle\sum_{(v,s) \in D(x)} {\sqrt {\dfrac{{{c_{v,s}}}}{{{F_x}}}} } ,{w_y}(A) = \displaystyle\sum_{(v,s,t) \in R(y)} {\sqrt {\dfrac{{{d_{v,s}}}}{{{B_y}}}} } . 其中D(x) 表示卸载到算力节点x 上的子任务集合,R(y) 表示占用链路y 的子任务传输集合. 因此,用户间的相互作用可以被建模为一个资源依赖加权的拥塞博弈. 证毕.本文将用户的效用函数
{V_u} 定义为该用户工作流的完成时间,即{V_u}({A_u},{A_{ - u}}) = {\bar C_u}({A_u},{A_{ - u}}), (22) 其中,
{A_{ - u}} 表示不包含用户u 的决策集,{\bar C_u}({A_u},{A_{ - u}}) 表示用户u 的工作流任务完成时间.定义1. 纳什均衡[21]. MOG的策略
{A^*} 是纳什均衡解当且仅当任意用户无法通过改变自身策略降低自己的效用值{V_u} .{V_u}(A_u^*,A_{ - u}^*) \leqslant {V_u}({A_u},A_{ - u}^*) . (23) 接下来,本文分析了MOG的纳什均衡的存在性,关键在于证明MOG是一个严格势博弈[7].
定义2. (严格势博弈[21]) 博弈
G = \{ U,{A_u},{V_u}\} 是严格博弈需满足式(24):{V_u}({A'_u},{A_{ - u}}) - {V_u}({A_u},{A_{ - u}}) = \varPhi ({A'_u},{A_{ - u}}) - \varPhi ({A_u},{A_{ - u}}), (24) 其中
\varPhi ({A_u},{A_{ - u}}) 表示为势函数.为了证明MOG是一个严格势博弈,本文将势函数定义为
\varPhi ({A_u},{A_{ - u}}) = \displaystyle\sum_{u \in U} {{\varPhi _u}({A_u},{A_{ - u}})} , (25) 其中,
{\varPhi _u}({A_u},{A_{ - u}}) = \displaystyle\sum_{h \in H} {w_u^h({A_j})\displaystyle\sum_{j \leqslant u} {w_j^h({A_j})} } ,H = \{ A \cup K\} 表示资源的集合.定理2. MOG是严格势博弈.
证明. 假设某一时刻用户
g 将决策\left( {{A_g},{A_{ - g}}} \right) 改变为\left( {A_g',{A_{ - g}}} \right) ,此时该用户的效用差值为{V_g}(A) - {V_g}(A') = \displaystyle\sum_{h \in H} {(w_g^h(A) - w_g^h(A'))} . (26) 下面分3种情况讨论:
1)对于用户
i < g :{\varPhi _i}(A) - {\varPhi _i}(A') = 0 .2)对于用户
i > g :{\varPhi _i}(A) - {\varPhi _i}(A') = \displaystyle\sum_{h \in H} (w_i^h(A)w_g^h(A) - w_i^h(A)w_g^h(A')) .3)对于用户
i = g :{\varPhi _i}(A) - {\varPhi _i}(A') = \displaystyle\sum_{h \in H} (w_g^h(A) \displaystyle\sum_{j \leqslant g} w_j^h(A) - w_g^h(A')\displaystyle\sum_{j \leqslant g} {w_j^h(A')} ) .综上,
\begin{aligned} &\varPhi (A) - \varPhi (A') = \displaystyle\sum_{i \in U} {({\varPhi _i}(A) - {\varPhi _i}(A'))} =\\ &\displaystyle\sum_{h \in H} \displaystyle\sum_{i>g} (w_i^h(A) w_g^h(A) - w_i^h(A)w_g^h(A')) + \\ & \displaystyle\sum_{h \in H} (w_g^h(A)\displaystyle\sum_{i \leqslant g} w_i^h(A)-w_i^h(A')\times\displaystyle\sum_{i \leqslant g} {w_j^h(A')} ) = \\ &\displaystyle\sum_{h \in H} {(w_g^h(A) - w_g^h(A'))} = {V_g}(A) - {V_g}(A')\end{aligned} 证毕.
3.1.3 基于势博弈的分布式工作流卸载算法
针对链式工作流应用,本文提出了基于势博弈的分布式工作流卸载算法,该算法的设计依据是基于博弈论的有限改进性质(在有限迭代轮次下可以获得一个纳什均衡解[26]). 伪代码如算法1所示.
算法1. DWO算法
①每个用户
u 随意选择一个可行策略,记为{A_u} ;② repeat
③按序选择一个用户
u ;④
{A'_u} = \left\{ {\begin{array}{*{20}{c}} {{{\hat A}_u},{V_u}({A_u},{A_{ - u}}) > {V_u}({{\hat A}_u},{A_{ - u}})} ,\\ {{A_u},{V_u}({A_u},{A_{ - u}}) \leqslant {V_u}({{\hat A}_u},{A_{ - u}})}; \end{array}} \right. / *
{\hat A_u} 表示从可行解中选择的一个解,{A'_u} 表示用 户u 新的策略. */⑤更新策略集为
A = ({A'_u},{A_{ - u}}) ;⑥ until所有用户都不再更新策略.
算法DWO根据MOG的有限改进性质,且一次只允许一个用户对它的策略进行改善. 首先,每个用户随机地选择一个可行策略;然后,在每一轮迭代过程中按序选择一个用户对它的策略进行改善,并更新到总的策略集上,直到所有的用户都不再更新策略,即算法达到纳什均衡.
3.1.4 时间复杂度分析
假设算力节点的数量为
M ,用户数量为U ,工作流任务拓扑中的节点数为S ,根据式(17)和式(18)可知资源分配策略的时间复杂度为O(US) . 在每一轮迭代过程中,用户进行决策的时间复杂度为O({M^S}US) . 假设算法DWO经过C 轮达到收敛,因此算法DWO的时间复杂度为O(C{M^S}US) . 当子任务数量较少时可以有效进行求解;而针对子任务数量较多的场景,一种可行的优化思路是先筛选若干个子任务切分点,将子任务数量降低,从而降低时间复杂度.3.1.5 PoA分析
本文探讨算法DWO的纳什均衡解的有效性. 算法DWO可能有多个纳什均衡解,根据博弈论中的PoA的定义,本文将最差的纳什均衡解和最优解的比值定义为算法DWO的PoA值.
PoA = \frac{{\mathop {\max }\limits_{A \in {\cal A}} V(A)}}{{V({A^*})}} , (27) 其中:
\cal A 表示算法DWO的纳什均衡解集,{A^*} 表示最优策略. 显然可以得到PoA值的下界:PoA \geqslant 1 (28) 本文将介绍PoA值的一个上界.
定理3. DWO的PoA值的上界为:
PoA \leqslant \dfrac{{3 + \sqrt 5 }}{2} .证明. 根据式(21),将总的效用表述为
V(A) = \displaystyle\sum_{u \in U} {({{\bar C}_u}(A)) = \displaystyle\sum_{u \in U} {\displaystyle\sum_{h \in H} {w_u^h({A_u})} } } {w_h}(A) = \displaystyle\sum_{h \in H} {w_h^2(A)}. (29) 根据纳什均衡的定义,可得:
\begin{aligned} {V_u}(A) =\displaystyle\sum_{h \in H} {w_u^h({A_u}){w_h}(A)} \leqslant \end{aligned} \begin{aligned} &\displaystyle\sum_{h \in H} {w_u^h(A_u^*)({w_h}(A) - w_u^h({A_u}) + w_u^h(A_u^*))}\leqslant\\ & \displaystyle\sum_{h \in H} {w_u^h(A_u^*)} ({w_h}(A) + w_u^h(A_u^*)). \end{aligned} (30) 将所有用户合成一个不等式,可得:
\begin{aligned} &\displaystyle\sum_{u \in U} {V_u}(A) = \displaystyle\sum_{u \in U} {\displaystyle\sum_{h \in H} {w_u^h({A_u}){w_h}(A)} } \leqslant \\ & \displaystyle\sum_{u \in U} {\displaystyle\sum_{h \in H} {w_u^h(A_u^*)({w_h}(A) + w_u^h(A_u^*))} } . \end{aligned} (31) 重新排序并重写式(31),可得:
\begin{aligned} & \displaystyle\sum_{h \in H} {\displaystyle\sum_{i \in {O_h}(A)} {w_i^h({A_i}){w_h}(A)} } \leqslant \\ & \displaystyle\sum_{h \in H} {\displaystyle\sum_{i \in {O_h}(A)} {w_i^h(A_i^*)({w_h}(A) + w_i^h(A_i^*))} } , \end{aligned} (32) 其中,
{O_h}(A) 表示卸载决策A 占用资源h 的用户与子任务集合. 因为总的权重\displaystyle\sum_{i \in {O_h}(A)} {w_i^h({A_i}){w_h}} (A) - w_h^2(A) 与资源h 相关,根据\displaystyle\sum_{i \in {O_h}(A)} {w_i^h{{({A_i})}^2}} \leqslant w_h^2(A) ,由式(32)推出:\displaystyle\sum_{h \in H} {w_h^2(A)} \leqslant \displaystyle\sum_{h \in H} {{w_h}({A^*}){w_h}(A) + \displaystyle\sum_{h \in H} {w_h^2({A^*})} }. (33) 通过柯西-施瓦茨不等式,可得:
\displaystyle\sum_{h \in H} {w_h^2(A)} \leqslant \sqrt {\displaystyle\sum_{h \in H} {w_h^2({A^*})} \displaystyle\sum_{h \in H} {w_h^2(A)} } + \displaystyle\sum_{h \in H} {w_h^2({A^*})} . (34) 对于式(34),两边同除
\displaystyle\sum_{h \in H} {w_h^2({A^*})} ,可得:\frac{{V(A)}}{{V({A^*})}} \leqslant \sqrt {\frac{{V(A)}}{{V({A^*})}}} + 1 . (35) 因为式(35)包含了DWO的所有纳什均衡解,同样包含了最差的纳什均衡解,因此:
PoA \leqslant \sqrt {PoA} + 1 . (36) 通过求解式(36),即证:
PoA \leqslant \dfrac{{3 + \sqrt 5 }}{2} .3.2 DAG式工作流卸载算法
针对DAG式工作流,本文同样将资源分配和任务卸载分开. 由于目标函数中含有不可微函数
\max ( · ) ,本文基于松弛的资源分配策略进行资源分配;由于算法DWO在子任务数量大的场景下其时间复杂度较高,难以在可接受的计算时间内获得一个可行解. 因此,本文设计了一种基于动态资源权重的启发式工作流卸载算法Heu-WO.3.2.1 松弛的资源分配策略
针对DAG式的工作流应用进行分析,由于DAG式工作流的完成时间中含有函数
\mathrm{m}\mathrm{a}\mathrm{x}(·) ,故其目标函数不能像链式的工作流转化成式(12). 而函数\mathrm{m}\mathrm{a}\mathrm{x}(·) 也是凸函数[22],所以该问题的目标函数式(6)仍然是凸函数;且定义域和约束函数与P1 问题中的一致,故原问题的定义域为凸集,约束函数也是凸函数,所以该问题也是凸优化问题. 但是因为函数\max ( · ) 不可微,求解比较困难. 所以本文将函数\max ( · ) 松弛为求和函数\sum {( · )} ,即,将目标函数从式(6)松弛成式(12),这样便可以通过3.1.1节中的式(17)和式(18)求解得到该问题的资源分配方案.3.2.2 基于动态资源权重的启发式工作流卸载算法
针对DAG式工作流应用,本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO,它将每个资源的占有情况记作资源权重,对每个子任务基于资源权重选择完成时间最少的节点进行卸载,并动态更新资源权重. 伪代码如算法2所示.
算法2. 基于动态资源权重的启发式工作流卸载算法Heu-WO
①初始化每个算力节点
m 的算力资源占用量c{o_m} ②初始化每条链路
(m,n) 的带宽资源占用量d{o_{m,n}} ③ for 每个用户
u ④ for 每个子任务
s ⑤
l = \mathop {\arg \min }\limits_m \left(\left(\mathop {\max }\limits_{i \in s. pre} \dfrac{{{d_s}d{o_{{A_{u,i}},m}}}}{{{B_{{A_{u,i}},m}}}}\right) + \dfrac{{{c_s}c{o_m}}}{{{F_m}}}\right) ;/*
s. pre ;表示子任务s 的前驱子任务集合, 寻找子任务s 完成时间最短的卸载位置*/⑥
{A_{u,s}} = l ;/*记录用户
u 子任务s 的卸载位置*//*
{A_{u,s}} ,记录子任务s 的卸载位置为l ,更新 所占用资源的占用量*/⑦
c{o_l} + = \sqrt {{c_s}} ;/*更新算力资源的占用情况*/
⑧
d{o_{{A_{u,i}},l}} + = \sqrt {{d_s}} ,\forall i \in s. pre ;/*更新带宽资源的占用情况*/
⑨ end for
⑩ end for
⑪
{P_{u,s}} = \dfrac{{\sqrt {{c_{u,s}}} }}{{c{o_{{A_{u,s}}}}}} ,{Q_{u,s,t}} = \dfrac{{\sqrt {{d_{u,s}}} }}{{d{o_{{K_{u,s,t}}}}}} ;/*进行资源分配*/
⑫ return
A,P,Q ./*输出卸载与资源分配方案*/
根据公平性原则,每个用户对其子任务
s 选择最佳的卸载方案,如算法2行⑤表示选择最小化子任务s 的完成时间的卸载位置,行⑥~⑧更新策略和环境中的占用情况,以供其他用户做出决策.3.2.3 时间复杂度分析
假设算力节点的数量为
M ,用户数量为U ,工作流任务拓扑中的节点数为S . 由算法2,外部(行③,④)是双层循环,故时间复杂度为O(US) ;内部(行⑤)是对所有算力节点的一次遍历,故时间复杂度为O(M) . 综上,本文所提算法Heu-WO的时间复杂度为O(USM) .4. 实验结果与分析
本文进行了算力网络环境下工作流任务的执行优化实验,首先对实验环境与参数进行说明,然后展示仿真结果并对其进行分析.
4.1 实验环境与参数设置
本文使用拥有i7-12700K CPU,32GB RAM的服务器作为算力网络环境工作流任务执行优化的硬件平台,软件平台采用Ubuntu 20.04 x86_64操作系统,Visual Studio Code 1.73.1版本以及Python3. 8版本的编程环境,并采用了DAG生成器[27]生成DAG拓扑数据,以此代表具有依赖关系的工作流任务. 通过控制参数n和参数density来随机生成不同的工作流任务,其中参数n控制DAG的节点个数,即子任务数量;参数density表示DAG密度,是边数与节点数的比值,用于控制DAG中节点间的边数,即子任务间的依赖关系,density值越大,DAG中的边数越多,子任务之间的数据交互就越多. 为了便于理解,图3展示了DAG生成器在不同参数下所生成的DAG结构. 同时,本文的网络拓扑也采用了DAG生成器用于生成复杂的网络环境.
本文实验环境参数如表2所示.
表 2 实验环境参数Table 2. Experimental environment Parameters环境参数 设置值 算力节点个数 [10, 50] 用户数 [100, 500] 算力节点计算资源/ TFLOPS [1.0, 3.0] 算力节点间带宽/ Mbps [40, 80] DAG节点数量 [1, 100] DAG密度 [1, 1.5] 子任务计算量/ GFLOPs [0.2, 1.2] 子任务传输数据量/ KB [100, 800] 4.2 对比算法
为了验证本文所提算法DWO和算法Heu-WO的有效性,将DWO和Heu-WO与其他4种算法进行对比实验. 具体描述为:
1)低延迟自适应工作负载分配(low-latency adaptive workload allocation,LAWA)[8]. 该算法在已知一条最优传输路径的前提下,通过联合优化计算寻路和工作负载分配来降低工作流应用的完成时间. 但是LAWA没有考虑如何寻找到最优路径. 因此,本文先通过最短路径算法获得传输路径.
2)最佳卸载(Optimal). 该算法通过暴力求解方法遍历卸载空间以获取最优解. 但该方法的复杂度太高,难以在大规模场景下进行求解.
3)最近卸载(Nearest). 该算法先根据任务的原数据量和结果数据量决策卸载到靠近发送方的算力节点或靠近接受方的算力节点上进行处理,用户独立选择最短传输路径,然后基于凸优化方法求得的最优的资源分配方案.
4)随机卸载(Random). 该算法指的是用户将每个子任务随机卸载到算力节点上,子任务传输独立选择最短路径,然后基于凸优化方法求得最优的资源分配方案.
4.3 DWO算法性能分析
验证算法的性能以及收敛性. 本节在小规模链式工作流场景下进行了500次独立实验,然后将结果按照Optimal的值进行规格化处理,最后取平均值.
如图4所示,DWO算法可以很快达到收敛,与Optimal相比,DWO解的近似比高达94.6%,与其他算法相比,加速比最高达3.2x,Heu-WO次之,然后依次是LAWA,Nearest,Random. LAWA考虑了在最优传输路径上进行卸载,有效利用了传输路径上的计算资源,但是没有联合计算路径和传输路径,其最优传输路径上的算力节点相比较其他算力节点未必是最优的. Nearest是一种0/1卸载,传输成本低,但是无法利用其他节点上的资源,导致计算时延大. Random随机地选择卸载位置会导致传输开销大,在网络带宽小的情况下尤为突出.
4.4 Heu-WO算法性能分析
4.4.1 算法效率分析
为了验证Heu-WO算法的效率,本节通过改变节点数量、用户数量和子任务数量进行了3组实验.
图5展示了算法完成时间与算力节点数量之间的关系,用户数量越多,算法的完成时间也就越长;随着算力节点的增加,算法的完成时间呈现出线性增长的趋势. 本文通过最小二乘法对各曲线进行线性拟合,得到的4条近似直线,其斜率由上到下依次是0.044,0.087,0.122,0.169. 可以看出,算法完成时间与相应的节点数之间存在线性关系.
图6展示了算法完成时间与用户数量之间的关系,算力节点数量越多,算法的完成时间也就越多;随着用户数量的增加,算法的完成时间同样呈现出线性增长的趋势. 同样通过最小二乘法对各曲线进行线性拟合,得到的4条近似直线,其斜率由上到下依次是0.048,0.090,0.128,0.169. 可以看出,完成时间与相应的用户数量之间也存在线性关系.
图7展示了算法完成时间与子任务数量之间的关系,其中:Cx_Ny表示在用户数为x、算力节点数为y的情况下,随着用户数量与节点数量的增加,算法的完成时间相应地增加;子任务数量越多,算法的完成时间也就越大,同样呈现出线性增长的趋势. 本文通过最小二乘法对各曲线进行线性拟合,得到的4条近似直线,其斜率由上到下依次是0.20,0.40,0.41,0.79. 可以看出,完成时间与用户数量和节点数量的乘积存在正比关系.
综上,图5,6,7共同体现出该算法的完成时间与算力节点数量、用户数量以及子任务数量均呈现出正比关系,从而验证了3.2.3节中所分析的Heu-WO的时间复杂度为
O(USM) .4.4.2 验证算力网络环境资源的影响
本节验证算力网络环境资源对算法性能的影响,通过实验分析平均时延与算力网络环境资源(节点计算能力和带宽资源)的关系.
图8展示了不同算法在不同算力节点计算能力下的平均时延. 随着算力节点计算能力的增加,各个算法的平均时延均有所降低. 这是因为算力节点的计算资源越多,可以分配给用户的计算资源相应地增加了,降低了计算带来的时间开销. 与其他算法相比, Heu-WO算法实现了最低平均时延(加速比最高达2.7x).
图9展示了不同算法在不同网络带宽下的平均时延. 随着网络带宽的增加,各个算法的平均时延也均有所降低. 这是因为网络带宽越大,传输数据则越快,降低了数据传输的时间开销. 与其他算法相比, Heu-WO算法实现了最低平均时延(加速比最高达2. 4x).
4.4.3 验证节点数量和用户数量的影响
本节验证节点数量和用户数量对算法性能的影响. 通过控制变量,分析平均时延与节点数量和用户数量的关系.
图10展示了不同算法在不同节点数量下的平均时延,随着节点数量的增加,各个算法的平均时延均有所降低. 这是由于资源增加使得用户之间的资源竞争减弱,用户可以分配更多的资源,从而降低了平均时延. 与其他算法相比, Heu-WO保持最优(加速比最高达2.8x).
图11展示了不同算法在不同用户数量下的平均时延,随着用户数量的增加,各个算法的平均时延均有所上升. 这是由于用户数量增加加剧了用户之间的资源竞争,从而增加了平均时延. 与其他算法相比, Heu-WO仍保持最优(加速比最高达1.9x).
4.4.4 验证子任务数量的影响
图12展示了不同算法在不同子任务数量下的平均时延. 随着子任务数量的成倍增加,各个算法的平均时延也呈现出线性上升的趋势. 这是因为虽然子任务数量增加,而资源没发生变化,子任务分配到的资源相应降低,从而导致平均时延的增加. 与其他算法相比, Heu-WO保持最优(加速比最高达1.7x).
5. 结论与展望
本文研究了算力网络环境下工作流任务卸载与资源分配问题. 根据工作流应用的特点,针对链式工作流任务,本文提出了一种基于势博弈的分布式工作流卸载算法DWO,首先已知卸载决策下的资源分配问题是一个凸优化问题,通过凸优化方法得到最优资源分配方案,基于凸优化求解的资源分配方案,将卸载问题建模成一个加权拥塞博弈. 本文证明了该博弈是一种势博弈(至少存在一个纳什均衡解)和PoA值;针对DAG工作流任务,本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO,每个子任务基于资源权重选择完成时间最少的节点进行卸载. 数值仿真实验表明,在子任务数较小场景下,DWO可以有效地取得高近似比的解(94.6%),相比其他算法可以获得最高3.2x的加速比;Heu-WO可以在较低多项式时间内进行求解,与现有算法相比,最高可以获得2.8x的加速比. 从而验证了本文所提算法DWO和Heu-WO的有效性.
未来的工作包括3个方面:
1)本文为了简化问题,在考虑子任务间传输时只考虑了单跳的传输路径(见式(2)),然而子任务间的传输可以是多跳的. 因此,下一步我们将对子任务多跳传输的路径选择问题做进一步研究.
2)DWO具有一定的理论性,但是针对子任务数量大的场景,时间复杂度较高(见3.1.4节),且难以适用于DAG式工作流任务;而Heu-WO虽然时间复杂度低,但是缺乏理论保证. 因此,下一步我们将考虑对DAG式工作流任务的卸载问题进行松弛,采用势博弈方法求解,并进行理论分析.
3)本文研究的工作流任务卸载问题只考虑了算力资源同构的场景. 事实上,在大规模算力网络环境下存在大量的异构算力节点,如中央处理器(central processing unit,CPU)、图形处理器(graphics processing unit,GPU). 因此,异构算力网络场景下的工作流任务卸载问题将是我们未来要进一步研究的工作.
作者贡献声明:姜玉龙负责算法设计、仿真与论文撰写;东方负责提出论文整体架构与论文修订指导;郭晓琳负责算法指导与文字把关;罗军舟负责总体思路指导.
-
表 1 主要符号的含义
Table 1 Meaning of the Main Symbols
符号 含义 {F_m} 算力节点m的算力 {B_{m,n}} 算力节点m和n之间的带宽 {c_{u,s}} 用户u的子任务s的计算量 {d_{u,s}} 用户u的子任务s的数据量 {A_{u,s}} 用户u的子任务s的卸载位置 A_{u,t} 用户u的子任务t的卸载位置 {P_{u,s}} 分配给用户u的子任务s的算力比例 {Q_{u,s,t}} 分配给用户u的子任务s到子任务t的带宽比例 表 2 实验环境参数
Table 2 Experimental environment Parameters
环境参数 设置值 算力节点个数 [10, 50] 用户数 [100, 500] 算力节点计算资源/ TFLOPS [1.0, 3.0] 算力节点间带宽/ Mbps [40, 80] DAG节点数量 [1, 100] DAG密度 [1, 1.5] 子任务计算量/ GFLOPs [0.2, 1.2] 子任务传输数据量/ KB [100, 800] -
[1] Wang Shibo, Yang Shusen, Zhao Cong. SurveilEdge: Real-time video query based on collaborative cloud-edge deep learning [C] //Proc of the IEEE Conf on Computer Communications (IEEE INFOCOM 2020). Piscataway, NJ: IEEE, 2020: 2519−2528
[2] Hochstetler J, Padidela R, Chen Qi, et al. Embedded deep learning for vehicular edge computing [C] //Proc of the 2018 IEEE/ACM Symp on Edge Computing (SEC). Piscataway, NJ: IEEE, 2018: 341−343
[3] Li En, Zeng Liekang, Zhou Zhi, et al. Edge AI: On-demand accelerating deep neural network inference via edge computing[J]. IEEE Transactions on Wireless Communications, 2020, 19(1): 447−457 doi: 10.1109/TWC.2019.2946140
[4] Rajput K R, Kulkarni C D, Cho B, et al. EdgeFaaSBench: Benchmarking edge devices using serverless computing [C] //Proc of the 2022 IEEE Int Conf on Edge Computing and Communications. Piscataway, NJ: IEEE, 2022: 93−103
[5] Fu Xing, Tang Bing, Guo Feiyan, et al. Priority and dependency-based DAG tasks offloading in fog/edge collaborative environment[C] //Proc of the IEEE 24th Int Conf on Computer Supported Cooperative Work in Design (CSCWD). Piscataway, NJ: IEEE, 2021: 440−445
[6] Huang Zhaowu, Dong Fang, Shen Dian, et al. Enabling low latency edge intelligence based on multi-exit DNNs in the wild [C] //Proc of the 2021 IEEE 41st Int Conf on Distributed Computing Systems (ICDCS). Piscataway, NJ: IEEE, 2021: 729−739
[7] Huang Zhaowu, Dong Fang, Shen Dian, et al. Enabling latency-sensitive DNN inference via joint optimization of model surgery and resource allocation in heterogeneous edge [C] //Proc of the 51st Int Conf on Parallel Processing (ICPP'22). New York: ACM, 2023: 1–11
[8] Guo Xiaolin, Dong Fang, Shen Dian, et al. Exploiting the computational path diversity with in-network computing for MEC [C] //Proc of the 19th Annual IEEE Int Conf on Sensing, Communication, and Networking (SECON). Piscataway, NJ: IEEE, 2022: 280−288
[9] Chen Long, Wu Jigang, Zhang Jun, et al. Dependency-aware computation offloading for mobile edge computing with edge-cloud cooperation[J]. IEEE Transactions on Cloud Computing, 2022, 10(4): 2451−2468 doi: 10.1109/TCC.2020.3037306
[10] Lv Xiaoyan, Du Hongwei, Ye Qiang. TBTOA: A DAG-based task offloading scheme for mobile edge computing [C] //Proc of the IEEE Int Conf on Communications (ICC 2022). Piscataway, NJ: IEEE, 2022: 4607−4612
[11] Zhang Jiawei, Chen Suhong, Wang Xudong, et al. DeepReserve: Dynamic edge server reservation for connected vehicles with deep reinforcement learning [C] //Proc of the IEEE Conf on Computer Communications (IEEE INFOCOM). Piscataway, NJ: IEEE, 2021: 1−10
[12] Ding Yan, Li Kenli, Liu Chubo, 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, 2022, 33(6): 1503−1519 doi: 10.1109/TPDS.2021.3112604
[13] Kang Y, Hauswald J, Gao C, et al. Neurosurgeon: Collaborative intelligence between the cloud and mobile edge[J]. ACM SIGARCH Computer Architecture News, 2017, 45(1): 615−629 doi: 10.1145/3093337.3037698
[14] Mohammed T, Joe-Wong C, Babbar R, et al. Distributed inference acceleration with adaptive DNN partitioning and offloading [C] //Proc of the IEEE INFOCOM 2020-IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, 2020: 854−863
[15] Tan Lin, Kuang Zhufang, Zhao Lian, et al. Energy-efficient joint task offloading and resource allocation in OFDMA-based collaborative edge computing[J]. IEEE Transactions on Wireless Communications, 2022, 21(3): 1960−1972 doi: 10.1109/TWC.2021.3108641
[16] Kao Yihsuan, Wright K. and Huang Pohan, et al. MABSTA: Collaborative computing over heterogeneous devices in dynamic environments [C] //Proc of the IEEE Conf on Computer Communications (IEEE INFOCOM 2020). Piscataway, NJ: IEEE, 2020: 169−178
[17] Yao Huijuan, Duan Xiaodong, Fu Yuexia. A computing-aware routing protocol for computing force network [C] //Proc of the 2022 Int Conf on Service Science (ICSS). Piscataway, NJ: IEEE, 2022: 137−141
[18] Dai Minghui, Su Zhou, Li Ruidong, et al. A software-defined-networking-enabled approach for edge-cloud computing in the Internet of things[J]. IEEE Network, 2021, 35(5): 66−73 doi: 10.1109/MNET.101.2100052
[19] Sundar S, Liang Ben. Offloading dependent tasks with communication delay and deadline constraint [C] //Proc of the IEEE Conf on Computer Communications (IEEE INFOCOM 2018). Piscataway, NJ: IEEE, 2018: 37−45
[20] Sahni Y, Cao Jiannong, Yang Lei, et al. Multihop offloading of multiple DAG tasks in collaborative edge computing[J]. IEEE Internet of Things Journal, 2021, 8(6): 4893−4905 doi: 10.1109/JIOT.2020.3030926
[21] Lã Q, Chew Y, Soong B. Potential Game Theory: Applications in Radio Resource Allocation [M]. Switzerland: springer, 2016: 1−172
[22] Boyd S, Vandenberghe L. Convex Optimization [M]. New York: Cambridge University Press. 2009
[23] Hong Zicong, Chen Wuhui, Huang Huawei, et al. Multi-hop cooperative computation offloading for industrial IoT-edge-cloud computing environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(12): 2759−2774 doi: 10.1109/TPDS.2019.2926979
[24] Sahni Y, Cao Jiannong, Yang Lei, et al. Multi-hop multi-task partial computation offloading in collaborative edge computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(5): 1133−1145 doi: 10.1109/TPDS.2020.3042224
[25] Funai C, Tapparello C, Heinzelman W. Computational offloading for energy constrained devices in multi-hop cooperative networks[J]. IEEE Transactions on Mobile Computing, 2020, 19(1): 60−73 doi: 10.1109/TMC.2019.2892100
[26] Fang Tao, Yuan Feng, Ao Liang, et al. Joint task offloading, D2D pairing, and resource allocation in device-enhanced MEC: A potential game approach[J]. IEEE Internet of Things Journal, 2022, 9(5): 3226−3237 doi: 10.1109/JIOT.2021.3097754
[27] Wang Jin, Hu Jia, Min Geyong. Fast adaptive task offloading in edge computing based on meta reinforcement learning[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(1): 242−253 doi: 10.1109/TPDS.2020.3014896
-
期刊类型引用(4)
1. 徐冬竹,周安福,马华东,张园. 基于连续学习的视频物联网任务需求理解与调度方法. 计算机研究与发展. 2024(11): 2793-2805 . 本站查看
2. 刘亮. 多接入算力网络任务执行及最优算力节点选择研究. 江苏通信. 2024(05): 55-60 . 百度学术
3. 王祝先,赵忠凯,叶润泽,关兴民,杨智涛,宋邦钰. IPV6多跳网络环境下双通道快速切换算法的构建研究. 应用科技. 2024(05): 101-106 . 百度学术
4. 方浩添,田乐,郭茂祖. 基于多群体混合智能优化算法的卸载决策寻优方法. 智能系统学报. 2024(06): 1573-1583 . 百度学术
其他类型引用(2)