云计算中基于服务能力与信任约束的任务调度算法

郑 鑫，武小年，孟 川，李 豪

（1.桂林电子科技大学广西无线宽带通信与信号处理重点实验室，广西桂林 541004；2.桂林电子科技大学信息与通信学院，广西桂林 541004）

云计算中基于服务能力与信任约束的任务调度算法

郑 鑫1，2，武小年1，2，孟 川2，李 豪2

（1.桂林电子科技大学广西无线宽带通信与信号处理重点实验室，广西桂林 541004；2.桂林电子科技大学信息与通信学院，广西桂林 541004）

针对云计算的可信服务选择与多个约束目标问题，提出一种基于服务能力与信任约束的任务调度算法。该算法首先对资源进行服务能力和信任评估，然后在任务调度过程中根据用户任务对资源的服务能力需求，筛选满足条件的候选资源集，并构造一个以信任效益和服务费用权衡的综合效益函数，从候选资源集为任务筛选满足条件的资源子集，最后采用负载均衡策略进行调度。仿真结果表明，该算法能够为用户任务选择满足服务能力与信任需求的资源，具有较好的系统性能和负载均衡性。

云计算；任务调度；信任约束；综合效益

云计算的外包服务模式引起的云平台安全风险是云计算发展的障碍。如何构建安全可信的云服务是云计算亟需解决的问题［1］。云服务中资源与任务的分配与调度，由云计算任务调度机制完成。在云计算的任务调度中，服务提供商根据云用户的请求，选择满足其需求的可信资源［2］。

云计算作为一种商业服务模式，其采用信任机制实现服务的可信评估和决策支持。文献［3］面向信任服务提出一种云计算工作流任务调度算法，用直接信任和推荐信任度量信任关系，并以均衡策略将用户不同的调度目标进行均衡。文献［4］设计了一种基于安全意识与预算意识的调度策略，采用信任安全因子计算任务的优先级，并将预算费用作为约束目标进行任务与资源的映射。文献［5］基于粒子群算法，在云工作流中修改粒子群的适应度函数，将信任服务与存储服务作为资源选择的约束条件，实现资源与任务的映射。文献［6］以人际关系信任模型为基础，提出了包含用户对服务资源的信任需求和服务资源的可信度信任度量模型，满足任务在信任方面的需求，提高调度成功率。Fan等［7］提出了一种基于模糊差距度量和证据推理方法的二阶段评价模型来度量云服务的可信度，用户获得了高可信度的服务。通常用户任务的约束目标需求并不是单一的，针对云计算的可信服务选择与任务的多个约束目标需求问题，提出一种基于服务能力与信任约束的任务调度（TSTC）算法。

1 基于服务能力与信任约束的任务调度

资源的服务能力是云平台商业化运作的基础，而具有强大服务能力的可信资源能够进一步提高用户的满意度。

针对云计算任务调度中的任务请求与资源分配问题，引入资源服务能力与信任评估策略对资源进行评估，从资源的服务能力和可信度筛选出满足云用户需求的资源集。最后从系统全局出发，进行负载均衡调整，将合适的资源提供给云用户。任务调度结构如图1所示。

图1 任务调度结构Fig.1 The structure of task scheduling

1.1 资源服务能力评估

资源服务能力的评估从资源的性能属性考虑，主要包括资源的通信带宽Wr，存储能力Sr以及计算能力Cr。由于Wr、Sr、Cr单位不同且数值相差较大，采用min-max标准化方式对数据进行归一化处理，将不同类型的数据映射到区间［0，1］，使数据快速收敛。

其中：x为样本数据；xmax为样本数据的最大值；xmin为样本数据的最小值；x～为x的归一化值。

基于归一化处理，采用线性加权的方式计算资源的服务能力，以Qj表示资源rj的服务能力，则

1.2 资源信任评估

在云计算任务调度中，资源信任缺失引发的恶意行为将降低服务质量或导致任务调度失败［8］。因此，采用信任机制，从资源的安全性和可靠性评估云计算的资源信任［9］。

资源的安全性通过对任务的真实性、保密性和完整性进行评估，以srj表示资源rj的安全性，则

其中：Arj、Prj、Irj∈［0，1］分别为对资源rj进行归一化后的真实性、保密性和安全性结果；权重因子ω1、ω2、ω3∈［0，1］，且ω1＋ω2＋ω3＝1。

资源通常存在失效率，随着时间的推移，资源可靠性降低。因此，根据资源的失效率和系统的运行时间评估资源的可靠性。资源rj的可靠性

其中：frj为资源的失效率；ti为任务Ti执行前系统的运行时间［10］。

1.3 资源筛选

基于资源的服务能力和信任评估，在任务调度中，针对用户任务对资源服务能力、信任与服务费用需求，为用户任务筛选满足用户需求的资源集并选择合适的资源进行分配。

将用户任务对资源的服务能力需求量化处理，用户任务Ti的服务能力需求qi，

其次，将信任效益和服务费用需求进行权衡量化，用户对服务质量的综合满意度可以更好地筛选出满足用户综合需求的资源。

以U（i，j）表示任务Ti对资源rj的信任和服务费用需求的综合满意度，则

其中：权重因子λ1、λ2∈［0，1］，且λ1＋λ2＝1；Cij为任务Ti在资源rj上的服务费用；为任务的平均预计服务费用［11］。服务费用越小，信任效益值越大，筛选出的资源更符合用户需求。

采用任务Ti对资源rj的安全性隶属函数Us（i，j）和可靠性隶属度函数Uk（i，j）加权，可得信任效益：

2 仿真测试及结果分析

实验采用云仿真器CloudSim 2.1.1［12］对TSTC算法进行仿真。计算机环境为Intel（R）Core i5-4200M2.50GHz，内存8GB，操作系统为Windows 7。在仿真中，实现TSTC算法并将其添加到DatacenterBroker类中进行任务调度，重置Cloudlet类与VM类，设置任务与虚拟机资源的参数。

1）资源参数：设置50个资源，每个资源包含一个处理器，计算能力Cr、通信带宽Wr和存储能力Sr的分布区间分别为［300，500］、［800，1000］和［2000，2500］。

2）资源失效率分布区间为［0.000 1，0.001 5］。

3）资源服务能力量化权值a＝b＝0.3，c＝0.4。资源安全性评估权值ω1＝ω2＝0.3，ω3＝0.4。信任效益均衡权值θ1＝θ2＝0.5。综合效益均衡权值λ1＝λ2＝0.5。

在相同的仿真测试环境下，分别实现Min-min算法、信任驱动的Min-min（TD Min-min）算法［13］、服务质量感知的QTS算法［14］、TSTC算法，并对比了算法在总信任效益、时间跨度、用户平均满意度和负载均衡情况。实验中任务数分别设置为200、500、1000、2000。

2.1 总信任效益测试

总信任效益是被调度的任务获得的信任效益之和。总信任效益越大，说明本次调度提供的资源安全性越高。4种算法的总信任效益如图2所示。

图2 4种算法总信任效益Fig.2 Total trust benefit value of four algorithms

从图2可看出，TSTC算法总信任效益优于Min-min算法与QTS算法，略低于TD Min-min算法。这是由于TSTC算法除了考虑任务的信任需求外，还考虑了服务费用，而TD Min-min算法仅追求信任效益，每次调度都选择信任效益最大的资源进行匹配。

2.2 时间跨度测试

时间跨度是评价算法性能的重要指标，是待调度任务集中所有任务执行完毕所花费的时间。时间跨度值越小，表示任务完成越快，系统的调度性能越好。4种算法的时间跨度如图3所示。

从图3可看出，TSTC算法在任务数量较小时，时间跨度最小。随着任务数量的增加，时间跨度略高于QTS算法。随着任务数量的增加，服务能力需求低的任务数量相应增加，TSTC算法为了负载均衡，这些任务被安排到负载小但性能非最优的资源上。而TD Min-min算法仅追求高信任效益而忽略完成时间，因此时间跨度最大。

图3 4种算法的时间跨度Fig.3 Makespan of four algorithms

2.3 用户平均满意度测试

用户满意度是用户对任务被执行结果的满意程度。根据任务的服务能力、信任和费用需求被满足时进行满意度度量。用户任务Ti在资源rj上执行的满意度

用户平均满意度

其中n为任务集合中任务的个数。4种算法用户平均满意度如图4所示。

图4 4种算法用户平均满意度Fig.4 Average users satisfaction of four algorithms

从图4可看出，TSTC算法在调度中综合考虑用户的服务能力、服务可信度和服务费用需求，其用户满意度与致力于服务质量感知的QTS算法近似。TD Min-min算法与Min-min算法仅追求单一目标的优化，用户平均满意度较低。

2.4 负载均衡测试

负载均衡用资源负载的相对标准差（RSD）来表示，其能较好地表达一组数据的离散程度，反映了资源的负载均衡情况。RSD越小，资源负载越均衡。4种算法的负载均衡如图5所示。

图5 4种算法的负载均衡Fig.5 Load balance of four algorithms

从图5可看出，TSTC算法的负载均衡性最优。因为在调度过程中，TSTC算法把对资源服务能力需求低的任务映射到满足条件且负载最小的资源上，进行了负载均衡调整，提高了资源利用率与系统性能。

3 结束语

针对云服务信任缺失与用户任务约束目标需求问题，提出一种基于服务能力与信任约束的任务调度算法。该算法通过资源服务能力评估与信任评估，为用户的服务质量需求提供选择依据。在资源筛选中，将信任效益与服务费用加权作为综合目标，均衡了用户多方面约束目标需求。算法将低服务能力需求的任务调度到负载小的资源上，获得了良好的负载均衡性。仿真结果表明，TSTC算法能够满足用户对资源服务的性能、可信度和服务费用的需求，提高了用户满意度，具有较好的负载均衡性。

［1］ 丁滟，王怀民，史佩昌，等.可信云服务［J］.计算机学报.2015，38（1）：133-149.

［2］ LIN Weiwei，LIANG Chen，WANG J Z，et al.Band-width-aware divisible task scheduling for cloud computing［J］.Software：Practice and Experience，2014，44（2）：163-174.

［3］ TAN Wenan，SUN Yong，LI L X，et al.A trust serviceoriented scheduling model for workflow applications in cloud computing［J］.IEEE Systems Journal，2014，8（3）：868-878.

［4］ ZENG Lingfang，VEERAVALLI B，LI Xiaorong.SABA：a security-aware and budget-aware workflow scheduling strategy in clouds［J］.Journal of Parallel and Distributed Computing，2015，75：141-151.

［5］ YANG Yuli，PENG Xinguang，CAO Jianfang.Trustbased scheduling strategy for cloud workflow applications［J］.Informatica，2015，26（1），159-180.

［6］ 曹洁，曾国荪，姜火文，等.云环境下服务信任感知的可信动态级调度方法［J］.通信学报，2014，35（11）：39-49.

［7］ FAN Wenjuan，YANG Shanlin，PEI Jun.A novel twostage model for cloud service trustworthiness evaluation［J］.Expert Systems，2014，31（2）：136-153.

［8］ LI Wenjuan，WU Jiyi，ZHANG Qifei，et al.Trust-driven and qos demand clustering analysis based cloud workflow scheduling strategies［J］.Cluster Computing：the Journal of Networks Software Tools and Applications，2014，17（3）：1013-1030.

［9］ WANG Wei，ZENG Guosun，TANG Daizhong，et al.Cloud-DLS：dynamic trusted scheduling for cloud computing［J］.Expert Systems with Applications，2012，39（3）：2321-2329.

［10］ POOLA D，GARG S K，BUYYA R，et al.Robust scheduling of scientific workflows with deadline and budget constraints in clouds［C］／／28th International Conference on Advance Information Networking and Applications，2014：858-865.

［11］ SU Sen，LI Ji，HUANG Qi，et al.Cost-efficient task scheduling for executing large programs in the cloud［J］.Parallel Computing，2013，39（4／5）：177-188.

［12］ CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al.CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Software Practice ＆Experience，2011，41（1）：23-50.

［13］ AZZEDIN F，MAHESWARAN M.Integrating trust into grid resource management systems［C］／／Proceedings of the International Conference on Parallel Processing，2002：1-8.

［14］ 周发超，王志坚，叶枫.一种新型的云任务调度算法研究［J］.中国科学技术大学学报，2014，44（7）：590-598.

编辑：曹寿平

A task scheduling algorithm based on service ability and trust constraint in cloud computing

ZHENG Xin1，2，WU Xiaonian1，2，MENG Chuan2，LI Hao2
（1.Key Laboratory of Guangxi Wireless Broadband Communication and Signal Processing，Guilin University of Electronic Technology，Guilin 541004，China；2.School of Information and Communication Engineering，Guilin University of Electronic Technology，Guilin 541004，China）

In view of selecting trusted service and multiple constraint objects in cloud computing，a task scheduling algorithm based on service ability and trust constraint is proposed.Firstly the service ability and creditability of resources are assessed.And then during the process of task scheduling，the candidate resources are selected if their service ability meets the requirements of users.Furthermore a comprehensive benefit function is designed by the weight of the trust benefit and cost，resource with the biggest comprehensive benefit is selected from the candidate resources.Finally the task is assigned to a resource according to load balancing strategy.Simulation results show that the algorithm can satisfy service ability and the trust requirements of users.And the performance and load balance of the system is good.

cloud computing；task scheduling；trust constraint；comprehensive benefit

TP393

：A

：1673-808X（2016）05-0382-05

2016-03-12

国家自然科学基金（61572148）；广西自然科学基金（2015GXNSFGA139007）；广西无线宽带通信与信号处理重点实验室基金（GXKL061510，GXKL0614110）；桂林电子科技大学研究生教育创新计划（YJCXS201524）

武小年（1972-），男，湖北监利人，副教授，硕士，研究方向为分布式计算、信息安全。E-mail：xnwu＠guet.edu.cn

郑鑫，武小年，孟川，等.云计算中基于服务能力与信任约束的任务调度算法［J］.桂林电子科技大学学报，2016，36（5）：382-386.