超密集边缘计算网络下的任务卸载与资源分配.pdf

：引用格式：唐煜星，王素红，韦睿，等超密集边缘计算网络下的任务卸载与资源分配无线电工程，（）：，（）：超密集边缘计算网络下的任务卸载与资源分配唐煜星，王素红，韦睿，郭文豪，覃团发，（广西大学 计算机与电子信息学院，广西 南宁；广西大学 广西多媒体通信与网络重点实验室，广西 南宁；广西大学 电气工程学院，广西 南宁）摘要：将超密集网络（，）技术应用于多接入边缘计算（，），通过密集化部署小基站与边缘服务器，提升了系统容量。大量用户的接入带来的计算与通信资源不足、用户之间产生严重干扰等问题，使得任务卸载过程面临巨大挑战，制定合理的卸载方案显得尤为重要。针对上述问题，联合考虑了计算与通信资源分配、功率控制，提出了基于混合遗传模拟退火算法（，）的任务卸载方法。通过实验仿真表明，所提方法与其他传统方法相比，提高了用户的卸载效益。关键词：多接入边缘计算；任务卸载；资源分配；功率控制；混合遗传模拟退火算法中图分类号：文献标志码：开放科学（资源服务）标识码（）：文 章 编 号：（），（，；，；，）：（）（），（）：；收稿日期：基金项目：国家自然科学基金（）：（）引言面对物联网时代下对移动设备的低功耗、低时延以及高安全性等需求，目前广泛使用的以云中心服务器来处理任务的云计算（，）方式已呈现许多弊端。为了应对这一问题，年，欧洲电信标准化协会正式提出了多接入边缘计算（，）的概念。与传统云计算中任务集中式处理的方式不同，边缘计算将任务的处理工作下放到了靠近用户的网络边缘侧，使部分网络功能脱离核心网络，实现了任务的高效传输。而传统蜂窝网络部署下的服务器已无法满足大规模用户的接入，将超密集网络（，）技术应用信号与信息处理 年 无线电工程 第 卷 第 期 于边缘计算网络是解决这个问题的重要手段。超密集网络技术通过在宏小区中密集部署小基站及无线接入点，提升了系统容量，实现了大量用户的接入需求。任务卸载与资源分配作为边缘计算的关键技术，一直是广大学者研究的一个热点。文献在单小区多用户的系统模型下，提出了基于粒子群算法与最大节能优先算法的卸载方案降低了系统能耗。文献设计了基于车联网场景下的任务卸载与资源分配方法，为行驶中的车辆提供计算服务。文献提出了用户与服务器之间的动态调度问题模型，并通过强化学习方法得到了解决。文献考虑了设备与设备通信技术（，）的卸载场景，解决了设备之间的延迟与干扰问题。文献将非正交多址（，）技术应用于任务卸载中，提升了频谱效率的同时降低了设备能耗。而针对超密集边缘计算网络的场景，文献均做了相关研究。目前，针对不同场景下的任务卸载模型，国内外相关科研工作者已经做了许多研究，并取得了显著成果，但仍然存在着不足。例如，未能将有限的服务器计算资源进行合理利用，采用的算法容易陷入局部最优的问题等。此外，面对大量边缘服务器以及大量用户接入的超密集边缘计算网络的场景，用户之间产生的干扰以及将有限的频谱资源进行合理分配同样不可忽视。针对上述问题，本文的主要贡献如下：针对下的任务卸载场景，提出了联合考虑时延与能耗的卸载模型，并将系统用户的卸载效用作为优化目标。融合了模拟退火算法的局部搜索能力和遗传算法的全局搜索能力，设计了基于混合遗传模拟退火算法（，）的任务卸载方法来求解用户最大卸载效用。由于原目标问题涉及多个变量，求解过程困难，将每次更新过程中的目标函数分解为关于计算资源分配以及传输功率控制的子问题，分别利用凸优化以及黄金分割法解决，并基于最大有效干扰进行信道分配以解决频谱资源有限及用户之间的干扰问题。通过仿真实验表明，本文提出的卸载方法与其他经典方法相比，具备更好的性能。系统模型和问题描述 网络模型系统模型如图所示。考虑一个包含有一个宏基站（，）和若干个小基站（，）部署的超密集边缘计算网络系统。其中，作为系统的网络信息流中心，其覆盖范围作为一个宏小区，每个的覆盖范围作为一个小小区，将具有中等计算能力的服务器配备于周围，为计算资源有限的覆盖范围内的用户提供任务卸载服务。以集合，表示所有用户集，集合，表示可供卸载的服务器集。传输过程采用正交频分多址方式，将覆盖范围内的系统可用带宽资源划分为个子信道，若系统总带宽为，则每个子信道的带宽为 ，以集合，表示可供用户选择的传输信道。每个用户都有一个需要进行处理的任务，且任务是不可分割的，即用户可以选择任务在本地设备进行处理，也可以选择将任务卸载到服务器上处理以缓解本地设备执行压力。本文基于一个准静态的网络模型考虑，即任务的传输过程中，用户始终处于静止状态。图超密集边缘计算网络系统模型 以二元数组（，）来代表每个用户需要进行处理的计算任务。其中，表示需要处理任务的数据量大小（包括图像、视频和文本等），单位。代表处理一项任务消耗的计算资源，用完成一项任务进行的循环周期量化。此外，将，定义为任务卸载的决策变量，当，时，表示任务在终端设备上执行；当，时，表示用户将任务卸载到服务器上执行。信号与信息处理 通信模型在用户上行传输过程中，任务上行传输过程中，不同用户复用同一信道将任务卸载到不同服务器时，会产生小区间的干扰。记，为信道选择决策变量，当任务通过子信道进行卸载时，否则，。因此，用户通过信道传输所产生的信干噪比（）为：，（）式中：表示用户的上行传输功率，表示用户与服务器之间的信道增益，是以零加性高斯白噪声表示的背景噪声，表示复用同一信道的用户产生的小区间干扰。由香农公式可以计算，用户到服务器所能达到的上行传输速率为：，（，），（）式中：表示用户传输信道的信道带宽。计算模型（）本地计算模型当某个用户产生的任务在本地设备上进行处理，所产生的时延可以计算为：，（）式中：表示用户的本地计算能力，可以用的周期频率来量化。相对应地，本地设备处理一项任务产生的能耗可以计算为：（），（）式中：表示设备的能耗系数，与的制作工艺和芯片结构有关，通常取。由于是已知的，所以本地设备的时延与能耗通常只受到和的影响。（）任务卸载模型将任务上传到服务器进行处理，还会产生额外的延迟与能耗。对每项任务而言，所产生的延迟包括数据通过上行链路传输到服务器的时间、任务在服务器上处理的时间以及服务器向用户返还计算结果的时间。能耗则取决于上行链路的传输能耗以及下行链路返还计算结果所产生的能耗。由于输入的数据量要远远大于输出的数据量，所以在下行传输过程中所产生的时延与能耗在本文中忽略不计。由前文所提到的通信模型可以得出，用户将任务传输到服务器的时间可以计算为：，。（）相应地，传输的能耗为：，。（）用表示服务器的理论计算能力，表示任务可以分配到服务器的计算资源占服务器总资源的比例，则该任务分配到的计算资源数量为，。因此，可以计算出任务在服务器上的执行时间为：，。（）用户在整个任务卸载过程中的总时延为：，。（）由于服务器部署在基站附近，而基站通常拥有独立的供电系统，通常情况下服务器具有的能量总是足够的。因此，服务器的执行能耗不在本文采用的模型中考虑，任务卸载的总能耗为：，。（）在所考虑的系统模型下，引用个定值：，（），。（）式（）和式（）表示采用任务卸载相对于本地执行的时延和能耗的改善情况，因此可以将卸载的效用函数定义为：()，（）式中：和分别代表任务对时延与能耗偏好程度的权重系数，且满足。针对不同类型的任务需求可以设定不同的权重，例如，处理一些时延敏感型任务时，更关心对时延的优化，可适当增加并减少。问题形成 问题描述本文旨在处理所有用户在时延和能耗权重因子的约束下，最大化用户的卸载总效用。当用户将任务卸载到服务器以供执行时，。此处定义（）为卸载到服务器上的用户数，卸载用户集定义为，。通过联合优化计算资源分配、信道选择、功率控制和卸载决策，目标问题可以表述为：信号与信息处理 年 无线电工程 第 卷 第 期：，：，：，：，：，：，：，()（，），。（）约束限制其中，约束和表示对信道分配的约束，任务可以在本地执行或至多通过一条信道传输到服务器。约束和表示对服务器选择的约束，任务可以在本地执行或者卸载到其中一个服务器执行。约束表示用户分配到的服务器资源数量不能超过服务器的最大负荷。约束表示用户的传输功率不能超过最大上传功率的限制。约束表示为了给用户更好的使用体验，任务执行的总时延不能超过最大容忍时延。问题分解由于原问题的多个变量之间是互相耦合的，在有限的多项式时间内找出目标问题的最优解变得极为困难。为了便于求解问题，首先将目标函数进行拆分。在给定一个满足目标约束的卸载策略下，原效用函数可以拆分为：，()，（）式中：，（）。分解后的目标函数中计算资源分配变量，与传输功率控制变量之间彼此是解耦的，要求出目标问题的最大效用函数值，可以先分别求解计算资源分配与传输功率控制的子问题。联合任务卸载与资源分配算法设计 计算资源分配由式（）式（）可知，卸载用户分配到的计算资源越多，所产生的执行时延和能耗相对更小。将原问题分解为关于计算资源分配的子问题，可以表示为：（），：，。（）引理：关于用户最优计算资源分配问题是凸优化问题。证明：目标函数是关于自变量的多元函数，此处构造一个卸载用户的资源分配比例矩阵，其中，行向量表示卸载用户，列向量表示服务器，矩阵中的每个元素表示由服务器分配给用户的计算资源所占服务器资源的比例。（）相应地，可以求出对于某一服务器下的海森矩阵为：。（）通过对海森矩阵上的元素进行计算，可以得出：，()，。（）可以看出，除了主对角线上的元素外，其余元素均为，且主对角线上的所有元素均大于，因此目标函数的海森矩阵为正定矩阵，计算资源分配问题是一个严格凸问题，因此计算资源分配问题存在着唯一最优解，可以通过构造拉格朗日函数求解目标问题。根据引理，目标问题的拉格朗日函数记为：（，），(，)，（）由于，()，()，（）因此，在目标问题的约束下，条件可以表达为：信号与信息处理 （，），（）式中第二项为求解计算资源分配问题的条件中的互补松弛条件。因此，服务器最优计算资源分配比例为：（，）槡 槡，（）同时，最优计算资源分配解为：（，）槡槡。（）信道分配给出了用户传输功率，用户的子信道分配问题可以记为：（），()()，（，）：，：，：，()（，），（）式中：，为信道对用户传输数据的有效干扰，可以用下式表示：，。（）可以看出，在用户传输功率已知时，信道分配决策主要由有效干扰决定。有效干扰越大则用户的卸载效益越大。对于进行卸载的用户集来说，在给定的信道分配策略下，约束可以转化为：，（）带入有效干扰的表达式，得到：，()。（）此处采用函数描述信道分配问题，式（）表示在任务卸载过程中分配有效干扰最大的信道进行卸载。，()。（）上行传输功率控制信道分配策略已知时，上行传输功率控制的子问题可以描述为：（）（，）：，：，()（，），。（）与信道选择策略类似，约束条件可以改写为：，()，（）用户的最佳上传功率的取值范围为：，()，。（）由功率控制问题表达式可以看出，用户之间的上行传输功率不会相互影响，因此，用户的上行传输功率控制函数可以记为：（）（，）：，()，。（）针对用户的上行传输功率控制，本文采用一种低复杂度且具有高收敛度的黄金分割法解决。首先，设定用户传输功率的搜索范围，、黄金分割点以及收敛精度，利用黄金均值公式计算出功率控制函数的上下搜索边界和之差的绝对值，当该值大于其收敛精度时，利用黄金均值公式计算（）和（）。若（）（），则向左减小搜索范围，否则向右减小搜索范围。搜索边界的计算方法由下式给出：（），（）（）。（）具体的算法流程如算法所示。信号与信息处理 年 无线电工程 第 卷 第 期 算法基于黄金分割法的上行传输功率控制方法输入：、输出：最优传输功率初始化，()，通过式（）、式（）计算、利用式（）计算（）、（）（）（），（）（），（），（）（），（）输出 基于的任务卸载方法从模拟退火算法的退火过程以及遗传算法的进化过程中得到启发，本文提出了结合二者算法思想的的任务卸载方案。模拟退火算法具有较强的局部搜索能力，但缺乏全局搜索能力，可以在模拟退火算法更新解的过程中，融入遗传算法的进化过程，扩大解的搜索范围。将遗传算法的种群初始化过程作为模拟退火算法的初始解，将进化操作后的解作为新解，并根据