1.   引言

当今社会科技革命和产业变革突飞猛进，物联网(Internet of Things,IoT)的飞速发展催生了数以亿计的移动智能应用，例如自动驾驶、增强现实、视频业务等^[1,2]。由于有限的计算能力和电池容量，用户的移动设备无法满足这些智能应用的计算需求^[3]。

移动云计算(Mobile Cloud Computing, MCC)将本地计算任务卸载到远程云服务器中以扩展移动设备的计算能力^[4]。但受限于主干链路的容量限制和网络波动，MCC常会导致额外的传输延迟和能量损耗，这严重降低了卸载效率^[5]。 因此雾计算(Fog Computing, FC)作为云计算的延伸应运而生，它既具备较强的计算存储能力又更靠近终端层网络，缓解核心网络压力的同时极大地提高了服务质量(Quality of Service, QoS)和资源利用率^[6]。

在面临交通拥堵、大型集会等场景时，由于移动用户计算任务的区域性激增，会导致局部网络拥塞和服务器过载，从而产生额外的丢包率和计算时延，甚至出现服务器单点失效现象^[7]。而服务器集群技术可以在付出较低成本的情况下获得在性能、可靠性、灵活性方面的较高收益，任务调度则是集群系统中的核心问题。如何有效规划任务调度策略和资源管理，既维持整体系统的负载均衡又保证用户时延和能耗最小化，这也是本文研究的重点之一。

近年来，已有许多学者对云雾系统中的卸载决策和资源分配问题进行了研究。文献[8]研究了基于雾计算的软件定义嵌入式系统，设计了一种结合系统存储容量的任务调度策略，尽量减少用户计算任务的完成时间。文献[9]考虑了雾服务提供商的成本，在执行时间阈值和用户优先级的约束下讨论了时延最小化问题。文献[10]提出效用函数和功耗的加权和问题，结合了交替方向乘子法和近端最小化算法将全局问题分解为多个子问题，实现了系统目标函数最小。文献[11]研究了雾环境下负载均衡的动态资源分配问题，通过静态资源分配和动态服务调度实现了雾计算系统的负载均衡。文献[12]研究了云边网络中时间能耗加权和最小化问题，提出两种算法分别优化计算频率、发射功率以及匹配策略，实现了系统效用函数最小化。但是，上述研究主要集中在传统云雾场景下对单因素或双因素的优化，均未考虑利用集群技术及集群间的协作模式解决计算任务区域性激增时多用户多节点的时延、能耗和负载均衡综合问题。针对上述问题，本文贡献如下。

(1) 在3层云雾混合计算模型中，通过联合优化计算资源、通信资源和任务调度策略，提出了SLEC (System Latency-Energy Cost)最小化问题。在硬约束条件下，通过集群协作模式实现负载均衡的同时满足系统时延和能耗加权和最小化。

(2) 由于各变量的复杂耦合，上述问题是一个混合整数非线性规划问题，无法直接求解。首先将原问题进行分解，经理论证明后通过库恩塔克(Karush-Kuhn-Tucker, KKT)条件和二分搜索迭代法分别优化计算和通信资源分配。然后提出基于分支定界的开销最小化卸载算法来寻找最优的任务调度策略。最终通过迭代资源分配结果和卸载决策达到全局最优解，实现最小化系统时延能耗加权和。

(3)实验结果表明，本文所提集群协作架构与传统计算方案相比具有显著优势，本文所提算法能够获得更低的时延和能耗，具有良好的收敛性。

2.   系统模型

本文提出一个基于集群协作的云雾混合计算模型，如图1所示由3层网络架构组成。

图 1  基于集群协作的云雾混合计算模型

下载: 全尺寸图片 幻灯片

其中终端用户层包含$U$个用户，由$\mathcal{U} = \left\{ {1,2, \cdots ,U} \right\}$表示。$N$个具有计算和存储能力的分布式雾集群共同构成雾层，表示为$\mathcal{N} = \left\{ {1,2, \cdots ,N} \right\}$。每个雾集群(Fog Cluster, FC)由负载控制器(Load Controller, LC)和多个具有计算存储能力的网络边缘设备(如路由器、微基站、智能车辆、交换机等)构成。每个FC都有一个覆盖区域，用户层被$N$个FC完全覆盖且覆盖区域彼此没有重叠。集中式云服务器${\text{d}}$构成云层，它通过广域网(Wide Area Network, WAN)与雾层中各个FC形成稳定的双向链路。

雾集群协作(Fog Cluster Collaboration, FCC)指的是当本集群计算任务负载过大时将部分任务通过LC迁移至另一集群进行协作并行计算，此模式有利于实现全局负载均衡。LC能够收集全局信息并且负责接收和转发计算任务，各集群中的LC端到端链接形成算力调节网络，从而实现FCC模式。假设云雾混合计算架构在任务迁移过程中是准静态模式^[13]，且传输时的信道状态和网络拓扑结构是固定的。

2.1   计算模型

定义用户$u \in \mathcal{U}$的计算任务为${\text{Ap}}{{\text{p}}_u}$，各用户的任务之间不存在依赖性且计算任务是不可分割的。用户$u$的任务属性由数组对表示为${\text{Ap}}{{\text{p}}_u} = \left\langle {{L_u},{C_u}} \right\rangle$，其中${L_u}$(bit)代表任务数据量，包含任务类别和指令代码等参数，${C_u}$(megacycle)代表完成此任务需要的CPU周期数。

(1)本地计算模型：指计算任务在用户端由移动设备自行处理。各用户具有不同的计算能力，用户$u$在本地计算的时间为

根据文献[1,14]，移动设备CPU的功耗是关于计算频率的超线性函数，表示为$P_u^{\text{l}} = {\kappa^{\text{l}}} \cdot {\left( {f_u^{\text{l}}} \right)^\phi }$，$P_u^{\text{l}}$为用户$u$的本地计算功耗，本文中$\phi$取2。所以用户在本地计算的能耗为

其中，$f_u^{\text{l}}$表示移动设备$u$的计算能力。${\kappa^{\text{l}}}$是设备能量转换系数，本文中设置${\kappa^{\text{l}}} = {10^{ - 6}}$。

(2)卸载计算模型：卸载计算包含雾计算和云计算。雾计算指计算任务被卸载至雾层并由其中一个雾集群执行。云计算是将任务交由集中式云服务器${\text{d}}$计算。假设每个雾集群的计算资源被所有卸载到此集群的用户所共享，定义雾集群$n$的最大承载计算能力为${F_n}$。雾计算模式下，用户$u$的任务在集群$n$的计算时延和能耗为

其中，$f_u^{n,{\text{e}}}$表示雾集群$n$分给移动用户$u$的计算频率，${\kappa^{\text{e}}}$为能量转换系数。当启动云计算模式时，用户$u$的计算任务在云服务器${\text{d}}$的执行时间为

如文献[15]，在云计算模式下本文不考虑中心云服务器产生的计算能耗。由于云服务器具有强大的计算能力，能够为用户提供充足的算力，因此如文献[16]一样，本文云服务器的计算频率是固定的，即不考虑对选择云计算模式的用户进行资源配置。

2.2   通信模型

本文将任务留在本集群中计算的模式命名为近端卸载(Proximal Offloading, PO)，这种模式节省了额外的传输时间。若用户所在集群的任务累积负载较大，集群中的LC会将部分任务迁移到轻负载集群执行以实现全局负载均衡这种模式命名为远端卸载(Remote Offloading, RO)。所有的计算节点用$S = \left\{ 0 \right\} \cup \left\{ {1,2, \cdots ,N,N + 1} \right\}$表示，其中$0$代表用户的移动设备，$1,2, \cdots ,N$表示$N$个雾集群，$N + 1$为集中式云服务器。式(6)定义2元决策变量${b_{u,s}} \in \left\{ {0,1} \right\}$为用户的任务执行策略。

(1)近端卸载：通过无线信道将任务上传至区域内的LC中，然后由LC传输至本集群内具有计算能力的网络边缘设备中执行。定义$K\left( n \right) = \displaystyle\sum\nolimits_{u = 1}^U {{b_{u,n}}}$为集群$n$中需要卸载的用户数，总带宽${{B}}$被$K(n)$个卸载用户均分。为了避免任务上传时集群内的用户间干扰，采用正交频分多址(Orthogonal Frequency Division Multiple Access, OFDMA)技术进行正交子信道分配。因此用户$u$的信息传输速率可以表示为

其中，$p_u^t$代表用户$u$的上传功率。${{{H}}_u}$是用户$u$与负载控制器的无线信道增益，${{B}}$和${{{N}}_{\text{0}}}$分别为信道总带宽和噪声功率密度。在近端卸载模式下，用户$u$的任务传输能耗和时间分别为

类似于文献[16,17]，由于计算任务的输出数据量远小于任务的输入数据量，本文不考虑计算输出结果的回传时间和能耗开销。

(2)远端卸载：假设FC之间的数据传输速率是固定的，用$R_n^{n'}$表示。FC与集中式云服务器${\text{d}}$间的传输速率为$R_n^{\text{d}}$。所以用户$u$的计算任务由集群$n$迁移至集群$n'$和云服务器${\text{d}}$的时延分别为

综上所述，考虑到用户任务的计算模型、通信模型和卸载策略，在基于集群协作的云雾混合计算中用户$u$的计算任务总执行时间和总能耗分别为

3.   问题构建

本文提出联合计算、通信资源分配和任务调度策略的优化模型，在考虑系统负载均衡的同时满足时延和能耗开销(System Latency-Energy Cost, SLEC)最小化。

定义1　${\text{SLEC}}$是用户在任务调度决策下执行某种计算方式(本地计算、雾计算或者云计算)时产生的时延和能耗加权和，表示为${\text{SLE}}{{\text{C}}_u} = {\alpha _u} \cdot T + {\beta _u} \cdot E$。${\alpha _u} \in [0,1]$和${\beta _u} \in [0,1]$是权重因子，分别用来衡量用户$u$对任务完成时间和能量消耗的偏好。

定义2　${L_n} = \displaystyle\sum\nolimits_{u = 1}^U {{b_{u,n}}{C_u}}$为集群$n$的负载量，表示集群内用户计算量的总和。${\text{LBD}}$为负载均衡度(Load-banlancing Degree, LBD)，它由系统中各集群任务负载量方差的倒数表示，其值越小代表负载分配越均衡。${\text{LBD}} = {N/ {\displaystyle\sum\nolimits_{n = 1}^N {{{[{L_n} - \overline L ]}^2}} }}$，其中$\overline L$代表雾集群的平均负载值。

本文负载均衡的实现采用分布式策略，在集群可承载计算总量和用户数阈值的约束下，通过负载控制器的预处置寻求全局最优雾节点，从而实现系统LBD最小化。LC从用户层接收任务描述，根据各用户任务计算量的大小，将任务映射到雾层最佳可用资源上实现网络路由和资源管理，最终执行雾集群的选择，实现负载均衡的同时满足系统时延和能耗最小化。

本文目的是从资源分配和负载均衡两个角度出发，联合优化${p_u}$, $f_u^{n,{\rm{e}}}$和卸载决策${b_{u,s}}$从而使整个系统的${\text{SLEC}} = \displaystyle\sum\nolimits_{u = 1}^U {{\text{SLE}}{{\text{C}}_u}}$最小化。基于此构建了一个联合资源分配和负载均衡(Joint Resource Allocation and Load Balance, JRALB)模型来表示SLEC最小化问题

其中，${\mathcal{U}}_{\mathcal{O}}=\{1,2,\cdots ,{U}_{\text{off}}\}$是所有选择卸载计算的用户集合，${F_n}$表示雾集群$n$正常负载状态的计算资源阈值，${\text{Ca}}{{\text{p}}_n}$表示雾集群$n$能够容纳的最大用户数。${\text{C}}1$和${\text{C}}2$确保每位用户只能选择一种计算方式。${\text{C}}3$保证了雾集群$n$的计算资源分配总和不会导致其进入过载状态。${\text{C}}4$规定了卸载过程中传输功率的上下阈值。${\text{C}}5$表示雾集群服务的用户数必须在其容纳范围内。

4.   问题分解

根据目标函数${\text{OPT}} - 1$及其约束条件可以看出JRALB是一个混合整数非线性规划问题(Mixed-Integer NonLinear Programming, MINLP)，它是非确定多项式难度(Non-deterministic Polynomial hard, NP-hard)问题且难以直接求解。由于优化变量间互不耦合，因此将JRALB问题分解为两个独立的子问题：资源分配和卸载决策

4.1   资源分配

本节在特定的卸载策略下对资源分配问题即最佳计算频率$f_u^{n,{{\text{e}}^ * }}$和最优传输功率$p_u^{{t^ * }}$进行优化。只有当用户选择卸载计算时资源分配问题成立，所以 JRALB问题又可以表示为

将式(3)、式(4)和式(8)—式(10)代入式(16)，问题${\text{OPT}} {\text{-}} 2$可被转化为

由式(17)可以看出，$f_u^{n,{\text{e}}}$和$p_u^t$是独立的，且约束${\text{C}}3$和${\text{C}}4$也是互不耦合的。本文选择用二分搜索迭代法和KKT条件分别求解最佳的传输功率$p{_u^{t^*}}$和计算频率$f{_u^{n,{\text{e}}^*}}$。

(1)计算频率分配：LC分配给用户$u$的最佳计算频率$f_u^{n,{{\text{e}}^ * }}$通过优化子问题${\text{OPT}} - 3$得到

令${\mu _u} = {\alpha _u}{C_u}$, $\delta _u^n = {{{\alpha _u}{L_u}} \mathord{\left/ {\vphantom {{{\alpha _u}{L_u}} {R_n^{n'}}}} \right. } {R_n^{n'}}}$, ${\theta _u} = {\beta _u}{{\kappa}^{\text{e}}}{C_u}$，则$g\left( {f_u^{n,{\text{e}}}} \right) = \dfrac{{{\mu _u} + \delta _u^nf_u^{n,{\text{e}}} + {\theta _u}(f_u^{n,{{\text{e}}}})^2}}{{f_u^{n,{\text{e}}}}}$。通过计算$g\left( {f_u^{n,{\text{e}}}} \right)$关于$f_u^{n,{\text{e}}}$的2阶导，可得到${{{\partial ^2}g}/{\partial {{(f_u^{n,{\text{e}}})^2}}}} = \left( {{{2{\mu _u}} \mathord{\left/ {\vphantom {{2{\mu _u}} {f_u^{n,{{\text{e}}^3}}}}} \right. } {(f_u^{n,{{\text{e}}}})^3}}} \right) > 0$且${{{\partial ^2}g} \mathord{\left/ {\vphantom {{{\partial ^2}g} {\partial f{{_r^m}^2}}}} \right. } {\partial {{(f_r^m)}^2}}} = 0\;\left( {u,n \ne r,m} \right)$。

由此得出子问题${\text{OPT}} {\text{-}} 3$是一个凸优化问题，本文采用KKT条件来优化计算频率分配问题。令${\mathcal{U}_n}$表示卸载到雾集群$n$的用户集合，式(18)的拉格朗日函数为

设$h(f_u^{n,{\text{e}}}) = {F_n} - \displaystyle\sum\nolimits_{n = 1}^N {{b_{u,n}} \cdot f_u^{n,{\text{e}}}}$，其中${\boldsymbol{\rho }} = \left[ {\rho _1},{\rho _2}, \cdots, {\rho _n} \right]^{\text{T}}$为拉格朗日乘子向量且${\boldsymbol{\rho }} \in {\mathbb{R}^ + }$。

定理1(KKT条件)：若$f{_u^{n,{\text{e}}^*} }$是子问题${\text{OPT}} - 3$的局部极小值，有效约束集是${\boldsymbol{I}}(f{_u^{n,{\text{e}}^*} }) = \{ i|{h_i}(f{_u^{n,{\text{e}}^*} }) = 0, i = 1,2, \cdots ,N\}$，并设$g(f_u^{n,{\text{e}}})$和${h_i}(f_u^{n,{\text{e}}})$在$f{_u^{n,{\text{e}}^*} }$处可微。若向量组$\nabla {h_i}(f{_u^{n,{\text{e}}^*} })(i \in {\boldsymbol{I}}(f{_u^{n,{\text{e}}^*} }))$线性无关，则存在向量${{\boldsymbol{\rho }}^ * } = {(\rho _1^ * ,\rho _2^ * , \cdots, \rho _n^ * )^{\text{T}}}$使得

所以通过${\text{OPT}} - 3$解得在卸载计算模式下雾集群$n$分配给用户$u$的最优计算频率$f{_u^{n,{\text{e}}^*} }$为

(2)用户上行传输功率：通过最小化${\text{OPT}} {\text{-}} 4$可以得到用户$u$的最优传输功率$p{_u^{t^*} }$

令$y(p_u^t) = \dfrac{{\eta _u^n + \chi _u^np_u^t}}{{{{\log }_2}(1 + \varepsilon _u^np_u^t)}}$，其中$\eta _u^n = \dfrac{{{\alpha _u}{L_u}K(n)}}{{{B}}}$, $\chi _u^n = \dfrac{{{\beta _u}{L_u}K(n)}}{{{B}}}$, $\varepsilon _u^n = \dfrac{{K(n){{{H}}_u}}}{{{{B}}{{{N}}_{\text{0}}}}}$。在文献[1]中已证明优化目标$y(p_u^t)$为拟凸函数，因此可以采用二分搜索法解决拟凸优化问题，保证每个用户得到最优的上行传输功率，如算法1所示。其中$s(p_u^t)$为$y(p_u^t)$1阶导数的分子项。

算法1　基于二分搜索迭代法的传输功率分配算法
初始化：传输功率范围0、$p_u^{\max }$，收敛阈值$\gamma$
(1) 根据式(23)计算$s(p_u^{\max })$
(2) if $\,s(p_u^{\max }) \le 0\,$ then
(3) 　$p{_u^{t^*} } = p_u^{\max }$
(4) else
(5) 　初始化参数$p_u^{\text{v}} = 0,p_u^{\text{r}} = p_u^{\max }$
(6) 　　$p_u^{\text{l}} = {{(p_u^{\text{v}} + p_u^{\text{r}})} \mathord{\left/ {\vphantom {{(p_u^{\text{v}} + p_u^{\text{r}})} 2}} \right. } 2}$
(7) 　　if $\,s(p_u^{\text{l}}) \le 0$ then
(8) 　　　$p_u^{\text{v}} = p_u^{\text{l}}$
(9) 　　else
(10) 　　　$p_u^{\text{r}} = p_u^{\text{l}}$
(11) 　　end if
(12) until $\,(p_u^{\text{r} } - p_u^{\text{v} }) \le \gamma \,$
(13) 　　$p_u^{\max } = {{(p_u^{\text{r}} + p_u^{\text{v}})} \mathord{\left/ {\vphantom {{(p_u^{\text{r}} + p_u^{\text{v}})} 2}} \right. } 2}$

下载: 导出CSV 

| 显示表格

如算法1所述，每一轮迭代中更新$s(p_u^t)$的值直至达到收敛阈值。由于$s(p_u^t)$是单调递增函数且起始点是负值，因此算法1在每次迭代中只需评估$s(p_u^t)$的值，若$s(p_u^t) > 0$则算法将以${\log _2}({{p_u^t} \mathord{\left/ {\vphantom {{p_u^t} \gamma }} \right. } \gamma })$次迭代终止。因此与传统二分法类似，算法1的复杂度为$O({\log _2}({{p_u^t} \mathord{\left/ {\vphantom {{p_u^t} \gamma }} \right. } \gamma }))$。通过算法1的输出可以获得在特定的卸载策略下用户$u$的最佳上行传输功率。

4.2   任务调度决策

本节将在上述资源分配的结果下，推导最佳的用户任务卸载策略。首先提出卸载决策子问题${\text{OPT}} {\text{-}} 5$

通过${\text{OPT}} {\text{-}} 5$可以看出，在4.1节得到最优资源分配结果后，式(14)中的原问题${\text{OPT}} {\text{-}} 1$变成一个关于${b_{u,s}}$的0～1整数线性规划(Integer Linear Programming, ILP)问题。参考文献[17]中的方法，本文提出基于分支定界的开销最小化卸载算法(Branch and Bound based Overhead Minimum Offloading Algorithm, BB-OMOA)解决任务调度问题${\text{OPT}} {\text{-}} 5$。

(1)松弛(Slack)：将卸载决策问题${\text{OPT}} {\text{-}} 5$中的整数约束${\text{C}}1$替换为式(24)中的新约束

此时原整数线性规划问题就变成了线性规划(Linear Programming, LP)问题$\widetilde {{\text{OPT}}} {\text{-}}5$，得到的新问题$\widetilde {{\text{OPT}}} {\text{-}} 5$称为${\text{OPT}} {\text{-}} 5$的松弛问题。

(2)分支(Branch)：利用内点法直接对松弛问题$\widetilde {{\text{OPT}}}{\text{-}} 5$进行求解，设${\text{SLE}}{{\text{C}}^ * }$为求得的最优值，${{\boldsymbol{b}}^ * }$为优解$b_{u,s}^ *$的集合。在${{\boldsymbol{b}}^ * }$中选取最大值的非整数变量${b_j}$添加为约束条件进行分支操作。设变量${b_j}$的值为${v_j}$，构造两个约束条件${b_j} \le \left\lfloor {{v_j}} \right\rfloor$和${b_j} \ge \left\lfloor {{v_j}} \right\rfloor + 1$，其中$\left\lfloor {{v_j}} \right\rfloor$为小于${v_j}$的最大整数。将这两个条件分别加入松弛问题$\widetilde {{\text{OPT}}} {\text{-}} 5$中，从而将$\widetilde {{\text{OPT}}} {\text{-}} 5$分为两个子问题${\widetilde {{\text{OPT}}}_1} {\text{-}} 5$和${\widetilde {{\text{OPT}}}_2} {\text{-}} 5$。然后不考虑整数条件约束，分别求解这两个子问题。

(3)定界(Bound)：以每个子问题为一分支并标明求解的结果，与其他问题的解进行比较，找出最优目标函数值最小者作为新的下界替换松弛问题$\widetilde {{\text{OPT}}} {\text{-}} 5$的解${\text{SLE}}{{\text{C}}^ * }$，记为${\tilde L_{{\text{lower}}}}$；从符合整数条件的各分支中，找出目标函数值最小者作为新上界，记为${\tilde L_{{\text{upper}}}}$。

(4)剪支(Shear)：各分支的最优目标函数值中若有大于${\tilde L_{{\text{upper}}}}$者，则剪掉这一分支；若小于${\tilde L_{{\text{upper}}}}$且不符合整数条件，则重复迭代上述操作，直至得到最优目标值${L^ * }$和对应的整解${\boldsymbol{b}}_j^ *$。

由算法2可知，在约束条件下若分支之间不存在任何优先关系，所有分支均不能减去。所以在最坏情况下，第j层中进行分支的节点数为$C_{N - 1}^j$，所以分支总数为$\displaystyle\sum\nolimits_{j = 0}^{N - 1} {C_{N - 1}^j} = {2^{N - 1}}$，因此在最坏情形下BB-OMOA算法的复杂度为$O({2^{N - 1}})$。

算法2　BB-OMOA
初始化：用户任务及系统参量，最优计算频率$f{_u^{n,{\text{e} }^*} }$，最优功率 　$p_u^{t^*}$，用户集合$U$，雾集群组$N$，求解精确度${\text{η }}$
(1) for $u = 1,2, \cdots ,U$ do
(2) 　求解松弛问题$\widetilde { {\text{OPT} } } {\text{-}} 5$，得${\mathbf{b}}$和${\tilde L_{{\text{lower}}}}$
(3) 　if ${b_{u,s}} \in Z,\forall u \in U$then
(4) 　　现行解${{\mathbf{b}}^ * }$即为最优解
(5) 　else
(6) 　　挑选不符合整数条件的变量${b_j}$构造约束${b_j} \le \left\lfloor {{v_j}} \right\rfloor$和 　　　　 ${b_j} \ge \left\lfloor {{v_j}} \right\rfloor + 1$进行分支形成子问题
(7) 设定待更新上下界${\tilde L_{{\text{lower}}}}$和${\tilde L_{{\text{upper}}}}$
(8) while ${\tilde L_{{\text{upper}}}} - {\tilde L_{{\text{lower}}}} > {\text{η }}$ do
(9) 　if 子问题${\widetilde { {\text{OPT} } }_i} {\text{-}} 5$有可行解
(10) 　　if ${\tilde L_i} \ge {\tilde L_{{\text{lower}}}}$且${\tilde L_i} \le {\tilde L_{{\text{upper}}}}$
(11) 　　　令${\tilde L_i}$为新的下界，即${\tilde L_{{\text{lower}}}} = {\tilde L_i}$
(12) 　　　回到步骤(6)迭代分支定界操作
(13) 　　else if ${\tilde L_i}$对应解的各分量都是整数then
(14) 　　　return ${\tilde L_{{\text{lower}}}}$
(15) 　　else 进行剪支操作舍弃这一子问题
(16) 　　end if
(17) 　else 进行剪支操作舍弃这一子问题
(18) 令${\tilde L_i}^ * = \min \{ {\tilde L_{{\text{lower}}}}|i \in {N_ + }\}$
(19) $\tilde L_i^ *$为式(26)最优值${L^ * }$，对应解即最优策略${{\mathbf{b}}^ * }$。

下载: 导出CSV 

| 显示表格

5.   仿真分析

本节提供数据结果在云雾混合计算模型中评估文中所提BB-OMOA算法。假定有多个具有计算任务的用户，多个内置LC和边缘设备的FC以及1个集中式云服务器。本文假设移动设备和雾集群之间的无线信道增益遵从瑞利随机衰落，带宽被同一区域内的用户平均分配，系统的其余仿真参数如表1所示。

表 1  仿真参数

参数	数值
系统带宽$B\left(\mathrm{M}\mathrm{H}\mathrm{z}\right)$	20
任务数据量$L\left(\mathrm{M}\mathrm{b}\mathrm{i}\mathrm{t}\right)$	0.1～0.5
任务所需CPU周期数$C\left(\mathrm{M}\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\right)$	500～2500
本地计算能力${f}_{u}^{\rm{{l}}}\left(\mathrm{G}\mathrm{H}\mathrm{z}\right)$	0.5～1.5
噪声功率谱密度${N}_{0}(\mathrm{d}\mathrm{B}\mathrm{m}/\mathrm{H}\mathrm{z})$	–174
最大传输功率${p}_{u}^{\mathrm{m}\mathrm{a}\mathrm{x}}\left(\mathrm{d}\mathrm{B}\mathrm{m}\right)$	25
雾集群最大计算能力${F}_{n}\left(\mathrm{G}\mathrm{H}\mathrm{z}\right)$	15～25
中心云总计算能力${f}_{{\rm{d}}}\left(\mathrm{G}\mathrm{H}\mathrm{z}\right)$	50

下载: 导出CSV 

| 显示表格

图2在不同的任务量下将本文所提BB-OMOA算法与文献[14]中的MDPCO算法、本地计算方案(Only Local Execution Sheme, OLES)和云计算方案(Only Cloud Execution Sheme, OCES)进行了比较。假设各用户的本地计算能力和任务量均有差异，仿真时在给定范围内随机取值。时延偏好因子${\alpha _u}$和能耗偏好因子${\beta _u}$均设为0.5。由图2可以看出随着用户任务量${C_u}$的不断增大，4种方案中SLEC的数值均逐渐上升，但本文提出的BB-OMOA算法始终优于其他3种方案。MDPCO算法虽明显优于OLES和OCES，但其值始终低于本文所提算法。由于移动设备有限的计算和存储能力，当任务量增多时OLES方案中的SLEC数值几乎呈线性增长。虽然集中式云服务器地理位置较远、传输速率较低，但得益于其强大的运算速度，OCES方案中的SLEC数值始终低于本地计算方案且较为稳定。

图 2  用户任务量与SLEC的关系

下载: 全尺寸图片 幻灯片

图3显示了用户卸载决策与任务量的关系。在给定用户总数$U$的情况下，随着系统负载的上升，选择本地计算的用户数逐渐下降，其原因在于移动设备较弱的计算能力会引起SLEC的急剧增大。当任务量增加到一定程度时，部分用户选择将任务卸载到云服务器上。但60%～80%的用户还是利用集群协作模式将任务迁移到轻负载集群中以实现SLEC最小化。图4描述了不同方案下系统负载与总开销SLEC的关系。将本文提出的BB-OMOA算法与文献[15]中的任务卸载及资源分配联合(Joint Task Offlfloading and Resource Allocation, hJTORA)算法和文献[18]中的随机布置方案展开了对比。因为本文的系统模型中启用了分布式雾集群协作，可以将任务自适应迁移到轻负载节点执行，提高了服务器的响应速度和网络吞吐量，所以BB-OMOA的系统开销始终低于另两种方案，证明了本文模型和算法的优越性。

图 3  任务量与用户分布的关系

下载: 全尺寸图片 幻灯片

图 4  系统负载与SLEC的关系

下载: 全尺寸图片 幻灯片

图5表示权重因子对系统时延能耗开销的影响。随着时延权重因子${\alpha _u}$的增大，OLES和OLCS方案中的系统总开销SLEC呈现出完全相反的走势。系统SLEC在纯本地计算方案中线性增大，而在云计算方案中不断下降。所提BB-OMOA算法的整体表现优于其他两种方案，当${\alpha _u}$<0.38时，BB-OMOA算法的SLEC表现更靠近本地计算方案，这反映了延迟不敏感应用更倾向于在本地执行；当${\alpha _u}$>0.38时，所提算法的SLEC趋势向云计算方案贴近，这说明为了节省时间更多的时延敏感型任务被卸载到雾层和云层执行。

图 5  权重因子与SLEC的关系

下载: 全尺寸图片 幻灯片

本文的出发点是在利用服务器集群技术在集群协作模式下考虑负载均衡且保证系统SLEC最小化。为了验证本文所提架构的有效性，在图6中与传统卸载方案进行了对比。考虑有10个具有计算任务的用户，每位用户可以选择本地计算、雾计算或云计算。雾集群个数固定为5，雾集群的总计算能力如表1范围设置。为了模拟实际场景中负载失衡的情况，每个雾集群覆盖范围内的用户数及其任务量设置有明显差异。由图6(a)和图6(b)可以看出若不启用集群协作，系统明显处于失衡状态，此时会因为任务拥塞而导致执行时间延长、丢包率上升、资源浪费、服务器单点失效等情况发生。而本文架构充分利用周围集群闲置计算资源，重负载集群的任务被迁移至轻负载节点执行从而实现系统负载均衡。结合图6中数据得出${\text{LBD}}(a) = 0.7137 < {\text{LBD}}(b) = 2.4739$，说明集群协作模式显著提高了系统负载均衡度。

图 6  不同模式下系统负载的分布

下载: 全尺寸图片 幻灯片

6.   结论

本文在基于集群协作的云雾混合计算场景中研究了资源分配和负载均衡策略，利用集群技术和集群协作模式以提高网络吞吐量及系统可靠性。通过联合优化计算资源、通信资源和卸载决策，提出一个SLEC最小化问题，即在负载均衡的约束下保证系统时延能耗开销最小化。将原问题分解为多个子问题后，采用KKT条件和二分搜索迭代法分别对计算和通信资源进行优化。接着提出了基于分支定界的开销最小化卸载算法BB-OMOA，在资源分配结果的基础上求解最优卸载决策。仿真结果表明，本文所提方案能够在满足时延能耗最小化的同时实现系统的负载均衡，体现了所提集群协作模式及算法的有效性。