随着物联网（Internet of Things, IoT）、大数据、人工智能等新兴技术的快速发展，传统的计算网络架构难以应对大量数据的集中式处理，从而导致较高的网络延迟、带宽消耗问题. 边缘计算作为分布式架构，将计算资源部署在网络的边缘，使得终端的部分数据在边缘节点上进行计算，可以减轻中心服务器的负担，从而提高计算效率、降低网络延迟^[1]. 为了适应更大规模的边缘计算任务，多层边缘计算网络应运而生^[2]. 与单层的场景不同，其终端往往处于不同的边缘计算服务器覆盖范围内. 其对终端设备层和边缘层进行任务卸载，根据不同的场景需求^[3-4]，灵活选择边缘层中某个服务器来执行计算任务以实现最优的资源分配和性能最大化.

在边缘计算的卸载分配任务中，须考虑到诸多因素. 一方面，由于用户和基站之间的信道质量参差不齐，终端和基站之间的信息交换会带来较大的传输时延，不同的终端须选择最适配的基站上传任务来实现整体的性能最优^[5-6]；另一方面，终端以及基站的计算性能受限，终端须与选定基站之间合理分配任务量^[7-9]. 因此须综合考虑各个过程中的时延以及性能限制，尽可能地提高性能、减少整体时延.

目前已有许多策略和算法用来解决边缘计算网络中的任务卸载问题^[10]. 从通信时延和计算时延两方面出发，通过调度终端和基站的资源来降低时延或减少能耗.

刘耿旗等^[11-13]分别针对边缘计算场景中的用户选择、无线资源分配和任务卸载进行研究，并提出最优的解决方案. He等^[14-15]采用博弈模型来优化系统总体开销和用户平均时延. 郭煜^[16]提出边缘计算中带有缓存机制的卸载策略，由于终端可能多次请求一样的任务，因此将部分处理好的结果缓存在边缘服务器从而降低整体的计算开销. Tran等^[17-18]利用不同的启发式算法优化系统任务完成时间和能量的加权和. 龙隆等^[19]考虑在无线频谱、算力受限下，构建系统时延并利用重构线性化、松弛法以及凸优化方法最小化所有终端设备执行任务总时延. 代美玲等^[20]在考虑算力资源分配的基础上，利用拉格朗日函数和拟牛顿法分别对单用户和多用户的场景进行优化. Jiang等^[21]为了维持终端用户满意度，在优化算力和频谱资源的基础上提出在线联合卸载和资源分配框架，能够在满足长期移动边缘计算(mobile edge computing,MEC)能耗约束的同时，达到接近最优的性能. Kim等^[22]综合考虑用户关联、资源分配、全任务卸载，提出基于分布式定价的任务解决方案来降低时延和能量消耗. 除此之外，现有的关于用户关联的研究^[23-25]是基于信道质量、信噪比之类与信道有关的参数进行优化的，没有考虑到基站算力对于用户关联的影响，但基站由于算力受限，一定程度上会影响用户关联，具体表现在基站无法无限制地承受任何用户，须保证已存在用户的通信质量.

已有研究很少同时考虑基站的算力、功率，终端的算力、任务特性，以及两者之间的频谱资源优化、用户关联、卸载决策、资源分配等重要的策略. 而这些对于多层边缘计算网络是尤为重要的. 1）基站的算力和功率同时影响用户关联. 当终端有计算任务须选择一个基站进行协同计算时，如果基站的算力充足但是没有足够的发射功率，此时任务卸载将不会带来时延增益，甚至会增大计算时延. 同样，如果基站有足够的发射功率，但是没有充足的算力，此时边缘服务器计算时延会增大. 2）频谱资源以及算力资源也同时影响卸载决策. 计算任务卸载的同时会引起额外的时延开销，如任务上传时延、边缘服务器计算时延以及任务下载时延，这3部分的时延由频谱资源以及算力资源共同决定. 在频谱资源不足的情况下，终端更倾向于在本地进行处理，反之则考虑计算卸载. 因此，在多层边缘计算网络中，终端和边缘服务器的各种限制使得如何合理进行用户关联和资源分配上存在着巨大的挑战.

本研究基于上述研究背景，综合考虑基站算力、功率、频谱分配受限的情况下，终端和基站的关联方案以及最优的卸载决策和资源分配策略. 本研究主要创新点如下. 1）建立多层边缘网络终端用户模型，考虑终端算力、基站算力、功率以及无线频谱资源受限情况下的联合优化. 首先分析边缘计算网络中的通信性能和计算时延，通信性能包括终端和基站之间的上行通信速率和下行通信速率，计算时延指终端的本地计算时延、终端将任务上传基站的时延、边缘基站计算时延和基站回传任务时延. 2）根据基站算力、功率，无线频谱资源的限制，建立最小化所有任务时延的优化问题. 3）通过问题分解，分别获得用户关联、任务卸载策略以及无线资源分配的最优解，并设计基于迭代的次优算法.

如图1所示为多层边缘计算网络示意图. 考虑一个典型的多层边缘计算场景，多个配备边缘服务器的小基站以及配备边缘服务器的宏基站组成一个多层的异构网络. 网络中随机分布着$K$个通信终端，每个终端都有计算任务需要处理，如视频渲染、压缩. 假设这些计算任务都是可以分割的，即任务可以被拆分计算. 考虑到终端的计算能力有限，如果所有的计算任务都放在本地进行，将带来较大的计算开销以及时延. 因此，终端可以将部分计算任务卸载到与之关联的边缘服务器. 设定系统内有$S$个小基站，1个宏基站，小基站之间有覆盖重叠区域，在重叠范围内终端可以选择一个小基站连接，也可以选择宏基站连接. 与传统的单层场景不同，在该多层系统模型中，除了须考虑单个基站内的边缘计算任务外，还须综合考虑多个基站之间的相互影响.

在系统中，须同时考虑终端以及基站的计算能力和终端与基站的信道质量，来权衡终端自己处理计算任务的时间和将任务上传到基站处理，并反馈结果所带来的时延. 假设终端${k_1}$可以连接的基站有${s_1}、{s_2}、{s_3}$，${k_1}$与基站${s_1}$的信道功率增益最大，与基站${s_2}$的信道功率增益其次，与基站${s_3}$的信道功率增益最小. 终端${k_1}$将部分任务在本地处理，同步上传剩下的任务到基站. 虽然终端${k_1}$和基站${s_1}$的信道增益是最大的，但如果场景中存在另一终端${k_2}$，且只能被基站${s_1}$覆盖到，那么基站${s_1}$必须使用一部分算力协助终端${k_2}$的计算，此时终端${k_1}$的任务并不能交给基站${s_1}$处理. 终端${k_1}$、${k_2}$和基站${s_1}、{s_2}、{s_3}$须进行联合优化处理，目的是为了使整个系统处理所有终端任务的时延最小.

基站和终端之间的通信可以采用频分复用（frequency division multiple access，FDMA）的方式复用上行和下行信道，基站和终端所分配用于通信的带宽影响计算任务上传和下载的时间，分配的带宽越高，通信速率越大，如果基站和终端之间采用其他多址接入方式也有相对应的结论，区别只在于考虑的资源复用不一样.

系统的优化目标是处理所有终端任务的时延和最小. 在这个优化目标下，由于基站算力和功率是有限的，须合理分配基站在其覆盖范围内所有终端的算力和功率. 因为终端和基站能分配的带宽总和是固定的，如果分配给基站的计算任务越多，相应分配的带宽也要越多.

多层边缘计算网络中的时延主要是由通信时延和计算时延组成. 其中通信时延主要产生在终端卸载任务到边缘服务器和边缘服务器回传处理好的任务这2个过程中. 计算时延也分为2部分：1）终端本地的计算时延；2）边缘服务器处理卸载任务产生的计算时延.

使用变量${a_{k,s}}$来表示终端$k$选择小基站$s$连接情况，其中，$s = 0$表示宏基站的连接情况. 每个小基站与宏基站各分配带宽为$B$的正交信道，因此，在该工作中不考虑小基站之间的干扰以及小基站与宏基站的干扰. 在每个小基站范围内，连接的终端以FDMA的方式复用上行信道以及下行信道，定义$ l_{k,s}^{\rm{U}} $为基站$s$分配给终端$k$的上行频谱比例. 因此，终端$k$的上行速率可以表示为

(1)$ R_k^{\rm{U}} = \displaystyle\sum\limits_s {{a_{k,s}}l_{k,s}^{\rm{U}}B{{\log }_2}\left( {1+\dfrac{{{p_k}{h_{k,s}}}}{{l_{k,s}^{\rm{U}}B{N_0}}}} \right)} . $

式中：${p_k}$为终端的发射功率，${N_0}$为噪声功率谱密度，${h_{k,s}}$为终端和基站之间的信道功率增益，$B$为基站能够分配的总带宽. 由于终端只能选择一个基站进行关联，须对所有基站选择的情况进行求和才能获得终端的上行速率. 终端$k$获得的下行速率可以表示为

(2)$ R_k^{\rm{D}} = \displaystyle\sum\limits_s {{a_{k,s}}l_{k,s}^{\rm{D}}B{{\log }_2}\left( {1+\dfrac{{{p_{k,s}}{h_{k,s}}}}{{l_{k,s}^{\rm{D}}B{N_0}}}} \right)} . $

式中：${p_{k,s}}$为基站$s$分配给终端的功率，$ l_{k,s}^{\rm{D}} $为基站$s$分配给终端$k$的下行频谱比例. 同样，须对所有基站选择的情况进行求和才能获得终端的下行速率.

先从时延性能角度来分析用户关联、资源优化以及任务卸载优化. 如图2所示为边缘计算处理流程. 可以看出，边缘计算的时延分为4个部分. 1）终端选择一个基站，这个基站可以是小基站也可以是宏基站，终端根据自身的算力和基站的算力、功率以及频谱资源分配来计算本地计算任务和基站计算任务所占的比例. 2）终端计算本地留存的任务，产生本地计算时延作为时延衡量的一个指标，并将剩下的任务发送到基站，这些数据会经过终端和基站之间的上行信道，产生上传卸载任务的时延. 3）基站根据自身的算力以及和终端的关联情况，分配自身的算力来计算不同的终端发送过来的任务，这也是边缘卸载任务计算时延的产生. 4）基站将处理好的任务回传给终端，处理好的任务经过基站和终端之间的下行信道，产生边缘服务器回传时延，边缘计算的总体时延由本地计算时延、上传卸载任务时延、边缘卸载任务计算时延和边缘服务器回传时延构成.

设定终端$k$有${d_k}$比特的计算任务，该计算任务可以被拆分，用本地处理的任务比例${\rho _k}$表示，$0 \leqslant {\rho _k} \leqslant 1.0$. 于是，在本地处理的计算任务数据量可以表示为${\rho _k}{d_k}$，剩下的表示在边缘端处理，处理完的数据量大小由该任务决定. 不失一般性，假设处理完的数据量大小与原有计算任务的数据量成比例关系，即${\xi _k}{d_k}$，${\xi _k}$为处理完的数据量大小与原有计算任务数据量的比例关系. 4部分时延表达式如下.

1） 本地计算时延：

(3)$ t_k^{\rm{L}} = {{{\rho _k}{d_k}f_k^{\rm{O}}}}/{{{f_k}}}. $

式中：${d_k}$为终端$k$的计算任务总量；${f_k}$为终端的算力；$f_k^{\rm{O}}$为处理该终端任务1个比特需要的算力，可以用CPU的周期数衡量.

2）上传卸载部分数据需要的时延：

(4)$ t_k^{\rm{C}} = {{\left( {1 - {\rho _k}} \right){d_k}}}/{{R_k^{\rm{U}}}}. $

3） 边缘服务器的处理时延：

(5)$ t_k^{\rm{E}} = \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}. $

式中：$\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} $表示所有基站分配给终端的算力，由于终端只能选择一个基站进行关联，须对所有基站选择情况进行求和.

4）边缘服务器计算完回传的时延：

(6)$ \mathop t\nolimits_k^{\rm{B}} = {{\mathop \xi \nolimits_k (1 - \mathop \rho \nolimits_k )\mathop d\nolimits_k }}/{{\mathop R\nolimits_k^{\rm{D}} }}. $

终端$k$计算任务的时延可以表示为

(7)$ {T_k} = \max \;\left\{ {t_k^{\rm{L}},t_k^{\rm{C}}+t_k^{\rm{E}}+t_k^{\rm{B}}} \right\}. $

终端的计算时延由本地计算部分以及卸载给边缘的部分的最大值决定，这是因为卸载决策决定后，任务卸载和本地计算可以同步进行，只有2部分都完成后，该任务才能视为计算完成.

从边缘计算的性能分析结果可知，计算时延由卸载的决策、用户关联以及资源分配共同决定. 为了提高边缘计算的效率，须通过优化用户关联、时隙分配、算力分配以及任务卸载策略，最小化所有终端任务计算的平均时延. 终端须权衡信道以及算力资源，选择合适的基站连接，并且选择最优的任务卸载策略. 该优化问题描述如下：

(8)$ \left.\begin{split} &\mathop {\min }\limits_{l_{k,s}^{\rm{U}},l_{k,s}^{\rm{D}},{a_{k,s}},{p_{k,s}},{f_{k,s}},{\rho _k}} \dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ; \\&\displaystyle\sum\limits_k {l_{k,s}^{\rm{U}}} \leqslant L_s^{\rm{U}},\; \displaystyle\sum\limits_k {l_{k,s}^{\rm{D}}} \leqslant L_s^{\rm{D}}, \;\displaystyle\sum\limits_s {{a_{k,s}}} = 1, \\&\displaystyle\sum\limits_k {{f_{k,s}}} \leqslant F_s, \;\displaystyle\sum\limits_k {{p_{k,s}}} \leqslant P_s, \;0 \leqslant {\rho _k} \leqslant 1.0, \\&l_{k,s}^{\rm{U}},l_{k,s}^{\rm{D}},{p_{k,s}},{f_{k,s}} \geqslant 0, \;{a_{k,s}} \in \left\{ {0,1} \right\}.\end{split}\right\} $

式中：${F_s}$表示基站$s$的总算力，${P_s}$表示基站$s$的总发射功率；限制条件$\sum\limits_k {l_{k,s}^{\rm{U}}} \leqslant L_s^{\rm{U}}$和$\sum\limits_k {l_{k,s}^{\rm{D}}} \leqslant L_s^{\rm{D}}$分别表示无线频谱资源的上行频谱资源和下行频谱资源是有限的；限制条件$\sum\limits_s {{a_{k,s}}} = 1$是指终端只能选择一个基站进行连接，但是基站可以同时连接多个终端；限制条件$\sum\limits_k {{f_{k,s}}} \leqslant F_s^{}$和$\sum\limits_k {{p_{k,s}}} \leqslant P_s^{}$分别考虑了边缘基站的算力和功率是有限的；限制条件$0 \leqslant {\rho _k} \leqslant 1.0$是指终端的任务卸载为0~1.0的数，取0是指终端只在基站处理计算任务，取1.0是指终端只在本地处理计算任务；限制条件$l_{k,s}^{\rm{U}},l_{k,s}^{\rm{D}},{p_{k,s}},{f_{k,s}} \geqslant 0$，表示资源的分配是非负的；限制条件${a_{k,s}} \in \left\{ {0,1} \right\}$，表示终端和基站的连接情况只能为1或是0，1为连接，0为不连接.

以上问题是混合整数非线性优化问题，是非凸且NP难的问题. 为了求解上述问题，首先将${T_k}$看成一个优化变量，即可去掉$\max $. 该问题的优化变量变为${a_{k,s}}、l_{k,s}^{\rm{U}}、l_{k,s}^{\rm{D}}、$${p_{k,s}}、{f_{k,s}}、{\rho _k}$，可以表示为

(9)$\left.\begin{array}{ll}{} &\mathop {\min }\limits_{l_{k,s}^{\rm{U}},l_{k,s}^{\rm{D}},{a_{k,s}},{p_{k,s}},{f_{k,s}},{\rho _k},{T_k}} \dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ; \\{\mathrm{s}}.{\mathrm{t}}. & \displaystyle\sum\limits_k {l_{k,s}^{\rm{U}}} \leqslant L_s^{\rm{U}},\;\displaystyle\sum\limits_k {l_{k,s}^{\rm{D}}} \leqslant L_s^{\rm{D}},\;\displaystyle\sum\limits_s {{a_{k,s}}} = 1,\\{} & \displaystyle\sum\limits_k {{f_{k,s}}} \leqslant F_s,\;\displaystyle\sum\limits_k {{p_{k,s}}} \leqslant P_s,\;\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k}, \\{} & \dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k}, \\{} & 0 \leqslant {\rho _k} \leqslant 1.0,\;l_{k,s}^{\rm{U}},l_{k,s}^{\rm{D}},{p_{k,s}},{f_{k,s}} \geqslant 0,\;{a_{k,s}} \in \left\{ {0,1} \right\}.\end{array}\right\} $

式中：新增的限制条件$\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k}$表示最小时延不小于本地计算时延. 限制条件$\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}} + \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+ \dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k}$，表示最小时延不小于边缘计算的上传、处理、回传时延和.

变量耦合导致问题变得复杂，须将这些变量分开优化. 观察上述变量可以知，问题可以分解为用户关联优化、卸载决策优化、以及无线资源分配优化.

给定$l_{k,s}^{\rm{U}}、l_{k,s}^{\rm{D}}$、${p_{k,s}}、{f_{k,s}}、{\rho _k}$变量后，原问题可以简化为

(10)$ \left.\begin{array}{ll}{}&\mathop {\min }\limits_{{a_{k,s}}} \;\dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ;\\{\mathrm{s.t}}. &\displaystyle\sum\limits_s {{a_{k,s}}} = 1,\;\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k},\\{}&\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}} + \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }} + \dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k},\\{}&{a_{k,s}} \in \left\{ {0,1} \right\}.\end{array} \right\}$

定理1　假设在边缘计算网络中存在$S$个边缘基站和$K$个终端，执行边缘计算任务时，基站$s$和终端$k$最优的用户关联满足：

(11)$ \begin{split} \mathop {a_{k,s}} =& \arg \min \limits_{{a_{k,s}}}\; {a_{k,s}}\left(\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{U}}B{{\log }_2}\;\left( {1 + \dfrac{{{p_k}{h_{k,s}}}}{{l_{k,s}^{\rm{U}}B{N_0}}}} \right)}}+\right. \\ &\left. \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{{f_{k,s}}}} + \dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{D}}B{{\log }_2}\;\left( {1 + \dfrac{{{p_{k,s}}{h_{k,s}}}}{{l_{k,s}^{\rm{D}}B{N_0}}}} \right)}}\right).\end{split} $

上述决策是一个选择问题，即针对每一个终端，在功率、算力、频谱资源已知的情况下，在考虑到信道质量和算力的基础上选择边缘计算上传、处理、回传整体时延最小的那个量，其物理意义是选择卸载后上传、处理、回传时延代价最小的那个基站.

(12)$ \begin{split} &\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{U}}B{{\log }_2}\left( {1+\dfrac{{{p_k}{h_{k,s}}}}{{l_{k,s}^{\rm{U}}B{N_0}}}} \right)}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{{f_{k,s}}}}+\\&\qquad \dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{D}}B{{\log }_2}\left( {1+\dfrac{{{p_{k,s}}{h_{k,s}}}}{{l_{k,s}^{\rm{D}}B{N_0}}}} \right)}}.\end{split} $

给定${a_{k,s}}、l_{k,s}^{\rm{U}}、l_{k,s}^{\rm{D}}$、${f_{k,s}}、{\rho _k}$变量后，原问题可以简化为

(13)$ \left.\begin{array}{ll}{}&\mathop {\min }\limits_{{\rho _k}} \dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ;\\{\mathrm{s.t}}. & 0 \leqslant {\rho _k} \leqslant 1.0,\;\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k},\\{}&\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k}.\end{array}\right\} $

卸载决策决定了任务上传服务器的数据量多少，当其他变量固定时，如果本地时延大于边缘计算时延，可以适当减少本地任务，将任务上传到基站，反之，可以增加本地任务，减少上传的任务. 显然，本地时延和边缘计算时延相等的卸载决策是卸载任务的最优解，定理如下.

定理2　假设在边缘计算网络中存在$S$个边缘基站和$K$个终端，执行边缘计算任务时，最优的卸载决策${\rho _k}$为

(14)$\begin{split} {\rho _k} = &\left.\left({{\dfrac{1}{{R_k^{\rm{U}}}}+\dfrac{{f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}}}{{R_k^{\rm{D}}}}}}\right)\right/\\&\left({{\dfrac{1}{{R_k^{\rm{U}}}}+\dfrac{{f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}}}{{R_k^{\rm{D}}}}+\dfrac{{f_k^{\rm{O}}}}{{{f_k}}}}}\right).\end{split} $

证明　式（13）的第2、3个限制条件均是${\rho _k}$的线性约束条件，为了方便表示，记

(15)$ \left. \begin{split} &{A_{1k}} = \dfrac{{{d_k}f_k^{\rm{O}}}}{{{f_k}}}, \\& {A_{2k}} = \dfrac{{{d_k}}}{{R_k^{\rm{U}}}}+\frac{{{d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}{d_k}}}{{R_k^{\rm{D}}}} .\end{split} \right\} $

则条件改写为

(16)$ \left. \begin{split} &{A_{1k}}{\rho _k} \leqslant {T_k}, \\& {A_{2k}}(1 - {\rho _k}) \leqslant {T_k}.\end{split} \right\} $

2个条件分别乘以${A_{2k}}$与${A_{1k}}$后相加，得到

(17)$ {A_{1k}}{A_{2k}} \leqslant ({A_{1k}}+{A_{2k}}){T_k}. $

等号在$ {A_{1k}}{\rho _k} = {A_{2k}}(1 - {\rho _k}) $时取到，代入后即可得到最优的卸载决策：

(18)$ \begin{split} {\rho _k} = & \left.\left({{\dfrac{1}{{R_k^{\rm{U}}}}+\dfrac{{f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}}}{{R_k^{\rm{D}}}}}}\right)\right/\\& \left({{\dfrac{1}{{R_k^{\rm{U}}}}+\dfrac{{f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}}}{{R_k^{\rm{D}}}}+\dfrac{{f_k^{\rm{O}}}}{{{f_k}}}}}\right).\end{split} $

定理2表明，${f_k}$越小，${\rho _k}$越小，也就是说当终端自身的算力越小，本地留存的任务量也就越少. 与边缘计算有关的资源${f_{k,s}}$、$R_k^{\rm{U}}$和$R_k^{\rm{D}}$越大，${\rho _k}$也越小.

当求解完用户关联以及卸载决策以后，可以分别优化$l_{k,s}^{\rm{U}}、l_{k,s}^{\rm{D}}、{p_{k,s}}、{f_{k,s}}$.

1）优化上行信道的分配，$l_{k,s}^{\rm{U}}$，优化问题可以表示为

(19)$ \left.\begin{array}{ll}{}&\mathop {\min }\limits_{l_{k,s}^{\rm{U}}}\; \dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ; \\{{\mathrm{s.t}}.}&\displaystyle\sum\limits_k {l_{k,s}^{\rm{U}}} \leqslant L_s^{\rm{U}},\;\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k},\\{}&\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k},\\{}&l_{k,s}^{\rm{U}} \geqslant 0.\end{array}\right\} $

上行频谱资源限制条件和本地计算时延条件都是线性的约束条件，边缘计算限制条件是关于$l_{k,s}^{\rm{U}}$的凸函数，因此该问题是凸优化问题，可以利用凸优化工具包解决.

2）优化下行信道和基站功率的分配，$l_{k,s}^{\rm{D}},\;{p_{k,s}}$，优化问题可以表示为

(20)$ \left.\begin{array}{ll}{}&\mathop {\min }\limits_{l_{k,s}^{\rm{D}},{p_{k,s}}} \dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ;\\{{\mathrm{s.t}}.}&\displaystyle\sum\limits_k {l_{k,s}^{\rm{D}}} \leqslant L_s^{\rm{D}},\;\displaystyle\sum\limits_k {{p_{k,s}}} \leqslant P_s,\\{}&\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k},\\{}&\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k},\\{}&l_{k,s}^{\rm{D}},{p_{k,s}} \geqslant 0. \end{array}\right\}$

同样，下行频谱资源限制条件、基站功率限制条件和本地计算时延条件是线性的约束条件，在边缘计算限制条件中，$ {{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}\Bigg/\Bigg[l_{k,s}^{\rm{D}}B{{\log }_2}\bigg( 1+ \dfrac{{{p_{k,s}}{h_{k,s}}}}{{l_{k,s}^{\rm{D}}B{N_0}}} \bigg)\Bigg] $是关于$l_{k,s}^{\rm{D}}、{p_{k,s}}$形如${1}\bigg/\bigg[{{x\log \left( {1+\dfrac{y}{x}} \right)}}\bigg]$的函数，由于${1}\bigg/\bigg[{{x\log \left( {1+\dfrac{y}{x}} \right)}}\bigg]$是凸函数，并且原有的目标约束中是可以拆分如下：

(21)$ \begin{split} &\displaystyle\sum\limits_s {a_{k,s}}\left(\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{U}}B{{\log }_2}\left( {1 + \dfrac{{{p_k}{h_{k,s}}}}{{l_{k,s}^{\rm{U}}B{N_0}}}} \right)}} + \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{{f_{k,s}}}}+ \right.\\&\qquad \left.\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{l_{k,s}^{\rm{D}}B{{\log }_2}\left( {1+\dfrac{{{p_{k,s}}{h_{k,s}}}}{{l_{k,s}^{\rm{D}}B{N_0}}}} \right)}}\right) .\\[-5pt]\end{split} $

因为每个用户只能选择一个基站进行连接，这个也是凸优化问题，仍然可以用凸优化工具包求解.

3）优化基站的算力分配，${f_{k,s}}$，优化问题可以表示为

(22)$\left.\begin{array}{ll} {}&\mathop {\min }\limits_{{f_{k,s}}} \;\dfrac{1}{K}\displaystyle\sum\limits_k {{T_k}} ;\\{{\mathrm{s.t}}.}&\displaystyle\sum\limits_k {{f_{k,s}}} \leqslant F_s,\;\dfrac{{{\rho _k}{d_k}f_k^{\rm{O}}}}{{{f_k}}} \leqslant {T_k},\\{}&\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}}+\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }}+\dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}} \leqslant {T_k},\\{}&{f_{k,s}} \geqslant 0.\end{array}\right\}$

算力的分配存在闭式解，这个闭式解使得基站对于和它关联的所有用户在边缘计算时延上保持一致，即定理3.

定理3　对于基站$m$来说，假设有$l$个终端与其关联，记为$ {j}_{1},{j}_{2},\cdots ,{j}_{l} $，那么基站$m$的算力分配满足：

(23)$ \begin{split} \frac{{\left( {1 - {\rho _{{j_1}}}} \right){d_{{j_1}}}f_{{j_1}}^{\rm{O}}}}{{f_{_{{j_1},m}}^2}} = &\frac{{\left( {1 - {\rho _{{j_2}}}} \right){d_{{j_2}}}f_{{j_2}}^{\rm{O}}}}{{f_{_{{j_2},m}}^2}} =\cdots = \\&\frac{{\left( {1 - {\rho _{{j_l}}}} \right){d_{{j_l}}}f_{{j_l}}^{\rm{O}}}}{{f_{_{{j_l},m}}^2}}. \end{split}$

证明　根据定理2，将最优的卸载决策代入问题，得到

(24)$ \left.\begin{split} &\mathop {\min }\limits_{{f_{k,s}}} \;\dfrac{1}{K}\displaystyle\sum\limits_k {\dfrac{{\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{U}}}} + \dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{\displaystyle\sum\limits_s {{a_{k,s}}{f_{k,s}}} }} + \dfrac{{{\xi _k}\left( {1 - {\rho _k}} \right){d_k}}}{{R_k^{\rm{D}}}}} ;\\&\qquad \sum\limits_k {{f_{k,s}}} \leqslant F_s.\end{split}\right\}$

在该优化问题中，只有第2项涉及到算力的优化，且因为${a_{k,s}}$是和用户关联有关的0-1变量，因此该问题等价于

(25)$ \left.\begin{split} &\mathop {\min }\limits_{{f_{k,s}}} \;\dfrac{1}{K}\displaystyle\sum\limits_s {\displaystyle\sum\limits_k {{a_{k,s}}\dfrac{{\left( {1 - {\rho _k}} \right){d_k}f_k^{\rm{O}}}}{{{f_{k,s}}}}} } ;\\&\qquad \displaystyle\sum\limits_k {{f_{k,s}}} \leqslant F_s.\end{split} \right\}$

由于每个基站的算力是单独优化的，根据柯西-施瓦茨不等式，使得目标函数最小的算力分配需要每个基站的算力分配满足

(26)$ \begin{split} \frac{{\left( {1 - {\rho _{{j_1}}}} \right){d_{{j_1}}}f_{{j_1}}^{\rm{O}}}}{{f_{_{{j_1},m}}^2}} =& \frac{{\left( {1 - {\rho _{{j_2}}}} \right){d_{{j_2}}}f_{{j_2}}^{\rm{O}}}}{{f_{_{{j_2},m}}^2}} =\cdots = \\ & \frac{{\left( {1 - {\rho _{{j_l}}}} \right){d_{{j_l}}}f_{{j_l}}^{\rm{O}}}}{{f_{_{{j_l},m}}^2}}. \end{split} $

基于上述分析，得到如下优化算法.

1）初始化所有变量，平均分配所有的资源.

2）根据定理1获得用户关联方案.

3）根据定理2求解卸载决策.

4）分别优化与资源分配有关的变量$ {l}_{k,s}^{\rm{U}}、 {l}_{k,s}^{\rm{D}}、{p}_{k,s}、{f}_{k,s} $. 这些变量可以并行优化. 使用凸优化工具包优化变量$l_{k,s}^{\rm{U}}$ $ {l}_{k,s}^{\rm{D}}、{p}_{k,s} $. 根据定理3求解变量${f_{k,s}}$.

5）重复步骤2）~4）直到给定循环步数$I$.

通过上述步骤，可以逐步优化得到用户关联、卸载决策和资源分配方案，完整的过程描述如下.

算法 1　边缘计算策略优化

1. 初始化所有优化变量${a_{k,s}}、{\rho _k}、l_{k,s}^{\rm{U}}、l_{k,s}^{\rm{D}}、$${p_{k,s}}、{f_{k,s}}$并指定循环次数$I$

2. For iter = 1∶I

3. 优化用户关联，根据定理1选择时延代价最小的基站

4. 优化卸载决策，根据定理2获得卸载决策

5. 优化资源分配，用凸优化工具包优化上行频谱分配、优化功率分配和下行频谱分配，根据定理3解决算力分配问题

6. end for

本研究提出的算法复杂度主要体现在各个子问题的优化中，主要考虑算法的最大迭代次数. 算法的最大迭代次数为$I$，在实际的仿真过程中，$I$=5时算法基本能够收敛. 在用户关联子问题中，每个用户须在考虑信道和算力的情况下与一个基站关联，每个用户须轮询所有基站，因此复杂度为$O(KS)$. 在卸载分配子问题中，由于该问题存在闭式解，其复杂度是一个常数，为$O(1)$，在资源分配子问题中，功率和频谱的优化通过内点法解决，内点法的最大迭代次数为$O(\sqrt {KS} \log\; ({\varepsilon ^{ - 1}}))$，其中$\varepsilon $为算法的精度，算力优化针对每个基站也拥有闭式解，复杂度为$O(S)$. 因此，本研究提出的算法总复杂度为$O(I(KS+\sqrt {KS} \log\; ({\varepsilon ^{ - 1}})+S+1))$，也即$O(I(\max \;(KS, \sqrt {KS} \log\; ({\varepsilon ^{ - 1}}))))$.

考虑由多终端和多基站组成的多层边缘计算网络系统，终端具有可分解的任务，且可以将任务卸载到基站进行计算. 在计算时延参数设置上，考虑3 km$ \times $3 km区域内有[10,50]的终端，基站数量为4，假定终端的计算能力是1×10¹⁰ ${\mathrm{cycle}}/{{\mathrm{s}}}$，基站的计算能力为2×10¹¹ ${\mathrm{cycle}}/{{\mathrm{s}}}$，终端要处理的任务量是$[20,80]$ ${\mathrm{Mb}}$的一个随机数. 在通信参数的设置上，假设无线信道带宽为B，终端的最大发射功率$P = $23 dBm，对应的噪声功率谱密度为${N_0} = - 174$ dBm/Hz，无线信道中大尺度衰落的模型为$ - 128.1 - 37.6 \times {\lg }\;d $，$d$表示终端和基站之间的距离，小尺度衰落满足瑞丽分布.

资源分配是边缘计算网络中非常重要的一环，对于基站来说，不与之关联的终端可以不分配相关的资源，而与之关联的终端需要合理分配资源. 因此本研究将所提算法与以下的方法进行比较.

1）算法1：本研究所提出的算法，即资源分配（包括上行、下行频谱和功率）、算力优化和用户关联均须解决；

2）算法2：无线资源平均分配，但是保持用户关联优化、算力优化；

3）算法3：无线资源以及用户关联进行优化，但是算力是平均分配；

4）算法4：无线资源平均分配、用户随机关联，但是算力优化；

5）算法5：全部的变量都是随机或者平均分配.

在上述的几种方法中，为了控制变量，卸载决策均须优化，只关注资源分配.

本研究验证了带宽资源为5 ~100 MHz的不同方案下的时延性能. 仿真得到的结果如图3所示. 其中，$B$ 为带宽资源，$T$为系统时延. 从仿真结果可以发现，算法1是最优的，说明用户关联、无线资源分配、算力分配都是非常重要的. 但是同样，算法2、3的优化结果也十分接近本研究提出的方案，这是因为只优化算力资源和无线频谱资源其中之一也能逼近最低的时延. 如果算力和资源均不加以优化（算法4），则会使得时延变得较大. 随着带宽资源的增加，经过优化的整体时延也会下降，但在全随机分配的资源中，也可能会出现时延增加的情况. 所以，在实际场景中，如果终端运算能力充足，须对无线资源、算力同时进行优化，以达到最低的时延，但是当终端的运算能力受限时，可以平均分配其中之一的资源来优化另一个资源的分配.

将联合优化中常用的启发式算法和近似算法与本研究提出的方法进行比较.

1） GA：模拟自然进化过程的优化算法，属于启发式搜索算法. 通过模拟物种在自然界中的生存竞争、繁殖和变异过程，逐步优化问题的解.

2） SQP：通过二次近似来解决非线性优化问题. 在每次迭代中，SQP会利用当前迭代点的信息，构造一个局部的二次近似问题，并求解该二次问题得到一个新的搜索方向. 然后，将该方向应用于当前的解，得到新的迭代点，直到收敛到一个最优解为止.

仿真结果如图4、5所示. 其中，${\mathrm{TP}}$为吞吐量，可以看出，传统的启发式算法或是近似迭代的优化算法在优化变量多的时候无法保证次优解的质量，在带宽资源变多时，反而由于解的质量较差，时延没有降低.

卸载决策是终端根据任务量、自身算力和基站算力的情况将自身的部分任务发送到基站进行处理.

当基站的算力充足时，终端会将几乎整个的任务都发送到基站，此时，终端几乎不处理任务. 因此，考虑基站算力缺乏时，将本研究的算法与以下策略进行比较.

1）算法1：本研究所提出的算法；

2）算法6：计算任务只在本地进行；

3）算法7：计算任务只在基站进行.

进一步的，设置不同的带宽和不同的基站算力来进行验证.

对于算法6，由于计算任务只在本地进行，整体的时延不受基站算力和无线频谱资源的影响，通过公式可以计算得到在如上的配置下，只在本地进行计算任务需要897.33 s，是个定值. 如图6、7所示，其中${{{F_s}}}/{{{f_k}}}$表示基站/用户算力比，分别为不同卸载决策下的时延、吞吐量对比. 可以看出，算法1由于综合利用了终端的算力资源和基站的算力资源，能够达到最小的时延，另外，随着服务器端算力以及通信带宽增加，算法1与只在基站端的算法7近似，这是因为此时通信不是主要的瓶颈，本地算力才是主要的瓶颈. 反之，所提出的算法趋近于只在本地计算，此时，服务器端计算没有很大的优势，且计算卸载带来的额外的通信开销成为主要的瓶颈. 如表1所示，测试了基站算力小于用户的极限情况下，3种不同方案下的时延. 在相同的条件下，随着服务器端可用算力增加，所提出的算法的时延也会降低，反之增大.

用户关联是终端与基站的配对情况，用户关联决定了优化的上限，因此合理的用户关联才能保证资源和算力的最优分配.

本研究提出的用户关联方案是基于信道和算力综合考量的. 为了验证本研究提出的用户关联方案的有效性，考虑以下几组方式：

1）算法1：本研究提出的用户关联策略；

2）算法8：只基于信道质量进行用户关联；

3）算法9：只基于算力进行用户关联；

4）算法10：随机用户关联.

在以上的几组方式中，所有的资源以及卸载的策略都须优化，且使用相同的算法. 进一步的，在用户数量分别为10、20、30的情况下测试不同关联方案的时延. 如图8、9所示为不同用户关联下的时延、吞吐量对比. 可以看出，其中$K$为终端数量，算法1的性能是最优的. 另外传统的根据信道选择因为忽略了不同基站可以使用的算力（算法8），而无法获得最优的性能，根据算力的关联算法9也一样，信道质量在通信系统是不能忽略的.

在多层边缘计算网络中，终端计算任务时延的优化不仅要考虑终端和基站的关联，还要考虑到终端的任务卸载和整体的资源分配. 为了解决该问题，本研究面向多层边缘计算网络，提出联合用户关联、任务卸载和资源分配的优化策略，有效降低了终端的计算时延. 此外，通过大量仿真验证了资源分配、任务卸载和用户关联在边缘计算网络中的重要作用. 实验结果证明，本研究所提出的基于信道质量和算力的用户关联决策能够在多层边缘计算网络中更好地进行终端、基站配对和性能优化. 考虑到能耗同样是边缘计算中较为重要的性能指标，将在后续的研究中同时考虑时延和能耗性能，并引入多连接概念，探讨并设计此场景下的性能优化算法.