移动边缘网络中基于用户移动的服务功能链迁移策略*

周冬杨,潘显兵

(1.重庆移通学院 数字经济与信息管理学院,重庆 401520;2.公共大数据安全技术重庆市重点实验室,重庆 401420)

0 引 言

物联网传感器的爆炸式增长和智能设备的广泛普及造成移动网络的流量迅速增加。因便携式移动设备的计算和存储资源容量有限,可以将任务卸载到远程云进行处理,但这不可避免地会导致响应延迟,降低用户体验[1-2]。移动边缘计算(Mobile Edge Computing,MEC)[3]是一种新兴的云架构,通过在基站(Base Station,BS)侧部署MEC服务器,为移动用户提供计算和存储资源,显著缩短响应延迟,满足多样化的业务需求。

网络功能虚拟化(Network Function Virtualization,NFV)技术用虚拟机中的软件替代传统硬件实现的网络功能,称为虚拟化网络功能(Virtual Network Function,VNF)。通常,业务流量需要由多个VNF按照逻辑顺序进行处理,称为服务功能链(service Function Chain,SFC)。NFV与MEC的结合可以减少云服务提供商(Cloud Service Provider,CSP)核心网的服务延迟和流量压力,提供方便灵活的VNF管理,大大降低CSP的运营费用。

由于边缘云(Edge Cloud,EC)的资源有限,合理分配EC资源以满足尽可能多的用户需求是至关重要的。另外,当用户跨基站移动时,需决定由以前的EC或迁移到新的EC执行流量处理。第一种情况,SFC没有迁移,以牺牲用户通信时延为代价节约了CSP的网络成本。第二种情况,用户通信延迟是最优的,但有潜在的SFC数据迁移成本。因此,移动用户的延迟和运营成本之间存在一个权衡。同时,为了让用户不能直接感知因SFC迁移过程造成的服务中断,需要进行无缝迁移[4]。

当前,部分文献主要关注MEC网络中VNF的映射[5-6],然而没有考虑到用户的移动性,这是MEC网络的一个基本特征。随着用户的移动,SFC固有的映射方法可能会导致用户服务延迟严重恶化。

文献[2]主要研究用户移动时VNF的最优迁移时间,但以整体网络迁移成本作为优化目标,不能保证单个移动用户的QoS总是可靠的。文献[8]使用图划分算法最小化VNF在集群之间迁移的数量,不能保证具有严格延迟要求的用户服务。

与上述研究不同,本文综合考虑迁移成本和服务时延两个指标,提出了基于用户移动的SFC无缝迁移策略。

1 系统模型

1.1 网络模型

用无向图G=(B∪V,L)表示移动边缘云网络,其中B为BS集合,V为EC集合,L为BS之间的物理链路集合。

每个基站b∈B起到服务接入和转发的作用。对于每个ECv∈V,用Cv表示最大的计算能力,可用于实现移动用户的SFC。为了节约CSP的成本,EC的数量小于BS的数量,即不是所有的BS都绑定EC。此外,BS和同位EC之间的传播延迟可以忽略不计。物理链路l∈L是一条高速光缆连接各个BS,将其表示为五元组{s,d,bl,dl,cl},其中s,d表示源BS和目的地BS,bl是最大带宽,dl是固有的传播延迟,cl表示数据在链路l上的传输成本。

1.2 移动用户模型

移动用户i的移动轨迹表示为Li={li(t)}。li(t)∈B为用户i在时隙t时的临时位置,此时,通过最近的BS接入网络,服务流量vi(t)通过相应的EC处理。随着用户移动,接入的BS会进行切换。

2 问题描述及模型定义

2.1 问题描述

假设每个移动用户只请求一种SFC类型,且该用户具有较高的移动性和服务延迟敏感性。当用户i在时隙t移动到一个新的临时位置时,如果业务流量vi(t+1)仍然由之前的EC处理,可能会违反用户u的端到端延迟容忍。因此,需要根据用户u的配置文件确定最优EC的位置。也就是说,当用户跨越EC,即vi(t)≠vi(t+1),需要一个合理的迁移策略来决定何时以及如何选择相关的路径对SFC进行无缝迁移。

2.2 相关参数定义

移动用户请求ri的端到端延迟主要分为四部分:接入延迟、通信延迟、执行延迟和迁移延迟。用户i将服务请求数据Qi,t(以b为单位)传输给相应的EC进行计算。

接入延迟dacc(i,t):表示请求ri在用户i和附近的无线信道与BSli(t)之间传输流量数据所花费的总时间。无线信道的最大数据传输速率ri,t(单位:b/s)为

(1)

式中:W为信道带宽;Pi为用户移动设备的发送功率;gt为时隙t无线信道增益;σ2为噪声功率。因此,接入延迟表示为

(2)

(3)

从本地BSli(t)到选定EC,流量vi(t)的传播延迟和传输延迟表示为

(4)

(5)

则总通信时延dcom(i,t)为

(6)

执行延迟dpro(i,t)是在相应的EC上处理用户数据包所花费的时间。设EC的最大处理能力为fi,t(单位:Hz),处理密度为wi(Hz),CPU分享率是ηi,t,则处理延迟dpro(i,t)表示为[9]

(7)

(8)

(9)

式(9)中:Δt表示时间间隔的大小。

(10)

(11)

(12)

(13)

未完成数据的新的执行延迟为

(14)

用zi(t)来指示是否触发迁移:

(15)

因此,最终在时隙t的迁移延迟dmig(i,t)表示为

(16)

用C(i,t)表示移动用户i的SFCi迁移成本。C(i,t)也是SFCi状态数据在路径上的传输成本,用以下公式计算:

(17)

2.3 问题模型设计

基于t-1时隙迁移的SFC映射,为时隙t需迁移的用户i找到一个最优的迁移路径集Pi,t,目标是使迁移成本与用户请求ri的端到端延迟之和最小。根据上一节的描述,用户请求ri在时隙t的总延迟为

D(i,t)=dacc(i,t)+dcom(i,t)+dexe(i,t)+dmig(i,t)

(18)

因此,MEC网络中的SFC迁移问题用公式(19)表示,约束条件为公式(20)～(25)。

O(S)=α1D(i,t)+α2C(i,t)

(19)

s.t. C1:xp,l,i(t)∈{0,1},yp,l,i(t)∈{0,1}

(20)

C2:D(i,t)≤Di

(21)

(22)

(23)

(24)

(25)

3 算法设计

3.1 算法概述

给定一个MEC网络G=(B∪V,L)和一个支持NFV的用户请求ri,目标是最小化用户在边缘网络上移动时的请求延迟和网络成本。要解决这个问题,有两个挑战:一是在整个时间范围T中触发SFC迁移的时机;二是如何选择SFC的迁移路径。

3.2 迁移触发

通过设计合理的SFC迁移触发机制,可以避免不必要的SFC迁移(为云服务提供商节省迁移成本)。当服务请求延迟大于延迟容忍阈值Di时,就会触发SFC跨节点迁移,而不是在移动用户i跨BS移动时就考虑迁移,从而影响移动用户的QoS。换句话说,SFC在时隙t满足D(i,t)>Di时迁移将被触发。

3.3 迁移算法

SFC的迁移实际上可以看作是有状态数据的迁移。给出迁移源EC和目标EC后,可以选择多个数据迁移路径并发执行,保证服务数据的无缝迁移。为此,提出了一种基于Dijkstra 的迁移算法。迁移算法(Migration Strategy Algorithm,MSA)的伪代码如下:

Output 数据迁移路径的集合:Pi,t;

1G′←通过阶段1推导出网络加权图;

6 return null;

7 end

10 更新网络加权图G′(阶段4);

11 end

12 returnPi,t;

MSA核心思想基于以下四个阶段:

阶段1：得到MEC网络的加权图(代码第1行)。考虑到网络链路的两个参数(数据迁移延迟和代价)的不同性质,将这两个参数集成为一个新的边缘参数。首先将这两个参数归一化到一个统一的量级,以得到相同规格的链路传播延迟和传播代价。归一化公式表示为

(26)

(27)

3.4 算法时间复杂度分析

4 性能评估

4.1 仿真设置

4.2 结果分析

平均SFC延迟如图1所示,MSA算法的结果是最好的,ODA的性能好于RBA和GBA。随着移动用户数量的增加,SFC请求的平均时延基本保持稳定,表明该模型和算法在不同规模场景下可以有效地改善用户体验。

图1 SFC的平均延迟比较Fig.1 Average latency comparison of SFC

整体迁移成本如图2所示,与移动用户数量近似成比例。原因是用户数量越多,在相同的时间间隔内迁移的数量就越多。此外,MSA的迁移代价最小,RBA和GBA代价最大。

图2 迁移代价比较Fig.2 Comparison of migration costs

执行时间如图3所示,MSA执行时间优于GBA算法;与ODA算法相似,随着网络节点的增加,每个算法的执行时间都会增加。

图4显示了权重参数α对MSA算法的平均延迟和总代价的影响。通过将α1从0增加到1,MSA算法更加关注平均SFC延迟,从而平均SFC延迟减小,然而总体迁移成本会增加。因此,CSP可以通过合理调整两个目标的权重参数来强调自己的偏好。

图4 权重参数α对MSA算法的影响Fig.4 The impact of weight parameter α on MSA algorithm

5 结 论

本文将MEC网络中的SFC迁移问题表述为一个考虑用户移动性的数学模型。为了实现无缝迁移,提出了MSA算法来计算SFC迁移路径,目标是最小化SFC的平均延迟和CSP的迁移成本。仿真结果表明,考虑用户移动性的MSA算法能够在保证服务延迟的同时有效地降低网络成本。