基于蚁群优化算法的云数据中心中虚拟机放置方法

摘要

本发明公开了一种基于蚁群优化算法的云数据中心中虚拟机放置方法，采用蚁群优化算法解决VMP问题，在虚拟机请求到达时，找到一种虚拟机的放置方法，使得云数据中心的总体能耗达到最小的同时减少虚拟机之间通信所需的网络总带宽。本发明的主要特征是生成虚拟机的放置次序及蚂蚁之间进行直接的信息交流等，其技术效果在于，在给定网络拓扑上通过运用基于蚁群优化算法，以最小能耗为优化目标，计算出一种满足实际部署要求的虚拟机部署放置方案。仿真实验与数据分析表明，本发明提出的蚁群优化算法相比于降序首次适应算法算法，在算法性能上具有显著优势，获得的虚拟机的部署方案能够明显地降低云数据中心的总体能耗，证明了本发明的可行性及优势。

说明书

技术领域

本发明涉及云计算与虚拟化技术领域，特别是一种基于蚁群优化算法的云数据中心中虚拟机放置方法。

背景技术

近年来，云计算技术发展迅速，随着云计算的发展，云计算的模式无处不在，有越来越多基于云的解决方案出现(参考文献R.Cohen,L.Lewin-Eytan,J.S.Naor,and D.Raz,"Almost optimal virtual machine placement for traffic intense data centers,"inINFOCOM,2013Proceedings IEEE,2013,pp.355-359.)。云计算是一种新的计算模式和资源供给，既指在互联网上作为服务交付的一种应用，也指提供这些服务的数据中心中的硬件和软件(参考文献M.Armbrust,A.Fox et al.,“A view of cloud computing,”Communications of the ACM,vol.53,no.4,pp.50–58,2010)，其一般被分为三种服务模式：基础设施即服务(IaaS)、平台即服务(PaaS)、和软件即服务(SaaS)(参考文献Buyya R,et al.Cloud computing and emerging IT platforms:vision,hype,and reality fordelivering computing as the 5th utility.Future Gener Comput Syst 2009；25(6):599–616.)，云计算中的物理资源是由数据中心提供，随着云计算的快速发展，云数据中心的规模和数量的也在急剧增加，云数据中心中的能源消耗及设备散热成本也随之增加，数据中心通常有三个主要的用电设备：服务器，冷却系统和数据中心网络设备，通常估计为：服务器(40-55％)，制冷系统(15-30％)和网络设备(10-25％)。全球数据中心在2010年消耗了201.8亿千瓦时的电力，足以满足美国1,900万平均家庭用户的需求，占全球耗电量的1.1-1.3％，到2020年预计将增长到8％(参考文献P.X.Gao,A.R.Curtis,B.Wong,andS.Keshav,“It’s not easy being green,”ACM SIGCOMM Computer CommunicationReview,vol.42,no.4,pp.211-222,Oct.2012.)。当前许多的云数据中心都采用了虚拟化技术(参考文献Barham P,Dragovic B,Fraser K,et al.Xen and the art ofvirtualization[J].ACM SIGOPS Operating Systems Review,2003,37(5):164-177)，虚拟化技术可以将物理资源抽象成逻辑资源，使得一台物理服务器可以虚拟化为多台虚拟机，将CPU、内存、IO等硬件资源池化，根据需求按需分配，从而提升了物理资源的利用率并且节约了能耗，在一个完全虚拟化的云数据中心，所有的应用程序都在虚拟机(VirtualMachine，简称VM)上运行。

将虚拟机合理的部署到相应的物理机能够降低云数据中心的能源消耗和提升云数据中心系统性能，虚拟机放置(Virtual Machine Placement，简称VMP)问题是一种将虚拟机合理放置在物理机上的NP难问题(参考文献R.K.Gupta and R.K.Pateriya,“Energyefficient virtual machine placement approach for balanced resourceutilization in cloud environment,”Int.J.of Cloud-Computing and Super-Computing,vol.2,no.1,pp.9-20,2015.)。VMP问题是云数据中心(Cloud Data Center，简称CDC)中资源管理和分配的重要组成部分。一般来说，对于解决此类问题，很难开发出在短时间内生成最优解的算法。元启发式算法可以在合理的时间内提出接近最优解的解决方案来解决此类问题，因此元启发式算法也被广泛的应用到了VMP问题当中，许多元启发式算法已经被用来解决VMP问题，用以优化能耗，QoS，资源利用率等问题。常见的元启发式算法有模拟退火算法(simulated annealing，简称SA)、遗传算法(genetic algorithm，简称GA)、蚁群优化算法(ant colony optimisation，简称ACO)、粒子群优化算法(particle swarmoptimisation，简称PSO)等。

蚁群算法是在1991年由Marco Dorigo等人提出的(参考文献M.Dorigo,V.Maniezzo,and A.Colorni.Positive feedback as a search strategy[R].TechicalReport 91-106,Dipartimento di Elettronic,Politecnico di Milano,IT,1991.)，蚁群在觅食的过程中会分泌出一种称为信息素的生物激素，它们通过这种生物激素来交流觅食信息，从而可以快速的找到觅食目标，Marco Dorigo等人根据这种基于信息的正反馈原理提出了蚁群优化算法，蚁群优化算法是一种基于种群的启发式仿真算法，该算法最早应用于节解决著名的旅行商问题(Travelling salesman problem,简称TSP)，结合分布式正反馈并行计算机制，易于与其他方法结合，具有较强的鲁棒性。

发明内容

本发明的目的是采用蚁群优化算法解决VMP问题，在虚拟机(Virtual Machine，简称VM)请求到达时，找到一种虚拟机的放置方法，使得云数据中心的总体能耗达到最小的同时减少虚拟机之间通信所需的网络总带宽。

实现本发明目的的技术方案如下：

基于蚁群优化算法的云数据中心中虚拟机放置方法，数据中心物理机个数为M，采用胖树拓扑结构，包括以下步骤：

步骤1获取请求创建的虚拟机个数N，获取每个虚拟机v_i所需的CPU资源和Memory资源获取虚拟机v_i与虚拟机v_j间通信所需的流量以虚拟机v_i与虚拟机v_j间通信所需的流量累加和计算所耗总流量SumTraffic，计算虚拟机v_i与虚拟机v_j间通信所需的流量与总流量SumTraffic的比值获取每个物理机p_j的CPU容量及Memory容量

步骤2根据虚拟机之间通信所需的流量降序生成虚拟机的放置次序列表vmList，根据网络拓扑生成物理机p_i和物理机p_j之间通信所要经过的交换机个数其中p_i≠p_j；

步骤3初始化蚁群算法所需的参数α、β、ρ_l、ρ_g及网络拓扑链路负载容量以启发素η₀和信息素τ₀分别对虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i.p_j)进行初始化，设置算法的最大迭代次数gen_max，当前代数gen＝0,当前蚂蚁k＝0；所述α表示信息素的重要程度，β表示启发素的重要程度，ρ_l表示局部信息素的挥发程度，ρ_g表示全局信息素的挥发程度；

步骤4选取第k个蚂蚁，使用和分别记录物理机p_j已经占用的CPU和Memory资源，用Place(k)记录第k个蚂蚁所寻得的解，Energy(k)记录该解所需要的能耗，Place(k,v_i)记录第k个蚂蚁求得的解中的虚拟机v_i所放置的物理机；

步骤5根据步骤2所生成的vmList按顺序取出虚拟机v_i，按照物理机CPU和Memory以及网络链路的约束条件，获取能够放置虚拟机v_i并且不会违背约束条件的物理机列表serverList；

步骤6依次按顺序从步骤5所得的serverList中取出物理机p_j，对虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)依据启发素更新式η₁(v_i,p_j)和启发素更新式η₂(v_i,p_j)计算出数值η₁和数值η₂，根据已放置的虚拟机数量n以方式更新；

步骤7在0到1之间随机生成实数q，若q＜q₀执行步骤8；否则执行步骤10；其中q₀为常数；

步骤8依次按顺序从步骤5所得的serverList中取出物理机p_j，根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i.p_j)计算出物理机p_j的乘积因子值获取最大的物理机乘积因子值Γ_max，并将的物理机p_j从serverList中移除；

步骤9依次按顺序从步骤8所得的serverList中取出物理机p_j，根据启发素更新式η₃(v_i,p_j)计算出新的物理机乘积因子值获取新的最大的物理机乘积因子值Γ_max，将虚拟机v_i放置到Γ_max所对应的物理机p_j上，并置Place(k,v_i)＝p_j，跳转到步骤11；

步骤10根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i,p_j)计算出物理机p_j的轮盘赌选择概率根据的大小以轮盘赌的形式选择出要将虚拟机v_i放置的物理机p_j,并置Place(k,v_i)＝p_j；

步骤11更新虚拟机v_i所选择放置的物理机p_j所使用的CPU资源和Memory资源以及虚拟机v_i与已放置的虚拟机之间通信所需的每个链路负载

步骤12用局部信息素更新方式更新虚拟机v_i与所选择放置的物理机p_j之间的信息素τ(v_i.p_j)，若有虚拟机没有放置，则跳转到步骤5；否则至步骤13；

步骤13根据蚂蚁k所寻得的解Place(k)，计算解Place(k)的能耗并记录到Energy(k)；

步骤14若k小于蚂蚁数量K，则k＝k+1并跳转到至步骤4；否则执行步骤15；

步骤15根据每只蚂蚁k所寻得的解Place(k)及解Place(k)的能耗Energy(k)，计算得出最低能耗Energy_best，并将最低能耗Energy_best对应的解作为全局最优解Place_best；

步骤16依据Place_best对每个所使用的物理机p_j使用全局信息素更新方式对物理机p_j与其上放置的虚拟机v_i之间的信息素τ(v_i,p_j)进行更新；

步骤17若当前代数gen小于gen_max，则gen＝gen+1，k＝0，并跳转至步骤4；否则，执行步骤18；

步骤18由全局最优解Place_best及计算虚拟机间通信所需网络总带宽B_min。

进一步的技术方案为，还包括：

步骤16.1使用蚂蚁适应度计算式对蚂蚁k所寻得的解Place(k)进行计算得出解的适应度值F_Place(k)，与其余蚂蚁j进行信息交流；根据蚂蚁k的解的适应度值F_Place(k)和蚂蚁j的解的适应度值F_Place(j)产生新的解Place′(k)，若解Place′(k)的能耗Energy'(k)低于解Place(k)的能耗Energy(k)，则用Place′(k)作为蚂蚁k所寻得的解；再用解Place′(k)的能耗Energy'(k)与最低能耗Energy_best进行比较，选能耗低者作为最低能耗Energy_best，并将最低能耗Energy_best对应的解作为全局最优解Place_best；对每只蚂蚁重复上述步骤，得到最终的最低能耗Energy_best和全局最优解Place_best；

步骤16.2若全局最优解Place_best被更新，则依据Place_best对每个所使用的物理机p_j使用全局信息素更新方式对物理机p_j与其上放置的虚拟机v_i之间的信息素τ(v_i,p_j)进行更新。

本发明的主要特征是生成虚拟机的放置次序及蚂蚁之间进行直接的信息交流等，其技术效果在于，在给定网络拓扑上通过运用基于蚁群优化算法，以最小能耗为优化目标，计算出一种满足实际部署要求的虚拟机部署放置方案。仿真实验与数据分析表明，本发明提出的蚁群优化算法相比于降序首次适应算法(First Fit Decreasing，简称FFD)算法，在算法性能上具有显著优势，获得的虚拟机的部署方案能够明显地降低云数据中心的总体能耗，证明了本发明的可行性及优势。

附图说明

图1为本发明使用的ACO算法的流程图；

图2为本发明使用的ACO算法与FFD算法在80VM-40PM下的能耗比较；

图3为本发明使用的ACO算法与FFD算法在120VM-40PM下的能耗比较；

图4为本发明使用的ACO算法与FFD算法在240VM-40PM下的能耗比较；

图5为本发明使用的ACO算法与FFD算法在80VM-40PM下的带宽比较；

图6为本发明使用的ACO算法与FFD算法在120VM-40PM下的带宽比较；

图7为本发明使用的ACO算法与FFD算法在240VM-40PM下的带宽比较。

本发明中所用符号如表1所示：

表1符号说明表

本发明中所用算法符号如表2所示：

表2算法符号说明表

具体实施方式

1、首先详细介绍一下本发明所解决的虚拟机放置问题，在一个云数据中心(DataCenter，简称DC)中采用胖树(Fat Tree，简称FT)网络拓扑结构，该数据中心有M台异构的物理机(异构指物理机的CPU容量及MEM容量不同)，每台物理机j的CPU容量及内存容量分别用和来表示，并且认为该DC已经完全虚拟化，所有的应用程序都在虚拟机(VirtualMachine，简称VM)上运行。假设要在该DC中创建N个虚拟机，并且在所要创建的虚拟机中，部分虚拟机之间需要一定的带宽需求来进行通信，我们不仅要为需要创建的N个VM找到合适的物理机来放置它们使得能耗减少，而且还要保证需要通信的虚拟机之间所用的链路不能过载，当虚拟机被部署放置完成后，虚拟机的运行需要占用物理机的CPU资源和内存资源，物理机的能耗与其CPU资源的使用率呈线性关系，随着物理机CPU利用率的增加，物理机的能耗也会随之增加，当物理机处于满载状态时其能耗就达到了最大值，然而当物理机处于空载状态时其能耗也为满载状态时能耗的百分之五十到七十之多，因此数据中心的能耗与虚拟机的放置位置有着重要的关系，虽然物理机能耗是数据中心能耗的重要部分，但数据中心的能耗不仅仅由物理机能耗所决定，数据中心中的网络设备的能耗也会对数据中心能耗产生不可小觑的影响，数据中心中最为重要的网络设备是交换机，交换机的能耗是由交换机的基础能耗与交换机的端口转发性能两部分所构成，交换机的基础能耗是由交换机的类型所决定的，而对于同类型的交换机其端口转发性能的不同所产生的能耗也不同，对于同类型交换机的具有相同转发性能的端口，其产生的能耗也是不一样的，我们使用式(1)来计算数据中心所产生的能耗，虚拟机之间的通信需要消耗带宽资源，我们在面向能耗优化的虚拟机放置时，极有可能使得虚拟机之间通信的链路过载，使得通信时延增加甚至发生链路拥塞，因此在优化数据中心能耗的同时对于网络性能的影响也不容忽视，我们使用式(6)来计算虚拟机消耗的总的带宽。

Power(Pms)+Power(Switches)(1)

其中，

式(1)是由物理机能耗及交换机能耗两部分构成的，其中式(2)为计算云数据中心中的物理机的能耗，其中式(4)为计算云数据中心中的交换机能耗，式中所用到的符号参看表1符号说明表。

其中，p(v_i)表示虚拟机v_i所放置在的物理机且表示物理机p_i与物理机p_j之间通信要经过的交换机个数，表示虚拟机v_i与虚拟机j之间流量大小。

本发明利用改进的蚁群优化算法，为虚拟机的放置选择合适的物理机，以数据中心的总体能耗为优化目标，并且在优化能耗的同时减少虚拟机之间通信所需的网络带宽。在满足虚拟机放置的约束条件下，优化目标为：

Minimize:

Power(Pms)+Power(Switches)(7)

其中，

Subject to：

且

上述约束条件中，式(12)表示要将所有虚拟机都要找到合适的物理机放置，式(13)表示对于同一个虚拟机只能够放置在一个物理机上，式(14)表示对于物理机p_j上放置的虚拟机的CPU资源需求的总和不能大于物理机p_j的CPU容量，式(15)表示对于物理机p_j上放置的虚拟机的Memory资源需求的总和不能大于物理机p_j的Memory容量，式(16)表示对拓扑中每条链路e_i的负载不能大于链路e_i的可用容量。

2、本发明实现其发明目的的具体手段是：

1)一种基于蚁群优化算法的云数据中心中虚拟机放置方法，在虚拟机(VirtualMachine，简称VM)请求到达时，找到一种虚拟机的放置位置，使得云数据中心的总体能耗达到最小的同时减少虚拟机之间通信所需的网络带宽。假设数据中心物理机个数为M，采用胖树(FatTree)拓扑结构，具体处理包括以下步骤：

步骤1获取请求创建的虚拟机个数N，获取每个虚拟机v_i所需的CPU资源和Memory资源获取虚拟机v_i与虚拟机v_j间通信所需的流量以虚拟机v_i与虚拟机v_j间通信所需的流量累加和计算所耗总流量SumTraffic，计算虚拟机v_i与虚拟机v_j间通信所需的流量与总流量SumTraffic的比值获取每个物理机p_j的CPU容量及Memory容量

步骤2根据虚拟机之间通信所需的流量降序生成虚拟机的放置次序列表vmList，根据网络拓扑生成物理机p_i和物理机p_j之间通信所要经过的交换机个数其中p_i≠p_j。

步骤3初始化蚁群算法所需的参数α、β、ρ_l、ρ_g及网络拓扑链路负载以启发素η₀(常数)和信息素τ₀(常数)分别对虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i.p_j)进行初始化，设置算法的最大迭代次数gen_max，当前代数gen＝0,当前蚂蚁k＝0。

步骤4选取第k个蚂蚁，使用和分别记录物理机p_j已经占用的CPU和Memory资源，用Place(k)记录第k个蚂蚁所寻得的解，Energy(k)记录该解所需要的能耗，Place(k,v_i)记录第k个蚂蚁求得的解中的虚拟机v_i所放置的物理机。

步骤5根据步骤2所生成的vmList按顺序取出虚拟机v_i，按照物理机CPU和Memory以及网络链路的约束条件，获取能够放置虚拟机v_i并且不会违背约束条件的物理机列表serverList。

步骤6依次按顺序从步骤5所得的serverList中取出物理机p_j，对虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)依据启发素更新式η₁(v_i,p_j)和启发素更新式η₂(v_i,p_j)计算出数值η₁和数值η₂，根据已放置的虚拟机数量n以方式更新。

步骤7在0到1之间随机生成实数q，若q≤q₀执行步骤8；否则执行步骤10。其中q₀为常数，本发明中q₀＝0.9。

步骤8依次按顺序从步骤5所得的serverList中取出物理机p_j，根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i.p_j)计算出物理机p_j的乘积因子值获取最大的物理机乘积因子值Γ_max，并将的物理机p_j从serverList中移除。

步骤9依次按序从步骤8所得的serverList中取出物理机p_j，根据启发素更新式η₃(v_i,p_j)计算出新的物理机乘积因子值获取最大的物理机乘积因子值Γ_max，将虚拟机v_i放置到Γ_max所对应的物理机p_j上，并置Place(k,v_i)＝p_j，跳转到步骤11。

步骤10根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i,p_j)计算出物理机p_j的轮盘赌选择概率根据的大小以轮盘赌的形式选择出要将虚拟机v_i放置的物理机p_j,并置Place(k,v_i)＝p_j。

步骤11更新虚拟机v_i所选择放置的物理机p_j所使用的CPU资源和Memory资源以及虚拟机v_i与已放置的虚拟机之间通信所需的每个链路负载

步骤12用局部信息素更新方式更新虚拟机v_i与所选择放置的物理机p_j之间的信息素τ(v_i.p_j)，若有虚拟机没有放置，则跳转到步骤5；否则至步骤13。

步骤13根据蚂蚁k所寻得的解Place(k)，计算解Place(k)的能耗并记录到Energy(k)。

步骤14若k小于蚂蚁数量K，则k＝k+1并跳转到至步骤4；否则执行步骤15。

步骤15根据每只蚂蚁k所寻得的解Place(k)，计算得出最优解Place_best以及最低能耗Energy_best。

步骤16依据Place_best对每个所使用的物理机p_j使用全局信息素更新方式对物理机p_j与其上放置的虚拟机v_i之间的信息素τ(v_i,p_j)进行更新。

步骤17使用蚂蚁适应度计算式对每个蚂蚁k所产生的解Place(k)进行计算得出解的适应度值F_Place(k)，顺序从蚁群中选择蚂蚁k，与其余蚂蚁j进行信息交流，根据蚂蚁k的解的适应度值F_Place(k)和蚂蚁j的解的适应度值F_Place(j)产生新的解Place′(k)，若Place′(k)优于蚂蚁k的解Place(k)则用Place′(k)作为蚂蚁k的解，并用Place′(k)与全局最优解Place_best进行比较，选优者作为全局最优解Place_best并且更新最低能耗Energy_best。

步骤18若全局最优解Place_best被更新，则依据Place_best对每个所使用的物理机p_j使用全局信息素更新方式对物理机p_j与其上放置的虚拟机v_i之间的信息素τ(v_i,p_j)进行更新。

步骤19若当前代数gen小于gen_max，则gen＝gen+1，k＝0，并跳转至步骤4；否则，执行步骤20。

步骤20由全局最优解Place_best及计算虚拟机间通信所需网络总带宽B_min。

步骤21输出全局最优解Place_best，最小能耗Energy_best，虚拟机之间通信所需的最小网络总带宽B_min。

2)实际处理过程中：

步骤2中生成虚拟机的放置列表vmList，我们采用的方式如下：

根据一组虚拟机V和虚拟机间通信所需的流量矩阵T，每次从流量矩阵中获取通信流量最大的虚拟机对v_i和v_j，然后将虚拟机对v_i和v_j添加到vmList列表中，将虚拟机对v_i和v_j从虚拟机组V中移除，直至虚拟机组V为空，则生成的vmList为虚拟机的放置次序列表，伪代码如下：

3)实际处理过程中：

步骤5对于物理机CPU和Memory以及网络链路的约束条件如下：

且

上述约束条件中，式(12)表示要将所有虚拟机都要找到合适的物理机放置，式(13)表示对于同一个虚拟机只能够放置在一个物理机上，式(14)表示对于物理机p_j上放置的虚拟机的CPU资源需求的总和不能大于物理机p_j的CPU容量，式(15)表示对于物理机p_j上放置的虚拟机的Memory资源需求的总和不能大于物理机p_j的Memory容量，式(16)表示对拓扑中每条链路e_i的负载不能大于链路e_i的可用容量。

4)实际处理过程中：

步骤6中对虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)更新所依据的启发素更新式η₁(v_i,p_j)和启发素更新式η₂(v_i,p_j)如下：

其中，

上式(23)表示物理机p_k的CPU资源的剩余量，式(24)表示物理机p_k的Memory资源的剩余量，启发素更新式η₁(v_i,p_j)表示假设将虚拟机v_i放置到物理机p_j上时，计算云数据中心中所有物理机的资源剩余量与资源使用量的比值的倒数，由该启发式更新式计算出来的数值越大说明云数据中心的物理机的CPU资源和Memory资源使用比较平衡，当物理机的资源使用较平衡时则可以避免物理机的某种资源将耗尽时另一种资源却剩余很多这种情况发生，可以使物理机能够放置更多的虚拟机。

其中，

上式(26)表示假设将虚拟机v_i放置到物理机p_j上时，计算物理机p_j的总能耗，式(27)表示计算物理机p_k的总能耗，若为1表示物理机p_k被使用，若为0表示物理机p_k未被使用，启发素更新式η₂(v_i,p_j)表示假设将虚拟机v_i放置到物理机p_j上时，计算云数据中心中被使用的所有物理机能耗的总值与被使用物理机个数的比值的倒数，由该启发式更新式计算出来的数值越大说明云数据中心的所有被使用物理机的总能耗较低。

5)实际处理过程中：

步骤8中根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i.p_j)计算出物理机p_j的乘积因子值的方式如下：

上式(28)中η(v_i,p_j)表示虚拟机v_i与物理机p_j之间的启发素，τ(v_i.p_j)表示虚拟机v_i与物理机p_j之间的信息素，α表示信息素的重要程度，β表示启发素的重要程度，ω表示常数其作用是为对后续乘积因子值的处理统一量纲，本发明中ω＝100。

6)实际处理过程中：

步骤9中计算新的物理机乘积因子值依据的启发素更新式η₃(v_i,p_j)如下：

上式(29)表示计算新的物理机乘积因子值式(30)中表示虚拟机v_i与虚拟机v_k之间通信流量与通信的总流量SumTraffic的比值，该值在步骤1中被计算，启发素更新式η₃(v_i,p_j)表示虚拟机v_i与已经放置到物理机p_j上的所有虚拟机v_k之间的总和加1，该启发式的值越大说明虚拟机v_i与已放置到物理机p_j上的虚拟机之间的通信流量总和越大，该启发式的使用可以使得将通信流量较大的虚拟机对放置在同一个物理机上，该启发式结合步骤2生成的虚拟机放置次序列表vmList可以有效的减少虚拟机之间通信所需的网络总带宽。

7)实际处理过程中：

步骤10中根据虚拟机v_i与物理机p_j之间的启发素η(v_i,p_j)和信息素τ(v_i,p_j)计算出物理机p_j的轮盘赌选择概率方式如下：

上式(31)中的参数与式(28)中的意义相同。

8)实际处理过程中：

步骤12中用局部信息素更新方式更新虚拟机v_i与所选择放置的物理机p_j之间的信息素τ(v_i.p_j)，局部信息素的更新方式如下：

τ(v_i.p_j)＝(1-ρ_l)·τ(v_i.p_j)+ρ_l·τ(v_i.p_j)(32)

上式(32)中ρ_l表示局部信息素的挥发程度，本发明中ρ_l＝0.4。

9)实际处理过程中：

步骤13采用式(1)来计算解Place(k)的能耗Energy(k)。

10)实际处理过程中：

步骤16中用全局信息素更新方式更新虚拟机v_i与所选择放置的物理机p_j之间的信息素τ(v_i.p_j)，全局信息素的更新方式如下：

上式(33)中ρ_g表示全局信息素的挥发程度，本发明中ρ_g＝0.35，Energy_max表示所有蚂蚁求的解中的最大能耗，Energy_best表示求得的最小能耗。

10)实际处理过程中：

步骤17中使用蚂蚁适应度计算式对每个蚂蚁k所产生的解Place(k)进行计算得出解的适应度值F_Place(k)，顺序从蚁群中选择蚂蚁k，与其余蚂蚁j进行信息交流，根据蚂蚁k的解的适应度值F_Place(k)和蚂蚁j的解的适应度值F_Place(j)产生新的解Place′(k)的方式如下：

上式(34)中Power(Pms)+Power(Switches)为云数据中心的总能耗，为虚拟机消耗的总的带宽，以上式来计算每个蚂蚁k的解的适应度值F_Place(k)。

顺序从蚁群中选择蚂蚁k，与其余蚂蚁j进行信息交流，根据蚂蚁k的解的适应度值F_Place(k)和蚂蚁j的解的适应度值F_Place(j)产生新的解Place′(k)，我们认为解的适应度值大的蚂蚁传递的信息的可信度较高，反之解的适应度低的蚂蚁传递信息的可靠性较低，因此根据解的适应度值的大小的概率选择蚂蚁k，与蚂蚁j的解的部分信息来构造新解Place′(k)。

蚂蚁k，与蚂蚁j进行信息交流的方法如下伪代码所示：

11)实际处理过程中：

步骤20中使用式(6)来计算虚拟机间通信产生所需的网络总带宽。

下面结合附图，对本发明的实施作进一步的详细说明：

本发明采用ACO算法来解决VMP问题，其主要处理流程见附图1所示。

我们使用胖树拓扑作为云数据中心的网络拓扑，请求创建的虚拟机个个数为80，云数据中心中可用的物理机数为40，虚拟机的CPU及Memory需求在1500到5000之间服从均匀分布随机生成，物理机的CPU及Memory容量在5000到50000之间服从均匀分布随机生成，虚拟机对之间的流量分为大流量和小流量两种，小流量在1到10之间服从均匀分布随机生成，大流量在50到100之间服从均匀分布随机生成，相互之间以小流量通信的虚拟机的个数在3到20之间服从均匀分布随机生成，相互之间以小流量通信的虚拟机的个数在3到10之间服从均匀分布随机生成。根据生成的虚拟机之间相互通信所需流量的矩阵，生成虚拟机的放置次序列表，并且根据物理机所处的位置计算物理机之间相互通信所需经过的交换机的个数，设置蚁群算法所需要的参数α、β、ρ_l、ρ_g及网络拓扑链路负载并且初始化虚拟机与物理机之间的信息素和启发素。

选取第1只蚂蚁，让该蚂蚁按照生成的虚拟机的放置次序列表，按顺序为每台虚拟机寻找合适的物理机进行放置，假设蚂蚁按顺序从虚拟机放置次序列表中取出了虚拟机v_i，首先，蚂蚁根据资源约束条件和网络约束条件筛选出能够放置虚拟机v_i的物理机列表，然后依次计算更新虚拟机v_i和筛选出的物理机列表中的物理机之间的启发素，更新完启发素之后，随机生成一个0到1之间的实数，当这个实数小于0.9时，我们选择乘积因子值最大的物理机来放置虚拟机v_i，当这个值大于0.9的时候，我们根据乘积因子值的大小概率的选择一台物理机来放置虚拟机v_i，当我们为虚拟机v_i选择好要放置的物理机之后，对该物理机的使用资源信息进行更新，对整个拓扑的链路进行更新，并且更新局部信息素，当所有的虚拟机都被放置成功之后，便得到了一种放置的方法，然后选取下一只蚂蚁，按照上述流程得到该蚂蚁的解，直到所有的蚂蚁都寻得了自己的解，然后根据所有蚂蚁的解筛选出最好的解作为全局最优解，然后让所有的蚂蚁之间进行直接的信息交流为每只蚂蚁构成新的解，筛选出最好的解与全局最优解比较，选优者作为全局最优解，至此，一代的迭代过程就结束了，然后进入下一代，然后又按照上述的过程执行，直到达到最大代数，最后输出全局最优解作为虚拟机放置的方法。

为了验证本发明采用ACO算法解决VMP问题的方法的可行性及优势，我们进行了仿真实验，并与FFD进行了算法性能比较。

1)参数设置：

本发明随机生成虚拟机的资源需求，以及每个物理机的资源容量和虚拟机之间的通信流量矩阵。需求创建的虚拟机数量和可用的物理机数量作为算法的输入参数。

ACO算法中启发素都初始化为0，信息素初始化为0.0001，局部信息素的挥发程度为0.4，全局信息素的挥发程度为0.35，启发素的重要程度为2，信息素的重要程度为1，与生成的随机实数比较的常数为0.9，最大的蚂蚁数为30，最大的代数为3，物理机的最大能耗为550，普通交换机的基础能耗为147，核心交换机的基础能耗为550，普通交换机的10MB端口能耗为0.2，普通交换机的100MB端口能耗为0.4，普通交换机的1000MB端口能耗为1.1，核心交换机的10MB端口能耗为4，核心交换机的10MB端口能耗为8，核心交换机的10MB端口能耗为22，拓扑中每条链路的最大负载为1000。

2)场景设置：

本发明以所放置虚拟机与物理机的比例不同分为：80VM-40PM，120VM-40PM，240VM-40PM三种，并且每种不同比例下分三个场景，每个场景对应不同的虚拟机需求和物理机性能。

3)性能指标：

a)能耗：对于每一个场景，本发明采用的ACO算法对于该场景独立运行30次，取能耗的平均值与FFD算法的能耗相比较。

b)带宽：对于每一个场景，本发明采用的ACO算法对于该场景独立运行30次，取所耗带宽的平均值与FFD算法的能耗相比较。

4)结果比较：

附图2-7为FFD与本发明的结果对比图，从图中我们可以看到，无论在轻载，中载，或是重载的情况下，本发明采用的ACO算法在能耗及带宽方面都要小于FFD算法，综合而言，本发明更具有优势，进而说明了本发明的可行性及优势。