異構(gòu)網(wǎng)絡(luò)資源分配：改進多對一轉(zhuǎn)移匹配

劉 崗，趙杭生，李大力，邵鴻翔，

1.解放軍理工大學(xué) 通信工程學(xué)院，南京 210007

2.南京電訊技術(shù)研究所，南京 210007

1 引言

隨著移動互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、智能終端的飛速發(fā)展，不斷增長的無線業(yè)務(wù)需求對帶寬和速率提出了極高要求。引入異構(gòu)網(wǎng)絡(luò)被視作一種提高資源利用率，增強用戶體驗的關(guān)鍵技術(shù)[1]。異構(gòu)網(wǎng)絡(luò)通過在傳統(tǒng)宏蜂窩部署低功率小蜂窩，有效地提高了覆蓋范圍和系統(tǒng)吞吐量[2]。但是，部署異構(gòu)網(wǎng)絡(luò)帶來便利的同時，也帶來了一些挑戰(zhàn)。因為微蜂窩和宏蜂窩復(fù)用相同資源，微蜂窩用戶會對宏蜂窩用戶造成跨層干擾，同時微蜂窩之間也會引起同層干擾，降低了系統(tǒng)性能，所以如何合理對頻譜資源進行分配顯得尤為重要[2-4]。

匹配理論是一種能夠有效解決無線資源分配問題的方法，可以減小組合優(yōu)化問題的復(fù)雜度，使問題更易求解[5]。目前，匹配理論被大量應(yīng)用在資源分配問題中[6-8]。在文獻[6]中作者將信道分配問題建模為穩(wěn)定匹配模型，然后利用Gale-Shapley匹配算法對模型進行求解[9]。文獻[7]利用匹配理論對LTE-U系統(tǒng)中非授權(quán)頻段進行分配。文獻[8]利用匹配理論對異構(gòu)網(wǎng)絡(luò)資源分配進行了分析。但是文獻[6-7]沒有考慮匹配個體間的相互影響—匹配外部性（Externality）。大量文獻對匹配的外部性進行了研究[10-11]，這時Gale-Shapley匹配算法不再適用。文獻[12-13]建立系統(tǒng)模型后，在考慮匹配外部性的基礎(chǔ)上，利用匹配理論進行分析，最后設(shè)計了轉(zhuǎn)移匹配算法對模型進行求解。

受文獻[11-13]啟發(fā)，本文提出了一種在保證宏蜂窩用戶服務(wù)質(zhì)量的情況下，各信道可動態(tài)地被多個FUE用戶同時復(fù)用的資源分配方案。利用雙邊匹配理論，將問題建模成多對一匹配問題。FUE用戶和信道根據(jù)各自設(shè)計好的效用函數(shù)分別建立偏好序，通過改進遞延算法（Gale-Shapley）形成穩(wěn)定的資源分配方案。在形成的穩(wěn)定資源分配方案基礎(chǔ)上再利用改進轉(zhuǎn)移匹配交換各用戶復(fù)用資源，最終形成穩(wěn)定的多對一穩(wěn)定轉(zhuǎn)移匹配方案。該方案不僅降低了計算復(fù)雜度和網(wǎng)絡(luò)時延，而且提高了資源利用率。

2 系統(tǒng)模型與問題描述

考慮下行雙層異構(gòu)無線網(wǎng)絡(luò)，一些微基站（FBS）和宏用戶（MUE）隨機分布在一個宏基站（MBS）的覆蓋范圍內(nèi)。FBS集合為F={1,2,…,M}， ||F=M ，MUE集合為MU={Mu1,Mu2,…,MuM}， ||MU=M。微基站m，m∈F，覆蓋范圍內(nèi)隨機分布Nm個微蜂窩用戶（FUE），記作 FUm={Fum1,Fum2,…,FumNm}，如圖1所示。故系統(tǒng)總蜂窩用戶數(shù)量可表示為，蜂窩用戶集合記作FU={Fu1,Fu2,…,FuN}。所有MUE和FUE共用R個信道，集合為C={c1,c2,…,cR}。假設(shè)各信道已經(jīng)提前分配給對應(yīng)的MUE，如cj分配給Muj。為了充分利用頻譜資源，假設(shè)各信道可同時被多個FUE復(fù)用，但各FUE最多只能復(fù)用一個信道，為了避免同一FBS下用戶的劇烈干擾，規(guī)定同一微蜂窩用戶不能復(fù)用同一信道。為了保證了Muj的服務(wù)質(zhì)量，規(guī)定所有FUE對Muj在cj上造成的總干擾不能超過干擾門限。

圖1 系統(tǒng)模型

其中Bj為cj的帶寬。所以微基站m中Fui的可達速率可表示為。復(fù)用cj的微基站m中Fui在cj上對Muj造成的跨層干擾可表示為

其中g(shù)m,Muj為微基站m與Muj之間的信道增益。Fui在cj上對Muj的干擾為。Muj受到的總跨層干擾可表示為。本文優(yōu)化目標是最大化整個系統(tǒng)FUE的可達速率，表示如下：

在 P1中，限制條件C1規(guī)定所有FUE在cj上對Muj造成的干擾低于Muj的干擾門限，從而保證了Muj的服務(wù)質(zhì)量。限制條件C2規(guī)定各FUE至多復(fù)用一個信道。限制條件C3規(guī)定同一蜂窩用戶不能復(fù)用相同信道。顯然P1是一個混合0-1規(guī)劃問題，其復(fù)雜度是指數(shù)冪[15]。復(fù)雜度會隨著網(wǎng)絡(luò)規(guī)模的增大而急劇增加。為解決此問題，提出利用多對一雙邊匹配理論[16]對模型進行求解。

3 基于匹配理論的資源分配方案

3.1 改進轉(zhuǎn)移匹配

本文將信道分配問題建模成多對一匹配，用(FU,C,qj,?FU,?C)表示，其中，?FU,?C分別表示信道和FUE的偏好關(guān)系。和傳統(tǒng)多對一匹配不同的是，并沒有對復(fù)用信道的FUE的數(shù)量進行直接限制，而是通過干擾門限Imax對FUE數(shù)量間接限制，即復(fù)用信道的FUE的數(shù)量具有動態(tài)性，另外在同一蜂窩中所有FUE不能復(fù)用同一信道，即在同一蜂窩中用戶可以理解為簡單的一對一匹配。為了提出具有動態(tài)配額的轉(zhuǎn)移匹配算法首先作出如下定義：

定義1匹配μ定義為一個多值映射：FU?C→FU?C，?i∈FU,?j∈C，當且僅當滿足下列條件時：

（1）(i,j)∈ μ 。

（2） ||μ(i) ≤1,?i∈FU 。

（3） ||μ(j)≤1,?j∈C，且 ||μ(j)∈FUm??，?m∈F。

（4） ||μ(j)≤qj,?j∈R ，且 ||μ(j)∈FU?? ，其中 qj是RBj的干擾配額。

（5）當且僅當i∈μ(j)時，μ(i)=j。

對于FUE來說，F(xiàn)UE更加傾向于復(fù)用使得自身擁有更大速率的信道。而對于信道來說，由于每個信道提前已經(jīng)分配給各個MUE，信道更傾向于分配給對MUE造成干擾更小的FUE。所以，F(xiàn)UE的偏好序和信道的偏好序可根據(jù)如下偏好度函數(shù)建立：

定義2對于多對一匹配，如果滿足下列條件：

圖2 傳統(tǒng)轉(zhuǎn)移匹配

圖3 改進轉(zhuǎn)移匹配

改進轉(zhuǎn)移匹配定義如公式（7）、（8），其中，n=μ(i)，n′=μ(i′)。

定義3對于多對一轉(zhuǎn)移匹配，如果滿足下列條件：

稱主體對 {(i,n),(i′,n′)}或 (i,n)為轉(zhuǎn)移阻礙穩(wěn)定對。其中，定義 Iin=0,?i∈FU,n=? ，即 Fui不復(fù)用資源時干擾為0。表示cn上的干擾余量，U(μ)表示匹配μ的效用，可由計算。條件（1）表示如果在滿足干擾條件下，i、i′交換其復(fù)用信道資源后總效用增加；條件（2）表示在滿足干擾條件下，i通過放棄復(fù)用當前信道，而重新復(fù)用其他信道可以使得總效用增加。

定義4當一個匹配中不存在阻礙穩(wěn)定對時，稱該匹配為穩(wěn)定匹配。

定義5當一個匹配中不存在轉(zhuǎn)移阻礙穩(wěn)定對時，稱該匹配為轉(zhuǎn)移穩(wěn)定匹配。

3.2 改進轉(zhuǎn)移匹配算法

本文為了求出穩(wěn)定匹配，提出了改進轉(zhuǎn)匹配算法。該算法分為兩層：Stage 1為改進型Gale-Shapley匹配算法（Modified Gale-Shapley），其中遞延匹配算法（Gale-Shapley）由諾貝爾獎經(jīng)濟學(xué)獎獲得者GALE和SHAPLEY解決匹配問題時提出[9]。Stage 1共分4步：步驟1：初始化，根據(jù)公式（5）、（6）構(gòu)建偏好列表 P ；步驟2：建立分配矩陣A，將其中各元素置0，各信道上的干擾余量設(shè)置為=，找出當前未匹配且其偏好列表非空的FUE。步驟3、4：FUE逐個向信道提出申請，信道根據(jù)其偏好列表對FUE進行決策。如果所有FUE都已匹配好或者未匹配DUE的偏好列表為空，此時Stage 1結(jié)束。Stage 2為轉(zhuǎn)移匹配過程，共分為兩步：步驟1：FUE尋找能使系統(tǒng)FUE擁有更高效用的信道，如果存在這樣的信道，則該FUE復(fù)用該信道，放棄當前復(fù)用信道，否則保持不變；步驟2：同一蜂窩不同F(xiàn)UE用戶之間交換復(fù)用RB，如果交換后系統(tǒng)FUE總效用增加，則交換，否則保持不變。直到不存在阻塞轉(zhuǎn)移匹配對存在時，算法結(jié)束。

改進型轉(zhuǎn)移匹配算法具體步驟如下：

Stage 1改進型Gale-Shapley匹配過程

步驟1 根據(jù)公式（5）、（6）計算Ui(j)，Uj(i)，?i,j，建立偏好矩陣P。

步驟2初始化分配矩陣A中元素xi,j=0，=，?i∈FU,j∈C，未匹配FUE集合記作dum={dum1,dum2,…,dumM}，其中dumi表示Fi中未匹配FUE向量，F(xiàn)i∈M。

步驟3 while存在dumn≠?，dumn∈dum且其偏好列表非空。

步驟4 fori∈dumn。

j是在i偏好列表中偏好序較高的信道，將 j從i偏好列表中刪除，找出i′∈dumn

else

找出目前匹配信道 j的所有 i″，i″∈dumdumn且 i?ji''，記作集合dle。

j拒絕dle中偏好序最低的i''，

end while

else

A=temp，

end if

end if

end for

end while

Stage 2改進轉(zhuǎn)移匹配過程

while不存在阻塞轉(zhuǎn)移穩(wěn)定對

步驟1對?i∈Fum,m∈F，如果(i,n)是阻礙轉(zhuǎn)移穩(wěn)定對，μ←μi，μi定義見公式（7）。否則當前匹配保持不變。

步驟2 對?i∈Fum,m∈F，選取i′∈{Fumdi}，如果{(i,n),(i′,n′)}是阻礙轉(zhuǎn)移穩(wěn)定對，μ←μi′i，μi′i定義見公式（8）。

end while

3.3 算法穩(wěn)定性、復(fù)雜度分析

定理1改進轉(zhuǎn)移匹配算法的解是穩(wěn)定的。

證明 在Stage 1中，對于?(i,j)∈FU×R，μ(i)≠j，滿足 j?iμ(i)。由算法步驟4知Fui曾經(jīng)向cj提出過申請，由μ(i)≠j可知：算法結(jié)束時cj拒絕了Fui的申請，由步驟4可知，?Fui∈FU ，不存在 Fui′?jFui，滿足條。由定義2可知不存在阻礙穩(wěn)定對。綜上，由定義4可知Stage 1的匹配是穩(wěn)定的。另外在Stage 2中，算法結(jié)束條件為不存在阻塞轉(zhuǎn)移穩(wěn)定對。由定義5可知最終結(jié)果是轉(zhuǎn)移穩(wěn)定的，證畢。

證明 在Stage 1中，由于每個FUE最多向R個信道提出用頻申請，N個FUE最多提出N×R次用頻申請，因此時間復(fù)雜度為ο(N×R)。而在Stage 2中，由于未轉(zhuǎn)移時匹配μ0與最終穩(wěn)定轉(zhuǎn)移匹配μfinal效用值的差值為Φμ0→μfinal，Δmin為每次轉(zhuǎn)移過程中效用值得最小增量。故算法復(fù)雜度小于等于，綜上改進轉(zhuǎn)移匹配算法的復(fù)雜度是，證畢。

4 仿真分析

仿真考慮一個異構(gòu)網(wǎng)絡(luò)部署在250 m×250 m的正方形區(qū)域內(nèi)，MBS位于正方形區(qū)域中心，MUE、FBS隨機分布在MBS通信范圍內(nèi)。各FUE隨機分布在以FBS坐標為圓心半徑為20 m的圓內(nèi)。MBS發(fā)射功率為46 dBm，F(xiàn)BS功率為23 dBm，噪聲功率為－90 dBm，各信道帶寬為180 kHz，并假設(shè)各信道干擾門限相同。信道增益gT,R=10(-L(dT,R)/10)，L(dT,R)為發(fā)射端與接收端的路徑損耗，假設(shè) L(dT,R)=15.3+37.6lg(dT,R)，dT,R為FBS與FUE之間的距離。gT,R可代表MBS到FUE，F(xiàn)BS與FUE，F(xiàn)BS與MUE之間的信道增益。

圖4分析了在信道數(shù)量固定為5，F(xiàn)UE數(shù)量分別為10、20、30情況下的累計分布函數(shù)（Cumulative Distribution Function，CDF）曲線。從曲線中可以看出，隨著FUE數(shù)量的增多，轉(zhuǎn)移操作次數(shù)增加。因為隨著FUE數(shù)量的增多，出現(xiàn)阻塞轉(zhuǎn)移穩(wěn)定對的概率會增加。CDF曲線表明改進轉(zhuǎn)移匹配算法能夠在短時間內(nèi)收斂。如當FUE數(shù)量為20時，轉(zhuǎn)移次數(shù)大約為20次時能保證算法收斂。

圖4 轉(zhuǎn)移次數(shù)累計分布函數(shù)(R=5)

圖5 對比了所提改進轉(zhuǎn)移匹配算法，傳統(tǒng)轉(zhuǎn)移匹配算法和改進Gale-shapley匹配算法在FUE數(shù)量為10，信道數(shù)量為2～20時的系統(tǒng)的效用曲線。在FUE數(shù)量固定的情況下，隨著信道的增多，系統(tǒng)總效用增加，這時可供FUE復(fù)用的信道增多，未復(fù)用信道的FUE也能復(fù)用信道。從圖中可以看出改進Gale-shapley匹配算法效用曲線最低，傳統(tǒng)轉(zhuǎn)移匹配效用曲線次之，最高的是所提改進轉(zhuǎn)移匹配效用曲線，因為改進Gale-shapley匹配算法完全沒有考慮不同DUE之間的相互干擾，傳統(tǒng)轉(zhuǎn)移匹配雖然考慮了DUE之間相互干擾，但正如圖2、圖3所示，相對于改進轉(zhuǎn)移匹配算法只考慮了不同F(xiàn)UE之間交換復(fù)用信道，而改進轉(zhuǎn)移匹配算法綜合考慮了不同F(xiàn)UE之間，F(xiàn)UE自身信道的交換，多樣性更強。

圖5 系統(tǒng)FUE用戶總效用(N=10,N1=N2=3,N3=4)

圖6 分析了在R=10，各小蜂窩FUE數(shù)量為：N1分別為2、3、5、6、8、10、11、12，N2分別為 2、3、5、6、8、10、11、12，N3分別為1、4、5、8、9、10，13、16情況下FUE數(shù)量對三種算法的影響。從改進Gale-shapley匹配算法曲線可以看出，在FUE數(shù)量較小（小于15）時，系統(tǒng)總效用隨著FUE數(shù)量的增加而增加，因為這時信道相對于FUE來說較充足，隨著FUE數(shù)量的繼續(xù)增加（大于15，小于25），F(xiàn)UE之間相互干擾加強，增加DUE的效用，小于該FUE共享信道對其他FUE的影響，所以這時系統(tǒng)效用反而會下降。最后當FUE數(shù)量增多時（大于25）時，因為此時信道相對不足，各小蜂窩中FUE不能復(fù)用相同信道，受蜂窩數(shù)量限制，各復(fù)用相同信道的FUE數(shù)量小于等于3。當復(fù)用相同信道的FUE數(shù)量達到3時，該信道上干擾限制變?nèi)酰@時決定系統(tǒng)效用是FUE數(shù)量，F(xiàn)UE越多意味著信道可匹配選擇增多。由于傳統(tǒng)轉(zhuǎn)移匹配算法是在改進Gale-shapley匹配算法匹配結(jié)果上進行轉(zhuǎn)移匹配，故曲線趨勢相近，且效用較改進Gale-shapley匹配算法好。另外，從所提轉(zhuǎn)移匹配算法曲線可以看出，在FUE數(shù)量較少時，F(xiàn)UE增加會使系統(tǒng)效用明顯增加。隨著FUE數(shù)量的繼續(xù)增加，網(wǎng)絡(luò)效用繼續(xù)增加，但由于此時信道數(shù)量不足，F(xiàn)UE間干擾增強，所以效用增加較平緩。效用繼續(xù)增加是由于所提算法充分考慮了FUE數(shù)量增加對網(wǎng)絡(luò)其他FUE的影響，如果新增FUE引入的干擾使得網(wǎng)絡(luò)效用其他FUE減少的效用大于該FUE的效用則該FUE不能復(fù)用資源，也即是說新增FUE使系統(tǒng)效用增加時，該FUE才能復(fù)用信道。從圖中也可以看出所提改進轉(zhuǎn)移匹配算法較其他兩種算法性能更好。

圖6 系統(tǒng)FUE用戶總效用(R=10)

圖7 分析了MUE干擾門限對系統(tǒng)FUE總效用影響。在干擾門限較低時，三種算法所得系統(tǒng)FUE總效用隨干擾門限增加而增加，干擾門限增加使得更多的FUE有機會復(fù)用信道。但是繼續(xù)隨著干擾門限增加，這時干擾門限已經(jīng)對改進Gale-shapley匹配算法和傳統(tǒng)轉(zhuǎn)移匹配算法不再起主要作用，即干擾門限的變化不會引起匹配結(jié)果的變化。而所提改進轉(zhuǎn)移匹配算法充分利用了干擾門限，F(xiàn)UE在自身和其他FUE之間合理進行交換復(fù)用信道，所以性能更好。

圖7 系統(tǒng)FUE用戶總效用(N=10,N1=N2=3,N3=4,R=5)

5 總結(jié)

本文針對分層異構(gòu)網(wǎng)絡(luò)，分析了在保護MUE服務(wù)質(zhì)量情況下的信道分配問題。將問題建模為具有動態(tài)配額的多對一雙邊匹配，提出了一種改進轉(zhuǎn)移匹配算法，在轉(zhuǎn)移匹配過程中，各FUE之間不斷地進行信道交換，最終達到收斂狀態(tài)。仿真結(jié)果表明，所提改進轉(zhuǎn)移匹配算法相對于傳統(tǒng)匹配算法和不考慮外部性匹配算法能收斂到高系統(tǒng)效用值。同時降低了計算復(fù)雜度，有利于實際系統(tǒng)的部署。