一种面向边缘计算QoE的服务组合及调度方法
2019-07-09简琤峰裘科意张美玉
简琤峰,裘科意,张美玉
(浙江工业大学 计算机学院 数字媒体技术研究所,杭州 310023)
1 引 言
全球物联网和无线网络的快速发展推动了移动终端和“边缘计算”的发展,使得网络边缘设备的数量迅速增加,从而产生了海量的实时数据.以云计算模型为核心的集中式大数据处理方式,通过将大量的资源集中统一进行管理,并根据用户的请求动态分配,由于其良好的商业模式得到蓬勃发展.但完全集中化的模式由于在数据传输过程中网络延迟,处理过程中的计算能力限制,能量消耗等缺点,其关键技术无法满足强实时性要求以及大数据量的交互与处理[1-3].在这样的大环境下,边缘计算应运而生,它是云计算之后回归的新兴的计算范例.通过将应用、数据和服务从集中式节点推向网络边缘,在网络边缘处理数据,边缘计算能够有效缩短响应时间,提高处理效率并降低网络压力,从而满足实时性要求.传统的云计算调度往往只从技术角度——服务质量(QoS)来体现性能指标,而在边缘计算中,我们同样需要重视用户的体验质量(QoE)[4-8].如何在确保网络边缘服务质量的(QoS)、提高用户的体验质量(QoE)的前提下对资源进行合理的调度是一个值得研究的课题[9-11].
在边缘计算资源协同与调度问题上,已有一些新兴的算法与研究.Yu等人[12]提出了一种联合调度算法,协调地分配无线和计算资源,能接纳更多请求,节能效果显著.Sardellitti等人[13]将MIMO多单元系统中的多个移动用户(MU)计算卸载到通用云服务器的问题转化为无线电资源和计算资源的联合优化问题,将总体用户的能耗降至最低,同时满足延迟约束,并提出了一种基于新颖的连续凸近似技术的迭代算法,收敛到原始非凸问题的局部最优解.Lin等人[14]提出了一种用于MCC任务调度问题的新算法,以在应用完成时间的硬约束下最小化移动设备中的应用的总能量消耗.Kiani等人[15]提出了两种时间尺度机制来将计算和通信资源分配给MU,制定了二元线性规划(BLP),旨在最大化服务提供商的利润和带宽分配的凸优化问题,设计了启发式算法来解决BLP问题,并针对带宽分配问题提出了集中式解决方案.但他们均未考虑在满足用户体验QoE的前提下对网络边缘资源进行合理的调度.
针对上述问题,本文采用了一种两阶段的调度模型[16],此模型在保证QoS约束的前提下,根据用户请求的QoE,筛选有效资源,并进行调度,使得整个服务执行的时间开销达到最小,从而满足实时性要求,本质上可规约成一个多目标优化问题.模型的第一阶段将用户QoE映射到QoS参数指标,并为每个服务请求选择满足其QoS的最优服务组合;第二阶段为调度阶段,利用提出的改进的天牛须粒子群算法(BAPSO)求解此问题.此算法将单个个体的天牛须搜索算法拓展至群体,在天牛开始觅食时加入天牛个体对自身历史最优位置的记忆以及群体历史最优位置记忆,并在觅食过程中引入动态因子和二阶振荡机制,丰富了天牛群体在移动过程中的搜寻信息,较好地避免了群体陷入局部极值问题.通过matlab仿真证明将该算法应用于此能够高效地解决大规模的边缘服务资源的调度和分配问题.
2 两阶段模型描述
2.1 服务组合结构
以用户的服务请求为驱动的资源调度优化问题可以理解为:如何在满足用户QoE的前提下最好地将任务分配给边缘节点.我们将流处理系统抽象为一个主从结构,边缘服务器是接收用户请求和分配任务的主节点,边缘节点是执行任务的从节点.在了解边缘节点可提供的资源及用户的服务请求信息后,将其做最优化最有效的“请求-服务”匹配,并且完成总时间最短这一高效性的要求.
图1 边缘服务组合结构Fig.1 Edge service composition structure
2.2 QoE与QoS的映射
相比传统云计算侧重于服务质量(QoS),边缘计算衡量业务品质的标准更侧重于用户的体验质量(Quality of Experience,QoE).相对于QoS关心以性能为中心的技术层面,QoE则更加关注用户使用业务的感受,实现以用户为中心的管理,它强调从终端用户的角度来反映QoS.因此需要解决QoE与QoS之间的映射方法.本文采用IQoE2QoS算法[17],使用多指标模糊判定理论,实现用户体验质量(QoE)到服务质量(QoS)的映射.
本文采用MOS(Mean Opinion Score)来评价用户的感知质量[18].在IQoE2QoS算法,首先利用指标统计图划分指标的范围,并离散化指标得到学习集,借助此学习集计算各指标间的权重关系.设指标集为I={I1,I2,…,In},每个指标离散化后得,Ii={ai1,ai2,…,ain}.平均互信息量计算如下:
I(S,Ii)=H(S)-S(S|Ii)
(1)
归一化后得到指标权重:
(2)
计算当前所有模式应属于的服务等级,若包含在已有集合中,则判定;若不存在,则对未知模式进行提前模糊归类.完成上述步骤后更新现有知识表.
IQoE2QoS算法采用机器学习的方法实现从QoS到QoE的映射,采用多指标模糊评价理论,得到QoE到QoS的反映射,并结合信息熵得到各指标同分类信息的互信息量,从而确定各个指标的权重比值.
根据上述方法得到的权重比值,子任务Ti使用对应服务资源Vi的各个QoS属性度量值的总和如下所示:
(3)
(4)
此外,我们需要将不同的QoS属性进行规约,即将不同的QoS属性转化至相同的度量单位,并解决正向和逆向QoS问题.本文中都转换为度量[1,50]的数值,考虑的逆向QoS属性是时间和成本,正向QoS属性是可靠性与可用性.QoS的计算公式如下,其中max和min是相应QoS属性的最大值和最小值.
(5)
2.3 调度时间开销
针对批量服务请求的调度策略主要的优化目标是在满足使用最优服务组合的条件下减少服务请求任务流执行的总时间.此外,本文还考虑服务切换的时间开销.将节点提供的服务之间的切换时间记为矩阵logn×n,则logij代表虚拟服务点i到虚拟服务点j的服务切换时间开销.
数组TimeTablem×n表示m个服务请求和n个服务点的最优边缘服务组合,记录了每个服务请求的各个子请求在每个服务点上的时间开销.其中,TimeTableij表示第j个服务节点对应的边缘服务sj完成第i号服务请求对应的子请求所花费的时间开销.
在服务切换时间上,我们需要考虑以下两种情况:
(6)
(7)
综上可知,面向批量服务请求的边缘服务调度问题可以描述为:在边缘服务资源有限的情况下,确定调度边缘服务执行服务请求的顺序,使得服务请求整体执行时间最少.将为各个服务请求选择出的最优服务组合的响应时间属性的度量值存储在TimeTableij中,并将其采用作为输入源进行整个过程的最优化调度.
3 改进的天牛须粒子群算法
3.1 算法简介
天牛须搜索(beetle antennae search,BAS)算法[19]和传统的启发式算法相比具有调节参数少、运算量小等优点,但其在高维情况下表现较差,且也容易陷入局部最优.因此,本文以粒子群算法原理为基础,在算法中加入天牛觅食的特性,将单个个体的天牛须算法拓展成群体算法,并使每个个体拥有对自身历史位置的最优记忆,使群体拥有群体历史最优位置记忆.在此基础上,引入动态因子和二阶振荡机制来调整粒子对两个最优记忆的学习因子,优化群体觅食时的参数机制.
与单个体的天牛须算法相比,新算法的群体性丰富了天牛移动时位置的多样性,弥补了单个体容易陷入局部最优的缺陷,提高了算法的全局搜索能力.天牛在迭代的每一步自身都有一个指向最优位置的“速度”,并根据对自身最优位置的记忆及对群体最优位置的记忆进行下一步位置的判断.与普通粒子群算法的位置更新方式相比,本文算法更容易找到最优解,求解能力更强,所求解质量更高.
3.2 天牛须粒子设计
基于以上特性,本文的天牛须粒子设计如下:
1)粒子拥有左右两须,且位于质心两侧.假设粒子在第t次迭代时质心的坐标为xt,则其左右两须的坐标分别为:
(8)
判断左右两须的气味强度大小,并据此计算下一步粒子的质心位置:
(9)
其中,δt表示第t次迭代时的步长,sign()为符号函数.
(10)
其中,rands()表示随机函数,k表示维度.
3)每个粒子拥有自身历史最优记忆Pbesti={Pbi_1,Pbi_2…Pbi_m},群体拥有全局最优记忆gbest={gb1,gb2,…,gbm}.
在调度过程中,将一个服务请求进行逻辑划分后得到m个子请求.此时,服务请求执行的顺序即对应天牛须粒子群算法中一个m维的粒子.每个粒子的位置由一个m维向量xi={xi_1,xi_2…xi_m}来表示,xi_j表示个体Pi第j维方向的位置,在服务调度过程中对应于执行边缘服务请求Tj的顺序编号.粒子与服务请求的映射关系如图2所示.
粒子621435⇩请求执行次序T1T2T3T4T5T6执行次序编号6rd2st1nd4th3th5th
图2 粒子个体与服务请求的映射关系
Fig.2 Mapping of particles to service requests
3.3 适应度函数
适应度函数在解决具体问题时具有极其重要的作用,它是具体问题的数学模型在算法中的体现.不同的粒子可以看做是不同的解,而将不同的解代入适应度函数得出对应的适应度函数值,将其与之前的全局最优值对比或者更新.本文处理批量服务请求的模型中,StartTimem×n与EndTimem×n分别表示开始时间矩阵和结束时间矩阵,m和n表示提供的边缘服务数目以及边缘服务请求的数目.矩阵PT表示各个服务请求对应的最优边缘服务的具体执行时间.PTij表示第j个服务点对应的边缘服务sj完成第i号服务请求对应的子请求所花费的时间.
适应度函数的输入包括:1)边缘服务资源的数目；2)边缘服务请求的数目；3)基于QoS的边缘服务组合选择得出的各个服务请求对应的最优服务组合的执行时间矩阵；4)代表解的群体Pi.综上,一个m维粒子Pi={Pi_1,Pi_2…Pi_m}对应的适应度函数运算过程如下:
fitness(Pi,n,m,pt)
fork=1:n
forl=1:m
ifpt(l,Pi_k)！=0
indexLast1=findlastProNotZero(pt,l,Pi_k);%上一个执行时间不为0的子请求.
StartTime(l,k)=max(EndTime(l-1,k)+log(indexLast1,l),EndTime(l,k-1));
EndTime(l,k)=StartTime(l,k)+pt(l,Pi_k);
else
EndTime(l,k)=EndTime(l-1,k);
EndTime(l,k)=EndTime(l,k);
end
end
fitness(Pi,n,m,pt)=EndTime(k,l)
3.4 天牛须粒子群算法迭代过程
首先,将单个个体拓展为群体,改进后群体的位置更新公式如下:
(11)
如果令：
(12)
则公式(11)可变型为:
(13)
针对天牛须算法和粒子群算法容易陷入局部最优等问题,为加快收敛速度并加强算法的全局搜索能力,在前期研究的基础上[20],利用二阶振荡方法对公式(12)进行改进,优化群体觅食时的参数机制,改进后的速度更新公式为:
(14)
其中β1=c1r1,β2=c2r2.
(15)
(16)
其中,r3,r4为(0,1)范围内的随机数.此外,添加权重因子α1与α2控制三角变换对学习因子c1和c2的影响.
(17)
(18)
综上所述本文的天牛须粒子群算法流程如下:
Input:Gmax,c1,c2,N;
Output:gbest;
t=0.initialise the population;
initialise related parameters;
for i=1:N
pbesti=xi
end for
gbest=argmaxxifitness(xi)
while(t update c1,c2 as(17)and(18) for i=1:N update viand xias(12)-(14) if fitness(xi)>fitness(pbseti) pbesti=xi end if end for gbest=argmaxfitness(pbest) end while 首次迭代时随机生成代表一组解的个体Pi,将其位置作为个体的历史最优并初始化全局最优.随着迭代的进行,根据适应度函数计算每个个体的适应度值并实时更新两个最优值.当达到最大迭代次数后,结束算法,最后一个服务请求执行的结束时间就是服务请求执行的总时间. 为了验证本文提出的改进的天牛须粒子群算法(BAPSO)在边缘计算资源协同与调度模型中的有效性,在matlab上进行仿真实验.主要运用本文提出的未加入二阶振荡的天牛须粒子群算法(MBAS)和二阶振荡天牛须粒子群算法(BAPSO)以及二阶振荡粒子群算法(MPSO)分别进行对比,为了减少偶然情况对实验结果的影响,本文在不同问题规模下对相应的算法进行对比,并对每种情况重复进行100次模拟实验,取平均值和最小值,以此来减小实验误差. 实验中,假设每个子服务的执行时间和服务切换时间范围是[1,60],单位分钟.设二阶振荡粒子群算法的惯性因子的值为0.8,天牛须算法的初始步长为3.0,两须间距离为0.8.为了对比不同的服务请求数目和服务总数情况下的服务请求执行的总时间,我们将实验分成三个对照组,每组的边缘服务总数分别是10,20和30.表1-表3是三个对比组的模拟仿真结果, 分别展示了三种算法仿真得到的总时间开销的平均值和最小值.其中,n代表边缘服务请求数目,m代表边缘服务总数. 表1 m=10时不同服务请求数目下3种算法的对比 MPSOMBASBAPSOnmminavgminavgminavg3010158116151542157815371575401018861909186419441853190550102233225521872233215722116010246224942484249924432493701027652811273927712718276180103089311330753094300430729010340934623385344233563436 表2 m=20时不同服务请求数目下3种算法的对比 MPSOMBASBAPSOnmminavgminavgminavg50202914293628422918283028736020313131533085314830373091702034843512346735183458349280204006403939514001389939779020435143844254436742524336100204636469446174691460246881102049464998492550064863494912020535754055281537052535338 表1-表3是二阶振荡粒子群算法和本文提出的两个新算法解决面向批量服务请求的调度问题得到的总时间开销情况,是不同服务请求数目和不同边缘服务总数情况下的实验仿真结果.从表中可以看出,将天牛须算法拓展成群体算法(MBAS)后,求得的总时间开销明显小于粒子群算法,算法效率得到提升,求解质量得到提高.再对算法加入二阶振荡机制,可以看出,相对于前两种算法,BAPSO在不同规模的服务请求数和边缘服务总数情况下求得的时间开销均小于前两种算法,边缘服务请求队列总的执行效率得到进一步提升,且由于采用最优服务组合作为服务调度的输入源,服务请求执行的质量也得到了提升. 表3 m=30时不同服务请求数目下3种算法的对比 MPSOMBASBAPSOnmminavgminavgminavg503035683591349035453472353160303813382237713802370837437030442244444374440243384378803046564682459946624559468390305084511050635101504450681003054025425535753795265535111030583658925772584457475822 此外,本文的模型还加入了服务切换时间,随着服务请求数的增加,问题规模也在逐渐增加.本文提出改进天牛须粒子群调度算法能够在保持收敛速度的情况下,保持解的质量和稳定性,并具有较强的避免陷入局部最优的能力,说明其能适应大规模的多目标优化问题的求解.篇幅限制,此处随机选取在边缘服务请求总数分别为50,70,100三种情况下,三种算法分别求得的总生产时间随迭代次数的变化趋势如图3-图5所示. 图3 请求数为50时三种算法的对比Fig.3 Comparison of three algorithms when the number of requests is 50 在图3中,BAPSO展现出较好的全局探索能力,在快速收敛的前提下较大地提高了解的质量,缩短了调度时的总时间开销.分析图4可知,BAPSO在迭代后期陷入局部最优的情况下及时作出调整,跳出了局部最优.在图5中,在问题规模较大的情况下,粒子群算法较早陷入了局部最优,改进后的MBAS在经过一段时间的停滞后虽及时跳出了局部最优,但进一步改进后的BAPSO算法展现出了更强的求解能力,不断搜寻更优解,并快速收敛. 图4 请求数为70时三种算法的的对比Fig.4 Comparison of three algorithms when the number of requests is 70 此外,进行多次实验,模拟了不同规模下执行BAPSO算法求解边缘服务中多目标问题所需运算时间,重复多次得出平均值,实验结果如表4所示. 由表4可知,随着问题规模的增大,BAPSO的运算时间基本呈线性增加,这保证了算法在求解过程中不会由于问题规模的增大而出现运算时间骤然增大的现象, 而是一个平稳的增加过程.当子任务数在250以内时,BAPSO算法基本能在8秒内找到最优解.子任务数量在500以内时,BAPSO算法的运算时间基本在16秒以内.由实验结果可知,从算法的计算时间开销来看,随着问题规模的增加,BAPSO算法也适用于求解边缘计算下大规模的资源协同与调度问题. 图5 请求数为100时三种算法的的对比Fig.5 Comparison of three algorithms when the number of requests is 100 表4 不同问题规模下的算法的运算时间开销 服务请求数边缘服务总数运算时间(/s)150157.0728250257.96743003010.52733503511.34004004012.59374504513.84535005015.15075505516.45986006017.8206 对比粒子群等算法,本文算法不仅保持了个体的独立性和种群的多样性,提升了最优解的质量.BAPSO算法在单个体的天牛须搜索算法的基础上拓展个体数量,引入了二阶振荡环节及对历史最优位置的记忆,不仅能增强全局搜索能力,丰富种群的多样性,在迭代过程中出现停滞时,BAPSO可以通过调整自身方向及速度来及时调整整个群体的移动,扩展种群位置的多样性和优良性,跳出局部最优.通过实验可以证明,该算法能够在保证用户感知的前提下高效地解决大规模的边缘调度问题,具有较好的应用价值.此外,随着问题规模的增加,算法的执行时间基本呈线性增长,实验结果表明算法是高效且可应用的. 在保证用户体验质量(QoE)的前提下求解边缘环境下资源协同及调度问题本质上是一个多目标优化问题,本文采用一种改进天牛须粒子群算法解决该问题.算法将单个个体的天牛须算法拓展至群体,并引入动态因子和二阶振荡机制等改进群体觅食的位置更新时的动态参数机制,丰富了群体移动时的位置多样性,提升了算法的效率和算法的全局搜索能力.实验在不同问题规模下运用本文最初改进的天牛须粒子群算法(MBAS)及加入二阶振荡后的BAPSO算法与二阶振荡粒子群算法(MPSO)分别进行对比,说明了BAPSO算法在保证用户体验质量(QoE)的前提下能一定程度上提高求解效率及解的质量,并适应较大规模的问题求解,具有一定的实际应用价值.4 实验仿真和结果分析
Table 1 Comparison of three algorithms for different edge service requests when m=10
Table 2 Comparison of three algorithms for different edge service requests when m=20
Table 3 Comparison of three algorithms for different edge
service requests when m=30
Table 4 Operation time overhead under different problem scales
5 结 论
