一种数据驱动的边缘响应时间优化方法转让专利
申请号 : CN201911030918.X
文献号 : CN110972147B
文献日 : 2021-05-25
发明人 : 魏同权 , 张润泽
申请人 : 华东师范大学
摘要 :
权利要求 :
1.一种数据驱动的边缘响应时间优化方法,其特征在于采用异构边缘服务器计算离线任务到达率的最优离线解,以及基于移动性感知博弈论的方法,计算在基站的任务到达率有波动时的最优解,优化系统的预期响应时间和移动用户的响应时间公平性,其具体优化包括以下步骤:
步骤1:定义云计算系统中的用户、基站、云服务器和边缘服务器,以及基站与服务器的拓扑关系和基站与系统的预期响应时间;
步骤2:离线阶段,利用整数线性规划计算离线任务到达率的最优离线解;
步骤3:当运行时所有基站的任务到达率没有波动时,直接利用上述步骤2的方案;否则,使用启发式算法,以重新确定具有改变的任务到达率的基站的最佳边缘/云服务器;
步骤4:在线阶段,通过转换为凸优化问题来解决合作博弈问题,计算在基站的任务到达率有波动时的最优解;
步骤5:分配结束;
所述步骤1的实现过程按下述步骤进行:步骤A1:表示出移动边缘云计算系统中K个移动用户:U={U1,U2,...,UK};M个基站:B={B1,B2,...,BM};N个边缘服务器SE={S1,S2,...,SN}以及一个云服务器S0,令S={S0,SE}是由云服务器和边缘服务器集组成的服务器集;
步骤A2:满足约束任何基站Bm∈B(1≤m≤M)不允许同时连接到两个不同的边缘/云服务器Si∈S和Sj∈S(0≤i,j≤N,i≠j),用无向图G=(V,E)表示M个基站和(N+1)和边缘/云服务器的拓扑,其中集合V表示M个基站和云服务器S0 的固定放置位置的集合,以及N个边缘服务器的可能放置位置;集合E表示基站和边缘/云服务器之间的通信链路集;
步骤A3:构建基站Bm响应时间模型:(1)
通信延迟W m,n由下述a式定义:(2)
任务执行延迟W m,n由下述b式定义:基站Bm预期响应时间Wm由下述c式定义:系统的预期响应时间 由下述d式定义:所述步骤2的实现过程按下述步骤进行:步骤B1:最小化整个系统和各个基站的预期响应时间的基站分配策略,并如下定义Pi,j和Am,n:
以整个系统的角度来看,性能函数由A3步骤中的预期响应时间 表征;从各个基站的角度来看,性能函数可用预期响应时间{W1,W2,…,WM}的标准偏差 描述,并由下述e式定义:
其中,标准偏差 由下述f式计算:步骤B2:为确保系统中的每个任务都得到可行的处理,必须满足每个边缘服务器Sj与一个基站完全位于同一位置,其约束条件为下述g式定义:步骤B3:每个基站Bm都被分配给一个边缘/云服务器,并由下述h式定义:步骤B4:发送到每个边缘/云服务器Sj的总任务到达率不超过边缘/云服务器可以处理任务的速率,并由下述i式定义:步骤B5:输入无向图G=(V,E)、基站的离线任务到达率 以及边缘/云服务器的计算能力{p0,p1,…,pN};
步骤B6:在上述步骤B2的约束条件下计算预期响应时间的最小值,找到边缘服务器的最佳放置策略 和分配策略 从而获得离线任* *
务到达率的最优离线解Ω=(P ,A);
所述步骤3的实现过程按下述步骤进行:步骤C1:用 表示改变任务到达率的Q个基站的集合,Q个基站彼此合作和竞争,使得不仅最小化他们各自的预期响应时间,而且最小化系统预期响应时间,经几轮迭代后,将得到最优解;
步骤C2:使用最大化与Q个改变任务到达率的基站的相关效用函数的乘积作为合作博弈的目标函数,且由下述j式定义基站的效用函数:其中:响应时间 被归一化到[0,1]的范围内;
步骤C3:由下述k式定义重新分配问题:s.t. Aq,n=0,1
其中:剩余计算能力Δpn由下述l式计算:所述步骤4的实现过程按下述步骤进行:* *
步骤D1:输入离线任务到达率的最优离线解Ω=(P ,A )、离线任务到达率在线任务到达率为 边缘/云服务器的计算能力{p0,p1,…,pN}和初始化任务到达率为0;
步骤D2检查基站的任务到达率是否在运行时改变,如果答案为否,则返回上述步骤B6的最优解;如果答案为是,则算法将任务到达率的标记设置为1并用启发式算法重新分配;
步骤D3:构建改变了任务到达率基站的集合B′={B1,B2,…,B Q};
步骤D4:计算每个边缘/云服务器的剩余计算能力Δpn;
步骤D5:重新确定每个基站的最佳边缘/云服务器,并相应地更新分配策略。
说明书 :
一种数据驱动的边缘响应时间优化方法
技术领域
背景技术
器代表他们自己执行任务执行,然而,这种模式导致移动用户在物联网时代不可避免地遭
受高服务延迟。作为替代解决方案,因此提出在移动用户和云服务器之间部署边缘服务器
的移动边缘云计算为众多移动用户提供低延迟服务。在过去几年中,人们对用于移动边缘
云计算系统的延迟感知边缘服务器部署的研究产生了广泛的兴趣。
发明内容
于移动性感知博弈论的方法,处理用户移动的动态特性,计算在基站的任务到达率有波动
时的最优解,有效解决了用户移动动态特性引起的基站工作负载波动,大大提高整个系统
和个人移动用户的预期响应时间,将系统预期响应时间缩短了54.55%,移动用户的响应时
间公平性提高了72.50%,方法简单,使用方便,效率高。
法,计算在基站的任务到达率有波动时的最优解,优化系统的预期响应时间和移动用户的
响应时间公平性,其具体优化包括以下步骤:
SE}是由云服务器和边缘服务器集组成的服务器集。
缘/云服务器的拓扑;其中:集合V表示 M个基站和云服务器S0 的固定放置位置的集合,以及
N个边缘服务器的可能放置位置;集合E表示基站和边缘/云服务器之间的通信链路集。
描述,并由下述e式定义:
* *
线任务到达率的最优离线解Ω=(P ,A)。所述步骤3的实现过程按下述步骤进行:
响应时间,经几轮迭代后,将得到最优解。
{p0,p1,…,pN}和初始化任务到达率为0。
配。
整个系统和个人移动用户的预期响应时间,将系统预期响应时间缩短了54.55%,移动用户
的响应时间公平性提高了72.50%,方法简单,使用方便,效率高。
附图说明
具体实施方式
6
理分布如图所示:平均任务到达率(每秒CPU周期数) 和每个基站的数据量分别为[4×10 ,
8
6×10 ]和[1,100]Mb;每个链路的通信容量是在[100,1000]KB/s的范围内随机选择的;电
5
磁波的传播速率设定为 2×10km/s。
算云服务器S0的计算容量p0为10×3.6GHz= 36.0GHz。此外,构建了基于HPE ProLiant
MicroServer Gen10服务器,Dell R230服务器,Lenovo TS250服务器和浪潮NP3020服务器
的边缘服务器集。本发明根据提出的离线和在线算法进行了两组对比实验:一组用于离线
算法 PEAB,即本发明的步骤2(离线阶段,利用整数线性规划技术计算离线任务到达率的最
优离线解),另一组用于在线算法RBEC,即本发明的步骤4(在线阶段,通过转换为凸优化问
题来解决合作博弈问题,计算在基站的任务到达率有波动时的最优解)。在第一组模拟中,
将离线算法PEAB与基准算法WRES, EPSO和DAPP进行了比较。在第二组仿真中,将在线算法
RBEC与基准算法 RALL和DGEN进行了比较。WRES旨在联合优化边缘服务器的工作负载和响
应时间,采用MILP技术进行边缘服务器的部署。EPSO旨在最小化边缘服务器的整体能耗,其
中利用众所周知的粒子群优化技术(PSO)来执行边缘服务器的部署。DAPP将边缘服务器放
置表示为图中的经典容量K中值问题,以便可以最小化系统响应时间。RALL尝试在运行时最
小化整个系统和各个基站的响应时间。其主要思想是通过修改本发明步骤2的算法来重新
分配所有基站,假设已经放置了所有边缘服务器。DGEN与方案RALL类似,也尝试在运行时最
小化整个系统和各个基站的响应时间。它利用中引入的遗传算法技术,以改变任务到达率
来重新分配基站。NAVE是一种天真的在线方法,直接采用我们提出的方法PEAB的输出,并且
它不采取任何行动来处理基站的任务到达率在运行时已经改变的情况。上述算法均采用C+
+实现,两组仿真实验均在配备16GB内存和Intel i5双核3.5GHz处理器的台式计算机上进
行。并且使用不同的基站工作负载设置执行3000次实验,以将建议的解决方案与基准测试
方案进行比较,具体优化过程按下述步骤进行:
的3233个基站组成的集合,即: B={B1,B2,…,B3233},平均任务到达率(每秒CPU周期数)和
6 8
每个基站的数据量分别为:[4×10 ,6×10]和[1,100]Mb。每个链路的通信容量是在 [100,
5
1000]KB/s的范围内随机选择的。电磁波的传播速率设定为2×10km/s。并选择选择配备10
核且每核工作频率为3.6GHz的HPE ProLiant ML350 Gen10 服务器作为云服务器S0,并假
设云服务器的任务执行时间遵循正态分布,平均值为10ms,方差为4。云服务器S0的计算能
力p0为10×3.6GHz=36.0GHz。此外,构建了HPE ProLiant MicroServer Gen10服务器,
Dell R230服务器, Lenovo TS250服务器和浪潮NP3020服务器的边缘服务器集,其具体性
能和参数见下表1:
服务器每个核的频率 3.4GHz 3.0GHz 3.9GHz 3.0GHz
核心 4 6 2 4
每台服务器的计算能力 13.6GHz 18.0GHz 7.8GHz 12.0GHz
执行时间的正态分布(ms) N(20,5) N(14,8) N(35,15) N(17,10)
到边缘服务器的最佳放置策略 和分配策略
* *
使用ILP求解器求解得离线任务到达率的最优离线解Ω=(P ,A)。
用 表示改变任务到达率的Q个基站的集合。Q个基站彼此合作
和竞争,使得不仅最小化他们各自的预期响应时间,而且最小化系统预期响应时间。经过几
轮迭代后,将得到最优解。使用最大化与Q个改变任务到达率的基站的相关的效用函数的乘
积作为合作博弈的目标函数,并由下述j式定义基站的效用函数:
5a)式描述为:
的最小值 并令 即:
务到达率有波动时的最优解。输入离线任务到达率的最优离线解Ω=(P ,A),离线任务到
达率 在线任务到达率 以及边缘/云服务器
的计算能力{p0,p1,…,pN},初始化任务到达率为0;检查基站的任务到达率是否在运行时改
* *
变。如果答案为否,则返回步骤2的离线最优解Ω=(P ,A);如果答案为是,则算法将任务到
达率的标记设置为1并用启发式算法重新分配;构建改变了任务到达率的基站的集合B′=
{B1,B2,…,BQ};计算每个边缘/云服务器的剩余计算能力Δpn;重新确定每个基站的最佳边
缘/云服务器,并相应地更新分配策略。
时间分别比基准算法EPSO,WRES,DAPP平均小45.21%,36.61%和16.46%。此外,PEAB的最
高改善率高达54.55%。例如,在第24个数据点中,PEAB和EPSO系统的预期响应时间的分别
为0.10 和0.22,其图中的每个数据点是100次实验的平均值。
预期响应时间的标准偏差分别比EPSO,WRES 和DAPP小61.23%,57.13%和42.41%。此外,
PEAB实现的最高改善率高达80.77%。例如,在第5个数据点,PEAB和EPSO的预期响应时间的
标准偏差分别为0.05和0.26。
示由于违反约束 移动用户的任务无法可行地安排。如图
所示,系统预期响应时间分别比基准算法NAVE和DGEN平均小41.87%和23.54%。此外,系统
预期响应时间比方法RALL平均高12.11%。
也可以看到算法RBEC不如方法RALL,平均性能差异为15.35%。
明,与方法RALL和DGEN相比,本发明的算法RBEC平均达到24.16和2.31倍的加速,加速计算
为测试中的基准测试方法所消耗的运行时与本发明的算法RBEC所消耗的运行时间的比率。
此外, RBEC方法的加速可达25.33,例如,在第9个数据点中,本发明的方法RBEC 和基准测
试方法RALL的运行时间分别为0.79和20.01。
用户移动的动态特性。更重要的是开发的方法共同考虑了边缘云协作和移动用户的性能公
平性。仿真结果表明,本发明的算法可以大大提高整个系统和个人移动用户的预期响应时
间。