云计算下的蚁群优化算法资源调度研究

2019-07-19杨爱华

通化师范学院学报 2019年8期

杨爱华

云计算是由分布式等发展而来的，依托付费方式为用户提供相应的服务.云计算服务本质在于运用虚拟机计算及其存储资源池进行动态分配等一系列处理，并为用户提供满足QS各项要求的计算及其存储服务.云计算具备高可靠性、自治性等特点，已成为人们处理海量数据的主要技术［1］，它也在不断地改变广大居民对软件的认识及操作熟练性，人们不需要对软件实施维护处理，利用付费的方法就能在互联网上获得所需的保护服务.云就是包含大规模的计算节点，而且这些节点受到计算、宽带等能力的限制，需要分析云计算和蚁群优化算法下的资源调度策略，减少用户数量，找到最合理的虚拟机资源，并快速将用户任务分配给相应的虚拟机，以确保用户在设定的时间内顺利完成任务［2-3］.本次研究中，提出ACO1、ACO2两个资源调度策略，并将其运用到双向蚂蚁机制中，期望依托前向和反向蚂蚁之间展开直接交流，确保实际运行中有效计算资源可以快速发掘出来，并在一定程度上提升使用算法收敛性，确保公司和用户签署服务等级协议SLA.

1 蚁群优化算法的资源调度

1.1 蚁群优化算法概述

蚁群算法（Ant Colony Optimization，ACO）又称作蚂蚁算法，是一种用于在图内找寻最优路径的几率算法［4］.与其他启发式算法相比，这种算法在信息交换积累上更容易进行优化，具有较高的效率.现阶段，大多数蚁群算法中蚂蚁主要由信息素进行交流，而不同蚂蚁间并没有展开直接的交流，因此，算法的收敛性不佳.在考虑云计算与网络环境存在明显差异的前提下，本文提出两个资源调度策略ACO1、ACO2.

在实际生活中，当蚂蚁寻找食物时，如果两只蚂蚁相遇，会利用触角进行交流，基于此，一只蚂蚁会根据另外一只蚂蚁提供的信息快速找到食物.蚂蚁开展资源搜索过程中，会在一定程度上提升蚂蚁相遇处理效率，用来提高算法的收敛性.在各节点预留出一定的存储区，用来保存反向蚂蚁携带的信息，并开启相应的定时器［5-6］.当定时器开展归零操作之前，前向蚂蚁则会快速到达这个节点，判定前向和反向两只蚂蚁已相遇.实施归零处理后，节点可以自动将各项信息进行及时地消除.如果某一个节点在多个时刻会出现多数蚂蚁经过的情况，这些蚂蚁会给出多个可利用的资源，下文采用两种方式进行解决.

①如果一个节点存储区域可以保存相应反向蚂蚁能够提供的消息，当后一蚂蚁经过相应地点，会对原先的信息实施覆盖，并将启动器再次开启.这种方法只是考虑一个可利用的资源，优势在于保存信息所用空间比较小，在求解下一跳转节点概率过程中，所用计算量比较少，不足之处在于保存全部的可用资源信息［7］.②一个节点存储区可以保存多数反向蚂蚁提供的信息，若有反向蚂蚁经过，就会为其启动与之对应的定时器［8］.除此之外，如果包含两个反向蚂蚁来源于相同的可用资源，节点保存后一蚂蚁提供的信息，这种方法的主要优点是能够把所有的可用资源均考虑其中，不足之处则是节点存储空间大，且需要开展大量的计算.

与以上两种方法对应的算法分别是ACO1、ACO2资源调度算法.

1.2 信息素修改

在借鉴其他学者研究成果基础上，通过虚拟机硬件资源对某个节点中的信息素实施判断，主要通过CPU个数m、内存（r）和外存容量（h）、带宽（b）等指标展开.根据下列公式为各参数设定阀值，如果大于这个阀值，则统一采用阀值计算.

先对节点的硬件信息素进行初始化处理：

其中，节点i信息素就是上面各类信息素的带权和，见公式（6）：

信息素实施修改主要由下列两种组成，一种就是对有价值节点的信息素实施修改；另一种是指对反向蚂蚁通过不同节点保存的信息进行修改［9-10］.

如果存在新任务被分配至相对应节点上，CPU利用率等指标会明显增大，这种条件下，信息素随之减小.信息素通过以下公式展开更新处理：

上述式子中，λ代表调节因子；τi(t)代表处于t时刻需要进行计算的节点信息素浓度；τi(t1)则表明有新任务为t1时刻到达i节点显示的信息素浓度.

在任务处于t2时运送完成或者失败，系统的负载会明显减轻.为确保节点上的负载平衡，这种情况下，信息素浓度求解公式为

此时，λ1表示调节因子；τi(t)代表t2时节点上（i）信息素浓度.

如果想要对顺利完成任务的节点进行奖励，可以设法加大这一节点信息素浓度，保障更多前向蚂蚁选取这个节点；当遭遇任务失败的节点，要接受一定的惩罚［11］.根据公式（8），对其添加相应的新因子λ2，变成公式（9），该指标用来表示增加或减少各节点状态下的信息素浓度.

如果任务成功地运行，则有0＜λ2＜1；反之，则为-1＜λ2＜0.

必须注意，随着时间这个指标逐渐推移，在有效节点上的任务数也会逐渐变少，承担的负载更轻，其信息素明显增多.这种状况下，各节点存储的有效节点信息素也随之增加.此时，可以每隔一定的时间，通过下列公式求解相应节点的信息素.

τe(t+1)代表在t+1时各节点开展修改处理后获取有效节点（e）显示的信息素浓度；λ3表明与之对应的调节因子；τe(t)表明在t时各节点存储的e信息素浓度.

1.3 修改任务预计执行时间

在云计算发展背景下，当某个节点可能需要执行多数任务.但云计算会将不同的任务分配至高效率节点上，提升整个云计算性能.在此基础上，构建相应的任务执行时间预测模型，主要功能就是对新任务所用执行时间展开预测，计算公式如下：

ET代表预计新任务Jpredict处于t2时刻估计在j这个节点上的执行时间；此处，通过j运行的任务数代表负载大小；npredict代表t2时刻j的负载表明t0时刻上某个已经完成的任务Jprevious到j，且在j上预计执行所需时间.nprevious代表上一个任务运行状态下的负载指出上一个处于t1对任务Jprevious完成实际所用的执行时间.

因有效节点会跟随运行任务变化有所减少，在有效节点上预计任务顺利完成时间也会明显减少.基于此，每隔相应的时间，可利用以下式子修改不同节点执行任务使用的预计时间.

1.4 前向蚂蚁选取下一跳节点

在前向和反向蚂蚁并未相遇的背景下，根据公式（13）展开计算，挑选其中一个较大概率的节点作为下一跳节点.

若某一节点仅保存一个反向蚂蚁给出的消息，且该蚂蚁i前一跳节点是k，对下一个跳节点进行选取，依次求解Pij、Pik.在Pij内，j则是i需要挑选的下一个跳节点，且j、k并非是同一个节点.根据以下公式求解：

τe表示节点k存储的有效节点e的信息素数值；Ae代表k这一节点中存储e预计执行操作使用时间.依托比较Pij和Pik这两个数值发现，前向蚂蚁会将最大的一个概率节点当作下一跳节点.

当一个节点中保存大量反向蚂蚁给出的信息，需要将多数的有效节点考虑在内.依托定义B(K)、E(K)集合，B(K)则表明前向蚂蚁会选取下个跳节点，这也成为反向蚂蚁经过节点总集合；E(K)表示大多数有效节点组合起来的集合.这种情况下，可以把下一跳节点j划分为不同的类：第一类：j∉Ns，且j∉B(K)，求解式子如下：

第二类节点计算公式为

上述两个式子中选取概率最大者作为下一跳节点.

2 算法仿真实验

为有效验证所用蚁群优化算法的效果，文中采用CloudSim平台实施仿真实验，并将资源调度策略ACO1、ACO2、AS和基于蚁群系统ACS所有时间展开对比分析.

2.1 设计实验参数

整个算法时间复杂度为O(k(m+n)，该式子中，k代表作业个数；O(n)表示将作业置于虚拟机资源上的时间复杂度；O(m)则表示前向蚂蚁找寻资源时间的复杂程度；本算法主要功能在于使前向蚂蚁找寻虚拟机资源使用时间尽量地缩小，确保分配虚拟机整体时间也明显减少.

算法内a～d这四个字母依次代表虚拟机CPU、内存、外存及其带宽的重要性.由于任务分配实施或受到处理器的影响，因此，可以将这四个字母设置为4、2、2、2.a、β依次代表信息素，对需要执行的不同项任务使用时间重要程度展开预计.n主要作用就是用于评估存在多数蚂蚁更合适.通过与之对应的实验，得到最优a、β、n组合.调节因子λ、λ1、λ3都设定为0.2；λ2就是当任务成功或者失败条件下依次取值0.2、-0.2.ρ、ρ1依次取0.4、0.2.Master定时器设定为5 s；虚拟机节点设置200个.在任务大小是500 M，虚拟机处理能力处于200～400 MIPS范围之内，带宽、外存容量依次为1～2 M/s、10～20 G范围中；内存容量设定512 M～1 G.

2.2 统计与分析实验结果

先要提交2 500 M的作业，这个作业反复提交次数为10次，最终得出相应的结果，存在7次在a=1，β、n分别是2、2.5条件下，进行作业调度有效节点时采用的时间最少.随后，挑选多种作业量重复上述环节，从而得出60%时，在a=1，β=2，n=2.5条件下，是作业所用时间最少的任务调度有效节点，这也说明，这种情况下是最优的组合.表1代表作业大小为2 500 M，a、β、n选取不同数值时，资源调度时间发生改变.

表1 资源调度时间变化情况

表2表示在作业大小为2 500 M，设定a=1，β=2，n=2.5的条件下，比较ACO1、ACO2及其与蚂蚁系统AS、蚁群系统ACS对资源调度中使用的时间.

表2 对比不同算法下资源调度时间

根据表2数据可知，ACO1和ACO2资源调度所用时间显著少于ACS、AS这两种算法，分析其原因可知，由于前向蚂蚁对虚拟机资源找寻过程中使用的时间有所减少，导致分配虚拟机整体所用时间缩短.当前向蚂蚁对虚拟机实施寻找时，会在一定程度上加大蚂蚁相遇过程中的交流，在前向与反向蚂蚁相遇这个前提下，前向蚂蚁会依据后向蚂蚁提供的重要节点信息，在上述信息内作出选择，及时找出达到执行作业任务要求的节点.与ACO1算法相比，ACO2算法所用的时间更少，分析发现，是因ACO2这种算法中节点内保存多数有效的节点信息，前向蚂蚁会从以上有效节点中选取最大的发生概率，说明这种方法使用调度时间是最少的.