一种基于能量优化的网格调度方法

摘要

本发明涉及一种基于能量优化的网格调度方法，其方法是：1.将能量资源作为调度的研究重点，引入能量初始值，网络带宽等因素；2.实现能量优化，使资源调度中的能量消耗值最小，网格资源调度中的能量消耗分为计算消耗和网络通信消耗；3.考虑时间跨度优化，达到能量优化过程中的资源负载均衡；4.提出一个综合考虑能量约束以及时间约束的基于能量优化的网格调度方法。本发明具有以下优点：1.改变了传统资源调度算法中资源类型单一这一局限性；2.将能量优化作为本调度模型的研究重点；3.解决了能量优化过程中所造成的负载不均衡问题；4.在时间跨度优化和能量优化的基础上，定义了能量代价函数，基于该代价函数，提出了基于能量优化的网格资源调度方法。

说明书

技术领域

本发明属于一种网格调度方法，特别是一种基于能量优化的网格调度方法。

背景技术

网格计算是近年来逐渐兴起的一种Internet计算模式，其目的是为了在分布、异构、自治的网络资源环境上构造动态的虚拟组织，并在其内部实现跨自治域的资源共享和资源协作，有效的满足面向互联网的复杂应用对大规模计算能力和海量数据处理的需求。因此，网格资源具有分布性和异构性这一特点，常见的网格资源有：计算资源、存储资源、网络资源、能量资源等。近年来随着Ad Hoc网络以及无线传感器网络(WSN)的快速发展和其在网格中的应用，能量资源在网格异构环境中越来越普遍。比如，在Ad Hoc网格中，各资源节点的能量储量都是有限的，在实现资源调度过程中，能量约束是一个不可忽视的因素。另外，近年来数据密集型网格应用不断增多，比如高性能物理研究、天体研究、天气预报等，这些应用都是建立在高性能数据网格之上的。高性能数据网格具有计算时间长，能量消耗大等特点，能量因素是在进行高性能计算中不得不考虑的一个问题。当前，随着人们对环境问题关注力度的不断增大，能量优化问题已经成为了各种领域内急需解决的一个问题。因此，在网格调度研究中考虑能量约束，实现调度的能量最优也将成为网格计算研究领域内的一个热点。

网格计算的资源调度是个NP完全问题。由于NP问题目前还找不到有效的解决方案，人们提出了一些启发式方法来寻求它的次优解，如遗传算法，蚁群算法，Min-Min，禁忌搜索，神经网络，模拟退火等算法。现阶段，对启发式调度算法的研究主要分为两个方面：静态调度算法和动态调度算法。静态算法是指所有的任务-资源映射策略在调度前已经确定，而动态调度算法是指部分任务-资源映射策略是在调度期间根据实际情况确定。因此静态调度算法相对比较简单，运行开销小，对数据依赖小，但静态调度算法对于网格环境中资源的分布性以及异构性支持力度不够。而动态调度算法很好的解决异构性分布性带来的负载平衡问题、效应测定问题、任务迁徙问题。动态调度算法可分为联机模式(onlinemodel)和批模式(batch model)。这两种方法各有优缺点，对于联机在线模式，由于当任务到达时就考虑分配，尽可能及时地将任务进行调度，因此反应快、任务的延迟时间短，但是可能导致资源的分配不够优化，因为没有考虑前后任务的特点，可能导致要求低的任务占用处理能力强的节点，而要求高的任务分配到处理弱的节点或者处于等待状态。而批处理方式则能够考虑更多的请求和资源状况，潜在地能得到更有效的网格资源利用率，但对于单个任务来说，延迟时间可能较长，对于某些服务质量没有办法实施。

网格应用的不断发展，尤其是服务网格的出现，促进和加速了对于网格服务质量(QoS)的研究。各种基于QoS的调度算法也逐渐出现，这些调度算法都是在原有经典调度算法的基础上加入各种QoS约束条件演化而成。一般研究的QoS约束主要集中在：网络带宽、网络延时、代价、时间、生存性、信任度等方面。相应的改进算法也能很好的解决很多调度过程中的核心问题：完成时间优化、调度效率优化、经济开销优化等。但由于涉及的网格资源类型比较单一和QoS约束条件本身的局限性，对于调度过程中的能量优化问题很少有涉及。

发明内容

本发明的目的是提供一种将能量资源引入到网格资源调度中，综合考虑能量约束以及时间约束的基于能量优化的网格调度方法。

为了实现上述目的，本发明的技术方案如下：

1、将能量资源作为调度的研究重点，引入能量初始值，网络带宽等因素。

2、实现能量优化，使资源调度中的能量消耗值最小，网格资源调度中的能量消耗主要分为计算消耗和网络通信消耗。

3、考虑时间跨度优化(Makespan)，达到能量优化过程中的资源负载均衡。

4、提出一个综合考虑能量约束以及时间约束的基于能量优化的网格调度方法。

考虑到网格资源调度过程中网格任务以及网格资源都具有分布性以及异构性，本发明的网格调度模型不能对真实的网格环境进行完全模拟，因此做出如下设定：

(1)各网格任务都是独立存在的，任务之间无数据依赖或通信。

(2)在调度模型中的能量资源能实现任务计算，任务执行等功能，与狭义上的只提供能源供应的能量资源有区别。

(3)每个资源只能同时执行一个网格任务。

(4)网格调度中的能量消耗只限于任务执行消耗和网络通信消耗，而网络通信消耗主要指任务与资源数据通信时的能量消耗，资源间通信的能量消耗忽略。

(5)网络通信时间为网络带宽的倒数，忽略网络延时等其他网络因素。

(6)每个资源的能量储备是有限的，不同资源的能量初始值不一样。

(7)资源处于空闲状态时，无能量消耗。

以下为本发明中的一些基本参数的定义：

(1)集合R＝{r₁，r₂，...，r_n}表示n个异构的能量资源组成的网格环境。

(2)集合T＝{t₁，t₂，...，t_m}表示m个独立的网格任务集合。

(3)矩阵其中ET_ij指的是能量资源r_j执行任务t_i所需要的执行时间，本专利中的ETC通过NWS获得。

(4)G_i表示任务t_i在任务执行前向能量资源提交的初始数据值大小。

(5)B_j表示能量资源r_j的初始能量值。

(6)E_j表示单位时间内能量资源r_j执行任务所消耗的能量消耗值。

(7)C_j表示单位时间内能量资源r_j通信单位数量数据的能量消耗值。

(8)BW_j表示能量资源r_j的网络带宽。

本发明的具体步骤如下：

第一步骤：对于任务集T中的每一个任务将其映射到资源集R中的每一个机器，求出每一个对应的代价值Cost(i，j)；

第二步骤：将资源集中的所有资源标记为未标记；

第三步骤：选取任务集中的任意一个任务ti，映射任务到代价值Cost(i，j)最小的那台资源rj，并且算出Cost(i，j)值，该值为最小代价；

第四步骤：算出该映射的sufferage值，该sufferage值表示如果将任务映射到除rj外的其他资源时将付出更多的代价，sufferage值等于最小代价与次最小代价的差值；

第五步骤：判断资源rj是否为未标示：

如果资源为未标示，则将任务ti从任务集T中删除，同时将资源rj标示为已标记；

如果为已标记，则比较已映射到资源rj上的任务tk与任务ti的sufferage值大小，若tk的sufferage值更小，则将tk重新放回任务集T中，而将ti映射到rj，同时将ti从任务集T中删除；

第六步骤：重复第三步骤--第五步骤，直到无新任务可以分配出去为止，完成一次迭代过程；

第七步骤：更新在此次迭代过程中被分配了新任务的资源的就绪时间D_i和资源剩余能量值；

第八步骤：重复第二步骤--第七步骤，完成数次迭代，直到任务集中的所有任务均已完成，算出参数EC_avg的值。

现阶段对网格资源调度的研究主要集中在最优跨度(Makespan)，服务质量(Qos)，负载均衡，经济原则等方面。针对这些研究方向提出的调度算法或调度模型也都能很好的解决其对应的问题，但是这些研究很少涉及能量优化方面的问题。随着网格技术的不断发展，各种能量储备有限的移动设备在网格应用中的重要性逐渐增加，各种高能耗的网格应用也逐渐增多。由此可见，能量优化问题已经成为了网格资源调度中的一个不容忽视的问题，对其的研究也将是网格资源调度的一个重点研究方向。本发明从网格资源调度的能量优化出发，综合考虑能量以及时间等QoS约束条件，提出了一个一种基于能量优化的网格调度模型。该模型把资源调度中的能量优化问题作为重点研究对象，同时也综合考虑了一般调度算法中的最优时间跨度，负载平衡等问题。能量优化调度模型主要分为能量优化模块和时间优化模块。这两个子模块分别从能量和时间约束出发，提出了各自的优化方案。调度模型基于这两个优化方案，给出了一个能量代价函数，该代价函数能很好的衡量在调度算法中能量的消耗情况。基于此代价函数，本发明提出了一个能量优化调度方法。

与传统的网格资源调度相比，本发明具有以下优点：1、针对异构环境下资源具有多样性这一特点，在此调度模型中加入了能量资源这一资源类型，改变了传统资源调度算法中资源类型单一这一局限性；2、将能量约束引入到资源调度中，重点考虑任务执行以及网络通信中的能量消耗问题，将能量优化作为本调度模型的研究重点；3、本调度模型也考虑了传统调度方法中的时间跨度(Makespan)最优，这很好的解决了能量优化过程中所造成的负载不均衡问题；4、在时间跨度优化和能量优化的基础上，定义了能量代价函数，基于该代价函数，提出了一种基于能量优化的资源调度方法。

附图说明

图1为本发明的调度方法流程图。

具体实施方式

下面结合附图对本发明作进一步的详细描述。

本发明的调度模型是为了实现网格异构环境中网格资源调度的能量优化而建立的，即在任务执行过程中在保证任务集T中所有任务均要完成的前提下，实现能量消耗值最小。同时，为了避免低能耗资源过分使用而高能耗资源长期闲置所造成的负载不均衡，时间跨度Makespan优化问题也是本调度模型研究的重点。因此，本调度模型可分为能量约束和时间约束两个子模块。

能量约束模块：本调度模型中的能量消耗包括执行任务能耗和通信能耗。由以上提供的参数可以得出任务t_i在资源r_j上执行能量消耗值EEC_i，j：

EEC_i，j＝ET_i，j*E_j.......................................(1)

任务t_i分配到资源r_j上通信能量消耗值CEC_i，j：

CEC_i，j＝G_i*(1/BW_j)*C_j.................................(2)

任务t_i在资源r_j上的总的能耗值为EEC_i，j与CEC_i，j的总和：

EC_i，j＝EEC_i，j+CEC_i，j................................(3)

资源r_j在整个调度过程中的能量消耗值为：

EC_j＝∑(EC_i，j)＜＝B_j..................................(4)

其中i为在资源r_j上执行的任务的任务编号。

在本模型中，只有满足了公式(4)的网格资源才是可用资源。

由以上公式推导出来的EC_j只是得出了单个机器(r_j)上能量消耗的情况，而模型中的能量优化问题是面向整个调度过程的，因此有必要引入一个衡量参数EC_avg：

${\mathrm{EC}}_{\mathrm{avg}}={\Sigma }_{j=0}^{n-1}({\mathrm{EC}}_j/B_j)/n,\mathrm{rj}\in R---\left(5\right)$

在公式(5)中，EC_avg表示的是平均能量消耗比率，是调度算法能量消耗的衡量标准。EC_avg越小，表示在整个调度过程中能量消耗少，EC_avg越大，表示调度过程中的能量消耗多。因此，本模型中的能量优化问题变成了求EC_avg最小值的问题。

时间约束模块：本调度模型中的时间优化问题与大多数网格资源调度算法中的时间优化一样，主要实现最优跨度Makespan。在此模型中，Makespan将不是一个重点考虑的优化对象，它的引入也是为了实现能量资源分配过程中的负载平衡。

设定任务t_i在资源r_j上的开始执行时间为D_j，则可以得出任务t_i在机器r_j上的预期完成时间C_ij为：

C_ij＝D_j+ET_ij..........................................(6)

由此，可以得出预期完成时间矩阵PEC：

$\mathrm{PEC}=\left(\begin{array}{ccc}{C}_{11}& ...& C_{1n}\\ .& & .\\ .& ...& .\\ .& & .\\ C_{m1}& ...& C_{\mathrm{mn}}\end{array}\right)$

设定任务ti分配给了资源rj执行，由矩阵PEC，可以得出实际执行时间Ci：

C_i＝C_ij...............................................(7)

最大执行时间Makespan就等于最大的任务完成时间与调度起始时间之间的差值，即从第一个作业开始执行到最后一个作业被执行完毕所花的时间，若设起始时间为零则有：

Makespan＝Max(Ci)，ti∈T..............................(8)

Makespan是异构计算系统的一个衡量标准，网格资源调度的主要目的就是要减小Makespan。Makespan值越小，则表示调度所花费的时间越小。因此本模型中的时间优化问题变成了求Makespan最小值的问题。

通过对能量约束和时间约束两个子模块的分析，可以得出本模型的代价函数，此函数综合考虑了在资源调度过程中的能量代价和时间代价：

Obj＝w*EC_avg+(1-w)*Makespan...........................(9)

其中，参数w用于调节EC_avg因素和Makespan因素两个因素在代价函数中所占的比例。特别的，当w等于1时，表示调度只考虑能量消耗代价，而当w等于0时，表示调度只考虑时间代价。

基于能量约束的网格资源调度能量优化方法是在启发式调度算法sufferage的基础上，加入能量约束演化而来的。在方法中将用到一下子代价函数：

Cost(i，j)＝w*(EC_i，j)+(1-w)*(Di+ET_ij)..............(10)

该子代价函数用来表示当任务ti分配到rj上对整个代价函数0bj值的影响情况。

调度方法执行步骤具体描述如下：

(1)对于任务集T中的每一个任务将其映射到资源集R中的每一个机器，求出每一个对应的代价值Cost(i，j)。

(2)将资源集中的所有资源标记为未标记。

(3)选取任务集中的任意一个任务ti，映射任务到代价值Cost(i，j)最小的那台资源rj，并且算出Cost(i，j)值，该值为最小代价。

(4)算出该映射的sufferage值，该sufferage值表示如果将任务映射到除rj外的其他资源时将付出更多的代价，sufferage值等于最小代价与次最小代价的差值。

(5)判断资源rj是否为未标示：

如果资源为未标示，则将任务ti从任务集T中删除，同时将资源rj标示为已标记；

如果为已标记，则比较已映射到资源rj上的任务tk与任务ti的sufferage值大小，若tk的sufferage值更小，则将tk重新放回任务集T中，而将ti映射到rj，同时将ti从任务集T中删除。

(6)重复(3)-(5)，直到无新任务可以分配出去为止，完成一次迭代过程。

(7)更新在此次迭代过程中被分配了新任务的资源的就绪时间D_i和资源剩余能量值。

(8)重复(2)-(7)，完成数次迭代，直到任务集中的所有任务均已完成，算出参数EC_avg的值。

在每一次迭代过程中，即步骤(3)-(6)，每次能够调度出去的任务个数不是固定的，它主要受一下三个因素的影响：

1)网格调度中机器的总个数；

2)被多个不同任务竞争的机器数目；

3)网格调度中任务的总个数；

在最坏的情况下，每次迭代过程只能分配出一个任务，也就是说要经过m次迭代才能完成整个资源调度过程。因此调度方法的时间复杂度是O(m²n)。

本说明书中未作详细描述的内容属于本领域专业技术人员公知的现有技术。