Software Engineering and Applications
Vol. 11  No. 01 ( 2022 ), Article ID: 48589 , 10 pages
10.12677/SEA.2022.111011

基于DDPG的MEC视频任务卸载算法

程浩宇

浙江理工大学信息学院,浙江 杭州

收稿日期:2021年12月13日;录用日期:2022年2月3日;发布日期:2022年2月10日

摘要

近年来移动边缘计算(Mobile Edge Computing, MEC)的出现满足了边缘设备(Edge Device, ED)处理视频数据任务的需求,ED通过将任务卸载到MEC服务器,来缓解自身计算能力不足的缺点。然而MEC系统中网络的时变性和任务生成的动态性,为求解任务卸载问题带来了挑战。本文考虑一个多ED的MEC系统,将MEC系统的任务处理时延作为优化目标。为了最小化任务处理时延,将原问题模型转化为马尔科夫决策过程(Markov Decision Process, MDP)。考虑到任务动态性及网络时变性,本文采用一种基于深度强化学习的深度确定性策略梯度算法(Deep Deterministic Policy Gradient, DDPG)来解决MDP问题。仿真结果表明,该算法能够有效地降低任务处理时延,并优于其他基准卸载策略。

关键词

移动边缘计算,深度强化学习,任务卸载

Video Task Offloading Algorithm Based on DDPG in MEC

Haoyu Cheng

School of Information Science and Technology, Zhejiang Sci-Tech University, Hangzhou Zhejiang

Received: Dec. 13th, 2021; accepted: Feb. 3rd, 2022; published: Feb. 10th, 2022

ABSTRACT

In recent years, the emergence of Mobile Edge Computing (MEC) meets the needs of Edge Device (ED) to process video data tasks. ED alleviates its lack of computing capacity by offloading tasks to MEC server. However, the time variability in MEC and the dynamics of task generation bring challenges to the task offloading problem. In this paper, a multi-EDs MEC system is considered, and the task processing latency of the MEC system is taken as the optimization objective. In order to minimize the latency of task processing, the original problem is transformed into a Markov Decision Process (MDP). Considering the dynamics of task and time variability of network, this paper exploits the Deep Deterministic Policy Gradient (DDPG) algorithm based on deep reinforcement learning to solve the MDP problem. Simulation results show that this algorithm can effectively reduce the task processing latency and is better than other baseline offloading policies.

Keywords:Mobile Edge Computing, Deep Reinforcement Learning, Task Offloading

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

移动边缘计算(Mobile Edge Computing, MEC)作为近年一种新型计算架构,有效地解决了云计算中时延和网络负载等问题,使得物联网设备和应用程序的网络响应、实时分析、访问安全性等需求得以满足 [1] [2]。随着MEC的出现,越来越多的边缘设备通过部署深度学习模型使其能够运行目标检测、视频分析和处理等计算密集型的任务应用 [3]。然而该类任务通常也是时延敏感型的,大多的边缘设备和移动设备自身没有足够强大的计算能力来满足这一需求,因此,针对时延敏感型的任务卸载问题近年来得到越来越多的关注与研究。文献 [4] 中针对时延敏感型且不可分的任务卸载问题,以最小化长期成本为目标,提出了一种基于深度强化学习的无模型算法,该算法能够高效利用边缘节点的处理能力,显著降低系统时延。文献 [5] 研究了动态MEC场景下的计算卸载问题,通过提出的深度强化学习算法优化卸载决策,实现任务完成数最大化的同时能耗也最小化。

在本文中所考虑的视频分析、处理类任务也属于MEC中时延敏感型任务,但因为视频数据任务的分析、处理需要多个具体的操作(如视频编解码、转码等)。例如道路交通中车辆检测的视频数据,需要编解码、运行深度学习模型推理来检测车辆道路状况 [6];工业生产中的质量检测也需要对生产线上工业摄像头采集的视频数据加以处理并分析。因此,本文通过对MEC场景中视频分析任务的卸载问题建立具体的模型,对时延敏感型任务建立对应的优化目标。为了最小化视频任务的处理时延,我们将原问题转化为马尔科夫决策过程,同时考虑MEC系统动态性与任务到达随机性,采用深度确定性策略梯度算法(Deep Deterministic Policy Gradient, DDPG)适应动态环境优化边缘设备的卸载决策。最后,通过仿真验证本文基于深度强化学习的卸载策略能够有效降低系统时延成本,且优于其他基准卸载方案。

2. 系统模型

本文研究的MEC系统,由一个MEC服务器(MEC Server, MECS)和多个边缘设备(Edge Device, ED)组成。这里将 N = { 1 , 2 , , N } 定义为Eds的集合,EDn表示为边缘设备集合 N 中第n个ED,本文中假定所有ED的硬件配置是相同的,即计算能力相同。

2.1. 任务模型

本文将视频处理任务具体化为视频数据的目标检测任务,即设备端运行深度学习(Deep Learning, DL)模型检测视频中每一帧的目标物体并对其分类。在该MEC系统中,各ED每隔Δ秒到达一个视频任务的处理需求。首先,该视频任务的原视频格式转码为RGB格式,然后将RGB格式的帧数据输入到DL模型中进行目标检测,最后保存并分析DL模型推理结果,以完成整个视频任务。我们将系统时间定义为一个时隙集合 T = { 1 , 2 , , T } ,将EDn在t时刻( t T )到达的视频任务用二元组 ( B n ( t ) , D n ( t ) ) 表示。其中 B n ( t ) 表示视频任务数据大小,单位为(bit); D n ( t ) 表示其视频任务的时长,单位为(秒)。

本文采用对每个视频任务细粒度划分的方式,将单个视频任务切分为多个时长相等的视频块。每个视频块的时长由d表示,单位为(秒),一个视频任务 ( B n ( t ) , D n ( t ) ) 切分后的视频块的数量为 D n ( t ) / d 。这里为了简化问题模型,本文假定每个视频块的数据大小是相等的,即 B n ( t ) d / D n ( t ) bits。EDn在t时刻的视频任务被切分为 D n ( t ) / d 个视频块,那么MEC系统的卸载决策就转换为决定每个视频块是否卸载到MECS上,或其在本地设备处理。 λ n ( t ) 表示EDn对t时刻到达的视频任务的卸载决策,这里 λ n ( t ) [ 0 , 1 ] 。因此,对于任务 ( B n ( t ) , D n ( t ) ) ,卸载到MECS处理的视频块数量 M n o f f ( t ) 表示如下:

M n o f f ( t ) = λ n ( t ) D n ( t ) d (1)

项表示卸载到MECS的视频块数量必须为整数,因此根据式(1),剩下在本地设备EDn处理的视频块数量 M n l o c ( t ) = D n ( t ) / d M n o f f ( t ) 。每个视频块完成转码操作所需的CPU周期数为 C 0 ,完成DL模型推理所需的CPU周期数为 C 2

2.2. 时延模型

2.2.1. 本地计算模型

在本文的MEC系统中,每个视频块须进入其所属ED的处理队列中排队处理。本地计算模型中,每个ED包含两个处理队列,分别为转码队列和DL模型推理队列(下文简称推理队列),其在t时刻起始时长度分别为 Q n e , 0 ( t ) Q n e , 1 ( t ) 。对于EDn在t时刻视频任务中将在本地处理 M n l o c ( t ) 个视频块的第i个视频块,我们将 L n , i e , t c 定义为该视频块完成转码的预计时延,其计算方式如下:

L n , i e , t c = Q n e , 0 ( t ) f c e C 0 + i f c e C 0 (2)

上式(2)中 i [ 0 , M n l o c ( t ) ] f c e 表示各ED的CPU频率,单位为(周期/秒)。以第i个视频块为例,在完成转码后的RGB帧数据进入推理队列排队等待推理,因此其完成推理的预计时延表示为

L n , i e = max ( Q n e , 1 ( t ) f g e C 1 , L n , i l , t c ) + C 1 f g e (3)

式(3)中 max ( ) 项代表该视频块必须在其完成转码,并且推理队列中剩余任务完成推理后,才能开始推理。那么对于t时刻,EDn处理完全部任务的预期时延可表示为最后一个视频块在本地处理完成的时延:

L n e ( t ) = L n , M n l o c ( t ) e (4)

需要注意的是,推理结果通常为数据量较小的文本文件,因此结果的收集时延可以忽略不计。

2.2.2. 卸载计算模型

当EDn对视频任务 ( B n ( t ) , D n ( t ) ) M n o f f ( t ) 个视频块卸载到MECS处理时,其整个过程由三部分组成。

1) 转码:与本地处理模型一样的是,视频块的原数据格式需要转码为RGB格式。该过程所需时延与上一小节中本地计算模型 L n , i e , t c 的计算方式一致,这里不重复给出。

2) 传输:当一个视频块转码完成后,其进入EDn的传输队列 Q n t r a n s ( t ) ,视频块RGB帧数据通过无线信道传输至MECS。对于t时刻ED与MECS间的传输速率,我们定义为

v ( t ) = W ( t ) log 2 ( 1 + P v h σ 2 ) (5)

这里 W ( t ) 表示t时刻的上行信道带宽, P v 和h分别表示ED的传输功率和无线信道增益, σ 2 代表高斯白噪声功率。本研究假定在一个时间间隔内传输速率是保持不变的。对于第i个视频块,它开始传输前的等待时延

L n , i w a i t = max ( Q n e , 0 ( t ) C 0 f c e , B n ( t ) d Q n t r a n s ( t ) D n ( t ) v ( t ) ) (6)

式(6)中 max ( ) 项代表第i个视频块的转码及传输必须在其转码队列和传输队列的剩余任务均完成后才能开始。因此,第i个视频块到达MECS的时间可表示为:

L n , i a r r i = L n , i w a i t + max ( B n ( t ) d D n ( t ) v ( t ) , C 0 f l e ) (7)

上式中 max ( ) 项代表了第i个视频块从开始转码到传输完成所消耗时延的近似表示,这样做的原因是MEC系统中,转码和传输采用并行的方式进行,转码时产生的固定大小的数据包不断向MEC服务器传输。同时,当网络条件较好时,转码的同时ED以数据包的形式不断传输视频块数据,转码消耗的时延和视频块数据传输完成时延近似相等;当网络条件较差时,数据传输的时延远大于转码操作的时延, max ( ) 项近似等于其传输时间,即

max ( B n ( t ) d D n ( t ) v ( t ) , C 0 f l e ) B n ( t ) d D n ( t ) v ( t ) (8)

3) 推理:视频块到达MECS后,视频块RGB帧数据进入MEC服务器的推理队列,这里用 Q i n f ( t ) 表示。那么,EDn的第i个视频块输入DL模型前,所需的排队时间为 Q i n f ( t ) C 1 / f s ,这里 f s 表示MECS的CPU频率。则第i个视频块完成推理的预期时延可表示为

L n , i s = Q i n f ( t ) C 1 f s + i f s C 1 (9)

对于t时刻,EDn卸载 M n o f f ( t ) 个视频块任务到MECS,MECS处理完成的预计时延 L n s ( t ) ,即为最后一个视频块在MECS推理完成的时延:

L n s ( t ) = L n , M n o f f ( t ) s (10)

综上,t时刻到达EDn的视频任务 ( B n ( t ) , D n ( t ) ) 全部完成的预期时延为

L n ( t ) = max ( L n e ( t ) , L n s ( t ) ) (11)

因此对于t时刻整个MEC系统完成全部任务的预期时延,即全部ED的视频任务最后一个视频块完成的时间如下:

L ( t ) = max ( L 1 ( t ) , L 2 ( t ) , , L N ( t ) ) (12)

2.2.3. 优化问题

在本文中,我们将N个ED和一个MECS作为一个完整的MEC系统,将这N个ED的任务卸载问题形式化为一个优化问题。本文的优化目标是通过求解最优卸载决策 λ ( t ) = [ λ 1 ( t ) , λ 2 ( t ) , , λ N ( t ) ] 使整个MEC系统的时延成本最小化,该问题表示如下:

arg max λ ( t ) L ( t ) s .t . C 1 : 0 λ n ( t ) 1 , n N , t T C 2 : Q inf ( t ) + n = 1 N M n o f f ( t ) Q max , t T (13)

约束条件C1表示每个ED在时刻t的卸载率必须在0和1之间。C2表示MEC服务器端的队列长度不能超过其阈值 Q max ,即MECS的缓存容量是存在上限的,该阈值需根据MECS硬件配置情况设定,本文 Q max 取值将在实验部分给出。本文讨论的用于视频任务处理的MEC系统中,视频任务的处理时延作为重要的性能指标,因此将时延作为问题模型的优化目标。需要注意的是,该优化问题为NP难问题并且MEC系统的网络时变性也给问题的求解带来了挑战,因此本文考虑采用深度强化学习算法来解决该问题。

3. 基于DDPG的任务卸载方案

3.1. 马尔科夫决策过程

为求解上述优化问题,本文采用深度确定性策略梯度(Deep Deterministic Policy Gradient, DDPG)算法。DDPG算法是一种基于连续动作空间的无模型深度强化学习(Deep Reinforcement Learning, DRL)算法,与其他强化学习算法一样,其智能体(Agent)与所在环境不断进行交互,每次交互根据当前状态信息(State)采取动作(Action),然后从环境中获取奖励(Reward)。智能体通过不断地学习、更新模型权重,寻找最优的Action以获取更大的Reward。强化学习的求解首先需要建立马尔科夫决策过程(Markov Decision Processing, MDP),本文所研究的问题中状态空间、动作空间和奖励函数表示如下:

1) 状态:我们将S(t)定义为t时刻MEC系统环境的状态向量,其由当前时刻的上行带宽W(t)、全部ED的视频任务信息、全部ED的队列信息及MEC服务器的队列信息组成。状态向量S(t)的具体表示如下:

S ( t ) = [ W ( t ) , B ( t ) , D ( t ) , Q e , 0 ( t ) , Q e , 1 ( t ) , Q i n f ( t ) ] (14)

其中,表示任务信息的向量 B ( t ) D ( t )

B ( t ) = [ B 1 ( t ) , B 2 ( t ) , , B N ( t ) ]

D ( t ) = [ D 1 ( t ) , D 2 ( t ) , , D N ( t ) ]

Q e , 0 ( t ) Q e , 1 ( t ) 表示各ED在t时刻的队列状态,具体为

Q e , 0 ( t ) = [ Q 1 e , 0 ( t ) , Q 2 e , 0 ( t ) , , Q N e , 0 ( t ) ]

Q e , 1 ( t ) = [ Q 1 e , 1 ( t ) , Q 2 e , 1 ( t ) , , Q N e , 1 ( t ) ]

2) 动作:本文的动作空间由所有ED的卸载决策组成,即卸载率 λ n ( t ) , n N 。Agent在t时刻执行的动作用动作向量 A ( t ) 表示如下:

A ( t ) = λ ( t ) = [ λ 1 ( t ) , λ 2 ( t ) , , λ N ( t ) ] (15)

3) 奖励函数:在本文研究的MEC系统中,其优化目标是最小化系统时延成本。同时强化学习的目的是最大化奖励值,因此我们将奖励函数 R ( t ) 定义为系统时延的负相关函数,为

R ( t ) = L ( t ) (16)

3.2. DDPG算法

DDPG是一种基于行为–批评(Actor-Critic, AC)框架的无模型DRL算法,它能够在高维状态空间及高维连续动作空间求解最优策略 [7]。考虑到MEC环境中状态信息的高维度和连续性的特点,状态向量中每一时刻的 W ( t ) 的时变性以及到达任务的数据量 B ( t ) 与时长 D ( t ) 的随机性,本文决定利用DDPG算法,通过优化最优卸载决策来求解系统时延最小化问题。

DDPG算法的网络模型采用Actor和Critic两个模块,每个模块包含一个当前网络和一个目标网络。Actor当前网络根据t时刻的状态向量 S ( t ) ,输出并执行基于状态 S ( t ) 的动作 A ( t ) ,与环境交互后获得奖励 R ( t ) 且状态变为 S ( t + 1 ) 。将状态转移信息四元组 ( S ( t ) , A ( t ) , R ( t ) , S ( t + 1 ) ) 放入经验回放池中,每次从经验回访池中随机采样一定数量的样本通过梯度下降方式更新Critic当前网络和Actor当前网络。Actor和Critic各自的目标网络用于输出当前网络的目标值,其参数的更新采用延迟更新加软更新的方式,即Actor、Critic当前网络的参数每更新固定步长再更新一次目标网络。针对本文中MEC视频任务卸载系统的DDPG算法伪代码如下:

4. 仿真结果

4.1. 参数设置

本文实验均在Ubuntu 18.04 LTS系统下基于Python 3.7编程实现,深度强化学习算法基于Py Torch 1.7.0框架编程实现。实验中将NVIDIA Jetson NanoB01作为MEC系统中的边缘设备,同时MEC服务器搭载IntelCorei7-7700的CPU及NVIDIAGe Force GTX 2080 (8 GB)的GPU。MEC系统中涉及的其他参数如表1所示。

Table 1. Experimental parameters in MEC system

表1. MEC系统实验参数

仿真实验中网络带宽数据来自真实世界测得的500组网络动态序列。本文中DDPG算法的训练迭代轮数设定为3000,其他超参数设置为:Actor和Critic网络的学习率 α = 10 4 ,更新参数采用Adam优化器;经验回放池的大小为10,000,每次参数更新选取的批样本大小为64,衰减因子 γ = 0.99 ,目标网络软更新的程度为 τ = 0.005 ,探索噪声 ϵ = 0.1 。本次实验中Actor网络和Critic网络均由两层含有128个神经元的隐藏层及一层输出维度为N的输出层组成。

4.2. 实验结果分析

为了验证DRL算法的收敛性,首先我们从500组网络序列中随机抽样450组序列用于算法训练,剩余50组序列用于算法评估。如图1所示,我们测得了不同学习率 α 下的DDPG算法的收敛过程,ED数量设定为5,其他参数参照表1。从图中可以看出,在算法训练初期,智能体仍在探索学习阶段,奖励值普遍较低且振荡。在训练中后期,算法的奖励值趋于稳定,且不难看出,对于学习率 α = 10 3 的奖励曲线总是优于其他两个学习率奖励曲线。因此本文后续仿真实验采用基于学习率为10−3的DDPG算法。

同时,DDPG算法中的其他超参数也通过实验进行了收敛性比较,如图2所示,绘制了3000次训练迭代后不同批样本大小(Batch size)下的算法收敛情况。当批样本大小较小时,如4和8,算法无法从历史经验中有效学习,导致奖励值一直无法提高及收敛。对于批样本大小为16时,随着迭代次数的增加,奖励值虽有增大趋势,但仍然存在较明显的波动。当批样本大小增大到32和64时,DRL算法可以从中学习到有效信息,最后达到收敛。因此本文后续仿真实验中批样本大小设定为64。

Figure 1. The influence of different learning rates on convergence of DDPG

图1. 不同学习率对DDPG算法收敛性的影响

Figure 2. The influence of different batch sizes on convergence of DDPG

图2. 训练不同批样本大小对DDPG算法收敛性的影响

为了验证DDPG算法在MEC视频任务卸载系统下的性能表现,我们将其与其他基准卸载策略进行了性能对比。所选的基准策略分别为:

1) 全本地处理(AllLocal):在每一时刻t,各ED到达的新任务均在当前ED设备本地处理,即 λ n ( t ) = 0 , n N

2) 全卸载处理(AllOffload):在每一时刻t,所有新任务执行卸载策略,即 λ n ( t ) = 1 , n N

3) 随机卸载(RandomPolicy):对t时刻到达的新任务,各ED的卸载率为一个0到1的随机数,因此 0 λ n ( t ) 1 , n N

图3为任务到达时间间隔Δ下各卸载策略的系统时延对比(设备数量 N = 5 )。当Δ较小时,意味着视频任务到达的更加频繁,使得设备的处理压力更大。如图3所示,较小的Δ往往带来更高的系统时延成本,反之设备的处理压力不大的情况下,系统时延成本较低。更重要的是,从图3中不难看出,本文采用的基于DRL的DDPG算法总能优于其他卸载策略,从而实现较低的系统时延成本,同时也说明该算法可以适应不同的任务到达间隔。

图4为不同边缘设备数量下的MEC系统时延成本对比(任务到达间隔 Δ = 20 )。ED数量的增加直接导致任务数量的增加,当多个ED的视频任务都决定卸载到MECS时,使得MECS的处理压力加剧。如图4所示,整体上可以看出随着ED数量的增加,系统时延成本呈现增大趋势。全本地策略的时延成本相对全卸载策略变化较小,是因为所有ED选择在本地执行任务,ED数量增加并不会加剧MECS的处理压力。ED的增加使得随机卸载策略相较于前两者策略的优势愈发明显,由于ED随机性地卸载一定数量的任务到MECS,从而减轻了本地设备的压力,同时MECS也不会总是超载。最后,从图4可以看出,本文采用的DDPG算法通过在环境中不断的学习最优策略函数,联合优化所有ED的卸载决策,使得其系统时延能够优于其他卸载策略。

Figure 3. The system latency cost at different task arrival time slots

图3. 不同任务到达时间间隔下的系统时延成本

Figure 4. The influence of number of EDs on the system latency cost

图4. 边缘设备数量对系统时延成本的影响

5. 结论

本文针对MEC场景中视频数据任务的卸载问题建立数学模型,建立最小化时延成本的优化目标,并将原问题转化为MDP以通过深度强化学习算法求解,通过不断优化边缘设备的卸载决策,最终仿真实验证明了该方法较其他基准卸载策略能够有效地减少视频任务处理时延,降低MEC系统成本。但本文侧重于时延敏感型的任务卸载问题,未来的工作中考虑将系统的能耗加入到优化目标中,联合优化MEC系统的时延与能耗。除此之外,多ED场景下的博弈关系值得研究,即采用多智能体的方法求解多ED任务卸载问题。

文章引用

程浩宇. 基于DDPG的MEC视频任务卸载算法
Video Task Offloading Algorithm Based on DDPG in MEC[J]. 软件工程与应用, 2022, 11(01): 91-100. https://doi.org/10.12677/SEA.2022.111011

参考文献

  1. 1. Vhora, F. and Gandhi, J. (2020) A Comprehensive Survey on Mobile Edge Computing: Challenges, Tools, Applications. 2020 4th International Conference on Computing Methodologies and Communication (ICCMC), Erode, 11-13 March 2020, 49-55. https://doi.org/10.1109/ICCMC48092.2020.ICCMC-0009

  2. 2. Lin, H., Zeadally, S., Chen, Z., et al. (2020) A Survey on Computation Offloading Modeling for Edge Computing. Journal of Network and Computer Appli-cations, 169, 102781. https://doi.org/10.1016/j.jnca.2020.102781

  3. 3. Zhu, Z., Han, G., Jia, G., et al. (2020) Mod-ified Densenet for Automatic Fabric Defect Detection with Edge Computing for Minimizing Latency. IEEE Internet of Things Journal, 7, 9623-9636. https://doi.org/10.1109/JIOT.2020.2983050

  4. 4. Tang, M. and Wong, V.W.S. (2020) Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing Systems. IEEE Transactions on Mobile Computing, 1. https://doi.org/10.1109/TMC.2020.3036871

  5. 5. Ale, L., Zhang, N., Fang, X., et al. (2021) Delay-Aware and Energy-Efficient Computation Offloading in Mobile Edge Computing Using Deep Reinforcement Learning. IEEE Transactions on Cognitive Communications and Networking, 7, 881-892. https://doi.org/10.1109/TCCN.2021.3066619

  6. 6. Ranft, B. and Stiller, C. (2016) The Role of Machine Vision for Intelligent Vehicles. IEEE Transactions on Intelligent Vehicles, 1, 8-19. https://doi.org/10.1109/TIV.2016.2551553

  7. 7. Lillicrap, T.P., Hunt, J.J., Pritzel, A., et al. (2015) Continuous Control with Deep Reinforcement Learning. arXiv preprint arXiv:1509.02971

期刊菜单