基于拍卖的网络切片虚拟资源分配算法研究

施颖洁，陈前斌，杨希希，唐 伦

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

0 引 言

5G时代，将有各种多样的业务及应用场景，有着不同的网络需求[1-2]。NGMN(next generation mobile networks)对于5G的愿景是5G可以创造一个全方位移动连接社会的系统[3-4]。为了解决多样化业务在网络速率、时延、可靠性方面的问题，根据业务对网络的功能、安全性等需求为每一种类型的业务都建立一个单独的网络，网络成本将会超出预算。因此，5G提出了构建相互独立且具有灵活性的网络切片[5]，为不同应用场景下的用户需求提供有力保障。

网络切片是满足物理基础设施上针对不同业务需求的虚拟网络。网络切片理论上可使多个切片共享相同的物理资源，该技术可以动态地调整虚拟网络的功能、大小等，有效提高资源利用率，较之传统架构可减少更多的实施成本[6]。目前虚拟网络切片的资源分配通常由基础设施提供商(infrastructure provider, InP)根据移动虚拟网络运营商(mobile virtual network operator, MVNO)中用户的需求决定最终资源分配方案。文献[7-8]以时延为约束条件，最大化网络吞吐量为目标构建优化模型进行资源分配。文献[9]通过建立马尔科夫决策模型，利用树搜索算法使网络成本最小化。但是，这些研究没有考虑到切片业务之间需求的区别，并且，没有考虑到切片空闲资源的回收，不能及时灵活调整切片的资源，造成资源浪费、资源利用率低。因此，在5G网络切片资源分配中考虑切片中资源的灵活性十分重要。

文献[10-11]将不同的切片分配给不同的虚拟运营商，获取最大收益。文献[12]以用户速率为约束条件，为不同的切片用户分配资源。以上研究中，网络切片可以相互调用资源，或是直接为用户“打标签”分配资源，不能较好地体现切片隔离性。网络切片理论上可使多个切片共享相同物理资源，网络切片中若一个切片发生拥塞现象，不能对其他切片造成影响[13]，所以，切片之间的隔离十分重要。

基于以上研究，本文抽象化无线资源，提出一种基于拍卖的虚拟资源动态分配算法。该算法首先根据切片阻塞率量化切片优先级，根据切片资源剩余量计算需求资源报价。其次，考虑资源需求量与资源总量之间的关系，确定资源拍卖价格。其中，资源总量包括系统剩余资源和回收资源。最后，提出一种新型的拍卖模型，综合考虑系统的总收益和用户需求进行资源分配，在满足用户服务质量(quality of service，QoS)需求的同时使收益最大化。

1 虚拟网络切片系统架构

1.1 虚拟网络切片系统

在5G网络中，由于大量不同的应用场景同时接入，网络切片的设计必须灵活且完全独立[17]。网络切片的灵活性可以动态满足各自业务及用户的需求，同时网络切片具有绝对独立性，各个切片间不能相互影响。

针对不同切片的业务需求，本文提出一种基于拍卖的虚拟资源动态分配算法，保证不同业务用户的QoS需求。首先，切片根据用户状态触发开关提出需求申请；其次，以价格为信誉因子，根据切片的优先级，回收并分配资源；然后，将切片分配资源时的空隙资源整合作为预留资源，减小分配资源带来的时延；最后，利用虚拟拍卖策略在满足用户QoS的同时使得收益最大化。

1.2 资源虚拟化方案

资源的虚拟化[2]，即将物理资源抽象化，并根据抽象资源的分配结果分配物理资源。本文抽象化资源的过程分为4个步骤：初始化、资源拍卖、提交方案以及资源映射。MVNO根据切片的业务需求，制定各类业务的切片，并为其分配一定资源以满足基本需求；用户根据业务类型分别接入各个切片，切片根据用户状态向MVNO进行反馈，并制定投标信息，MVNO根据决策为用户分配资源并及时对空隙资源进行整合，通过拍卖策略得到最终分配结果；InP根据请求与MVNO建立购买、租借策略，并分配物理资源；最后MVNO根据计划向InP租借物理资源。

在动态分配资源的过程中，根据切片状态提交异常信息，由业务需求以及用户状态联合制定切片优先级，在分配资源过程中优先级有着很重要的作用。分配资源时由于各切片资源需求差异会留有资源空隙，此时MVNO需要将这些资源空隙整合作为预留资源，在资源临界点作为缓冲资源进行分配。

1.3 虚拟资源拍卖机制

本节对基于内部拍卖的虚拟资源分配算法的系统架构及其工作机制进行详细介绍。该算法是在MVNO中根据切片提供的需求与回收信息，以及MVNO整合的空隙资源信息，形成一个如图1所示的拍卖模型。

该拍卖策略的核心思想是根据用户状态决定切片状态，计算切片优先级，以价格代替信誉因子，以此计算网络切片资源需求拍卖报价以及资源回收报价，从而将资源优化分配问题转换成为一个内部拍卖问题。MVNO处理资源分为2个部分，分别是资源分配(Allocate)和资源回收(Recyeling)(见图1中的虚线连接部分)，只有切片根据自身的状态触发异常开关时，需要向MVNO提交申请，否则切片只需对自身状态进行监测，切片不能自由调用资源，回收的资源和空隙资源均由MVNO统一处理。

图1 虚拟资源分配拍卖模型Fig.1 Virtual resource allocation auction model

整个拍卖过程中的计算分配量和实际分配资源都在MVNO中进行，切片没有实际的计算功能，只需要监测和记录，MVNO统一管理资源，避免切片直接接触造成干扰，在回收资源后和整合的空隙资源再次整合并分配资源；其次切片只具有监测和记录的能力，当切片异常时提交该时刻的切片状态，最后为各个切片确定需求量、供给量和报价信息，并综合考虑切片优先级为其分配资源。

2 系统模型

2.1 用户模型

每个切片接入对应类型的用户，因此，各个切片的用户状态是不同的。本文综合考虑切片业务的特殊性和用户状态计算切片的阻塞率，并分析切片当前的用户状态，判断切片是否需要资源或有空闲资源。最后，当切片属于异常状态时需要向MVNO提交当前切片信息。

假设，切片中的用户到达率服从参数为λa的泊松分布，业务持续时间Tk服从参数为μa的指数分布，在业务执行过程中，当业务中断，用户回到当前业务的概率为Pb，用户恢复当前业务的到达率服从参数为λa的泊松分布，且用户离开的时间服从参数为μb的指数分布。

切片中资源以其自身的定义，假设切片已有资源的数量为Nl={1,2,…,N}，Nnew为新用户接入时所用的资源，Nl与Nnew的差值为切片的预留资源。在切片中，最大服务率为NRlμb。其中，NRl为服务切片l的资源数。那么切片强度为

(1)

(1)式中，λl是切片l的业务总到达率，其由新业务和中断业务用户到达率构成，可以写成

(2)

(2)式中：等式右边第1项是切片l的业务达到率；第2项是切片l中业务中断后恢复的达到率；第3项是当用户在执行切片l中的业务，被其他业务打断的概率。则新业务的业务阻塞率和恢复业务的阻塞率分别为

(3)

(4)

2.2 切片模型

切片用户的QoS需求主要体现在速率和时延2个方面。每个切片具有其特殊大小的子信道带宽，可以直接为切片用户服务。当资源不足时，分配的子信道带宽若不能满足需求，则另外为切片增加CPU(central processing unit)，减少时延。

切片状态为Xl={Ul,Ml,xl}，Ul,Ml分别代表用户状态和剩余资源状态，用户状态包括切片强度Γ和业务阻塞率P；xl是一个二进制数，其值为0代表正常状态，为1代表异常状态。

切片中资源为Rl时，已有资源的数量定为NRl={1,2,…,N}。每个切片根据自己的资源数和需求量定制虚拟资源的参数，使其可以直接分给用户使用。{Cblock,Pclock}代表切片的子信道数和CPU，切片的剩余资源状态为R={Crem,Prem}，MVNO中的总资源可表示为{C,P}，其中，MVNO中的子信道数和CPU分别为

(5)

(6)

(7)

(8)

2.3 优先级及时延权重因子

根据当前切片的阻塞率和该切片业务需求的最大阻塞率计算切片的优先级，且最大阻塞率根据当前切片剩余资源状态实时更新。切片优先级越高则表示当前切片时延与业务需求差距越大，需要优先分配资源。若未完成的已决定的分配没有结束时，新的优先级已经形成，则允许优先级较高的切片进入分配队列。异常信息的紧急程度U与用户状态有关。

(9)

(9)式中，当xl=1时，0

优先级仅考虑了切片当前用户状态，而不同场景下，时延要求的差异尤为突出，针对不同的时延需求，引入一个时延权重因子

(10)

(10)式中：ρl是切片l容忍的最大时延门限；τl是切片允许的最大丢包率。

3 资源分配算法

3.1 确定报价

由于各个切片所定义的虚拟资源数不同，资源的收益也不同，MVNO需要综合剩余资源量与资源需求量，资源供给量统一单位资源的参数和定价，处于异常状态的切片将其状态提交，MVNO为各切片确定资源需求量与供给量。

当xl=1时,切片异常，MVNO需要根据具体的切片状态判断切片的异常分类并计算需求信息、回收信息以及相应的报价。需求信息Ql是针对各切片的不同需求以及当前的用户状态，由恢复业务的用户需求以及新用户需求2部分构成。恢复业务用户需求需要考虑其需求资源没有用到的可能性。根据MVNO计算需求信息Ql，制定其估价bl(Ql)为

(11)

切片的灵活性即切片中的资源会根据当前的用户状态实时改变的能力，当xl=1且MVNO判断需要回收切片空闲资源时，MVNO根据切片状态计算空闲资源Wl，并确定其报价al(Wl)，MVNO预留资源不够时，则调用切片的空闲资源。

al(Wl)=ζ[ql(NRl)-ql(NRl-Wl)]

(12)

(12)式中：ζ∈[0,1]是折扣因子；ql(NRl)是切片总资源的收益；ql(NRl-Wl)是切片的现有收益。

3.2 内部拍卖资源分配算法

可用资源包括其他切片中的空闲资源，MVNO首先整合空隙资源和切片空闲资源作为预留资源，当到达资源量的零界点时，则分配预留资源作为缓冲资源。本文以最大化需求收益与供给收益的差值为目标，建立拍卖获胜者问题模型

(13)

s.t. (a)wl∈{0,1}

(d)Pw,l∈{0,1}

(g)δRmin≤Rl

因为业务场景不同，需要优先满足优先级高且时延要求较高的切片，此时的资源分配分为2个阶段，第1阶段采用贪婪算法分配子信道，此时假设CPU与子信道按比例分配，当子信道分配完毕后再进行第2阶段的CPU分配和调整。基于以上讨论，首先进行优化问题Q1的第1阶段的资源分配，如Q2所示。

(14)

s.t. (a)cl∈{0,1}

(d)δRmin′≤Rl

现在问题已简化为CPU与子信道按比例分配的问题。cl为一个二进制数，表示切片是否中标；(b)式用于保证切片不会重复中标；(c)式表示分配的资源不超过总资源量；(d)式表示切片的资源需要满足用户及业务的需求，Rmin′是切片可接受的最小速率。

分配资源后检查切片是否能满足速率需求，如果不能满足，则再调整分配资源，直至速率满足或者优先级和时延权重因子影响的数组排列后移。在我们提出的算法求解过程中，对每一个有需求的切片，都会优先执行以下过程

算法1资源预分配算法。

输入Q:需求资源量；B(Q):需求资源报价；

W:回收资源量；B(W):回收资源报价

输出Rrem: 剩余资源量；

Rl：各切片的资源量

Rl—allocate：各切片的分配资源量;

1: while a new time period starts do

2: for(l= 1;l<=L;l++)

3:δl← 0;

4:ζl← 0; //初始化各切片的优先级和时延因子

5: end for

6: whilexl=1

7: if(fl=1)

10: else if(fl=0)

11:δ←δl;

12:ζ←ζl; //更新各切片的优先级和时延因子

13: end if

14:m← Max(δ1,δ2,…,δL);

15:n← Max(ζ1,ζ2,…,ζL);

//根据优先级和时延权重找到最大值

16: if(C>0 &P>0)

17: for(m=1;m<=L;m++)

18: for(n=1;n<=M;n++)

19:P←P-xCl—allocate;

20:C←C-Cl—allocate;

21:Rl←Rl+Rl—allocate;//分配并更新资源量

22: end for

23: end if

24: end while

25: end while

在第1阶段，分配资源时首先假设CPU与子信道成比例分配，但由于业务需求不同，CPU需求差异较大，在第2阶段，任务是在已分配资源的基础上对CPU进行实际分配和调整，尽量提高系统频道利用率及吞吐量。在第1阶段结束后，可以得到一个分配矩阵，在此阶段中首先需要判断切片需求是否已经满足，根据原始需求与第1阶段分配结果得到新的需求。基于Q2的分配结果，原优化模型Q1的第2阶段优化问题如Q3所示。

(15)

s.t. (a)pl∈{0,1}

(d)δRmin≤Rl

(15)式中：pl为一个二进制数，表示切片是否中标；(b)式用于保证切片不会重复中标；(c)式为总资源量的限制；(d)式表示切片的资源需要满足用户及业务的需求，此限制条件与Q2的一致。

此时的报价是原始报价与分配结果的差值，且只有CPU需求，不再对子信道进行分配。

算法2CPU调整分配算法。

输入Q:需求资源量；

输出B(Q):需求资源报价；

Pl：各切片的资源量；

1: while pre-allocation is over do

3: if(δlRmin>=Rl)

4:B’(Q)←B(Q);

5:δ←δl; //更新需求资源报价和切片优先级

6: end if

7:x← Max(δ1B′(Ql),δ2B′(Ql),…,δLB′(Ql));

8: for(x=1;x<=X;x++)

9: if(Premaind> 0)

10:Pl←Pl+Pl—allocate;

11:P←P-Pl—allocate; //分配并更新资源量

12: else if(Premaind<=0)

13: break;

14: end if

15: end for

16: return ;

17: end while

4 性能仿真与结果分析

本小结参照3GPP协议标准[14]，对上述虚拟资源分配算法进行数值仿真，表1为仿真参数设置。

表1 仿真参数设置

在实验中，设置5个网络切片，当切片状态达到最低资源利用率门限，则该切片提供供给资源，当切片状态达到阻塞率门限，则该切片需要分配资源，将最低资源利用率的最大值设置为0.5，而阻塞率决定是否为切片分配资源，所以，设置切片阻塞率为0.1时可以开始考虑为切片分配资源。由于切片业务应该具有较大的差异性，所以将切片的最低资源利用率门限值和阻塞率门限值分别设置为{0.5,0.4,0.3,0.2,0.1}和{0.1,0.2,0.3,0.4,0.5}，如此可以遍历所有情况，例如切片1最低资源利用率门限值和阻塞率门限值分别为0.5和0.1，即该切片对时延要求较高，当阻塞发生即可以分配资源。

图2给出了本文资源分配算法与按比例分配算法、按优先级分配算法的资源分配情况。比例公平算法按比例分配所有资源，使每个切片都能得到资源，保证了切片的公平性；按优先级分配算法保证了高优先级切片的所需资源，这样可能出现高优先级切片将资源用完，低优先级切片则无资源可用；本文的算法同时考虑切片的需求和切片的优先级，此时没有空闲资源，但存在空隙资源，剩余的空隙资源作为预留资源，等待下一周期的空闲资源或空隙资源一并整合分配。

图2 本文与比例公平算法、Priority分配算法分配结果的比较Fig.2 Compares with the results of the proportional fairness algorithm and the Priority distribution algorithm

为切片分配资源，首先考虑的是用户QoS需求，所以用户的满意度是切片资源分配的重要指标，本文设置的用户满意度的主要因素为系统是否为切片分配了其所需要的资源，并达到其QoS需求。

图3为本文资源分配算法与按比例分配算法、按优先级分配算法在资源不够的情况下各优先级对所分配资源的满意度的比较。随优先级的增加，按比例分配算法满意度降低，此算法虽然尽可能地保证所有切片的需求，但对于优先级高的用户考虑不周；按优先级分配算法可以保证优先级高的切片，但优先级低的切片满意度却很低，因为资源不够的压力完全转移给了优先级低的切片；本文算法的满意度随优先级的增加而增加，尽可能地保证优先级高的切片，而对优先级低的切片也分配一定的资源。

图3 优先级增加，本文与比例公平算法、Priority分配算法满意度比较Fig.3 Satisfaction compares with the proportional fairnessalgorithm, Priority distribution algorithm

图4为当所有切片需求同时增加时各优先级的切片所得到的资源情况，当资源足够时，各个切片均可得到相应的资源，当达到总资源的临界点时，调用整合的空隙资源继续分配，所以，切片获得的资源依然有一定程度的增加；当总资源不够时，将依次调用优先级低的切片资源，但依然要满足低优先级切片的最低需求，资源分配趋于稳定前开始调用下一优先级切片的资源，所以，资源量从最低优先级开始依次趋于稳定。

图4 切片需求同时增加，各优先级的切片所得到的资源情况Fig.4 Different slices own different priority obtained resource

图5为当资源不够且所有切片需求一致时各优先级的切片所得到资源的过程。从图5可看出，从优先级较高的切片开始，切片依次获得所需资源，但在满足最高优先级需求的同时也对其他优先级的切片有资源分配，在分配趋于稳定时，优先级较低的切片还没有得到全部所需资源，但此时资源已经不足，之后的切片获得的资源缓慢增加正是在分配预留资源直至全部预留资源分配完毕。

图5 切片需求一致时，各优先级的切片所得到资源的过程Fig.5 Slices have same consistent, the process of different slices own different priority obtained resource

5 结束语

本文针对5G网络中虚拟网络切片灵活且完全独立，动态满足各自业务及用户的需求，各个切片间不能相互影响的要求，提出一种双向且动态、基于内部拍卖的网络切片虚拟资源分配策略。首先，抽象化无线资源，对不同虚拟网络切片的不同业务需求定制其特殊虚拟资源需求，从用户层面提出需求，根据切片业务以及用户状态制定优先级，将业务需求与用户需求结合；切片根据用户状态触发开关提出需求申请；以价格为激励，根据切片的优先级，综合考虑系统的总收益和用户需求回收并分配资源；将切片分配资源时的空隙资源整合作为预留资源，减小分配资源带来的时延，最后，提出一种新型的内部拍卖模型，利用虚拟拍卖的方式决定资源分配情况。仿真结果表明，本文提出的资源分配算法可以在满足用户QoS的同时使得收益最大化。

参考文献：

[1] IMT-2020(5G)推进组. 5G无线技术架构白皮书[EB/OL]. (2015-11-03)[2017-07-06]. https://max.book118.com/html/2017/0607/112172915.shtm.

IMT-2020 (5G) push group. white paper of 5G wireless technology architecture[EB/OL]. (2015-11-03)[2017-07-06]. https://max.book118.com/html/2017/0607/112172915.shtm.

[2] ALZENAD M, SHAKIR M Z, YANIKOMEROGLU H, et al. FSO-based Vertical Backhaul/Fronthaul Framework for 5G+ Wireless Networks[J]. IEEE Communications Magazine, 2016(3)：1-9.

[3] COSTA M, HEISKA K. Joint Device Positioning and Clock Synchronization in 5G Ultra-Dense Networks[J]. IEEE Transactions on Wireless Communications, 2017, 16(5):2866-2881.

[4] SAMDANIS K, COSTA-PEREZ X, SCIANCALEPORE V. From network sharing to multi-tenancy: The 5G network slice broker[M]. New York: IEEE Press, 2016.

[5] CHEN J L, MA Y W, KUO H Y, et al. Software-Defined Network Virtualization Platform for Enterprise Network Resource Management[J]. IEEE Transactions on Emerging Topics in Computing, 2016,4(2): 179-186.

[6] HE H, HU J, SILVA D D. Enhancing Datacenter Resource Management through Temporal Logic Constraints[C]//2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). Orlando, FL, USA: IEEE Press, 2017:133-142.

[7] ZHU K, HOSSAIN E. Virtualization of 5G Cellular Networks as a Hierarchical Combinatorial Auction[J]. IEEE Transactions on Mobile Computing, 2016, 15(10): 2640-2654.

[8] WEI G U, XUE S, WANG Y, et al. Finite-time Consensus Based Distributed Cooperative Control for DC Microgrids[J]. Automation of Electric Power Systems, 2016.

[9] LOLOS K, KONSTANTINOU I, KANTERE V, et al. Adaptive State Space Partitioning of Markov Decision Processes for Elastic Resource Management[C]//2017 IEEE 33rd International Conference on Data Engineering (ICDE). San Diego, CA: IEEE Press, 2017:191-194.

[10] PATEROMICHELAKIS E, PENG C.Selection and Dimensioning of Slice-Based RAN Controller for Adaptive Radio Resource Management[C]//2017 IEEE Wireless Communications and Networking Conference (WCNC). San Francisco, CA: IEEE Press, 2017:1-6.

[11] TALARICO S, MAKHIJANI K, PILLAY-ESNAULT P. Efficient service auto-discovery for next generation network slicing architecture[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). Palo Alto, CA: IEEE Press, 2016:26-32.

[12] NGUYEN V G, BRUNSTROM A, GRINNEMO K J, et al. SDN/NFV-based Mobile Packet Core Network Architectures: A Survey[J]. IEEE Communications Surveys & Tutorials , 2017(99): 1-1

[13] FAN P, ZHAO J, CHIH-LIN I. 5G high mobility wireless communications: Challenges and solutions[J]. China Communications, 2017, 13(Supplement2):1-13.

[14] KAMEL M I, LONG B L, GIRARD A. LTE Wireless Network Virtualization: Dynamic Slicing via Flexible Scheduling[C]// Vehicular Technology Conference.[S.l]: IEEE Press, 2014:1-5.