物联网边缘计算卸载和资源分配关联算法
2022-08-16卫金菊郭荣佐
卫金菊，郭荣佐
(四川师范大学 计算机科学学院，四川 成都 610101)
0 引 言
随着物联网(internent of things，IoT)、无线通信技术等的发展，涌现出了大量新兴智能IoT应用设备，使得物联网终端设备需运行并处理大量的计算密集型数据，例如自动驾驶、人脸识别和自然语言处理等[1，2]对时延和能耗敏感要求较高的任务。基于物联网终端设备的缺陷，其计算能力和电池续航能力等均有一定限度，难以有效处理这些要求低时延、低能耗的应用。同时，传统云计算也难以处理爆炸式增长的边缘数据[3]，因此学者提出了移动边缘计算。移动边缘计算的概念及相关定理由文献[4]给出，将物联网终端设备的待处理任务通过无线接入点(radio access network，RAN)或基站(base station，BS)迁移到移动网络边缘并进行处理的过程。其中RAN具有较强的存储能力和计算能力，可为就近的移动物联网终端设备提供服务及计算能力，从而能够满足5G网络所需的低时延、低能耗、高可靠性及连续广域覆盖等需求[4]。
针对物联网边缘计算的能耗及时延的研究，主要通过卸载决策和资源分配等方式建立数学模型，对目标函数优化模型进行求解。但对这类属于NP-hard问题求解难度大。对此，本文提出了改进混合离散二进制粒子群算法(improve-BPSO)，该算法通过将离散二进制粒子群(binary particle swarm optimization algorithm，BPSO)与模拟退火算法(simulated annealing，SA)相结合，同时改进模拟退火算法中产生新算子的方法，提高了得到最优卸载决策和资源分配的概率。
1 相关研究
针对卸载决策和资源分配的研究，已存在大量处理能耗和时延的方法。国内外已有学者从多个角度提出了关于MEC的卸载决策和资源分配的解决方案[5-11]。在文献[5]中，学者提出基于深度强化学习和深度确定性策略梯度的动态调度策略解决多移动终端设备MEC系统中的动态缓存、计算卸载和资源分配问题，从而能够得到最小化成本函数的长期平均值。文献[6]提出了一种基于深度强化学习算法的在线解决方案，处理非正交多址访问的MEC网络中计算卸载和资源分配的联合优化问题。文献[7]中设计了一个有界改进分支有界算法来寻找全局最优解同时提出了一种求解次优解的组合算法，从而优化计算卸载和资源分配。文献[8]是在多智能体深度确定性策略梯度深度强化学习框架的动态通信环境下，提出了智能高效的资源分配和任务卸载决策算法及方案。文献[9]研究多个移动服务需求在不同的工作流调度问题，提出了基于遗传算法求解计算卸载方案。文献[10]针对基于时分多路无源光网络的移动边缘计算，提出了一种最小化延迟和网络部署联合成本的最大线性规划模型。文献[11]提出以最大限度地提高全网频谱效率和系统容量为目标的移动边缘计算资源分配的最优策略。但在单边缘服务器多物联网终端设备环境中基于边缘服务器计算资源有限的研究，如何实现计算卸载和资源分配的联合优化使系统总成本最小，即实现时延的减少和能耗的降低是值得研究的问题。
综上，针对物联网边缘计算卸载和资源分配求解时延和能耗的相关问题，在一个边缘服务器多物联网终端设备情景中、边缘服务器计算资源有限的情况下，将该系统模型转化为数学模型，提出联合卸载决策和资源分配的策略，同时设计系统总成本(时延和能耗的加权和)最小的函数模型，在此基础上采用改进混合离散二进制粒子群算法进行卸载决策研究，在该卸载决策下将原问题转化为计算资源分配问题，然后根据拉格朗日乘子法及其理论求出计算资源的最优解，最后，通过迭代可以求解出最优的卸载决策和资源分配的结果，从而能够降低系统总开销，有效提升物联网终端设备性能和服务质量。
2 物联网边缘计算模型架构、系统模型及问题描述
2.1 物联网边缘计算模型架构
由于传感器和移动智能设备等的显著增加，将物联网与边缘计算结合，把集中式数据资源转移到更靠近生成数据源的设备上，从而减少云计算的处理能力，以减少系统的延迟，提高物联网终端设备的性能。物联网边缘计算架构图如图1所示，该架构图主要由3部分组成：边缘设备层、中间服务层及数据中心层。其中边缘设备层是由两部分组成：物联网应用设备和感知设备，物联网应用设备包括智能家居、绿色农业、智慧医疗等，感知设备主要是通过传感器等感知物联网应用设备产生的数据，同时对数据进行收集和传输；中间服务层由无数个物联网网关和其它服务器组成，这些服务器可以促进通信，减轻处理数据功能并推进边缘服务器的操作同时还能对手机到的数据进行预处理，并将结果发送到数据中心。而预处理的作用主要是减轻带宽的限制，并优化转发数据，最小化传输数据量和节省大量传输成本。数据中心主要由边缘服务器等组成，边缘服务器能处理物联网终端设备终端的数据。
图1 物联网边缘计算模型架构
2.2 系统模型
图2 系统模型
2.3 计算模型
设每个物联网终端设备n有一个需要完成的且不可分割的计算密集型任务Un={Cn,Dn}，n∈[1,N]。 其中，Un表示第n个物联网终端设备待处理任务信息的集合，Cn表示第n个物联网终端设备请求的计算资源的数量，即完成任务Un的CPU周期总数，Dn表示第n个物联网终端设备的处理任务的数据量大小。
(1)本地计算模型
(1)
(2)
其中，k表示能量因子，大小取决于CPU芯片工艺，本文将该值取值为k=10-27。 本文不考虑到fl随着本地执行时任务消耗的能耗的变化而变化，即fl设置为一个不变值。
(2)卸载计算模型
(3)
其中，Dn为计算Cn所需输入数据的大小，rn为系统模型中无线信道中，物联网终端设备n的上行链路速率。
(4)
其中，fcn是边缘边缘服务器分配给物联网终端设备的计算资源。
设边缘服务器最大计算资源为Fc， 由于边缘服务器的计算资源有限，则约束条件应设为边缘服务器的允许的最大计算资源Fc应大于等于边缘服务器分配给卸载物联网终端设备的计算资源的总和，可用表达式表示为
(5)
(6)
(7)
本文的目的是通过使用智能算法找到使出整个系统中所有物联网终端设备的总成本(时延和能耗加权和)最小的卸载决策和资源分配的最优解，则本文的最终优化问题转化为S=
(8)
(9)
(10)
s.t.
(11)
(12)
(13)
(14)
其中，C1表示用户设备的卸载决策；C2表示边缘服务器分配给卸载用户设备的计算资源为正数；C3表示边缘服务器分配给每个卸载用户设备的计算资源的总和小于等于边缘服务器的最大计算资源；C4中α、β是权重系数，表示对时延和能耗的权衡，若对时延敏感性应用，则取α的值大于β的值；若对设备能耗不足时，则取β的值大于α的值，本文研究时延和能耗同等重要，则取α与β均等于0.5。
基于上式(8)～式(14)的优化函数及约束条件，其同时存在着整数约束和连续变量型，则该优化问题属于NP-hard问题。针对这一问题，本文将优化目标问题分解为卸载决策和资源分配两个问题，并通过智能算法进行求解。
3 算法设计
在本文所提模型中，卸载决策问题的本质是0-1规划为问题，故用离散二进制粒子群算法(BPSO)对卸载决策求解，但由于BPSO易陷入局部最优，存在早熟早收敛等缺陷，为解决这一问题，引入了模拟退火算法(SA)，同时对SA中产生算子的方法改进，在SA中，设置一个较高的温度作为初始值，该温度按照一定的下降参数不断下降，当算法中的某个解趋于稳定时，可利用模拟退火算法具有以某个概率能跳出局部最优的特点，可有效避免算法陷入局部最优解，同时提高算法精度，从而找到卸载决策和资源分配的联合最优解。在应用improve-BPSO算法优化系统总成本的问题时，主要思路是：①利用改进混合离散二进制粒子群算法 (improve-BPSO)制定卸载决策；②在更新卸载决策情况下，利用拉格朗日乘子法及其理论进行资源分配，计算适应度函数得出全局最优和个体最优；③随机选择个体最优作为模拟退火的初始值，执行模拟退火操作，其在降温过程中，可概率性地接受不优于当前解的新解，依次迭代，得到最优解。
3.1 离散二进制粒子群算法
粒子群算法(particle swarm optimization，PSO)是一种基于全局搜索的智能算法[14]，其主要优化目标是基于连续性计算的问题。BPSO于1997年由 James Kennedy和Russell C.Eberhart首次提出[15]，其主要优化目标是基于离散空间约束的问题，BPSO是PSO的扩展和应用。下面给出BPSO的基本步骤：
BPSO的速度更新公式为
(15)
位置更新公式：利用sigmoid函数，计算粒子的速度映射到区间[0,1]的概率，并将该概率作为粒子下一步取值为1的概率
(16)
位置变化的概率可表示为
(17)
3.2 模拟退火算法
模拟退火算法(SA)由Metropolis在1953年首次提出[16]，同时在1983年首次提出SA可解决组合优化的问题。本文所采用的模拟退火的基本思路是对当前解重复产生新解，计算适应度函数的差，判断是否能接受的迭代过程与BPSO结合，从而找到最优解，该算法具有概率性地跳出局部极值等优点。
3.3 改进的混合离散二进制粒子群算法
在改进的混合离散二进制粒子群算法中，初始化粒子的速度和位置，确定全局最优、个体最优，同时更新速度和位置，计算适应度函数，更新粒子的个体最优，然后随机取出一个个体最优，运用模拟退火算法，产生新的算子，进而得到更小的适应度函数，依次迭代，直至找到最优解。图3是该算法的流程。
图3 算法流程
Improve-BPSO算法的流程图。如图3所示。
4 卸载用户设备计算资源分配
通过上述改进混合离散二进制粒子群算法制定用户的卸载决策后可得到用户的卸载决策Xn， 由前文可知Xc表示卸载的任务的集合，则原目标问题可以简化为
(18)
(19)
则资源分配minf由g(f) 决定，可以观察到g(f) 的定义域为凸集，利用凸优化判别式的二阶条件，可证明目标函数g(f) 的Hessian矩阵是半正定的，可得到g(f) 为凸函数。在定义式(18)中不等式约束条件C1、C2下的拉格朗日函数表达式为
(20)
(21)
5 仿真实验
通过MATLAB对本文所提算法进行仿真实验，然后对其进行性能分析。在该仿真实验中，设每个任务的数据量大小为Dn(单位:Kbits)服从 (300,500) 的均匀分布，且所需要的CPU周期数为Cn(单位:MHz)服从 (800,1200) 的均匀分布。边缘服务器的计算能力Fc为15 GHz。设N个用户设备的计算能力是相同的，其任务在本地处理的频率fl均为0.8 GHz，任务卸载到边缘服务器的上传信道速率rn为2 Mbit/s，传输功率Pt为500 mw。为便于仿真实验的对比和分析，设置如下对比方案，将改进混合离散二进制粒子群算法(improve-BPSO)与文献[17]中模拟退火粒子群算法(PSOSA)、离散二进制粒子群算法(BPSO)、模拟退火算法(SA)、全部卸载(OFFLOAD)、全部本地(LOCAL)进行对比分析。
5.1 迭代次数对算法的影响
设终端用户设备为20个，设种群数目为60，迭代次数从1递增到100。由图4可知，全部本地执行(LOCAL)和全部卸载到边缘服务器执行(OFFLOAD)不会随着迭代次数的增加而变化，但始终处于较高的数值处。由图5知，其它几种算法随迭代次数的增加，其总成本数值逐渐递减直至收敛，但总的来说，improve-BPSO算法的收敛速度最快且收敛效果最好。
图4 迭代次数对系统总成本的影响
图5 迭代次数对总成本影响的详情
5.2 任务数量对算法的影响
本节任务数量从10到55以间距为5不断增加，拟定迭代次数为100，比较6种算法在系统总成本上的差别。如表1所示，在这6种算法中，系统的总成本均随着任务数量的增加而不断增加，这是由于任务数据量的增加，导致系统需要更多的时延和能耗开销，故系统的总成本会随着任务数据的增加而增加。在同一任务数量下，但improve-BPSO与其它几种算法相比，其总成本较低，则本文提出的improve-BPSO算法具有一定的优势。
5.3 任务周期数对算法的影响
假设任务数量为20，迭代次数为100次，比较任务周期数从800 MHz到1200 MHz以间距为100 MHz增加，对比分析在其它条件相同时，仅在不同任务周期数的情况下，各算法的系统总成本的大小，以及在同周期下不同算法中系统总成本的大小。如图6所示，随着周期数的增加，导致处理任务时的计算时延增加，从而使系统的总成本增加；在相同周期情况下，improve-BPSO算法系统总成本与其它几种算法进行比较分析，可得出improve-BPSO算法的总成本低于其它几种算法。
表1 不同任务数量对系统总成本的影响数据
图6 周期数与总成本的关系
5.4 传输数据量对算法的影响
假设任务数量为20，迭代次数为100次，传输数据量从300 Kbits增加到500 Kbits以50 Kbits的间距增加，improve-BPSO算法与其余几种算法进行对比。如图7所示，随着传输数据量的增加，系统总成本不断增加，这是由于传输数据量增加时其任务的计算时延和能耗不断增加，从而导致总成本在不断增加。由图7可知，在相同的传输数据量的情况下，improve-BPSO算法与其余几种算法进行比较，可得出该算法的总成本略低。
图7 传输数据量与总成本的关系
6 结束语
本文对物联网边缘计算卸载和资源分配的关联算法研究，在单边缘服务器多物联网终端设备的场景中，边缘服务器的计算资源有限的情况下，将边缘计算卸载和资源分配策略关联，提出以最小化系统总成本(时延和能耗的加权和)为优化目标的函数模型。然后采用improve-BPSO算法制定卸载决策，并在该卸载决策下，将原问题转化为计算资源分配的子问题，然后根据凸优化及其理论，再利用拉格朗日乘子法求出计算资源分配的最优解。实验结果表明，该方案在迭代次数、任务数量、任务周期数及传输数据量方面均优于BPSO、PSOSA、SA、LOCAL、ODDLOAD这5种算法。
