一种基于聚类云转码动态任务调度方法

1.本发明属于云计算资源调度和多媒体内容处理技术领域，尤其涉及一种基于聚类云转码动态任务调度方法。


背景技术：

2.随着新媒体和互联网技术的高速发展，加快了视频行业的发展，也推动了短视频行业和直播行业的发展模式，越来越多的行业选择以视频为载体进行信息的传播，用户可以选择视频平台进行视频的创作，借助互联网进行传播，供其他的用户观看；选择直播实时性视频播放的方式，进行文化内容的创作供用户观看，随着科学技术的发展，观看平台、文件格式和视频流技术的增加产生了对视频转码的需求，视频服务行业在提供视频服务进行视频编解码时，这对算力提出了很高的需求。
3.基于云计算的云转码可以用于克服本地视频转码的局限性，云转码的解决方案的资源几乎是无限的，视频服务提供商可以随时随地付费获取他们业务所需的算力，以更低的成本处理不可预测的需求，云转码平台可以为视频服务提供商提供很强的并行运算的能力，大大缩短业务完成的时间，提高视频服务提供商的服务质量，将视频转码所需的资源部署在云计算平台上，搭建云转码平台，是近几年视频行业的主流趋势。
4.在云转码平台中，会将视频流作业切割成云转码任务，分配在部署在云转码平台的虚拟机上完成转码，不同类型的虚拟机在处理不同类型的云转码任务时，工作效率是有明显差异的，转码任务具有不同的处理时间，目前在主流云计算平台，对于转码任务调度方法并没有充分利用不同任务和虚拟机之间的差异性，且这些调度方法很难做出动态的调整，导致云转码平台存在资源利用率低、负载不均衡、视频转码任务完成时间长和运行成本高的问题。


技术实现要素：

5.本发明的目的在于：为了解决云转码平台存在资源利用率低、负载不均衡、视频转码任务完成时间长和运行成本高的问题，而提出的一种基于聚类云转码动态任务调度方法。
6.为了实现上述目的，本发明采用了如下技术方案：一种基于聚类云转码动态任务调度方法，具体包括以下步骤：s1、建立任务模型，获得转码视频后，生成云转码任务；s2、建立任务和虚拟机模型，建立将服务器的计算资源分成若干处理云转码任务的虚拟机；s3、数据标准化及归一化，将虚拟机数据标准化及归一化处理后，将虚拟机模型属性映射成聚类空间的维度；s4、利用模糊均值聚类算法fcm对虚拟机进行分类得到若干聚类中心；s5、任务集合分类，利用虚拟机分类中得到的多个虚拟机聚类中心对任务集合进
行分类；s6、分类后云转码和虚拟机集群的动态调度，用贪心策略对任务类与虚拟机类之间完成类与类的初始化调度方案；s7、执行动态任务调度方案，云转码动态任务调度结束后，更新虚拟机队列，虚拟机集群根据虚拟机队列，完成对云转码任务的转码需求。
7.作为上述技术方案的进一步描述：所述建立任务和模拟机模型的方法包括：用户上传或者请求播放视频后，在云转码平台提交视频转码作业，视频转码作业会被切割成很多大小不一的视频流，每个视频流生成若干个云转码任务。
8.假设有n个云转码任务，可以表示为，task称为任务集合；任务集合中任务集合中，其中表示任务的编号，表示任务的长度，表示任务所需的带宽，表示任务所需的计算量，表示任务所需的内存；其中、和分别代表着任务所需的资源量；建立虚拟机模型，如下：视频服务提供商将服务器数据中心的计算资源分成若干个不同的虚拟机，且每个虚拟机可以处理多个云转码任务；假设有m个虚拟机，可以表示为，vm称为虚拟机集合；虚拟机集合中虚拟机集合中，其中表示虚拟机的编号，表示虚拟机的带宽，表示虚拟机的计算能力，表示虚拟机的存储能力；其中，、和分别代表着虚拟机所能提供的性能。
9.作为上述技术方案的进一步描述：所述虚拟机数据标准化及归一化处理的方法包括：在聚类空间中，初始化一个三维的空间，将虚拟机模型属性映射成聚类空间的维度，其中三个维度分别为、和；将m个虚拟机的参数转换成三维空间的坐标，就有m个样本分布；在该空间中利用fcm算法实现对m个样本的分类，由于vm的各项参数单位并不统一，需要将参数进行标准化及归一化处理；建立一个虚拟机的样本矩阵，为样本矩阵的一个元素，表示第i个元素，第j个维度，；标准化公式：
式中为所有样本在维度j上的平均值，为所有样本在维度j上的标准差；归一化公式：式中和分别为标准化后，所有样本中第j维的最大值和最小值；将标准化及归一化后的虚拟机参数，重新分布在一个标准的三维空间，且每个维度的取值范围[0，1]；将m个虚拟机按照构建好的模型，将虚拟机按规划分为3类，分别是计算型虚拟机类、带宽型虚拟机类和存储型虚拟机类。
[0010]
作为上述技术方案的进一步描述：所述s4中利用fcm算法将样本精确分类到确定类别的具体实现步骤如下：fcm算法模型：虚拟机数据集中有m个样本，样本集x是由m个标准化及归一化的虚拟机组成，，为第j个样本数据，3维向量，分别是，，；簇心，为第i个类的中心坐标，也是3维向量；每一个样本属于某一类簇的隶属度或者概率为,可以构成一个3*m的隶属度矩阵u；根据以下确定算法的目标函数（3）和约束条件（4）如下所示，隶属度满足的约束公式（4）；目标函数j值越小表示算法的分类更准确，用来度量第ｊ个样本与第ｉ个簇心点之间的距离，采用的是欧式距离，m为加权指数；初始化及聚类更新：随机初始化隶属度矩阵u，满足公式（4）；初始化加权指数m，最大迭代次数t=max，迭代停止阈值；隶属度更新公式：聚类中心更新公式：fcm算法迭代结束，得到最优隶属度矩阵u，及3个虚拟机类的聚类中心；在隶属度矩阵u的列矩阵找最大值元素；
若为，表示虚拟机属于类，其中分别为计算型、带宽型和存储型虚拟机类。
[0011]
作为上述技术方案的进一步描述：任务集合分类包括在fcm聚类算法对虚拟机集合进行分类后，得到3个虚拟机类的聚类中心，利用聚类中心对任务集合进行分类，分为4类，分别为普通型、计算型、带宽型和存储型任务类；具体步骤如下：任务聚类模型：任务t的向量由，，组成，构成三维向量坐标，采用对虚拟机的处理方式，对任务t进行处理；按照公式（1）和（2），分别对任务t进行标准化及归一化处理，得到任务，；i,j表示第i个任务的第j个维度；任务分类：计算3个虚拟机聚类中心两两之间的距离，采用欧式距离，公式如下：计算任务与各虚拟机聚类中心的欧式距离表示任务与聚类中心的距离；若任务距各聚类中心的最小欧式距离为，与其他两个聚类中心的平均欧式距离为；比较与的大小，根据结果将任务划分到具体任务类中，具体如下：划分到具体任务类中，具体如下：表示任务属于类，分别是分别为计算型、带宽型、存储型和普通型任务类。
[0012]
作为上述技术方案的进一步描述：所述s6中用贪心策略对任务类与虚拟机类之间完成类与类的初始化调度方案的步骤包括：当进行计算型的任务类和虚拟机类处理时，类中的每个任务完成所需的总资源和每个虚拟机所能提供的总资源；计算公式如下：式中是经过标准化和归一化处理，分别是第k类的任务数量和虚拟机数量；
将任务类中所有的任务按照从大到小进行排列，排列组成任务队列tasklist_k；将虚拟机类中所有的虚拟机按照从小到大进行排列，排列组成虚拟机队列vmlist_k；将tasklist_k中的任务依次循环分配到vmlist_k中的虚拟机上，例，，表示第k类中第j个虚拟机上分配了3个任务，为第k类第a个任务，其中任务所需的资源是从大到小的，。
[0013]
作为上述技术方案的进一步描述：所述带宽型和存储型任务与虚拟机类采用相同的初始化调度方案。
[0014]
作为上述技术方案的进一步描述：所述s7中执行动态任务调度方案包括普通任务类和虚拟机类的动态调度方法包括：计算每个类中虚拟机的运行时间，为第k类的第i个任务完成所花费的时间，为第k类的第j个虚拟机处理完分配在该虚拟机上所有任务所花时间，a为分配在虚拟机上任务的数量；公式如下：将分配在虚拟机上的所有任务，根据任务处理完成时间的值从大到小排序；将虚拟机队列vmlist_k上的虚拟机按照每个虚拟机的运行时间从小到大排序，更新vmlist_k；计算虚拟机队列vmlist_k的总运行时间，是第k虚拟机类的虚拟机数量，公式如下：其中总运行时间最大的虚拟机类为，最小的虚拟机类为；根据任务调度模型，确定相关参数，迭代次数，最大迭代次数，停止迭代阈值，普通调度与动态调度的迭代边界；，执行普通任务类动态调度；，执行虚拟机类的动态调度；进行普通任务类动态调度时，普通任务类的任务队列为，按照公式（9）的进行从大到小进行排列，每次调度从队列中由前到后选取特定数量的任务
分配到某虚拟机队列进行处理，待处理任务队列为，待处理的任务数量；将队列的任务分配在的虚拟机类上，即队列；取，依次选取中最大的任务，且任务序号从小到大，分配在队列中有最短运行时间的虚拟机上，直到，更新；重新选取队列中第2大的任务进行分配，虚拟机序号从小到大，直到队列中所有任务分配完成；分配完成，更新虚拟机队列和tasklist_4待处理任务队列，等待下次普通任务类调度；在虚拟机类的动态调度时，选取类中队列运行时间的虚拟机，组成动态虚拟机队列，虚拟机按照由小到大排列；依次选择队列中最大的虚拟机序号从大到小，将该虚拟机上多余的任务重新分配到类，队列上的虚拟机，依次选取中最小的虚拟机序号从小到大；依次选择上最小的任务序号从大到小重新分配到；当选择的虚拟机的，则选取队列中下一个虚拟机替换，若中所有的虚拟机都被选取，更新所有的，等待下次动态调度；当选择的虚拟机的，则选取队列中上一个虚拟机替换，若中的所有虚拟机都被选取，更新所有的，等待下次动态调度。
[0015]
完成任务类或虚拟机类的动态调度后，若》,动态任务调度完成，否则继续调度。
[0016]
综上所述，由于采用了上述技术方案，本发明的有益效果是：1、本发明中，本发明通过对云转码平台上的任务及虚拟机建立数学建模，对其数据标准化和归一化，利用fcm聚类算法对虚拟机进行分类，利用欧氏距离对任务进行分类，利用贪心策略初始化一个较好的调度方案，采用特定的算法完成普通任务类及虚拟机类的动态调度。
[0017]
2、本发明中，充分利用任务与虚拟机之间的特异性，并且结合动态的调度算法，在满足服务质量的情况下，缩短整个视频转码作业的完成时间，节省服务提供商的运行成本，提高资源的利用率，实现负载均衡。
附图说明
[0018]
图1是本发明方法的任务与虚拟机分类调度框架。
[0019]
图2是本发明中聚类虚拟机及任务的动态调度算法流程图。
具体实施方式
[0020]
下面将结合本发明实施例中，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。
[0021]
本发明提出的一种面向转码云平台的多任务调度方法，结合图1的任务与虚拟机分类调度框架和图2的聚类虚拟机及任务的动态调度算法流程图所示，包括以下步骤：在用户上传视频作业时，云转码平台利用视频分割器将其转化成可利用虚拟机进行独立转码的任务，将这些若干个云转码任务task放入任务队列；同时云转码平台会将部署在其上的服务器资源细化成vm虚拟机集群，将其加入虚拟机队列vm；所述转码系统是云端服务器上为进行视频转码搭建的服务系统，包括云计算的硬件资源和相对应的软件系统。
[0022]
建立任务和虚拟机模型假设有n个云转码任务，表示为，task称为任务集合，任务集合中中，其中表示任务的编号，表示任务的长度，表示任务所需的带宽，表示任务所需的计算量，表示任务所需的内存，其中，，分别代表着任务所需的资源量。
[0023]
假设有m个虚拟机，可以表示为，vm称为虚拟机集合，虚拟机集合中虚拟机集合中，其中表示虚拟机的编号，表示虚拟机的带宽，表示虚拟机的计算能力，表示虚拟机的存储能力，其中，，分别代表着虚拟机所能提供的性能；数据标准化及归一化将虚拟机模型，选择其中三个维度分别为，，，为样本矩阵的一个元素，表示第i个元素，第j个维度，；标准化公式：式中为所有样本在维度j上的平均值，为所有样本在维度j上的标准差；归一化公式：
式中，分别为标准化后，所有样本中第j维的最大值和最小值；的每个维度取值范围为[0,1]；任务模型同理，进行标准化及归一化处理；虚拟机分类将进行了标准化和归一化处理的虚拟机队列vm，进行分类处理，根据模糊c均值算法的目标函数（3）和约束条件（4）进行分类，算法中的隶属度满足的约束公式（4）目标函数j值越小表示算法的分类更准确，用来度量第ｊ个样本与第ｉ个簇心点之间的距离，采用的是欧式距离，m为加权指数；算法进行迭代更新分类：随机初始化隶属度矩阵u，满足公式（4）；初始化加权指数m，最大迭代次数t=max，迭代停止阈值；隶属度更新公式：聚类中心更新公式：fcm算法迭代结束，得到最优隶属度矩阵u，及3个虚拟机类的聚类中心，在隶属度矩阵u的列矩阵找最大值元素；若为，表示虚拟机属于类；其中分别为计算型、带宽型和存储型虚拟机类。
[0024]
任务集合分类利用虚拟机分类中得到的三个虚拟机聚类中心对任务集合进行分类，分为4类，分别为普通型、计算型、带宽型、存储型任务类；具体步骤如下：任务聚类模型：任务t的向量由，，组成，构成三维向量坐标，采用对虚拟机的处理方式，对任务t进行处理；按照公式（1）和（2），分别对任务t进行标准化及归一化处理，得到任务，；i,j表示第i个任务的第j个维度；任务分类：计算3个虚拟机聚类中心两两之间的距离，采用欧式距离，公式如下：
计算任务与各虚拟机聚类中心的欧式距离表示任务与聚类中心的距离；若任务距各聚类中心的最小欧式距离为，与其他两个聚类中心的平均欧式距离为，比较与的大小，根据结果将任务划分到具体任务类中，具体如下：划分到具体任务类中，具体如下：表示任务属于类，分别是分别为计算型、带宽型、存储型和普通型任务类；以上步骤将云转码平台中的转码任务和虚拟机集群分类完成，以下将进行云转码和虚拟机集群之间的动态调度；分类后云转码和虚拟机集群的动态调度用贪心策略初始化任务调度方案：以计算型的任务类和虚拟机类为例，类中的每个任务完成所需的总资源和每个虚拟机所能提供的总资源；计算公式如下，式中是经过标准化和归一化处理，分别是第k类的任务数量和虚拟机数量：将任务类中所有的任务按照从大到小进行排列，排列组成任务队列tasklist_k；将虚拟机类中所有的虚拟机按照从小到大进行排列，排列组成虚拟机队列vmlist_k，将tasklist_k中的任务依次循环分配到vmlist_k中的虚拟机上；例，，表示第k类中第j个虚拟机上分配了3个任务，为第k类第a个任务，其中任务所需的资源是从大到小的，；带宽型、存储型任务与虚拟机类采用一样的初始化调度方案；计算每个类中虚拟机的运行时间，为第k类的第i个任务完成所花费的时间，为第k类的第j个虚拟机处理完分配在该虚拟机上所有任务所花时间，a为分配在虚拟机上任务的数量；公式如下：将分配在虚拟机上的所有任务，根据任务处理完成时间的值从大到小排序；将虚拟机队列vmlist_k上的虚拟机按照每个虚拟机的运行时间从小
到大排序，更新vmlist_k。
[0025]
计算虚拟机队列vmlist_k的总运行时间，是第k虚拟机类的虚拟机数量，公式如下。
[0026]
其中总运行时间最大的虚拟机类为，最小的虚拟机类为；根据任务调度模型，确定相关参数，迭代次数，最大迭代次数，停止迭代阈值，普通调度与动态调度的迭代边界；进行任务调度，步骤如下： ，执行第四类的普通任务类动态调度：普通任务类的任务队列为，按照公式（9）的进行从大到小进行排列；在进行普通任务类调度时，每次调度从队列中由前到后选取特定数量的任务分配到某虚拟机队列进行处理，待处理任务队列为，待处理的任务数量；将队列的任务分配在的虚拟机类上，即队列；取，依次选取中最大的任务（任务序号从小到大），分配在队列中有最短运行时间的虚拟机上，直到，更新，重新选取队列中第2大的任务进行分配（虚拟机序号从小到大），直到队列中所有任务分配完成；分配完成，更新虚拟机队列和tasklist_4待处理任务队列，等待下次普通任务类调度；，执行虚拟机类的动态调度：选取类中队列运行时间的虚拟机，组成动态虚拟机队列，虚拟机按照由小到大排列；依次选择队列中最大的虚拟机（序号从大到小），将该虚拟机上多余的任务重新分配到类，队列上的虚拟机，依次选取中最小的虚拟机（序号从小到大），依次选择上最小的任务（序号从大到小）重新分配到；当选择的虚拟机的，则选取队列中下一个虚拟机替换，若中所有的虚拟机都被选取，更新所有的，等待下次动态调度；当选择的虚拟机的，则选取队列中上一个虚拟机替换，若中的所有虚拟机都被选取，更新所
有的，等待下次动态调度。
[0027]
，若《,重复上述步骤，否则任务调度完成；执行动态任务调度方案云转码动态任务调度结束后，更新虚拟机队列，虚拟机集群根据虚拟机队列，完成对云转码任务的转码需求。
[0028]
以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。

技术特征：
1.一种基于聚类云转码动态任务调度方法，其特征在于，具体包括以下步骤：s1、建立任务模型，获得转码视频后，生成云转码任务；s2、建立任务和虚拟机模型，建立将服务器的计算资源分成若干处理云转码任务的虚拟机；s3、数据标准化及归一化，将虚拟机数据标准化及归一化处理后，将虚拟机模型属性映射成聚类空间的维度；s4、利用模糊均值聚类算法fcm对虚拟机进行分类得到若干聚类中心；s5、任务集合分类，利用虚拟机分类中得到的多个虚拟机聚类中心对任务集合进行分类；s6、分类后云转码和虚拟机集群的动态调度，用贪心策略对任务类与虚拟机类之间完成类与类的初始化调度方案；s7、执行动态任务调度方案，云转码动态任务调度结束后，更新虚拟机队列，虚拟机集群根据虚拟机队列，完成对云转码任务的转码需求。2.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述建立任务和模拟机模型的方法包括：用户上传或者请求播放视频后，在云转码平台提交视频转码作业，视频转码作业会被切割成很多大小不一的视频流，每个视频流生成若干个云转码任务；假设有n个云转码任务，可以表示为，task称为任务集合；任务集合中任务集合中，其中表示任务的编号，表示任务的长度，表示任务所需的带宽，表示任务所需的计算量，表示任务所需的内存；其中、和分别代表着任务所需的资源量；建立虚拟机模型，如下：视频服务提供商将服务器数据中心的计算资源分成若干个不同的虚拟机，且每个虚拟机可以处理多个云转码任务；假设有m个虚拟机，可以表示为，vm称为虚拟机集合；虚拟机集合中虚拟机集合中，其中表示虚拟机的编号，表示虚拟机的带宽，表示虚拟机的计算能力，表示虚拟机的存储能力；其中，、和分别代表着虚拟机所能提供的性能。3.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述虚拟机数据标准化及归一化处理的方法包括：在聚类空间中，初始化一个三维的空间，将虚拟机模型属性映射成聚类空间的维度，其中三个维度分别为、和；将m个虚拟机的参数转换成三维空间的坐标，就有m个样本分布；在该空间中利用fcm算法实现对m个样本的分类，由于vm的各项参数单位并不统一，需要将参数进行标准化及归一化处理；
建立一个虚拟机的样本矩阵，为样本矩阵的一个元素，表示第i个元素，第j个维度，；标准化公式：式中为所有样本在维度j上的平均值，为所有样本在维度j上的标准差；归一化公式：式中和分别为标准化后，所有样本中第j维的最大值和最小值；将标准化及归一化后的虚拟机参数，重新分布在一个标准的三维空间，且每个维度的取值范围[0，1]；将m个虚拟机按照构建好的模型，将虚拟机按规划分为3类，分别是计算型虚拟机类、带宽型虚拟机类和存储型虚拟机类。4.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述s4中利用fcm算法将样本精确分类到确定类别的具体实现步骤如下：fcm算法模型：虚拟机数据集中有m个样本，样本集x是由m个标准化及归一化的虚拟机组成，，为第j个样本数据，3维向量，分别是，，；簇心，为第i个类的中心坐标，也是3维向量；每一个样本属于某一类簇的隶属度或者概率为,可以构成一个3*m的隶属度矩阵u；根据以下确定算法的目标函数（3）和约束条件（4）如下所示，隶属度满足的约束公式（4）；目标函数j值越小表示算法的分类更准确，用来度量第ｊ个样本与第ｉ个簇心点之间的距离，采用的是欧式距离，m为加权指数；初始化及聚类更新：随机初始化隶属度矩阵u，满足公式（4）；初始化加权指数m，最大迭代次数t=max，迭代停止阈值；隶属度更新公式：
聚类中心更新公式：fcm算法迭代结束，得到最优隶属度矩阵u，及3个虚拟机类的聚类中心；在隶属度矩阵u的列矩阵找最大值元素；若为，表示虚拟机属于类，其中分别为计算型、带宽型和存储型虚拟机类。5.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，任务集合分类包括在fcm聚类算法对虚拟机集合进行分类后，得到3个虚拟机类的聚类中心，利用聚类中心对任务集合进行分类，分为4类，分别为普通型、计算型、带宽型和存储型任务类；具体步骤如下：任务聚类模型：任务t的向量由，，组成，构成三维向量坐标，采用对虚拟机的处理方式，对任务t进行处理；按照公式（1）和（2），分别对任务t进行标准化及归一化处理，得到任务，；i,j表示第i个任务的第j个维度；任务分类：计算3个虚拟机聚类中心两两之间的距离，采用欧式距离，公式如下：计算任务与各虚拟机聚类中心的欧式距离表示任务与聚类中心的距离；若任务距各聚类中心的最小欧式距离为，与其他两个聚类中心的平均欧式距离为；比较与的大小，根据结果将任务划分到具体任务类中，具体如下：划分到具体任务类中，具体如下：表示任务属于类，分别是分别为计算型、带宽型、存储型和普通型任务类。6.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述s6中用贪心策略对任务类与虚拟机类之间完成类与类的初始化调度方案的步骤包括：当进行计算型的任务类和虚拟机类处理时，类中的每个任务完成所需的总资源和每个虚拟机所能提供的总资源；计算公式如下：
式中是经过标准化和归一化处理，分别是第k类的任务数量和虚拟机数量；将任务类中所有的任务按照从大到小进行排列，排列组成任务队列tasklist_k；将虚拟机类中所有的虚拟机按照从小到大进行排列，排列组成虚拟机队列vmlist_k；将tasklist_k中的任务依次循环分配到vmlist_k中的虚拟机上，，表示第k类中第j个虚拟机上分配了3个任务，为第k类第a个任务，其中任务所需的资源是从大到小的，。7.根据权利要求6所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述带宽型和存储型任务与虚拟机类采用相同的初始化调度方案。8.根据权利要求1所述的一种基于聚类云转码动态任务调度方法，其特征在于，所述s7中执行动态任务调度方案包括普通任务类和虚拟机类的动态调度方法包括：计算每个类中虚拟机的运行时间，为第k类的第i个任务完成所花费的时间，为第k类的第j个虚拟机处理完分配在该虚拟机上所有任务所花时间，a为分配在虚拟机上任务的数量；公式如下：将分配在虚拟机上的所有任务，根据任务处理完成时间的值从大到小排序；将虚拟机队列vmlist_k上的虚拟机按照每个虚拟机的运行时间从小到大排序，更新vmlist_k；计算虚拟机队列vmlist_k的总运行时间，是第k虚拟机类的虚拟机数量，公式如下：其中总运行时间最大的虚拟机类为，最小的虚拟机类为；根据任务调度模型，确定相关参数，迭代次数，最大迭代次数，停止迭代阈值，普通调度与动态调度的迭代边界；，执行普通任务类动态调度；，执行虚拟机类的
动态调度；进行普通任务类动态调度时，普通任务类的任务队列为，按照公式（9）的进行从大到小进行排列，每次调度从队列中由前到后选取特定数量的任务分配到某虚拟机队列进行处理，待处理任务队列为，待处理的任务数量；将队列的任务分配在的虚拟机类上，即队列；取，依次选取中最大的任务，且任务序号从小到大，分配在队列中有最短运行时间的虚拟机上，直到，更新；重新选取队列中第2大的任务进行分配，虚拟机序号从小到大，直到队列中所有任务分配完成；分配完成，更新虚拟机队列和tasklist_4待处理任务队列，等待下次普通任务类调度；在虚拟机类的动态调度时，选取类中队列运行时间的虚拟机，组成动态虚拟机队列，虚拟机按照由小到大排列；依次选择队列中最大的虚拟机序号从大到小，将该虚拟机上多余的任务重新分配到类，队列上的虚拟机，依次选取中最小的虚拟机序号从小到大；依次选择上最小的任务序号从大到小重新分配到；当选择的虚拟机的，则选取队列中下一个虚拟机替换，若中所有的虚拟机都被选取，更新所有的，等待下次动态调度；当选择的虚拟机的，则选取队列中上一个虚拟机替换，若中的所有虚拟机都被选取，更新所有的，等待下次动态调度；完成任务类或虚拟机类的动态调度后，若>,动态任务调度完成，否则继续调度。

技术总结
本发明公开了一种基于聚类云转码动态任务调度方法，属于云计算资源调度和多媒体内容处理技术领域，S1：构建任务Task和虚拟机VM模型；S2：虚拟机数据标准化及归一化处理；S3：模糊均值聚类算法FCM对虚拟机分类；S4：任务集合分类；S5：贪心策略初始化调度方案；S6：普通任务类和虚拟机类的动态调度。本发明中，本发明通过对云转码平台上的任务及虚拟机建立数学建模，对其数据标准化和归一化，利用FCM聚类算法对虚拟机进行分类，利用欧氏距离对任务进行分类，利用贪心策略初始化一个较好的调度方案，采用特定的算法完成普通任务类及虚拟机类的动态调度。的动态调度。的动态调度。


技术研发人员：洪广杰 蔡茂国 詹楷杰 欧基发
受保护的技术使用者：深圳大学
技术研发日：2023.01.10
技术公布日：2023/9/25