一种基于深度强化学习的任务卸载方法*

高宇豆 ，黄祖源 ，王海燕 ，保 富 ，张 航 ，李 辉

(1.云南电网有限责任公司 信息中心，云南 昆明 650214；2.西南林业大学 大数据与智能工程学院，云南 昆明 650224)

0 引言

车联网(Internet of Vehicle，IoV)是车载网(Vehicular Ad hoc Network，VANET)和物联网(Internet of Things，IoT)的深度融合，旨在提高车辆网络的性能，降低交通拥堵的风险[1]。在车联网中，许多车辆应用不仅需要大量的计算资源，还对响应时间有严格的要求[2]。但是，车辆是计算资源和通信能力有限的装置。对于这些计算密集、延迟敏感的应用，车辆无法提供足够的计算和存储资源[3]。

为应对车载应用所需的大量计算资源，云计算被视为一种可行的解决方案。在云计算环境下，车辆可以通过无线网络将计算密集型应用卸载到云上运行。这种端-云协作的计算模式很好地扩展了车辆的计算能力[4]。

然而，对于计算密集、延迟敏感的应用，端-云协作的计算模式是不够的。因为，远程任务卸载带来的高传输延迟会降低用户体验[3]。为解决此问题，将车联网和边缘计算相结合的车辆边缘计算，被认为是满足低延迟的更好解决方案[5]。

但是，由于边缘服务器具有的计算资源和存储资源是有限的，过多的卸载任务会导致边缘服务器过载[6]。在边缘服务器过载情况下，任务的等待时间会显著延长，从而增加任务的完成时间。为此，本文提出了一种车联网中基于深度强化学习的任务卸载方法，主要贡献包括以下几点：

(1)把以最小化任务完成时间为目标的多任务卸载问题规约为优化问题；

(2)提出了一种基于深度强化学习的任务卸载算法，使用深度强化学习来求解上述优化问题；

(3)通过实验，验证了所提算法的有效性。

1 相关工作

相关学者使用动态规划方法对任务卸载进行了研究。文献[7]使用二次约束二次规划方法，提出了一种两层计算卸载框架，用于将移动用户和小基站的计算密集型任务分别卸载到移动边缘服务器和宏基站；文献[8]基于混合整数线性规划方法，提出一种对边缘云上的计算、缓存和通信进行联合优化的方法；在此基础上，文献[9]提出了一种基于混合整数非线性规划的任务卸载方法，实现了在节省用户设备电池寿命的同时最大限度地减少延迟。这些工作主要将计算卸载问题规约为凸优化问题，使用动态规划方法对问题进行求解。但是，车辆边缘计算环境下的任务卸载未必总是凸优化的。

相关学者使用博弈论对任务卸载进行了研究。文献[10]将移动设备用户间的分布式计算卸载决策问题规约为一个多用户计算卸载博弈，并设计了一个可以达到纳什均衡的分布式计算卸载算法；文献[11]使用博弈论，提出了一个移动感知的分层边缘计算框架，实现同时降低智能设备的能源成本和任务执行时间；文献[12]研究了基于端-边-云车联网下的计算卸载机制，提出了各种基于博弈论的任务卸载优化策略，可用于边缘服务器的选择和任务传输管理。这些工作仅考虑了卸载策略对系统一个快照的最优方案或接近最优方案，未考虑车辆边缘计算环境下当前策略对资源分配的长期影响。

与上述工作相比，本文工作的主要区别在于：使用深度强化学习方法来求解车辆边缘计算环境下的任务卸载问题。由于深度学习方法能提高对车辆网络的认知能力，因此该方法能更好地学习到任务卸载的复杂特征。

2 本文方法

2.1 车辆网边缘计算架构

本文将考虑多任务的车辆网边缘计算架构。此架构由1 个基站(Base Station，BS)、k 辆车、m 个路侧单元(Road Side Unit，RSU)和m 个边缘服务器组成，其中，车辆集表示为V={v1，v2，…，vK}，路侧单元集表示为R={r1，r2，…，rM}，边缘服务器集表示为S={s1，s2，…，sM}。在此架构下，借鉴文献中基站的思想[13]，本文将基站作为控制实体，用于获取边缘计算可用资源、信道可用资源、任务信息等；道路旁的每个路侧单元配备了一个边缘服务器；每个边缘服务器可为其覆盖范围内的车辆提供计算和存储资源；车辆是任务的产生者，通过无线网络与路侧单元进行通信。

在给定的时间间隔t，每辆车可以产生多个任务。每个任务表示为二元组Ti，j=＜di，j，ci，j＞，其中，di，j表示执行第i 辆车产生的第j 个任务所需的数据量的大小，ci，j表示执行第i 辆车产生的第j 个任务所需的计算量的大小，i∈[1，2，…，K]，j∈[1，2，…，J]。这些任务通路侧单元可以被卸载到边缘服务器上执行。

2.2 本地计算模型

当车辆vi产生的任务Ti，j在本地执行时，则该任务的完成时间由两部分组成：执行时间和等待时间，定义如下：

2.3 卸载计算模型

当车辆vi产生的任务Ti，j被卸载到边缘服务器执行时，则该任务的完成时间由四部分组成：任务所需数据的传输时间、任务在边缘服务器的执行时间、任务在边缘服务器的等待时间和执行结果返回时间，定义如下：

进一步，本文考虑车辆与路侧单元间的无线传输是基于正交频分多址的，则数据传输率si，l又由分配给任务的上行线路的带宽、车辆的传输功率ρi、车辆与路侧单元间的信道增益决定λi，l。于是，数据传输率的定义如下：

其中，B 表示上线线路的带宽，N 表示将带宽分为N 份，σ 表示高斯噪声。

其中，αe表示边缘服务器每个计算单元的计算能力(单位为GHz)，βe表示边缘服务器分配车辆给任务的单元数。

2.4 问题定义

在多任务的车辆边缘计算架构下，任务卸载的目标是：通过优化任务卸载决策，最小化任务的完成时间。

首先，需要定义任务卸载决策。由于每个任务要么在本地执行，要么被卸载边缘服务器执行，故而，任务卸载决策可以定义为：

其中，αi，j为卸载决策变量，其定义如下：

其次，定义每个任务的完成时间。基于卸载决策变量，任务的完成时间定义如下：

最后，基于上述分析，以最小化任务完成时间为目标的多任务卸载问题可以规约为一个如下所示的单目标优化问题：

3 基于深度强化学习的任务卸载

本节将提出一种基于深度强化学习的任务卸载算法，使用DQN 来求解优化问题。该算法主要包括四部分内容：(1)设置DQN 的配置；(2)基于DQN 的任务卸载算法；(3)基于ε-贪婪策略的动作选择；(4)使用经验回放来更新DQN。

3.1 DQN 的配置

DQN 是一种基于值的深度强化学习方法，将强化学习和深度学习进行了很好的结合。其核心是：使用神经网络来近似传统Q-Learning 算法中的Q 函数[14]。本文选择DQN 的原因是：在面对高维空间的复杂问题时，DQN能够很好地学习到优化策略。

在多任务的车辆边缘计算架构下，为了利用DQN，需要设置DQN 的配置，包括agent、环境、状态和奖励。

首先，在基站上部署agent。agent 通过一系列的观察、动作和奖励对环境做出反应。具体地，当收到来自车辆的任务请求时，agent 根据当前观察(状态)选择动作，并确定卸载决策变量。然后，agent 将卸载决策变量回传给车辆，以指示车辆是否卸载该任务。任务执行结束后，再将任务的本地完成时间与边缘服务器上完成时间的差值作为奖励反馈给agent。

其次，环境由车辆网络组成，主要包括边缘服务器的计算资源、路侧单元的带宽资源和任务信息。其定义如下：

然后，在时间步τ，观察（状态）由边缘服务器的可用计算资源和路侧单元的可用带宽资源组成。其定义如下：

最后，在时间步τ，对于任务Ti，j，动作a 的奖励由任务的本地完成时间与边缘服务器上完成时间的差值组成。其定义如下：

3.2 卸载算法框架

当动作和状态对空间变得高维连续时，传统的QLearning 算法遍历高维Q-table 是非常耗时的。为了解决这一问题，DQN 使用深度神经网络来近似Q(s，a)。基本思想是：首先，agent 根据对当前环境观察得到状态s；其次，将状态s 作为深度神经网络的输入，得到神经网络输出的多个Q(s，a)；然后，使用ε-贪婪策略从这多个Q(s，a)中选择一个动作a，与此同时，环境将响应选定的动作，给出奖励r，并演化到新状态s'；最后，将(s，a，r，s')存入经验池D，并使用D 更新DQN。

基于上述分析，算法1 给出了基于DQN 的任务卸载算法框架，记为DQN。

算法1 基于DQN 的任务卸载(DQN)：

输入：预测网络Qpre，预测网络的参数θpre，目标网络Qtar，目标网络的参数θtar，经验池D，当前状态sτ；

输出：预测网络和目标网络。

在动作选择上，DQN 引入了ε-贪婪策略。具体地，agent 采用1-ε 概率来选择最大Q 值的动作，采用概率ε来随机选择动作。因此，基于ε-贪婪策略的动作选择可定义为：

3.3 DQN 网络更新

为了进一步打破数据间的关联性、防止过拟合，在训练过程中，DQN 使用了预测网络Qpre和目标网络θtar。具体地，针对当前的动作对(s，a)，预测网络Qpre使用最新参数θpre预测当前Q 值，而目标网络使用很久前的参数θtar得到目标Q 值。与预测网络相比，目标网络的结构完全相同，但参数不同。

DQN 的代价函数可以定义如下：

其中，ri是当前获得的奖励，γ 是折现系数。

基于损失函数，算法2 描述了DQN 的更新过程。

算法2 DQN 网络的更新：

输入：预测网络Qpre，预测网络的参数θpre，目标网络Qtar，目标网络的参数θtar；

输出：θpre，θtar。

(1)从经验池中随机采样得到Dτ；

(2)使用式(18)计算目标Q 值yi；

(3)使用式(17)计算代价函数Li(θi)；

(4)对Li(θi)使用梯度下降，以更新预测网络Qpre中的参 数θpre；

(5)每C 步后，使用参数θpre更新目标网络Qtar中的参 数θtar；

(6)输 出θpre和θtar。

4 实验

4.1 实验设置

实验考虑包含10 个RSU、10 辆车、30 个任务的场景。进一步，实验模拟环境所需的参数设置如表1 所示。

表1 参数设置

实验中，本文选择下述3 个基准算法，与本文所提DQN 方法进行对比。

(1)本地任务卸载(LTO)。车辆产生的所有任务全部在本地执行。

(2)随机任务卸载(RTO)。车辆产生的任务随机卸载到边缘服务器执行。

(3)边缘任务卸载(ETO)。车辆产生的所有任务全部卸载到边缘服务器执行。

4.2 平均完成时间的比较

图1 直观显示了30 个任务平均完成时间的对比。从图1 可以看出：本文所提方法DQN 的性能优于其他3种基准算法。相比于表现最差的LTO 算法，DQN 算法的性能提升了15.5%；相比于表现较好的ETO 算法，TODQN算法的性能提升了4.1%。这是因为DQN 算法同时充分考虑了车辆边缘计算环境下的计算资源和带宽资源，而基准算法没有考虑这些资源对任务完成时间的影响。

图1 平均完成时间的对比

4.3 参数对算法性能的影响

本实验研究了各种参数对算法性能的影响，例如任务的数量、任务所需的数据量。

(1)任务的数量：本实验中，其他参数保持不变，任务数量从30 增加到70。从图2 可以看出，随着任务数量的增多，任务总完成时间开始增加。相比于其他3 种基准算法，DQN 算法的增加幅度最小。这是因为DQN 可以合理地利用车辆的计算资源和边缘服务器的计算资源。

图2 任务数量变化对总完成时间的影响

(2)任务计算量：本实验中，其他参数保持不变，任务所需的计算量从0.5 Gigacycle 增加到1.3 Gigacycle。从图3可以看出，随着任务计算量的增加，所有算法的总完成时间都在增加，尤其是ETO 算法的性能逐渐低于RTO算法。这是因为边缘服务器过载造成的。与ETO 和RTO相比，DQN 能很好地解决边缘服务器过载的问题。

图3 任务计算量变化对总完成时间的影响

5 结论

本文提出了一种车辆边缘计算环境下基于深度强化学习的任务卸载方法。该方法使用DQN 对任务卸载问题进行求解，可以得到具有最小完成时间的优化卸载策略。通过实验结果表明，该方法具有良好的性能。在下一步的研究工作中，将同时考虑任务完成时间和缓冲内容的任务卸载。