一种面向边缘人工智能应用的QoE感知的服务增强方法

摘要

本发明公开了一种面向边缘人工智能应用的QoE感知的服务增强方法，包括以下步骤：A、物联网终端将运算任务发送至调度器，调度器根据运算任务的要求判定将运算请求发送至本地服务器或上传至数据中心；B、建立感知质量的服务增强模型的目标和约束条件；C、建立两阶段调度策略，降低计算复杂度。本发明能够解决现有技术的不足，提升用户的服务体验和任务的完成率。

说明书

技术领域

本发明属于物联网技术领域，具体是一种面向边缘人工智能应用的QoE感知的服务增强方法。

背景技术

由于人工智能（AI）算法的复杂性，在资源有限的物联网设备上执行人工智能任务已被证明是困难的。边缘计算为执行AI任务提供了一种有效的计算范式，大量的AI任务可以被卸载到边缘服务器来更高效地执行。然而，现有的工作大多集中于通过提高服务质量(QoS)来实现有效的计算卸载，如降低平均服务器端延迟（例如中国发明专利申请201910307861 .7）。但是，由于延迟等因素对用户体验质量(QoE)的异构影响，这些方式往往并不足够高效。

发明内容

本发明要解决的技术问题是提供一种面向边缘人工智能应用的QoE感知的服务增强方法，能够解决现有技术的不足，提升用户的服务体验和任务的完成率。

本发明的内容包括以下步骤，

A、物联网终端将运算任务发送至调度器，调度器根据运算任务的要求判定将运算请求发送至本地服务器或上传至数据中心；

B、建立感知质量的服务增强模型的目标和约束条件，服务增强模型用于对现有的边缘计算卸载方法进行QoE层面的调度优化，以进一步提高用户的服务体验；

C、建立两阶段调度策略，降低计算复杂度。

作为优选，步骤B中，建立感知质量的服务增强模型的目标和约束条件包括以下步骤，

在任务处理过程中，在线到达任务T_k,i>k,i,pre_t_k,i,req_q_k,i)首先在调度器中被拆分，每个虚拟机VM_k,j被分配一部分的任务数据，其权值为w_k,i,j，该任务是由一组多个虚拟机并行完成的；在任务划分的过程中，需要满足结果精度的约束，即，每个虚拟机持有一个自身的任务队列；对于任务T_k,i，虚拟机被分配x_k,i*w_k,i,j个CPU周期的任务量，而这些子任务的外部延迟都相同，为pre_t_k,i；设当新任务到达时，每个虚拟机队列中已经有几个任务，仍然在队列中等待或已经被处理，在队列Q_k,j中任务T_k,i的子任务为state_k,i,j，

，

根据上述定义，队列Q_k,j中的T_k,i的子任务可以被重新定义为一个元组

，

其中的每个元素分别代表完成子任务所需的CPU周期、子任务状态和外部延迟，将定义为处理时间的向量，其中，定义，作为k类型任务的外部延迟，，，令表示子任务是否在队列的第l位置，

，

第h个类型为k(T_k,h)的任务到达时，用以下h阶矩阵表示类型为k的所有在线到达任务的位置信息，

，

且，h阶矩阵的每个行向量为，h阶矩阵的每个列向量为，计算重新调度的中的子任务的服务器端延迟，

，

定义重新调度的中的子任务的外部延迟为，

，

重新调度的中的子任务的整个服务延迟为，定义的位置为，其中，，任务的服务延迟表示为，

，

约束条件为，

目标函数最大化所有在线到达任务的QoE，确保任务分配策略在结果准确性方面满足需求，声明任务应该由k类型的所有虚拟机完全完成，表示每个分配的子任务只包含每个虚拟机的一个特定位置信息，声明在某个队列的任何位置上都只有一个子任务，和定义变量的域。

作为优选，步骤C中，两阶段调度策略包括，

第一阶段，负载均衡的任务划分:对虚拟机的在线到达任务进行合理的划分，以达到负载均衡；

第二阶段，感知QoE的动态队列调度:根据所涉及任务的QoE敏感性和处理延迟，调整每个虚拟机的任务队列，使整体QoE最大。

作为优选，负载均衡的任务划分具体包括，

每个虚拟机分配一个专用的任务队列，一个任务由一组多个虚拟机并行完成；对于新到达的任务，调度器确定任务的任务分区方案，以最小化最长的任务服务器端延迟，从而实现所涉及的所有虚拟机之间的负载平衡；

总共有n个虚拟机，即，其中，和分别表示每个虚拟机的计算能力和虚拟机所采用AI算法的准确性；每个虚拟机在动态缓冲池中都有一个任务队列，用于k类型任务的所有虚拟机的队列可以表示为；权向量表示任务的任务分区方案，其中；具体来说，对于任务，有CPU周期分配给；

，

其中表示，表示任务的精度要求；根据任务分区方案，完成队列中任务所需的CPU周期为；任务到达后，队列的任务完成时间计算如下，

为了平衡所有相关虚拟机的工作负载，同时满足对结果准确性的要求，应该尽量减少所有队列的最大完成时间；负载均衡任务划分的目标和约束可以总结为，

最小化所有相关虚拟机的最大完成时间，表示任务分区方案应该满足任务的精度要求，声明任务应该完全由相关的虚拟机分配，定义变量的域。

作为优选，感知QoE的动态队列调度具体包括，

使用任务服务延迟的导数作为QoE灵敏度的值，对于在队列的子任务，QoE灵敏度可以表示为，

，

其中服务延迟包含外部延迟、到目前为止的队列等待时间和估计的处理时间；解决方案是使用-最大导数到队列的位置；重新引入排序方法，

，

排在前面的子任务具有较高的QoE敏感性和较短的处理时间，根据CPU周期最大的子任务的排序指标来调整每个队列的排序顺序。

本发明的有益效果是，本发明从QoE的角度来设计人工智能任务的边缘调度。针对人工智能应用的物联网任务，提出了一种基于多算法的基于质量感知的服务增强方法。该模型根据任务的QoE敏感性，优化任务分配和调度策略，使得QoE值较高。此外，此模型并发执行相同类型的任务，因此满足用户对准确性和延迟的异构性要求。针对这类NP-hard问题，提出了一种高效的两阶段调度过程。本发明可以以高QoE值、高任务完成率和低服务器端延迟来完成任务处理服务。

附图说明

图1为本发明的系统流程图。

图2为QoE和服务延迟的关系图。

图3为仿真过程中600秒的模拟时间内的QoE的对比图。

图4为仿真过程中600秒的模拟时间内的服务器端延迟对比图。

图5为仿真过程中不同任务到达率下的平均QoE的对比图。

图6为仿真过程中不同任务到达率下的任务完成率的对比图。

图7为仿真过程中600秒仿真时间内的QoE增益。

图8为MSR方法在不同QoE阈值下的任务完成率与任务到达率的关系图。

图9为在不同任务划分策略和任务到达率下的平均QoE对比图。

图10为在不同任务划分策略和任务到达率下的任务完成率对比图。

图11为在不同任务划分策略和任务到达率下的均服务器端延迟对比图。

具体实施方式

参照图1，本发明包括以下步骤，

A、物联网终端将运算任务发送至调度器，调度器根据运算任务的要求判定将运算请求发送至本地服务器或上传至数据中心；

B、建立感知质量的服务增强模型的目标和约束条件；

C、建立两阶段调度策略，降低计算复杂度。

步骤B中，建立感知质量的服务增强模型的目标和约束条件包括以下步骤，

在任务处理过程中，在线到达任务T_k,i>k,i,pre_t_k,i,req_q_k,i)首先在调度器中被拆分，每个虚拟机VM_k,j被分配一部分的任务数据，其权值为w_k,i,j，该任务是由一组多个虚拟机并行完成的；在任务划分的过程中，需要满足结果精度的约束，即，每个虚拟机持有一个自身的任务队列；对于任务T_k,i，虚拟机被分配x_k,i*w_k,i,j个CPU周期的任务量，而这些子任务的外部延迟都相同，为pre_t_k,i；设当新任务到达时，每个虚拟机队列中已经有几个任务，仍然在队列中等待或已经被处理，在队列Q_k,j中任务T_k,i的子任务为state_k,i,j，

，

根据上述定义，队列Q_k,j中的T_k,i的子任务可以被重新定义为一个元组

，

其中的每个元素分别代表完成子任务所需的CPU周期、子任务状态和外部延迟，将定义为处理时间的向量，其中，定义，作为k类型任务的外部延迟，，，令表示子任务是否在队列的第l位置，

，

第h个类型为k(T_k,h)的任务到达时，用以下h阶矩阵表示类型为k的所有在线到达任务的位置信息，

，

且，h阶矩阵的每个行向量为，h阶矩阵的每个列向量为，计算重新调度的中的子任务的服务器端延迟，

，

定义重新调度的中的子任务的外部延迟为，

，

重新调度的中的子任务的整个服务延迟为，定义的位置为，其中，，任务的服务延迟表示为，

，

约束条件为，

目标函数最大化所有在线到达任务的QoE，确保任务分配策略在结果准确性方面满足需求，声明任务应该由k类型的所有虚拟机完全完成，表示每个分配的子任务只包含每个虚拟机的一个特定位置信息，声明在某个队列的任何位置上都只有一个子任务，和定义变量的域。

步骤C中，两阶段调度策略包括，

第一阶段，负载均衡的任务划分:对虚拟机的在线到达任务进行合理的划分，以达到负载均衡；

第二阶段，感知QoE的动态队列调度:根据所涉及任务的QoE敏感性和处理延迟，调整每个虚拟机的任务队列，使整体QoE最大。

负载均衡的任务划分具体包括，

每个虚拟机分配一个专用的任务队列，一个任务由一组多个虚拟机并行完成；对于新到达的任务，调度器确定任务的任务分区方案，以最小化最长的任务服务器端延迟，从而实现所涉及的所有虚拟机之间的负载平衡；

总共有n个虚拟机，即，其中，和分别表示每个虚拟机的计算能力和虚拟机所采用AI算法的准确性；每个虚拟机在动态缓冲池中都有一个任务队列，用于k类型任务的所有虚拟机的队列可以表示为；权向量表示任务的任务分区方案，其中；具体来说，对于任务，有CPU周期分配给；

，

其中表示，表示任务的精度要求；根据任务分区方案，完成队列中任务所需的CPU周期为；任务到达后，队列的任务完成时间计算如下，

为了平衡所有相关虚拟机的工作负载，同时满足对结果准确性的要求，应该尽量减少所有队列的最大完成时间；负载均衡任务划分的目标和约束可以总结为，

最小化所有相关虚拟机的最大完成时间，表示任务分区方案应该满足任务的精度要求，声明任务应该完全由相关的虚拟机分配，定义变量的域。

感知QoE的动态队列调度具体包括，

使用任务服务延迟的导数作为QoE灵敏度的值，对于在队列的子任务，QoE灵敏度可以表示为，

，

其中服务延迟包含外部延迟、到目前为止的队列等待时间和估计的处理时间；解决方案是使用-最大导数到队列的位置；重新引入排序方法，

，

排在前面的子任务具有较高的QoE敏感性和较短的处理时间，根据CPU周期最大的子任务的排序指标来调整每个队列的排序顺序。

两阶段调度策略可以概括为以下程序语言：

输入为新到达的任务，队列的状态、VMs的结果质量、VMs的计算能力、任务日志分别记为变量Queue、 quality 、 capacity 、TaskLog。具体来说，任务日志记录队列中每个任务的等待时间，可以从系统中获得。输出是重新调度后的队列顺序。这三个功能共同构成了两阶段调度策略。函数TaskPartition和InsertTask负责任务分区，而函数ReorderTask根据它们的QoE敏感性和处理时间重新排列任务顺序。该算法首先计算新到达任务的分配权重 (第7-10行)，然后根据权重 (第12-17行)将任务分配给每个VM队列。任务的重新排序由函数ReorderTask完成。上文的排名指数是使用子任务的最大完成时间来计算的(第22-25行)。最后，每个队列中的任务根据它们的排名索引重新排序。

本发明中，QoE是指用户体验质量，而且QoE的值和服务延迟是非线性相关的，虽然在传统的相关工作中也有针对QoE进行的优化，但是这类工作基本都是通过尽可能优化最小化平均服务延迟来实现较高的QoE水平。而本发明中，我们认为QoE的值和和服务延迟是非线性相关的，遵循一种“S”型的下降曲线。参照图2，纵坐标的服务延迟表示边缘服务器的处理延迟加上数据往返边缘服务器花费的传输时间。在本发明中，分别称之为服务器端延迟和外部延迟。其中，外部延迟是受网络传输带宽等影响，在到达调度器时是个已知的变量，因此本发明模型中把它视为已知量。服务器端延迟则是一个受调度方法影响的变量，因为不同的任务分配方法会带来不同的处理延迟。外部延迟和服务器端延迟共同构成了任务的服务延迟，服务延迟决定着用户的体验质量，即本发明的QoE。本发明的优化目标是最大化用户整体的QoE值，使得本发明的优化方案能够使用户群的满意度最大化，这是传统的调度方法所没有涉及到的。此外，本发明的模型也考虑了不同任务的结果精度需求不同。精度的异质性需求只是本发明模型中的一个约束条件。

性能仿真测试：

1. 实验数据:采用不同的机制来模拟所涉及的信息。在本实验中，我们假设QoE最大值为5，QoE值和服务延迟的关系设置为QoE(SD)=-4.298exp(-0.0347*SD)+1.390。对于算法池，其中相同类型的任务采用的VM数量为5个，它们执行的算法不同，计算精度分别设置为75%、80%、85%、90%、95%。计算精度要求越高，计算过程越复杂，计算要求越高。将每种VM的计算速度(f) GHz与结果精度(q)的关系定义为f=1/[c(1+q)^s_c]，其中c=0.1为最小计算需求，s_c=4为调整算法复杂度与性能关系的参数。在线任务按照泊松分布到达，其要求的精度服从正态分布，均值为80%，方差为0.05。每个在线到达任务的CPU周期按照[5,20]G的均匀分布进行设置。任务的外部延迟在[0.5,2.5]秒范围内均匀生成。

2. 比较算法:对以下算法进行了补充和比较:

FAFS：First-Arrive-First-Served，先来先服务的方法。此方法是一个基线，其中第一个到达的任务将以最高优先级处理。

SFR：Sensitivity-First Ranking，敏感性优先排序法。其中QoE灵敏度设置为任务外部延迟及其在QoE曲线上的等待时间之和的导数。具体来说，QoE模型中延迟和斜率最大的任务将按第一顺序分配，依此类推。

MSR：Mixed-Sensitivity Ranking，混合灵敏度排序法。该方法在考虑任务处理时间和QoE敏感性的基础上，采用混合策略对队列序列进行重新调度。处理时间短、QoE敏感性高的任务优先级高。

3. 评估指标:使用以下指标严格分析以上方法。

QoE值：对于一个外部延迟为补充属性的物联网在线到达任务，排序方法可以确定任务的处理顺序和服务器端延迟。因此，可以通过基于QoE曲线的总延迟来估计用户的QoE。

服务器端延迟：在实验中，服务器端延迟被定义为任务到达Cloudlet服务器开始，到该任务被处理完成为止。

任务完成率：在没有对任务上传数据中心进行处理的情况下，如果卸载到服务器的任务过多，那么部分任务会因为优先级较低而滞留在队列中等待。完成率表示在给定的时间限制内完成任务的比率。

评价方法如下。首先，按所述实验设置生成实验模型。然后根据所述的任务划分方法建立任务分配权向量。给定一组在线到达的任务，对它们的输入数据划分给每个VM，并根据算法规划这些任务的调度策略。最后，按照所述的任务调度方法对其性能进行仿真，分别测量其QoE值、服务器端延迟和任务完成率等指标。

为了适应任务到达率波动的实际情况，将前200秒的任务到达率λ设置为一个较大值1，将后400秒的任务到达率λ设置为一个较小值0.2，以使得虚拟机有足够的时间消耗队列中累积的任务。所有的实验结果都是在600秒的模拟时间内得到的。另外，QoE的最大值和最小值分别设置为5和1.39。

图3为不同在线到达任务下的比较方法的QoE曲线。在前200秒，QoE值较低的任务逐渐累积，队列长度和任务等待时间逐渐增加。在接下来的400秒内，随着任务到达率的降低，队列逐渐变短，导致QoE值变大。MSR方法执行得最好，大量的任务以较高的QoE值被服务器处理。此外，FAFS方法的QoE值连接成一个近乎连续的曲线，因为任务是按照到达的顺序处理的。相比之下，SFR和MSR方法的QoE值是分散的，这是因为在不影响任务到达顺序的情况下，这两种方法调整了任务处理的优先级。图4展示了这一过程中每个任务的服务器端延迟。

在图5中，前200秒的任务到达率设置为0.4到1.6，后400秒的任务到达率仍然设置为0.2，可以看出，所有比较方法的平均QoE均随着任务到达率的增加而降低。这是因为较大的任务到达率会加剧队列拥挤，导致服务器端延迟较长，QoE值较低。此外，由于综合考虑了排序指标，MSR方法在三种比较方法中表现最好。需要注意的是，随着队列长度的延长，在给定的600s的时间限制下，有些排在后面的任务无法完全处理。比较方法的任务完成率如图6所示。具体来说，当前200秒的任务到达率小于1.0的时候，任务几乎可以在仿真时间内全部完成。然而，随着任务到达率的增加，任务完成率呈线性下降。对于MSR方法，当λ= 1.6时可以完成80%以上的任务，而FAFS和SFR方法的任务完成率仅为72%左右。

图7给出了仿真时间为600s时，MSR方法相比于SFR方法的QoE增益。其中，这里的QoE增益表示QoE值相对于基线的增益。将前200秒的任务到达率设置为1，后面400秒的任务到达率设置为0.2。曲线上的每个点是任务在20秒内的平均QoE增益。从图中可以看出，QoE的增益在前20秒和后80秒接近于0。这是因为队列在这些时间窗口中刚刚开始累积或已经恢复。在这种情况下，虚拟机可以提供即时服务，因此这些方法的QoE值是类似的。然而，当任务队列拥挤时，QoE增益是令人满意的。对于SFR方法， QoE值的最大增益可达210%左右（第260秒），而对于MSR方法，其最大增益达到了250%以上（第300秒）。

图8展示了MSR方法在不同QoE阈值下的任务完成率与任务到达率的关系。在该图中，根据实际情况，一旦某个任务的QoE低于一个阈值，系统将直接放弃它（拒绝该任务或者上传到云数据中心）。传统的方法是设定一个任务期限，即QoE曲线开始下降的时间点。但是，这种方法不能充分利用计算资源来完成更多的任务。容忍QoE值的轻微下降可以为更多的任务提供一个完成的机会。与传统带有任务期限约束的方法相比(QoE= 5)，MSR方法在QoE> 3.5,QoE>4,和QoE> 4.5时可以得到更大任务完成比例。

对三种策略进行比较:1)多算法与任务划分(M-Partition)，一组虚拟机配置不同精度的算法用于处理同一类型的任务，卸载的任务根据其精度需求拆分到多个虚拟机来共同处理；2)多算法无任务划分(M-NonPartition)，一组虚拟机配置不同精度的算法用于处理同一类型的任务，但是计算卸载任务不进行拆分，而是根据精度需求安排到一个虚拟机来处理；3)单算法无任务分区(S-NonPartition)，一组虚拟机的资源分配给一个虚拟机，配置一种算法（95%）用于处理该类型的任务，卸载的任务直接安排给该虚拟机进行处理。

图9-11显示了不同任务分区策略下的任务平均QoE值、任务完成率和服务器端延迟。M-Partition策略在这三个指标中表现最好。其原因是，该任务是由一组具有不同精度和计算速度算法的虚拟机并行来完成的。相比之下，M-Nonpartition策略只能选择一个虚拟机处理一个任务，而无法满足精度的异质性需求，从而增加了处理时间。S-Nonpartition策略的性能甚至更差。这是因为所有的任务都会被一个算法不加区别地处理。虽然该算法可以提供令人满意的结果精度，但复杂的算法会导致较高的计算量和处理时间，进而影响总体的QoE值。

综上所述，本申请为提高QoE值和任务完成率提供了一种令人满意的方法。具体来说，当任务队列在λ = 1的情况下出现200秒的拥塞时，本申请的MSR方法的QoE值可以获得大约200%的增益。另外，与传统的基于任务期限的方法相比，本申请的MSR方法将QoE阈值设置为4.5，在600s的模拟时间内，大约可以完成两倍的任务。与传统的S-Nonpartition策略相比，当λ < 1时，M-Nonpartition策略也显著降低了任务的平均服务器端延迟。