面向多接入边缘计算的VNFM分布式部署方案

马 悦，张玉梅

(1.陕西中医药大学 信息化建设管理处，陕西 咸阳 712046；2.陕西师范大学 计算机科学学院，陕西 西安 710119)

移动互联网的飞速发展促使数据流量空前增长，5G多样化和动态化的网络服务对移动通信网络提出超可靠低延迟(Ultra-Reliable Low-Latency Communications，URLLC)的需求。移动多接入边缘计算(Multi-access Edge Computing，MEC)作为5G通信网络的重要支撑技术，将计算能力、存储能力“下沉”到移动边缘节点，降低延迟并提升带宽速率，为更多用户提供高可靠、低时延的网络服务。实际部署中，网络功能虚拟化(Virtual Network Functions，NFV)为多接入边缘计算的实现提供了网络架构级解决方案。欧洲电信标准协会(European Telecommunications Standards Institute，ETSI)提出在多接入边缘计算架构中部署虚拟网络功能(Virtual Network Function，VNF)实例来实现网络功能虚拟化[1]。在不改造底层物理网络的基础上分层解耦部署VNF，将各个物理资源池划分为不同的管理域，并通过在管理域上部署独立的虚拟化网络功能管理器(Virtual Network Function Manager，VNFM)实现对虚拟网络功能实例的分布式管理。

可见，虚拟化网络功能管理器实例的部署将直接影响网络性能。近年来，虚拟网络功能部署问题得到广泛研究，但是关于虚拟化网络功能管理器部署的文献相对匮乏。典型的虚拟化网络功能管理器部署算法通常以合理配置所需的计算和通信资源为目标[2]进行研究。文献[3-4]在能耗、网络流量等约束条件的限制下最大化计算和通信资源利用率。文献[5-6]聚焦于降低部署成本，设计了面向用户服务质量(Quality of Service，QoS)优化的虚拟化网络功能管理器部署方案。针对混合云架构下的虚拟化网络功能管理器部署方案，文献[7-8]研究了不同基础架构组合起来的混合云环境虚拟化网络功能管理器部署问题，但并不涉及边缘部署。在此基础上，文献[9]提出了一种虚拟化网络功能管理器部署解决方案。该方案实现了多云环境中成本效率与用户服务质量之间的折衷。上述文献聚焦于如何提高虚拟化网络功能管理器部署过程中的资源利用率和用户服务质量等。由于多接入边缘计算边缘托管的网络服务对传输时延较为敏感，而上述算法没有考虑传输时延的优化问题，因此难以满足多接入边缘计算的实际应用需求。

在多接入边缘计算架构中，为了向用户提供低时延的网络服务，运营商将部分时延敏感的网络功能“下沉”到了网络边缘，在业务面形成了分布式的虚拟网络功能部署架构。然而，传统的虚拟化网络功能管理器部署方案仅考虑了同一管理域内的时延优化问题，因此虚拟化网络功能管理器主要部署在网络中心。在多接入边缘计算场景下，上述方案无法保证边缘虚拟网络功能的管理面时延。为了解决上述问题，笔者聚焦于研究分布式云平台环境下的虚拟化网络功能管理器部署问题，旨在设计分布式的虚拟化网络功能管理器部署算法，保证多接入边缘计算架构下的管理面时延。目前，多接入边缘计算场景下的虚拟网络功能部署问题已经出现了一些研究成果，但是相应的虚拟化网络功能管理器部署问题并未得到深入研究。文献[10-12]提出边缘云架构下的虚拟化网络功能管理器部署问题应考虑相关VNFC组件在中心云基础架构物理机和多接入边缘计算服务器上的协同部署。针对边缘云和中心云的混合环境中的虚拟网络功能部署问题，文献[13]考虑到最小带宽和最大端到端延迟的要求，在边缘和中心云基础架构上引入虚拟网络功能部署算法和优化策略。文献[14]通过在传统云中部署更多的虚拟网络功能从而增加边缘云的最大利用率。文献[15]将计算资源分配给虚拟实例，并将其部署在传统云基础架构上，提高了服务可用性并降低了管理成本。在此基础上，文献[16]提出了边缘云混合架构中虚拟网络功能部署的最小延迟算法。文献[17]针对高可靠低延迟的需求，设计了一种基于遗传算法的虚拟网络功能方案，得到虚拟网络功能实例部署最小通信开销的思路。

上述研究全面地考虑了分布式云架构下虚拟网络功能部署的用户服务质量优化问题。但是虚拟化网络功能管理器功能作为NFV管理编排(MANagement and Orchestration，MANO)模块中的基础组件，需要周期性的采集所有边缘服务器的个体状态信息，形成网络全局视图。上述研究没有考虑如何优化多接入边缘计算架构下业务面VNF实例与VNFM之间的传输时延，因此难以保证NFV管理平面的实时性。

基于此，以多接入边缘计算架构下的超可靠低延迟应用场景为导向，提出了一种面向多接入边缘计算的VNFM功能分布式部署方案。首先，利用混合整数规划模型对VNFM部署问题进行建模，提出基于整数线性规划的VNFM部署模型；然后，在所提整数线性规划模型的基础上，设计了一种基于免疫优化算法的部署方案。算法综合考虑个体的抗体亲和度和抗原亲和度，通过引入更全面的个体评价机制对VNFM部署策略的多样性进行评价，并加入了相应的免疫机制，从而得出最佳VNFM实例部署方案。免疫算法在保留智能算法优良特性的前提下，有目的地利用多样性特征信息来抑制其优化过程中出现的退化现象，能够更加全面地评价个体，同时能够有效避免算法在部署过程中陷入局部最优解，提高算法性能。可见，免疫优化算法适用于解决多接入边缘计算中的VNFM部署问题。仿真结果证明，相比于量子遗传算法，免疫优化算法的个体评价机制能够更有效地描述VNFM部署问题中个体的适应度和个体间的相似度，减少算法在局部反复迭代的次数，提高算法的收敛效率和性能。

1 VNFM部署问题与模型描述

1.1 基于MEC架构的VNFM分布式部署

为了降低MEC架构下远端VNF实例与NFV管理平面之间的传输时延，笔者采用了分布式VNFM部署方法，其逻辑示意图如图1所示。其中，网络的基础设施包含多个地理上呈分布式部署的物理资源池，各个物理资源池由多个功能边缘服务器和网络转发设备组成，负责为边缘云VNF实例提供业务处理所需的计算、存储和网络资源。为了提高分布式NFV 平台的管理效率，将MANO模块中的VNFM功能抽象为分布式部署的多个逻辑模块。在VNFM功能部署的过程中，首先将各个资源池划分为不同的管理域，并通过在各个管理域部署独立的VNFM管理实例以实现系统的分布式管理，各个域的VNFM实例通过统一的服务化接口互联互通，在逻辑上形成集中的管理平面对地理上呈分布式部署的VNF实例进行集中管理。文中关注的问题是如何设计合理的部署算法，划分各个管理域并选择合适的节点部署VNFM实例，使得管理平面的传输时延最小，提高MEC架构下NFV MANO管理平面的通信效率。

1.2 基于整数线性规划的部署模型

在VNFM部署模型中，设物理网络为无向赋权图GS=(NS，LS)，其中，NS代表物理服务器节点组成的集合，LS代表服务器节点间链路组成的集合。VNFM部署请求为无向赋权图GV=(NV，LV)，其中，NV为请求的VNFM功能实例组成的集合，LV为实例间链路组成的集合。设定物理服务器的数量为n，VNFM实例的数量为m。定义n维列向量W，其中的任一元素wi表示服务器i上需要管理的VNF实例数量。定义n×m维矩阵D，其中任一元素dij表示服务器i与VNFM实例j之间的时延，同时根据服务水平协议(Service Level Agreement，SLA)中的QoS需求，设定最大时延阈值为s。最后，定义二值化n维列向量X，其中任一元素xi=1，表示在服务器i上部署VNFM实例，反之xi=0。设二值化n×m维矩阵Z，其中任一元素zij=1表示服务器i上的VNF实例由VNFM实例j负责管理。综合上述定义，VNFM部署问题可以规约为如下0-1规划模型。

优化目标：

(1)

约束条件：

(2)

zij≤xj， ∀i∈NS，j∈NV，

(3)

(4)

dij≤s， ∀i∈NS，j∈NV，

(5)

zij∈{0，1}，xi∈{0，1}， ∀i∈NS，j∈NV。

(6)

2 基于免疫优化算法的VNFM部署方案

为了获取VNFM实例部署的最小通信开销，部署方案需要确定需要部署的VNFM实例的数量、各个VNFM部署的物理服务器位置，以及每个VNFM实例的管理范围。相比于现有的智能算法[18-19](如遗传算法、粒子群算法和蚁群算法等)以种群中个体适应度为导向的寻优策略，免疫优化算法借鉴了免疫系统的多样性特征，引入了个体亲和度，能够更加全面地评价个体。笔者提出了一种基于免疫优化算法的VNFM部署方案，加入了对VNFM部署策略的多样性评价和相应的免疫机制，并用其求解上述0-1规划模型，从而得出最佳VNFM实例部署方案。

2.1 抗体群初始化

免疫优化算法是根据抗体与抗原间以及抗体之间亲和度的寻优的智能算法。针对VNFM部署问题，采用直接编码方式对抗体进行编码。编码后抗体为[α1，…，αm]，其中，任意码字αi=ni表示VNFM实例i部署在序号为ni的服务器上，m为预设的VNFM实例数量。针对有30个服务器的边缘云，预设请求的VNFM数量为4个，若编码为[2，7，9，14]，则表示在序号为2，7，9，14的4个服务器上部署VNFM实例。此种编码方式可以保证部署决策满足式(4)和式(6)的约束条件。

2.2 多样化评价

抗体与抗原亲和度：抗体与抗原之间的亲和度用于表示抗体对抗原的识别程度，在VNFM部署问题中表示求解的部署策略与优化目标之间的接近程度。针对第二节中提出的0-1规划模型，本节设计了抗原与抗体v间亲和度计算公式：

(7)

抗体间亲和度：抗体间的亲和度用于表示抗体之间的相似程度，此处采用R位连续匹配方案计算抗体间亲和度的值，即

(8)

其中，kv，s表示抗体v和抗体s中连续相同的位数，m表示抗体编码长度。在VNFM部署问题中抗体间亲和度能够有效地识别相似的部署策略，从而避免算法过早陷入局部最优，优化求解性能。

抗体浓度：抗体浓度表示种群中与抗体v相似的抗体所占的比例，即

(9)

其中，N表示种群数量，ε(·)表示阶跃函数，δ表示适应度阈值，即超过该阈值则认为抗体间表现出过高的相似性。

期望繁殖概率：在种群中，任一抗体v的繁殖概率由抗体与抗原间亲和度Av以及抗体浓度μv共同决定，即

(10)

抗体的抗原亲和度越高，期望繁殖概率越大，同时抗体浓度机制会抑制相似的抗体不断繁殖；当抗体浓度增加时，期望繁殖概率会下降。

2.3 基于免疫优化算法的VNFM部署

基于免疫优化算法的VNFM部署方案如算法1所示，算法输入参数为云平台的物理拓扑和时延矩阵，输出参数为最优的VNFM部署决策矩阵。其中，第①、②行对免疫优化算法所需的基本参数进行了初始化，第③～⑨行实现免疫优化算法的迭代进化。第⑤行中算法随机从种群中选择两个抗体进行配对，并随机设置任意单点码位作为交叉点，根据预设的交叉概率交换两个抗体交叉点处的编码字段，从而产生出两个新的抗体。为了防止算法快速陷入局部最优，第⑥行采用了轮盘赌法选择进行变异操作的码位。轮盘赌选择机制是一种放回式随机采样方法。利用期望繁殖概率表示其变异概率，个体期望繁殖概率越高，其发生变异的可能性越大。

算法1基于免疫优化算法的VNFM部署。

输入：云平台物理拓扑，时延矩阵D。

输出：最优VNFM部署决策矩阵X*和Z*。

① 初始化免疫优化参数：种群规模NIND，最大进化代数MAXGEN，惩罚因子η和适应度阈值δ等。

② 初始化编码种群中的全部抗体。

③ for gen=1∶MAXGEN

④ 计算各个抗体的期望繁殖概率。

⑤ 采用随机交叉法执行抗体编码字段交叉操作。

⑥ 采用轮盘赌法在抗体上选择码位执行变异操作。

⑦ 计算新生成抗体的期望繁殖概率。

⑧ 用子代中适应度高的染色体替换父代中适应度低的染色体，形成新的种群。

⑨ end for

⑩ 保留最终代中最优染色体，返回其对应的VNFM部署决策变量X*和管理关系Z*。

图2 物理网络拓扑图

3 性能评估及分析

3.1 仿真环境

在Intel(R) Pentium(R) 3.40 GHz CPU，4 GB内存的PC机上仿真，使用GT-ITM生成物理网络，拓扑结构如图2所示。图中物理拓扑共包含31个物理节点，每个节点表示一个边缘高性能服务器配置参数选用华为2 288H V5型服务器，28核 2.2 GHzCPU，64 GB内存，2 TB硬盘，实验所用物理拓扑如图2所示。免疫优化算法参数设置如下：种群规模设为50，记忆库容量为10，最大迭代次数为100，交叉概率为0.5，变异概率为0.4。

3.2 结果分析

将VNFM数量设置为6个，分别为经过免疫优化算法和量子遗传算法计算后得到如图3和图4所示的VNFM部署示意图。从拓扑管理的角度分析，当节点位置符合“域内聚合、域间离散”时，对网络拓扑进行管理的效果最佳。对比图3和图4，可知图3所示免疫优化算法的部署结果能够更好地实现网络拓扑的管理域划分。

图3 免疫优化算法部署示意图

图4 量子遗传算法部署示意图

图5给出了当前状态下免疫优化算法、量子遗传算法以及蚁群算法的通信开销和收敛性对比图，其中通信开销由式(1)定义，表示VNFM管理面的总体通信时延。通过对比可以得出，文中所提基于免疫优化的VNFM部署方案能够在量子遗传算法和蚁群算法的基础上降低VNFM实例间通信的总体时延。此外，所提免疫优化算法能够提高收敛效率，更快地获取VNFM部署的最优解。仿真结果证明，相比于量子遗传算法和蚁群算法，免疫优化算法的个体评价机制能够更全面和有效地描述VNFM部署问题中个体的适应度和个体间的相似度，减少算法在局部反复迭代的次数，提高算法的收敛效率和性能。

图6给出在部署不同数量VNFM实例的场景下，免疫优化算法、量子遗传算法和蚁群算法的通信开销对比情况。如图6所示，随着VNFM数量的上升，3种算法的通信开销都呈现出先下降后上升的趋势，这是由于初始状态VNFM实例的增多降低了远端节点与管理平面之间的通信时延，从而实现系统通信开销的下降；而随着VNFM实例的持续增加，管理平面内部通信时延显著增加，而此时VNFM节点的增加仅能少量地降低管理平面与远端节点之间的通信时延，因此系统的总体通信开销反而呈上升趋势。比较3种算法，可见免疫优化算法的通信开销较量子遗传算法和蚁群算法更低。且相比于其他两种算法，免疫优化算法引入了更全面的个体评价机制，综合考虑了个体的抗体亲和度和抗原亲和度，有效地避免算法过早陷入局部最优解，从而在全局的角度更加逼近最优解。

图5 算法收敛对比

图6 网络通信开销对比

对比量子遗传算法与免疫优化算法的进化过程，量子遗传算法采用了单一的适应度函数描述VNFM部署问题的优化目标，且采用了编码长度较长的量子编码方法描述VNFM的部署结果。相比之下，免疫优化算法采用了抗原-抗体适应度相结合的复合方法描述该问题的优化目标，同时采用了编码长度较短的整数编码方式表示部署结果。通过综合对比两种算法在收敛曲线和通信开销方面的性能可以得出结论，本文提出的免疫优化算法更适合分布式VNFM部署问题的求解。

图7 算法执行CPU时间

图7给出了7种算法执行的CPU时间对比，对比实验中3种算法的最大进化代数都固定为50代。由图7所示，本文所提免疫优化算法的CPU运行时间较其他两种算法更低。相比于量子遗传算法，免疫优化算法不需要进行量子旋转门和个体之间的矩阵内积运算，降低了算法的复杂度，因此提高了算法的运行效率。与蚁群算法相比，在VNFM节点较少的场景中，因为免疫优化算法的适应度评价指标更加复杂，其消耗的CPU时间相对更长，但是随着VNFM节点的增多，文中提出的免疫优化算法占用了更少的CPU时间。其主要原因在于免疫优化算法的评价方式更加全面，算法不易陷入局部最优，能够更快地收敛到最优解。

4 结束语

针对MEC架构下的VNFM功能部署问题，笔者提出一种基于免疫优化算法的VNFM部署方案。首先，利用混合整数规划模型对VNFM的部署问题进行建模，给出基于整数线性规划的VNFM部署模型；然后，在所提整数线性规划模型的基础上，设计了一种基于免疫优化算法的部署方案。所提免疫优化算法在保留智能算法优良特性的前提下，借鉴免疫系统的多样性特征，引入了个体亲和度，同时关注系统整体及单个VNFM性能。通过引入更全面的个体评价机制对VNFM部署策略的多样性进行评价，并加入了相应的免疫机制，从而得出最佳VNFM实例部署方案。仿真结果表明相比于量子遗传算法，免疫优化算法的个体评价机制能够更有效地描述VNFM部署问题中个体的适应度和个体间的相似度；算法能够有效避免算法在部署过程中陷入局部最优解，提高算法性能；并且能够加速算法收敛效率，降低算法执行的CPU时间。但是本文方案不能智能化地确定所需的VNFM实例数量。后续工作中将针对该问题进行改进。