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

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

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

1 引言

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

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

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

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

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

圖1 系統(tǒng)模型

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

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

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

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

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

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

定義1匹配μ定義為一個(gè)多值映射：FU?C→FU?C，?i∈FU,?j∈C，當(dāng)且僅當(dāng)滿足下列條件時(shí)：

（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）當(dāng)且僅當(dāng)i∈μ(j)時(shí)，μ(i)=j。

對(duì)于FUE來(lái)說(shuō)，F(xiàn)UE更加傾向于復(fù)用使得自身?yè)碛懈笏俾实男诺?。而?duì)于信道來(lái)說(shuō)，由于每個(gè)信道提前已經(jīng)分配給各個(gè)MUE，信道更傾向于分配給對(duì)MUE造成干擾更小的FUE。所以，F(xiàn)UE的偏好序和信道的偏好序可根據(jù)如下偏好度函數(shù)建立：

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

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

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

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

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

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

定義4當(dāng)一個(gè)匹配中不存在阻礙穩(wěn)定對(duì)時(shí)，稱(chēng)該匹配為穩(wěn)定匹配。

定義5當(dāng)一個(gè)匹配中不存在轉(zhuǎn)移阻礙穩(wěn)定對(duì)時(shí)，稱(chēng)該匹配為轉(zhuǎn)移穩(wěn)定匹配。

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

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

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

Stage 1改進(jìn)型Gale-Shapley匹配過(guò)程

步驟1 根據(jù)公式（5）、（6）計(jì)算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改進(jìn)轉(zhuǎn)移匹配過(guò)程

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

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

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

end while

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

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

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

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

4 仿真分析

仿真考慮一個(gè)異構(gòu)網(wǎng)絡(luò)部署在250 m×250 m的正方形區(qū)域內(nèi)，MBS位于正方形區(qū)域中心，MUE、FBS隨機(jī)分布在MBS通信范圍內(nèi)。各FUE隨機(jī)分布在以FBS坐標(biāo)為圓心半徑為20 m的圓內(nèi)。MBS發(fā)射功率為46 dBm，F(xiàn)BS功率為23 dBm，噪聲功率為－90 dBm，各信道帶寬為180 kHz，并假設(shè)各信道干擾門(mén)限相同。信道增益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情況下的累計(jì)分布函數(shù)（Cumulative Distribution Function，CDF）曲線。從曲線中可以看出，隨著FUE數(shù)量的增多，轉(zhuǎn)移操作次數(shù)增加。因?yàn)殡S著FUE數(shù)量的增多，出現(xiàn)阻塞轉(zhuǎn)移穩(wěn)定對(duì)的概率會(huì)增加。CDF曲線表明改進(jìn)轉(zhuǎn)移匹配算法能夠在短時(shí)間內(nèi)收斂。如當(dāng)FUE數(shù)量為20時(shí)，轉(zhuǎn)移次數(shù)大約為20次時(shí)能保證算法收斂。

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

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

圖5 系統(tǒng)FUE用戶(hù)總效用(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ù)量對(duì)三種算法的影響。從改進(jìn)Gale-shapley匹配算法曲線可以看出，在FUE數(shù)量較小（小于15）時(shí)，系統(tǒng)總效用隨著FUE數(shù)量的增加而增加，因?yàn)檫@時(shí)信道相對(duì)于FUE來(lái)說(shuō)較充足，隨著FUE數(shù)量的繼續(xù)增加（大于15，小于25），F(xiàn)UE之間相互干擾加強(qiáng)，增加DUE的效用，小于該FUE共享信道對(duì)其他FUE的影響，所以這時(shí)系統(tǒng)效用反而會(huì)下降。最后當(dāng)FUE數(shù)量增多時(shí)（大于25）時(shí)，因?yàn)榇藭r(shí)信道相對(duì)不足，各小蜂窩中FUE不能復(fù)用相同信道，受蜂窩數(shù)量限制，各復(fù)用相同信道的FUE數(shù)量小于等于3。當(dāng)復(fù)用相同信道的FUE數(shù)量達(dá)到3時(shí)，該信道上干擾限制變?nèi)?，這時(shí)決定系統(tǒng)效用是FUE數(shù)量，F(xiàn)UE越多意味著信道可匹配選擇增多。由于傳統(tǒng)轉(zhuǎn)移匹配算法是在改進(jìn)Gale-shapley匹配算法匹配結(jié)果上進(jìn)行轉(zhuǎn)移匹配，故曲線趨勢(shì)相近，且效用較改進(jìn)Gale-shapley匹配算法好。另外，從所提轉(zhuǎn)移匹配算法曲線可以看出，在FUE數(shù)量較少時(shí)，F(xiàn)UE增加會(huì)使系統(tǒng)效用明顯增加。隨著FUE數(shù)量的繼續(xù)增加，網(wǎng)絡(luò)效用繼續(xù)增加，但由于此時(shí)信道數(shù)量不足，F(xiàn)UE間干擾增強(qiáng)，所以效用增加較平緩。效用繼續(xù)增加是由于所提算法充分考慮了FUE數(shù)量增加對(duì)網(wǎng)絡(luò)其他FUE的影響，如果新增FUE引入的干擾使得網(wǎng)絡(luò)效用其他FUE減少的效用大于該FUE的效用則該FUE不能復(fù)用資源，也即是說(shuō)新增FUE使系統(tǒng)效用增加時(shí)，該FUE才能復(fù)用信道。從圖中也可以看出所提改進(jìn)轉(zhuǎn)移匹配算法較其他兩種算法性能更好。

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

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

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

5 總結(jié)

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