开放科学(资源服务)标志码(OSID)：

0 概述

随着移动设备在全国各城市中迅速普及和增长，密集型计算任务随之激增^[1-2]，这给移动设备的计算能力和电池寿命提出了更高的要求。然而，由于微芯片架构和低功耗设计，使得移动设备计算能力有限^[3-4]，导致设备在处理高密集、低延迟任务时存在较大的延误。同时，设备在处理这些任务时也产生了更多的能耗，这也进一步缩短了设备的续航时间。为解决该问题，研究人员提出移动边缘计算 ^[5]，通过在靠近移动设备的网络边缘部署计算资源，使移动设备能够高效地卸载计算密集型任务。相比云计算，数据传输不再需要经过核心网络，移动设备即能够获得较低的传输延迟和较强的续航能力。

计算卸载是移动边缘计算中最突出和广泛讨论的问题之一，其为移动边缘计算的智能核心因素。目前，现有研究工作主要从应用拓扑结构、优化目标多样性和计算资源竞争等特性分别展开，然而很少联合考虑应用拓扑结构、优化目标多样性及计算资源竞争的特性。首先，对于多用户并发型数据流任务计算卸载问题，任务之间不仅会对边缘服务器的计算资源产生竞争，而且也会对移动设备本地计算资源产生竞争，这种双边竞争进一步增加了计算资源竞争的复杂程度。其次，从数学建模角度来讲，决策变量包括任务卸载比例(连续变量)和任务执行顺序(离散变量)，因此该问题本质上是一个多目标混合整数问题的求解。此外，在多目标优化问题中，帕累托前沿包含多个非支配解构成的帕累托解集，而在实际应用中只需选取代表帕累托前沿特征的少量解。

本文在同时考虑应用拓扑结构、优化目标多样性及计算资源竞争的基础上，设计一种多目标并发型数据流任务计算卸载混合整数模型，并给出基于多目标优化和多属性决策的两阶段优化框架进行求解。在多目标优化阶段，提出一种改进DMP-NSGA-II算法以解决局部收敛和全局搜索难以平衡的问题，并通过基于混合式求解框架的DMP-NSGA-II算法求解该模型。在多属性决策阶段，给出一种FCM-GRP集成方法，在帕累托前沿上采用模糊C-均值聚类(Fuzzy C-Means，FCM)算法获得不同偏好下的聚类解集，并根据灰关联投影(GRP)算法选出不同偏好下最优折衷卸载决策。

1 相关工作

现有研究工作大多针对应用拓扑结构、优化目标多样性和计算资源竞争的某一特性展开。首先，任务卸载模型是计算卸载的首要考虑因素，一般分为全部卸载模型和部分卸载模型。全部卸载模型主要针对高度耦合的任务，只能作为整体在本地执行或边缘执行。文献[6]根据网络信道特性、缓存排队状态、本地及边缘计算能力来选择整体卸载决策。文献[7]采用动态电压和频率缩放技术在时延允许范围内最小化应用执行的能量消耗，并优化数据传输以执行整体卸载。部分卸载模型通常是指流式数据处理任务，如文件压缩、视频分析等，数据以任意比例切分在本地和边缘同时执行。文献[8]采用一种李雅普诺夫优化策略对连续到达的数据流进行动态卸载决策，以最小化移动终端能耗。文献[9]则采用动态规划方法实现数据流卸载决策，在满足任务延迟约束的同时最小化移动终端能耗。此外，考虑到边缘服务器的计算资源有限，需要合理优化计算资源分配。文献[10]采用无线资源和计算资源联合优化方法，以实现满足时延约束下最小化能耗。文献[11]研究了多车辆多边缘服务器场景下计算卸载及资源分配问题，旨在最小化所有任务延迟。然而，现有研究很少同时考虑应用拓扑结构、优化目标多样性及计算资源竞争的特性。

其次，如何高效地处理混合整数决策变量是多目标混合整数问题求解的关键。目前，多目标混合整数问题的主流求解框架包括转换求解框架、分层式求解框架、混合式求解框架^[12]。转换求解框架是借助离散化或连续化方法将其转化为单一变量多目标优化问题，然而这种框架存在一定限制性，因为有些问题的混合整数决策变量难以转换成单一变量类型。分层式求解框架是将离散变量和连续变量分为上层和下层，独立评价并相互反馈，然而这种框架具有较高的计算成本，不适合复杂优化问题。混合式求解框架则在同一个层次中同时搜索离散变量与连续变量，相对分层式求解框架，其在保留求解的通用性的同时简化了求解流程。因此，在考虑到本文模型中决策变量难以转换的前提下，混合式求解框架是首选的求解框架。

此外，在多目标优化问题中，主流选解方法包括先验方法^[13]、后验方法^[14]和交互方法^[15]。先验方法是优化前将多个目标组合成单个目标，具有简单、方便的特性，但其主观程度较高。在交互式方法中，决策者参与优化过程，其过程较为复杂。后验方法的搜索和决策过程是分离的，当偏好发生变化时，无需重复执行优化算法，其已被证明是首选的研究方法。目前，相关研究工作主要是采用多目标优化和多属性决策相结合的方法从有限组合方案中确定最优组合^[16-17]。

2 问题建模 2.1 系统模型

本文研究的是多用户单边缘服务器的系统架构，边缘服务器内嵌边缘智能，负责移动设备端计算卸载决策。在某物理区域内随机分布多个移动设备，并在同一时刻产生并发型数据流任务，任务可以任意比例切分为本地和边缘服务器同时执行。被切分任务通过无线网络传输至通信节点并转发到边缘服务器，边缘服务器放置于无线通信节点旁侧。图 1所示为多用户并发型数据流任务计算卸载流程。

本文以多个移动设备为研究对象，每个移动设备$ {M}_{i} $可以表示成一个六元组：$ {M}_{i}=\{{c}_{i}^{\mathrm{m}}, {P}_{i}^{\mathrm{c}}, {P}_{i}^{\mathrm{n}}, {P}_{i}^{\mathrm{s}}, $ $ {P}_{i}^{\mathrm{r}}, {d}_{i}\} $，其中，$ i $表示移动设备$ {M}_{i} $的编号，$ i\in \left[1, N\right] $，$ N $为移动设备总数，$ {c}_{i}^{\mathrm{m}} $表示移动设备$ {M}_{i} $的计算能力，$ {P}_{i}^{\mathrm{c}} $和$ {P}_{i}^{\mathrm{n}} $分别表示移动设备$ {M}_{i} $计算模块在工作状态和空闲状态下的功率，$ {P}_{i}^{\mathrm{s}} $和$ {P}_{i}^{\mathrm{r}} $分别表示移动设备$ {M}_{i} $的通信模块在发送数据和空闲状态下的功率，$ {d}_{i} $表示移动设备$ {M}_{i} $到通信节点的物理距离。此外，边缘服务器的计算能力用$ {c}^{\mathrm{v}} $表示。

本文以并发型数据流任务为研究对象，每个移动设备$ {M}_{i} $的并发型数据流任务可以表示为一个四元组：$ {S}_{i}=\{{n}_{i}, {s}_{i, j}, {l}_{i, j}, {k}_{i, j}\} $，其中，$ {n}_{i} $表示移动设备$ {M}_{i} $并发型数据流任务的个数，$ {s}_{i, j} $表示移动设备$ {M}_{i} $第$ j $个任务，$ {l}_{i, j} $表示任务$ {s}_{i, j} $的软截止时间，表示当前任务的相对紧急程度，$ {k}_{i, j} $表示任务$ {s}_{i, j} $的数据容量。

2.2 任务时间模型

任务完成时间可以分成在移动设备本地执行和边缘服务器边缘执行两个部分。

首先，任务$ {s}_{i, j} $在移动设备本地执行的开始时间和结束时间分别表示为$ {S}_{i, j}^{\mathrm{m}} $和$ {F}_{i, j}^{\mathrm{m}} $，其计算公式如下：

$ {F}_{i, j}^{\mathrm{m}}={S}_{i, j}^{\mathrm{m}}+{t}_{i, j}^{\mathrm{m}} $

(1)

$ {S}_{i, j}^{\mathrm{m}}=\left\{\begin{array}{l}0, {O}_{i, j}^{\mathrm{m}}=\mathrm{\varnothing }\\ {F}_{i, j-1}^{\mathrm{m}}+{t}_{i, j}^{\mathrm{w}}, {O}_{i, j}^{\mathrm{m}}\ne \mathrm{\varnothing }\end{array}\right. $

(2)

$ {t}_{i, j}^{\mathrm{m}}=\frac{(1-{x}_{i, j}){k}_{i, j}}{{c}_{i}^{\mathrm{m}}} $

(3)

$ {t}_{i, j}^{\mathrm{w}}=\sum {t}_{i, k}^{m}, k\in {O}_{i, j}^{\mathrm{m}} $

(4)

其中：$ {x}_{i, j} $表示任务$ {s}_{i, j} $边缘卸载任务比例变量；$ \left(1-{x}_{i, j}\right){k}_{i, j} $表示任务$ {s}_{i, j} $在本地执行的任务量；$ {F}_{i, j-1}^{\mathrm{m}} $表示任务$ {s}_{i, j} $前一个任务的结束时间；$ {t}_{i, j}^{\mathrm{m}} $表示任务$ {s}_{i, j} $本地执行时间；$ {t}_{i, j}^{\mathrm{w}} $表示任务$ {s}_{i, j} $本地等待计算时间；$ {O}_{i, j}^{\mathrm{m}} $表示任务$ {s}_{i, j} $在移动设备$ {M}_{i} $上所有前置任务的集合，其依赖于任务$ {s}_{i, j} $本地排序变量$ {y}_{i, j} $。

然后，任务$ {s}_{i, j} $在边缘服务器边缘执行的开始时间和结束时间分别表示为$ {S}_{i, j}^{\mathrm{v}} $和$ {F}_{i, j}^{\mathrm{v}} $，其计算公式如下：

$ {F}_{i, j}^{\mathrm{v}}={S}_{i, j}^{\mathrm{v}}+{t}_{i, j}^{\mathrm{v}} $

(5)

$ {S}_{i, j}^{\mathrm{v}}=\left\{\begin{array}{l}{t}_{i, j}^{\mathrm{r}}, {O}_{i, j}^{\mathrm{v}}=\mathrm{\varnothing }\\ {F}_{i, j-1}^{\mathrm{v}}+{t}_{i, j}^{\mathrm{a}}, {O}_{i, j}^{\mathrm{v}}\ne \mathrm{\varnothing }\end{array}\right. $

(6)

$ {t}_{i, j}^{\mathrm{r}}=\frac{{x}_{i, j}{k}_{i, j}}{{r}_{i}} $

(7)

$ {t}_{i, j}^{\mathrm{v}}=\frac{{x}_{i, j}{k}_{i, j}}{{c}^{\mathrm{v}}} $

(8)

$ {t}_{i, j}^{\mathrm{a}}=\sum {t}_{i, k}^{v}, k\in {O}_{i, j}^{\mathrm{v}} $

(9)

其中：$ {x}_{i, j}{k}_{i, j} $表示任务$ {s}_{i, j} $在边缘执行的任务量；$ {F}_{i, j-1}^{\mathrm{v}} $表示任务$ {s}_{i, j} $前一个任务的结束时间；$ {t}_{i, j}^{\mathrm{v}} $表示任务$ {s}_{i, j} $在边缘服务器的执行时间；$ {t}_{i, j}^{\mathrm{a}} $表示任务$ {s}_{i, j} $在边缘服务器的等待执行时间；$ {O}_{i, j}^{\mathrm{v}} $表示任务$ {s}_{i, j} $在边缘服务器上所有前置任务的集合，其依赖于任务$ {s}_{i, j} $边缘排序变量$ {z}_{i, j} $；$ {t}_{i, j}^{\mathrm{r}} $表示任务$ {s}_{i, j} $卸载到边缘服务器的无线传输时间；$ {r}_{i} $表示移动设备信道的传输速率。

本文假设移动设备采用正交频分多址技术网络通信模式，因此：

$ {r}_{i}=B\mathrm{l}\mathrm{b}\left(1+\frac{P{s}_{i}{h}_{i}}{{\sigma }^{2}}\right) $

(10)

$ {h}_{i}=\rho {P}_{i}^{-\eta } $

(11)

其中：$ B $表示固定最大信道带宽；$ {\sigma }^{2} $表示固定信道噪声功率；$ {h}_{i} $表示移动设备$ {M}_{i} $的信道状态信息；$ \rho $表示信道功率增益；$ \eta $表示路径损耗指数。

由于返回数据量较小，本文不考虑数据回传时间，因此任务$ \mathrm{t}\mathrm{a}\mathrm{s}{\mathrm{k}}_{i, j} $的完成时间$ {T}_{i, j} $表示为：

$ {T}_{i, j}=\mathrm{m}\mathrm{a}\mathrm{x}({F}_{i, j}^{\mathrm{m}}, {F}_{i, j}^{\mathrm{v}}) $

(12)

2.3 设备能耗模型

移动设备能耗分为移动设备计算能耗和传输能耗两个部分。

首先，移动设备计算模块包括运行和空闲两种状态。当计算任务时处于运行状态，当停止计算任务时处于空闲状态，其计算公式如下：

$ {E}_{i}^{\mathrm{c}}={P}_{i}^{\mathrm{c}}\cdot \sum {t}_{i, j}^{\mathrm{m}} $

(13)

$ {E}_{i}^{\mathrm{n}}={P}_{i}^{\mathrm{n}}\cdot \left(\mathrm{m}\mathrm{a}\mathrm{x}{F}_{i, j}^{\mathrm{m}}-\sum {t}_{i, j}^{\mathrm{m}}\right) $

(14)

$ {E}_{i}^{1}={E}_{i}^{\mathrm{c}}+{E}_{i}^{\mathrm{n}} $

(15)

其中：$ {E}_{i}^{\mathrm{c}} $表示运行状态下的计算能耗；$ {E}_{i}^{\mathrm{n}} $表示空闲状态下的计算能耗；$ {E}_{i}^{1} $表示移动设备$ {M}_{i} $的总计算能耗。

然后，移动设备传输部分包括发送和空闲两种状态。由于返回数据量较小，本文不考虑数据返回能耗，其传输能耗计算如下：

$ {E}_{i}^{\mathrm{s}}={P}_{i}^{\mathrm{s}}\cdot \sum {t}_{i, j}^{\mathrm{r}} $

(16)

$ {E}_{i}^{\mathrm{r}}={P}_{i}^{\mathrm{r}}\cdot \sum ({t}_{i, j}^{\mathrm{v}}+{t}_{i, j}^{\mathrm{a}}) $

(17)

$ {E}_{i}^{2}={E}_{i}^{\mathrm{s}}+{E}_{i}^{\mathrm{r}} $

(18)

其中：$ {E}_{i}^{\mathrm{s}} $表示发送状态下的传输能耗；$ {E}_{i}^{\mathrm{r}} $表示空闲状态下的传输能耗；$ {E}_{i}^{2} $表示移动设备$ {M}_{i} $的总传输能耗。

因此，移动设备$ {M}_{i} $的总能耗$ {E}_{i} $可以表示为：

$ {E}_{i}={E}_{i}^{1}+{E}_{i}^{2} $

(19)

2.4 优化目标

为了更好地平衡任务时间延误和设备能耗，本文设计了以下的优化目标：

$ \left\{\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}{f}_{1}=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{{n}_{i}}\left(\mathrm{m}\mathrm{a}\mathrm{x}(0, {T}_{i, j}-{l}_{i, j})\right)\\ \mathrm{m}\mathrm{i}\mathrm{n}{f}_{2}=\sum\limits_{i=1}^{N}\left({E}_{i}\right)\end{array}\right. $

(20)

其中：$ {f}_{1} $是所有移动设备总延误之和；$ {f}_{2} $是所有移动设备总能耗之和。其他约束包括：边缘卸载比例变量$ 0\le {x}_{i, j}\le 1 $约束任务卸载比例变量以任意的百分比进行切分，本地排序变量$ {y}_{i, j}\le {n}_{i} $约束移动设备本地排序变量不超过该设备的任务总数量，边缘排序变量$ {z}_{i, j}\le \sum\limits_{i=1}^{N}{n}_{i} $约束移动设备边缘排序变量不超过所有设备的任务总数量。

3 两阶段优化框架

为了求解本文提出的模型，本文设计一种基于多目标优化和多属性决策的两阶段优化框架。在多目标优化阶段，提出一种改进DMP-NSGA-II算法，并设计一种基于混合式求解框架的DMP-NSGA-II算法求解多目标混合整数规划模型；在多属性决策阶段，设计一种FCM-GRP集成方法来选出不同偏好下最优折衷卸载决策。两阶段优化求解框架如图 2所示。

3.1 多目标优化阶段 3.1.1 DMP-NSGA-II算法

NSGA-II以其计算速度快、复杂度低等优点在多目标优化工程领域中得到非常广泛的应用^[18-20]，但是该算法仍然存在局部收敛和全局搜索难以平衡的问题^[21]。鉴于此，本文在NSGA-II算法的基础上提出一种改进动态多种群并行NSGA-II算法(DMP-NSGA-II)，包括多种群多交叉策略、动态调整种群规模、二次局部搜索的改进策略。首先，设计了基于非支配等级排序的种群划分方式，将单一种群划分为精英种群和一般种群，并分配不同性能的交叉算子，以平衡算法局部收敛和全局搜索能力；其次，设计了非线性种群规模动态调整策略，以提高种群的适应性；最后，采用莱维飞行的二次局部搜索策略，以增强局部搜索精度。

3.1.2 多种群多交叉策略

多种群策略可以很好地提高种群多样性，但也容易导致局部收敛能力不足。为了弥补这一缺陷，本文在NSGA-II算法基础上设计了一种新的多种群多交叉策略，通过在不同种群进化过程中采用不同性能的交叉算子，从而更好地平衡算法局部收敛和全局搜索能力。多种群多交叉策略过程如下：

首先，采用非支配排序方法将种群个体进行分级，并按照不同等级把个体分成两个子种群，分别为精英种群和非精英种群。其中，精英种群由非支配排序等级第一的个体组成，非精英种群由其他非支配排序等级的个体组成。

然后，精英种群采用模拟二进制交叉算子用于加快收敛速度，以增强局部收敛能力；非精英种群采用算术交叉算子，用于克服陷入局部最优，以增强全局搜索能力。具体来讲，随机选择两个父代为$ {x}_{1}=\left({x}_{11}, {x}_{12}, \cdots , {x}_{1n}\right) $和$ {x}_{2}=\left({x}_{21}, {x}_{22}, \cdots , {x}_{2n}\right) $，并随机选择交叉点。当采用模拟二进制交叉算子时，两个子代$ {y}_{1} $和$ {y}_{2} $交叉方式如下：

$ \left\{\begin{array}{c}{y}_{1i}=0.5\times \left[\left(1-\beta \right)\right]{x}_{1i}+\left[\left(1+\beta \right)\right]{x}_{2i}\\ {y}_{2i}=0.5\times \left[\left(1+\beta \right)\right]{x}_{1i}+\left[\left(1-\beta \right)\right]{x}_{2i}\end{array}\right. $

(21)

其中：$ \beta \left(\alpha \right)=\left\{\begin{array}{l}{\left(\alpha \right)}^{\frac{1}{\gamma +1}}, \alpha \le 0.5\\ 2{\left(1-\alpha \right)}^{\frac{-1}{\gamma +1}}, \alpha > 0.5\end{array}\right. $，$ \alpha $为[0, 1]区间均匀分布的随机数。

当采用算术交叉算子时，两个子代$ {y}_{1} $和$ {y}_{2} $交叉方式如下：

$ \left\{\begin{array}{c}{y}_{1i}=\alpha {x}_{1i}+\left(1-\alpha \right){x}_{2i}\\ {y}_{2i}=\alpha {x}_{2i}+\left(1-\alpha \right){x}_{1i}\end{array}\right. $

(22)

其中：$ \alpha $同样为[0, 1]区间均匀分布的随机数。

3.1.3 动态调节种群规模

固定子种群规模划分方式一定程度上会影响搜索性能，在进化初期应采用较大规模的非精英种群以大范围搜索，进行全局进化避免过早收敛；在进化后期应采用较大规模的精英种群以小范围搜索，进行局部进化提高解的精度。鉴于此，本文提出一种基于非线性种群规模动态调整策略，种群规模变化曲线以生物群体增长Logistic曲线为基础，其数学表达式如下：

$ \omega \left(t\right)=\lambda \left(1+\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{a}}\left(1+\frac{{F}_{1}\left(t\right)}{N}\right)\right) $

(23)

其中：$ \omega \left(t\right) $表示在$ t $次迭代中精英种群占整个种群的比例；$ {F}_{1}\left(t\right) $表示在$ t $次迭代中非支配排序等级第一的种群数量；$ N $表示种群总数；$ \lambda $为调节系数，可随环境不同适当调整，本文取值为0.2。此外，为了防止搜索停滞，采用最大最小限制方法将精英种群占种群总数的比例限制在$ \left[{\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}, {\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $的范围，其中：

$ \omega \left(t\right)=\left\{\begin{array}{l}{\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}, \omega \left(t\right)\le \omega \\ {\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}, \omega \left(t\right)\ge \omega \\ \omega \left(t\right), {\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}}\le \omega \left(t\right)\le {\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}}\end{array}\right. $

(24)

其中：$ {\omega }_{\mathrm{m}\mathrm{i}\mathrm{n}} $和$ {\omega }_{\mathrm{m}\mathrm{a}\mathrm{x}} $分别为精英种群占种群总数比例的最小值和最大值，可随环境不同适当调整，本文分别取值为0.2和0.8。

3.1.4 二次局部搜索策略

为了防止精英种群中的个体陷入局部最优，增强精英种群个体的局部搜索性能，本文引入了基于莱维飞行的二次局部搜索策略，通过在种群进化过程中周期性地执行局部搜索操作，进一步改善对已知搜索区域的搜索深度。莱维飞行是一种长短步相间的飞行方式，这种随机的飞行方式使得搜索范围加大，找到最优解的概率也相应增加。对当前精英种群采用莱维飞行的个体更新公式为：

$ {x}_{i}\left(t+1\right)={x}_{i}\left(t\right)+\alpha \oplus \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}\left(\lambda \right) $

(25)

其中：$ \alpha $是步长缩放因子，本文取值为1；$ \oplus $表示点对点乘法；$ \mathrm{L}\mathrm{e}\mathrm{v}\mathrm{y}\left(\lambda \right) $表示服从莱维分布的路径。

3.1.5 DMP-NSGA-II求解模型流程

对于本文多目标混合整数问题，如何高效地处理混合整数决策变量是问题求解的关键。鉴于混合式求解框架的优势，本文设计了一种基于混合式求解框架的DMP-NSGA-II方法求解本文模型，离散变量和连续变量并行执行交叉、变异的进化操作。基于混合式求解框架的DMP-NSGA-II算法求解模型具体步骤如下：

1) 变量编码与解码。以边缘卸载比例变量$ {x}_{i, j} $、本地排序变量$ {y}_{i, j} $和边缘排序变量$ {z}_{i, j} $作为决策变量采用混合编码，$ {x}_{i, j} $采用连续编码方式，$ {y}_{i, j} $和$ {z}_{i, j} $采用离散编码方式，通过编码拼接可得完整染色体编码$ \left({x}_{i, j}, {y}_{i, j}, {z}_{i, j}\right) $。

2) 生成初始种群。边缘卸载比例变量$ {x}_{i, j} $取[0, 1]之间的任意数值，本地排序变量$ {y}_{i, j} $取1~$ {n}_{i} $之间的任意一种排序值，边缘排序变量$ {z}_{i, j} $取1~$ \sum\limits_{i=1}^{N}{n}_{i} $之间的任意一种排序值，设定初始种群个体的规模，同时随机产生初始种群，其中每个个体对应一种卸载决策。

3) 个体适应度计算。计算每个个体的所有目标函数值，同时采用快速非支配排序方法计算个体的非支配排序等级和基于个体目标域局部拥挤距离计算个体的拥挤度，个体适应度评价取决于个体的非支配排序等级和拥挤度。

4) 多种群划分和动态调整。按照不同等级把个体分成两个子种群，分别为精英种群和非精英种群。其中，精英种群由非支配排序等级第一的个体组成，非精英种群由其他非支配排序等级的个体组成。同时，种群规模变化曲线以生物群体增长Logistic曲线为基础，对种群规模进行动态调整。

5) 二元锦标赛选择。从种群中等概率随机选择两个个体，筛选出其中适应度较好的个体，循环执行直到种群规模达到初始种群规模。

6) 种群进化。在种群迭代进化过程中，不同种群分配不同进化能力的交叉算子，而连续编码和离散编码也分别采用匹配度更好的交叉算子。具体来讲，精英种群的连续编码采用模拟二进制交叉算子，离散编码顺序排序交叉算子；非精英种群的连续编码采用算术交叉算子，离散变量采用顺序排序交叉算子。其中，顺序排序交叉算子已被证明在求解离散的排序问题性能较为突出。同时，对于精英种群的连续编码采用基于莱维飞行的二次局部搜索策略，进一步改善对已知搜索区域的搜索深度。

7) 精英保留。将父代和子代个体重新组成新种群，并基于个体适应度从新种群个体筛选出优良个体进入下一代种群。

8) 帕累托解集。经过步骤3)~步骤7循环直到满足迭代结束，再采用快速非支配排序和拥挤度得到帕累托解集，即计算卸载决策最优集合。基于混合式求解框架的DMP-NSGA-II算法求解模型流程如图 3所示。

3.2 多属性决策阶段

为进一步给出不同偏好下最优折衷卸载决策，在多属性决策阶段设计了一种FCM-GRP集成方法。首先，采用FCM算法对获得的帕累托解集进行聚类处理，以获得不同偏好下的帕累托子集；然后，对不同偏好下的帕累托子集采用GRP算法，以选出最优折衷卸载决策。

3.2.1 FCM算法

FCM算法是一种基于函数最优方法的聚类算法^[22]，通过优化目标函数获得每个样本点对于类中心的隶属度，从而决定样本点的类属以实现样本点分类。FCM算法的目标函数和约束条件如下：

$ \left\{\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}{J}_{\mathrm{F}\mathrm{C}\mathrm{M}}\left(S, C\right)=\sum\limits_{i=1}^{{N}_{p}}\sum\limits_{j=1}^{{N}_\text{clu}}{\eta }_{i, j}{‖{s}_{i}-{c}_{i}‖}^{2}\\ \mathrm{s}.\mathrm{t}.\sum\limits_{j=1}^{{N}_\text{clu}}{\eta }_{i, j}=1\end{array}\right. $

(26)

其中：$ J $是聚类损失函数；$ S $是帕累托最优解集；$ {N}_{p} $是解集的个数；$ C=\left\{{c}_{1}, {c}_{2}, \cdots , {c}_{{N}_{\mathrm{c}\mathrm{l}\mathrm{u}}}\right\} $是聚类中心的集合；$ {N}_{\mathrm{c}\mathrm{l}\mathrm{u}} $是聚类中心的个数；$ {\eta }_{i, j} $是第$ i $个样本对于第$ j $类的隶属度，取值范围为[0, 1]。本文采取三类不同决策偏好，因此聚类中心的个数取值为3。

3.2.2 GRP算法

灰关联投影法(GRP)是基于灰色系统理论和矢量投影原理的集成方法，兼具了两者优点的同时在多属性决策领域有很好的应用^[23-24]。为此，本文选取基于GRP的多属性决策方法对多目标优化得到的卸载决策集合进行评估，根据优属度大小找到最优折衷卸载决策。最优折衷卸载决策选取过程如下所示：

首先，第$ m $个卸载决策的第$ k $个评价指标可以表示成二元组$ {S}_{m, k}=\left\{\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}{\mathrm{n}}_{m}, \mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_{k}\right\} $，$ \mathrm{其}\mathrm{中}：\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}{\mathrm{n}}_{m} $表示第$ m $个卸载决策，$ m\in \left[1, M\right] $，$ M $为卸载决策总数；$ \mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}{\mathrm{x}}_{k} $表示第$ k $个评价指标，$ k\in \left[1, N\right] $，$ N $为评价指标总数。因此，$ {S}_{m, k} $的灰关联度系数$ {\mu }_{m, k}^{+(-)} $为：

$ {\mu }_{m, k}^{+(-)}=\frac{\underset{M}{\mathrm{m}\mathrm{i}\mathrm{n}}\underset{N}{\mathrm{m}\mathrm{i}\mathrm{n}}\left|{V}_{0, k}^{+(-)}-{V}_{m, k}\right|+\gamma \underset{M}{\mathrm{m}\mathrm{a}\mathrm{x}}\underset{N}{\mathrm{m}\mathrm{a}\mathrm{x}}\left|{V}_{0, q}^{+(-)}-{V}_{m, k}\right|}{\left|{V}_{0, k}^{+(-)}-{V}_{k, q}\right|+\gamma \underset{{N}^{*}}{\mathrm{m}\mathrm{a}\mathrm{x}}\underset{Q}{\mathrm{m}\mathrm{a}\mathrm{x}}\left|{V}_{0, k}^{+(-)}-{V}_{m, k}\right|} $

(27)

其中：$ {V}_{m, k} $为标准化处理后的$ {S}_{m, k} $；$ {V}_{0, k}^{+\left(-\right)} $为标准化处理后的理想(负理想)卸载决策下的第$ k $个评价指标；$ \gamma $为分辨系数，通常$ \gamma $取0.5。

然后，$ \mathrm{d}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}{\mathrm{n}}_{m} $在理想(负理想)卸载决策上的投影值$ {L}_{m}^{+\left(-\right)} $为：

$ {L}_{m}^{+\left(-\right)}=\sum\limits_{k=1}^{N}{\mu }_{m, k}^{+(-)}\frac{{\varphi }_{k}^{2}}{\sqrt[]{\sum\limits_{k=1}^{N}{\varphi }_{k}^{2}}} $

(28)

其中：$ {\varphi }_{k} $为第$ k $项评价指标权重，表示该指标的相对重要程度，本文取$ 0.5 $。

理想(负理想)卸载决策的模值$ {L}_{0} $为：

$ {L}_{0}=\sum\limits_{k=1}^{N}\frac{{\varphi }_{k}^{2}}{\sqrt[]{\sum\limits_{k=1}^{N}{\varphi }_{k}^{2}}} $

(29)

最后，$ \mathrm{d}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}{\mathrm{n}}_{m} $的优属度$ {\delta }_{m} $为：

$ {\delta }_{m}=\frac{{\left({L}_{0}-{L}_{m}^{-}\right)}^{2}}{{\left({L}_{0}-{L}_{m}^{-}\right)}^{2}+{\left({L}_{0}-{L}_{m}^{+}\right)}^{2}} $

(30)

其中：$ 0\le {\delta }_{m}\le 1 $，其值越大表示与理想卸载决策越接近，与负理想卸载决策越远，反之亦然。因此，优属度最大的卸载决策即最优折衷卸载决策。

4 实验仿真与结果分析

实验编程软件为MATLABR2020b，运行环境Intel^® Core^TM i7-2700QCPU_2.6 GHz_16 GB_Windows10，并分别设计了测试函数和模型实例两个对比实验。

4.1 数值实验 4.1.1 参数设置

本文选取了测试函数ZDT系列中的ZDT1、ZDT2、ZDT3、ZDT4和ZDT6作为基准测试函数^[25]，并选用了两个性能评估指标HV以及SP进行评价。HV用于衡量非支配解集与参照点围成的目标空间中区域的体积，HV定义如下：

$ \mathrm{H}\mathrm{V}\left(C, R\right)=\mathrm{v}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{m}\mathrm{e}\left(\underset{x\in C}{\overset{C}{\cup }}v\left(x, r\right)\right) $

(31)

其中：$ r=\left(\mathrm{1, 1}\right) $为待评价解集$ C $的参考点；$ x=\left(\frac{{f}_{1}-{f}_{1\mathrm{m}\mathrm{i}\mathrm{n}}}{{f}_{1\mathrm{m}\mathrm{a}\mathrm{x}}-{f}_{1\mathrm{m}\mathrm{i}\mathrm{n}}}, \frac{{f}_{2}-{f}_{2\mathrm{m}\mathrm{i}\mathrm{n}}}{{f}_{2\mathrm{m}\mathrm{a}\mathrm{x}}-{f}_{2\mathrm{m}\mathrm{i}\mathrm{n}}}\right) $；$ v $表示$ x $与$ r $围成的超立方体体积。HV值越大表明待评价解集越逼近问题的真实帕累托前沿，同时更均匀地分散在目标空间中。

SP用于衡量解集中每个解到其他解最小距离的标准差，SP的定义如下：

$ \mathrm{S}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{n}\mathrm{g}\left(P\right)=\sqrt[]{\frac{1}{\left|P\right|-1}}\sum\limits_{i=1}^{\left|P\right|}{\left(\stackrel{-}{d}-{d}_{i}\right)}^{2} $

(32)

其中：$ {d}_{i} $表示第$ i $个解到PF中其他解的最小距离；$ \stackrel{-}{d} $表示所有$ {d}_{i} $的均值；$ \left|P\right| $代表所有解的个数。SP的值越小越说明算法所求解的分布越均匀。

4.1.2 算法对比分析

为了验证提出DMP-NSGA-II算法的性能，选取NSGA-II算法、MOEA/D算法^[26]及MOEA/D-DE算法^[27]3种应用较为广泛的多目标算法进行对比。涉及到这4种算法共同参数设置包括：种群个数为100，最大迭代次数为200，交叉概率为0.9，变异概率为0.1，其他参数设置与上述算法保持一致。此外，为每个算法设置相同的初始种群，独立运行10次，以实现对比公平性。HV指标和SP指标的均值(方差)结果如表 1和表 2所示，其中加粗标注为最优表现。

从表 1和表 2中可以看出，在ZDT1、ZDT2、ZDT3、ZDT6中，DMP-NSGA-II的HV指标均值和方差、SP指标均值都优于其他3个算法，具有非常明显的优势。而在ZDT4问题中，虽然DMP-NSGA-II的HV指标均值表现弱于MOEA/D，但SP指标均值仍然能够获得最好的表现。此外，DMP-NSGA-II的SP指标方差虽然没有表现出很明显的优势，但是相较NSGA-II仍然有较大提升。综上，DMP-NSGA-II的改进预期目标已经基本达到，即通过多种群多交叉、动态调整种群规模、二次局部搜索的改进策略，增强NSGA-II算法局部收敛和全局搜索能力。

4.2 模型算例 4.2.1 数据准备

本文实验仿真了一个真实的计算卸载应用场景，并从文献[28-30]中选择相应参数的值范围。首先，采用路由节点提供的传输网络，其固定最大信道带宽为5×10⁶ Hz，固定信道噪声功率为10^-13，信道功率增益为2，路径损耗指数为10^-4，网络半径为200 m。单个边缘服务器位于无线路由旁侧，其计算能力为5×10⁶ MIPS，每个移动设备通过无线网络连接到路由节点并转发到边缘服务器。其次，3个移动设备随机部署在网络中，其计算能力范围为0.1×10⁶ MIPS~0.2×10⁶ MIPS，计算模块在工作和空闲状态下的功率范围分别是100~300 mW和5~10 mW，通信模块在传输和空闲状态下的功率范围分别是50~150 mW和8~15 mW。最后，假设每个移动设备任务并发数均为3，每个并发型任务软截止时间范围为0.1~2.0 s，每个并发型任务数据量范围为10~200 KB。

4.2.2 算法性能比较

为了求解多目标并发型任务计算卸载混合整数规划模型，分别采用基于混合式求解框架的NSGA-II算法和DMP-NSGA-II算法进行对比求解。同时为了全面衡量算法在模型求解上的有效性，在HV和SP优化指标的基础上增加了平均延误Meantime和平均能耗Meanenergy两个模型评价指标。两个算法的种群规模为100，最大迭代次数为200，交叉概率为0.9，变异概率为0.1。表 3所示为两种算法求解模型10次得到的HV、SP、Meantime和Meanenergy指标的均值(方差)结果，其中加粗标注为最优表现。从表 3可以直观地看出，DMP-NSGA-II算法在HV、SP、Meantime和Meanenergy平均值、方差上的表现全面要优于NSGA-II算法，这表明基于混合式求解框架的DMP-NSGA-II算法在求解模型时具有更优的求解精度和稳定性。

4.2.3 模型参数分析

为研究任务的数据量对于时间延误和能耗的影响，图 4仿真了不同任务数据量下时间延误和能耗的变化情况，包括数据量为0.1~0.5 MB、0.5~1.0 MB、1~2 MB和2~4 MB这4种情况。从图 4可以直观地看出，随着任务数据量的不断增加，对应的时间延误和能耗呈明显增加趋势，其原因可能是较大的任务数据量会增加本地执行时间、数据传输时间和边缘执行时间，从而导致任务整体执行时间的延长，而较大的任务数据量也会带来计算模块和通信模块更多的能耗。此外，不同数据量规模下其帕累托曲线仍然可以保持很好的收敛性和多样性，这表明提出的DMP-NSGA-II算法可以很好地适应不同任务数据量的计算卸载问题。

为研究任务并发数对于任务竞争程度的影响，图 5仿真了不同任务并发数下时间延误和能耗的变化情况，包括任务并发数3、4、5和6这4种情况。从图 5可以直观地看到，随着任务并发数的不断增大，对应的时间延误和能耗呈上升趋势，尤其是时间延误显著增加，其原因可能是较大的并发数会增加任务在本地和边缘排队时间，排队靠后的任务时间延误会显著增加，进一步增加了整体时间延误，这也表明并发数增加会恶化任务之间竞争程度，而能耗的增加是因为任务个数增加也会带来计算模块和通信模块更多的能耗。在不同任务并发数下，其帕累托曲线仍然可以保持很好的收敛性和多样性，这表明提出的DMP-NSGA-II算法可以很好地适应不同任务并发数下的计算卸载问题。

为研究边缘计算卸载对于并发型计算任务的重要性，图 6仿真了不同边缘服务器计算能力下时间延误和能耗的变化情况，分别包括边缘计算能力为0.5、1、5、10和50 MIPS这5种情况。从图 6可以直观地看出，随着边缘服务器计算能力的不断增大，对应能耗和时间延误呈下降趋势，其原因可能是当边缘计算能力远远大于本地计算能力时，会将更多的数据量卸载到边缘侧执行，以减少本地执行数据量，从而缩短了任务执行时间。同时，由于传输功率远远小于计算功率，随着卸载的数据量增加，计算能耗的减少远远大于传输能耗的增加，从而减少了设备整体能耗。当边缘计算能力为50 MIPS时只存在一个解，即全部并发型任务卸载到边缘端执行的完全卸载方案，其计算时间和能耗都趋近于零，该解相当于一个极限点。同样，不同任务并发数下其帕累托曲线仍然可以保持很好的收敛性和多样性，这表明提出的DMP-NSGA-II算法可以很好地适应不同边缘计算能力下的计算卸载问题。

4.2.4 不同偏好下最优折衷解分析

通过上述分析可以看出，时间延误和能耗两个优化目标之间是矛盾的，时间延误改善有可能会引起能耗降低，难以使时间延误和设备能耗同时达到最优值，只能选取具有代表性的少量计算卸载方案。为此，本文分别选取3种代表性的偏好，包括偏好时间延误、偏好设备能耗和无偏好，并采用FCM-GRP集成方法选取出具有代表性的折衷解。

首先，采用FCM算法对卸载方案集合进行聚类处理，得到的3种偏好下聚类结果如图 7(a)所示。从图中可以直观地看到，卸载方案集合被分为3类，三角形DM-1表示偏好能耗，圆圈DM-2表示无偏好，五角星DM-3表示偏好时间延误。

然后，采用GRP方法计算相应的优属度，得到的3种偏好下选解结果如图 7(b)所示。其中，实心的点表示不同偏好下最优折衷卸载方案。

5 结束语

本文针对移动边缘计算场景下的并发型数据流任务计算卸载及资源竞争问题，设计一种基于并发型数据流任务的多目标计算卸载混合整数模型，为对模型进行求解，给出一种基于多目标优化和多属性决策的两阶段优化框架，并分别在多目标优化阶段和多属性决策阶段提出改进动态多种群并行NSGA-II(DMP-NSGA-II)算法与基于模糊C均值聚类和灰关联投影法的后验选解方法。实验结果表明，在ZDT系列测试函数上，DMP-NSGA-II算法的HV和SP指标表现明显优于NSGA-II、MOEA/D和MOEA/D-DE对比算法，在模型实例上，DMP-NSGA-II算法的Meantime和Meanenergy指标相较于NSGA-II算法分别提升了30.1%和8.9%。由于本文研究重点为并发型数据流任务的计算卸载，下一步将对柔性依赖性任务的计算卸载问题进行研究。同时，高维多目标计算卸载问题也是后续将要关注的研究方向。