一种面向雾计算的任务调度算法研究*

刘林东，邬依林

广东第二师范学院计算机学院，广东广州 510303

计算密集型应用和资源受限型设备之间的矛盾［1-3］已成为雾计算中提供满意体验的瓶颈，需要通过任务调度来解决此问题。雾计算［4］相对于传统的分布式计算和云计算［5］，由数量众多的位置分布的雾结点和终端设备构成，一般由计算性能有限的设备组成，包括路由器、交换机、网关和终端设备等［1，6-8］。由于带宽以及能耗因素影响，性能异构的物联网［9-12］设备（IOT） 得到的数据可以边缘设备上进行计算、分析和调度，从而可以减轻云端的负担。

现有的雾计算任务调度研究［13］，一般根据资源利用率、时间、能耗、成本、负载均衡等优化目标进行资源分配或任务分配。文献［14］ 提出了一种面向雾计算的多用户小区聚类资源优化策略，该策略以最大交付时延作为衡量服务质量的重要指标；文献［15］ 通过定义计算延迟以及通信延迟模型的方法，为雾计算结点的任务调度提供依据；文献［16］ 通过边缘计算和云计算之间的协作，达到功耗以及传输延迟间的负载平衡；文献［17］ 提出了一种启发式任务调度算法，达到调度跨度以及调度成本间的平衡。雾计算任务调度是一个NP完全问题［1，18］。

文中对独立任务流水线任务调度问题进行研究，通过改进的分类挖掘算法建立雾计算任务调度模型以及相应的调度算法，以任务调度跨度和平均等待时间作为主要优化目标，从而提升雾计算用户服务质量以及任务调度吞吐量。

1 雾计算模型

雾计算由前端层、雾层以及云层三层架构构成［19］，如图1 所示。前端层作为用户接口，一般由各种类型的物联网设备组成，向雾层发送任务请求；雾层包括m个异构的雾结点，向雾层发送任务请求，雾层离前端层很近，一方面用户可以直接利用雾层中的计算资源，另一方面，也可以减轻云层的计算压力；部署了多台服务器或者云结点的云层，相比较雾层计算能力更强，由于物理上远离前端层，用户请求一般不直接发送至云层。

图1 雾计算系统架构Fig. 1 System architecture of fog computing

2 I-Apriori分类挖掘算法

2.1 算法描述

经典Apriori算法［20-21］每次迭代产生频繁项集都需要去扫描事务数据库D，由于扫描数据库次数过多，造成生成频繁项集的算法效率较低。为改进经典Apriori算法效率低下的问题，提出一种分类挖掘I-Apriori算法。I-Apriori算法包括两个阶段。第一步：产生频繁1项集L1，获取每个项集的事务标识TID，产生候选集1 项集C1，利用最小支持度阈值得到L1；第二步：生成频繁项集L. 当Lk-1不为空时循环进行后面几项操作，1） 候选k项集Ck直接通过Lk-1的自连接运算得到；2） 利用候选k项集Ck直接得到项集计数；3） 基于最小支持度阈值删除候选k项集Ck中不满足条件项集，得到频繁k项集Lk. 循环结束后最终得到频繁项集L. 算法描述如算法1所示。

算法1：I-Apriori算法

1 产生候选1项集C1；

2 统计事务D中TID的数量count；

3 循环对C1中每个项集s｛

4s. item-set=s；

5C1中s的数量s. count；

6 产生所有包含项集s的TID列表

7 如果s. count＜min_sup*count

8 删除C1中的s；

9 ｝

10k=1；Lk=Ck，；

11 while （Lk-1≠Ø）｛

12 循环对Lk-1中的每个项集l1｛

13 循环对Lk-1中的每个项集l2｛

14 对l1和l2进行连接；

15 直接统计c. tid-list；

16 直接统计c. count；

17 ｝

18 ｝

19 如果c. count大于最小支持度计数｛

20 把c添加Ck中；

21Lk=Ck；｝

22 ｝

2.2 算法分析

利用Java 分别实现经典Apriori 算法和I-Apriori 算法，基于Intel Core（TM）i5-8265U 1. 6 GHz CPU、8 GB内存的硬件环境以及Win10系统生成频繁项集。

在最小置信度为0. 6 的实验条件下，通过对比50～500 个事务数下产生频繁项集的执行时间。图2（a）为最小支持度计数为0. 40的情况下两种算法时间开销对比情况；图2（b）为最小支持度计数为0. 45的情况下两种算法的时间开销对比情况。通过实验得出，I-Apriori算法在两种不同最小支持度下的时间开销均小于经典Apriori 算法的时间开销，最小支持度为0. 40 的情况性能提升了8. 1%～34. 4%，在最小支持度为0. 45的情况性能提升了7. 6%～37. 0%；总体上I-Apriori具有更好的性能。

图2 两种算法在不同最小支持度下执行时间对比Fig. 2 Comparison of execution time of two algorithms under different minimum support

设Apriori 算法中事务数为n，项目数为m，频繁项集迭代数为k， 则算法时间复杂度为O（k4·m·n）；I-Apriori算法的时间复杂度为O（m+n+k3），I-Apriori时间复杂度性能更优。

3 雾计算中任务调度

3.1 任务调度模型

针对雾计算环境中独立任务流水线任务调度问题，将I-Apriori 算法融入到任务调度过程中。雾计算任务调度模型如图3 所示，任务调度模型包括雾结点集F、任务集T、事务集D、调度关系R以及I-Apriori 和ITPS两种算法，在F和T间实现资源分配和任务调度。任务调度的过程是一个迭代更新的过程，每次迭代的基本流程首先利用I-Apriori算法对历史调度事务集D进行分类挖掘，得到F与T间的调度规则，然后利用ITPS算法读取调度规则，得到F与T间的调用关系R，并循环将R更新到D中。

图3 雾计算中任务调度模型Fig. 3 Task scheduling model of fog computing

3.2 ITPS调度算法

ITPS任务调度算法（详见算法2） 主要包括3个步骤：

1） 任务选择。循环选择任务集中的任务，首先选择到达时间ATi最早的任务，若两个以上任务同时到达，则优先选择调度关系R中的任务；若任务到达时间均不相同，算出全部任务在雾计算资源上的最早完成时间，依据最早完成时间和加权链接数的从小到大进行调度；

2） 雾计算结点选择。选择最早完成时间最小的雾计算结点进行任务调度；

3） 任务调度。在雾结点上完成任务的执行，得出任务执行时间等调度数据，直到所有任务被调度完成为止。

3.3 调度过程

通过一个完整的任务调度案例分析ITPS 算法的调度过程，任务调度过程包括任务初始化、初始事务集、I-Apriori算法、任务调用关系以及ITPS算法调度等几个步骤。

3.3.1 任务初始化设任务集T中包含10（n=10）个独立流水线任务，每个任务ti（0≤i≤9）的到达时间如表1所示，其中t0，t2和t5，t3和t4的到达时间相同；雾计算结点集F中包括4（m=4）个性能异构的计算结点Fj（0≤j≤3），任务ti在雾计算结点Fj上的执行开销如表2 所示，执行开销满足一致性模型条件，即任务ti如果在雾计算结点Fj上的执行开销比雾计算结点Fk上的执行开销短，则任何其他任务也是如此。

表1 任务到达时间Table 1 Arrival time of task ms

表2 任务集在处理机集上的执行开销矩阵Table 2 Execution time of task set on fog node set ms

3.3.2 初始事务集初始事务集是任务集T中的任务ti与雾计算结点集F的结点Fj之间的调度关系的集合，事务集中每一条记录为每一次任务调度的信息，“1” 表示任务ti以及雾计算结点Fj出现在某条事务Tz中，“0” 表示事务Tz不包含任务ti以及雾计算结点Fj，设事务集中包含10（z=10）条事务，初始事务集D如表3所示。

表3 事务集Table 3 Transaction set

3.3.3 I-Apriori算法

1） 产生频繁项集。基于初始事务集D执行I-Apriori算法，以最小支持度0. 5为例，得到｛F1，F0，F3，t2｝

算法2：ITPS算法

输入：Time［n，m］，R［t，c］，任务集TS

输出：任务调度跨度makespan，任务平均等待时间AWT

1 针对任务集｛ //循环对每个任务集进行调度

2 针对每个任务｛

3 针对每个雾计算结点｛

4 计算EFT［］；

5 ｝

6 查找具有最小最早完成时间的任务tj；

7 计算任务开始时间ST［］；

8 按EFT［］值对任务进行排序；

9 ｝

10 当任务集非空｛

11 针对雾计算结点

12 计算加权最小链接nwc［］；

13 若多个任务同时到达

14 选择调度关系R中的任务

15 否则

16 选择最早完成时间EFT［］最小的任务ti；

17 选择任务ti最早完成时间EFT ［i］ 最小的雾计算结点Fj上调度；

18 计算任务调度时间WT；

19 更ST［］和FT［］；

20 任务降序排列；

21 ｝

22 计算并输出makespan以及AWT；

23｝

以及｛F2，F0，F3，t3｝两个频繁项集；

2） 产生关联规则。设最小置信度为0. 7，利用生成的频繁项集，得到两个关联规则，分别为t2⇒F1∨F0∨F2，t3⇒F2∨F0∨F3.

3.3.4 任务调用关系根据I-Apriori 算法得出的两个关联规则，生成对应的任务调度关系。任务调用关系是任务集T中的任务ti与雾计算结点集F中的结点Fj之间的强关系的集合，即出现在任务调度关系中的任务ti优先被调度。ti和Fj存在3种关系：①若ti与Fj未出现在关联规则中，则ti行对应的值全部为0，其中t0，t1，t4，t5，t6，t7，t8，t9与Fj未出现在关联规则中；②若ti与Fj出现在关联规则中，则计算任务ti在雾计算结点Fj上的置信度，t2在F0，F1，F2上的置信度分别为0. 33，0. 37和0. 30，t3在F0，F1，F2，F3上的置信度分别为0. 33，0，0. 35 和0. 32；③没有出现在关联规则中的雾计算结点，对应的位置值为-1，F3未出现在t2中。

3.3.5 ITPS算法调度利用ITPS算法进行任务调度，以表1～2和任务调用关系作为输入，输出任务集任务调度跨度makespan以及平均等待时间AWT。

以任务集｛t0，t1，t2，t7｝作为调度对象，由于任务t1最早到达，所以先对任务t1进行调度，选择最早完成时间最小的雾计算结点F2进行调度；接下来选择任务t0和t2，由于t0，t2任务同时到达，且任务t2出现在关联关系R中，因此任务t2被优先调度，然后选择最早完成时间最小的雾计算结点F0进行调度；任务集中还有任务t0和t7未被调度，由于任务t0早于任务t7到达，因此选择任务t0在F1上调度；最后再将任务t7调度到F3，得到任务集｛t0，t1，t2，t7｝与雾计算结点集｛F0，F1，F2，F3｝的调度关系如图4所示。

图4 任务与雾计算结点之间调度关系图Fig. 4 Scheduling relationship between tasks and fog computing nodes

4 模拟结果与结果分析

为了验证ITPS算法的性能和效率，搭建基于SimGrid［22-24］模拟器工具包的仿真实验环境。实验环境中雾计算结点间通过高速网络连接，雾计算结点的计算性能异构，雾计算结点进行任务调度的同时也可以与其他雾计算结点进行通信，独立流水线任务分配到雾计算结点上执行直到任务执行完成。

实验中使用的计算机配置：Intel Core（TM）i5-8265U 1. 6 GHz CPU、4 GB 内存硬件环境、Ubuntu12操作系统以及SimGrid3. 11工具包，在相同实验条件对ITPS算法以及wLC和wRR算法进行性能比较。

4.1 测试数据集

为测试各种算法的性能，需要给定任务调度算法的测试数据集，包括任务集、雾结点集、任务执行开销矩阵、事务集以及调度关系等。任务测试集中的任务数从50开始，每次递增50个任务，最大到1 000个任务，任务集中的任务与任务编号通过随机程序生成，任务集中每个任务的到达时间通过随机程序生成；雾结点测试数据集包括4个性能异构的结点；任务集在雾结点集上的执行开销通过随机程序生成；调度关系由I-Apriori算法根据初始事务集D得到；初始事务测试集由500个随机生成的事务构成。

4.2 实验结果分析

利用测试数据集，分别执行ITPS、wLC 以及wRR 任务调度算法，对不同任务数及不同任务到达时间对任务集进行调度，任务到达时间区间为［0，50］的调度情况，以及任务到达时间区间为［0，100］的调度情况图5所示。

图5 不同任务数性能对比Fig. 5 Performance comparison of different tasks

通过上述实验可以得到，ITPS 算法在不同任务数以及不同任务到达时间条件下，任务调度跨度和平均等待时间均比wLC 和wRR 算法要短，而wRR 算法的性能总体上要优于wLC 算法。ITPS算法相比wLC 算法的任务调度跨度缩短2. 48%～10. 62%，平均等待时间AWT 值缩短14. 97%～49. 79%，任务越晚到达，IPTS 的性能更优；ITPS 算法相比wRR 算法的任务调度跨度缩短2. 19%～11. 78%，平均等待时间AWT 值缩短4. 55%～20. 53%，任务越早到达，IPTS 的性能更佳，总体上ITPS 算法要优于wLC 和wRR 两种任务调度算法。

5 结 语

通过对经典Apriori算法的改进，提出一种雾计算环境中任务的分类I-Apriori算法，I-Apriori算法提升了分类挖掘的效率和性能；利用I-Apriori 算法，面向雾计算环境下的任务调度问题，建立雾计算任务调度模型，并提出ITPS任务调度算法。ITPS算法在makespan及AWT具有更好的性能。