第14卷第2期 智能系统学报 Vol.14 No.2 2019年3月 CAAI Transactions on Intelligent Systems Mar.2019 D0:10.11992/tis.201710004 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180413.1722.008.html 负载敏感的云任务三支聚类评分调度研究 吴俊伟，姜春茂 (哈尔滨师范大学计算机科学技术与信息工程学院，黑龙江哈尔滨150025)） 摘要：在云计算商业化的服务模式中，追求服务质量、负载均衡与经济原则的多目标优化调度。针对集群资 源使用率偏低的现象，提出了三支聚类评分(three-way clustering weight.,TWCW)算法，首先分析云任务的多样 化需求与资源的动态特性，采用三支聚类算法对任务集合聚类划分，然后结合任务属性对类簇对象进行评分调 度。基于Cloudsim实验模拟表明：相比于k-means与FCM聚类调度，三支聚类评分算法(TwCW在任务平均 响应时间与资源利用率等方面均有显著提升。 关键词：云计算；优化调度；多样化需求；动态资源：三支聚类；评分调度；任务响应时间：资源使用率 中图分类号：TP311.13文献标志码：A 文章编号：1673-4785(2019)02-0316-07 中文引用格式：吴俊伟，姜春茂.负载敏感的云任务三支聚类评分调度研究J.智能系统学报，2019,14(2)：316-322. 英文引用格式：VU Junwei,JIANG Chunmao..Load-aware score scheduling of three-.way clustering for cloud task.CAAI trans- actions on intelligent systems,2019,14(2):316-322. Load-aware score scheduling of three-way clustering for cloud task WU Junwei,JIANG Chunmao (School of Computer Science Technology and Information Engineering,Harbin Normal University,Harbin 150025,China) Abstract:A commercialized model is established for multi-objective optimization scheduling of service quality,bal- anced load,and economic principles in cloud computing.A three-way clustering weight(TWCW)algorithm is pro- posed to solve the problem of the low utilization rate of cluster resources.First,the diversified requirements of cloud tasks and the dynamic characteristics of resources are analyzed to cluster and divide the task set by the TWCW al- gorithm and then score scheduling by combination with task attributes.Simulation results based on Cloudsim show that compared with k-means and FCM clustering scheduling,the TWCW algorithm has significant improvements in the av- erage task response time and resource utilization rate. Keywords:cloud computing;optimal scheduling;diversified requirement;dynamic resource;three-way clustering; scoring scheduling;response time of task;resource utilization rate 在云计算提供强大服务的背后，存在集群资trace分析发现-，云任务可分为即时响应的应用 源使用率偏低的现象：Bohrer"指出集群节点的使与批处理任务，其服务特征、资源需求具有多样 用率一般仅为11%~50%，大量资源处于闲置状态， 性。多数研究通过分析任务作业时长，资源使用 资源浪费严重。Barrsos等通过统计分析近5000 特性等，对任务进行聚类1，以此描述任务的异 台主机近半年的运行状况，节点的使用率仅有10 构性特征，并根据聚类后各类簇的特性设置调度 50%。因此，如何准确有效地分配云资源，提高集 函数，其实验结果表明聚类调度对任务响应时间 群资源利用率是云计算的一个重要研究内容。 与集群资源使用有显著改善。但任务聚类通常并 在云计算的研究中，通过对Google cluster 不完全是非此即彼的类别划分，也可能出现中间 收稿日期：2017-10-10.网络出版日期：2018-04-16 态模糊集。针对此类问题，三支决策聚类通过定 基金项目：中国博土后面上基金项目(2014M561330) 通信作者：吴俊伟.E-mail:1344845860@qq.com. 义边缘域概念拓展了传统的二支聚类算法，并根
DOI: 10.11992/tis.201710004 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180413.1722.008.html 负载敏感的云任务三支聚类评分调度研究 吴俊伟，姜春茂 （哈尔滨师范大学 计算机科学技术与信息工程学院，黑龙江 哈尔滨 150025） 摘 要：在云计算商业化的服务模式中，追求服务质量、负载均衡与经济原则的多目标优化调度。针对集群资 源使用率偏低的现象，提出了三支聚类评分 (three-way clustering weight，TWCW) 算法，首先分析云任务的多样 化需求与资源的动态特性，采用三支聚类算法对任务集合聚类划分，然后结合任务属性对类簇对象进行评分调 度。基于 Cloudsim 实验模拟表明：相比于 k-means 与 FCM 聚类调度，三支聚类评分算法 (TWCW) 在任务平均 响应时间与资源利用率等方面均有显著提升。 关键词：云计算；优化调度；多样化需求；动态资源；三支聚类；评分调度；任务响应时间；资源使用率 中图分类号：TP311.13 文献标志码：A 文章编号：1673−4785(2019)02−0316−07 中文引用格式：吴俊伟, 姜春茂. 负载敏感的云任务三支聚类评分调度研究[J]. 智能系统学报, 2019, 14(2): 316–322. 英文引用格式：WU Junwei, JIANG Chunmao. Load-aware score scheduling of three-way clustering for cloud task[J]. CAAI transactions on intelligent systems, 2019, 14(2): 316–322. Load-aware score scheduling of three-way clustering for cloud task WU Junwei，JIANG Chunmao (School of Computer Science Technology and Information Engineering, Harbin Normal University, Harbin 150025, China) Abstract: A commercialized model is established for multi-objective optimization scheduling of service quality, balanced load, and economic principles in cloud computing. A three-way clustering weight (TWCW) algorithm is proposed to solve the problem of the low utilization rate of cluster resources. First, the diversified requirements of cloud tasks and the dynamic characteristics of resources are analyzed to cluster and divide the task set by the TWCW algorithm and then score scheduling by combination with task attributes. Simulation results based on Cloudsim show that compared with k-means and FCM clustering scheduling, the TWCW algorithm has significant improvements in the average task response time and resource utilization rate. Keywords: cloud computing; optimal scheduling; diversified requirement; dynamic resource; three-way clustering; scoring scheduling; response time of task; resource utilization rate 在云计算提供强大服务的背后，存在集群资 源使用率偏低的现象：Bohrer[1]指出集群节点的使 用率一般仅为 11%~50%，大量资源处于闲置状态， 资源浪费严重。Barrsos 等 [2]通过统计分析近 5 000 台主机近半年的运行状况，节点的使用率仅有 10%~ 50%。因此，如何准确有效地分配云资源，提高集 群资源利用率是云计算的一个重要研究内容。 在云计算的研究中，通过对 Google cluster trace 分析发现[3-4] ，云任务可分为即时响应的应用 与批处理任务，其服务特征、资源需求具有多样 性。多数研究通过分析任务作业时长，资源使用 特性等，对任务进行聚类[5-10] ，以此描述任务的异 构性特征，并根据聚类后各类簇的特性设置调度 函数，其实验结果表明聚类调度对任务响应时间 与集群资源使用有显著改善。但任务聚类通常并 不完全是非此即彼的类别划分，也可能出现中间 态模糊集。针对此类问题，三支决策聚类通过定 义边缘域概念拓展了传统的二支聚类算法，并根 收稿日期：2017−10−10. 网络出版日期：2018−04−16. 基金项目：中国博士后面上基金项目 (2014M561330). 通信作者：吴俊伟. E-mail：1344845860@qq.com. 第 14 卷第 2 期 智 能 系 统 学 报 Vol.14 No.2 2019 年 3 月 CAAI Transactions on Intelligent Systems Mar. 2019
第2期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·317· 据对象属性对兼具多标签对象作出进一步的划 以利等根据作业长短及重要性聚类任务，构建 分，其中，三支决策理论源于Yao对概率粗糙集 LPM模型，追求最大化的任务完成数，文献[9]采 和决策粗糙集3个域的合理解释1).是一种更 用层级聚类对云任务进行预处理，以最小化任务 为一般，有效的决策方法。本文将其引入云计 完成时间为目标函数调度任务，兼顾资源负载与 算，为任务调度问题提供新的解决方案。 系统吞吐量，在满足服务质量的同时，缩短任务 完成时间。高正九等提出了一种基于任务分类 1相关工作 的延迟调度算法，根据任务长度聚类，并依据该 作为一种有效的问题解决手段，三支决策的 类别调整任务等待时间阈值。相比于DS、FIFO 基本思想是通过一对阈值（α，B)将一个全集U划分 算法，该算法有效缩短了任务响应时间。 成3个独立的部分，然后针对各个区域设置相应 三支决策理论体系的引入，将对任务调度提 的策略。其特征是使用三支方法进行问题解决和 供新思路。本文提出的三支聚类评分(three-way 信息处理。三支决策基于启发式方法，将复杂问 clustering weight,.TWCW)算法，对任务进行三支 聚类划分，追求最大化资源使用，根据聚类结果 题利用分治策略转化为简单问题，其定义为 中核心态与模糊态任务偏好设置调度策略。 ca9:T:U→{S1,S2,S3} (1) 式中：基于条件集C,三支决策通过映射x将实体 2TWCW算法 集U分成3个两两互不相交的S1、S2、S,然后根 据3个区域的特点，有针对性的设计策略和动作， 2.1任务模型 以期达到某种收益的最大化。关于三支决策的理 在2011公布的Google Cluster Trace中，作业 论，模型与应用研究已经取得了较大进展，如垃 由一个或多个任务构成，与任务相关的属性有优 圾邮件过滤研究，、代价敏感的三支决策模型研 先级、资源请求(resource request)与限制条件等。 究、三支决策和博弈论1%、多粒度三支决策n 从任务优先级的角度观察，Google设置了任务的 序列三支决策8劉、动态三支决策例、三支决策与 12个优先级，并将其依次划分为高优先级(9-11)、 逻辑20等。 中优先级(2-8)与低优先级(0-1)三类。优先级越 作为三支决策在聚类算法方面的有效应用， 高，意味着成功调度的几率更大，拥有更高的服 三支聚类2122拓展了对象与集合的隶属关系。给 务质量。且各优先级作业，其运行时长，资源使 用特征存在异构性。在资源请求的维度上，任务 定对象集合U={1,x2,…,xn,n表示对象数。以二 请求的资源主要有CPU与内存空间，通过对 支聚类的思想判定，对象x,要么属于集合c,要 CPU与内存在请求率上的回归分析得出，两者存 么不属于集合c5,其聚类的结果为CS={cS1,cs2,…c5b 在关联，但关联性较弱(R≈0.14)。在任务的限制 k为类别数。而以三支的角度观察，对象x:与集合 条件中，通常是由用户为作业指定主机性能或是 cs,的所属关系有：x属于cS,x可能属于cs,x不属 其他关联性任务，限制条件数量与任务的延迟调 于cs,因此集合cs,被划分为互不相交的L域、M域 度并不存在明显关联关系，例如，对于只有一个 和R域，其中L域表示该类簇的核心对象集合， 限制条件的任务集合，与同时拥有6个限制条件 M域为边缘对象集合。其聚类结果为CS={(L(cs), 的任务集合，其平均调度延迟差值较小。 M(cs1),(L(cs2),M(cs2),·,(L(cs),M(cs)川。三支聚 在trace数据中，作业可分为面向用户的交互 类算法根据簇间离散度与簇内聚合度，对类中对 式作业与批处理作业，它们对资源的请求存在多 象之间的紧密程度作进一步划分。 样化特性，且主要体现为对计算、内存与带宽资 传统的二支聚类算法在云计算中被广泛应 源的请求。因此本文选择在资源请求的维度为任 用。文献[5]使用k-means算法将任务聚类为计 务建模，以(id,mips,mem,bw)元组的形式描述任务 算、存储与网络类型，引入权重因子调整属性间 的资源请求，其中，id表示任务标识，mips表示任 优先级，根据任务类型调度任务。刘家志6将 务请求的计算资源，执行任务指令。mem表示任 FCM算法引入到任务调度中，根据CPU、内存 务请求的内存资源，用于构建程序数据结构， IO与带宽等属性为任务建模并聚类，根据类簇特 bw表示请求的带宽资源，用于访问任务链接的外 征为任务设置调度函数。文献[7]根据集群资源 部资源。 的多维属性定义资源可见度，通过静态阈值划分 2.2调度模型 可见度等级，在PSO调度中以该等级与任务执行 调度器是集群的核心，负责任务的调度与资 时间作为适应性函数，提高集群负载均衡度。张 源的合并、迁移，其调度方式与效率将极大影响
据对象属性对兼具多标签对象作出进一步的划 分，其中，三支决策理论源于 Yao 对概率粗糙集 和决策粗糙集 3 个域的合理解释[11-13] ，是一种更 为一般，有效的决策方法。本文将其引入云计 算，为任务调度问题提供新的解决方案。 1 相关工作 (α, β) U 作为一种有效的问题解决手段，三支决策的 基本思想是通过一对阈值 将一个全集 划分 成 3 个独立的部分，然后针对各个区域设置相应 的策略。其特征是使用三支方法进行问题解决和 信息处理。三支决策基于启发式方法，将复杂问 题利用分治策略转化为简单问题，其定义为 c(α,β) : τ : U → {S 1,S 2,S 3} (1) C τ U S 1、S 2、S 3 式中：基于条件集 ，三支决策通过映射 将实体 集 分成 3 个两两互不相交的 ,然后根 据 3 个区域的特点，有针对性的设计策略和动作， 以期达到某种收益的最大化。关于三支决策的理 论，模型与应用研究已经取得了较大进展，如垃 圾邮件过滤研究[14] 、代价敏感的三支决策模型研 究 [15] 、三支决策和博弈论[16] 、多粒度三支决策[17] 、 序列三支决策[18] 、动态三支决策[19] 、三支决策与 逻辑[20]等。 U = {x1, x2,··· , xn} n xi csi csi CS ={cs1, cs2,··· csk} k xi csi xi csi xi csi xi csi csi L M R L M CS = {(L(cs1), M(cs1)),(L(cs2), M(cs2)),··· ,(L(csk), M(csk))} 作为三支决策在聚类算法方面的有效应用， 三支聚类[21-22]拓展了对象与集合的隶属关系。给 定对象集合 ， 表示对象数。以二 支聚类的思想判定，对象 ，要么属于集合 ，要 么不属于集合 ，其聚类的结果为 ， 为类别数。而以三支的角度观察，对象 与集合 的所属关系有： 属于 ， 可能属于 ， 不属 于 ，因此集合 被划分为互不相交的 域、 域 和 域，其中 域表示该类簇的核心对象集合， 域为边缘对象集合。其聚类结果为 。三支聚 类算法根据簇间离散度与簇内聚合度，对类中对 象之间的紧密程度作进一步划分。 传统的二支聚类算法在云计算中被广泛应 用。文献[5]使用 k-means 算法将任务聚类为计 算、存储与网络类型，引入权重因子调整属性间 优先级，根据任务类型调度任务。刘家志[ 6 ]将 FCM 算法引入到任务调度中，根据 CPU、内存、 IO 与带宽等属性为任务建模并聚类，根据类簇特 征为任务设置调度函数。文献[7]根据集群资源 的多维属性定义资源可见度，通过静态阈值划分 可见度等级，在 PSO 调度中以该等级与任务执行 时间作为适应性函数，提高集群负载均衡度。张 以利等[8]根据作业长短及重要性聚类任务，构建 LPM 模型，追求最大化的任务完成数，文献[9]采 用层级聚类对云任务进行预处理，以最小化任务 完成时间为目标函数调度任务，兼顾资源负载与 系统吞吐量，在满足服务质量的同时，缩短任务 完成时间。高正九等[10]提出了一种基于任务分类 的延迟调度算法，根据任务长度聚类，并依据该 类别调整任务等待时间阈值。相比于 DS、FIFO 算法，该算法有效缩短了任务响应时间。 三支决策理论体系的引入，将对任务调度提 供新思路。本文提出的三支聚类评分 (three-way clustering weight，TWCW) 算法，对任务进行三支 聚类划分，追求最大化资源使用，根据聚类结果 中核心态与模糊态任务偏好设置调度策略。 2 TWCW 算法 2.1 任务模型 R ≈ 0.14 在 2011 公布的 Google Cluster Trace 中，作业 由一个或多个任务构成，与任务相关的属性有优 先级、资源请求 (resource request) 与限制条件等[3]。 从任务优先级的角度观察，Google 设置了任务的 12 个优先级，并将其依次划分为高优先级 (9-11)、 中优先级 (2-8) 与低优先级 (0-1) 三类。优先级越 高，意味着成功调度的几率更大，拥有更高的服 务质量。且各优先级作业，其运行时长，资源使 用特征存在异构性。在资源请求的维度上，任务 请求的资源主要有 CPU 与内存空间，通过对 CPU 与内存在请求率上的回归分析得出，两者存 在关联，但关联性较弱 ( )。在任务的限制 条件中，通常是由用户为作业指定主机性能或是 其他关联性任务，限制条件数量与任务的延迟调 度并不存在明显关联关系，例如，对于只有一个 限制条件的任务集合，与同时拥有 6 个限制条件 的任务集合，其平均调度延迟差值较小。 (id,mips,mem,bw) id mips mem bw 在 trace 数据中，作业可分为面向用户的交互 式作业与批处理作业，它们对资源的请求存在多 样化特性，且主要体现为对计算、内存与带宽资 源的请求。因此本文选择在资源请求的维度为任 务建模，以 元组的形式描述任务 的资源请求，其中， 表示任务标识， 表示任 务请求的计算资源，执行任务指令。 表示任 务请求的内存资源，用于构建程序数据结构， 表示请求的带宽资源，用于访问任务链接的外 部资源。 2.2 调度模型 调度器是集群的核心，负责任务的调度与资 源的合并、迁移，其调度方式与效率将极大影响 第 2 期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·317·
·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) 寻找最佳聚类数，使用聚类算法 (如 kmeans) 聚类任务集合 ，根据类簇间离散度与类 簇内聚合度择优确定最佳聚类结果； 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 卷
第2期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·319· 式中：w表示类簇第维属性得分值；矩阵的行向 对于M(C)域的任务，根据任务请求的资源在 量w;=[w1W2…wM]表示各类簇中心在第i维资 集群资源中的所占比确定该任务请求的主资源， 源上的评分值，记录类簇间资源请求的比重：矩 将多维属性映射到单维空间，从而确定权重因子 阵的列向量w,=[ww2j…ww「表示类簇资源请 4,其算法描述如下。 求偏好。评分函数通过排序算法比较centroid, 输入任务t: centroid2,…,centroid间第i维属性，确定行向量 输出权重因子μ w=[w1M2…ww。假设评分矩阵为 1)初始化权重因子 4321 2)获取集群资源resource,.初始化迭代变量i-O: W3x4= 3142 2413 3)计算在第维属性中，任务t在资源resource 观察W行向量可知，对于请求的mips资源， 中的比重prop,=t.attr/resource,; centroid,>centroid2>centroid3>centroid,所以w1.it的 4)如果i<N,i=i+1,转至步骤3)。否则转至5) 得分最高，w12次之。接着观察其列向量，以列向量 5)确定prop,中比重最大的第维属性，将u置 w1=[432"为例，类簇cs,中的任务请求4单位的 为1，算法结束。 mips,3单位的mem与2单位的bw。任务偏好为4：32。 2.3.4时间复杂度分析。 2.3.3调度 TWCW算法包括了任务聚类、评分与调度，其中： 在完成对任务的聚类、评分后，根据聚类结 1)三支聚类时间复杂度分析。设任务集合的 果CS与评分矩阵W,分别对cs的L域、M域任务设 任务数为n,聚类分支数为k,近邻数为g,k-means 置调度函数。TWCW算法追求最大化的资源使 的迭代次数为1，寻找最佳聚类数目的时间复杂度 用，因此调度函数需充分利用闲置资源，均衡集 为0n21+n2q),确定分支域对象的时间复杂度为 群负载。通过定义主机host,资源剩余可分配空间 O(n logn+-kmg)Pu。 表示其资源空闲度。 2)类簇评分时间复杂度分析。设聚类分支数 定义2主机host的第维资源剩余可分配空 为k,确定类簇中心在单个属性的排序算法的时间 间space,,如式(6)所示。 复杂度为O(klogk)。 space=(allocable-allocated)/allocable (6) 3)选择目标主机时间复杂度分析。设任务集 式中：allocable,表示host最大可分配的j维资源， 合的任务数为n,主机列表的节点数为m,对于单 allocated表示host,已分配的j维资源。 个任务选择目标节点的时间复杂度为Om),那么 定义3主机host的资源剩余可分配空间，如 选择目标主机的时间复杂度为O(m)。 式(7)所示。 3实验及数据分析 Si= ∑4 -spaceN=3 (7) 3.1实验环境与参数设置 本文采用cloudsim.3.0进行实验。实验模拟 式中μ表示主机host的第维资源的权重。 1000个节点，主机均为四核的，单核处理能力为 TWCW算法可最大限度的利用空闲资源，根 37274MPS。主机RAM为8GB,硬盘容量为1TB. 据任务属性评估节点列表H的剩余可分配空间 带宽1Gb/s。随机生成一系列虚拟请求构成的任 S,选择资源可分配空间最大的主机作为目标节 务（请求序列）。任务的相关参数如表1所示。 点，如式(8)所示 实验采用了两个指标来评估TWCW算法的 et=max(uspace.)N=3,i=1,2.....n (8) 性能：平均响应时间和系统资源利用率。其中， j1 平均响应时间包括等待时间和处理时间，系统资 TWCW算法可最大限度的利用空闲资源，根 源利用率为主机集合的平均使用率。实验同时实 据任务属性评估节点列表H的剩余可分配空间 现了k-means和FCM聚类调度算法，观察它们 S,选择资源可分配空间最大的主机作为目标节 在上述性能方面的表现。 点，如式(8)所示。 表1任务参数 对于L(C)域的任务，通过归一化评分矩阵 Table 1 Task parameters setup W列向量确定权重因子μ，如式(9)所示。 参数 数值 ,N=3 (9) 长度(CPU/MIPS [400,1000] 文件大小MB [200,1000] 内存MB [20,60]
wi, j j i wi = [wi,1 wi,2 ··· wi,M] i wj = [w1, j w2, j ··· wN, j] T j centroid1, centroid2,··· , centroidk i w = [wi,1 wi,2 ··· wi,M] 式中： 表示类簇 第 维属性得分值；矩阵的行向 量 表示各类簇中心在第 维资 源上的评分值，记录类簇间资源请求的比重；矩 阵的列向量 表示类簇 资源请 求偏好。评分函数通过排序算法比较 间 第 维属性，确定行向量 。假设评分矩阵为 W3×4 = 4 3 2 1 3 1 4 2 2 4 1 3 W mips centroid1 > centroid2 > centroid3 > centroid4 w1,1 w1,2 w1 = [4 3 2]T cs1 mips mem bw 观察 行向量可知，对于请求的 资源， ，所以 的 得分最高， 次之。接着观察其列向量，以列向量 为例，类簇 中的任务请求 4 单位的 ，3 单位的 与 2 单位的 。任务偏好为 4:3:2。 2.3.3 调度 CS W csi L M hosti 在完成对任务的聚类、评分后，根据聚类结 果 与评分矩阵 ，分别对 的 域、 域任务设 置调度函数。TWCW 算法追求最大化的资源使 用，因此调度函数需充分利用闲置资源，均衡集 群负载。通过定义主机 资源剩余可分配空间 表示其资源空闲度。 hosti j spacei, j 定义 2 主机 的第 维资源剩余可分配空 间 ，如式 (6) 所示。 spacei, j = (allocablei, j −allocatedi, j)/allocablei, j (6) allocablei, j hosti j allocatedi, j hosti j 式中： 表示 最大可分配的 维资源， 表示 已分配的 维资源。 host 定义 3 主机 i的资源剩余可分配空间，如 式 (7) 所示。 S i = ∑N j=1 µj ·spacei, j , N = 3 (7) µj hosti 式中 表示主机 的第 j 维资源的权重。 H S i TWCW 算法可最大限度的利用空闲资源，根 据任务属性评估节点列表 的剩余可分配空间 ，选择资源可分配空间最大的主机作为目标节 点，如式 (8) 所示。 htarget = max(∑N j=1 µjspacei, j ), N = 3,i = 1,2,··· ,m (8) H S i TWCW 算法可最大限度的利用空闲资源，根 据任务属性评估节点列表 的剩余可分配空间 ，选择资源可分配空间最大的主机作为目标节 点，如式 (8) 所示。 L(Ci) W µj 对于 域的任务，通过归一化评分矩阵 列向量确定权重因子 ，如式 (9) 所示。 µj = wj,i ∑N j=1 wj,i ,N = 3 (9) M(Ci) µ 对于 域的任务，根据任务请求的资源在 集群资源中的所占比确定该任务请求的主资源， 将多维属性映射到单维空间，从而确定权重因子 ，其算法描述如下。 输入 任务 t ； 输出 权重因子 µ。 1) 初始化权重因子 µ ； 2) 获取集群资源 resource，初始化迭代变量 i=0； 3) 计算在第 i 维属性中，任务 t 在资源 resource 中的比重 propi=t.attri /resourcei； 4) 如果 i < N，i = i+1 ，转至步骤 3)。否则转至 5)； 5) 确定 propi 中比重最大的第 l 维属性，将 µl置 为 1，算法结束。 2.3.4 时间复杂度分析。 TWCW 算法包括了任务聚类、评分与调度，其中： n k q means I O(n 2 I +n 2q) O(nlogn+knq) 1) 三支聚类时间复杂度分析。设任务集合的 任务数为 ，聚类分支数为 ，近邻数为 ， k- 的迭代次数为 ，寻找最佳聚类数目的时间复杂度 为 ，确定分支域对象的时间复杂度为 [21]。 k O(k logk) 2) 类簇评分时间复杂度分析。设聚类分支数 为 ，确定类簇中心在单个属性的排序算法的时间 复杂度为 。 n m O(m) O(nm) 3) 选择目标主机时间复杂度分析。设任务集 合的任务数为 ，主机列表的节点数为 ，对于单 个任务选择目标节点的时间复杂度为 ，那么 选择目标主机的时间复杂度为 。 3 实验及数据分析 3.1 实验环境与参数设置 本文采用 cloudsim3.0 进行实验。实验模拟 1 000 个节点，主机均为四核的，单核处理能力为 37 274 MIPS。主机 RAM 为 8 GB，硬盘容量为 1 TB， 带宽 1 Gb/s。随机生成一系列虚拟请求构成的任 务 (请求序列)。任务的相关参数如表 1 所示。 实验采用了两个指标来评估 TWCW 算法的 性能：平均响应时间和系统资源利用率。其中， 平均响应时间包括等待时间和处理时间，系统资 源利用率为主机集合的平均使用率。实验同时实 现了 k-means[5]和 FCM[6]聚类调度算法，观察它们 在上述性能方面的表现。 表 1 任务参数 Table 1 Task parameters setup 参数 数值 长度 (CPU)/MIPS [400, 1 000] 文件大小/MB [200, 1 000] 内存/MB [20, 60] 第 2 期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·319·
·320· 智能系统学报 第14卷 3.2任务平均响应时间比较实验 算操作返回结果从而减少任务运行时间。经统 评估了TWCW聚类调度在任务响应时间的 计TWCW算法任务的平均响应时间，相比于FCM 表现。实验分别实现了TWCW、k-means和FCM 与k-means算法减少了约7%。 算法来验证聚类方式的改变对任务响应时间的影 3.3 集群资源利用率比较实验 响，实验结果分别如图2所示。 验证了TWCW算法在资源利用率方面的优 2.00 化效果。实验分别评估了TWCW、k-means和 1.75 FCM FCM算法在集群资源利用率方面的表现。实验 结果分别如图34所示。 1.00 0.7 ◆-FCM 0.15 0.6 k-means ◆-TWCW 0.50 0.25 0.5 0.00 1000 300050007000 9000 资源请求数 80.3 图2资源请求增加时响应时间对比 0.2 Fig.2 The average response time comparison when requests are increased 0.1 1000 3000 5000 7000 9000 由图2可以看出TwCW算法比k-means或 资源请求数 FCM在任务响应时间上有一定下降。说明TW 图3：资源请求增加时平均利用率对比 CW在对任务更细粒度聚类划分后，为任务选择 Fig.3 The resource average utilization comparison when 偏好属性更充足的节点，使其能够更快地完成计 requests are increased 1.0 1.0 0.8 0.6 0.6 0.4 0.2 0.0 0.0 FCM k-means TWCW FCM k-means TWCW (a)资源请求2000个 (b)资源请求4000个 1.0 1.0 0.6 0.6 0.4 0.4 e, 00 FCM k-means TWCW FCM k-means TWCW (c)资源请求6000个 (d)资源请求8000个 图4资源请求增加时资源使用情况对比 Fig.4 The resource usage comparison when requests are increased 由图3可知，集群资源使用率随着负载的增 相对集中且利用率中位数均高于其他算法，说明 加而增加，可以看出，在资源请求为1000~2000 相比于k-means.或FCM需提前设置聚类分支， 个时3种算法的差别不大，而在请求幅度继续增 大时，TWCW算法的优化效果较为明显，相对其 TWCW聚类类簇的三支划分与域对象的分类调 他算法最高有近11.3%的改善。 度能细粒度地将任务匹配给合适资源，避免了节 图4中四分位区间内的实线表示资源利用率 点的过量负载与资源闲置，从而能更有效地平滑 的中位数。可以观察到，TWCW算法四分位区间 集群负载，提高资源使用率
3.2 任务平均响应时间比较实验 评估了 TWCW 聚类调度在任务响应时间的 表现。实验分别实现了 TWCW、k-means 和 FCM 算法来验证聚类方式的改变对任务响应时间的影 响，实验结果分别如图 2 所示。 由图 2 可以看出 TWCW 算法比 k-means 或 FCM 在任务响应时间上有一定下降。说明 TWCW 在对任务更细粒度聚类划分后，为任务选择 偏好属性更充足的节点，使其能够更快地完成计 算操作返回结果从而减少任务运行时间。经统 计 TWCW 算法任务的平均响应时间，相比于 FCM 与 k-means 算法减少了约 7%。 3.3 集群资源利用率比较实验 验证了 TWCW 算法在资源利用率方面的优 化效果。实验分别评估了 TWCW、k-means 和 FCM 算法在集群资源利用率方面的表现。实验 结果分别如图 3~4 所示。 由图 3 可知，集群资源使用率随着负载的增 加而增加，可以看出，在资源请求为 1 000~2 000 个时 3 种算法的差别不大，而在请求幅度继续增 大时，TWCW 算法的优化效果较为明显，相对其 他算法最高有近 11.3% 的改善。 图 4 中四分位区间内的实线表示资源利用率 的中位数。可以观察到，TWCW 算法四分位区间 相对集中且利用率中位数均高于其他算法，说明 相比于 k-means或 FCM 需提前设置聚类分支， TWCW 聚类类簇的三支划分与域对象的分类调 度能细粒度地将任务匹配给合适资源，避免了节 点的过量负载与资源闲置，从而能更有效地平滑 集群负载，提高资源使用率。 2.00 1.75 平均任务响应时间/s 1.50 1.25 1.00 0.75 0.25 0.00 1 000 3 000 5 000 资源请求数 7 000 9 000 0.50 FCM k-means TWCW 图 2 资源请求增加时响应时间对比 Fig. 2 The average response time comparison when requests are increased 0.7 0.6 0.5 平均资源利用率/% 0.4 0.3 0.2 0.1 FCM k-means TWCW 1 000 3 000 5 000 资源请求数 7 000 9 000 图 3 资源请求增加时平均利用率对比 Fig. 3 The resource average utilization comparison when requests are increased 平均资源利用率/% 平均资源利用率/% 平均资源利用率/% 平均资源利用率/% 0.8 1.0 0.6 0.4 0.2 0.0 0.8 1.0 0.6 0.4 0.2 0.0 0.8 1.0 0.6 0.4 0.2 0.0 0.8 1.0 0.6 0.4 0.2 0.0 FCM k-means TWCW FCM k-means TWCW FCM k-means TWCW FCM k-means TWCW (a) 资源请求 2 000 个 (b) 资源请求 4 000 个 (c) 资源请求 6 000 个 (d) 资源请求 8 000 个 图 4 资源请求增加时资源使用情况对比 Fig. 4 The resource usage comparison when requests are increased ·320· 智 能 系 统 学 报 第 14 卷
第2期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·321· 4结束语 Task scheduling algorithm based on improved particle swarm optimization algorithm in cloud computing environ- 本文在云任务调度中，引入三支聚类评分算 ment[J].Computer simulation,2013,30(10):363-367,410. 法，以提高资源利用率为目标，利用任务的多样 [8]张以利，杨万扣.云环境下基于任务分类和LPM优化模 化特性，对任务集合进行三支聚类，通过类簇评 型的调度算法).微型电脑应用，2013,29(10少：5-8. 分调度，实现资源的合理分配。并在试验中实现 ZHANG Yili,YANG Wankou.Scheduling algorithm 并比较了k-means和FCM聚类调度算法，考察它 based on task classifying and linear pogramming model in 们在上述性能方面的表现，实验结果表明：对任 a cloud environment[J].Microcomputer application,2013, 务集合细粒度的类簇划分与对象的针对性调度， 2910):5-8. 有利于集群资源利用率与负载均衡。 [9]陈晶晶.云环境下基于非均匀粒度分类的任务调度算法 研究D]南京：南京邮电大学，2015：1-59 在未来的工作中，将对任务进行更细化的分 CHEN Jingjing.Research on task scheduling algorithm 类建模，改进任务与资源的匹配模型，且基于节 based on non-uniform granularity classification in cloud 能角度的考虑，对资源负载进行动态迁移，确定 environment[D].Nanjing,China:Nanjing University of 虚机迁移阈值的在线学习方案，设计评价函数动 Posts and Telecommunications,2015:1-59. 态调整阈值区间等。 [10]高正九，郑烇，辛波，等.基于任务分类的延迟调度算法 参考文献： [).计算机系统应用，2014,23(9)：139-143 GAO Zhengjiu,ZHENG Quan,XIN Bo,et al.Delay [1]BOHRER P,ELNOZAHY E N,KELLER T,et al.The scheduling algorithm based on task classification[J]. case for power management in web servers[M]//GRAY- Computer systemsand applications,2014,23(9): BILL R.MELHEM R.Power Aware Computing.Boston, 139-143. MA,USA:Springer,2002:261-289. [11]YAO Yiyu.The superiority of three-way decisions in [2]BARROSO L A,HOLZLE U.The case for energy-propor- probabilistic rough set models[J].Information sciences, tional computing[J].Computer,2007,40(12):33-37. 2011.181(6):1080-1096. [3]REISS C.TUMANOV A.GANGER G R.et al.Hetero- [12]YAO Yiyu.Three-way decisions with probabilistic rough geneity and dynamicity of clouds at scale:Google trace sets[J].Information sciences,2010,180(3):341-353. analysis[C]//Proceedings of the third ACM Symposium on [13]YAO Yiyu.Three-way decision:an interpretation of rules Cloud Computing.New York,NY,USA,2012:1-13. in rough set theory[Cl//Proceeding of the 4th Internation- [4]LIU Zitao,CHO S.Characterizing machines and work- al Conference Rough Sets and Knowledge Technology loads on a Google cluster[C]//Proceedings of 2012 41st In- Gold Coast.Australia.2009:642-649. ternational Conference on Parallel Processing Workshops. [14]ZHOU Bing,YAO Yiyu,LUO Jigang.Cost-sensitive Pittsburgh,PA,USA,2012:397-403. three-way email spam filtering[J].Journal of intelligent [5]左利云.云计算中基于任务特性和资源约束的调度方法 information systems,2014,42(1):19-45. 研究D].广州：华南理工大学，2016：1-139 [15]ZHANG Hengru,MIN Fan,HE Xu,et al.A hybrid re- ZUO Liyun.The scheduling methods based on the task commender system based on user-recommender interac- features and resource constraints in cloud computing[D]. tion[J].Mathematical problems in engineering,2015, Guangzhou,China:South China University of Technology, 2015:145636 2016:1-139 [16]YAO Jingtao,AZAM Nouman.Web-based medical de- [6]刘家志.模糊C-均值算法在任务调度问题上的应用 cision support systems for three-way medical decision [C]/第十届中国通信学会学术年会论文集.沈阳，中国 making with game-theoretic rough sets[J.IEEE transac- 2014:310-313」 tions on fuzzy systems,2015,23(1):3-15. LIU Jiazhi.Application of fuzzy c-means algorithm in task [17]QIAN Yuhua,ZHANG Hu,SANG Yanli,et al.Multi- scheduling problem[C/A Collection of Academic Annual granulation decision-theoretic rough sets[J].International Meetings of the Tenth China Communications Society. journal of approximate reasoning,2014,55(1):225-237. Shenyang,China,2014:310-313. [18]LI Huaxiong,ZHOU Xianzhong,HUANG Bing,et al. [7]封良良，夏晓燕，贾振红，等.实验基于资源预先分类的 Cost-sensitive three-way decision:a sequential strategy 云计算任务调度算法[计算机仿真，2013,30(10)： [M]//LINGRAS P,WOLSKI M,CORNELIS C,et al. 363-367,410. Rough Sets and Knowledge Technology.Berlin,Ger- FENG Liangliang,XIA Xiaoyan,JIA Zhenhong,et al. many:Springer,2013:325-337
4 结束语 本文在云任务调度中，引入三支聚类评分算 法，以提高资源利用率为目标，利用任务的多样 化特性，对任务集合进行三支聚类，通过类簇评 分调度，实现资源的合理分配。并在试验中实现 并比较了 k-means 和 FCM 聚类调度算法，考察它 们在上述性能方面的表现，实验结果表明：对任 务集合细粒度的类簇划分与对象的针对性调度， 有利于集群资源利用率与负载均衡。 在未来的工作中，将对任务进行更细化的分 类建模，改进任务与资源的匹配模型，且基于节 能角度的考虑，对资源负载进行动态迁移，确定 虚机迁移阈值的在线学习方案，设计评价函数动 态调整阈值区间等。 参考文献： BOHRER P, ELNOZAHY E N, KELLER T, et al. The case for power management in web servers[M]//GRAYBILL R, MELHEM R. Power Aware Computing. Boston, MA, USA: Springer, 2002: 261–289. [1] BARROSO L A, HÖLZLE U. The case for energy-proportional computing[J]. Computer, 2007, 40(12): 33–37. [2] REISS C, TUMANOV A, GANGER G R, et al. Heterogeneity and dynamicity of clouds at scale: Google trace analysis[C]//Proceedings of the third ACM Symposium on Cloud Computing. New York, NY, USA, 2012: 1–13. [3] LIU Zitao, CHO S. Characterizing machines and workloads on a Google cluster[C]//Proceedings of 2012 41st International Conference on Parallel Processing Workshops. Pittsburgh, PA, USA, 2012: 397–403. [4] 左利云. 云计算中基于任务特性和资源约束的调度方法 研究[D]. 广州: 华南理工大学, 2016: 1–139. ZUO Liyun. The scheduling methods based on the task features and resource constraints in cloud computing[D]. Guangzhou, China: South China University of Technology, 2016: 1–139. [5] 刘家志. 模糊 C-均值算法在任务调度问题上的应用 [C]//第十届中国通信学会学术年会论文集. 沈阳, 中国, 2014: 310–313. LIU Jiazhi. Application of fuzzy c-means algorithm in task scheduling problem[C]//A Collection of Academic Annual Meetings of the Tenth China Communications Society. Shenyang, China, 2014: 310-313. [6] 封良良, 夏晓燕, 贾振红, 等. 实验基于资源预先分类的 云计算任务调度算法[J]. 计算机仿真, 2013, 30(10): 363–367, 410. FENG Liangliang, XIA Xiaoyan, JIA Zhenhong, et al. [7] Task scheduling algorithm based on improved particle swarm optimization algorithm in cloud computing environment[J]. Computer simulation, 2013, 30(10): 363–367, 410. 张以利, 杨万扣. 云环境下基于任务分类和 LPM 优化模 型的调度算法[J]. 微型电脑应用, 2013, 29(10): 5–8. ZHANG Yili, YANG Wankou. Scheduling algorithm based on task classifying and linear pogramming model in a cloud environment[J]. Microcomputer application, 2013, 29(10): 5–8. [8] 陈晶晶. 云环境下基于非均匀粒度分类的任务调度算法 研究[D].南京: 南京邮电大学, 2015: 1–59. CHEN Jingjing. Research on task scheduling algorithm based on non-uniform granularity classification in cloud environment[D]. Nanjing, China: Nanjing University of Posts and Telecommunications, 2015: 1–59. [9] 高正九, 郑烇, 辛波, 等. 基于任务分类的延迟调度算法 [J]. 计算机系统应用, 2014, 23(9): 139–143. GAO Zhengjiu, ZHENG Quan, XIN Bo, et al. Delay scheduling algorithm based on task classification[J]. Computer systemsand & applications, 2014, 23(9): 139–143. [10] YAO Yiyu. The superiority of three-way decisions in probabilistic rough set models[J]. Information sciences, 2011, 181(6): 1080–1096. [11] YAO Yiyu. Three-way decisions with probabilistic rough sets[J]. Information sciences, 2010, 180(3): 341–353. [12] YAO Yiyu. Three-way decision: an interpretation of rules in rough set theory[C]//Proceeding of the 4th International Conference Rough Sets and Knowledge Technology. Gold Coast, Australia, 2009: 642–649. [13] ZHOU Bing, YAO Yiyu, LUO Jigang. Cost-sensitive three-way email spam filtering[J]. Journal of intelligent information systems, 2014, 42(1): 19–45. [14] ZHANG Hengru, MIN Fan, HE Xu, et al. A hybrid recommender system based on user-recommender interaction[J]. Mathematical problems in engineering, 2015, 2015: 145636. [15] YAO Jingtao, AZAM Nouman. Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets[J]. IEEE transactions on fuzzy systems, 2015, 23(1): 3–15. [16] QIAN Yuhua, ZHANG Hu, SANG Yanli, et al. Multigranulation decision-theoretic rough sets[J]. International journal of approximate reasoning, 2014, 55(1): 225–237. [17] LI Huaxiong, ZHOU Xianzhong, HUANG Bing, et al. Cost-sensitive three-way decision: a sequential strategy [M]//LINGRAS P, WOLSKI M, CORNELIS C, et al. Rough Sets and Knowledge Technology. Berlin, Germany: Springer, 2013: 325–337. [18] 第 2 期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·321·
·322· 智能系统学报 第14卷 [19]LIU Dun,LI Tianrui,LIANG Decui.Three-way de- cision clustering algorithm based on k-means[J].Journal cisions in dynamic decision-theoretic rough sets[M]//LIN- of computer applications,2016,36(8):2061-2065,2091. GRAS P,WOLSKI M,CORNELIS C,et al.Rough Sets 作者简介： and Knowledge Technology.Berlin,Germany:Springer, 2013:291-301. 吴俊伟，男，1993年生，硕士研究 [20]SHE Yanhong.On determination of thresholds in three- 生，主要研究方向为云计算。 way approximation of many-valued nm-logic[M]//COR- NELIS C,KRYSZKIEWICZ M,SLEZAK D,et al. Rough sets and Current Trends in Computing.Cham, Germany:Springer,2014:136-143. [21]于洪.三支聚类分析.数码设计，2016,5(1)：31-35， 30. 姜春茂，男，1972年生，教授，硕 YU Hong.Three-way cluster analysis[J].Peak data sci- 士生导师，主要研究方向为云计算、嵌 入式计算和大数据。主持省部级以上 ence,2016,5(1)31-35,30. 科研项目3项，厅局级项目5项，省级 [22]于洪，毛传凯.基于k-means的自动三支决策聚类方法 教改项目2项。发表SCI、EI检索文 ).计算机应用，2016,36(8)：2061-2065,2091. 章30余篇。 YU Hong,MAO Chuankai.Automatic three-way de- 2019年第四届控制与机器人工程国际会议（ICCRE2019) 2019 The 4th International Conference on Control and Robotics Engineering (ICCRE 2019) Welcome to the official website of the 4th International Conference on Control and Robotics Engineer- ing(ICCRE 2019).The conference will be held in Nanjing,China during April 20-23,2019.The aim as well as objective of ICCRE 2019 is to present the latest research and results of scientists related to Control and Robotics En- gineering topics.ICCRE2019 is Sponsored by Hohai University,China and Jiangsu Key Laboratory of Power Transmis- sion and Distribution Equipment Technology An engineering discipline that is on the rise,robotics engineering is a breeding ground for creativity and innovation from people with a background in mechanical,electrical,or software engineering.Robotics engineers may work in the agricultural,military,medical,and manufacturing industries,among others,conceiving of new uses for robots,design- ing improved robots for existing systems,or repairing and maintaining industrial robots,says the Princeton Review.Be- cause robots are already widely used (on production lines,for example),hands-on technical jobs can easily be found in the robotics engineering field,but there are also plenty of opportunities to take on more inventive roles in experimental arenas. 会议网站：www.iccre.org 会议日期：2019年4月20一23日 会议地点：中国南京
LIU Dun, LI Tianrui, LIANG Decui. Three-way decisions in dynamic decision-theoretic rough sets[M]//LINGRAS P, WOLSKI M, CORNELIS C, et al. Rough Sets and Knowledge Technology. Berlin, Germany: Springer, 2013: 291–301. [19] SHE Yanhong. On determination of thresholds in threeway approximation of many-valued nm-logic[M]//CORNELIS C, KRYSZKIEWICZ M, ŚLȨZAK D, et al. Rough sets and Current Trends in Computing. Cham, Germany: Springer, 2014: 136–143. [20] 于洪. 三支聚类分析[J]. 数码设计, 2016, 5(1): 31–35, 30. YU Hong. Three-way cluster analysis[J]. Peak data science, 2016, 5(1): 31–35, 30. [21] 于洪, 毛传凯. 基于 k-means 的自动三支决策聚类方法 [J]. 计算机应用, 2016, 36(8): 2061–2065, 2091. YU Hong, MAO Chuankai. Automatic three-way de- [22] cision clustering algorithm based on k-means[J]. Journal of computer applications, 2016, 36(8): 2061–2065, 2091. 作者简介： 吴俊伟，男，1993 年生，硕士研究 生，主要研究方向为云计算。 姜春茂，男，1972 年生，教授，硕 士生导师，主要研究方向为云计算、嵌 入式计算和大数据。主持省部级以上 科研项目 3 项，厅局级项目 5 项，省级 教改项目 2 项。发表 SCI、EI 检索文 章 30 余篇。 2019 年第四届控制与机器人工程国际会议（ICCRE 2019） 2019 The 4th International Conference on Control and Robotics Engineering (ICCRE 2019) Welcome to the official website of the 4th International Conference on Control and Robotics Engineering (ICCRE 2019). The conference will be held in Nanjing, China during April 20—23, 2019. The aim as well as objective of ICCRE 2019 is to present the latest research and results of scientists related to Control and Robotics Engineering topics. ICCRE2019 is Sponsored by Hohai University, China and Jiangsu Key Laboratory of Power Transmission and Distribution Equipment Technology. An engineering discipline that is on the rise, robotics engineering is a breeding ground for creativity and innovation from people with a background in mechanical, electrical, or software engineering. Robotics engineers may work in the agricultural, military, medical, and manufacturing industries, among others, conceiving of new uses for robots, designing improved robots for existing systems, or repairing and maintaining industrial robots, says the Princeton Review. Because robots are already widely used (on production lines, for example), hands-on technical jobs can easily be found in the robotics engineering field, but there are also plenty of opportunities to take on more inventive roles in experimental arenas. 会议网站：www.iccre.org 会议日期：2019 年 4 月 20—23 日 会议地点：中国南京 ·322· 智 能 系 统 学 报 第 14 卷
