基于多阶段的混合云多目标任务调度策略研究.pdf

第 卷 第 期 年 月南昌工程学院学报 收稿日期：基金项目：中央引导地方科技发展资金项目（）；太原科技大学研究生联合培养示范基地项目（）；太原科技大学研究生教育创新项目（）作者简介：崔志华（），男，博士，教授，文章编号：（）基于多阶段的混合云多目标任务调度策略研究崔志华，赵孟凯，郭婉婉（太原科技大学 计算机科学与技术学院，山西 太原 ）摘要：为了解决混合云环境中任务调度问题，本文研究了多阶段任务调度策略以应对混合云架构灵活的特点和用户多样化的服务需求。首先，设计了数据感知资源供应算法，结合任务量和私有云性能判断是否对可用资源池进行成本最小化的动态扩展，保证任务能够在截止时间内顺利完成。其次，为了满足用户多样化的需求，考虑任务完成时间、数据安全性和负载均衡构建了混合云多目标任务调度模型。最后，为了更好地求解模型，提出了改进的 算法，该算法通过结合收敛性指标和拥挤度距离进行环境选择和匹配选择，使得算法在非支配解较多的时候仍然能够取得优秀结果。通过仿真模拟，提出的调度算法不仅能花费最小公有云租用成本，还能在保证任务截止时间完成任务的基础上，对数据安全和负载均衡产生显著优化效果，对比初始调度方案，其性能提升了 。关键词：混合云环境；任务调度；多目标优化算法；多阶段中图分类号：文献标志码：，（，）：，：；近年来，混合云架构以其灵活、可扩展的特性，受到了越来越多企业用户的青睐，大量的企业和组织开始利用混合云架构来部署应用系统 。混合云 由一个以上的私有云和公有云组成。其中，私有云一般指企业自建的云服务，因而能够提供对数据隐私、安全性和服务质量最有效的控制，核心属性是专有资源服务。公有云通常指第三方供应商提供的云服务，其优点是具有近乎无限的资源量，核心属性是共享资源服务 。由于数据安全性的原因，企业希望将隐私数据托管至私有云上，然而其有限的资源量往往不能支持企业处于业务高峰时处理大规模的数据所需的计算资源。此时使用公有云扩展资源已经成为企业用户的首选。因此，基于混合云独特的优势和企业多样性的云服务需求，如何在混合云环境中合理调度私有云和公有云资源，从而充分利用混合云的特点并提高用户的满意度，成为了一个关键问题 。针对混合云环境下的任务调度问题，国内外学者开展了广泛的研究。文献 提出了一种基于市场的混合云优化调度方法，多个云服务商共同组成市场，通过本地和全局双层调度优化了 满足率和任务分配效率。针对混合云中公有云和私有云的成本最小化问题，文献 将这个问题建模为混合整数线性规划，并提出了一种时分任务调度算法 ，将任务有效地分配给公有云和私有云。与现有的调度策略相比，的调度策略可以在满足任务时延约束的同时，提高吞吐量，降低私有云成本。文献 基于性能和费用目标提出了两种调度策略，对于截止时间要求比较高的任务可以优先调度至公有云，对费用要求高的任务可以优先调度至私有云，且两种策略均满足截止时间和一定的费用约束。在文献 中，提出了基于 神经网络优化的任务调度方法，将成本和期限作为约束，最大化私有云资源利用率，提高了云服务服务质量。上述研究虽然对混合云调度过程中的完成时间、成本、资源利用率等目标进行了优化，但是在调度过程中却忽略了云任务的数据安全和隐私保护需求。因为部分任务可能涉及大量用户信息，包括公司数据、个人健康等隐私信息，如果这些任务被分配到不可靠的公有云执行，相关隐私数据则存在泄露的风险。因此在混合云调度中考虑数据安全和隐私保护是必不可少的。在保护隐私信息方面，文献 采用身份验证服务、完整性服务和机密服务来构建安全模型，同时提出了一种安全和成本感知调度（）算法，将截止时间和风险率作为约束，优化任务执行成本。等研究了隐私或敏感数据被限定在私有云的前提下，通过提出的多目标隐私感知工作流调度（）算法优化了任务时间和成本。文献 构建了混合云环境下成本与隐私感知的工作流调度模型，并提出一种相应的云工作流调度算法（）。该算法可在混合云环境下调度多个云工作流应用，并在满足降低隐私暴露风险与截止时间约束的前提下，优化执行成本。然而，这些工作大多都将云任务数据按照隐私等级进行分类，隐私级别较高的任务分配到私有云中执行，隐私级别较低的可以分配到私有云和公有云执行。但是对于企业实际的用云需求，云任务可能同时具备截止时间、成本和安全隐私等多重约束。因此，仅仅按照隐私级别进行二元决策是不够的。只有考虑多目标优化理论 ，平衡相互冲突的不同需求，才能得到企业满意的任务调度策略。另一方面，以往研究大多都忽略了企业实际用云中何时扩展公有云资源以及购买多少公有云资源的问题。针对以上问题，本文考虑了混合云的特点和优势，设计了多阶段的混合云环境多目标任务调度策略。在第一阶段，提出了截止时间约束的数据感知资源供应算法，基于任务规模求解合适的公有云资源数量。在第二阶段，考虑任务完成时间、数据安全、负载均衡构建多目标任务调度优化模型。最终，为了更好地求解模型，设计了结合收敛性和拥挤度距离进行环境选择的 算法，得到了符合用户满意度的调度策略。混合云环境下任务调度问题建模及求解 问题描述首先，为了更好地构建混合环境云任务调度模型，做出以下假设：（）本工作研究的混合云任务调度是一个时间片段内的静态问题，云任务为独立任务且没有优先级关系，任务被提交后同时分配给虚拟机资源。（）每个虚拟机性能稳定且无故障，任务分配到虚拟机后，一旦开始执行中途无法停止。（）多个任务分配在同一个虚拟机空间共享资源，即在虚拟机上串行执行任务。在混合云调度模型中，用户提交的任务集合表示为 ，为任务个数。表 展示了云任务和虚拟机的详细参数及含义。此外，由不同云服务提供的虚拟机共同构成了用户可用的虚拟资源池，其中每个云服务均提供多个虚拟机。资源模型中的虚拟机集合表示为 ，为虚拟机个数。同时，为了便于管理，每个云服务中的虚拟机性能保持一致。第 期崔志华，等：基于多阶段的混合云多目标任务调度策略研究表 任务参数参数描述任务虚拟机中执行的云任务大小 云任务上传数据大小 云任务下载数据大小云任务隐私等级虚拟机虚拟机安全级别 虚拟机内存大小 虚拟机储存大小 虚拟机平均执行速度虚拟机上传带宽虚拟机下载带宽 截止时间约束的数据感知资源供应算法为了满足企业灵活的资源数量需求，发挥混合云架构可扩展的独特优势，企业需要从公有云中无缝获取资源和释放资源。同时，如今主流的云计算按量付费模式最小租用时间为。因此，调度程序必须根据私有云的资源数量，对必须外包给公有云的任务量做出有效决策 ，以满足应用程序的截止时间限制。同时任务在私有云执行时，由于数据处于本地不需要考虑传输时间，而任务在公有云执行时则需要考虑数据上传和下载的传输时间。在第一阶段，企业需要根据提交的任务列表，选择最合适的公有云资源数量，在保证截止时间的约束下，最小化成本。算法 展示了本文提出的数据感知资源供应算法。首先通过云任务的具体属性值计算任务量和传输量。随后根据私有云的性能计算其在截止时间内能够完成的任务量，从而判断是否需要从公有云扩展资源。由于在公有云资源上执行任务需要将数据从本地存储传输到分配的虚拟机上，因此算法将计算剩余任务量在公有云执行所需的传输时间。通过截止时间减去总传输时间和资源启动时间来计算可有效用于任务执行的实际剩余时间。最终，结合剩余时间和公有云性能计算能够满足截止时间要求的公有云资源量。任务总量、数据上传总量 和数据下载总量 的计算公式如式（）（），其中任务，和 分别表示第 个任务的任务大小、上传数据量和下载数据量。，（），（）（）私有云在截止时间内能够执行的任务量计算为 ，（）式中 是截止时间，表示私有云虚拟机数量。公有云执行剩余任务所需的上传时间、下载时间和执行时间计算为 （），（）（），（）（）由于私有云不需要进行数据传输，因此无法获得准确的剩余传输量，本工作采用对照任务量等比例估算的方式获得。需要扩展的公有云资源数量计算为 （）式中 为启动资源的等待时间；为需要扩展的公有云虚拟机数量，同时采用进一法保持整数。数据感知资源供应算法如下：通过式（）（）计算总任务量和数据传输总量；：通过式（）计算私有云在截止时间内能够完成的任务量；：通过式（）（）计算公有云执行剩余任务所需上传时间、下载时间和执行时间，通过式（）计算需要购买的公有云资源量；：不需要使用公有云对可用资源池进行扩展。多目标任务调度优化模型在第二阶段，对于给定的资源数量，为了进一步优化时间，并且满足用户的多样化需求，在考虑了任务最大完成时间、安全性和负载均衡的前提下构建了多目标混合云任务调度优化模型。任务完成时间任务完成时间表示从用户提交任务到收到执行结果之间的时间跨度。公有云中的任务完成时间由执行时间、等待时间和传输时间组成。由于私有云是本地建立的，因此不需要考虑任务传输时间，私有云的任务完成时间由执行时间和等待时间组成。同时，混合云环境中的多个虚拟机是并行执行任务的，因此将运行时间最长的虚拟机作为整个调度过程的最终完成时间。任务完成时间的计算如式（）（）所示。（），（）南昌工程学院学报 年 ，（），（）()（）式中 和 分别为虚拟机数量和分配至第 个虚拟机中的任务数量；、和 分别为第 个虚拟机的执行时间、传输时间和等待时间；、和 分别为第 个虚拟机上第 个任务的大小、上传数据大小和下载数据大小；、和 分别为第 个虚拟机的平均执行速度、上传带宽和下载带宽。数据安全性数据安全是所有企业用户上云最关注的问题之一。在本文中，任务被划分为多个隐私等级，表示该任务分配至公有云执行时被攻击的概率，其值通过任务数据的影响范围、影响主体、影响时间等因素进行划分。同时，云服务也将划分为不同的信任级别，表示云任务数据在受到攻击时云服务能够泄露任务数据的概率，其值通过对云服务可靠性、安全性等指标进行多维度评估，本文不作深入研究。因此，安全性方面只评估不同隐私级别的任务运行在不同信任级别的云服务上的风险，其值越小越好。（）（），（）式中 为任务个数，（）为第 个任务被攻击的概率，（）表示第 个任务在受到攻击时云服务能够保护其数据的概率。负载均衡负载均衡表示云任务在各个资源节点的分配情况，负载均衡越低，说明各个云服务虚拟机上的任务分配比较均衡，其资源利用率也就越高，能够充分利用云服务的性能。由于不同的任务具有不同的任务量和传输量，因此本文通过完成时间计算标准差来平衡每个云服务的负载，标准差系数越小，分配给虚拟机的负载越均衡，混合云的整体性能就越高。（）槡，（）（）式中 为虚拟机数量；为第 个虚拟机的任务完成时间。综上所述，通过考虑混合云任务调度过程中的各种因素，构建了一个多目标混合云任务调度优化模型。改进的 算法上述模型需要用到多目标算法求解，其中，算法 被广泛运用于复杂的、非线性的多目标优化问题。但是 在种群迭代的收敛性，防止陷入局部最优等方面还需要改进。本文在算法每次迭代后选择理想点，将理想点与个体的距离作为收敛性指标。通过结合收敛性和多样性设计环境选择策略从而对原算法进行改进。当 算法对 个目标进行优化时，由于维度较高，在算法迭代过程中会出现大量的非支配解，使用拥挤度距离对非支配解进行选择时仅考虑了种群的多样性。使得算法的收敛性不足，本文使用式（）（），结合理想点距离和拥挤度距离对环境选择策略进行扩充，使种群能够保留更好的个体，在后期扩展种群规模。同时将此指标辅助锦标赛选择法来改进匹配选择，加速种群的收敛，得到更优的分配策略。，（）（）槡，（）()（）式中 和 分别为算法的当前迭代次数和最大迭代次数；和 分别为种群大小和目标个数；为理想点；为第 个个体中第 个目标的值；为第 个个体的拥挤度距离。仿真实验与分析选择了近年一些经典、优秀的多目标优化算法 ，和 ，通过标准测试集和模型优化结果从而验证本文提出的混合云任务优化模型和改进的 算法的优越性。实验参数设置实验 的 硬 件 环 境 为 （），。应用环境为 框架 和 。实验中设置了一个公有云服务一个私有云服务，其属性值的参数设置如表 所示。云任务属性参数设置如表 所示，组合其中不同的属性值得到不同的云任务。实验中测试的多目标优化算法的参数设置均与文献 保持一致。第 期崔志华，等：基于多阶段的混合云多目标任务调度策略研究表 虚拟机参数属性属性私有云公有云 （）表 任务参数属性属性值 ，（），为了验证改进的 算法的优越性，在标准测试集 和 上分别比较了改进的 算法与其他 种多目标算法的性能。算法种群大小设置为 ，目标数为 ，独立运行 次，每次评价 次。实验结果使用反向代际距离（）评价，其值是参考点位于最近的总体之间的欧氏距离。值越低，算法的性能越好。从表 可以看出，改进的 算法在 的测试函数中均取得了最佳的结果，在 上性能最优，其他算法均没有取得较好的结果。说明在 个目标的情况下，由于非支配解增多，改进的 算法在收敛性和多样性上具有显著的优势。从表 可以看出，算法在 测试函数中，、和 上均取得了最优的结果。在 上效果最佳，在 上得到了最好的值，而 则在 和 效果最好。因此，本文提出的改进 算法在优化 个目标时，相比于其他多目标算法具有明显的优势。表 种算法在 测试集上 结果展示问题函数目标数 （）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）表 种算法在 测试集上 结果展示问题函数目标数 （）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）南昌工程学院学报 年 混合云模型验证为了对混合云任务调度模型进行求解，得到优秀的分配策略。本节对模型的完成时间、安全性和能耗进行全面优化。任务个数为 ，私有云虚拟机数量为 ，算法种群大小设置为 ，迭代次数为 ，任务截止时间设置为 。通过数据感知资源供应算法可以计算出公有云虚拟机个数为 。图 展示了 种算法分别在任务完成时间、数据安全和负载均衡上的优化效果。为了充分展示最终的优化效果，目标值为种群个体的平均值，且初始化的目标值经过了缩减处理。从图 中可以看出，在任务完成时间和负载均衡两个目标上，改进的 算法均取得了最优的效果，平均值分别达到了 和 。而由于目标之间的冲突性，在两个目标达到最优的情况下，改进的 算法在数据安全性上效果不佳，其平均值为 ，处于所有算法的第 位。总体来看，改进的 算法在模型上得到了最优的优化效果。图 种算法在完成时间上的优化结果图 种算法在数据安全上的优化结果图 种算法在负载均衡上的优化结果由于多目标优化算法能够得到一组解，决策者需要按照其偏好选择合适的分配策略。表 展示了种在 个目标以及综合考虑的情况下，最优的目标优化结果。对于综合考虑的情况，本文分别对 个目标进行归一化，随后叠加取最小值作为综合指标。从表中可以看出在完成时间上改进的 算法和 均能优化至任务截止时间 。在数据安全上除了 之外，其他算法均能将发生风险的概率降为 。而在负载均衡上，表现优秀，其最小值达到了 ，改进的 算法排在第 位。最后，在综合考虑的情况下，算法显著优于其他算法。相比于初始化种群的综合指标，优化了 的性能。表 种算法在不同偏好下的结果展示算法完成时间 数据安全 负载均衡综合考虑 综上所述，本文提出的 算法可以在混合云多目标任务调度模型上发挥显著的效果，从而帮助决策者得到优秀的任务调度方案。结论混合云架构作为近年来云计算的发展方向，以其灵活的特点，为企业多样化的用云需求提供了解决方案。本文通过分析混合云架构的特点，设计了多阶段的云任务调度策略，在第 阶段，通过数据感知算法对截止时间和任务量进行评估，最小化需要租用的公有云资源量，从而降低成本。第 阶段，在第 期崔志华，等：基于多阶段的混合云多目标任务调度策略研究保证任务截止时间完成任务的基础上，进一步优化数据安全和负载均衡，从而提高用户的满意度。经过实验验证，本文提出的方法不仅能在任务截止时间内花费最小的成本，还能优化数据安全性和负载均衡。对比初始种群，其性能优化幅度达到 ，为企业提供了更高质量的分配策略，提高了云服务资源利用率。参考文献：，（）：，（）：，：田倬瞡，黄震春，张益农 云计算环境任务调度方法研究综述 计算机工程与应用，（）：，（）：，：，（）：左利云，董守斌，舒磊 混合云中基于截止时间和费用约束的调度方法研究 计算机应用研究，（）：，（）：，（）：，：，：文一凭，王志斌，刘建勋 混合云环境下成本与隐私感知的工作流调度方法 计算机集成制造系统，（）：蔡星娟，胡钊鸣，张志霞 基于高维多目标优化的多无人机协同航迹规划 中国科学：信息科学，（）：，（）：，：，：，（）：，：，：，：，（）：，：南昌工程学院学报 年