基于移动边缘计算的混合分布式任务容错调度方法*

陈 刚 王志坚 徐胜超

（广州华商学院数据科学学院 广州 511300）

1 引言

移动边缘计算［1～2］以及物联网等技术的高速发展，异构分布式系统被广泛的应用到飞机控制、核电站控制等各项高端系统中。这些系统在执行任务时都存在实时性，因此若任务不能在规定时间内完成，会给整个系统带来灾难性打击。为保障系统任务在出现故障后，仍能在任务时效范围内完成任务，需要分布式系统［3～4］具备容错力。因此移动边缘计算中的任务调度也成了近年来国内外学者的重点关注与研究的问题。

文献［5］研究了一种基于综合匹配度的边缘计算系统任务调度方法，针对边缘计算系统资源异构且受限的特性，研究边缘任务与目标设备资源深度匹配的有效方法，设计了基于任务资源匹配、负载均衡和任务公平性的综合匹配度评估方法，并设计基于网络流的在线多任务调度算法，时限任务调度，但是该方法由于调度环境较差，导致调度时延较高的问题。

文献［6］研究了社会属性感知的边缘计算任务调度策略，根据服务器的负载分布情况衡量整个网络的负载均衡度，结合强化学习方法为任务匹配合适的边缘服务器，进而构造任务时延和终端发射功率的映射关系来满足物理域的约束，结合终端用户属性，为任务不断地选择合适的中继终端，通过终端辅助调度的方式实现任务调度，但是该方法的约束条件构建较差，导致调度精度低。

文献［7］研究了面向优先级用户的移动边缘计算任务调度策略，该算法根据任务的处理价值及任务的数据量，计算任务的优先级，结合任务截止时间、服务器调度次数，制定资源匹配方案，解决了边缘网络中服务器为不同优先级的用户进行计算资源分配的问题，实现了任务调度，但是该方法由于匹配精度低，并且调度环境差，导致任务调度时的容错成功率低。

移动边缘计算可以有效构建平稳的调度环境，因此，为解决上述任务任务调度方法中存在的问题，提出基于移动边缘计算的混合分布式任务容错调度方法。并且在此基础上，结合了任务容错调度模型，优化了任务容错调度方法，实现任务容错调度，以期提高任务调度效率。

2 建立任务容错模型

在对混合分布式任务开展容错调度前，需要建立相对安全的移动边缘计算环境，构建混合分布式任务的容错调度模型。

2.1 基于边缘计算的调度环境

容错技术是指混合分布式系统在硬件、软件故障的情况下仍然能正确的执行任务，其本质就是冗余，因此系统任务容错调度是系统的冗余容错技术。该技术包括信息冗余、时间冗余、冗余附加。

信息冗余是指系统为达到纠正信息的目的，加入外部信息。采用冗余码制式纠正信息。时间冗余主要是通过重复的执行命令来消减瞬时错误影响。执行过程为从系统源地址出发，经过处理器处理，送至目的节点，该执行过程成功，则执行下一个任务指令，反之则复执不成功。冗余附加是上述技术的保障，包括关键程序信息的冗余存储和调用、系统检测、切换、纠错等预处理。

系统任务在容错调度时，系统状态较为复杂，并且需要处理大量的信息，同时，容错技术存在时延长的局限性，因此，在容错技术的基础上，需要引入移动边缘计算，构建一个稳定的容错调度环境的同时，处理调度任务数据，降低时延，提高调度精度。

移动边缘计算是Intel、IBM等企业制定的电信标准。主要负责用户周边的IT服务环境，从而避免系统故障出现计算瓶颈。因此在开展混合分布式任务容错调度前，需要依据移动边缘计算构建安全平稳的容错调度环境。

移动边缘计算架构于混合分布式系统与用户移动设备之间，从而衍生出三层层次结构。移动边缘计算采用任务卸载方式增强终端的设备性能，保障混合分布式系统及时完成任务。移动边缘计算体系具体结构如图1所示。

图1 移动边缘计算体系结构图

构建移动边缘计算环境的关键点是通过云计算在混合式系统边缘、网络以及移动网络边缘，为用户提供计算，保障数据的敏感以及延迟敏感的应用。

依据图1可知，移动边缘计算体系结构由四分部分组成，分别为终端、边缘网络、核心网络和云计算。终端主要由传感器、手机等物联网设备组成，主要作用是采集数据并上报。边缘计算部分主要由边缘网络节点构成，分布在边缘网络模块中，边缘计算层包含多个边缘网络服务器，通过合理部署和调配网络边缘侧的计算和存储能力，实现任务调度的基础服务响应。核心网络由移动网络构成，即主干网，其是在主要连接点之间建立的通信网络。云计算部分是混合式分布系统组成，其是数据处理中心，并且存储边缘计算传输的数据，主要处理的内容是边缘计算未分析处理的任务。

通过上述可知，移动边缘计算体系将移动网络、边缘计算和云计算等相结合，即结合了边缘计算、移动计算等，构建了一个云、边、端的任务调度环境，它可以更加稳定网络环境，还可以通过边缘计算模块处理任务的容错调度数据，保障了系统任务的容错调度精准性。

2.2 构建混合分布式任务容错调度模型

混合分布式系统是由若干有线宽带网络互联形成的处理器构成，运行时需要控制多个回路，且每个回路以固定频率运行，从而实现数据采集、运算、控制输出等任务。由于任务之间互相影响，因此在控制过程中需要不同的处理器实施处理。

设定混合分布式控制系统的处理器［8～9］集合为C，获取处理器cij的处理能力执行速度，过程如下式所示：

式中，标准处理器执行时间表述成S()nor形式，在cij上的执行时间描述成S()cij形式，处理器处理能力系数标记δ。

由于系统在任务处理时，任务之间存在独立主版本以及副板本，在不同的处理器上运行。因此，混合分布式系统在运行时若出现故障，通常先是主版本故障，再是副版本，所以需采用集成电路技术（Integrated Circuit，IC）决定任务主、副版本的控制。基于此，计算处理器平均利用率Pi计算过程如下式所示［10］：

式中，处理器数量标记N形式，i表示任务，任务i的实时回路任务用ηi表述，T表示执行周期。

最后依据上述制定的各项约束条件，建立混合分布式任务容错调度模型，结果如下式所示：

式中，φ表示处理器执行时间系数，混合分布式任务容错调度模型用β描述。依据上述容错调度模型［11～12］，确定任务执行时的系统错误类型。

3 任务容错调度

为达到容错目的，将任务分配在不同的处理器上，系统执行任务时，通过主版本执行任务，执行过程若未发生故障，版本持续运行直至任务结束，若主版本发生故障，直接将任务调整至副版本投入运行。依据上述建立的混合分布式任务容错调度模型，将混合分布式任务容错调度分为任务分配以及处理器局部调度两个部分。为实现容错，需使任务在容错调度时，满足如下条件：

1）确定任务满足∀ηi∈Tφ·dp+φ·db≤ηi·Pi，主版本处理器标记dp形式，副版本用db表述，规避任务在主版本因故障执行失败后，副版本能够有足够的时间调度执行任务。

2）系统实时任务ηi执行主副版本需安置在不同的处理器上，且执行过程不重叠。

3）保证主副处理器之间的通信时间，忽略处理器消息传递时间。

通过抢占式EDF（Earliest Deadline First）调度算法［13］对调度单处理器，调度过程当主版本时限为φ·dp≤ηi·(Pi-db)时，说明处理器未发生故障，但是任务同样未能执行，此时副版本处理任务。

设定任务集R在处理器集上C上的调度条件

混合式分布系统执行任务时，发生故障时处理器cij要同时执行主、副两个版本任务。基于上述分析结果，可使用贝克分析方法建立处理cij的任务可调度条件，过程如下式所示：

式中，tj表示第j个处理器的执行时间，Pj表示第j个处理器的利用率。由于系统在执行容错调度时，主版本与副版本的任务时限需要小于计算出的采样周期，因此需要对获取的调度条件［14～15］更新优化，过程如下式所示：

式中，t'表示副版本执行时限。依据上述更新后调度条件，依据，获取任务执行时最小处理器数量，通过任务分配算法分配任务，通过分配结果，实现任务的容错调度，过程如下：

步骤1：在模型中输入任务的执行时间、最小处理器数量，对模型中任务周期等参数初始化处理。

步骤2：辨识模型中最小处理器数量是否大于制定的相关约束条件。

步骤3：依据升序方式排列系统任务，依据上述获取的满足条件对任务分配处理。

步骤4：当任务ηi在分配的处理器中出现故障，依据制定的容错调度条件，对任务容错调度处理，依据处理结果，实现混合分布式系统的任务容错调度。

4 实验与性能分析

4.1 实验方案

为了验证上述移动边缘计算下的任务容错调度方法的整体有效性，需要测试设计方法的性能。设计整体实验方案，准备实验，明确研究对象，说明实验参数，这是实验的基础。在完成实验准备后，分型设计方法的性能，任务在开展容错调度时，容错调度方法的调度性能是检测容错调度方法优劣的关键，依据任务容错调度时任务的延时程度、调度精度以及容错成功率检测结果。根据上述实验方案进行实验分析。

4.2 实验准备

实验以某企业的混合分布式系统为研究对象，在该系统上应用所提方法。该企业系统的日任务调度规模在15G左右，随机选取1000Mb的任务调度数据，并且在是实验时，设置6个错误发生时间点，分别为0.2、0.4、0.6、0.8、1.0和1.2。具体实验参数如表1所示。

表1 任务容错调度实验参数

实验环境网络包含一个云服务器、多个边缘网络服务器，两个RSU节点，n个任务节点，任务节点数量n≥1，使用Tra CI移动模型的SUMO模型放置的多个任务调度节点。在实验中，云服务器、多个边缘网络服务器的位置固定，每个任务节点与云服务器以及边缘服务器彼此之间都是独立的，任务节点在与云服务器、边缘服务器进行信息传输交互过程互不影响。在实验过程中允许的数据包大小即队列容量上限为256 bytes。

4.3 性能分析

分别采用基于移动边缘计算的混合分布式任务容错调度方法（本文方法）、社会属性感知的边缘计算任务调度策略（文献［6］方法）、面向优先级用户的移动边缘计算任务调度策略（文献［7］方法）测试。

1）任务容错调度的延迟程度测试

将任务调度延迟为调度效果测试指标，任务调度延时结果越大，说明调度效果越差，反之则越好。选取所提方法、文献［6］方法以及文献［7］方法开展任务容错调度时，测试上述3种方法的任务调度延迟程度，结果如表2所示。

表2 不同方法的任务调度延迟测试结果

分析表2实验数据可知，随着调度规模的增加，3种方法测试出的调度延迟结果均出现不同程度的上升趋势。其中，本文方法在开展任务容错调度时，测试出的调度延时是3种方法中最小的，证明本文方法在任务容错调度时的延时较短，调度效果好。

2）任务调度精度测试

任务调度规模是在相关约束条件下，将满足调度条件的任务分配到相应处理器上，可作为调度精度的辨别指标。

采用本文方法、文献［6］方法以及文献［7］方法开展任务容错调度时，测试上述3种方法的任务调度规模，测试结果如图2所示。

分析图2实验数据可知，任务调度规模的大小会影响调度方法的调度精度。其中，本文方法在开展任务容错调度时，所受的影响低于其他两种方法，在任务调度规模达到600Mb时，本文方法的任务容错调度精度为88.9%，文献［6～7］方法的调度精度分别为64.8%和52.9%，本文方法比文献方法高了24.1%和36.0%，因此，本文方法有效提高了任务容错调度精度。这主要是因为本文方法在开展任务容错调度前，建立了基于移动边缘计算的任务调度环境，从而有效地提升了任务的调度精度。

图2 不同方法的任务调度精度测试结果

3）容错成功率测试

容错成功率是指系统在任务执行时，任务容许的失误几率。任务容错调度时，保证一定的容错成功率，能够有效增加调度的可靠性。

采用本文方法、文献［6］方法以及文献［7］方法开展任务容错调度时，测试上述3种方法任务调度时的容错成功率，测试结果如图3所示。

图3 不同方法的任务调度容错成功率测试结果

分析图3可知，在任务容错调度过程中，任务执行时执行前期的容错成功率会高于任务执行后期。本文方法测试出的容错成功率明显高于文献

［6］方法以及文献［7］方法，在时间点为1.2时，本文方法的容错成功率为90.8%，文献方法容错成功率分别为73.1%和61.2%，相比本文方法分别低了17.7%和29.6%，因此，说明所提方法在任务容错调度时，具备有效性。

综上所述，本文方法在任务容错调度时，调度延迟低、调度精度高、容错成功率大，证明本文方法在任务容错调度时，调度性能好。

5 结语

随着混合分布式系统使用范围的增加，混合分布式任务容错调度就变得尤为重要。针对传统容错调度方法中存在的问题，提出基于移动边缘计算的混合分布式任务容错调度方法。该方法依据相关约束条件建立系统的任务容错调度模型，基于建立的模型以及制定的容错调度条件，完成混合分布式现任务的容错调度。本文方法的调度延迟仅为1.27s，调度精度提高了24.1%和36.0%，调度容错成功率提高了17.7%和29.6%，由此可知，本文方法具备可行性和有效性，其应用价值更高。在未来的工作中，需要针对调度条件，深入优化调度方法。