面向移动感知的计算卸载及资源分配策略研究.pdf

第 49卷 第 8期2023年 8月Computer Engineering 计算机工程面向移动感知的计算卸载及资源分配策略研究班玉琦1，段利国1，温昊宇2，李爱萍1，赵菊敏1（1.太原理工大学 信息与计算机学院，山西 晋中 030600；2.南京农业大学 人工智能学院，南京 210031）摘要：在移动边缘计算(MEC)中，用户设备将计算密集任务卸载至边缘服务器执行以降低执行时延与能耗，基于5G 技术的新型应用要求计算过程支持设备的高速移动性，而目前计算卸载方案的研究大多集中于静态场景。为提高用户体验质量，在多设备与多 MEC 服务器场景下，对 MEC 中考虑设备移动轨迹的计算卸载方案进行研究。结合设备移动性、计算与通信资源、信道状态及任务需求等因素,将场景下的计算卸载方案设计为混合整数非线性规划问题。为降低求解难度，将上述问题分解为卸载服务器选择问题和固定服务器选择方案下的计算资源分配与子信道选择问题，采用凸优化技术及改进的 Kuhn-Munkres算法对子问题进行求解，并依据子问题的解设计启发式卸载服务器选择算法，基于多项式时间复杂度获得次优卸载方案。通过 EdgeCloudSim 工具对本文卸载策略进行仿真，并与常用的卸载算法进行对比，实验结果表明，该算法在满足任务的实时性要求下，与穷举算法的平均系统效用差距控制在 2.3%以内。关键词：移动边缘计算；移动感知；计算卸载；资源分配；卸载算法开放科学（资源服务）标志码（OSID）：源代码链接：https：/ J.计算机工程，2023，49（8）：163-173.英文引用格式：BAN Y Q，DUAN L G，WEN H Y，et al.Research on mobility-aware computation offloading and resource allocation strategy J.Computer Engineering，2023，49（8）：163-173.Research on Mobility-Aware Computation Offloading and Resource Allocation StrategyBAN Yuqi1，DUAN Liguo1，WEN Haoyu2，LI Aiping1，ZHAO Jumin1（1.College of Information and Computer，Taiyuan University of Technology，Jinzhong 030600，Shanxi，China；2.College of Artificial Intelligence，Nanjing Agricultural University，Nanjing 210031，China）【Abstract】In Mobile Edge Computing（MEC），user equipment offloads computationally intensive tasks to edge servers for execution to reduce execution delay and energy consumption.This process requires 5G technology-based applications to support the high-speed movement of devices during computing.However，much of the current research on computational offload solutions is focused on static scenarios.To improve the quality of user experience，this study investigates a computational offloading scheme that considers device movement trajectories in MEC and thus more suitable multi-device and multi-MEC server scenarios.Because this scheme considers multiple factors such as device mobility，computing and communication resources，channel states，and mission requirements，it can be described as a mixed-integer nonlinear programming problem.To reduce the difficulties inherent in solving this problem，this study decomposes the problem into subproblems of offloading server selection，computing resource allocation，and subchannel selection under a fixed-server selection scheme.The convex optimization technique and improved Kuhn-Munkres algorithm are then used to solve the subproblems.This study also designs a heuristic offload server selection algorithm based on the solution to the subproblems and derives a suboptimal offload solution with polynomial time complexity.Simulations are conducted using the EdgeCloudSim tool，the results of which prove the effectiveness of the proposed algorithm as compared with five other commonly used offloading algorithms.The experimental results show that the average system utility gap between the algorithm and exhaustive algorithm can be controlled to within 2.3%when it 基金项目：国家自然科学基金（61972273）。作者简介：班玉琦（1997），男，硕士研究生，CCF 学生会员，主研方向为移动边缘计算；段利国，副教授、博士；温昊宇，本科生；李爱萍、赵菊敏，教授、博士。收稿日期：2022-12-14 修回日期：2023-01-30 Email：移动互联与通信技术文章编号：1000-3428（2023）08-0163-11 文献标志码：A 中图分类号：TP3912023年 8月 15日Computer Engineering 计算机工程meets the real-time requirements of a given task.【Key words】Mobile Edge Computing（MEC）；mobility-aware；computation offloading；resource allocation；offloading algorithmDOI：10.19678/j.issn.1000-3428.00665220概述 物联网的快速发展与移动终端设备的技术进步促 进 了 新 型 应 用 的 普 及，而 用 户 设 备（User Equipment，UE）中有限的资源很难支持这些新型应用。由 移 动 边 缘 计 算（Mobile Edge Computing，MEC）1-2演变而来的多接入边缘计算3技术提供了更好的解决方案。MEC 旨在将原来置于云计算平台的功能和服务“下放”到移动网络的边缘，并在移动边缘网络中提供处理这些功能和服务所需要的通信、存储和计算等资源，从而使用户可以获得高带宽与超低时延的高质量网络功能服务。由此形成的计算卸载4旨在将计算密集型应用从计算资源匮乏的UE 卸载到边缘网络中具有强大计算能力的服务器上，从而解决终端计算任务能耗大、时延长、实时感知等问题。根据优化目标的不同，现有的计算卸载方案主要分为最小化时延4-5、最小化能耗6-7、权衡时延与能耗8-9。目前针对计算卸载的多数研究场景都假设为准静态场景，即假设设备在卸载过程中保持静止，时间范围从数百毫秒到几秒10，或忽略了设备移动带来的影响。然而，在现实世界的多数应用场景中，用户设备的移动性是不可忽视的。如在车联网场景中，车辆在行驶过程中发生卸载，车载设备需要将所执行任务的输入数据通过无线信道传输至基站所部署的边缘服务器上。由于车辆的高速移动，车辆位置在任务输入数据传输开始到结束的过程中改变较大，这造成了信道状态的较大变化。同时，在一些任务输入数据量较大11、信道带宽较小，或是存在干扰等因素的场景中也会出现信道状态的波动。若设备移动到服务基站覆盖区域外而没有及时进行基站切换，可能会导致任务卸载失败。在此类应用场景中，准静态场景下的卸载决策会导致对卸载任务过程中产生的时延与能耗计算不准确，最终会影响卸载决策的性能或卸载的准确性。因此，当考虑用户移动性时，设计最优计算卸载策略更具有挑战性。目前，研究者对 MEC 中移动性进行了广泛研究，并从不同角度提出了许多支持用户移动性的方法，按是否可预知设备在卸载期间的移动路径，现有工作可以分为两类。文献 12-14 使用移动预测的方法预测用户设备未来移动轨迹，并据此设计计算卸载方案。文献 12 利用 Geolife 轨迹模拟用户移动，使用 Miac 预测模型预测用户未来移动信息，并设计了基于深度强化学习的算法来对卸载问题求解，文献 13 使用卡尔曼滤波算法预测用户移动，提出 一 种 基 于 亲 和 度 传 播 的 聚 类 辅 助 卸 载 方 案，文献 14 采用 ConvLSTM 来预测设备的移动，在终端、边缘、云协同计算模式下将卸载优化问题转化为马尔可夫决策问题，并提出一种基于深度强化学习的任务卸载方法。文献 15-17 研究设备移动路径已知场景下的计算卸载问题。文献 15 假设移动设备在未来一段时间内可预测，并提出一种移动性感知卸载算法，文献 16 考虑设备移动引起的数据上传率变化，在此基础上提出基于凸优化和拉格朗日方法的卸载策略，文献 17 在智能检测场景和设备检测路径已知的前提下，提出一种基于博弈论的分布式算法来设计任务卸载及迁移方案。此类计算卸载方案依赖于未来信道状态及设备位置的预测结果，且算法一般具有较高的时间复杂度。还有一类计算卸载方案不考虑移动设备的未来运动轨迹、信道状态等先验知识，一般以设备的长期系 统 效 用 为 优 化 目 标。文 献18设 计 一 种 基 于Lyapunov优化和半定规划的在线移动性感知卸载与资源分配算法，该算法不需要预先了解用户移动性、能量收集模型和信道状态。文献 19 设计一种适用于可分割应用的跨边计算卸载框架，并基于此提出一种支持设备移动的在线算法。文献 20 提出一种利用非正交多址和双连通的计算卸载方案，该方案联合优化任务分割和功率分配以最小化总能量消耗。文献 21 考虑了设备移动造成的任务交接时间成本，按用户端是否拥有基站端信息分 2 种情况讨论，并提出 2种卸载算法。此外，支持设备移动性的技 术 还 包 括 任 务 迁 移 方 案 设 计17-18与 路 径 选择11等。上述计算卸载方案从不同角度及适用场景来支持用户的移动性。然而，目前的工作对设备移动性的处理方式主要包括：划分时间间隔，认为移动设备在单间隔内保持静止且信道状态不发生变化；或是认为设备在单个基站通信范围内状态不发生变化，只考虑设备在基站间移动时的移动性造成的影响。这些处理方式没有考虑设备的实时变化性，并且这类措施对不同移动速度设备评价的准确性是不同的，在高移动性场景下对系统的评估往往会与实际结果有较大出入。针对移动性所带来的问题，本文在多边缘服务器多设备场景下，充分考虑设备移动性、无线信道状态、边缘服务器及移动设备端计算资源可用性和任务需求等因素，以用户端整体时延与能耗为优化目标，提出一种低复杂度的次优卸载方案。首先结合场景中设备的移动性，评估移动对卸载过程的影响。围绕设备消耗的时延与能耗加权和，建立联合任务164第 49卷 第 8期班玉琦，段利国，温昊宇，等：面向移动感知的计算卸载及资源分配策略研究卸载决策、计算及通信资源分配方案的系统效用模型。联合资源分配的卸载决策问题为混合整数非线性规划问题，由于对问题的直接求解较为困难，因此将原问题分解为卸载服务器选择问题、边缘服务器计算资源分配问题及子信道选择问题，使用凸优化技术及改进的 Kuhn-Munkres算法解决固定服务器选择方案下的计算资源分配问题及子信道分配问题，并在 2个子问题解的基础上，设计一种启发式的卸载服务器选择算法，以较低的复杂度获得次优卸载方案。1系统模型 本文研究超密集网络下的计算卸载问题，通过密 集 部 署 低 功 率 小 型 基 站（Small Base Stations，SBS）缓解宏基站压力，同时覆盖宏基站存在的盲区，进一步解决移动设备计算能力不足以及存储资源受限等问题。图 1所示为多用户多服务器的 MEC系统，该区域可以是学校、小区或医院等。将区域内MEC 服务器集编号为M=12M，部署在 SBS上，为资源受限的移动设备提供服务。MEC 服务器可以是中等计算能力的虚拟机或是物理服务器8。区域内的移动设备（如手机、智能眼镜、手环等）记为N=12N，设备可将自身产生的计算密集型任务通过无线信道卸载至就近的 MEC 服务器执行，从而减少执行任务的时延与能耗，提高用户体验。移动设备可以在区域内随机移动。类似于文献 15 的研究，设备轨迹预测是当前智能交通领域中广泛研究的课题之一，目前对设备移动轨迹的预测方法可以在路线状况复杂的情况下实现高预测精度，因此本文假设可以在任务产生后短期时间tp内准 确 预 测 用 户 设 备 的 移 动 轨 迹。定 义 用 户 设 备n N在可预测期间内的移动轨迹为：ln()t=()xn()t yn()tt 0tp（1）其中：t 代表任务产生后所经过的时间；xn(t)与yn(t)代表在 t时刻用户设备在所设想的二维场景中的位置坐标。1.1任务模型本文假设在用户设备n N上每次产生一个计算任务Tn，假定任务为原子且不可分割，即全部在本地设备执行，或全部卸载至 MEC 服务器执行。Tn可用三元组dn cnn表示，其中：dn为用户 n上计算任务传输至 MEC 服务器所需的输入数据，以位为单位；cn为执行任务所需计算量，即所需 CPU 周期总数；n用于指定任务最晚完成时间，以秒为单位。与文献 15 类似，dn与cn的值可以通过应用程序分析器来获得。为了在更加真实的环境下模拟，本文假设各设备 上 产 生 的 计 算 任 务 有 增 强 现 实（Augmented Reality，AR）、健康医疗和信息处理 3种不同类型，各类型分别对应不同的设备移动性、时延敏感性、所需计算量、输入数据等因素，这些因素根据设定的平均值由高斯分布随机生成。1.2通信模型本文采用正交频分多址（Orthogonal Frequency Division Multiple Access，OFDMA）作为上行链路多址方案8。其中，每个 SBS端的频带（带宽 B）被分为S个正交的无线子信道，子信道带宽为W=B/S，定义子信道集合为S=12S，任务卸载执行时将为设备分配一个子信道用于数据传输。卸载至不同MEC 服务器的用户设备可以复用相同的子信道，认为使用同一子信道卸载至不同 MEC 服务器的用户设备间会产生干扰，而卸载至同一 MEC 服务器的用户设备间不存在干扰18。定义卸载决策变量asnm01nNmMsS，当asnm=1时代表用户设备 n 所产生的计算任务Tn通过子信道 s卸载至服务器 m 执行。由于任务的原子性与 MEC 服务器端子信道的传输限制，决策变量需满足以下约束：m M s S asnm 1n N（2）n N asnm 1m Ms S（3）其中：式（2）指设备 n上的任务Tn最多可通过一个子信道卸载至一个 MEC 服务器执行；式（3）指任意时刻每个 MEC 服务器的子信道最多有一个设备传输任务输入数据。假设 t 时刻用户设备 n 与基站 m 间的小尺度瑞丽衰落为nm(t)，并认为其服从单位均值的指数分布。此时，t时刻用户设备 n 与服务器 m 间的信道功率 增 益 可 通 过hsnm(t)=nm(t)g0(d0/dnm(t)计 算，其中，g0代表路径损耗常数，代表路径损耗指数，d0为参 考 距 离，dnm(t)为 t 时 刻 设 备 n 与 基 站 m 的 距离18-19。由香农公式，在 t时刻，设备 n卸载任务时的瞬时传输速率为：Rnms(t)=Wlb(1+pnhsnm()tIsnm+2)（4）图 1移动设备卸载场景示意图Fig.1Schematic diagram of the offloading scenario for mobile devices1652023年 8月 15日Computer Engineering 计算机工程其中：pnhsnm(t)/(Isnm+2)为信干噪比（Signal to Interference plus Noise Ratio，SINR），pn为用户设备 n 的传输功率，2为背景噪声方差，Isnm为区间干扰，代表同一子信道 s上其余设备卸载到其他 MEC服务器所造成的干扰，即Isnm=i N nj M masijpihsij(t)。由式（4）的计算方法可知，传输速率受设备移动性、区间干扰以及衰落的影响而实时变化，其中区间干扰取决于各设备卸载时的子信道选择方案。1.3本地计算模型当用户设备n N上的计算任务Tn选择在本地执行时，定义设备 n 的计算能力为fln，满足fln 0，代表每秒可执行 CPU周期数。Tn本地执行时延为：tln=cnfln（5）本地执行能耗计算采用广泛使用的功耗模型=f38，其中为芯片体系结构功耗系数。因此，任务本地执行时产生的能耗为：eln=(fln)2cn（6）1.4任务卸载模型计算任务Tn选择通过子信道 s卸载至 MEC服务器 m 的执行过程包含 3 个阶段：1）将输入数据从用户设备传输至 MEC 服务器；2）任务在 MEC 服务器上远程执行；3）将计算结果从 MEC 服务器反馈给用户设备。由于任务输出数据量通常比输入数据量小得多，且下行链路传输速率比上行链路高得多，因此参照文献 18 中的处理方式，在建模过程中忽略结果回传的开销。1）输入数据传输阶段。如第 1.2节所述，用户设备将输入数据传输至 MEC 服务器的传输速率受用户移动性、区间干扰及衰落的影响。如：设备与基站距离使得信道增益实时变化；小尺度衰落使得传输速率为随机变量；区间干扰Isnm的取值又依赖于卸载决策以及相同子信道上其余传输设备实时变化的信道增益。因此，对传输速率的实时估算较为困难，且计算卸载方案的设计又有低复杂度的需求。因此，拟将问题场景分割为蜂窝状，如图 2所示，以相邻正六边形来分割场景区域，以灰色正六边形来表示用户设备的移动路径，以正六边形中点的瞬时传输速率代替设备在该六边形内移动路径的传输速率，由此将卸载过程中实时变化的传输速率用数个离散值近似代替。当设备 n 上的计算任务Tn通过子信道 s卸载至 MEC 服务器 m 执行时，用R*nms(k)表示自任务产生时刻起到移动路径可预测时间内（即0tp时间段内）设备 n在移动路径所经过的正六边形 k中点的瞬时传输速率，其中k=12为用相邻灰色正六边形代替设备移动路径后按途径顺序的六边形区域编号。tnk0tp为设备 n在移动过程中离开正六边形区域 k 的时间，且规定tn0=0，tnk末项为tp。此时，任务Tn的传输时延tupnms可通过数值积分梯形法则计算，即累计各区域内可传输数据量近似估计传输时延，算法描述如算法 1所示。算法 1 任务卸载传输时延近似计算输入 R*n，m，s(k)，tn，k，dn输出 tupn，m，s1.tupn，m，s，k 0，data dn，sendEnd true2.while sendEnd do3.k k+14.if data(tn，k-tn，k-1)R*n，m，s(k)5.data data-(tn，k-tn，k-1)R*n，m，s(k)6.if tn，k=tp7.sendEnd false8.end if9.else10.tupn，m，s tn，k-1+data/R*n，m，s(k)11.sendEnd false12.end if13.end while此外，由于设备移动可预测时间为tp，即tp之后的数据传输速率由于设备的移动而变得不可预测，若信道状态较差或传输数据量较大时导致任务无法在 可 预 测 时 间 内 完 成 卸 载 数 据 传 输，则 设 定tupnms=，此时任务选择本地执行是更好的选择，即数据传输时延需满足以下约束：tupnms tpn Nm Ms Sasnm=1（7）由此，输入数据传输能耗计算为：eupnms=pntupnms（8）2）任务卸载执行阶段。在基站上部署的 MEC服务器能同时面向多个用户服务，量化 MEC 服务器m 上计算资源为fm，代表该 MEC 服务器每秒能执行的 CPU 周期数。当用户设备 n 选择将任务卸载至MEC 服务器 m 执行时，设服务器分配给该任务的计算资源为fmn。计算资源需满足如下约束：fmn 0n Nm M（9）n Nfmn fmm M（10）因此，若任务Tn卸载至 MEC 服务器 m 执行且分图 2场景划分及传输速率近似Fig.2Scenario division and transmission rate approximation166第 49卷 第 8期班玉琦，段利国，温昊宇，等：面向移动感知的计算卸载及资源分配策略研究配计算资源为fmn时，执行时延为：texenm=cnfmn（11）综上所述，任务Tn通过子信道 s 卸载至场景中某一 MEC 服务器 m 执行时产生的时延ton与设备端在卸载期间产生的能耗eon计算为：ton=tupnms+texenm（12）eon=eupnms（13）1.5卸载效用优化模型本文以最小化场景内用户设备执行任务所产生的时延与能耗为优化目标，结合计算与通信资源做出 卸 载 决 策。定 义 执 行Tn所 产 生 的 时 延tn与 能耗en为：tn=m Ms Sasnmton+()1-m Ms Sasnmtln（14）en=m Ms Sasnmeon+()1-m Ms Sasnmeln（15）由于任务存在最晚完成时间限制，需满足约束：tn nn N（16）若任务Tn无法在n之内完成，则认为任务执行失败。定义设备 n执行任务Tn的卸载效用un为：un=tn(tln-tntln)+en(eln-eneln)（17）其中：tn01，en01，且满足tn+en=1，2 个参数分别指定为用户设备 n 对时延与能耗的偏好程度。如对时延要求高的设备可提高tn来加快任务的执行；电池容量受限的设备可选择较高的en，代价是需要较长的任务执行时间；un代表相较于本地执行，任务卸载后时延与能耗的改善程度，显然当任务选择本地执行时，un=0。当场景中任务数量较多，对有限的计算、通信资源争用激烈时，选择卸载过多的任务会造成较长的时延或较高的能量消耗，此时un的取值可能为负，即卸载效用低于本地执行，这时将任务在本地执行是更好的选择。定义系统效用为各设备卸载效用的加权和，即n Nnun，其中，n(01，代表服务提供商对设备 n 的重视程度，权值取值可根据用户付费来确定，或对一些负责公共安全的设备设置较高的权值。本文的目标是通过优化卸载决策与资源分配来提高系统效用，定义A=asnm|n Nm Ms S，代表 卸 载 时 MEC 服 务 器 与 子 信 道 选 择 方 案；F=fmn|n Nm M 为 MEC 服务器端计算资源分配方案。此时，系统效用最大化问题可描述为：P1：maxAFn Nnuns.t.式（2），式（3），式（7），式（9），式（10），式（16）（18）在问题 P1中，目标函数与约束条件均为非线性的，且要优化的卸载决策变量asnm为离散值，而计算资源fmn为连续值，即问题 P1 是同时包含连续变量与离散变量的非线性规划问题，使得问题 P1为混合整数非线性规划问题。由文献 22 可知，混合整数非线性规划问题为 NP-hard问题，寻找最优解通常需要指数级时间复杂度。本文的目标是设计一种低复杂度的次优计算卸载方案，在保证实用性的同时能够有较好的性能。2移动感知的卸载及资源分配算法 本节针对问题 P1，提出一种低复杂度的计算卸载方案。首先重写问题 P1中的目标函数：n Nnun=n Nm Ms Snasnm(1-tntexenmtln-)tupnms()tntln+enpneln（19）通过分析重写后的目标函数可以观察到，当固定一个符合约束式（2）、式（3）的设备卸载服务器选择方案时，式（19）中外层括号内第 1 项为常数项；第 2 项取值取决于 MEC 服务器上计算资源 F 的分配，可以看作卸载后任务的执行开销；第 3项可以看作在卸载过程中任务传输开销，取决于任务传输时延，当任务的卸载服务器选择方案已经确定时，传输开销直接受子信道选择的影响。第 2 项与第 3 项在固定服务器选择方案下目标函数与约束条件具有可分离的性质。基于此，在固定的卸载服务器选择方案下，可以将问题 P1转化为计算资源分配与子信道选择 2 个子问题，而原问题可由子问题的解转化为场景中用户设备设计卸载服务器选择问题，以最大化卸载效用。定 义A*=anm|anm=s Sasnmn Nm M为 用 户设备的卸载服务器选择方案，NOF=n N|m Manm=1为选择任务卸载至服务器执行的用户设备集，Nm=n N|anm=1为任务卸载至服务器 m 执行的用户设备集。子信道选择矩阵BN*S代表卸载设备集的子信道选择方案，矩阵中元素bns=1代表设备 n选择子信 道 s 卸 载 任 务。针 对 卸 载 决 策 的 约 束 式（2）、式（3），可根据A*与bns修改为：m Manm 1n N（20）n Nanm|S|m M（21）s Sbns 1n NOF（22）nNmbns 1s Sm M（23）基于上述思想，将 P1重新表述为：P2：maxA*()nNmMnanm-minF()A*F-minB()A*Bs.t.式（7），式（9），式（10），式（16），式（20），式（21），式（22），式（23）（24）在 某 一 确 定 的 用 户 设 备 卸 载 服 务 器 选 择1672023年 8月 15日Computer Engineering 计算机工程方案A*下，(A*F)=n Nm Mntntexenm/tln(A*B)=n Nm Ms Snbnstupnms(tn/tln+enpn/eln)，定义为计算资源分配问题与子信道分配问题，子问题约束条件彼此分离。2.1MEC服务器计算资源分配对(A*F)进一步化简，并结合MEC服务器上计算资源的约束条件，确定卸载服务器选择方案下的计算资源分配问题可描述为问题P3，该问题通过优化计算资源分配方案以降低任务卸载后的执行开销。P3：minFm Mn Nmntnflnfmns.t.fmn 0m Mn Nmn Nmfmn fmm M（25）问题 P3 中约束条件为凸约束，且各 MEC 服务器 上 的 计 算 资 源 分 配 彼 此 独 立。定 义Fm=fmn|n Nm为服务器 m 上的计算资源分配方案。问 题 P3 中 任 意 服 务 器 m 的 目 标 函 数m=n Nmntnfln/fmn对于Fm中变量的二阶偏导数都存在，即：2mfmifmj=2ntnflnf3mii=j0i j （26）其中：2ntnfln/f3mi 0。由文献 23 可知，目标函数m对应的 Hessian 矩阵正定，因此目标函数为凸函数，进而证明计算资源分配问题 P3为凸优化问题。使用内点法对该凸优化问题求解，首先构造m的广义拉格朗日函数：L(fmn)=n Nmntnflnfmn+()n Nmfmn-fm（27）其中：为拉格朗日乘子。对L(fmn)求导后令其为 0，构建 KKT条件与约束条件为：-ntnflnf2mn+=0fm-n Nmfmn=0（28）式（28）中第 2 个等式为最优解必须满足的互补松弛条件。通过对式（28）求解，得到原问题的最优计算资源分配方案f*mn为：f*mn=ntnflna Nmataflafmm Mn Nm（29）对应问题 P3最优解值为：()A*F*=m M()n Nmntnfln2fm（30）2.2子信道分配本文假设设想场景中的任务选择在本地执行时，能满足最晚完成时间约束，即tln n。因此，在确定计算资源分配方案后，约束式（16）可转化为tupnmsn-cn/f*mn，结合约束式（7）可表述为：tupnms min()tpn-cnf*mnn Nmm Ms S（31）由问题 P2中的(A*B)结合传输时延约束以及子信道约束，优化任务传输开销的子信道分配问题可描述为：P4：minBn Nm Ms Snbnstupnms(tntln+enpneln)s.t.式（22），式（23），式（31）（32）分析子信道分配问题 P4 可知，在固定A*情况下，式（32）中目标函数的取值取决于各设备的传输时延，而对于某一设备 n在确定要卸载的服务器后，传输时延主要受到当前卸载子信道上的区间干扰Isnm的影响。因此，问题 P4即为尽可能减小传输开销而对卸载设备进行子信道的合理分配。定义为卸载设备集，初始为所有Nm的集合，按包含的卸载设备数降序排序，s为效益矩阵，其中元素ns用于指示设备 n选择子信道 s卸载任务时，该子信道上已安排的所有设备的目标函数值之和，代表设备 n与子信道之间的权值。子信道分配算法基于改进的 Kuhn-Munkres算法24，尽可能使各子信道负载均衡，步骤如下：1）初始化与BN*S，若卸载设备总数NOF小于子信道数|S|，则为每个设备随机分配不同子信道，算法结束。2）选择当前集中卸载设备数最多的Nm，令 Nm。3）计算当前所选Nm中卸载设备与子信道间的权值ns，构建效益矩阵s。4）若设备 n 选择子信道 s 卸载时，会使信道 s 上存在任务无法满足时延约束式（31），则将 n与 s之间权值取为无穷。5）若某一设备 n 对所有子信道权值都为无穷，则认为该任务执行失败，将设备加入Nfail集合。6）此时Nm中卸载设备的子信道选择方案可根据效益矩阵s转化为求带权二分图的最佳匹配问题，使用 Kuhn-Munkres算法求当前Nm集合中设备的子信道选择方案，由分配结果更新BN*S。7）重复步骤 2）步骤 6），直至为所有设备分配子信道后，算法结束。2.3结合资源分配的卸载服务器选择方案在第 2.1节、第 2.2节中，对于固定的卸载服务器选择方案A*，通过求解问题 P3 及 P4，可以得到计算资源分配方案F*与子信道分配方案BN*S，使得卸载过程中的卸载执行开销与传输开销尽可能得小，且168第 49卷 第 8期班玉琦，段利国，温昊宇，等：面向移动感知的计算卸载及资源分配策略研究通过 P2 中的目标函数能获得当前分配方案下的系统效用。因此，基于 2个子问题的解F*与BN*S，可以将问题 P2重新表述为卸载服务器选择问题 P5，该问题为场景中用户设备安排卸载服务器选择方案，以最大程度地提升系统效用。P5：maxA*(nNmMnanm-()A*F*-)()A*B*N*Ss.t.anm01n Nm M，式（20），式（21）（33）由anm的取值可知，卸载服务器选择方案共有2|N|M种，虽然可通过约束式（20）、式（21）筛选出一部分不符合条件的方案，然而当场景中的用户设备与 MEC 服务器数量较大时，使用穷举算法来获取卸载决策是不切实际的。又由于问题 P5的组合性质，在多项式时间内求解出问题的最优解极具挑战性。鉴于此，本文使用一种低复杂度的启发式算法，在多项式时间内获得问题 P5的次优解。首先在子信道分配时可知，若对某一服务器不合理地分配卸载设备，可能会因为任务无法满足约束式（31）而造成任务执行失败，并且认为任务在本地执行时可以满足最晚完成时间约束式（16）。因此，认为系统不能容忍由不满足约束式（31）所造成的任务失败，即对于某一分配方案A*下，若在服务器m 上卸载的设备存在任务失败的情况，则将此方案以及继续选择在 m 上卸载任务的方案A*加入失败集A*fail，代表无意义的卸载服务器选择集。此外，算法从任务全部本地执行开始，对解的搜索主要包括更新及删除操作。令=anm A*|anm=1为卸载集，删除操作代表若从中删去anm，即让已卸载的任务本地执行，能改善系统效用，则删去anm。更新操作指对于anm A*，令其为 1后，删去集中由于anm的加入导致不满足约束式（20）、式（21）的元素，且对于约束式（21），删去的元素为Nm中卸载效用最小的设备 z 对应元素azm，即更新操作为添加1个元素，删除 02个元素。卸载服务器选择方案的启发式算法如算法 2所示。算法 2 启发式卸载服务器选择算法输入 N，M，S，dn，cn，n，fln，fm，tp输出 卸载设备集1.初始化：=，A*fail=2.abd=argmaxanm A*n Nnun3.abd4.if exists anm，d anm，U(d)(1+g(k)U()5.d6.go back to step 4.7.end if8.for all aij A*do9.u update(，aij)10.if u A*fail11.continue12.end if13.if exists task execution failed in U(u)14.A*fail A*fail F(u)15.continue16.end if17.if U(u)(1+g(k)U()18.u19.go back to step 4.20.end if21.end for算法 2中U()代表在对应的A*下，利用问题P3 与 P4 所求得的当前卸载服务器选择方案下的系统效用。update(aij)代表决策变量对的更新操作。g(k)表示效用改善程度的最小增量，其中，k=|N|M|，g(k)根据场景中设备与 MEC 服务器数量适当取值。F()指与相关的无意义卸载服务器选择集。算法将从空集开始，通过更新及删除操作，使其不断逼近全局最优调度，且通过A*fail集跳过无意义的卸载方案以降低算法的执行时间。将上述启发式卸载服务器选择算法与第 2.1节、第 2.2节中 2个子问题的求解方法相结合，设计的计算卸载方案整体框架如图 3 所示。图 3 中左半部分即为启发式卸载服务器选择算法的执行流程，其中update 操作与 delete 操作产生的卸载设备集u与d，在转换为A*后即为固定的卸载服务器选择方案，通过求解第 2.1节与第 2.2节中的计算资源分配方案与子信道分配方案并代入式（24），以获得该卸载服务器选择方案下的系统效用，由系统效用取值决定是否更新。图 3卸载方案的整体框架Fig.3Overall framework for offloading scheme1692023年 8月 15日Computer Engineering 计算机工程复杂度分析：算法每次对卸载集做出删除或更