论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　I
　　E(C)D=XxE(t,)⑵
　　i=1
　　其中,EG,)表示结点i对任务的响应时间。在M/M/1排队模型中，结点空闲概率可以表示为^=1-E(Pi),因此，要降低E(C)D,可以通过增大E(Pl)来实现，而计算结点期望服务强度E(Pl)与任务调度概率及单个结点的服务强度相关，其计算公式为：
　　E^PJ)=XPjxPj⑶
　　通过上述公式可知，想要增大期望服务强度就必须将大服务强度的任务j调度到计算结点i上，以增加结点服务强度，同时降低结点空闲时间，并最终降低系统的空闲能耗E(C)D。因此，通过上述理论推导,改进任务调度策略使得所有计算结点保持忙碌状态，有利于提高系统资源的利用效率与降低系统空闲能耗。
　　对于系统执行能耗E(C)B,考虑到同一计算任务在不同结点运行时，由于执行功率较大的计算结点性能较高,任务的执行时间较短，因此也可以使得执行功率较大的计算结点总的执行能耗达到最小。任务j在计算结点i的执行能耗可以表示为：
　　E(C)s=p,x丄⑷
　　即执行功率与任务j调度到计算结点i的概率成正比，与任务j在计算结点i中服务率成反比。任?
　　务j调度到计算结点i的概率取决于任务调度策略,与系统本身没有关系，因此可以减少任务到达来降低执行能耗E(C)B,但需要注意的是，能耗优化不能违背云计算的初衷，在降低系统能耗的同时必须考虑系统的执行性能，如果只考虑到执行能耗的最优,则会发生少数计算结点运行大量计算任务的不合理现象，导致系统资源的极大浪费与运行效率低下。因此，为了均衡系统的执行效率与执行能耗，可以通过增加任务j在计算结点i中服务率来降低执行能耗，即将时间成本较小的任务分配到功率较大的计算结点中，提高执行功率大的结点的服务率，以降低执行能耗，同时也可以保证系统的运行效率不受影响。
　　3.2最小能耗优化
　　根据上述的理论分析与推导，云计算平台中能耗问题主要包括空闲能耗与执行能耗2种，并且可以通过改进任务调度策略使得计算结点尽量忙碌,以及将时间成本较小的任务分配给功率较大的计算结点，以达到降低整体能耗的目的。同时能耗问题也需要综合考虑，并不能为了改善系统能耗而导致系统运行效率的降低，通过分析可知，这种情况很有可能会发生。因此，本文将综合考虑系统能耗优化与运行效率的均衡问题，分析系统任务执行的功率与时间、任务调度过程的计算结点数量、分配子任务数量、资源调度成本、数据文件使用成本、回收数据文件成本等因素对两者的影响，并将系统能耗优化问题转化成系统成本控制问题，在不会对系统运行效率有较大影响的情况下，想要达到最小能耗优化,只需满足最小系统消耗成本。在给出基于最小能耗优化的总消耗成本目标函数之前，首先定义相关参数式(6)计算系统文件资源调度时间成本,如果计算结点i在任务分配时使用过文件资源r,则=1,否则为0。式(7)计算任务分配成本,将空闲能耗的期望服务强度E(Pl)与执行能耗中的服务率/^作为分配成本的_部分,对于给定的计算结点，采用资源实际使用数量与总时间的乘积，再加上空闲能耗与执行能耗的核心要素构成了总的任务分配成本。式(8)计算使用与回收资源的成本。这3个成本函数构成了总消耗成本目标函数，在计算时需要考虑其约束条件，式(9)保证计算结果不能为负,即初始资源数量与分配的资源数量之和要不小于回收资源数量。式（10)表示系统资源需求量应不小于初始设定的资源需求量。式（11)表示期望服务强度E(Pl)与服务率/^不能为0。式（12)表示子任务的预计时间大于子任务分配时间成本与回收时间成本之和。
　　综上，最小能耗优化问题即为求解满足总消耗成本目标函数（式5)最小的最优任务与资源分配万条。
　　3.3算法设计
　　总消耗成本目标函数优化求解问题是一个NP难问题，解决方法有基于图论、整数规划的精确求解方法以及基于启发式的近似求解方法。想要在短时间内完成NP难问题精确求解是比较困难的,往往需要强大的硬件资源与高效处理技术。因此本文基于启发式搜索技术来解决该优化求解问题，设计出最
　　小能耗优化的任务分配算法（MinimumEnergyConsumptionOptimizationTaskAllocationAlgorithm,
　　MECOTAA)。算法采用随机轮流与轮盘赌相结合的方法来选择最优分配方案,并设计多点交叉操作进行多角度方案选择操作，以尽可能多的获得候选分配方案，同时为了增强方案的多样性，设计了_个任务更新操作函数，可以对新分配方案进行随机更新。具体的操作步骤如下：
　　算法1MECOTAA
　　输入计算任务列表参数设置表1,最小成本阈值m
　　输出最优任务分配方案TA
　　(1)系统初始化操作函数/nitialOp(),将计算任务列表放入到任务调度队列TL中，根据参数设置表1相关参数，其中JsLengthCTLhB.为用户给定的预计时间成本,r=1表示只有一种输入文件类型。
　　(2)根据式（5)设计任务分配方案AS=(A.?,'），并假设所有的资源调度时间成本为1,即设置ooL=1，KiJ=1,J=1。
　　(3)在初始分配方案中随机生成（A.F.Xj),然后根据式（9)~式（12)判断生成的方案是否有效，如果有效则根据式(5)~式⑷分别计算X(P),Y(P),Z(P)以及Cost(P),否则重新生成分配方案。
　　(4)取其中_个任务分配方案为最优方案，并设定Cost(P)为最小消耗时间成本MinCost。
　　(5)设计一个随机轮流选择与轮盘赌选择相结合的算法ChooseOpO,以尽可能地使得搜索结点与最优结果相接近,并且避免可早地陷入到局部最优。先由轮盘赌根据生成概率F(C,)生成2种分配方案ASt和AS2，如果无效就重新生成。
　　(6)设计一个多点交叉操作函数Crossver〇p(),并将ASi和AS2进行随机多角度交叉操作，交叉点设置为Min(Length(ASi),Length(AS2))的三次方根，得到2个新分配方案:AS3,，S4。
　　(7)设计一个更新操作函数UpdateOp(),对新的分配方案进行随机更新，以增强方案的多样性与扩展搜索空间。
　　(8)对2种新的分配方案分别计算Cost(P),并与MinCost进行对比，如果小于MinCost则进行替换，将新的方案作为最优与次优方案，循环执行步骤(4)~步骤(8),直接达到循环结束条件。
　　(9)循环结束条件为：1)最优与次优方案AS1和AS。满足最小成本阈值m;2)达到一定的循环次数,譬如5000次，则取最小Cost(P)对应的方案作为最优方案TA。
　　在得到最佳任务分配方案后，系统根据方案将输入的任务进行分配执行，以达到系统能耗与性能的最优。将传统云计算任务调度模型与本文的任务分配方案相结合，设计出最小能耗优化云模型,因此该模型是基于传统云平台的_种改进，以进_步提升系统资源整合利用的效率。模型如图2所示。
　　图2最小能耗优化云模型
　　Driver为主控结点（机架服务器），Task1,Task2等分别表示计算任务列表T_List中输入任务，TL是T_List的简称,i1,i2等分别计算结点（刀片服务器），tl是计算任务列表,/nitialOp()为系统初始化操作函数,将计算任务列表T_List放入到任务调度队列TL中，根据参数设置表1相关参数。ChooseOp()为随机轮流选择与轮盘赌选择相结合的算法，使得搜索结点与最优结果相接近，并且避免可早地陷入到局部最优。CrossverOp()为多点交叉操作函数。UpdateOp()为更新操作函数，对新的分配方案进行随机更新,以增强方案的多样性与扩展搜索空间。
　　4动态图挖掘方法
　　4.1动态图
　　在最小能耗优化云中进行动态图挖掘首先要解决动态图的表示与挖掘算法的并行化问题。下面给出相关概念与定义。
　　定义1(动态图）令五元组G=(V,E,U,P)表示一个动态图G5,其中，V表示顶点集合;E表示边的集合;乏为标记集合;映射A:(VUE)-$表示入每个顶点与每条边分配一个标记;P为权值集合。在时间段te=(t-t')内，图G=(VE)由一种状态转变为另一个状态G'=(V',E'),若满足条件：（1)V'=V;(2)E'=E-E1其中，(Vx
　　V)-E,则称图G为动态图,G'为转变图。
　　图的转变本质是边与结点的产生与消失，将权值集合P作为边的存在可能性函数,定义为(0,1],则动态图就是_种所有边带权值的图结构。如果所有边的权值为1,表示图中边不会发生改变，图是确定的，因此确定图是一个所有边权值为1的特殊动态图。
　　动态图数据库是动态图的集合，令GDB={^,
　　G2,…，表示一个动态图数据库，其中G2,…，分别表示不同的动态图。在动态图数据库中挖掘频繁子图模式需要考虑树的变化特征，同时传统的支持度定义方法在动态图挖掘中也并不适用，因此本文需要根据图的变化特征对支持度进行重新定义。
　　定义2(动态图的转变概率）给定一个动态图G=(VE)和一个转变图G'=在时刻t下
　　转变图G'出现的概率为H:
　　P((G/〇-)^)=ne)on(1-p(e))
　　eeEeeE*-E
　　(13)
　　其中,P(e)表示边的转变概率,本文假设动态图中不同边的存在与否是相互独立的，根据概率统计可知：对于动态图G,可用函数P((G/G')|t)表示在样本空间的S(G)的概率分布，其中S(G)={G'1,G'2,ooo,G'"}表示图的集合。
　　定义3(S(G)转变概率）给定一个动态图数据库GDB和S(G),在有效时间段te=(t-t')内S(G)出现的概率为：
　　n
　　P((GDB/S{G)V)|te)=nG,/G')(14)
　　定理对于_个给定的动态图数据库GDB,函数P((GDB/S(G)V)|te)定义在样本空间S(GDB)上的概率分布,S(GDB)表示动态图数据库下所有S(G)的集合。
　　定义4(期望支持度）对于一个给定的动态图数据库GDB,在有效时间段te内子图g在GDB中的期望支持度定义为：
　　n
　　ESGDB(g|te)=XS,oPCS,|te)(15)
　　i=1
　　或：
　　ESGDB(g|te)=XSq(g)o
　　qeSTGDB)
　　P((GDB/q)|te)(16)
　　其中，q=S(G),子图g在动态图G中出现，当且仅当g存在于S(G)中任意一个图中，根据概率统计,将上述公式转化以简化计算过程，得到下式：
　　1|GDB|
　　ESGDB(g|te)=|GDB|XP((g.G)|te)(17)
　　定义5(动态支持度）对于给定的动态图数据库GDB,子图g在时间段te内的期望支持度为ESGDB(gIte),则称ESGDB(gIte)为g的动态支持度。
　　将动态图的期望支持度作为挖掘支持度，不仅可以体现动态图的变化特征，而且根据定义，转变概率与期望支持度都满足Apriori性质，因此在动态图挖掘过程中可以利用Apriori性质进行剪枝，提高挖掘的效率。