0 概述

网络切片(Network Slicing, NS)^[1]是5G时代的关键技术之一, 网络以灵活有效的方式构建NS, 以满足个性化的容量和覆盖范围需求^[2-4]。NS可以虚拟化各种不同的网络元素, 并解耦软件定义网络(Software Defined Network, SDN)的集中控制功能^[5]。随着网络功能虚拟化(Network Function Virtualization, NFV)技术的成熟, NS实现了软硬件解耦、基础设施资源共享以及按需调度^[6]。此外, SDN将数据平面与控制平面解耦合, 简化了网络管理与路由配置^[7]。因此, 文献[8]提出在NFV的架构中引入SDN, 使得NS的编排和部署更具可行性。

编排是网络切片技术中的一种新兴概念, 网络切片编排的实质是资源编排, 包括虚拟资源和物理资源。文献[9]提出混合无线/有线网络的无线虚拟网络功能(Virtual Network Function, VNF)配置问题, 其在小型网络中引入一种基于整数线性规划(Integer Linear Programming, ILP)算法, 并为大型网络部署提供可扩展的启发式算法, 但是在其模型中, 无线网络的功能仅用一个简单的参数进行表示。文献[10]分析由于服务的动态到达和离开引起的VNF过度部署, 以及部署在网络中的大量VNF利用率极低的问题, 并将它们建模为网络功能整合(Network Function Consolidation, NFC)问题, 采用ILP算法进行解决。同时, 文献[10]还设计一种基于贪心策略的启发式算法来解决大规模NFC问题。文献[11]以网络运营成本和资源利用率为优化目标, 对VNF的数量和布局进行编排, 并称之为VNF编排问题(VNF Orchestration Problem, VNF-OP), 最后在CPLEX软件上采用ILP算法解决VNF-OP。但是, 文献[10-11]都只针对VNF进行优化编排, 并未体现SDN架构的集中控制优势。相比优化算法, 启发式解决方案的资源利用率较低, 但是其复杂度明显降低, 对网络的计算资源要求也随之降低。文献[12]提出一种基于切片划分的网络资源控制机制, 其通过贪婪策略对网络需求进行排序, 然后逐一编排。文献[13]提出一种SDN/NFV架构下的基于GA-PSO优化的NS编排算法, 该算法利用粒子群算法能够快速收敛于全局最优解的特性, 设计针对NS性能的评价函数。文献[14]提出一种基于网络效用最大化的虚拟资源分配算法, 其采用商业化模式将频谱资源作为收益载体, 并对不同的切片网络进行差异化定价。

目前, 在无线虚拟化环境下基于NS对资源进行动态分配是一个研究热点, 但多数算法仅以网络吞吐量作为优化目标, 不能充分体现5G三大应用场景(eMBB、uRLLC、mIoT)间的业务差异性。本文设计一种基于NS的带宽资源编排算法, 该算法将带宽资源的编排方式作为优化对象, 考虑eMBB切片与uRLLC切片在吞吐量和时延上的差异化需求, 以吞吐量和时延的加权值作为优化目标建立模型。在此基础上, 分别设计针对小型网络的全局搜索算法和针对大型网络的启发式算法, 以对模型进行求解。

1 系统模型与性能评价指标 1.1 系统模型

本文系统模型如图 1所示, 整个网络分为3层, 从底层到顶层分别为基础设施提供商(Infrastructure Providers, InPs)、移动虚拟网络运营商(Mobile Virtual Network Operators，MVNOs)、服务提供商(Service Providers, SPs)。其中，基础设施提供商被虚拟化为具有相应虚拟网络资源和虚拟网络功能的vBS，该过程也被称为NFV。VNF₁~VNF₃代表各VNF集合, 虚拟资源与不同的VNF集合相组合, 以对不同用户进行服务。图 1是3种不同业务类型的NS在基础设施上的示例, 且基站上的频谱资源保持不变。基站上的频谱资源需要根据业务类型进行编排, 在整个网络结构中, 基站带宽资源的有效编排直接影响系统的性能。

本文考虑底层网络上的2个切片eMBB和uRLLC。将eMBB和uRLLC切片中的用户设备(User Equipment, UE)集合分别表示为I^e和I^u, 将基站的集合表示为J。每个用户i∈I^e∪I^u在基站j∈J处的频谱效率可以表示为:

$ {\eta _{i,j}} = {\rm{1b}} \left( {1 + \mathit{SIN}{\mathit{R}_{i,j}}} \right) $

(1)

其中, SINR_{i, j}表示用户i在基站j上的信干噪比, 表示为:

$ SIN{R_{i,j}} = \frac{{{P_j} \cdot {h_{i,j}}}}{{\sum\limits_{l \in J,l \ne j} {{P_l} \cdot {h_{i,l}}} + {\sigma ^2}}} $

(2)

其中, P_j为基站j的发射功率, h_{i, j}为用户i到基站j的信道增益, P_l为干扰基站l的发射功率, h_{i, l}为用户i到基站l的信道增益, σ²为高斯白噪声。由香农公式可知用户i的吞吐量为:

$ {R_i} = \sum\limits_{j \in J} {{y_{i,j}}} {B_j}{\eta _{i,j}} $

(3)

其中, y_{i, j}∈[0, 1]表示基站j分配给用户i的频谱资源比例, B_j为基站j的带宽。假设x_{i, j}∈{0, 1}表示用户i是否与基站j相连, x_{i, j}=1表示用户i与基站j相连, 且一个用户在某时刻只能请求一种服务, 故一个用户只能与一个基站进行连接, 由此得到:

$ \sum\limits_{j \in J} {{x_{i,j}}} = 1,\forall i \in {I^e} \cup {I^u} $

(4)

此外, 基站j上所有用户分配的频谱资源不能超过带宽限制, 即:

$ \sum\limits_{i \in {I^e} \cup {I^u}} {{y_{i,j}}} \le 1,\forall j \in J $

(5)

可以看出, 当且仅当x_{i, j}=1时, 基站j上的频谱资源被分配给用户i, 故进一步得到:

$ {y_{i,j}} \le {x_{i,j}},\forall i \in {I^e} \cup {I^u},\forall j \in J $

(6)

显然, 一个基站不可能无限制地接入用户, 假设基站j能够接入的最大用户数为u_j, 则有:

$ \sum\limits_{i \in {I^e} \cup {I^u}} {{x_{i,j}}} \le {u_j},\forall j \in J $

(7)

1.2 性能评价指标

本文考虑eMBB和uRLLC场景下的业务, 针对其不同的业务需求, 设计2种性能评价指标, 具体如下:

1) eMBB切片可以保证移动宽带业务的传输速率和吞吐量。本文在满足eMBB切片上所有用户的吞吐量和时延最低性能需求的同时, 尽可能提高用户的最小吞吐量。因此, 本文将eMBB业务的性能评价指标定义为最小吞吐量:

$ a \buildrel \Delta \over = \mathop {\min }\limits_{i \in {I^e}} {R_i} $

(8)

2) uRLLC切片超低的时延需求是其区别于其他业务的最明显特点, 本文在保证uRLLC切片中所有用户的传输时延均满足业务KPI指标(1 ms)的同时, 最小化其最大传输时延, 以保证uRLLC切片的整体时延性能。因此, 本文将最大传输时延作为uRLLC切片的性能评价指标:

$ b \buildrel \Delta \over = \mathop {\max }\limits_{i \in {I^u}} \frac{{{L_i}}}{{{R_i}}} $

(9)

其中, L_i表示用户i的传输数据长度。

上述2种不同切片共享带宽资源, 但两者对吞吐量和时延的要求不同。为提高eMBB切片的最小吞吐量, 同时降低uRLLC切片的最大传输时延, 本文引入权重系数w∈[0, 1], 并提出基于eMBB和uRLLC切片带宽资源编排的双目标优化问题(Bandwidth Orchestration Problem, BOP), 本文称其为e & u-BOP问题, 该优化问题的数学模型可以表示为:

$ \begin{array}{l} \mathop {\max }\limits_{{x_{i,j}},{y_{i,j}}} \left\{ {wa - (1 - w)b} \right\},{\rm{e\& u - BOP}}\\ {\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{. }}\\ {\rm{C1}}:{x_{i,j}} \in \left\{ {{\rm{0}},{\rm{1}}} \right\},\forall i \in {I^e} \cup {I^u},\forall j \in J\\ {\rm{C}}2:{y_{i,j}} \in \left[ {0,1} \right],\forall i \in {I^e} \cup {I^u},\forall j \in J\\ \begin{array}{*{20}{l}} {{\rm{C}}3:a \le {R_i},\forall i \in {I^e}}\\ {{\rm{C}}4:b \ge \frac{{{L_i}}}{{{R_i}}},\forall i \in {I^u}} \end{array}\\ {\rm{C}}5:\sum\limits_{i \in {I^e} \cup {I^u}} {{y_{i,j}}} \le 1,\forall j \in J\\ {\rm{C}}6:\sum\limits_{j \in J} {{x_{i,j}}} = 1,\forall i \in {I^e} \cup {I^u}\\ \begin{array}{*{20}{l}} {{\rm{C}}7:\sum\limits_{i \in {I^e} \cup {I^u}} {{x_{i,j}}} \le {u_j},\forall j \in J}\\ {{\rm{C}}8:{y_{i,j}} \le {x_{i,j}},\forall i \in {I^e} \cup {I^u},\forall j \in J} \end{array} \end{array} $

(10)

2 e & u-BOP问题求解与算法设计 2.1 e & u-BOP问题求解

通过式(10)可以看出, e & u-BOP是一个非确定多项式(Non-Deterministic Polynomial, NDP)问题。x_{i, j}是二进制离散变量, 故满足所有约束条件的x_{i, j}的个数有限, 可以用传统的全局遍历(Global Traverse, GT)算法遍历所有的x_{i, j}值, 带入式(10), 然后求出其对应的y_{i, j}和函数值, 最后选择所得函数值最大的一组x_{i, j}和y_{i, j}, 即为式(10)的最优解。

对于满足约束式(1)、式(6)、式(7)的x_{i, j}集合, 最优解x_{i, j}^*一定在该集合内, 故此时x_{i, j}^*可以看作已知, 原e & u-BOP问题可以进一步表示为:

$ \begin{array}{*{20}{l}} {\mathop {\max }\limits_{{y_{i,j}}} \left\{ {w{a^*} - (1 - w){b^*}} \right\},{\rm{BAP}}}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{.}}}\\ {{\rm{C}}2,{\rm{C}}3,{\rm{C}}4,{\rm{C}}5}\\ {{{\rm{C}}^*}8:{y_{i,j}} \le x_{i,j}^*,\forall i \in {I^e} \cup {I^u},\forall j \in J} \end{array} $

(11)

通过式(11)可以看出, 当变量x_{i, j}值确定时, 原e & u-BOP问题转化为简单的带宽分配问题(Bandwidth Allocation Problem, BAP)。二进制离散变量x_{i, j}的个数为2^I×J, 显然, 针对大型网络, 遍历所有x_{i, j}值需要消耗大量的资源。

2.2 算法分析

因为x_{i, j}是离散的二元变量, 且与y_{i, j}有关, 所以式(10)的目标函数是非凸函数, 需先将其转化为凸函数再进行求解。将变量x_{i, j}松弛为变量$ \tilde{x}_{i, j}$, 且$ \tilde{x}_{i, j}$∈[0, 1], 松弛后的变量$ \tilde{x}_{i, j}$可以看作是用户连接该基站的概率, 则松弛后的e & u-BOP问题就转化为e & u-BORP问题, 如下:

$ \begin{array}{l} \mathop {\max }\limits_{{{\tilde x}_{i,j}},{y_{i,j}}} \left\{ {wa - (1 - w)b} \right\},{\rm{e\& u - BORP}}\\ {\rm{s}}.\;{\rm{t}}.\\ {\rm{\tilde C}}1:{{\tilde x}_{i,j}} \in [0,1],\forall i \in {I^e} \cup {I^u},\forall j \in J\\ {\rm{\tilde C}}6:\sum\limits_{j \in J} {{{\tilde x}_{i,j}}} = 1,\forall i \in {I^e} \cup {I^u}\\ {\rm{\tilde C}}7:\sum\limits_{i \in {I^e} \cup {I^u}} {{{\tilde x}_{i,j}}} \le {u_j},\forall j \in J\\ {\rm{\tilde C}}8:{y_{i,j}} \le {{\tilde x}_{i,j}},\forall i \in {I^e} \cup {I^u},\forall j \in J\\ {\rm{C}}2,{\rm{C}}3,{\rm{C}}4,{\rm{C}}5 \end{array} $

(12)

通过式(8)、式(9)可以看出, a是拟凸函数(实际上是拟线性), b是凹函数, 故式(11)的目标函数具有凸函数的性质, 且式(11)中的所有约束均可用凸函数或仿射函数进行表示, 即式(11)是一个凸优化问题, 可以采用MATLAB中的CVX工具箱求解, 但得到的解$ \tilde{x}_{i, j}$和y_{i, j}并不满足原e & u-BOP问题的约束, 从约束C8可以看出, x_{i, j}和y_{i, j}强相关, 对于确定的x_{i, j}, 可以求得确定的y_{i, j}。因此, 只需将$ \tilde{x}_{i, j}$中的元素全部重置为0或1, 即可得到相应的y_{i, j}和函数值。

松弛变量$ \tilde{x}_{i, j}$可以看作是用户与基站间的连接概率, 首先应尽可能保证高概率连接。对此, 本文设计一种保证高概率连接的启发式(High Probability Guarantee Heuristic, HPGH)算法, 以重置松弛变量$ \tilde{x}_{i, j}$。HPGH算法执行过程如算法1所示。松弛变量$ \tilde{x}_{i, j}$执行算法后得到重置解$ {{\hat x}_{i, j}}$, 将$ {{\hat x}_{i, j}}$带入式(11)可得到y_{i, j}和目标函数值, 即为原方程式(10)的近似全局最优解。

算法1  HPGH算法

输入  $ \tilde{x}_{i, j}, I=I^{e} \cup I^{u}$

输出  $ {{\hat x}_{i, j}}$

1.初始化${{{\rm{\hat x}}}_{{\rm{i, j}}}} $ ←zeros[I, J]

2.m_{i^*, j^*}: ${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $中i^*行、j^*列的元素

3.n←0:${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $中重置为1的元素个数

4.取出${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $中最大的元素, 赋值给m_{i^*, j^*}, m_{i^*, j^*}←max${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $, 对应坐标(i^*, j^*)

5.然后将${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $中(i^*, j^*)处的值置0, ${{{\rm{\hat x}}}_{{\rm{i, j}}}} $中(i^*, j^*)处的值置1:$ {{{\rm{\tilde x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}$←0, $ {{{\widehat {\rm{x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}}$←1, 更新${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $和${{{\rm{\hat x}}}_{{\rm{i, j}}}} $

6.如果满足条件$\sum\limits_{{{\rm{j}}^*}} {{{\widehat {\rm{x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}} \le 1 $且$\sum\limits_{{{\rm{i}}^{\rm{*}}}} {{{\widehat {\rm{x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}} \le {{\rm{u}}_{\rm{j}}} $, 那么n←n+1, 否则, 转到步骤7

7.将${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $和${{{\rm{\hat x}}}_{{\rm{i, j}}}} $中(i^*, j^*)处的值均置0, $ {{{\rm{\tilde x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}$ ←0, $ {{{\widehat {\rm{x}}}_{{{\rm{i}}^{\rm{*}}}{\rm{, }}{{\rm{j}}^{\rm{*}}}}}}$ ←0, 更新${{{\rm{\tilde x}}}_{{\rm{i, j}}}} $和${{{\rm{\hat x}}}_{{\rm{i, j}}}} $

8.若满足条件n=I+1, 则得到重置后的${{{\rm{\hat x}}}_{{\rm{i, j}}}} $并输出; 否则, 跳转到步骤4.

本文对GT和HPGH 2种算法的计算复杂度进行对比分析, 如下:

1) GT算法:计算x_{i, j}的复杂度为O(2^i×j); 求解BAP是一维线性规划问题, 对于a和b都是冒泡排序的过程, 其算法复杂度为O(n²), 故求解BAP过程的复杂度为O(i²×j²)。因此, GT算法的计算复杂度为O(2^i×j+i²×j²)。

2) HPGH算法的计算复杂度分为3个方面:松弛x_{i, j}为$ \tilde{x}_{i, j}$, 式(12)变为二元线性规划问题, 计算复杂度为O(i²×j²); 基于高概率的贪婪算法重置$ \tilde{x}_{i, j}$为$ {{\hat x}_{i, j}}$, 也是一个冒泡排序的过程, 算法复杂度为O(i²×j²); 将$ {{\hat x}_{i, j}}$带入BAP求y_{i, j}和目标值, 算法复杂度为O(j²)。因此, HPGH算法的计算复杂度为O(2×i²×j²+j²)。

GT算法得到的解为全局最优解, 但其对计算资源的要求非常高。尽管HPGH算法得到的解为局部最优解, 但其复杂度明显降低, 更适用于求解大型网络下的e & u-BOP问题。

3 仿真结果与分析

本文提出基于网络切片eMBB和uRLLC的带宽资源编排问题e & u-BOP, 并设计一种启发式算法HPGH对e & u-BOP问题进行求解。x_{i, j}能体现基站与用户的连接情况, 因此, 确定x_{i, j}的过程即是无线链路适配的过程。传统的无线链路适配过程(Classical Wireless Link Adaptation Process, CWLAP)基于信道质量指数(Channel Quality Index, CQI)来决定是否连接信道。

为验证HPGH算法的性能, 本文将其与多小区动态资源分配算法(Multi-cell Dynamic Resource Allocation algorithm, MDRA)^[15]进行对比分析。本次实验主要模拟LTE系统的下行链路, 并与基于CQI反馈的CWLAP进行比较。为提高仿真的准确性和通用性, 本文模拟固定位置的基站, 在4个基站下随机分布60个用户, 用户与基站的分布情况如图 2所示, 每次随机生成用户位置和类型, 通过多次仿真求平均值的方式对结果进行统计分析。具体仿真参数设置如表 1所示。

无论是eMBB用户考虑的吞吐量还是uRLLC用户考虑的延迟, 都与其连接的基站带宽分配有关。本文将基站为用户分配的带宽作为研究对象, 并将吞吐量与时延作为优化目标进行研究。本节通过实验模拟分析权值w∈[0, 1]对系统性能的影响。因为MDRA算法的目标函数是系统总吞吐量, 与w无关, 故本节主要对本文HPGH算法与基于CQI的CWLAP算法进行对比分析。假设eMBB用户和uRLLC用户的比例不变且为1:1, w取0~1的值, 步长为0.1, 得到用户数u为30和60两种情况下的实验结果。图 3所示为系统性能随权值w的变化情况。从图 3可以看出, 在相同的用户数和业务比例下, eMBB业务的最小吞吐量、平均吞吐量, 以及uRLLC业务的最大传输时延、平均传输时延均随权值w的增加而提高, 最后趋于恒定值。HPGH算法下eMBB业务的最小吞吐量总是大于CWLAP算法。对于uRLLC业务的最大传输时延而言, HPGH算法和CWLAP算法的性能与权值w的取值有明显关系。此外, 在w∈[0, 0.2]时, 不论是HPGH算法还是CWLAP算法, 其性能都有较大提升, 对于w∈[0.2, 1.0], w的变化对系统性能基本没影响。因此, 可以认为在本文场景中, w∈[0, 0.2]有效。本次仿真用户数分别为30、60, 可以看出, 不管w取何值, eMBB业务的最小吞吐量和平均吞吐量均随用户数的增加而减小, uRLLC业务的平均传输时延随用户数的增加而增大。

为更直观地显示不同w值对系统性能的影响, 根据图 3的分析结果, 分别取w=0.05(将uRLLC业务的最大传输时延作为更重要的性能指标)和w=0.5(将eMBB业务的最小吞吐量作为更重要的指标), 对MDRA、HPGH和CWLAP 3种算法进行仿真分析, 结果如图 4所示。从图 4可以看出, 对于eMBB的最小吞吐量和平均吞吐量而言, HPGH算法总是优于CWLAP算法, 且这2种算法都明显优于MDRA算法。对于uRLLC的最大传输时延和平均传输时延而言, HPGH算法和CWLAP算法相较于MDRA算法均有明显改善, 且当w=0.05时, HPGH算法和CWLAP算法在降低uRLLC最大传输时延和平均传输时延方面有显著效果。

图 5所示为w=0.05、w=0.5时3种算法的系统吞吐量变化情况。从图 5可以看出, 在w=0.05、w=0.5的情况下, HPGH算法系统吞吐量总是高于CWLAP算法。此外, w的变化不会改变系统吞吐量随用户数的变化趋势。

通过上述分析可以看出, 相较于CWLAP算法, HPGH算法能够提高eMBB业务的最小吞吐量和平均吞吐量, 在一定范围内降低uRLLC业务的最大传输时延和平均传输时延, 并提高系统的总体吞吐量。权值w可作为eMBB业务最小吞吐量和uRLLC业务最大传输时延的折中, w越大表示指标a占比越大, 当切片的最小吞吐量和最大传输时延确定时, 总能求得最适合的权重系数w。采用MDRA算法在提升eMBB业务吞吐量的同时也会提升uRLLC业务的吞吐量, 从而造成不必要的带宽资源浪费。

4 结束语

为了提升eMBB业务的最小吞吐量并降低uRLLC业务的最大传输时延, 本文提出一种基于网络切片的带宽资源分配算法HPGH。仿真结果表明, 该算法能够实现对带宽资源的按需分配, 并提高系统的总吞吐量。但HPGH算法只考虑eMBB和uRLLC 2种业务类型, 未涉及5G三大应用场景中的mIoT, 因此, 对mIoT业务的带宽资源进行高效编排将是下一步的研究方向。