异构边缘云架构下的多任务卸载算法

尼俊红, 臧云

(1.华北电力大学(保定) 电子与通信工程系,河北 保定 071003; 2.华北电力大学 河北省电力物联网技术重点实验室,河北 保定 071003)

随着移动通信技术的发展和智能终端的普及,增强现实(augmented reality,AR)、虚拟现实(virtual reality,VR)、无人驾驶等各种应用不断涌现,用户对服务质量(quality of service,QoS)和体验质量有了更高的要求。预计到2030年,移动数据流量将出现爆炸式增长,全球移动终端数将接近1 000亿,中国可能达到200亿[1]。在终端设备上运行这些新兴的数据量较大的应用程序,需要大量的计算资源、存储资源以及较高的能耗,而移动设备的计算能力、资源存储和电池电量往往是有限的,无法满足这些需求。

欧洲电信标准化协会在2014年成立了移动边缘计算(mobile edge computing,MEC)规范工作组,促进对移动边缘计算的研究[2]。移动边缘计算是指在移动网络边缘部署计算和存储资源,为移动网络提供IT服务环境和云计算能力,从而为用户提供超低时延和高带宽的网络服务解决方案[3-4]。MEC的关键技术为计算卸载,为应用制定适合的卸载决策[5]是近年来的研究热点。

研究人员为了研究任务卸载决策的相关问题做了许多工作,通过建立车辆和无人机协助下的MEC模型,将不同的任务按需卸载到不同的边缘节点,并设计了分布式匹配-贪婪算法[6]。Gu等[7]研究了车辆网络移动边缘计算系统,提出了2种独立的启发式匹配算法解决移动中的任务卸载问题。Du等[8]通过联合优化卸载决策和计算资源、无线电资源的分配,解决混合云/雾系统中的计算卸载问题。Wang等[9]提出了基于智能体的任务卸载体系架构,协同无人机和边缘服务器上的计算资源为用户提供最优的任务卸载决策。Yu等[10]建立了深度多标签分类模型,并将模型分为离线演示生成、离线模型训练和在线决策3个阶段,提出了基于深度模仿学习的MEC任务卸载策略。Ke等[11]考虑车辆移动场景下信道的时变性,建立了异构车载网络任务计算卸载模型,提出了一种基于深度强化学习的自适应计算卸载方法,通过权衡能耗、带宽分配和缓冲队列的成本来选择任务最佳卸载策略。

除了以上这些方法,还有一些研究者通过群体智能算法解决卸载问题,例如遗传算法(genetic algorithm,GA)、粒子群算法(particle swarm optimization,PSO)等。王妍等[12]提出云辅助移动边缘计算的计算卸载策略,在GA算法的基础上,设计了一种基于改进GA算法的计算卸载算法。罗斌等[13]针对时延敏感型的应用,提出了一种基于PSO算法的计算卸载策略,在能耗约束条件下最小化时延,使用惩罚函数来平衡时延与能耗。Wu等[14]考虑延迟和能量消耗因素,提出了一种边缘云协同多任务计算卸载模型,采用非线性指数惯性权重PSO算法进行求解。Wei等[15]通过建立异构网络模型以及任务依赖关系模型,设计了结合贪婪策略的PSO和动态PSO 2种算法研究任务卸载策略。Adhikari等[16]研究了分布式雾设备和集中式云数据中心的协作,使用加速PSO技术为分层雾云环境设计了一种多目标卸载策略,在有效利用计算资源的同时,最小化总成本和延迟。

上述研究工作的共同特点是边缘节点类型单一或者在构建系统模型时未考虑不同计算任务的差异性。而在实际环境中,往往是复杂异构的边缘网络,而用户侧无论是任务的类型还是任务的数量都不是单一的。本文考虑构建混合云/雾的异构边缘网络模型,将多任务卸载到车辆、无人机、路边单元等边缘节点或者通过边缘节点卸载到边缘云,满足用户的服务质量和体验质量。

1 异构边缘云系统模型

1.1 网络模型

如图1所示,本文考虑由N个用户,M个边缘节点,1个边缘云组成的异构边缘云系统,其中无人机、路边单元、车辆作为边缘节点,数量分别为I、J、K,I+J+K=M。为了满足用户的服务质量和体验质量,用户可以在本地执行任务,也可以将任务通过D2D方式卸载到车辆,或通过蜂窝无线网络卸载到无人机、路边单元(road side unit,RSU)等边缘节点。由于边缘节点的计算能力和能源有限,当其无法满足用户需求时,可将任务通过边缘节点中继到边缘云服务器。边缘云部署在服务小区的基站上,无人机和车辆通过无线方式连接到边缘云,路边单元通过有线链路连接到边缘云。

图1 异构边缘云系统网络模型

用户卸载决策的约束条件为:

(1)

1.2 计算模型

为了便于分析,假定边缘节点和边缘云仅在接收到所有输入数据之后,开始执行任务。

1.2.1 本地执行

(2)

(3)

1.2.2 边缘节点执行

Bn/Rn,ei,j+Cn/fei,j+Dn/Rei,j,n

(4)

式中:ei,j的第1个下标i表示边缘节点类型,i=1,2,3分别对应无人机、路边单元和车辆;j表示边缘节点的序号;Bn、Rn,ei,j分别表示用户n上传数据量大小以及用户n和边缘节点ei,j之间通信链路的上行传输速率;fei,j表示边缘节点ei,j的计算能力;Rei,j,n表示边缘节点ei,j与用户n之间的下行传输速率。假定通信链路的上、下行信道条件相同,且分配带宽相同,则上、下行传输速率相等,即,Rn,ei,j=Rei,j,n。

用户n将任务卸载到边缘节点执行的能耗为:

(5)

1.2.3 边缘云执行

除了以上几种任务执行方式之外,还可以将任务通过边缘节点中继到部署在基站的边缘云服务器执行。

因此,任务通过边缘节点中继到边缘云服务器卸载的时延为:

(6)

(7)

(8)

(9)

此外,数据在无人机和边缘云服务器之间传输阶段和任务执行阶段,UE处于空载状态,此时的能耗为:

(10)

1.3 问题表述

用户n任务执行时,系统的时延Tn和能耗En可以分别表示为:

(11)

(12)

(13)

2 H-PSOGA任务卸载算法

PSO和GA算法都是经典的群体智能算法。PSO算法原理简单、搜索速度快,但是容易陷入局部最优;GA算法具有很强的全局搜索能力,但是收敛精度不高。本文采用先串行后并行的方式,提出了一种基于PSO算法和GA算法的混合优化算法(hybrid particle swarm optimization and genetic algorithm,H-PSOGA)。

假设粒子群规模为S,整个粒子群的位置集合表示为X={x1,x2,…,xS},速度集合表示为V={v1,v2,…,vS}。

H-PSOGA算法首先进行PSO进化,计算每个个体的适应度值并进行排序,然后利用PSO融合GA进行子代的选择、多点交叉、反向变异,形成新的子代;子代再进行PSO进化,并重复上述过程再次形成新的子代;循环往复,直至得到最优解。H-PSOGA算法优化过程如图2所示,m为粒子群初始规模,算法实现具体步骤为:

图2 H-PSOGA 算法优化过程

1)随机初始化每个个体的速度、位置以及相关参数,对不满足约束条件的个体重新初始化;

2)将个体当前位置设置为个体最优任务分配方案Gbest,并将适应度值最大的个体的位置设置为群体最优分配方案Hbest,计算每个个体的适应度值为:

(14)

式中:λt和λe为时延和能耗的权重系数;τmax q和emax q分别为q类型任务的容忍时延和容忍能耗。

3)根据式(15)、(16)更新个体每一维度的速度与位置并取整:

v(t+1)=ω·v(t)+c1·mrand·(Gbest-x(t))+

c2·mrand·(Hbest-x(t))

(15)

x(t+1)=x(t)+v(t+1)

(16)

式中:ω为惯性权重;c1、c2为学习因子;mrand为分布在区间[0,1]的随机数。

权重ω随着适应度值的变化而变化:

(17)

式中:F表示目前的适应度值;Favg、Fmin分别表示目前所有粒子适应度的平均值和最小值。当粒子目标值比较分散时,减小惯性权重,粒子目标值比较集中时,增加惯性权重;

4)判断是否满足PSO进化的迭代次数或者收敛精度,若满足条件,则执行步骤5),否则执行步骤2),直到满足条件为止;

5)计算每个个体的适应度值并按照从大到小的顺序进行排序;

6)种群选择,将排序后的种群Q平均分成4个子种群,淘汰适应度值最小的子种群4,如图3所示;

图3 选择操作示意

7)多点交叉和反向变异:保留的3个子种群进行交叉、变异操作,对每一维度进行取整;

定义平均距离的概念,通过判断交叉父代同一维度的距离与平均距离的大小,本文设计了一种交叉方式。假设2个个体分别为x1和x2,定义2个个体的平均距离为:

(18)

图4 交叉操作示意

由图4(a)的2个个体的基因序列,根据式(18)计算2个个体的平均距离为1.37,图4(a)中第4维和第5维的距离大于平均距离,则第4维和第5维对应的基因分别交换位置,得到图4(b)的子代。

在实数编码时,等位基因的类型不再是简单的布尔型,故变异不能简单的取反。本文采用基于时变概率的反向学习方式进行均匀变异,使个体跳出局部最优。设个体目前适应度值为Fs,目前种群的平均适应度值为Favg,适应度值方差ψ2为:

(19)

(20)

(21)

8)适应度值最大的子种群直接进行PSO速度和位置更新生成子代;

9)计算所有子代的适应度值并按照从大到小的顺序进行排序;

10)选择适应度值较大且数量与初始种群相同的子代重新组成新的种群;

11)判断总的迭代次数或者收敛精度是否满足条件,若满足条件,则输出最优解,即最优卸载方案,否则执行步骤2)。

3 H-PSOGA算法仿真与结果分析

3.1 仿真参数设置

本文使用Matlab 2020a软件对H-PSOGA算法性能进行仿真验证。首先用6种标准测试函数对H-PSOGA算法的性能进行测试,为了便于观察,采用测试函数值的相反数进行绘图。然后将H-PSOGA算法应用到系统模型中,通过与基线算法的对比,验证本文算法在解决异构边缘云架构下的多任务卸载中的适用性。表1为仿真模型参数。

表1 仿真参数

表2为6种标准测试函数。算法控制参数:粒子群规模S=40,粒子维度N=100,迭代次数D=1 000,学习因子c1=1.5,c2=2.5,惯性权重的最大值和最小值为ωmax=0.8,ωmin=0.4,标准测试函数最优解为0。因为是n维粒子空间,(0)n为每个维度的粒子的最优位置都是0。

表2 标准测试函数

3.2 仿真结果分析

惯性权重ω可以控制粒子的搜索范围,增大ω的值可以提高算法的全局搜索能力,减小ω的值可以提高算法的局部搜索能力。对多种PSO改进方案进行对比实验,如图5所示,随着迭代次数的增加,几种改进PSO的方案以收敛速度为代价提高了收敛精度,非线性递减改进权重方案的收敛精度最高,故采用该方案与本文H-PSOGA算法进行对比实验。

图5 不同惯性权重适应度值曲线

为了更加清晰直观地说明H-PSOGA算法的性能,通过6种标准测试函数比较标准PSO、非线性改进权重方案、PSOGA算法以及本文H-PSOGA算法的收敛情况,如图6所示。

图6 6种标准函数测试结果对比

从图6可以看出,6种算法的适应度值均随着迭代次数的增加而逐渐增加。对于任意标准测试函数,标准PSO、非线性改进权重方案以及PSOGA算法的适应度值增加到定值达到稳定,即收敛状态。而对于H-PSOGA算法来说,对于不同的标准测试函数,H-PSOGA算法的适应度值表现出不同的收敛效果。

图6(a)和(b)中H-PSOGA算法适应度值整体呈现增加的趋势,还未达到收敛的状态;图6(c)和(e)中H-PSOGA算法的适应度值收敛到定值,且收敛精度高于其他算法。图6(d)和(f)中H-PSOGA算法在迭代到一定次数时停止迭代,此时得到最优解。

总体来说,H-PSOGA算法的收敛精度更高,用多种测试函数也证明了H-PSOGA算法的普适性。将H-PSOGA算法应用到系统网络模型,进行对比实验,如图7所示,收敛后的适应度值比标准PSO和PSOGA算法分别提升36.5%和16%。

图7 适应度函数收敛曲线

从图7可以看出,随着迭代次数的增加,标准PSO算法、非线性改进权重PSO算法、PSOGA算法的适应度值都会增加,最后收敛到相对稳定的状态。相对于基线方案,H-PSOGA算法的适应度值较大,随着迭代次数的增加收敛速度较快,收敛精度也较高,证明了H-PSOGA算法适用于本文提出的异构网络模型,同时也验证了H-PSOGA算法的性能。

图8所示为不同类型业务的卸载决策。图中数字1～5为5种具有不同任务复杂度、容忍时延、容忍能耗的计算任务,任务类型序号越大,任务复杂度越高。任务的复杂度越大,本地执行任务的概率越小,卸载到无人机、路边单元、车辆以及边缘云的概率越大,这是因为本地无法满足用户业务的需求,需要将任务卸载到计算能力更大的边缘节点或边缘云服务器。

图8 不同类型任务卸载方案概率分布

图9为系统平均开销与用户数量的关系曲线。从图9中可以看出,随着用户数量的增加,系统的平均开销逐渐增大。

图9 系统平均开销与用户数量关系

在用户数量相同的情况下,与对照方案相比,H-PSOGA算法的系统平均开销最小。在用户数较少时,几种方案的性能较为接近,H-PSOGA算法的性能优势不是很明显;当用户数超过 150时,系统性能提升较为明显,例如在用户数为200时,相比标准PSO、非线性改进算法和PSOGA算法的性能提升分别为43.06%、42.98%和31.52%;在用户数为300时,相对上述3种对照方案的性能提升分别为31.08%、30.38%和29.4%。

4 结论

1)提出混合优化算法H-PSOGA实现异构边缘云架构下的多任务卸载,有效提高了收敛精度,降低了系统总开销。

2)本文在研究任务卸载时将通信资源和计算资源设为固定值,而在实际情况中,需要联合任务卸载和资源分配进行优化,将是后续研究重点解决的问题。