雾计算网络中基于移动感知的任务卸载和资源分配

Task Offloading and Resource Allocation Based on Mobile-Aware in Fog Computing Networks

摘要

在雾计算网络中由于雾计算节点（fog computing node，FCN）有限的覆盖范围和用户的移动，导致用户很容易离开原雾节点的覆盖范围并产生任务执行结果的迁移，同时引起能量消耗和时间延迟，进而影响用户的收益。针对这些问题，在三层雾计算网络中，通过分析用户驻留时间来考虑用户的移动性；通过任务卸载、FCN的选择和计算资源分配进行联合优化减少任务迁移概率，进而降低系统开销，最大化用户的总收益。该最大化问题被分解为任务卸载和资源分配两部分进行求解。在任务卸载方面，提出了基于基尼系数的雾计算节点选择算法；在资源分配方面，提出了基于遗传算法的分布式资源分配算法。仿真实验结果表明，本文算法与其他算法相比能获得更多的用户总收益。

Abstract

In fog computing networks, due to the limited service coverage of fog computing node(FCN)， the moving users may be out of the coverage, which would cause the migration of execution results. Furthermore, energy consumption and time latency are generated and affects the revenue of users. To solve these problems, a generic three layers fog computing networks is considered, and the mobility of users is characterized by the sojourn time. To maximize the revenue of users and reduce system overhead, the offloading decisions, FCN selection and computation resource allocation are jointly optimized to reduce the probability of migration. The maximization problem is divided into two parts: task offloading and resource allocation. A FCN selection algorithm based on Gini coefficient (FSAGC) is proposed to get a task offloading strategy, and a distributed resource allocation algorithm based on genetic algorithm (DRAAGA) is implemented to solve the computing resource allocation problem. Simulations demonstrate that the proposed algorithms can achieve more revenue performance compared with other algorithms.

Graphical abstract

关键词

雾计算网络 / 基尼系数 / 资源分配 / 任务卸载

Key words

fog computing networks / Gini coefficient / resource allocation / task offloading

0　 引 言

快速发展的移动通信技术促使大量新颖业务出现，例如：增强现实、虚拟现实等。然而用户终端设备有限的计算能力和电池容量，很难满足以上业务的需求。云无线接入网络，虽然可以提供强大的计算资源，但是由于云端远离本地，系统带宽受到限制，传输时延较长，因此，对传输延迟敏感的业务很难得到应用。为解决该问题，雾计算网络应运而生。由于雾计算节点（fog computing node, FCN）部署在用户的附近，如果用户的任务卸载到FCNs上执行，则可以大大减少通信的传输延迟并节省从FCNs到云服务器（cloud servers, CSs）间回传链路的带宽^[1]。

雾计算网络可以通过多维资源管理来改善能量消耗、传输时延，满足QoS需求等，但在雾计算网络的资源分配领域还面临一些挑战，例如：1）FCN的计算能力受限时，为了减少能量消耗，如何优化任务卸载和资源分配的问题；2）为了提升系统性能，FCN如何协作匹配的问题；3）由于用户的移动性产生任务迁移，进而产生额外的资源消耗，在考虑用户移动性的条件下，如何设计任务卸载策略减少资源消耗的问题。针对这些问题，现有一些文献进行了研究。文献[2~5]研究了任务卸载和资源分配问题。文献[2]提出了一种基于社会感知的动态任务卸载策略，并通过博弈论方法来最小化任务执行消耗。文献[3]提出一种近似最优的资源分配策略应用于任务卸载中。文献[4]提出了一种减少能量消耗和任务延迟的任务卸载策略。文献[5]提出了一种基于边缘计算的部分任务卸载策略来减少雾节点的能量消耗和减少任务平均延迟。文献[6~9]研究了FCN协作匹配问题。文献[6]提出了一种延迟最小的协作和卸载策略用于雾节点协作。文献[7]采用博弈论方法，研究了雾节点间的协作关系。文献[8]在雾计算网络中采用排队论来解决多FCN最优化匹配问题。文献[9]提出了一种匹配博弈的延迟接收算法，用来减少雾节点协作时的平均等待时间。文献[10~13]在考虑用户移动性的条件下，研究任务卸载策略。文献[10]在雾计算网络中研究了一种基于用户移动性和网络异构性的划分算法。文献[11]提出了一种基于遗传算法的卸载策略来提高用户的服务质量和最小化资源消耗。文献[12]提出了一种考虑用户移动性的机会任务卸载策略。文献[13]提出了一种基于跟踪匹配子序列方法的用户接入预测算法，该算法用来减少任务完成时间，减少能量消耗和提升任务卸载成功率。通过以上的分析我们可以看到，这些研究都是将问题独立分解研究，而实际应用中，往往会联合考虑FCN的计算能力、用户的移动性、任务迁移带来的资源消耗、传输资源和计算资源的联合调度问题。

因此，与以往独立研究不同，本文在三层雾计算网络中，通过用户驻留时间分析用户的移动性，并通过联合考虑任务卸载策略、FCN选择和计算资源分配来减少任务迁移的概率，降低系统开销，进而最大化用户的总收益。本文研究的用户收益最大化问题可以转换为一个混合整数非线性规划问题，该问题是一个非确定性多项式难题（non-deterministic polynomial-hard problem，NP-hard problem），可分解为任务卸载和资源分配两部分，我们分别采用基于基尼系数的雾计算节点选择算法（FCN selection algorithm based on Gini coefficient,FSAGC）和基于遗传算法的分布式资源分配算法（distributed resource allocation algorithm based on genetic algorithm,DRAAGA）进行求解。

1　 雾计算网络架构与计算模型

1.1　雾计算网络架构

图1为三层雾计算网络架构中的用户移动模型。三层雾计算网络包括云计算层、雾计算层和用户层。云计算层距离用户端较远，其计算和存储能力强大，但执行用户任务时传输时延大。雾计算层包括大量具有计算功能的FCN，并且这些节点距离用户端较近，可以为用户提供计算资源。当用户的任务卸载到FCN进行计算时，可以降低任务传输到云计算层的传输时延。用户层包括大量的用户设备，例如车辆、智能终端等，这些设备具有移动性和计算能力。

在图1中，考虑了用户设备的移动性，由于FCN覆盖的范围有限，如果一个移动设备已经将任务卸载给FCN，但是在他离开原FCN覆盖范围前，任务仍然没有执行完成，这时执行结果将通过云服务器迁移给正在提供服务的FCN，这会引起额外的开销，包括能量消耗和时间延迟。

在该网络中，用户设备广泛分布在FCN附近，而FCN则是随机分布的。令N_F=\{\mathrm{F}\mathrm{C}{\mathrm{N}}_{\mathrm{1}},\mathrm{F}\mathrm{C}{\mathrm{N}}_{\mathrm{2}},\cdots ,\mathrm{F}\mathrm{C}{\mathrm{N}}_f,\cdots ,\mathrm{F}\mathrm{C}{\mathrm{N}}_F\}表示雾计算网络中的FCN集合,其中F表示FCN的数量，\mathrm{F}\mathrm{C}{\mathrm{N}}_f用f代替。N_U=\{\mathrm{u}\mathrm{s}\mathrm{e}{\mathrm{r}}_{\mathrm{1}},\mathrm{u}\mathrm{s}\mathrm{e}{\mathrm{r}}_{\mathrm{2}},\cdots ,\mathrm{u}\mathrm{s}\mathrm{e}{\mathrm{r}}_u,\cdots ,\mathrm{u}\mathrm{s}\mathrm{e}{\mathrm{r}}_U\}表示用户设备的集合，其中U表示用户设备的数量，任意用户设备\mathrm{u}\mathrm{s}\mathrm{e}{\mathrm{r}}_u本文用u代替。假设每个用户设备每个时刻只有一个任务需要去执行。每个计算任务Z_u包含有3个参数，Z_u=\left\{D_u,f_u,T_u^{\mathrm{m}\mathrm{a}\mathrm{x}}\right\}，\forall u\in N_U。这里D_u（bit）表示从用户设备端到FCN端需要传输执行的任务量的大小（例如：输出参数、程序代码和系统设置等）;f_u（GHz）表示完成用户u的任务所需的计算资源；T_u^{\mathrm{m}\mathrm{a}\mathrm{x}}（s）表示完成任务Z_u允许的最大时延。本文用CPU周期数衡量任务需要的计算资源^[14]。每个任务可以本地执行或卸载到FCN中执行。S=\left\{s_u,u\in N_U\right\}表示卸载决定的集合，其中s_u=\left\{\mathrm{0,1}\right\}。s_u=\mathrm{1}表示任务Z_u将被卸载到一个FCN中去执行；s_u=\mathrm{0}表示任务将在本地移动设备上执行。

本文考虑正交频分多址接入（orthogonal frequency division multiple access,OFDMA）上行系统采用多接入的方式。假设在一个FCN的覆盖区域内，一个FCN能同时连接多个用户设备。即使设备在重叠覆盖区域内，每个用户设备也只能同时连接到一个FCN中。定义集合A表示包含所有FCN选择的变量集合，即A=\left\{a_{uf}\left|u\in N_U,f\in N_F\right.\right\}，a_{uf}=\mathrm{1}表示用户设备u选择卸载它的任务给第f个FCN即\mathrm{F}\mathrm{C}{\mathrm{N}}_f。选择策略必须满足如下限制

\sum _{u\in N_U}{a}_{uf}\le K（1）

\sum _{f\in N_F}{a}_{uf}\le \mathrm{1}（2）

其中，K表示每个FCN拥有的最大子信道数。（1）式表示每个FCN能同时服务的用户设备数目最大为K。（2）式表示每个用户设备同时只能连接到一个FCN。令U_f=\left\{u\in N_U\left|a_{uf}=\mathrm{1}\right.\right\}表示卸载任务给\mathrm{F}\mathrm{C}{\mathrm{N}}_f去执行的用户设备集合。设置U_{\mathrm{o}\mathrm{f}\mathrm{f}}={\cup }_{f\in N_F}{U}_f表示系统中卸载任务给FCNs的所有用户设备的集合。用户设备的收益可以通过卸载任务给FCN来实现。定义用户的收益为任务在本地执行时的消耗与任务卸载到FCN执行时的消耗之差。执行一个任务的消耗可以包括能量消耗和计算延迟。本地计算模型和雾计算模型将会在下文分别讨论。

1.2　计算模型

1.2.1　本地计算模型

当用户的任务在本地执行时，s_u=\mathrm{0}，消耗的能量用E_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}表示，执行时间用T_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}表示。令c_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}表示本地用户设备u的计算能力。因此，本地计算时间T_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}可以表示为

T_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}=\frac{f_u}{c_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}}，\forall u\in N_U（3）

当任务在本地执行时，能量消耗可以用每个CPU周期消耗的能量表示，即表示为E=\kappa c^{\mathrm{2}},这里\kappa是与芯片结构有关的系数，c是在本地执行任务时，执行该任务需要的CPU的计算资源^[15]。基于该模型，任务Z_u的能量消耗E_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}可以通过下式得到

E_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}=\kappa {\left(c_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}\right)}^{\mathrm{2}}{f}_u，\forall u\in N_U（4）

因此，本地执行的开销可以表示为

q_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}={\lambda }_u^{\mathrm{E}}{E}_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}+{\lambda }_u^{\mathrm{T}}{T}_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}，\forall u\in N_U（5）

这里{\lambda }_u^{\mathrm{E}}和{\lambda }_u^{\mathrm{T}}分别表示用户u在任务Z_{\mathrm{u}}上的能量消耗和时间延迟的权重系数。其中，{\lambda }_u^{\mathrm{E}}的数值我们可以取0.1、0.5(默认)、0.9。{\lambda }_u^{\mathrm{T}}的数值可以取0.1, 0.5(默认),0.9。假设{\lambda }_u^{\mathrm{E}}+{\lambda }_u^{\mathrm{T}}=\mathrm{1}，并且{\lambda }_u^{\mathrm{E}}，{\lambda }_u^{\mathrm{T}}\in \left[\mathrm{0,1}\right]。这些系数与用户的任务类型有关。如果，表示用户u对执行任务的延迟比较敏感。这里的任务包括视频流、在线通信等。换句话说，如果用户u的电池电量较低的话，{\lambda }_u^{\mathrm{E}}一般取值就要大于{\lambda }_u^{\mathrm{T}}，甚至在极端情况下{\lambda }_u^{\mathrm{E}}=\mathrm{1}。

1.2.2　雾计算模型

如果当用户u卸载它的任务Z_u给一个FCN时，总执行过程的延迟T_{uf}^F包括：

1） 从用户u到\mathrm{F}\mathrm{C}{\mathrm{N}}_f的上行传输时间t_{uf}^{\mathrm{u}\mathrm{p}}；

2） \mathrm{F}\mathrm{C}{\mathrm{N}}_f处理任务Z_u的执行时间t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}；

3） 从\mathrm{F}\mathrm{C}{\mathrm{N}}_f返回用户的传输时间。

本文假设执行结果的数据量都远小于输入的数据量，并且下行信道的条件要远好于上行信道的条件。因此，执行结果回传给用户的传输延迟可以被忽略^[16]。

每个FCN能同时服务于多个用户。只要每个用户到\mathrm{F}\mathrm{C}{\mathrm{N}}_f的传输信干噪比\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}能满足下列要求，该用户就能接入。

\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}\ge \mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}^{\mathrm{t}\mathrm{h}}（6）

其中，\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}^{\mathrm{t}\mathrm{h}}是保障用户收益的门限。因此，能够接入到\mathrm{F}\mathrm{C}{\mathrm{N}}_f的用户集合可以表示为U_f^c=\left\{u\in N_U\left|\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}\ge \mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}^{\mathrm{t}\mathrm{h}}\right.\right\}。假设用户传输他们的任务给FCN的最大传输功率为P=\left\{p_u\left|u\in N_U\right.\right\}，p_u表示用户u上分配的功率。用户与FCN间的子信道增益用G表示，G=\left\{g_{uf}\left|\forall u\in N_U,\forall f\in N_F\right.\right\}，g_{uf}表示从用户u到\mathrm{F}\mathrm{C}{\mathrm{N}}_f的上行子信道增益。用户u与\mathrm{F}\mathrm{C}{\mathrm{N}}_f间的\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}可以表示为

\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}=\frac{p_u{g}_{uf}}{{\sigma }^{\mathrm{2}}+\sum _{i\in N_F\backslash \left\{f\right\}}\sum _{j\in U_i}{a}_{ji}{p}_j{g}_{ji}}（7）

其中，{\sigma }^{\mathrm{2}}为背景噪声，用高斯白噪声表示。分母中的第二部分表示在相同子载波上，从所有用户到其他FCN的积累干扰。因此，传输速率r_{uf}可以表示为

r_{uf}=w\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\mathrm{1}+\mathrm{S}\mathrm{I}\mathrm{N}{\mathrm{R}}_{uf}\right)，\forall u\in N_U,\forall f\in N_F（8）

这里w表示子信道的带宽。当用户u的任务卸载到\mathrm{F}\mathrm{C}{\mathrm{N}}_f时，传输时间t_{uf}^{\mathrm{u}\mathrm{p}}可以表示为

t_{uf}^{\mathrm{u}\mathrm{p}}=\frac{D_u}{r_{uf}},\forall u\in N_U,\forall f\in N_F（9）

每个FCN的总计算资源可以表示为c^F，令C_f=\left\{c_{uf}^F\left|u\in U_f\right.\right\}表示\mathrm{F}\mathrm{C}{\mathrm{N}}_f上采用的计算资源分配策略，c_{uf}^F表示用户u在\mathrm{F}\mathrm{C}{\mathrm{N}}_f上分配的计算资源。令C_{\mathrm{o}\mathrm{f}\mathrm{f}}={\cup }_{f\in N_F}{C}_f表示\mathrm{F}\mathrm{C}{\mathrm{N}}_f上采用的全部计算资源分配策略的集合。因此，c_{uf}^F需要满足

\sum _{u\in U_f}{c}_{uf}^F\le c^F，\forall f\in N_F（10）

执行时间延迟t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}可以表示为

t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}=\frac{f_u}{c_{uf}^F}，\forall u\in N_U,\forall f\in N_F（11）

因此，任务在\mathrm{F}\mathrm{C}{\mathrm{N}}_f上处理过程的总时间可以表示为上传时间与在FCN上执行时间之和

T_{uf}^F=t_{uf}^{\mathrm{u}\mathrm{p}}+t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}，\forall u\in N_U,\forall f\in N_F（12）

传输时消耗的能量可以表示为

E_{uf}^{\mathrm{u}\mathrm{p}}=p_u{t}_{uf}^{\mathrm{u}\mathrm{p}}，\forall u\in N_U,\forall f\in N_F（13）

于是用户u在\mathrm{F}\mathrm{C}{\mathrm{N}}_f上执行任务总的消耗可以表示为

q_{uf}^F\left(c_{uf}^F\right)={\lambda }_u^{\mathrm{E}}{E}_{uf}^{\mathrm{u}\mathrm{p}}+{\lambda }_u^{\mathrm{T}}{T}_{uf}^F，\forall u\in N_U,\forall f\in N_F（14）

1.2.3　考虑用户移动性的雾计算模型

在以上雾计算模型基础上，考虑FCN的覆盖范围有限和用户的移动性，根据文献[16]，用户的移动性可以用驻留时间进行衡量，用户的驻留时间可以表示为一个指数函数。令t_{uf}^{\mathrm{s}}表示用户u在\mathrm{F}\mathrm{C}{\mathrm{N}}_f的覆盖范围内的驻留时间。因此，t_{uf}^{\mathrm{s}}的概率密度函数为

f_{{\tau }_{uf}}\left(t\right)=\frac{\mathrm{1}}{{\tau }_{uf}}{\mathrm{e}}^{-\frac{t}{{\tau }_{uf}}},t\ge \mathrm{0}，\forall u\in N_U,\forall f\in N_F（15）

其中，{\tau }_{uf}表示用户u在\mathrm{F}\mathrm{C}{\mathrm{N}}_f的覆盖范围内的平均驻留时间。由于用户设备有不同的移动轨迹和特点，{\tau }_{uf}是一个变量。假设每个用户的驻留时间{\tau }_{uf}是独立同分布的，为了简化处理，假设{\tau }_{uf}服从高斯独立同分布。

考虑到用户的移动性，当任务卸载给FCN时，按照执行过程的延迟和预测用户的驻留时间之间的关系，任务在FCN中执行有以下两种情况。

情况1：在\mathrm{F}\mathrm{C}{\mathrm{N}}_f的覆盖范围内，当任务Z_u卸载给\mathrm{F}\mathrm{C}{\mathrm{N}}_f时，用户u的驻留时间t_{uf}^{\mathrm{s}}超过\mathrm{F}\mathrm{C}{\mathrm{N}}_f上处理过程的总时间T_{uf}^F，即t_{uf}^{\mathrm{s}}>T_{uf}^F，这意味着执行结果能够直接回传给用户。在这种情况下，任务迁移的情况不会发生。根据（15）式可知，驻留时间t_{uf}^s服从指数分布，此时的概率表示为P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}>T_{uf}^F\right)。用户u在\mathrm{F}\mathrm{C}{\mathrm{N}}_f上的总消耗可以表示为

q_{uf}^{F,\mathrm{1}}=q_{uf}^F\left(c_{uf}^F\right)，\forall u\in N_U,\forall f\in N_F（16）

情况2：如果用户的驻留时间短于传输时间，任务卸载过程将不能完成，任务将在本地执行。对于某些用户来说，如果任务Z_u卸载给\mathrm{F}\mathrm{C}{\mathrm{N}}_f，并且用户u的驻留时间t_{uf}^{\mathrm{s}}短于\mathrm{F}\mathrm{C}{\mathrm{N}}_f上处理过程的总时间T_{uf}^F，此时的概率是P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}\le T_{uf}^F\right)，执行结果将通过云服务器迁移给正在为用户u提供服务的FCN中。这时的迁移过程将引起额外的能量消耗和时间延迟，这些都是用户消耗的部分。实际上，迁移消耗也与任务类型和与FCN的距离等因素有关^[17]，为了简化，本文假设任务发生迁移时的消耗只与需要迁移任务量的大小有关，因此可以表示为q_u^{\mathrm{m}\mathrm{i}\mathrm{g}}=\delta D_u，其中\delta表示迁移消耗系数。因此，情况2条件下，用户u的总消耗可以表示为

q_{uf}^{F,\mathrm{2}}=q_{uf}^F\left(c_{uf}^F\right)+q_u^{\mathrm{m}\mathrm{i}\mathrm{g}}，\forall u\in N_U,\forall f\in N_F（17）

从（16）和（17）式可以得出，执行任务Z_u在这两种情况下的消耗可表示为

q_{uf}^F=\left\{\begin{array}{ll}{q}_{uf}^{F,\mathrm{1}}, & P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}>T_{uf}^F\right)\\ q_{uf}^{F,\mathrm{2}}, & P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}\le T_{uf}^F\right)\end{array}\right.，\forall u\in N_U,\forall f\in N_F（18）

因此，消耗q_{uf}^F的期望值可以表示为执行任务Z_u的总消耗

\overline{q_{uf}^F}=P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}>T_{uf}^F\right)q_{uf}^{F,\mathrm{1}}+P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}\le T_{uf}^F\right)q_{uf}^{F,\mathrm{2}}（19）

其中，

P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}\le T_{uf}^F\right)={\int }_{\mathrm{0}}^{T_{uf}^F}\frac{\mathrm{1}}{{\tau }_{uf}}{\mathrm{e}}^{-\frac{t_{uf}^{\mathrm{s}}}{{\tau }_{uf}}}\mathrm{d}{t}_{uf}^{\mathrm{s}}=-{\mathrm{e}}^{-\frac{T_{uf}^F}{{\tau }_{uf}}}+\mathrm{1}（20）

P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}>T_{uf}^F\right)=\mathrm{1}-P_{{\tau }_{uf}}\left(t_{uf}^{\mathrm{s}}\le T_{uf}^F\right)（21）

2　 数学模型及求解算法

2.1　数学模型

如上所述，用户u的收益与能量消耗和计算延迟相关。因此，当任务Z_u卸载给FCN，则将收益定义为本地执行任务时的消耗与FCN上执行相同任务时的消耗之差。当用户u的任务Z_u在FCN上执行时，令Q_u表示用户u所能获得的收益。因此，当确定了哪些用户卸载任务给\mathrm{F}\mathrm{C}{\mathrm{N}}_f去执行时，Q_u可表示为

Q_u\left(s_u,a_{uf},c_{uf}^F\right)=\left\{\begin{array}{c}{q}_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-\sum _{f\in N_F}{a}_{uf}\overline{q_{uf}^F}, s_u=\mathrm{1}\\ \mathrm{0}, s_u=\mathrm{0}\end{array}\right.（22）

基于以上对用户设备的收益分析，本文提出了一个在计算资源和延迟限制条件下最大化用户总收益的问题,表达如下

（23）

其中，C1表示保证任务在FCN上处理过程的总时间T_{uf}^F，不能超过完成任务Z_u允许的最大时延T_u^{\mathrm{m}\mathrm{a}\mathrm{x}}；C2表示\mathrm{F}\mathrm{C}{\mathrm{N}}_f上所使用的计算资源不能超过分配给\mathrm{F}\mathrm{C}{\mathrm{N}}_f的总计算资源；C3和C7限制a_{uf}和s_u变量的取值范围；C4中的I\left(•\right)表示指示函数，如果“\left(•\right)>\mathrm{0}”，则令I\left(•\right)=\mathrm{1}，否则，令I\left(•\right)=\mathrm{0}，C4保证了FCN不能分配计算资源给任务在本地执行的用户；C5表示每个FCN能够同时服务用户的数量最大不超过K，该数量取决于子载波的数量；C6表示一个用户只能接入一个FCN来卸载它的任务；C8表示如果用户决定卸载自己的任务时，该用户必须接入到一个FCN中。

由（23）式可知，用户的总收益与任务卸载决策、FCN选择和计算资源分配有关。而且用户的移动性对用户的总收益有很大的影响。如果卸载任务的执行结果不能直接传回用户端，则FCN需要将结果通过云服务器迁移给另一个FCN。迁移过程将引起能量消耗和时间延迟。

按照用户的不同驻留时间，通过采用比较合适的卸载策略，选择稳定的FCN和分配合适的资源，迁移概率将会大大降低。这时迁移消耗也将减少，用户的收益将提高。因此，在下节，我们提出了一种基于基尼系数的雾计算节点选择算法FSAGC来联合考虑最优化任务卸载决策和FCN选择，随后提出一种基于遗传算法的分布式资源分配算法DRAAGA解决计算资源分配的最优化问题。

2.2　求解算法

2.2.1　基于基尼系数的雾计算节点选择算法

根据文献[18],基尼系数常用于经济学领域用来衡量收益差距的指标，我们受到基尼系数的启发，采用基尼系数解决FCN选择问题。本文每个用户设备的收益被定义为一个选择函数，不同的用户设备对系统总收益有不同贡献。采用选择函数获得U_f=\left\{u\in N_U\left|a_{uf}=\mathrm{1}\right.\right\}，这里被选中的用户设备可以贡献主要收益，收益包括能量、时间和迁移量。因此基于基尼系数的雾计算节点选择算法（FCN selection algorithm based on Gini coefficient, FSAGC），详见算法1。

1） 算法步骤

步骤1 预卸载

首先设置\mathrm{F}\mathrm{C}{\mathrm{N}}_f的候选用户集合B_f为空集。如果用户u的任务{\mathrm{Z}}_u能够卸载到FCN去执行，这时需要满足以下两个限制条件，分别是和。当用户u满足以上两个限制条件时，任务能够卸载给FCN去执行，这时将该用户添加到B_f中。如果t_{uf}^{\mathrm{u}\mathrm{p}}>{\tau }_{uf}，则任务在一个较高概率下将被终止传输，这是由于在FCN的覆盖范围内，用户u驻留时间较短。如果q_{uf}^F\ge q_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}，则表示用户u的任务在FCN上的计算消耗要大于任务在本地执行时的计算消耗，这时用户u任务将在本地执行。因此，FCN就需要选择为其他用户提供服务。这样由于用户数量减少，进而减少了（23）式中的计算难度。

步骤2 基尼系数计算

首先，通过选择函数来计算用户的收益，选择函数可以表示为

{\psi }_{uf}={\eta }_{uf}{\left[q_u^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-\overline{q_{uf}^F}\left(c^F\right)\right]}^{+}，\forall u\in N_U,\forall f\in N_F（24）

其中，{\left[x\right]}^{+}=\mathrm{m}\mathrm{a}\mathrm{x}\left\{x,\mathrm{0}\right\}，并且{\eta }_{uf}是用户u的收益权重值，可以通过下式计算

{\eta }_{uf}=\left(\frac{\sum _{u\in B_f}{\epsilon }_{uf}^F}{\left|B_f\right|{\epsilon }_{uf}^F}\right)\left(\frac{{\tau }_{uf}}{t_{uf}^{\mathrm{u}\mathrm{p}}+t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}}\right)，\forall u\in N_U,\forall f\in N_F（25）

其中，B_f可以通过步骤1获得；{\epsilon }_{uf}^F=f_u/\left({\tau }_{uf}-t_{uf}^{\mathrm{u}\mathrm{p}}\right)；{\left[q_{\mathrm{u}}^{\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{l}}-\overline{q_{uf}^F}\left(c^F\right)\right]}^{+}表示当全部的计算资源分配给用户时，用户u从\mathrm{F}\mathrm{C}{\mathrm{N}}_f获得的收益。

权重值{\eta }_{uf}综合考虑了需求的计算资源和用户驻留时间。其中，\frac{\sum _{u\in B_f}{\epsilon }_{uf}^F}{\left|B_f\right|{\epsilon }_{uf}^F}用来表示分配给用户u的计算资源占用户收益的比例；\frac{{\tau }_{uf}}{t_{uf}^{\mathrm{u}\mathrm{p}}+t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}}表示驻留时间的比例。由于移动性是影响用户收益的重要因素，考虑用户的驻留时间与计算资源相关，故在权重值中将\frac{{\tau }_{uf}}{t_{uf}^{\mathrm{u}\mathrm{p}}+t_{uf}^{\mathrm{e}\mathrm{x}\mathrm{e}}}作为一个乘数。

然后，根据选择函数计算在每个FCN中的B_f的用户收益。在B_f中的所有用户的收益值{\psi }_f^{\mathrm{s}}按照升序排列：{\psi }_f^{\mathrm{s}\mathrm{1}}\le {\psi }_f^{\mathrm{s}\mathrm{2}}\le \dots \le {\psi }_f^{\mathrm{s}\left|B_f\right|}。排列后的B_f可以表示为B_f^{\mathrm{s}}。定义属于\mathrm{F}\mathrm{C}{\mathrm{N}}_f的收益之和表示为Y_f={\displaystyle \sum _{u=\mathrm{1}}^{\left|B_f\right|}}{\psi }_{uf}，\forall f\in N_F，并定义累计收益率，表示为y_{if}=\frac{\mathrm{1}}{Y_f}{\displaystyle \sum _{u=\mathrm{1}}^i}{\psi }_{uf}， i=1,2,…,\left|B_f\right|。\mathrm{F}\mathrm{C}{\mathrm{N}}_f的基尼系数G_f可以表示为

G_f=\mathrm{1}-\frac{\mathrm{1}}{\left|B_f\right|}\left(\mathrm{1}+\mathrm{2}{\displaystyle \sum _{i=\mathrm{1}}^{\left|B_f\right|-\mathrm{1}}}{y}_{if}\right)，\forall f\in N_F（26）

并且定义选择的\mathrm{F}\mathrm{C}{\mathrm{N}}_f的数量为

I_f=\mathrm{m}\mathrm{i}\mathrm{n}\left\{⌈\frac{\mathrm{1}}{G_f}⌉+⌈\frac{L_f}{\left|B_f\right|}\left(\left|B_f\right|-⌈\frac{\mathrm{1}}{G_f}⌉\right)⌉,\left|B_f\right|\right\}（27）

其中, ⌈\frac{\mathrm{1}}{G_f}⌉的值表示用户获得的主要收益；⌈\frac{L_f}{\left|B_f\right|}\left(\left|B_f\right|-⌈\frac{\mathrm{1}}{G_f}⌉\right)⌉表示⌈\frac{\mathrm{1}}{G_f}⌉的修正系数，L_f是\mathrm{F}\mathrm{C}{\mathrm{N}}_f的资源负载容量，\frac{L_f}{\left|B_f\right|}是\left|B_f\right|与⌈\frac{\mathrm{1}}{G_f}⌉之间差异的权重系数。

L_f=\mathrm{m}\mathrm{i}\mathrm{n}\left\{⌊\frac{c^F}{{\epsilon }_{f,\mathrm{m}\mathrm{i}\mathrm{d}}^F}⌋,\left|B_f^{\mathrm{s}}\right|,K\right\}（28）

{\epsilon }_{f,\mathrm{m}\mathrm{i}\mathrm{d}}^F=\left\{{\epsilon }_{uf}^{\mathrm{s},F}\left|u=⌊\frac{\left|B_f\right|}{\mathrm{2}}⌋\right.\right\}（29）

其中，{\epsilon }_{uf}^{\mathrm{s},F}是{\epsilon }_{uf}^F按升序进行存储的集合。

最后，（23）式中的系数问题可以进一步简化并且\mathrm{F}\mathrm{C}{\mathrm{N}}_f服务的用户的卸载空间可以表示为

B_f^{\mathrm{s},\mathrm{o}}=\left\{B_{f,\left|B_f^{\mathrm{s}}\right|}^{\mathrm{s}},B_{f,\left|B_f^{\mathrm{s}}\right|-\mathrm{1}}^{\mathrm{s}},\cdots ,B_{f,\left|B_f^{\mathrm{s}}\right|-I_f+\mathrm{1}}^{\mathrm{s}}\right\}，\forall f\in N_F（30）

步骤3 匹配选择

（23）式中的C5和C6表示限制每个用户能连接到FCN的数量。但是在基尼系数计算中被选的用户可能同时连接的FCN数量多于一个。因此，集合B_f^{\mathrm{s},\mathrm{o}}将进一步设置来满足C5和C6的要求，具体设置如下。

首先，如果用户u被多个FCN选择，可以比较该用户从不同FCN上获得的收益，进而选择收益最大的FCN。同时从另一个B_f^{\mathrm{s}.\mathrm{o}}集合中删除用户u，并且从集合\left\{B_{f,i}^{\mathrm{s}}\left|i=\left|B_f^{\mathrm{s}}\right|\right.-I_f,\left|B_f^{\mathrm{s}}\right|-I_f-\mathrm{1},\cdots ,\mathrm{1}\right\}中添加新的用户。然后，做循环操作直到所有的用户满足C6的要求。最后，获得每个FCN的集合U_f=\left\{u\in N_U\left|a_{uf}=\mathrm{1}\right.\right\}，如果用户没有被任何FCN选中，则该用户的任务将在本地执行。

2） 算法复杂度分析

FSAGC算法的复杂性是多项式复杂性，分析如下：

做\left|N_F\right|\left|U_f\right|次迭代来确定某些不适合卸载任务的用户，这些用户在本地执行任务。

计算复杂度是{\rm O}\left(\left|B_f\right|\right)并且存储过程的复杂度是{\rm O}\left({\left|B_f\right|}^{\mathrm{2}}\left|N_F\right|\right)。

通过\left|N_F\right|\left|U_f\right|次迭代获得每个FCN的集合U_f。因此，FSAGC的计算复杂度可以表示为{\rm O}\left(\left|N_F\right|\left|U_f\right|+\left|B_f\right|+{\left|B_f\right|}^{\mathrm{2}}\left|N_F\right|+\left|N_F\right|\left|U_f\right|\right)。由于\left|B_f\right|\le \left|U_f\right|\le K，因此复杂度能进一步表示为{\rm O}\left(K^{\mathrm{2}}F\right)，可以看到FSAGC算法的复杂度只与FCN中的信道数和FCN的数量有关。由此可知FSAGC算法复杂度较低，可以满足在实际系统中的应用。

2.2.2　基于遗传算法的分布式资源分配算法

由于FCNs是彼此相互独立的，因此，每个FCN的资源分配能够独立进行。用户的收益可表示为一个适应度函数，该函数用来估计每个个体的适合程度。问题（23）的约束条件将在初始条件和选择时得到保障。选用实数编码串作为算法所用的染色体。每个染色体都是问题（23）的一个解，可以表示为

J_i^f=\left[J_{\mathrm{1}},\dots ,J_u,\dots ,J_{\left|U_f\right|}\right]，\forall f\in N_F（31）

这里J_u=c_{uf}^F表示用户u在FCN _f 上分配的计算资源。

当任务卸载决策和FCN选择完成后，（23）式的求解问题转化为对资源进行分配的求解问题，常见的求解方法有回溯法^［15］、动态规划法算法^［15］等，但是这些算法需要较多的迭代次数，时间复杂度和空间复杂度都较高。为了减少迭代次数和时间、空间复杂度，本文提出了一种基于遗传算法的分布式资源分配算法（distributed resource allocation algorithm based on genetic algorithm, DRAAGA），如算法2。该算法受达尔文进化论的启发，是一种启发式搜索方法，用于逼近最佳解，算法过程体现了自然选择，它选择最合适的个体进行后代遗传，该算法广泛应用于机器学习、组合优化和智能计算中。

首先，在算法开始时，将随机生成K个个体。这里的个体就是资源分配方案，包括了FCN中计算资源的分配、用户设备的上行信道和功率的分配。其次，在每次进化的过程中都要做概率为P_{\mathrm{c}}的交叉操作和概率为P_{\mathrm{m}}的变异操作。最后，经过多次进化后，最佳个体即资源分配方案将被计算出来。在交叉操作和变异操作中，将采用随机竞赛选择法^［15］。该方法有较低的计算复杂度和较好的个体选择性。每次随机选择两个个体，保留其中最好的一个个体。直到所有个体都被选到。如果在选择操作中最好的个体被忽略，则下一代中最好的个体将被提取出来，并代替最好的个体。

在算法复杂度方面，本文提出的DRAAGA算法的复杂度为{\rm O}({\left|U_f\right|}^{\mathrm{2}})，可以看到其计算复杂度较低，只与将任务卸载到FCN端执行的用户设备的数量有关，因此适合在实际系统中应用，例如：车联网、无人驾驶、超清视频等。

3　 仿真分析

3.1　仿真参数及对比算法

为了验证本文所提算法在不同参数下的用户收益，在Win10系统下，采用Matlab R2014a进行1 000次的蒙特卡洛随机仿真实验。我们依据参考文献[3]和[19]设置仿真参数如表1。雾计算网络的基站覆盖半径是500 m，每个FCN的覆盖半径是100 m。

FCN和用户是随机分布的，随着用户的移动，用户的平均驻留时间服从高斯分布\mathrm{C}\mathrm{N}\left({\mu }_t,{\sigma }_t^{\mathrm{2}}\right)，这里{\mu }_t=30 s 并且{\sigma }_t=10。DRAAGA算法中的子信道数K=\mathrm{32}，P_{\mathrm{c}}=\mathrm{0.6}，P_{\mathrm{m}}=\mathrm{0.1}。本文提出的算法将与另外4种算法进行比较。第一种算法采用了接近最优的资源分配机制（near optimal resource allocation mechanism，NORAM），该机制中的计算资源均匀分配，但是该机制没有考虑用户的移动性^[3]。第二种算法是忽略移动性的资源分配算法（allocation algorithm regardless of mobility，AARM），类似于NORAM算法，计算资源采用最优的分配方式，AARM算法也没有考虑用户的移动性。第三种算法是随机卸载算法（randomly offloading algorithm regard of mobility，ROARM），随机卸载的概率是0.5，计算资源均匀分配。第四种算法是全卸载算法（all offloading algorithm regard of mobility，AOARM），任务全部卸载，并且计算资源均匀分配。

3.2　FCN的数量与用户总收益之间的关系

假定仿真参数：用户数量为70，迁移消耗\delta =\mathrm{0.05}，c^F=\mathrm{4}\mathrm{G}\mathrm{H}\mathrm{z}。对用户的总收益随FCN的数量变化情况进行仿真实验，实验结果如图2所示。

从图2可以看到，随着FCN数量的变化，不同算法下的用户总收益不断提升。用户是随机分布在FCNs附近。由于每个FCN计算资源有限，因此只有少部分用户能够得到服务。随着部署在用户附近的FCN越多，将会有越多的用户能得到服务，更多的任务将被卸载，进而提高用户的总收益。根据执行任务所需求的计算资源和用户的平均驻留时间，考虑用户的移动性并根据信道条件，可以帮助FCN选择合适的用户卸载任务。由于驻留时间服从指数分布，因此根据每个用户的平均驻留时间，再分配一定数量的计算资源，就可以帮助FCN去计算用户的迁移概率。因此，通过采用最优化的任务卸载和资源分配策略，用户的迁移概率可以尽可能地降低，最终提升用户的总收益。

从图2中还可以看到，在ROARM算法中，当FCN的数量大于25时，算法取得的总收益基本保持不变；在本文提出的算法、AOARM算法、AARM算法和NORAM算法中，当FCN的数量大于35时，所有算法所取得的总收益基本保持不变。这是由于被服务的用户的数量保持不变，当FCN的数量大到足够给所有用户提供服务时，随着FCN数量的增加，由于某些用户的信道条件较差和某些用户的驻留时间较短，因此这些用户不能将任务卸载到FCN，所以算法得到的总收益也不会进一步提升，这也是为什么ROARM算法的总收益最差，而本文提出的算法的总收益最好的原因。由于NORAM算法的计算资源采用近似最优的分配方法，这也使得NORAM算法的总收益要略小于计算资源最优分配的AARM算法。

3.3　用户数量与未迁移任务比例之间的关系

假定仿真参数：每个FCN的总计算容量c^F=\mathrm{4}\mathrm{G}\mathrm{H}\mathrm{z}，迁移消耗\delta =\mathrm{0.05}，FCN的数量为20。对未迁移任务的比例随用户数量变化情况进行仿真，实验结果如图3。

未迁移任务的比例是指未迁移任务的数量占总卸载任务数量的比例。由图3可知，当用户的数量较小时，本文提出的算法可保障94%的卸载任务在用户离开FCN的覆盖区域前被执行完毕。随着用户数量的增加，采用AOARM算法、AARM算法和NORAM算法时，未迁移任务的比例的下降速度要快过本文提出的算法和ROARM算法的下降速度。这是由于AARM和NORAM算法没有考虑用户的移动性，出现卸载量大的问题，而AOARM算法是任务全部卸载的算法，因此它是所有算法中未迁移任务的比例最小的。从图3中还可知，当用户数量较多时，采用AARM和NORAM算法，有近一半的卸载任务不能在用户离开前执行完毕，因此产生了任务迁移。这也说明，如果选择不合适的FCN也会降低未迁移任务的比例。采用AOARM算法时未迁移任务的比例的下降速度最快的原因是，由于AOARM算法是卸载所有的任务，故未迁移任务的比例要小于其他算法。采用本文提出的算法时未迁移任务的比例也降低，但是降速较慢，这是因为本文提出的算法充分考虑了用户的移动性进行了最优的任务卸载，并且也采用了最优的资源分配方式。同时，我们还能看到采用ROARM算法时，未迁移任务的比例下降最慢，这是因为随机卸载50%的任务，卸载量较小。同时结合仿真图4，我们还能分析出，当任务卸载越多，任务迁移就越多，对用户的总收益影响越大，因为迁移任务将产生系统的消耗。

3.4　用户数量与用户总收益之间的关系

假定仿真参数：每个FCN的总计算容量c^F=\mathrm{4}\mathrm{G}\mathrm{H}\mathrm{z}，迁移消耗\delta =\mathrm{0.05}，FCN的数量为20。对用户的总收益随用户数量变化情况进行仿真，实验结果如图4。

从图4中可以看到随着用户数量的增加，AOARM、AARM和NORAM算法的用户总收益的变化不同于本文算法和ROARM算法。起初，所有算法的总收益都随着用户数量的增加而增加。然而，随着用户数量的增加，AOARM、AARM和NORAM算法增长的速率逐渐变慢，当用户数量值达到60时，总收益开始降低。由于FCN数量和计算容量的限制，因此FCN只能服务于有限的用户数量。用户数量没有达到上限时，这些算法总收益不断增加；伴随着任务卸载量的增加，迁移的任务也在增加，当增加的迁移消耗大于任务卸载所获得的收益时，这些算法的用户总收益开始下降。因为AOARM算法卸载所有的任务，AARM算法没有考虑用户的移动性，只要FCN有计算容量，AARM算法就卸载任务，因此AOARM算法任务迁移量要多于AARM算法，AOARM算法的收益要低于AARM算法。另外，当用户数量大于60时，NORAM算法的收益也随着用户数量的增加逐渐变小，这是因为，FCN的计算资源均匀分配给每个用户，当用户数量增多时，就使得有更多的任务不能在用户离开FCN覆盖区域前执行完毕，就会产生迁移，使得用户收益开始下降。本文提出的算法和ROARM算法还未开始下降，是因为本文提出的算法考虑了用户的移动性和迁移的概率，因此较好地控制了卸载任务数量；ROARM算法采用随机卸载的概率是0.5，使得卸载量较少。因此这两种算法在用户数量为20~80时都还未达到FCN处理的瓶颈，所以用户的总收益未随着用户数量的增加而下降。从图4中还能够看到，NORAM算法的收益要低于AARM算法，这是因为NORAM算法是均匀的分配资源给用户，而AARM算法是最优的方式分配资源给用户。

3.5　FCN的计算容量与用户总收益之间的关系

假定仿真参数：用户数量为70，FCN的数量为20，迁移消耗\delta =\mathrm{0.05}。对用户总收益随FCN的计算容量c^F变化情况进行仿真，实验结果如图5。

从图5中可以看到，随着FCN的计算容量从4~8 GHz变化时，所有算法的总收益随着每个FCN的计算容量的提升而增加。当起始处FCN的计算容量较小时，本文算法的总收益仍然高于其他算法，这说明本文算法能较好地利用FCN的计算资源。然而，随着FCN计算容量的增加，本文算法与AARM和NORAM算法相比差距在逐渐变小。因为本文算法为了减少迁移的概率将以用户总收益最大化为目标，选择性地卸载任务，随着FCN计算容量的增加，卸载的任务需要保证在用户离开FCN覆盖的范围前，能以较高概率执行完毕。由于本文算法中卸载任务的数量没有快速地改变，因此总收益增长得较慢。然而，在AARM和NORAM算法中，当FCN计算容量增加时，任务迁移减少，使得这两种算法用户总收益增长的速度要大于本文算法。从图5中还可以看到，当FCN计算容量增加，AARM算法和NORAM算法所获得的用户总收益，与AOARM算法所获得的用户总收益之间的差距将越来越大。这是因为AOARM算法卸载任务的数量和迁移任务的数量都大于AARM和NORAM算法，在AOARM算法中所有任务被卸载，使得某些用户只能在较差的信道条件下也进行卸载，因此影响了用户总收益。在ROARM算法中由于是随机卸载50%的任务，任务量较少，随着FCN计算容量的增加，卸载的任务都能在用户离开FCN覆盖范围前执行完毕，因此，ROARM算法所获得的用户总收益增长最少。

3.6　用户平均驻留时间与用户总收益之间的关系

假定仿真参数：用户数量为70，FCN的数量为20，迁移消耗\delta =\mathrm{0.05}，计算容量c^F=\mathrm{4}\mathrm{G}\mathrm{H}\mathrm{z}。在这里用户的平均驻留时间服从高斯分布\mathrm{C}\mathrm{N}\left({\mu }_t,{\sigma }_t^{\mathrm{2}}\right)，其中{\mu }_t=\mathrm{30} s，{\sigma }_t=\mathrm{10}。对用户总收益随用户平均驻留时间{\mu }_t变化情况进行仿真，实验结果如图6。

在图6中，能看到当用{\mu }_t小于40 s时，本文算法在用户总收益上增加得比其他四种算法要快。这是因为随着{\mu }_t的增加，参与仿真的用户数量也要多于以前。因此，考虑到每个用户的驻留时间的增加，能帮助FCN选择更多的用户提供服务，而且不需要分配过多的计算资源来减少迁移概率，因此有更多用户的计算资源得以节省。需要注意的是当{\mu }_t大于50 s时，几乎每种算法的总收益都停止增加。因为当驻留时间足够长时，用户绝大部分的卸载任务都能在迁移前完成，并将结果传回用户端。再看算法间的不同，虽然{\mu }_t增加，但每个用户仿真所用的平均驻留时间较小，增加的平均驻留时间不会给用户带来更多的总收益，因此增加{\mu }_t将不会缩小本文算法与其他算法间的差距。

3.7　任务迁移消耗与用户总收益之间的关系

假定仿真参数：用户数量为70，FCN的数量为20，计算容量c^F=\mathrm{4}\mathrm{G}\mathrm{H}\mathrm{z}。对用户的总收益随迁移消耗数量变化情况进行仿真，实验结果如图7。

从仿真中可以看到，尽管随着迁移消耗的增加，用户的总收益下降，但是本文算法所获得的总收益与其他算法相比要多，这证明了本文算法能有效的降低用户迁移的概率。在AARM算法、NORAM算法和AOARM算法中，由于忽略了用户的移动性，将导致较多的任务卸载。由于用户和FCN上的计算资源有限，使得迁移概率变高，因此，大量增加的迁移消耗将引起用户总收益的下降。很明显地可以看到，AOARM算法与AARM算法和NORAM算法相比，随迁移消耗的增加所获得的用户总收益降低的幅度要少，这是因为，AOARM算法在卸载全部任务的同时，与AARM和NORAM算法相比，更能够平衡用户短驻留时间和长驻留时间所产生的影响，因此用户总收益变化幅度较小。由于ROARM算法采用随机卸载的方法，并且计算资源相对充足，因此有较少的任务被卸载，所以迁移概率较小，迁移消耗的增加对用户总收益产生的影响较小，因此仿真曲线比较平滑。

4　 结 语

本文将用户的移动性用符合指数分布的驻留时间进行描述。在雾计算网络中，为了减少迁移概率的同时最大化用户的总收益，提出了一个考虑移动感知下的任务卸载和计算资源分配算法。提出的算法在考虑用户移动性的同时，能最大化用户设备的总收益。仿真结果显示，本文提出的算法与其他现有的算法相比较，能提高用户的总收益。

参考文献

[1] LIU X N， ZHANG H J， LONG K P， et al. Energy efficient user association， resource allocation and caching deployment in fog radio access networks［J］. IEEE Transactions on Vehicular Technology， 2022， 71（2）： 1846-1856. DOI： 10.1109/TVT.2021.3131720 .

[2] LIU L， CHANG Z， GUO X. Socially aware dynamic computation offloading scheme for fog computing system with energy harvesting devices［J］. IEEE Internet of Things Journal， 2018， 5（3）： 1869-1879. DOI：10.1109/JIOT.2018.2816682 .

[3] SHAH MANSOURI H， WONG V W S. Hierarchical fog-cloud computing for IoT systems： A computation offloading game［J］. IEEE Internet of Things Journal， 2018， 5（4）： 3246-3257. DOI： 10.1109/JIOT.2017.2788802 .

[4] ZHANG G W， SHEN F， YANG Y，et al. Fair task offloading among fog nodes in fog computing networks［C］// 2018 IEEE International Conference on Communications. New York： IEEE Press，2018： 1-6. DOI： 10.1109/ICC.2018.8422316 .

[5] BOZORGCHENANI A， TARCHI D， CORAZZA G E. Centralized and distributed architectures for energy and delay efficient fog network-based edge computing services［J］. IEEE Transactions on Green Communications and Networking， 2019， 3（1）： 250-263. DOI： 10.1109/TGCN.2018.2885443 .

[6] YOUSEFPOUR A， ISHIGAKI G， GOUR R， et al. On reducing IoT service delay via fog offloading ［J］. IEEE Internet of Things Journal， 2018， 5（2）： 998-1010. DOI： 10.1109/JIOT.2017.2788802 .

[7] XIONG Z H， FENG S H， WANG W B， et al. Cloud/fog computing resource management and pricing for blockchain networks ［J］. IEEE Internet of Things Journal， 2019， 6（3）： 4585-4600. DOI： 10.1109/JIOT.2018.2871706 .

[8] LIU L Q， CHANG Z， GUO X J， et al. Multiobjective optimization for computation offloading in fog computing［J］. IEEE Internet of Things Journal， 2018， 5（1）： 283-294. DOI： 10.1109/JIOT.2017.2780236 .

[9] CHITI F， FANTACCI R， PICANO B. A matching theory framework for tasks offloading in fog computing for IoT systems ［J］. IEEE Internet of Things Journal， 2018， 5（6）： 5089-5096. DOI： 10.1109/JIOT.2018.2871251 .

[10] LI G L， WU J， LI J H， et al. Service popularity-based smart resources partitioning for fog computing-enabled industrial Internet of Things ［J］. IEEE Transactions on Industrial Informatics， 2018， 14（10）： 4702-4711. DOI： 10.1109/TII.2018.2845844 .

[11] RAHMAN A， JIN J， CRICENTI A， et al. Motion and connectivity aware offloading in cloud robotics via genetic algorithm ［C］// 2017 IEEE Global Communications Conference. New York： IEEE Press，2017： 1-6. DOI：10.1109/GLOCOM.2017.8255040 .

[12] WANG C， LI Y， JIN D P. Mobility-assisted opportunistic computation offloading ［J］. IEEE Communications Letters， 2014，18（10）： 1779-1782. DOI： 10.1109/LCOMM.2014.2347272 .

[13] SHI Y， CHEN S Z， XU X. MAGA： A mobility-aware computation offloading decision for distributed mobile cloud computing［J］. IEEE Internet of Things Journal， 2018， 5（1）： 164-174. DOI： 10.1109/JIOT.2017.2776252 .

[14] 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（4）：182412-182421. DOI：10.1109/ACCESS.2020.3028942 .

[15] 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 .

[16] 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 .

[17] 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 .

[18] WEN Y G， ZHANG W W， LUO H Y. Energy-optimal mobile application execution： Taming resource-poor mobile devices with cloud clones［C］// 2012 IEEE INFOCOM. Orlando： IEEE Press， 2012： 1-6. DOI： 10.1109/INFCOM.2012.6195685 .

[19] 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 .

基金资助

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

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

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

2022年度沈阳市高校“双服务”重点项目(202201016)

2022年度中国刑事警察学院重大培育项目(D2022004)

辽宁省教育科学“十四五”规划2021年度阶段性成果(JD21DB535)

2022年度辽宁省应用基础研究计划项目(2022JH21013)