移动感知下小小区网络的任务卸载、迁移及资源分配策略

Mobile-Aware Task Offloading，Migration and Resource Allocation Strategy in Small Cell Networks

摘要

针对基于移动边缘计算（mobile edge computing， MEC）的小小区网络中任务迁移产生额外开销的问题，提出一种优化的移动感知下小小区网络的任务卸载、迁移及资源分配策略，以达到减小迁移概率的同时最大化总收益的目的。首先，利用移动设备（mobile equipment，ME）的驻留时间分析移动设备的移动性，并通过效用函数表示总收益最大化这一问题。其次，由于该问题是一个混合整数非线性规划（mixed integer non-linear programming，MINLP）问题，提出基于遗传算法的分布式资源最优化算法（distributed resource optimization algorithm based on genetic algorithm， DROAGA）来进行求解。最后，通过仿真实验模拟移动设备数量、计算资源数量、任务迁移开销和平均驻留时间对移动设备总收益的影响。实验结果表明，与其他算法相比，本文提出的算法能更有效地提高用户的总收益。

Abstract

In order to solve the problem of extra cost caused by task migration in small cell networks with mobile edge computing (MEC), an optimized mobile-aware task offloading, migration and resource allocation strategy for small cell networks is proposed to reduce the probability of migration and maximize the total revenue. Firstly, the mobility of mobile equipment (ME) is analyzed by the sojourn time, and the problem of maximizing the total revenue of MEs is formulated by the utility function. Secondly, since the maximization problem is formulated as a mixed integer non-linear programming (MINLP) problem, a distributed resource optimization algorithm based on a genetic algorithm (DROAGA) is proposed to solve it. Finally, the effects of the number of ME, computing resources, task migration cost and average sojourn time on the total revenue of MEs are simulated through simulation experiments. Experimental results show that compared with other algorithms, the proposed algorithm can improve the total revenue of users more effectively.

Graphical abstract

关键词

移动边缘计算 / 卸载 / 迁移 / 移动感知

Key words

mobile edge computing (MEC) / offloading / migration / mobile-aware

0　 引 言

移动通信的快速发展，促进了新兴业务的出现。5G网络技术的兴起，使许多创新技术得以蓬勃发展，例如：增强现实（augmented reality， AR）和虚拟现实（virtual reality， VR）技术，物联网（internet of things， IoT）和车联网等。这些技术大多数都是直接在移动设备（mobile equipment，ME）上使用，然而，由于移动设备硬件条件的限制，例如有限的计算能力、存储空间和电池容量等，使得在移动设备上处理这类应用所能达到的时延和消耗的能量不能满足业务的需求。在移动网络边缘部署移动边缘计算（mobile edge computing，MEC）服务器，可以解决移动设备传输延迟和能量消耗的问题^［1］。

小小区网络（small cell networks，SCNs，即覆盖范围和发射功率较小的微微蜂窝组成的网络）中，移动设备能通过多个小小区基站来提供连续的服务。移动边缘计算最重要的一个优势是提供计算资源给附近的移动设备，进而减少本地移动设备的任务量和传输时延。因此，近年来，基于移动边缘计算的资源管理成为一个重要的研究热点，包括移动边缘计算的任务卸载和任务迁移两个研究方向。在任务卸载方面，文献［1］将博弈论的方法应用于任务卸载策略中；文献［2］在考虑缓存和全双工通信时，将交替方向的乘法算法应用于任务卸载时的资源分配中；文献［3］是以最小化能量消耗为目的，通过迭代优化算法来处理任务缓存和卸载中的资源分配问题；文献［4］在不同信道条件下，分析了任务卸载策略和资源分配算法；文献［5，6］提出任务被分割时的任务卸载和内容缓存策略。在任务迁移方面，文献［7］根据用户与MEC服务器间的平均距离、平均时延、中断时间和迁移消耗等参数选择最优的MEC服务器进行任务迁移；文献［8］提出采用马尔科夫过程并根据迁移消耗和用户得到服务质量来选择最佳的MEC进行任务迁移；文献［9］对用户的一维近似随机步行移动进行建模，并通过门限值来确定是否进行任务迁移；文献［10］将文献［9］中的一维随机步行移动模型扩展到二维模型，并利用马尔科夫过程来解决任务迁移的顺序问题；文献［11］考虑在成本效益最大和性能最优情况下进行任务迁移策略的制定。

但是现有关于任务迁移的文献^［7~11］，只考虑用户的移动性，未考虑将任务卸载、任务迁移与计算资源分配进行联合研究。因此，本文提出一种移动感知下小小区网络的任务卸载、迁移及资源分配策略。具体的贡献是：

1） 基于用户的移动性，联合考虑任务卸载、迁移和计算资源的分配来减小任务迁移概率，使得移动设备的总收益最大化。

2） 提出利用一个效用函数来表示系统的消耗成本与收益之间的关系，并通过最大化效用函数来最大化用户的总收益。该最大化问题是一个混合整数非线性规划（mixed integer nonlinear programming， MINLP）问题，为了求解该非确定性多项式难题（non-deterministic polynomial-hard problem，NP-hard problem），本文提出一种基于遗传算法的分布式资源最优化算法（distributed resource optimization algorithm based on genetic algorithm， DROAGA）。

1　 系统模型

1.1　系统架构

本文中，正交频分多址（orthogonal frequency division multiple access， OFDMA）上行系统采用多接入的方式，并且这些信道彼此正交，每个用户设备只能分配一个信道，因此可以避免干扰。系统模型如图1所示，采用宏基站和小小区基站共同覆盖的方式，移动设备根据距离小小区基站的地理位置或接收信号的信噪比（signal noise ratio，SNR）选择接入小小区的基站。小小区中心区域部署MEC服务器，移动设备随机分布于小区中。小小区半径相对较小，由于移动设备的移动，其无法长时间驻留在该小小区覆盖的范围内。

如图1所示，移动用户1所持移动设备的任务卸载工作在MEC服务器中完成时，该设备仍然驻留在原小小区覆盖的范围内。移动用户2所持移动设备的任务卸载工作在MEC服务器中完成时，该设备已经离开了原小小区覆盖的范围。这时，任务执行结果将迁移到另一个小小区内进行，这个过程将会引起额外的开销。

令N_{\mathrm{u}}=\left\{\mathrm{1,2},\cdots ,i,\cdots ,N\right\}表示在小小区内的移动设备的集合。移动设备i的任务可以表示为W_i=\left\{M_i,f_i,T_i^{\mathrm{m}\mathrm{a}\mathrm{x}}\right\}，\forall i\in N_{\mathrm{u}}，其中，M_i表示计算任务的大小，f_i表示移动设备的计算能力（例如CPU的时钟频率等），T_i^{\mathrm{m}\mathrm{a}\mathrm{x}}表示执行完任务允许的最大延迟时间。本文用CPU的周期数来衡量任务所需计算资源的数量^［12］。假设计算任务的数量较大并且任务是计算密集型，则卸载任务能节省时间和能量消耗。然而，由于MEC服务器上的计算资源有限，当移动设备的计算任务较大时，不能将所有任务都卸载到MEC服务器上。本文用C_{\mathrm{M}\mathrm{E}\mathrm{C}}表示MEC服务器上的计算资源；A=\left\{a_i,i\in N_{\mathrm{u}}\right\}表示任务卸载的集合，a_i=\mathrm{1}表示任务被卸载，a_i=\mathrm{0}表示任务在本地执行。

假设移动设备i的传输功率p_i为一个常数，则移动设备i的信噪比可以表示为^［1］

\mathrm{S}\mathrm{N}{\mathrm{R}}_i=\frac{p_i{h}_i{d}_i^{-\theta }}{{\sigma }^{\mathrm{2}}},\forall i\in N_{\mathrm{u}}（1）

其中，d_i（m）表示移动设备与小小区基站间的距离；\theta表示路径损耗指数；{\sigma }^{\mathrm{2}}（dBm）表示加性高斯白噪声的功率；h_i表示信道增益。

因此，移动设备i的上行传输速率可以表示为

R_i=B\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\mathrm{1}+\mathrm{S}\mathrm{N}{\mathrm{R}}_i\right),\forall i\in N_{\mathrm{u}}

其中，B（MHz）表示带宽^［2］。

1.2　计算模型

本节提出两种计算模型来表示任务在本地或MEC服务器上执行的时间和消耗的能量。

1.2.1　本地计算模型

令C_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}表示本地移动设备i的计算能力即处理任务所需的CPU运行周期数，则本地执行时间可以表示为

t_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}=\frac{C_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}}{f_i},\forall i\in N_{\mathrm{u}}（2）

根据文献［13］，任务在本地计算执行时的能量消耗可以表示为

E_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}=\kappa f_i^{\mathrm{2}}{C}_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}},\forall i\in N_{\mathrm{u}}（3）

其中，\kappa表示将在本地执行任务的硬件设备的能力（例如CPU的计算能力等）转化为能量消耗的转化系数^［13］，一般取值为常数。

1.2.2　边缘计算模型

将任务卸载给MEC服务器，这个过程分为传输和执行两步。传输时间表示为t_i^{\mathrm{u}\mathrm{l}}=M_i/R_i，能量消耗表示为E_i^{\mathrm{u}\mathrm{l}}=p_i{t}_i^{\mathrm{u}\mathrm{l}}。令C=\left\{C_i,i\in N_{\mathrm{u}}\right\}表示在MEC服务器上能够分配给移动设备的计算资源的集合，C_i表示分配给移动设备i的计算资源。则执行时间可以表示为t_i^{\mathrm{e}\mathrm{x}\mathrm{e}}=f_i/C_i,\forall i\in N_{\mathrm{u}}。由于计算资源有限，因此，分配给移动设备的计算资源必须满足{\displaystyle \sum _{i=\mathrm{1}}^N}{C}_i\le C_{\mathrm{M}\mathrm{E}\mathrm{C}}的限制。当计算结果即输出数据量与输入数据量相比很小时，回传时间可以忽略不计^［14］。如果移动设备未离开原小小区覆盖的范围，这时计算结果通过小小区的基站，利用OFDMA系统的下行信道回传给用户端；否则，计算结果将通过上行线路传输给宏小区基站，宏小区基站可以通过有线的方式与小小区基站连接，这时宏小区基站将会通过下行线路传输给移动设备当前所在的小小区基站，由其通过OFDMA系统的下行信道传输给用户端。因此，总的边缘计算时间t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}可以表示为任务上行传输给MEC端的时间t_i^{\mathrm{u}\mathrm{l}}与在MEC端执行该任务的执行时间t_i^{\mathrm{e}\mathrm{x}\mathrm{e}}之和，即

t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}=t_i^{\mathrm{u}\mathrm{l}}+t_i^{\mathrm{e}\mathrm{x}\mathrm{e}},\forall i\in N_{\mathrm{u}}（4）

1.3　移动性模型

移动设备的移动性可用其在某一基站的驻留时间表征，并且该驻留时间可以用指数分布函数表示^［15］，因此用户设备驻留时间的概率密度函数（probability density function， PDF）可以表示为

f_{{\tau }_i}\left(t\right)=\frac{\mathrm{1}}{{\tau }_i}{\mathrm{e}}^{-\frac{t}{{\tau }_i}},t\ge \mathrm{0}（5）

其中，t表示移动设备的驻留时间，{\tau }_i表示移动设备i的平均驻留时间，可用以表征移动设备的移动强度，例如{\tau }_i较小代表设备移动性较强。为了简化，假设{\tau }_i服从高斯分布。

2　 数学模型

本文提出利用效用函数表示当任务被卸载到MEC服务器时，移动设备获得的收益与消耗的成本之差。将节省的时间和本地节省的能量作为收益，资源消耗和迁移支出作为成本。节省的时间可以看作是本地执行时间与边缘计算执行时间之差，因此可以表示为

T_i^{\mathrm{g}\mathrm{a}\mathrm{i}\mathrm{n}}=\gamma \left(t_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right),\forall i\in N_{\mathrm{u}}（6）

其中，\gamma表示节省时间的收益系数。

资源消耗包括传输数据时的能量消耗和MEC计算资源的消耗。因此总的资源消耗可以表示为

Z_i^{\mathrm{M}\mathrm{E}\mathrm{C}}=\alpha E_i^{\mathrm{u}\mathrm{l}}+\beta C_i,\forall i\in N_{\mathrm{u}}（7）

其中，\alpha表示传输时消耗能量的代价系数，\beta表示MEC计算时的计算代价系数。这两个系数反映了用户接受服务所需要支付的单位成本代价。

当任务被卸载到MEC上执行时，需要比较任务在MEC上执行的时间与预测的移动设备在该小小区的驻留时间，因为这涉及到任务是否被迁移的问题，因此，将分两种情况讨论效用函数。

情况1：在移动设备离开原小小区覆盖范围前，如果任务能够在原MEC服务器端执行完毕，即，则任务迁移不会发生。情况1发生的概率可以表示为P_{{\tau }_i}\left(t>t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)。这时的效用函数可以表示为

Q_i^{\mathrm{1}}=T_i^{\mathrm{g}\mathrm{a}\mathrm{i}\mathrm{n}}+Z_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-Z_i^{\mathrm{M}\mathrm{E}\mathrm{C}},\forall i\in N_{\mathrm{u}}（8）

其中，Z_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}=\alpha E_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}表示本地剩余能量收益。

情况2：当任务在原MEC服务器上执行完毕时，如果移动设备已经离开了原小小区覆盖范围，该情况发生的概率可以表示为P_{{\tau }_i}\left(t\le t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)。这时，MEC服务器上的执行结果将通过宏基站迁移到另一个小小区的基站处，该基站将会把执行结果传输给移动设备，这时会产生额外开销Z_i^{\mathrm{m}\mathrm{i}\mathrm{g}}。本文为了简化，假设迁移开销只与任务量的多少相关，用Z_i^{\mathrm{m}\mathrm{i}\mathrm{g}}=\delta M_i表示^［8］，其中\delta表示迁移开销。因此，这种情况的效用函数可以表示为

Q_i^{\mathrm{2}}=T_i^{\mathrm{g}\mathrm{a}\mathrm{i}\mathrm{n}}+Z_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-Z_i^{\mathrm{M}\mathrm{E}\mathrm{C}}-Z_i^{\mathrm{m}\mathrm{i}\mathrm{g}},\forall i\in N_{\mathrm{u}}（9）

将（8）式与（9）式相结合，可得

Q_i=\left\{\begin{array}{c}{Q}_i^{\mathrm{1}} ,P_{{\tau }_i}\left(t>t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)\\ Q_i^{\mathrm{2}} ,P_{{\tau }_i}\left(t\le t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)\end{array}\right.,\forall i\in N_{\mathrm{u}}（10）

因此，用移动设备i的期望收益来衡量系统性能，可以表示为

{\overline{Q}}_i= P_{{\tau }_i}\left(t>t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)Q_i^{\mathrm{1}} +P_{{\tau }_i}\left(t\le t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)Q_i^{\mathrm{2}} ,\forall i\in N_{\mathrm{u}}（11）

其中

P_{{\tau }_i}\left(t\le t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)={\int }_{\mathrm{0}}^{t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}}\frac{\mathrm{1}}{{\tau }_i}{\mathrm{e}}^{-\frac{t}{{\tau }_i}}\mathrm{d}t=-{\mathrm{e}}^{-\frac{t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}}{{\tau }_i}}+\mathrm{1}（12）

P_{{\tau }_i}\left(t>t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)=\mathrm{1}-P_{{\tau }_i}\left(t\le t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}\right)（13）

结合以上分析，任务是否卸载、迁移都会影响用户的收益，因此，由任务卸载、迁移决定，并受计算资源分配影响的用户收益最大化问题可以公式化为

（14）

其中，约束项C1表示确保边缘计算时间t_i^{\mathrm{M}\mathrm{E}\mathrm{C}}小于业务最大延迟时间T_i^{\mathrm{m}\mathrm{a}\mathrm{x}}；约束项C2表示分配给移动设备执行任务的计算资源数量小于等于MEC服务器的总计算资源；约束项C3表示变量{\eta }_i的限制取值范围，{\eta }_i=0表示任务在本地设备上执行，{\eta }_i=1表示任务在MEC服务器端上执行；在约束项C4中，I\left(C_i\right)表示指示函数，如果C_i>0，则I\left(C_i\right)=\mathrm{1}，否则，I\left(C_i\right)=\mathrm{0}，C4表示当任务在本地执行时，确保计算资源不分配给MEC服务器。尤其，当{\eta }_i=\mathrm{0}时，任务将在本地执行，移动设备将不能从MEC服务器中获得收益，所以，这种情况下{\overline{Q}}_i=\mathrm{0}。

3　 DROAGA

根据以上分析，问题（14）是一个混合整数非线性规划问题，同时也是一个NP-hard问题，并且移动边缘计算本身属于分布式计算技术，因此本文提出一种基于遗传算法的分布式资源最优化算法（distributed resource optimization algorithm based on genetic algorithm，DROAGA），用来求解该最优化问题。

在遗传算法中，每个资源分配方案都是一个独立的个体，被编码为二进制的“基因串”。多个个体形成一个种群，在每个种群的遗传过程中，适应度值越高，则个体生存的机会也会越高。经过基因杂交、突变的过程，选定的个体将组成新的种群。交叉操作是根据定义的交叉概率P_{\mathrm{c}}交换基因串中的某些位来实现的；突变操作是根据概率P_{\mathrm{m}}，通过随机更改基因串中的某位来实现的。

本节主要讨论如何使用DROAGA获得（14）式的解，该算法如算法1所示。在该算法中，适应度指标定义为（14）式中的目标函数。每个任务的资源分配策略被编码为长度为g_e=⌈\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}^j⌉的二进制字符串，其中j是资源分配准确率。在本文中，我们设置j=100。由于共有N个用户设备，因此基因库中个体的长度可以表示为{\displaystyle \sum _{i=\mathrm{1}}^N}{g}_{\mathrm{e}}。

在DROAGA算法开始时，将随机生成K个个体。随后经过多次的进化，最佳个体将被保留，最终达到最优的解决方案。在进化的每一代中，都将进行交叉和变异的选择操作，并将产生新的种群以供后续进化。由于随机竞赛选择法^［16］有较低的计算复杂度和较好的个体选择性，本文采用该方法来选择个体。每次随机选择两个个体，保留其中最好的一个个体。一直这样选择，直到所有个体都被选到。如果在选择操作中最好的个体被忽略，则下一代中最差的一个个体将被提取出来，并代替最好的这个个体。

DROAGA算法主要步骤如下：

1） 对每个个体计算适应度。

2） 每个用户的任务所采用的资源分配策略被编码为二进制字符串，每个字符串就是问题（14）的一个解，因此每个用户的任务所采用的资源分配策略分布矩阵可以表示为

L_i^{\mathrm{M}\mathrm{E}\mathrm{C}}=\left[L_{\mathrm{1}},\cdots ,L_i,\cdots ,L_N\right]（15）

其中，L_i={\left[{\eta }_i,C_i\right]}^{\mathrm{T}}是移动设备i的变量集合。按照（14）式的限制条件C4，如果{\eta }_i=\mathrm{0}，则令L_i={\left[\mathrm{0,0}\right]}^{\mathrm{T}}。

3） 进行基因交叉操作。对集合A和C进行概率为P_{\mathrm{c}}的基因个体交叉操作。对于集合A，我们使用统一的交叉操作。该操作可以加速收敛，防止Q_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}落入局部极值中。对于集合C，我们采用重组法，可以表示为

C_i\left(\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{1}\right)=\left(\mathrm{1}-b\right)C_i\left(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{1}\right)+b{C}_i\left(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{2}\right)（16）

C_i\left(\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{2}\right)=b{C}_i\left(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{1}\right)+\left(\mathrm{1}-b\right)C_i\left(\mathrm{p}\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{2}\right)（17）

其中，b表示一个取值在（0，1）之间的随机变量，child1和child2分别表示子染色体，parent1和parent2表示双亲染色体。

4） 进行基因变异操作。在限制条件（14）中，将{\eta }_i取值0或1，使概率为P_{\mathrm{m}}的集合C_i增加或减少一个随机变量。首先选择一个可行的变量，并添加一个接近边界的不可行变量。因为，下一个迭代的不可行变量很可能会成为可行的变量。

在算法复杂度方面，本文提出的DROAGA的复杂度为{\rm O}\left({\left|N_{\mathrm{u}}\right|}^{\mathrm{2}}\right)，计算复杂度较低，因此适合在实际系统中应用。

4　 仿真分析

4.1　仿真参数及对比算法

参照文献［2，4］，设置仿真实验中的参数。小小区覆盖半径是80 m，移动设备随机分布在小区内。移动设备的传输功率服从高斯分布\mathit{𝒞}\mathit{𝒩}({\mu }_{\mathrm{1}};{\sigma }_{\mathrm{1}}^{\mathrm{2}})，{\mu }_{\mathrm{1}}=\mathrm{20} dBm，{\sigma }_{\mathrm{1}}=\mathrm{2}。信道参数：带宽为10 MHz，路径损耗指数\theta =\mathrm{2}。对于移动设备而言，其计算能力C_i^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}取值范围为0.5~0.8 GHz。任务量的大小在100~150 MB范围内随机取值；f_i=\epsilon M_i，表示需要的计算资源，其中\epsilon表示每兆比特的CPU工作的周期，在这里\epsilon的取值范围是［0.4， 0.5］。由于任务量较大，因此设定最大延迟T_i^{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{80} s。根据文献［2］，设置不同类型任务的代价：\alpha =8，\beta =2，\gamma =4。根据文献［17］，设置\kappa =\mathrm{1.0}\times {\mathrm{10}}^{-\mathrm{11}}。在移动性分析中，移动设备的平均驻留时间服从高斯分布\mathit{𝒞}\mathit{𝒩}({\mu }_{\mathrm{2}};{\sigma }_{\mathrm{2}}^{\mathrm{2}})，{\mu }_{\mathrm{2}}=\mathrm{40} s和{\sigma }_{\mathrm{2}}=\mathrm{20}。DROAGA中的输入参数K=\mathrm{32}，P_{\mathrm{c}}=\mathrm{0.6}，P_{\mathrm{m}}=\mathrm{0.1}。

为了验证本文提出的DROAGA在用户设备移动性、MEC的计算资源分配和任务卸载方面的性能，将该算法与其他算法进行比较。

AARM算法：忽略用户移动性的资源分配算法（allocation algorithm regardless of mobility， AARM），该算法类似于本文提出的基于遗传算法的资源最优化算法，只是在AARM算法中没有考虑用户的移动性^［6］。

ROARM算法：考虑用户移动性的随机卸载算法（randomly offloading algorithm regard of mobility， ROARM），该算法在考虑用户移动性的同时，随机卸载任务的比例是0.5，在该算法中MEC的计算资源采用均匀分配的方式分配给用户设备。

AOARM算法：考虑用户移动性的全卸载算法（all offloading algorithm regard of mobility， AOARM），该算法在考虑用户移动性的同时，卸载全部的任务，在该算法中MEC的计算资源采用均匀分配的方式分配给用户设备。

4.2　移动设备数量与卸载、迁移任务数量及总收益之间的关系

假定仿真参数MEC的总计算资源C_{\mathrm{M}\mathrm{E}\mathrm{C}}=\mathrm{26} GHz、迁移开销\delta =\mathrm{0.5}，采用不同算法，对移动设备数量不同时任务卸载和任务迁移数量的变化情况进行仿真实验，结果如图2所示；对移动设备数量不同时设备总收益的变化情况进行仿真实验，结果如图3所示。

由图2可知，当移动设备数量增加时，卸载和迁移任务的数量都在增加。DROAGA由于考虑用户移动性，因此卸载和迁移任务的数量变化不大。AARM由于没有考虑到用户移动性，因此随着用户设备数量的增加，其卸载和迁移任务的数量都在增加。AOARM采用全卸载任务策略，因此随着用户设备数量的增加，任务卸载和迁移的数量最多。ROARM采用卸载50%的任务的策略，因此在移动设备数量较少时，其任务卸载和迁移的数量最少。但是随着用户设备的数量增加，ROARM由于采用资源均匀分配的方法，而DROAGA采用最优的资源分配方法，因此当移动设备的数量多于18时，ROARM的任务迁移量多于DROAGA的任务迁移量，当移动设备的数量多于23时，ROARM的任务卸载量多于DROAGA的任务卸载量。

从图3中可以看到，随着移动设备数量的增加，采用不同算法时移动设备总收益的变化是非常大的。当移动设备的数量小于12时，由于计算资源充足，AARM和AOARM的总收益逐渐增加；当移动设备的数量大于12时，随着任务迁移数量的增加，迁移的开销也在增加，并且开始超过所获得的增益，因此，总收益开始减少。

从图3还可以看到，当移动设备的数量小于20，AOARM和AARM开始卸载任务时，由于AOARM在资源分配时考虑用户的移动性，因此它的收益高于AARM的收益。但是，当移动设备的数量超过20后，任务卸载和迁移的数量基本上保持不变，AARM的总收益开始保持平稳，而AOARM由于考虑用户的移动性，因此迁移开销仍然在增加，并且随时间的增长，收益开始下降，因此总收益仍然减少。ROARM与AOARM类似，只是任务卸载量是AOARM的一半，当移动设备的数量大于18时，任务迁移数量的增加量比AOARM更少，这也使得任务迁移开销更少，因此采用ROARM获得的总收益更高。

从图2和图3可以看到，采用DROAGA时，在资源充足的情况下，随着移动设备数量的增加，越来越多的任务被卸载，并且这些任务大部分可以避免任务迁移；但是当移动设备数量超过12时，任务卸载数量和任务迁移数量开始变得缓慢，但是移动设备获得的收益却在不断增加。这是因为，计算资源有限，只能服务于一部分移动设备，但是较多的移动设备因此得到了选择性增益即通过选择合适的移动设备的任务，在用户离开该小区前，任务能够在MEC端执行完毕，因此减少了任务迁移的数量，使得总收益仍然继续增加，只是速率减缓。

4.3　移动设备总计算资源与总收益之间的关系

假定移动设备MEC总计算资源C_{\mathrm{M}\mathrm{E}\mathrm{C}}的变化范围为18~32 GHz，移动设备数N=18，迁移开销\delta =\mathrm{0.5}时，对移动设备总收益随MEC不同计算资源的变化情况进行仿真实验，实验结果如图4。

由图4可知，随着MEC总计算资源的增长，所有算法都获得了较高的收益，但是受任务卸载和迁移数量影响，这些算法的增长速率并不相同。采用DROAGA时，随着计算资源的增加，有选择地卸载任务，因此减少了任务迁移的概率。采用该算法时，移动设备在离开本小区前卸载任务完成的概率较高，因此，总收益会缓慢地增加，这与采用ROARM时的情况与此类似。采用ROARM时，由于采用随机卸载50%的任务的策略，在MEC端执行的任务较少，而且随着MEC计算资源的不断提升，在移动设备离开覆盖区前，任务都能够在MEC端执行完毕，因此任务迁移的概率会很低，这时移动设备的收益主要与时间增益有关，移动设备总收益变化不大。采用AOARM时，采取的是全部卸载任务策略，随着MEC计算资源的不断提升，在MEC端可以执行完的卸载任务的数量会越来越多，因此迁移任务的数量也会越来越少，迁移开销也会随之减少，总收益增加得较快。AARM在开始时收益增加得较慢，这是因为该算法没有考虑用户的移动性，由于卸载任务越多，任务迁移概率越高，迁移概率的提高会使移动设备总收益增长减缓，但随着总计算资源的增加，AARM可以处理较多的卸载任务，因此能够减少任务迁移的概率，所以移动设备的总收益增加，此时该算法的增速类似于AOARM。因此，图4间接说明忽略移动性的算法将会出现卸载任务和迁移任务数量均增加的情况。

4.4　任务迁移开销与移动设备总收益之间的关系

假定C_{\mathrm{M}\mathrm{E}\mathrm{C}}=\mathrm{26} GHz， 迁移开销\delta为\mathrm{0.2}~\mathrm{0.7}，N=18，对移动设备的总收益随任务迁移开销\delta的变化情况进行了仿真实验，结果如图5所示。

由图5可知，对于4种算法，随着任务迁移开销增加，总收益均逐渐减少。采用DROAGA时，移动设备总收益的下降速率较慢，这是因为该算法能减少任务迁移的概率，因此任务迁移开销增加对该算法的影响较小。采用ROARM时，由于卸载任务较少，当计算资源相对充裕时，任务迁移的概率较小，因此总收益降低较慢。采用AARM时，忽略了用户的移动性，因此任务迁移量较大，当任务迁移开销增加时，系统收益下降较快。采用AOARM时，任务全部被卸载，由于计算资源短缺，增加了迁移的概率，当有许多任务被迁移时，迁移开销增加，因此总收益下降较快。由图5还可以看到，随任务迁移开销的变化，AOARM的收益比AARM的收益减少的要慢，这是因为AOARM在资源分配时考虑了移动设备的移动性，这种算法可以确保大部分任务迁移的概率较低，因此，与不考虑用户移动性的AARM相比，AOARM能够获得较高的系统收益。

4.5　移动设备平均驻留时间与总收益之间的关系

假定仿真参数MEC的总计算资源C_{\mathrm{M}\mathrm{E}\mathrm{C}}=\mathrm{26} GHz， 迁移开销\delta =\mathrm{0.5}时，对采用不同算法获得的移动设备总收益随用户设备平均驻留时间的均值即

\overline{{\tau }_i}=\frac{{\displaystyle \sum _{i=\mathrm{1}}^N}{\tau }_i}{N}

的变化情况进行仿真实验，结果如图6所示。

在图6中可以看到，相比其他3种算法，随平均驻留时间的增加，采用本文算法获得的移动设备总收益最大。这是因为采用本文算法时，平均驻留时间越长，用户任务迁移的概率越低，MEC不需要分配太多的计算资源用于任务迁移，因此MEC节省下来的计算资源可以服务更多的移动设备，由于任务迁移需要消耗系统的收益，减少迁移则会增加移动设备的总收益；反之，驻留时间越短，则移动设备迁移的概率越高，移动设备的总收益越低。需要注意的是当移动设备的平均驻留时间较长（约大于50 s）时，每种算法的收益不再继续增加。因为当移动设备驻留时间足够长时，几乎所有的卸载任务都能在用户离开该小小区覆盖的范围前完成并将结果传回用户端，而不会发生任务的迁移。

5　 结 语

本文在基于MEC的小小区网络中，利用移动设备的驻留时间，分析其移动性。同时将任务卸载、迁移和计算资源的分配联合进行优化，减少任务迁移的概率，进而最大化移动设备的总收益。本文提出的基于效用函数的总收益最大化问题是一种混合整数非线性规划问题，为了解决该NP-hard问题，提出了基于遗传算法的分布式资源最优化算法，即DROAGA。在仿真实验中，我们通过模拟移动设备总收益随移动设备的数量、MEC总计算资源、任务迁移开销和移动设备平均驻留时间的均值等因素的变化情况来验证本文算法的性能。实验结果表明，与其他3种算法相比，本文提出的算法能有效地节省迁移开销并增加移动设备的总收益。

参考文献

[1] DENG M F， TIAN H， LIU X C. Adaptive sequential offloading game for multi-cell mobile edge computing［C］// 2016 IEEE 23rd International Conference on Telecommunications. New York： IEEE Press， 2016： 1-5. DOI：10.1109/ICT.2016.7500395 .

[2] TAN Z Y， YU F R， LI X，et al. Virtual resource allocation for heterogeneous services in full duplex-enabled SCNs with mobile edge computing and caching ［J］. IEEE Transactions on Vehicular Technology， 2018， 67（2）： 1794-1808. DOI：10.1109/TVT.2017.2764002 .

[3] HAO Y X， CHEN M， HU L，et al. Energy efficient task caching and offloading for mobile edge computing ［J］. IEEE Access， 2018， 6： 11365-11373. DOI：10.1109/ACCESS.2018.2805798 .

[4] ZHANG J， XIA W W， YAN F， et al. Joint computation offloading and resource allocation optimization in heterogeneous networks with mobile edge computing［J］. IEEE Access， 2018，6： 19324-19337. DOI：10.1109/ACCESS.2018.2819690 .

[5] LIU M T， YU F R， TENG Y L，et al. Joint computation offloading and content caching for wireless blockchain networks［C］// 2018 IEEE Conference on Computer Communications Workshops. New York： IEEE Press， 2018： 517-522. DOI：10.1109/INFCOMW.2018.8406929 .

[6] LIU M T， YU F R， TENG Y L，et al. Computation offloading and content caching in wireless blockchain networks with mobile edge computing ［J］. IEEE Transactions on Vehicular Technology， 2018， 67（11）：11008-11021. DOI：10.1109/TVT.2018.2866365 .

[7] TALEB T， KSENTINI A. An analytical model for follow me cloud ［C］ //2013 IEEE Global Communications Conference. New York： IEEE Press， 2013： 1291-1296. DOI： 10.1109/GLOCOM.2013.6831252 .

[8] KSENTINI A， TALEB T， CHEN M. A Markov decision process-based service migration procedure for follow me cloud［C］//2014 IEEE International Conference on Communications. New York： IEEE Press， 2014： 1350-1354. DOI： 10.1109/ICC.2014.6883509 .

[9] WANG S Q， URGAONKAR R， HE T，et al. Mobility-induced service migration in mobile micro-clouds ［C］//2014 IEEE Military Communications Conference. New York： IEEE Press， 2014： 835-840. DOI： 10.1109/MILCOM.2014.145 .

[10] WANG S Q， URGAONKAR R， ZAFER M，et al. Dynamic service migration in mobile edge-clouds ［C］//2015 IEEE IFIP Networking Conference. New York： IEEE Press， 2015： 1-9. DOI： 10.1109/IFIPNetworking.2015.7145316 .

[11] TALEB T， KSENTINI A， FRANGOUDIS P A. Follow-me cloud： When cloud services follow mobile users ［J］. IEEE Transactions on Cloud Computing， 2019， 7（2）： 369-382. DOI： 10.1109/TCC.2016.2525987 .

[12] ZENG J， SUN J Y， WU B W，et al. Mobile edge communications， computing， and caching （MEC3） technology in the maritime communication network ［J］. China Communications， 2020， 17（5）：223-234. DOI：10.23919/JCC.2020.05.017 .

[13] YAO D Z， YU C， YANG L T， et al. Using crowdsourcing to provide QoS for mobile cloud computing ［J］. IEEE Transactions on Cloud Computing， 2019， 7（2）： 344-356. DOI：10.1109/TCC.2015.2513390 .

[14] ZHANG Y M， LAN X L， REN J， et al. Efficient computing resource sharing for mobile edge-cloud computing networks［J］. IEEE/ACM Transactions on Networking， 2020， 28（3）：1227-1240. DOI：10.1109/TNET.2020.2979807 .

[15] MAHBAS A J， ZHU H L， WANG J Z. Impact of small cells overlapping on mobility management［J］. IEEE Transactions on Wireless Communications， 2019， 18（2）： 1054-1068. DOI：10.1109/TWC.2018.2889465 .

[16] GAO S， PENG Z， XIAO B， et al. Detection and mitigation of DoS attacks in software defined networks ［J］. IEEE/ ACM Transactions on Networking， 2020， 28（3）： 1419-1433. DOI： 10.1109/ TNET. 2020.2983976 .

[17] SUN Y Z， GUO G， ZHANG S Q， et al. A cluster-based energy-efficient resource management scheme with QoS requirement for ultra-dense networks ［J］. IEEE Access， 2020， 8：182412-182421. DOI：10.1109/ACCESS.2020.3028942 .

基金资助

辽宁省自然科学基金(20180550046)

辽宁省教育厅科学研究项目(ZGXJ2020005)

辽宁省社会科学基金(L20BGL008)

沈阳市高校“双服务”重点项目(202103023)

中央高校基本科研业务费重大培育项目(D2019012)