一種低復(fù)雜度的無線虛擬網(wǎng)絡(luò)資源分配策略

曾菊玲，張春雷，盛明哲，夏 凌，解 冰

(1.三峽大學(xué)，湖北 宜昌 443002；2.中國聯(lián)通研究院，北京 100032；3.天翼電信終端有限公司，北京 100032)

0 引言

為了提供面向應(yīng)用、開放靈活、可編程和易維護的服務(wù)，未來5G將采用虛擬網(wǎng)絡(luò)架構(gòu)[1-3]。虛擬化技術(shù)在提供高效及靈活組網(wǎng)的同時，也增大了技術(shù)實現(xiàn)復(fù)雜度，特別是資源分配更加復(fù)雜。由于虛擬化技術(shù)導(dǎo)致虛擬資源層或移動虛擬網(wǎng)絡(luò)操作層(Mobile Virtual Network Operators，MVNOs)的出現(xiàn)，使得原本在基礎(chǔ)設(shè)施提供層(Infrastructure Providers，InPs)和用戶(Users,UEs)之間進行的資源分配，變?yōu)镸VNOs向InPs購買或租用無線資源，再向UEs提供服務(wù)。資源提供途徑和各方收益都變得更加復(fù)雜，特別考慮到無線信道的實時多變特性，采用自適應(yīng)資源分配策略時，雖然獲得更大收益，但中間層MVNOs的存在，也將自適應(yīng)策略變得更加復(fù)雜。

對于無線虛擬網(wǎng)絡(luò)資源分配，目前已有很多相關(guān)研究。文獻[4-5]提出了InPs與用戶之間直接分配資源的方法，由于MVNOs未參與其中，不能實現(xiàn)真正虛擬化。文獻[6]提出了InPs-MVNOs-UEs三級架構(gòu)，但沒有給出具體算法。文獻[7-8]采用InPs-MVNOs-UEs三級架構(gòu)，提出了基于三層架構(gòu)的二級聯(lián)合分層拍賣機制資源，整體效用最優(yōu)，但個體效用非最優(yōu)，中心控制方式導(dǎo)致計算復(fù)雜度較大。文獻[9-10]采用Stackelberg博弈和McAfee拍賣兩階段聯(lián)合機制對虛擬網(wǎng)絡(luò)功率進行了分配，但不能進行切片選擇。文獻[11]采用分層博弈研究了超密集蜂窩網(wǎng)絡(luò)資源分配問題，但只能保證效用最大，沒有討論頻譜效率優(yōu)化問題。文獻[12]提出了InPs-MVNOs以及MVNOs-UEs分層匹配博弈，然后循環(huán)迭代直至收斂的分層匹配博弈機制，有效解決了三級架構(gòu)下業(yè)務(wù)選擇和資源購買兩階段聯(lián)合優(yōu)化問題(簡稱聯(lián)合分層博弈)，但上、下層間循環(huán)迭代導(dǎo)致計算量過大，且沒有考慮到對時變無線信道的跟蹤，導(dǎo)致資源利用率較低，同時，兩層多對一匹配不能實現(xiàn)用戶與切片精確匹配，片內(nèi)資源優(yōu)化無法實現(xiàn)。事實上，在虛擬網(wǎng)絡(luò)中，MVNOs作為獨立運營商，向UEs提供業(yè)務(wù)與向InPs購買資源是獨立的，上、下兩層博弈可以獨自進行，不需要循環(huán)迭代，通過兩層獨立的多對一匹配博弈，實現(xiàn)用戶組與切片組的匹配，較大地降低復(fù)雜度。但用戶組與切片組匹配不能實現(xiàn)用戶與切片的一對一精確匹配，且分層匹配博弈只能實現(xiàn)無線虛擬網(wǎng)絡(luò)中資源分配的效用最大化，不能保證頻譜效率最優(yōu)。因此，需要在分層匹配博弈之后再次進行無線資源分配，以保證精確匹配和頻譜效率最大化，目前還未見研究二者結(jié)合的文獻。自適應(yīng)無線信道的資源分配策略在OFDMA網(wǎng)絡(luò)中研究較多，通過為用戶分配較好子信道和適應(yīng)于信道的功率，提高系統(tǒng)無線資源利用率，文獻[13-15]提出了一種低復(fù)雜度的比例公平的資源分配策略，具有較好效果。InPs為MVNOs分配切片及功率的過程，恰好類似于OFDMA為用戶分配子載波及其功率的過程，因此，可借用之。

本文提出一種低復(fù)雜度的分層匹配博弈結(jié)合比例公平的無線虛擬網(wǎng)絡(luò)資源分配策略。首先，采用2層獨立的分層匹配博弈避免雙層循環(huán)導(dǎo)致的較高計算復(fù)雜度，博弈下層為UEs與MVNOs構(gòu)成的多對一匹配，實現(xiàn)UEs對MVNOs依效用選擇，上層為MVNOs與InPs構(gòu)成的多對一匹配，實現(xiàn)MVNOs對切片依效用選擇，通過二層博弈，最終實現(xiàn)用戶組與切片組效用最高匹配。然后，在匹配InPs與MVNOs間采用比例公平的資源分配策略，實現(xiàn)用戶與切片的精確匹配，并在比例公平的條件下，實現(xiàn)頻譜效率最大。

1 系統(tǒng)模型

圖1是三級架構(gòu)的無線虛擬網(wǎng)絡(luò)。最高層是InPs，每個InP包含一個基站，基站的每一個信道抽象成一個切片，一個InP包含NS個切片。假定每個切片帶寬相同，功率可調(diào)，假定一個切片只能同時服務(wù)一個MVNO，對不同的MVNOs收取不同報酬。中間層是MVNOs，MVNOs通過獨立合約，根據(jù)網(wǎng)絡(luò)狀況和資源價格等因素，動態(tài)地向InPs購買無線資源，且一個MVNO可以購買多個切片，MVNOs根據(jù)服務(wù)等級等因素以不同的價格向終端用戶提供服務(wù)。最底層是UEs，以不同價格向MVNOs提出帶寬請求，一個用戶可向多個MVNOs提出服務(wù)申請。

資源分配的過程為： UEs向MVNOs提出帶寬申請，再由向InPs申請網(wǎng)絡(luò)切片。

2 分層匹配博弈

2.1 多對一匹配博弈

多對一匹配是指匹配雙方中的一方B能接納另一方的A中多個成員，而A的成員只能在B中選擇一個成員。

定義1：一個匹配μ是從集合A∪B到A∪B所有子集構(gòu)成的集合的一個映射，對所有a∈A和所有b∈B，有

μ(a)∈B∪?,μ(b)?A,

(1)

B=μ(a)?a∈μ(b)。

(2)

一個匹配是穩(wěn)定的，每一個參與者的匹配對象都是可接受的，且不存在一對未發(fā)生匹配的參與者，他們互相偏好與對方發(fā)生匹配。

定義2：如果匹配μ滿足對所有的個體a∈A∪B，μ(a)R(a)φ，對所有的b∈B，Cb(μ(b))=μ(b),稱μ是一個穩(wěn)定匹配。其中，μ(a)R(a)φ表示A中的元素a在B中的映射不是空集，Cb(a)表示元素a在B中的選擇集。

穩(wěn)定匹配存在的條件：A或B中所有個體都存在嚴格偏好。

對于穩(wěn)定匹配，可采用拒絕——接收算法求解。

2.2 用戶UEs與MVNO間多對一匹配博弈

在下層博弈， UEs向MVNOs購買帶寬，得到服務(wù)，達成自身滿意度，1個UE只能向1個MVNO購買帶寬，1個MVNO可向多個UEs提供帶寬服務(wù)。UEs以不同價格向MVNOs購買帶寬，同理，MVNO向不同UE提供帶寬時，具有不同收益。UEs與MVNOs雙方應(yīng)根據(jù)效用最大原則選擇對方，因此，構(gòu)成UEs為租用者、MVNOs為供給者的多對一匹配。

假定第m個MVNO(m∈M)向一組UEs提供服務(wù)，Κ=UmΚm為總的UEs數(shù)目，Km表示第m個MVNO服務(wù)的用戶數(shù)，用符號|Κ|表示集合K的基數(shù)，為了簡單，用K表示用戶總數(shù)，Um表示Km的并集。

對于無線網(wǎng)絡(luò)的UEs，主要考慮數(shù)據(jù)流量，是盡力而為業(yè)務(wù)，帶寬越大，傳輸?shù)臄?shù)據(jù)流量越大，用戶滿意度越高，滿意度函數(shù)為：

(3)

式中，Bk,m為MVNOs提供給UEs的帶寬，s1為正常數(shù)，Bmax為達到最大效用的帶寬，受相關(guān)信道容量及通過率限制。

第k個UE從MVNOm購買帶寬獲得的效用為：

Ek,m=Udata(Bk,m)dk-λk,mBk,mdk，

(4)

式中，dk為UEk對切片的需求數(shù)；λk,m為第k個UE向MVNOm購買帶寬的價格且各不相同，Bk,m為第k個UE向第m個MVNO購買的帶寬；因此， UEs的優(yōu)化目標為：

(5)

式中，uk,m=1表示第k個UE購買MVNOm的帶寬。

對于第m個MVNO，向第k個UE提供帶寬獲得的報酬，

(6)

式中，μm,k為第m個MVNO向第k個UE提供帶寬的價格且各不相同。特別說明的是，在式(6)中，計算MVNO的報酬時，本應(yīng)減掉MVNO為向第k個UE提供帶寬而向INP購買物理資源需要付出的成本，但考慮到那樣做會將上、下兩層博弈耦合，相互影響，系統(tǒng)達到博弈穩(wěn)定的計算復(fù)雜度太高。而事實上，MVNOs作為虛擬中間商，向用戶提供帶寬與向INP購買物理資源可作為兩個獨立的過程，因此，忽略了購買物理資源的成本。

因此，第m個MVNO的優(yōu)化函數(shù)為：

(7)

為了聯(lián)合求解式(5)和式(7)，得出第k個UE與MVNO的最佳匹配uk,m，UEs與MVNO間構(gòu)成多對一匹配，其中UEs的偏好函數(shù)為式(4)，MVNO的偏好函數(shù)為式(6)，步驟如下。

步驟1:任意UEk向可接受的最偏好的MVNOm遞交服務(wù)申請；每一個MVNO根據(jù)已定指標數(shù)在收到所有申請中留下本集中的申請(每個MVNO可選擇多個用戶)，拒絕其他用戶。

步驟k:每一個未匹配的UEk′向還未拒絕過它的、最偏好的MVNOm′遞交服務(wù)申請；每一個MVNOm′根據(jù)已定指標，在收到的剩下所有用戶申請中留下它選擇集中的申請，拒絕所有其他申請。

當沒有拒絕發(fā)生時，算法結(jié)束。每一個MVNO服務(wù)它在算法最后一步中接受的所有用戶，算法產(chǎn)生一個匹配。

2.3 InPs與MVNOs間多對一匹配博弈

在上層博弈，InPs向MVNOs提供物理資源。假定物理資源的單位是切片，每切片的帶寬已定并相等，因此，InPs向MVNOs提供切片并分配功率，但二者同時進行會導(dǎo)致計算復(fù)雜度太高。因此，首先假定各切片功率相等(平分總功率)，假定1個切片只能提供給1個MVNO，而1個MVNO則可租用多個切片，InPs向MVNOs提供切片時，對不同的MVNO有不同收益。同理，MVNO租用不同切片時，具有不同價格。為了使各自效用最大，用戶與MVNOs雙方應(yīng)根據(jù)偏好進行選擇，因此，構(gòu)成MVNOs為租用者、InPs為供給者且為多方的多對一匹配。

InPs與MVNOs多對一匹配博弈中， MVNO選擇切片組，結(jié)合下層博弈，實現(xiàn)用戶組選擇切片組。確定MVNOs與InPs的連接關(guān)系后，采用功率受限的比例公平原則進行功率分配，以提高公平性和資源利用率，并適應(yīng)信道變化。

對于MVNO，向InPs購買物理資源，向InP支付代價，其成本函數(shù)為：

(8)

式中，χm,n為MVNOm租用切片n時，向InPs購買功率的價格，購買的功率為pm,n，sm為MVNOm購買的切片總數(shù)。

因此，此時MVNOm的優(yōu)化函數(shù)為：

(9)

式中，πm,n=1表示MVNOm購買切片n,mq表示MVNOm購買切片的指標。

對于InP，其向MVNO出售功率獲得的收益為：

EInP,m,n=βm,npm,nsm，

(10)

式中，βm,n為InP提供切片功率的價格。

因此，InP的優(yōu)化函數(shù)為：

(11)

為了聯(lián)合求解式(9)和式(11)，得出InP與MVNO的最佳匹配πm,n， InP與MVNO構(gòu)成多對一匹配，偏好函數(shù)分別為式(8)和式(10)，當購買或出售功率的為價格隨機時，式(8)和式(10)所示偏好是嚴格單調(diào)的，因此，匹配穩(wěn)定解一定存在，即能得到效用最優(yōu)的切片選擇策略，穩(wěn)定匹配可采用與2.2節(jié)末尾的一樣的UEs與MVNO間多對一匹配拒絕接收算法。

3 比例公平的低復(fù)雜度功率分配策略

3.1 優(yōu)化模型

當UEs-MVNOs，MVNOs-InPs兩層多對一匹配完成后，形成用戶組與切片組匹配。例如圖1中，用戶組(UE1,UE2)通過MVNO1與切片組(s1,s2)形成匹配組，無法得到UEs與切片間的一對一匹配關(guān)系，進而不能直接根據(jù)信道特點為切片分配功率。因此，匹配保證了特定價格下UEs，MVNOs，InPs三者收益最大，但不能保證頻譜效率最高，需要進一步采用資源分配策略，實現(xiàn)UEs與InPs的精確匹配并使頻譜效率最優(yōu)。這一問題可以通過對系統(tǒng)頻譜效率建模，并考慮到系統(tǒng)負載平衡，使優(yōu)化問題首先速率比例公平來解決。

假定Km為與MVNOm匹配的一組用戶，Sm為與MVNOm匹配的一組切片，即Km與Sm匹配，Hk,n為第k個UE與切片n之間的信道，pk,n為切片n分配給第k個UE時的功率，假定切片帶寬相等，則對Km與Sm資源分配，建立如下優(yōu)化模型：

(12)

(13)

γk,n=pk,nHk,n。

(14)

式(12)是一個非線性整數(shù)聯(lián)合優(yōu)化問題，具有NP-hard的復(fù)雜度，不適合在線求解。

3.2 低復(fù)雜度策略

為了求解優(yōu)化式(12)，采用次優(yōu)算法。貪婪定理是復(fù)雜度較低的搜索算法，首先由用戶根據(jù)貪婪定理選擇匹配組內(nèi)的切片，然后根據(jù)KKT條件，求每切片的功率。

3.2.1 切片選擇算法

為了簡化式(12)的求解，將其解耦成兩步：用戶選擇切片和切片功率分配。對于切片選擇，式(12)是一個非凸問題，通過對ck,n整數(shù)放松，可變?yōu)橥箖?yōu)化問題，但計算復(fù)雜度太高，考慮到功率分布平坦時，多用戶信道容量具有與單用戶相同的注水效應(yīng)，即在等功率條件下，用戶選擇信道質(zhì)量較好的切片。因此，切片選擇可采用貪婪定理：假定每切片功率相等，在迭代過程中每次讓用戶選擇信道質(zhì)量最好的切片，就能保證頻譜效率最高，為了保證公平性，每次從速率比例最小的用戶開始選擇。貪婪定理不僅采用啟發(fā)式方法解決了非凸整數(shù)NP-HARD最優(yōu)化問題，而且搜索效率較高。

假定對于MVNOm，匹配的用戶組為Km=∪kk，匹配的切片組為Sm=∪nn，假定每切片功率相等，令nk表示第k個用戶選擇的切片數(shù)，具體步驟如下：

①?k∈(1,2,…Km),n∈(1,2,…Sm),令

ck,n=0,Rk=0,nk=0,p=Pm,TOT/N,

Km={1,2,…Km},Sm={1,2,…Sm}。

② fork=1 toKm

Sm=Sm/n*,ck,n*=1,nk=nk+1，

Rk=Rk+log2(1+pk,n*Hk,n*)。

Sm=Sm/n*,ck*,n*=1,nk*=nk*+1，

Rk*=Rk*+log2(1+pk*,n*Hk*,n*)，

Ifnk*>dk*，Km/k*→Km。

3.2.2 切片功率分配策略

當用戶選定切片之后，對于MVNOm連接的用戶組和切片組，優(yōu)化式(12)變?yōu)椋?/p>

(15)

(16)

式中，nk表示第k個UE分到的切片數(shù)，Pm,tot表示MVNOm購買的總功率。

3.2.2.1 單個用戶的切片間分配功率

對于式(15)，應(yīng)用拉格朗日乘數(shù)法則，對單個用戶可得：

(17)

由此可得：

(18)

(19)

式中，pk表示MVNOm所連第k個UE的功率。

3.2.2.2 用戶間分配功率

對所有用戶，由式(15)可得：

(20)

對式(16)，有Km個變量，Km個非線性等式，求解計算量較大，為了簡化，假定用戶所需速率之比等于分到的切片數(shù)量之比。即：

Rk1:Rk2…Rkm=nk1:nk2…nkm=φ1:φ2…φkm，

則pk=(bk-P1)/ak,k,k=2,...,K，

(21)

(22)

4 策略實現(xiàn)框圖及復(fù)雜度分析

綜合以上分析，本文策略的實現(xiàn)步驟如圖2所示，可描述為：

① UEs與MVNOs間多對一匹配，實現(xiàn)UEs對MVNOs的選擇；

② InPs與MVNOs間多對一匹配，實現(xiàn)切片對MVNOs的選擇；

③ 通過步驟①～②，實現(xiàn)用戶組與切片組的匹配；

④ 在每一組(用戶組—切片組)內(nèi)實現(xiàn)切片選擇和功率分配。

圖2 策略實現(xiàn)框圖Fig.2 Strategy diagram

可以看到，本文提出的匹配博弈結(jié)合比例公平的無線虛擬網(wǎng)絡(luò)資源分配策略，低復(fù)雜度表現(xiàn)在以下幾方面：

① 分層匹配博弈是兩層獨立的博弈，克服了文獻[12]上、下兩層循環(huán)迭代導(dǎo)致的大計算量。由于下層博弈中，對用戶每次需要計算其對每個MVNO的偏好函數(shù)并排序，因此計算復(fù)雜度為O(kmlog2m)，其中，k，m分別為UEs和MVNOs的數(shù)量，而每個MVNO都要對選擇它的用戶排序，計算復(fù)雜度為O(mqlog2mq)，其中，mq為MVNOm的指標數(shù)，一般來說，k>>m,m>>mq，因此，下層博弈的計算復(fù)雜度為O(kmlog2m)。同理，上層博弈的計算復(fù)雜度為O(Nmlog2m),其中，N為切片數(shù)量，可見，上、下層多對一匹配博弈分別小于一對一匹配博弈的復(fù)雜度O(kNlog2N)。

② 對于比例公平資源分配策略，基于貪婪定理的切片選擇計算復(fù)雜度為O(kmqNmqlog2Nmq)，其中，kmq,Nmq分別是MVNOm連接的用戶數(shù)和切片數(shù)，相比在全網(wǎng)進行切片選擇的計算復(fù)雜度O(kNlog2N)要小很多。

③ 對于比例公平資源分配策略，功率分配策略將一個不可解的非凸優(yōu)化問題用一步算法即可實現(xiàn)，而且計算復(fù)雜度僅為O(kmq)。①～③說明本文策略在圖2所示各個環(huán)節(jié)的計算復(fù)雜度低于聯(lián)合分層博弈。

④ 信道反饋信息簡化，文獻[12]在用戶與MVNO的博弈中，構(gòu)造了MVNOm-InPn對mn，并在偏好函數(shù)中引入了信道信息，即每個用戶需要知道所有切片的信道信息。而本文所提策略中，用戶只需知道匹配組中的切片信道信息，反饋量大大降低。

總而言之，本文所提策略的主要優(yōu)勢在于避免了循環(huán)迭代，降低了計算復(fù)雜度，采用比例公平的資源分配策略提高了頻譜效率。本文仿真只對這兩方面性能進行說明。

5 仿真及性能分析

假定10個UEs均勻分布于區(qū)域中，3個MVNOs向1個InP租用資源向UEs提供業(yè)務(wù)，各MVNOs能容納的用戶指標分別為3,3,4，InP的信道抽象成10個切片。切片到用戶的信道包含大尺度衰落和小尺度衰落，大尺度衰落由d-2決定，10個UEs的損耗根據(jù)與基站的距離決定，假定其中4個的損耗為1,4個的損耗為0.1,另外2個的損耗為0.05。所有信道的小尺度衰落服從均值相等的Rayleigh衰落，每切片的等功率為1 W，功率分配時，總功率保持與平均功率時相等，不考慮信道的誤比特率，信噪比為-20 dB,速率為單位帶寬的速率，用戶滿意度中的參數(shù)s取4.5。為簡化，假定每用戶所需切片數(shù)dk為1，用戶購買帶寬的價格、MVNOs向用戶出售帶寬的價格、MVNOs向InPs購買功率的價格以及InPs向MVNOs出售功率的價格分別均勻分布于[4 8]，[2 4]，[3 7]，[4 6]。圖3比較了本文提出的低復(fù)雜度的兩層獨立匹配博弈結(jié)合比例公平資源分配策略與兩層聯(lián)合匹配博弈的系統(tǒng)和速率，可以看到，本文提出的策略遠遠高于文獻[12]中的兩層聯(lián)合匹配博弈。

圖3 頻譜效率比較Fig.3 Comparison of the two spectrum efficiency

圖4(其中，策略1為本文策略，策略2為兩層聯(lián)合匹配博弈)比較了本文策略與兩層聯(lián)合匹配博弈在價格相同、信道改變時的效益?？梢钥吹?，由于兩層聯(lián)合匹配博弈在上、下層博弈中可以耦合，即MVNOs在向UEs提供帶寬時，同時考慮向InPs購買功率的成本，因此各部分效用稍高于本文策略。但從計算復(fù)雜度來說，上、下兩層聯(lián)合的匹配博弈，要達到循環(huán)穩(wěn)定，百次左右迭代在所做仿真中占比大概2/10，多數(shù)需要更多次循環(huán)。本文策略不需循環(huán)，只在匹配博弈之后增加少量計算，通過切片選擇和功率分配，實現(xiàn)用戶與切片間的精確匹配并提高頻譜效率，計算量和跟蹤時延大大降低，結(jié)合圖3的效率提高，說明本文策略性能優(yōu)于兩層聯(lián)合匹配博弈。

圖4 效用比較Fig.4 Comparison of the two strategy’s utility

6 結(jié)束語

本文提出了一種低復(fù)雜度的分層匹配博弈結(jié)合比例公平的無線虛擬網(wǎng)絡(luò)資源分配策略。通過兩層獨立的多對一匹配博弈實現(xiàn)用戶組與切片組的匹配，在匹配的切片組與MVNOs間采用功率受限的比例公平資源分配策略，實現(xiàn)用戶與切片的精確匹配，并在保證比例公平的條件下，使系統(tǒng)效率達到最大。仿真表明，相比兩層聯(lián)合匹配博弈，本文雖然效用稍低，但較大地降低了計算復(fù)雜度和跟蹤時延，提高了頻譜效率，總體性能更優(yōu)。