一种云边协同的车载云计算资源调度算法

黄晴晴

(广东东软学院 计算机学院，广东佛山528225)

摘要：随着自主驾驶的发展，下载大文件的需求经历了爆炸式的增长。为解决自动驾驶本地计算能力有限导致大规模文件请求的高延迟和低效的资源调度。提出了一种基于优先级资源调度的最大回报车载云计算资源调度算法。该算法利用改进的动态贪心算法建立了设备对设备场景下的系统回报模型，考虑了车辆请求的优先级、请求数据量和用户允许时间等因素，以实现回报的最大化。仿真结果表明，该算法可以通过改变不同的参数设置，得到车辆协同的最优资源分配，验证了算法的可行性。

关键词：车载云计算；最大回报；资源调度；车载协同模型

随着经济的快速发展，人们的生活水平不断提高。随着自动驾驶技术的发展，对大型文件的信息传输提出了更高的要求。另外，资源调度的合理性对系统的整体性能有很大的影响。由于存储和计算能力的限制，仅仅依靠车辆侧的边缘计算来进行大规模的文件传输是不够的。在这种情况下，也应该考虑云平台来提高自动驾驶时代大规模文件传输的效率和有效性。本文考虑了车辆请求的优先级、请求数据量和用户允许时间，构建一种动态分配云资源的算法，实现回报的最大化。提出了一种基于D2D架构的车辆信息传输计算和存储资源动态分配方法。使用信道衰落模型和车辆协同下载模型来最大化系统的回报。

1系统模型

本节将系统模型分为以下几部分进行描述。首先介绍了长期演进（Long Term Evolution，LTE）算法。然后分别描述了系统整体优化模型、信道衰落模型、优先级模型和车辆协同模型。

我们假设车辆通信场景发生在四个循环单元内，包括前向行驶和后向行驶车辆，如图1所示。车辆向循环单元发送数据请求(假设它只发送到最近的单元)。然后云平台计算上传数据的最大回报，并将结果返回到循环单元，获得最大回报的请求被优先处理。此外，车辆到基础设施(Vehicle to Infrastructure，V2I)通信可以在循环单元的传输范围内进行，车到车（Vehicular to Vehicular ,V2V）通信可以在传输范围之外进行。

图1  系统模型

1.1 总体优化目标

将计算资源、带宽资源和节省的时间集成到回报函数中，由增益函数与开销函数之差可得：

         (1)

其中，为VCC平台的状态集，包括计算速率、占用带宽、计算服务价格、每台虚拟机的带宽价格、无云时的能耗、时间消耗单价、云服务请求数。VCC平台的操作集为，其中0表示云平台不为请求分配虚拟机，表示云平台可以分配的虚拟机的最大数量。影响云平台资源调度的事件集为，这四个事件分别表示车辆的到达和离开，请求的到达和离开。

我们使用表示时间和功耗的增加。当事件在状态下发生时，即操作。可以表示如下：

          (2)

其中，表示由云平台处理的单个请求的增益。由于本文考虑的是系统，所以应该综合所有请求的优点。由于云平台的优势在于强大的资源和数据处理能力，的变化主要是由时间消耗和能量消耗引起的。因此，为:

(3)

其中，和分别表示车辆无法获取云的虚拟机资源并从普通互联网下载时请求的能耗和时间消耗。和分别是请求从道路集传输到云端的平均时间和传输功率。当时，车辆实际上不享受云服务，增益为0；，车辆享受云服务。因此，它避免了普通互联网下载所需的大量能耗和时间消耗。但是上传过程要添加和的消耗。这部分体现在开销函数中。

系统开销函数包括信道衰落引起的能量消耗、时间消耗和能量消耗，可表示为：

(4)

其中，指单位时间内发生的费用。是通过云服务请求的时间。是信道衰落引起的开销。

由于是由云平台所分配的虚拟机数量决定的，则有:

   (5)

其中，表示为虚拟机安排的请求数，为本决策占用的虚拟机总数。

另外，应在用户允许的时间内，并服从参数的指数分布。当时，。直接对云平台服务时间建模并不容易。但考虑到它的倒数，是云平台服务率。由于车辆的到达和离开对V2V通信有影响，因此决策只与请求的到达和离开相关，因此只将其分为式(6)所示的三类情况。

(6)

其中，是云平台分配给所有请求的虚拟机的总计算能力。当新请求到达时，应该保留一定数量的虚拟机资源。为了保证系统的平稳运行，这里取最大值是为了满足新请求的计算要求。当请求离开时，虚拟机资源将被释放。为保证云平台正常工作，取中间值，避免乐观估计。

1.2  信道衰落模型

VANET不同于其他静态网络，它具有较高的动态特性。而车辆的快速移动导致无线信道发生剧烈变化，导致信道显著衰落，通信能力减弱。时间消耗和能量消耗受到影响。本文用Nakagami分布来描述信道衰落模型。概率密度分布函数如下：

  (7)

其中，表示函数。

为衰落过程中的平均接收功率（），为描述衰落严重程度的与环境和距离相关的参数（）。根据文献[9]的试验结果，我们取，；，。可由以下公式计算：

         (8)

其中，和分别为衰落过程中的路径损耗参数和路径衰落指数，

且。

1.3  请求优先级模型

由于该机制主要针对VCC系统，因此多个服务请求必然涉及处理甚至丢弃问题的顺序。其实，这个机制也可以根据优先请求来服务。该机制的优先级考虑了文件需求、数据量和用户允许时间。其方程可表示为:

       (9)

其中，和分别为用户容差时间和数据量的权重。不同类型文件的资源需求是不同的，计算密集型文件需要虚拟机内存容量和处理速度，通信密集型文件主要关注网络带宽资源的需求。因此，和分别用于调整计算和通信资源的重视程度。从式(9)可以看出，在相同的条件下，用户容错时间越短，请求的数据量越小，文件需求程度越高，处理优先级越高。在、和三个优先考虑因素中，是最重要的。这是因为当云端接收到请求时，它在做调度决策之前检查是否存在相同的请求。如果存在，则选择最高优先级的服务，并且可以从具有V2V的服务车辆中获得其他相同的请求。

1.4  车辆协同下载模式

如果车辆通过V2V向车辆获取文件，则车辆和分别为目标车辆和辅助车辆。根据车辆交通场景，V2V通信可以分为三种情况。即目标车辆与辅助车辆对向行驶、反向行驶和同向行驶。假设V2V的传输带宽为100kB/s，车辆通信设备的传输半径为[50m, 500m]。则车辆协同下载的通信持续时间可表示为：

(10)

其中，为单车通信半径，和分别为目标车与辅助车的矢量行驶速度。为目标文件数据量，为车辆通信速度，为车辆保持相对运动的时间。式(10)中，第1行表示车辆处于相对运动时的通信持续时间，包括对向行驶和反向驾驶；第2行表示两辆车在同向行驶，但不相对静止时的通信持续时间；第3行表示两辆车相对静止时的通信持续时间。

2动态的贪婪算法

针对贪心算法的简单性和较低的时间复杂度，在选择子问题的最优解时，根据请求优先级进行改进，使资源调度更加全面、合理。

为了合理优化云平台剩余计算资源，我们设计了一个动态贪心算法，如算法1所示。该算法将云平台资源优化问题简化为若干子选择问题。每个子选择使当前收益最大化，从而得到局部最优解。当云平台有新的资源释放时，再次进行选择，得到新的子问题的局部最优解。

算法1基于优先级的动态贪婪算法

Input: Output: sorted Begin Initialize parameters; for to Calculate corresponding ,; endfor for to for to if then Exchange and; end if endfor endfor for to if then if then Exchange and; endif endif endfor for to if then if then Exchange and; else break endif else break endif endfor Allocate VMs in the sequence of end

具体来说，该算法首先计算云平台接收到的每个请求的系统回报。接下来，根据回报级别进行排序。如果请求具有相同的回报，则根据指定的优先级从高到低，从而形成一个整体有序的任务队列。从任务队列的第一个位置开始，每次尝试分配足够的虚拟机来满足带宽和计算方面的需求数量。如果优化措施比其他请求更好，分配就完成了。否则将选择任务队列中的下一个请求。

云平台在等待期间收集服务请求，并在决策期间做出决策。VCC在资源调度时，云平台总是提供高优先级、高回报的服务。收集服务请求后，将在下一个决策期间再次执行该过程。由于这两个时间间隔都很小，因此形成了一个动态的云平台资源调度决策过程。我们使用来表示云平台在等待决策时收集的请求集。

3仿真分析

本文提出了基于动态资源调度的云平台虚拟机资源优先级。由于系统回报是模型中的目标函数，因此主要分析了相关参数的仿真结果。我们使用MATLAB来分析云平台的资源调度机制。我们设置的场景是云平台还没有达到饱和状态，始终保持计算资源和带宽资源。车辆的到达和离开以及请求遵循泊松分布。其他仿真参数设置如表1所示。

表1仿真参数设置

仿真参数	值
每台虚拟机的计算能力	[1000,3000] MIPs
每台虚拟机占用带宽	[0,40] Mbps
云平台最大虚拟机数量	[1,80]
虚拟机计算价格	1.1元/小时
带宽价格	0.8元/小时

图2展示了每个虚拟机的系统回报的相对计算率。、和分别表示请求到达、离开和保持不变。从图上可以看出，系统回报随着每个虚拟机的计算速度的增加而增加。这是因为计算能力的提高使得处理请求的总数增加，时间成本降低，从而提高了系统的回报。另外，还可以看出，当新请求到达时，系统奖励最高。排名第二，是最后一名。这是因为当平台请求的数量不饱和时，回报与接收请求的数量呈正相关。

图2虚拟机计算率对系统回报的影响

图3展示了每个虚拟机的带宽与系统回报的关系。从图上可以看出，每个虚拟机需要占用的带宽越大，系统的回报就越小。因此，在相同的条件下，虚拟机占用的带宽应尽可能小，以满足需求。

图4展示了最大虚拟机数量对系统回报的影响。从图上可以看出，当收到的请求数量不变时，奖励不变。当一个新的请求到达或离开时，随着云平台上最大可分布虚拟机数量的增加，回报的幅度减小，然后变得稳定。

图3  虚拟机带宽对系统回报的影响

图4  最大虚拟机数量对系统回报的影响

4结论

提出了一种从云平台下载大型文件的VCC资源调度算法。该算法同时考虑了能量消耗和时间消耗，以实现回报的最大化。在此基础上，通过仿真得到了系统整体回报的影响因素。通过对该算法的仿真实现，验证了该算法的可行性，并通过改变不同的参数设置，分析了各参数对算法性能的影响。为云平台资源调度的参数设置和调度部署提供参考。

参考文献：

[1]苏命峰,王国军,李仁发.基于利益相关视角的多维QoS云资源调度方法[J].通信学报, 2019(6):102-115.

[2]Boukerche A, Grande R E D. Vehicular Cloud Computing: Architectures, Applications, and Mobility[J]. Computer Networks, 2018, 135.

[3]耿新力.城区不确定环境下无人驾驶车辆行为决策方法研究[D]. 中国科学技术大学, 2017.

[4]张雪,高德云.一种优化的基于软件定义车联网的路由方法[J].计算机技术与发展, 2018, 28(1):37-42.

[5]王渤茹,范菁,单泽,等.5G移动通信组网关键技术研究综述[J].通信技术, 2019(5):1031-1040.

[6]唐登洪,周杰.基于密集街道V2V通信的几何信道模型[J].计算机工程与设计, 2017, 38(11):77-81.

[7]张永棠.高速公路场景下车载网路侧单元部署研究[J]. 应用科技, 45(06):63-66.