最小能耗优化云模型中的动态图挖掘方法

　　【摘要】：为满足海量数据挖掘的需求，提出一种新的动态图挖掘方法。给出云计算平台能耗度量公式，分析任务调度策略的合理性，综合考虑系统能耗优化与系统运行效率问题，在保证系统运行效率良好的前提下减少能耗，将系统能耗优化问题转化成系统成本控制问题，并得出总消耗成本目标函数，基于该函数设计出计算任务自适应分配算法与最小能耗优化云模型。改变传统图挖掘算法的串行执行方式，提出一种基于MapReduce模型的大规模动态图挖掘算法，并将其应用于最小能耗优化云模型中以提升整个系统综合利用效率。实验结果表明，该方法具有较高的运行效率，能够降低整个挖掘体系的能源消耗，特别是在大图情况下效果明显。

　　【关键词】：大数据;数据挖掘；云计算；能耗优化;动态图

　　1概述

　　在大数据^时代背景下,数据以前所未有的速度急剧增长，这些海量数据已经成为一种可利用的、有价值的、基础性资源,是政府机关与企业最重要的资产之一。大数据的具体表示形式多样，其中最重要、应用最广泛的一种表示形式是图结构，如社会网络、RFID、生物基因、电子商务、互联网数据等都可以用图来表示。然而随着时间的推移与外界环境的变化，图的内部结构也可能发生改变，此类图称为动态图或者不确定图0。例如生物医学中的活性酶分子是_种蛋白质结构，可以用图结构来表示，活性酶对温度极其敏感，当外部温度发生改变时，酶分子结构就是从一种状态变化成另外一种状态，状态的改变会引发酶的变性,导致酶的失活。另外，电子商务中用户交易行为数据同样也会随情况发生改变，当消费者与企业发生退换货时，或者当消费者因某些原因更换经常光顾的商品销售企业时，用户交易行为数据结构就会随之发生改变。在这些情况下，如何发现图数据共同的特性或者隐藏的信息，以及获取图结构变化规律具有重要研究意义，并逐渐成为一个热点研究问题。

　　本文改进了在传统云计算平台中进行图挖掘应用的方式，针对云计算过程中的高能耗问题，研究任务调度与资源分配策略，提出最小能耗优化云模型与大规模动态图挖掘方法，以达到挖掘系统整体效率的最优化。

　　2相关研究

　　动态图问题主要包括动态图挖掘、建模、查询等,然而与传统图挖掘算法相比，动态图挖掘仍然是一项挑战。因此，许多专家学者们对此进行研究，并提出了相关解决方案。文献3]研究边的存在可能性及概率分布问题，讨论图的不确定性问题，提出_种计算子图期望支持度的方法与基于深度优先搜索策略的不确定图挖掘算法，将子图同构测试时间复杂度降低至线性级。文献4-5]研究不确定图的查询问题，分别提出了不确定图的k.N查询算法与top士近邻查询算法。文献64分别研究不确定图中最短路径与最短距离问题，后者提出一种基于对称变量、无偏的随机采样近似算法与期望最短距离计算方法，提高了计算效率。文献8]提出了不确定图的最可靠最大流问题和可靠性计算模型，并分别提出SPCA算法与SDBA算法,无需求得所有最大流分布获得最大流,提高了算法运行效率。另外，对于路径可达及大图查询方面的问题，专家学者也给出了相关算法GRAIL19与BitPathM,在一定程度上提高了大图查询效率。然而这些算法都是基于串行模式的单机运行算法，在测试数据集与小规模的真实环境下能很好的运行，并且具有良好的运行效率，但是在大数据环境下，数据规模往往是海量的，同时决策者对挖掘时效有一定要求，如果采取传统方式挖掘，所需时间较长，挖掘效率较低，已无法满足现实发展的需要。

　　针对上述问题,将云计算技术与图挖掘算法相结合是一种可行的解决方法&243。MapReduce的分布式编程模型是一种通用云计算处理模型，主要包括HadoopE1与HOP14,这些模型具有高可扩展性与高可用性，已广泛应用于学术界与产业界的各个领域。但同时也存在着诸多问题，其中高能耗M就是其中最为重要的问题之_。在云计算系统中，除了必要的硬件所需能源开销之外，主要的能耗存在于系统内部任务处理过程当中。主要表现在2个方面：（1)任务处理的随机性。由于云计算系统一般包含大量的处理器等硬件资源，而这些资源在任务处理的过程中往往处于低效率利用状态，任务并不是按需进行，而是随机到达的，根据有关研究&5发现，云计算处理器在空闲时的功率消耗会占峰值功率的50%~60%,因此资源浪费严重。（2)云计算处理器对不同的计算任务执行功率与响应时间一般不同，因此产生的功耗也不同，不合理的任务调度方式可能会把原本在低能耗结点就可以解决的任务发送给高能耗的结点，造成奢侈能耗，这也是不合理的。上述的空闲消耗与奢侈消耗极大地造成电能浪费，是造成云计算高能耗的2个最主要的因素，而产生的根本原因在于云计算任务的不合理调度，云计算的核心问题是资源管理问题16,这些问题也引起了专家学者们的关注与研究,并提出了一些很好的云计算任务调度策略1748,可以在_定程度上缓解上述问题。

　　本文的主要工作如下：

　　(1)根据系统空闲消耗与奢侈消耗问题，提出云平台的能耗度量公式，并推导出2种任务调度策略。

　　(2)均衡考虑系统能耗优化与系统运行效率问题，将系统能耗优化问题转化成系统成本控制问题，提出_个总消耗成本目标函数与启发式任务动态分配算法，设计出最小能耗优化云模型，系统将根据当前任务与资源利用情况，自适应分配计算资源，以达到计算资源消耗的最小化。

　　(3)根据传统图挖掘算法无法满足海量数据挖掘的需求与决策者对挖掘时效的要求，提出一种基于MapReduce模型的大规模动态图挖掘算法，并将算法应用于最小能耗优化云模型中，提高挖掘效率与系统综合利用率。

　　(4)通过大量实验验证最小能耗优化云模型与动态图挖掘算法的可行性。

　　3最小能耗优化云模型

　　3.1云平台能耗度量

　　在云计算平台中，系统能耗主要体现在硬件能耗与运行能耗两方面，硬件能耗中的基础电能、网络、空调等必要能耗本文暂不考虑，本文主要研究运行能耗问题，即通过调整云计算平台内部运行机制来降低整体能源消耗。

　　传统云平台任务执行时，由于调度的不合理而造成的计算结点空闲等待与高功率结点的能源消耗是构成运行能耗的重要影响因素。常见的运行能耗优化方法包括:通过降低系统计算结点的运行频率,延长任务执行周期来降低能耗，以及通过改进云计算平台的任务调度策略，将任务集中在少数计算结点上运行，关闭闲置结点与将其处理休眠状态来降低系统能耗。本文将采用优化云计算平台的任务调度策略来降低系统能耗，在讲具体实现方法之前，首先描述传统云计算平台的任务调度机制与能耗度量方法。

　　在云平台任务调度过程中，系统主控节点Driver输入的任务Task进行分割预处理，并缓存到总任务队列TL中，然后根据各个计算结点i状态参数表，将任务随机分配给结点对应的子任务队列tl,计算结点依次接受任务并执行，同时更新状态参数表并反馈到主控节点中，调度过程如图1所示。

　　任务随机调度机制虽然简单易行，但并没有考虑到系统整体运行效率与能耗优化等方面问题。在由计算结点组成的云计算平台，由于同一计算任务在不同结点上运行时间与结点执行功率不同，使得在不同结点上执行的计算性能与产生的能耗也大不一样，因此系统能耗与结点执行任务的功率及执行时间是紧密相关的。而任务执行的功率与时间又与任务调度过程的计算结点数量、分配子任务数量、资源调度成本、数据文件使用成本、回收数据文件成本等因素密切相关。可以通过考虑这些影响因素来改进系统资源调度与任务分配策略以实现能耗的最优。为了便于研究能耗度量与能耗优化问题，假设云计算平台中任务到达计算结点时间间隔是相互独立的，其不同任务在同一计算结点上的运行时间也是相互独立的。

　　本文参考文献15]中M/M/1排队模型来对云计算平台能耗进行度量研究,根据该模型分析能耗优化的具体实现方法。首先给出能耗度量的参数说明，如表1所示。

　　表1能耗度量参数

　　参数参数解释

　　i计算结点数量,iE[1,/]

　　J任务数量,[1，]

　　?任务j在计算结点i中的服务率

　　Pa任务j在计算结点i中的服务强度

　　任务j调度到计算结点i的概率

　　E(Pi)计算结点i的期望服务强度

　　Pd单个计算结点的空闲概率

　　E(C)D云平台的空闲能耗

　　E(C)B云平台的执行能耗

　　云计算平台的运行能耗主要包括空闲能耗与执行能耗2种，因此云平台总能耗公式可以表示为：

　　E(C)=E(C)D+E(C)(1)

　　云平台的空闲能耗E(C)D是最重要能耗之一，由于任务调度与存储访问等原因，计算结点往往无法达到性能的最佳状态，大部分时间是处于半利用或者空闲利用状态，因此造成了系统资源的浪费。当任务进入计算结点i到执行完成所产生的空闲能耗可以根据结点空闲的概率与结点响应时间来度量，计算公式如下：

　　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()为更新操作函数，对新的分配方案进行随机更新,以增强方案的多样性与扩展搜索空间。