基于模糊聚类分析的云计算负载平衡策略

文章编号:1001-9081(2012)01-0213-05 doi:10.3724/SP.J.1087.2012.00213

摘 要:如何实现资源访问的负载平衡成为云计算实施的关键问题之一。基于云计算环境的特点，改进了模糊聚类算法，将粒子群优化算法与模糊C均值聚类算法融合，提高算法正确率。将改进后的聚类算法应用于对各个计算节点的输入输出(I/O)及中央处理器(CPU)利用率的分析,得到对于负载度的分类，并以此为依据判断需要迁移任务的节点，进而实现负载平衡。实验结果表明无论是在UCI机器学习库或是针对提出的负载平衡机制环境下,改进的模糊聚类算法在算法的准确率方面均优于传统算法10%以上，且在算法稳定性方面亦优于传统算法。

关键词:云计算；模糊聚类；负载平衡；粒子群优化算法

中图分类号: TP18; TP311.52 文献标志码:A

Abstract: It plays an important role in realizing cloud computing to implement the load balance of accessing resources. Therefore, based on the characteristics of cloud computing environment, an improved fuzzy clustering analysis algorithm was proposed in this paper. Furthermore, integrating Particle Swarm Optimization (PSO) algorithm with fuzzy C-means algorithm improved the algorithm accuracy. Then, using the improved fuzzy clustering algorithm in analyzing utilization ratio of I/O and Central Processing Unit (CPU) of all computing nodes, each node was divided into an affirmatory collection. And it represented its load level, as a basis for judging the node which needed to transfer tasks, so as to achieve the load balance. According to the experimental results, in terms of algorithm accuracy, no matter what is in the UCI machine learning repository, or for the proposed load balancing mechanism, the improved fuzzy clustering algorithms reached the traditional ones by 110%. Besides, it surpasses the traditional one in the stability of the algorithm.

Key words: cloud computing; fuzzy clustering; load balance; Particle Swarm Optimization (PSO) algorithm

0 引言

在云计算环境下，大量用户对系统提出请求时，均希望可以在短时间内得到响应,此时对任务的分配显得尤为重要。应尽可能调整每个节点的计算量，使得整个系统能处于均衡状态［1］，这就是负载平衡策略所要完成的最根本的任务。现有的负载平衡算法主要可以分为两种：一种是预测法；另一种是实测法。

1)预测法。指通过对计算节点以前的负载情况的学习，预测该计算节点之后的负载状况。文献［2］中，作者利用了基于误差反向传播（Back Propagation, BP）算法的人工神经网络的方法对计算节点的负载状况进行预判，从而得到下一时刻该节点的负载状况。在基于模拟退火遗传算法的网络负载平衡算法［3］研究中，作者利用了模拟退火遗传算法对计算节点的负载状况进行预判，从而得到下一时刻该节点的负载状况。文献［4］中，作者提出了一种基于随机延迟论的层次结构负载平衡策略，这个策略的优点在于应用通信优化的层次结构减小负载平衡开销，并且还将广义神经网络理论模型应用到了节点计算速率以及通信介质的随即延迟上。但是作者提出的这种负载平衡策略还不能解决多对多的通信，并且系统的容错性也较差。上述文献中的预测算法虽然在一定程度上提高了网络资源利用率，提高了网络负载平衡的能力，但是这些算法都需要很多人为设定的参数，比如交叉、变异概率等，且一旦系统资源发生重大变化，则需要重新训练。

2)实测法。指通过直接或间接调用系统函数或访问注册表来测量节点负载状况。文献［5］在分析了分组到达率和服务率关系的基础上，提出了一种具有自适应、并发控制能力的动态负载均衡算法“加权时序动态算法”。该算法可以对权重进行自动调整，负载平衡算法比传统的循环方法好。但是由于网络数据的突发性，当取得到达率和带宽的值之后，权重计算的时间间隔该如何设定在这篇文章中并没有涉及，计算的时间间隔太短会造成系统忙碌，太长则失去了公平性。文献［6］在研究了负载平衡中产生额外开销的基础上，给出了一个移动负载的粒度公式，当需要移动时才开启负载平衡，该算法使用过去一段时间的旧值和大概估计值，没有考虑到一段时间内的变化情况。文献［7］提出了“二分网络”平衡算法，能适用于大多数条件下的负载平衡，但如果任务无限可分或者平衡过程中不断产生新任务时，该算法无法处理。文献［8］提出了一种具有双适应度的遗传算法,通过此算法寻找总任务完成时间较短的调度结果。

在负载平衡系统中,亟须解决的问题之一是确定计算节点的负载轻重,模糊聚类算法可以很好地解决此问题。文献［9］提出了一种基于区间直觉模糊集(Interval-Valued Intuitionistic Fuzzy Set, IVIFS)的C均值聚类算法。它使用IVIFS的欧氏距离,构造聚类的目标函数，再根据拉格朗日乘数法得出聚类迭代公式。文献［10］提出了一种基于熵正规化的模糊C均值（Fuzzy C Means, FCM）聚类算法。然而这两种算法的收敛速度都过慢且正确率不高。

本文针对以上算法的不足，采取了基于改进的FCM算法的负载平衡算法，提高了算法的收敛速度，同时减少了人为设定参数使得结果不确定这一问题。此算法通过调用系统函数获取节点的关于负载状况的各种特征指标，在短时间内完成对迁移策略的计算，可以有效避免在较长一段时间内负载的变化。

1 基于模糊聚类的负载平衡系统

1.1 云计算体系结构

通用云计算体系结构如图1所示。

云用户端是用户与系统交互的媒介，用户通过浏览器定制服务并对权限内的服务进行操作。服务目录是用户在取得权限后形成的可操作的服务列表。管理系统和部署工具的功能是对用户进行授权、认证、登录等管理,并管理可用计算资源和服务，接受用户请求，根据用户请求转发相应程序，动态分配、调度、回收资源。资源监控是对云系统内的资源使用状况进行监控，完成节点同步配置、负载均衡配置和资源控制，以确保资源的合理分配。服务器集群是整个云计算的核心。它是由管理系统管理的，专门用来处理大运算量的计算。整个运作流程是：用户通过云用户端登录系统获取权限，从列表中选择所需服务，请求通过管理系统调度相应资源，通过部署工具分发请求、配置Web应用。最后交由服务器集群进行计算。

1.2 负载平衡模型

根据上述云计算体系结构，本文将针对资源监控，把负载平衡系统分成5个模块，如图2所示。

它们分别由信息采集模块、消息处理模块、推理机、规则库和数据库构成信息处理模块部分；其余4部分分别是协调策略、负载平衡算法、通信模块、迁移策略。它们的处理过程是：信息采集模块采集云内节点的各个资源使用状况信息并将此信息提交给消息处理模块，消息处理模块对采集来的信息进行量化处理，得到推理机能够识别的信息类型，推理机根据规则库中的相关规则信息推断系统内节点的负载，并将得出的节点负载状况信息存储于数据库中，协调模块从数据库中选出需要执行负载平衡的节点，并通过负载平衡算法模块执行负载平衡决定，通过迁移策略得到迁移的作业数量。通信模块具体对各个服务器发出负载均衡指令。

1.3 信息处理模块

1.3.1 信息采集

调用各个计算节点系统内部函数测得该计算节点的负载信息，如I/O、CPU利用率等。由于是在云计算环境下,计算节点负载状况会实时更新。所以采集信息的时间间隔取泊松分布函数（泊松分布适用于描述单位时间内随机事件发生的次数）：

P(X=k)=e-λλkk!; k=0,1,2,…

其中λ为系统单位时间内测量负载信息的平均发生概率。此参数可以根据实际应用背景测试选取适当值。

1.3.2 消息处理

将信息采集模块采集回来的数据在消息处理中利用极差规格化公式进行规格化处理（因极差规格化计算相对简单，且区分度好），使得采集的数据变成推理机可推理的数据。具体做法如下。

用uij代表第i个计算节点的第j个特性指标。

极差规格化公式如式(1)所示：

uij′=uij-mjMj-mj； i=1, 2, …, n， j=1, 2, …, m(1)

其中：

Mj=max(u1j,u2j,…,unj)(2)

mj=min(u1j,u2j,…,unj)(3)

其中：i=1,2,…,n； j=1,2,…,m。

1.3.3 规则库

规则库提供聚类算法，使推理机根据此算法算出聚类中心和分类结果。因而算法的优劣在一定程度上会影响到推理机是否能合理地分析当前各个节点的负载状况。原有的C均值聚类算法由于存在对初始值敏感和容易陷入局部最优解的缺陷，利用粒子群优化(Particle Swarm Optimization, PSO)算法的优化搜索能力对原有的C均值聚类算法进行改进，使得问题的全局最优解的寻找与初始值的选取无关。改进的C均值聚类算法如下。

设所需分类的节点的集合为U={u1,u2,…,un}。每一个ui均有m个特性指标。每个特性指标均与该节点的负载状况相关联，相应的特性指标矩阵为：

u11u12…u1mu21u22…u2mun1un2…unm(4)

将节点集U分成5类后，其5个聚类中心向量构成的矩阵为：

V=V1V2V5=v11v12…v1mv21v22…v2mv51v52…v5m(5)

在PSO中的3此处为3个关键点，而后面却列出4个，是不是论述有误，请作相应调整。个设计关键点如下。

1)个体确定与粒子编码。

聚类算法的关键是确定聚类中心，因此选取聚类中心为种群中的个体。粒子采用实数编码的方式，编码长度为5mm是变量？还是单位？请明确。是变量。

2)目标函数。

C均值聚类算法设定的目标函数如式(6)：

J(R,V)=∑nk=1∑ci=1(rik)2uk－Vi2(6)

当求得的模糊分类矩阵R及聚类中心矩阵V，可使目标函数达到极小值时,此时的V即为最优聚类中心矩阵，R为最优模糊分类矩阵。根据R可得出具体分类情况。式(6)中uk－Vi表示对象uk与第i个聚类中心向量Vi的距离。其计算公式如式(7)：

uk－Vi=(∑mj=1(ukj－uij)p)1p; p≥1(7)

因为在PSO中一般取适应值最大值所对应的解为最优解，所以将原目标函数的负数定义为适应值函数,即：

JPSO(R,V)=－∑nk=1∑ci=1(rik)2uk－Vi2(8)

3)速度位移更新机制。

速度位移更新机制决定了算法的收敛速度和精度。原始的速度位移公式收敛速度较慢，所以本文引入了惯性权重ω,速度位移公式如下：

vi+1=ωvi+c1r1(pi－si)+c2r2(g－si)(9)

si+1=si+vi(10)

ω=ωmax－iter×(ωmax－ωmin)/itertotal(11)

其中：c1和c2为正学习因子，r1和r2为0到1之间均匀分布的随机数，pi是当前该粒子的最优位置，g为全局最优位置，iter为当前迭代次数，itertotal为累计迭代次数。

终止条件

①最优解对应的目标值保持不变或变动小于阈值ε；

②迭代次数已达到之前设定的最大迭代次数。

以上两个条件满足其一即可。

迭代自组织数据分析(Iterative Self-Organizing Data Analysis Technique, ISODATA)迭代算法具体步骤如下。

1)对算法参数赋值。

2)在样本各属性值的范围内，按照编码原则随机生成初始种群，每个粒子代表各类的聚类中心。

3)根据目标函数计算初始种群中个体的适应值。

4)计算粒子的速度并通过速度位移公式更新粒子位移，iter=iter+1。

5)计算种群中的个体适应值，若满足终止条件，则算法结束；否则转4）。

对于聚类效果检验有两种方法。

1）利用分类系数进行检测。

分类系数：

Fc(R)=1n∑nk=1∑ci=1r2ik(12)

当R∈McMc是矢量、向量或矩阵吗？请明确。时，Fc(R)=1。因此Fc(R)越接近于1效果越好。

2）利用平均模糊熵进行验证。

平均模糊熵：

Hc(R)=－1n∑nk=1∑ci=1rikln rik(13)

当Hc(R)越接近0效果越好。

1.3.4 推理机

根据规则库中的规则对各个计算节点进行聚类操作，并分析所得到的聚类结果。对得到的聚类中心矩阵，将其各项指标进行综合评定。对于聚类中心矩阵中元素的最大值，无论其属于哪项指标，所对应的行向量即为任务重的分类,依次取第二大的元素对应的行向量为任务较重的,依次类推直到这五类全部被分完为止。其中若遇到分类依据的这个元素对应的行向量已被分配,则依次寻找下一个最大元素。最后将这五类行向量按照负载重、较重、中、较轻和轻的顺序重新排列，以便进行接下来的操作。

1.3.5 数据库

数据库负责将推理机分好的五类数据分别记录到数据库不同的位置中。数据库采取循环队列的方式记录。总共有五个队列，分别记录负载重、较重、中、较轻和轻的节点。

2 仿真分析

实验1 为了测试本文提出的算法性能，本文从UCI机器学习数据库中选取了Iris和Wine数据集进行性能实验。将原始的FCM算法与本文提出的改进后的算法进行对比。Iris是由150个4维向量组成的，它们平均地分配到3种类别当中。Wine由178个13维向量样本组成，它也分为3类，其中每类分别包含59,71,48个向量。对于这两种方法分别做10次实验，最终取这10次结果的平均值作为本次实验的最终结果。

实验分析 根据对Iris和Wine数据集进行的实验，发现本文提出的改进后的FCM算法在正确率方面明显优于传统的FCM算法。由于传统FCM算法使用下降梯度法，算法容易陷入局部最优。根据对最优值方差的比较发现传统的FCM算法最为不稳定，对初值给予一个微小的扰动即对聚类结果产生较大影响。对比文献［9-10］发现，对于Iris数据集而言，本文改进的算法比文献［9］中提出的算法在运算速度方面有大幅提高，与文献［10］相比在正确率及运算速度方面都只有小幅提升；针对Wine数据集，本文提出的算法比文献［10］中的算法在正确率方面有很大提高。算法稳定性也相对较强。所以综合评定以上各算法发现,本文提出的改进算法相对于其他三个算法而言更适合于本文提出的负载平衡机制。当应用在本文提出的负载平衡机制中时，由于传统FCM算法正确率低，算法不够稳定，会导致需要采取负载平衡的节点选取不正确，影响负载平衡效果。故不适合于此机制。文献［9］不适合用于此机制的一个最为重要的原因是，此算法的运行时间过长，若用于此机制势必会造成负载平衡时间过长，不利于系统对用户提供优质服务。文献［10］是由于对需聚类的数据有些敏感，类似于Iris数据集，此算法的聚类效果较好。但对于类似于Wine的数据集，此算法的正确率较低。故文献［10］中的聚类算法也不能适用于本文提出的负载平衡机制。在稳定的系统当中，训练时间所占系统运行时间往往很少。因此，聚类的正确性对提高系统的运行效率就显得更为重要。

实验2 结合本文所述的负载平衡机制为此算法选取服务节点的特性指标。为了实验方便，这里设计算节点有20个。其中每个节点的特性指标有2个：一个是I/O利用率；第二个是CPU利用率。现在将这20个计算节点按前述方法分成5类，这5个聚类中心向量构成的矩阵为：

V=V1V2V5=v11v12v21v22v51v52(14)

文献［12］根据问题的不同介绍了一些选取参数的方法，根据文中的规则，对应本文的问题选取初始参数如表2所示。

经过文献［11］改进C均值聚类后，各个样本的隶属度如图5所示。由此可得计算节点分类集合，如表4所示。

经过本文改进C均值聚类后，各个样本的隶属度如图6所示。由此可得计算节点分类集合，如表5所示。

分别对原始算法及本文改进后的算法进行聚类效果检验，结果如表6所示。

实验分析 根据本文提出的负载平衡机制对以上20个计算节点进行分类实验，利用分类系数对实验结果进行判断，发现改进后的F(R)比原始的聚类算法更接近于1，并且平均模糊熵H(R)比原始的聚类算法在高一个数量级上更接近于0。更为直观的是从模糊分类矩阵上看，改进后的聚类算法比原始算法在隶属度在50%附近的节点减少了，从而使得分类不明显的节点减少，进而有可能分类错误的节点也随之减少。所以改进的聚类算法取得了较好的结果，对协调模块挑出需要执行负载平衡的节点即任务重的节点提供了更好的依据。另外，迁移策略需要根据聚类中心的值以及事先设定的阈值确定需要迁移的作业数量，所以聚类中心精确度的提高在一定程度上提高了作业迁移数量的准确性，避免无谓的迁移造成系统响应时间延长。相对于作业迁移的时间（100个作业使用虚拟机之间相互独立的静态调度算法平均需要600~700ms完成），此算法所花费的时间是在几个毫秒以内，所以是在合理的可忍受的范围内。

使得整个负载平衡过程变得更加有效还要得益于以下这两方面。

1)聚类算法分类的合理性使得此负载平衡机制较为灵活，当整体节点计算任务都比较重的时候，可以将任务较重的一类同重的一类一起调入到协调模块中，之后再一起进行任务迁移。而在整体节点计算任务不是很重的情况下，只需要将任务重的一类进行负载平衡即可。

2)在现实的负载平衡系统内,计算节点的变更也是不容忽视的问题，此时，若是对每一次改变都直接对整个系统进行训练则会严重影响该系统的性能。可以将新加入的小样本组织成一个整体，运用本文提出的方法进行训练,将训练好的小样本整合到整个系统中，与整个系统一起参与计算。

3 结语

本文提出了一种在云计算环境下基于模糊聚类分析的负载平衡策略，此策略可以满足不同类型的请求，虽然改进的FCM算法迭代次数比原始算法要多，但由于它分类的精确度比原始的高，使得系统迁移任务的正确率也相应提高，根据文献［13］可知造成系统浪费的最关键因素是任务迁移。所以在此策略的协调下，此系统可以在尽可能短的时间内将所有请求处理完成，不会造成系统资源浪费。在本文所设计的系统中，当计算节点发生变化的时候，可采用小样本训练方法对变化部分进行处理，以加快训练速度。此外，虽然改进的FCM算法仍需要设定参数，但由于这些参数已根据相关文献得到了确定的数值，所以解决了预测算法的不足。数据采集的时间间隔对负载平衡的系统性能和分类的准确性有比较大的影响，本研究的后续工作主要集中在基于负责平衡的实际调度实现数据采集时间间隔的动态调节。

参考文献:

[1]

GANNON D. Head in the clouds ［EB/OL］. ［2011-04-05］. www.省略/uidfinder/10.1038/449963a.

[2]

张少辉.基于BP算法的动态负载平衡预测［D］.开封：河南大学，2009.

[3]

易辉.基于模拟退火遗传算法的网络负载平衡算法研究［D］.武汉：武汉理工大学，2006.

[4]

ZHENG G. Achieving high performance on extremely large parallel machines: Performance prediction and load balancing ［D］. Illinois: University of Illinois at Urbana Champaign, 2005.

[5]

BRYHNI H, KLOVNING E, KURE O. A comparison of load balancing techniques for scalable Web servers ［J］. IEEE Network, 2000, 14(4): 58-64.

[6]

李冬梅，施海虎.负载平衡调度问题的一般模型研究［J］.计算机工程与应用,2007,43(8):121-125.

[7]

WU RONGTENG, SUN JIZHOU, CHEN JINYAN. Parallel execution time prediction of the multitask parallel programs ［J］. Performance Evaluation, 2008, 65(10): 701-713.

[8]

李剑锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用,2011,31(1):184-186.

[9]

WANG ZHOUJING, LI K W, WANG WEIZE. An Approach to multiattribute decision making with interval-valued intuitionistic fuzzy assessments and incomplete weights ［J］. Information Science, 2009, 179(17): 3026-3040.

[10]

KANZAWA Y, ENDO Y, MIYAMOTO S. Fuzzy C-means algo-rithms for data with tolerance based on opposite criterions ［J］. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, 2007, E90-A(10): 2194-2202.

[11]

刘坤朋，罗可.改进的模糊C均值聚类算法［J］.计算机工程与应用,2009,45(21):97-98.

[12]

HASHEMI A B, MEYBODI M R. A note on the learning automata based algorithms for adaptive parameter selection in PSO ［J］. Applied Soft Computing, 2011, 11(1): 689-705.

[13]

刘振英,方滨兴,胡铭曾,等.一个有效的动态负载平衡方法［J］.软件学报,2001,12(4):563-569.

收稿日期:2011-07-11;修回日期:2011-09-15。

基金项目:

中央高校基本科研业务费专项(GK361001)。

作者简介:

姚婧(1987-),女,陕西西安人,硕士研究生,主要研究方向：智能计算； 何聚厚(1972-),男,陕西西安人，副教授,博士,主要研究方向：网络安全、信息对抗、网络与远程教育。