针对云计算环境中任务调度中存在的执行效率低的问题，提出了一种基于改进的基于密度的聚类算法（DBSCAN）的云任务调度策略.首先使用改进的基于密度的聚类算法DBSCAN对云任务进行聚类，然后与已经分类的资源进行匹配，解决资源与任务匹配程度低的问题.实验结果表明，对任务进行聚类后进行任务调度，任务在终端上的平均执行时间减少了大约35.2%，任务的调度时间也有了明显减少.
Cloud scheduling strategy based on improved density-based spatial clustering of applications with noise (DBSCAN) clustering algorithm was proposed to solve the problem of low efficiency of task scheduling in the implementation of cloud computing environment. Firstly, an improved DBSCAN clustering algorithm was used to cluster tasks. Secondly, the classified tasks were matched with classified resources to solve the low matching degree in resources and tasks. Experiments showed that the average execution time of tasks on the terminal was reduced by about 35.2% after clustering task, and the task scheduling time had also been significantly reduced.
近年来，云计算技术[1-2]成为国内外计算机领域广泛关注的一个研究热点.它将互联网上闲置的资源整合成一个逻辑上统一的虚拟资源池，最大化利用这些资源为用户提供各类计算或存储任务.任务调度是在一定规则限制下将任务与资源以优化为目的进行映射，对于任务的执行效率和任务的最终执行效果具有决定性的作用.基于密度的聚类算法(DBSCAN，density-based spatial clustering of applications with noise)[3]算法是一种基于密度的聚类算法，可以发现任意形状的聚类簇并且聚类结果受噪声影响小.但该算法中需要2个参数：扫描半径(Eps)和最小包含点数(MinPts)，当数据集的密度不均匀时，参数取值不当会影响聚类效果.对此，提出了一种改进的DBSCAN算法，利用粒子群[4](PSO)将数据集划分为k个子数据集，获得k个不同的Epsi，依次调用排序后的Epsi作为参数使用DBSCAN算法对样本集X进行聚类.将此聚类方法应用到任务调度中，提高任务与资源的匹配程度，从而改善调度时间与终端任务的执行时间.
1 任务调度介绍任务调度[5-6]主要目的是提高系统的资源利用率以及服务质量，用户能够获得较高的任务处理速率，服务提供方能获得较高的云计算系统吞吐率.
为了构建按需、廉价的云平台，笔者依据任务在虚拟终端上执行时消耗的CPU，带宽，内存，磁盘等数据，将任务分类为与资源类别对应的类别[7]，例如有些任务用于大文件传输，对网络带宽和磁盘资源要求比较高；持久性链接的网络交互性任务，需要一定的内存来保存链接状态.鉴于这些情况，将任务分为计算型.带宽型和磁盘型，在任务调度时根据任务的偏好性寻找对应的虚拟资源，使得各类的资源都能得到充分利用并且提高任务的执行效率.
2 改进的DBSCAN算法 2.1 DBSCAN算法和粒子群算法DBSCAN能把高密度的区域划分为一类，并可发现任意形状的聚类.该算法的具体描述如下.
输入n个样本集X={x1, x2, …, xn}∈Rm, 每个xj=(xj1, xj2, …, xjm)为m维向量，两个全局参数：半径Eps，最少数目MinPts；
1) 从样本集中抽出一个未处理的样本点，判断输入点是否为核心对象，如果是则找出所有从该点密度可达的对象，将这些点标注为同一簇，否则暂时标注该点为边缘点.
2) 重复步骤1) 直到所有的样本点都被处理.
粒子群算法，初始化为一群随机粒子，每个粒子i包含一个d维的位置向量Xi=(xi1, xi2, …, xid)T和速度向量Vi=(vi1, vi2, …, vid)T，在每次迭代开始时，粒子根据自己到目前位置发现的最好位置(pBest)pBesti=(pi1, pi2, …, pid)和目前为止整个群体中所有粒子发现的最好位置(gBest，是pBest中的最好值)gBesti=(pg1, pg2, …, pgd)，利用如下公式来调整自己在第k+1次迭代中的第d维速度vidk+1和自身位置xidk+1:
| $ \begin{array}{l} v_{_{{\rm{id}}}}^{^{k + 1}} = \omega v_{_{{\rm{id}}}}^{^k} + {c_1}{\rm{rand}}_{_1}^{^k}\left( {p{\rm{Best}}_{_{{\rm{id}}}}^{^k}-x_{_{{\rm{id}}}}^{^k}} \right) + \\ {c_2}{\rm{rand}}_{_2}^{^k}\left( {g{\rm{Best}}_{_d}^{^k}-x_{_{{\rm{id}}}}^{^k}} \right) \end{array} $ | (1) |
| $ x_{_{{\rm{id}}}}^{^{k + 1}} = x_{_{{\rm{id}}}}^{^k} + v_{_{{\rm{id}}}}^{^{k + 1}} $ | (2) |
其中：rand1和rand2是(0, 1) 之间的随机数，c1和c2被称作学习因子，通常取c1=c2=2;ω是加权系数(惯性权重)，取值在0.1到0.9之间.粒子通过不断学习更新，最终找到最优解所在位置，即全局最优解gBest，结束搜索过程.迭代终止准则为最大迭代次数Tmax、计算精度ε或最优解的最大停滞步数Δt.
2.2 算法步骤提出了DBSCAN算法的改进(以下简称P-DBSCAN)，首先利用基于粒子群算法的方法获取较优的初始聚类中心和k个不同的Epsi；然后分别选取排序后的Epsi进行DBSCAN聚类.
关于数据集的划分，涉及如下定义[8].
定义1 对于一个初始聚类中心，它到离它最近的一个其他初始聚类中心的距离的一半称为该初始聚类中心的划分距离(PartitionDistance).
定义2 到初始聚类中心的距离不大于PartitionDistance-ε的点称为中心点，如果一个区域内的所有点都是某一初始聚类中心的中心点，则称该区域为该初始聚类中心的中心区域(CoreRegin).
定义3 到初始聚类中心的距离大于PartitionDistance-ε且小于PartitionDistance的点称为ε-中心点.若一个区域内的所有点都是某一初始聚类中心的ε-中心点，则称该区域为该初始聚类中心的ε-中心区域(ε-CoreRegin).
定义4 既不是中心点也不是ε-中心点的点称为该点的非中心点，若一个区域内的所有点都是某一初始聚类中心的非中心点，则称该区域为非中心区域(Non-CoreRegin).
图 1所示为点O的中心区域、ε-中心区域和非中心区域.
|
图 1 中心区域、ε-中心区域和非中心区域 |
P-DBSCAN的算法流程描述如下.
1) 参数设置：样本数X，聚类数K，数据的维数为d，从样本集X中随机抽取NK个样本点，初始化粒子的初始搜索点的位置和速度v0.粒子编码结构设计为：c11, c12, …, c1d, c21, c22, …, c2d, …, ck1, ck2, …, ckd，每个粒子由kd维数据组成.其中cij(i=1, 2, …, k, j=1, 2, …, d)表示第i个聚类中心第j维.
2) 计算群体中每个个体的适应度值.
3) 如果粒子的适应值大于pBest，则令pBest等于当前位置；若粒子适应度值大于全局最好位置gBest，则令gBest等于目前找到的最好pBest.
4) 更新每个粒子速度和位置.
5) 若没有达到最大迭代次数Tmax转入步骤2) 进行新一轮的迭代，否则输出gBest的位置，即最优的K个聚类中心.
6) 求每个初始聚类中心的PartitionDistance.
7) 根据K个初始聚类中心的PartitionDistance对数据集进行划分.
8) 计算每个数据子集的参数Epsi，并对其进行升序排序.
9) 依次调用排序后的Epsi作为参数使用DBSCAN算法对样本集X进行聚类.
10) 每次调用DBSCAN后，对已有聚类的数据点进行标记，标记过的点不再进行后面的DBSCAN聚类，直到所有的Epsi使用完毕，没有经过处理的数据点认为是噪声点.
3 基于聚类的任务调度算法从客户端搜集每个应用在空闲终端上的资源消耗情况，包括CPU、内存、磁盘、带宽，得到样本集X={X1, X2, …, Xn}表示n个任务的集合，每个任务有t个属性，则第i个任务的执行情况为Xi={x1, x2, …, xt}，0≤i≤n.使用P-DBSCAN算法对样本进行聚类来分析任务对资源的消耗特征.
将P-DBSCAN算法应用到任务调度中整个算法的执行过程描述如下.
1) 从客户端搜集各种任务在空闲虚拟终端上的资源消耗情况，做归一化处理后得到X={X1, X2, …, Xn}，以此作为P-DBSCAN的样本点.
2) 使用P-DBSCAN算法对样本集X={X1, X2, …, Xn}进行聚类.
3) 对步骤2) 中的聚类结果中的每一类任务对资源的消耗情况进行分析，将任务分为计算型、带宽型和磁盘型.
4) 根据3) 中聚类的结果，将任务调度给相应的虚拟资源(假定每个资源在资源列表中已有属于自己的标签来标注该资源属于计算型、带宽型或者磁盘型).
4 实验设计与分析 4.1 测试平台介绍选用笔者团队开发的一个云平台IVCE来验证聚类算法应用到任务调度中的效果.该平台分为应用层、任务层、虚拟资源层和资源管理层.应用层包括5种任务，应用ID分别为App-5，App-18，App-19，App-20，App-21，一个任务的执行情况即为后面聚类时的一个样本点；任务层接受应用层提交上来的任务进行调度并下发到虚拟资源节点；虚拟资源节点执行完任务后将结果返回到FTP结果服务器，结果经过收集处理之后将数据插入到数据库中；资源管理层主要管理虚拟资源的注册，资源信息的采集和资源状态的管理.
4.2 实验过程设计实验中使用以上5种应用作为请求任务进行测试，将一种任务发送到终端上执行多次，对收集回来的数据进行处理，从每种任务的数据中选出200条可用数据，收集到1 000条任务在终端上的消耗情况(CPU、内存、磁盘、带宽)，将这1 000条数据作为样本集进行聚类得到这5种任务的任务类型.
为了验证将聚类算法应用于任务调度中的效果，首先采集每个任务在未改进的任务调度算法中的调度时长和执行时间，然后调度聚类后的任务与计算型、带宽型和磁盘型资源进行匹配后下发并执行，采集此过程中的调度时长和任务执行时间等信息.最后，将两个过程中的数据进行对比，直观地得到采用聚类算法后云任务调度的效果.
4.3 实验结果与分析经过对以上5种任务在终端上运行对CPU、带宽、内存、磁盘的消耗情况的结果回收，得到了1 000条数据，包括带宽、系统CPU占用率、内存占用率及磁盘占用大小，部分数据如表 1所示，经过聚类之后的结果如表 2所示.
|
表 1 聚类样本集中部分样本点 |
|
|
表 2 任务聚类结果 |
请求1 000个任务数，在未使用聚类方法和对聚类后的任务进行调度的情况下，任务在终端上的执行时间如图 2所示，可以看出，未使用P-DBSCAN聚类方法时，任务在终端上的平均执行时间为5.804 s，使用该方法之后，任务在终端上的平均执行时间减少为3.761 s，减少了大约35.2%.
|
图 2 P-DBSCAN聚类前后任务执行时长对比 |
当请求任务数为1 000、3 000、5 000、7 000、10 000时，加入聚类算法前后任务调度时长如图 3所示.随着请求的任务数量增加，在任务聚类的基础上进行任务调度的优势越来越明显，这是由于当任务数量很大时，加入P-DBSCAN对任务进行聚类后，在任务调度时能够很快找到与任务匹配的资源.
|
图 3 P-DBSCAN聚类前后每调度100个任务的耗时 |
首先分析了云计算任务调度中任务与资源的匹配程度问题，进而提出了使用改进的DBSCAN算法对任务聚类后与已分类的资源进行匹配.从实验结果可知，将聚类算法应用到任务与资源的匹配上可以缩短任务的调度时长和任务在虚拟资源上的执行时长，使系统能够尽快满足用户的需求.
| [1] | Armbrust M, Fox A, Griffith R, et al. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50–58. doi: 10.1145/1721654 |
| [2] | Meinel L, Findeisen M, Hes M, et al. Automated real-time surveillance for ambient assisted living using anomnidirectional camera[C]//2004 IEEE International Conference on Consumer Electronics.[S.l.]:IEEE, 2014: 396-399. |
| [3] | Li Xia, Jiang Shengyi, Zhang Qiansheng, et al. A dynamic density-based clustering algorithm appropriate to large -scale text processing[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2013, 49(1): 133–139. |
| [4] | 周飞红, 廖子贞. 自适应惯性权重的分组并行粒子群优化算法[J]. 计算机工程与应用, 2014, 50(8): 40–44. |
| [5] | 吴皓. 云环境下任务调度算法研究[D]. 南京: 南京邮电大学, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10293-1013167598.htm |
| [6] | 李丽英. 面向一种云计算平台的任务调度技术研究[D]. 长沙: 湖南大学, 2011. http://cdmd.cnki.com.cn/Article/CDMD-10532-1013171344.htm |
| [7] | 陈廷伟, 周山杰, 秦明达. 面向云计算的任务分类方法[J]. 计算机应用, 2012, 32(10): 2719–2723. |
| [8] | 王桂芝, 王广亮. 改进的快速DBSCAN算法[J]. 计算机应用, 2009, 29(9): 2505–2508. |