0 概述

随着移动通信技术和互联网的快速发展，虚拟现实、增强现实和人脸识别等具有计算密集、时延敏感等特性的应用不断出现^[1-2]。然而，由于终端设备在计算能力和电池寿命方面存在一定的局限性，导致它们难以支持上述应用^[3]。受软件定义网络（Software Defined Network，SDN）和网络功能虚拟化（Network Function Virtualization，NFV）的驱动，移动云计算（Mobile Cloud Computing，MCC）技术应运而生，其允许用户将计算密集型任务卸载到资源丰富的远端云服务器执行，以缓解终端设备资源受限与高性能任务处理需求之间的冲突^[4-5]。但是，在实际情况中，云服务器一般距离用户较远，云计算方案难以适用一些时延敏感的应用。为了解决这一问题，移动边缘计算（Mobile Edge Computing，MEC）技术被提出^[6]，它能够在靠近移动设备的网络边缘提供云资源，不仅可以满足时延敏感型应用的QoS需求，而且还在一定程度上降低了计算密集型应用所带来的网络负载和设备终端能耗^[7-8]。

目前，已有学者针对MEC任务卸载与资源分配问题进行研究。文献[9]考虑信道状态和任务到达的随机性，研究MEC系统中能量效率与时延的权衡问题。文献[10]针对正交频分多址的移动边缘网络，设计一种基于计算能效的资源分配方案。文献[11]以最小化移动设备和MEC服务器的平均总功耗为目标，提出一种在线无线资源和计算资源管理算法。文献[12]引入能量和时延加权因子，提出一种能量感知的卸载方案。虽然上述研究在一定程度上降低了任务时延和系统能耗，但考虑的均是单MEC服务器场景下的资源分配问题，存在一定的局限性。在多服务器的MEC系统场景下，文献[13]提出一种以最小化服务成本、最大化服务终端数量为目标的任务卸载和资源分配算法，文献[14]以最小化设备能耗和任务时延为目标，提出一种两层博弈论的贪婪卸载方案，文献[15]研究任务卸载和资源分配的联合优化问题，以降低设备能耗为目标，分别设计基于分支界定算法的最优方案以及基于组合算法的次优方案，这些方案更适用于实际边缘计算网络场景。此外，文献[16-17]将MEC与能量收集技术相结合，研究卸载策略与资源分配问题。然而，上述基于平均值设计的MEC系统难以满足低时延、高可靠的业务需求。文献[18]虽然保证了用户低时延、高可靠的需求，但是其忽略了对MEC服务器计算资源的优化，从而提高了执行任务所消耗的功率成本并最终影响MEC的系统收益。

考虑到任务到达的随机性，本文建立一种任务队列动态调度模型。为了满足用户对时延和可靠性的需求，对任务队列施加概率约束并建立最大化MEC系统平均收益的资源优化模型。在此基础上，利用马尔科夫不等式^[19]将概率混合优化问题转化为非概率优化问题，通过Lyapunov优化理论将不同时隙下的耦合优化问题转化为3个子问题并分别进行求解，以得到最优任务卸载与资源分配方案。

1 系统模型与问题建模 1.1 系统场景

MEC系统场景如图 1所示，其由$ M $个用户、$ S $个基站和多个MEC服务器组成。其中，每个用户通过无线链路关联到距离其最近的基站，每个基站通过有线链路连接一个配备多CPU内核的MEC服务器^{[11, 18]}。为了方便分析，本文假定用户计算任务由一个MEC服务器处理，不考虑任务在服务器之间转发。本文将网络运行时间划分为若干个时隙，用$ \mathit{\Gamma}=\left\{\mathrm{0, 1}, \cdots \right\} $表示网络运行的时隙集合，其中，定义每个时隙$ t $的时间长度为$ \tau $。考虑到任务到达的随机性，本文建立两级任务队列模型，即用户任务队列模型和MEC服务器任务队列模型，以对计算任务的状态进行刻画。

1.2 用户任务队列模型

假设每个用户都有一个队列缓冲区，存储到达但未处理的计算任务。在每个时隙内，用户计算任务的到达过程是独立同分布的，且平均到达率为$ {\lambda }_{i}={ E}\left[{A}_{i}\left(t\right)\right] $。同时，对于每个计算任务都可以选择在用户本地或者卸载到MEC服务器进行处理。因此，本文定义时隙$ t $时用户任务队列长度向量为$ \boldsymbol{Q}\left(t\right)=\left[{Q}_{1}\left(t\right), {Q}_{2}\left(t\right), \cdots , {Q}_{M}\left(t\right)\right] $，$ {Q}_{i}\left(t\right) $的更新过程为：

$ {Q}_{i}(t+1)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{Q}_{i}\left(t\right)+{A}_{i}\left(t\right)-{D}_{{\mathit \Sigma} , i}\left(t\right), 0\right\} $

(1)

其中，$ {D}_{{\mathit \Sigma} , i}\left(t\right) $为$ t $时刻用户$ i $所处理的总计算任务量，其具体表达式为：

$ {D}_{{\mathit \Sigma} , i}\left(t\right)=\frac{\tau {f}_{i}\left(t\right)}{{L}_{i}}+\sum \limits_{j\in S}R{}_{ij}(t) $

(2)

式（2）等号右侧的第一部分为用户本地处理的计算任务量，$ {f}_{i}\left(t\right) $是用户$ i $处理计算任务所分配的计算资源，即CPU周期频率，$ {L}_{i} $表示执行每比特计算任务所需的CPU周期；第二部分为卸载到MEC服务器处理的计算任务量，$ R{}_{ij}(t) $是$ t $时刻用户$ i $卸载计算任务到MEC服务器$ j $时的传输速率，其表达式为：

$ R{}_{ij}(t)={\xi }_{ij}(t)W\tau \mathrm{l}\mathrm{b}\left(1+\frac{{p}_{ij}\left(t\right){h}_{ij}\left(t\right)}{{\xi }_{ij}\left(t\right){N}_{0}W}\right) $

(3)

其中，$ W $为MEC服务器的带宽，$ {\xi }_{ij}\left(t\right) $表示MEC服务器$ j $为用户$ i $分配的带宽比例，$ {p}_{ij}\left(t\right) $和$ {h}_{ij}\left(t\right) $分别表示从用户$ i $到MEC服务器$ j $的传输功率和信道增益，$ {N}_{0} $为高斯白噪声的功率谱密度。另外，由于每个基站都连接一个MEC服务器，因此在本文中$ j\in S $同时表示MEC服务器。

任务请求具有动态性，可能出现任务队列长度超出用户缓存空间的情况，从而导致数据包的丢失。因此，为了满足低时延、高可靠的任务需求，本文对用户队列长度添加概率约束^[20]，即：

$ \underset{t\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}P\left({Q}_{i}\left(t\right)\ge {Q}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right)\le {\varepsilon }_{i} $

(4)

其中，$ {Q}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}} $表示用户$ i $的队列阈值，$ {\varepsilon }_{i} $表示用户$ i $任务队列的上溢容忍阈值，其取值远小于1。

1.3 MEC服务器任务队列模型

每个MEC服务器中有多个队列缓冲区，可以同时存储多个用户卸载但尚未由MEC服务器处理的计算任务。本文定义MEC服务器$ j $中用户$ i $的任务队列为$ {X}_{ji}\left(t\right) $，其更新过程为：

$ {X}_{ji}(t+1)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{X}_{ji}\left(t\right)+{A}_{ji}\left(t\right)-\frac{\tau {f}_{ji}\left(t\right)}{{L}_{i}}, 0\right\} $

(5)

其中，$ {A}_{ji}\left(t\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{{Q}_{i}\left(t\right)+{A}_{i}\left(t\right)-\frac{\tau {f}_{i}\left(t\right)}{{L}_{i}}, R{}_{ij}(t)\right\} $表示$ t $时刻用户$ i $卸载到MEC服务器$ j $的计算任务，$ {f}_{ji}\left(t\right) $表示MEC服务器$ j $分配给用户$ i $的计算资源。由于部署MEC服务器的目的是为用户提供更强的计算能力，因此本文将每个服务器的CPU核至多分配给一个用户以执行计算任务。

本文同样对MEC服务器任务队列长度添加概率约束，即：

$ \underset{t\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}P\left({X}_{ji}\left(t\right)\ge {X}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right) <{\varepsilon }_{ji} $

(6)

其中，$ {X}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}} $表示MEC服务器$ j $中用户$ i $的任务队列阈值，$ {\varepsilon }_{ji} $表示MEC服务器$ j $中用户$ i $的任务队列上溢容忍阈值，其取值远小于1。

1.4 问题建模 1.4.1 时间平均吞吐量

由式（1）可得$ t $时刻用户$ i $所处理的计算任务量为$ {D}_{{\mathit \Sigma} , i}\left(t\right) $，将其记为$ t $时刻系统用户$ i $的吞吐量，相应的用户$ i $时间平均吞吐量定义为$ {D}_{i} $，其表达式为：

$ {D}_{i}=\underset{T\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{1}{T}\sum \limits_{t=0}^{T-1}E\left\{{D}_{{\mathit \Sigma} , i}\left(t\right)\right\} $

(7)

进一步定义MEC系统的时间平均收入为：

$ \stackrel{-}{r}=\sum\limits _{i\in M}{\alpha }_{i}{D}_{i} $

(8)

其中，$ {\alpha }_{i} $表示处理用户$ i $任务的单位收入。

1.4.2 时间平均功耗

由式（2）、式（3）可知，用户$ i $在$ t $时刻的处理功耗和传输功耗分别为：

$ {p}_{i, \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}\left(t\right)=\kappa {\left[{f}_{i}\left(t\right)\right]}^{3} $

(9)

$ {p}_{i, \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}}\left(t\right)=\sum\limits_{j\in S}{p}_{ij}\left(t\right) $

(10)

其中，$ \kappa $是与芯片结构相关的有效系数^[17]。用户$ i $的时间平均功耗可表示为：

$ {p}_{i}=\underset{T\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{1}{T}\sum\limits_{t=0}^{T-1}\left\{{p}_{i, \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}\left(t\right)+{p}_{i, \mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}}\left(t\right)\right\} $

(11)

由式（5）可知，MEC服务器$ j $在$ t $时刻的处理功耗为：

$ {p}_{j}\left(t\right)=\sum\limits_{i\in M}\kappa {\left[{f}_{ji}\left(t\right)\right]}^{3} $

(12)

则MEC服务器$ j $的时间平均功耗可表示为：

$ {p}_{j}=\underset{T\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{1}{T}\sum\limits_{t=0}^{T-1}E\left\{{p}_{j}\left(t\right)\right\} $

(13)

基于上述用户和MEC服务器的时间平均功耗，可定义用户和MEC服务器的时间平均功率消耗成本分别为：

$ {\stackrel{-}{c}}_{u}=\beta \sum\limits_{i\in M}{p}_{i} $

(14)

$ {\stackrel{-}{c}}_{m}=\gamma \sum\limits_{j\in S}{p}_{j} $

(15)

其中，$ \beta $和$ \gamma $分别表示用户和MEC服务器的功率单位成本。

1.4.3 优化模型

本文设计一种联合功率、带宽以及计算资源的分配算法，以在满足低时延、高可靠业务需求的同时最大化MEC系统的时间平均收益。时间平均收益指系统中所有用户任务的时间平均收入与用户和MEC服务器时间功率消耗成本的差值，其优化模型如下：

$ \begin{array}{l}\mathrm{P}1:\underset{p, f, \xi }{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{ }（\stackrel{-}{r}-{\stackrel{-}{c}}_{u}-{\stackrel{-}{c}}_{m}）\\ \mathrm{s}.\mathrm{t}.\;\;\;\mathrm{C}1:0\le {f}_{i}\left(t\right)\le {f}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\in M\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}2:\sum\limits_{j\in S}{p}_{ij}\left(t\right)\le {p}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\in M\end{array}\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}3:{p}_{ij}\left(t\right)\ge 0, \forall i\in M\end{array}, \forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}4:\sum\limits_{i\in M}{\xi }_{ij}\left(t\right)\le 1, \end{array}\forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}5:0 <{\xi }_{ij}\left(t\right)\le 1, \end{array}\forall i\in M, \forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}6:\sum\limits_{i\in M}\left\{{f}_{ji}\left(t\right)>0\right\}\le N, \end{array}\forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}7:0\le {f}_{ji}\left(t\right)\le {f}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \end{array}\forall i\in M, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}8:\end{array}\underset{t\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}P\left({Q}_{i}\left(t\right)\ge {Q}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right)\le {\varepsilon }_{i}, \forall i\in M\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}9:\underset{t\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}P\left({X}_{ji}\left(t\right)\ge {X}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right)<{\varepsilon }_{ji}\end{array}, \forall i\in M, \forall j\in S\end{array} $

(16)

约束条件说明：$ \mathrm{C}1 $表示为用户分配的计算资源不能超过总的计算资源$ {f}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}} $；$ \mathrm{C}2 $和$ \mathrm{C}3 $表示用户的传输功率约束；$ \mathrm{C}4 $和$ \mathrm{C}5 $表示MEC服务器$ j $分配给用户$ i $的带宽比例约束；$ \mathrm{C}6 $表示在MEC服务器中并行处理用户任务队列的数量不能超过CPU总核数$ N $；$ \mathrm{C}7 $表示MEC服务器$ j $分配给用户$ i $的计算资源不能超过单个CPU核的最大资源值$ {f}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}} $；$ \mathrm{C}8 $和$ \mathrm{C}9 $分别表示用户任务队列上溢概率和MEC服务器任务队列上溢概率。

2 资源优化问题转化 2.1 概率混合问题转化

由上述优化模型可得问题$ \mathrm{P}1 $是一个概率混合优化问题，其分析处理具有一定难度。因此，本文引入马尔科夫不等式，对概率约束进行转化^[20]。

定义1 （马尔科夫不等式）  若$ X $是一个非负随机变量，$ a>0 $，则$ \left[P\right(X\ge a)\le \mathrm{{\rm E}}X\mathrm{ }]/a $。

利用定义1可将约束$ \mathrm{C}8 $和$ \mathrm{C}9 $转化为：

$ \mathrm{C}{8}^{\text{'}}:\overline{{Q}_{i}}=\underset{T\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{1}{T}\sum\limits_{t=1}^{T}E\left\{{Q}_{i}\left(t\right)\right\}\le {Q}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\cdot {\varepsilon }_{i} $

(17)

$ \mathrm{C}{9}^{\text{'}}:\overline{{X}_{ji}}=\underset{T\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\frac{1}{T}\sum\limits_{t=1}^{T}E\left\{{X}_{ji}\left(t\right)\right\}\le {Q}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}\cdot {\varepsilon }_{ji} $

(18)

其中，$ \mathrm{C}{8}^{\text{'}} $和$ \mathrm{C}{9}^{\text{'}} $为连续时隙的平均约束，而$ \mathrm{C}1\sim\mathrm{C}7 $是单时隙的瞬时约束。传统方法难以处理不同时隙下的耦合问题，因此，本文利用Lyapunov优化理论设计一种基于单时隙状态的资源分配方案。

2.2 基于Lyapunov的优化理论分析

本文引入虚拟队列$ {Y}_{i}\left(t\right) $和$ {Z}_{ji}\left(t\right) $对时间平均约束进行转化，虚拟队列更新方程分别为：

$ {Y}_{i}(t+1)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{Y}_{i}\left(t\right)+{Q}_{i}(t+1)-{Q}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\cdot {\varepsilon }_{i}, 0\right\} $

(19)

$ {Z}_{ji}(t+1)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{{Z}_{ji}\left(t\right)+{X}_{ji}(t+1)-{X}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}\cdot {\varepsilon }_{ji}, 0\right\} $

(20)

在$ t $时刻系统的队列状态向量可表示为$ \mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)=\left[{Y}_{i}\right(t), {Z}_{ji}(t\left)\right] $，进而定义Lyapunov函数为：

$ L\left(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right)=\frac{1}{2}\left[\sum\limits_{i=1}^{M}{\left({Y}_{i}\left(t\right)\right)}^{2}+\sum\limits_{j=1}^{S}\sum\limits_{i=1}^{M}{\left({Z}_{ji}\left(t\right)\right)}^{2}\right] $

(21)

式（21）表征了系统中的队列拥塞程度，函数值越大，队列越长，相应的用户任务处理等待时间就越长。因此，为了缩短用户的等待时延，保持系统的稳定性，本文定义单时隙Lyapunov偏移为：

$ \mathrm{\Delta }\left(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right)=E\left\{L\left(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}(t+1)\right)-L\left(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right)\left|\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\right(t)\right\} $

(22)

在优化理论中，Lyapunov偏移通常用来进行资源分配策略选择，为其添加一个加权代价函数，从而得到Lyapunov偏移加罚。本文的Lyapunov偏移加罚定义为单时隙Lyapunov偏移与该时隙MEC系统时间平均收益期望的加权差，即：

$ \begin{array}{l}\mathrm{\Delta }\left(\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right)-VE\left\{\stackrel{-}{r}-{\stackrel{-}{c}}_{u}-{\stackrel{-}{c}}_{m}\left|\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right.\right\}\le \\ \zeta -E\left\{\sum\limits_{i\in M}\left[{Q}_{i}\left(t\right)+{Y}_{i}\left(t\right)\right]{D}_{\mathrm{\Sigma }, i}\left(t\right)\left|\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right.\right\}+\\ E\left\{\sum\limits_{i\in M}\sum\limits_{j\in S}\left\{\left[\left({X}_{ji}\left(t\right)+{Z}_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]-\right.\right.\\ \left.\left.\left[\left({X}_{ji}\left(t\right)+{Z}_{ji}\left(t\right)\right){D}_{ji}\left(t\right)\right]\right\}\left|\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right.\right\}-\\ VE\left\{\stackrel{-}{r}-{\stackrel{-}{c}}_{u}-{\stackrel{-}{c}}_{m}\left|\mathit{\boldsymbol{ \boldsymbol{\varTheta} }}\left(t\right)\right.\right\}\end{array} $

(23)

其中，$ V $为权衡偏移函数与代价函数的非负控制参数，$ \zeta $为一个有限正常数，$ {D}_{ji}\left(t\right) $大小为$ \tau {f}_{ji}\left(t\right)/{L}_{i} $。

进一步将问题$ \mathrm{P}1 $转化为最小化Lyapunov偏移加罚上界的问题，即最小化式（23）的右侧，得到：

$ \begin{array}{l}\mathrm{P}2:\mathrm{ }\underset{p, f, \xi }{\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{ }\sum\limits_{i=1}^{M}\left[V\beta \kappa {\left[{f}_{i}\left(t\right)\right]}^{3}-{\mathit \Phi }_{i}\left(t\right)\frac{\tau {f}_{i}\left(t\right)}{{L}_{i}}\right]+\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\sum\limits_{i=1}^{M}\sum\limits_{j=1}^{S}\left[V\beta {p}_{ij}\left(t\right)-\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right)R{}_{ij}(t)\right]+\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\sum\limits_{j=1}^{S}\sum\limits_{i=1}^{M}\left[V\gamma \kappa {\left[{f}_{ji}\left(t\right)\right]}^{3}-{\mathit \Psi }_{ji}\left(t\right)\frac{\tau {f}_{ji}\left(t\right)}{{L}_{i}}\right]\\ \mathrm{s}.\mathrm{t}.\;\;\;\;\mathrm{C}1\sim\mathrm{C}7\end{array} $

(24)

在优化问题$ \mathrm{P}2 $中，$ {\mathit \Phi }_{i}\left(t\right)=V{\alpha }_{i}+{Q}_{i}\left(t\right)+{Y}_{i}\left(t\right) $，$ {\mathit \Psi }_{ji}\left(t\right)= $ $ {X}_{ji}\left(t\right)+{Z}_{ji}\left(t\right) $。

3 计算资源与无线资源联合分配方案

由文献[11, 21]可知，问题$ \mathrm{P}2 $可以转化成3个子问题，即用户本地计算资源分配问题$ \mathrm{P}2.1 $、功率与带宽资源分配优化问题$ \mathrm{P}2.2 $以及MEC服务器的计算资源分配问题$ \mathrm{P}2.3 $。

3.1 用户本地计算资源分配问题

根据式（24）可得用户本地计算资源分配问题如下：

$ \begin{array}{l}\mathrm{P}2.1:\mathrm{ }\underset{\boldsymbol{f}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{i=1}^{M}\left\{V\beta \kappa {\left[{f}_{i}\left(t\right)\right]}^{3}-{\mathit \Phi }_{i}\left(t\right)\frac{\tau {f}_{i}\left(t\right)}{{L}_{i}}\right\}\\ \mathrm{s}.\mathrm{t}.\mathrm{ }\;\;\;\;\mathrm{C}1:0\le {f}_{i}\left(t\right)\le {f}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\in M\end{array} $

(25)

从式（25）可以看出，问题$ \mathrm{P}2.1 $是一个凸优化问题，而且其目标函数和约束条件都可以对$ {f}_{i}\left(t\right) $进行分解，因此，可对每个$ {f}_{i}\left(t\right) $进行优化。本地计算资源最优解$ {f}_{i}^{\mathrm{*}}\left(t\right) $可表示为：

$ {f}_{i}^{\mathrm{*}}\left(t\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\sqrt{\frac{{\mathit \Phi }_{i}\left(t\right)\tau }{3V\beta \kappa {L}_{i}}}, {f}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right\} $

(26)

3.2 功率与带宽资源分配优化问题

与无线资源相关的系统决策包括任务卸载的发射功率分配和带宽分配，因为两者为常数，所以难以适应时变的系统状态^[11]，因此，本文对问题$ \mathrm{P}2 $中的带宽约束$ \mathrm{C}5 $进行修改，如下：

$ \mathrm{C}{5}^{\text{'}}:\delta <{\xi }_{ij}\left(t\right)\le 1, \forall i\in M, \forall j\in S $

(27)

其中，$ \delta $为带宽分配的最小比例，其取值范围为$ \left(0, 1/{M}_{j}\right) $，$ {M}_{j} $表示接入基站$ j $的用户数量。根据式（24）、式（27）可将P2.2优化问题转化为：

$ \begin{array}{l}\mathrm{P}2.2\mathrm{ }:\mathrm{ }\mathrm{ }\underset{p, \xi }{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{i=1}^{M}\sum\limits_{j=1}^{S}\left[V\beta {p}_{ij}\left(t\right)-\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]\\ \mathrm{s}.\mathrm{t}.\;\;\;\;\mathrm{C}2:\sum\limits_{j\in S}{p}_{ij}\left(t\right)\le {p}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\in M\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}3:{p}_{ij}\left(t\right)\ge 0, \forall i\in M\end{array}, \forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}4:\sum\limits_{i\in M}{\xi }_{ij}\left(t\right)\le 1, \end{array}\forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}{5}^{\text{'}}:\delta <{\xi }_{ij}\left(t\right)\le 1, \end{array}\forall i\in M, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\end{array} $

(28)

当$ {\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\le 0 $时，问题$ \mathrm{P}2.2 $的目标函数随$ {p}_{ij}\left(t\right) $的增大而增大。当$ {p}_{ij}\left(t\right)=0 $时，问题$ \mathrm{P}2.2 $取最小值。令$ {M}^{\text{'}}\left(t\right) $表示$ {\mathit \Phi }_{i}\left(t\right)\le {\mathit \Psi }_{ji}\left(t\right) $的用户集合，最优功率为$ {p}_{ij}^{\mathrm{*}}\left(t\right)=0 $，最优带宽比例为$ {\xi }_{ij}^{\mathrm{*}}\left(t\right)=\delta $。

当$ {\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)>0 $时，优化问题变成一个凸优化问题。令$ \tilde{M}\left(t\right) $表示$ {\mathit \Phi }_{i}\left(t\right)>{\mathit \Psi }_{ji}\left(t\right) $的用户集合，因此，子问题$ \mathrm{P}2.2 $可简化为：

$ \begin{array}{l}\mathrm{P}2.{2}^{\text{'}}:\mathrm{ }\mathrm{ }\underset{p, \xi }{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{i\in \tilde{M}\left(t\right)}\left[V\beta {p}_{ij}\left(t\right)\mathrm{ }-\left({\mathit \Phi }_{i}\left(t\right)\mathrm{ }-{\mathit \Psi }_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]\\ \mathrm{s}.\mathrm{t}.\;\;\;\;\mathrm{C}2:{p}_{ij}\left(t\right)\le {p}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\in \tilde{M}\left(t\right), \forall j\in S\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\begin{array}{cc}\mathrm{C}3:{p}_{ij}\left(t\right)\ge 0, \forall i\in \tilde{M}\left(t\right), \forall j\in S, & \end{array}\\ \begin{array}{cc}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{C}{4}^{\text{'}}:\sum\limits_{i\in \tilde{M}\left(t\right)}{\xi }_{ij}\left(t\right)\le 1-{M}^{\text{'}}\left(t\right)\delta , \forall j\in S& \end{array}\\ \begin{array}{cc}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{C}{5}^{\text{'}}:{\xi }_{ij}\left(t\right)>\delta , \forall i\in \tilde{M}\left(t\right), \forall j\in S& \end{array}\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\end{array} $

(29)

子问题$ \mathrm{P}2.{2}^{\text{'}} $的目标函数中含有2个变量，若利用一般的凸优化方法，算法有较高的复杂性。因此，本文将子问题$ \mathrm{P}2.{2}^{\text{'}} $解耦为功率分配与带宽分配2个子问题，通过多次迭代得到最优资源分配方案。

3.2.1 功率分配子问题

给定带宽分配比例，用户的功率资源分配问题可表示为：

$ \begin{array}{l}\mathrm{P}2.{2}^{\text{'}}.1:\mathrm{ }\mathrm{ }\underset{p}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{i\in \mathrm{ }\tilde{M}\left(t\right)}\left[V\beta {p}_{ij}\left(t\right)\mathrm{ }-\left({\mathit \Phi }_{i}\left(t\right)\mathrm{ }-{\mathit \Psi }_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]\\ \mathrm{s}.\mathrm{t}.\;\;\;\;\mathrm{C}2:{p}_{ij}\left(t\right)\mathrm{ }\le \mathrm{ }{p}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \forall i\mathrm{ }\in \mathrm{ }\tilde{M}\left(t\right), \forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}3:{p}_{ij}\left(t\right)\mathrm{ }\ge \mathrm{ }0, \forall i\mathrm{ }\in \mathrm{ }\tilde{M}\left(t\right)\end{array}, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\end{array} $

(30)

类似于问题$ \mathrm{P}2.1 $，本文对每个用户的功率进行优化，得到：

$ \begin{array}{l}{p}_{ij}^{\mathrm{*}}\left(t\right)=\mathrm{m}\mathrm{i}\mathrm{n}\\ \left\{\mathrm{m}\mathrm{a}\mathrm{x}\left\{\frac{\left[{\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right]\tau {\xi }_{ij}\left(t\right)W}{V\beta \mathrm{l}\mathrm{n}\mathrm{ }2}-\frac{{\xi }_{ij}\left(t\right){N}_{0}W}{{h}_{ij}\left(t\right)}, 0\right\}, {p}_{i}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right\}, \\ i\in \tilde{M}\left(t\right)\end{array} $

(31)

3.2.2 带宽分配子问题

给定功率分配方案，用户的带宽资源分配问题可表示为：

$ \begin{array}{l}\mathrm{P}2.{2}^{\text{'}}.2:\mathrm{ }\underset{\xi }{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{i\in \tilde{M}\left(t\right)}\left[-\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]\\ \mathrm{s}.\mathrm{t}.\;\;\;\mathrm{C}{4}^{\text{'}}:\sum\limits_{i\in \tilde{M}\left(t\right)}{\xi }_{ij}\left(t\right)\le 1-{M}^{\text{'}}\left(t\right)\delta , \forall j\in S\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}{5}^{\text{'}}:{\xi }_{ij}\left(t\right)>\delta , \end{array}\forall i\in \tilde{M}\left(t\right)\mathrm{ }, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\end{array} $

(32)

子问题$ \mathrm{P}2.{2}^{\text{'}}.2 $是一个凸优化问题，联合目标函数和约束条件可得到对应的拉格朗日函数，表示为：

$ \begin{array}{l}L(\xi , \mu )=\sum\limits_{i\in \tilde{M}\left(t\right)}\left[-\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right){R}_{ij}\left(t\right)\right]+\\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mu \left(\sum\limits_{i\in \tilde{M}\left(t\right)}{\xi }_{ij}\left(t\right)-(1-{M}^{\text{'}}(t\left)\delta \right)\right)\end{array} $

(33)

其中，$ \mu $为约束条件对应的非负拉格朗日乘子。进一步，通过$ L(\xi , \mu ) $对$ \xi $求偏导数得到：

$ -\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right)\frac{\mathrm{d}{R}_{ij}\left(t\right)}{\mathrm{d}{\xi }_{ij}\left(t\right)}+\mu =0 $

(34)

定义$ {G}_{i}\left(\mu \right) $为式（34）的解，因此，可以利用KKT条件得出最优解，其中，最优带宽分配$ {\xi }^{\mathrm{*}} $和最优拉格朗日乘子$ {\mu }^{\mathrm{*}} $满足：

$ \left\{\begin{array}{l}\sum\limits_{i\in \tilde{M}\left(t\right)}{\xi }_{ij}^{\mathrm{*}}\left(t\right)=\left(1-{M}^{\text{'}}\left(t\right)\delta \right)\\ {\xi }_{ij}^{\mathrm{*}}\left(t\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\delta , {G}_{i}\left({\mu }^{\mathrm{*}}\right)\right\}\\ {\mu }^{\mathrm{*}}\ge 0\\ \mu \left[\sum\limits_{i\in \tilde{M}\left(t\right)}{\xi }_{ij}^{\mathrm{*}}\left(t\right)-\left(1-{M}^{\text{'}}\left(t\right)\delta \right)\right]=0\end{array}\right. $

(35)

由式（35）可知，$ \frac{\mathrm{d}{R}_{ij}\left(t\right)}{\mathrm{d}{\xi }_{ij}\left(t\right)} $随$ {\xi }_{ij}\left(t\right) $增加而减小，因此，根据$ {\xi }_{ij}\left(t\right) $可以得到$ \mu $的取值范围$ \left[{\mu }_{\mathrm{m}\mathrm{i}\mathrm{n}}, {\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $，即：

$ {\mu }_{\mathrm{m}\mathrm{i}\mathrm{n}}=\underset{i\in \tilde{M}\left(t\right)}{\mathrm{m}\mathrm{a}\mathrm{x}}\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right)\frac{\mathrm{d}{R}_{ij}\left(t\right)}{\mathrm{d}{\xi }_{ij}\left(t\right)}\left|{}_{{\xi }_{ij}\left(t\right)=1-{M}^{\text{'}}\left(t\right)\delta }\right. $

(36)

$ {\mu }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\underset{i\in \tilde{M}\left(t\right)}{\mathrm{m}\mathrm{a}\mathrm{x}}\left({\mathit \Phi }_{i}\left(t\right)-{\mathit \Psi }_{ji}\left(t\right)\right)\frac{\mathrm{d}{R}_{ij}\left(t\right)}{\mathrm{d}{\xi }_{ij}\left(t\right)}\left|{}_{{\xi }_{ij}\left(t\right)=\delta }\right. $

(37)

进一步利用二分搜索法得到$ \mu $的最优解并代入式（35）中，从而得到带宽分配方案。

3.3 MEC服务器计算资源分配问题

根据式（24）可以得到MEC服务器的计算资源分配问题，如下：

$ \begin{array}{l}\mathrm{P}2.3:\mathrm{ }\underset{f}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum\limits_{j=1}^{S}\sum\limits_{i=1}^{M}\left\{V\gamma \kappa {\left[{f}_{ji}\left(t\right)\right]}^{3}-{\mathit \Psi }_{ji}\left(t\right)\frac{\tau {f}_{ji}\left(t\right)}{{L}_{i}}\right\}\\ \mathrm{s}.\mathrm{t}.\;\;\;\mathrm{C}6:\sum\limits_{i\in M}\left\{{f}_{ji}\left(t\right)>0\right\}\le N, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\\ \begin{array}{cc}& \mathrm{ }\mathrm{C}7:0\le {f}_{ji}\left(t\right)\le {f}_{ji}^{\mathrm{m}\mathrm{a}\mathrm{x}}, \end{array}\forall i\in M, \forall j\in S\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\mathrm{ }\end{array} $

(38)

由于约束条件$ \mathrm{C}6 $是一个离散约束，导致P2.3问题是一个非凸优化问题，但是，当忽略约束条件$ \mathrm{C}6 $时，该问题是一个线性问题且目标函数和约束条件都可以对$ {f}_{ji}\left(t\right) $进行分解。因此，本文首先对$ {f}_{ji}\left(t\right) $进行优化，得到初始计算资源分配方案，然后将得到的资源分配方案代入约束$ \mathrm{C}6 $中，判断是否满足约束，若满足即得到最终解；否则，在初始解中依次选择对目标函数贡献最小的用户，收回计算资源，即将$ {f}_{ji}\left(t\right) $设置为0，直到满足约束$ \mathrm{C}6 $。MEC服务器计算资源分配算法描述如算法1所示。

算法1   MEC服务器计算资源分配算法

1.初始化：MEC服务器CPU核数$ \mathrm{N} $，每个CPU核的计算资源状态

2.在时隙$ \mathrm{t} $观察虚拟队列$ {\mathrm{Y}}_{\mathrm{i}}\left(\mathrm{t}\right) $和$ {\mathrm{Z}}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right) $的状态

3.for $ \mathrm{j}\in \mathrm{S} $ do

4.for $ \mathrm{i}\in \mathrm{M} $ do

5.$ {\mathrm{f}}_{\mathrm{j}\mathrm{i}}^{\mathrm{*}}\left(\mathrm{t}\right)=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\sqrt{\frac{{\mathrm{ \Psi }}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right)\mathrm{\tau }}{3\mathrm{V}\mathrm{\gamma }\mathrm{\kappa }{\mathrm{L}}_{\mathrm{i}}}}, {\mathrm{f}}_{\mathrm{j}\mathrm{i}}^{\mathrm{m}\mathrm{a}\mathrm{x}}\right\}, \forall \mathrm{i}\in \mathrm{M}, \forall \mathrm{j}\in \mathrm{S} $

6.更新$ \mathrm{n}=\sum\limits_{\mathrm{i}\in {\mathrm{U}}_{\mathrm{j}}}\left\{{\mathrm{f}}_{\mathrm{j}\mathrm{i}}^{\mathrm{*}}\left(\mathrm{t}\right)>0\right\}, \forall \mathrm{j}\in \mathrm{S} $

7.end for

8.end for

9.if $ \sum\limits_{\mathrm{i}\in \mathrm{M}}\left\{{\mathrm{f}}_{\mathrm{j}\mathrm{i}}^{\mathrm{*}}\left(\mathrm{t}\right)>0\right\}\le \mathrm{N}, \forall \mathrm{j}\in \mathrm{S} $ then

10.得到MEC服务器计算资源分配的最优解$ {\mathrm{f}}^{\mathrm{*}}\left(\mathrm{t}\right) $

11.else

12.while $ \mathrm{n}>\mathrm{N} $ do

13.$ {\mathrm{i}}^{\mathrm{\text{'}}}=\underset{\mathrm{i}\in {\mathrm{U}}_{\mathrm{j}}\left(\mathrm{t}\right)}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}\left\{\mathrm{V}\mathrm{\gamma }\mathrm{\kappa }{\left[{\mathrm{f}}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right)\right]}^{3}-{\mathrm{ \Psi }}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right)\mathrm{\tau }{\mathrm{f}}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right)/{\mathrm{L}}_{\mathrm{i}}\right\} $

14.$ {\mathrm{f}}_{\mathrm{j}{\mathrm{i}}^{\mathrm{\text{'}}}}\left(\mathrm{t}\right)=0 $，更新$ \mathrm{n}\leftarrow \mathrm{n}-1 $和$ {\mathrm{U}}_{\mathrm{j}}\left(\mathrm{t}\right)={\mathrm{U}}_{\mathrm{j}}\left(\mathrm{t}\right)\backslash {\mathrm{i}}^{\mathrm{\text{'}}} $

15.end while

16.得到MEC服务器计算资源分配方案

17.end if

3.4 本文算法描述

结合3.1节~3.3节的分析，基于Lyapunov的任务卸载与资源分配算法描述如算法2所示。该算法是一个2层迭代算法：外层循环是移动边缘计算系统内的用户队列、MEC服务器队列以及虚拟队列的更新；内层循环是对任务卸载与资源分配的3个子问题求解。

算法2  基于Lyapunov的任务卸载与资源分配算法

1.初始化：

1）用户任务队列$ {\mathrm{Q}}_{\mathrm{i}}\left(\mathrm{t}\right) $，MEC服务器任务队列$ {\mathrm{X}}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right) $，虚拟队列$ {\mathrm{Y}}_{\mathrm{i}}\left(\mathrm{t}\right) $和$ {\mathrm{Z}}_{\mathrm{j}\mathrm{i}}\left(\mathrm{t}\right) $

2）时间因子$ \mathrm{T} $，惩罚因子$ \mathrm{V} $，队列上溢概率$ {\mathrm{\varepsilon }}_{\mathrm{i}} $和$ {\mathrm{\varepsilon }}_{\mathrm{j}\mathrm{i}} $，终止条件$ \mathrm{\eta } $

2.for $ \mathrm{t}=\mathrm{1, 2}, \cdots , \mathrm{T} $ do

3.根据式（26）得到用户本地计算资源分配方案

4.while $ \left|{\mathrm{P}}^{\mathrm{k}+1}\left(\mathrm{t}\right)-{\mathrm{P}}^{\mathrm{k}}\left(\mathrm{t}\right)\right|\ge \mathrm{\eta } $ do

5.根据式（31）得到功率分配方案

6.基于功率分配方案，利用二分搜索法得到带宽分配方案进而更新$ {\mathrm{\xi }}_{\mathrm{i}\mathrm{j}}^{\mathrm{k}+1}\left(\mathrm{t}\right) $

7.end while

8.执行算法1得到MEC服务器计算资源分配方案

9.输出当前时隙的资源调度方案$ {\mathrm{p}}^{\mathrm{*}} $、$ {\mathrm{\xi }}^{\mathrm{*}} $和$ {\mathrm{f}}^{\mathrm{*}} $

10.end for

4 仿真结果与分析

为了验证本文所提算法的有效性，在一个$ 400\mathrm{ }\mathrm{m}\times 400\mathrm{ }\mathrm{m} $的区域内均匀部署4个基站和$ N $个用户，其中，每个基站都配备一个CPU核数为8的MEC服务器。将本文算法与基于Lyapunov优化的在线联合任务卸载与资源分配（OJ-TORA）算法^[13]、基于时延与可靠性感知的任务卸载与资源分配（LRA-TORA）算法^[18]以及任务全部本地执行（Non-MEC）算法和任务全部卸载到MEC服务器执行（Fully-MEC）算法2个基线算法进行比较。参考文献[22]，本文的路径损耗模型定义为$ h=127+30\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}d $，d的单位为km。考虑到用户所到达的任务与用户所消耗功率以及MEC所消耗功率的量级不同，因此，在文献[21]收益和成本参数的基础上对本文参数进行设置，单位任务收入为$ 1\times {10}^{-3}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}/\mathrm{b}\mathrm{i}\mathrm{t} $，单位功率成本为$ 0.2\mathrm{ }\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}/\mathrm{W} $。本文其他仿真参数设置如表 1所示。

图 2所示为用户数为40时MEC系统时间平均收益随控制参数V的变化情况。从图 2可以看出，时间平均收益随控制参数V的增加而逐渐增大并趋于平稳，这是因为在Lyapunov优化过程中，控制参数V越大，则系统越倾向于优化罚函数，即系统时间平均收益，该结果验证了本文所提算法的有效性。

图 3所示为不同算法下任务到达率与系统时间平均收益的关系。从图 3可以看出，系统时间平均收益随着任务到达率的增大而增大，而且对于任意任务到达率，本文算法在所有算法中收益最高。这是因为本文综合考虑功率、带宽资源以及计算资源并进行优化，能在满足用户QoS需求的同时合理地分配任务资源。

从图 4可以看出，本文算法相比其他3种算法平均端到端时延更短，说明本文算法在当前业务激增的网络环境下具有较好的时延性能。此外，Fully-MEC算法相比其他算法平均端到端时延最长，这是因为其他3种算法考虑了用户本地执行，在一定程度上缩短了时延。

图 5所示为不同算法下系统时间平均收益与用户数的关系，从图 5可以看出，4种算法的系统时间平均收益都随用户数的增加而增加，但是当用户数大于40后，收益的增长速率变缓。由于本文算法在分配带宽资源时根据用户实际需求动态分配而非均等划分，提高了系统任务的收入，另一方面，该算法根据任务队列状态对MEC服务器的计算资源进行分配，提高了资源利用率，节约了系统成本。因此，本文算法在系统时间平均收益上明显优于其他3种算法。

由于队列长度是评估用户时延和数据可靠性的关键因素，因此本文对任务队列长度的互补累积分布函数（CCDF）进行仿真，并将本文算法与LRA-TORA和OJ-TORA算法进行对比。当任务到达率为3 kb/slot时，定义用户队列阈值和MEC服务器队列阈值分别为$ 6\times {10}^{4}\mathrm{b}\mathrm{i}\mathrm{t} $和$ 5\times {10}^{5}\mathrm{b}\mathrm{i}\mathrm{t} $，平均队列长度CCDF如图 6所示。从图 6可以看出，OJ-TORA算法用户队列和MEC服务器任务队列长度CCDF都高于本文算法和LRA-TORA算法，其可靠性最差。本文算法用户任务队列长度CCDF均小于其他2种算法，而MEC服务器任务队列长度CCDF略高于LRA-TORA算法，但并未超过队列阈值，因此，本文算法仍具有较好的可靠性。

5 结束语

本文基于Lyapunov优化理论，提出一种最大化MEC系统时间平均收益的任务卸载与资源分配算法。该算法在多MEC服务器多用户系统模型下，建立任务队列动态调度模型并为队列施加概率约束，在保证用户时延和可靠性需求的同时对无线资源和计算资源实现联合分配。同时，利用马尔科夫不等式以及Lyapunov优化理论将优化问题转化为3个子问题并进行求解。仿真结果表明，该算法在时延、可靠性以及系统收益方面均具有较好的性能表现。下一步将对动态场景下的任务卸载与资源分配问题进行研究。