移动边缘计算中服务功能链的自适应优化部署策略*

2023-11-25熊泽凯王素红王靖君祝长鸿覃团发

电讯技术 2023年11期

熊泽凯,王素红,王靖君,祝长鸿,覃团发

(广西大学 a.计算机与电子信息学院;b.广西多媒体通信与网络技术重点实验室,南宁 530004)

0 引言

移动边缘计算(Mobile Edge Computing,MEC)[1]是一种新兴的云架构,通过在基站(Base Stations,BS)部署MEC服务器,为移动用户提供计算和存储资源,显著缩短响应延迟,满足多样化的业务需求。在现代移动通信发展进程中,软件定义网络(Software Defined Network,SDN)与网络功能虚拟化(Network Function Virtualization,NFV)这两个技术发挥的作用也正日益凸显。其通过虚拟化技术和云技术,利用商用服务器上的软件应用程序取代了需要专用硬件的网络功能。其中,在虚拟机中实现的网络功能称为虚拟网络功能(VNF);同时,业务流量需要由多个VNF按照严格的逻辑顺序进行处理,该逻辑顺序被称为服务功能链(Service Function Chain,SFC)[2]。目前,将NFV与移动边缘计算相结合引起了广泛的关注,但由于CPU计算能力、服务器缓存资源等通信资源具有非常强的耦合性,也为移动边缘计算网络中的功能虚拟化带来了更大的挑战:首先是边缘网络节点种类多样,其通信特征、计算能力和缓存内容有较大差异,很难满足未来网络发展要求[3];其次是随着移动通信业务种类与数量的增长,对服务的要求也日益复杂。

NFV构架由物理网络层与虚拟网络层组成。若要为通信业务提供相应的服务,则需要完成相对应的SFC部署,即在SFC系统性能准则下,在网络基础设施上设计VNF的映射和路由方案[4]。如何将SFC高效且准确地映射和部署在底层的物理硬件网络上,是目前受到广泛关注的课题之一[5-14]。目前的主流研究方向有两个:一个是将系统成本开销最小化,从而获得最大化的收益;另一个则是将通信流量最小化,从而降低系统的通信时延。

由于地理位置的限制,SFC中的各个节点被分散在整个网络中,边缘节点之间,核心节点与边缘节点之间有着地理位置上的距离,在地理上分离的节点之间传输数据的时间成本很高[15],因此地理位置因素是在边缘网络中部署服务功能链时须考虑的首要问题。其次,由于资源的约束,额外配置对应的VNF节点会造成有限资源的浪费,因此节点合理化共享和节点缓存资源的自适应更新在SFC部署中尤为重要。此外,文献[5-14]的研究工作并未考虑有线用户和无线用户存在的信道特征差异,有线和无线的传输成本相差巨大;同时也缺乏基于时延和开销折中优化的SFC部署研究。

针对上述问题,为更加高效且准确地部署SFC,在考虑不同用户信道特征选取相应的VNF节点的同时,还需要考虑不同VNF之间的资源协调分配,进而提高利用率和准确率,从而降低SFC的网络部署成本。因此,在有线用户和无线用户都存在业务需求的网络场景下,本文提出了一种移动边缘计算中服务功能链的自适应优化部署策略,并通过实验仿真验证了其有效性。

1 网络模型

系统模型如图1所示,包括物理网络层和虚拟网络层。在物理网络层中,存在许多的硬件设施资源,其中包括了计算资源、缓存资源、有线通信资源和无线接收接发资源等,能够为有线用户和无线用户提供相应的通信业务需求服务。其中,无线用户需要与邻近的无线通信设备进行业务请求与接收业务服务,有线用户则通过本地主机进行业务请求与接收业务服务。在虚拟网络层中,有许多功能不同的VNF节点,当有业务需求的请求时,通过连接不同的VNF节点以源端点到目的端点的方式形成对应的SFC,最后通过映射算法将SFC映射到物理网络层中,从而实现对不同用户的通信业务的服务。

图1 移动边缘计算中的SFC部署系统模型

2 问题描述与系统模型

2.1 问题描述

将物理层网络可表示为￡=(X,Y),X表示边缘计算中的物理节点集合,Y表示物理链路的集合。其中,物理链路中存在有线链路和无线链路,有线链路可以表示为Y(e,f),无线链路可以表示为Yw(e,f)。SFC的请求集合可以将其表示为S={Sk|k=1,2,…,K},K为业务请求的数值。由于每条SFC是由多个功能类型不同的VNF所构成的,因此Sk={v1,v2,v3,…,vi|vi∈V},V为多个VNF节点的集合。由于节点的异构,因此需要考虑不同节点在某个时刻的缓存资源量和映射能力。有线节点的CPU计算资源为C(ne),缓存资源为M(ne),转发资源为F(ne);无线节点的CPU计算资源为C(nf),天线数目为A(nf),无线缓存资源为B(nf),天线的发射功率为P(nf)。这里考虑到路径损耗这个无线信道的衰落问题,其计算公式如下:

(1)

式中:d为距离或范围,单位为m;f为信号发射的频率,单位MHz。在一个时隙系统中,用t∈{1,2…}表示时隙序号。定义VNF的流量改变因子为

(2)

式中:rin和rout为VNF节点的输入流量和输出流量。接下来需要对VNF节点的缓存资源进行部署。不同业务需求所需要的缓存资源也不同,VNF节点的缓存资源可以表示为M={m1,m2,…,mn},因此VNF节点当前时刻的请求报告可以定义为R={r|r=(ui,tj,mn)},u为用户集合。VNF节点间缓存内容的相似度可以表示为

(3)

式中:Ri,k表示在t时刻第i个VNF节点中缓存内容k的请求次数。相似度γ∈[0,1],其越接近1则说明两个VNF节点之间的内容越相近,能够共同处理相同的业务请求。令有线链路的传输时延为Te,则可以表示为

(4)

式中:Lin为发送的数据包长度;Ve为有线节点之间的有线链路传输速率。令无线链路传输时延为Tw,则有

(5)

式中:Vw表示无线链路的传输速率,利用香农公式可以将其表示为

(6)

式中:P为无线发射功率;h为VNF节点之间的无线信道系数;B为VNF节点之间的无线信道带宽;σ2为接收机噪声的方差。在时隙t时刻,VNF节点的可用资源表示为

W=C(t)+M(t)+F(t) 。

(7)

式中:C(t)表示CPU的计算资源;M(t)表示节点的缓存资源;F(t)为传输资源。特别地,对于具有无线传输功能的VNF节点,其可用资源可以表示为

Wf=W+A(t)+Bm(t)+p(t) 。

(8)

式中:A为天线数目;Bm为无线缓存资源;p为无线传输功率。令VNF节点的部署资源所需成本为

Cn=∑(αC(vi)+βM(vi)+μF(vi)) 。

(9)

式中:α,β,μ分别表示CPU计算资源、VNF节点缓存资源和转发资源的加权系数。定义Q为系统组件的可靠性,表示为

Q=∏rn。

(10)

式中:rn为系统组件在规定时隙时段内无故障提供业务服务的概率,可以表示为

(11)

式中:ρ表示系统组件正常工作的时间;ξ代表组件需要的修复时间。令虚拟链路集合为L={li,0,li,1,…,li,n},li,i+1表示第i个VNF节点与第i+1个VNF节点之间所构成的虚拟链路。将虚拟链路映射至物理网络层时,由于功能不同,不同的VNF节点所组成的链路也不同,与之对应的映射方法也不同,因此,SFC的映射所需要的成本开销也不同。令Cm为SFC的映射成本,可以将其表示为

(12)

式中:括号内的第一项为VNF节点vi所映射到的物理节点上的物理链路的映射带宽资源和业务请求的链路成本;φ表示的时物理链路之间固有的资源消耗;第三项为链路带宽消耗,其中,b为链路剩余带宽,τ表示当前的VNF节点到下一节点的跳数最小值。为了扩展系统带宽,增加系统的吞吐量,加强网络数据的处理能力,提高网络的灵活性和可用性,在这里考虑各个物理节点的负载均衡。因此,具有无线功能的物理节点的资源成本可以表示为

(13)

式中:H(vi)表示VNF节点vi被请求业务所需的无线资源;q表示物理节点启用无线虚拟功能所需要的资源成本;A(n)表示无线传输所需的天线数目;Aall(n)表示节点总共的天线数目;B(n)表示节点无线传输所需的无线资源块数;Ball(n)表示节点拥有的无线资源总块数;P(n)表示节点处理业务时所占用的无线功率;LP表示路径损耗功率;Pall(n)表示节点拥有的最大无线传输功率;x∈{0,1},当x为1时表示vi已部署之边缘节点,反之则未部署之边缘节点。

综上,整个SFC网络部署的总代价可以表示为

(14)

式中:ω1,ω2,ω3分别表示VNF部署所需资源成本、SFC映射成本和物理节点资源成本的权重系数;ω4表示节点之间的传输资源的权重系数;τ表示初始节点到目的节点之间的最短条数;b(li)为整个虚拟链路所需带宽资源。

2.2 系统模型

2.2.1 统评价指标

1)SFC部署成功率

定义为在规定时间内到达的SFC请求数量与成功部署的SFC的数量的比值,表示为

(15)

式中的分子表示在总运行时间趋向于无穷大的时候,已经完成的SFC的部署总量;分母表示在总运行时间趋向于无穷大的时候,SFC请求的总量。

2)系统平均可靠性

由于节点的部署是独立的,因此SFC系统的平均可靠性可以表示为

(16)

3)系统平均时延

SFC的传输时延为传输时延、节点处理数据时延以及虚拟链路的部署时延之和,可以表示为

(17)

公式中的第一项表示系统中有线链路的传输时延总和;第二项表示系统中无线链路的传输时延总和;第三项表示节点部署与虚拟链路部署时延总和;第四项表示节点数据处理时延,其中,C(n)表示节点CPU计算能力,Bs表示处理业务的内容数据大小。则系统平均时延可以表示为

(18)

4)系统带宽消耗

SFC成功部署所需要的带宽可以表示为

(19)

式中:b为第k条SFC成功部署所需要消耗的带宽资源。

2.2.2 优化目标函数

在SFC的部署时,为了满足业务需求,需要使部署成本最小。同时,为了提高SFC部署的可靠性,也要降低链路的时延。优化目标函数可以表示为

min[μ1T+μ2ψc]。

(20)

式中:μ1表示SFC传输时延的加权系数;μ2表示SFC部署总成本的加权系数。

2.2.3 约束条件

SFC中任意的VNF节点都能够部署在物理网络层的有线或无线的节点上,由于物理网络层的节点功能异构,因此只能够将最多一个物理节点进行实例化,即

(21)

用y∈{0,1}表示虚拟链路在物理层链路的部署方式,当y的值为1时表示li部署至无线链路,反之则部署至有线链路。为了确保业务请求链路的通畅,每条SFC虚拟链路只能对其对应的那一条物理链路进行映射,即

(22)

每个物理节点所映射的VNF节点所消耗的资源,不能够超过物理节点所拥有的最大资源,即

Cvi≤Cnj。

(23)

式中:Cvi表示VNF节点的映射消耗资源量;Cnj表示物理节点能够提供给VNF节点的映射资源的总量。由于系统带宽的限制,SFC部署时所需带宽不能超过该时隙时刻系统中的闲置带宽,即

(24)

式中:φ∈{0,1},当其值为1时表示已将虚拟链路映射至物理网络层,反之则表示并未将虚拟链路映射至物理网络层。规定时延要小于用户所能承受的最大等待时延,即

T≤T0(li),∀li∈L。

(25)

式中:T0(li)表示用户所能承受的最大等待时延。而对于VNF节点而言,还需要满足以下约束条件:

(26)

(27)

(28)

式中:maxB(j),maxA(j),maxP(j)分别表示节点能够提供的最大无线资源块数、天线最大数量和最大的发射功率。

3 算法介绍

SFC的部署是一种虚拟化网络的嵌入问题[16],属于非确定性多项式问题,求解难度很大,因此,需要降低SFC部署方案的计算复杂度。在对时隙时刻的随机业务请求到达时,对用户地理位置和通信方式进行分类,区分有线和无线通信类型的用户类型,提出了基于用户通信类型与位置感知的共享节点选取算法,判断所需部署SFC中的VNF位置与通信类型,用于满足节点共享的条件,达到减小VNF节点之间、物理节点与用户之间的通信时延和提高通信可靠性。在VNF节点配置阶段,根据用户请求处理的数据内容的新鲜度记录,自适应动态增加和删减相应的缓存,利用资源感知算法在保证数据传递可靠性的同时减少服务节点的配置个数,降低配置开销。最后,在服务功能链部署阶段,利用基于KSP的功耗感知算法求出最短路径的集合,得到低时延低功耗的SFC链路映射,不但保证了SFC部署的低时延和低功耗,还能减少链路重映射。

3.1 基于用户通信类型与位置感知的共享节点选取算法

针对用户的位置与通信类型,将用户分为有线用户和无线移动用户。为保证信息传输的可靠性,有线用户只能够和有线的物理边缘节点进行信息交互,无线用户只能够和无线的物理边缘节点进行信息交互,但是各个有线或无线的边缘物理节点都能够进行信息传输与处理。为此,则需要感知VNF节点的位置与通信方式是否满足用户的通信类型。当有SFC业务请求时,首先判断用户的通信类型和地理位置,便于寻找各类用户所对应距离最短的VNF节点。接着再判断整个SFC中的VNF节点是否存在着功能互斥,在这里将共享节点的内容相似度门限设为0.85,这样在确保节点能够进行共享的同时,还能够使得共享后的节点可以高效地处理相同类型业务,不但保证了系统具有较高的鲁棒性,还能减少额外节点的配置。最后根据流量因子乘积是否满足共享条件,求出进行共享的VNF节点集合。

基于用户通信类型与位置感知的共享节点选取算法(算法1)具体步骤如下:

输入:物理层边缘网络信息￡,用户通信类型与位置信息

输出:共享VNF节点集合Group

IF用户为无线用户

确定满足条件且离用户最近的无线VNF节点作为源节点

ELSE

将有线用户的VNF节点作为源节点

FOR除源节点外所有待部署的VNF节点

IF当前VNF节点满足初始共享条件(γ> 0.85)

进入下一步共享操作

ELSE

退出共享

END IF

END FOR

IF 该时刻下SFC具有无线功能

FORSk中所有待部署的VNF

IF当前位置满足无线和有线功能性约束的VNF集合为连续VNF节点所组成

该VNF集合进入待合并队列Group’

ELSE

解散该VNF集合

FOR Group’中的每个VNF集合

IF有线和无线VNF节点都满足δ(vii)>1&δ(vii+1)<1&δ(vii+2)<1

该VNF进入合并队列Group

ELSE

解散当前Group’集合

END IF

END FOR

ELSE

FORSk中的每一个有线VNF节点

IF当前位置满足有线功能性约束的VNF集合为连续VNF节点所组成

该VNF集合进入待合并队列Group’

ELSE

解散该VNF集合

FOR Group’中每个VNF集合

IF有线VNF节点满足δ(vii)>1&δ(vii+1)<1&δ(vii+2)<1

该VNF进入合并队列Group

ELSE

解散当前Group’集合

END IF

END FOR

END IF

3.2 基于缓存内容新鲜度的节点配置算法

在对用户的通信类型与地理位置进行对应的VNF节点感知后,就要对SFC中相应的节点进行配置。本文提出了基于缓存内容新鲜度的节点自适应配置算法,在主动缓存放置的时段中,如果用户发出了请求Sk,且最近的对应VNF节点中没有相应的缓存内容,则进行缓存内容的替换,并将该缓存内容的新鲜度数值赋值为10。接着遍历整个缓存内容的新鲜度矩阵,对VNF节点内的3次请求都未利用到的缓存内容资源块的新鲜度数值减去1,最后删除新鲜度数值低于阈值所对应的缓存内容资源(本文设定阈值为6)。这样不仅能够保证部署SFC的效益值更高,减少了配置VNF节点的个数,还能够提高缓存资源的利用率。

基于缓存内容新鲜度的节点配置算法(算法2)具体步骤如下:

输入:VNF节点缓存内容矩阵Z,Sk请求缓存内容B(k),新鲜度矩阵D

输出:更新的VNF节点缓存内容矩阵Z

IFB(k)被请求且节点并未有相应缓存

THEN

将B(k)缓存内容添加至矩阵Z

THEN

将D中B(k)所对应的新鲜度赋值为10

THEN

FORZ中的所有缓存内容

IF 该缓存内容已有3次未被利用

在新鲜度矩阵中对应的新鲜度数值减1

END IF

END FOR

FOR 新鲜度数值矩阵Z

IF 新鲜度数值<6

在Z中删除对应的缓存内容

END IF

END FOR

更新VNF节点的缓存内容矩阵Z

END IF

3.3 基于KSP的功耗感知虚拟链路映射算法

在VNF节点选取和配置成功后,需要对相应的链路进行虚拟映射。首先,将该时隙中的带宽矩阵转化为稀疏矩阵,删除不满足带宽要求和所选取VNF节点之间互不相通的链路,以便节省带宽资源,提高传输效率。利用基于KSP的功耗感知链路映射算法,得到时延与功耗均低于系统约束条件的虚拟链路集合,进而找到最优的映射链路。

基于KSP的功耗感知虚拟链路映射算法(算法3)具体步骤如下:

输入:待部署的所有SFC映射方案集合Sk′

输出:所要部署SFC的映射方案Sk

FOR待部署的所有SFC映射方案集合Sk′

利用KSP算法计算相应加权路径的功耗矩阵

求出最短路径跳数τ和组成链路的VNF节点集合

计算重复映射链路数量

根据最短路径更新集合Sk′

END FOR

FOR 更新后的集合Sk′

IF该Sk不具有无线功能

FORSk中的VNF节点

计算Sk功耗

计算Sk时延

END FOR

IF该Sk时延>用户时延约束条件

删除该Sk

ELSE

将该Sk放入新的集合Sk″

END IF

ELSE

FORSk中的VNF节点

计算Sk有线和无线功耗总和

计算Sk时延

END FOR

IF该Sk时延>用户时延约束条件

删除该Sk

ELSE

将该Sk放入新的集合Sk″

END IF

END FOR

FOR满足用户时延约束条件的待部署SFC映射方案集合Sk″

IF该Sk功耗为最小

映射成功,更新链路剩余资源

ELSE

映射不成功,删除该Sk的部署

END FOR

4 实验仿真

本节对本文所提方案与随机选择算法、遍历选择算法和贪婪算法(Greedy Algorithm,GA)这三种基准方案进行系统的评估比较,考虑了SFC部署的平均资源消耗、平均时延、平均可靠性、链路重映射数量、平均带宽消耗、规定时隙内映射成功率、算法时间复杂度、有线和无线业务请求数量与SFC部署成功率的关系等作为系统性能的评价指标。其中,随机选择算法不进行VNF节点的共享,仅根据业务请求类型随机选择可用节点;遍历选择算法和贪婪算法都进行VNF节点的共享,两者不同之处在于遍历选择算法会根据每一条业务请求进行全局遍历寻优,进而选择下一最优节点,而贪婪算法只对当前VNF节点的下一节点集合进行遍历寻优,选择最优的下一个VNF节点。此外,所进行对比的三种算法均不进行节点缓存内容的自适应更新和链路映射时最短路径的选择,也不考虑负载均衡。

在仿真平台上,设置边缘网络节点数为100,其中随机的40个节点拥有无线功能。随机产生用户数量和用户的通信业务需求,用户分为有线用户和无线用户,无线用户只能够与无线物理节点进行信息交互。SFC服从到达率为0.05的泊松分布,且为动态到达模式。为了减少其他因素的影响,将300次实验后的平均值作为仿真的最终结果,每次实验有40 000个时隙单位,且每个资源块是不可分割的。相应的参数配置如表1所示。

表1 仿真参数设置

图2为在各个方案下的SFC成功部署数量对平均资源消耗、平均时延、平均可靠性、平均带宽消耗和链路重映射数量这5个系统评价指标的影响情况。图2(a)为平均资源消耗对比,可见随着SFC成功部署数量的增加,本文方案的平均资源消耗均小于另外三种方法。随机选择算法由于没有考虑节点的共享,且随机选择的无线节点数量过多,导致路径损耗较大,故资源消耗最多。遍历选择算法和贪婪算法虽然考虑了节点的共享,但都忽略了负载均衡,且每次确定最佳的下一节点都要进行一次遍历,故资源消耗较多。本文方案以边缘节点资源有限作为前提,通过节点的共享和缓存资源的自适应动态调整,减少了VNF的配置个数和节点之间的跳数,故平均资源消耗最少。图2(b)为平均时延对比,可见随着SFC成功部署数量的增加,本文方案的平均时延大都优于另外三种算法。随机选择算法由于缺少了节点的共享,故平均时延最高。贪婪算法是局部最优的选择算法,在没达到局部最优之前,平均时延略小于本文算法,但达到了局部最优之后,其跟遍历选择算法一样,都需要对全局进行遍历寻优,增加了相应的时延。本文将物理节点共享给更多的VNF节点,且利用基于新鲜度的缓存替换策略,将VNF节点之间的数据变成节点内部数据进行传输,在缓存资源获取时不需要每次都进行遍历寻优,且在SFC映射时将时延权重作为评判标准,故平均时延最低。图2(c)为平均可靠性对比,可见除了随机选择算法,其他的三种方案的平均可靠性均高于0.8。因为这三种方案都在共享节点时将可靠性权重作为考虑的依据,通过优先选择高可靠性的节点来提高平均可靠性。本文方案还考虑了用户的地理位置和通信特性,区分与用户对接的邻近节点的通信特性和缓存特性,故有更高的平均可靠性。图2(d)为平均带宽消耗对比,可见本文方案由于将节点进行共享并利用了缓存自适应动态调整策略,且在SFC映射时考虑了负载均衡,故平均带宽开销均低于另外三种方案。随机算法由于为对节点进行共享,且未考虑负载均衡,故平均带宽开销最大。遍历算法和贪婪算法虽然考虑了节点的共享,但在SFC映射时未考虑节点最短路径的选择,故平均带宽消耗较高。图2(e)为各方案链路重映射数量随SFC成功部署数量的变化关系,可见本文利用基于KSP的功耗感知映射算法,在寻找最短路径时利用功耗矩阵作为约束条件,能够降低链路重映射的数量,故本文方案的链路重映射数量低于另外三种方案。

图3为各个方案稳定性的对比实验结果。为衡量部署方案的鲁棒性和稳定性,将以规定时隙内的SFC映射成功率、算法时间复杂度和不同类型、不同数量的业务请求条件下的SFC部署成功率作为评价指标。图3(a)为在规定的40 000个时隙单位内四种算法的SFC映射成功率对比,可见随机选择算法由于没有考虑节点的资源共享,也没有考虑负载均衡,因此增大了时延和资源消耗,故映射成功率最低。遍历选择和贪婪算法虽然考虑了节点的共享,但未综合考虑全局的时延与功耗,只考虑了局部的最优,因此在SFC部署中不能够同时保证时延和功耗,故映射成功率也低于本文算法。图3(b)为所进行的300次实验中四种方案的算法时间对比,可以看出遍历选择和贪婪算法的时间复杂度较高。这是因为遍历选择和贪婪选择都需要对每一个当前节点的下一跳节点进行遍历寻优,进而耗费了大量时间。随机选择算法由于其算法流程过于简单,故算法时间复杂度最低,但对比于本文所提方案,其系统性能指标均存在较大的劣势。本文所提方案由于考虑了最佳节点的选取和节点缓存资源的自适应更新,不需要频繁对节点的选择进行遍历寻优,极大地降低了最短路径的生成时间,故相较于遍历选择和贪婪算法,本文所提方案能够在保证系统性能的同时极大降低算法的时间复杂度。图3(c)和图3(d)分别为有线业务请求的SFC部署成功率对比和混合无线与有线业务请求的SFC部署成功率对比,可见在只有有线业务请求的情况下,由于随机选择算法没有共享节点,故SFC的部署需要消耗更多的资源,且时延也得不到满足,故SFC部署成功率低于另外三个方案。遍历选择和贪婪算法由于没有从全局考虑时延和功耗,故SFC部署成功率略低于本文所提方案。在混合了有线和无线业务请求的情况下,由于没有根据用户的地理位置和通信特征进行节点的选取,也没有根据业务内容的新鲜度对节点进行缓存内容的自适应动态调整,故另外三种方案的SFC部署成功率都明显低于本文所提方案。由于考虑了业务类型和用户地理位置和通信特征,且从全局对时延和功耗进行加权约束,本文方案无论是在有线业务处理场景下或是混合有线无线业务处理场景下都有着较稳定的SFC部署成功率。