边缘计算计算卸载与资源分配联合优化算法

张兰勇 王梦琳

固定资产管理是企事业单位中一项非常严肃,政策性、原则性、技术性很强的后勤工作,它将把控资产信息、提高管理效率、降低支出成本作为管理目标,提升了企业的资产管理水平[1].早在2020 年,财政部发布了《关于加强行政事业单位固定资产管理的通知》,来加强事业单位的后勤资产管理水平.除此之外,我国在军事后勤建设的投入逐年增加,后勤工作会议指出：加快建设现代军事物流体系和军队现代资产管理体系[2].无论军事还是民用,后勤资产管理建设都是现阶段发展重点,必须探索出一条能够推进后勤资产管理工作向现代化和智能化方向发展的道路,引领我国后勤资产管理实力迈向新台阶.

我国资产管理经历手工记账、二三维条码的发展过程,形成了信息化管理系统.由于资产管理特殊性,现有系统普遍存在以下问题：精细化程度低、平台功能有限；资产辨认与定位难、可视化程度低；编码体系不统一、编码覆盖信息不全[3].因此,结合传感定位、网格剖分、实时监控等技术,建设统一后勤资产业务管理平台,实现可以为全天候、全地域环境提供精细化保障的“可视化后勤”,是现代后勤建设的主要目标[4].

专家学者对相关技术开展研究来提升资产管理系统服务水平.LIN Y 完成了基于射频识别的仓库研究与实践物流管理系统设计,针对仓储管理中手工作业多、效率低的问题,设计了基于射频识别（radio frequency identification,RFID）仓库自动化解决方案,满足大型仓储企业需求[5].WANG T 等利用RFID 技术建立基于物联网技术的固定资产管理平台,实现合理高效使用和部署固定资产,优化和简化管理过程,确保得到可靠和完整的资产数据[6].LEE C 等提出了一种基于蓝牙定位用于跟踪资产的室内定位系统,实现一种经济高效的资产管理解决方案[7].

应用北斗网格剖分技术解算资产位置构建统一定位编码标准,基于RFID 系统、北斗定位系统、摄像头等设备采集资产数据,利用软件及数据库技术实现具备实时监控与资产可视化功能的先进资产管理系统.在后勤资产管理系统发展过程中,传统系统构架直接将企业管理系统连接至后勤云计算中心,随着接入硬件设备逐渐增多,大量原始数据未经过解算全部上传至云端会占用更多的带宽和服务器资源,给系统的运维带来极大资源负担,也不利于对资产环境视频监控画面进行实时调取,在一定程度上影响用户体验,限制了后勤资产管理系统向现代化发展[8].

云计算、联邦学习、边缘计算等分布式计算技术被提出用于协调共享资源的使用,边缘计算具有实时性高、计算能力强、带宽高、安全性高等优点,在众多通信新技术中脱颖而出[9].在系统构架中引入边缘层,能在数据源头实现定位、RFID 标签等原始数据的及时处理与响应,向云端直接传输解码结果减少数据传输消耗.同时边缘计算及多码流处理技术的结合运用,也为实时视频监控需求提供了解决方案,能够提高视频图像数据价值,降低带宽与时延,提高处理效率.

边缘计算技术核心是基于分布式边缘服务器,在数据源头提供具有网络、计算、存储等功能的服务器节点,完成被卸载的计算任务,经过资源分配等步骤将结果返回设备端[10].为了提升技术服务性能,本文针对边缘计算服务模型中资源分配、计算卸载两项业务开展研究,优化调度模型、寻找更佳的控制策略来提供最优服务.

相关专家也对边缘计算计算卸载以及资源分配等问题开展相关研究,SONG H K 等研究了无线边缘网络中边缘计算服务器部署和用户卸载关联的网络,设计了一种改进遗传算法来解决该问题,有效减少平均服务延迟[11].TANG C G 等提出了一个通用的支持缓存的车载边缘计算方案,同时考虑任务缓存带来的响应延迟和能耗,同其他算法相比具有优势性[12].XU F 等提出了两阶段计算卸载算法,能够有效降低时延[13].黄冬晴等提出一种面向多用户的联合计算卸载和资源分配策略,利用拉格朗日乘子法获得最佳计算资源分配,基于贪心算法获得最佳卸载决策,不断迭代降低系统成本[14].

目前许多专家对资产管理系统进行优化,开展边缘计算技术业务研究,但大都是针对单一目标进行优化设计.也有不少专家对单一业务进行多目标优化,例如针对卸载决策或资源分配问题进行时延能耗多目标优化.随着研究不断深入,逐渐向多业务联合优化方向发展,也提出了计算卸载和资源分配联合优化的概念,通过不断迭代两个业务问题的求解获得更优解.由于联合优化计算过程复杂,现有论文一般采用复杂度较低的算法来求解卸载决策计算问题,例如文献[14]采用贪心算法计算.因此,本文研究计算卸载和资源分配问题,基于数学推导解决计算资源分配问题,基于进化类算法计算卸载决策,迭代计算联合优化时延和能耗两个目标,得到最优控制策略.

1 系统模型与问题描述

1.1 系统模型

1.2 本地执行模型

1.3 传输模型

由香农公式,移动用户上行链路传输速率：

1.4 卸载至边缘服务器执行模型

若任务在边缘端执行,则计算时间由任务上传、处理以及下载3 部分组成,由于任务处理后数据大小远小于执行前数据大小,且下行链路传输速率也远高于上行链路传输速率,因此,忽略下载任务的时延和能耗,任务上传时间为：

其中,Rie为移动用户i 与边缘服务器上行链路传输速率,任务处理时间为：

忽略边缘设备在计算过程中消耗的能耗,将任务Mi卸载到边缘服务器所需能耗为：

1.5 卸载至云端服务器的执行模型

同理,若任务在云端执行,忽略下载任务的时延和能耗,任务执行时间仅由任务上传与任务处理2部分组成,任务上传时间为：

其中,Ric为移动用户i 与云端服务器上行链路传输速率,任务处理时间为：

任务卸载到云端服务器后,由于云端计算资源充足,不考虑资源分配,忽略任务处理能耗,得到任务Mi卸载到云端服务器所需能耗为：

其中,Pec为云端服务器的上传功率.

1.6 目标函数

由以上公式可知,移动用户的任务执行能耗和时延的期望为：

则遍历所有终端设备,得到任务执行总时间和设备消耗总能耗如下：

本文目标是探究任务执行总时间和设备总能耗综合最小的卸载策略,α 为权重因子,在（0,1）之间取值,反映了时延和能耗的重视程度,目标函数定义如下：

优化目标建模为：

2 问题的分解与求解

本章将大问题分解得到上行功率分配、计算资源分配、卸载决策3 个子问题,针对前两个问题进行求解与公式推导.

2.1 问题分解

由于通信与计算资源是连续变量,卸载决策是整数向量,该问题是一个混合整数非线性规划的问题,属于非确定性多项式问题研究范畴,将其改写为：

由于卸载决策向量与资源分配变量完全解耦,进一步将该问题分解为上行链路通信和计算资源分配问题与最优分配方式下的计算卸载问题,综合计算两个问题求解最小化系统开销.

拆解出的资源分配问题可表示为：

设定了卸载方式,代入上式拆解整理可得：

上式中,Q 是不参与待优化变量相关的常数项,式中第1 项为通信资源分配资问题,第2 项为计算资源分配子问题,可分别求解.

上行功率分配子问题为：

计算资源分配子问题为：

2.2 上行功率分配问题求解

将上行功率分配子问题改写为：

2.3 计算资源分配问题求解

将计算资源分配子问题改写成：

由于海森矩阵正定,因此,该问题是凸问题,采用卡罗需-库恩-塔克（Karush-Kuhn-Tucker,KKT）条件求解,拉格朗日函数可表示为：

其中,式（34）为拉格朗日函数求极值的必要条件,式（35）、式（36）是互补松弛条件,式（37）、式（38）为不等式约束条件,由式（36）、式（38）可知μ=0.通过对式（34）求导,得到最优计算资源分配：

由式（35）知,最优计算资源分配满足：

则由上两式联立求解得：

则综合求解得最优计算资源分配表达式为：

3 联合优化算法设计

上面求解了上行功率分配与计算资源分配问题,本章将根据上行功率分配求解结果设计动态调整算法,提出改进粒子群（particle swarm optimization,PSO）算法进行计算卸载问题求解,最后提出联合优化算法.

3.1 上行功率分配动态调整算法设计

在分配问题求解过程中,可能出现某MEC 服务器分配资源之和超出上限的情况,需要动态调整分配量,按照原分配方案等比例缩小,使资源分配和恰好达到服务器上限,算法描述如算法2 所示.

3.2 计算卸载改进PSO 算法设计

拆解出的计算卸载子问题为：

很多学者联合优化问题选择贪心算法、博弈论等简单策略实现卸载决策的求解,获得较好的局部最优卸载结果.而在卸载决策单一问题的研究中,会更偏向算法优化设计,倾向于选择进化算法、强化学习等优化算法,获得接近于全局最优的卸载决策.由于本文目的是循环迭代卸载决策和资源分配问题实现联合优化,因此,选择以“循环优化”为核心的进化类算法求解卸载决策.PSO 算法搜索能力强、易实现,在高维度优化问题上收敛速度很快,但易早熟陷入局部最优[77].因此,本文提出基于改进PSO 算法求解最优卸载决策,在标准PSO 基础上设计了自适应调整的惯性权重系数，在算法迭代后期引入交叉重组机制,来打破粒子早熟停滞的问题[17].

3.2.1 标准粒子群算法

其中,C1、C2是学习因子,调节影响飞行方向比重；ξ和η 是服从U（0,1）均匀分布的随机值；ω 是惯性权重,调节飞行速度；t 是迭代次数.

3.2.2 编码

本文采用整数编码机制,假设粒子群规模为D,每个粒子代表一个卸载策略,粒子元素取值为0～n+1的整数.假设系统中用户终端设备周围有3 个边缘服务器,用户任务数目为7 个,任务集合为TASK={task1,task2,…,task7},此时假设任务的某个卸载决策向量为,其中,0 代表task1在本地执行,4 代表task2在云端执行,2 代表task3在编号为2 的MEC 服务器上执行,1 代表task4在编号为1 的MEC 服务器上执行,以此类推,编码方式效果图如图1 所示.

图1 编码方式图Fig.1 Coding scheme

图2 编码变换图Fig.2 Transcoding map

3.2.3 适应度函数

本文求解目标是最优卸载策略使能耗和时延代价和最小,由系统目标函数可知,f 总代价越大,方案评价越差,本文将目标函数作为适应度函数,其中,规定f 最小值不为0.

3.2.4 算法的改进

本文在标准PSO 基础作出以下两点改进：1）自适应调整惯性权重系数；在迭代寻优过程中动态调整模型中的惯性权重系数,提高解的全局、局部寻优能力来提高解的质量.2）引入遗传交叉思想,提高算法后期在解空间的探索能力.

1）自适应调整惯性权重系数

惯性权重系数ω 用来平衡全局和局部搜索,标准PSO 算法中固定ω 的值使得搜索效果不佳,很容易使算法陷入局部最优.因此,自适应调整惯性权重系数的值,在算法初期取较大的ω 值,增强算法的全局探索能力,随着算法的执行逐渐减小ω 值,增强算法的开发能力,在本文中应用的权重计算方式如下所示：

其中,t 为当前迭代次数,ωmax和ωmin表示惯性权重系数最大和最小取值,本文取ωmax=0.9,ωmin=0.4,Tmax为最大迭代次数.

2）遗传交叉重组

PSO 算法初期收敛速度快,后期容易陷入局部最优,为了跳出局部最优,在迭代达到一定次数后,触发遗传交叉重组机制丰富种群多样性.

遗传交叉重组的规则定义如下：在当前迭代的种群中,根据交叉率选取一定数量的粒子放入交叉重组池内,池内粒子随机两两交叉得到同样数目的子代粒子,并将子代粒子与当前迭代种群粒子混合,按照适应度排序筛选出排名前H 的粒子参与下一次迭代,本文定义执行交叉重组后得到子代粒子的位置和速度向量分别如下[18]：

本文定义改进PSO 算法流程图设计如图3 所示.

图3 算法流程图Fig.3 Algorithm flowchart

3.3 决策与资源分配联合优化策略设计

由上述描述可知,本文提出的计算卸载和资源分配联合优化算法是通过相互迭代卸载决策和资源分配两个子问题来获得最佳解,有关该算法的具体求解步骤如算法3 所示.

4 仿真与试验验证

为验证本文所提基于改进粒子群算法的计算卸载与资源分配联合优化算法性能,在其余参数不变的基础上,分别与3 种算法进行仿真对比试验,算法介绍如下：

随机卸载决策（Random）算法：任务随机分配云端、边缘端、本地执行,资源平均分配.

贪心（Greedy）算法：文献[14]的算法,上行功率与计算资源分配按照二分法、拉格朗日乘子法求取,基于贪心算法求取卸载决策,执行计算卸载与资源分配联合优化策略.

标准粒子卸载决策群（standard PSO,STPSO）算法：卸载决策基于标准PSO 求解,资源平均分配.

交叉重组PSO（cross recombination PSO,CRPSO）算法：本文算法,基于引入交叉重组机制与自适应ω的PSO 算法求解决策卸载,基于二分法、拉格朗日乘子法求取上行功率与计算资源分配,执行计算卸载与资源分配联合优化策略.

有关本章算法及仿真参数的设定如表1、表2 所示,其任务输入数据量服从[1,50]之间的均匀分布（单位为MB）,任务工作量服从[1,200]之间的均匀分布（单位为GHz）.

表1 算法相关参数Table 1 Algorithm related parameters

表2 实验仿真参数设置Table 2 Experimental simulation parameter settings

根据以上模型,在本仿真参数的验证中,忽略移动过程中通信链路切换带来的影响,重点关注卸载过程.任务可在本地、边缘端、云端执行,且假设所有边缘服务器的计算能力相同,在本次仿真环境中,边缘服务器的数目为8 个.基于表1～表2 两个表格中的参数,利用仿真平台进行对比试验,分别论证迭代次数、权重系数、用户数量、工作量对系统总代价的影响.

4.1 迭代次数对系统总代价的影响

Greedy 算法仅仅迭代到精度要求就停止计算,Random 算法结果的优劣是波动的,它们不属于进化类算法,解算出卸载决策的优劣受迭代次数影响较小,因此,不参与本部分测试.重点关注STPSO 和CRPSO算法中系统总代价与迭代次数之间的关系,以便选取合适的迭代次数值继续后续的测试.取平均用户数目m=300,时延与能耗的权重系数α=0.5,迭代次数T 设置为从1～500 均匀增加,仿真结果如图4所示.

图4 迭代次数仿真图Fig.4 Iteration number simulation diagram

随着迭代开始进行，两种算法的系统总代价都逐渐减小,当迭代次数达到300 次后,两种算法都能将系统总代价下降到较好的水平,但STPSO 算法系统易陷入局部最优导致总代价趋于平稳不再变化,CRPSO 算法由于在算法后期加入了交叉重组机制,系统总代价仍能缓慢下降.因此,在后续测试中将算法迭代次数设置为500,迭代到300 次后,在CRPSO算法中启用交叉重组机制,打破局部最优获得更优卸载决策.

4.2 时延能耗权重系数对系统总代价影响

系统总代价包括任务执行时间和设备消耗能耗,因此,时延与能耗的权重系数也会影响系统总代价,在测试中,设置迭代次数为500 次,用户数量为300,研究权重系数在0.1～0.9 之间均匀变化时,Random、Greedy、STPSO 和CRPSO 算法间性能比较,仿真结果图如图5 所示.

图5 时延能耗权重系数仿真图Fig.5 Simulation diagram of delay energy consumption weight coefficient

随着权重系数逐渐增大,时延相较于能耗的比重越来越高,系统总代价整体呈增加趋势,证明了时延在系统总代价中占据主导地位.在4 种算法中,Random 算法的卸载结果具有随机性,导致在4 种算法中评价最差.Greedy 算法虽然采取了和本文相同的资源分配方案及联合优化思想,但贪心算法在卸载决策的求取上还具有一定局限性,使得该算法总代价评价在4 种算法中位列第3.STPSO 算法仅采取资源平均分配方式,未充分体现联合优化思想,但基于粒子群算法能够得到较好的卸载决策,该算法评价仅次于CRPSO 算法.CRPSO 算法基于改进的粒子群算法求解更优的卸载决策,基于数学方法求解资源分配方式并充分应用联合优化思想,使算法评价达到最优.综合来看,CRPSO 算法显著降低系统总代价,降低了Random 算法总代价的54.09%,Greedy 算法的45.66%,STPSO 算法的18.26%.

4.3 用户数量对系统总代价的影响

当用户数目发生改变,系统的时延与能耗也会随之发生变化,系统总代价也会受到影响.为了探究用户数量与系统总代价之间的关系,设置迭代次数为500 次,时延与能耗权重系数为0.5,研究用户数目在50～500 之间均匀变化时,4 种算法性能比较,仿真结果图如图6 所示.

图6 用户数量仿真图Fig.6 Simulation diagram of the number of users

随着用户数目逐渐增多,接入系统的任务量增加,导致卸载过程的时延与能耗也在增加,系统总代价逐渐增大.结合4 种算法的自身特点,算法之间的总代价关系同上个实验相比保持不变.同样地,本文提出的CRPSO 算法系统总代价最小,降低了Random算法总代价的66.15%,Greedy 算法的54.53%,STPSO算法的35.34%.

4.4 工作量对系统总代价的影响

工作量也是影响系统总代价的因素,当任务工作量发生改变时,系统总代价也会受到影响.为了探究工作量与系统总代价之间的关系,设置迭代次数为500 次,时延与能耗权重系数为0.5,用户数量为300,研究最大工作量在60～200 之间均匀变化时,4种算法的性能比较,仿真结果图如图7 所示.

图7 工作量仿真图Fig.7 Workload simulation diagram

根据图7 可知,随着最大工作量不断增加,导致卸载过程中所需的时延与能耗增加,使系统总代价整体呈现增加趋势.基于4 种算法计算的系统总代价关系仍与之前仿真结果保持一致,本文提出的CRPSO 算法总代价最小,能够降低Random 算法总代价的59.34%,Greedy 算法的45.74%,STPSO 算法的24.07%.

基于以上4 项实验可知,设计资源分配求解方案、应用联合优化思想,基于进化类算法求解卸载决策等优化方式都能够降低系统总代价,相比较而言改进进化类算法来求解卸载决策的方式在降低系统总的代价上的效果更为显著.本文提出的CRPSO 算法不仅通过数学方法来求解资源分配方案,重点改进了粒子群算法来求解更优的卸载决策,还应用了联合优化卸载决策与资源分配两个业务的思想,使得本文算法在多项实验的仿真验证中评价最好,因此,本文提出的CRPSO 算法能够显著降低系统的时延与能耗,可以对边缘环境下移动服务起到很好的优化作用.

5 边缘计算在资产管理系统中应用

基于以上边缘计算联合优化算法,设计基于边缘计算技术的后勤资产管理系统构架.将北斗定位系统、RFID 系统、监控系统部署在资产终端用于采集资产实时监控管理所需数据,将各类底层数据的解析任务卸载到边缘服务器上,边缘服务器完成计算后直接将有效的数据推理结果上传至云端.用户操纵底层终端系统发布资产业务请求,系统首先会根据边缘服务器中存储的资产信息迅速完成响应,一些较为复杂的系统功能会通过调用云端存储数据来实现.

在系统运行过程中,本文提出的联合优化算法可以实现边缘计算业务优化,更好地为资产管理系统提供服务,终端设备层随机生成数据解算任务序列,结合当前各层服务器参数通过调度程序给出最优卸载决策方案,下放到各个单元执行.在本方案设计中,边缘层承担了主要计算业务需求,云端承担了主要存储工作,有效提升系统性能与用户体验,实现实时资产业务响应、精细化资产信息存储的功能需求[19].基于边缘计算技术后勤资产管理系统设计构架如图8 所示.

图8 边缘计算模式构架图Fig.8 Edge computing mode architecture diagram

为了验证应用边缘计算技术应用的有效性,本文根据软件定义网络的思想,构建了“Flootlight+Mininet”边缘计算平台环境来模拟引入边缘层及相关控制器算法的资产管理系统实际情况[20].同时和未引入边缘层的环境进行对比,图9、图10 展示了通过Mininet 所编写的两种环境下的网络拓扑.

图9 引入边缘层的网络拓扑Fig.9 Network topology with edge layer

图10 未引入边缘层的网络拓扑Fig.10 Network topology without edge layer

根据图9、图10,上方的h1 代表计算节点主机,下方的h2～h11 代表用户设备端,引入边缘层的网络拓扑中多了一层交换机（S8～S11）,通过在控制器C0中设置控制算法对交换机进行调度.分别设置两种环境下交换机数量为10 个和6 个,设备端的计算任务请求节点均为10 个,链路带宽设置为20 Mb/s,计算任务流大小为10～20 Mb/s,并根据上图编写网络拓扑运行脚本.启动Floodlight,运行Mininet 脚本并连接至控制器,连接成功后,利用Xterm、Iperf 软件从设备端请求节点向计算节点主机发送计算任务流,计算从单节点到多节点同时向计算节点主机交互的系统总时延,整理如图11 所示.

图11 节点与主机交互时延图Fig.11 Node and host interaction delay diagram

由图11 可知,随着计算任务请求节点增多,系统响应总时延不断增加,在引入了边缘层后,控制器会对请求节点的任务流进行合理调度,在多个节点任务流同时请求时减少用户总时延、提升用户体验.因此,本文提出的应用在资产管理系统环境的边缘计算构架以及边缘计算业务算法,可减少用户时延与设备能耗,提升用户体验.

6 结论

本文提出建立后勤资产管理系统边缘计算服务构架来解决现代化进程中的难题,重点研究边缘计算服务模型中资源分配与计算卸载业务,为降低边缘设备任务卸载的时延和能耗,提出了计算卸载与计算资源分配联合优化算法,将优化目标设定为用户的计算时延和能耗的加权和,来共同优化资源分配和计算卸载问题.基于二分法和拉格朗日乘子法分别求解上行功率以及计算资源分配问题,然后提出了改进的粒子群算法来求解计算卸载问题,最后给出本文提出的联合优化算法.试验仿真验证了本文提出算法的有效性,同其他标准算法相比,该算法能有效降低系统总代价,在后勤资产系统及未来的边缘系统环境中有很多优势和应用,但仍存在以下不足：

1）终端频繁移动的情况需要考虑

本文在仿真建模过程中假设当前时刻终端位置是固定的,然而在实际应用场景中,移动终端是频繁移动的,而这不仅会使上传速率发生变化,同时也会增加不同终端间的连接几率,使问题更具复杂化,因此,下一步的研究重点是在终端频繁移动的条件下,提出有效的卸载算法来降低系统总代价.

2）系统优化目标需考虑用户体验

目前仅选取计算时延和能耗的加权和最小作为本文的优化目标,然而在实际应用中,用户体验衡量系统好坏是一个十分重要的指标,因此,在后续的研究中,在研究目标的选择上,还应充分考虑用户体验等关键信息.