一种用于移动边缘计算环境下的工作流任务迁移方法

摘要

一种用于移动边缘计算环境下的工作流任务迁移方法，包括以下步骤：S1：构建用户位置预测的隐马尔科夫模型；S2：训练隐马尔科夫模型的参数；S3：预测用户在未来时间内所处的位置；S4：构建工作流任务迁移问题的优化模型；S5：求解工作流任务的迁移位置；S6：将需要迁移的工作流任务复制到对应的边缘服务器上；S7：检测下一个控制周期是否开始，若是，转向步骤S1，否则，转向步骤S7。本发明充分考虑了用户的移动性以及用户与边缘服务器之间的连接随时间动态变化的情况，能够极大优化系统的服务质量与成本支出，以便在满足工作流截至时间的情况下最小化由任务迁移所带来的系统开销。

说明书

技术领域

本发明涉及移动边缘计算领域，尤其是涉及一种用于移动边缘计算环境下的工作流任务 迁移方法。

背景技术

近年来，移动互联网和物联网的飞速发展导致移动终端设备数量激增，人们越来越期待 能够在移动终端上运行更多的计算与数据密集型任务。这些计算与数据密集型任务通常需要 消耗大量的计算与存储资源，并且对于时延有严格的要求。但是，受限于计算、存储和带宽 等资源的匮乏，终端设备往往不能独立且高效地处理这些计算与数据密集型任务，传统的云 计算也不能很好地解决以上问题。在这种背景下，移动边缘计算应运而生。

随着计算机的普及、网络技术的发展，工作流技术已被广泛运用到物流、电子商务、医 疗、行政办公等各种企业管理系统当中。它将业务过程从应用程序中分离出来，进行独立管 理，使得软件更容易支持多变的业务流程，或是更高效地并行处理任务，从而提高工作的效 率。

由于移动边缘计算具有高带宽、低时延以及位置感知等技术特征，因此越来越多的企业 将工作流任务提交至移动边缘计算环境执行，以便快速得到运行结果。但是，在移动边缘计 算网络中，当一个用户从一个区域移动到另一个区域时，既可以继续在前一个区域的边缘服 务器上运行工作流任务，并通过回程网络将数据传输给用户，也可以将工作流任务迁移到新 区域中的边缘服务器上。第一种情况会延长工作流的执行时间，第二种情况会导致额外的迁 移成本，如何在二者之间进行有效权衡是一个挑战性的问题。

目前，经过许多优秀学者的不断努力，针对移动边缘计算环境下的任务迁移问题已经提 出了一些优秀的解决方法，然而，这些方法大部分都是简单地把一个任务划分成若干个相互 独立的子任务来分别进行调度。在工作流环境下，用户提交的工作流由一组相互依赖的任务 节点组成，即一个任务必须在另一个或多个任务执行完毕后才能被执行，而现有的方法并没 有考虑这一点。

发明内容

针对现有技术存在的问题，本发明提供了一种用于移动边缘计算环境下的工作流任务迁 移方法，能够在保证工作流截至时间要求的情况下，最小化任务迁移的成本。

本发明提供的用于移动边缘计算环境下的工作流任务迁移方法，包括以下步骤：

S1：构建用户位置预测的隐马尔科夫模型；

S2：训练隐马尔科夫模型的参数；

S3：预测用户在未来时间内所处的位置；

S4：构建工作流任务迁移问题的优化模型；

S5：求解工作流任务的迁移位置；

S6：将需要迁移的工作流任务复制到对应的边缘服务器上；

S7：检测下一个控制周期是否开始，若是，转向步骤S1，否则，转向步骤S7。

进一步，步骤S1中，所述隐马尔科夫模型包括隐藏序列集合、观测序列集合、用户位置 的状态转移概率矩阵、直连边缘服务器状态转移概率矩阵以及初始状态概率矩阵。

进一步，步骤S2中，基于用户的历史移动记录，利用Baum-Welch算法对隐马尔科夫模 型的参数进行训练。

进一步，步骤S2中，所述隐马尔科夫模型的参数λ为：

λ＝(Π，A，B)

其中A为用户位置的状态转移概率矩阵；B为直连边缘服务器状态转移概率矩阵；Π为 初始状态概率矩阵，代表用户的起始位置。

进一步，步骤S3中，利用Forward算法对用户在下一个时间段所处的位置进行预测。

进一步，步骤S4中，对在预测的用户位置下工作流任务的迁移决策问题建立优化模型， 优化模型如下：

其中，目标函数(1)为最小化任务迁移的次数，M与N分别代表工作流任务子集与边缘服务器的数量；x

约束函数(2)与约束函数(3)确保每个边缘服务器上的可以获得的CPU资源与带宽资 源可以满足分配到其上的任务的资源需求，

约束函数(4)确保每个任务子集只能迁移到一个边缘服务器上，SM表示由用户工作流 的M个任务子集所构成的集合；

约束函数(5)确保工作流的完成时间不会超过用户给定的截至时间，Makespan

约束函数(6)定义了决策变量的取值范围。

进一步，步骤S5中，利用狼群优化算法求解工作流任务的迁移位置，所述狼群优化算法 包括人工狼的编码与解码、狼群初始化、确定头狼、探狼游走行为、头狼召唤行为、猛狼围 攻行为及狼群更新。

进一步，步骤S5中，所述狼群优化算法的步骤包括：

S51：人工狼的编码与解码，使用一维数组对人工狼(解向量)进行编码，数组的大小等 于工作流中任务子集的数量M，数组的下标对应不同的任务子集，数组元素的取值为(0,N)之 间的一个实数，N为所有边缘服务器的数量；解码过程通过下取整函数来实现，取整后的数 组元素值代表一个边缘服务器的编号，解码完成后，将会生成一个任务子集与边缘服务器的 映射关系，即任务迁移优化问题的一个解；

S52：狼群初始化，假设狼群P的规模为SG，则狼群中第i只狼P

P

其中，P

S53：确定头狼，选取猎物气味浓度值(目标函数适应度值)最大的人工狼作为头狼，如 果存在多只猎物气味浓度值相等的狼就随机选取一只，狼群中其它的狼可以通过不断地竞争 来替代头狼；

S54：探狼游走行为，狼群中除去头狼外适应度最优的前z匹狼称为探狼，其中z取

P

上述游走行为不断重复，直到某匹探狼感知到的猎物气味浓度大于头狼的猎物气味浓度， 或者游走次数达到最大游走次数；

S55：头狼召唤行为，头狼通过嚎叫发动召唤行为，听到嚎叫的猛狼i都以相对较大的奔 袭步长step

其中，

其中，ω是距离判定因子；

S56：猛狼围攻行为，狼群对猎物进行围攻时，头狼的位置就是猎物的位置，对于第k代 狼群，假设猎物在第j维空间中的位置为

其中，λ为[-1,1]范围内的随机数，step

step

其中，S是步长因子；

S57：狼群更新，狼群按照捕猎过程中的功劳大小进行分配食物，即在算法中适应度值最 差的R匹人工狼被去除，同时随机产生R匹新的人工狼；R的取值为[SG/2β,SG/β]之间的随 机整数，β为狼群更新比例因子。

进一步，步骤S57中，所述人工狼的优劣通过以下规则进行比较：

对于任意两个解S

进一步，步骤S6中，通过步骤S5获得的每个任务子集的迁移位置，提前将需要迁移的 任务子集复制到相应区域基站所对应的边缘服务器上。

本发明通过提供一种用于移动边缘计算环境下的工作流任务迁移方法，充分考虑了用户 的移动性以及用户与边缘服务器之间的连接随时间动态变化的情况，首先基于隐马尔科夫模 型来预测用户的移动位置，然后利用狼群优化算法来求解任务的迁移位置，最后通过提前将 所迁移的任务复制到相应的服务器上，能够极大优化系统的服务质量与成本支出，以便在满 足工作流截至时间的情况下最小化由任务迁移所带来的系统开销。

附图说明

在下文中将基于实施例并参考附图来对本发明进行更详细的描述。其中：

图1为本发明中用于移动边缘计算环境下的工作流任务迁移方法的流程图；

图2为用于移动边缘计算环境下的工作流任务迁移方法的工作场景图；

图3为用于移动边缘计算环境下的工作流任务迁移方法的实例部署图。

具体实施方式

为清楚说明本发明的发明内容，下面结合实施例对本发明进行说明。

在本发明的描述中，需要说明的是，术语“上”、“下”、“水平”、“顶”、“底” 等指示的方位或位置关系均为基于附图所示的方位或位置关系，仅仅是为了便于描述本发明 和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造 和操作，因此不能理解为对本发明的限制。此外，术语“第一”、“第二”仅用于描述目的， 而不能理解为指示或暗示相对重要性。

如图1所示，本发明提供的一种用于移动边缘计算环境下的工作流任务迁移方法，具体 包括以下步骤：

步骤S1：建立用户位置预测的隐马尔科夫模型；

步骤S2：基于用户的历史移动记录，利用Baum-Welch算法对隐马尔科夫模型的参数进 行训练；

步骤S3：通过Forward算法对用户在下一时间段所处的位置进行预测；

步骤S4：对在预测的用户位置下工作流的M个任务子集的迁移决策问题建立优化模型；

步骤S5：基于预测的用户位置，利用狼群优化算法求解工作流的M个任务子集的迁移位 置；

步骤S6：将需要迁移的任务子集复制到对应的边缘服务器上，以便以最小的迁移成本支 出满足工作流的截至时间要求。

步骤S7：检测下一个控制周期是否开始，若是，转向步骤S1，否则，转向步骤S7。

结合图2，本发明提供的用于移动边缘计算环境下的工作流任务迁移方法，包括具有N 个边缘服务器的移动边缘计算系统，用户的工作流任务被分割成M个子任务集，卸载到用户 周围的边缘服务器上进行计算，在工作流完成之前，用户可能在不同的无线网络中任意穿梭， 我们的目标是通过预测用户的移动位置，提前将工作流的任务副本迁移到合适的边缘服务器 上，以便在保证工作流截至时间的要求下最小化迁移的成本。

本发明使用隐马尔科夫模型来预测用户未来所处的位置，基于用户的历史移动记录利用 Baum-Welch算法训练隐马尔科夫模型的参数λ＝(Π，A，B)，其中A代表用户位置的状态转 移概率矩阵，B为直连边缘服务器状态转移概率矩阵，初始状态概率矩阵Π代表用户的起始位 置，然后通过Forward算法预测用户在下一个时间段内所处的位置。

本发明提供的用于移动边缘计算环境下的工作流任务迁移方法，具体为在移动边缘计算 环境下用户移动位置感知的工作流任务迁移策略，该策略考虑了用户的移动性以及用户与边 缘服务器之间的连接随时间动态变化的情况，首先基于隐马尔科夫模型来预测用户的移动位 置，然后利用狼群优化算法来求解任务的迁移位置，最后通过提前将所迁移的任务复制到相 应的服务器上来优化系统的服务质量与成本支出。

其中，隐马尔科夫模型包括隐藏序列集合、观测序列集合、用户位置的状态转移概率矩 阵、直连边缘服务器状态转移概率矩阵以及初始状态概率矩阵。

在训练隐马尔科夫模型的参数时，基于用户的历史移动记录，利用Baum-Welch算法对 隐马尔科夫模型的参数进行训练。

隐马尔科夫模型的参数λ为：

λ＝(Π，A，B)

其中A为用户位置的状态转移概率矩阵；B为直连边缘服务器状态转移概率矩阵；Π为 初始状态概率矩阵，代表用户的起始位置。

预测用户在未来时间内所处的位置时，通过Forward算法对用户在下一个时间段所处的 位置进行预测；在得到预测位置后，解决在预测的用户位置下工作流的M个任务子集的迁移 决策问题，该问题的优化模型如下：

上述优化模型中，目标函数(1)最小化任务迁移的次数，其中决策变量x

本发明采用狼群优化算法对以上任务迁移优化问题进行求解，所开发的狼群优化算法主 要包括七个核心组件，即人工狼的编码与解码、狼群初始化、确定头狼、探狼游走行为、头 狼召唤行为、猛狼围攻行为与狼群更新。

各个组件的实现细节及步骤如下：

人工狼的编码与解码：使用一维数组对人工狼(解向量)进行编码，数组的大小等于工 作流中任务子集的数量M，数组的下标对应不同的任务子集，数组元素的取值为(0,N)之间的 一个实数，N为所有边缘服务器的数量；解码过程通过下取整函数来实现，取整后的数组元 素值代表一个边缘服务器的编号，解码完成后，将会生成一个任务子集与边缘服务器的映射 关系，即任务迁移优化问题的一个解；

狼群初始化：假设狼群P的规模为SG，则狼群中第i只狼P

P

其中，P

确定头狼：选取猎物气味浓度值(目标函数适应度值)最大的人工狼作为头狼，如果存 在多只猎物气味浓度值相等的狼就随机选取一只，狼群中其它的狼可以通过不断地竞争来替 代头狼；

探狼游走行为：狼群中除去头狼外适应度最优的前z匹狼称为探狼，其中z取

P

上述游走行为不断重复，直到某匹探狼感知到的猎物气味浓度大于头狼的猎物气味浓度， 或者游走次数达到最大游走次数；

头狼召唤行为：头狼通过嚎叫发动召唤行为，听到嚎叫的猛狼i都以相对较大的奔袭步 长step

其中，

其中，ω是距离判定因子；

猛狼围攻行为：狼群对猎物进行围攻时，头狼的位置就是猎物的位置，对于第k代狼群， 假设猎物在第j维空间中的位置为

其中，λ为[-1,1]范围内的随机数，step

step

其中，S是步长因子；

狼群更新：狼群按照捕猎过程中的功劳大小进行分配食物，即在算法中适应度值最差的 R匹人工狼被去除，同时随机产生R匹新的人工狼；R的取值为[SG/2β,SG/β]之间的随机整 数，β为狼群更新比例因子。

由于在搜索过程中生成的人工狼既有可行解也有不可行解，因此使用如下的规则来比较 两个人工狼的优劣。对于任意两个解S

最后，基于狼群优化算法的输出可以获得每个任务子集的迁移位置，利用此信息，任务 迁移决策模块做出迁移决策，提前将需要迁移的任务子集复制到相应区域基站所对应的边缘 服务器上，从而以最小的迁移成本支出满足工作流的截至时间要求。

本发明提供的采用上述用于移动边缘计算环境下的工作流任务迁移方法的移动边缘计算 系统，包括区域代理服务器(边缘服务器)集群及工作流任务迁移决策器，工作流任务迁移 决策器上设置有位置信息收集模块、移动位置预测模块与任务迁移模块。

结合图3，本发明的用于移动边缘计算环境下的工作流任务迁移方法，通过上述移动边 缘计算系统计算时具体包括以下实施步骤及实施内容：

步骤S1：在区域代理服务器集群中填加一台服务器作为工作流任务迁移决策器；

步骤S2：把位置信息收集模块、移动位置预测模块与任务迁移模块部署到工作流任务迁 移决策器上；

步骤S3：位置信息收集模块实时记录代理服务器所报告的用户位置信息，并将其转发给 移动位置预测模块；

步骤S4：移动位置预测模块基于用户的历史位置信息，利用隐马尔科夫模型预测用户在 未来一段时间内所处的位置信息，并将其转发给任务迁移模块；

步骤S5：任务迁移模块基于预测的用户位置信息构建优化模型，并使用狼群优化算法求 解每个任务子集的迁移位置；

步骤S6：将狼群优化算法的输出发送到相关的代理服务器上，相关的代理服务器进行工 作流任务的复制操作。

需要重点指出的有，通过本发明中的用于移动边缘计算环境下的工作流任务迁移方法， 能够极大优化系统的服务质量与成本支出，以便在满足工作流截至时间的情况下最小化由任 务迁移所带来的系统开销。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离 本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一 点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求 而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化囊括 在本发明内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。

此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一 个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明 书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员可以理解 的其他实施方式。