施穎潔，陳前斌，楊希希，唐 倫

(重慶郵電大學 移動通信技術重點實驗室，重慶 400065)

0 引 言

5G時代，將有各種多樣的業(yè)務及應用場景，有著不同的網絡需求[1-2]。NGMN(next generation mobile networks)對于5G的愿景是5G可以創(chuàng)造一個全方位移動連接社會的系統(tǒng)[3-4]。為了解決多樣化業(yè)務在網絡速率、時延、可靠性方面的問題，根據業(yè)務對網絡的功能、安全性等需求為每一種類型的業(yè)務都建立一個單獨的網絡，網絡成本將會超出預算。因此，5G提出了構建相互獨立且具有靈活性的網絡切片[5]，為不同應用場景下的用戶需求提供有力保障。

網絡切片是滿足物理基礎設施上針對不同業(yè)務需求的虛擬網絡。網絡切片理論上可使多個切片共享相同的物理資源，該技術可以動態(tài)地調整虛擬網絡的功能、大小等，有效提高資源利用率，較之傳統(tǒng)架構可減少更多的實施成本[6]。目前虛擬網絡切片的資源分配通常由基礎設施提供商(infrastructure provider, InP)根據移動虛擬網絡運營商(mobile virtual network operator, MVNO)中用戶的需求決定最終資源分配方案。文獻[7-8]以時延為約束條件，最大化網絡吞吐量為目標構建優(yōu)化模型進行資源分配。文獻[9]通過建立馬爾科夫決策模型，利用樹搜索算法使網絡成本最小化。但是，這些研究沒有考慮到切片業(yè)務之間需求的區(qū)別，并且，沒有考慮到切片空閑資源的回收，不能及時靈活調整切片的資源，造成資源浪費、資源利用率低。因此，在5G網絡切片資源分配中考慮切片中資源的靈活性十分重要。

文獻[10-11]將不同的切片分配給不同的虛擬運營商，獲取最大收益。文獻[12]以用戶速率為約束條件，為不同的切片用戶分配資源。以上研究中，網絡切片可以相互調用資源，或是直接為用戶“打標簽”分配資源，不能較好地體現切片隔離性。網絡切片理論上可使多個切片共享相同物理資源，網絡切片中若一個切片發(fā)生擁塞現象，不能對其他切片造成影響[13]，所以，切片之間的隔離十分重要。

基于以上研究，本文抽象化無線資源，提出一種基于拍賣的虛擬資源動態(tài)分配算法。該算法首先根據切片阻塞率量化切片優(yōu)先級，根據切片資源剩余量計算需求資源報價。其次，考慮資源需求量與資源總量之間的關系，確定資源拍賣價格。其中，資源總量包括系統(tǒng)剩余資源和回收資源。最后，提出一種新型的拍賣模型，綜合考慮系統(tǒng)的總收益和用戶需求進行資源分配，在滿足用戶服務質量(quality of service，QoS)需求的同時使收益最大化。

1 虛擬網絡切片系統(tǒng)架構

1.1 虛擬網絡切片系統(tǒng)

在5G網絡中，由于大量不同的應用場景同時接入，網絡切片的設計必須靈活且完全獨立[17]。網絡切片的靈活性可以動態(tài)滿足各自業(yè)務及用戶的需求，同時網絡切片具有絕對獨立性，各個切片間不能相互影響。

針對不同切片的業(yè)務需求，本文提出一種基于拍賣的虛擬資源動態(tài)分配算法，保證不同業(yè)務用戶的QoS需求。首先，切片根據用戶狀態(tài)觸發(fā)開關提出需求申請；其次，以價格為信譽因子，根據切片的優(yōu)先級，回收并分配資源；然后，將切片分配資源時的空隙資源整合作為預留資源，減小分配資源帶來的時延；最后，利用虛擬拍賣策略在滿足用戶QoS的同時使得收益最大化。

1.2 資源虛擬化方案

資源的虛擬化[2]，即將物理資源抽象化，并根據抽象資源的分配結果分配物理資源。本文抽象化資源的過程分為4個步驟：初始化、資源拍賣、提交方案以及資源映射。MVNO根據切片的業(yè)務需求，制定各類業(yè)務的切片，并為其分配一定資源以滿足基本需求；用戶根據業(yè)務類型分別接入各個切片，切片根據用戶狀態(tài)向MVNO進行反饋，并制定投標信息，MVNO根據決策為用戶分配資源并及時對空隙資源進行整合，通過拍賣策略得到最終分配結果；InP根據請求與MVNO建立購買、租借策略，并分配物理資源；最后MVNO根據計劃向InP租借物理資源。

在動態(tài)分配資源的過程中，根據切片狀態(tài)提交異常信息，由業(yè)務需求以及用戶狀態(tài)聯合制定切片優(yōu)先級，在分配資源過程中優(yōu)先級有著很重要的作用。分配資源時由于各切片資源需求差異會留有資源空隙，此時MVNO需要將這些資源空隙整合作為預留資源，在資源臨界點作為緩沖資源進行分配。

1.3 虛擬資源拍賣機制

本節(jié)對基于內部拍賣的虛擬資源分配算法的系統(tǒng)架構及其工作機制進行詳細介紹。該算法是在MVNO中根據切片提供的需求與回收信息，以及MVNO整合的空隙資源信息，形成一個如圖1所示的拍賣模型。

該拍賣策略的核心思想是根據用戶狀態(tài)決定切片狀態(tài)，計算切片優(yōu)先級，以價格代替信譽因子，以此計算網絡切片資源需求拍賣報價以及資源回收報價，從而將資源優(yōu)化分配問題轉換成為一個內部拍賣問題。MVNO處理資源分為2個部分，分別是資源分配(Allocate)和資源回收(Recyeling)(見圖1中的虛線連接部分)，只有切片根據自身的狀態(tài)觸發(fā)異常開關時，需要向MVNO提交申請，否則切片只需對自身狀態(tài)進行監(jiān)測，切片不能自由調用資源，回收的資源和空隙資源均由MVNO統(tǒng)一處理。

圖1 虛擬資源分配拍賣模型Fig.1 Virtual resource allocation auction model

整個拍賣過程中的計算分配量和實際分配資源都在MVNO中進行，切片沒有實際的計算功能，只需要監(jiān)測和記錄，MVNO統(tǒng)一管理資源，避免切片直接接觸造成干擾，在回收資源后和整合的空隙資源再次整合并分配資源；其次切片只具有監(jiān)測和記錄的能力，當切片異常時提交該時刻的切片狀態(tài)，最后為各個切片確定需求量、供給量和報價信息，并綜合考慮切片優(yōu)先級為其分配資源。

2 系統(tǒng)模型

2.1 用戶模型

每個切片接入對應類型的用戶，因此，各個切片的用戶狀態(tài)是不同的。本文綜合考慮切片業(yè)務的特殊性和用戶狀態(tài)計算切片的阻塞率，并分析切片當前的用戶狀態(tài)，判斷切片是否需要資源或有空閑資源。最后，當切片屬于異常狀態(tài)時需要向MVNO提交當前切片信息。

假設，切片中的用戶到達率服從參數為λa的泊松分布，業(yè)務持續(xù)時間Tk服從參數為μa的指數分布，在業(yè)務執(zhí)行過程中，當業(yè)務中斷，用戶回到當前業(yè)務的概率為Pb，用戶恢復當前業(yè)務的到達率服從參數為λa的泊松分布，且用戶離開的時間服從參數為μb的指數分布。

切片中資源以其自身的定義，假設切片已有資源的數量為Nl={1,2,…,N}，Nnew為新用戶接入時所用的資源，Nl與Nnew的差值為切片的預留資源。在切片中，最大服務率為NRlμb。其中，NRl為服務切片l的資源數。那么切片強度為

(1)

(1)式中，λl是切片l的業(yè)務總到達率，其由新業(yè)務和中斷業(yè)務用戶到達率構成，可以寫成

(2)

(2)式中：等式右邊第1項是切片l的業(yè)務達到率；第2項是切片l中業(yè)務中斷后恢復的達到率；第3項是當用戶在執(zhí)行切片l中的業(yè)務，被其他業(yè)務打斷的概率。則新業(yè)務的業(yè)務阻塞率和恢復業(yè)務的阻塞率分別為

(3)

(4)

2.2 切片模型

切片用戶的QoS需求主要體現在速率和時延2個方面。每個切片具有其特殊大小的子信道帶寬，可以直接為切片用戶服務。當資源不足時，分配的子信道帶寬若不能滿足需求，則另外為切片增加CPU(central processing unit)，減少時延。

切片狀態(tài)為Xl={Ul,Ml,xl}，Ul,Ml分別代表用戶狀態(tài)和剩余資源狀態(tài)，用戶狀態(tài)包括切片強度Γ和業(yè)務阻塞率P；xl是一個二進制數，其值為0代表正常狀態(tài)，為1代表異常狀態(tài)。

切片中資源為Rl時，已有資源的數量定為NRl={1,2,…,N}。每個切片根據自己的資源數和需求量定制虛擬資源的參數，使其可以直接分給用戶使用。{Cblock,Pclock}代表切片的子信道數和CPU，切片的剩余資源狀態(tài)為R={Crem,Prem}，MVNO中的總資源可表示為{C,P}，其中，MVNO中的子信道數和CPU分別為

(5)

(6)

(7)

(8)

2.3 優(yōu)先級及時延權重因子

根據當前切片的阻塞率和該切片業(yè)務需求的最大阻塞率計算切片的優(yōu)先級，且最大阻塞率根據當前切片剩余資源狀態(tài)實時更新。切片優(yōu)先級越高則表示當前切片時延與業(yè)務需求差距越大，需要優(yōu)先分配資源。若未完成的已決定的分配沒有結束時，新的優(yōu)先級已經形成，則允許優(yōu)先級較高的切片進入分配隊列。異常信息的緊急程度U與用戶狀態(tài)有關。

(9)

(9)式中，當xl=1時，0

優(yōu)先級僅考慮了切片當前用戶狀態(tài)，而不同場景下，時延要求的差異尤為突出，針對不同的時延需求，引入一個時延權重因子

(10)

(10)式中：ρl是切片l容忍的最大時延門限；τl是切片允許的最大丟包率。

3 資源分配算法

3.1 確定報價

由于各個切片所定義的虛擬資源數不同，資源的收益也不同，MVNO需要綜合剩余資源量與資源需求量，資源供給量統(tǒng)一單位資源的參數和定價，處于異常狀態(tài)的切片將其狀態(tài)提交，MVNO為各切片確定資源需求量與供給量。

當xl=1時,切片異常，MVNO需要根據具體的切片狀態(tài)判斷切片的異常分類并計算需求信息、回收信息以及相應的報價。需求信息Ql是針對各切片的不同需求以及當前的用戶狀態(tài)，由恢復業(yè)務的用戶需求以及新用戶需求2部分構成?；謴蜆I(yè)務用戶需求需要考慮其需求資源沒有用到的可能性。根據MVNO計算需求信息Ql，制定其估價bl(Ql)為

(11)

切片的靈活性即切片中的資源會根據當前的用戶狀態(tài)實時改變的能力，當xl=1且MVNO判斷需要回收切片空閑資源時，MVNO根據切片狀態(tài)計算空閑資源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

因為業(yè)務場景不同，需要優(yōu)先滿足優(yōu)先級高且時延要求較高的切片，此時的資源分配分為2個階段，第1階段采用貪婪算法分配子信道，此時假設CPU與子信道按比例分配，當子信道分配完畢后再進行第2階段的CPU分配和調整?；谝陨嫌懻?，首先進行優(yōu)化問題Q1的第1階段的資源分配，如Q2所示。

(14)

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

(d)δRmin′≤Rl

現在問題已簡化為CPU與子信道按比例分配的問題。cl為一個二進制數，表示切片是否中標；(b)式用于保證切片不會重復中標；(c)式表示分配的資源不超過總資源量；(d)式表示切片的資源需要滿足用戶及業(yè)務的需求，Rmin′是切片可接受的最小速率。

分配資源后檢查切片是否能滿足速率需求，如果不能滿足，則再調整分配資源，直至速率滿足或者優(yōu)先級和時延權重因子影響的數組排列后移。在我們提出的算法求解過程中，對每一個有需求的切片，都會優(yōu)先執(zhí)行以下過程

算法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; //初始化各切片的優(yōu)先級和時延因子

5: end for

6: whilexl=1

7: if(fl=1)

10: else if(fl=0)

11:δ←δl;

12:ζ←ζl; //更新各切片的優(yōu)先級和時延因子

13: end if

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

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

//根據優(yōu)先級和時延權重找到最大值

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與子信道成比例分配，但由于業(yè)務需求不同，CPU需求差異較大，在第2階段，任務是在已分配資源的基礎上對CPU進行實際分配和調整，盡量提高系統(tǒng)頻道利用率及吞吐量。在第1階段結束后，可以得到一個分配矩陣，在此階段中首先需要判斷切片需求是否已經滿足，根據原始需求與第1階段分配結果得到新的需求。基于Q2的分配結果，原優(yōu)化模型Q1的第2階段優(yōu)化問題如Q3所示。

(15)

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

(d)δRmin≤Rl

(15)式中：pl為一個二進制數，表示切片是否中標；(b)式用于保證切片不會重復中標；(c)式為總資源量的限制；(d)式表示切片的資源需要滿足用戶及業(yè)務的需求，此限制條件與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; //更新需求資源報價和切片優(yōu)先級

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協(xié)議標準[14]，對上述虛擬資源分配算法進行數值仿真，表1為仿真參數設置。

表1 仿真參數設置

在實驗中，設置5個網絡切片，當切片狀態(tài)達到最低資源利用率門限，則該切片提供供給資源，當切片狀態(tài)達到阻塞率門限，則該切片需要分配資源，將最低資源利用率的最大值設置為0.5，而阻塞率決定是否為切片分配資源，所以，設置切片阻塞率為0.1時可以開始考慮為切片分配資源。由于切片業(yè)務應該具有較大的差異性，所以將切片的最低資源利用率門限值和阻塞率門限值分別設置為{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，即該切片對時延要求較高，當阻塞發(fā)生即可以分配資源。

圖2給出了本文資源分配算法與按比例分配算法、按優(yōu)先級分配算法的資源分配情況。比例公平算法按比例分配所有資源，使每個切片都能得到資源，保證了切片的公平性；按優(yōu)先級分配算法保證了高優(yōu)先級切片的所需資源，這樣可能出現高優(yōu)先級切片將資源用完，低優(yōu)先級切片則無資源可用；本文的算法同時考慮切片的需求和切片的優(yōu)先級，此時沒有空閑資源，但存在空隙資源，剩余的空隙資源作為預留資源，等待下一周期的空閑資源或空隙資源一并整合分配。

圖2 本文與比例公平算法、Priority分配算法分配結果的比較Fig.2 Compares with the results of the proportional fairness algorithm and the Priority distribution algorithm

為切片分配資源，首先考慮的是用戶QoS需求，所以用戶的滿意度是切片資源分配的重要指標，本文設置的用戶滿意度的主要因素為系統(tǒng)是否為切片分配了其所需要的資源，并達到其QoS需求。

圖3為本文資源分配算法與按比例分配算法、按優(yōu)先級分配算法在資源不夠的情況下各優(yōu)先級對所分配資源的滿意度的比較。隨優(yōu)先級的增加，按比例分配算法滿意度降低，此算法雖然盡可能地保證所有切片的需求，但對于優(yōu)先級高的用戶考慮不周；按優(yōu)先級分配算法可以保證優(yōu)先級高的切片，但優(yōu)先級低的切片滿意度卻很低，因為資源不夠的壓力完全轉移給了優(yōu)先級低的切片；本文算法的滿意度隨優(yōu)先級的增加而增加，盡可能地保證優(yōu)先級高的切片，而對優(yōu)先級低的切片也分配一定的資源。

圖3 優(yōu)先級增加，本文與比例公平算法、Priority分配算法滿意度比較Fig.3 Satisfaction compares with the proportional fairnessalgorithm, Priority distribution algorithm

圖4為當所有切片需求同時增加時各優(yōu)先級的切片所得到的資源情況，當資源足夠時，各個切片均可得到相應的資源，當達到總資源的臨界點時，調用整合的空隙資源繼續(xù)分配，所以，切片獲得的資源依然有一定程度的增加；當總資源不夠時，將依次調用優(yōu)先級低的切片資源，但依然要滿足低優(yōu)先級切片的最低需求，資源分配趨于穩(wěn)定前開始調用下一優(yōu)先級切片的資源，所以，資源量從最低優(yōu)先級開始依次趨于穩(wěn)定。

圖4 切片需求同時增加，各優(yōu)先級的切片所得到的資源情況Fig.4 Different slices own different priority obtained resource

圖5為當資源不夠且所有切片需求一致時各優(yōu)先級的切片所得到資源的過程。從圖5可看出，從優(yōu)先級較高的切片開始，切片依次獲得所需資源，但在滿足最高優(yōu)先級需求的同時也對其他優(yōu)先級的切片有資源分配，在分配趨于穩(wěn)定時，優(yōu)先級較低的切片還沒有得到全部所需資源，但此時資源已經不足，之后的切片獲得的資源緩慢增加正是在分配預留資源直至全部預留資源分配完畢。

圖5 切片需求一致時，各優(yōu)先級的切片所得到資源的過程Fig.5 Slices have same consistent, the process of different slices own different priority obtained resource

5 結束語

本文針對5G網絡中虛擬網絡切片靈活且完全獨立，動態(tài)滿足各自業(yè)務及用戶的需求，各個切片間不能相互影響的要求，提出一種雙向且動態(tài)、基于內部拍賣的網絡切片虛擬資源分配策略。首先，抽象化無線資源，對不同虛擬網絡切片的不同業(yè)務需求定制其特殊虛擬資源需求，從用戶層面提出需求，根據切片業(yè)務以及用戶狀態(tài)制定優(yōu)先級，將業(yè)務需求與用戶需求結合；切片根據用戶狀態(tài)觸發(fā)開關提出需求申請；以價格為激勵，根據切片的優(yōu)先級，綜合考慮系統(tǒng)的總收益和用戶需求回收并分配資源；將切片分配資源時的空隙資源整合作為預留資源，減小分配資源帶來的時延，最后，提出一種新型的內部拍賣模型，利用虛擬拍賣的方式決定資源分配情況。仿真結果表明，本文提出的資源分配算法可以在滿足用戶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.