车载边缘计算系统中一种有效的资源分配策略

陈国龙，李现伟*，黄迎辉，许东波

(1.蚌埠学院 计算机与信息工程学院，安徽 蚌埠 233030;2.蚌埠市精彩电子科技有限公司，安徽 蚌埠 233030)

随着网络通信技术和物联网技术的进步，车载网(Internet of Vehicles，IoVs)近年来得到了飞速的发展，已经成为5G的重要应用场景[1]。以自动驾驶和图像辅助导航为代表的各种车载应用不断出现，这些车载应用涵盖了安全驾驶和信息娱乐等各个方面[2-3]。在方便人们生活的同时，这些应用也产生了需要大量计算资源和低延迟处理的数据，这对网络带宽和计算资源提出了更高的要求[4]。由于车辆设备的计算资源有限，已不能满足车载大数据的处理要求。移动边缘计算(Mobile Edge Computing，MEC)的出现为解决这个问题提供了方案。通过把计算资源部署在网络的边缘端，移动边缘计算为云资源服务的本地化提供了可能[5]。通过把MEC技术和车载网技术进行结合，车载边缘计算(Vehicular Edge Computing，VEC)为处理车载应用所产生的大数据提供了新的解决方案[4,6]。在VEC系统中，车辆应用产生的数据可以卸载到路边单元(RSU,Road Side Unit)的MEC服务器上来完成应用的处理和数据的分析，从而缓解车辆计算资源的不足以及降低处理应用的时间和能耗[7-8]。

近年来，国内外研究人员针对MEC和VEC中的资源分配和数据处理问题进行了大量的研究。文献[1]针对车联网中车辆终端多媒体业务量的增长导致大量数据增加带来的延迟和能耗问题，研究了基于MEC的车联网中的计算资源、缓存资源和功率资源的分配问题，提出了一种有效的资源分配机制。仿真实验结果验证了所提出的机制的有效性。文献[2]研究了VEC中缓存资源和计算资源的分配问题，设计了一种联合缓存资源和任务处理的机制，对缓存资源和计算资源的调度进行了优化，以此降低任务的处理时间。文献[3]针对车联网环境下车辆数据传输的问题提出了一种调度算法，实验结果表明所提出的算法能明显改善网络的性能。文献[4]针对VEC网络中有限的车辆终端计算资源不能处理海量任务数据以及VEC服务器不均衡导致资源利用率和任务卸载效率低的问题，提出了一种资源分配方案，以最大化用户的效用。文献[5]研究了超密集组网(UDN)环境下MEC计算功率的分配和任务卸载的问题，目标是优化系统的能耗。仿真实验结果表明所提出的方案能够降低系统的能耗，提高系统的性能。文献[6]针对VEC系统中由于车辆移动而导致的任务完成时间增加的问题，提出了一种名为MPOHS的任务卸载策略。这种策略基于移动路径可预测，降低由于车辆的移动而造成对任务卸载的影响。实验结果表明所提出的任务卸载策略能够有效降低由于车辆移动造成的对计算卸载的影响，降低任务的平均完成时间。文献[7]研究了在车联网与MEC环境结合的环境下任务处理的时间、所消耗的能量和处理速率的均衡关系，提出了一种基于DQN的任务卸载算法，并通过比较仿真实验、Q学习算法，验证了所提出算法的有效性。文献[9]研究了MEC环境下车载应用计算卸载的问题，通过采用无人机来降低障碍物对计算卸载的影响，提出了一种最小增量任务分配算法来提高资源利用率以及降低系统花费。文献[10]研究了在公有云和边缘云环境下，车载网的通信资源和计算资源有效分配的问题。首先采用K-近邻算法为车载应用的任务处理选择使用的资源，然后使用强化学习来解决通信资源和计算资源的分配问题。仿真实验表明所提出的策略可以有效地降低系统的花费。文献[11]研究了VEC系统中的任务卸载问题，提出了一种基于自适应学习的任务卸载算法来最小化任务卸载的延迟。在仿真实验和真实的场景下的实验表明，所提出的算法与现有的基于置信上限的学习算法相比，在任务处理的平均延迟方面降低了30%。文献[12]研究了车辆通信中安全和可靠性的问题，提出VEC网络中一个基于中消息分发的PoQF一致性算法。所提算法的理论性能通过推导消息验证中失败和延迟的界限、块生成的吞吐量和渐近延迟、安全性和通信复杂性得到验证。文献[13]提出了一个新的VEC框架来模拟在双向道路上行驶的移动车辆的计算卸载过程。基于此框架，采用契约理论的方法为VEC服务提供商设计最优卸载策略，从而在提高车辆效用的同时最大化提供商的收入。为了进一步提高VEC服务器计算资源的利用率，提出了一种高效的VEC服务器选择和计算资源分配算法。数值结果表明，提出的方案大大提高了云计算提供商的收入，同时提高了云计算资源的利用率。文献[14]在自动驾驶领域提出了一种基于深度学习的内容缓存框架。首先通过使用深度学习模型来预测自动驾驶车辆要缓存的内容；其次提出了一个用于检索要缓存的信息娱乐内容通信模型；然后提出了一个缓存模型用于检索的内容，并为缓存的内容提出了计算模型。文献[15]研究了边缘软件定义的车载网络中的路由问题，提出了一种有效的基于在线顺序学习的自适应学习算法路由方案，能够根据车流量的状况选择最优的路由策略。实验结果表明所提出的路由方案能够在不同的情况下根据交通状况作出选择。为了解决VEC系统中资源利用率低的问题，文献[16]提出了一种分布式的计算卸载策略，利用遗传算法和深度强化学习算法来解决最优任务分配的机制，所提出的计算卸载策略能够确保在MEC服务器资源不够的情况下满足车载任务处理延迟的要求。文献[17]研究了车载网络中基于公有云和边缘云的计算资源分配的问题，以达到降低网络延迟的目标。提出了一种结合K近邻算法和强化学习算法的多平台任务卸载和计算资源分配的算法。首先利用K近邻算法进行计算资源的选择，然后利用强化学习算法进行资源的分配。仿真结果验证了算法的有效性。文献[18]研究了基于MEC系统的V2X任务卸载方案。车辆终端产生的数据既可以卸载到MEC系统，也可以卸载到相邻的车辆。设计了一种拍卖机制来最大化车辆的效益。文献[19]研究了基于软件定义网络的VEX系统中的任务卸载策略，目标是优化任务卸载过程中的处理时间和消耗的能量。利用Q-学习的方法来解决所建立的数学问题，但是他们只考虑了网络资源的分配。在本文的研究中，我们同时考虑计算资源和网络通信资源的分配来降低车载应用数据处理的时间。

1 系统模型和问题的描述

1.1 网络模型

假设有一个由N个车辆终端和部署在RSU附近的MEC服务器组成的VEC网络系统模型，如图1所示。本文的系统模型主要参考了文献[1]、文献[10]、文献[11]、文献[17]至文献[19]。每个车辆终端都有一个应用需要处理，对于这些应用，要么用车载终端的计算资源处理，要么通过RSU卸载到MEC服务器来处理。对于车辆终端k的应用，k∈{1,2,…,N}，我们用Dk表示车载应用的数据大小，Ck表示完成车辆终端k应用的一个比特数据所需要的CPU周期数，Fk,l表示车载终端k的CPU频率，也就是车载终端k的计算能力，F表示MEC服务器的CPU频率，也就是MEC服务器的计算能力。

图1 VEC网络系统模型

1.2 车辆终端层计算模型

在车辆终端层计算模型中，车辆终端应用产生的数据将由车辆终端的计算资源完成处理。对于车辆终端k，数据的计算完成时间和消耗的能量可以用如下公式来表示：

(1)

1.3 通信模型

车辆终端应用的数据卸载通过RSU到MEC服务器时，会在上行链路上产生传输延迟和能耗。对于车辆终端k来说，上行链路的数据传输数据率可以用公式(2)表示

(2)

在公式(2)中，Bk表示分配给车辆终端k的带宽，qk表示该车辆终端的传输功率，hk代表该车辆终端与RSU的信道增益，N0表示高斯白噪声功率。

根据公式(2)，车辆终端应用数据在上行链路的传输时间为：

(3)

1.4 边缘云层的计算模型

在边缘云层的计算模型中，当车辆终端应用数据到达后，MEC服务器会提供计算资源来处理应用数据。对于车辆终端k来说，处理应用数据所需要的时间可以用公式(4)表示：

(4)

在公式(4)中，Fk,e表示分配给车辆终端k的计算资源的数量。

根据以上模型可知，如果使用卸载的方式来处理应用的数据，那么所需要的时间是

(5)

车辆终端k应用数据的处理时间可以用公式(6)表示：

(6)

在公式(6)中，ok表示车辆终端k的卸载策略。ok=1，表示车辆终端k使用边缘云层的计算资源来处理应用数据；ok=0，表示车辆终端k使用本身的计算资源来处理应用数据。

2 问题描述和解决方案

2.1 问题描述

当车载终端处理应用产生数据的时候，首先检查自身的计算资源所产生的计算时间，其次检查卸载到边缘云层时所产生的计算时间，然后选择一个比较优的方法处理应用所产生的数据。我们的目标是最小化VEC系统的计算时间，因此，我们的优化目标可以表示为：

问题1:

C3:Fk,e≥0

C4:ok∈{0,1}

C1表示分配给车辆终端的带宽约束条件，C2表示边缘云层MEC服务器分配给车辆终端的计算资源约束条件，C3表示分配给车辆终端的计算资源是非负的，C4表示车辆终端的卸载策略。

问题1是0-1混合整数非线性规划(Mixed Integer Nonlinear Programming，MINP)问题，目标函数是非凸的，是NP难的问题。解决这类问题可以利用一些传统的方法，如分支定界法(Branch and Bound)和交替方向乘子算法(Alternating Direction Method of Multipliers，ADMM)等[20]。但是这些传统算法具有非常大的时间复杂度[21]。下面我们提出一种有效的算法来解决所构造的问题。

2.2 解决方案

根据文献[22]，我们可以把问题1分解为三个子问题：

子问题1：带宽分配的子问题；

子问题2：MEC服务器计算资源分配的子问题；

子问题3：车载应用数据卸载的子问题。

在计算资源和应用卸载是固定值的情况下，问题1变为：

子问题1：

Bk≥0

(7)

(8)

在公式(8)中，μ≥0是拉格朗日乘子。

根据KKT条件[22]，我们有

(9)

(10)

μ≥0

(11)

通过公式(9)，我们可以知道μ>0，并且可以得到

(12)

因此，把公式(12)代入到公式(10)，我们可以得到

(13)

通过公式(13)，我们可以得到

(14)

把公式(14)代入式(9)，我们有

(15)

在带宽和应用卸载是固定值的情况下，问题1变为：

子问题2：

Fk,e≥0

(16)

(17)

在公式(17)中，v≥0是拉格朗日乘子。

根据KKT条件[22]，有

(18)

(19)

v≥0

(20)

通过公式(18)，我们可以知道v>0，并且可以得到

(21)

把公式(21)代入公式(19)，我们可以得到

(22)

通过公式(22)，我们得到

(23)

把公式(23)代入公式(21)，我们可以得到

(24)

在车辆k的应用卸载确定的情况下，把公式(24)和公式(15)代入到公式(6)中，可以得到在此情况下的计算时间。

在子问题1和2解决后，我们得到车辆应用的卸载策略。

对于车载设备k，应用卸载策略可以表示为：

(25)

3 结果与分析

本地处理算法：在该算法中所有的车辆应用数据都利用车辆设备的计算资源来处理。

MEC服务器处理：在该算法中所有的车辆应用数据都利用MEC服务器的计算资源来处理。

表1 参数值

设VEC系统中有5个车辆设备，图2和图3分别表示每个车辆设备的数据卸载决策、在本地端与MEC端的数据处理时间。由图2可以看出，车辆设备1和2选择使用自己的计算资源来处理应用数据，而车辆设备3，4和5选择使用MEC服务器的计算资源来处理应用数据。这是由于车辆设备3，4和5需要处理的数据比较大，使用本地资源处理需要的时间比MEC端要长，所以会选择在MEC端处理，这在图3中得到了验证。

图2 车辆设备数据卸载策略

图3 本地端和MEC端的数据处理时间

为了验证所提算法的有效性，我们与对比算法在数据处理时间方面进行了比较，结果如图4所示。

图4 所提算法的有效性

通过图4可知，所提算法在数据处理时间方面有了明显的改进，特别是当车辆设备增加的时候。从图4可以看出，当车辆设备的数量是5时，与本地处理算法相比，所提算法最高能降低11.7%的处理时间；与MEC服务器处理算法相比，所提算法最高能降低7.79%的处理时间。

4 结论

研究了VEC系统中车辆设备数据处理和资源分配机制，提出了一种有效的车辆应用大数据处理的资源分配策略。实验结果表明，所提出的方法能有效地降低车辆应用大数据处理的时间。由于非正交多址(Non-Orthogonal Multiple Access,NOMA)在应用数据卸载方面有降低延迟的优点，在未来研究中，我们将采用与VEC系统结合的方式来降低系统的计算花费。由于区块链和联合学习能保护数据传输的安全，所以把区块链和联合学习应用在VEC系统中也是我们未来的研究课题。