MEC 中基于改进遗传模拟退火算法的虚拟网络功能部署策略

陈卓，冯钢，刘怡静，周杨

（1.重庆理工大学计算机科学与工程学院，重庆 200433；2.电子科技大学通信抗干扰技术国家级重点实验室，四川 成都 710077；3.奥本大学计算机科学与软件工程学院，奥本 36849)

1 引言

移动边缘计算（MEC,mobile edge computing）作为一种新的云服务模式，将传统集中式部署和管理的云端资源分布式地部署至无线接入网（RAN，radio access network），使移动业务就近得到处理，从而获得良好业务体验[1-2]的同时降低了回程网络的网络负载[3]。将网络功能虚拟化（NFV,network function virtualization）技术[4]应用于MEC，运营商能将提供服务所需的IT 资源以虚拟网络功能（VNF,virtual network function）的形式快速实例化，这进一步提升了MEC 的服务弹性。将服务节点成簇互联形成集群化的MEC 网络[5-7]能根据业务所需的网络功能类型及业务量的变化情况动态调整VNF 的实例化规模，使业务流尽可能地在MEC 集群内完成端到端的服务从而达成就近高效服务的目标。但集群化的MEC 的部署需要结合移动应用的请求位置分散且对资源的需求动态变化等特点，同时还存在着单个MEC 集群的IT 资源受限、MEC 集群之间的网络资源受限及多个VNF 需根据业务类型进行逻辑关联等诸多限制，因此，在集群化MEC 网络中合理部署VNF 和进行业务流传输路径的优选，为移动业务提供最优的端到端服务时延颇具挑战。目前，缺乏针对性的研究工作，亟需深入探讨。

在集群化的MEC 网络中，本文以为时延敏感类移动业务提供低时延服务为目标，基于开放Jackson 排队网络建立了业务流的端到端时延的数学优化模型。通过将该优化问题归结为一个二维背包问题（2KP,twodimensional knapsack problem），从而证明其NP 性，进一步提出了一种集群化部署的MEC 网络中通过合理部署VNF 及业务流路径选择的策略——iGSA（improvedgenetic and simulated annealing），该策略结合了遗传算法和模拟退火算法分别在全局解和局部解的搜索能力的优势，通过对服务节点的提前映射机制避免了在节点部署时可能带来的MEC 网络拥塞，同时通过个体的约束性判断和纠正遗传的方法避免了局部最优的出现。在多个网络场景下的对比实验表明，iGSA 策略均能在单个MEC 集群内或多个MEC 集群之间，通过优化改善VNF 部署和业务流的路径选择提供更低的业务流端到端时延，有效地改善了移动业务的体验。

2 相关研究工作

在集群化部署的MEC 网络中提供低时延服务所面临的挑战及具有智能特征的算法在大规模系统中快速求得优化解方面所具有的独特优势形成了本文研究方法的依据。与本文相关的工作可按照MEC网络的部署场景和VNF 的部署方法进行分类讨论。

在MEC 网络场景类似的工作介绍如下[5-7]。文献[5-6]将NFV 引入边缘节点并建立起虚拟化MEC网络架构，通过构建服务功能链（SFC,service function chain）为移动边缘应用提供就近的IT 弹性服务。文献[5]侧重于通过SFC 实现缓存服务改善移动业务的体验，而文献[6]则着重从主动故障恢复机制设计方面，探讨提升虚拟化MEC 网络的系统可靠性问题。文献[5-7]在集群化部署的MEC 网络场景下，力图通过计算最优的MEC 集群数量来提高业务流的服务质量。但局限在独立的MEC 集群中开展研究，缺乏对更一般化的MEC 部署场景中的相关问题进行探讨。另外，和中心化的云服务相比较，MEC 最显著的优势是能够为用户就近提供低时延服务，因此，本文从MEC 的主要功能特性出发，研究并提出改善集群化部署的MEC 网络中端到端服务时延的策略。针对VNF 的优化部署方法，相关工作参考文献[8-12]。其中文献[8-10]针对不同类型的业务请求，分别从效用最大化、能耗最低及能够容纳的业务流最大化等角度进行了研究，并提出了将预先定义了次序的多个VNF 进行链接部署，建立起SFC 的策略。文献[11]通过优化多个微服务提供服务的时序，以达到改善移动应用服务体验的目的。文献[12]则借助强化学习方法研究了VNF 部署过程中虚拟节点到物理节点的优化映射和实例化的问题。上述研究工作[8-12]的网络场景是IT 资源（节点计算资源、节点存储资源和网络带宽）相对充裕的数据中心网络或移动核心网络，其关注的重点集中在有效提升虚拟化的IT 资源使用效率问题或提高整个系统服务能力的问题上，所采用的方法通常是将多个物理指标转化为统一的系统开销和系统收益，并建立优化模型加以分析。与之相比，本文所研究的处于网络边缘的MEC 节点IT 资源相对稀缺，网络系统在提供低时延端到端服务的同时，合理分配IT 资源显得尤其重要。而这涉及在MEC 集群内和MEC 集群之间的VNF 优化部署及业务流虚拟路径的合理选择。

与已有工作相比较，本文的创新性主要体现在以下2 个方面。1)在多个MEC 集群共存的边缘网络场景下，面向移动业务请求位置分散及对IT 资源需求动态变化的特点，通过排队网络模型对端到端的服务时延进行了形式化分析并建立最优化模型。2)分析求证了1)中优化问题的NP 性，并提出了一种易于部署的快速求解策略——iGSA。该策略通过将遗传算法和模拟退化算法合理的结合，在进行全局最优解搜索的同时有效地提高了求解效率并降低了运行时间，这对在大规模MEC 网络中进行快速的VNF 部署决策具有积极的借鉴意义。

3 模型化分析

3.1 网络场景描述及形式化定义

本文考虑集群化部署的MEC 网络场景。如图1所示，MEC 集群化部署在移动通信网络边缘且和一个或多个eNode B 连接[6]，MEC 集群通过PDN-GW（packet data network gateway）和云化的5G 移动核心网连接。一个MEC 集群可以包括若干个虚拟化MEC 节点。另外，MEC 集群之间通过网络连接，具备多个MEC 集群之间协作的能力。与云化的数据中心网络或移动核心网中的IT 资源可近乎认为无限不同的是，MEC 集群中节点数量和能提供的IT 资源都是受限的。MEC 集群优先在本集群内完成对请求业务的服务，当资源无法满足时，则利用其他MEC 集群的可用IT 资源构建新的VNF 完成服务。整个MEC 集群的资源统计和分配由位于移动核心网中的网络控制器实现[13]。集群化的MEC部署方式，能够跨越多个eNode B 和网络区域，为时延敏感类移动业务提供端到端的低时延服务，这对智能车/无人驾驶这类时延敏感类应用尤其重要。

将一个集群化部署的 MEC 网络定义为G={G1,…,Gg}，其中g为集群的数量，Gn表示第n个MEC 集群。定义一个无向图Gn=（Vn,En），其中Vn和En分别为MEC 集群Gn中的边缘节点和集群内网络链路。(u,w)表示2 个边缘节点u和w之间的链路，此外，u和w可以属于同一个或不同的集群MEC。lu,w表示链路(u,w)的可用网络带宽资源，边缘节点u和w的距离表示为Du,w。nv(v∈V)表示用于构建VNF 的通用服务节点（即虚拟机）数量。Mn表示在MEC 集群Gn中由边缘节点经虚拟化后的通用服务节点集合，对于MEC 集群Gn中某个通用服务节点m(m∈Mn)，当前可用计算资源表示为。集群化部署的MEC 网络为各类移动业务提供服务，以H表示MEC 网络在时间T内收到h个移动服务请求，H={d1,d2,…,dh}。对于服务请求di(di∈H)的入口节点和出口节点分别用Ii和Ei表示，Ii到Ei的路径表示为Pi，di的数据率为Ri。根据不同移动应用业务的需求，多个VNF 按照某种次序从逻辑上连接成一种串行结构或并行结构的SFC[13]，其中采用并行连接有助在MEC 网络中提高时延敏感类移动业务的服务效率。如图2 所示，为服务请求di提供服务的SFC 表示为Si={Si,1,Si,2,Si,3,…,Si,K}，其长度表示为|Si|，其中Si,j(1≤j≤K)表示SFC 上的某一个VNF 或经并行连接后为di提供服务的多个VNF 组成的集合，例如图 2 中的。假设在时间T内在MEC 网络中能建立不同类型的VNF，用集合F表示。对于某一类型的 VNFf(f∈F)能最多被实例化建立|Nf|个，定义fk为建立类型为VNFf(f∈F)的第k个实例，其计算资源占用量表示为表示fk和之间的通信所占用网络带宽，∀f,f'∈F，1≤k≤|Nfk|，1≤k' ≤|Nf'|。定义矩阵B为G中各条链路的带宽占用量。定义I(Si,j)为di提供服务的SFC 的路径Pi中对应的通用服务节点的索引。对于di的业务流按指定的顺序遍历多个 VNF，即I(Si,j)≤I(Si,j')，∀Si,j,Si,j'∈Si，j＜j'。

图1 集群化部署的MEC 网络框架

图2 MEC 集群中串行或并行逻辑连接的多个VNF

3.2 服务时延模型

移动业务通过集群化MEC 网络实现端到端服务的过程中产生的时延包括业务流数据分组在VNF 处等待处理的排队时延、业务流数据分组接受VNF 的处理时延及业务流数据分组在MEC 集群内和MEC 集群之间传输产生的时延。特别说明的是，对于VNF 在通用服务节点之上的运行部署可能带来不同影响程度的处理时延，在评估集群化部署的MEC 网络中端到端服务时延时必须要将其纳入进行考虑[14-15]。

首先业务流从入口节点到出口节点需经过一条SFC 中的多个VNF 进行处理，每个VNF 在处理业务流时将产生处理时延。本文基于M/M/1/c 类型的Jackson 排队网络[15]对业务流在MEC 网络中的处理时延进行建模，将一个MEC 网络中的VNF 视作服务节点，假设业务数据分组到达该VNF 的过程是一个泊松过程。对于VNFfk，定义λf,k和uf,k分别表示其平均到达率和平均服务率，且。为保证VNF 服务的系统稳定性，有ρf,k＜ 1。对于MEC 网络中的某个VNF，输入流量来自入口节点直接导入，也可能来自同集群或邻居集群的VNF流量输出，因此，定义Pjw表示业务流在VNFj完成处理并输出至VNFw的概率，定义表示从MEC入口节点到VNFw的流量。VNFw的输入流量速率可表示为

则在VNFfk的缓存队列中的数据分组平均数可表示为

V NFfk可运行部署在节点w之上，则fk的服务率导入至物理节点w可表示为，其中R(w)由对业务流的传输能力决定，更详细的计算方法可参考文献[15]。由Little 定理[16]可得到VNFfk的处理时延，则有

其中，λi表示第i条业务流的速率，表示di需要fk提供服务，则表示di不需要fk提供服务。则对于移动业务请求di的处理时延可表示为

基于M/M/1/c 排队网络进行模型化分析，单个VNF 的平均排队时延可表示为

其中，qj表示当有j个用户到达系统时的平滑概率[16]，则业务请求的排队时延可表示为

本文定义了一个由二元决策变量组成的矩阵A，矩阵中的任意元素为，且有表示业务流fk经由MEC 集群n中的通用服务节点u进行处理，表示业务流fk没有流经MEC 集群n中的通用服务节点u。另外，定义二元决策变量表示映射到底层网络链路lu,w，表示没有映射到底层网络链路lu,w。

业务请求的传播时延可表示为

其中，p表示信号在物理链路上的传输速率，Du,w表示物理链路的长度，E表示整个MEC 集群内的网络链路组成的整体集合。

在集群化部署的MEC 收到多个业务请求的情况下，对于存在各种资源限制的集群化部署MEC 网络中，本文通过VNF 的部署和业务流路径的选择优化业务流端到端服务时延。该最优化模型可表示为

该优化模型中，式(9)表示同一个MEC 集群中的2个通用服务节点间的链路带宽资源限制。式(10)表示MEC 集群之间的链路带宽资源限制。式(11)表示MEC 集群n中的节点u上当前已部署的一个或多个VNF 占用的计算资源不能超过其计算资源总量。式(12)表示MEC 网络中除入口节点和出口节点之外所有活动节点需要满足流量守恒。式(13)和式(14)表示服务请求仅从一个入口节点进入MEC网络且仅从一个出口节点离开集群化部署的MEC网络。式(15)要求一条SFC 业务流需经过其预定义的所有VNF。式(16)表示业务请求的时延约束。式(17)和式(18)分别表示需要具备可行的链路和节点映射。

3.3 NP 性讨论

在运筹学领域，多维背包问题（MKP,multidimensional knapsack problem）是一个经典的优化问题，其求解目标是在满足各项资源约束的前提下,从候选对象集中找出可以使目标价值达到最大（或最小）的对象子集。该问题已被证明是一种 NP-Hard[17]问题。

在3.2 节建立的最优化模型中，集群化的MEC网络同时为多条业务流提供端到端服务，并为业务流服务的多个VNF 需求同时占用计算处理资源和转发业务流的链路带宽资源。由于VNF 部署于MEC 网络中的通用服务节点之上，因此这2 种资源的占用分别不能超过通用服务节点的可用计算资源和通用服务节点之间的物理链路带宽（包括MEC集群内和MEC 集群间的链路带宽）。假设MEC 集群中能为第i条业务流提供服务的通用服务节点为n个，r1,j表示为业务流提供服务需占用第j个通用服务节点的计算资源，r2,m和r3,m分别表示为业务流提供服务第j个通用服务节点需占用的MEC 集群内和MEC 集群间的带宽资源。定义xj表示通用服务节点xj是否被选中用于部署为业务流提供服务的VNF。由于业务流的端到端服务需经过多个部署了VNF 的通用服务节点，因此定义pj表示当业务流通过通用服务节点xj产生的时延，则式(8)所描述的最优化问题可简化为，满足约束条件I：和约束条件II表示通用服务节点被选中，xj=1表示通用服务节点未被选中。若进一步将服务业务流对于MEC集群内和MEC集群间的链路带宽资源占用视作一类资源，则式(8)简化后的最优化问题是一个2KP。根据MKP 问题的NP 性，因此本文所描述的在集群化部署的MEC 网络中的业务流端到端时延最小化问题也是一个NP-Hard 问题。

4 基于遗传模拟退火算法的部署策略

第3 节所定义的问题难以在多项式时间复杂度内找到全局最优解。而当问题的规模较大时，若采用贪心法或者枚举法等精确算法的运行时间代价较高，很难在集群化MEC 网络中进行实际部署。因此需要采用相应的近似算法对其进行求解。而以模拟退火算法[18]和遗传算法[19]为代表的智能算法近年在多个领域得到了广泛有效的应用。其中，模拟退火算法模拟固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性来达到寻找全局最优或近似全局最优的目的。若在模拟退火算法的运行过程中融入遗传算法，称为遗传模拟退火算法[20-21]。

本文所研究的问题从本质上是根据业务流类型和性能约束条件，按照某种预定义顺序将多个VNF 映射到多个MEC 通用服务节点之上，实现时延最优的离散优化问题。在求解该优化问题时，需要权衡好求解方法的执行效率和求解质量。本文所提的iGSA 策略做了2 个规定：1)依据业务请求到达MEC 网络的时间先后顺序进行分析，如果多个业务请求同时到达，则针对这些请求所形成的业务流的总时延为优化目标；2)当一个MEC 群集中已实例化的VNF 资源不足以满足服务需求时，则采用在当前MEC 集群中新开启通用服务节点并实例化VNF 或将业务流引导至相邻MEC 集群。iGSA策略设计时在2 个方面做了性能改进，一方面在K最短路径的选择和业务流的引导之前进行在通用服务节点的映射（即虚拟机的映射），以避免网络拥塞；另一方面对不符合约束的个体加以纠正，然后将纠正的个体放入下一代个体中，以避免陷入局部最优。iGSA 策略的主要步骤包括编码、选择复制、交叉、变异和可行性检测。

4.1 编码

设第k代种群中的个体数目为N，这里每个个体即为nv×mf染色体矩阵，mf表示需要使用多少个VNF，nv表示当前已经开启的通用服务节点数量。矩阵Qk={A1,A2,…,Ak}表示个体，第k代种群的第r个个体表示为

4.2 选择复制

其中，tk表示状态k下的温度，而初始的温度值定义为，Z为一个常量，，其中。

4.3 交叉

本文使用多行矩阵杂交，例如使Qk中的和进行配对，并且将相对应的行以概率Pc=0.6进行互换。种群中2 个染色体之间的交叉过程如下

4.4 变异和可行性检测

本文假设突变的概率Pm=0.01。对于任何个体，需要判断是否发生了突变。如果发生了突变，就需要对该个体进行可行性检测。

在交叉和变异操作之后，需要判断这些新个体是否满足资源限制条件。对于一个给定的染色体，可以得到VNF 映射策略，从中可进一步获得决策变量的值，从而判断是否满足通用服务节点映射的约束。如果不满足，则节点不满足计算资源限制，并且将对应于这些节点的行元素从1 随机校正为0，直到满足节点计算约束。通过VNF 的映射可以获得相应的最优网络链路映射，然后为每条业务流在K条最短路径中选择合适的路径匹配，在满足链路和时延约束的同时最小化适应度函数。以这种方式，在第一阶段中将纠正的个体和链接映射策略重复至下一代。在集群化部署的MEC 网络中，iGSA策略的时间复杂度为O(n2)，其中n表示通用服务节点的数量。对于通用服务节点规模较小的MEC 网络而言，该算法的计算复杂度在可接受的程度内。iGSA 策略的伪码如算法1 所示。

算法1基于遗传模拟退火的启发式策略——iGSA

输入集群化部署的MEC 网络通用服务节点和链路信息，各条链路的带宽占用量矩阵B，某个MEC 集群Gn中某个通用服务节点m（m∈Mn）当前可用计算资源，VNF 的类型集合F，SFC 集合（包括SFC 长度、SFC 类型和Ri）。

输出SFC 的部署策略Mbest和Bbest，以及对于在[t,t+T]时间间隔内到达的业务请求的端到端时延预估值tavg

5 实验与性能评估

5.1 实验方法及仿真参数设置

本文通过 Matlab 建立数值仿真环境评估iGSA 策略的性能。实验基于Congent[22]生成MEC集群网络的拓扑。实验生成了2 种类型的网络（网络I 和网络II）以评估算法在不同MEC 集群网络规模下的表现，其中网络I 包括3 个MEC 集群，部署30 个通用服务节点、55 条集群内和集群间的链路，集群内的带宽资源参数在10～200 Mbit/s 内随机选取，集群间的带宽资源参数在10～100 Mbit/s内随机选取。网络II 的MEC 集群数量为10 个，部署200 个通用服务节点、355 条集群内和集群间的网络链接，集群内的带宽资源参数在1～10 Gbit/s内随机选取，集群间的带宽资源参数在200 Mbit/s～1 Gbit/s 内随机选取。2 种网络中的服务功能链SFC 的平均长度为4。SFC 的类型、MEC 网络中通用服务节点的计算资源、不同类型VNF 所需计算资源和VNF 之间的关联关系等参数从各自的区间内随机选择。与文献[23]类似，集群化部署的MEC 网络节点之间的传播时延与其链路距离成比例，通过乘以在区间[0.8,1.5]中取得的随机数引入适当的随机性。本文参考文献[24]，服务请求所需的流量服从幂率分布，设置α=2.1产生了xmin=10 Mbit/s 的服务请求。随机地在MEC集群中选择一个服务请求的入口网元和出口网元以模拟不同类型的移动业务。另外，突变概率为0.01，MEC 群集之间和内部的交叉概率分别设置为Pc=0.6 和Pc=0.8，温度变化系数ξ=0.45。

实验中使用以下几种典型策略进行对比以客观评估 iGSA 策略的性能。1)AH 策略（AH strategy）[25]，该算法在一个MEC 网络中优先选择具有最多剩余资源的可用节点部署VNF 和建立SFC。和iGSA 策略相比较，AH 策略减少了VNF的处理时延，但没有考虑处理时延和传播时延的整体优化，特别没有考虑多个MEC 集群共存的一般化场景。2)贪心策略（greedy strategy）：集群化部署的MEC 网络逐个处理时间T内的服务请求，并依次最小化每个服务请求的端到端时延。3)随机策略（random strategy）在时间T内收到i个服务请求，该策略在满足计算资源限制、链路带宽资源限制和服务请求的时延限制的通用服务节点用于部署VNF 和建立SFC。

5.2 实验结果与分析

本文首先探讨在同一时间段内，到达集群化部署MEC 网络中的服务请求数与平均端到端服务时延之间的关系。图3 显示了在网络I 场景下，获得服务的平均时延与服务请求数量之间的关系。从图3 可以看到，服务的平均时延随着服务请求的数量增加而增加，这主要是因为随着业务请求的增加，当一个MEC 集群中的计算和网络资源不足以开启部署新的VNF 时，业务流将被引导至相邻MEC 集群，而跨MEC 的带宽资源受限从而导致服务的整体时延增加。和典型的AH 策略、贪心策略和随机策略相比，基于遗传模拟退火算法的iGSA策略在降低服务时延方面有更好的表现。同时由于贪心策略考虑了多个MEC 集群共存的情况，优先在同一个MEC 集群中选择通用服务节点以降低服务时延，因此其表现优于AH 策略。在网络I 场景中，相较于其他策略，iGSA 策略都具有稳定的性能表现，分别比贪心策略、AH 策略及随机策略有平均10.62%、23.94%和71.36%的端到端服务时延优势。

图3 不同服务请求量下的服务时延对比(网络I)

为业务请求提供持续高质量的服务，多个不同类型的VNF 从逻辑上链接成SFC 或服务功能图（SFG,service function graph），本文还深入探讨了SFC 的长度与服务请求的平均时延之间的关系。从图4 中可以观察到，服务请求的平均时延随着SFC 长度（即一条SFC 链上的VNF 的个数）的增加而同步增加，其主要原因是SFC 越长，表示业务流流经的VNF 实例也越多，则在网络资源固定的情况下需要更多的计算、网络带宽及存储资源，从而导致可用的节点和链路变得更稀缺。本文在3.1 节图2 中所描述的并行逻辑连接的多个VNF 构成了SFG，该逻辑结构是一种特殊的SFC。和SFC 的主要区别在于，SFG 通过分析业务流经过的多个VNF 之间的依赖关系，引入VNF 的并行化执行思想实现对业务流的更高效服务，基于SFG 模式的业务流服务，能显著降低业务的端到端时延[26]。实验场景中设置了部分服务请求不能以并行化只能以串行化SFC 的方式提供服务，SFC 和SFG 的总数量为100。在一个SFC 或一个SFG 中，业务流需经过8 个VNF 的处理才能完成端到端的服务。该实验通过增加SFG 的数量来评估对于服务请求的端到端平均时延的影响。从图5中可以发现，在SFG 的数量从10 增到100 的过程中，即SFG 的占比增加，而SFC 的占比下降，服务请求的平均时延减少。其主要原因是当SFG 占比增加时，越来越多的VNF 都在并行处理业务流数据，完成端到端的服务时延减少。该实验结论表明，本文所提的iGSA 策略能很好地适应采用不同的 VNF 逻辑链接关系建立的MEC 应用。

图4 不同SFC 长度下的服务时延对比(网络II)

图5 不同SFG 下的服务时延对比(网络II)

将NFV 技术引入MEC 网络后，MEC 能够根据服务的请求量动态调整通用服务节点的数量以实现在服务质量和资源开销之间的平衡。本文评估了当MEC 集群中根据业务请求开启不同规模的通用服务节点时，不同算法的端到端服务时延对比，并比较了在网络II 的10 个MEC 群集中从开启80 个通用服务节点到260 个通用服务节点时端到端的平均服务时延，从图6 可以观察到，平均时延随着MEC 集群中开启的通用服务节点数量的增加而下降，其原因主要是随着每个MEC集群开启的通用服务节点数量的增加，实例化的VNF 数量也同步增加，服务请求更多地可以在入口网元所在的MEC 集群中得到处理，而不需要导入至其他相邻的MEC 集群。进一步地可以看到，在一个MEC 集群中开启相同的通用服务节点的情况下，得益于iGSA 策略能够在多个MEC集群中进行跨区域的路径选择，该策略总能提供更低的端到端服务时延。相对于集中式部署的云数据中心或云化的移动核心网，MEC 的计算及网络等IT 资源都相对受限，因此本文继续对比了IT资源受限情况下不同的策略所提供的端到端服务时延，包括通用服务节点的计算资源以及MEC集群之间的平均链路带宽受限。

图6 MEC 集群中不同的通用服务节点规模下的服务时延对比(网络II)

图7 和图8 分别对比了MEC 集群之间的带宽资源和MEC 集群计算资源处于不同稀缺情况下的业务流端到端时延。MEC 集群之间的带宽资源从200 Mbit/s 增加到1 Gbit/s，服务请求数为100 个。当IT 资源增加时，服务请求的平均服务时延逐渐降低。这是因为计算资源增加后更多的VNF 可以在本地MEC 集群中的通用服务节点生成。同时，由于MEC 集群之间的链路带宽增加，可以将业务流所需的更多的计算和网络资源引导至相邻MEC 集群。可以看到，随着MEC 集群的计算资源的逐渐增加，更多的服务请求将在本地集群中得到处理，服务的端到端路径将有效缩短。在图7和图8 中，当MEC 的计算资源处于不同稀缺程度时，相对于其他策略，iGSA 均能取得更好的性能。在不同的带宽资源稀缺程度下，iGSA 策略分别比贪心策略和AH 策略平均有13.32%和48.76%的性能优势，在不同计算资源稀缺程度下，iGSA策略则分别比贪心策略和AH 策略平均有22.72%和35.29%的性能优势。

上述实验对比中，通过设置不同的参数，包括服务请求数量、MEC 网络中服务节点规模、MEC集群数量及VNF 之间的逻辑连接关系等，详细对比了iGSA 策略和几个相关策略性能。实验结果表明，iGSA 策略通过将模拟退火和遗传算法相结合，在保证算法效率的同时获得了更优的求解方案，使时延敏感类移动业务获得更好体验。实验结论有力地支撑了本文通过改进遗传模拟退火算法解决VNF在MEC 网络中的优化部署问题上所做的创新。

图7 不同MEC 集群间的网络带宽资源下服务时延对比(网络II)

图8 不同MEC 集群计算资源下的服务时延对比（网络II）

6 结束语

本文研究了多集群MEC 网络中的VNF 的优化部署策略，首先将业务流经过部署在MEC 通用服务节点的多个 VNF 的过程形式化为一个开放Jackon 排队网络，并进一步得到业务流的服务时延最优化模型。在证明了该优化问题是一个NP-Hard问题的基础上，通过将遗传算法和模拟退火算法结合，提出一种MEC 集群网络中基于遗传模拟退火算法的VNF 部署及路径优选策略。通过在不同参数条件下，将所提策略与类似策略进行了详细对比，结果表明所提出策略能为移动业务提供更低的端到端服务时延，有效改善业务的体验。本文所提出的算法及结论能为优化MEC 的资源部署提供有借鉴意义的参考。在将来的工作中，将把本文的场景继续扩展到融合网络切片的MEC 网络，研究MEC 节点和网络切片中的虚拟资源部署和联合调度。