基于模糊聚类的自适应QoS粒度划分方法

摘要

本发明公开了一种基于模糊聚类的自适应QoS粒度划分方法，针对云计算面向用户，按需分配资源的要求，本发明提出了一种综合考虑用户满意度和资源利用率的用户任务预处理分类方法，该方法能根据用户任务的QoS需求，采用模糊聚类的算法对用户需求进行分类，这为之后的资源的分配提供了一种参考方法。

说明书

技术领域

本发明涉及任务调度的技术领域，特别涉及一种基于模糊聚类的自适应QoS 粒度划分方法。

背景技术

云计算环境下，一方面用户数量的日益增加，用户QoS需求的多种多样， 造成了云用户的任务在数量和类型两方面的快速增长，这使任务调度问题变得 异常复杂；另一方面，具体的任务调度策略成为云环境下任务调度好坏的决定 性因素，因此这些年来，云计算的调度问题吸引了大量专家学者对其进行深入 的研究。

云计算的任务调度的QoS需求包括截止时间、费用、可靠性、安全性等诸 多内容。JohannT等人提出了一种基于粒子群优化的任务调度和资源分配方法， 该方法考虑任务的截止时间和费用两个约束条件。LiBing等人提出了一种基于 QoS等级划分的任务调度模型；对于QoS要求较低的应用任务，采用一种优化 的Chord算法对其进行调度，确保任意QoS约束要求的应用任务均可以得到一 个满意的任务完成时间；该策略具有很好的实用性，且其资源利用率明显优于 传统方法。针对不同的QoS需求，有人提出基于贪心算法的任务分类模型，对 不同的用户采取不同的任务调度策略，同时利用公平性评判函数对调度策略进 行调整，这样能更好的满足用户的QoS需求。综上所述QoS需求在用户任务调 度策略中扮演十分重要的角色，如何对不同的QoS需求进行合理的划分成为调 度策略能否成功的关键因素。

为了解决上述问题，对QoS需求划分合理的话，不但能提高云资源的利用 效率，而且能提高云用户的满意度；如果对QoS需求粒度划分过小，容易造成 资源利用率下降；如果对QoS需求粒度划分过大，容易造成用户满意度下降。 本发明提出的基于模糊聚类的自适应QoS粒度划分方法能很好解决粒度的划分 问题。

发明内容

本发明目的在于提供一种基于模糊聚类的自适应QoS粒度划分方法，该方 法利用模糊聚类算法对多属性特征的任务进行粗粒度的划分，然后不但减小粒 度阈值，直到资源利用率和用户满意度达到一定程度的折中，进而缓和两者之 间的矛盾。

具体地说，本发明是采用以下的技术方案来实现的：基于模糊聚类的自适 应QoS粒度划分方法，其特征在于，利用模糊聚类算法对多属性特征的任务进 行粗粒度的划分，然后不断减小粒度阈值，直到资源利用率和用户满意度达到 一定程度的折中，进而缓和两者之间的矛盾，包含如下步骤：

步骤1：根据用户的任务模型和QoS模型建立任务的m×n样本矩阵，

其中，m代表任务的数目，n代表任务的维数，假设两个集合G＝(G₁,...,G_c)和 V＝(v₁,...,v_c)，如果满足以下两个条件：

$\underset{i=1}{\overset{c}{\cup }}{G}_i=X,G_i\cap G_j=\Phi (i\ne j),$那么称G＝(G₁,...,G_c)为X一个划分；

步骤2：对样本矩阵参数进行规范化，

$v^{\prime }=\frac{v-{\min }_A}{{\max }_A-{\min }_A}(new\_{\max }_A-new\_{\min }_A)+new\_{\min }_A,$其中min_A、max_A分别为属 性A的最小值和最大值，公式将A的值v映射到区间[new_min_A,new_max_A]中的v′；

步骤3：初始化粒度值N以及初始的N个聚类中心

步骤4：对于每个样本任务分配到最近的聚类中心，

根据公式来分配样本到最近的聚类中心；

步骤5：更新相应N个类别的聚类中心，

根据公式来重新计算新的聚类中心；

步骤6：直到样本矩阵收敛，转到步骤7，否则转到步骤4，

其中，如果或收敛，则样本矩阵收敛；

步骤7：根据评价函数确定N值，如果N值过大，则减少N值，转到4， 否则转到8，

根据评判函数来判断QoS粒度是否合适；

步骤8：输出划分之后的任务矩阵。

基于模糊聚类的自适应QoS粒度划分方法，其特征进一步在于，所述步骤 3中粒度值N以及N个聚类中心是将样本随机分成N类，把每类的重心作为初 始的聚类中心。

本发明的有益效果如下：1、本发明缓和了用户满意度和资源利用率之间的 矛盾。2、本发明提高了任务调度的效率。

附图说明

图1是本发明的方法流程图。

具体实施方式

如图1所示，本发明提出了一种基于模糊聚类的自适应QoS粒度划分方法， 其包括如下步骤：

1、建立任务的样本矩阵

根据任务的QoS要求建立一个m×n的样本矩阵，其中m代表任务的数目， n代表任务的维数。假设两个集合G＝(G₁,...,G_c)和V＝(v₁,...,v_c)。如果满足以下两个 条件：

$\underset{i=1}{\overset{c}{\cup }}{G}_i=X,G_i\cap G_j=\Phi (i\ne j),$那么称G＝(G₁,...,G_c)为X一个划分。

2、样本的规范化

对样本数据的每个属性进行最小-最大规范化处理，也即：

$v^{\prime }=\frac{v-{\min }_A}{{\max }_A-{\min }_A}(new\_{\max }_A-new\_{\min }_A)+new\_{\min }_A,$其中min_A、max_A分别为属 性A的最小值和最大值，公式将A的值v映射到区间[new_min_A,new_max_A]中的v′。 规范化可以帮助防止具有较大初始值域的属性与具有较小初始值域的属性相比 权重过大。

3、初始化粒度值N以及初始的N个聚类中心

初始化N的取值。

初始化N个聚类中心

4、对于每个样本任务分配到最近的聚类中心

首先计算每个样本到N个聚类中心的附属函数

其中表示x_k和之间的欧式距离。

而m是大于1的一个整数。

根据附属函数得到每个样本相对于聚类中心的附属程度。然后找到最优的 划分U使目标函数最小化：

$J_0(U,V)=\underset{i=1}{\overset{N}{\Sigma }}\underset{k=1}{\overset{m}{\Sigma }}{u}_{ki}D(x_k,v_i),$其中U∈U_f，

$U_f=\{U=\left(u_{ki}\right):\underset{j=1}{\overset{c}{\Sigma }}{u}_{kj}=1,1\le k\le N;u_{ki}\in [0,1],1\le k\le N,1\le i\le c\}.$等价于 $\bar{U}=\arg \underset{U\in U_f}{\min }{J}_{fcm}(U,\bar{V}).$

5、更新N个类别的聚类中心

新的聚类中心：

根据附属度函数和样本矩阵计算新的聚类中心，也就是寻找最 优的V值使：

$\bar{V}=\arg \underset{V}{\min }{J}_{fcm}(\bar{U},V)$

6、样本矩阵收敛

如果或收敛，则样本矩阵收敛。

对于收敛，也就是说

对于一个很小正值ε，满足其中是本次迭代附属函数向量， 是上次迭代附属函数向量。

对于收敛，也就是说

对于一个很小正值ε，满足其中是本次迭代聚类中心向量， 是上次迭代聚类中心向量。

7、评价函数的确定

本发明采用误差平方和聚类准则来作为评价函数，若N_i是第i聚类Γ_i中的 样本数目，m_i是这些样本的均值，即

$m_i=\frac{1}{N_i}\underset{y\in {\Gamma }_i}{\Sigma }y,$

把Γ_i中的各样本y与均值m_i间的误差平方和对所有类相加后为

$J_e=\underset{i=1}{\overset{c}{\Sigma }}\underset{y\in {\Gamma }_i}{\Sigma }\left|\right|y-m_i|{|}^2,$

对于不同的聚类，J_e的值是不同的，使连续两次的J_e差值满足一定误差 就结束。

虽然本发明已以较佳实施例公开如上，但实施例并不是用来限定本发明的。 在不脱离本发明之精神和范围内，所做的任何等效变化或润饰，同样属于本发 明之保护范围。因此本发明的保护范围应当以本申请的权利要求所界定的内容 为标准。