VEC中基于动态优先级的抢占式任务调度方法

贾梦欣,范艳芳,宋志文,陈若愚,蔡英

(北京信息科技大学 计算机学院,北京 100101)

0 引言

随着网络技术的不断发展,车联网(Internet of vehicles,IoV)成为智能交通系统的基础技术[1]。随之而来的变化就是车辆上涌现出各式各样的应用,如安全类的车载增强现实、车辆避障等,以及非安全类的车内观影、视频通话等。这些应用的出现为车辆用户提供了便利[2]。然而,部分应用或对资源的需求较高,或对时延较敏感,车载软件和硬件系统难以满足其苛刻的要求[3-4]。为解决车辆自身计算能力有限的问题,引入移动云计算(mobile cloud computing,MCC)[5]技术,利用云服务器中丰富的资源为应用提供计算服务,可为车辆用户带来更高质量的体验[6]。但是,云服务器部署的位置通常距离车辆较远,远程通信会带来过高的传输延迟,可能会对车辆用户的生命安全造成严重威胁[7-8]。

为了解决移动云计算中任务传输时延过大的问题,作为移动边缘计算[9](mobile edge computing,MEC)和车联网的交叉领域,车载边缘计算(vehicular edge computing,VEC)可以满足车载应用在时延和计算能力方面的严格要求[10]。在VEC环境中,服务器被部署在距离车辆更近的网络边缘[11],通过降低服务器和车辆之间的传输延迟,为车辆提供高质量的服务。但是对于边缘服务器来说,资源不如云服务器丰富[12],特别是在工作负载密集的场景中,不断增加的车辆和计算任务会导致边缘服务器负载过重,其中的任务可能由于不合理的调度顺序,出现争抢资源的情况,从而导致任务失败率升高。若失败的是与安全相关的任务,会影响车辆及用户的生命财产安全。

现有研究主要通过为任务设置优先级来安排任务的执行顺序。然而,车辆上的应用多种多样,若只考虑某一类应用的需求,优先级的设定会具有较强的针对性,忽略其他类应用的计算需求,从而导致整体效果不佳。因此,在设定任务优先级时需要兼顾应用的多种计算需求。与此同时,车辆的高移动性致使其在基站(base station,BS)覆盖范围内的停留时间有限,若车辆无法在驶出通信范围前收到计算结果,也会导致任务失败。因此,通过考虑多种因素综合判断出任务紧急程度,在执行任务时适时调高紧急任务的优先级,以降低任务失败率,保护车辆用户的安全。

本文的主要贡献在于设计了多因素任务优先级模型,在处理任务时可以更好地平衡车载应用的多种计算需求,避免优先级偏向某一种类型的应用。通过设计基于任务紧迫性的优先级动态调整策略,及时关注到由车辆移动性导致的任务计算需求的变化,从而提升紧急任务成功完成的可能性。通过将任务最大可等待时间与优先级相结合,设计了一种任务抢占机制,使任务之间频繁抢占的状况得到改善,降低了任务失败的可能性。

1 相关工作

在VEC环境中,为了解决服务器内部任务执行顺序的问题,现有的相关研究关注任务的优先级策略。优先级策略根据任务特性安排执行顺序并按需为其分配计算资源,主要分为两种:静态优先级和动态优先级。

静态优先级是指任务的优先级一经确定,便不会再改变,直至任务从队列中被删除。在现有基于静态优先级的任务调度研究文献中,一般是基于任务的某一个特征来制定优先级。Liu等[13]研究车辆应用在路边单元(roadside unit,RSU)中的排序,对多个应用程序按照时延限制排序,并对同一应用程序中的多个任务按照依赖性排序,提出一个多应用多任务调度算法求解调度决策问题。仿真结果表明该算法可以显著减少多个应用程序的平均完成时间。Chen等[14]针对移动环境下的调度问题,提出一种混合动态调度方案,由决策函数在基于队列的算法和基于时间的算法中选择一种,两种算法分别按照服务器中队列长度以及已等待时间进行排序,结果表明该方案在不稳定的VEC环境中具有优越的性能。Wang等[15]研究VEC网络中根据车辆位置、速度和方向将任务调度给服务车辆(service provided vehicles,SPV)集群,并将SPV建模为M/G/K/N队列系统。提出了基于模仿学习的在线调度算法。仿真表明,该方案与基准算法相比,平均能耗、本地SPV的任务处理率和平均任务执行延迟方面均有超过50%的提高。Selvi等[16]对车辆上的紧急信息、一般信息和娱乐信息进行优先排序,利用基于SMTP的相似性指标来定义信息的优先级,并使用自适应调度分区技术完成紧急信息的广播。Paymard等[17]提出了一种基于优先级的任务调度策略,共同优化计算和通信资源分配,以便在满足用户的服务质量、用户和基站的功耗以及服务速率分配的同时,使移动网络运营商的利润最大化。

动态优先级是指系统先为任务分派一个初始优先级,在运行过程中根据任务状态等因素改变任务的优先级。云计算环境中有部分文献是基于任务的多种特性制定优先级。如叶波等[18]根据任务价值度与任务紧急度计算动态优先级,同时参考萤火虫行为,由吸引度、亮度以及负载均衡度得出调度决策。该方案可以缩短总任务的完成时间,尤其当任务数与节点数规模较大时,该方案在负载均衡方面的优势更为明显。刘亚秋等[19]利用任务价值密度和执行紧迫性计算动态优先级,通过模拟萤火虫行为将任务调度至合适的虚拟机中。该方案可以降低任务的总完成时间,均衡虚拟机的负载,并降低任务的截止期错失率。

然而,云环境中的任务是由固定设备或手机、电脑等移动性不高的设备产生,而在VEC环境中,任务是由移动车辆产生的,因此也要考虑到车辆的高移动性对调度决策的影响。Wang等[20]解决了车载系统中联合任务调度与资源分配问题,首先利用任务的时延容忍度制定优先级,再通过分组来优化低优先级的任务被提前处理的可能性,最后将资源分配问题转化为马尔可夫决策过程,用强化学习来求解。Li等[21]研究自动驾驶实时应用中计算资源调度问题。为了减少车辆从卸载数据时刻到接收结果时刻之间行驶的距离,根据边缘服务器计算能力以及车辆移动性确定任务处理顺序,用深度强化学习方法确定构造的基于Whittle的指标来得到随机调度方案。该方案以较低的复杂度,在适应车辆移动性的同时及时将结果传递给车辆。Zhang等[22]提出了一种针对车辆自组网安全消息的动态优先级调度方案,动态调整消息的优先级以满足车辆的安全需求,该方案在车辆密度较高时可以减少网络的重复远程通信流量,在车辆密度较低时增加数据可传输的距离。

综上,静态优先级的性能在一般情况下不如动态优先级,因为它无法体现车载任务需求的动态性。虽然在云计算中已经有部分研究是根据任务的多种特性来制定优先级,但在现有VEC任务调度研究中,优先级制定依据较为单一,无法同时满足任务的多种计算需求。此外,VEC环境中现有研究的优先级较为固定,难以适应由车辆移动性引起的任务紧迫性的变化,容易导致任务失败率升高。因此,在考虑制定任务优先级时综合多种应用的特点,设计一种基于动态优先级的任务调度方法是很有必要的。

2 系统模型

2.1 车载边缘计算场景

本节对车载边缘计算场景进行描述。图1所示为在城市单向道路上,一个由车辆、BS和VEC服务器组成的车载网络。道路一侧部署了覆盖半径为L的BS,BS中配置了VEC服务器,服务器的计算能力用f表示。道路中的车辆通过V2I(vehicle to infrastructure)的方式与BS通信,用集合N={1,2,3,…,n}表示某一时间段中BS覆盖范围内的所有产生任务的车辆,由于车辆自身的计算资源有限以及处理车辆任务可能需要用到BS范围内的某些信息(环境等),因此本文中考虑的每个任务都需要卸载到VEC服务器并在延迟约束内执行,且每个车辆一次只产生一个计算任务,任务之间相互独立。

图1 车载边缘计算场景Fig.1 Vehicular edge computing scenario

2.2 任务优先级模型

由于以上三种因素的单位不一致,若直接利用原始数据进行计算,容易突出数值较大的因素的作用,同时削弱数值较小的因素的作用。为了消除数据单位带来的影响,对初始数据进行标准化处理。本文采用离差标准化,分别对这三种影响因素的原始数据进行线性变换,使其结果映射到0和1之间,再根据各自的权重计算优先级。以xi,j表示任务i的第j个优先级影响因素,则处理后的数据x′i,j表示为

(1)

对任务原始数据进行标准化处理后,依据影响因素各自的权重值计算综合优先级,公式表示如下:

(2)

2.3 时延计算模型

(3)

(4)

(5)

2.4 任务优先级调整策略

在实际生活中,与手机、电脑等移动性较弱的移动设备不同,车辆的移动性较强,使得车辆在BS覆盖范围内的行驶时间有限,这对车载任务能否按时完成提出了挑战。对于优先级较低但紧迫性随车辆移动而升高的任务,静态优先级策略无法很好地适应。因此,需要动态调整优先级以降低任务失败率,并分析影响优先级调整的因素。

为了确保车辆在驶离范围前及时收到任务的计算结果,要关注车辆的位置变化,重点研究临近覆盖范围边界的车辆。首先,利用车辆的坐标可以计算出t时刻车辆与通信范围边界的距离di,计算公式如下:

(6)

(7)

(8)

(9)

(10)

因此,在任务优先级的调整策略中,本文设计一种优先级调整必要性分析模型,将车辆在BS通信范围内的剩余时间和任务执行状态一同表示为任务的紧迫性,来决定是否调整任务优先级。令Ui表示任务紧迫性对优先级调整决策的影响:

(11)

当服务器检测到有Ui=1的任务时,将任务的优先级调至最高,抢占当前正在执行的任务,使得紧急任务可以优先获得计算资源。

3 任务调度问题描述

本文研究VEC服务器内的任务执行顺序,以降低任务失败率过高对车辆用户带来的影响。为了更精确地计算服务器中任务的失败率,选取某一时间段内的任务,将任务总数记为n。本文以最小化任务失败率为目标。首先,计算成功完成的任务数量S:

(12)

式中,Fi用来判断任务是否在最大时延限制内完成。

然后,制定最小化任务失败率的优化目标:

(13)

式中:第一个约束表示优先级的三个影响因素的权重值之和为1;第二个约束表示任务的总完成时间要在其最大时延限制内;第三个约束表示生成的车辆坐标要保持在服务器通信范围内。

4 基于动态优先级的抢占式调度

4.1 抢占式调度机制

在VEC环境中,当车辆的行驶位置临近BS的覆盖范围边界,且处于就绪态的任务紧迫性升高时,在传统的非抢占式调度中,任务会因车辆驶出范围而中断执行,也可能会由于等待时间过长而错过最大时延限制,最终致使任务失败。与此同时,由于任务优先级由最大时延限制、任务重要性以及所需资源量共同决定,而优先级高的任务大多数都是与车辆安全相关的,任务失败会对车辆用户的安全造成很大影响。因此,需要为紧迫性升高的任务优先分配计算资源,最直接的办法就是抢占当前正在执行的任务。

然而,车辆的高移动性可能会使多辆车的任务在一段时间内都需要尽快执行,它们的优先级也可能会被频繁地调整。若一个高优先级任务A刚抢占完毕,又出现了优先级比它更高的任务B,根据抢占式调度算法,B是不会考虑A的执行状态的,于是B又抢占了A的资源,那么不仅A无法完成,B也面临着被优先级更高的任务的抢占。频繁的互相抢占不仅会浪费计算资源,也会导致任务的失败率升高。因此,为了保证任务的完成率,需要在抢占之前对抢占行为的必要性进行判断。

由于抢占式调度中具有任务之间频繁抢占导致失败率升高的不足,因此需要找出合理的抢占时机,确保任务被抢占后依然能够在时延限制内完成。本节引入任务的最大可等待时间这一概念[23]。任务的最大可等待时间是任务最大时延限制与总完成时间之间的差值,用来表示任务在最大时延限制内可以被耽搁的最长时间。公式表示为

(14)

将任务的最大可等待时间与任务优先级同时作为抢占行为的判断条件,主要思想是看参与抢占的两个任务能否容忍让对方先完成。假设当前执行的任务是A,要抢占的任务是B,具体抢占行为判断流程如下:

(15)

4.2 抢占式调度算法

算法1 基于动态优先级的抢占式调度算法输入:任务数量n输出:任务执行顺序1. 初始化f、α、β、γ、θ、τ、xi、yi;2. for i = 1 to n do3. Pprii=α·x′i,1+β·x′i,2+γ·x′i,3,存入队列;4. 利用快速排序算法按优先级数值从小到大排列,如果优先级数值相同,则按照tmaxi的值从小到大排列;5. 每隔τ时间:6. if Ui+1 = 1:7. if tmaxwait,i+1

5 实验结果

5.1 实验参数设置

本文运用Python语言进行实验,在不失一般性的前提下,考虑如下场景:取一段长为1 000 m的直线郊区道路,每辆车在这条道路范围内最多只产生一个任务。道路一侧部署了基站,在其范围内车辆可与之进行通信。其他具体仿真参数如表1所示。

表1 仿真实验参数Table 1 Parameters of simulation experiment

5.2 实验结果分析

引入以下三种方案与本文的动态优先级抢占式调度方案(dynamic priority preemptive scheduling,DPPS)进行比较。

1)静态优先级调度方案(static prioritized scheduling,SPS)。服务器根据任务的初始优先级进行排序,不考虑处理过程中任务优先级的变化。

3)直接抢占调度方案(direct preemption scheduling,DPS)。当任务优先级发生变化时,服务器不考虑当前任务的执行状态,直接让高优先级任务抢占资源。

首先将本文方案与SPS和HRRN进行对比,比较任务失败率。当任务数量较少时,大部分任务都能按时完成;而当任务数量较多时,任务失败的概率增大。因此,在固定的任务数量下比较三种算法的执行结果。图2给出了任务数量与任务失败率的关系。可以看出,当服务器中任务数量较少时,三种方案几乎都能保证任务在各自的时延限制内完成;随着任务数量的增长,任务的失败率呈缓慢上升趋势。本文方案的失败率整体增幅是最慢的,即方案能保证大部分任务在时延限制内完成,原因是采用动态优先级的方式能够考虑到由车辆移动性以及等待时间所引起的任务紧迫性的变化,重点关注失败可能性较大的任务,及时调整此类任务的优先级,保证大部分任务的完成率。静态优先级调度方案中的优先级一经确定就不再改变,随着任务数量的增加,队列中优先级较低的任务很可能因为等待时间过长而超出时延限制,导致任务失败。HRRN方案虽然考虑了任务的等待时间,但任务的优先级每时每刻都在变化。随着任务数量的增加,优先级需要调整的次数也随之增加,任务的排序不稳定,会互相抢占计算资源,如此反复,可能会令多数任务都无法按时完成,也会导致失败率升高。

图2 任务数量与任务失败率的关系Fig.2 Relationship between number of tasks and task failure rate

任务最大时延限制表示任务从生成开始所能容忍的最长时间,时延限制越小的任务失败的概率越大。因此比较不同时延限制对三种算法失败率的影响。图3给出了任务最大时延限制与任务失败率的关系。

图3 任务最大时延限制与任务失败率的关系Fig.3 Relationship between maximum task delay limit and task failure rate

可以看出,随着最大时延限制的增加,三种方案的任务失败率在整体上皆呈下降趋势。静态优先级调度方案与本文的方案相比缺乏灵活性,虽然任务最大时延限制的增加能够提升部分低优先级任务被处理的可能性,但长时间的等待也会增加部分任务失败的可能性。HRRN方案中任务的优先级随着等待时间的增加在实时变化,对时延敏感的任务通常被优先处理,留下部分对时延不敏感的任务,这些任务的执行顺序不固定,所有任务都面临着被其它任务抢占的可能性,而可能性的大小会影响任务的完成,因此该方案无法保证任务的完成率。本文的方案对以上两种方案进行了权衡,不仅能够及时地为紧急任务分配计算资源,同时也会分析抢占行为的必要性,能够保证多数任务被成功处理。

服务器的计算能力决定了任务的计算时间,计算时间越长的任务失败的概率越大。因此比较不同服务器计算能力对三种算法失败率的影响。图4给出了服务器的计算能力与任务失败率的关系。可以看出,随着服务器计算能力的增大,本文的方案和静态优先级调度方案的任务失败率在大体上皆呈下降趋势,仅有小范围内的波动,这是因为当服务器能力相差不大时,任务的计算时间也相差不大,又因为抢占行为本身具有不确定性,可能使少数任务无法成功完成,但从整体的角度来看,本文方案优于静态优先级调度方案。而HRRN方案的失败率变化幅度较大,原因是随着服务器计算能力的提升,资源需求量较小的任务可以在短时间内完成,但资源需求量较大的任务的完成时间较长,在处理的过程中容易受到高优先级任务的直接抢占而被迫中断,导致任务失败。

图4 服务器计算能力与任务失败率的关系Fig.4 Relationship between server computing power and task failure rate

然后将本文方案与DPS进行对比,在固定的任务数量下比较两者的执行结果。图5给出了任务数量与任务抢占次数的关系。可以看出,与直接抢占调度方案相比,本文的方案能够有效降低任务抢占次数。在直接抢占调度中,服务器不会考虑被抢占任务的执行状态,而是默许优先级较高的任务直接中断当前任务以获取计算资源,频繁的抢占不仅会增大任务失败的可能性,还会增加抢占时产生的系统开销,从而造成计算资源的浪费。而本文提出的方案会通过考虑任务执行状态来决定是否需要抢占,最大程度上减少不必要的抢占行为。

图5 任务数量与任务抢占次数的关系Fig.5 Relationship between number of tasks and number of task preemptions

图6给出了检测时间间隔与任务失败率的关系。由于在任务执行过程中需要检测是否有Ui=1的任务,因此设定一个检测时间间隔τ,τ取值的不同会导致优先级调整结果的不同,从而影响到任务失败率。因此为了选择合适的检测时间间隔,实验从[3,10] s中每隔0.5 s选取一次作为τ的取值。可以看出,当τ≤7 s时,任务失败率的增幅较小,从τ>7 s之后,任务失败率的增幅较大。因此本文在实验过程中选择3到7的中间值5 s作为τ的取值。

图6 检测时间间隔与任务失败率的关系Fig.6 Relationship between detection time interval and task failure rate

6 结束语

本文在车载边缘计算场景下设计一个考虑多因素的任务优先级模型,并以此提出一种基于动态优先级的任务调度方案,解决了因优先级固定导致紧迫任务失败率过高的问题。该方案通过设计结合任务最大可等待时间和优先级的任务抢占机制,使紧迫性升高的任务及时得到处理,从而降低任务失败率。仿真结果表明,相比于直接抢占调度方案,所提方案可以减少任务争抢资源所带来的抢占次数,降低频繁抢占对失败率的影响;相比于静态优先级调度和高响应比优先调度方案,所提方案可以降低10%以上的任务失败率。