随着5G时代的到来，为了应对移动数据流量的爆炸式增长和海量设备连接，必须变革传统的核心网架构^[1]. 在传统的核心网架构中，控制面和用户面耦合，软件和硬件耦合^[2]. 3GPP新的5G技术标准定义了新型的核心网构架，实现了控制面和用户面分离，并引入网络功能虚拟化和软件定义网络技术实现核心网部署，提高了网络的灵活性和可扩展性^[3-4]. 集中部署的核心网用户面具有较高的回程时延，无法满足5G低时延业务需求. 利用移动边缘计算和雾计算这些新兴技术，将用户面功能（user plane function，UPF）部署在更靠近用户的边缘服务器上，可以显著降低端到端时延^[5].

UPF部署问题是典型的虚拟网络功能(virtual network function, VNF)部署问题. 近年来，VNF部署问题受到广泛关注. Pham等^[6-9]针对性地研究了VNF的静态部署，忽略了VNF的动态部署需求. 唐伦等^[10]考虑VNF迁移开销，提出VNF迁移开销与网络能耗联合优化算法，该方法没有考虑部署决策的延迟影响. 针对时变流量条件下VNF动态部署问题，Jia等^[11]采用正则化方法将其分解为一系列正则化子问题进行求解，但该方法的求解精度较低. 唐伦等^[12]针对服务功能链资源需求的动态变化，提出基于深度确定性梯度策略的VNF迁移算法，但该方法训练过程比较耗时. Eramo等^[13]考虑VNF实例迁移造成的收益损失，建立能耗和重配置成本感知的VNF实例迁移优化模型，并提出基于马尔可夫决策过程(Markov decision process, MDP)的启发式算法. 能效和时延是5G关键性能指标^[14]，UPF部署需要综合考虑能耗和时延. 为了降低边缘服务器能耗，UPF网元应该整合到尽可能少的边缘服务器上；为了降低用户面数据时延，UPF网元应该尽可能靠近用户设备(user equipment, UE)部署. 除了能耗和时延之外，还须考虑UPF部署成本. UPF部署成本不仅取决于当前时隙的部署决策，还取决于前一时隙的部署决策，因此相邻时隙部署决策相互耦合. 现有技术依次优化每个时隙，忽略部署决策的延迟影响，造成UPF部署的成本增加.

本研究以整个运行周期内总的边缘服务器能耗、UPF部署成本及用户面数据时延最小化为目标，建立核心网用户面UPF部署和流量调度多阶段规划模型. 采用Benders分解算法，将模型分解为1个UPF部署主问题和一系列流量调度子问题，交替迭代求解主问题和子问题，以获得最优的UPF部署和流量调度.

如图1所示为5G核心网用户面在边缘网络中分布式部署的示意图. 假设基站分布服从泊松点过程，每个基站处部署1个边缘服务器，将UPF部署在这些边缘服务器上，可以显著降低用户面时延. 如图所示，能耗优化策略将流量整合到尽可能少的边缘服务器上，降低了边缘服务器能耗，时延优化策略将流量调度到附近的边缘服务器，降低了用户面时延. 本研究将综合考虑边缘服务器能耗和用户面时延，兼顾时变负载条件下的重部署重调度成本，构建UPF部署与流量调度多阶段规划模型.

设 $I$为边缘服务器集合， $J$为边缘服务器资源类型的集合， $ {R_{ij}} $为边缘服务器 $i\;(i \in I)$上 $j\;(j \in J)$类型资源的容量. 设 $K$为UPF虚拟网络功能类型的集合， ${r_{kj}}$为 $k\;(k \in K)$类型的UPF实例对 $j$类型资源的需求， $ u_{_k}^{{\text{UPF}}} $为 $k$类型的UPF实例的处理容量. 设 $ M $为基站集合. 基站的数据流量具有明显的昼夜模式，通常是周期性的^[15]. 设 $T$为单个周期的时隙集合， $ \Delta t $为时隙时长. 令 $u_{mt}^{{\text{gNB}}}$表示时隙 $t\;(t \in T )$基站 $m\;(m \in M )$的数据流量.

令 $ {y_{it}} \in \left\{ {0,1} \right\} $判断时隙 $t \in T$边缘服务器 $i$是否开启： ${y_{it}} = 1$ ，表示开启； ${y_{it}} = 0$ ，表示未开启. ${n_{ikt}}( {n_{ikt}} \in N )$为时隙 $t$边缘服务器 $i$上部署的 $k$类型的UPF实例数量. ${u_{mit}} \geqslant 0$为时隙 $t$基站 $m$与边缘服务器 $i$之间的数据流量. 考虑以下3个优化目标：边缘服务器能耗、UPF部署成本、用户面数据时延.

采用基于CPU利用率的线性功耗模型^[16]，边缘服务器 $i$的功耗表示为

(1) $ {P_i} = P_i^{{\text{idle}}}+(P_i^{{\text{peak}}} - P_i^{{\text{idle}}})u_i^{{\text{CPU}}} . $

式中： $ P_i^{{\text{idle}}} $、 $ P_i^{{\text{peak}}} $分别表示边缘服务器 $i$的空闲功耗和峰值功耗， $ u_i^{{\text{CPU}}} $为边缘服务器 $i$的CPU利用率. 时隙 $t$的边缘服务器能耗表示为

(2) $ {E_t} = \sum\limits_{i \in I} {{y_{it}}\left( {P_i^{{\text{idle}}}+(P_i^{{\text{peak}}} - P_i^{{\text{idle}}})\sum\limits_{k \in K} {{n_{ikt}}r_k^{{\text{CPU}}}} /R_i^{{\text{CPU}}}} \right)\Delta t} . $

式中： $ R_i^{{\text{CPU}}} $为边缘服务器 $i$的CPU容量， $ r_k^{{\text{CPU}}} $为 $k$类型的UPF虚拟网络功能对CPU资源的需求.

UPF部署成本包括部署新的UPF实例所需的能耗成本、部署延迟所造成的收益损失. 令 $ c_k^{{\text{UPF}}} $为 $\,k$类型的UPF实例的部署单价. 令 $ \Delta {n_{ikt}} $为时隙 $t$边缘服务器 $i$上新部署的 $k$类型的UPF实例数量，表示为

(3) $ \Delta {n_{ikt}} = {\text{max}}\left\{ {{n_{ikt}} - {n_{ik(t - 1)}}{\text{,}}\,0} \right\} . $

因此，时隙 $t$的UPF部署成本表示为

(4) $ C_t^{{\text{dep}}} = \sum\limits_{i \in I} {\sum\limits_{k \in K} {\Delta {n_{ikt}}c_k^{{\text{UPF}}}} } . $

用户面时延主要由4部分组成：处理时延、排队时延、传输时延和传播时延. 仅传播时延与用户面功能部署的地理位置有关，因此本研究仅考虑用户面的传播时延. 令 ${d_{mi}}$为基站 $m$和边缘服务器 $i$之间的传播时延，基站和边缘服务器之间通过光纤或者毫米波回程链路连接，传播时延与基站和边缘服务器之间的地理距离成正比. 时隙 $t \in T$的用户面数据时延表示为

(5) $ {D_t} = \sum\limits_{m \in M} {\sum\limits_{i \in I} {{u_{mit}}\cdot \Delta t \cdot {d_{mi}}} } . $

以运行周期内总的边缘服务器能耗、UPF部署成本及用户面数据时延最小化为目标，UPF部署与流量调度问题表示为

$ \tag{6a} \min {\text{ }}\sum\limits_{t \in T} {({\beta _{\text{e}}} \cdot {E_t}+C_t^{{\text{dep}}}+{\beta _{\text{d}}} \cdot {D_t})} $

$\tag{6b} \,{\rm{s.t.}} {\text{ }}\sum\limits_{k \in K} {{n_{ikt}}\cdot{r_{kj}}} \leqslant {y_{it}}\cdot{R_{ij}};\, t\in T,i \in I,j \in J . $

$ \tag{6c} \quad\;\;\sum\limits_{m \in M} {{u_{mit}}} \leqslant \sum\limits_{k \in K} {{n_{ikt}}\cdot u_k^{{\text{UPF}}}} ;\, t \in T,i \in I . $

$ \tag{6d} \quad\;\;\; u_{mt}^{{\text{gNB}}} = \sum\limits_{i \in I} {{u_{mit}}} ;\, t \in T,m \in M . $

$ \tag{6e} \quad\;\;\; \Delta {n_{ikt}} \geqslant {n_{ikt}} - {n_{ik(t - 1)}};\, t \in T,i \in I,k \in K . $

$ \tag{6f} \quad\;\;\; {y_{it}} \in \{ 0,1\} ;\, t \in T,i \in I . $

$ \tag{6g} \quad\;\;\;{n_{ikt}} \in {\rm \bf {N}};\; t \in T,i \in I,k \in K . $

$ \tag{6h} \quad\;\;\; {u_{mit}} \geqslant 0;\; t \in T,m \in M,i \in I . $

$ \tag{6i} \quad\;\;\; \Delta {n_{ikt}} \geqslant 0;\; t \in T,i \in I,k \in K . $

式(6b)为边缘服务器的资源容量约束，保证每个边缘服务器的资源分配不超过该边缘服务器的资源容量. 式(6c)为边缘服务器的处理容量约束，保证调度到每个边缘服务器的数据流量不超过该边缘服务器的处理容量. 式(6d)为流量守恒约束，表示基站 $m$的数据流量等于从基站 $m$调度到所有边缘服务器的数据流量之和. 式(6e)、(6i)由辅助变量 $ \Delta {n_{ikt}} $的定义式(3)推导得到. $ {\;\beta _{\text{e}}} $、 $ {\;\beta _{\text{d}}} $分别为能耗价格和单位数据时延的成本，用于将能耗和数据时延转化为货币成本. 可以看出，式(6)是混合整数线性规划问题.

定理1 　式(6)中的UPF部署与流量调度问题是NP-难问题.

证明：采用限制法^[17]构建该问题的特例，说明该特例为已知的NP-难问题. 1）令 $ c_k^{{\text{UPF}}} = 0 $，则问题可以按时隙进行分解. 2）令 $ {\beta _{\text{d}}} = 0 $，使得流量调度变得无关紧要. 3）限制仅考虑单个边缘服务器和单种资源类型. 于是，式(6)转化为整数最小背包问题. 因为整数最小背包问题已知是NP-难的^[18]，所以式(6)也是NP-难的.

采用Benders分解算法求解UPF部署与流量调度问题. 为了有效降低求解问题的计算复杂度，将式(6)分解为1个UPF部署主问题和一系列流量调度子问题.

定理2 　5G核心网用户面UPF部署与流量调度问题是具有复杂变量^[19]的混合整数线性规划问题.

证明：由式(6e)可知，每个时隙的部署成本不仅取决于当前时隙的部署决策，还取决于前一时隙的部署决策. 决策变量 ${n_{ikt}}$阻碍式(6)按时隙进行分解. 若变量 ${n_{ikt}}$固定为给定值，则式(6)可以分解为一系列流量调度子问题. 因此，变量 ${n_{ikt}}$是式(6)中的复杂变量.

根据定理2，采用Benders分解算法求解式(6). Benders分解算法是迭代算法. 在每次迭代中，分别求解主问题和子问题，计算式(6)的下界和上界. 当下界和上界足够接近时，算法终止.

通过将复杂变量 ${n_{ikt}}$固定为给定值，式(6)可以按时隙分解为一系列流量调度子问题. 在第 $v$次迭代中，时隙 $t$的流量调度子问题为

$\tag{7a} \min \;{D_t} $

$ \tag{7b} {\rm{s.t}}.\; \text{ }式\text{(6c)}、\text{(6d)}、\text{(6h)}\text{.} $

$ \tag{7c} \qquad\;\;\,{n_{ikt}} = n_{iktv}^*;\; i \in I,k \in K. $

优化目标是最小化时隙 $t$的用户面数据时延；式(7b)为与流量调度相关的约束； ${n_{ikt}}$固定为给定值，由当前迭代中求解主问题得到. 在式(7)中，将变量 ${n_{ikt}}$视为连续变量. 可以看出，流量调度子问题是连续线性规划问题.

令 $ D_{tv}^* $为求解式(7)子问题所得时隙 $t$的用户面数据时延. 运行周期内核心网用户面总的运营成本表示为

(8) $ {\textit{z}}_v^{{\text{ub}}} = \sum\limits_{t \in T} {({\beta _{\text{e}}} \cdot E_{tv}^*+C_{tv}^{{\rm{dep*}}}+{\beta _{\text{d}}} \cdot D_{tv}^*)} . $

式中： $ E_{tv}^* $、 $ C_{tv}^{{\rm{dep*}}} $分别为当前迭代中求解主问题所得时隙 $t$的边缘服务器能耗及UPF部署成本. ${\textit{z}}_v^{{\text{ub}}}$是式(6)最优值的1个上界. 令 $ \lambda _{iktv}^* $为与式(7c)相关的对偶变量的最优值，用于生成主问题中的Benders最优割.

在第 $v$次迭代中，UPF部署主问题为

$ \tag{9a}\;\,\;\;\;\;\;\;\; \min \sum\limits_{t \in T} {({\beta _{\text{e}}} \cdot {E_t}+C_t^{{\text{dep}}}+{\beta _{\text{d}}} \cdot {\alpha _t})} $

$ \tag{9b} {\rm{s.t}}.\;式(6\text{b})、\text{(6e)}\sim{\rm{(6g)}}、(6\text{i}), \; t\in T\text{.} $

$ \tag{9c} \left. \begin{aligned} \qquad \qquad \;{\alpha _t} \geqslant & D_{tj}^*+\sum\limits_{i \in I} {\sum\limits_{k \in K} {\lambda _{iktj}^*({n_{ikt}} - n_{iktj}^*)} } ; \\ & t \in T, \; j = 1,\cdots,v - 1. \\ \end{aligned}\right\} $

$ \tag{9d} \qquad \;\;\;\;\;\;\; {\alpha _t} \geqslant \alpha _t^{{\text{down}}};\; t \in T . $

目标函数式(9a)对应式(6a)，其中 ${\alpha _t}$为时隙 $t$用户面数据时延的预估值；式(9b)为与UPF部署相关的约束；式(9c)为先前迭代中生成的Benders最优割集；式(9d)设置 ${\alpha _t}$的下界为 $ \alpha _t^{{\text{down}}} $，加速Benders分解算法的收敛. 可以看出，主问题是整数线性规划问题.

由式(6c)、(6d)可知，变量 ${n_{ikt}}$必须满足约束：

(10) $ \sum\limits_{i \in I} {\sum\limits_{k \in K} {{n_{ikt}}u_k^{{\text{UPF}}}} } \geqslant \sum\limits_{m \in M} {u_{mt}^{{\text{gNB}}}} , \; t \in T . $

由于式(10)不包含在主问题中，从主问题的解中获得的复杂变量的固定值可能会使子问题不可行. 在这种情况下，可行割被添加到主问题中，这使得Benders分解算法计算成本很高. 为了使子问题始终可行，将式(10)添加到主问题中. 没有可行割被添加到主问题中，Benders分解算法的计算复杂度显著降低.

令 ${\textit{z}}_v^{{\text{lb}}}$为第 $v$次迭代中主问题的最优值，它是式(6)最优值的1个下界. 令 $ n_{iktv}^* $为第 $v$次迭代中主问题的最优解，作为当前迭代中子问题复杂变量的固定值.

如图2所示，采用Benders分解算法求解UPF部署与流量调度问题的具体步骤如下. 1）初始化参数，将UPF部署与流量调度问题的目标函数的上界设为 $ {{\textit{z}}^{{\text{ub}}}} = \infty $，下界设为 $ {{\textit{z}}^{{\text{lb}}}} = - \infty $，UPF部署主问题中Benders最优割集设为空. 2）求解UPF部署主问题，得到 ${\textit{z}}_v^{{\text{lb}}}$、 $ n_{iktv}^* $，将UPF部署与流量调度问题的目标函数的下界更新为 $ {{\textit{z}}^{{\text{lb}}}} = {\textit{z}}_v^{{\text{lb}}} $，并将 $ n_{iktv}^* $代入流量调度子问题. 3）求解流量调度子问题，得到 $ D_{tv}^* $、 $ \lambda _{iktv}^* $，将UPF部署与流量调度问题的目标函数的上界更新为

(11) $ {{\textit{z}}^{{\text{ub}}}} = \min {\text{\{ }}{{\textit{z}}^{{\text{ub}}}},{\textit{z}}_v^{{\text{ub}}} = \sum\limits_{t \in T} {({\beta _{\text{e}}} \cdot E_{tv}^*+C_{tv}^{{\rm{dep*}}}+{\beta _{\text{d}}} \cdot D_{tv}^*)} {\text{\} }} . $

4）判断是否满足收敛条件，令 $\varepsilon $为预设的误差容限，若 $({{\textit{z}}^{{\text{ub}}}} - {{\textit{z}}^{{\text{lb}}}})/{{\textit{z}}^{{\text{lb}}}} \leqslant \varepsilon $，则迭代终止，否则，生成Benders最优割：

(12) $ {\alpha _t} \geqslant D_{tv}^*+\sum\limits_{i \in I} {\sum\limits_{k \in K} {\lambda _{iktv}^*({n_{ikt}} - n_{iktv}^*)} } , \; t \in T . $

并将式（12）添加到UPF部署主问题，返回步骤2）.

本研究所提算法将式(6)分解为1个UPF部署主问题和 $\left| T \right|$个流量调度子问题. UPF部署主问题是整数规划问题，仅考虑1种UPF类型，并假设每个边缘服务器可部署的UPF实例数目相同，记为 ${n_{\max }}$，UPF部署主问题的求解复杂度为 $ O({2^{\left| I \right|\left| T \right|}}{({n_{\max }}+1)^{2\left| I \right|\left| T \right|}}) $，流量调度子问题是线性规划问题，求解复杂度为 $O({(\left| M \right|\left| I \right|)^3})$，每次迭代的计算复杂度为 $ O({2^{\left| I \right|\left| T \right|}}{({n_{\max }}+1)^{2\left| I \right|\left| T \right|}}+\left| T \right|{(\left| M \right|\left| I \right|)^3}) $，总的计算复杂度为 $O(L({2^{\left| I \right|\left| T \right|}}{({n_{\max }}+1)^{2\left| I \right|\left| T \right|}}+ \left| T \right|{(\left| M \right|\left| I \right|)^3}))$. $L$为算法收敛所需的迭代次数，在本实验场景中，只需较少的迭代次数，算法即可收敛. 直接求解式(6)的计算复杂度为 $ O({2^{\left| I \right|\left| T \right|}}{({n_{\max }}+1)^{2\left| I \right|\left| T \right|}} \left| T \right|{(\left| M \right|\left| I \right|)^3}) $，因此所提算法大大降低了式(6)的求解复杂度. 在仿真实验中，将所提算法与逐阶段求解方法、基于MDP的启发式算法进行比较：逐阶段求解方法的计算复杂度为 $ O(\left| T \right|{2^{\left| I \right|}}{({n_{\max }}+1)^{2\left| I \right|}} {(\left| M \right|\left| I \right|)^3}) $；基于MDP的启发式算法采用逐阶段求解方法确定动作集，计算复杂度为 $ O(\left| T \right|{2^{\left| I \right|}}{({n_{\max }}+1)^{2\left| I \right|}} {(\left| M \right|\left| I \right|)^3}) $，采用策略迭代算法求解最优策略，计算复杂度为 $ O(L'{\left| T \right|^3}{(\left| M \right|\left| I \right|)^3}) $，其中 $L'$为算法收敛所需的迭代次数，总的计算复杂度为 $O(\left| T \right|{2^{\left| I \right|}}{({n_{\max }}+1)^{2\left| I \right|}} {(\left| M \right|\left| I \right|)^3} + L'{\left| T \right|^3}$ ${(\left| M \right|\left| I \right|)^3}) $.

通过仿真实验验证基于Benders分解的5G核心网用户面UPF部署与流量调度算法的有效性.

在4.0 km×4.0 km的区域中，假设基站位置分布服从泊松点过程^[20]，密度为1个/km². 每个基站处放置1个边缘服务器，用于部署5G核心网用户面UPF网元. 每个边缘服务器配置有48个CPU内核（仅考虑CPU为瓶颈资源），其峰值功耗为1 000 W，空闲功率系数 $\alpha $（空闲功耗与峰值功耗之比）设为0.4. 仅考虑1种UPF类型，其CPU资源需求为1个CPU内核，吞吐量为0.1 Gb/s. 基站与边缘服务器之间通过毫米波回程链路连接，其间的传播时延与其地理距离成正比^[21]. 基站的流量周期性变化，周期为1 d，因此，设 $T$=24 h，取 $ \Delta t $=1 h. 基站的流量从集合{0.5,1.0,1.5, 2.0,2.5} Gb/s中均匀随机选取.

考察所提算法的收敛性. 如图3所示为UPF部署与流量调度问题的上界和下界随迭代次数的变化曲线. 图中，C为总成本，η为迭代次数. 设置能耗价格为1元/(kW·h)，单位数据时延的成本设为5元/(Gb·ms)，UPF实例部署单价设为0.02元，误差容限 $\varepsilon $=0.01. 可以看出，随着迭代次数的增加，上界和下界逐渐趋近，上下界的相对误差逐渐趋近于0，在迭代29次之后，上下界的相对误差下降到误差容限以下.

将所提算法与逐阶段求解方法、基于MDP的启发式算法^[13]进行比较. 逐阶段求解方法依次对每个时隙进行优化，未考虑部署决策的延迟影响. 基于MDP的启发式算法将原问题建模为马尔可夫决策过程，并采用策略迭代算法求解，但其求解精度受限于动作集的选择. 如图4所示为不同UPF实例部署单价c_UPF下3种算法的总成本. 可以看出，所提算法总成本最小，且UPF实例部署单价越高，该算法的优势越明显. 当c_UPF=0.06元时，所提算法相比逐阶段求解方法和基于MDP的启发式算法，分别节省了10.4%和5.1%的总运营成本.

分析空闲功率系数 $\alpha $、时延成本 $\;{\beta _{\text{d}}}$对算法性能的影响. 如图5所示为不同参数值下平均每时隙使用的边缘服务器数量和平均用户面时延. 图中，U_s为平均服务器使用数量，D_u为平均用户面时延. 可以看出， $\alpha $越大或 $ \;{\beta _{\text{d}}} $越小，UPF实例整合到尽可能少的边缘服务器上，此时平均每时隙使用的边缘服务器数量越小，平均用户面时延越大. 相反， $\alpha $越小或 $\;{\beta _{\text{d}}}$越大，UPF实例尽可能部署到本地的边缘服务器上，此时平均每时隙使用的边缘服务器数量越大，平均用户面时延越小.

本研究针对边缘网络环境下5G核心网用户面动态部署问题，提出基于Benders分解的UPF部署与流量调度多阶段规划算法. 为了获得最优的UPF部署和流量调度，所提算法考虑边缘服务器能耗、UPF部署成本及用户面数据时延，兼顾部署决策的延迟影响，建立了UPF部署和流量调度多阶段规划模型，并采用Benders分解算法进行求解. 仿真结果表明，所提算法能够节省边缘服务器能耗和UPF部署成本，同时降低用户面数据时延. 所提算法在问题的规模较大时，仍然存在计算复杂度高的问题. 后续将进一步针对大规模的核心网用户面部署问题开展研究.