隐私与成本感知的云工作流调度方法_文一凭_W

1、第 卷第期 计算机集成制造系统 年月 ： 隐私与成本感知的云工作流调度方法 文一凭，刘建勋，陈聪阳 （湖南科技大学 知识处理与网络化制造湖南省普通高校重点实验室，湖南 湘潭 ； 南京大学 计算机科学与技术系，江苏 南京 ） 摘 要：针对云工作流执行过程中的用户隐私保护需求，建立了相应的云工作流调度模型，在粒子群优化算法及模拟退火智能优化算法的基础上，通过引入经典表调度算法 中的任务优先级计算策略，提出一种具有隐私与云资源使用成本感知能力的云工作流调度方法 。该方法采用考虑成本因素的上行与下行权重来计算各个工作流任务的优先级，结合隐私保护需求搜索并优化调度方案。通过仿真实验说明了该方法的有效性。

2、 关键词：云工作流；隐私；成本；调度；感知中图分类号： 文献标识码： ， ， ，（ ， ，； ， ， ，） ： ， （） （）， ， ：； 调整所需要的云服务资源，从而使传统工作流中 引 言 的资源调度与管理等方法都需要重新设计与思考。在 工作流是一类能够完全或者部分自动执行的业务过程，这类业务过程广泛存在于电信、金融、制造、医疗和科学计算等领域中。近年来，随着云计算技术的蓬勃发展，越来越多的组织将传统的业务过程与应 用迁移到云计算环境。与传统计算环境相比， 云计算环境采用面向市场的商业模式，可让用户通过网络以按需、按使用付费的方式选择、获取并随时 此背景下，云计算环境下的工作流资源调度（或称

3、云工作流调度）成为一个新的研究热点。 隐私指用户认为是自身敏感且不愿意公开的信息。在云计算环境中，数据的存储和安全完全由云计算提供商负责，对用户的隐私保护存在着极大的风险。目前，尽管国内外学者已对云工作流调度开展了大量研究，但现有方法很少考虑云计算带 收稿日期：。 基金项目：国家自然科学基金资助项目（，）。： ，（，） 文一凭 等：隐私与成本感知的云工作流调度方法 第期 来的数据隐私保护问题。供应链管理和健康医疗等算环境中执行这些业务过程，将不可避免地进行跨数据中心的数据传输。如果调度时不考虑隐私数据的存储位置等因素，随着业务过程的反复运行，不 但将极大地增加用户隐私的泄露风险，而且由于云存储

4、资源需付费使用，还将增加云用户的使用成本。 为此，本文在现有云工作流研究的基础上，进一步研究考虑用户隐私保护需求的云工作流调度模型， 并将经典表调度算法与元启发式智能搜索算法相结合，设计具有隐私与成本感知能力的调度方法。 相关研究 云工作流调度是映射并管理一组相互依赖的任务在云服务资源中执行的过程，调度方案不仅可对系统的性能产生显著影响，还将直接影响用户的使用成本与云服务提供商的收益。为此，在成本感知的云工作流调度研究方面产生了一系列成果。文献 从服务质量、系统功能和系统架构三个方面分析 了云计算环境下成本感知的工作流系统所面临的挑 战，并据此对现有成本感知的云工作流调度方法进行了分类；文献采

5、用微粒群优化（ ，）算法与蚁群优化（ ，）算法研究了云计算环境下的工作流 调度问题，提出一种面向市场的分层调度策略； 文献通过对经典表调度算法 （ ）进行扩展，以最小化完成时间 与成本为目标，结合亚马逊弹性计算云（ ，）的运营特点，提出一种多目标云工作流调度算法 （云计算环境下由第三方服务供应商提供的存储服 务中的个人媒体数据隐私保护问题的解决方案， 该方案主要包括四部分： 用于清洗媒体数据的垂直数据分块； 用于访问媒体数据集的数据合并； 完整性检查； 对普通文本与加密文本的混合搜索。此外，也有一些方 法从有别于上述三类技术的新的角度展开研究。例如：文 献采 用本体和描述逻辑进行隐私属性的描述

6、，提 出一种云计算中面向需求的隐私保护框架，该 框架包括隐私冲突检测层、隐私策略协商层和隐 私协定取证层三个层次； 文献从跨域云场景中的企业隐私角度出发， 提出一种用于大数据应 用的隐私感知的跨云服务组合方法，以保护服务 组合中云服务交互（执行） 记录的细节；文献针对移动健康服务中用户隐私保护偏好与用户个性化需求 保障之间的天然矛盾开展研究，探讨如 何选择最少或者最优的个性化特性指标，以使系 统既能满足为用户提供个性化服务的质量要求、又 能较好地保护相关的隐私信息。 但是，如何在云工作流执行中尽可能地保护隐私数据，是现有云工作流调度研究的一个盲点，考虑数据安全需求的云工作流的相关研究并不多见。

7、文献为保障公有云环境中的企业安全需求，提出选择执行工作流或工作流子集的安全解决方案；文献考虑在执行工作流任务时用户不同程度的安全需求，对云服务的安全性进行量化，并基于安全与成 本考虑引入不可移动数据集的概念，提出安全与成本预算感知的云工作流调度策略。本文将在上述研 究的基础上，进一步探讨用户隐私保护需求与成本 感知的云工作流调度问题。 * 问题描述 ）。 对于云计算环境中的隐私保护问题 ，现 有研究主要采用数据加密 、数据扰动与数据 三类技术。文献提 出一种云环境下解决移动设备 。针对云计算环境中数字内容安全和用户隐私保护本文主要研究在涉及跨数据中心数据传输的云工作流执行过程中，如何在满足用户

8、隐私保护约束的前提下，以最小的云资源使用成本来完成应用调度。为方便描述该问题，下面首先介绍目标系统的相关定义与说明，然后给出本文所采用的云资源使用成本模型。 的需求，文献针对跨组织间协作中的医疗健康数据安全共享问题，采用基于属性 的加密等方法， 提出一个可在半可信跨云计算环 境中保护患者数据安全与隐私的系统架构。文献提出 系统模型 定义 工作流应用描述。一个工作流应用可以描述为 （，），其中： 是一组工作流任务的集合 ， 计算机集成制造系统 第 卷?，?， 为任务名称， 与 分别为与该任务相关的输入与输出数据集， 描述该任务的计算量大小； 为一组有向边的集合，用以描述工作流任务间的控制流依赖情

9、况， ?，?，? ，若?，?，则称 为 的前驱任务； 描述了工作流任务间的数据流依赖情况， ?， ?， ， 是向 传递的数据量大小，单位为 ， 且 ； 源的一个有效映射，若其中的元素 ，则表示任务 被调度到虚拟机 上执行。 云资源使用成本模型 云计算环境下，如果一个工作流任务有多个输入数据集，则必须在该任务开始执行前将输入数据集传输到任务所在的执行位置。因此，执行云工作 流所需花费的资源使用成本主要包括计算成本、传 输成本、存储成本三部分，表示为 。（） 为便于计算，设工作流任务 的直接前驱任务 为工作流相关数据的集合，包 括任务的输入集为（），即（ ） ，输出数据等， ?，?，为与 分别为虚

10、拟机 上第一个与最后一个被执行数据的唯一标识符， 表示 的数据量大小， 的任务，（ ， ）与（ ， ）分别为 上 的开 表示数据的隐私属性。 始时间与 的完成时间，并假设云服务提供商采用定义 数据中心。目标系统中的可用数据中心可描述为 ?，?，其中： 表示数据中心 当前可用的存储空间总 量， 表 示 的 存 储 价 格，单 位 为 。 每单元定价的形式收取费用，即根据用户的使用总量，以每单位资源的价格乘以总量的方式计算服务费 用。因此，给定调度方案，虚拟机执行工作流任务所需的计算成本表示为 （，）（，） 定义 虚拟机资源。假设各云服务提供商可 提供不同租赁价格与配置的虚拟机资源来执行工作 流任

11、务，这些资源可表示为 ?， ，?，其中： 表示虚拟机的计算能力， 表 ； （） （，） （，）（，）；（） （ ） （ ， ） （ ， ） 。 （） 示收费时间单位， 表示该虚拟机的价格函数（如 常值型函数或周期分段型函数）， 表示该虚拟机式中 （，）为任务 开始执行前，将 的输出所在的数据中心。 定义 通信带宽与传输价格。假设存在 个数据中心，各数据中心之间的通信带宽与传输价格 分别用矩阵 与 表示，其中： （， 数据传输到 所在的执行位置所需的传输时间。 假设任务 与 所在的执行位置分别位于数据中心 与 ， 向 传递的数据量大小为 ，则相应的传输时间、传输成本分别表示为 ）表示 到 之间的

12、通信带宽，单位为 （，） ； （） ； （，）表示到之 （ ，） 。 （） 间的传输价格，单位为。 因此，给定调度方案，其所需的传输成本、存定义 隐私保护需求。用户的隐私保护需求可表示为：，矩阵 代表工作流中储成本表示为 （ ，）； （） 所包含的用户隐私数据到数据中心的一个有效映 。 （）射，若其中的元素 ，则表示用户的隐私数据 （ ） 需存放在数据中心 上。 定义 云资源使用成本。云资源使用成本是完成工作流任务所花费的费用，主要包括执行任务所需的计算费用、存储数据所需的费用、传递任务输入与输出数据所需的费用三部分。 定义 调度方案。该方案可表示为： ，矩阵 表示工作流中所有任务到虚拟机资

13、隐私与成本感知的云工作流调度算法 表调度算法与元启发式智能优化算法是解决工作流调度问题常用的两类方法。表调度算法的基本思想是：首先计算各任务的优先级，然后根据任务的优先级大小，按降序依次为任务分配合适的资源。为提高调度的有效性，本 文结合经典表调度算法 文一凭 等：隐私与成本感知的云工作流调度方法 第期 （） 与 、式中：表示第 个微粒，（）为微粒 当前的个体 模拟退火（，）算法，提出最优位置，（）为所有微粒当前的全局最优位置， 一种隐私与成本感知的云工作流调度算法 （ ），该算法主要分两步：计算任务优先级；优化调度。 计算任务优先级 算法将上行与下行权重之和作为各个任务的优先级，但并未考虑资

14、源使用成本因素。为此， 与 为正的学习因子， 与 为 均匀分布的随机数。 惯性权重 是 算法中最重要的参数之一，能够直接影响算法寻找潜在最优解 的整体时间。目前已有许多对 值进行动态选择或修正的方法， 在本文算法中，为降低算法寻找最优解的计算时间， 微粒在第次迭代时的惯性权重 采用 算法通过借鉴其计算策略，分别采用式（） 算法进行动态更新，即 和式（）计算各个任务的上行与下行权重。 烄 ， ； （ ） （ ） （ ） 烅 （） （ （ ，）（）； （） ，其他； 烆 （ ）（ ， （ （ ）（ （）； （ ） （ ） 烄 （ （）（ （） （，） （）。 （） 式中：（）为工作流任务 的直接后

15、续任务集， 烅 烆， 其他。 （） （ ） ， ； 为 在不同 式中： 为 均匀分布的随机数， 为接受概 （ ） 类 型 虚 拟 机 上 执 行 所 需 的 平 均 计 算 成 本； （ ，）为任务 将 大小的数据传输到 所花费的平均传输成本。计算任务的优先级，相当于对工作流中的任务调度进行预处理，提 前对工作流中要进行调度的任务进行排序，从 而在为任务安排虚拟资源进行调度之前首先获得一 个任务的调度列表，尤其对并行任务而言，能够很 好地提高任务的并发性，相对于直接分 配任务的方法虽然增加了排序的时间，但却能较 好地降低执行工作流所花费的资源使用成本。 优化调度 算法中的优化调度阶段主要基于标

16、准 算法进行迭代寻优。微粒的各个位置分量均与不同的工作流任务对应，代表为该服务分配的虚拟机编号。用户的隐私保护需求作为设置、更新 各微粒位置时的约束条件，使相关任务只能调度到指定的数据中心执行。 同时，为提高算法性能， 算法采用动态调整惯性权重参数的策略更新各微粒位置，即在第 次迭代时，分别按式（）和式（）更新各微粒的速度和位置： （）（）（） （）（）（）； （） （） （）（）。 （） 率， 为当前退火温度，（）与（）分别为微粒在第 次、第次迭代时的优化目标函数（即执行云工作流所需花费的资源使用成本） 适应值。 粒子如果在初始阶段就找不到一个比较好的位置，则容易陷入局部最优，从而降低粒子的

17、全局搜索能力。 算法能够克服局部搜索过早收敛，以一定的概率接受较差解，从而避免搜索时陷入局部最优，从而很好地平衡例子的局部和全局搜索能力。 仿真实验 为分析和评估 算法的性能 ，本 文在平台上参照 中的按需实 例进行仿真实验。实验设置有 个数据中心 、 个不同类型的虚拟机实例，所采用的工 作流模型与数据中心连接情况分别如图和图所示，工作 流中各任务参数（通过随 机产生 个任务、每个任务不同大小的数据）设 置如表 所示，不同类型虚拟机实例参数设置如表 所示。 算法与标准 算法（ ，）（将文献中提出的 算法称 为标准 算法，以区别对其改进后的 算法） 在实验中的种群规模均为，学习因子 。 计算机集

18、成制造系统 第 卷表 各工作流任务参数设置 任务任务输入数据 输出数据数据的隐私编号长度保护需求 也优于 算法。这说明本文所提的 算法能够适应数据密集型工作流调度的需求，其在平均完成时间优化方面也优于 算法。 需存放在数据中心 需存放在数据中心 表 不同类型虚拟机实例参数设置 实例类型 单价 存储价格 传输价格 （ ）（ ） （ ） 图 和图 所示为不同工作流实例数量下，根据 算法与 算法得出的调度方案执行所有工作流任务所需的平均成本与时间。由图 易知，在成本优化方面 算法明显优于 算法。这是因为 容易陷入局部收敛，而 经过， 等过程的优化，增强了算法的全局搜索能力，较好地提升了算法的全局求解

19、能力，能够获得较好的解，保证任务平均调度成本的最小化。同时由图易知，在任务数较少时，使用 得出的平均调度时间与 几乎相同，但随着任务数的增加， 得出的平均调度时间明显比 优越，说明本文所提 算法能够适应云工作流调度的需求，其在执行时间优化方面 文一凭 等：隐私与成本感知的云工作流调度方法 第期 图和图所示为隐私保护需求对算法结果的影响。由图和图易知，在非隐私保护调度的情况 下， 的性能与 相比提升得并不明显，这是因为 主要是针对隐私保护进行的调度，相对于普通工作流任务的调度并不能体现其优越性。但在隐私保护调度的情况下， 的性能比 的性能优异的多， 能够较好地减少因任务的隐私保护所需的额外调度时间和成本，平均调度时间和成本分别减少和。 计算机集成制造系统 第 卷 结束语 ）刘雅辉，张铁赢，靳小龙，等大数据时代的个人隐私保护计算机研究与发展，（）： ，（）： ， ， ，（）： ，