基于卸载策略的物联网边缘计算任务调度优化

摘要：移动边缘计算 （Mobile Edge Computing， MEC） 通过将计算任务卸载到边缘服务器， 为用户提供了低延时、低能耗的服务，解决了传统云计算的不足。在移动边缘计算中，如何进 行卸载决策是提供低延时、低能耗服务的关键技术之一。除此之外，由于无线信道的带宽资源 有限，不合理的带宽分配会使用户设备的能耗和延时增加，因此如何进行合理的资源分配也是 边缘计算实现的关键。为联合优化时延、能耗与计算资源，本文提出了一个基于蒙特卡洛树搜 索的多通道探索算 法 （Multi-Channel Search Algorithm based on Monte Carlo Tree Search， MCS-MCTS）。首先，以延时和能耗的成本为优化目标，将计算资源分配决策及传输功率建模 决策建模为凸优化问题，采用梯度下降法求解最优传输功率分配问题，通过拉格朗日乘子法及 卡罗需-库恩-塔克 （Karush-Kuhn-Tucker， KKT） 条件求解最优计算资源分配问题。随后，通过 MCS-MCTS 算法处理二进制卸载决策问题，为避免搜索结果陷入局部最优，引入模拟退火算 法。数值结果表明，MCS-MCTS 算法能在线性相干时间内得到接近最优的卸载决策与资源分 配决策，与现有的启发式搜索算法相比，该算法可以在减少时间复杂度和提高系统能量有效性 的同时，达到接近最优的性能。

关键词：物联网；移动边缘计算；深度学习；任务卸载；资源分配

中图分类号：TN915

文献标志码：A

随着人工智能、移动通信与物联网设备的日益 普及，涌现出了在线游戏、虚拟现实等众多新型、高 需求量的应用，此类应用需要无线设备终端拥有庞 大的计算能力，从而导致更多的能量消耗。但是，目 前设备终端计算能力是有限的，导致设备的硬件设 施条件要求更高，无法满足多样化的应用需求，设备 对资源消耗过高的应用无法进行实时解决。因此， 如何在设备上提高数据计算处理能力，同时解决高 时延与高能耗的问题成为了当前研究热点。随着第 五代移动通信技术的核心技术之一—移动边缘计 算技术[1] 的不断发展，无线设备的计算能力得到了显 著的提升，移动边缘计算（MEC）将计算资源和服务 直接部署在终端的边缘服务器，以相对较低的网络 延迟传输数据信息，从而提供更快的响应时间和更 低的能量消耗，满足了当前市场对于低时延和低功 耗的需求。

当前国内外对移动边缘计算任务卸载技术的研 究主要集中于能耗与延时的降低方面。Cui 等[2] 提出了一种新的基于多用户细粒度的物联网卸载调 度方法来解决 MEC 中细粒度卸载的能量和延迟问 题，将计算卸载视为一个约束多目标优化问题，然后 提出了一种改进的 NSGA-II 算法来解决该问题，该 算法可以实现局部和边缘并行处理，有效地降低了 延迟和能耗。Dai 等[3] 在工业物联网提出了一种使 用 D2D 辅助 MEC 网络中整合迁移成本和卸载意愿 的共同卸载框架，在此基础上设计了一种基于学习 的任务协同卸载算法，该算法使工业物联网设备能 够从候选边缘节点中观察和学习系统成本，从而在 不需要完整卸载信息的情况下选择最佳边缘节点。 Chen 等[4] 提出了采用人工智能的方法来实现物联网的普及连接以及可靠的低延时通信。Zhao 等[5] 提出 了一种基于 ARIMA-BP 的选择性卸载策略（ABSO）， 该策略在满足延迟要求的同时，最大限度地减少了 移动设备的能耗。Bi 和 Tran 等[6-7] 提出了启发式局 部搜索算法，Dinh 等[8] 提出了半定松弛方法。每当 信道环境发生较大变化时，这些算法都需要重新进 行大量的迭代才能适应新的信道环境，因此它们并 不适用于快速衰落信道。 Chen 等 [9]研究了动 态 MEC 系统中的任务卸载调度问题，通过将能量收集 技术集成到物联网设备中，提出了一种混合能源供 应模型，随后基于随机优化理论提出了一种在线动 态任务卸载算法（DTOME），通过权衡系统成本和队 列稳定性来做出任务卸载决策。

本文以智慧农业大棚的物联网环境监控场景为 例，设计了一个多服务器、多无线设备的 MEC 系统 模型，通过将 MEC 技术应用于智慧农业大棚的环境 监控，来实现数据实时采集和分析，提高农业生产的 效率和质量。相较于以往的研究，本文针对新的应 用场景，通过建立多服务器、多无线设备的 MEC 系 统模型，解决了传统单服务器单设备的 MEC 系统无 法满足大规模数据处理需求的问题。同时，本文还 联合优化任务时延、设备能耗，建立了一个成本最小 化优化问题，并提出了一种基于蒙特卡洛树搜索的 多通道探索算法，该算法能够动态调整通道数和选 择最优可能导致最优解的节点，以适应不同的任务 负载和网络条件，能够高效地搜索到最优解。最后，通过实验验证了该算法的有效性。

1""" 系统模型

本文考虑的 MEC 系统以智慧农业大棚的物联 网环境监控为背景，系统模型如图 1 所示。该 MEC 系统中，无线设备产生的任务遵循二进制卸载策略。

在本文中，令N={1，2，… ，N}表示无线设备集合，令M={1，2，… ，M}表示MEC服务器集合，每一个无线设备可以选择M种MEC服务器或者直接本地执行处理任务，因此，每一个无线设备有M＋1种方式处理计算任务。用yn表示每个无线设备的卸载决策，y. E {0，1，2，… ，N}。当yn=0时，无线设备n的任务将在本地进行计算;当ya=m（l ≤m≤M）时，无线设备n的计算任务将被卸载到MEC服务器m中进行计算，用集合币= fn c N，m ∈ M}表示所有无线设备卸载策略。

本文假设每个无线设备都有一个需要完成的计算密集型任务，表示为T.={D.Z..T\"\"*}，其中，D.表示输入任务大小，Z表示完成任务所需的计算量，T表示任务所能容忍的最大时延。

任务卸载流程如图2所示，在产生一个随机任务后，首先决定是本地执行还是卸载到MEC服务器中执行，如果选择本地执行则直接计算结果，若选择卸载到MEC服务器中执行，则需要将任务上传到MEC服务器中，待MEC服务器计算完成后再将计算结果回传到无线设备中。

图 3 示出了迭代次数、无线设备数量以及模拟 次数对几种方法归一化奖励函数的影响，从图中可 以看出，本文所提出的 MCS-MCTS 算法扩大了搜索 过程，提高了全局搜索的能力，总体性能比较好，随 着迭代次数的增加其收敛速度要优于其他几种方 法，在迭代此数为 120 次左右时就基本已经完成收 敛；而本地执行 LE 由于只能使用本地资源，导致系 统处理任务效率低，因此其获得的奖励最低；而除了 OE 外其他方法基本 在 200 次左右全部收敛 ， 但 OE 方法可能导致系统一些关键功能或性能缺失，系 统的覆盖范围受到影响，导致性能下降，从而影响其 归一化奖励值，因此实验参数选取为 220 次迭代次 数。从图 3（b） 中可以发现，对于不同数量的移动设 备，MCS-MCTS 的中位数总是接近于 1，置信区间大 多高于 0.995，相比之下其他两种方法的置信区间虽 然大多都大于 0.980，但明显 MCS-MCTS方法可以在 不同的网络布局下实现接近最优的计算性能。从 图 3（c） 可以看出，模拟次数超过 2000 时，归一化奖 励值趋于稳定，约为 0.998，由此可知，本文所提出的 MCS-MCTS 算法可以获得接近于最优的任务调度 解，图形的波动是由于随机采样造成的。

图 4 描述了不同参数下几种算法的系统成本对 比。图 4（a） 示出了无线设备数量 N 对系统成本的影 响。随着移动设备数量增多，系统成本急剧增长，这 是因为移动设备数量越多，所需要处理的任务也更 多，导致传输时延与能耗都更高，因此所需系统总成 本会更大。图 4（b） 描述了几种方法在不同的时间权 重 与和能耗权重 下对系统成本的影响，当 取 不同参数时，则相应地 ，由图可以看出，本 地执行时系统成本随着 的增大、 的减小而不断 减小，卸载执行时系统成本则随之不断增大，而其他 方法在增大到一定程度时，系统成本有着下降的趋 势，从图中明显看出，MCS-MCTS 算法要优于其他 DQN 算法与 GA 算法。图 4（c）与图 4（d） 描述了输入 任务大小与完成任务所需计算量变化时，几种方法 所需系统成本的对比。从图中可以看出，除了本地 执行计算任务时，系统成本不会随着输入任务大小 增大而改变外，其余方法均随着输入任务大小或随 着完成任务所需计算量的增大而增大。本地执行计 算任务时，由于其计算时间与能耗均与输入的任务 大小无关，因此本地计算时系统成本不会随着输入 任务大小改变而改变。综上，与其他几种方式相比， MCS-MCTS 算法在减小系统成本上有着明显优势。 因此，选择合适的输入任务大小与完成任务所需计 算量，对降低系统成本有着很大的作用。

图 5 描述了无线设备数 N 与服务器数 M 不同 时，几种方法对系统开销成本与奖励值的对比。由 图 5（a）～5（c） 可以看出，当 N 不变，M 增加时，只有本 地执行时的成本不变，这是因为本地执行时与是否 有边缘服务器无关，而其他几种方式的系统成本均 随着服务器数量增加而减小，因为边缘服务器数量 越多，会增加任务卸载时可供选择方案，当出现更优服务器时，卸载成本就会下降，从而使系统总成本下 降；而当 M 不变，N 增加时，无线设备数量越多，所需 处理的任务越多，因此整体所花时间与能耗均增大， 导致系统开销成本增高。显然本文所提出的 MCS[1]MCTS 方法所获得的系统成本明显低于其他几种。 由图 5（d） 可以看出，无论无线设备数量还是服务器 数量改变时，本文所提出的 MCS-MCTS 方法都能获 得更优的奖励值。

4""" 结 论

在物联网 MEC 系统中，随着无线设备计算能力 的增强与功能的复杂化，任务量不断增加。此时，若 任务全部本地执行或全部卸载执行都会造成计算压 力的急剧增加。本文针对智慧农业大棚的环境监控 应用场景下的 MEC 系统任务调度问题，建立了移动 边缘计算任务调度架构。基于该架构，以联合优化 能耗与延时为目标，提出了系统开销成本最小化的 优化问题。根据该优化问题，将计算资源分配决策 和传输功率分配决策建模为凸优化问题，并通过拉 格朗日乘子法与 KKT 条件获得最优资源分配策略， 使用梯度下降法获得最优传输功率分配策略。接 着，本文设计了一个 MCS-MCTS 算法来生成最优卸 载决策，并引入模拟退火算法增加了 MCS-MCTS 算 法收敛于最优解的可能性。在仿真实验中，对比了 MCS-MCTS、DQN、GA、OE、LE 这几种方法在不同 无线设备数量、时延与能耗权重、输入任务大小等不 同指标下的表现。结果显示，本文所提出的 MCS[1]MCTS 算法在保证决策生成效率的同时，生成了最优 的卸载决策，降低了系统的总体开销。在未来的研 究中，我们将分析大任务量时的卸载决策策略和资 源分配策略。

参考文献：

SIRIWARDHANA" Y，" PORAMBAGE" P，" LIYANAGE M， et al." A" survey" on" mobile" augmented" reality" with" 5G mobile" edge" computing：" Architectures，" applications，" and technical" aspects[J]." IEEE" Communications" Surveys" amp; Tutorials， 2021， 23（2）： 1160-1192.

CUI" Y，" ZHANG" D，" ZHANG" T， et al." A" novel" offloading scheduling" method" for" mobile" application" in" mobile" edge computing[J]. Wireless Networks， 2022， 28（6）： 2345-2363.

DAI" X，" XIAO" Z，" JIANG" H， et al." Task" co-offloading" for D2D-assisted mobile edge computing in industrial internet of" things[J]." IEEE" Transactions" on" Industrial" Informatics， 2022， 19（1）： 480-490.

CHEN" M" Z，" CHALLITA" U，" SAAD" W， et al." Artificial neural networks-based" machine" learning" for" wireless"" net[1]works：" A" tutorial[J]." IEEE" Communications" Surveys" amp; Tutorials， 2019， 21（4）： 3039-3071.

ZHAO" M，" ZHOU" K." Selective" offloading" by" exploiting ARIMA-BP for" energy" optimization" in" mobile" edge"" com[1]puting networks[J]. Algorithms， 2019， 12（2）： 48.

BI" S" Z，" ZHANG" Y" J." Computation" rate" maximization" for wireless powered mobile-edge computing with binary com[1]putation" offloading[J]. IEEE" Transactions" on" Wireless Communications， 2018， 17（6）： 4177-4190.

TRAN" T" X，" POMPILI" D." Joint" task" offloading" and resource allocation" for" multi-server" mobile-edge"" comput[1]ing" networks[J]. IEEE Transactions" on" Vehicular" Techno[1]logy， 2019， 68（1）： 856-868.

DINH" T" Q，" TANG" J" H，" LA" Q" D， et al." Offloading" in mobile edge computing： Task allocation and computational frequency scaling[J]." IEEE" Transactions" on"" Communica[1]tions， 2017， 65（8）： 3571-3584.

CHEN Y， ZHAO F， LU Y， et al. Dynamic task offloading for" mobile" edge" computing" with" hybrid" energy" supply[J]. Tsinghua Science and Technology， 2022， 28（3）： 421-432.

TRAN" T" X，" POMPILI" D." Joint" task" offloading" and resource allocation" for" multi-server" mobile-edge"" comput[1]ing networks[J]." IEEE" Transactions" on" Vehicular" Techno[1]logy， 2018， 68（1）： 856-868.

CHEN" X." Decentralized" computation" offloading" game" for mobile cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 26（4）： 974-983.

LYU" X，" TIAN" H，" SENGUL" C， et al." Multiuser" joint" task offloading" and" resource" optimization" in" proximate clouds[J]." IEEE" Transactions" on" Vehicular" Technology， 2016， 66（4）： 3435-3447.

MNIH"" V，"" KACUKCUOLU"" K，"" SLIVER"" D， et al."" Hu[1]manlevel"" control"" through"" deep"" reinforcement "learning[J]. Nature， 2015， 518（7540）： 529-533.