陆战场中的计算卸载和资源分配*

杨 力，马伟东，郭江宇，魏德宾，张钟铮

（1.大连大学通信与网络重点实验室，辽宁 大连 116620；2.南京理工大学，南京 210094；3.北方自动控制技术研究院，太原 030006）

0 引言

随着战场信息化建设的快速发展，战场数据逐渐呈现出种类繁多、更新频率大、周期短的发展趋势［1］，简单的信息收集无法支撑作战指挥，而将具备大带宽、低时延等特点的5G 网络与具备方便携带、功能全面等特点的智能设备应用于陆战场，可提升战场通信速度，保障信息及时性和继承性［2］，也可缩短OODA 循环时间。但是军事需求相较于民事需求更为复杂、苛刻，对智能设备的计算能力与存储能力也提出了更高的要求，尽管近年来智能设备的性能在不断提升，但仍表现出计算资源不足、设备功耗严重等问题。

云计算虽在一定程度上缓解了计算资源不足的问题，但由于其部署位置较远，造成作战场景下业务处理时延高、服务质量无法保障的问题［3］。相比之下，边缘计算由于其部署位置更靠近网络边缘，具备低时延、高可靠、高安全、低流量等特性，符合战场低时延响应的需求［4］，同时使武器具备一定的自主决策能力、简化指战员的理解操作［5］。但边缘计算的引入也同样带来了额外的时延和能耗，且MEC 资源有限，因此，如何有效地制定卸载策略与优化资源分配成为当今研究热点。

大量学者针对上述问题展开了详细的研究，在优化目标方面可分为以最小化任务执行时间为目标、以最小化设备耗能为目标等方向。随着5G 网络的应用，部分学者以5G 网络为应用背景，研究了5G 网络中针对接入点激增、边缘计算系统负载过大等问题的卸载策略制定。文献［6］中，KHAN 等考虑到5G 异构网络的复杂性等特性，提出了CUMS（collaborative utility-maximization scheme）卸载策略，分3 部分——MD 分组，优化资源分配与迭代资源分配对问题进行优化，并最终得出最优解。除此之外，在文献［7-10］中分别基于免疫算法、基于遗传算法等其他启发式算法对问题进行求解。面对5G环境下的超密集组网（UDN）情况，CHEN 等提出了CRADE（channel resource allocation algorithm）算法来解决任务卸载和资源优化问题［11］。但大部分研究的对象仅是单一类型的业务，未能考虑重要业务优先享用边缘资源的情况［12］，面对战场态势变化频繁、单兵穿戴设备计算能力薄弱等问题，如何综合考量各类型任务和设备本身的特性，划分优先级并将其与卸载决策的制定和资源分配的优化相结合，进而避免低优先级任务抢占高优先级任务资源的现象影响边缘计算系统在军事应用背景中的性能。

区别于现阶段的研究，本文在所构建的网络模型中根据不同类型任务的特点，对各类型任务的卸载优先级进行划分，考量各类型任务对耗时与耗能的需求，以最小化系统开销为目标的同时提升高卸载优先级任务的卸载数量，构建待优化问题，采用不同的求解方式制定卸载决策、优化资源分配。本文的主要工作如下：

1）构建单小区、多用户的边缘计算网络模型，在此网络模型中讨论不同计算模式下的系统功耗与时延。

2）根据各类型任务输入量、计算量以及时延需求，采用AHP（层次分析法），划分各种类型任务卸载优先级，以此作为后续制定卸载决策的基础。

3）根据待优化问题的特性，将优化问题转化卸载决策制定与资源分配优化两个子问题，针对子问题1，采用改进后的免疫算法进行求解，在此基础上，使用拉格朗日乘数法对子问题2 进行求解。

1 系统模型与问题分析

本章将详细介绍本文所使用的网络模型，并在此基础上叙述任务卸载过程、讨论本地计算模式和卸载计算模式下的时延构成与能耗构成。

1.1 网络模型

本文构建了一个单小区、多用户的边缘计算网络模型，并根据文献［13］将网络中待卸载任务划分为时间敏感型任务、能量消耗型任务以及成本需求型任务。如图1 所示，网络中包括一个边缘计算服务器与若干智能设备，其中，边缘计算服务器可配备在通信节点车辆或情报处理车辆；智能设备通过无线网络向边缘计算服务器提出卸载请求，且每个设备都携带一个特定类型的待计算任务。网络中，认为每个智能设备在整个通信过程与卸载过程中仅通过一条稳定的无线链路与基站进行交流，各无线链路间不存在干扰，链路环境稳定。所涉的参数如下页表1 所示。

表1 关键参数Table 1 Key parameters

图1 边缘计算网络模型Fig.1 Edge computing network model

1.2 计算模型

为方便表达，本文将任务描述成四元组，即I={Dk，Ck，Pk，Rk}。其中，Dk表示任务的输入量；Ck表示完成任务所需要的计算量；Pk表示任务的优先级；Rk表示结果大小。由于任务可以选择卸载执行或本地执行，接下来将从本地计算与卸载计算两个模式讨论计算过程中的耗时与耗能

1.2.1 本地计算模式

其中，式（1）表示任务本地执行的耗时；式（2）表示任务本地执行耗能；ξ 代表与芯片硬件架构相关的功耗系数。

1.2.2 卸载计算模式

卸载计算模式下，各设备通过无线传输的方式与边缘计算服务器沟通，并将任务卸载至边缘计算服务器进行执行，计算结果通过无线网络回传至相应设备。此模式下的时延分别由任务上传时延、任务执行时延与结果回传时延构成，由于计算任务的输出结果大小远小于输入量大小，故忽略因结果回传而带来的时延与功耗。由此，可将卸载模式时延表示为：

1.3 问题分解

基于以上分析，可进一步将设备k 的耗能与耗时归纳为：

式中，dk表示设备k 是否选择卸载任务；dk=0 表示选择本地执行任务，反之为卸载执行。进而根据不同类型任务对时延和功耗的不同需求，将执行任务k 的系统开销定义为：

综上所述，以降低系统开销为目标优化卸载决策与资源分配，并表达为：

其中，条件c1 表示设备k 的任务仅能选择本地执行或卸载执行；条件c2 表示被卸载的任务总数不能超过MEC Sever 可服务任务数的上限；条件c3、c4 表示分配给各个卸载任务计算资源的取值范围，且总和不能超过MEC Sever 的总计算资源；条件c5 与c6 表示时间参数与功耗参数的取值范围及关系。

由于卸载策略为离散型变量，而计算资源为连续性变量，故待式（12）为MINP（混合整数非线性规划问题），直接对其求解存在极大的困难，为了方便求解，将上述问题解耦成两个子问题，解耦后的两个问题为：1）卸载策略制定问题；2）资源分配优化问题。

2 问题求解

2.1 卸载优先级划分

不同类型的任务具有不同的数据输入量、时延要求及计算要求，难以根据单一的任务属性划分其卸载优先级，对此，本文采用多属性决策AHP 予以解决。

首先，如式（13）所示，构建矩阵

可见矩阵A 为一致阵，根据一致阵每一个列向量都是特征向量的特性，本文采取简化计算法计算矩阵的特征向量与特征值，过程如下：

计算后的特征向量为：

时延敏感型任务卸载优先级> 能量消耗型任务卸载优先级>成本需求型任务卸载优先级。符合战场在信息收集和行动指挥方面低时延的需求。

2.2 基于免疫算法的卸载决策的制定

将上文中所涉及的subProblem1 表示为：

可见式（14）为NP 问题，直接求解复杂且困难。为解决式（14），本文参考文献［16-17］，采取启发式算法求解，由于免疫算法具有“确定”与“随机”结合与全局寻优的特点，本文拟将任务卸载优先级与免疫算法结合，改进免疫算法中的变异操作，使算法在以最小化开销为目标的求解过程中，将更多的高卸载优先级任务卸载至边缘计算服务器。详细过程如算法1 所示。

算法根据设备数生成相应数量的待卸载任务，并根据其他限制条件生成数量为S 的初始种群，即备选解。当进化代数为0，即初代种群，算法根据下述各式计算各个抗体的目标值、浓度、亲和度及激励值等参数，并根据排序结果，选择初代最优抗体。当算法进入迭代阶段，通过反复计算上述各值，并根据激励值选择抗体进行克隆、交叉操作。结合任务卸载优先级的概念，对抗体进行变异操作。变异操作结束后，针对变异后的抗体采取克隆抑制操作，选取目标值低、浓度低的个体进入下一代种群，保证种群多样性。每次迭代后都将本代最优抗体与当前最优抗体进行比较，生成新的最优抗体，直至算法迭代次数达到最大，算法最后输出的最优抗体即为卸载决策。

算法1.基于免疫算法的卸载策略制定输入：种群个体S，迭代次数T，交叉率pc，变异率images/BZ_22_2075_578_2225_621.png编码长度CHROMLENGTH.初始化：生成CHROMLENGTH 个卸载任务，生成S 个个体将最优解的目标值初始化为Ibest=∞。标记任务优先级while iteration ≤T do for i=0 to S do依据式（14）计算个体目标值依据式（19）计算个体亲和度依据式（20）计算个体激励值end for免疫选择操作for i=1 to S do随机选取两个抗体以交叉率pc 执行交叉操作end for for i=1 to S do随机选取一个基因位，依据式（21）进行变异操作end for克隆抑制操作，选取低目标值、低浓度抗体并形成新种群查询本次迭代后最优抗体的images/BZ_22_1731_1547_1787_1593.pngif images/BZ_22_1313_1606_1464_1651.pngthenimages/BZ_22_1285_1664_1445_1710.pngend if end while输出：Offloading strategy A

算法1 中，依据式（15）、式（16）计算各抗体间相似度，

进而依据式（17）、式（18）计算抗体浓度，其中，rad 为相似度阈值，

依据式（14）、式（19）分别计算各个抗体的目标值与亲和度，

根据式（20）计算各抗体的激励值。

为模仿基因突变过程以获取更优结果，算法对克隆后的抗体将进行变异操作。依据抗体长度随机生成变异位；判断变异位任务所属的优先级，如式（21）所示，根据不同任务卸载优先级的变异率进行变异；重复此操作直至所有克隆个体都经历变异过程。针对过程中存在的不合理个体，算法采取遗弃并补充新抗体重新进行变异操作的处理方式。

2.3 基于拉格朗日乘数法的资源分配优化

通过上述方法，已经获得卸载决策，由于sub-Problem2 为有约束条件最优化问题，故在上述研究的基础上，使用拉格朗日乘数法对subProblem2 进行精准求解，具体如下。

将subProblem2 表示为：

并将其与约束条件构建成如下拉格朗日函数：

结合约束条件，即可获得最终结果：

3 仿真及结果分析

本章将对上述算法进行实验仿真，验证其可行性与优越性。本文对时间敏感型任务、能量消耗型任务与成本需求型任务设置同文献［18-20］，并取各自平均值，如表2 所示，实验其他设置如表3 所示。

表2 任务设置Table 2 Task settings

表3 仿真参数设置Table 3 Simulation parameter settings

为方便比较，共设置以下几种情况：

1）全本地模式：所有待执行任务不进行卸载，全部本地执行；

2）全卸载模式：在满足约束的条件下，将所有任务卸载至MEC Sever 进行执行，不在本地执行；

3）改进算法：即本文所讨论的结合任务卸载优先级的免疫算法，通过多次迭代求解卸载决策，并结合拉格朗日乘数法，获取最终系统开销；

4）传统算法：即未改进的免疫算法，默认认为所有任务都是同等优先级，在执行变异操作过程中不细致区分，且计算资源分配方式为平均分配。

3.1 算法收敛性分析

针对式（14）的求解过程虽包含两个阶段，但算法的收敛性仅与改进后的免疫算法有关，故仅对其进行收敛性验证。本文在用户总数为15 个且每个用户仅携带一个待卸载任务的条件下，针对时间敏感型任务在总任务中占比为40%、60%、80%三种情况进行验证，仿真结果如图2 所示。

图2 算法敛散性Fig.2 Convergence of algorithms

由图2 可知，改进后的免疫算法运行先期呈现逐步降低趋势，高卸载优先级任务不同占比情况下虽略有差别，但当迭代次数达到80 代左右时，所有情况的系统开销变化甚微，直至1 000 代算法结束，基本保持不变。由此可知，改进后的免疫算法具有收敛性。

3.2 系统开销及卸载数量分析

针对系统开销问题，在逐步增加用户数量的同时考量高卸载优先级任务在不同占比情况下的系统开销大小，如图3 所示。

图3 系统开销Fig.3 System overhead

如图3（a）所示，若高卸载优先级任务占比为40%，当用户数量较小时，改进后的免疫算法虽比全本地模式与传统算法具备更低的系统开销，但表现仍不如全卸载模式。当用户数量到达35 个后，全卸载模式的系统开销高于改进后的算法与传统算法，这是由于随着用户数量的增大，边缘计算服务器中有限的计算资源不能够满足所有任务的计算需求，影响任务执行质量。图3（b），图3（c）所显示的情况大致与图3（a）相同，改进算法分别于用户数量30个和25 个左右时表现优于全卸载模式。且随着高优先级任务占比的逐步提升，系统开销逐渐减少，这是因为高优先级任务输入量与计算量都小于其他两种类型的计算任务，当高优先级任务占比较少时，其他两种任务占比较多，故而系统开销较大。

针对高卸载优先级任务被卸载数量问题，仿真结果如图4 所示。

图4 高优先级任务卸载数量Fig.4 Number of high-priority tasks unloaded

由图4（a）可知，当高卸载优先级任务占比为40%时，改进算法的高卸载优先级任务卸载数量少于传统算法的高卸载优先级任务卸载数量，这是因为传统算法在进行变异操作时，不区分任务卸载优先级，导致低卸载优先级任务和高卸载优先级任务具备同样地位，使得低卸载优先级任务抢占高卸载优先级任务的卸载机会。由图4（b）、图4（c）可知，随着高优先级任务占比的增加与任务数量的增加，改进算法的卸载数量呈现大于传统算法的卸载数量的趋势。当高卸载优先级任务占比较多时，改进算法可使更多的高卸载优先级任务被卸载执行。结合针对图3 的分析可知，改进算法实现了降低系统开销的同时增加高卸载优先级任务卸载数量的目标。

3.3 算法卸载率分析

由图5 可知，无论高卸载优先级任务占比如何，改进算法的最终卸载率都由初始的1.0 左右逐步降低至0.5～0.6 左右。这是因为当用户数量较少时，边缘计算服务器可满足有所任务的卸载需求，但MEC Sever 服务能力有限，随着用户数量的增加，边缘计算服务器不得不拒绝部分卸载请求，当达到最大可卸载数量后，剩余任务将在本地执行，故图5呈现逐步降低趋势。

图5 卸载率Fig.5 Unloading rate

4 结论

本文以陆战场为应用背景，提出了一种考虑任务卸载优先级的卸载策略制定和资源分配优化解决方法。基于所提出的单边缘计算服务器、多用户网络模型，讨论了不同模式下的耗时模型、耗能模型；将难于直接求解的问题分解为两个易于求解的子问题，并分别采用改进后的免疫算法与拉格朗日乘数法求解，意在降低系统开销的同时使更多的高卸载优先级任务能够被卸载至网络边缘。经过实验仿真，验证了改进后算法的收敛性与优越性。

在未来工作中，将以此研究为基础，把针对任务卸载优先级的卸载策略推广至星地结合网络环境中，并继续优化包括无线资源、发射功率在内的其他资源分配。同时结合机器学习的思想，将战场任务分类细致化、准确化，将卸载优先级划分合理化，为战场指挥提供技术支撑。