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

　　【摘要】：为满足海量数据挖掘的需求，提出一种新的动态图挖掘方法。给出云计算平台能耗度量公式，分析任务调度策略的合理性，综合考虑系统能耗优化与系统运行效率问题，在保证系统运行效率良好的前提下减少能耗，将系统能耗优化问题转化成系统成本控制问题，并得出总消耗成本目标函数，基于该函数设计出计算任务自适应分配算法与最小能耗优化云模型。改变传统图挖掘算法的串行执行方式，提出一种基于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到执行完成所产生的空闲能耗可以根据结点空闲的概率与结点响应时间来度量，计算公式如下：