D2D网络中具有动态配额的资源分配算法

,,,

(1.解放军理工大学 通信工程学院,南京 210007; 2.南京电讯技术研究所,南京 210007)

0 概述

随着移动互联网、物联网、智能终端的飞速发展,不断增长的无线业务需求对带宽和速率提出了极高要求。设备到设备(Device-to-Device,D2D)通信技术被视作一种提高资源利用率、增强用户体验的关键技术[1-2]。通过运用D2D技术,两个距离较近的通信设备之间可以不通过基站直接通信,这不仅降低了通信时延,而且提高了系统吞吐量[3-4]。但是,D2D技术带来便利的同时,也带来一些挑战。因为D2D复用频谱资源时会对系统中的授权用户造成干扰,降低系统性能,所以如何合理地对频谱资源进行分配显得尤为重要[5]。目前,大量文献对D2D网络的干扰管理作了研究。例如,文献[6]提出了一种基于比例公平的启发式资源分配方案。在提高系统吞吐量的同时,兼顾了公平性。文献[7]对多小区CDMA系统D2D通信上行性能进行了研究。文献[8]提出了一种D2D通信中基于信噪比均衡的资源分配算法。文献[9]将信道分配问题建模成混合非线性整数规划问题,利用贪婪启发式算法对模型进行求解。但是每个信道至多被一个D2D用户对复用,无法获得较高的频谱利用率。文献[10]用拍卖博弈的方法对蜂窝网络中的信道分配进行了分析。在文献[11-12]中,为了保证蜂窝用户的服务质量,将问题建模成具有静态配额的多对一匹配模型。

受此启发,本文提出一种在保证各蜂窝授权用户服务质量的情况下,各资源块可动态地被多个D2D用户同时复用的资源分配算法。利用双边匹配理论,将问题建模成多对一匹配问题。D2D用户和资源块(Resource Block,RB)根据各自设计好的效用函数分别建立偏好序,最后通过改进递延算法形成稳定的资源分配方案。

1 系统模型与问题描述

图1 系统模型

(1)

C3:xdi,j={0,1},∀di∈D,j∈R

在P1中,限制条件C1规定所有DUE在RBj上对CUEcj造成的干扰低于CUEcj的干扰门限,从而保证了cj的服务质量。限制条件C2规定各DUE至多复用一个RB。显然P1是一个混合0-1规划问题,其复杂度是指数幂。复杂度会随着网络规模的增大而急剧增加。

2 基于稳定匹配的资源分配

2.1 匹配理论

匹配理论是一种能够有效解决资源分配问题的方法,可以减小组合优化问题的复杂度,使问题更好求解[13]。匹配理论通常用于建模2个独立集合间的分配问题,且在这2个集合中,一方集合中个体对另一方集合中个体存在。这种偏好关系反映了一方集合中个体在选择对方集合中个体时的选择顺序[13]。

2.2 稳定静态匹配算法

(2)

C3:xdi,j={0,1}

定义1匹配μ定义为一个多值映射,即D∪R→D∪R,∀di∈D,∀j∈R,当且仅当满足下列条件时:

1)(di,j)∈μ;

2)|μ(di)|≤1,∀di∈D;

3)当且仅当di∈μ(j)时,μ(di)=j。

(3)

定义2对于多对一匹配,如果满足下列情况,称主体对(di,j)为阻碍稳定对:

定义3当一个匹配中不存在阻碍稳定对时,称该匹配为稳定匹配。

为了求出稳定匹配,可利用递延匹配算法[14]对其求解,算法略。

2.3 具有动态配额的稳定匹配

定义4匹配μ定义为一个多值映射:D∪R→D∪R,∀di∈D,∀j∈R,当且仅当满足下列条件时:

1)(di,j)∈μ;

2)|μ(di)|≤1,∀di∈D;

3)|μ(j)|≤qj,∀j∈R,且|μ(j)|∈D∪∅,其中qj是RBj的配额;

4)当且仅当di∈μ(j)时,μ(di)=j。

对于DUE来说,DUE更加倾向于复用使得自身拥有更大速率的RB。而对于RB来说,由于每个RB提前已经分配给各个CUE,RB更倾向于分配给对CUE造成干扰更小的DUE。所以,DUE的偏好序和RB的偏好序根据如下偏好度函数建立:

(4)

(5)

定义5对于多对一匹配,如果满足下列情况,称主体对(di,j)为阻碍稳定对:

对于所建立的多对一匹配模型,目标是寻找一个稳定匹配,而不是一个最优解,即以较低的计算复杂度来找到尽量使得个体满意的资源分配方式。

改进型Gale-Shapley匹配算法具体步骤如下:

步骤1根据式(4)、式(5)计算Udi(j)、Uj(di),∀di,j,建立偏好矩阵P。

步骤3whiledum≠∅,且其偏好列表非空。

步骤4fordi∈dum

j是在di偏好列表中偏好序较高的RB,将j从di偏好列表中删除;

else

找出目前匹配RBj的所有di',且di≻jdi',记作集合dle;

end while

else

end if

end if

end for

end while

2.4 算法稳定性、复杂度分析

对于所提改进递延匹配算法,从稳定性、优化性能和复杂度对算法进行分析。

定理1改进递延匹配算法的解是稳定的。

定理2改进递延匹配算法的复杂度是ο(M×R)。

证明:由于每个DUE最多向R个RB提出用频申请,M个DUE最多提出M×R次用频申请,因此时间复杂度为ο(M×R)。证毕。

3 仿真分析

仿真考虑一个D2D网络部署在250 m×250 m的正方形区域内,RB、CUE数量都取3,DUE数量M在区间[1,10]内动态变化。eNB的位置为正方形区域中心,CUE、DUE位置随机生成。DUE收发机之间距离固定为20 m。eNB发射功率为46 dBm,DUE发射机发射功率为23 dBm,噪声功率为-90 dBm,各RB带宽为180 kHz。信道增益gT,R=10(-L(dT,R)/10),L(dT,R)为发射端与接收端的路径损耗,假设L(dT,R)=15.3+37.6 lg(dT,R),dT,R为发射端与接收端的距离。gT,R可代表eNB到CUE之间或DUE收发机之间的信道增益。

为了对比算法性能,在不同干扰门限条件下将所提改进型Gale-Shapley匹配算法的求解结果和随机匹配算法、静态匹配算法做比较,仿真结果如图2所示。从仿真曲线可以看出,本文所提动态配额匹配算法的分配结果的效用曲线和通过穷收得到的最优结果效用曲线基本重合,接近最优解。本文所提算法相对于静态匹配算法能够得到更好的性能。随着干扰门限的增大,系统对CUE的保护性越弱,这时干扰门限限制不再影响分配结果,3种算法在高干扰门限时,分配效用具有相同的趋势。

图2 算法优化性能分析

图3为本文所提算法在RB总数为6,网络DUE总数分别为5、10、15、20、25、30的情况下,干扰门限和改进型Gale-Shapley匹配算法中的平均申请总数的关系。

图3 算法收敛性能分析

从图3可以看出,在DEU总数固定的情况下,随着干扰门限的增加,算法平均申请总数呈递减趋势,在干扰门限为-85 dBm～-60 dBm时下降最明显。因为在干扰门限很低的情况下,每次DUE提出申请时都被拒绝,这时理论上申请次数应该为M×R,其中每个DUE共申请R次。随着干扰门限增加,DUE逐渐被接受,这时每个DUE申请次数少于R次,总申请次数逐渐减少,当干扰门限大到对每个DUE直接接入其认为最好的RB,申请次数为M,即图中最后平均申请次数趋于不变。综上,算法时间复杂度为ο(M×R)。

在RB总数为6、干扰门限为-75 dBm、DUE总数为20的情况下,每个DUE申请次数如图4所示。

图4 各DNE的申请次数对比

从图4可以看出,d7申请次数为1,d2、d3、d4、d6、d11、d18申请次数为2,d16申请次数为3,d17申请次数为4,其余申请次数的用户最大申请数为6。从改进递延匹配算法可以看出,DUE申请次数和自身对CUE造成的干扰有关,对CUE造成的干扰大,被RB拒绝的次数越多。d7申请次数最小,是因为d7对其接入RB的干扰小,使得d7优先被接受,而申请次数为6的DUE对其所申请RB的干扰大被优先拒绝,最大拒绝次数为6。对于RB来说,CUE希望将自己的RB分配给对其干扰较小的DUE复用,从而保证了自身的服务质量。

4 结束语

本文针对分层D2D网络,分析研究了在保护CUE服务质量情况下的RB分配问题。将问题建模为具有动态配额的多对一双边匹配,提出了一种改进递延匹配算法,分别根据接入RB的可达速率和DUE接入RB对CUE造成的干扰来建立偏好列表,DUE和RB通过不断申请和拒绝最终找到资源分配方案。仿真结果表明,所提算法接近于最优分配方案,比静态匹配算法性能更优,同时降低了计算复杂度,有利于实际系统的部署。

[1] 焦 岩,高月红,杨鸿文,等.D2D技术研究现状及发展前景[J].电信工程技术与标准化,2014(6):83-87.

[2] BOCCARDI F,HEATH R W,LOZANO A,et al.Five disruptive technology directions for 5G[J].IEEE Communications Magazine,2014,52(2):74-80.

[3] 王俊义,巩志帅,符杰林,等.D2D通信技术综述[J].桂林电子科技大学学报,2014,34(2):114-119.

[4] ASADI A,WANG Qing,MANCUSO V.A survey on device-to-device communication in cellular networks[J].IEEE Communications Surveys & Tutorials,2014,16(4):1801-1819.

[5] LIU Jiajia,KATO N,MA Jianfeng,et al.Device-to-device communication in LTE-advanced networks:a survey[J].IEEE Communications Surveys & Tutorials,2014,17(4):1923-1940.

[6] 王俊涛,李 慧,卜智勇.一种基于比例公平的启发式D2D资源分配方案[J].计算机工程,2017,43(12):78-82.

[7] 程永生,董宇涵,张学聃,等.多小区CDMA系统D2D通信上行性能研究[J].计算机工程,2013,39(7):11-15.

[8] 郜伟伟,易辉跃,胡艳军,等.D2D通信中基于信噪比均衡的资源分配算法[J].计算机工程,2012,38(10):5-8.

[9] LEI Lei,ZHONG Zhangdui,LIN Chuang,et al.Operator controlled device-to-device communications in LTE-advanced networks[J].IEEE Wireless Communications,2012,19(3):96-104.

[10] XU Chen,SONG Lingyang,HAN Zhu,et al.Efficiency resource allocation for device-to-device underlay communication systems:a reverse iterative combinatorial auction based approach[J].IEEE Journal on Selected Areas in Communications,2013,31(9):348-358.

[11] HASAN M,HOSSAIN E.Distributed resource allocation for relay-aided device-to-device communication under channel uncertainties:a stable matching approach[J].IEEE Transactions on Communications,2015,63(10):3882-3897.

[12] MANLOVED F.Algorithmics of matching under preferences[M].[S.l.]:World Scientific Pub.Co.,2013.

[13] GU Y,SAAD W,BENNIS M,et al.Matching theory for future wireless networks:fundamentals and applications[J].IEEE Communications Magazine,2015,53(5):52-59.

[14] GALE D,SHAPLEY L S.College admissions and stability of marriage[J].American Mathematical Monthly,2013,69(5):9-15.

[15] GUSFIELD D,IRVINGR W.The stable marriage problem:structure and algorithms[M].Cambridge,USA:MIT Press,1989.