基于分簇能耗聚集的云计算多目标任务调度算法

王翠娥

（吕梁学院 计算机科学与技术系，山西 吕梁 033000）

基于分簇能耗聚集的云计算多目标任务调度算法

王翠娥

（吕梁学院 计算机科学与技术系，山西 吕梁 033000）

在云计算环境下的多分簇目标的任务调度是提高软件嵌入式系统稳定性的关键，由于云计算中能耗扩散，在多处理器集群多目标任务调度中出现任务调度优先级列表混乱，调度性能不好的问题.传统方法采用节点行为信息流特征分析方法进行任务调度，随着分簇能耗扩散，收敛性不好.提出一种基于分簇能耗聚集的云计算多目标任务调度算法.待分析任务调度信息流的分层能耗聚集轨迹峰值往往含有重要的信息，提取待分析任务调度信息的能耗特征，构建云计算多目标任务调度模型，实现对云计算多目标任务调度算法的改进.仿真结果表明：采用该算法能有效提高云计算多目标任务调度效率，任务执行时间较短，系统稳定性高.

云计算；任务调度；软件；嵌入式

0 引言

随着计算机技术的快速发展，各种嵌入式设备和应用系统对计算机的运算速度和水平也提出了更高的要求，例如在ARM和Linux等嵌入式操作系统设计和应用中，又例如各种先进的三维图形处理、大数据处理、实时任务调度等，均要求计算机系统具有非常强大的运算能力.云计算作为一种主要的大数据计算方式，逐渐应用到智能数据信息处理、资源调度和数据挖掘等领域，同时，云计算与嵌入式设备结合，在模式识别和计算机智能控制等领域有着较大的应用前景.在嵌入式云计算环境中，需要进行多分簇目标的任务调度，以提高软件嵌入式系统稳定性.研究云计算环境下的多目标任务调度算法，对提高系统运行的稳定性和可靠性，提高软件执行任务的时效性等方法具有极其重要的意义，因此，研究嵌入式云计算多目标任务调度算法成为当前计算机信息领域研究的热点课题[1].

由于云计算中能耗扩散，在多处理器集群多目标任务调度中可能出现任务调度优先级列表混乱、调度性能不好的问题.传统方法中，对嵌入式云计算多目标任务调度采用的是PSO粒子群调度算法、神经网络算法、遗传自适应调度算法和决策树算法等[2-6]，这些算法在实现云计算多目标任务调度过程中，取得了一定的效果，特别是对多用户、多任务的多线程的目标任务调度效果较好.其中文献[7]通过加权模糊算法实现对与计算多处理器集群的目标任务调度，通过聚类中心搜索，进行模式特征搜索和识别，改进优先级列表，提高调度性能，但该算法计算开销较大.文献[8]提出基于多目标节点行为融合处理的云计算任务调度算法，通过Linux嵌入式任务调度的优化设计，采用聚类中心节点，实现多目标任务调度优化，但是该算法对任务区间失衡的控制性能不好.可见，传统方法采用节点行为信息流特征分析方法进行任务调度，随着分簇能耗扩散，收敛性不好[9].针对传统方法出现的问题和弊端，笔者提出一种基于分簇能耗聚集的云计算多目标任务调度算法.首先构建云计算多目标任务调度模型，提取任务信息流模型特征，并进行分簇能耗聚集算法设计，最后实现对云计算多目标任务调度算法改进，通过仿真实验进行了性能验证，展示了本文算法在实现云计算多目标任务调度中的优越性能.

1 问题描述与云计算多目标任务调度模型构建

1.1 问题的描述

嵌入式操作系统作为一种新型的网络操作系统，成为云计算的主要载体，在发展过程中产生多目标复合型任务调度等问题，有以下几个重要的问题需要首先解决：

1）云计算环境下，嵌入式设备的异构特征兼容.随着计算机硬件技术快速发展，多处理器集群的发展速度也是非常迅速的，在不同的时期，不同的多处理器版本层出不穷，由于不同时期多处理器版本的计算能力差异很大，而一个实际的应用系统中，多是由多个不同版本的多处理器不断升级而来的.所以，如何在这些不同版本的多处理器上实现统一的任务调度和分配是其发展中需要最先解决的兼容性问题.

2）云计算环境下，嵌入式设备的可伸缩能力.在许多实际的多处理器应用系统中，通常需要对多处理器系统进行不断的扩展，在动态扩展时，有时候需要减少系统构成，降低成本和组成，有时候需要加大系统组成，不断升级，所以需要多处理器集群具有强大的可伸缩能力.

3）云计算多目标任务调度中，嵌入式设备集群的容错能力.在不同版本、不同平台上，多处理器运行时，不同平台之间融合运算时，可能会出现错误.这时，要求多处理器集群系统具有强大的容错能力来对不同平台下的错误进行融合处理，保证多处理器系统高效完备的执行.

4）云计算多目标任务调度中任务调度优先级策略.在用户的使用过程中，可能会实时中断运算系统，加入新的用户任务，那么在旧任务执行的过程中，就必须设定任务回调的监测方法，实时对任务的执行情况进行监测，在用户有更高优先级的任务需要执行时，系统让出当前资源，给优先级更高的用户应用程序执行.

传统的云计算任务调度运算模式在日常的文件处理、数据运算等方面均能很好的适应，但是对于数据量非常庞大的图形运算、实时多维运算等的应用性能较弱，需要进行多目标任务调度.

1.2 云计算多目标任务调度模型构建

笔者构建的云计算多目标任务调度模型，其结构设计如图1所示.

在图1中，采用分区特征融合的策略，以节点行为信息流特征分析进行任务调度，当执行云计算任务时，管理节点将1个作业任务（Task）划分若干个特征区间，设置其时间片为当前的调度执行规模BTavg.假设任务调度时间片内目标数据pi执行任务nj，节点m发送数据进行任务调度，节点交换数据序列为：

图1 云计算多目标任务调度节点模型

在异构的云计算多目标任务调度模型中，静态任务调度通常采用带权有向无环图（DAG）表示任务模型. DAG图中结点表示任务，为了实现模糊云计算，需要产生随机矩阵z，为c×D维的云数据，其每个分量都在（0，1）之间.根据Lorenz映射形式，得到NP个随机数序列分量：

W是一个n×m的矩阵，n表示DAG图中的任务数，使编码端接收到的数据出现层间模式重叠，接收端需要将接收到的视频数据进行分片重组，通过模糊云计算，通过结点的CP（vi）值判断其是否为关键任务.如果CP（vi）=CP（ventry），则vi为关键任务，相互独立并行任务集合CP（vi）定义如下：

云计算任务调度处理机pi执行任务nj所能嵌入式系统执行效率DR（pi，nj）定义为：

每当进程k就绪时，类型为rk的任务在时间段T进行云计算多目标任务调度的时间为：

设计模糊云计算核函数，使得核函数满足时数据定位识别的约束条件和要求，由此实现了云计算多目标任务调度模型构建，为多目标任务调度算法设计提供模型基础.

2 分簇能耗聚集方法的提出和任务调度算法改进

2.1 信息流特征提取及分簇能耗聚集设计

在上述云计算多目标任务调度节点模型计的基础上，进行信息流特征提取，为云计算多目标任务调度提供数据基础.传统方法采用节点行为信息流特征分析方法进行任务调度，随着分簇能耗的扩散，收敛性不是很好，对此本文提出一种基于分簇能耗聚集的云计算多目标任务调度算法.

首先对云计算任务调度节点DAG图中的任务进行任务归并，然后将DAG图分层，从整个任务图的全局出发考虑任务的优先级，构建分簇能耗聚集模型，在多处理器集群任务调度.根据计算机上的每个处理器的特性，进行相应的数据格式转换，使得系统数据兼容，并且具备一定的差错数据冗余处理能力.首先进行多目标任务信息的特征提取，由数据分析函数定义，对于尺度为a的多个任务流集合，以t/a代替t，则相应的分析函数定义为：

其中，下标ia表示尺度a数据分析函数的任务流的优先级属性.可知任务流的优先级属性的分簇能耗聚集约束关系为：

当下面的条件成立：

分簇能耗聚集调度状态方程：

在云计算嵌入式设备中，通过进程管理子系统，完成进程的创建、中止、进程间的通信及任务调度，云存储资源时，添加控制速度的约束因子a，待分析任务调度信息流的分层能耗聚集轨迹峰值往往含有重要的信息，提取待分析任务调度信息，进行任务调度.

2.2 目标任务调度算法改进实现

根据计算机上的每个处理器的特性，进行相应的数据格式转换，添加动量惯性系数ω，用来提高调度性能的可靠性，由于 r1，r2服从均匀分布，得到多分簇云计算的特定数据层间预测结果为：

采用分簇能耗聚集算法，在特定数据在云计算中的传输距离小于阈值d0时，通过亮度均值差的自由空间信道传输模型构建，得到目标任务调度感知能耗系数是εfs；目标任务调度的聚集能耗用一个四元组G表示，G=（V，E，W，C），在目标任务调度中，任务间的通信开销集合，C（vi，vj）表示任务vi与vj间的通信开销，EST2（vi，pq）是复制任务vi关键父结点 时任务vcp，i的最早开始时间，EST1和EST2的计算方法如下：

其中，child（vi）={vj|ei，j∈E}表示任务vi的子结点集合.计算模糊云模型中的已经调度到处理器内核pq上的任务全部执行完成的时间，定义量度F（β，X）来评价由β=[β1，β2]所定位的目标资源的y=βX的空间特征向量，得到目标任务调度的能耗衰减量度F（β，X）优化结果为：

由此实现了基于分簇能耗聚集的云计算多目标任务调度，在降低系统能耗的同时，提高任务调度的效率.

3 仿真实验与结果分析

为了验证本文算法在实现云计算多目标任务调度中的优越性能，进行了仿真实验，仿真实验建立在Matlab数学编程之上，实验采用的计算机型号Dell 2210b，处理器为Intel Core2 Duo1.80 GHz，1 G内存，主频为DDR2 667.在云计算任务调度中，采用多目标任务组合方式，对调度任务进行随机重组，模拟100个系统请求任务，把待调度的目标任务数据集分为3类，每个类别分别包括59，71和48个样本，每个目标任务的数据样本中有13个特征属性.根据上述仿真环境设计，进行仿真实验，首先构建云计算下的多目标任务调度特征信息数据模型，得到3个通道中的目标任务调度特征信息采集结果如图2所示.

图2 3个通道中的目标任务调度特征信息采集结果

图3 目标任务调度分簇能耗聚集结果

以上述特征信息采集数据为研究对象，进行分簇能耗聚集实验，得到能耗聚集结果如图3所示.

从图3可见，通过分簇能耗聚集，实现了对调度任务数据的融合，为提高任务调度的均衡性和效率奠定了基础，最后进行任务调度仿真实验，为了对比性能，采用本文算法和传统算法，对相同规模的任务调度量进行多目标任务调度，以执行时间为参考，得到不同算法的调度运行时间仿真对比结果如图4所示.从图4可见，采用本文算法，节省了目标任务调度时间，提高了效率，提高软件嵌入式系统稳定性.

4 结论

在嵌入式云计算环境中，需要进行多分簇目标的任务调度，以提高软件嵌入式系统稳定性.研究云计算环境下的多目标任务调度算法，对提高系统运行的稳定性和可靠性，提高软件执行任务的时效性等方法具有重要的意义，笔者提出一种基于分簇能耗聚集的云计算多目标任务调度算法.首先构建云计算多目标任务调度模型，提取任务信息特征码，并进行分簇能耗聚集算法设计，最后实现对云计算多目标任务调度算法改进，实验结果表明，采用本文算法能节省了目标任务调度时间，提高了效率，具有优越性.

图4 执行效率对比

[1]王娟，李飞，张路桥.限制解空间的PSO云存储任务调度算法[J].计算机应用研究，2013，30（1）：127-129+154.

[2]张松慧，熊锦江.一种针对非平稳网络任务调度防冲突算法研究[J].科技通报，2013，29（10）：143-145.

[3]许丞，刘洪，谭良.Hadoop云平台的一种新的任务调度和监控机制[J].计算机科学，2013，40（1）：112-117.

[4]李静梅，王雪，吴艳霞.一种改进的优先级列表任务调度算法[J].计算机科学，2014，41（5）：20-23.

[5]CHONG S K，GABER M M，KRISHNASWAMY S，et al.Energy Conservation in Wireless Sensor Networks：a Rule-based Approach[J].Knowledge and Information Systems，2011，28（3）：579-614.

[6]刘少伟，孔令梅，任开军，等.云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J].计算机学报，2011，34（11）：2 021-2 130.

[7]孟宪福，解文利.基于免疫算法多目标约束P2P任务调度策略研究[J].电子学报，2011，39（1）：101-107.

[8]李文娟，张启飞，平玲娣，等.基于模糊聚类的云任务调度算法[J].通信学报，2012，33（3）：146-154.

[9]周浩，高远，朱昌平.基于双门限能量检测的选择式协作频谱感知[J].计算机仿真，2014，31（1）：199-203.

（责任编辑 李健飞）

Cloud Computing Multi-objective Task Scheduling Algorithm Based on Energy Consumption Cluster Aggregation

WANG Cui-e
（Department of Computer Science&Technology，Lvliang University，Lvliang，Shanxi 033000，China）

Computing task scheduling multicluster target environment in the cloud is the key to improve the stability of the software of the embedded system.Owing to the energy diffusion in cloud computing，task scheduling priority list appears chaos in the multi processor cluster multi-objective task scheduling，and scheduling performance is not good.The traditional method uses the node behavior information flow characteristic to analyze task scheduling，with the cluster energy diffusion，convergence is not good.This paper presents a method for calculating the multi-objective task scheduling algorithm based on energy consumption of the cloud cluster aggregation.The simulation results show that，the algorithm can effectively improve the efficiency of cloud computing multi-objective task scheduling，task execution time is short，and it has high stability of the system.

cloud computing；task scheduling；software；embedded type

TP302.7

A

1673-1972（2015）03-0049-06

2015-03-28

王翠娥（1981-），女，山西吕梁人，讲师，主要从事软件技术研究.

book=54,ebook=55