车联网中基于DDQN 的边云协作任务卸载机制

于晶，鲁凌云，李翔

（1.北京交通大学 计算机与信息技术学院，北京 100044；2.北京交通大学 软件学院，北京 100044）

0 概述

随着人工智能、5G 移动通信和车联网技术的发展，大量的智能车载应用不断被开发，例如自动驾驶、碰撞预警、虚拟现实等［1］。然而，计算密集型和时延敏感型的任务对于车载终端来说无疑是一个巨大的挑战。移动云计算（Mobile Cloud Computing，MCC）能够将任务卸载到资源丰富的远程云服务器上，可以解决车辆计算能力不足的问题［2］，因此成为解决上述矛盾的一个关键技术，但远距离任务传输带来的时延无法满足安全类应用对实时性的要求［3］。对此，移动边缘计算（Mobile Edge Computing，MEC）被引入到车联网中，MEC 服务器被部署到道路两侧的路边单元（Road Side Unit，RSU）中，为车辆提供近距离的任务卸载服务［4］。相比于云计算卸载，边缘计算卸载不仅可以缓解车辆终端的资源不足，而且可以降低任务传输时延，缓解核心网络的压力。

目前，针对车联网中的任务卸载问题，国内外学者展开了大量研究，但大部分研究都是单独针对云计算卸载或者边缘计算卸载，很少有研究关注云计算和边缘计算的协作。此外，文献往往假设MEC 服务器具有足够资源，能够满足所有任务的卸载请求，然而事实并非如此。受硬件和成本的制约，MEC 服务器可提供的资源也相对有限，尤其是在车辆密集的区域，仅依靠边缘层可能无法满足海量数据的计算和存储［5］。由于云计算和边缘计算都拥有各自的优势，云服务器适合处理计算密集但对实时性要求低的任务，而边缘服务器更适合处理计算量小或者对时延敏感的任务，因此，让两者相互协作以实现优势互补逐渐吸引了大家的关注。在网络架构方面，软件定义网络（Software Defined Network，SDN）技术由于具备转控分离、集中控制、开放接口、可编程等特性，因此对于实现边云异构网络的有效协作具有重要意义［6］。

在车联网中，影响卸载决策的因素比如车辆位置、服务器资源、信道状态等都具有时变性，如果使用传统的最优化算法或者启发式算法来求解最优决策，不仅要对环境做出很多静态假设，而且每当有新任务时，都需要重新经历一次复杂度超高的计算［7］，这对于那些对时延极其敏感的安全类应用来说无疑是巨大的隐患。除此之外，现有的工作在制定任务卸载决策和资源分配方案时很少考虑车载应用的紧急程度，所以任务卸载到每个服务器的可能性是相同的，而且卸载到同一个服务器的任务分配到的资源也是相同的，这也许会导致对时延敏感的任务无法在限制时间内完成。为简化问题，很多采取部分卸载方式的方案中也会忽略车辆在上传任务过程中的移动性，并假设任务可以在剩余通信时间内上传完成，但这在实际应用中是不现实的。

为解决上述问题，本文综合考虑环境动态性以及任务优先级，提出基于双深度Q 网络（Double Deep Q Network，DDQN）算法的边云协作任务卸载机制，DDQN 算法在与环境交互过程中可以对未来的环境变化进行一定程度的估计，通过不断学习并调整策略实现长期效用最大化。同时，提出基于任务优先级的资源分配方案，使优先级越高的任务能分配到的资源越多。此外，给出一种基于确定卸载决策和资源分配方案的的卸载比例计算方法，在任务能够完成上传的前提下，最小化任务处理时间。

1 相关研究

针对车辆边缘计算环境中的任务卸载决策问题，目前已经有大量的研究工作。文献［8］提出一种基于遗传算法和启发式规则的混合智能优化算法，制定的卸载决策可以最小化时延和资源消耗。文献［9］对多用户多MEC 服务器场景中的负载均衡和任务卸载问题进行了联合优化。文献［10-12］也基于各种数值优化理论提出相应的任务卸载和资源分配方案。强化学习作为解决复杂环境下序列决策问题的强大武器，被学者们用来解决任务卸载问题。文献［13］将计算卸载调度问题形式化为优化时延和能耗组成的长期成本问题，并将其建模为一个等价的马尔可夫决策过程（Markov Decison Process，MDP），设计的基于深度强化学习（Deep Reinforcement Learning，DRL）的算法可以得到问题的最优解。然而，上述工作均假设MEC 服务器拥有足够多的计算和存储资源，但是在实际场景中，MEC 的资源受限于硬件和成本，在车辆密集的区域可能无法保证服务质量。

边缘计算与云计算的融合可以构建出更加高效可靠的边云协作任务卸载环境。文献［14］为充分利用云服务器和边缘服务器的资源，提出约束随机化卸载和约束启发式贪心卸载两种方案解决协同任务卸载问题。文献［15］通过构建一个云端-边缘-车辆三层协同的网络，将任务卸载决策问题形式化为收益和服务质量最大化问题，并提出由Kuhn-Munkres 算法、遗传算法、内点法和KKT 条件组成的算法求解上述非确定性多项式（Nondeterministic Polynomially，NP）问题。包括上述文献在内的很多工作都假设动态的车联网环境可以被准确地建模，然而，这在实际情况下很难做到。因此，能够摆脱模型限制的DRL 算法特别适合用来解决复杂动态车联网环境中的任务卸载问题。

文献［16］研究了边云协作环境中的非独立任务卸载问题，并且提出一个基于强化学习和序列二次规划的两级交替方法框架。文献［17-19］利用DRL算法解决了车联网中的任务卸载问题。近年来，利用SDN 协助车联网计算卸载的研究有一定的成果［20-22］，例如，文献［21］通过设计一种集成SDN 和MEC 的车联网框架，实现网络、缓存和计算的动态编排。文献［22］构建一种MEC 辅助的软件定义车联网架构，并提出一种带重处理机制的任务卸载方案，能够在满足时延约束的前提下最大化可靠性。

与现有工作相比，本文考虑了车联网的时变性、任务的优先级、通信链路的持续时间以及计算资源成本对任务卸载决策制定的综合影响。还提出一种基于DDQN 的算法来学习任务卸载决策，该算法可以最大化由时延和成本构成的长期效用。

2 系统模型

2.1 系统架构分析

如图1 所示，本文构建的基于SDN 的边云协作车联网架构在逻辑上由用户层、数据层和控制层组成。

图1 基于SDN 的边云协作车联网架构Fig.1 Architecture of edge-cloud collaborative vehicular network based on SDN

用户层由行驶在一段单向双车道公路上的车辆用户构成。本文假设每个时隙最多有n个车辆，车辆集合记为N={1，2，…，n}。每个车辆在同一时隙最多可以拥有一个待处理的任务，车辆i的任务描述为Ti={di，ci，，θi}，其中：di是任务的总数据量，单位为比特（bit）；ci是完成任务Ti所需要的CPU 周期数；是任务可以容忍的时延上限；θi(0 ≤θi≤1)是任务的卸载比例，为充分利用车辆本地的计算资源并进一步降低任务处理时延，本文采取部分卸载方式，将(1-θi)比例的任务留在本地处理，将车辆可用计算资源记为Flocal=

数据层由边缘卸载计算层和云卸载计算层构成，负责执行用户层车辆卸载的计算任务。其中，边缘计算层是由m个依次部署在RSU 中的边缘服务器构成，边缘服务器资源相对比较少，主要负责执行对时延要求高或者对计算资源要求少的任务。车辆会通过无线车辆到基础设施（Vehicle-to-Infrastructure，V2I）链路将任务上传到其通信范围内的中继RSU中，然后中继RSU 通过有线基础设施到基础设施（Infrastructure-to-Infrastructure，I2I）链路将任务转发给目标MEC 服务器执行。m个边缘服务器当前可用的资源可以表示为Fmec=云计算层由1 个部署在基站（Base Station，BS）中的云服务器构成，云服务器具有充足的资源，用表示。但是远距离的任务传输会产生不可预测的时延，安全和隐私也得不到保障，所以云服务器的主要作用是弥补边缘计算层资源的不足。一些计算量大且对时延要求较低的任务会被卸载到云服务器执行，中继RSU 通过有线光纤链路将任务转发到云服务器中。本文构建的边云协作计算卸载环境可以通过优势互补的方式克服云计算和边缘计算各自的缺点，充分发挥各自的长处。

控制层主要是指部署在基站中的SDN 控制器。逻辑上集中的SDN 控制层具有瞬时获取全局网络状态的能力，可配置、可编程、对第三方开放的网络基础能力等一系列突破对于实现边缘计算和云计算的有效协作具有重要意义，能够帮助实现两者的优势互补，满足边云协作计算网络对于统一控制、任务合理卸载和资源有效分配的需求。

在本文构建的基于SDN 的边云协作计算环境中，车辆的计算任务会被部分卸载到云服务器或边缘服务器中执行，所有车辆在某个时隙的卸载决策集合可以表示为X={α1，α2，…，αi，…，αn}，其中，αi∈{0，1，2，…，m}，当αi=0 时，表示车辆i的任务将被卸载到云服务器执行；当αi=j，j∈{1，2，…，m}时，表示车辆i的任务将被卸载到编号为j的边缘服务器上执行。

2.2 任务优先级设定

考虑到车载应用的多样性，比如碰撞预警这类对时延要求极高的安全类应用、语音识别这类对时延不敏感的娱乐性应用等，本文将抽象出一个任务优先级的评定标准，用于指导计算资源的分配以及卸载策略的制定。除了任务的紧急程度，任务所需的计算量也是任务卸载和资源分配时必须参考的指标，任务的优先级可以定义为式（1）所示：

其中：psf是缩放系数，用来调整任务计算量或者时延对优先级的影响程度。式（1）表明，任务所需计算量越大，或者任务所能容忍的最大时延越小，任务的优先级越高。

2.3 通信模型

行驶在道路上的车辆需要将任务通过无线V2I链路传给中继RSU，链路的传输速率直接影响任务的上传时间。根据香农公式，车辆i与编号为k的中继RSU 之间的无线数据传输速率Ri，k可以利用式（2）计算得到：

其中：Bi，k是信道带宽；Pi，k是车辆i的发射功率；σ2是噪声功率；信道增益Gi，k与车辆和RSU 之间的距离di，k密切相关，具体关系可以表示为Gi，k=-30-35lg(di，k)［23］。此 外，本文还假设车辆 和RSU 之间的无线通信采用了正交频分多址技术，所以忽略了信道之间的干扰。

2.4 计算模型

本文除了将任务处理时延作为评价指标，为了避免计算资源的浪费，还引入成本这一因素来指导决策的制定。本文采取部分卸载方式，将任务在本地和服务器中按比例并行处理。任务Ti在本地处理部分所需时间的计算式如式（3）所示：

任务在本地处理时不消耗服务器的资源，所以没有成本。卸载处理的那部分任务有边缘服务器和云服务器两类选择。

2.4.1 边缘卸载

当αi=j，j∈{1，2，…，m}时，车辆i的任务将被卸载到编号为j的MEC 服务器中执行。任务的上传时间计算式如式（4）所示：

其中：δi用来调整时延和成本所占的权重；Ce是MEC服务器的单位计算资源成本；Gsf是缩放因子，用来将成本值调整到合适的取值范围内。

2.4.2 云卸载

当αi=0 时，车辆i的任务将被卸载到云服务器中执行。任务的传输时间计算式如式（9）所示：

其中：υfiber=1 μs/bit，是RSU 到云服务器的单位数据传输时延是返回的执行结果数据量，一般远小于输入的数据量，所以往往忽略其占用的传输时间。

任务的执行时间计算式如式（10）所示：

其中：Cc是MCC 服务器的单位计算资源成本。

2.5 效用函数

基于以上定义，可以得到一个用于衡量卸载决策和资源分配方案优劣的效用函数：

式（14）表示所有任务的平均效用，并且将任务的优先级作为系数进一步加强任务优先级的重要性。其 中，X是问题的解，当αi∈{1，2，…，m}时，ui=，当αi=0 时，ui=。因此，在求解卸载策略和资源分配方案时，优化目标就是最大化上述由时延和成本构成的效用函数。

3 边云协作任务卸载机制

车辆移动性、计算资源、信道状态的时变性等因素导致车联网环境的高度不确定，此时将任务卸载决策问题建模为MDP 过程，这是一种高效的解决方案。尽管在理论上可以采用动态规划或者启发式算法求解MDP，但其超高的计算复杂度无法满足车载应用对实时性的要求。此外，MDP 的状态转移概率矩阵也很难获取，在这种情况下，不基于模型的强化学习（Reinforcement Learning，RL）算法可以用来获取最优策略。RL 算法不需要任何先验知识，通过不断与环境交互学习，最终获得的决策模型可以实现长期效用最大化。近年来，深度强化学习算法又利用神经网络强大的近似能力解决了RL 算法状态空间有限的问题。

因此，本节首先将效用优化问题转化为马尔可夫决策过程，并采用深度强化学习方法求解最优策略。然后，阐述在任务卸载策略已知情况下的基于优先级的资源分配方案。最后，在卸载策略和资源分配方案已知的情况下，以最小化任务处理时间和保证传输可靠性为目标，给出任务最佳卸载比例的计算方法。

3.1 基于DDQN 的任务卸载决策机制

DDQN［24］是一种基于价值的深度强化学习算法，适用于车辆任务卸载这种具有大规模离散动作空间的场景。DDQN 的核心思想是使用深度神经网络近似代替动作价值（以下简称“Q值”）函数，将环境状态作为输入，输出是每个动作对应的Q值，其中最大Q值对应的动作将成为当前最优策略，环境也会反馈一个奖励值来评价动作的好坏，同时也用来优化神经网络的参数，然后环境将进入下一个状态，不断循环上述过程直到收敛。

本节首先阐述MDP 的3 大要素，即状态空间、动作空间和奖励函数，然后介绍动作价值函数以及最优策略的定义，最后给出动作价值网络的更新过程。

3.1.1 状态空间

具有全局信息瞬时收集能力的SDN 控制器恰好可以承担DRL 中智能体这一角色，在每个时隙中，SDN 控制器监控其通信范围内的车联网环境，并且收集状态信息，包括车辆位置、车辆任务、以及边缘服务器和云服务器的资源可用信息。定义状态空间为S，t时隙的状态s(t)如下：

3.1.2 动作空间

根据t时隙观察到的状态s(t)，智能体会输出一个动作作为当前时隙采取的卸载策略。定义动作空间为A，t时隙的动作a(t)如式（16）所示：

其中：αi(t)，i∈{0，1，…，n}是车辆i在t时隙的卸载目标服务器，其他两类动作，即ϕj(t)，j∈{1，2，…，m}和ϕ0(t)分别是边缘服务器和云服务器在当前时隙提供的资源比例，用来降低资源成本，尽量用更少的资源完成更多的任务。

3.1.3 奖励函数

在t时隙，智能体根据状态s(t)给出动作a(t)之后，环境立刻反馈一个奖励Rt，如式（17）所示。该奖励值可以用来评价动作a(t)的好坏，并指导价值网络参数的更新。

3.1.4 动作价值函数

强化学习算法关注的是系统长期效用最大化，即从当前时隙到结束时隙的累计效用最大。t时隙的长期累积折扣效用可以表示为Ut=Rt+γRt+1+γ2Rt+2+…+γ3Rt+n，其中，γ是折扣因子，未来时隙的奖励对当前时隙的影响要打一个折扣。由于状态转移和动作选择的不确定性，在当前时隙，很难得到准确的Ut。在上述情况下，通过马尔可夫性假设和求期望的方式可以消除随机性，得到只与当前时隙的状态st和动作at有关的动作价值函数Qπ(st，at)，其计算式如式（18）所示：

3.1.5 最优策略的定义

解决强化学习问题意味着要寻找一个最优策略π*，该策略使个体在与环境交互过程中获得的效用始终大于其他策略。一般来说，很难直接找到这个最优策略，只能通过比较若干不同策略的优劣来找到一个相对比较好的策略，也就是局部最优解。比较策略的优劣可以通过比较策略产生的动作价值实现，最优策略对应的动作价值优于其他策略的动作价值。所以，基于最优动作价值，可以给出最优策略的定义如式（19）所示：

从式（19）可以看出，在当前状态下，最大Q值对应的动作就是最优动作。因此，可以通过比较当前状态下所有动作的Q值来找到最优动作。

3.1.6 动作价值网络的更新

根据贝尔曼方程，可以得到t时隙的动作价值和t+1 时隙的动作价值的递推关系，如式（20）所示，利用该公式，在理论上可以求出所有情况的Q值。

然而，对于状态空间很大的复杂场景，使用动态规划或者Q-learning 这种传统的方式计算Q值将产生巨大的时间和内存成本，这明显不适用于本文场景。深度强化学习解决上述问题的方式是利用神经网络近似计算Q值，参数为ω的动作价值网络将状态作为输入，输出不同动作的Q值，神经网络的正向传播所需计算量极小。所以，解决深度强化学习问题的核心变成了动作价值网络参数的训练，不断优化网络参数，使计算出的Q值尽可能接近真实值。

在深度强化学习算法中，同样使用梯度下降法更新神经网络的参数，此时需要一个真实值与神经网络的估计值进行比较，但真实值却无法获得。根据式（20）可以得到式（21）：

使用γQπ(st+1，at+1)近似代替γE[Qπ(st+1，at+1)]后，式（21）的等号左边变成Qπ(st，at)-γQπ(st+1，at+1)，Qπ(st，at)和Qπ(st+1，at+1)都可以通过神经网络计算，而等号右边是t时隙获得的真实奖励，使Qπ(st，at)和Qπ(st+1，at+1)的差值尽量接近Rt是神经网络的优化目标。根据贪心策略，下一个状态st+1是在状态st下执行最优动作at得到的，然后将st+1作为输入，计算得到的Q值中，选取最大Q值用于参数更新。此时，可以得到均方差损失函数，如式（22）所示：

原始DQN 算法使用同一个神经网络计算Qπ(st，at)和Qπ(st+1，at+1)，导致相关性太强，不利于收敛。对此，Natural DQN 算法使用两个结构相同的网络来分别计算Qπ(st，at)和Qπ(st+1，at+1)，并将计算当前时隙Qπ(st，at)的网络称作当前Q网络，将计算Qπ(st+1，at+1)的网络成为目标Q网络，目标Q网络无需训练，只是定期从当前Q网络复制参数过来，以减少目标Q值计算和神经网络参数更新的依赖关系。然而，使用贪心策略选择最大的Qπ(st+1，at+1)这种方式会导致过度估计的问题，使训练得到的模型有很大的偏差。对此，在Natural DQN 的基础上，DDQN算法解耦了目标Q值动作的选择和目标Q值的计算，先利用当前Q网络选出下一个状态下Q值最大的动作a′=(st+1，at+1，ω)，然后从目标Q网络获得动作a′对应的Q值，即(st+1，a′，ω′)，值得注意的是，此时的目标Q值未必是最大值。以上是对算法思想的介绍，基于DDQN 的任务卸载决策算法具体描述见算法1。

算法1基于DDQN 的任务卸载决策算法

3.2 基于优先级的资源分配方案

本文提出一个基于优先级的资源分配方案，优先级越高的任务可以分配到越多的计算资源，相比于平均分配的方式，可以提高高优先级任务的完成率。通过上一节的策略模型可以得到当前时隙的卸载策略，在此基础上，本节首先根据优先级计算任务的资源分配系数，然后为其分配相应比例的计算资源。

3.2.1 边缘服务器的资源分配

如果车辆i的卸载目标服务器的编号为j，那么任务Ti的资源分配系数λi如式（23）所示：

其中：mecj代表卸载目标为编号j的MEC 服务器的车辆集合。

任务Ti分配到的资源如式（24）所示：

3.2.2 云服务器的资源分配

如果车辆i的卸载目标服务器为云服务器，那么任务Ti的资源分配系数λi如式（25）所示：

其中：mcc0代表卸载目标云服务器的车辆集合。任务Ti分配到的资源如式（26）所示：

3.3 卸载比例计算

4 实验结果与分析

本文通过python 语言对本文算法进行仿真并分析其性能。仿真场景是由1 个云服务器、3 个边缘服务器和若干车辆用户组成的云-边-车辆3 层结构。环境参数和神经网络的参数设置如表1 所示。

表1 参数设置Table 1 Simulation parameters

为验证本文算法的性能，选择以下5 种算法进行比较。

1）Natural DQN 算法。该算法是一种深度强化学习算法，在仿真实验中，除了目标Q值的计算不同，其他均与本文算法保持一致。

2）模拟退火算法。与本文算法的区别是，该算法在每次迭代中会随机选择任务的卸载目标服务器，并以所有任务的平均效用作为优化目标，所以只要迭代的次数足够多，在理论上可以找到使平均效用最大的策略。

3）平均分配资源算法，在资源分配时，不考虑任务的优先级。

4）全部卸载处理算法，任务全部卸载处理。

5）全部本地处理算法，任务全部留在本地处理。

图2 是本文算法和Natural DQN 算法的收敛过程，为更清晰地展示2 个算法的差别，图2（b）进一步放大了前2 000 步的迭代过程。可以看出在迭代400步以后，Natural DQN 算法的波动更明显，而且均方误差大于本文算法，这恰好验证了Natural DQN 算法对于目标动作价值的过渡估计。此外，本文算法在迭代2 000 步左右就已经完全收敛，而Natural DQN的曲线在迭代8 000 步左右才趋于一条稳定的直线算法。

图2 不同算法的损失值变化Fig.2 Loss value change of different algorithms

图3 是不同算法产生的平均任务处理效用。将MEC 和MCC 服务器的数量分别固定为3 和1，针对10 种不同的车辆数进行对比实验。由图3 可知，随着任务数量的增多，除了全部本地执行算法以外的所有算法产生的平均效用都呈现下降的趋势，这是因为分配给每个任务的计算资源逐渐减少，导致完成任务所需的时间增多。全部本地执行算法的性能最差，而模拟退火算法获得了效用最大的卸载决策，但是付出了很高的时间成本，相反，本文算法和Natural DQN 算法却可以在极短的时间内获得近似最优解。此外，相比于平均分配资源这种方式，本文算法在效用方面获得了3 倍以上的提升，这说明本文基于优先级的资源分配方式让资源得到了更好的利用。最后，相比于全部卸载执行算法，本文算法采取部分卸载的方式显然更加合理，效用至少提高了2 倍。

图3 不同算法的平均任务处理效用Fig.3 Average task processing utility of different algorithms

图4 是不同算法产生的平均任务处理时延。可以看出，除了全部本地执行算法，随着任务数增多，其他算法的平均时延都逐渐增多，这是因为任务分配到的资源变少，而全部本地执行算法主要与本地资源量有关，不受任务数量影响，所以变化较小。除了模拟退火算法，本文算法在时延性能方面要优于其他算法，其中，全部卸载算法卸载的任务量最大，所以产生的时延大幅增长。仔细观察还可以发现，时延与效用的关系并不绝对，因为所有算法的优化指标都是效用，而效用由时延和成本两部分构成，所以效用大不代表时延小。

图4 不同算法的平均任务处理时延Fig.4 Average tasks processing delay of different algorithms

图5 和图6 分别是任务和高优先级任务的完成比例。首先，在资源总量不变的情况下，当任务数量增加到一定程度时，任务的完成率将不可避免地下降，其中，全部卸载算法由于卸载的任务量大及浪费了本地资源，所以任务完成率很低。而对于全部本地执行算法，利用有限的本地资源，几乎很难在规定时间内完成任务，任务量大且时延敏感的高优先级任务完成比例甚至均为0。其次，本文算法的任务和高优先级任务完成比例都最接近模拟退火算法，在任务数适中的情况下，任务完成比例可以稳定维持在100%。由于在卸载决策制定和资源分配时都将优先级作为参考标准，因此相对于平均分配资源算法，本文算法能大幅提升高优先级任务的完成比例。

图5 不同算法的任务完成比例Fig.5 Success rate of tasks processing of different algorithms

图6 不同算法的高优先级任务完成比例Fig.6 Success rate of higher priority tasks processing of different algorithms

5 结束语

为缓解车载应用日益丰富与车辆资源有限之间的矛盾，本文构建一种基于SDN 的边云协作车联网计算卸载架构，并将任务卸载问题建模为马尔可夫决策过程，把时延和计算资源成本构成的效用作为优化目标，提出基于DDQN 的任务卸载机制和基于任务优先级的资源分配方案。通过在卸载决策制定和资源分配过程中考虑任务优先级因素，提高系统平均效用及降低任务处理时延。实验结果表明，本文提出的卸载比例计算方法在一定程度上提高了任务传输的可靠性，实现当前策略的时延最小化。下一步将引入无线电干扰等复杂因素，构建更加符合实际场景的通信模型。