云环境下基于CROTS算法的虚拟机放置策略(2)

　　（1）给定算法参数，每一次迭代都把当前分子w′作为禁忌算法的当前解，置禁忌表为空，藐视准则定义为：当前解的物理机使用个数少于best so far，则忽视禁忌表属性，用当前解代替best so far。；
　　（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤；
　　（3）利用当前解的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解；
　　（4）判断候选解是否满足藐视准则？若满足，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤；
　　（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素；
　　（6）转步骤（2）。
　　2）分解反应
　　发生分解反应时，一个分子w将变成两个新的分子w1和w2。这两个新分子的结构与原来的分子结构有很大的差异。本文算法中，用Order Crossover（OX）算子实现分解。
　　在OX算子中，第一个母体是原来的分子w，第二个母体是随机创建的一个解。w1由w的前半部分和随机解的后半部分组合得到。而w2由w的后半部分和随机解的前半部分组合得到。
　　3）无损分子碰撞反应
　　无损分子碰撞是两个分子碰撞后发生微小的变化又分开。这个反应有点类似无损器壁碰撞，但是不同的是这个反应涉及到两个分子，并且没有分子动能（KE）丢失到中央能量缓冲区。我们用OX算子实现这个反应。
　　4）合成反应
　　3.3 算法描述
　　在算法开始之初，需要初始化如下参数：PopSize， KELossRate， MoleColl， buffer， InitialKE，α，β。其中PopSize表示种群大小，KELossRate表示动能丢失率，MoleColl取值为[0，1]，是每次迭代时判断单分子碰撞和多分子碰撞的参数。α，β分别代表单分子碰撞和多分子碰撞选择的极限值。当一个分子的撞击次数超过α后，它的优越性还没提升则会发生分解反应。β代表一个分子所拥有的最小的动能，如果低于这个值则会发生合成反应。目标函数值就等价于分子的势能值，要找最小的函数值就得找到最稳定的势能最小的分子。
　　迭代开始之后，会随机产生一个[0，1]之间的整数K，当K大于MoleColl时则发生单分子碰撞，反之则发生多分子碰撞。迭代过程会一直继续直到达到停止标准，最终输出一个近似最优解。
　　4 实验与分析
　　4.1 实验环境设置
　　在Myeclipse中采用面向对象的java语言实现CROTS算法，并将该算法与CRO、ACO和FFD等算法进行性能上的比较，同时也分析了算法在不同的虚拟机请求规模时的性能。模拟的集群系统包含600个物理服务器（设置了600个物理服务器是为了考虑最差的放置情况，一台虚拟机占用一台物理服务器），每个服务器包含CPU，内存，存储和带宽四种资源，为了更方便的考察该算法性能，在本次实验中只考虑物理结点一个因素，假设QOS、SLA等其他因素都满足条件，本次实验适用在同构环境，600台物理服务器的性能是一样的，分别是10000MIPS、50GB内存、1TB存储、10G的带宽。实验模拟的虚拟机数目在{100， 200， 300， 400， 500，，600}内取值。类似于Amazon EC2的虚拟机实例，实验设置了四种虚拟机类型，其资源请求数目分别为：（1000， 4， 20，1）， （2000， 8， 50， 2）， （3000， 16， 100， 2）， （5000， 24， 200，4）。基于文献[ 11]对实际服务器（Dell PowerEdge1950）功耗的测量，实验设定服务器在空闲pidle和满负载pmax 时的功耗大小分别为171瓦特和218瓦特。为了对比不同算法的能耗大小，实验设定计算周期T为24小时。
　　4.2 实验结果与分析
　　实验中，为了考虑到公平性，对所有算法的虚拟机请求序列设置为一样，对虚拟机数目分别为100、200、300、400、500、600时进行10次运算最终取平均值。本文中算法的优化目标是使物理机数最少和降低能耗，根据公式（6）中的能耗模型，物理机数和它的资源利用率对能耗有直接影响，通过实验证明了真实性。
　　图3显示不同虚拟机数目情况下4种放置算法得到的能耗比较情况。随着虚拟机数目的增多，四种算法得到的能耗也逐渐增大。与FFD和ACO算法相比，CRO算法在能耗指标上平均降低了13.5%和9.9%。而与CRO算法相比，CROTS算法在能耗指标上平均降低了3.1%。这主要因为物理服务器的使用数目与数据中心的能耗有直接的关系，CRO和CROTS算法相对于FFD和ACO算法来说，能够获得更优的放置解。
　　图4比较了不同虚拟机配置数目情况下四种算法得到的物理服务器的数目比较。随着虚拟机数目的增多，四种算法的物理服务器的数目也在增大。其中，FFD算法的性能最差，其所需要的平均物理服务器数目分别是ACO、CRO、CROTS算法的1.04、1.09、1.13倍。表明算法CROTS相对于其他三种算法，具有最好的求解能力。而且从图4中可以看出当虚拟机规模越大，CROTS算法的性能越好，这是因为CROTS适合求解大规模优化问题。