异构网络资源分配：改进多对一转移匹配

刘 岗，赵杭生，李大力，邵鸿翔，

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数量较小（小于15）时，系统总效用随着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之间不断地进行信道交换，最终达到收敛状态。仿真结果表明，所提改进转移匹配算法相对于传统匹配算法和不考虑外部性匹配算法能收敛到高系统效用值。同时降低了计算复杂度，有利于实际系统的部署。