基于动态目标策略的云计算资源调度优化方法及应用

技术领域

本发明涉及云计算资源调度技术领域，具体涉及基于动态目标策略的云计算资源调度优化方法及应用。

背景技术

美国国家标准与技术研究院(NIST)对云计算的定义是：云计算是一种按使用量付费的模式，这种模式提供可用的、便捷的、按需的网络访问，进入可配置的计算资源共享池(资源包括网络、服务器、存储、应用软件和服务)，这些资源能够被快速提供，只需投入很少的管理工作，或与服务供应商进行很少的交互。

在“大数据时代”来临之际，云计算所要面临的问题一般都具有相当大规模的数据量，所以资源的调度至关重要，它关系着云计算的成本和效率。已被证明云计算资源调度是一个有很多限制的NP难问题，几乎不可能在多项式时间内得到最优解，只能找出一个接近最优的解。随着智能计算方法的发展，研究和探索利用智能计算方法求解云计算资源调度问题上已经引起了广泛的关注。虽然云资源调度问题已经被广泛研究，但是还是无法很好的满足用户的服务质量(Quality of Service,QoS)，而且没有很好的考虑到云计算资源的特点—弹性(elasticity)和非均质性(heterogeneity)。另一方面，很多研究者把目光都集中在最小化任务的运行时间这个一般衡量效果的标准上，却很少考虑到任务执行的成本。而在任何的商业行为中，成本绝对是不可忽视的因素之一。追求最快的完成任务往往需要较大的投入，而导致整体效益降低。需要平衡成本和时间的关系，达到经济效益的最大化。

Rodriguez和Buyya在2014年的IEEE TRANSACTIONS ON CLOUD COMPUTING提出了一种基于截止时间最小化运行成本的模型，并提出用粒子群算法(Particle SwarmOptimization,PSO)来解决这个问题。但在粒子群算法中粒子中某一维向最佳的粒子学习的过程中，资源编号的倾向学习不一定能很好的导向更好的结果，并且会导致收敛快但很容易早熟收敛。

发明内容

为了克服现有技术存在的缺陷与不足，本发明提供一种基于动态目标策略的云计算资源调度优化方法，在相同截止时间约束下可以得到成本更低的调度方案，在较小截止时间的约束下仍然可以得到可行的调度方案。

本发明的第二目的在提供一种基于动态目标策略的云计算资源调度优化系统。

本发明的第三目的在于提供一种存储介质。

本发明的第四目的在于提供一种计算设备。

为了达到上述目的，本发明采用以下技术方案：

一种基于动态目标策略的云计算资源调度优化方法，包括下述步骤：

初始化种群：对种群中的每一个染色体，随机生成一个资源调度序列；

适应值评估：采用任务流执行成本的倒数评价适应值；

动态目标策略：若第一代初始化时没有满足最终截止时间需求的可行解，则将任务流执行时间作为优化目标，将任务流执行时间倒数评价染色体的适应值，每次迭代选择TET更小而适应值更高的染色体，直至种群中出现染色体得出的解满足最终截止时间需求，再重新采用任务流执行成本的倒数评价适应值；

选择算子：根据染色体的适应值，通过轮盘赌选择进入下一代的染色体个体；

染色体的交叉和变异：每个染色体都设有一个交叉概率和一个变异概率，对每个资源调度序列生成一个随机数，若随机数小于交叉概率，则选择该资源调度序列作为交叉的父本之一；

对每个资源调度序列的每个任务，生成一个随机数，若随机数小于变异概率，则该任务所占资源编号发生变异；

最优个体保留策略：每一代中，若当代中有染色体的适应值高于当前最优染色体，则将当代中所述染色体作为新的最优染色体；否则，采用当前最优染色体个体替换掉当代中适应值最小的染色体；

当找到一个可行解后，执行到指定代数后无法找到可行解的时，输出产生的最优染色体的解。

作为优选的技术方案，所述对种群中的每一个染色体，随机生成一个资源调度序列，具体步骤包括：

采用资源和任务的编号表示相应的资源和任务，每一个染色体第i位基因表示任务t

作为优选的技术方案，所述通过轮盘赌选择进入下一代的染色体个体，资源调度序列被选择的概率为：

fitness

其中，TEC表示任务流执行成本，fitness

作为优选的技术方案，所述染色体的交叉和变异的步骤中，每当选择到2个染色体时，生成一个随机数n∈[1,N-1],n∈Z，对应交换两个资源调度序列的前n个任务的资源编号。

为了到达上述第二目的，本发明采用以下技术方案：

一种基于动态目标策略的云计算资源调度优化系统，包括：种群初始化模块、适应值评估模块、动态目标策略构建模块、选择算子模块、染色体交叉和变异模块、最优个体保留策略构建模块和输出模块；

所述种群初始化模块用于初始化种群，对种群中的每一个染色体，随机生成一个资源调度序列；

所述适应值评估模块用于采用任务流执行成本的倒数评价适应值；

所述动态目标策略构建模块用于构建动态目标策略，具体为：若第一代初始化时没有满足最终截止时间需求的可行解，则将任务流执行时间作为优化目标，将任务流执行时间倒数评价染色体的适应值，每次迭代选择TET更小而适应值更高的染色体，直至种群中出现染色体得出的解满足最终截止时间需求，再重新采用任务流执行成本的倒数评价适应值；

所述选择算子模块用于根据染色体的适应值，通过轮盘赌选择进入下一代的染色体个体；

所述染色体交叉和变异模块用于完成染色体的交叉和变异，每个染色体都设有一个交叉概率和一个变异概率，对每个资源调度序列生成一个随机数，若随机数小于交叉概率，则选择该资源调度序列作为交叉的父本之一；

对每个资源调度序列的每个任务，生成一个随机数，若随机数小于变异概率，则该任务所占资源编号发生变异；

所述最优个体保留策略构建模块用于构建最优个体保留策略，具体为：每一代中，若当代中有染色体的适应值高于当前最优染色体，则将当代中所述染色体作为新的最优染色体；否则，采用当前最优染色体个体替换掉当代中适应值最小的染色体；

所述输出模块用于输出最优解，在找到一个可行解后，执行到指定代数后无法找到可行解的时，输出产生的最优染色体的解。

为了到达上述第三目的，本发明采用以下技术方案：

一种存储介质，存储有程序，所述程序被处理器执行时实现上述基于动态目标策略的云计算资源调度优化方法。

为了到达上述第四目的，本发明采用以下技术方案：

一种计算设备，包括处理器和用于存储处理器可执行程序的存储器，所述处理器执行存储器存储的程序时，实现上述基于动态目标策略的云计算资源调度优化方法。

本发明与现有技术相比，具有如下优点和有益效果：

(1)现有的粒子群算法中粒子中某一维向最佳的粒子学习的过程中，资源编号的倾向学习不一定能很好的导向更好的结果，并且会导致收敛快但很容易早熟收敛，本发明提出用遗传算法来解决这个问题，因为在遗传算法中的交叉变异过程并不会涉及类似的学习过程，所以降低了算法搜索的盲目性，以及遗传算法能避免早熟收敛的问题。

(2)由于遗传算法不适用于有约束条件的优化目标，所以本发明提出了动态目标策略，当在以基于截止时间约束最小化成本作为优化目标的情况下没有得到可行的调度方案(即超过截止时间)，就用任务完成时间作为优化目标直到算法找到可行的调度方案再重新将基于截止时间约束最小化成本作为优化目标，这个策略使算法的适用性更强，在较小截止时间约束下仍能找到可行解。

附图说明

图1为本发明云计算任务流实例示意图；

图2为本发明运行时间及数据转移时间矩阵实例示意图；

图3为本发明云计算任务流调度方案示意图；

图4为本发明遗传算法中交叉的示意图；

图5为本发明遗传算法中变异的示意图；

图6为本发明基于动态目标策略的云计算资源调度优化方法的流程示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

实施例

用户有一系列的任务需要执行，而云计算平台提供一系列可供用户按需租赁的运行资源(虚拟机)，所以如何分配任务到相对应的资源上运行就形成了一个资源调度问题。如图1所示，从图中可以看到一个任务组中有许多的任务，而这些任务之间存在一个拓扑结构，即任务之间有着父子关系。其中每条边上的值代表着数据的传输时间，即当父子任务不在同一个资源上运行时，父任务要将一些子任务运行需要的数据传输给子任务所需的时间。此外各个任务在各个资源执行所需的时间也是已知的。为了编程实现，本实施例采用编号来表示任务和资源，定义exetime和transfertime两个矩阵，其中表示任务t

在本实施例中，要优化的目标模型是基于截止时间最小化执行成本，其数学表达式如(1)和(2)所示，其中TEC和TET分别表示任务完成的成本和任务完成所需的时间。

Minimize TEC (1)

TET

TEC和TET的计算方法由(3)和(4)所示，其中对每一个资源r

最后定义一个调度方案，以一个调度序列pos[|T|]表示，pos[i]的值代表任务t

对每一个任务t

如图4所示，本实施例提供一种基于动态目标策略的云计算资源调度优化方法，包括以下步骤：

(1)初始化种群

对种群中的每一个染色体，随机初始化生成一个资源调度序列；按照遗传算法的种群定义，种群中的每一个染色体对应问题的一个解，所以每一个染色体就对应每一个调度方案，即一个调度序列。本实施例用资源和任务的编号来代表相应的资源和任务，每一个染色体第i位基因表示任务t

(2)适应值评估

每个染色体的适应值的评价式子如(5)所示，由于遗传算法中适应值越高的染色体越好而目标是最小化成本，所以用任务流执行成本TEC(Total Execution Cost，TEC)的倒数作为染色体的适应值。由于编程需要，如果染色体得到的解的deadline不符合要求，即解的任务流执行时间(Total Execution Time，TET)超出deadline，则将此染色体的TEC定义为inf，即一个很大的数：

fitness

(3)动态目标策略

若第一代初始化时没有满足deadline需求的可行解，则将任务流执行时间，即将TET作为优化目标，用TET的倒数评价染色体的适应值，算法每次迭代选择TET更小而适应值更高的染色体，直到种群中有一个染色体得出的解可以满足deadline需求，即该染色体的TET小于deadline，再重新用TEC的倒数来评价适应值，即式子(5)；

(4)选择算子

根据染色体的适应值，通过轮盘赌选择进入下一代的染色体个体；资源调度序列i被选择的概率如公式(6)所示；

(5)染色体的交叉和变异

每个染色体都有一个交叉概率P

如图6所示，对每个染色体，即每个资源调度序列的每个任务，生成一个随机数r∈[0,1]，若r

(6)最优个体保留策略

每一代中，若当代中有染色体的适应值高于最优染色体，则用此染色体作为最优染色体，否则，用最优染色体个体替换掉当代中最差、即适应值最小的染色体，本实施例采用一个变量存储最优的染色体个体；保留最优个体可以保证算法运行过程中所产生的最优解不被丢弃，加快算法找到最佳的调度方案；

(7)结束条件

当找到一个可行解后执行到指定代数(4000代)或者在100000代以内无法找到可行解的时候，输出算法所产生的最优解，结束整个流程。

针对遗传算法不适用于有约束条件的优化目标，本实施例提出了动态目标策略；当在以基于截止时间约束最小化成本作为优化目标的情况下没有得到可行的调度方案，就用任务完成时间作为优化目标，每次选择任务完成时间更少的调度方案，直到算法找到可行的调度方案后再重新将基于截止时间约束最小化成本作为优化目标，每次选择任务调度成本更小的调度方案，不断循环，直到程序运行结束；这个策略使算法的适用性更强，在较小截止时间约束下仍能找到可行解。

实施例2

本实施例提供一种基于动态目标策略的云计算资源调度优化系统，包括：种群初始化模块、适应值评估模块、动态目标策略构建模块、选择算子模块、染色体交叉和变异模块、最优个体保留策略构建模块和输出模块；

在本实施例中，种群初始化模块用于初始化种群，对种群中的每一个染色体，随机生成一个资源调度序列；

在本实施例中，适应值评估模块用于采用任务流执行成本的倒数评价适应值；

在本实施例中，动态目标策略构建模块用于构建动态目标策略，具体为：若第一代初始化时没有满足最终截止时间需求的可行解，则将任务流执行时间作为优化目标，将任务流执行时间倒数评价染色体的适应值，每次迭代选择TET更小而适应值更高的染色体，直至种群中出现染色体得出的解满足最终截止时间需求，再重新采用任务流执行成本的倒数评价适应值；

在本实施例中，选择算子模块用于根据染色体的适应值，通过轮盘赌选择进入下一代的染色体个体；

在本实施例中，染色体交叉和变异模块用于完成染色体的交叉和变异，每个染色体都设有一个交叉概率和一个变异概率，对每个资源调度序列生成一个随机数，若随机数小于交叉概率，则选择该资源调度序列作为交叉的父本之一；

对每个资源调度序列的每个任务，生成一个随机数，若随机数小于变异概率，则该任务所占资源编号发生变异；

在本实施例中，最优个体保留策略构建模块用于构建最优个体保留策略，具体为：每一代中，若当代中有染色体的适应值高于当前最优染色体，则将当代中所述染色体作为新的最优染色体；否则，采用当前最优染色体个体替换掉当代中适应值最小的染色体；

在本实施例中，输出模块用于输出最优解，在找到一个可行解后，执行到指定代数后无法找到可行解的时，输出产生的最优染色体的解。

实施例3

本实施例还提供一种存储介质，存储介质可以是ROM、RAM、磁盘、光盘等储存介质，该存储介质存储有一个或多个程序，所述程序被处理器执行时，实现上述实施例1基于动态目标策略的云计算资源调度优化方法。

实施例4

本实施例还提供一种计算设备，所述的计算设备可以是台式电脑、笔记本电脑、智能手机、PDA手持终端、平板电脑或其他具有显示功能的终端设备，该计算设备包括该计算设备包括处理器和存储器，存储器存储有一个或多个程序，处理器执行存储器存储的程序时，实现上述实施例1基于动态目标策略的云计算资源调度优化方法。

上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。