基于改进粒子群算法的边云协同计算卸载策略

刘向举,李金贺,蒋社想

(安徽理工大学 计算机科学与工程学院,安徽 淮南 232001)

为了弥补移动云计算(Mobile Cloud Computing,MCC)的不足,移动边缘计算(Mobile Edge Computing,MEC)作为一种有效的计算范例出现。MEC将计算和存储资源从云数据中心地理分布部署到网络的边缘,可以在物理上接近用户设备对数据进行分析和处理,从而大大降低任务执行的延迟和能耗,有效减轻核心网的流量负荷,延长移动设备的使用寿命。虽然与MCC相比,MEC具有更短的延迟和更强的可靠性,但它所能提供的资源量仍然远远小于MCC。因此,将移动设备生成的所有任务都卸载到MEC服务器上是不合理的,将云资源与边缘资源相结合,利用云资源作为边缘资源的辅助,形成云边协作的卸载场景,可以充分利用网络中的现有资源,为不同需求的任务提供更多的卸载选择。

计算卸载一直是一个热门的研究焦点。He W等人[1]研究了一个多用户全双工通信的MEC系统,考虑了功率控制、时间调度、卸载决策和用户配对策略,提出的最优算法有效的解决了系统延迟最小化问题。罗馨玥等人[2]针对多个移动设备的MEC系统,考虑了在系统时延的约束下,提高系统的能量效率。然而,这些工作只考虑了如何利用边缘服务器的资源,没有考虑到结合云服务器的资源。因此,现有的工作研究了云边缘协作环境中与计算卸载相关的问题,张帆等人[3]针对云边协同的计算卸载模型,以最小化时延为目标,设计了一种多任务计算卸载方法。杨君等人[4]提出了一种边云协同计算的能耗感知资源调度方法,能够在实时性的前提下有效降低能耗。于滨等人[5]考虑了多移动设备组成的边云协同系统,为了降低移动设备的时延,提出了基于深度强化学习的任务卸载算法。

上述工作只针对单一目标进行优化,没有考虑到时延和能耗的联合优化。因此,本文研究以时延和能耗的加权和为目标,提出了一种基于改进的粒子群算法的卸载方法,能够为边云协同场景范围内的所有移动设备制定计算卸载策略。

1 系统模型和问题描述

1.1 网络模型

本文考虑了一个具有1个云服务器、多个MEC服务器和多个用户的云-边缘协作网络框架,如图1所示。其中在基站上配置了可以执行计算密集型和数据敏感性任务的边缘服务器,每个移动用户通过无线信道关联到相应基站,可以在唯一的MEC服务器上执行计算卸载,或者边缘节点通过回程链路将任务卸载到远程云服务器。

基站或MEC服务器集合可以表示为N={1,2,…,n,…,N},用户移动设备任务集合为U={1,2,…,u,…,U}。每个移动用户u每次都有一个不可分割任务需要执行,任务属性采用二元组表示为Qu={su,wu},其中su表示上传计算的任务数据大小,wu表示处理任务所需的计算量。

1.2 通信模型

假设系统内的所有移动设备采用正交方式接入,移动设备之间不存在干扰。系统中每个用户在一定时间间隔内位置不变,根据香农信道容量公式,移动用户u与边缘服务器n之间的上行传输速率可表示为

(1)

1.3 计算模型

(1) 本地计算:假设每个用户设备具有固定且不同的CPU频率,则用户任务Qu在本地计算的执行时间和能耗分别为

(2)

(3)

(2) 移动边缘计算:用户将任务卸载至MEC服务器的处理主要包括3个阶段:上传数据、在MEC服务器上执行任务和结果返回。由于任务结果数据量相对较小,任务结果在下行传输中的能耗和延迟可以忽略不计,所以本文主要关注前2个阶段。

根据式(1),移动用户u卸载任务Qu上行传输到基站n时的传输时延和能耗分别为

(4)

(5)

(6)

(7)

式中:pedge为与MEC服务器n相联的基站平均功率。则任务Qu卸载至边缘计算的时延和能耗分别为

(8)

(9)

(3) 云服务器计算:当任务卸载至云计算时,任务需要先卸载至MEC服务器,再传输至云服务器进行云计算和结果返回。由于云距离边缘节点较远,本文将不同的边缘节点和云服务器之间的距离视为相等,同样忽略了结果返回的延迟。假设边缘节点上传任务到云服务器的传输速率为常量Rc。任务Qu的传输延迟和能耗分别为

(10)

(11)

任务Qu在云服务器的执行时间和能耗分别为

(12)

(13)

(14)

(15)

1.4 问题优化模型

根据上述模型,处理任务Qu的总延迟和总能耗分别为

(16)

(17)

式中:αu,βu,γu取值为0,1整数的二元变量卸载决策,当取1时分别表示任务Qu在移动设备本地、MEC服务器或云服务器进行计算,由于任务只能在一个地方执行,需满足约束条件αu+βu+γu=1。

在MEC系统中,执行计算任务的时延和能耗决定了QoS,由于不能同时最小化平衡2个因素,本文将系统总成本定义为执行任务时延和能耗的加权和,则有

(18)

式中:λ为时间成本和能量消耗的加权系数,可以根据实际需求进行调整。

本文优化目标是通过优化卸载决策来最小化所有任务在边缘云之间执行总成本C,优化问题表述如下

s.t.C1:αu,βu,γu∈{0,1}

C2:αu+βu+γu=1

C4:0≤λ≤1

(19)

式中:约束C1、C2表示任务只能在一个地方被处理,约束C3为给移动设备任务分配的计算资源约束;约束C4限制时延和能耗的权重和为1。当用户数和基站数目较大时,问题(19)为大规模混合整数非线性规划问题,穷举搜索方法虽然能够得到最优解,但是不实际和不可行,因此本文使用改进粒子群算法解决该问题。

2 基于改进粒子群算法的移动边缘计算卸载方法

粒子群优化算法(Particle Swarm Optimization Algorithm,PSO)是一种广泛使用的启发式优化算法[7],不需目标函数的连续性和凸性,但容易出现早熟,导致局部收敛。模拟退火算法(Simulated Annealing Algorithm,SA)收敛效率较低,但其收敛到全局最优解的概率为1[8]。结合2种算法的优点,可以提高算法的灵活性和粒子多样性,获得较强的全局优化能力,从而提高参数优化的精度。因此,本文将SA与PSO结合,使用改进粒子群算法(Improve Particle Swarm Optimization Algorithm,IPSO)的方法解决问题P1。

2.1 编码和初始化

本文采用整数编码,粒子收敛的位置表示最终的卸载决定。用户任务可以在本地、N个MEC服务器、1个云服务器的场景中执行,因此位置范围定义为N={0,1,…,N,N+1},其中0表示在本地计算,1～N表示在边缘服务器1～N中计算,N+1为云计算。PSO在每次迭代中,使用式(22)和式(23)更新粒子的位置和速度,但每个粒子的位置值由式(20)转换为离散数值。

(20)

2.2 适应度函数

在PSO中每个粒子都通过一个适应度函数来评估,本文适应度值由式(21)计算,表示为

(21)

2.3 粒子更新策略

(22)

(23)

式中:k表示迭代次数;c1和c2为学习因子;ω为速度惯性权重;rand()表示在[0,1]之间的均匀分布的随机数。

为了更好的平衡算法的全局搜索能力和局部改进能力,惯性权重ω应合理设置,一些研究者提出了改进的惯性权值的PSO算法[9-10]。但是,这些方法并没有充分限制动态求解过程中惯性权值的取值范围,并且与每一代粒子的适应度的相关性还有改进的空间。本文采用基于适应度值和迭代次数的惯性权重策略。

(24)

(25)

式中:当f(Xi)≥favg时,如果ω>0.99,则ω=0.99。当f(Xi)

IPSO算法优化卸载决策的主要过程如下:

步骤1:设置PSO算法的迭代次数kmax、种群大小Num、加速度因子c1和c2,设置SA算法的初始温度T、退火系数h和马尔可夫链长度s,初始化每个粒子的速度和位置。

步骤2:选择式(21)作为适应度函数,计算所有粒子的适应度值,确定初始最优种群位置。

步骤3:根据式(25)更新惯性权值ω,式(22)和(23)更新速度和位置,根据适应度函数找到新的最优个体位置pbesti和最优群体位置gbesti。如果PSO算法收敛,找到当前最优位置pbesti,则继续执行步骤4,否则重复步骤3,直到算法收敛。

步骤4:引入SA算法,将步骤3中得到的当前最优位置pbesti作为SA算法的初始位置z,即z(t)=pbesti(t),并在其邻域内随机选取一个新的位置z′。分别计算2个适应度J(z)和J(z′),并用Metropolis准则来判断是否接受替换新的最优种群位置。

更新温度T(t+1)=hT(t),迭代至s后,继续执行步骤5。

步骤5:如果SA算法搜索的最终位置z的适应度小于PSO算法搜索的当前最优种群位置Pg(t),则z作为PSO算法新的最优种群位置。

步骤6:判断适应度值是否满足条件,如果满足,输出种群的最优位置;否则,返回步骤3,直到PSO算法完成kmax次迭代。

3 试验结果与分析

3.1 试验环境配置

为了评估提出算法的有效性,本文试验使用MATLAB R2022b。仿真环境为30个用户和5个MEC服务器在1 000×1 000 m2的区域中随机分布,其中云服务器位于中心。其他仿真参数如表1～2所示。

表1 IPSO算法参数设置

表2 仿真环境参数设置

3.2 对比方法

将本文提出的基于IPSO的边云协同算法与以下算法性能进行对比:

(1) 本地计算(Local Offloading,LO):计算任务由本地设备计算,不进行任务卸载。

(2) 边缘卸载(Edge Offloading,EO):所有任务由边缘服务器完成。

(3) 随机卸载:(Random Offloading,RO):所有任务进行随机卸载。

3.3 试验结果及分析

首先评估提出的算法的收敛性,然后验证提出的算法与其他基线算法的性能比较。

3.3.1 算法收敛性

图2为30个移动用户数下的算法收敛性。从收敛曲线可知,PSO需要约50次迭代才能收敛,IPSO只需20次左右迭代即可收敛,能够快速求解到最小系统成本,比PSO降低了8.7%的系统成本,这表明IPSO具有良好的收敛性,能够克服PSO算法容易陷入局部极值点的缺点。

图2 算法收敛性

3.3.2 移动用户数的影响

对IPSO算法及对比算法在不同移动用户数量下的性能进行了评估,如图3所示。在此试验中所有用户卸载同一个任务,即su=700 kB。结果表明,相对于其他方案,IPSO算法一直是最优策略,实现了最低的总计算成本。这是因为本文所提出的算法是一种边云协同卸载方案,用户可以在本地、边缘服务器和云服务器处理任务,可以充分利用计算能力较强的边缘节点的计算资源,同时分配更多的云计算资源来辅助计算能力较弱的边缘节点,使得卸载决策更合理的分配任务,减小任务执行成本。当用户数为30时,与EO、RO、LO算法相比,IPSO算法的系统总成本平均分别降低了24.1%、53.9%、72.3%。

图3 用户数量对系统成本的影响

3.3.3 任务数据大小的影响

将每个任务的数据大小从500 kB到2 500 kB递增,给出的不同算法下任务数据大小对系统总成本的影响如图4所示。结果表明,增加数据大小不会改变LO算法总计算成本。其余算法成本随着任务数据大小的增加而增加,这是因为系统中通信资源是固定的,输入数据量的增加会直接影响到卸载任务的上行传输延迟和能耗。这说明,计算少量数据的卸载任务可以获得更好的结果。

图4 任务数据大小对系统成本的影响

3.3.4 用户偏好的影响

用户时延偏好λ从0.1变化到0.9对IPSO的任务平均时延和能耗的影响如图5所示。结果表明,随着λ的增加,平均时间消耗降低,能量消耗增加,表明IPSO能够根据用户需求进行动态调整卸载决策,求解最小的系统成本。

图5 用户偏好的影响

4 结语

为了充分利用云服务器、用户移动设备和MEC服务器的异构计算能力,本文提出了一种基于改进粒子群算法的边云协同任务卸载策略。该策略实现了网络资源的协同和管理,能够满足在多种约束下处理用户任务的系统成本最小化的需求。试验结果表明,该算法有效且能够在有限迭代次数内收敛。与基准算法相比,本文算法具有最低的系统成本、能量消耗和延迟,并且随着任务数量的增加,优势更加明显。然而,本文研究的MEC场景为准静态系统,在未来的研究中,将考虑到用户移动性、环境参数的时变性等问题,为动态多变的场景提供更好的卸载策略。