基于多目标优先级粒子群算法的资源调度策略

朱新峰，吴名位，王国海

(1.扬州大学 信息工程学院，江苏 扬州 225100；2.中电科航空电子有限公司 航空电子事业部，四川 成都 610000)

0 引 言

近年来，随着5G技术的应用推广，移动边缘计算(mobile edge computing，MEC)的研究和应用也越来越广泛。MEC一直被公认为是一种很有发展前景的技术，尤其在触觉互联网、物联网(IoT)和互联网等下一代互联网应用领域中，增强现实、无人驾驶等众多新兴领域对延迟提出了更高的要求。MEC将网络控制、数据处理和相关存储迁移到网络边缘，为覆盖范围内的移动用户提供高可用的密集型计算服务。因此，智能移动终端上可运行对带宽、存储和计算高要求的应用任务，同时大大降低传输时延，从而提高用户的无感体验。但随着移动网络和电子信息技术的发展，移动用户和智能移动终端数量呈爆炸式增长，这为MEC的发展带来很大的挑战，尤其是在边缘基站的计算资源分配方面。边缘基站计算资源的紧缺性要求尽可能公平地为用户分配相关资源，如果没有公平的资源分配，可能无法满足部分用户的最小资源需求，造成用户设备性能下降、用户体验差等不良影响。目前，边缘云均由若干个智能基站组成，因此要实现边缘云的资源公平分配，就要合理调度边缘云中每个基站的资源，使得每个基站的资源都可以得到充分利用，从而实现整个边缘云资源的充分利用，使边缘云既能满足用户使用体验，又尽可能惠及更多的用户。合理的资源调度在实现边缘云充分利用的同时实现了资源的集约化，也为服务提供商带来了更多的利润。

1 相关工作

在边缘云中，如何较好地满足用户需求,为用户提供合理的资源需求是服务提供者需要考虑的重要问题。随着客户数量的变化，用户所需资源量也在不断变化，或大或小，边缘云需要有效调度各基站的资源来应对这种变化，同时做到资源的集约化使用，并尽可能满足每个用户的资源需求。因此，如何有效调度现有的资源来满足这些需求显得至关重要。该文从用户实际资源需求出发，结合边缘基站部署结构，设计了MPPSO算法，对用户任务进行合理分类，把用户子任务和边缘基站进行联合编码，最终寻找出最优资源调度器。文献[4]通过在网络外围提供云服务减少服务延迟回程负载，并增强相关操作方面的体验质量。文献[5]在资源匹配算法中，从资源位置、任务优先级和网络传输成本等方面构建了资源匹配的优化问题，通过添加伪容器将最优问题转化为加权二部图的最优匹配问题，实现了边缘服务器上任务资源匹配的最优策略，有效降低了网络时延，提高了服务质量。文献[6]将数据块的优化布置与任务的优化调度相结合，减少提交任务的计算延迟和响应时间，提高边缘计算的用户体验。文献[7]基于混合整数线性规划的云数据中心虚拟机迁移问题，采用支持向量机实现虚拟机在系统间的分配，实现了稳定且低成本的媒体服务。文献[8]优化了一组虚拟机的平均任务响应时间，提出并求解了有功耗约束的多核服务器处理器的最优时间划分问题，既优化一组虚拟机的整体性能，又使虚拟机的总功耗不超过一定的可用功率。文献[9]基于特征粒子群优化的虚拟机初始配置改进离散粒子群优化算法，基于内存利用率、带宽利用率和虚拟机大小的虚拟机将运营成本和环境影响降到最低。文献[10]提出的特殊任务的调度算法，使任务选择合适的边缘云执行，规划边缘云上调度执行顺序，使用预测算法应对任务的移动性，在指定的时间内，使得更多的任务得到处理。文献[11]提出的自适应梯度多目标粒子群算法(AGMOPSO)，采用stocktickerMOG方法更新文档，提高了算法的收敛速度和边缘云的计算性能，平衡了AGMOPSO的收敛性和多样性。

2 问题描述

边缘云由多个智能基站组成，每个基站具有计算、存储和带宽控制等功能，边缘云向其覆盖范围内的移动用户提供资源服务，每个用户所需的资源可以有多种。以日常使用的APP为例，一个任务需要多种资源，例如CPU计算、数据存储和必要的软硬件。因此，根据不同用户的需求来制定对应的资源分配策略，把虚拟化资源合理地提供给用户是现在常用的方法，一套虚拟资源里包含各种资源类型，以满足用户的各种需求。

假设用户为User,用户群体如式(1)：

User：={User,User,…,User}

(1)

用户需要执行

n

个任务

T

，则用户可以定义为：User:={

T

1,

T

2,…,

T

}

(2)

每个任务需要的资源定义为：

T

:={CP,SR,SW,BW,

Co

}

(3)

边缘云有

m

个智能基站群，如式(4)：

BT:={BT,BT,…,BT}

(4)

每个基站拥有多种虚拟资源，一般如式(5)：

BT:={CP,SR,SW,BW,Co}

(5)

其中，CP为计算资源，SR为存储资源，SW为软硬件资源，BW为带宽资源，Co为单位资源功耗。假设边缘云由

m

个智能基站组成，覆盖范围内有

k

个用户，每个用户需要执行

n

个任务，目标是找到科学合理的资源调度策略，把边缘云内的资源分配给用户，保证用户的任务得到有效执行，并满足以下条件：

边缘云为用户提供相应服务时，要综合考虑各种因素，这里主要考虑以下三个：

(1)数据传输速率。对于基站来说，速率的不断提高可大大降低时延，也是考察边缘基站的主要性能之一，这对服务提供商来讲可以获得较高的利润。因此，最好的方式就是合理优化任务分类，尽量将优先级高的任务卸载至边缘基站，优化资源调度程序，避免信道拥挤和非必要占用，实现所有任务数据传输速率总和最大，从而提高基站性能。

(2)任务优先级

q

。如何满足不同用户的不同优先级任务的资源需求也是衡量基站性能的重要指标之一。在有限的资源内，能覆盖的用户数量也是一定的，如何让现有的资源尽可能满足任务的需求，此时参照任务优先级调用资源显得十分重要。

(3)任务执行能耗。基站的能耗是一定的，也是影响运行商利润的重要因素之一，在提供一定资源量的前提下，建设消耗每单位资源功耗为(Cost)，则总功耗应不小于所有任务执行结束时的总和。

3 基于多目标粒子群算法的资源分配机制

3.1 标准粒子群算法PSO

PSO算法源自自然界中鸟群觅食的灵感，当鸟在觅食的时候，除了按照自己的目标飞行，还要参照群里其他鸟的飞行轨迹，尤其是靠近食物的那只鸟。在PSO中，每只鸟都被看作是一个粒子，鸟群被看作是粒子群，每个粒子被编码成一种任务资源调度程序。PSO的主要目标是在迭代更新多次后从种群寻找出最优的粒子，也就是最优的任务资源调度程序，粒子的更新公式如式(6)：

(6)

3.2 多目标粒子群MOPSO

在单粒子群算法中，只要一个适应度函数，在粒子的更新过程中，也在不断计算粒子的适应度值，然后依次做比较，寻找个体历史最优值和群体全局最优。在多目标粒子群算法中要面临两个主要问题，一是如何选择pb(个体最优)。在单目标粒子群中，只要对比一下就可以选出pb，但对于多目标，有多个适应度函数,很难判断谁优谁劣，无法严格说明哪个好，哪个差。二是如何选择gb(全局最优)。在单目标粒子群算法中只有一个gb,但在多目标粒子群中，最优的个体可能有多个，而每个粒子只能选择一个领导者，这让很多粒子难以抉择。针对以上问题，引进帕累托算法理论，调整相关参数，使得多个适应度函数向相同方向递进，这样就可以避免个体在寻找最优时背向而行。对于第二个问题，这里使用外部存档集，将最优解存放至外部存档集，从中选取全局最优值，以粒子拥挤度来选择领导者，为了保证粒子的搜索能力，尽量选择密度小的粒子。

3.3 帕累托最优理论在多目标粒子群算法中的应用

在边缘云面临多个目标考量的情况下，很难选择出一个最优的资源调度程序，无法保证该资源调度程序是否在所有方面都优于其他调度程序。也就是说，假设一共有

a

个适应度函数，假设有资源调度程序A和B，A中的一部分适应度值优于B中的适应度值，但是B剩余部分的适应度值要优于A中的适应度值，此时，就很难确定A和B谁更优。帕累托最优理论可以在多个资源调度程序中对比出谁更优一些。根据这一理论，可以确定，在MPPSO中生成的所有资源调度程序中肯定至少存在一个最优的资源调度程序。假设Si为所提出MPPSO算法产生的资源调度程序，前文介绍了三个性能指标，这里使用其中两个，即数据传输速率和任务执行能耗，在MPPSO产生的资源调度程序中，Si的这两项指标要优于其他任意资源调度程序。

4 MPPSO

文中分析在资源有限的MEC中如何实现系统资源的均衡调度，包括带宽、功率的资源的联合分配，考虑到用户任务的优先级和全局吞吐量，设计两个适应度函数。

4.1 适应度函数设计

用户属性(user)：用户数量

N

，用户序号

i

=(1,2,…,

N

)，每个用户包含

j

个任务(

T

)，

j

=(1,2,3…)，用户

i

可表示如式(7)：

(7)

每个任务包含

k

个子任务(

t

)，

k

=(1,2,…,

K

)，则第

i

个用户的第

j

个任务可表示为：

(8)

子任务如式(9)：

(9)

参照香农公式，任意子任务数据上行传输速率如式(10)：

(10)

则第

i

个用户的第

j

个任务的任务数据上行传输速率如式(11)：

(11)

α

,,可筛除未卸载至边缘基站的子任务。任意子任务卸载至边缘云处理总能耗为数据传输能耗与任务处理能耗之和，如式(12)：

(12)

此时

α

,,=1，未卸载至边缘基站的子任务功耗如式(13)：

(13)

此时

α

,,=0，则第

i

个用户的第

j

个任务的任务总能耗如式(14)：

(14)

考虑边缘基站资源有限和任务相关要求，式(11)和式(14)应满足式(15)和式(16)：

(15)

(16)

综上，适应度函数

f

=max(

R

,)，适应度函数

f

=min(

E

,)，为提高算法性能，文中修改

f

=-max(

R

,)。

4.2 粒子编码和解码

文中采用子任务长度和基站数量结合的方式进行编码，单个粒子的长度为子任务个数的两倍的一维矩阵，矩阵中从首元素至尾元素，每两元素分别代表子任务的优先级和基站调度序号。例如{3,2,2,1,1,3}，从左至右表示优先级为3的任务在第2个基站执行，优先级为2的任务在第1个基站执行，优先级为1的任务在第3个基站执行。优先级越高，越优先卸载至边缘云执行，同时尽量使得每个边缘基站可以均匀调用。

在解码时，从粒子中提取在边缘基站执行的子任务排序，综合考虑每个子任务执行前的子任务在边缘基站的执行时间和其父任务相邻的子任务的执行时间，按照优先级的高低依次为每个子任务安排执行时间，执行时间均尽可能早。

粒子的更新公式(6)适应连续变量优化问题，文中为解决非连续变量的非整数优化问题，做了一些优化。主要做法为：将粒子中的每个变量就近取整，因为每个变量的变化范围均有一定的限制，设计一种以限制值为半径的圆形策略，当变量超过该半径时，用梯度下降使变量回到限制范围内。

4.3 MPPSO算法步骤

(1)初始化粒子群，初始化参数，初始化适应度函数；

(2)初始化外部存档集，初始化粒子拥挤度；

(3)进入迭代，利用公式(6)开始更新粒子群，根据帕累托最优理论，将符合条件的粒子存入外部存档集；

(4)对比外部存档集个数，如果数量小于或等于

K

，则进行步骤5，否则进行步骤6；(5)更新未进入外部存档集的粒子，根据帕累托最优理论，继续填充外部存档集，直到数量等于

K

；

(6)如果达到迭代最大值，或者外部存档集不再发生变化，停止更新，进入步骤8，否则进入步骤7；

(7)进入步骤3，直到达到迭代最大值，或者外部存档集不再变换；

(8)结束算法，此时的粒子群为最优集，为边缘云资源调度资源提供参考。

5 实验结果与分析

为了验证实验效果，采取了对比实验，分别选取了资源分配常用的DE算法和PSO算法。利用MATLAB2016a作为实验平台，PC配置为联想启天T5000，16G内存，酷睿i7CPU，Windows10操作系统。边缘云的资源调度会受到很多因素的影响，比如基站的部署方式、用户量、基站所处物理环境等，这里为了便于对比和获得较好的实验效果，假设三个算法条件相同。但对于多目标优化问题来说，无法通过单一指标确定谁优谁劣，因此采取两种指标来对比实验效果，一是在相同用户量和任务量的条件下，边缘云中每个边缘基站的调用频率，二是在数量相同的，且优先级顺序相同的子任务下，观察最优的资源调度程序按照任务优先级顺序执行情况。

部分实验参数见表1。

表1 部分实验参数

续表1

边缘基站的调用频率对比如图1～图3所示。

图1 基站调用次数(MPPSO算法)

图2 基站调用次数(DE算法)

图3 基站调用次数(PSO算法)

综上对比，在相同的条件下，MPPSO算法可使边缘云中的边缘基站调用次数相对均匀，间接证明在MPPSO算法使得边缘云资源得到了合理的调度。而DE和PSO算法中，均有一个基站调用次数过多，这容易使得某个基站运行过载，或有些任务得不到较好执行，或其他邻居基站的资源得不到充分利用。

接下来是子任务执行情况对比，将任务优先级设定为

P

=3，

P

=2和

P

=1，即数值越大，任务优先级越高，输入相同数量级的任务，任务执行情况对比如图4～图6所示。

图4 任务执行情况(MPPSO算法)

图5 任务执行情况(DE算法)

图6 任务执行情况(PSO算法)

综上对比可以看出，MPPSO算法使任务基本是按照任务优先从大至小的顺序执行，且执行的大多数是优先级较高的任务，这不仅可以充分保证优先级高的任务优先执行，还可以保证边缘基站的资源用在关键时刻，而其他非必须卸载至边缘云执行的非高优先级任务则少量卸载至边缘基站执行。DE算法也是基本优先执行高优先级的任务，但是优先级不高的任务也得到了一定量的执行，这使得一些非必须卸载至边缘基站的任务也得到了执行，虽然可以降低本地功耗，相对充分利用边缘云资源，但却缩小了边缘基站的利润空间，增加了任务执行时延，同时还有可能使得一些高优先级任务得不到执行，给用户带来不好的使用体验。PSO算法下的资源分配比较中性，其基本按照任务的数量进行判断是否需要卸载至边缘基站执行，实际生活中，中等优先级占大多数，且对各方面资源要求均不太高，高优先级任务和低优先级任务相对不是很多，可以理解成该算法排斥优先级较高和较低的任务，因此，PSO算法一般适用于小型基站，或用户量不大且对资源要求不高的群体，某种程度讲也是一种资源节约。

总结上述可以得出结论：对于一些大型的边缘计算中心，在用户活跃度较高且复杂高级任务执行数量较多的环境中，MPPSO更加适合。

6 结束语

移动边缘计算有助于实现5G新业务超低时延、高能效和高可靠的高密度连接需求。文中主要研究了边缘云计算中的资源调度问题，将此类问题归类为多目标优化问题，提出了MPPSO算法，利用数据传输速率和任务执行能耗设计了两个适应度函数。同时，基于边缘云资源调度特征，联合用户和边缘基站，设计了一种粒子编码机制，并对传统的粒子演化机制进行了改进，使其适应于非连续整数变量优化问题，并引入了帕累托最优理论，寻找最优资源调度程序。实验和两个在资源分配中的常用算法DE和PSO进行对比，证明MPPSO算法在用户数量较多，且高级复杂任务较多的边缘云中表现更好。下一步，将进一步细化任务分类机制，深入研究更复杂的资源分配问题。