面向用户移动的边缘云服务迁移方法*

李 苗

（中国石油大学（华东）计算机科学与技术学院 青岛 266580）

1 引言

用户移动过程中对服务质量的实时需求不断提高，如AR 游戏、自动驾驶［1］等，移动边缘计算［2］以其为移动应用提供超低服务时延的能力而日益受到重视。然而边缘服务器的计算能力以及覆盖范围也是有限的，因此服务迁移应用而生［3］。同时，时延与迁移开销之间的优化问题也更加突出，最初的解决方案是将假定用户移动模型的迁移问题转化为特定的马尔科夫决策（MDP）系统框架来求解出最优的迁移决策［4］。Wang［5］等建立了一个基于用户移动距离的系统来决定何时何地进行决策，但该系统可伸缩性较低，不能够适应于各种用户移动场景。由于原有的MDP 决策在大量用户移动时会出现状态空间爆炸现象，因此将该迁移决策映射到强化学习决策的方法被相关的研究学者所采用［6］。随后又提出了动态调配迁移过程中边缘云资源，从而减少服务资源浪费现象的发生［7］。但是这些方案中存在着用户移动不确定、决策算法复杂以及系统架构可扩展较低的问题。因此本文提出的无模型深度强化学习算法建立了极具普适性的系统模型且可实现多个优化目标的快速迁移决策的功能。

2 系统模型

服务迁移［8］过程是将为移动用户提供服务的源边缘服务节点迁移至目标边缘服务节点，从而在用户移动时可以降低服务延迟，提高服务体验度［9］。图1展示的是用户移动过程中边缘云的服务迁移对比图，其中图（a）为不迁移过程，图（b）为迁移过程。因此构建通用的系统模型是高效迁移决策的基本要求，其可以使得无模型的深度强化学习算法实现多种优化目标需求的迁移决策。接下来将通过边缘云网络场景、用户移动模块、边缘云服务模块来介绍该系统模型。

图1 服务迁移流程图

2.1 边缘云网络场景

边缘云服务迁移的网络场景由基站（节点）、中间节点和移动用户构成，边缘云服务随机的放置在节点上，主要功能模块由移动用户模块和边缘云服务模块组成。在该场景中边缘云服务模块收集移动用户模块中的相关信息，并且根据服务迁移的性能指标来来决定边缘云服务是否进行迁移。

在该网络架构中的节点集合为B，b(b∊B)被定义为其中的一个节点。边缘云服务节点Mi∊M随机放置在边缘云网络中的任意节点上，并且为每个边缘云设置了一个邻域K。us(t)定义的是在t时为用户u提供服务的信息。bu(t)∊B定义的是在时间t时用户所连的接入点。

2.2 用户移动模块

用户移动模块的主要功能是收集模拟的用户在移动过程中的相关信息。实验中的用户移动是基于随机移动模型，用来研究无模型的迁移策略。

2.3 边缘云服务模块

边缘云服务模块主要功能是如何选择最优服务迁移方案。该模块中会给出本研究中迁移成立的约束条件以及优化目标的评价标准。关于服务节点内存资源的约束条件如式（1）所示：

其中代表的是边缘云Mi可用的内存源；代表Mi在t时刻可用内存资源。

服务迁移过程中的性能优化评价指标是指在一段时间间隔内用户服务性能表现，具体如下：

1）时延

服务时延测量标准是与用户关联的边缘云服务节点和用户所连接的接入点之间的距离有关，如式（2）所示，其中λd和λ是实值的参数。

2）节点能耗

能耗指的是邻域内所有边缘云节点在t时的内存资源情况。

其中代表的是迁移能耗的最大值1，代表的是迁移能耗的最小值0，Effi(t)代表的是在t时刻边缘云的资源利用率。

3）迁移开销

迁移开销是由节点能耗以及通信成本两方面决定的。

其中式（4）中的为通信成本；代表的是边缘云服务状态，可划分为迁移状态的服务(=1) 和非迁移状态的服务(=0) 。(t)表示的是t 时刻边缘云Mi位置，1｛·｝表示的是当括号内的条件成立时其值为1，否则为0。

定义1：在服务迁移策略的选择过程中优化目标函数的具体数学表现形式如下：

服务迁移的决策过程中要最小化MinC，其中ω1，ω2相关的参数。

在进行服务迁移选择过程中面临的服务时延、迁移开销以及两者之间的折衷优化问题会随着用户的移动以及边缘云放置的不确定性而变得复杂，因此利用深度强化强化学习算法进行合理的迁移决策成为解决服务迁移问题的方案之一［10］。

3 解决方案

用户移动过程中关于最佳的服务迁移策略的选择问题映射到一个基于深度强化学习方法的决策方案中，图2 描述的就是深度强化学习中的迁移决策模型。在解决大规模的优化策略问题中深度Q-Learning 算法与深度神经网络（DNN）的结合尤为突出［11］。

图2 基于深度强化学习的服务迁移模型

3.1 基于NMDQN服务迁移算法

大规模移动用户状态信息呈现的算法复杂性的问题以及迁移决策中出现的算法收敛缓慢的问题［12］，促使了服务迁移决策不依赖于用户移动模型的建立。在该迁移方案中，在不需要了解移动过程中用户确切位置信息情况下，边缘云节点（Agent）收集相关领域内的边缘云节点状态信息以及用户所连接的基站的状态信息（State），并且通过Deep Q-Learning 算法做出相应的动作（Action）抉择，得到如式（8）所示的奖励值（Reward），通过DNN 来协助边缘云节点学习有效的经验值，反复进行以上的操作，最终得到最优的迁移决策［13］。

3.2 算法优化设计

1）动作选择的优化

在强化学习算法中，动作决策中采用的是ϵ-贪婪算法，主要是开发-探索（exploitation-exploration）的决策方案选择［14］。由于大规模的状态空间中会出现Q值重现的问题，相应地会减缓算法的收敛速度，因此对exploitation 进行了优化。在exploitation 中以字典的方式将Q值存储起来，将迁移过程中的状态值作为键，将该状态下动作的选择以及对应得到的奖励作为另一个参数来存储。优化后的动作选择如式（9）所示：

2）神经网络的优化

传统Q-Learning算法中Q值更新如式（10）：

其中α为学习率，γ为折扣因子。

由于用户移动的高度不确定性以及边缘云服务放置的随机性，传统算法中缺乏对经验值快速学习的能力，造成服务延迟的现象［15］，因此基于DQN算法可以有效地解决这些问题。在本研究中，服务迁移策略的选择是不依赖于用户移动的，因此采用无模型的DQN（NMDQN）算法可在大规模状态空间中提高决策速率且实现多个目标的优化。

在NMDQN 算法中，Q值为DNN 中有一个带有权重θ的近似值，其目的是在每一次迭代时通过不断的更新θi的值来获得服务迁移算法中最小的折损函数值，然后对折损函数求梯度，并且在此基础上对回放经验的取样过程通过一个优先级的来决定最终的抽样经验值。关于折损函数的描述如式（11）所示。

其中Y（t）的如式（12）所示。

首先对折损函数进行批量梯度下降，然后更新参数θi，具体的实现如式（13）、式（14）所示。

在对回放经验取样操作时，进行了一个优先级的处理方法，可以减少服务迁移过程中无效经验的选取使用。将折损函数与δpr之间取差值之后做了一个指数运算，得出单个取样的优先级，最终与所有取样结果之和相比，得出优先级的大小，从而得到有效的经验值，具体如下所示：

算法1是NMDQN的服务迁移算法。

4 实验分析

由于在真实世界的移动边缘云网络架构中不易进行实验，因此本文的性能评估是在实验平台上模拟的网络架构中进行的。实验平台中的网络模型是由50 个节点构成的（30 个基站和20 个中间节点），节点之间通过最小生成树连接的，且每个节点连接着4 个最近节点，边缘云是被随机放置在任意节点上，如图3 所示。实验中相关的参数默认值如表1 所示。采用线性运动模型模拟了16 个用户的移动模型，每个用户都连接着一个基站，并与一项服务相关联。每当用户连接到新的基站时，相关服务的被重新评估，并且迁移方案被触发。状态-动作值函数Q（S，A）由3层20个神经元的深度神经网络逼近。

表1 实验参数设置

图3 边缘云网络架构图

4.1 基于服务时延的评估

通过对服务时延的测评可以看出迁移策略对实时服务的响应能力。图4 展示的是在各个方法下对服务时延的评估。本文的提出的NMDQN 算法是有蓝色的线表示的，将本文提出的方法与两个基线策略进行比较。其中一个基线策略为红线表示的局部邻域最优的迁移方法，另外一个基线策略为黑线表示的基于DQN［10］的迁移方法。可以看出本文提出的NMDQN算法是优于DQN算法的，主要归功于本文提出的算法是基于无模型的，不需要根据用户的移动位置信息建立复杂的成本函数，在大规模边缘云迁移时减小了算法复杂度，提高了策略响应速度。

4.2 基于时延与迁移开销折衷优化的评估

本文中还将服务时延与迁移开销的折衷优化函数作为一个奖励函数进行评估系统性能，以此来验证NMDQN 算法可实现时延与开销之间的折衷优化任务。图5 展示了一段时间内的平均迁移次数，可以看出本文的NMDQN 算法明显较低。图6展示了一段时间内的平均回报，且NMDQN 的算法的效果是优于DQN 算法的，由此可以看出本文的算法避免了频繁迁移带来的迁移开销以及节点能耗的问题，提升了用户整体的服务质量水平。

图5 平均迁移次数的评估

图6 时延与开销的评估

5 结语

本文研究关于移动边缘云的服务迁移问题，由移动边缘云节点来决定何时何地迁移边缘云服，提出的基于无模型的深度强化学习算法无需根据事先已知的用户移动模型即可建立通用的系统框架，从而在各种不同的优化目标需求条件下实现优于基线水平的迁移决策。实验仿真结果验证了我们提出的方法。本文中边缘云迁移过程中考虑到了对每一个边缘云的局部领域范围内进行策略优化，在边缘云动态添加时关于移动边缘云的局部邻域K 的最佳选择值得考虑的。未来的工作将重点考虑动态添加边缘云时的服务迁移策略问题。