云计算中蚁群算法的并行化

云计算中蚁群算法的并行化摘要云计算是一种新的商业计算模型和服务模式，是分布式计算、并行计算、效用计算、网络存储、虚拟化、负载均衡等传统计算机和网络技术发展融合的产物。并行计算（ParallelComputing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。云计算与并行计算是一脉相承的，云计算的基础架构首先是要确保能实现并行计算。随着云计算的发展，云计算基础设施的规模正在急剧地变大。云计算数据中心通常拥有成千上万台物理结点，在其上运行着各种各样的服务和应用程序，由此产生了巨大的能源耗费。当前云计算中数据中心的节能问题成为了研究热点，本文通过考虑虚拟机的整合技术，减少物理主机的使用，节约电能。同时，本文提出蚁群算法来实现虚拟机的迁移，并将此算法并行化。关键字：云计算，并行计算，蚁群算法，并行化ABSTRACTCloudcomputingisanewcommercialcalculationmodelandservicemode,anditisproducedbydistributedcomputing,computing,utilitycomputing,networkstorage,virtualization,loadbalanceandothertraditionalcomputerandtechnologydevelopment.Parallelcomputingistheprocedureofusingmultiplecomputingresourcestosolveacomputationalproblem,anditisaneffectivemeanstoimprovethecomputingspeedandprocessingabilityofcomputersystem.Cloudcomputingandparallelcomedowninonecontinuousline.Cloudcomputinginfrastructure,atfirst,tomakesurethatitcanbeimplementedinparallelcomputing.Withthedevelopmentofcloudcomputing,theinfrastructuresarebecomingincreasinglylargescale.Clouddatacentercanpotentiallyhousethousandsofphysicalservers,andtherearevariousservicesandapplicationsrunningonthem.Therefore,ithasahugeenergyconsumption.Currently,energysavinghasbecomeacommondiscussedtopicindatacenter.Inthispaperweresearchtheplacementofvirtualmachine,minimizingthenumberofhostused,tosaveenergy.Atthemeantime,weproposedantcolonyalgorithmtoaddressthemigrationofvirtualmachines.Finally,weproposeaparallelalgorithmbasedonthisalgorithm.KEYWORDS：Cloudcomputing;Parallelcomputing;Antcolonyalgorithm;Parallel.1.1云计算的介绍1.1.1云计算的概念目前业界对于到底什么是云计算还没有形成一个统一的概念，其中文献[1]就罗列了20多种各个领域的专家从不同的视角给出的云计算概念，本文从中列举出几个如下：（1）加州大学伯克利分校：云计算指的是通过互联网提供的应用服务和在数据中心中提供这些服务的软件和硬件设施。这些服务长期以来被称作软件即服务（SoftwareasaService，SaaS），而数据中心中的软件和硬件设施就是被我们叫做的“云”[2]。（2）美国国家标准与技术研究院（NIST）：云计算是一种能够通过网络以便利的、按需付费的方式获取计算资源（包括网络、服务器、存储、应用和服务等）并提高其可用性的模式，这些资源来自一个共享的、可配置的资源池，并能够以最省力和无人工干预的方式获取和释放[3]。（3）墨尔本大学的Buyya教授：云计算是由一组内部相互连接的、虚拟化的机器组成的并行的、分布式的计算系统，这个系统能够根据服务提供方和用户之间协商好的服务等级协议来动态地提供一个或多个标准的计算资源[4]。上述的几个概念分别从不同的视角对云计算的概念进行了描述。本文采用文献[5]中的定义，认为云计算是一种商业计算模型，它将计算任务分布在大量计算机构成的资源池上，并通过网络提供给用户，使用户能够按需获取计算力、存储空间和信息服务。这种资源池称为“云”。“云”是一些可以自我维护和管理的虚拟计算资源，通常是一些大型服务器集群，包括计算服务器、存储服务器和宽带资源等。云计算将计算资源集中起来，并通过专门软件实现自动管理，无需人为参与。用户可以动态申请部分资源，支持各种应用程序的运转，无需为烦琐的细节而烦恼，能够更加专注于自己的业务，有利于提高效率、降低成本和技术创新。云计算是并行计算（ParallelComputing）、分布式计算（DistributedComputing）和网格计算（GridComputing）的发展，或者说是这些计算科学概念的商业实现。云计算是虚拟化（Virtualization）、效用计算（UtilityComputing）、将基础设施作为服务Iaas（InfrastructureasaService）、将平台作为服务Paas（PlatformasaService）和将软件作为服务SaaS（SoftwareasaService）等概念混合演进并跃升的结果[6]。1.1.2云计算服务模式在云计算服务模式中，用户交互接口以WebService方式为各种用户提供访问接口，以获取用户需求；配置工具用以在分配的节点上准备任务运行环境；系统管理模块负责管理和分配所有可用的资源，其核心是保证负载均衡；服务目录是用户可以访问的服务清单；监视统计模块负责监视节点的运行状态，并完成用户使用节点情况的统计。用户交互接口允许用户从目录中选择并调用一个服务，将请求传递给系统管理模块后，它将为用户分配合适的资源,然后调用配置工具为用户准备运行环境。在云服务器端,所有的计算及存储资源分布在不同的节点上，系统管理员主要是使用一些配置工具和系统管理软件，一方面可以方便快捷地为用户提供计算和存储资源，另一方面可以对这些计算存储资源进行高效管理，提高资源利用率。1.2并行计算并行计算（ParallelComputing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户[7]。云计算与并行计算式一脉相承的技术，云计算的基础架构首先是要确保能实现并行计算。并行计算的作用是将大型的计算任务拆分，然后派发到云中的各个节点进行分布式的并行计算，最终再将结果收集后统一处理。2基于蚁群算法的多目标优化虚拟机放置策略从理论上来说，组合优化问题的最优解可以通过简单的枚举得到，但实际上一般无法实现。尤其对于规模巨大的实际问题来说，可行解的数量可能特别大。如何有效地处理组合爆炸是解决问题的关键之一。本文采用蚁群算法来处理组合优化问题，下面详细描述所提出的多目标优化虚拟机放置问题的蚁群算法的设计步骤和具体的处理过程[8]。2.1适宜度函数在蚂蚁觅食过程中，距离目标越近的路径其上的信息量就越多。而装箱问题可以通过适宜度函数[8]的大小来评价一个解的好坏，适宜度函数的值越大说明算法解的效果越好。因此，分别定义了3个子适宜度函数：SLA违背率函数0.91()1CPUSLACPUufue(2.1)其中，CPUu表示物理结点的CPU利用率。为了减少SLA违背率的发生，我们为物理结点的CPU利用率设定了一个门限值，其值为90%。从公式中可以看出当CPU利用率从0到90%变化时，SLAf下降地比较缓慢；但当CPU利用率超过90%后，SLAf会迅速地下降。SLAf值的范围在[0~1]之间，CPU利用率越低，函数值就越大。2）资源利用函数(,,)resourceCPUmembwCPUmembwfuuuuuu(2.2)其中，CPUu、memu、bwu表示物理结点上CPU、内存和网络带宽的利用率。resourcef反映了各个资源在物理结点的利用情况，当各个资源均充分利用时其值最大。resourcef值的范围在[0~1]之间。2.2信息素蚂蚁完成对虚拟机的搜索过程或者是完成一次循环后，就会在虚拟机上释放信息素，从而形成信息素轨迹。信息素的浓度大小会影响蚂蚁的搜索路径，即改变虚拟机的放置顺序。初始时刻，各个信息素的强度均相等，设Ciu)0(（C为常数，i表示虚拟机，u表示主机结点），即对任意一个虚拟机与主机结点对的初始信息素都是相同的。为了提高搜索效率，我们采用最大最小蚂蚁系统[9]（MMAS）对信息素进行更新，也就是在每次循环以后，只有最优解上的信息素得到加强。信息素更新规则如式（2.3-2.4）所示。(1)bestiuiuiu(2.3)(),0,bestbestiufSiu如果虚拟机装载在结点上其他(2.4)其中，表示信息素的挥发系数，取10是为了避免虚拟机上的信息量无限增加，可见其值越大，信息素挥发的就越快；bestiu表示本次循环最优解中虚拟机与结点对的信息素增量，也就是说只有最优解中的虚拟机与结点对的信息素得到了加强，而其他解中虚拟机与结点对的信息素就会因为信息素的挥发而减少。)(bestSf为信息素增量函数，也就是适宜度函数，其中bestS表示最优解集。2.3概率转移函数每个蚂蚁k需要根据概率转移函数)(tPkiu从待放置的虚拟机中搜索下一个虚拟机i，并将其装载到当前的主机结点u上。为了满足实际装箱过程中的需求，在完成一次循环以前，不允许蚂蚁选择已经搜索过的虚拟机和主机结点u装载不下的虚拟机[10]。根据这个约束条件，系统为每个蚂蚁都设计一个称为禁忌表（Tabulist）的数据结构。禁忌表记录了在t时刻蚂蚁已经搜索过的虚拟机和主机结点u装载不下的虚拟机，不允许蚂蚁在本次循环结束前再访问这些虚拟机。当本次循环结束后，系统清空禁忌表，然后该蚂蚁就可以自由地进行选择了。概率转移函数)(tPkiu为()(),()()()0,kiuiukksusuiusallowedttiallowedttPt其他(2.5)其中，1,2-kkallowedntabu（，，）表示蚂蚁k下一次允许选择的虚拟机；是信息启发式因子，是能见度启发式因子，这两个参数反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。由上式可知，转移概率函数)(tPkiu与)()(ttiuiu成正比。)(tiu是虚拟机i上的信息素强度，强度越大，虚拟机被选择的概率就越大。)(tiu为能见度因数，其表达式为111()111iuCPUmembwiiitrrr(2.6)其中，CPUir、memir、bwir分别为虚拟机i请求的CPU、内存和网络带宽占主机结点u上相应资源的比例；)(tiu为蚂蚁搜索虚拟机i的启发程度，这个量随着虚拟机的变化而变化，有利于蚂蚁寻求最优装