面向复杂车载雾计算系统环境的混合动态任务调度方法

摘要

本发明公开一种面向复杂车载雾计算系统环境的混合动态任务调度方法，步骤为：(1)建立车载雾计算调度模型，初始化车载雾计算场景中的任务集与雾服务器集；(2)通过系统环境变化测量函数Var(r)观察车载雾计算环境中的任务流变化与雾系统服务能力变化，进而获得系统变异系数v1,v2；(3)根据变异系数反映的离散差异情况，决策支持函数DSF(v1,v2)产生决策，并调用合适的调度算法将车载任务分配给雾服务器。本发明通过观察车载雾计算系统环境的变化情况，动态的选择调度算法，使得车载任务能够合理高效的分配给各个雾服务器进行处理，提高了车载任务的处理效率，同时改善了雾服务器服务能力的稳定性。

说明书

技术领域

本发明属于车载通信技术，具体涉及一种面向复杂车载雾计算系统环境的混合动态任务调度方法。

背景技术

车联网，是一种以车载为主体参与网联的新兴领域，是物联网在交通领域的典型应用。通过互联单个车载的智能性，分享道路交通信息，提高车-X(X：车、路、行人及互联网等)之间的无线通信与信息交互，促进了智能交通体系的发展。而随着车联网技术与产业的发展，智能汽车数量的增加及车载应用的多样化，车载信息量与信息传播速度都呈几何级数增长，如何处理这些庞大的数据及数据的处理效率成了车联网中必须解决的问题。

传统的车联网从网络上看，是一个“端管云”三层系统，端指的是负责收集车载信息、感知行车状态与环境的智能传感器；管指的是解决车-X的互联互通，实现网络间的通信与漫游；云指的是一个云架构的信息平台，提供虚拟化、安全认证、实时交互、海量存储等云计算功能。虽然，云技术在一定程度上解决了车联网中数据存储与处理效率问题，但是，当面对大量分布广泛的车载终端设备以及所采集的海量车载数据时，车联网中的云系统不可避免地遇到一些难题。

首先，海量的车载数据涌入核心网络云中，将造成严重的网络拥塞；其次，车载设备与云数据中心存在较远的距离，这使得数据传输存在较高的延迟；最后，从车载设备到云的远距离通信存在一定的风险，并且云中备份的成本也高。

另一方面，随着车辆工业技术的发展，使得车载具有一定的计算能力与存储能力，但单个车载的能力并不能很好的处理所有的车载数据与任务，不过将全部车载数据与任务传输到云端处理也会造成车载物理资源的空闲，导致云服务系统负载过大。

因此，在车联网中，将大量的数据处理过程传输到云中心进行并不一定是有效的方法，需要应用适合车联网环境的调度方案，使得车载数据处理能够及时高效的完成的同时提高车载资源的利用率。

在现有的方案中，有不少基于安全性的调度算法、关注于故障恢复的任务调度、考虑能量与效率的调度、以及数据并行处理的调度架构。但是，这些方案考虑的场景是一种车载任务队列与服务器遵循以稳定的平均值随机分布；而现实的车载环境中，车载的任务队列与服务能力存在多变的情况，通常表现为一种具有不同值的随机过程。所以，现有的调度方案并没有考虑到车载环境多样化，只是单一的将车载环境假设为一种固定的状态。因此，考虑到车载环境的多样化，本发明提供了一种面向复杂车载雾计算系统环境的混合动态任务调度方法。

发明内容

发明目的：本发明的目的在于解决现有技术中存在的不足，提供一种面向复杂车载雾计算系统环境的混合动态任务调度方法。

技术方案：本发明、一种面向复杂车载雾计算系统环境的混合动态任务调度方法，包含两种动态调度算法，适用于不同的车载雾计算系统中的车载任务调度，包含以下步骤：

(1)建立车载雾计算调度模型(即是指先利用车载中空闲的物理资源，构造出一种雾计算环境；然后在该环境中应用调度算法，从而提高车载中数据与任务的处理效率)，初始化车载雾计算场景中的任务集与雾服务器集；

(2)通过系统环境变化测量函数Var(r)观察车载雾计算环境中的任务流变化与雾系统服务能力变化，进而获得系统变异系数v₁和v₂；其中变异系数是原始数据标准差与原始数据平均数的比值，用于比较两组数据的离散程度，变异系数反映了数据离散程度的绝对值；其数据大小不仅受变量值离散程度的影响，而且还受变量值平均水平大小的影响；另外原始数据是指在车载环境中车-车、车-路和车-网之间通信产生的相应任务流数据，以及车载雾计算环境中各服务器能力的相关数据；在本车载雾计算调度模型中，变异系数包括车载任务队列工作流到达变化v₁与雾服务器能力变化v₂；

(3)根据变异系数的离散情况，决策支持函数DSF(v₁,v₂)产生决策，并调用相应的调度算法将车载任务分配给雾服务器；且所述动态调度算法根据实际情况选择下面两种中的相应一种方法：

a)基于队列的动态调度算法QDS，其调度过程与服务器中等待队列的长度有关，在一定时间范围内，车载任务将分配给等待队列长度最短的服务器进行处理与完成；

b)基于时间的动态调度算法TDS，其调度过程与队列中的任务完成时间有关，在指定的时间点，车载任务将分配给任务完成用时少的服务器进行处理与完成。

进一步的，所述的基于队列的动态调度算法QDS用p(Q)表示，且p(Q)由一个决策函数DF_QDS(t)构成，根据QDS算法的原理，DF_QDS(t)函数表示为：

其中，C为系统环境的一个常系数，t为传输时间点，Q(t)为该时间点系统产生的等待队列长度，因为Q(t)的值随时间点t的变化而改变，因此该队列长度为瞬时队列长度，记为T[Q(t)]，T[Q(t)]为t时刻内所传输的队列长度。

进一步的，所述的基于时间的动态调度算法TDS用p(T)表示，且p(T)由一个决策函数DF_TDS(t)构成，根据TDS算法的原理，DF_TDS(t)函数表示为：

其中，K是系统用户数量；R(t)为t时刻系统系统的响应时间，由于该响应时间为t时刻的瞬时值，故标记为T[R(t)]；R_S(K)为平均响应时间且为固定值，由于该事件是通过M/M/1//K队列模型近似计算而得，故为近似平均响应时间，记为E[R_S(K)]；即E[R_S(K)]为平均响应时间且为固定值，T[R(t)]为t时刻的传输响应时间。

进一步的，所述不同的车载雾计算系统包括：存在多种任务需求的车载雾计算系统及系统服务能力不稳定等情况。

进一步的，所述步骤(1)中初始化的具体方法为：

(1.1)任务集J中的元素为车载雾计算系统中的任务j_k，在所构建的车载雾计算调度模型中，每个车载任务为一个五元组，即

j_k＝<k,v,λ,l,p>,j_k∈J(k＝1,2,...,n)

其中，k为车载任务的ID，v为源车辆的索引，λ为车载任务的产生率，l为车载任务的长度，p为车载任务所选用的调度算法；

(1.2)雾服务器集S，S中的元素为车载雾计算系统中的雾服务器s_i,在所构建的车载雾计算调度模型中，每个雾服务器为一个四元组，即

s_i＝<i,v,μ,t>,s_i∈S(i＝1,2,...,m)

其中，i为雾服务器的ID，v为提供物理资源的车辆索引，μ为给定雾服务器的服务能力，t为车辆移动过程中雾服务器剩余的服务时间。

进一步的，所述步骤(2)的过程具体如下：

(2.1)基于车载的任务产生率λ与雾服务器服务能力μ计算标准差σ：

(2.2)计算变异系数CV：

Var(λ)＝CV_λ；Var(μ)＝CV_μ；

其中，CV_λ为任务流到达变化情况，CV_μ为雾服务器服务能力变化情况；

(2.3)获得系统变异系数v₁,v₂：

v₁＝CV_λ；v₂＝CV_μ；

进一步的，所述步骤(3)中的决策支持函数DSF(v₁,v₂)的过程具体如下：

其中，v_out为调度算法选择，若值为1，说明工作任务流到达的离散程度较大，则选择基于队列的动态调度算法QDS，若值为0，说明雾服务器服务能力的离散程度较大，则选择基于时间的动态调度算法TDS。

有益效果：本发明利用车载物理资源构造一种车载雾计算环境，提高了车载资源的利用，同时改善了车联网中负载均衡问题；而且基于所构建的车载雾计算调度模型，本发明提出了一种动态的混合调度方法，针对车载雾计算环境中车载任务队列的变化情况与雾服务器服务能力的稳定情况，调用不同的算法进行车载任务分配，从而提高了车载任务的处理效率。

附图说明

图1为本发明中车载雾计算调度模型图；

图2为本发明中基于队列的动态调度算法QDS具体过程示意图；

图3为本发明中基于队列的动态调度算法QDS具体过程示意图；

图4为本发明中混合调度算法与对比方法的实验结果图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述实施例。

如图1所示，本发明的一种面向复杂车载雾计算系统环境的混合动态任务调度方法，首先建立了一个车载雾计算调度模型，然后在所构建的模型基础上，提供了一种适用于多样化车载雾计算环境中的混合动态调度方法。具体的包括：(1)建立车载雾计算调度模型，初始化车载雾计算场景中的任务集与雾服务器集；(2)通过系统环境变化测量函数Var(r)观察车载雾计算环境中的任务流变化与雾系统服务能力变化，进而获得系统变异系数v₁,v₂；(3)根据变异系数的离散情况，决策支持函数DSF(v₁,v₂)产生决策，并调用合适的调度算法将车载任务分配给雾服务器。

其中，如图2与图3所示，所述方法中的两种动态调度算法具体过程描述如下：

a)基于队列的动态调度算法QDS，如图2所示，其调度过程与服务器中等待队列的长度有关，在一定时间范围内，车载任务将分配给等待队列长度最短的服务器进行处理与完成；

b)基于时间的动态调度算法TDS，如图3所示，其调度过程与队列中的任务完成时间有关，在指定的时间点，即使处理队列中任务个数多，车载任务也将新任务分配给任务完成用时少的服务器进行处理与完成。

车载雾计算环境中，所述混合调度方法中的基于队列的动态调度算法QDS用p(Q)表示，且p(Q)由一个决策函数DF_QDS(t)构成，根据QDS算法的原理，DF_QDS(t)函数具体描述如下：

其中，C为系统环境的一个常系数，t为传输时间点，T[Q(t)]为t时刻内所传输的队列长度。

车载雾计算环境中，所述混合调度方法中的基于时间的动态调度算法TDS用p(T)表示，且p(T)由一个决策函数DF_TDS(t)构成，根据TDS算法的原理，DF_TDS(t)函数具体描述如下：

其中，E[R_S(K)]为平均响应时间且为固定值，T[R(t)]为t时刻的传输响应时间。

在车载雾计算环境中，所述的不同的车载雾计算系统包括：存在多种任务需求的车载雾计算系统及系统服务能力不稳定等情况。

建立车载雾计算调度模型，初始化系统中的任务集与雾服务器集具体的实施步骤如图1所示，在车载网络环境中，由于丰富的应用及车辆的联网合作，源车辆存在大量的数据任务需要处理，所以将源车辆中的任务定义为一个任务集J；另外，利用车载中空闲的物理资源，将道路上邻近的车辆集群构建为雾服务器，不同的雾服务器构成雾服务器集S，如图1中的雾服务器S₁与雾服务器S₂构成雾服务器集S，其具体实施步骤如下：

a)任务集J，J中的元素为车载雾计算系统中的任务j_k,在所构建的车载雾计算调度模型中，每个车载任务为一个五元组，具体表示如下：

j_k＝<k,v,λ,l,p>,j_k∈J(k＝1,2,...,n)

其中，k为车载任务的ID，v为源车辆的索引，λ为车载任务的产生率，l为车载任务的长度，p为车载任务所选用的调度算法；

b)雾服务器集S，S中的元素为车载雾计算系统中的雾服务器s_i,在所构建的车载雾计算调度模型中，每个雾服务器为一个四元组，具体表示如下：

s_i＝<i,v,μ,t>,s_i∈S(i＝1,2,...,m)

其中，i为雾服务器的ID，即当i为1时表示S₁雾服务器，i为2时表示S₂雾服务器；v为提供物理资源的车辆索引，μ为给定雾服务器的服务能力，t为车辆移动过程中雾服务器剩余的服务时间。

所述步骤(2)中的变异系数是原始数据标准差与原始数据平均数的比值，用于比较两组数据的离散程度，变异系数反映了数据离散程度的绝对值；其数据大小不仅受变量值离散程度的影响，而且还受变量值平均水平大小的影响。

系统环境变化测量，其具体步骤如下：

a)基于车载的任务产生率λ与雾服务器服务能力μ计算标准差σ：

b)计算变异系数CV：

Var(λ)＝CV_λ；Var(μ)＝CV_μ；

其中，CV_λ为任务流到达变化情况，CV_μ为雾服务器服务能力变化情况；

c)获得系统变异系数v₁,v₂：

v₁＝CVλ；v₂＝CV_μ；

决策支持函数DSF(v₁,v₂)的具体步骤如下：

其中，v_out为调度算法选择，若值为1，说明工作任务流到达的离散程度较大，则选择基于队列的动态调度算法QDS，若值为0，说明雾服务器服务能力的离散程度较大，则选择基于时间的动态调度算法TDS。

实施实例：

本实施的面向复杂车载雾计算系统环境的混合动态任务调度方法，图1显示了建立车载雾计算调度模型并初始化车载雾计算场景中的任务集与雾服务器集后的场景；依据图1所构建的场景，将所定义的基于队列的动态调度算法QDS与基于时间的动态调度算法TDS部署在调度模型中，使得在多样化的车载雾计算环境中的车载任务队列，可以动态的应用不同的调度算法，从而有效的调度给不同雾服务器进行处理与完成。

此外，在具体的实验中，考虑多样化车载雾计算环境中的不同的任务调度算法的效率。实验中，本发明利用PEPA(Performance Evaluation Process Algebra)性能评估进程代数进行建模。PEPA是一种高级模型规范语言，它与经典的进程代数不一样，在PEPA中，每个活动都遵循指数分布的一个随机时间。另外，在本实验中选择两种对比方案与本发明所提的方案进行比较，从而证明了本发明使用混合调度方法的高效性。具体的对比方案为：

对比1：在多样化的车载雾计算环境中仅使用基于队列的动态调度算法QDS；

对比2：在多样化的车载雾计算环境中仅使用基于时间的动态调度算法TDS；

如图4所示，实验结果表明了本发明所提的混合调度方法较其他两种方法更具高效性与稳定性，混合的调度方法能产生更好的系统性能。

通过上述实施例可以看出，本发明通过观察车载雾计算系统环境的变化情况，动态的选择调度算法，使得车载任务能够合理高效的分配给各个雾服务器进行处理，提高了车载任务的处理效率，同时改善了雾服务器服务能力的稳定性。