核心网是移动通信系统的重要组成部分. 在传统的EPC（evolved packet core）网络架构中，网元部署在专用的硬件平台上，网络的灵活性和可扩展性差，部署成本高. 随着5G时代的到来，为了应对爆炸式的移动数据流量增长以及海量的设备连接等挑战，移动运营商必须改变传统的EPC网络架构. 网络功能虚拟化（network function virtualization, NFV）作为新的网络范式，彻底变革了传统的网络功能实现方式. 在NFV范式中，网络功能被实现为软件设备，运行在云环境或者通用服务器上，提高了网络的灵活性和可扩展性，节省了部署成本. 因此，NFV技术被引入5G核心网的架构设计^[1-2].

vEPC（virtualized EPC）作为NFV最重要的用例之一，已经被广泛研究. Taleb等^[3]讨论云化EPC的可行性，并提出EPC即服务的概念. 核心网控制面与用户面分离进一步提升网络的灵活性和可扩展性，Abe等^[4]分析了核心网控制面与用户面分离的影响. Parvez等^[5]针对端到端时延问题，讨论核心网架构设计. Hawilo等^[6]建立vEPC虚拟网络功能(virtual network function, VNF)放置的混合整数线性规划模型，并提出启发式算法，以最小化端到端时延. 王琛等^[7]提出联合遗传和禁忌搜索算法的资源调度算法，以满足5G低时延业务需求.

核心网虚拟化为移动运营商带来新的挑战：如何根据负载需求，弹性伸缩核心网资源配置，在满足性能要求的前提下，降低运营成本. Alawe等^[8]利用循环神经网络和深度神经网络预测5G核心网流量负载，实现5G核心网资源的弹性伸缩. Arteaga等^[9]提出基于阈值的vEPC伸缩机制，利用垂直伸缩和水平伸缩应对工作负载变化. Prados-garzon等^[10]提出基于开放Jackson网络的vMME（virtualized mobility management entity）性能分析模型，利用该模型计算所需的vMME实例数量. Prados-garzon等^[11]建立vEPC资源规划与映射联合优化模型，提出启发式求解方法. Bagaa等^[12]提出vEPC切片构建方法，利用混合整数线性规划确定核心网网元虚拟实例的最优数量.

本文采用G/G/m队列的开放排队网络建立核心网控制面性能评估模型，推导出信令流程平均响应时间的近似表达式. 在此基础上，综合考虑处理性能和VNF实例部署成本，建立核心网控制面资源分配多目标优化模型. 为了求解上述资源分配问题，提出改进的多目标遗传算法，改进拥挤距离计算方法.

LTE（long term evolution）控制面由用户设备（user equipment, UE）、基站、移动管理实体（mobility management entity, MME）、服务和分组数据网关控制面（serving and packet data network gateway control plane, SPGW-C）与归属用户服务器(home subscriber server, HSS)组成. 核心网控制面集中部署在云数据中心，每个网元由多个虚拟实例组成，并且有缓存队列用于缓存待处理信令，所有网元均为单队列多服务台排队系统. LTE控制面信令流程需要经过多个网元处理，分别对每个网元进行性能分析是不合理的，本文采用排队网络对LTE控制面进行建模. M/M/m队列的开放Jackson网络是经典的排队网络，但其受限于强假设：外部到达过程是泊松过程，服务时间服从指数分布^[13]. LTE控制面每个网元需要处理多种信令，每种信令的处理时间均为常数，服务时间并不服从指数分布，因此，M/M/m队列的开放Jackson网络并不适用. 采用G/G/m队列的开放排队网络^[14]对LTE控制面进行性能分析，将每个网元建模为G/G/m排队系统，并利用到达时间间隔及服务时间的均值和平方变异系数表征. 无线接入网(E-UTRAN)作为整体采用G/G/∞排队系统建模.

令 $F = \left\{ {{\rm{MME,SPGWC,HSS}}} \right\}$为核心网控制面网元的集合， ${n_f}$为网元 $f \in F$虚拟实例的数量. 令 $S$为LTE控制面信令流程的集合，信令流程 $s \in S$的路由路径为 ${f_{s1}},{f_{s2}}, \cdots ,{f_{sk}}, \cdots ,{f_{s{N_s}}}$，其中 ${f_{sk}} \in F \cup $ $ \{ {{\rm{E - UTRAN}}}\}$为信令流程 $s$经过的第 $k$个网元， ${N_s}$为信令流程 $s$所经过网元的数量. 核心网控制面网元 $f \in F$的信令到达速率为

(1) ${\lambda _f} = \sum\limits_{s \in S} {\sum\limits_{k = 1}^{{N_s}} {{n_{\rm{_U}}}{\mu _s} I\left\{ {{f_{sk}} = f} \right\}} } .$

式中： ${n_{\rm{_U}}}$为UE数量； ${\mu _s}$为每个UE产生信令流程 $s \in S$的速率； $I(x)$满足当条件 $x$为真时， $I(x) = 1$，否则 $I(x) = 0$. 核心网控制面网元 $f \in F$服务时间的均值和平方变异系数分别为

(2) ${\tau _f} = \frac{{\displaystyle\sum\limits_{s \in S} {\displaystyle\sum\limits_{k = 1}^{{N_s}} {{n_{\rm{_U}}}{\mu _s} I\left\{ {{f_{sk}} = f} \right\} {\tau _{sk}}} } }}{{\displaystyle\sum\limits_{s \in S} {\displaystyle\sum\limits_{k = 1}^{{N_s}} {{n_{\rm{_U}}}{\mu _s} I\left\{ {{f_{sk}} = f} \right\}} } }},$

(3) $c_{{\rm{s,}}f}^2 = \frac{{\displaystyle\sum\limits_{s \in S} {\displaystyle\sum\limits_{k = 1}^{{N_s}} {{n_{\rm{_U}}}{\mu _s} I\left\{ {{f_{sk}} = f} \right\} \tau _{sk}^2(c_{sk}^2 + 1)} } }}{{\tau _f^2\displaystyle\sum\limits_{s \in S} {\displaystyle\sum\limits_{k = 1}^{{N_s}} {{n_{\rm{_U}}}{\mu _s} I\left\{ {{f_{sk}} = f} \right\}} } }} - 1.$

式中： ${\tau _{sk}}$、 $c_{sk}^2$分别为信令流程 $s \in S$在其路由路径的第 $k$个网元上服务时间的均值、平方变异系数. 令 $c_{{\rm{a,}}f}^2$为LTE控制面网元 $f \in F \cup \left\{ {{\rm{E - UTRAN}}} \right\}$信令到达时间间隔的平方变异系数，满足线性方程组^[14]：

(4) $\left. {\begin{array}{*{20}{l}} {c_{{\rm{a,E - UTRAN}}}^2 = {a_{{\rm{E - UTRAN}}}} + c_{{\rm{a,MME}}}^2{b_{{\rm{MME,E - UTRAN}}}}}， \\ \begin{gathered} c_{{\rm{a,MME}}}^2 = {a_{{\rm{MME}}}} + c_{{\rm{a,E - UTRAN}}}^2{b_{{\rm{E - UTRAN,MME}}}} + \\ c_{{\rm{a,SPGWC}}}^2{b_{{\rm{SPGWC,MME}}}} + c_{{\rm{a,HSS}}}^2{b_{{\rm{HSS,MME}}}}， \\ \end{gathered} \\ {c_{{\rm{a,HSS}}}^2 = {a_{{\rm{HSS}}}} + c_{{\rm{a,MME}}}^2{b_{{\rm{MME,HSS}}}}} ，\\ {c_{{\rm{a,SPGWC}}}^2 = {a_{{\rm{SPGWC}}}} + c_{{\rm{a,MME}}}^2{b_{{\rm{MME,SPGWC}}}}} . \end{array}} \right\}$

求解式（4），可以得到：

(5) $ \begin{split} c_{{\rm{a,MME}}}^2 =& ({a_{{\rm{MME}}}} + {a_{{\rm{E - UTRAN}}}}{b_{{\rm{E - UTRAN,MME}}}} + \\ &{a_{{\rm{SPGWC}}}}{b_{{\rm{SPGWC,MME}}}} + {a_{{\rm{HSS}}}}{b_{{\rm{HSS,MME}}}}) \times \\ &(1 - {b_{{\rm{MME,E - UTRAN}}}}{b_{{\rm{E - UTRAN,MME}}}} - \\ &{b_{{\rm{MME,SPGWC}}}}{b_{{\rm{SPGWC,MME}}}} - \\ &{b_{{\rm{MME,HSS}}}}{b_{{\rm{HSS,MME}}}}{)^{ - 1}} . \end{split} $

进一步可以求得 $c_{{\rm{a,E - UTRAN}}}^2$、 $c_{{\rm{a,HSS}}}^2$和 $c_{{\rm{a,SPGWC}}}^2$.

基于上述分析，核心网控制面网元 $f \in F$均建模为G/G/m排队系统，队列中信令的平均等待时间为^[14]

(6) ${t_f} = \frac{{c_{{\rm{a,}}f}^2 + c_{{\rm{s,}}f}^2}}{2}t_f^{{\rm{M/M/m}}}.$

式中： $t_f^{{\rm{M/M/m}}}$为M/M/m队列中信令的平均等待时间. 平均一次信令流程经过网元 $f \in F$处理的次数 ${V_f}$为

(7) ${V_f} = {{{\lambda _f}}}\bigg{/}{{\displaystyle\sum\limits_{s \in S} {{n_{\rm{_{U}}}}{\mu _s}} }}.$

可以得到平均一次信令流程的响应时间为

(8) $T = \sum\limits_{f \in F} {({t_f} + {\tau _f}) {V_f}}. $

为了降低信令流程的平均响应时间，需要增加核心网控制面VNF实例，但是这会导致更高的VNF实例部署成本. 为了确定核心网控制面VNF实例的最优配置数量，综合考虑处理性能和VNF实例部署成本，建立核心网控制面资源分配多目标优化模型.

核心网控制面资源分配多目标优化问题可以描述为

(9) $\left. {\begin{array}{*{20}{l}} \min \;T = \displaystyle\sum\limits_{f \in {F}} {({t_f} + {\tau _f}) {V_f}} ,\\ \min \;C = \displaystyle\sum\limits_{f \in {F}} {{n_f} {c_f}} . \end{array}} \right\}$

(10) ${\rm{s}}.{\rm{t}}.\;\; {n_f}\geqslant n_f^{\min },\;{n_f}\leqslant n_f^{\max },\;{n_f} \in {{\bf{N}}^ + };\;\forall f \in F.$

式中： $T$为核心网控制面处理性能，用信令流程的平均响应时间来表征； $C$为核心网控制面VNF实例部署成本； ${c_f}$为网元 $f \in F$虚拟实例的部署成本； $n_f^{\min }$为使得网元 $f \in F$服务强度 ${\rho _f} < 1$所需的最小虚拟实例数量； $n_f^{\max }$为网元 $f \in F$的最大配置数量. 上述问题是多目标整数非线性规划问题.

针对核心网控制面资源分配多目标优化问题，采用实数编码的NSGA-II算法求解^[15]. 为了提高进化过程中种群的多样性，改进拥挤距离计算方法.

由于处理性能与部署成本具有不同的量纲和取值范围，这里采用Min-Max方法对种群中个体的目标函数值进行归一化处理. 假设种群中个体 $i$的第 $j$个目标函数值为 ${x_{ij}}$，进行归一化处理

(11) ${\bar x_{ij}} = \frac{{{x_{ij}} - {x_{j\min }}}}{{{x_{j\max }} - {x_{j\min }}}}.$

式中： ${x_{j\operatorname{m} {\rm{ax}}}}$为种群中第 $j$个目标函数的最大值， ${x_{j\operatorname{m} {\rm{in}}}}$为种群中第 $j$个目标函数的最小值. 传统的拥挤距离计算方法不能准确反映个体的拥挤程度. 因此Wang等^[16]提出调和距离的概念. 个体 $i$的调和距离定义为

(12) ${d_i} = \frac{K}{{\dfrac{1}{{{d_{i1}}}} + \dfrac{1}{{{d_{i2}}}} + \cdots + \dfrac{1}{{{d_{iK}}}}}}.$

式中： ${d_{i1}},{d_{i2}}, \cdots ,{d_{iK}}$为个体 $i$与其 $K$个最近邻的欧氏距离.

在生成新的父代种群时，合并当前父代种群和子代种群，对合并后的种群进行快速非支配排序. 对每个个体，从同一非支配等级和更高非支配等级中寻找其 $K$个最近邻，计算其调和距离^[16]. 上述调和距离计算方法存在以下问题. 1）在计算个体的调和距离时没有考虑更低非支配等级的选中个体. 如图1（a）所示，根据调和距离的定义，个体A的调和距离大于个体B，但是实际上个体A比个体B更拥挤，原因是个体A附近存在很多更低非支配等级的选中个体. 2）在计算临界层^[17]个体的调和距离时考虑了同一非支配等级的未选中个体. 如图1（b）所示，虽然个体A附近存在很多同一非支配等级的个体，但是这些个体未被选为新的父代个体，对个体A的拥挤程度并没有影响，因此个体A比个体B稀松.

针对上述问题，本文提出改进措施：在生成新的父代种群之后计算个体的调和距离，从新的父代种群中寻找个体的 $K$个最近邻. 在生成新的父代种群时，从临界层选择新的父代个体的具体步骤如下：1）初始化临界层剩余个体集合和已选中个体集合；2）计算临界层剩余个体与已选中个体之间的欧氏距离；3）从已选中个体中寻找临界层剩余个体的 $K$个最近邻，并计算临界层剩余个体的调和距离；4）从临界层剩余个体中选择具有最大调和距离的个体作为新的父代个体，并更新临界层剩余个体集合和已选中个体集合；5）若已选中个体数目达到种群规模，停止选择，否则返回步骤2）.

分析计算个体调和距离和从临界层选择新的父代个体的复杂度，种群规模为 $N$. 计算个体的调和距离时，个体之间欧氏距离的计算复杂度为 $O({N^2})$，寻找个体的 $K$个最近邻的复杂度为 $O({N^2}{\rm{log}}K)$. 因此，个体调和距离的计算复杂度为 $O({N^2}{\rm{log}}K)$. 从临界层选择新的父代个体时，临界层剩余个体与已选中个体之间欧氏距离的计算复杂度为 $O({N^2})$，寻找临界层剩余个体的 $K$个最近邻的复杂度为 $O({N^2}{\rm{log}}K)$，从临界层剩余个体中选择具有最大调和距离个体的复杂度为 $O({N^2})$. 因此，从临界层选择新的父代个体的复杂度为 $O({N^2}{\rm{log}}K)$.

通过仿真实验验证本文提出的核心网控制面性能评估模型以及资源分配算法，实验参数设置如下. 考虑3种信令流程：服务请求流程（SR）、S1释放流程（S1R）、切换流程（HO），3种信令流程的产生速率分别为0.004 5、0.004 5、0.001 2次/（UE·s），且服从泊松过程. 3种信令流程的路由路径分别为1）SR: E-UTRAN,MME,E-UTRAN,MME,SPGW-C,MME；2）S1R: E-UTRAN,MME,SPGW-C,MME,E-UTRAN,MME；3）HO: E-UTRAN,MME,SPGW-C,MME,E-UTRAN.基于Amazon EC2的m3.xlarge实例实现MME和SPGW-C，m3.xlarge实例的按需价格为3.471元/h，基于开源的核心网软件OpenAirInterface测试所得，MME和SPGW-C的信令处理时间均设为0.000 1s.

为了验证本文提出的改进多目标遗传算法的有效性，将本文算法与NSGA-Ⅱ^[15]、HaD-MOEA^[16]进行性能比较. 实验中，UE数量设为2 000 000，算法参数设置如下：种群规模设为20，选择操作采用二元锦标赛选择算子，交叉、变异操作分别采用模拟二进制交叉算子、多项式变异算子^[18]，交叉概率、变异概率分别设为0.9、0.1，交叉分布指数、变异分布指数均设为20，本文算法和HaD-MOEA的参数 $K = 4$.

将本文提出的核心网控制面性能评估模型与Jackson排队网络模型、SimEvents仿真进行比较. 虚拟MME实例的数量和虚拟SPGW-C实例的数量分别为3、1. 如图2所示为不同UE数量下3种性能分析方法的平均响应时间. 由图可知，本文提出的性能评估模型结果与SimEvents仿真结果非常接近，Jackson排队网络模型结果明显高于SimEvents仿真结果，原因是Jackson排队网络模型假设服务时间服从指数分布.

分析本文提出的改进多目标遗传算法的收敛性. 采用反转世代距离（inverted generational distance, IGD）指标^[19]评价算法获得的近似Pareto解集的质量，IGD指标值越小表明所获得的近似Pareto前沿越接近真实Pareto前沿. 如图3所示为解集的IGD指标值随进化代数的变化情况. 图中， $t$ 为进化代数. 可以看出，随着进化代数的增加，IGD指标值逐渐减小，当 $t$=30时算法收敛.

将本文算法与NSGA-Ⅱ、HaD-MOEA进行性能比较. 采用IGD和超体积比（hypervolume ratio, HVR）指标^[20]评价算法获得的近似Pareto解集的综合性能. HVR指标能够同时反映解集的收敛性和多样性，HVR指标值越大表明解集的综合性能越好. 如表1所示为t=30时3种算法的IGD和HVR指标值. 从表中可以看出，本文算法获得的近似Pareto解集的IGD和HVR指标优于其他2种算法，综合性能最优，原因是本文算法改进了拥挤距离计算方法，丰富了进化过程中种群的多样性. 如图4所示为采用本文算法得到的Pareto前沿. 决策者需要根据偏好从Pareto前沿中选择最优折中解，权衡核心网控制面处理性能与部署成本.

将本文提出的核心网控制面资源分配算法与Prados-Garzon等^[11]提出的PES算法及2个单目标遗传算法SGA-T、SGA-C进行比较，其中PES算法中vEPC控制面处理延迟预算设为控制面信令流程服务时间0.000 4 s的1.1倍，即0.000 44 s，这亦与文献[11]一致，SGA-T、SGA-C分别以处理性能和部署成本为优化目标. 如图5所示为不同资源分配算法下核心网控制面的处理性能和部署成本. 由图可知，SGA-T以高昂的部署成本为代价获得最优的处理性能，SGA-C与之相反. PES算法在满足延迟预算的条件下获得最低的部署成本. 相比PES算法，本文算法以较小的性能损失（5.4%）为代价换取显著的成本节省（9.1%）.

针对NFV环境下核心网控制面资源分配问题，提出性能感知的核心网控制面资源分配算法. 采用排队网络对核心网控制面进行性能分析，能够获得更好的性能评估结果. 所提出的核心网控制面资源分配算法，综合考虑了处理性能和部署成本，与NSGA-II和HaD-MOEA相比，综合性能更好，能够实现核心网控制面处理性能与部署成本的权衡. 后续将进一步针对核心网控制面动态部署中VNF实例初始化产生的能耗、引起的用户QoS的下降进行研究，分析部署决策的延迟影响，并采用强化学习解决核心网控制面动态部署问题.