面向边缘计算环境的基于博弈理论的微服务请求分发方法转让专利
申请号 : CN202110411844.5
文献号 : CN113225385B
文献日 : 2022-05-06
发明人 : 冯志勇 , 石博文
申请人 : 天津大学
摘要 :
权利要求 :
1.一种面向边缘计算环境的基于博弈理论的微服务请求分发方法,包括以下步骤:步骤1:将边缘服务器ej从自身利益最大化即时延最小化的角度进行的微服务请求分发决策问题转换为如下的优化问题:
约束条件为:
λ′i≤Ωi·μi,1≤i≤m (6)其中Tj表示边缘服务器ej将基于微服务架构的应用请求分发完毕后产生的平均响应时间;服务器集合表示为E∪{e0},E表示边缘服务器集合,边缘服务器个数为n,e0表示云服务器;定义基于微服务架构的应用请求是由m个微服务组成的调用链SC完成,即SC={ms1,ms2,…,msm};Φj=(j,Φ1,Φ2,…,Φi,…,Φm,j)表示边缘服务器ej上应用请求的生命周期,即各个微服务调用的顺序,Φi表示调用微服务msi时选择的边缘服务器;A=(1,1,…,
1),它表示阶为1×(n+1)的矩阵;O1表示阶为(n+1)×1的零矩阵;O2表示阶为(n+1)的零方T
阵;λ′i=(λ′i,0,λ′i,1,…,λ′i,j,…,λ′i,n) 表示微服务msi在不同服务器上的请求到达速率集合,其中λ′i,0表示微服务msi在云服务器e0上的请求到达速率,λ′i,j表示微服务msi在边缘T
服务器ej上的请求到达速率;μi=(μi,0,μi,1,…,μi,j,…,μi,n) 表示微服务msi在不同服务器上的请求处理速率集合,其中μi,0表示微服务msi在云服务器e0上的请求处理速率,μi,j表示微服务msi在边缘服务器ej上的请求处理速率;Ωi表示微服务msi的实例在服务器上的部署情况即:
其中Ωi,0表示微服务msi的实例在云服务器e0上的部署数量,Ωi,j表示微服务msi的实例在边缘服务器ej上的部署数量; 表示微服务请求路径为Φj的概率,定义 表示云服务器或边缘服务器ej分发关于微服务msi的请求到云服务器或边缘服务器ek的概率,则表示为:
其中∏表示累乘,由于应用请求的响应结果总是会回传到源边缘服务器上然后返回给用户,所以 不会影响 值的大小,即:用 表示边缘服务器ej对微服务ms1的请求分发策略,用 表示对微服务msi+1,1≤i≤m‑1,的请求分发策略,即:TΦ表示经过Φj路径所需要的延时时间;
步骤2:将边缘协作空间内n个边缘服务器之间微服务请求分发决策问题抽象为一个非合作博弈模型:
其中E表示博弈参与者即边缘服务器集合; 表示边缘服务器ej的策略集合;Tj(Sj,S‑j)表示博弈参与者即边缘服务器ej的效益函数,即用来计算边缘服务器ej服务范围内收到的应用请求的平均响应时间的函数,其中Sj表示边缘服务器ej的微服务请求分发策略,S‑j表示除边缘服务器ej外,剩余边缘服务器的微服务请求分发策略集合;
步骤3:n个边缘服务器作为博弈参与者采用同步轮转的方式,不断更新自己的策略,经过多个轮次的迭代最终实现纳什均衡状态,即没有任何一个边缘服务器可以在该状态通过更新自己的微服务请求分发策略来进一步的提高自己的效益;
步骤4:根据最终得到的纳什均衡解,制定每个边缘服务器ej的微服务请求分发决策Sj即:
2.根据权利要求1所述的微服务请求分发方法,其特征在于,在每个边缘服务器更新自己策略并计算效益Tj的过程中考虑邻近边缘服务器服务重叠区域内对微服务ms1请求的分发优化,此优化的步骤如下:
步骤3.1:构成服务重叠区域的边缘服务器集合 t表示重叠区域O内用户上传速率最大的边缘服务器et,设定重叠区域内微服务ms1的请求会优先分发给et处理,设定重叠区域O内的应用请求数量为Onum,边缘服务器et的应用请求到达速率为λt,边缘服务器et对微服务ms1的请求分发策略为步骤3.2:初始化重叠区域内微服务ms1请求分发的优化策略 根据公式计算用户直接将微服务ms1的请求分发给边缘服务器ek可以节省的时间,构成集合H={hu,1,hu,2,…,hu,k,…,hu,l},其中u表示某一用户, 表示微服务ms1的请求参数大小, 表示用户到边缘服务器et的上传速率, 表示边缘服务器et和边缘服务器ek之间的数据传输速率, 表示用户到边缘服务器ek的上传速率;
步骤3.3:对H降序排序;
步骤3.4:按照优先将微服务ms1的请求发送给最节省时间开销的边缘服务器的原则来分发重叠区域的请求,直至Onum分发完或没有可以再优化分发的边缘服务器为止;
步骤3.5:最后,若Onum还有剩余,直接按照原请求分发路径进行分发并返回优化策略向量 按照 对微服务ms1进行请求分发从而进一步的降低时延Tj。
说明书 :
面向边缘计算环境的基于博弈理论的微服务请求分发方法
技术领域
背景技术
(Microservice Architecture)应运而生。微服务架构将复杂的软件服务拆分成细粒度的
微服务,并对这些微服务采用分布式的方式进行开发、部署、管理和更新。相较于传统的单
体服务,微服务架构具有高可扩展性、松散耦合、高弹性、易于部署和访问、敏捷开发等诸多
优点。
缘设备,并以边缘设备为服务载体为用户提供服务,从而将服务从云服务中心迁移到距离
用户更近的网络边缘。微服务小而自治的特点,使其正适合于独立部署在边缘设备上。如此
一来,用户可以直接访问边缘设备上的微服务,而无需经过核心网与云服务中心进行交互,
因此,与传统的云计算模式相比,极大地缩减了服务数据在核心网上传输所需的时间与能
耗开销,提升了用户的服务体验质量;同时,还可以降低核心网的数据传输量,缓解核心网
的数据传输压力;此外,由于服务数据直接在边缘设备上处理,故而降低了数据被窃听和篡
改的风险,保护了用户的数据安全和隐私。
常只能部署有限数量的微服务实例,处理有限种类的微服务请求,因此,不足以覆盖用户复
杂多样的服务需求。当边缘服务器无法满足用户的微服务请求时,需要将服务请求转发给
临近的可以满足该服务请求的边缘服务器,即边缘服务器之间组成一个协作空间,并在集
群管理技术下,相互协作,资源共享。除此之外,一个基于微服务架构的应用程序是由几个
逻辑上相关但功能上独立的微服务构建而成,一个微服务不会仅仅单独完成一个简单的任
务,而是会按照一定的调用顺序,组成一个服务调用链,来共同完成更加复杂的应用请求。
边缘协作空间内,在基于容器技术的帮助下,一个特定应用程序所包含的一组微服务实例
可以很容易的部署在边缘服务器以及云服务器上,并且由于边缘服务器和云服务器具有不
同的计算、存储和通信能力,微服务实例可以具有各种各样的部署方案(部署位置及个数)。
对于一个微服务请求,可能会有多个边缘服务器或者云服务器提供所需的服务,因此,在已
知微服务部署方案的前提下,如何为一个微服务调用链中不同微服务请求做出合理的分发
决策以降低应用请求的响应时间成为亟待解决的关键问题。本发明将研究合理的微服务请
求分发策略,达到最优化服务质量,即最小化应用响应时间的目的。
算系统中所有边缘服务器的实时服务执行状态、服务请求的到达速率以及边缘服务器之间
的网络信息,从而基于这些信息制定微服务请求的分发决策。然而,这种模型对系统状态信
息更新的实时性要求过高,在大规模的动态系统中,很难达到此要求;频繁的信息交互容易
产生高昂的网络传输开销;此外,该模型过分依赖中心控制节点,单点故障瓶颈凸显,即中
心控制节点一旦出现故障,会导致整个边缘计算系统的崩溃,因此,模型还存在易出错、难
扩展、鲁棒性低等缺点。
发明内容
法,该方法将边缘服务器之间的微服务请求分发问题建模为非合作博弈模型,边缘服务器
作为博弈参与者通过多轮次的博弈和计算资源的竞争来为其收到的应用请求做出最优的
分发策略,即最小化这些应用请求的平均响应时间,称其为MRDG算法。技术方案如下:
服务器;定义基于微服务架构的应用请求是由m个微服务组成的调用链SC完成,即SC=
{ms1,ms2,…,msm};Φj=(j,Φ1,Φ2,…,Φi,…,Φm,j)表示边缘服务器ej上应用请求的生命
周期,即各个微服务调用的顺序,Φi表示调用微服务msi时选择的边缘服务器;丑=(1,
1,…,1),它表示阶为1×(n+1)的矩阵;o1表示阶为(n+1)×1的零矩阵;o2表示阶为(n+1)的
T
零方阵;λ′i=(λ′i,0,λ′i,1,…,λ′i,j,…,λ′i,n)表示微服务msi在不同服务器上的请求到达
速率集合,其中λ′i,0表示微服务msi在云服务器e0上的请求到达速率,λ′i,j表示微服务msi在
T
边缘服务器ej上的请求到达速率;μi=(μi,0,μi,1,…,μi,j,…,μi,n) 表示微服务msi在不同服
务器上的请求处理速率集合,其中μi,0表示微服务msi在云服务器e0上的请求处理速率,μi,j
表示微服务msi在边缘服务器ej上的请求处理速率;Ωi表示微服务msi的实例在服务器上的
部署情况即:
云服务器或边缘服务器ej分发关于微服务msi的请求到云服务器或边缘服务器ek的概率,则
表示为:
收到的应用请求的平均响应时间的函数,其中Sj表示边缘服务器ej的微服务请求分发策略,
S‑j表示除边缘服务器ej外,剩余边缘服务器的微服务请求分发策略集合;
态通过更新自己的微服务请求分发策略来进一步的提高自己的效益;
优先分发给et处理,设定重叠区域O内的应用请求数量为Onum,边缘服务器et的应用请求到达
速率为λt,边缘服务器et对微服务ms1的请求分发策略为
节省的时间,构成集合H={hu,1,hu,2,…,hu,k,…,hu,l},其中u表示某一用户, 表示微服务
ms1的请求参数大小, 表示用户到边缘服务器et的上传速率, 表示边缘服务器et和边缘
服务器ek之间的数据传输速率, 表示用户到边缘服务器ek的上传速率;
附图说明
最近的边缘服务器来调用应用程序。
对DataCollection、HealthQuery、AutoReport三种微服务的路由和调用过程;5号过程表示
应用的执行结果回传到接收用户应用请求的源边缘服务器上;6号过程代表最后的检测结
果返回给老人,至此整个微服务调用链的调用过程结束(OnlineAid是一款基于微服务架构
的老年人在线检测应用程序)。
理,直至应用执行结果返回给用户。
时间。
具体实施方式
模型构建和算法设计的详细说明。
服务器;定义基于微服务架构的应用请求是由m个微服务组成的调用链SC完成,即SC={ms1,
ms2,…,msm};Φj=(j,Φ1,Φ2,…,Φi,…,Φm,j)表示边缘服务器ej上应用请求的生命周
期,即各个微服务调用的顺序,Φi表示调用微服务msi时选择的边缘服务器;丑=(1,1,…,
1),它表示阶为1×(n+1)的矩阵;o1表示阶为(n+1)×1的零矩阵;O2表示阶为(n+1)的零方
T
阵;λ′i=(λ′i,0,λ′i,1,…,λ′i,j,…,λ′i,n) 表示微服务msi在不同服务器(云服务器和边缘服
务器)上的请求到达速率集合,其中λ′i,0表示微服务msi在云服务器e0上的请求到达速率,
λ′i,j表示微服务msi在边缘服务器 上的请求到达速率;μi=(μi,0,μi,1,…,
T
μi,j,…,μi,n) 表示微服务msi在服务器(云服务器和边缘服务器)上的请求处理速率集合,其
中μi,0表示微服务msi在云服务器e0上的请求处理速率,μi,j表示微服务msi在边缘服务器
上的请求处理速率;Ωi表示微服务msi的实例在服务器(云服务器和边缘服务器)
上的部署情况即:
表示服务器(云服务器和边缘服务器)ej分发关于微服务msi的请求到服务器(云服务器
和边缘服务器)ek的概率,则 表示为:
服务ms1的服务器(云服务器和边缘服务器)上的传输时间;Trouting表示服务链中各项微服务
调用的路由时间;Tstaying表示微服务请求在每个服务器(云服务器和边缘服务器)上的逗留
时间(包括排队等待的时间和服务执行的时间);Tbackhaul由两部分组成,首先是微服务msm完
成应用请求后将响应结果回传到接收应用请求的源边缘服务器ej的时间,然后由边缘服务
器ej将响应结果返回给终端用户的时间。
(5)保证了所有微服务请求的分发概率总是满足非负性;最后,约束(6)保证了服务器(云服
务器和边缘服务器)的稳定性,因为根据排队理论,如果服务器当前可用的服务处理速率低
于服务请求到达的速率,等待执行的任务队列将无限长,使得应用请求的响应时间也将是
无限长的。
收到的应用请求的平均响应时间的函数,其中Sj表示边缘服务器ej的微服务请求分发策略,
S‑j表示除边缘服务器ej外,剩余边缘服务器的微服务请求分发策略集合。
态通过更新自己的微服务请求分发策略来进一步的提高自己的效益。本发明为了进一步的
降低微服务请求的响应时间,在每个边缘服务器更新自己策略并计算效益Tj的过程中特意
考虑了邻近边缘服务器服务重叠区域内对微服务ms1请求的分发优化,其优化的步骤如下:
内微服务ms1的请求会优先分发给et处理。设定重叠区域O内的应用请求数量为Onum,边缘服
务器et的应用请求到达速率为λt,边缘服务器et对微服务ms1的请求分发策略为
节省的时间,构成集合H={hu,1,hu,2,…,hu,k,…,hu,l},其中u表示某一用户, 表示微服务
ms1的请求参数大小, 表示用户到边缘服务器et的上传速率, 表示边缘服务器et和边缘
服务器ek之间的数据传输速率, 表示用户到边缘服务器ek的上传速率。
行。
信。MRDG算法就是由这组调度代理定期执行完成的。
可以看出,MRDG算法优于GA(遗传算法)和PRDA(按比例分配算法)并且非常接近Optimal(全
局最优算法),这表明本发明所提算法的有效性。图6和图7是MRDG算法的收敛性评估。可以
看到,每个边缘服务器的平均响应时间在最开始迭代阶段变化比较明显,但随着迭代次数
的增加,所有边缘服务器的变化放缓,并最终达到一个稳定状态,在该状态所有边缘服务器
都获得了一个相互满意的请求分发策略,已经没有进一步优化的必要了,表明MRDG算法可
以收敛于一种稳定状态,即纳什均衡状态。图8是MRDG算法对于服务重叠区域内请求分发优
化的必要性评估。可以看到,随着重叠区域请求占比的增加,考虑服务重叠区域请求分发优
化的MRDG算法的平均响应时间在不断的下降,而不考虑服务重叠区域内请求分发优化算法
的平均响应时间没有发生变化,因此,重叠区域占比越大,考虑重叠区域内请求分发优化的
必要性就越明显。
请求信息,从而制定自身所持有应用请求的分发策略。因此,去中心模式可以克服集中式优
化模型中的实时信息获取难以及中心控制节点单点故障等问题,具有灵活、易扩展、可靠性
高等优点。采用基于博弈理论(Game Theory)的方法来解决上述提出的问题。