異構網絡資源分配：改進多對一轉移匹配

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

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

2.南京電訊技術研究所，南京 210007

1 引言

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

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

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

2 系統模型與問題描述

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

圖1 系統模型

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

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

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

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

3.1 改進轉移匹配

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

定義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來說，FUE更加傾向于復用使得自身擁有更大速率的信道。而對于信道來說，由于每個信道提前已經分配給各個MUE，信道更傾向于分配給對MUE造成干擾更小的FUE。所以，FUE的偏好序和信道的偏好序可根據如下偏好度函數建立：

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

圖2 傳統轉移匹配

圖3 改進轉移匹配

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

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

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

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

定義5當一個匹配中不存在轉移阻礙穩定對時，稱該匹配為轉移穩定匹配。

3.2 改進轉移匹配算法

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

改進型轉移匹配算法具體步驟如下：

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

步驟1 根據公式（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向量，Fi∈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改進轉移匹配過程

while不存在阻塞轉移穩定對

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

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

end while

3.3 算法穩定性、復雜度分析

定理1改進轉移匹配算法的解是穩定的。

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

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

4 仿真分析

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

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

圖4 轉移次數累計分布函數(R=5)

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

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

圖6 分析了在R=10，各小蜂窩FUE數量為：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數量對三種算法的影響。從改進Gale-shapley匹配算法曲線可以看出，在FUE數量較?。ㄐ∮?5）時，系統總效用隨著FUE數量的增加而增加，因為這時信道相對于FUE來說較充足，隨著FUE數量的繼續增加（大于15，小于25），FUE之間相互干擾加強，增加DUE的效用，小于該FUE共享信道對其他FUE的影響，所以這時系統效用反而會下降。最后當FUE數量增多時（大于25）時，因為此時信道相對不足，各小蜂窩中FUE不能復用相同信道，受蜂窩數量限制，各復用相同信道的FUE數量小于等于3。當復用相同信道的FUE數量達到3時，該信道上干擾限制變弱，這時決定系統效用是FUE數量，FUE越多意味著信道可匹配選擇增多。由于傳統轉移匹配算法是在改進Gale-shapley匹配算法匹配結果上進行轉移匹配，故曲線趨勢相近，且效用較改進Gale-shapley匹配算法好。另外，從所提轉移匹配算法曲線可以看出，在FUE數量較少時，FUE增加會使系統效用明顯增加。隨著FUE數量的繼續增加，網絡效用繼續增加，但由于此時信道數量不足，FUE間干擾增強，所以效用增加較平緩。效用繼續增加是由于所提算法充分考慮了FUE數量增加對網絡其他FUE的影響，如果新增FUE引入的干擾使得網絡效用其他FUE減少的效用大于該FUE的效用則該FUE不能復用資源，也即是說新增FUE使系統效用增加時，該FUE才能復用信道。從圖中也可以看出所提改進轉移匹配算法較其他兩種算法性能更好。

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

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

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

5 總結

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