一种能耗关键的公共计算环境虚拟机部署算法

朱 伟，吴传峰，夏 兴

(江苏自动化研究所，江苏 连云港 222061)

0 引言

水下无人平台作为一种小型化作战平台,具备自主探测、定位和打击目标的能力,这些能力的达成需一定规模的计算资源支持;另一方面,水下无人平台受空间、能源配置限制,需统筹配置共用计算资源,并对资源的能耗提出了较高要求。公共计算环境通过提供公共的信息处理资源,具有资源共用、架构开放和健壮抗毁等显著特点,可提升舰船装备集成优化设计水平及信息实时处理、抗毁生存能力,提高系统开放性、装备使用的灵活性,代表了未来舰艇电子装备发展的方向[1]。公共计算环境可在满足水下无人平台信息处理对计算资源需求的同时,有效解决空间、能源受限问题。公共计算环境作为一种云环境,能耗大小与虚拟机(Virtual Machine,VM)数量、部署算法有直接的关系。

国内外众多学者从不同角度开展了VM部署算法研究。文献[2]为解决由非最佳VM放置导致的SLA违规问题,提出了一种基于多资源的VM放置方法,以提高CPU利用率和降低程序执行时间。文献[3]针对CPU和内存的资源使用状态提出了一种基于双游标控制机制的VM部署选择算法,在一定程度上实现了双目标优化平衡。文献[4]提出了一种多目标蚁群系统VM部署算法,目标是获得Pareto最优解集,同时提高通信收入和降低服务器的功耗。文献[5]针对数据中心能耗问题,提出了一种融合模拟退火算法的蚁群算法(ACOSA)。虽然目前的相关研究己经取得一些成果,但VM部署问题属于NP问题,无法在多项式时间内找到最优解,VM部署方式仍有进一步优化的空间。

本文面向水下无人平台公共计算环境能耗问题,提出了一种能耗关键的VM部署模型,设计了基于改进蚁群的VM部署算法来求解该模型,算法提出了负载感知概率选择模型,改进了蚁群的路径选择;提出了动态信息素模型,优化了信息素更新规则,从而实现了对VM部署方式的优化,并通过仿真实验验证了算法的有效性。

1 问题建模

通过虚拟化技术,物理服务器可以同时运行多个VM,每个VM可以独立运行应用程序或服务[6]。VM部署问题是在计算环境中将VM合理地分配到物理服务器上的过程[7]。VM部署的合理性可以直接影响计算资源的利用效率、性能和服务器集群能耗[8]。

1.1 相关定义

VM部署需要考虑多种因素,部署过程往往十分复杂,在研究过程中需要对其进行简化建模处理[9]。相关定义如下[10]:

定义1

公共计算环境中所有VM的集合为V={VM1,VM2,…,VMn},n为VM数量。每台VM表示为:

VMi=(VMCPUi,VMMemi,VMDiski,VMBwi),

(1)

式中:i为VM标识号,VMCPU为CPU需求,VMMem为内存需求,VMDisk为磁盘需求,VMBw为网络需求。

定义2

公共计算环境中服务器节点集合为P={PM1,PM2,…,PMm},m为服务器节点数量。每个服务器节点表示为:

PMj={PMCPUj,PMMemj,PMDiskj,PMBwj},

(2)

式中:j为服务器节点标识号,PMCPU为CPU资源,PMMem为内存资源,PMDisk为磁盘资源,PMBw为网络资源。

定义3

VM与服务器之间的映射关系可用部署矩阵θ表示。将n个VM部署到m个服务器节点上,用矩阵的形式表示如下:

(3)

式中:θij为VM与服务器PM的对应关系,若θij值为1,表示虚拟机i被部署到服务器j上;若θij值为0,则虚拟机i未被部署到服务器j上。

定义4

由部署矩阵θ得到VM与服务器之间的部署约束条件,表示如下:

(4)

前4个约束条件的物理意义为部署在服务器j上的所有VM需要的CPU资源、内存资源、磁盘资源与网络资源总数不得超过服务器j所能提供的资源数。最后一个约束条件为部署矩阵每一行只能有一个θ为1,表示一个VM只能部署到唯一服务器上。

定义5

(5)

定义6

服务器j的综合资源利用率Uj计算如下:

(6)

定义7

当进行VM部署时,服务器当前的CPU资源剩余可用量

(7)

定义8

服务器集群的综合资源平均利用率(AVG)的计算如下:

(8)

式(8)表示所有服务器综合资源利用率的平均值,值越大表示VM部署越合理。

1.2 能耗模型

服务器的电源能耗取决于CPU、内存、磁盘和网络设备的能耗,而其中CPU能耗占服务器能耗的比重最大。研究表明,服务器节点的CPU利用率与电源能耗呈线性关系[11]。

文献[12]研究表明,服务器空闲时的电源能耗约占满负载能耗的70%,关闭空闲的服务器可以减少能耗。如服务器的满负载功率可知,空闲功率未知,服务器的能耗功率可以定义为基于CPU利用率与最大能耗功率的线性函数:

(9)

(10)

服务器集群的单位时间的总能耗Eall由所有服务器的能耗之和求得:

(11)

本文所研究的VM部署问题,目的是优化服务器集群的能量消耗,因此目标函数式为:

min(Eall(s)),s∈S,

(12)

式中:s为满足约束条件式(4)的部署方案,S为所有部署方案s组成的方案域。

2 基于改进蚁群的VM部署算法

蚁群优化 (Ant Colony Optimization,ACO) 算法是由意大利学者Marco Dorigo于1992年提出的一种基于自然界蚂蚁群体智能行为的启发式算法[13],其模拟了蚂蚁在寻找食物过程中放置信息素的行为,并通过这种信息素来控制蚂蚁的搜索方向,从而找到最优路径[14]。蚁群算法广泛应用于解决各种优化问题,能够有效地处理大规模和复杂问题,并在全局搜索空间中找到较优解。

在蚁群算法中,蚂蚁是算法的基本单元,它们通过在路径上释放化学物质——信息素,来引导其他蚂蚁前往食物的位置。蚁群算法的关键步骤包括蚂蚁的移动和信息素更新[15]。蚂蚁在移动过程中根据当前位置的启发式规则和信息素浓度,计算下一步移动的概率。当蚂蚁选择一条路径并到达目标后,会在路径上留下信息素,其他蚂蚁在搜索过程中通过感知信息素的浓度,更倾向于选择信息素浓度较高的路径。这种正反馈机制使得信息素浓度逐渐增强,最终导致蚂蚁集中在最短路径或最优解附近。

2.1 带有负载感知的概率选择模型

在云计算服务中,用户申请的服务不同,所需求的资源也不同,进而导致了用户需求的VM类型多种多样。根据VM需求的资源类别,可以将VM分为CPU需求型、储存需求型、内存需求型、网络需求型与混合需求型。进行VM部署时,如果将同种类型的VM部署在同一个服务器上,会导致同类需求VM之间的资源竞争,降低服务器工作效率。另一方面,也会使某一类型资源过载,而其他资源未被合理利用,降低资源利用率,导致服务器集群可放置的VM数减少,总功耗增加。如图1所示,一个服务器上放置多个内存需求型VM,会导致内存资源短缺,而CPU资源剩余,资源利用率低。

图1 VM部署简图Fig.1 VM deployment diagram

基于这一问题,设计了基于负载感知的概率选择模型,在进行VM部署时,尽量在服务器上部署不同资源需求的VM,避免部署过多类型相同的VM,进而提升资源利用率,降低服务器集群能耗。

蚁群算法中,概率选择式(13)是算法的核心,蚂蚁在路径选择上依据概率公式计算每条路径的选择概率,通过轮盘赌的方式,最终选择一条道路。概率选择式影响蚂蚁在节点的方向选择,从而决定最终的路径解。

(13)

路径启发因子ηij是决定状态转移函数的核心元素,路径的本身属性影响着蚂蚁的路径选择方向,从这个角度出发,对路径启发因子进行优化设计,可以改进蚁群算法的性能。

传统启发因子一般设计为VM功耗的倒数,计算如下:

(14)

式中:Ej为服务器j当前时刻单位时间功耗,计算见式(10)。该启发因子单纯地依赖服务器的功耗进行VM部署,未考虑资源的合理利用,会导致一些资源未被完全利用,而另一些资源负载严重,使得服务器的资源利用不均衡,平均资源利用率低。

针对传统启发因子的设计问题,本文综合考虑当前待分配虚拟机i的资源需求与服务器剩余的可用资源量,计算服务器的资源满足度,设计路径启发因子。

(15)

式中:leftj为服务器j中资源剩余可用量,计算方法见式(7);虚拟机i的资源需求与服务器j剩余资源可用量的比值VPLEFTi,j表示服务器资源的满足度,VPLEFTi,j越大,表示该服务器的满足度越高。

(16)

式中:AvgVPLEFTi表示虚拟机i部署时,平均的服务器资源满足度。

改进的启发因子设计如下:

(17)

虚拟机i的资源需求与服务器j之间的资源满足度VPLEFTi,j越大于平均资源满足度AvgVPLEFTi,路径启发因子ηij越大,表示服务器j可以更好地满足虚拟机i的资源需求,虚拟机i部署在服务器j的概率越高。

传统的启发因子进行VM部署时只考虑服务器功耗,会导致资源利用不均衡。改进后的启发因子会综合考虑服务器的资源负载需求,使资源利用更均衡,提高资源的平均利用率,进而降低服务器集群能耗,实现对VM更合理的部署。

2.2 动态信息素更新规则

ACO算法存在收敛性问题,算法迭代过程中无法收敛到正确的结果或者收敛时间较长。蚂蚁之间信息交互及通信通过信息素来完成,优化信息素更新方式可以优化蚁群算法的求解性能。

基于这一问题,本文设计了动态信息素更新规则,信息素的更新随算法阶段动态变化,使其适应算法不同阶段的运行方式,可以改进蚁群算法求解的效率。传统的蚂蚁信息素的生成及更新规则如下。

在每只蚂蚁进行巡逻,构建好路径解之后,蚂 蚁k在经过的路径上留下信息素,则路径(i,j)上的局部信息素τij更新规则如下:

(18)

完成一次算法迭代,要对全局信息素进行更新,供算法下次迭代使用。全局信息素更新规则如下:

(19)

传统的信息素变化量模型:

(20)

在传统的信息素变化量模型中,信息素强度是一个定值,算法执行不同阶段的信息素强度相同。信息素对后续蚂蚁的指引作用减弱,解不容易收敛。

通过对蚁群算法路径搜索过程进行研究,可以将蚁群寻优过程分为2个阶段:算法前期为蚂蚁探索阶段,初期每条路径上信息素浓度为预设初值,各个路径上信息素浓度差别不大,蚂蚁相当于更依赖路径信息的短路径贪心搜索;算法后期为信息素利用阶段,此时蚂蚁在经过的路径上释放了相应的信息素,路径信息素又反过来影响蚂蚁的路径选择。减少前期信息素留存,可以扩大蚂蚁的搜索范围。增大后期信息素留存,可以加快解的收敛速度。

对此,本文提出时变信息素策略,设计时间变化函数f(t)来优化信息素Q释放规则,使信息素跟随算法执行时间动态变化。前期时变函数f(t)取值较小,可以减少蚂蚁释放信息素,扩大解的搜索空间。后期时变函数f(t)取值较大,可以增加蚂蚁释放信息素,进而加快解路径的收敛速度。时变函数设计如下:

(21)

式中:K为算法初始设置的最大迭代次数,t为蚂蚁巡逻时间,即算法当前迭代回合。K=20时的函数图像如图2所示。

图2 信息素时变函数Fig.2 Pheromone time-varying function

Q(t)=f(t)×Q,

(22)

式中:Q为信息素强度,Q(t)为引入时变策略的动态信息素。信息素强度跟随算法迭代时间动态变化。

2.3 算法描述

本文面向VM部署中的能耗问题,对蚁群算法进行改进,提出基于负载感知的概率选择模型与动态信息素更新规则的VM部署算法(VMACO),算法具体步骤如下:

① 初始化算法各参数,包括VM参数、服务器参数、蚂蚁数量、最大迭代次数和信息素强度等;

② 取一只蚂蚁携带n个VM,置于初始出发点;

③ 根据当前VM资源需求与服务器剩余资源量可用量,通过式(17)计算负载感知路径启发因子;

④ 根据概率选择式(13)计算蚂蚁下一步的运动方向,通过轮盘赌的方式,将VM部署在服务器上;

⑤ 更新服务器剩余资源可用量;

⑥ 重复③～⑤,直到完成所有VM的部署;

⑦ 计算当前蚂蚁的路径长度,即根据式(11)计算服务器集群能耗;

⑧ 根据当前迭代回合数,通过式(22)计算当前信息素强度;

⑨ 通过局部信息素更新式(18),更新路径的信息素值,作为之后蚂蚁的指引;

⑩ 重复执行②～⑧,直到所有蚂蚁都已构造路径解;

3 仿真实验与分析

Cloudsim云计算仿真平台是2009年由澳大利亚墨尔本大学Rajkumar Buyya教授提出的云计算系统仿真工具集,提供了云计算场景下多种虚拟资源分配和应用调度接口[16]。通过该平台,用户不需要运营维护庞大的云计算系统便可以模拟云计算中的各种资源,方便快捷地实现相关仿真实验[17]。

本文在Java环境的CloudSim仿真平台上进行仿真实验。为了模拟真实情况下的计算环境异构问题,服务器类型配置、VM类型配置如表1和表2所示。

表1 服务器节点性能参数Tab.1 Server node performance parameters

表2 VM性能参数Tab.2 VM performance parameters

算法的性能会受到参数影响,为确定参数的取值,本文参考文献[18]进行设置相关缺省值,再采取控制变量法,控制其他系数不变,仅改变待研究的系数,研究该系数对算法性能的影响,确定各个参数的最优取值,当VM数量在100～1 000时,参数综合最优设置如表3所示。其中α为启发因子系数,β为信息素强度系数,ρ为局部蒸发率,Q为信息素强度,Imax为最大迭代次数,Ants为蚂蚁数。

表3 算法参数Tab.3 Algorithm parameters

为验证本文提出的调度算法的性能,在相同环境和条件下将本文提出的调度算法与文献[5]提出的融合蚁群算法、轮询 (Round Robin,RR)算法进行比较。实验中,服务器节点由表1的5种类型组成,每种类型数量为40。每次申请的VM由表2的10种类型组成,每种类型数量相等,VM申请数量由100递增到600,步长为100。为减少实验偶然性的影响,实验都在相同环境下运行10次,并取平均值作为最终结果。

① 算法收敛性对比

在不同VM数量条件下,算法VMACO与ACOSA得到最优解的平均迭代次数如表4所示。因为RR算法属于调度算法中的直接法,故不讨论其收敛性。

表4 算法平均迭代次数Tab.4 Algorithm average iterations

本文提出的VM部署算法VMACO相比ACOSA平均迭代次数减少19.7%,收敛速度更快。

② 资源利用率对比

在不同VM数量条件下,3种算法进行VM初始部署时的服务器平均资源利用率如图3所示,计算方式见式(8)。

图3 平均资源利用率对比Fig.3 Comparison of average resource utilization

由图3可以看出, VMACO平均资源利用率最高。VMACO在VM部署时考虑服务器上各个资源的负载水平,尽量在同一台服务器上安置资源需求不同的VM,使得整个服务器集群平均资源利用率更高。

③ 服务器启动数量对比

在不同VM数量条件下,3种算法进行VM初始部署时所需要启动的最少服务器数量如图4所示。

图4 服务器启动数量对比Fig.4 Comparison of number of servers

由图4可以看出, VMACO服务器启动数量最少, RR最多。VMACO对资源的利用率更高,所启动服务器数更少。

④ 平台能耗对比

在不同VM数量条件下,3种算法进行VM部署时的服务器平台的单位时间能耗如图5所示,计算方式见式(11)。

由图5可以看出,VMACO能耗最低。尽量在服务器上部署资源需求不同的VM,使得资源利用率更高,从而减少所需服务器数,降低服务器集群能耗。

图5 平台总能耗对比Fig.5 Comparison of total platform energy consumption

4 结束语

为降低水下无人平台公共计算环境能耗,本文以最小能耗为目标,建立了一种能耗关键的VM部署模型,设计了基于改进蚁群的VM部署算法来求解该模型,提出了负载感知概率选择模型,改进了蚁群的路径选择;提出了动态信息素模型,优化了信息素更新规则。通过算法对比实验,验证了提出的VM部署算法能够提升平均资源利用率,显著降低公共计算环境的能耗。本文仅考虑VM部署中的静态部署问题,现实情况中VM会根据需要动态销毁与创建,进一步的工作应考虑VM的动态部署问题。