﻿ 面向云数据中心资源均衡分配需求的聚类调度算法研究
 上海理工大学学报  2020, Vol. 42 Issue (4): 404-410 PDF

Clustering scheduling algorithm for resource allocation requirements of cloud data centers
XU Yuting, CHEN Shiping
School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Aiming at the problem of low resource utilization and high energy consumption in cloud data center, a resource balancing scheduling strategy based on the resource demand difference was proposed. Based on a package-cluster framework model, the packages with large differences in resource requirements were clustered an improved k-means algorithm using the distance metrics related to resource requirements. The resources were used as the distance between packages and clusters. In the process of resource allocation, the package was mapped into clusters in a centralized manner, thereby the number of clusters used could be reduced. The experimental results show that under the concept of package-cluster framework, the improved k-means clustering algorithm based on the difference of resource requirements can optimize the packet clustering step. The resource scheduling algorithm presented can improve the utilization of various resources and reduce the energy consumption in the cloud data center. The algorithm is of effectiveness and scalability.
Key words: data center     package-cluster framework     k-means algorithm     resource allocation

1 传统的k-means算法

2 包聚类算法 2.1 改进的k-means算法初始值选定

a. 集合中2个需求差异最大的包之间的距离L。现假设集合中有点 $i:({x_{i,1}},{x_{i,2}})$ $j:({x_{j,1}},{x_{j,2}})$ ，其中， ${x_{i,1}}$ ${x_{j,1}}$ 表示包的CPU需求， ${x_{i,2}}$ ${x_{j,2}}$ 表示包的内存需求，若在某时刻这2个包的需求差异最大，则将它们之间的距离定义为集合中包之间的最大距离。

 $L = \sqrt {{{({x_{i,1}} - {x_{j,1}})}^2} + {{({x_{i,2}} - {x_{j,2}})}^2}}$ (1)

b. 距离因子 $d({x_i},{x_j})$ $d({x_i},{x_j})$ 表示聚类的距离度量因子， $x_i,\;x_j$ 分别代表包的CPU需求和内存需求。

 $d(\!{x_i},\!{x_j}\!)\! \!=\!\! \!\left\{\!\!\!\!\!\! {\begin{array}{*{20}{c}} {{{\left[\! {\dfrac{{{x_{i,1}}}}{{L}} \!-\! \left(1\! -\! \dfrac{{{x_{j,1}}}}{{L}}\right)}\! \right]}^2} \!\!\!+\!\! {{\left[\! {\dfrac{{{x_{i,2}}}}{{L}} \!-\! \left(\!1 \!-\! \dfrac{{{x_{j,2}}}}{{L}}\!\right)\!} \right]}^2}\!,}\,{L \!> \!0} \\ {0,}\;{L \!=\! 0}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \end{array}} \right.\!\!\!$ (2)

$L > 0$ 时，可由式（2）计算点 $i$ 与点 $j$ 之间的距离因子。以CPU需求差异为例，若点 $i$ 与点 $j$ 的CPU需求 ${x_{i,1}}$ ${x_{j,1}}$ 之间的差异越大，则 ${x_{i,1}}/L$ $(1 - {x_{j,1}}/L)$ 的值越接近，则满足聚类原则中距离相近的点聚为一类的条件；当 $L = 0$ 时，表示集合中任意2个包之间的资源需求均相等，包之间不存在资源需求差异，此时 $d({x_i},{x_j})$ =0。因此，若包之间的CPU需求、内存需求差异越大，则2点之间的距离因子越近，最终需求差异大的2个包将处于1个聚类中。

c. 距离因子均值 $D_{\rm{is}}$ $D_{\rm{is}}$ 为集合中所有包的距离因子的均值。n为集合中所有包样本点的数目。

 ${D_{{\rm{is}}}} =\frac{{ 2\displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{j = 1}^n {d({x_i},{x_j})} } }}{{(n - 1)}}$ (3)

d. 包样本点分布密度 $f(i)$ $f(i)$ 定义为集合中与包样本点 $i$ 之间的距离因子小于 $D_{\rm{is}}$ 的包样本点数目，表示点 $i$ 的分布密度，所有满足条件的包样本点构成一个聚类。

 $f(i) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {g({x_i},{x_j})} }$ (4)
 $g({x_i},{x_j}){\rm{ = }}\left\{ {\begin{array}{*{20}{c}} {{\rm{1,}}}&{d({x_i},{x_j}) < D_{\rm{is}}}\\ {{\rm{0,}}}&{d({x_i},{x_j}) \geqslant D_{\rm{is}}} \end{array}} \right.$ (5)

e. 聚类包中的距离因子均值 $\theta (i)$ $\theta (i)$ 表示已经形成的聚类包的距离因子的平均值。

 $\theta (i) =\frac{{ 2\displaystyle\sum\limits_{i = 1}^{f(i)} {\displaystyle\sum\limits_{j = 1}^{f(i)} {d({x_i},{x_j})} }}} {{f(i){\rm{(}}f(i){\rm{ - 1)}}}}$ (6)

f. 2个不同分布密度的聚类包的距离因子 $h(i)$ $h(i)$ 表示聚类包中心点 $i$ 与其他聚类包中心点之间的距离因子。现存在2种情形：

（a）若存在聚类包中心点 ${j_{1,}}{j_{2, }}\cdots,{j_R}$ R为聚类包的总个数，它们的分布密度均大于 $f(i)$ ，分别计算点 $i$ 与它们之间的距离因子，若点 $i$ 与点 ${j_r}(r \in R)$ 之间的距离因子 $d(i,{j_r})$ 最小，则 $h(i){\rm{ = }}d(i,{j_r})$

（b）若点 $i$ 的分布密度 $f(i)$ 大于任意一个聚类中心点的分布密度，分别计算点 $i$ 与其他聚类中心点之间的距离，若点 $i$ 与点 $b$ 之间的距离因子 $d(i,b)$ 最大，则 $h(i){\rm{ = }}d(i,b)$

g. 聚类包的最大分布密度乘积 $\mu$ 。由上述分析可知， $f(i)$ 值越大，则 $i$ 的周围的点就越多； $\theta (i)$ 值越小，聚类包中的点就越紧密； $h(i)$ 值越大，则2个聚类包的差异性就越大。由聚类的基本原则定义最大分布密度乘积 $\mu ,\;\mu$ 为聚类包中的距离因子均值、聚类包内的分布密度、聚类以后的包之间的距离的倒数这三者的乘积。

 $\mu = \frac{{f{(i)^2}\left[ {f(i) - 1} \right]}}{{2\displaystyle\sum\limits_{i = 1}^{f(i)} {\displaystyle\sum\limits_{j = 1}^{f(i)} {d({x_i},{x_j})} }}} h(i)$ (7)
2.2 基于资源需求差异的k-means算法

2.3 示例说明

a. 定义集合D，并将表1中所有包需求参数放入集合D中。首先根据式（2）分别计算8个包的距离因子，根据式（3）计算出距离因子均值 $D_{\rm{is}}$ ，再根据式（4）计算包样本点分布密度 $f(i)$

b. 定义集合A，将分布密度 $f(i)$ 最大的包设为第一个聚类中心点，首先选择 $f(i)$ 最大为4的包样本点，即编号为7的包样本点，作为第一个聚类中心，将其放入集合A中，并将满足与编号为7包样本点之间的距离因子小于 $D_{\rm{is}}$ 的样本点从D中删除，删除包编号为3，4，6，8的样本点。

c. 通过b的计算，D中剩下包编号为1，2，5的点，再分别根据式（6）计算其 $\theta (i)$ ，以及它们各自的 $h(i)$ ，根据式（7）分别计算它们与b确定的编号为7的包样本点之间的 $\mu$ ，得出编号为1的包样本点具有最大 $\mu$ ，作为第二个聚类中心，并将其放入集合A中，并将满足与编号为1包样本点之间的距离因子小于 $D_{\rm{is}}$ 的样本点从D中删除，删除包编号为2，5的样本点，此时集合D为空，基于分布密度的canopy算法结束。

d. 执行k-means算法聚类流程。根据上述步骤得到k值为2，初始类中心点为编号1和7的包。继续计算表1中其他样本点与它们之间的距离因子，将距离因子与中心点最小的样本点分配到它们所在的类中，计算平均值，更新类中心，根据k-means算法步骤，一直循环，直至聚类完成。

 图 1 聚类以后的包 Fig. 1 Package after clustering

C1，C2分别为第一个、第二个聚类包的聚类中心点。

3 包簇资源调度算法 3.1 包簇资源利用率及能耗定义

 $U = {R_v}[t]{W_p}[t]{\rm{/}}{S_p}[t]$ (8)

 ${E_p} = {\alpha _{\rm{0}}} + \sum\limits_{j = 1}^m {{\alpha _j}} {F_j}\left( {{y_{{p}}}} \right)$ (9)

3.2 包簇之间的距离计算

 $\begin{split} & {{\rho _{{R_v}(t),{W_p}(t)}}} =\\ &\quad {\frac{{\displaystyle\sum\nolimits_t {\left( {\dfrac{{{R_v}[t]}}{{{S_p}[t]}} - \overline {\dfrac{{{R_v}[t]}}{{{S_p}[t]}}} } \right)\left( {\dfrac{{{W_p}[t]}}{{{S_p}[t]}} - \overline {\dfrac{{{W_p}[t]}}{{{S_p}[t]}}} } \right)} }}{{\sqrt {\displaystyle\sum\nolimits_t {\left( {\dfrac{{{R_v}[t]}}{{{S_p}[t]}} - \overline {\dfrac{{{R_v}[t]}}{{{S_p}[t]}}} } \right)} } \sqrt {\displaystyle\sum\nolimits_t {\left( {\dfrac{{{W_p}[t]}}{{{S_p}[t]}} - \overline {\dfrac{{{W_p}[t]}}{{{S_p}[t]}}} } \right)} } }}} \\&\quad{1\leqslant v \leqslant k,\;1\leqslant p \leqslant n}\\[-13pt] \end{split}$ (10)

 ${L_{{R_v}(t),{W_p}(t)}} = [{\rho _{{R_v}(t),{W_p}(t)}} + 1]/2$ (11)

3.3 包簇资源调度算法的流程

4 相关实验

 图 2 实验聚类结果 Fig. 2 Clustering experiment results

 图 3 簇使用个数比较 Fig. 3 Cluster number comparison

 图 4 CPU利用率比较 Fig. 4 CPU utilization comparison

 图 5 内存利用率比较 Fig. 5 Memory utilization comparison

 图 6 能耗比较 Fig. 6 Energy consumption comparison
5 结束语

 [1] HE J, ZHANG Y X, JU L, et al. Block-stream as a service: a more secure, nimble, and dynamically balanced cloud service model for ambient computing[J]. IEEE Network, 2018, 32(1): 126-132. DOI:10.1109/MNET.2018.1700167 [2] 朱亚会, 陈丹, 庄毅. 云数据中心资源利用率均衡的虚拟机调度算法[J]. 小型微型计算机系统, 2017, 38(2): 232-237. [3] ZHOU B Y, WU L, WANG L, et al. Joint optimization of server and network resource utilization in cloud data centers[C]//Proceedings of GLOBECOM 2017 IEEE Global Communications Conference. Singapore: IEEE, 2017: 1-6. [4] SELIM G E I, EL-RASHIDY M A, EL-FISHAWY N A. An efficient resource utilization technique for consolidation of virtual machines in cloud computing environments[C]//Proceedings of 2016 33rd National Radio Science Conference. Aswan: IEEE, 2016: 316-324. [5] COMBARRO M, TCHERNYKH A, KLIAZOVICH D, et al. Energy-aware scheduling with computing and data consolidation balance in 3-tier data center[C]//Proceedings of 2016 International Conference on Engineering and Telecommunication. Moscow: IEEE, 2016: 29-33. [6] 房丙午, 黄志球. 云计算中能耗和性能感知的虚拟机优化部署算法[J]. 计算机工程与科学, 2016, 38(12): 2419-2424. DOI:10.3969/j.issn.1007-130X.2016.12.006 [7] 卢浩洋, 陈世平. 基于包簇映射的云计算资源分配框架[J]. 计算机应用, 2016, 36(10): 2704-2709. DOI:10.11772/j.issn.1001-9081.2016.10.2704 [8] 王法玉, 刘志强. Spark框架下分布式K-means算法优化方法 [J]. 计算机工程与设计, 2019, 40(6): 1595-1600. [9] TONG J F. User clustering based on Canopy+K-means algorithm in cloud computing [J]. Journal of Interdisciplinary Mathematics, 2017, 20(6/7): 1489-1492. [10] 徐雨婷, 陈世平. 基于能耗感知的包簇资源分配算法研究[J]. 软件, 2019, 40(2): 141-146. DOI:10.3969/j.issn.1003-6970.2019.02.028 [11] 袁玉美. 一种均衡物理资源和网络带宽的虚拟机部署方法研究[J]. 无线互联科技, 2017(7): 40-41. DOI:10.3969/j.issn.1672-6944.2017.07.015 [12] WANG Y, XIA Y. Energy optimal VM placement in the cloud[C]//Proceedings of 2016 IEEE 9th International Conference on Cloud Computing. San Francisco: IEEE, 2016: 84-91. [13] MENG X Q, SCI C, KEPHART J, et al. Efficient resource provisioning in compute clouds via VM multiplexing[C]//Proceedings of the 7th International Conference on Autonomic Computing. Washington, DC, USA: ACM, 2010: 11-20. [14] 王霞俊. CloudSim云计算仿真工具研究及应用[J]. 微型电脑应用, 2013, 29(8): 59-61. DOI:10.3969/j.issn.1007-757X.2013.08.019 [15] 林伟伟, 刘波, 朱良昌, 等. 基于CSP的能耗高效云计算资源调度模型与算法[J]. 通信学报, 2013, 34(12): 33-41. DOI:10.3969/j.issn.1000-436x.2013.12.004