2. 国家计算机网络应急技术处理协调中心, 北京 100029
为了对虚拟计算环境(iVCE)中有资源偏好的应用需求做更精细化的资源调度支撑, 提出了基于模糊聚类的资源调度算法.该算法针对应用的资源偏好, 使用模糊关联聚类的方法对资源进行处理, 进一步缩小了资源的选择范围, 降低了直接对原始资源进行聚类的空间复杂度, 从而为资源的精细化调度提供了基础.
2. National Computer Network Emergency Response Technical Team/Coordination Center, Beijing 100029, China
In order to solve the problem of reasonable resource scheduling in virtual computing environment (iVCE), the optimization for resource clustering technology was carried out. A resource matching algorithm (fuzzy clustering scheduling) based on fuzzy clustering was proposed. Scheduling strategy for different resources with different tasks and attributes was put forward in the proposed model. The algorithm narrows choices of resources and directly reduces the space complexity of the original resource.
虚拟计算环境(iVCE，virtual computing environment)存在资源和任务异构的特点，应用需求多样化导致需调度的任务可能对资源有特殊的偏好，Min-Min算法、Max-Min算法及其改进算法[1-3]是目前使用最普遍的任务调度算法.任务调度中的资源匹配问题已经引起了一些研究者的关注[4-6].模拟iVCE的若干应用场景，提出了一种基于模糊聚类的资源调度算法，对资源的静态属性预先进行分类，根据资源特性，对资源按照任务需求进行模糊关联聚类，实现了任务和资源的匹配.
1 基于模糊聚类的资源匹配模型1.1 资源的预先分类虚拟计算环境中资源的静态信息(简称SI)见表 1所列，资源节点的地理位置(location)、互联网服务提供商类型(ISP type)(ISP)、网络接入类型(access type)等作为预先分类的标准.静态信息中的各项参数构成一个一维向量SI，反映了该资源节点的固有属性，资源满足任务的静态需求才可能进入到该任务的调度池中.
|
表 1 静态信息向量SI |
该部分介绍对资源的进一步聚类，同时对资源和任务进行匹配.借鉴文献[6]中关于模糊关联聚类的知识网选择方法，提出资源和任务的聚类算法.
定义1 资源的属性完善度
设资源节点集合P={p1, p2, …, pn}，则在P上的一个模糊集定义为γ(pi):P→[0, 1], xi∈P, γ(pi)称为资源节点的属性完善度.
定义2 模糊关系矩阵
模糊矩阵通常用来表示二元模糊关系.设A1，A2，…AN为N个资源节点，依据相似度函数式两两计算，可获得N (N-1) /2个相似度值，将其组成一个N×N矩阵，即为模糊关系矩阵，设为R.其中相似度函数定义如下：
|
(1) |
由于受篇幅所限具体参数略.
对于有资源偏好的应用，设用户任务的偏好资源为Y，使用任务的资源偏好与每个类中排序最高的资源依据式(2) 进行计算，得到相似度，相似度越大，说明任务与该类资源越匹配，这有别于资源库中资源的比较，因此式(2) 是式(1) 的升级.
|
(2) |
提出的资源模糊关联聚类与选择方法的步骤如下：
1) 列出资源库中N个资源节点的信息，如属性完善度、属性数、所处的属性层次等，按照式(1) 计算两两资源的相似度；
2) 相似度计算值rij=sim(Vi，Vj)，并用其构造出模糊关联矩阵R=[rij], i, j=1, 2, …N；
3) 将矩阵R进行分解，得R=G·GT，建立最优化目标函数：
|
(3) |
4) 使用适合的梯度迭代算法，取定学习梯度值β以及最大迭代次数.计算G获得资源的隶属信息:
G=[gij], i=1, 2, …, N, j=1, 2, …, c
5) 根据用户的任务需求偏好选择映射到偏好资源，由式(2) 计算偏好资源与每个类中类隶属度排序最高资源的相似度，从而确定哪一类资源为参考资源类；再由式(1) 计算目标资源与确定的参考资源类中资源的相似度，从而确定哪一资源为参考资源.
2 基于模糊聚类的资源调度算法2.1 基于模糊聚类的资源调度算法基于模糊聚类算法的资源调度算法，即FCS算法，是对文献[7]中提出的基于“资源滑动窗口”模型(RSW模型)算法的进一步优化，是对资源静态属性进行预先分类后，对资源动态属性的进一步聚类.
定义3 资源调度窗口是一组资源集合U，第i个资源满足Si∈U (i∈[1, n]，n为资源数目)的条件是rwi=1. rwi由式(4) 确定：
|
(4) |
其中：rwi表示该资源在资源调度窗口中的状态，smi表示满足向量SI调度要求的参数，fci表示满足任务和资源聚类调度要求的变量.三者均定义为一个布尔值，当smi和fci的值同时为真时，即smi=1且fci=1时，该资源才能被调度.
2.2 基于模糊聚类资源调度算法的iVCE基本框架图 1给出了基于模糊聚类资源调度算法的iVCE基本框架，即在虚拟计算环境中用户任务提交到执行的过程.
|
图 1 基于模糊聚类资源调度算法的iVCE基本框架 |
依据上述基于“模糊聚类资源调度算法(FCS)”对文献[7]中提出基于“资源滑动窗口”模型的RSW-Min-Min和RSW-Max-Min算法进行进一步优化，优化后的算法为FCS-Min-Min和FCS-Max-Min.通过对比仿真实验，比照文献[7]中的场景，增加了任务对资源的需求信息作为一个变量，即任务需求目标资源的属性完善度(用Ps表示，当任务对资源无特殊需求即应用无特殊偏好时此值为空，本实验每组场景实验20次，Ps在不同实验里随机赋值)，测试优化后调度算法的性能.资源静态属性信息中资源节点的接入地理位置、互联网服务提供商(ISP)数量将作为本实验的另2个变量.另外，本仿真实验共提供3个场景10 000个任务的调度，且有1 000个满足不同场景的资源节点.
场景一：节点的地理位置数目为2，ISP类型数量为2，资源的属性完善度Ps，(简称(2, 2, Ps)).此条件下，1 000个节点平均分成4组，每组250个节点，代表某一个地域、一种类型ISP接入的节点.
场景二和场景三分别为场景一在同等条件下参数为(10, 4, Ps)、(20, 5, Ps)的情况.
3.2 实验1任务的执行成功率比较图 2表示当节点接入地理位置和互联网服务提供商类型数量的应用需求分别为(2，2，Ps)、(10，4，Ps)和(20，5，Ps)时，优化算法FCS相比于RSW在任务执行成功率方面的优势.由图 2可看出，优化后的FCS算法在各种场景下，任务执行成功的比例均高于RSW算法.算法优化后，资源会预先模糊聚类，并增加任务对资源的需求信息，为不同的任务匹配最合适的资源.
|
图 2 FCS-Min-Min和FCS-Max-Min与RSW-Max-Min和RSW-Min-Min任务执行成功率的比较 |
图 3表示当节点接入地理位置和互联网提供商类型数量的应用需求分别为(2，2，Ps)、(10，4，Ps)和(20，5，Ps)时，优化算法FCS和RSW算法在任务完成所用时间方面的优势.
|
图 3 FCS-Min-Min和FCS-Max-Min与RSW-Max-Min和RSW-Min-Min任务完成时间的比较 |
优化后的算法有效地提升了任务完成的时间.由于任务的不同，需匹配的资源差异较大，但优化后的算法比传统Min-Min算法在任务完成时间方面更具优势.
4 结束语针对有资源偏好的应用需求与海量、动态、异构资源的快速匹配问题，提出了一种基于模糊聚类的资源调度算法.该算法对任务和资源提供了较好的匹配，可以满足不用的应用对资源的不同偏好需求，初步实现了“特定资源服务于特定任务”的调度目的，进一步提升平台的适用性.仿真实验对比的结果表明，所提优化后的调度算法可以有效提高系统的任务执行成功率，缩短任务完成时间.将进一步对调度应用需求进行建模，在多维度的任务需求下，建立自适应动态的调度算法.
| [1] | Etminani K, Naghibzadeh M. A min-min max-min selective algorithm for grid task scheduling [C]//2007 3rd IEEE/IFIP International Conference in Central Asia on Internet, ICI 2007. Tashkent, Uzbekistan: [s. n. ], 2007: 1-7. |
| [2] | Baraglia R C, Gabriele D P, Pagano G. A multi-criteria job scheduling framework for large computing farms[J].Journal of Computer and System Sciences, 2013, 79(2): 230–244. doi: 10.1016/j.jcss.2012.05.005 |
| [3] | 封良良, 夏晓燕, 贾振红, 等. 实验基于资源预先分类的云计算任务调度算法[J]. 计算机仿真, 2013, 30(10): 363–367. doi: 10.3969/j.issn.1006-9348.2013.10.083 |
| [4] | Abbadi I M, Ruan A. Towards trustworthy resource scheduling in clouds[J].IEEE Transactions on Information Forensics and Security, 2013, 8(6): 973–984. doi: 10.1109/TIFS.2013.2248726 |
| [5] | 李文娟, 张启飞, 平玲娣, 等. 基于模糊聚类的云任务调度算法[J]. 通信学报, 2012, 33(3): 146–154. |
| [6] | 杨人子, 严洪森. 基于模糊关联聚类的知识网选择方法[J]. 控制理论与应用, 2013, 30(1): 8–16. |
| [7] | 朱春鸽, 刘欣然, 杨义先, 等. 虚拟计算环境下面向应用的基于信任的资源匹配模型[J]. 通信学报, 2013, 34(9): 24–32. |