·318· 智能系统学报 第14卷 集群的性能输出。本文建立的调度模型如图1所 则t可能属于类簇cs。其聚类结果为={L(cs), 示，其主要模块和功能如下： CSM(cs1),·,(L(cs),M(cs)l。三支聚类算法包括 l)调度器(Scheduler):聚类调度，为任务选择 寻找最佳聚类数与确定类簇域对象两个子步骤， 合适节点。 其基本思想如下： 2)计算节点(Host):物理机节点，承载虚机。 1)寻找最佳聚类数，使用聚类算法（如k- 3)虚机(VM):资源分配的基本单元，执行请 means)聚类任务集合T,根据类簇间离散度与类 求任务。 簇内聚合度择优确定最佳聚类结果： 调度器 2)确定类簇域对象，首先通过近邻域确定类 簇M域对象，然后使用差值排序进一步划分类簇 LIIIIIII CLIIIO L域与M域对象，其具体内容如下：对于类簇cs, 任务队列 KILIIIIIDN 任务4、t与近邻域Neig,G),其中，类簇cs存在中心 CS& 点centroid,Neig()表示在欧式距离上离t,最近的 调度函数 q个任务，当csh,t∈Neiga()时，若t∈csh,则确 定t:为M(csa)对象，然后根据类簇c5h内任务集合 Task, Task Task Tasks Task, Task Task, h,2,…,ti与中心点centroid的欧式距离差值排序， Task 确定差值最大的任务对tp-1和tp,将t,t2,…,‘p-划分 M VM, M VM, 到(cs%)中，tp,p+1,…,划分给M(cs)。其算法描述 Host Host, 如下： 图1集群架构图 输入任务集合T,近邻数q。 Fig.1 Cluster architecture 输出CS={(L(cs),M(cs),…,(L(cs,M(cs川 如图1所示，用户任务(Task)进入任务队列 1)初始化，k=2; (Task queue),调度器(Scheduler)首先提取Task 2)随机选取k个聚类中心y1,V2,…,; queue中的任务集合，根据任务属性将其聚类划 3)对于每个任务，计算其到每个聚类中心 分为{cs1,cs2,·,cs,然后通过调度函数(Strategies) y的距离，将其划分到距离最小的类中： 为各类簇任务选择目标主机(Host),由Host中的 4)更新聚类中心v=y,,…,出 虚机(VM执行该任务，将结果返回。 5)如果聚类中心不发生变化至6)：否则转至3)： 2.3算法描述 6)计算CVN(CS),如果k≤N,那么k=k+1, 给定任务集合T={,2,…,n,其中t:={id,mips 转至2)；否则转至7)： mem,bw},分别表示任务i标志，请求的计算、内 7)考查任务和类cs,其中t,∈cs,t∈Neiga(()o 存、带宽资源。设有主机列表H={h1,h2,·,hm,其 如果t∈cs,那么把，划分到M(cs); 8)对于类中剩余非M域中对象，根据差值排 中h={(P,p),(M,m),(B,b,》,P、M、B,分别表示 h,最大可分配的计算、内存与带宽资源，P、m、b: 序法，找到第一个距离差值最大的对象对t-和， 则分别表示，已分配的计算、内存、带宽资源。 把及其后的对象划分到M(cs): 9)算法结束，输出结果CS={(L(cs),M(cs).·, TWCW算法由聚类，评分与调度3部分组成。 (L(cs:),M(cs)ho 2.3.1聚类 2.3.2评分 基于三支聚类算法，提出任务类簇的三支表 在对任务集合T进行三支聚类后得到聚类结 示形式： 果CS={(L(cs),M(cs),…,(L(cs),Mcs)》,其中， cs;=(L(cs:),M(cs;)) (2) 类簇cs,的类簇中心centroid,={mips,mem,bw}。通 式中：L(cs)ST且M(cs)sT。设R(cs)=T-L(cs)- 过比较类簇中心centroidl间属性大小确定类簇间属 M(cs),则L(cs、M(cs)、R(cs)构成了类簇cs:的核 性比重与类簇内属性偏好，以评分矩阵的形式记 心域、边缘域和琐碎域，它们满足如下性质： 录评分结果。 T=L(csi)UM(csi)UR(cs:) (3) 定义1类簇评分矩阵WwM,如式(5)所示。 L(cs;)nM(csi)=O L(cs:)nR(csi)=0 (4) W11W1,2· WI.M M(cs )nR(cs)=0 W2.1W2.2·W2M 若任务t∈L(cs),则r属于类簇cs;若任务 WNXM= N=3,M=k(5) t∈R(cs),则1不属于类簇cs;若任务teM(cs), WN.I WN.2··WNM集群的性能输出。本文建立的调度模型如图 1 所 示，其主要模块和功能如下： 1) 调度器 (Scheduler)：聚类调度，为任务选择 合适节点。 2) 计算节点 (Host)：物理机节点，承载虚机。 3) 虚机 (VM)：资源分配的基本单元，执行请 求任务。 {cs1, cs2,··· , csk} 如图 1 所示，用户任务 (Task) 进入任务队列 (Task queue)，调度器 (Scheduler) 首先提取 Task queue 中的任务集合，根据任务属性将其聚类划 分为 ，然后通过调度函数 (Strategies) 为各类簇任务选择目标主机 (Host)，由 Host 中的 虚机 (VM) 执行该任务，将结果返回。 2.3 算法描述 T = {t1,t2,··· ,tn} ti = {id,mipsi , memi ,bwi} H = {h1,h2,··· ,hm} hi = {(Pi , pi),(Mi ,mi),(Bi ,bi)} Pi、Mi、Bi pi、mi、bi hi 给定任务集合 ，其中 ，分别表示任务 i 标志，请求的计算、内 存、带宽资源。设有主机列表 ,其 中 , 分别表 示 hi 最大可分配的计算、内存与带宽资源， 则分别表示 已分配的计算、内存、带宽资源。 TWCW 算法由聚类，评分与调度 3 部分组成。 2.3.1 聚类 基于三支聚类算法，提出任务类簇的三支表 示形式： csi = (L(csi), M(csi)) (2) L(csi) ⊆ T M(csi) ⊆ T R(csi) = T − L(csi)− M(csi) L(csi)、M(csi)、R(csi) csi 式中： 且 。设 ，则 构成了类簇 的核 心域、边缘域和琐碎域，它们满足如下性质： T = L(csi)∪ M(csi)∪R(csi) (3) L(csi)∩ M(csi) = Ø L(csi)∩R(csi) = Ø M(csi)∩R(csi) = Ø (4) t ∈ L(csi) t csi t ∈ R(csi) t csi t ∈ M(csi) 若任务 ， 则 属于类簇 ；若任务 ， 则 不属于类簇 ；若任务 ， t csi = {(L(cs1), CS M(cs1)),··· ,(L(csk), M(csk))} 则 可能属于类簇 。其聚类结果为 。三支聚类算法包括 寻找最佳聚类数与确定类簇域对象两个子步骤， 其基本思想如下： T 1) 寻找最佳聚类数，使用聚类算法 (如 k￾means) 聚类任务集合 ，根据类簇间离散度与类 簇内聚合度择优确定最佳聚类结果； M L M csk ti tj Neigq(ti) csk centroidk Neigq(ti) ti q ti < csh tj ∈ Neigq(ti) tj ∈ csh ti M(csh) csh t1,t2,··· ,tl centroidh tp−1 tp t1,t2,··· ,tp−1 L(csh) tp,tp+1,··· ,tl M(csh) 2) 确定类簇域对象，首先通过近邻域确定类 簇 域对象，然后使用差值排序进一步划分类簇 域与 域对象，其具体内容如下：对于类簇 ， 任务 、 与近邻域 ，其中，类簇 存在中心 点 ， 表示在欧式距离上离 最近的 个任务，当 ， 时，若 ，则确 定 为 对象，然后根据类簇 内任务集合 与中心点 的欧式距离差值排序， 确定差值最大的任务对 和 ，将 划分 到 中， 划分给 。其算法描述 如下： 输入 任务集合 T ，近邻数 q。 输出 CS = {(L(cs1), M(cs1)),··· ,(L(csk), M(csk))} 1) 初始化， k = 2 ； 2) 随机选取 k 个聚类中心 v1, v2,··· , vk； ti vi 3) 对于每个任务 ，计算其到每个聚类中心 的距离，将其划分到距离最小的类中； v = {v ′ 1 , v ′ 2 ,··· , v ′ k 4) 更新聚类中心 } ; 5) 如果聚类中心不发生变化至 6)；否则转至 3)； CVIN(CS ) k ⩽ √ 6) 计算 ，如果 N ,那么 k = k+1， 转至 2)；否则转至 7)； ti cs ti ∈ cs,tj ∈ Neigq(t) tj ∈ cs ti M(cs) 7) 考查任务 和类 ，其中 。 如果 ，那么把 划分到 ； M ti−1 ti ti M(cs) 8) 对于类中剩余非 域中对象，根据差值排 序法，找到第一个距离差值最大的对象对 和 ， 把 及其后的对象划分到 ； CS = {(L(cs1), M(cs1)),··· , (L(csk), M(csk))} 9) 算法结束，输出结果 。 2.3.2 评分 CS = {(L(cs1), M(cs1)),··· ,(L(csk), M(csk))} csi centroidi = {mips,mem,bw} centroid 在对任务集合 T 进行三支聚类后得到聚类结 果 ，其中， 类簇 的类簇中心 。通 过比较类簇中心 间属性大小确定类簇间属 性比重与类簇内属性偏好，以评分矩阵的形式记 录评分结果。 定义 1 类簇评分矩阵 WNxM ，如式 (5) 所示。 WN×M =   w1,1 w1,2 ··· w1,M w2,1 w2,2 ··· w2,M . . . . . . . . . wN,1 wN,2 ··· wN,M   , N = 3, M = k (5) Task1 Task2 VM1 Host1 调度器 调度函数 Task3 Task4 VM2 Task5 Task6 Task7 VM3 Host2 Task8 VM4 任务队列 ... cs1 cs2 csk 图 1 集群架构图 Fig. 1 Cluster architecture ·318· 智 能 系 统 学 报 第 14 卷