基于网络切片的网络效用最大化虚拟资源分配算法

唐 伦 张 亚 梁 荣 陈前斌



基于网络切片的网络效用最大化虚拟资源分配算法

唐 伦 张 亚*梁 荣 陈前斌

(重庆邮电大学移动通信技术重点实验室 重庆 400065)

为了实现网络资源的动态分配，提高网络资源利用率，满足用户业务多样性带来的切片网络差异需求，该文提出一种基于网络效用最大化的虚拟资源分配算法。该算法采用商业化模式将频谱资源作为收益载体，并对不同切片网络进行差异化定价。同时将计算资源和回程链路作为开销，还考虑了切片网络对计算资源和频谱资源的差异性需求，最后以最大化网络收益建立效用模型。并通过拉格朗日对偶分解设计了分布式迭代算法对效用模型进行求解。仿真结果表明，该算法提高了服务用户比例，并使得网络资源获得最大收益。

网络切片；虚拟化；资源分配；网络效用

1 引言

移动用户业务的多样性和对时延、速率的高要求，给现有的网络带来了巨大的挑战。无线虚拟化和网络切片技术被认为是提高网络灵活性，保证用户服务质量，提供业务多样性和增加网络收益的有效方法[1]。无线网络虚拟化是一个广泛的概念，可以指频谱的共享、设备的虚拟化和空口的虚拟化等[2]。它主要是将有限的网络资源经过分割和重组，形成逻辑上相互独立的虚拟网络资源供各个切片网络使用，以此实现网络资源的重复高效利用，减少运营商的成本投入[3]。所以，无线虚拟化技术给网络资源的分配带来了多样性和灵活性，也是实现网络切片的有效途径。如何对无线虚拟资源进行高效的分配是对无线虚拟化技术作用的检验，也是实现无线虚拟化的最终目标。

无线虚拟化资源分配已经成为当下研究的热点。文献[4]研究了多无线网络场景下的频谱资源分配问题，提出了一种机会频谱共享方法来更有效地实现频谱资源的分配。但该文献未考虑不同切片网路的不同需求。文献[5]为了提高频谱资源利用率同样设计了一种机会频谱共享算法，考虑了在满足最低频谱需求下怎样提高频谱利用率。但该文献仅仅对频谱资源进了考虑，也没有区分用户业务的不同。文献[6]在网络功率受限的情况下，通过多步动态优化实现网络虚拟化和资源分配，但文中只考虑了频谱资源的分配。文献[7]通过小区关断机制设计了一种提高能效同时保证用户服务质量的虚拟资源分配算法。该文献也未考虑不同业务用户的需求差异。文献[8,9]将回程链路作为网络开销，以网络效用作为目标函数，此方法比较符合网络虚拟化中资源分配价值准则，但文献中未考虑计算资源。

虽然现在已有不少的文章对无线虚拟化环境下资源分配算法进行了研究。但普遍只考虑了频谱资源的分配，且未充分体现用户业务的差异性，同时多数文献都是以网络吞吐量作为优化目标。所以，本文利用商业化模型设计了一种基于网络切片的网络效用最大化虚拟资源分配算法。该算法首先利用频谱资源作为收益来源，将计算资源和回程链路作为网络开销的两个元素；其次，还考虑了不同切片网络收益差异性和对计算资源以及频谱资源的不同需求；再次，以虚拟化网络中产生的最大化收益作为优化目标建立效用模型；最后，采用拉格朗日对偶方程设计了分布式迭代算法对模型进行求解。

2 系统模型与效用方程

2.1系统模型

本文系统模型如图1所示，整个网络被分为3层模型，从下至上依次为基础设施提供商(Infrastructure Provider, InP)，移动虚拟运营商(Mobile Virtual Network Operator, MVNO)和服务提供商(Service Provider, SP)。在该系统中InP拥有网络设备、频谱资源(Spectrum Resources, SR)、计算资源(Computing Resources, CR)和回程链路资源(Backhaul Resources, BR)等物理网络资源；MVNO从InP中租用网络设备和无线资源形成虚拟网络资源，即虚拟频谱资源(Virtual Spectrum Resources, VSR)、虚拟计算资源(Virtual Computing Resources, VCR)以及虚拟回程链路资源(Virtual Backhaul Resources, VBR)，再将虚拟网络资源分配给属于不同切片网络的SP，通过向SP收取相应的服务费用而获得收益；在这里SP直接与用户相连接，MVNO分配的虚拟网络资源实际上是直接分配给与各个SP相连接的用户。在整个网络结构中，虚拟网络资源的有效分配直接影响着MVNO的收益，所以虚拟资源分配算法将对MVNO起着重要作用。

(3)

(5)

用户在基站上所占用的计算资源与用户需要的CPU、存储空间和服务时间等都有关系，本文研究的重点是将计算资源作为效用函数和约束条件的一个因素，精确的计算资源表达不是文章研究的主要内容。考虑到基站的正常运行条件，必须实现频谱资源和计算资源的匹配，可以看作每个基站所分配带宽的每个子载波需要匹配一个最小的计算单元(Computing Unit, CU)，每个最小计算单元具有相同的计算能力MIPS(每秒处理百万条指令Million Instructions Per Second)[11]。所以在文中简单定义基站的计算资源与它的频谱资源成正比关系：，为了计算简便，这里令。在此，用户在基站上占用的计算资源比例表示为。所有与基站相连接的用户占用计算资源总和不能超过该基站的计算资源限制，所以，

考虑到为满足不同切片网路，即不同SP之间的网络服务需求，分配给各个不同SP的频谱和计算资源必须满足不同SP的最低频谱资源需求和最低计算资源需求，所以不同业务切片网络的频谱资源和计算资源限制可表示为

(7)

2.2效用方程

(10)

所以虚拟运营商的总收益效用模型可以表示为

(12)

3 分布式算法

3.1算法分析

所以对偶问题为

(16)

(18)

(19)

同理，根据式(18)可以得到：

(22)

3.2算法描述

本文设计了分布式迭代算法对问题进行求解，具体执行过程描述如表1和表2所示。

表1迭代算法1

步骤1 初始化对偶变量；步骤2(1)根据迭代算法2求得数学关系和的局部最优解；(2)将与的局部最优解代入式(22)，再根据计算每个对应的；(3)对每个基站，取的最大值以确定最优的用户和业务对；(4)根据式(23)求得连接标识局部最优解；(5)将分别代入式(20)，式(21)确定局部最优解和；步骤3 根据次梯度算法更新对偶变量；步骤4 。检查收敛条件是否满足，否则跳转步骤2。当满足收敛条件，则获得问题式(12)的连接标识全局最优解，频谱资源分配比例全局最优解和计算资源分配比例全局最优解。

表2迭代算法2

步骤.1 初始化对偶变量；步骤2 根据式(20)，式(21)求得数学关系和；步骤3 根据次梯度算法更新对偶变量　；步骤4 。当满足收敛条件，则获得与的局部最优解，否则跳转步骤2。

4 性能仿真与分析

为验证本文提出的基于切片的虚拟资源分配(Slicing-based Virtual Resource Allocation, SVRA)算法，这里主要对LTE系统下行链路进行仿真，并将文献[14]中的多小区动态资源分配(Multi-cell Dynamic Resource Allocation, MDRA)算法和文献[15]中部分资源预留(Partial Resource Reservation, PRR)算法进行比较分析。为提高仿真的准确性和普遍性，仿真将基站进行固定，每次随机改变用户位置，并采用多次仿真求平均值的方式对结果进行统计分析。具体仿真参数设置如表3所示。

如图2比较了不同算法下，服务用户数量随总用户数量的变化情况。可以看出，3种算法的服务用户都随着总用户的增加而增加。此外，在相同总用户数的情况下，SVRA算法的服务用户要高于MDRA算法，且MDRA算法优于PRR算法。因为SVRA算法和MDRA算法都是在满足业务最低速率下，将所剩资源进行统一协调调度，提高了整体资源的利用率，而PRR算法将固定保留部分资源保障自身用户的服务质量，所以会降低部分资源的利用率，从而导致整体服务用户数量减少。另一方面，SVRA算法是以资源产生的效用为目标对资源进行最大化价值利用，进而SVRA会选择更多用户进行服务从而使得网络产生最大收益。MDRA则是以最大速率进行资源共享，忽略了资源产生的收益。

图3评估了不同速率要求下，3种算法服务用户的数量，此时用户总数设置为90。根据结果可以看出，速率要求越高所对应的满足要求的服务用户数量将会减少。在低速率区域3种算法的服务用户数量比较接近。但是，当速率要求超过一定值时，服务用户有明显的下降趋势，且这种下降趋势随着速率要求的增加而进一步增大。此外，当速率要求较小时SVRA算法将优于MDRA算法和PRR算法，但是当速率要求超增加到一定值后MDRA算法将优于SVRA算法。这是因为PRR算法保留了过多的固定资源，降低了整体资源的使用效率。另一方面，MDRR是以最大化吞吐量为目标为准则进行资源分配，所以会更多地接入高速率用户从而达到最大化网络吞吐量的目的。

图4比较了3种算法下系统吞吐量的变化情况。可以看出，随着用户数的增加，系统吞吐量也会逐渐增大，但是当总用户数到达一定值时系统吞吐量将趋于稳定，此时网络到达最大负载值。图4中还可以看出，在相同用户数情况下，SVRA算法的吞吐量会高于PRR算法。这是因为从图2，图3中看出，SVRA算法的服务用户数和整体用户速率都高于PRR算法，这必将会带来吞吐量的提升。但是，以最大化吞吐量为目标的MDRA算法的吞吐量将要略高于SVRA算法。这是因为MDRA算法会优先选择高速率用户分配资源，以最大化吞吐量，而SVRA算法则是以实现资源最大收益为目标进行资源分配。

表3仿真参数

参数数值参数数值 基站数量J3热噪声密度-174 dBm/Hz 用户数量K4,6,8,10,12,14,16/(业务cell)信道模型3D-Uma[16] 业务数量I3资源单价 100,2,40 units/MHz 站间距500 m最低带宽需 4,2,0.5 MHz 基站发送功率46 dBm最低计算资源需求 4,2,0.5 xCU 载波频率2 GHz业务收费单价 20,15,10 units/Mbps 带宽10 MHz(50 PRBs)业务最低速率要求20,10,1 Mbps 回程链路限制10 MHz迭代步长0.05 计算资源CU权衡参数(0.1,1)

图3 不同速率要求下服务用户的比较

图4 系统吞吐量随总用户数的变化趋势

图5是不同用户数下，总效用变化情况。图5中可以看出用户数的增加会引起总效用的升高，但是这种上升幅度在随着用户数的增加而减少，不难推断当用户数到达一定数值后，网络整体效用将会趋于一个稳定值。这是因为网络资源是有限的，网络中服务用户也将会到达一个上限，所以带来的网络收益效用也将会有个最大值。并且，图中结果显示SVRA算法的总体效用会优于其它两种算法，很好地体现了该算法最大化网络效用的特点。此时权衡参数的取值为0.5，不同对效用函数的影响如图6所示。

图7在各种业务用户数相同的情况下，比较了不同业务对效用函数的影响，此时权衡参数取值为0.5。图中看出，相同算法下业务收益越高将会带来更高的收益效用。这是因为相比于低收益业务，高收益业务将会分得更多的频谱资源，以此来实现网路收益的最大化。图中还可以看出，对于相同业务SVRA算法优于其余两种算法，这与图5表现出的趋势相吻合。

5 结束语

本文基于网络切片技术提出了一种网络效用最大化虚拟资源分配算法SVRA。该算法采用商业化模型将频谱资源作为收益载体，并对不同切片网络进行差异化定价，同时将计算资源和回程链路资源作为虚拟运营商的两个开销因素，最后采用网络收益作为效用目标函数进行建模。仿真结果表明，本文算法能有效提高服务用户比例，使网络资源产生最大化收益。但是，本文考虑的计算资源模型比较简单，随着大数据、云计算等技术的发展，将会对计算资源提出更高的要求，所以后续研究中可以对计算资源进行更加精确的建模。并且，低碳绿色通信已经成为以后通信发展的方向，用户体验也会受到更多的关注，所以效用函数中也可以增加更多的权重因素，例如能效和用户服务质量等，但这可能会带来更大的复杂度和计算量。

图5 网络总效用比较

图6 权衡参数对效用函数的影响

图7 不同业务带来的效用比较

[1] HAMMAD A, NEJABATI R, and SIMEONIDOU D. Cross- layer optimization of network resource virtualization in IP over O-OFDM networks[J]., 2016, 8(10): 765-776.doi: 10.1364/JOCN.8.000765.

[2] ROST P, BERBERANA I, MAEDER A,. Benefits and challenges of virtualization in 5G radio access networks[J]., 2015, 53(12): 75-82. doi: 10.1109/MCOM.2015.7355588.

[3] RAHMAN M M, DESPINS C, and AFFES S. Design optimization of wireless access virtualization based on cost & QoS trade-off utility maximization[J]., 2016, 15(9): 6146-6162. doi: 10.1109/TWC.2016.2580505.

[4] YANG M, LI Y, JIN D,. Opportunistic spectrum sharing based resource allocation for wireless virtualization[C]. IEEE Seventh International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS), Taichung, 2013: 51-58. doi: 10.1109/IMIS.2013.18.

[5] LIU X, LI M, SONG M,. Wireless virtual network embedding based on spectrum sharing allocation[C]. IEEE 11th International Conference on Computer Science & Education (ICCSE), Nagoya, 2016: 670-675. doi: 10.1109/ ICCSE.2016.7581660.

[6] LU X, YANG K, and ZHANG H. An elastic sub-carrier and power allocation algorithm enabling wireless network virtualization[J]., 2014, 75(4): 1827-1849.

[7] ZOU S, YANG F, TANG Y,. The resource mapping algorithm of wireless virtualized networks for saving energy in ultradense small cells[OL]. https://www.hindawi.com/ journals/misy/2015/958431/.

[8] LIANG C and YU F R. Virtual resource allocation in information-centric wireless virtual networks[C]. IEEE International Conference on Communications (ICC), London, 2015: 3915-3920. doi: 10.1109/ICC.2015.7248935.

[9] CHEN L, YU F R, JI H,. Distributed virtual resource allocation in small-cell networks with full-duplex self-backhauls and virtualization[J]., 2016, 65(7): 5410-5423. doi: 10.1109/ TVT.2015.2469149.

[10] NG D W K, LO E S, and SCHOBER R. Energy-efficient resource allocation in multi-cell OFDMA systems with limited backhaul capacity[J]., 2012, 11(10): 3618-3631. doi: 10.1109/ TWC.2012.083112.111951.

[11] 师雪霖, 徐恪. 云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013, 36(2): 252-262.

SHI Xuelin and XU Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]., 2013, 36(2): 252-262.

[12] FOOLADIVANDA D and ROSENBERG C. Joint resource allocation and user association for heterogeneous wireless cellular networks[J]., 2013, 12(1): 248-257. doi: 10.1109/TWC. 2012.121112.120018.

[13] BOYD S and VANDENBERGHE L. Convex Optimization [M]. Cambridge: Cambridge University Press, 2004: 35-475.

[14] KAMEL M I, LE L B, and GIRARD A. LTE multi-cell dynamic resource allocation for wireless network virtualization[C]. IEEE Wireless Communications and Networking Conference (WCNC), New Orleans, 2015: 966-971. doi: 10.1109/WCNC.2015.7127600.

[15] GUO T and ARNOTT R. Active LTE RAN sharing with partial resource reservation[C]. IEEE 78th Vehicular Technology Conference (VTC Fall), Las Vegas, 2013: 1-5. doi: 10.1109/VTCFall.2013.6692075.

[16] 3GPP TR 36.873 V12.2.0. Study on 3D channel model for LTE[S]. 2015.

Virtual Resource Allocation Algorithm for Network Utility Maximization Based on Network Slicing

TANG Lun ZHANG Ya LIANG Rong CHEN Qianbin

(,,400065,)

To realize the dynamic allocation of network resources, improve the network resources utilization and meet the demand of the diverse networks, this paper proposes a virtual resource allocation algorithm based on network utility maximization. The spectrum resource is used as the revenue and the differentiated price is commercialized according to slicing networks. It also takes the computing resources and the backhaul as the cost, and also takes into account the different demands of the slicing network on the computing resources and spectrum resources. Finally, the utility model is established to maximize the network revenue. A distributed iterative algorithm is designed to solve the utility model by Lagrangian dual decomposition. The simulation results show that the algorithm improves the percentage of service users and maximizes the network revenue.

Network slicing; Virtualization; Resource allocation; Network utility

TN929.5

A

1009-5896(2017)08-1812-07

10.11999/JEIT161322

2016-12-08；

改回日期：2017-04-17；

2017-05-18

张亚 516395398@qq.com

国家863计划项目(2014AA01A701)，国家自然科学基金(61571073)

The National 863 Program of China (2014AA01A701), The National Natural Science Foundation of China (61571073)

唐 伦： 男，1973年生，教授，博士，主要研究方向为新一代无线通信网络、异构蜂窝网络、软件定义无线网络等.

张 亚： 男，1990年生，硕士生，研究方向为软件定义无线网络、网络虚拟化.

梁 荣： 男，1989年生，硕士生，研究方向为密集蜂窝网络容量覆盖与负载均衡.

陈前斌： 男，1967年生，教授，博士生导师，主要研究方向为个人通信、多媒体信息处理与传输、下一代移动通信网络、异构蜂窝网络等.