Computation Offloading Cost Optimization Based on Hybrid Particle Swarm Optimization Algorithm

1.   引言

近年来，随着移动终端(Mobile Terminal, MT)的爆发式增加，以及自动驾驶、人工智能、虚拟现实/增强现实(VR/AR)等急需计算资源且对时延有极高要求的计算密集型业务的不断增长，给资源受限的移动计算系统和无线通信网络带来了前所未有的挑战^[1,2]。

移动边缘计算(Mobile Edge Computing, MEC)通过将计算和存储资源部署在网络边缘，允许MT将计算任务卸载到边缘服务器，为用户提供了超低时延、高带宽的网络服务^[3]。但是，由于无线和计算资源有限，如果太多的MT将其计算任务卸载到MEC服务器，会导致严重的网络计算拥塞和干扰^[4]。超密集异构网络^[5]通过在宏小区中部署更为密集的小基站(Small Base Station, SBS)并与MEC相结合，能进一步缩短MT与MEC服务器间的距离以降低传输时延及支持海量链接。

时延和能耗作为计算卸载性能评估的重要指标，近年来得到了深入的研究。文献[6]提出了一种延迟感知计算卸载算法，联合优化保密配置、计算卸载和无线资源分配，以最大限度地减少整体执行延迟。文献[7]在超密集网络场景下对卸载策略、信道资源和传输功率进行联合优化，以最小化系统能耗。文献[8]建立SBS和宏基站(Macro Base Station, MBS)之间的无线回程链路以实现共享频谱的目的，并最终最小化能耗和执行时间的加权和。但是上述研究或是利用单个MEC服务器来满足传入的卸载请求，或是未实现MEC服务器计算资源的合理利用。而对于多MT的场景，MEC服务器很容易拥塞，这将直接影响用户体验。

鉴于此，越来越多的研究倾向于多MEC服务器的场景。文献[9]在多用户和多MEC服务器场景下，联合优化计算卸载和资源分配策略以最小化MT能耗。文献[10]在能量约束下，通过优化卸载决策和计算资源分配以最大限度地降低超密集网络中MT的计算延迟。进一步，为更合理分配网络及计算资源，研究者开始关注卸载成本问题。文献[11]针对非正交多址接入的车载边缘计算网络，联合任务卸载、用户分簇和计算资源块联合优化以最小化任务处理成本问题。文献[12]研究了基于边缘计算的车联网，通过优化任务的卸载时间、无线带宽分配和计算资源分配来最小化系统的计算与通信成本。文献[13]为了最小化系统的计算和通信成本，提出了一种具有垂直和水平卸载的4层云边缘计算系统。虽然文献[11-13]考虑了任务卸载时所需支付的计算和通信费用，但未连同任务在本地计算时产生的开销一起考虑。

不同于上述研究，本文研究了融合MEC的超密集异构网络下多小区多用户的计算卸载问题，将联合执行计算卸载和计算资源管理，并在相同的带宽利用率下最小化用户的任务处理成本。其中，任务处理成本由本地能耗开销、无线频谱占用开销和边缘计算资源租用开销3部分组成。本文的主要贡献总结如下：

(1)在融合MEC的超密集异构网络中，将用户任务处理所需支付的费用作为计算卸载成本，联合无线资源、计算资源管理，满足时延约束的同时，使所有用户的任务处理成本最小化，并建立相应的问题模型。

(2)设计了混合粒子群优化(Hybrid Particle Swarm Optimization, HPSO)算法来解决上述非凸问题，该算法先后执行多样性增强(Diversity Enhancement, DE)的自适应遗传算法和自适应粒子群算法。但不同于文献[14]中的分层自适应搜索(Hierarchical Adaptive Search, HAS)算法，HPSO算法引入了部分参量的规范化处理，且改变了粒子群算法的权重更新规则以提升粒子群算法的收敛速度。此外，与[4,14]不同的是，为更合理地分配MEC服务器的计算资源，HPSO算法改进了遗传算法中的资源块初始化操作，并由此引进了计算资源块按需分配策略。最后，通过仿真验证了本文所提算法优越性。

2.   系统模型

2.1   网络模型

超密集异构边缘计算网络的系统模型如图1所示，每个六边形的蜂窝网格包含1个宏基站(MBS)、N个微基站(SBS)和K个MT，并且每个基站配有一个MEC服务器。不失一般性的情况下，本文考虑一个MBS的场景。假设基站的索引集合为$\mathcal{N} = \{ 1,2, \cdots ,n, \cdots ,N,N + 1\}$，其中MBS的索引为N+1，MT集合表示为$\mathcal{K} = \{ 1,2, \cdots ,k, \cdots ,K\}$。

图  1  系统模型

下载: 全尺寸图片 幻灯片

考虑到SBS的小范围覆盖和超密集部署，为降低控制开销，SBS的控制信令可由MBS负责处理。类似文献[14]，本文亦将频带分割为控制面和用户面，其中控制面用于传输控制信令，用户面用于传输数据。由于计算卸载发生在用户面，因此计算卸载机制研究时仅需关注此平面。在图1中，MT可以选择将自己的数据任务上传至SBS或者MBS上进行处理，亦可自身完成计算任务。值得注意的是，MBS不仅需要处理网格中的所有控制信令，还需处理由MT上传的数据，而SBS仅需完成数据处理任务。在计算卸载过程中，对于任何任务，如果其本地计算时延小于任务截止时间，MT会选择本地计算以降低额外开销，否则MT将任务上传至基站进行计算以减少时延，保证满足时延约束。

一般来说，计算卸载包括以下3个阶段。首先，MT的计算任务通过无线信道上传到BS上；然后，BS执行计算任务；最后，BS反馈计算结果给MT。考虑到计算结果的数据量相对较小，反馈过程可忽略不计。

2.2   资源模型

如图1所示，每个宏小区内所有小基站形成一个簇。为消除层间和层内的干扰，用户面所用频带$F$被划分为${F_1}$和${F_2}$两部分以分别供宏基站和小基站使用，其带宽分别为$\mu W$和$(1 - \mu )W$，其中$\mu$表示频带划分因子。为了消除宏基站间的干扰，频带${F_1}$被再次划分成3个子带${F_{11}}$, ${F_{12}}$和${F_{13}}$，即相邻宏小区中的宏基站的频带带宽为$\mu W/3$。为了消除小基站簇之间的干扰，频带${F_2}$同样被再次划分成3个子带${F_{21}}$, ${F_{22}}$和${F_{23}}$。进一步，为消除簇内小基站间的干扰，任意簇所用子带被平分给簇内小基站，即每个小基站可利用的频带带宽为$(1 - \mu )W/3N$。最后，为了再次提升用户上行传输性能，宏小区及小小区内MT间的干扰需要被消除。为此，假设任意基站可利用的频带被平分给其所关联的MT。此外，假设每个MEC服务器提供U个具有相同处理能力的计算资源块，其索引集合记为$\mathcal{U} = \{ 1,2, \cdots ,U\}$，其中每个计算资源块的处理能力记为${f^{{\text{unit}}}}$。

2.3   通信模型

根据2.2节中频带的使用规则，为消除同一基站下其他用户的干扰，关联同一基站的所有用户均分带宽。因此，当MTk上传计算任务到MBS，即n=N+1时，所分配到的带宽为$\mu W/3\sum\nolimits_{m \in \mathcal{K}} {{x_{nm}}}$。于是，其上行速率为

其中，${x_{nk}} \in \{ 0,1\}$，${x_{nk}}$表示MTk的卸载决策；若${x_{nk}} = 1$，表示MTk和基站n关联，否则表示MTk的任务在本地执行；${p_k}$表示MTk的传输功率；${h_{nk}}$是MTk和基站n之间的信道增益；${\sigma ^2}$是基站的噪声功率。值得注意的是，任意一个MTk最多只关联一个基站，即$\displaystyle\sum\nolimits_{n \in \mathcal{N}} {{x_{nk}}} \le 1$。

同理，上传计算任务到SBS，即n≠N+1时，所分配到的带宽为$(1 - \mu )W/3N \displaystyle\sum\nolimits_{m \in \mathcal{K}} {{x_{nm}}}$，上行速率为

2.4   计算模型

对于任意MTk，其计算任务由3元组${T_k} = \{ {d_k},{l_k},T_k^{{\text{max}}}\}$表示，其中${d_k}$表示计算任务的数据大小，${l_k}$表示用于完成1 bit计算任务所需的CPU周期数，$T_k^{{\text{max}}}$表示计算任务不能超过的最大时延。

(1)本地计算。假设所有MT的计算能力相同，记为${f^{{\text{loc}}}}$。那么，MTk的本地计算时延(时间)为

MTk的本地计算能耗为

那么，MTk的能耗费用为

其中，${\omega _1}$(单位：元/kJ，下文所有单位“元”均指人民币)为单位能耗下所需的费用，$\alpha$为依赖于芯片架构的能量系数。

(2)边缘计算。当MTk和基站n相关联时，需要将其计算任务传输到该基站。根据之前的考虑，边缘计算时延应该包括上行传输时延和远程计算时延。于是，MTk上传至MBS和SBS的传输时延分别为

假设第n个MEC服务器分给MTk的计算资源块个数记为${\lambda _{nk}} \in \mathbb{N}$。那么，MTk在计算服务器上的处理时延为

类似于文献[11]，当用户需要借助MEC服务器来计算任务时，需要向运营商交付以下费用：一是任务上传时占用带宽而产生的开销，二是租用计算资源块进行计算所产生的开销。设用户使用无线资源的单价为${\omega _2}$(元/(MHz·s))，那么MTk传输任务时所产生的费用为

其中，${\bar w_k}$表示MTk所占用的频带宽度。若对于任意基站n，${x_{nk}} = 0$，即MTk不与任何基站关联，那么$Y_k^{{\text{trans}}} = 0$。

当${x_{nk}} = 1$且n=N+1时，即MTk选择了MBS，占用的带宽${\bar w_k} = \mu W/3 \displaystyle\sum\nolimits_{m \in \mathcal{K}} {{x_{nm}}}$；当${x_{nk}} = 1$且n≠N+1时，即MTk选择了SBS，占用的带宽${\bar w_k} = (1 - \mu ) W/3N\sum\nolimits_{m \in \mathcal{K}} {{x_{nm}}}$。计算推导，MTk的传输费用可已归结为以下形式

从式(10)来看，MTk的传输费用和${d_k}$, ${p_k}$, ${h_{nk}}$, ${\sigma ^2}$有关。具体而言，当${d_k}$增加时，$Y_k^{{\text{trans}}}$增加；当${p_k}$增加时，由于$t_k^{{\text{trans}}}$降低，$Y_k^{{\text{trans}}}$也降低。因此，在不考虑设备电量极度不足的情况下，为减少任务处理开销，最直观的方法是MT以最大功率发射。鉴于此，假设所有MT的发射功率恒定，均为最大功率${p^{{\text{max}}}}$。

假设租用计算资源块的单价为${\omega _3}$(元/个)，那么MTk的任务在MEC服务器上处理产生的计算费用

最后，MTk完成计算任务所需要支付的总费用为

3.   问题建模

在保证任务满足最低处理时延的前提下，通过联合优化任务卸载决策${\boldsymbol{X}} = \{ {x_{n1}},{x_{n2}}, \cdots ,{x_{nK}}\}$和计算资源块分配${\boldsymbol{\lambda}} = \{ {\lambda _{n1}},{\lambda _{n2}}, \cdots ,{\lambda _{nK}}\}$以最小化所有MT的总开销。具体而言，优化问题可规划为

其中，${t_k} = \left(1 - \displaystyle\sum\nolimits_{n \in \mathcal{N}} {{x_{nk}}} \right)t_k^{{\text{loc}}} + \displaystyle\sum\nolimits_{n \in \mathcal{N}} {{x_{nk}}} \left(t_k^{{\text{trans}}} + t_k^{{\text{edge}}}\right)$；约束C1表示任何MTk的任务处理时延不能超过其截止时延$T_k^{\max }$；约束C2表示任何MTk的计算任务只能在本地或者某一个基站上执行；约束C3表示任何MTk的计算任务最多只能卸载至一个基站执行；约束C4表示任何MTk能分配到的计算资源块数落于自然数集合$\mathbb{N}$内；约束C5表示任意基站n分配给所关联MTs的计算资源块不能超其总量。

经过推导，容易得出所有MT总的费用为

其中，$A = {\omega _1}\alpha {({f^{{\text{loc}}}})^2}\displaystyle\sum\nolimits_{k \in \mathcal{K}} {{d_k}{l_k}}$可视为常数项。因此，最小化问题P1的目标函数等价于最大化公式(14)的后半部分$Z({\boldsymbol{X}},{\boldsymbol{\lambda}} )$。在约束条件不变的情况下，问题P1可转化为问题P2，即

显然，问题P2是非凸优化问题，其目标函数和约束表现为混合整数及非线性的形式。

4.   算法设计

遗传算法有很强的全局搜索能力，但是局部搜索能力较差^[15]；而粒子群算法比较简单，收敛速度很快^[16]，但容易陷入局部最优值出现早熟。鉴于两种算法有着互补的优势，因此，类似于文献[4,14]，联合遗传算法和粒子群算法来开发HPSO算法以解决问题P2。为了避免过早收敛，提高收敛速度，糅合了基于DE的自适应遗传算法和自适应粒子群算法，前者用于粗粒度搜索，后者则用于细粒度搜索，算法流程如图2所示。

图  2  算法流程图

下载: 全尺寸图片 幻灯片

4.1   遗传算法

作为一种随机搜索算法，遗传算法从一组初始可行解集开始，其关键因素及相应步骤如下：

(1)染色体。在问题P2中，优化参量${\boldsymbol{X}}$被编码成染色体${\boldsymbol{S}} = \{ {s_{ik}},\forall i \in \mathcal{I},\forall k \in \mathcal{K}\}$，参量${\boldsymbol{\lambda}}$被编码成染色体${\boldsymbol{Q}} = \{ {q_{ik}},\forall i \in \mathcal{I},\forall k \in \mathcal{K}\}$，其中$\mathcal{I}=\{1,2,\cdots ,I\}$为个体集群。在任意个体i中，${s_{ik}}$和${q_{ik}}$分别表示MTk所选择的基站索引号及所获取的计算资源块数，${s_{ik}} = 0$表示个体i中的MTk不选择基站，在本地完成计算任务。

(2)适应度函数。考虑到约束C1具备混合整数非线性的形式，在遗传算法的初始化和基因操作中难以满足，它被作为一个惩罚项引入适应度函数中。鉴于此，为解决问题P2，个体i的适应度函数被定义为

其中，${{\boldsymbol{S}}_i} = \{ {s_{ik}},\forall k \in \mathcal{K}\}$；${{\boldsymbol{Q}}_i} = \{ {q_{ik}},\forall k \in \mathcal{K}\}$；$\phi ({{\boldsymbol{S}}_i},{{\boldsymbol{Q}}_i})$为个体i的罚函数，${\eta _k}$为MTk的罚因子。

(3)种群初始化。在问题P2的约束下，初始种群的个体基因可根据以下规则生成。具体而言，对于个体i的基因${s_{ik}}$和${q_{ik}}$，如果MTk的本地计算时延小于任务截止时延$T_k^{{\text{max}}}$，设置$s_{ik}^0 = 0$且$q_{ik}^0 = 0$，反之$s_{ik}^0 = {\text{randi}}(\mathcal{N})$，$q_{ik}^0 = {\text{randi}}(\mathcal{U})$，其中${\text{randi}}(\mathcal{A})$表示从集合$\mathcal{A}$中随机输出一个元素。

不同于${s_{ik}}$，由于${q_{ik}}$需满足约束C5，因此在随机分配之后还需要对计算资源块的分配情况进行溢出检测及处理。具体规则如下：假设基站n关联下的MT分配到的总计算资源块数为${U_n}$，如果${U_n} > U$，说明不满足约束C5，需对${q_{ik}}$进行规范化处理。为了保证公平，在保证比例$q_{ik}^0/{U_n}$不变的情况下，将U个计算资源块以整数形式重新分给MT。此时，如果MTk分配到$q_{ik}^0$个计算资源块，则该MT实际分配到的计算资源块个数为${\text{round}}\left( {q_{ik}^0U/{U_n}} \right)$或${\text{round}}\left( {q_{ik}^0U/{U_n}} \right) - 1$(当${\text{round}}\left( {q_{ik}^0U/{U_n}} \right) \,=\, U$时)，其中${\text{round}}(\chi )$表示对$\chi$四舍五入取整。

(4)选择。在本文，锦标赛算法被用于遗传算法的个体选择。为保持种群的多样性，引导算法朝着最优解方向前进，在每一轮选择操作中，若历史最佳个体未被选入新种群，则用它取代新种群中最差的个体。

(5)交叉。任意两个相邻的父系个体i和j被选中以概率${\text{p}}{{\text{c}}_{ij}}$进行基因交叉操作，交叉操作会产生两个新个体。染色体交叉位置随机确定，但所有染色体交叉位置一致。相邻个体i和j之间的交叉概率${\text{p}}{{\text{c}}_{ij}}$为

其中，$0 < {{{b}}_{\text{1}}} \le 1$, $0 < {{{b}}_{\text{2}}} \le 1$；${\bar G_{ij}}$表示个体i和j中适应度较小个体的适应度(函数)值；${G^{{\text{min}}}}$和${G^{{\text{ave}}}}$分别表示种群的最小适应度值和平均适应度值。从式(17)，不难发现，优质个体能获得更多的交叉机会。

(6)变异。在变异操作中，首先随机选择一个个体i，再随机选择染色体的一个基因片段，并在问题P2的约束条件下以概率${\text{p}}{{\text{m}}_i}$发生变异。个体i的变异概率为

其中，$0 < {b_3} < 1$, $0 < {b_4} < 1$；${G_i}$表示个体i的适应度函数值；${G^{{\text{max}}}}$表示种群的最大适应度值。

在上述概率下，任意个体i中${s_{ik}} \ne 0$所对应基因点位的MTk可以根据以下规则执行变异操作

其中，${a_1}$和${a_2}$为服从0-1均匀分布的随机数。

为了避免遗传算法出现过早收敛的情况，在变异和交叉操作之前增加了多样性增强的变异。为此，先对当前种群的多样性进行测度^[17]。如果当前种群的多样性水平较低，那么需要适当提升变异概率；反之，则需降低变异概率。对于n维数值问题，多样性测度被定义为

其中，$s_k^{{\text{ave}}} = {{\displaystyle\sum\nolimits_{i \in \mathcal{I}} {{s_{ik}}} } / I}$；$q_k^{{\text{ave}}} = {{\displaystyle\sum\nolimits_{i \in \mathcal{I}} {{q_{ik}}} } / I}$；${L_1}$和${L_2}$分别为${\boldsymbol{S}}$和${\boldsymbol{Q}}$的可行域对角线的长度。待确定多样性测度后，可根据概率${\text{pd}}$执行变异操作。具体如下

其中，$0 < {\overline {{\text{dm}}} _1} < 1$, $0 < {\overline {{\text{dm}}} _2} < 1$为多样性阈值。

结合上述遗传算法因素，基于DE的自适应遗传算法的完整过程可概述表1。

表  1  基于DE的自适应遗传算法(算法1)

步骤1　设置迭代次数${t_1} = 0$，初始化种群中的I个体；根据 　　　　 式(16)计算所有个体的适应度值，并找到当前最佳个 　　　　 体，以当前最佳个体更新历史最佳个体。
步骤2　以锦标赛算法建立新种群，若历史最佳个体未被选入新 　　　　 种群，则用它取代新种群中最差的个体。
步骤3　所有个体根据概率式(21)执行多样性增强的变异，并对 　　　　 计算资源块进行溢出检测及处理。
步骤4　根据式(16)计算所有个体的适应度值。
步骤5　任意两个相邻个体以概率(17)执行交叉操作，并对计算 　　　　 资源块进行溢出检测及处理。
步骤6　所有个体根据规则式(19)以概率式(18)执行变异操作， 　　　　 并对计算资源块进行溢出检测及处理。
步骤7　根据式(16)计算所有个体的适应度值，并更新当代最佳 　　　　 个体和历史最佳个体。
步骤8　${t_1} = {t_1} + 1$；如果${t_1} < {T_1}$，则回到步骤2，否则输出当 　　　　 前种群并终止循环，${T_1}$为迭代终止次数。

下载: 导出CSV 

| 显示表格

4.2   粒子群算法

在粒子群算法中，粒子(个体)的位置代表问题P2的解，速度则展示解的演化情况。粒子群算法中粒子的初始位置取值为算法1的输出值。具体而言，粒子群算法的关键要素及步骤如下。

若粒子i中MTk任务的本地计算时延小于任务截止时延，设置${s_{ik}}$和${q_{ik}}$的速度${\text{sv}}_{ik}^{t + 1}$和${\text{qv}}_{ik}^{t + 1}$为0，反之设

其中，$\theta _i^t$表示第t次迭代时粒子i的惯性权重；${{{e}}_{\text{1}}}$和${{{e}}_{\text{2}}}$是加速参数；${\xi _{ik}}$和${\varepsilon _{ik}}$是区间[0,1]上的随机数；${\text{spbest}}_{ik}^t$和${\text{qpbest}}_{ik}^t$表示第t次迭代时粒子i中MTk的${s_{ik}}$和${q_{ik}}$的历史最佳位置；${\text{sgbest}}_k^t$和${\text{qgbest}}_k^t$表示第t次迭代时种群全局最佳粒子中MTk参量的位置。此外，由于PSO搜索过程有着非线性且复杂度高的特点，线性递减惯性权重的方法不能反映实际的优化搜索。因此，类似于文献[18]，粒子i的速度惯性权重$\theta _i^t$在迭代过程中按照以下非线性的形式进行自适应更新

其中，${\theta ^{{\text{max}}}}$和${\theta ^{{\text{min}}}}$分别为最大和最小惯性权重。然后，粒子i中MTk的${s_{ik}}$和${q_{ik}}$的位置可更新为

类似于文献[14,19]，二度更新全局最佳粒子的速度，迫使全局最佳粒子j朝着局部最小值移动。数学上，全局最佳粒子j中MTk的${s_{ik}}$和${q_{ik}}$的速度可更新为

其中，${{{e}}_{\text{3}}}$为加速参数；$0 \le {\varsigma _{jk}} \le 1$为随机数；${\rho ^t}$为第t次迭代时的缩放因子。

全局最佳粒子j中MTk的${s_{ik}}$和${q_{ik}}$的位置可更新为

其中${\rho ^{t + 1}}$更新为

其中，${\text{NS}}$表示连续成功的次数，${\text{NF}}$表示连续失败的次数；${\kappa _1}$和${\kappa _2}$为阈值参数。在式(27)中，$G({\text{gbes}}{{\text{t}}^t}) = G({\text{gbes}}{{\text{t}}^{t - 1}})$被定义为失败，其他情况被定义为成功。

结合上述要素，自适应粒子群算法的完整过程可被概述表2。

表  2  自适应粒子群算法(算法2)

步骤1　设置迭代次数${t_2} = 0$与${\rho ^{{t_2}}} = 1$；以算法1的输出初始化 　　　　 ${\text{sl}}_{ik}^{{t_2}}$, ${\text{ql}}_{ik}^{{t_2}}$, ${\text{spbest}}_{ik}^{{t_2}}$与${\text{qpbest}}_{ik}^{{t_2}}$；以区间[0,1]的随机数初 　　　　 始化${\text{sv}}_{ik}^{{t_2}}$与${\text{qv}}_{ik}^{{t_2}}$；找到初始种群中的全局最佳粒子。
步骤2　根据式(23)更新惯性权重。
步骤3　根据式(22)、式(24)更新粒子的速度和位置，并对计算 　　　　 资源块进行溢出检测及处理。
步骤4　根据式(16)计算所有粒子的适应度值；对于任意一粒子， 　　　　 如果它的当前适应度值高于自身的历史最高值，则更新 　　　　 自身的历史最佳粒子，然后在所有历史最佳粒子中找到 　　　　 全局最佳粒子。
步骤5　根据式(25)、式(26)更新全局最佳粒子的速度和位置， 　　　　 并对计算资源块进行溢出检测及处理。
步骤6　根据式(27)更新缩放因子$\rho$。
步骤7　${t_2} = {t_2} + 1$；如果${t_2} < {T_2}$，回到步骤2，否则输出所有 　　　　 的卸载决策${\text{sgbes}}{{\text{t}}_k}$与资源块分配决策${\text{qgbes}}{{\text{t}}_k}$，其中 　　　　 ${T_2}$为粒子群算法的最大迭代次数。

下载: 导出CSV 

| 显示表格

按顺序执行算法1和算法2，这一过程归纳成混合粒子群优化(Hybrid Particle Swarm Optimization, HPSO)算法。容易发现，算法1使用随机分配的方式初始化计算资源块，这点和文献[4]类似，但并未考虑MT计算任务的实际需求，资源块分配不足可能会导致时延约束不满足，进一步影响算法的收敛速度和结果；而资源块分配溢出则会降低计算资源利用率，且增加任务处理成本。实际上，对于关联基站的MTk，只需使得分配给其的计算资源块恰好能够满足在剩余可执行时间${\text{RE}}{{\text{S}}_k}$内完成计算任务即可，其中${\text{RE}}{{\text{S}}_k} = T_k^{{\text{max}}} - t_k^{{\text{trans}}}$。此时若再额外分配计算资源块，只会增加不必要的计算费用。为此，本文提出按需分配策略来替代算法1中随机分配计算资源块的方式，以改进HPSO算法，其具体过程如表3所示。

表  3  计算资源块按需分配策略(算法3)

输入：种群规模I，MT的数量K，${T_k} = ({d_k},{l_k},$$T_k^{{\text{max}}})$，初始卸 　　　 载决策$s_{ik}^0$，计算资源块总数U，上行速率${r_{nk}}$。
输出：初始计算资源块分配决策$q_{ik}^0$。
步骤1　如果$s_{ik}^0 = 0$，令$q_{ik}^0 = 0$；如果$s_{ik}^0 \ne 0$，即对于MTk， 　　　　 计算其任务在基站的剩余可执行时间${\text{RE}}{{\text{S}}_k}$。
步骤2　如果${\text{RE}}{{\text{S}}_k} \le 0$，说明任务需要卸载，但由于初始过程中 　　　　 随机生成的卸载决策无法保证关联的基站是理想的，那 　　　　 么令此时MTk分配到的计算资源块个数$q_{ik}^0 = 1$；如果 　　　　 ${\text{RE}}{{\text{S}}_k} > 0$，结合式(8)，此时MTk分配到的计算资源块 　　　　 个数$q_{ik}^0 = {\text{round}} \left( {{d_k}{l_k}/({\text{RE}}{{\text{S}}_k}{f^{{\text{unit}}}}) + 0.5} \right)$。
步骤3　对MTk分配到的计算资源块进行溢出检测及处理。

下载: 导出CSV 

| 显示表格

5.   仿真及对比分析

5.1   参数设置

在超密集异构边缘计算网络中，每个宏小区随机部署40个SBS和30个MT，其中任意两个相邻MBS间的距离为1000 m。设置噪声功率谱密度为–174 dBm/Hz；$\mu$=0.5；${\eta _k}$=1000；${{{b}}_{\text{1}}}$=0.8, ${{{b}}_{\text{2}}}$=0.8, ${{{b}}_{\text{3}}}$=0.3, ${{{b}}_{\text{4}}}$=0.3, ${{{b}}_{\text{5}}}$=0.6, ${{{b}}_{\text{6}}}$=0.03, ${{{b}}_{\text{7}}}$=10^–5, ${\overline {{\text{dm}}} _1}$=0.01, ${\overline {{\text{dm}}} _2}$=0.25^[17] ；${\theta ^{\max }}$=0.9, ${\theta ^{\min }}$=0.4^[18]；${{{e}}_{\text{1}}}$=${{{e}}_{\text{2}}}$=${{{e}}_{\text{3}}}$=1.5；${\kappa _1}$=15, ${\kappa _2}$=5^[20]。此外，其他参数设置见表4。特别说明，能耗单价${\omega _1}$参照2021年居民用电收费标准。

表  4  实验参数

参数	数值		参数	数值
系统带宽W	20 MHz		资源块的计算能力${f^{{\text{unit}}}}$	1 GHz
设备最大发射功率${p^{{\text{max}}}}$	23 dBm		资源块的个数U	100
任务的数据大小${d_k}$	2～5 Mbit		种群大小I	16
单位任务计算量${l_k}$	1000 cycles/bit		能耗单价${\omega _1}$	1.519×10–4 元/kJ
任务的截止时延$T_k^{{\text{max}}}$	1～10 s		无线资源单价${\omega _2}$	1/2/3/4/5 元/(MHz·s)
能量系数$\alpha$	10–24		计算资源块单价${\omega _3}$	0.1/0.2/0.3/0.4/0.5 元/个
设备的计算能力${f^{{\text{loc}}}}$	0.7 GHz

下载: 导出CSV 

| 显示表格

在仿真中，本文主要研究了计算资源块和无线信道资源的单位价格对不同卸载算法的任务平均处理时延及任务平均处理成本的影响。通过对比任务的平均处理时延和成本及算法的收敛性来论证所设计算法的有效性。为此，引入如下其他算法作为对照组。

全本地算法：所有MT的计算任务都在本地执行；全关联算法：所有MT的计算任务都卸载到MEC服务器上执行，其中计算资源块分配方式为随机分配。此外，在全关联算法中，本文考虑的是将MT的计算任务卸载到与其对应的信道增益最好的基站上；HGP算法：此算法为文献[4]中分层的遗传和粒子群优化 (Hierarchical Genetic and Particle swarm optimization, HGP)算法，其中计算资源块分配方式为随机分配；HAS算法：此算法为文献[14]中的分层自适应搜索算法，其中计算资源块分配方式为随机分配。

5.2   结果分析

图3给出了两种资源单价的变化对任务平均处理时延的影响。在图3(a)中，无线资源单价${\omega _2}$固定为1 元/(MHz·s)，在图3(b)中，计算资源块的单价${\omega _3}$固定为0.1元。可以看到，几种算法下的任务平均处理时延并不会随着计算资源块或无线资源单价的变动而受到影响。这是因为对于在本地计算的任务而言，其处理时延主要取决于任务的数据量和MT的计算能力，而对于要上传到基站进行计算的任务，其处理时延主要取决于传输时的信道状态和分到的计算资源块个数。

图  3  单价变化对任务平均处理时延的影响

下载: 全尺寸图片 幻灯片

此外，在图3中，全本地算法的任务平均处理时延最长，全关联算法最短，其他3种算法则介于两者之间。这是由于其他3种算法考虑了任务截止时延的约束，对于无法在截止时延内完成计算任务的MT，这3种算法才会选择关联基站，而全本地算法中实际存在着不满足时延约束的MT。在全关联算法中，虽然所有任务的时延约束都满足了，但该算法的任务平均处理成本也是最高的。相比于全本地算法，引入资源块按需分配策略的HPSO算法的任务平均处理时延缩短了约25%，资源块随机分配策略下的HAS算法则更低。这是因为这两种算法都满足了时延约束(由图5(b)可验证)，但在随机分配策略下，计算资源块可能存在额外分配的情况。因此，HAS算法下任务平均处理时间会更短，这也意味着HAS算法的开销会更高。

图  5  适应度值的搜索情况

下载: 全尺寸图片 幻灯片

图4为两种资源单价的变化对任务平均处理成本的影响。在图4(a)中，随着计算资源块单价的增加，除全本地算法外，其他算法的任务平均处理成本都相应地增加了。虽然全本地算法的任务平均处理成本最低，但是它不能保证所有任务都满足时延约束。随机分配策略下的全关联算法的任务平均处理成本最高，这是因为所有MT都选择将任务上传至基站进行计算，甚至是一些满足时延约束，可以在本地完成计算的任务。另外，可以发现，引入资源块按需分配策略的HPSO算法是使得任务平均处理成本最低的算法。

图  4  单价变化对任务平均处理成本的影响

下载: 全尺寸图片 幻灯片

在图4(b)中，引入资源块按需分配策略的HPSO算法依旧是任务处理成本最小的算法。此外，会发现随着无线资源单价的不断提高，HGP算法的任务平均处理成本逐渐逼近甚至高于全关联算法。这是因为随着无线资源单价的提高，传输费用会成为任务处理的主要开销。结合式(10)也不难理解，虽然在全关联算法中或许将一部分可以在本地进行计算的任务上传到了基站，但每次选择的都是对应信道增益最好的基站，而HGP算法由于无法找到一个合适的解(由图5(b)可验证)，最后得到的卸载决策可能并不理想。因此，最终会导致HGP算法下的任务平均处理成本逐渐逼近甚至高于全关联算法。

图5给出了适应度值在遗传和粒子群算法部分的收敛变化情况。从图5(a)可以发现，在有限的迭代次数内，HGP算法中传统的遗传算法难以求解P2这一混合整数非线性规划问题。而相较于HAS算法中改进的遗传算法，HPSO算法中的自适应遗传算法由于一开始引入计算资源块按需分配策略，使得资源约束条件变得更为苛刻。因此，初始化时最优个体的适应度值较高，但在迭代过程中会快速收敛。

在图5(b)中，HGP算法中传统的粒子群算法在迭代求解过程中依旧没有找到合适的可行解。相比于会对全局最佳粒子的速度和位置进行更新的自适应粒子群算法，HAS算法和HPSO算法中的自适应粒子群算法最终都能收敛。此外，容易发现，采用非线性惯性权重的HPSO算法相比采用线性惯性权重的HAS算法收敛速度明显更快，并且最终的收敛结果更好。

6.   结束语

本文研究了超密集异构边缘计算网络中任务处理成本最小优化问题。具体而言，在延迟和计算资源约束条件下，联合优化了计算卸载和MEC服务器的计算资源块分配以使用户的任务处理成本降最小。在此之前，一个有效的频带划分方案被引入以用于消除平面间、层间和层内的干扰。考虑到最终所规划的问题具备非线性且混合整数形式，同时为满足问题约束条件及提升算法收敛速度，本文改进HAS以获取HPSO算法。仿真结果表明，同其他卸载算法相比，HPSO算法在减少任务处理成本方面具有显著的优势。