乔楠楠 尤佳莉

(中国科学院声学研究所国家网络新媒体工程技术研究中心 北京 100190)

一种面向网络边缘任务调度问题的多方向粒子群优化算法

乔楠楠 尤佳莉

(中国科学院声学研究所国家网络新媒体工程技术研究中心 北京 100190)

任务调度是云计算及网格计算环境中的重要问题，已有的调度算法往往仅致力于最小化任务的总执行时间而不设置其他约束条件，以致难以实现多种性能指标的同时优化。所提出的面向网络边缘任务调度问题的多方向粒子群优化算法，用于解决并发任务在网络边缘服务节点中的分布式调度问题，调度的目标是在任务执行的资源开销不超过阈值的情况下，最小化任务完成的总时间。该方法与现有的离散粒子群优化算法相比同时降低了任务的总完成时间及资源开销，且在合理预设资源开销上限的情况下，其计算复杂度实现了较大程度优化。仿真表明，所提出的方法比现有的离散粒子群优化算法的任务总完成时间缩短约10.52%～13.23%，资源开销减少约10.32%～13.29%。同时，在合理降低资源开销阈值的情况下，该方法的程序运行时间比现有的粒子群调度方法明显缩短。

任务调度 多方向粒子群优化 最小化完成时间 开销阈值

0 引 言

在Web2.0时代，大规模的任务处理需求开始呈现，例如多媒体特效任务、大数据处理任务等。在这些任务场景下，最常见的用户需求就是实时性需求，也即要求任务能够被快速响应、快速执行、且执行结果能够快速回传给用户，因此，最小化任务完成时间是任务调度问题中最常见的目标。除此之外，任务调度问题考虑的因素还涉及硬件设备功耗、分布式设备负载均衡度等。

云计算[1]通常通过互联网来提供动态易扩展的虚拟化的资源，以往的任务调度策略研究也大多是基于云环境展开。在云计算之后，近年来研究者提出了一些基于网络边缘环境的分布式计算模型。

Zhu等提出一种新的多媒体云计算框架[2]，也即媒体边缘子云(MEC)，将存储、中央处理单元和图形处理单元部署在云边缘位置，以便为各类设备提供分布式并行处理及QoS适配。思科于2011年提出雾计算[3]架构，雾计算是半虚拟化的服务计算架构模型，它更强调网络边缘计算设备的作用。在雾计算架构中，服务节点可能是分散在网络边缘的零散设备，单个服务节点的计算能力可能较弱，然而依托于特有的低延迟、位置感知特性，这些节点可能提供更具实时性的服务。

以上基于网络边缘的分布式计算架构利用网络边缘的低延迟特性，为用户请求提供了实时性响应。本文所讨论的任务调度问题，正是基于以下环境特点：

(1) 所有服务节点均分布于网络边缘的ISP中，用户节点位于其中某个ISP。用户节点及服务节点均具有带宽感知能力，可以对本节点到其他节点的数据传输时延进行预测。

(2) 任务的执行成本采用pay-as-you-go原则进行计算，也即，执行任务所对应的资源开销与实际的资源用量正相关。

1 现有任务调度算法及存在的问题

任务调度问题是NP-hard问题，已有的任务调度算法主要分为两大类，一类是基于局部贪心策略的算法[4]，另一类是启发式的智能搜索方法。

在局部贪心策略方面，Max-Min算法用ECT矩阵表示各个任务在各个机器节点上的完成时间的预测值，且每次优先调度具有最长完成时间的作业。Min-Min算法与Max-Min算法计算方式相似，不同之处在于，Min-Min优先调度具有最短完成时间的作业。Sufferage算法用任务在机器上的最早完成时间与次早完成时间差值的绝对值表示为损失度，并优先调度损失度较大的任务。此类基于局部贪心策略的算法，调度的原则是让当前任务尽可能占用较优的服务器资源，因而可能无法让所有任务公平地占用资源。

Khaled等提出基于遗传算法的任务调度方法[5]，该算法将一个调度方案表示为一个染色体，并利交叉、变异等运算符实现调度方案的进化。遗传算法所实现的方案进化是均匀的进化，其收敛速度较慢。

粒子群优化算法(PSO)[6]由Kenney等在1995年提出。PSO算法从随机解出发，通过适应度函数来评价解的优劣，并通过迭代寻找最优解。相比于遗传算法，PSO通过追随当前搜索到的最优值来寻找全局最优解，规则更为简单，不需要进行交叉和变异等操作。Kenney和Eberhard定义的粒子坐标更新的方式如下所示：

vid=vid+φ(pid-xid)+φ(pgd-xid)

(1)

xid=xid+vid

(2)

其中，d是解空间的一个维度，xi表示粒子群中的第i个粒子，也即第i个解，pi是xi当前在历次迭代中的获得的最优解，也即局部最优解，pg则是整个粒子群当前的全局最优解。

由于PSO致力于在连续解空间中进行搜索，对于解决离散解空间中的问题具有局限性。1997年，Kenney等提出了基于离散二进制解空间的粒子群优化算法[7]，在该算法中，每一个粒子的坐标都是二进制取值。Kenney等对粒子坐标更新的方式进行了重新定义：

if (rand()

(3)

其中S(v) 是Sigmoid函数，如式(4)所示，Sigmoid函数取值与自变量取值呈正相关，其函数值位于区间[0,1]。当S(vid)大于随机数rand()时，粒子xi在d维的坐标取1，否则取0。

(4)

上述方法有效解决了粒子群在二进制解空间中的粒子坐标编码问题，通过该方法得出的粒子坐标均为二进制取值。

在此之后，研究者们基于粒子群及离散粒子群优化算法提出了多种任务调度方法，这些方法的优化思路包括粒子坐标编码[8]、自适应速度调整[9]及局部搜索[10]等。然而现有的基于粒子群优化的任务调度方法仍然存在以下问题：

(1) 现有方法大多沿用经典粒子群中的群体迁移思想，即选取全局最优解和局部最优解作为粒子进化的方向。由于局部最优解仅为当前粒子所取得的历史最优解，并非代表整个群体的最优信息，因此，以局部最优解为导向的进化可能会损失一部分性能；

(2) 现有方法中，随着迭代次数增加，群体中的粒子数目维持恒定，对于在无效解空间中的搜索行为缺少制约条件。

2 多方向粒子群优化算法解决任务调度问题

针对上一节中提到的现有粒子群调度算法存在的问题，本节提出一种多方向粒子群优化算法。所提出的算法主要致力于从以下2个方面实现创新及改进：

(1) 提出一种新的群体迁移方式。在实际的调度问题中，由于一个粒子实际指代调度问题的一个可行解，也即一个任务分配方案，而非自然界中的个体位置信息，因此粒子的移动无须保持自身的原有轨迹。本文提出的粒子群优化算法，从任务总完成时间(makespan)及资源总开销(budget)2个维度分别得出精英解集，以2个精英解集为方向实现粒子迁移，使得粒子群同时向makespan优化和budget优化2个方向移动，提供了一种有效的信息共享方法。

(2) 提出基于模糊集合的粒子淘汰机制。该算法制定了基于模糊集合的适应度函数，并根据粒子适应度的优劣进行粒子淘汰，避免了在无效解空间的搜索行为，在一定条件下，可降低程序的计算复杂度。

2.1 问题假设及目标

假设用户发起N个任务{T1,T2,…,TN}，位于网络边缘ISP中的M个服务节点{S1,S2,…,SM}提供任务响应及处理。该调度问题基于以下假设：

(1) 每个任务可以被任一服务节点执行；

(2) 每个服务节点在同一时刻只能处理1个任务；

(3) 每个服务节点处理单位大小的源文件所需的时间是已知的；

(4) 每个服务节点在工作状态下单位时间内的资源开销是已知的；

(5) 同一个ISP内部的多个服务节点之间的数据传输造成的资源开销可忽略不计，跨ISP传输单位大小文件造成的资源开销是已知的；

(6) 同一个ISP内部的多个服务节点之间的数据传输速率大于不同ISP之间的数据传输速率。

基于以上假设，调度问题的一个可行解可表示为x=[x(1),x(2),…,x(N)]，其中x(i)为第i个任务对应的服务节点ID。该调度问题的目标为：寻找一个任务-服务节点分配矩阵，在任务执行的总开销不超过预设上限的前提下，最小化任务的总完成时间。

2.2 性能指标计算

根据主流的云计算平台如AmazonEC2提供的计费机制，用户因使用弹性资源而支付的费用主要包含两方面，一方面是占用虚拟机的计算资源及存储资源所带来的开销，另一方面开销则来自数据传输费用。在虚拟机资源计费方面，为适应不同使用场景下的用户需求，Amazon制定了3种可选使用方式，也即按需使用型实例、预留型实例及即时型实例；在数据传输计费方面，数据在同一可用区域之内传输不计费，在不同的区域之间视InternetData计费。

在本文所涉及的任务执行成本计算原则上，为详细分析不同任务调度方法所对应的任务执行开销，参考Amazon制定的按需使用计费方式，假设单个服务节点的计算成本正比于该节点上任务的完成用时。除此之外，用户还需支付其向服务节点传输任务源文件所造成的数据传输费用，此项费用正比于跨区域传输的实际数据量。

基于以上原则，用ecti,j表示任务Ti在服务节点Sj上的预测完成时间，bi,j表示Ti在机器Sj上的执行开销，则ecti,j和bi,j的计算方式如式(5)-式(8)所示：

eti,j=ifsi/mipsj

(5)

sti,j=max(at,itj)+ttr(u,j,ifsi)

(6)

ecti,j=sti,j+eti,j

(7)

bi,j=bpsj×eti,j+btr(u,j,ifsi)

(8)

其中，eti,j为任务Ti在服务节点Sj上的预测执行用时，ifsi为Ti的源文件大小，mipsj为节点Sj单位时间可处理的源文件大小，sti,j为Ti在Sj上最早开始时间，at为批量任务的到达时间，itj为Sj的最早空闲时间，bpsj为Sj在工作状态下单位时间内的运行开销，该取值与Sj的计算能力也即单位时间内的文件处理能力正相关。ttr(u,j,ifsi)为从用户节点到服务节点Sj传输大小为ifsi的文件所需时间，令用户节点u到服务节点Sj的传输速率为bwu,j，则ttr(u,j,ifsi)的计算方式如式(9)所示。btr(u,j,ifsi)为从用户节点u到Sj传输ifsi大小文件所需网络资源开销，当u与Sj属于同一区域ISP时，该项取值为0，否则，令跨区域传输单位数据量所需的网络资源开销为ξ，则btr(u,j,ifsi)计算方式如式(10)所示。

ttr(u,j,ifsi)=ifsi/bwu,j

(9)

btr(u,j,ifsi)=ξ×ifsi

(10)

对于已知的任务集合{T1,T2,…,TN}及服务节点集合{S1,S2,…,SM}，若存在调度问题的一个可行解x=[x(1),x(2),…,x(N)]，则该解对应的任务总完成时间makespan(x)及总开销budget(x)计算方式如下：

(1) 将makespan(x)及budget(x)赋值为0；

(2) 对于每一个任务Ti，执行步骤(3)-步骤(5)；

(3) 根据式(3)计算ecti,x(i)；

(4) 根据式(4)计算bi,x(i)，更新budget(x)的值为budget(x)+bi,x(i)；

(5) 更新服务节点Sx(i)的最早空闲时间；

2.3 粒子群初始化

调度问题的一个可行解称为一个粒子，在初始化阶段，若种群初始规模设置为L，则生成L个随机粒子x1,x2,…,xL。其中，每一个粒子xi为N维向量，可表示为x=[xi(1),xi(2),…,xi(N)]，其中第j维度坐标值xi(j)为第j个任务对应的服务节点ID。

2.4 适应度函数

由于该调度问题的优化目标是在任务执行的总开销不超过预定阈值b+的情况下，最小化任务的总完成时间，因此设定粒子的适应度值f(x)与其对应的任务总完成时间makespan(x)负相关，即，一个可行解对应的makespan(x)值越大，其适应度越低。同时，对于执行开销超过阈值的解，对其适应度取值加以限制。

设定任务执行开销的阈值b+和准阈值b-(b-b+，则b属于A的概率为0，也即绝对不属于A，当b-

(11)

如前所述，任务调度的目标是在任务执行的总开销不超过既定阈值的情况下，最小化任务的总完成时间。因此，适应度函数设定的原则为：当粒子对应的调度方案总执行开销不超过准阈值b-时，其适应度值与任务的总完成时间成反比，若其总开销超过b-，则粒子适应度以一定的风险取0，若其总开销超过阈值b+，则其适应度以100%的概率取0。适应度函数定义如式(12)所示，其中A为式(11)所定义的模糊集合。

(12)

2.5 多方向粒子群进化

2.5.1 基于精英解集的多方向粒子移动

由于一个粒子实际指代调度问题的一个可行解，也即一个任务分配方案，而非自然界中的个体位置信息，因此粒子的移动无须保持自身的原有轨迹。在每一轮迭代中，为保证领导者提供优质的信息，只选取全局最优解作为种群的领导者。

根据2.2节所述的成本计算原则，可以得出makespan和budget两个性能指标之间的基本关联：因为节点单位时间内的运行成本与其计算能力正相关，因此，具有较优计算资源的节点在快速处理任务的同时也造成更多资源开销。但是，makespan与budget两项指标又在一定程度上存在一致性，由于一个区域ISP内部的数据传输不计成本，且传输速率大于不同ISP之间的数据传输速率，因此，在一定程度上减少跨区域的数据传输，可能实现makespan和budget的同时优化。

(1) 将当前粒子群中的所有粒子按照makespan值进行升序排序，并将前K个粒子存放入精英解集Archive1；

(2) 将所有粒子按budget值进行升序排序，并将前K个粒子存放入精英解集Archive2；

(13)

(14)

β=[prob1,prob2,1-prob1-prob2]

(15)

2.5.2 基于模糊集合的粒子淘汰

为了控制粒子的budget值，使其满足约束条件，在每一轮迭代中淘汰适应度为0的粒子，从而使群体中保留的粒子均符合约束条件。当满足下列条件之一时，迭代终止。

(1) 迭代次数超过预设值Max(Iters)

(2) 剩余粒子数目小于预设值Min(Population)

粒子群进化算法表示如下所示：

Initial the swarm with x1,x2,…,xL;

Setthebudgetconstraintb+andb-;

Settheprobabilityprob1andprob2;

t←1;

whiletheterminalconditionisnotmetdo

GettheelitesetArchive1andArchive2;

fort←1toLdo

endfor

fort←1toLdo

endif

endfor

L←thecurrentpopulationoftheswarm;

t←t+1;

endwhile;

上述方法在每一轮迭代中，淘汰适应度为0的解，即，以100%的概率淘汰budget值超过b+的解，并以一定概率淘汰budget值超过b-的解，从而实现对于群体budget的整体控制。

3 仿真测试

(16)

(17)

(18)

上述方法提供了适用于本文调度问题的离散坐标编码方式，从而提供了重现的可能性。同时，该方法与本文具有相似的优化目标，也即致力于优化并发任务的总完成时间，因此本节对上述方法进行重现，并与本文提出的多方向粒子群优化方法进行比较，着重分析任务处理的总时间(makespan)、资源开销(budget)及程序运行的时间(runtime)。

3.1 测试环境

基于Windows平台Matlab7.1工具进行了仿真测试，处理器型号为Inteli5-4570，CPU频率为3.2GHz，可用内存为3.43GB。

3.2 任务规模及服务节点设置

提供服务的14个虚拟机节点VM1-VM14分布在ISP1-ISP3中。CP表示虚拟机节点计算能力，也即节点在单位时间内处理的文件规模(KB/s)，BPS表示节点在工作状态下每秒的开销(cent/s)。发起任务请求的客户端建立在ISP2中的VM9节点上，在测试初始化时发起15个任务，任务的源文件规模为32～64MB。如表1所示。

表1 服务节点计算能力及开销设置

假设一个ISP内部多个节点之间的文件传输代价可忽略，跨ISP的文件传输开销与文件大小呈正相关，具体设置如表2所示。同一个ISP内各虚拟机之间传输速率为1.25Mbps，不同ISP的虚拟机之间传输速率为10Mbps。

表2 各ISP之间文件传输开销设置

3.3 仿真结果及分析

在如下所示2个实例中，精英解集Archive1和Archive2的元素个数均设置为K=5，开销“准阈值”b-均比b+减少10cent，即b+-b-=10，其余各个参数取值设置如表3所示。

表3 仿真参数设置

在以上2个实例中，针对粒子群初始化规模为200、500、1 000三种情况进行了仿真，且随着迭代次数的改变，共得出9个数据点P1-P9，如表4所示。

表4 初始化粒子数目及迭代次数设置

在图1、图2及图3中，实例1对应的数据曲线标记为MDPSO-1及DPSO-1，实例2对应的数据曲线标记为MDPSO-2及DPSO-2，横坐标表示9个数据点P1-P9，仿真结果如下所示。

图1 Makespan仿真结果

图2 Budget仿真结果

图3 Runtime仿真结果

在实例1中，就makespan而言，如图1所示，MDPSO算法的平均makespan为1 275.2s，相比于DPSO的1 469.7s平均减少 13.23%。就budget而言，如图2所示，实例1受到阈值b+=150的限制，MDPSO算法的平均budget为144.2cent，相比于DPSO的160.8cent平均减少10.32%。

在实例2中，MDPSO平均实现了1297.5s的makespan，相比于DPSO的1 450.1s降低了10.52%，由于设置了更低的b+值，MDPSO算法实现了更低的budget，MDPSO的budget为138.3cent，相比于DPSO的159.5cent降低了13.29%。

就runtime而言，如图3所示，由于MDPSO算法涉及全局较优解集合的提取，该步骤具有较高的计算复杂度，在实例1中，随着粒子数目及迭代次数增加，其runtime逐渐高于DPSO。但在实例2中MDPSO通过合理降低b+值，也即降低budget的上限，可以在每一轮迭代中促使更多无效的解被淘汰，因此粒子的数目明显减少，在后续的迭代中计算复杂度逐渐降低，runtime明显低于DPSO。

仿真表明，本文提出的多方向粒子群进化方法具有较好的信息共享能力，通过makespan及budget两个维度分别获得全局最优解，实现一种多方向粒子迁移，并使全局最优解的优质的信息以较高的概率保存至新一代粒子群。同时，在适当降低开销阈值的情况下，算法的计算复杂度得以降低，实现较短的程序运行时间。

4 结 语

本文提出了一种面向网络边缘任务调度问题的多方向粒子群优化算法，该方法利用网络边缘ISP中的服务节点为终端用户提交的任务请求提供实时响应，致力于在任务执行的总开销不超过阈值的前提下，最小化所有任务的总完成时间。一方面，该算法设计了基于精英解集的粒子迁移方法，通过2个全局最优解实现高效的信息共享，使得解空间中的粒子在makespan及budget两个维度实现同时优化。另一方面，该算法采用基于模糊集合的粒子淘汰方法，在一定条件下降低了算法的计算复杂度。

仿真表明，所提出基于精英解集的粒子迁移方法具有较好的信息共享能力，能够实现多个目标的同时优化，比现有的离散粒子群优化算法实现的任务总完成时间缩短约10.52%～13.23%，资源开销减少约10.32%～13.29%。同时，基于模糊集合的粒子淘汰方法，在每一轮迭代中淘汰适应度极低的粒子，在合适的开销阈值限制下，该方法能够极大地缩短程序运行的总时间。

[1]ArmbrustM,FoxA,GriffithR,etal.Aviewofcloudcomputing[J].CommunicationsoftheACM,2010,53(4):50-58.

[2]ZhuW,LuoC,WangJ,etal.MultimediaCloudComputing[J].IEEESignalProcessingMagazine,2011,28(3):59-69.

[3]BonomiF,MilitoR,ZhuJ,etal.FogComputinganditsRoleintheInternetofThings[C]//ProceedingsofthefirsteditionoftheMCCWorkshoponMobileCloudComputing.ACM,2012:13-16.

[4]TabakEK,CambazogluBB,AykanatC.ImprovingthePerformanceofIndependentTaskAssignmentHeuristicsMinMin,MaxMinandSufferage[J].IEEETransactionsonParallelandDistributedSystems,2014,25(5):1244-1256.

[5]KhaledAKM,TalukderA,KirleyM,etal.MultiobjectivedifferentialevolutionforschedulingworkflowapplicationsonglobalGrids[J].ConcurrencyandComputation:Practice&Experience,2009,21(13):1742-1756.

[6]KennedyJ,EberhartR.Particleswarmoptimization[C]//IEEEInternationalConferenceonNeuralNetworks,1995:1942-1948.

[7]KennedyJ,EberhartRC.Adiscretebinaryversionoftheparticleswarmalgorithm[C]//IEEEInternationalConferenceonSystems,Man,andCybernetics.IEEE,1997:4104-4108.

[8]LiaoCJ,TsengCT,LuarnP.Adiscreteversionofparticleswarmoptimizationforflowshopschedulingproblems[J].Computers&OperationsResearch,2007,34(10):3099-3111.

[9]ZuoX,ZhangG,TanW.Self-AdaptiveLearningPSO-BasedDeadlineConstrainedTaskSchedulingforHybridIaaSCloud[J].IEEETransactionsonAutomationScienceandEngineering,2014,11(2):564-573.

[10]MoslehiG,MahnamM.AParetoapproachtomulti-objectiveflexiblejob-shopschedulingproblemusingparticleswarmoptimizationandlocalsearch[J].InternationalJournalofProductionEconomics,2011,129(1):14-22.

A MULTI-DIRECTIONAL PARTICLE SWARM OPTIMIZATION ALGORITHM FOR NETWORK EDGE TASK SCHEDULING

Qiao Nannan You Jiali

(NationalNetworkNewMediaEngineeringResearchCenter,InstituteofAcoustics,ChineseAcademyofSciences,Beijing100190,China)

Task scheduling is an important problem in cloud computing and grid computing environments. Existing scheduling algorithms are often only dedicated to minimizing the total execution time of tasks without setting other constraints, making it difficult to optimize multiple performance metrics simultaneously. The proposed multi-directional particle swarm optimization algorithm for network edge task scheduling problem solves the distributed scheduling problem of concurrent tasks in network edge service nodes. The goal of scheduling is to minimize the total time of task completion in the case that the resource cost of task execution less than the threshold. Compared with the existing discrete particle swarm optimization algorithm, this method reduces the total task completion time and resource cost, and achieves a large degree of optimization of its computational complexity in the case of a reasonable preset resource overhead. The simulation results show that compared with the existing discrete particle swarm optimization algorithm, this method can reduce the total task completion time by about 10.52%～13.23% and the resource cost by 10.32% ～13.29%. Meanwhile, the running time of this method is significantly shorter than that of the existing discrete particle swarm optimization algorithm in the case of a reasonable reduction of resource overhead threshold.

Task scheduling Multi-direction particle swarm optimization Minimal makespan Overhead threshold

2016-03-16。中国科学院战略先导技术专项基金(XDA06040501)。乔楠楠，硕士生，主研领域：优化算法，多媒体服务。尤佳莉，副研究员。

TP3

A

10.3969/j.issn.1000-386x.2017.04.053