改进快速稀疏算法的云计算资源负载均衡

李菁

(湖南电子科技职业学院 机械与电子工程分院， 长沙 410000)

0 引言

随着各个领域每天都会出现大量的数据，目前已经进入了大数据时代，传统单机数据处理技术已经不能满足人们对数据处理速度的要求，因此出现了云计算技术[1]。云计算技术将多种类型的设备如存储器、网络终端、大型打印机等进行连接，通过“按需分配”、收费方式提供给用户使用，是一种大数据处理技术[2]。在云计算技术的实际应用中，由于云计算资源不仅数量有限，而且十分宝贵，但是用户的任务规模比较大，如何合理地将云计算资源分配给用户任务、同时保证云计算资源负载均衡十分关键[3]。

针对云计算资源负载均衡问题，全世界各地的研究人员以及高校进行了广泛的研究，出现了许多类型的云计算资源负载均衡方法[4]。云计算资源负载均衡方法可以划分为两种类型，一类是传统方法，一类是现代方法，传统方法主要包括模糊聚类分析算法的云计算资源负载均衡方法、穷举式搜索算法的云计算资源负载均衡方法，当云计算资源负载规模比较少时，可以保证云计算资源负载均衡，用户任务完成的效率高，但是随着云计算资源负载数量增加，其计算复杂度会呈指数形式增长，难以满足用户任务的实时性要求[5,6]。现代方法主要是引进人工智能技术[7-9]对云计算资源负载均衡问题进行求解，如：萤火虫算法、禁忌搜索算法、蜂群优化算法、社会力群智能优化算法，它们首先建立云计算资源负载均衡问题的数学模型，然后采用萤火虫算法、禁忌搜索算法、蜂群优化算法、社会力群智能优化算法进行时求解，找到云计算资源负载最优分配方案，求解速度高，时间短，成为当前云计算资源负载均衡的主要研究方向[10,11]。但是在实际应用中，现代云计算资源负载均衡方法也存在一些不足，如云计算资源的负载分配不均衡，有的资源负载多，有的资源长期处于空闲状态，用户无法分配得到最合理的云计算资源，使得云计算资源浪费十分严重，影响了云计算资源利用率，用户任务不能在规定时间完成[12]。

为了提高云计算资源利用率，保证云计算资源负载均衡，提出基于改进快速稀疏算法的云计算资源负载均衡方法，与其它方法进行了云计算资源负载均衡仿真实验结果表明，本文方法提高了云计算资源利用率，能够保证各个云计算资源之间的负载均衡，相对于其它云计算资源负载均衡方法，本文方法具有十分明显的优越性。

1 云计算资源负载均衡问题描述

1.1 云计算系统

在一个云计算系统中，包括大量的云计算资源，每一种云计算资源的性能各异，因此具有典型的异构特性，由于云计算系统主要针对大规模数据的处理，通常采用Map/Reduce的数据处理模式，首先服务器节点资源对一个大规模用户任务进行细化和分配，然后每一个云计算资源得到相应的任务，并执行任务，最后对每一个云计算资源任务完成结果进行融合，得到大规模用户任务执行结果。在云计算系统工作过程中，要建立2个级别映射，具体为：

(1)建立服务器与计算资源之间的映射关系。

(2)建立云计算资源和用户任务之间的映射关系。

1.2 云计算资源负载均衡的数学模型

云计算资源负载均衡调度定义：根据一个云计算资源负载调度策略，结合云计算资源的能力，给每一个云计算资源分配一定数量的用户任务，在满足用户任务完成要求的前提上，保证云计算资源之间负载分配均衡，使云计算资源利用率达到最大。设用户任务集合为：T={t1,t2,…,tm}，其中m表示任务数量，云计算资源集合为：R={r1,r2,…,rk}，其中k表示云计算资源数量，而一个云计算资源主要包括CPU、内存、网络带宽等具体物理设备，物理设备组成的集合为：D={d1,d2,…,dn}，这样可以得到式(5)。

S={T,R,D,Mtr,Mrd}

(1)

式中，Mtr表示云计算法资源和用户任务之间联系；Mrd表示云计算资源和具体物理设备间的联系。

设ti被分配到rj，rj使用dk执行ti，任务ti在dk的执行时间为ETC(ti,dk)，那么可以得到式(2)。

ETCkn=ETC(tiMtr,dj)

(2)

Start(dk)为物理设备dk开始执行任务时间，ti完成时间的计算式为式(3)。

F(tiMtr,dk)=Start(dk)+ETC(tiMtr,dk)

(3)

物理设备dk上任务完成时间之和的计算式为式(4)。

(4)

式中，cik的取值方式如式(5)。

(5)

T={t1,t2,…,tm}完成总时间计算式为式(6)。

(6)

云计算资源负载均衡问题的求解实际上就是找到一个用户任务完成时间最少的云计算资源分配方案，即式(7)。

(7)

2 改进快速稀疏算法的云计算资源负载均衡方法

2.1 云计算任务调度信息流的稀疏表示

当前云计算任务调度信息流通常采用分块细化方式进行，这样会使得数据之间存在一定的空余，影响云计算任务调度效率，云计算任务调度信息流模型可以表示为式(8)。

(8)

式中，p表示任务的阶数；ai(t)表示分块参数为式(9)。

ai(t)=-2m(t)cos(θ(t))

(9)

式中，m(t)表示正态随机分布，θ(t)表示均匀分布。

采用改进快速稀疏算法对云计算任务调度信息流进行分解，得到不同大小的云计算任务，这样便于分配最合理资源。

2.2 自适应遗传算法求解云计算资源负载均衡问题

由于当前云计算资源负载均衡问题求解算法，如蜂群优化算法，存在收敛速度慢，难以找到全局最优的云计算资源负载均衡方案，因此本文引入自适应遗传算法对云计算资源负载均衡问题的数学模型进行求解。自适应遗传算法主要通过交叉算子和变异算子不断产生新的个体，以保证种群的多样性，使种群搜索方向朝着问题的全局最优解方向进行搜索，进化初期，交叉概率(Pc)的取值相对较小，变异概率(Pm)的取值相对较大，加快算法的搜索速度，具体方式为式(10)、式(11)。

(10)

(11)

进化后期，Pc的取值相对较大，Pm的取值相对较小，提高算法的搜索精度，具体为式(12)、式(13)。

(12)

(13)

式中，fmax和favg为最大适应度值和适应度平均值，Pc0和Pm0分别表示交叉概率和变异概率的初值。

3 改进快速稀疏算法的云计算资源负载均衡方法工作步骤

(1)建立云计算系统，确定各种云计算资源的数量以及各种云计算资源的处理能力。

(2)收集用户任务，并采用改进快速稀疏算法对云计算任务调度信息流进行分解，得到不同大小对云计算任务。

(3)根据云计算任务、云计算资源以及物理设备之间的关系，以任务完成时间最少为目标建立云计算资源负载均衡问题的求解数学模型。

(4)设置自适应遗传算法，如种群中的个体数量等。

(5)初始种群，种群中每一个个体与云计算资源负载均衡问题的一个解相对应，并根据适应度函数值对个体进行排序，确定当前最优个体。

(6)通过选择、交叉、变异操作产生新的种群，并根据适应度函数值对新种群个体进行评价，并采用当前最优个体替代历史最优个体。

(7)进化代数增加。

(8)如果当前进化代数等于最大进化代数，那么，根据当前最优个体得到云计算资源负载均衡问题的最优解，不然继续执行步骤(6)～(7)。

4 云计算资源负载均衡方法的性能验证

为了分析改进快速稀疏算法的云计算资源负载均衡方法的性能，选择文献[10]和文献[11]的云计算资源负载均衡方法进行对比实验。

3种云计算资源负载均衡方法的任务完成时间如图1所示。

图1 云计算资源负载均衡方法的任务完成时间

对图1的云计算资源负载均衡方法的任务完成时间进行分析可以知道，改进快速稀疏算法的云计算资源负载均衡方法的任务完成时间最短，其次为文献[11]的云计算资源负载均衡方法，任务完成时间最长的是文献[10]的云计算资源负载均衡方法，这表明改进快速稀疏算法可以为用户任务分配到更优的云计算资源，提升了用户任务完成的速度。

3种云计算资源负载均衡方法的资源负载分配结果如图2所示。

图2 云计算资源负载的分布结果对比

对图2云计算资源负载均衡方法的资源负载分配结果进行对比和分析可知，改进快速稀疏算法的云计算资源负载十分均衡，没有出“过负载”或者“空负载”现象，而文献[10]和文献[11]的云计算资源负载均衡方法均出现了“过负载”或者“空负载”现象，这表明改进快速稀疏算法提高了云计算资源利用率，每一个云计算资源都可以分配得到了最合理数量用户任务，提高了云计算系统的处理能力。

5 总结

为了解决当前云计算资源负载分配不均衡、资源利用率低等难题，提出基于改进快速稀疏算法的云计算资源负载均衡方法。仿真实验结果表明，与其它云计算资源负载均衡方法相比，改进快速稀疏算法可以提高云计算资源的利用率，使得云计算资源负载分配更加均衡，加快了云计算任务完成的速度，具有十分广泛的应用前景。