1 引　言

在先进的5G蜂窝系统高速发展驱动下, 各种新兴的资源需求型、时延敏感型移动应用不断涌现. 例如数据流、实时视频、3D游戏等, 这些新兴的应用为人们的生活带来了极大的便利. 然而, 随着业务逐渐复杂和多样化, 移动网络的流量呈指数级增长. 传统的集中式网络架构由于回程链路负载过重、时延较长, 无法满足移动用户的需求^[1,2]. 据IDC预测, 到2025年底将有超过416亿终端设备联网, 其中超过50%的数据需要在网络边缘分析、处理与存储^[3]. 而传统的“云-端二体协同计算”模式已无法满足低时延、高带宽的需求. 移动边缘计算(mobile edge computing, MEC) 是将网络能力从核心网下放至边缘网络的新型体系结构, 使移动终端能够将计算负载转移到边缘服务器, 为这一问题提供了一种有效的解决方案^[4] . 由于接近终端设备, MEC不仅减轻了云中心的处理压力, 而且节省了端到云的高带宽成本, 降低了端到边缘节点的网络响应时延^[5,6].

计算卸载作为移动边缘计算中一种增强移动设备计算能力的技术已经崛起. 它能够打破移动设备资源限制, 拓展移动设备计算能力、电池容量和存储能力等^[7]. 通过将移动设备的计算任务卸载到边缘服务器中执行, 达到增强移动设备的计算能力、缩短服务时延、节省移动设备能耗的目的. 然而, 在动态变化的网络环境中, 移动用户很难实时的做出细粒度的计算卸载决策, 从而无法最大化降低系统卸载开销^[8,9]. 一方面, 由于移动用户与边缘服务器之间的无线链路具有实施不确定性; 另一方面, 相比于云服务器, 边缘服务器在计算、存储等方面的资源仍相对有限^[10]. 近年来, 基于MEC的计算卸载问题得到了越来越多的关注, 学界提出了各种计算卸载策略. 现有的工作大多集中在小型同步MEC系统的卸载设计^[11-15], 卸载策略问题通常被表述为一个静态的凸或非凸优化问题, 并将能源消耗和时延做为主要的性能指标. 例如, Tan等人^[16]研究了边缘计算系统中的可持续计算卸载. 他们提出在线奖励-最优拍卖的策略来优化卸载任务的长期奖励总和, 同时适应高度动态的能量收集过程和计算任务到达. 针对大规模异步MEC系统场景, Liu等人^[17]设计了一种基于索引的实时任务卸载策略, 该方法可捕获随机临界性的任务. 文献[18]提出基于混合非正交倍数接入(non-orthogonal multiple access, NOMA)-正交多址(orthogonal multiple access, OMA)传输策略, 采用逐次凸逼近技术设计了一种求解复杂非凸问题的有效算法.

然而, 上述工作大多在卸载决策前认定信道状态信息是已知和静态的, 这意味着无线信道的相干时间远远大于应用程序的执行时间^[19,20]. 另外, 为了提高频谱效率和增强边缘用户的覆盖, 网络部署趋向于密集化, 这大大增加了不同接入单元(计算接入点或微基站) 的密度和规模, 导致传统卸载方法计算复杂度增大, 在信道相干时间内难以求解, 并且大多数方法仅考虑用户和运营商单方面的效益. 与此同时, 为实现用户邻近性并提高服务质量, 访问单元集成移动边缘服务器(MEC servers, MESs)也趋向于密集, 所以合理的用户关联也十分重要. 为此, 需要设计快速、多用户的计算卸载机制, 同时考虑符合实际计算资源和任务延迟场景下的用户关联决策.

本文考虑了多用户的MEC场景(如图1所示), 我们设计了高能效的计算卸载算法进行卸载决策, 同时寻求最佳的用户关联匹配. 特别是在卸载决策问题中, 引入机会网络做服务缓存, 并使用博弈方法分析建立了一个全网最优效益的计算卸载算法. 最后, 模拟结果表明, 提出的计算卸载算法与基准算法相比始终保持了最小化能耗和延迟, 且具有良好的性能和时间复杂度特性. 综上所述, 本文的贡献如下.

(1)本文提出了一个具有MEC密集部署的计算卸载系统模型, 其中小基站(small base stations, SBSs)和边缘计算节点都配备了MESs. 在边缘网络计算卸载过程结合了服务缓存, 显著地降低了延迟和能耗, 提升了系统的整体效率.

(2)提出了云-边-端协同的计算卸载框架, 引入D2D通信和机会网络的计算卸载场景, 并结合服务缓存, 更好适配了5G蜂窝系统下的MEC应用场景. 从而使云计算中心强大计算能力和边缘云距离终端设备的邻近性优势互补. 另外, 对不同卸载模式建立了能耗和时延模型, 将效益最优化问题转化成混合整数非线性规划问题, 该问题属于NP-hard.

(3)对多用户计算卸载问题, 每个用户是理性的(为收益最大化而调整卸载策略), 采用博弈方法可保证全网每个用户的收益最大化, 并通过数学推导证明了多用户计算卸载问题为严格势力场博弈. 最后设计了基于博弈理论的计算卸载算法, 并分析算法收敛性和时间复杂度. 此外, 在卸载决策基础上, 改进基于Gale-Shapley的匹配算法, 设计了最佳用户关联匹配算法.

(4)在模拟实验中, 我们考虑了一个实际的场景, 其中部署多个用户和SBSs, 并与其他基准算法进行比较, 验证了该算法的高能效.

本文第2节总结相关工作. 在第3节中, 我们详细描述系统模型和问题形式化. 第4节给出多用户联合计算卸载和用户关联匹配算法. 第5节讨论计算卸载和关联匹配算法的实验结果和性能评价. 最后, 第6节对本文进行总结.

2 相关工作

移动边缘计算(MEC)作为物联网和5G的一项关键使能技术, 可显著减少核心网络拥塞导致的延迟. 计算卸载是近年来MEC中的一个关键问题和研究热点^[21,22], 例如, 文献[23]提出了一个分时和计算时限约束下的总能耗最小化优化方法, 制定了对具有异构输入数据到达时间和计算截止时间的资源管理策略. 在文献[24]中, 设计了一种混合光纤-无线网络, 为集中云和多接入边缘计算的共存提供支持, 并提出了采用光纤-无线接入网络的架构和卸载方案. 为了提高效率, 文献[25-30]集中于二进制全卸载策略的研究, 以最小化延迟或能耗. Guo等人^[31]综合考虑了卸载决策、信道分配以及计算资源分配方案的优化. 通过结合遗传算法和粒子群算法的优点改进卸载算法性能和收敛速度, 提出了一种基于遗传算法和粒子群算法的次优算法. 然而, 这些工作只关注无线接入网的计算卸载过程, 忽略了无线接入网信道信息的动态变化和干扰. 针对多用户计算卸载问题, 文献[32]提出了一个综合效益最优的D2D资源共享方案, 该方案可显著改善卸载网络的性能. 文献[33]利用D2D卸载计算、并结合用户行为和特定网络运行条件, 开发了大规模D2D支持的蜂窝网络ESE评估框架. 为分析信噪比分布和平均速率, 文献[34]提出了一种D2D通信框架. 此外, 文献[35]中, 作者采用了频谱共享, 并提供了两种不同共享模式的覆盖性能比较分析.

最近的一些工作致力于采用分散式的计算卸载方案. 例如, 文献[36]提出一个以共同确定计算卸载方案、传输调度规则和定价规则的博弈算法. 该算法可使全网范围内的效益最大化, 同时实现移动用户之间的博弈均衡. Quang等人^[37]针对边缘节点对通信和计算资源争用问题提出了一种非合作的具体潜在博弈(noncooperative exact potential game), 旨在最大化计算卸载的长期效益. Zhang等人^[38]采用进化博弈论(evolutionary game)优化子载波分配方案, 为信道状态较好的子载波分配更多的子载波, 使能量效率最优. 在文献[39]中研究了一种MEC网络中新的计算卸载问题, 移动设备可以通过D2D通信或MEC服务器将任务卸载到分布式计算节点上, 并将移动设备的卸载决策问题推导为一个序列博弈. 然而, 文献[39]没有到考虑服务缓存, 即在分布式计算节点和边缘服务器^[40]上没有缓存与计算任务运行所依赖的二进制文件. 由于边缘服务器的计算和存储资源有限, 会导致不可避免的影响服务质量.

鉴于此, 我们对多接入MEC的计算卸载进行了新的研究. 与已有工作关注点不同的是, 本文研究了异构网络环境下多用户计算卸载和传输调度的能耗和时延最小化问题, 引入D2D通信和机会网络到MEC网络, 并结合服务缓存. 为克服边缘节点资源不足的缺陷, 我们设计了云-边-端协同的计算卸载框架, 既保证了边缘服务器与终端设备的邻近性, 又利用了云端的强大计算和存储资源. 本文集中于研究在云-边-端协同的计算卸载问题上使用博弈方法, 相比其他传统方法, 所设计的基于多用户卸载问题的博弈卸载算法和用户关联匹配算法, 可在信道相干时间内快速求解组合优化问题, 并综合考虑了全网效益最优的卸载策略. 数值计算结果表明, 与现有的优化方法相比, 该算法在计算时间上显著减少, 且性能接近最优.

3 系统模型及问题形式化 3.1 网络模型

如图1所示, 我们提出了一个云-边-端协同的计算卸载框架, 与已有卸载框架不同, 所提出的框架是结合了D2D通信和机会网络, 并考虑计算任务服务缓存的联合计算卸载模型. 该框架3层如下.

(1)云服务器层: 该层是由各类资源充足的云节点组成, 可提供集中式的云服务和缓存终端用户任务依赖的二进制文件功能.

(2)边缘服务层: 在本层中, 接受计算的服务器包括多接入MEC服务器和具备一定计算能力的计算节点(computing node, CN). MEC服务器被附加到蜂窝通信基站中, 移动设备连接到MEC服务器和计算节点分别通过蜂窝链路和D2D链路, 这两条链路之间由于频率不同, 相互隔离, 互不干扰.

(3)移动设备层: 该层由各类移动终端组成, 任意移动设备的计算密集型任务都可以在本地运行或卸载到边缘服务层进行计算. 边缘服务层缓存了计算任务所依赖的二进制文件以确保卸载任务正确执行. 注意, 当MEC服务器和计算节点存储空间不够, 未能缓存所需的二进制文件时, 可通过核心网向云服务器层或机会网络缓存所需的文件.

考虑移动边缘计算环境是由N个移动用户MUs (mobile user, MU)和K个计算接入点CAPs (computational access points, CAPs)构成的多用户移动边缘计算系统, 我们分别用N={1, 2, …, i, …, N}和K={1, 2, …, k, …, K}表示, 这里的接入点可以是具有计算能力的基站和移动边缘计算服务器等. 定义 $\mathrm{\Gamma }=\{{l}_{1}, {l}_{2}, \dots, {l}_{j}, \dots, {l}_{J}\} $ 表示所有的任务集, j表示计算任务的类型, 每个移动设备运行着不同类型的计算任务, 如计算密集型和延迟敏感的应用程序. 每个移动设备i上的j类型的计算任务 ${L}_{i}^{j}=\{{B}_{i}^{j, {\rm{in}}}, {B}_{i}^{j, {\rm{out}}}, {C}_{i}^{j}, {D}_{i}^{j}, {T}_{i, {\rm{MAX}}}^{j}\}, i\in N, j\in J$ . 其中, $ {B}_{i}^{j, {\rm{in}}} $ 是计算任务的输入数据, $ {B}_{i}^{j,{\rm{ out}}} $ 是返回的计算结果, $ {C}_{i}^{j} $ 是计算任务所需的CPU周期数, $ {D}_{i}^{j} $ 是计算任务所需依赖的二进制文件大小, ${T}_{i, {\rm{MAX}}}^{j}$ 是任务 $ {L}_{i}^{j} $ 的最大可接受时延. 每个MU i要么在本地执行计算任务 $ {L}_{i}^{j} $ , 要么完全卸载任务到MEC服务器执行.

3.2 通信模型

在MEC系统中, 移动设备可以通过计算无线接入点将计算任务卸载到边缘服务器^[41]. 我们定义每个移动用户MU n的设备传输速率为 $ {V}_{n} $ , 表示为:

$ {V}_{n}={W}_{k}{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\left(1+\frac{{p}_{n}{h}_{n, k}}{{w}_{0}+\displaystyle\sum _{m\in N\setminus \left\{n\right\}}{p}_{m}{h}_{m, k}}\right) $

(1)

本文考虑了通信的链路之间的相互干扰. 在上式中, $ {p}_{n} $ 是MU n的传输功率, $ {W}_{k} $ 是信道带宽, $ {w}_{0} $ 是信道的背景噪音功率, $ {h}_{n, k} $ 是MU n和计算接入点k间的信道增益, 是一个独立同分布的随机变量^[42], 可由公式(2)得出.

$ {h}_{n, k}={g}_{0}\left(\frac{{d}_{0}}{d}\right)^{\xi } $

(2)

其中, $ \xi $ 是路径损耗指数, $ {d}_{0} $ 是参考距离, d是移动设备与MEC服务器的距离, $ {g}_{0} $ 是路径损耗常数.

3.3 计算模型

考虑到服务缓存, 我们在卸载模型中引入了D2D通信和机会网络(opportunistic networks, ONs). 机会网络是一种自组织网络, 它引入节点移动带来的相遇机会从而实现通信, 使通信不再依赖于源节点与目标节点之间的完整链路. 其次, 当通信双方距离较近时, 移动终端可以直接利用D2D技术进行通信, 节省了大量信令带宽资源, 并减少了传输延迟. 由于路径损耗远低于基站到MU之间的通信损耗, D2D技术可以提高网络信道的频谱效率^[42-44]. 每个MU决定是否将其计算任务卸载到K个计算接入点中任意一个, 我们定义MU i的j类计算任务的卸载类型和链路传输数据时延分别为 ${a}_{i}^{j}=\{\mathrm{0, 1}, \mathrm{2, 3}, 4\}、{T}^{\rm off}$ , 使用指示函数 $ II $ 表示不同卸载模式, 具体如下.

(1)本地计算: 当 $ {a}_{i}^{j}=0 $ , , 计算任务 $ {L}_{i}^{j} $ 通过MU i的本地计算资源执行任务. 定义MU的设备CPU周期频率为 ${f}_{\rm MU}$ . 令 ${t}_{{L}_{i}^{j}}^{\rm local}$ 表示本地执行任务的时间. 可由公式(3)给出:

$ {t}_{{L}_{i}^{j}}^{\rm local}=\frac{{C}_{{L}_{i}}}{{f}_{\rm MU}} $

(3)

$ {T}_{\rm local}^{\rm off}=0 $

(4)

(2) MEC服务器计算: 考虑到服务缓存, 卸载任务到MEC服务器分两种情况. 一方面, 当 $ {a}_{i}^{j}=1 $ , 计算任务 $ {L}_{i}^{j} $ 将卸载到与SBSs相连的MEC服务器上, 并且MEC服务器已缓存了计算任务所依赖的二进制文件. 我们用 ${t}_{{L}_{i}^{j}}^{\rm MEC}, {t}_{{L}_{i}^{j}}^{\rm Tran}, {t}_{{L}_{i}^{j}}^{\rm Comp}, {t}_{{L}_{i}^{j}}^{\rm Res}, {T}_{\rm MEC}^{\rm off}$ 分别表示卸载任务执行总耗时、传输时延、计算耗时、接收返回结果时延和数据总的链路传输时间. 令MEC的CPU周期频率、光纤传输速率、MU与SBSs之前链路的传输速率、传输功率、传输带宽、信道增益和噪音功率分别为 ${f}_{\rm MEC}, c, {V}_{{L}_{n}^{j}}^{\rm MEC}, {p}_{\rm MEC, tran}^{i}, {W}_{\rm MEC}, {h}_{m, k}, {w}_{0}$ , 则传输速率和总时延为:

$ \begin{array}{c}\begin{array}{cc}& {V}_{{L}_{i}^{j}}^{\rm MEC}={W}_{MEC}{\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\left(1+\dfrac{{p}_{\rm MEC, tran}^{i}{h}_{i, k}}{{w}_{0}+\displaystyle\sum _{m\in N\setminus \left\{n\right\}} II({a}_{i}^{j}=1){p}_{\rm MEC, tran}^{m}{h}_{m, k}}\right)\\ & \end{array}\end{array} $

(5)

$ \begin{array}{c}{t}_{{L}_{i}^{j}}^{\rm MEC}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Comp}+{t}_{{L}_{i}^{j}}^{\rm Res}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{c}+\dfrac{{C}_{i}^{j}}{{f}_{\rm MEC}}\\ \end{array} $

(6)

其中, $\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{c}$ 为卸载任务从基站通过光纤接入到MEC服务器的传输链路时延. 则卸载的时延为:

$ {T}_{\rm MEC}^{\rm off}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Res}=\frac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\frac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{c} $

(7)

另一方面, 当 $ {a}_{i}^{j}=2 $ , 即接受计算任务的MEC服务器没有缓存卸载任务 $ {L}_{i}^{j} $ 计算所依赖的二进制文件, 此时需要通过核心网访问远程云中心层下载所需二进制文件, 同时更新缓存内容, ${t}_{{L}_{i}^{j}}^{\rm Cloud}$ 和 ${t}_{{D}_{i}^{j}}^{\rm Cloud}$ 分别代表总的时延和从远程云服务中心下载所需文件的时延, 则总时延为:

$ \begin{array}{c}{t}_{{L}_{i}^{j}}^{\rm Cloud}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Comp}+{t}_{{L}_{i}^{j}}^{\rm Res}+{t}_{{D}_{i}^{j}}^{\rm Cloud}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{c}+\dfrac{{C}_{i}^{j}}{{f}_{\rm MEC}}+\dfrac{{D}_{i}^{j}}{c}\\ \end{array} $

(8)

$ \begin{array}{c}{T}_{\rm Cloud}^{\rm off}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Res}+{t}_{{D}_{i}^{j}}^{\rm Cloud}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}+{D}_{i}^{j}}{c}\\ \end{array} $

(9)

(3) D2D卸载到计算节点: 同理, D2D卸载分为两种情况. 当 ${a}_{i}^{j}=3 $ , 计算任务 ${L}_{i}^{j} $ 通过D2D链路卸载到邻近的计算节点(如Cloudlet, 微数据中心等), 同时该计算节点已缓存了卸载任务所依赖的二进制文件, D2D链路与MU之间的传输速率、传输带宽, 传输功率, 信道增益, 噪音功率, 数据总的链路传输时间分别为 ${V}_{{L}_{n}^{j}}^{\rm D2D}, {W}_{\rm D2D}, {p}_{\rm D2D, tran}^{i}, $ ${h}_{i, {u}_{n}}, {w}_{0}, {T}_{\rm D2D}^{\rm off} $ , 由以下公式得出.

$ {V}_{{L}_{i}^{j}}^{\rm D2D}={W}_{\rm D2D}{\log}_{2}\left(1+\frac{{p}_{\rm D2D, tran}^{i}{h}_{i, {u}_{n}}}{{w}_{0}+\displaystyle\sum _{m\in N\setminus \left\{n\right\}}II({a}_{i}^{j}=3){p}_{\rm D2D, tran}^{m}{h}_{m, {u}_{n}}}\right) $

(10)

$ {t}_{{L}_{i}^{j}}^{\rm D2D}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Comp}+{t}_{{L}_{i}^{j}}^{\rm Res}=\frac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}+\frac{{C}_{i}^{j}}{{f}_{\rm D2D}} $

(11)

$ \begin{array}{c}{T}_{\rm D2D}^{\rm off}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Res}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}\end{array} $

(12)

当 $ {a}_{i}^{j}=4 $ , 即卸载的计算节点没有缓存卸载任务计算依赖的二进制文件, 类似文献[45], 此时需要通过机会网络链接任务运行所依赖的文件并下载他们, 机会网络不需要源节点和目的节点之间存在完整路径, 利用节点移动带来的相遇机会实现网络通信, 之后更新计算节点的缓存. 令传输速率、传输带宽、传输功率、信道增益、噪音功率、数据总的链路传输时间分别用 ${V}_{\rm load}^{\rm ONs}, {W}_{\rm ONs}, {p}_{\rm load}^{\rm ONs}, {h}_{n, {u}_{n}}, {w}_{0}, {T}_{\rm ONs}^{\rm off}$ 表示, 则传输速率和总时延为:

$ {V}_{\rm load}^{{\rm{ONs}}}={W}_{{\rm{ONs}}}{\log}_{2}\left(1+\dfrac{{p}_{\rm load}^{n}{h}_{n, {u}_{n}}}{{w}_{0}}\right) $

(13)

$ \begin{array}{c}{t}_{{L}_{i}^{j}}^{\rm ONs}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Comp}+{t}_{{L}_{i}^{j}}^{\rm Res}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}+\dfrac{{C}_{i}^{j}}{{f}_{\rm D2D}}+\dfrac{{D}_{i}^{j}}{{V}_{\rm load}^{\rm ONs}}\\ \end{array} $

(14)

$ \begin{array}{c}{T}_{\rm ONs}^{\rm off}={t}_{{L}_{i}^{j}}^{\rm Tran}+{t}_{{L}_{i}^{j}}^{\rm Res}=\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}+\dfrac{{D}_{i}^{j}}{{V}_{\rm load}^{\rm ONs}}\end{array} $

(15)

则根据不同卸载方式下, 总的时延表示为:

$ {T}^{\rm off}=\{{T}_{\rm local}^{\rm off}, {T}_{\rm MEC}^{\rm off}, {T}_{\rm Cloud}^{\rm off}, {T}_{\rm D2D}^{\rm off}, {T}_{\rm ONs}^{\rm off}\} $

(16)

综合以上不同的卸载类型, MU可通过无线传输向CAP发送数据时, 可以调整传输功率. 因此, MU的卸载策略 $ {s}_{n} $ 可表示为:

$ {s}_{n}=\{{P}_{n}, {a}_{n}\} $

(17)

其中, ${P}_{n}\in \left[0, {P}_{\rm max}\right],$ 分别表示设备的发射功率和策略集, 则策略集 $S=({s}_{1}, {s}_{2}, \dots, {s}_{n})$ .

3.4 能耗模型

针对计算模型提出的5种卸载类型, 本节将分别对不同卸载类型建立能耗模型, 定义 ${e}^{i}, {e}_{\rm MEC}^{i}, {e}_{\rm D2D}^{i}$ 分别表示计算任务在本地、MEC、D2D环境下每个CPU周期消耗的能量.

(1)本地计算能耗: 当 $ {a}_{i}^{j}=0 $ , 则MU i的j类型任务在本地执行的能耗 ${e}_{{L}_{i}^{j}}^{\rm local}$ 为:

$ {e}_{{L}_{i}^{j}}^{\rm local}={C}_{i}^{j}{e}^{i} $

(18)

结合公式(3)的本地计算总时延, 令 $ \alpha $ 和 $\; \beta $ 分别表示计算任务 $ {L}_{i}^{j} $ 的时延和能耗权重系数, 且 $ \alpha +\beta =1 $ . 可以得出本地执行任务的总开销 ${E}_{{L}_{i}^{j}}^{\rm local}$ 为:

$ {E}_{{L}_{i}^{j}}^{\rm local}=\alpha {t}_{{L}_{i}^{j}}^{\rm local}+\beta {e}_{{L}_{i}^{j}}^{\rm local} $

(19)

(2) MEC服务器卸载能耗: 当 $ {a}_{i}^{j}=1 $ , 则卸载到MEC服务器执行任务的能耗 ${e}_{{L}_{i}^{j}}^{\rm MEC}$ 为:

$ \begin{array}{c}{e}_{{L}_{i}^{j}}^{\rm MEC}={p}_{\rm MEC, tran}^{i}\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{c}+{C}_{i}^{j}{e}_{\rm MEC}^{i}\\ \end{array} $

(20)

结合公式(6)的MEC卸载总时延 ${t}_{{L}_{i}^{j}}^{\rm MEC}$ , 可以得出总开销 ${E}_{{L}_{i}^{j}}^{\rm MEC}$ 为:

$ {E}_{{L}_{i}^{j}}^{\rm MEC}=\alpha {t}_{{L}_{i}^{j}}^{\rm MEC}+\beta {e}_{{L}_{i}^{j}}^{\rm MEC} $

(21)

同理, 当 $ {a}_{i}^{j}=2 $ , 此时MEC服务器通过访问远程云中心下载任务所依赖的二进制文件后执行任务, 则总能耗 ${e}_{{L}_{i}^{j}}^{\rm Cloud}$ 为:

$ \begin{array}{c}{e}_{{L}_{i}^{j}}^{\rm Cloud}={p}_{\rm MEC, tran}^{i}\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm MEC}}+\dfrac{{B}_{i}^{j, in}+{B}_{i}^{j, {\rm{out}}}}{c}+{C}_{i}^{j}{e}_{\rm MEC}^{i}+\dfrac{{D}_{i}^{j}}{c}\\ \end{array} $

(22)

结合公式(8)的访问云主机的卸载总时延 ${t}_{{L}_{i}^{j}}^{\rm Cloud}$ , 可以得出总开销 ${E}_{{L}_{i}^{j}}^{\rm Cloud}$ 为:

$ {E}_{{L}_{i}^{j}}^{\rm Cloud}=\alpha {t}_{{L}_{i}^{j}}^{\rm Cloud}+\beta {e}_{{L}_{i}^{j}}^{\rm Cloud} $

(23)

(3) D2D卸载能耗: 类似D2D计算模型, 当 $ {a}_{i}^{j}=3 $ , 则通过D2D链路卸载的能耗 ${e}_{{L}_{i}^{j}}^{\rm D2D}$ 为:

$ {e}_{{L}_{i}^{j}}^{\rm D2D}={p}_{\rm D2D, tran}^{i}\dfrac{{B}_{i}^{j, {\rm{in}}}+{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}+{e}_{\rm D2D}^{i}{C}_{i}^{j} $

(24)

结合公式(11)的D2D卸载总时延 ${t}_{{L}_{i}^{j}}^{\rm D2D}$ , 可以得出总开销 ${E}_{{L}_{i}^{j}}^{\rm D2D}$ 为:

$ {E}_{{L}_{i}^{j}}^{\rm D2D}=\alpha {t}_{{L}_{i}^{j}}^{\rm D2D}+\beta {e}_{{L}_{i}^{j}}^{\rm D2D} $

(25)

同理, 当 $ {a}_{i}^{j}=4 $ , 此时, 通过机会网络下载文件后执行计算卸载的能耗为 ${e}_{{L}_{i}^{j}}^{\rm ONs}$ 为:

$ \begin{array}{c}{e}_{{L}_{i}^{j}}^{\rm ONs}=\dfrac{{p}_{\rm D2D, tran}^{i}{B}_{i}^{j, {\rm{in}}}+{p}_{i,{\rm{ rec}}}^{i}{B}_{i}^{j, {\rm{out}}}}{{V}_{{L}_{i}^{j}}^{\rm D2D}}+{e}_{\rm D2D}^{i}{C}_{i}^{j}+\dfrac{{p}_{\rm load}^{n}{D}_{i}^{j}}{{V}_{\rm load}^{\rm ONs}}\\ \end{array} $

(26)

结合公式(14)的访问机会网络ONs卸载的总时延 ${t}_{{L}_{i}^{j}}^{\rm ONs}$ , 可以得出总开销 ${E}_{{L}_{i}^{j}}^{\rm ONs}$ 为:

$ {E}_{{L}_{i}^{j}}^{\rm ONs}=\alpha {t}_{{L}_{i}^{j}}^{\rm ONs}+\beta {e}_{{L}_{i}^{j}}^{\rm ONs} $

(27)

综合以上5种卸载类型, 总的开销 $ E\left(S\right) $ 为:

$ E\left(S\right)=\{{E}_{{L}_{i}^{j}}^{\rm local}, {E}_{{L}_{i}^{j}}^{\rm MEC}, {E}_{{L}_{i}^{j}}^{\rm Cloud}, {E}_{{L}_{i}^{j}}^{\rm D2D}, {E}_{{L}_{i}^{j}}^{\rm ONs}\} $

(28)

3.5 效益函数和问题形式化

通过以上两节建立的计算和能耗模型, 我们可以给出每个MU的效益函数 $ {\chi }_{n}\left(S\right) $ 模型. 首先令 ${D}_{n}^{l}, {D}_{n}^{\rm OFF}$ 分别表示计算任务在本地执行和卸载到边缘服务器执行所需要的CPU周期数. 类似文献[46], 假设卸载任务执行所需CPU周期数与卸载数据比特数成正比, 则:

$ {D}_{n}^{l}=II({a}_{n}^{j}=0){C}_{i}^{j} $

(29)

$ \begin{array}{c}\begin{array}{cc}& {D}_{n}^{\rm OFF}=II({a}_{i}^{j}\ne 0)\theta {T}^{\rm off}{V}_{i}=\theta {T}^{\rm off}\displaystyle\sum\nolimits_{\begin{array}{*{20}{c}} {k \in K}\\ {a_i^j \in \{ {\rm{1}},{\rm{2}},{\rm{3}},{\rm{4}}\} } \end{array}} {\begin{array}{*{20}{c}} \end{array}}{W}_{k}{\log}_{2}\left(1+\frac{{a}_{n}^{j}{p}_{n}{h}_{n, k}}{{w}_{0}+\displaystyle\sum\nolimits_{m \in N \setminus \left\{ n \right\}}{a}_{m}^{j}{p}_{m}{h}_{m, k}}\right)\\ & \end{array}\end{array} $

(30)

其中, $ II $ 为指示函数, 表示不同的卸载模式. $ \theta $ 为计算数据比, 即处理每bit数据所需消耗的CPU周期数, 则执行任务总的CPU周期数 $ {D}_{n} $ 表示为:

$ \begin{array}{c}{D}_{n}\left(S\right)={D}_{n}^{l}+{D}_{n}^{\rm OFF}=II({a}_{n}^{j}=0){C}_{i}^{j}+\theta {T}^{\rm off}\displaystyle\sum\nolimits_{\begin{array}{*{20}{c}} {k \in K}\\ {a_n^j \in \{ {\rm{1}},{\rm{2}},{\rm{3}},{\rm{4}}\} } \end{array}} {W}_{k}{\log}_{2}\left(1+\frac{{a}_{n}^{j}{p}_{n}{h}_{n, k}}{{w}_{0}+\displaystyle\sum\nolimits_{m \in N \setminus \left\{ n \right\}}{a}_{m}^{j}{p}_{m}{h}_{m, k}}\right)\\ \end{array} $

(31)

由于在多接入MEC系统中, 参与计算卸载的每个用户是理性的, 也就是说, 每个用户都愿意通过增大各自的传输功率来卸载计算密集型任务到边缘云处理, 即最大化已处理CPU周期数, 最终导致整个传输信道性能下降. 鉴于此, 每个MU的效益函数必须仔细考虑能耗和性能^[47]. 在实际情况下, 能源消耗是有成本的, 本文考虑了一种能源感知的效益函数模型 $ {\chi }_{n}\left(S\right) $ 为:

$ {\chi }_{n}\left(S\right)={\mu }_{1}{D}_{n}\left(S\right)-{\mu }_{2}{E}_{n}\left(S\right) $

(32)

该效益函数模型可反映每个MU的卸载收益, 综合考虑了能耗和时延. 因此, 每个MU的任务卸载决策可形式化为联合优化问题P1:

$\left\{ \begin{aligned} &\left(\mathrm{P}1\right)\;\forall n\in N, \max{\chi }_{n}\left(S\right)\\ &{\rm{s.t.}}\left\{\begin{aligned} & \leqslant {t}_{{L}_{i}^{j}}\leqslant {T}_{i, {\rm{MAX}}}^{j}\left(33{\rm{a}}\right)\\ & {a}_{i}^{j}\in \left\{\mathrm{0, 1}, \mathrm{2, 3}, 4\right\}\left(33{\rm{b}}\right) \\ & 0 < {P}_{i}\leqslant {P}_{\rm max}\left(33{\rm{c}}\right)\\ & 0 < {P}_{i}^{\rm MEC}\leqslant {P}_{\rm max}^{\rm MEC}\left(33{\rm{d}}\right)\\ & \sum\nolimits_{i \in N}{D}_{i}\leqslant {D}_{\rm MEC}\left(33{\rm{e}}\right)\\ & i\in N, j\in J\left(33{\rm{f}}\right)\end{aligned}\right. \end{aligned} \right.$

(33)

公式(33)中的约束33a表示任务最大能容忍时延. 33b表示卸载类型, 33c表示每个MU的发射功率不得超过设备最大功率, 33d限定了每个边缘服务器功率不得超过最大功率. 33e限定了缓存任务运行必备的二进制文件大小不应超过MEC服务器最大存储容量 ${D}_{\rm MEC}$ . 相应的33f约束了设备和计算任务类型的范围. 该效益函数全面反映每个MU的整体收益, 既体现卸载任务带来的收益, 又考虑了能耗的影响. 注意, 效益函数的推导过程如公式(34)所示.

$ \begin{aligned}[b] {\chi }_{n}\left(s\right)&={\mu }_{1}{D}_{n}\left(S\right)-{\mu }_{2}{E}_{n}\left(S\right)\\ &={\mu }_{1}\left(II\right({a}_{n}^{j}=0){C}_{n}^{j}+\theta {T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{{1, 2}, {3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left(1+\frac{{a}_{n}^{j}{p}_{n}{h}_{n, k}}{{w}_{0}+\displaystyle\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}^{j}{p}_{m}{h}_{m, k}})\right)-{\mu }_{2}{E}_{{L}_{n}^{j}}\left(S\right)\\ & =\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{\mathrm{1, 2}, \mathrm{3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N}{a}_{m}^{j}{p}_{m}{h}_{m, k}\right)+{\mu }_{1}II({a}_{n}^{j}=0){C}_{n}^{j}-{\mu }_{2}{E}_{{L}_{n}^{j}}\left(S\right)\\ &\;\; -\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{\mathrm{1, 2}, \mathrm{3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}^{j}{p}_{m}{h}_{m, k}\right) \end{aligned} $

(34)

$ \begin{aligned}[b] {\chi }_{n}({S}'_{n}, {S}_{-n})-{\chi }_{n}({S}''_{n}, {S}_{-n}) =&\left(\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{{1, 2}, {3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}{p}_{m}{h}_{m, k}+{a}'_{n}{p}'_{n}{h}_{n, k}\right)\right.\\ & -\left.\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{{1, 2}, {3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}{p}_{m}{h}_{m}+{a}''_{n}{p}''_{n}{h}_{n, k}\right)\right)\\ & -[{\mu }_{2}{E}_{{L}_{n}^{j}}({s}_{n}{)'}-{\mu }_{2}{E}''_{{L}_{n}^{j}}\left({s}_{n}\right)]+[{\mu }_{1}II\left({a}'_{n}\right){C}_{n}^{j}-{\mu }_{1}II\left({a}''_{n}\right){C}_{n}^{j}]\end{aligned} $

(35)

$ \begin{aligned}[b] \varphi ({S}'_{n}, {S}_{-n})-\varphi ({S}_{n}, {S}''_{-n}) =&\left(\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{{1, 2}, {3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}{p}_{m}{h}_{m, k}+{a}'_{n}{p}'_{n}{h}_{n, k}\right)\right.\\ &\left. -\theta {\mu }_{1}{T}^{\rm off}\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \{{1, 2}, {3, 4}\}\end{array}}{W}_{k}{\log}_{2}\left({w}_{0}+\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}{p}_{m}{h}_{m, k}+{a}''_{n}{p}''_{n}{h}_{n, k}\right)\right)\\ & -\left[{\mu }_{2}\sum\nolimits _{m\in N\setminus \left\{n\right\}}{E}_{{L}_{n}^{j}}({S}_{m})+{\mu }_{2}{E}_{{L}_{n}^{j}}({S}_{n}{)'}-\left({\mu }_{2}\sum\nolimits _{m\in N\setminus \left\{n\right\}}{E}_{{L}_{n}^{j}}({s}_{m})+{\mu }_{2}{E}''_{{L}_{n}^{j}}({s}_{n})\right)\right]\\ & +[{\mu }_{1}II({a}'_{n}){C}_{n}^{j}-{\mu }_{1}II({a}''_{n}){C}_{n}^{j}]\end{aligned} $

(36)

4 多用户联合计算卸载和关联匹配算法

基于每个MU的能效模型, 我们设计一种高能效计算卸载算法, 即EDCO (energy efficient distributed computing offloading)算法. 采用基于博弈理论为基础的多用户联合计算卸载算法, 并证明了该博弈是一个严格势力场博弈(exact potential game, EPG). EDCO算法可在有限次迭代后达到全网最优效益的纳什均衡状态. 同时我们分析了EDCO算法的收敛性和时间复杂度. 最后, 针对用户关联匹配问题, 我们受Gale-Shapley匹配理论启发, 对其做出修改并改进, 并结合EDCO算法, 设计了最佳用户关联匹配算法(best user association matching algorithm, BUAM).

4.1 博弈模型

与传统单用户计算卸载不同, 在对接入MEC系统中, 随机分布的每个参与方是自私的, 为了实现个人效益最大化, 每个用户倾向于调整自己的发射功率来卸载计算密集型任务, 即最大化任务已处理CPU周期数来相互竞争. 这势必会导致一个分布式决策问题, 更具体地说, 这是一个多用户计算卸载系统上的非合作博弈. 形式上, 这个博弈可以表示为:

$ G=\{N, A={A}_{1}\dots{A}_{n}, \chi :A⟶{R}^{N}\} $

(37)

其中, N表示博弈的参与者集合 $ i\in N $ , A表示每个参与者的策略空间 $ {S}_{i} $ , $ \forall i\in N $ , $ \chi $ 表示每个参与者的效益函数, 即公式(33)定义的形式. 令 ${s}_{-i}=\{{s}_{1}, {s}_{2}, \dots, {s}_{i-1}, {s}_{i+1}, \dots,{s}_{n}\}$ 表示除了用户i以外的所有其他参与者的策略组合向量. 则博弈G的纳什均衡(Nash equilibrium, NE)可定义为:

定义1. 在博弈G中, 如果由每个博弈方的一个策略组成的某个策略组合 ${s}^{*}=\{{s}_{1}^{*}, {s}_{2}^{*}, \dots, {s}_{i}^{*}, \dots,{s}_{n}^{*}\}$ 中, 任意一个博弈方MU i的策略 $ {s}_{i}^{*} $ 都是对其余博弈方策略组合 $ {s}_{-i}^{*}=\{{s}_{1}^{*}, {s}_{2}^{*}, \dots, {s}_{i-1}^{*}, {s}_{i+1}^{*}, \dots, {s}_{n}^{*}\} $ 的最佳对策, 即:

$ {\chi }_{n}\left({s}_{i}^{*}, {s}_{-i}^{*}\right)\geqslant {\chi }_{n}\left({s}_{i}, {s}_{-i}^{*}\right),\;\;\forall {s}_{i}^{*}\ne {s}_{i} $

(38)

则称 $\{{s}_{1}^{*}, {s}_{2}^{*}, \dots, {s}_{i}^{*}, \dots,{s}_{n}^{*}\}$ 为G的一个纳什均衡. 显然, 博弈G的纳什均衡很大程度上依赖于卸载策略 $ {s}_{i} $ , 因此, 为了保证所有移动用户都愿意按效益最大化的方式自行管理各自计算卸载策略, 以保证用户自身的效益.

在卸载决策时, 应以全网范围内的最优解为博弈G中的NE, 即:

$ {s}_{i}^{*}=\hat{{s}_{i}},\;\;\forall i\in N $

(39)

$ {s}_{i}^{*}, \hat{{s}_{i}} $ 分别是博弈G的纳什均衡解和计算卸载效益优化问题P1的输出. 为方便分析本文提出的EDCO算法收敛性, 在分析其收敛性前, 我们引入收敛性较好的严格势力场博弈. 其中, 严格势力场函数(exact potential function, EPF)可反映参与博弈的移动用户策略单独发生改变时效用函数的变化^[38].

定义2. 博弈G是一个以 $ \varphi $ 为势函数的严格势力场博弈. $ \varphi $ 的形式如下:

$ \begin{array}{c}\varphi \left(S\right)=\theta {\mu }_{1}{T}^{\rm off}{\displaystyle\sum\nolimits }_{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \left\{{1, 2}, {3, 4}\right\}\end{array}}{W}_{k}{\log}_{2}\left({W}_{0}+\displaystyle\sum _{m\in N}{a}_{m}^{j}{p}_{m}{h}_{m, k}\right)+{\mu }_{1}II({a}_{n}^{j}=0){C}_{n}^{j}-{\mu }_{2}\sum _{n\in N}{E}_{{L}_{n}^{j}}\left({S}_{n}\right)\\ \\ \end{array} $

(40)

证明: 博弈G是严格势力场博弈(EPG), 存在一个势函数 $\varphi :S\to R, \forall {S}'_{i}, {S}''_{i}\in {S}_{i}$ , 使下列等式恒成立.

$ \varphi ({S}'_{i}, {S}_{-i})-\varphi ({S}''_{i}, {S}_{-i})=\chi ({S}'_{i}, {S}_{-i})-\chi ({S}''_{i}, {S}_{-i}) $

(41)

EPG的证明推导过程如公式(35)所示. 其中, ${S}'_{i}, {S}''_{i}$ 表示MU n上一个不同于 $ {s}_{n} $ 的卸载策略, 也就是说, 当MU i从策略 ${S}'$ 切换到策略 ${S}''$ 时, 潜在的变化等于该用户效用值的变化. 根据公式(34)效用函数 $ {\chi }_{n}\left(S\right) $ 的形式, 我们可推导出公式(35). 注意, 公式(34)的最后一项只和其他MU的策略 $ {S}_{-n} $ 有关, 所以 $\chi ({S}'_{i}, {S}_{-i})-\chi ({S}''_{i}, {S}_{-i})$ 可以消除这一项. 势函数 $ \varphi $ 的详细的推导细节在公式(36), 类似公式(35)推导过程, $\varphi ({S}'_{i}, {S}_{-i})-\varphi ({S}''_{i}, {S}_{-i})$ 中可以消除只与其他MU的策略相关的项 $ {S}_{-n} $ . 综合公式(35)和公式(36), 可知公式(41)恒成立. 故博弈G是一个以函数 $ \varphi $ 为势函数的严格势力场博弈. 综上所述, 如果一种博弈模型满足EPG时, 当用户以最佳对策动态连续调整时, 博弈就会收敛到纯纳什平衡点, 并使势函数 $ \varphi $ 取得最大值. 任何异步最佳对策更新过程都必须是有限的, 通过有限异步最佳对策更新过程来达到纳什均衡. 即有以下推论^[48]:

推论1. 对于EPG博弈G, 存在一个纯策略纳什均衡, 并且可以通过有限次的最佳响应过程得到.

4.2 高能效的的分布式计算卸载算法

基于上述博弈理论, 我们设计了一个通过有限次最佳对策得到高效能计算卸载决策的算法(EDCO algorithm), 算法具体步骤如下:

(1) 初始化卸载策略及关联匹配关系表, 并随机选择一个计算任务 $ {L}_{i}^{j} $ , 选中的概率为 $ \dfrac{1}{N} $ , 卸载策略 $ {S}_{i}=\mathrm{\varnothing } $ ;

(2) 在每次迭代中, 计算接入点依次对每个MU i进行最佳对策更新 $ {S}_{i} $ . 具体来讲, 在给定更新后的用户计算卸载决策 $\{{s}_{1}^{t+1}, {s}_{2}^{t+1}, \dots, {s}_{n-1}^{t+1}\}$ 和在第t次迭代中剩余未更新用户的卸载决策 $\{{s}_{n+1}^{t}, {s}_{n+2}^{t}, \dots, {s}_{N}^{t}\}$ 情况下, 用户n将选择卸载决策 $ \left\{{s}_{n}^{t+1}\right\} $ 来获取最大化收益. 即:

$ {s}_{n}^{t+1}=\underset{{a}_{i}\in \{\mathrm{0, 1}, \mathrm{2, 3}, 4\}}{\rm argmax}\chi (s, {s}_{1}^{t+1}, {s}_{2}^{t+1}, \dots,{s}_{n-1}^{t+1}, {s}_{n+1}^{t},\dots, {s}_{N}^{t}) $

(42)

(3)根据公式(17)所示的 $ {s}_{i}=\{{P}_{i}, {a}_{i}\} $ , 每个用户抢占更新的概率是均等的, 并且每个用户在更新决策后, 会广播决策 $ {s}_{n}^{t+1} $ 给其他用户, 让其他用户知道当前的卸载决策.

(4)每个移动设备通过有限次迭代, 异步执行各自的最佳对策更新, 直至达到纳什均衡状态, 得出最佳卸载决策S. 之后调用最佳用户关联匹配算法BUAM, 计算最佳关联匹配算法. 注意, BUAM算法的具体细节见第4.3节.

EDCO算法和BUAM算法具体细节如算法1和算法2所示.

4.2.1 收敛性分析

由于纳什均衡解不一定是最优解, 我们使用无政府代价(price of anarchy, PoA)来量化纳什均衡最坏的情况^[49]. 令 $ \sigma $ 为纳什均衡集, $\underset{{S}_{i}^{*}\in \sigma }{\max}\displaystyle\sum _{n\in K}{\chi }_{n}\left({s}_{i}^{*}\right)$ 表示最大化收益. 则PoA为:

$ PoA=\frac{\underset{{S}_{i}^{*}\in \sigma }{\max}\displaystyle\sum _{n\in K}{\chi }_{n}\left({s}_{i}^{*}\right)}{\underset{{S}_{i}\in S}{\min}\displaystyle\sum _{n\in K}{\chi }_{n}\left({s}_{i}\right)} $

(43)

定理1. 博弈G的PoA最大值为 $\frac{\displaystyle\sum _{n\in K}({\mu }_{1}{D}_{n}^{l}-{\mu }_{2}{E}_{n}^{\rm local})}{\displaystyle\sum _{n\in K}\min\{{\chi }_{n}^{\rm local}, {\chi }_{n}^{\rm off}\}}$ .

证明: 在纳什均衡下, 每个用户n的能量消耗最多为 ${E}_{\rm local}$ , 即选择始终在本地执行计算任务. 因此

$ \sum _{n\in K}{\chi }_{n}\left({s}_{i}^{*}\right)\leqslant \sum _{n\in K}{\chi }_{n}^{\rm local}=\sum _{n\in K}({\mu }_{1}{D}_{n}^{l}-{\mu }_{2}{E}_{n}^{\rm local}) $

(44)

$ \sum _{n\in K}{\chi }_{n}\left({s}_{i}\right)\geqslant \min\{{\chi }_{n}^{\rm local}, {\chi }_{n}^{\rm off}\} $

(45)

其中, ${\chi }_{n}^{\rm off}={\mu }_{1}{D}_{n}^{\rm OFF}-{\mu }_{2}{E}_{n}\left(S\right)={\mu }_{1}\theta {T}^{\rm off}\displaystyle\sum\nolimits _{\begin{array}{c}k\in K\\ {a}_{n}^{j}\in \left\{\mathrm{1, 2}, \mathrm{3, 4}\right\}\end{array}}{W}_{k}{\mathrm{log}}_{2}\left(1+\dfrac{{a}_{n}^{j}{p}_{n}{h}_{n, k}}{{w}_{0}+\displaystyle\sum\nolimits _{m\in N\setminus \left\{n\right\}}{a}_{m}^{j}{p}_{m}{h}_{m, k}}\right)-{\mu }_{2}{E}_{{L}_{n}^{j}}\left({s}_{i}\right)$ , 基于公式(44), 公式(45)可得:

$ PoA\leqslant \frac{\displaystyle\sum _{n\in K}({\mu }_{1}{D}_{n}^{l}-{\mu }_{2}{E}_{n}^{\rm local})}{\displaystyle\sum _{n\in K}\min\{{\chi }_{n}^{\rm local}, {\chi }_{n}^{\rm off}\}} $

(46)

该结果表明EDCO算法具有很好的收敛性, 在有限次迭代后可快速收敛. 实际上, 在后续实验结果也表明了该算法的收敛性明显好于传统基准算法.

算法1. EDCO.

输入: K, N, µ₁, µ₂, W_MEC , W_D2D , W_ONs, w₀, N₀, h_n,k, P_MU , P_MEC ,P_D2D , P_ONs, P_res, P_MAX , d₀, θ, g₀, f_MEC, f_D2D, f_MU, $e_{L_i^j}^{\rm local},e_{L_i^j}^{\rm MEC},e_{L_i^j}^{\rm D2D},e_{L_i^j}^{\rm ONs} $ (0 < i < n);

输出: 计算卸载策略S, 最小能耗E_min, 关联匹配Θ.

1. 初始化阶段: 被占用的信道数为k=0, 时间段内所有的移动设备MU的卸载决策S_i = 0, $\forall i $ ∈ N , 默认是本地执行, 随机选择一个计算任务 $L_i^j $ , (选中的概率为 $ \dfrac{1}{N}$ ), 卸载策略S_i =Ø.

2. while t<T do

3. 　 for all i ∈ Ndo

4. 　　根据公式(5), 公式(7), 公式(9)计算slot t+1的不同类型设备的传输速率: $V_{L_i^j}^{\rm MEC},V_{L_i^j}^{\rm D2D},V_{\rm load}^{\rm ONs}$ , 并根据公式(33)以及相应的约束条件计算最大收益的卸载策略 $s_i^j $ .

5.　　 if $s_i^j $ 满足约束规则33a, 33b, 33c, 33d, 33e then

6. 　　　更新 $s_i^j $

7. 　　 end if

8. 　 end for

9.　 if s^t ≠ s^t+1 and S ≠ Ø then

10.　　 if 如果设备i争取到更新机会 then

11.　　　 根据公式(33)用户选择卸载决策 $s_n^{t+1} $ 最大化自己的收益.

12. 　　　 $s_i=s_i^{t+1} $

13.　　 else

14. 　　　 $s_i=s_i^t $

15.　　 end if

16. 　 end if

17. 　Set t = t + 1

18. end while

19. 根据公式(28)计算出最优决策S下的最小功耗E_min.

20. Θ ← BUAM (S)

21. return S, E_min, Θ.

算法2. BUAM.

1. 初始化A_user, Θ_K (k), J_max

2. 从接受的所有卸载请求协议中获取卸载决策S, 并计算MU和MESs的偏好.

3. for each n=1 to N do

4. 　对卸载请求S中的每个MU根据公式(16)对MU偏好π_N (n, k) 进行升序排序, 得到L_N (n)

5. end for

6. for each k=1 to K do

7. 　对每个MESs根公式(33)对MESs偏好π_K (k, n) 进行降序排序, 得到得到L_K (k)

8.end for

9.while |Θ_K (k)| ≤ J_max do

10. 　 $n=\arg {\max _{\Theta _K^C(k)}}$ π_K(k, n)

11. 　 if MU和MESs都满足对QoS的要求 then

12.　　考虑过的MESs分配给MU

13. 　　更新 Θ_K (k)← Θ_K (k) ∪ n

14.　　 $\Theta _K^C(k) $ ← { $\Theta _K^C(k) $ \n}

15. 　　 A_user ← {A_user \n}

16.　　 S ← {S\n}

17. 　 else

18.　　考虑过的MESs不能分配给MU

19. 　清空Θ_K (k) = Ø.

20.　 end if

21. end while

4.2.2 时间复杂度分析

命题1. 算法1中, EDCO的计算复杂度为O(T·N), 其中T为EDCO收敛迭代次数, N为计算任务数.

证明: 算法1中的EDCO共有两层循环. 根据推论1, 外部for循环表示博弈参与者, 当博弈达到NE态时, 其收敛时间是有限的. 我们用T表示EDCO中外部for循环的迭代次数. 此外, 步骤1–6的内部for 循环最多运行N次, 从步骤7–15的过程时间复杂度为O(1). 最后, 总运行时间EDCO的计算方法是将它们相乘, 即 O(T·N), 其中T为算法的收敛迭代次数,N为计算任务数.

4.3 用户关联算法

在算法1解算出卸载决策后, 可对用户和MEC服务器的关联匹配做出最优分配, 该问题可形式化为:

$ \left\{\begin{aligned} &\left(\mathrm{P}2\right)\;\;\forall n\in N, \max\chi \left(a\right)\\ &{\rm{s.t.}}\left\{\begin{array}{l}0 < {a}_{n}^{k}\leqslant {q}_{\max}\left(47{\rm{a}}\right)\\ \displaystyle\sum _{m=1}^{M}{a}_{n}^{m}=1\left(47{\rm{b}}\right)\\ n\in N\text{, }k\in K\left(47{\rm{c}}\right) \end{array}\right. \end{aligned}\right.$

(47)

其中, P2是一个关于卸载决策a的匹配问题, 47a限制了每个MESs关联的用户数量不能超过 ${q}_{\max}$ . 47b表示每个用户只能关联一个MESs, 47c表示用户范围约束. 我们设计的用户关联匹配算法受Gale-Shapley理论^[50]的启示, 对P2中的用户和MEC服务器两组参与者可以根据多对一双边匹配理论做出用户关联决策. 为此, 我们改进了该算法, 并提出了最佳用户关联匹配BUAM算法. 首先给出用户和MESs的偏好函数和偏好列表.

(1)用户偏好: 为了满足服务质量的保障, 用户会更倾向于与较低延迟的MESs关联. 因此, 我们使用公式(16)中的卸载延迟作为用户的偏好函数 $ {\pi }_{N} $ , 并根据函数值的升序得到偏好列表 $ {L}_{N} $ , 则MUn对MESs的偏好函数为:

$ \begin{array}{c}{\pi }_{N}\left(n, k\right)={T}^{\rm off}\left(\mathrm{a}\right)\end{array} $

(48)

定义MU n的偏好列表为 ${L}_{N}\left(n\right)=[1, \dots, k, \dots, K], \mathrm{即}{\pi }_{N}$ 按升序排列 $ {\pi }_{N}(n, 1)\leqslant \cdots\leqslant {\pi }_{N}(n, k)\leqslant \cdots \leqslant {\pi }_{N}(n, K) $ .

(2) MESs偏好: MESs运营商为了获得更好的效益, 更愿意接受能够带来高效益的用户请求. 基于此, 我们使用公式(33)效益函数作为MESs的偏好函数 $ {\pi }_{K} $ , 并根据函数值的递减顺序确定偏好列表 $ {L}_{K} $ . MESs对MU n的偏好为:

$ \begin{array}{c}{\pi }_{k}(k, n)={\chi }_{n}\left(S\right)\end{array} $

(49)

令MES m的偏好列表为 ${L}_{K}\left(k\right)=[1, \dots, n, \dots, N], 即{\pi }_{k}$ 按降序排列 ${\pi }_{k}(k, 1)\geqslant \dots \geqslant {\pi }_{k}(k, n)\geqslant \dots \geqslant {\pi }_{N}(K, N)$ . 令 $ \mathrm{\Theta } $ 为MU和MESs的一组关联匹配关系对, $ \mathrm{\Theta }=\left\{\right(n, k) $ , 表示MU n与MES k关联, $ n\in N, K\in K\} $ , 给定匹配函数 $\mathrm{\Theta },\; {\mathrm{\Theta }}_{N}\left(n\right)$ 为 MU n匹配的一组MESs. 相反, $ {\mathrm{\Theta }}_{K}\left(k\right) $ 表示匹配MESs k的一组用户. ${A}_{\rm user}$ 记录了当前未匹配任何MESs的用户集合, $ {\mathrm{\Theta }}_{K}^{C}\left(k\right) $ 表示请求至MESs k的所有用户集合, ${J}_{\rm max}$ 表示MESs最多能关联的MU数量. 基于EDCO计算卸载算法求解的卸载决策后, 本文提出了一种基于Gale-Shapley匹配理论的最佳用户关联匹配算法(BUAM)来获得最优匹配. 算法的细节如算法2所示.

5 数值模拟

在本节中, 我们通过模拟实验验证提出计算卸载算法和关联匹配算法的能效. 下面首先给出模拟设置的详细信息, 然后讨论下列评价问题.

● EDCO算法相比其他基准算法整体的能效和时延表现如何?

● 关联匹配算法BUAM算法相比其他关联匹配算法的能效表现如何?

● 权重系数对卸载时延和能耗有多敏感?

● 设备和基站的距离对能耗的影响? 即算法对用户移动性的支持.

● EDCO算法的收敛速度如何?

5.1 模拟设置

本实验通过Matlab进行数值模拟实验进行验证, 表1是试验中用到的主要参数. 根据4G蜂窝网络特性^[45], 设定每个移动用户的传输功率为[100, 200] mW. 基于移动边缘计算辅助视频和游戏等应用的配置^[51], 设置输入数据包大小和任务所需的平均CPU周期数分别是[300, 800] KB、[100, 1000] Megacycles. 对于不同的移动用户, 其计算任务可能是异构的, 因此本实验设定卸载任务的最大容忍时延范围为 ${t}_{\max} $ =[1, 2] s之间. MU与边缘服务器间的距离d, 均匀分布在(200, 500)米范围内.

为了进一步验证提出的EDCOS (energy efficient distributed computing offloading scheme)的性能, 我们将其与以下几种基准算法进行比较, 分别为始终不卸载NOS (no offloading scheme)、随机组件委派模式RCAS (random component assignment scheme)、基于遗传算法GACS (genetic algorithm based computation scheme). 在NOS中, 所有用户都选择计算任务在本地执行, 不再卸载任务到边缘服务器. 特别地, 本节中的能耗是指完成任务所消耗的全部能耗. 在RCAS中, 用户随机做出卸载决策和传输功率, SBSs随机的分配信道和计算资源给用户. GACAS是基于遗传算法进行计算卸载. 最后, 为对比关联匹配算法的效果, 在关联匹配算法的对比基准算法上, 我们与基于最近关联原则的联合卸载决策算法(JODRA-NAP)和资源均等分配的联合用户关联算法(JUAOD-ERA) ^{[52, 53]}对比.

5.2 性能对比

在图2、图3中, 除了NOS方式, 对于其他3种卸载模式, 每个用户的平均时延成本和能耗都随着MU数量的增加而增大. 其原因是: (1)移动用户数量越大, 卸载任务数增多, 排队系统越拥挤, 等待延迟和能耗越高. (2)信道干扰随着设备的增加而增加. 由于始终在本地执行计算, NOS保持不变. 从图中结果表明所提出的EDCOS保持了最小化能耗和总时延代价. EDCOS的调度规则很好地平衡了所有移动用户在计算卸载中的等待成本和能耗成本, 取得了明显优于其他基准算法的效果.

图4(a)给出了不同卸载策略下, 如本地计算( $ {a}_{i}=0 $ )、MEC卸载( $ {a}_{i}=\mathrm{1, 2} $ )和D2D卸载( $ {a}_{i}=\mathrm{3, 4} $ ), 每种卸载策略的效益值与MUs数量之间的定量关系. 可以看出, 随着MU数量的增加, 选择D2D卸载和MEC卸载的效益值逐渐低于EDCOS的效用值. 由于随着MU数的增加, 传输能量消耗和传输延迟增加, 导致开销增大, 选择本地计算与其他卸载方式相结合的策略成为更好的选择. 在图4(b)中展示了不同卸载模式下的能耗和基站数量之间的定量关系. 结果表明, EDCOS和GACS的能耗随着SBSs数量的增加而增大. 虽然系统在这种情况下保留了更多的资源, 但干扰也随之增加. 因此, EDCOS和GACS的能耗都出现上升趋势. 对于NOS, 始终选择本地执行任务, 不会因为基站数量改变而改变. 对于RCAS, 由于资源是随机分配的, 所以无法确保性能. 图4(c)展示了随着SBSs数量的增加, 运营商的效益值变化. 显然, 我们设计的BUAM算法获得了用户关联算法中最大的效用, 并且随着SBSs数目的增加, 其相对于基准算法的增益也越来越明显. 因为EDCOS共同优化了用户关联, 而基准算法只考虑其中的一种或两种.

从图4(a)和图4(b)可以看出, 我们提出的EDCOS算法性能优于其他3种基准算法. 在RCAS中, 卸载决策是随机进行的, 这可能导致不同SBSs之间的信道干扰增大, 从而导致能耗变得很大. 且由公式(1)可知传输速率也会随着干扰而下降, 这导致了卸载时延的增加, 所以在两图中RCAS保持了最高能耗和时延. EDCOS通过优化信道分配和功率控制, 从而控制卸载MU的数量与信道干扰的数据量, 因此节省了整体的卸载能耗和时延. GACS性能优于RCAS和NOS, 遗传操作(交叉和变异)可以保持解的多样性, 扩展搜索区域, 从而跳出局部最优. EDCOS利用博弈思想, 保持了每个MU的结果最优, 性能优于其他3种基准算法.

5.3 权重系数对性能的影响

图5(a)展示了随着MU数量增加, EDCOS算法在迭代过程中势函数 $ \varphi $ 值的变化. 数值模拟显示算法在Iteration=45后, 曲线保持水平静止, 表明博弈达到纳什均衡状态, 进一步验证了收敛点是NE. 根据势博弈的性质, 势函数 $ \varphi $ 值在其最大值为NE时单调递增并收敛. 因此, 博弈经过少量迭代后实现了纳什均衡.

在图5(b)描述了不同的 $ \;{\mu }_{1}/{\mu }_{2} $ 的比值下, 不同卸载模式的能耗变化. 随着 $ \;{\mu }_{1} $ 的增大, 由于NOS始终在本地计算, 其能耗比其他卸载算法要高得多. 当 $\; {\mu }_{1}/{\mu }_{2}={10}^{6} $ 之后, RCAS, GACS, EDCOS的能耗都降到800 mJ以下. GACS算法在当 $ \;{\mu }_{2} $ 足够高时, MU 的传输功率反而会降低, 导致能耗增大. 关于随机分配和本地处理, 由于MU的卸载策略不依赖于参数 $ \;{\mu }_{1}, {\mu }_{2} $ , 所以它们的能耗是常量. 通过对比可以发现, 基于博弈理论的EDCOS算法保持了更小的能耗成本.

图5(c)中展示了不同数据计算比 $ \theta $ 下EDCOS的能耗. 实际上, 当 $ \theta $ 在低值时(如运行一些低CPU周期数的任务时), MU的最优决策是使用本地进程的CPU周期. 当 $ \theta $ 增大时, MU的卸载任务数量增多, 需要处理的CPU周期数也会增加. 这意味着更多的任务会通过无线信道与计算接入点连接, 导致严重的信道干扰, 近而导致能耗增加. 图5(d)描述了MU和SBSs之间距离对能耗的影响. 对比发现: EDCOS的性能总是优于粗粒度的卸载模式(RCAS和GACS). 其中本地计算NOS模式由于始终在本地进行计算任务, 保持了较高恒定的能耗. 此外, 我们观察到距离d对EDCOS的影响很小, 这意味着EDCOS支持MU的移动性, 在各种网络条件下能够保持稳定.

本文所考虑的3层卸载框架可对应于一个静态的物联网网络, 该网络的发射机和接收机固定在某个位置. 文献>[54, 55]的测量实验表明, 信道不变的信道相干时间在1~10 s之间, 通常不小于2 s. 以N=30的MEC网络为例, 我们设计的EDCO算法的执行完毕时间平均为0.061 s, 这对于现场部署来说是可以接受的开销. 因此, EDCO算法使得信道衰落环境下无线MEC网络的计算卸载成为切实可行的.

6 结　论

本文研究了基于多用户多MEC场景中的计算卸载决策和用户关联算法. 首先我们提出一个云-边-端的联合计算卸载框架, 将云计算中心和边缘节点优势互补, 并通过优化卸载决策, 同时考虑了干扰管理和功率控制. 接着对多用户计算卸载模型进行形式化描述为一种能效感知的效益模型, 将能耗和时延最优化问题转化为混合整数非线性规划问题, 这是NP-hard问题. 其次, 多用户计算卸载中每个用户是理性的, 即每个用户会追求自身效益最大化而调整卸载策略. 为了确保以网络范围内的最优方案进行卸载决策, 建立了博弈论模型来共同确定计算卸载方案, 并证明了该场景下的多用户计算卸载为严格势力场博弈. 所设计的计算卸载算法可以使每个用户的效用最大化. 此外, 为了进一步优化服务质量, 我们设计了用户关联匹配算法, 寻找边缘服务器和请求卸载的用户之间的最佳匹配关系. 最后, 相比起基准算法, 我们提出卸载算法在收敛速度和能效上明显优于传统基准算法.

我们的方法也存在不足, 在未来的工作中, 我们将对D2D和机会网络节点之间链路丧失导致数据丢失或计算失败情况下卸载策略的代价考虑进来. 同时, 我们也对不同性能需求情况下制定合理的定价规则和资源分配感兴趣. 从运营商的角度出发做效益优化, 保证在多用户QoS约束下提高运营商的潜在效益.