基于图着色的加权优先D2D资源分配算法研究

薛建彬，陈谱滟

(1.兰州理工大学 计算机与通信学院，甘肃 兰州 730050；2.东南大学 移动通信国家重点实验室，江苏 南京 210096)



基于图着色的加权优先D2D资源分配算法研究

薛建彬1，2，陈谱滟1

(1.兰州理工大学 计算机与通信学院，甘肃 兰州 730050；2.东南大学 移动通信国家重点实验室，江苏 南京 210096)

针对蜂窝用户与D2D用户所构成的异构网络系统中同频干扰问题，提出一种基于图着色的加权优先D2D资源分配算法。该算法不仅允许多个D2D用户复用一个蜂窝用户资源，而且能够实现简单功控。首先建立异构干扰图，对系统终端用户及干扰类型进行分类异构。然后计算着色优先级，考虑各种影响因子以提升算法的实用性。最后再由分配结果进行组内功率控制，以满足绿色通信的要求。仿真表明，该算法不仅可以降低系统用户接入损失率，提高系统吞吐量，而且还减少了功率消耗。

资源分配；分类异构；图着色；功率控制；绿色通信

D2D(Device-to-Device)通信能够使得短距离范围内的终端用户不通过基站转发而直接进行数据传输，从而很大程度提高了数据传输速率。此外，D2D用户还可以用非正交方式复用蜂窝用户的无线资源以提高频谱资源利用率，因此，D2D通信在近年来受到业界的广泛关注[1-3]。然而对无线资源的复用会在系统中产生同频干扰[4-5]，所以如何通过为D2D用户分配无线资源以抑制同频干扰对提高频谱利用率和满足用户的高速数据传输需求具有重要的现实意义和研究价值[6-8]。

在文献[9]中LEE Changhee等人根据D2D用户提供的干扰列表建立干扰图，并基于图着色进行顺序资源分配，但该算法对终端设备的性能要求较高。文献[10]建立D2D用户和蜂窝用户间加权二分图，并采用最优匹配算法分配无线资源，提高了系统吞吐量，但算法复杂度较高。在文献[11]中HAN Jiang等人允许一个D2D用户复用一个蜂窝用户的无线资源，并利用最优匹配实现了最小化系统中同频干扰。TAB Li等人在文献[12]中对基于图着色理论给出一种认知频谱分配方法，该方法将系统带宽分为多个子信道，再将子信道分配给用户，从而最小化带宽需求，但该方法不能最大化系统吞吐量。此外，现已存在的图着色资源分配算法均是将D2D用户与蜂窝用户作为对等用户建立常规干扰图，再进行无线资源分配。然而D2D通信的引入仅仅是作为蜂窝通信的一种辅助通信方式，这样的无线资源分配不能有效体现出不同通信类型用户的重要性。此外，传统图着色资源分配算法仅根据顶点饱和度来评判着色优先级的策略已远远无法满足实际通信需求。

考虑到上述存在的问题，本文针对D2D用户复用LTE系统中蜂窝用户下行链路进行通信时，尤其在社交网络中对通信质量和传输速度要求较高的场景下，提出了一种基于图着色的加权优先D2D资源分配算法。相比于传统图着色资源分配算法，该算法的优势在于：1) 在D2D异构网络中，建立了一张异构干扰图，以体现出网络中两类用户重要程度的差异。2)着色顺序不再是以往的随机着色或者顺序着色，而采用加权优先着色。3)确定了无线资源分配以后，引入简单分组功控，不仅能够进一步减小用户发送功率降低干扰影响，还能够动态调整特定无线资源上的能量消耗。最后，结合算法仿真图，对比分析该算法相对于其他类似算法的优势。

1　系统模型

在D2D异构网络中，系统内存在着两类用户：传统蜂窝用户和短距离D2D用户对。建立系统模型如图1所示，系统中共有M个蜂窝用户，记为C={C1,C2,…,CM}；N个D2D通信对，记为D={D1,D2,…,DN}。其中，Ci表示第i个蜂窝用户，Txi表示第i个D2D用户对中的发送端用户，Rxi表示接收端用户。同时D2D用户以相同初始发送功率进行数据传输。另外，用LC表示蜂窝链路集合，LD表示所有D2D链路集合，Lk表示使用无线资源k的链路集合。为提高频谱利用率，允许多个D2D用户对复用同一蜂窝用户的无线资源进行数据传输。

由于LTE系统下行采用OFDM(Orthogonal Frequency Division Multiplexing)技术，因此，蜂窝用户之间不存在干扰，而D2D用户以非正交方式复用蜂窝用户下行信道资源，则系统中主要存在两种干扰：D2D用户对之间的干扰和D2D用户对与蜂窝用户之间的干扰。

具体干扰情况如图1所示。图中C1，Tx1，Tx2使用相同信道资源进行数据传输，基站会对Rx1，Rx2造成同频干扰；同时Tx1也会对C1和Rx2造成同频干扰；另外Tx2也会对C1和Rx1造成同频干扰。由此可见，D2D异构网络中的干扰情况比较复杂，为此需要对频谱资源进行合理分配以协调同频干扰，从而保证终端用户通信质量并提高频谱利用率。

图1　系统模型

此外假设(φi,ri)是用户i的极坐标，则用户i与用户j之间的距离dij在极坐标下表示为

(1)

式中：ri表示用户i到基站距离；φi表示用户i方位角。那么系统中的路损模型如下

基站到用户的路径损失为

p=148+37.6lg(d[km])

(2)

不同用户之间的路径损失为

p=148+40lg(d[km])

(3)

其中，d表示通信链路收发端之间的距离。

2　基于图着色的加权优先资源分配

根据实际情况，在D2D异构网络中，D2D通信为辅助通信方式，蜂窝用户是主用户而D2D用户仅为从用户，因此在进行干扰分析时应严格对主从用户进行区分。另外，为满足用户的正常通信质量需求，预设蜂窝用户正常通信的SINR阈值为γ1，D2D用户正常通信的SINR阈值为γ2。在基于图着色的加权优先分配资源时，将系统中的通信链路和链路之间的同频干扰分别抽象为图中的“顶点”和“边”，从而建立一张异构干扰图H。特别指出，在建立异构干扰图时，应先将系统中每条通信链路抽象为异构图的“顶点”，然而两个“顶点”之间“边”是否存在，则要结合用户SINR阈值要求和用户间同频干扰程度来决定。

2.1建立异构干扰图

异构干扰图中的“顶点”由蜂窝链路和D2D链路构成。其中，所有蜂窝链路构成顶点集合V1，所有D2D通信链路构成顶点集合V2。V1和V2一起组成图中所有顶点的集合V。根据顶点间干扰以及用户的通信质量要求构成边的集合E，从而可得到异构干扰图H(V(V1,V2),E)。结合D2D异构网络的特性，图H中边主要分为两类：单类干扰边和混合类干扰边。其中，单类干扰边则是针对蜂窝链路仅收到D2D链路的单一干扰所建立的边；混合类干扰边则是针对D2D链路遭受的干扰为来自蜂窝链路和其他D2D链路的混合干扰所建立的边。

当多个D2D用户对以非正交方式与同一蜂窝用户使用相同无线资源k时。蜂窝用户Ci的SINR为

(4)

D2D链路接收端Rxj的SINR为

(5)

式中：SINRCi表示Ci的SINR；Pi,k表示基站在信道k上对Ci的发送功率；GB,Ci表示基站到Ci的链路增益；PTxj,k表示Txj在信道k上的发送功率；GTxj,Ci表示Txj到Ci的链路增益；η表示高斯白噪声功率；B表示信道带宽。

另外定义链路i的发送端对链路j的接收端产生的干扰为Iij，具体表示为

Iij=PiGij

(6)

式中：Pi表示链路i发送端的发送功率；Gij表示链路i发送端到顶点j的接收端链路增益。

边建立的详细步骤如下：

1)单类干扰边建立，步骤(伪代码)如下：

Begin

1. 初始化集合φi=φ，顶点i=j=1，权值ωij=0

2.fori=1toM

3.Whilej≤Nthen

4. 用公式(5)计算 SINRij

5.φi=φi+{j}

6.endwhile

7.do

8.IfSINRij=min(SINRi)andj∈φithen

9. 顶点j与顶点i之间建立异类干扰边j→i，并记边加权值为 ωji=Iji

10.endif

11.While(SINRij>γ1)

12.endfor

13.End

2)混合类干扰边建立

混合类干扰边的建立步骤和方法与单类干扰边的建立类似，不同之处在于第4步，SINR的计算采用式(5)，以及第11步中的判断条件更改为SINRij>γ2。故此处不再进行赘述。

在单类与混合类干扰边建立完成之后，最终得到一个异构干扰图H。此时，根据图H定义顶点的i饱和度S(i)为

(7)

2.2加权优先资源分配

假设基站端有两个缓冲队列，分别存放发起资源请求的蜂窝用户和D2D用户，每个用户对应一个数据队列用来缓存待发送的数据。为不失一般性，定义影响获得资源优先级的因素包括：1)信道质量；2)用户排队等待时延；3)用户待发送数据量；4)用户能忍受的最大时延。一般地，用户获得资源的优先级越高，则要求信道质量好、用户排队时延大、待发送数据多、用户可忍受等待时延小。假设用户i发起资源请求的时刻记为ti,arr_time，获得无线资源的时刻记为ti,leave_time，那么用户i在队列中的排队等待时延Ti为

Ti=ti,leave_time-ti,arr_time

(8)

当等待时延超过能承受的最大时延时，用户则会丢弃待发送的数据包。为了避免信道质量差的用户长时间分配不到资源，降低系统公平性，因此这里将延迟作为影响用户获得获取资源优先级的一个重要因素，定义用户i的延迟权重为

(9)

式中：Ti,max用户i允许接受的最大延迟。

假设用户期望发送数据量的大小为Qi′，数据队列能缓存的最大数据量为Qi,max，因此对应数据队列中实际待发送数据大小Qi为

Qi=min{Qi′,Qi,max}

(10)

同时以信噪比衡量信道质量，信噪比越大说明信道质量越好。链路i接收端的信噪比具体表示为

(11)

基于上述分析，将用户i获得无线资源的优先级定义为

(12)

式中：D(i)表示用户i获得资源的优先级；对应顶点i和i′属于同类集合的顶点。

对顶点着色时，综合考虑用户优先级和对应顶点饱和度确定着色顺序。根据式(7)和式(12)对图中顶点i着色等级F(i)定义为

(13)

当前层着色顶点color*需满足条件为

(14)

同时将已着色顶点从对应顶点集合中删除，更新未着色顶点。

考虑到D2D通信只是一种辅助通信模式。因此在基于图着色的异构加权进行着色资源分配时，需要优先对顶点集合V1中的顶点着色，再对集合V2中顶点着色。具体着色步骤(伪代码)描述如下：

Begin

1. 初始化系统中可用无线资源数为K，可选颜色集合φ={φj|j∈V2,φj=K}，未着色顶点集合ϑ=V2，顶点i=j=1

2.fori=1toM

3. 根据式(13)计算F(i)，确定着色顺序并为顶点着色

4.endfor

5.forj=1toN

6. 根据式(13)计算F(j)，更新φj=K-定点j的度

7.endfor

8.Do

9. 根据式(14)找到集合ϑ中顶点着色优先级最高的顶点i

10.Ifφi=1then

11.elseifφi>1then

12. 从φi集合的可用颜色中，选择已经被其他顶点着色次数最多的颜色，并将其为顶点i着色

13.endif

14.更新未着色顶点集合ϑ=ϑ-i；找到与i相邻的顶点，并从这些顶点的可用颜色列表中去掉顶点i使用过的颜色

15.while(ϑ=空集)

16.End

为了评判系统中D2D用户间的公平性，采用jains公平性评估标准如

(15)

式中：Fair表示系统公平性；n表示请求资源的D2D用户数量；xi表示D2D用户i的传输速率。

将D2D系统用户损失率定义为因超过最大时延而放弃排队等待资源分配的用户数与请求用户总量比值，具体定义为

(16)

式中：n表示等待时延超过最大时延的D2D用户数；N表示请求资源的D2D用户数。

2.3分组功率控制

为了减小用户终端功率消耗，以保证用户最低SINR要求为前提，采用简单功率调控最小化对应用户的发送功率。根据图着色无线资源分配结果，将占用相同无线资源的所有用户作为一个分组，对每组中所有用户进行功率调控，从而优化用户的发送功率。

根据资源分配结果，计算蜂窝用户和D2D用户实际SINR。结合Cm的SINR阈值γ1和同组Gm的D2D用户的发送功率，可以得到其最低发送功率为

(17)

式中：Pm′表示经过功率调控后；基站对Cm的发送功率。

按式(17)更新基站对Cm的发送功率，同时结合式(5)计算所有D2D用户的SINR，并按此时的SINR从大到小逐个更新D2D用户发送功率。根据阈值要求γ2，更新Gm当前SINR最大的Rxn相应Txn的发送功率表示为

(18)

式中：PTn′表示经功率控制后Tn的发送功率；若Ti发送功率已更新，则PTi为更新后的发送功率，否则为原始功率。

对未更新功率的D2D用户按照SINR从大到小的顺序，继续采用式(18)更新发送功率，从而减小系统功率消耗。

3　仿真与性能分析

为了评估本文提出的D2D无线资源分配算法对系统性能的影响，采用计算机仿真来进行验证和分析。用户在小区内服从均匀分布，蜂窝用户分布在基站中心200m内，D2D用户复用蜂窝用户下行链路资源。每个用户排队等待时延在仿真时随机生成，其余仿真参数设置如表1所示。由于所有用户在小区中的位置具有一定随机性，仿真次数为500次并取平均值以便得到的数据更具有参考价值。同时，将以随机着色资源分配算法(RCA)、仅考虑时延的着色资源分配算法(DCA)和传统图着色资源分配算法(TGCA)作为参考，对比本文的分配算法(DGCA)，重点考察D2D系统公平、系统吞吐量和系统功率消耗等方面的性能。

表1仿真参数设置

参数名参数取值小区半径/m750D2D通信对距离/m10～25子信道数5系统带宽/MHz5蜂窝请求用户数5基站发送功率/dBm43D2D用户发送功率/dBm24高斯白噪声密度/(dBm·Hz-1)-174γ1,γ2/dB12,16蜂窝、D2D链路阴影衰落标准差/dB10,12α,β0.7,0.3

图2比较了不同算法下，D2D系统资源分配的公平性影响。从图中可以看出，随着D2D请求对数增加，D2D系统公平度开始下降。其中，TGCA以吞吐量最大为目标，而相对牺牲了较多的公平性。在系统中有80对D2D用户的情况下使用DGCA算法，则相比于DCA算法可以提高5%的调度公平性。这是因为DCA算法仅考虑时延而没考虑顶点饱度，而DGCA不仅考虑了顶点饱和度，而且也将时延作为着色的一个因素，能够在一定程度上提高那些因为信道质量差而迟迟得不到资源的D2D用户获得资源的优先级，因此，系统的公平性得到了提高。

图2　不同算法公平度比较

图3比较了不同着色资源分配算法下，D2D系统平均时延的影响。由图可看出不同算法的系统平均时延都随着资源请求的D2D对数增加而增加。其中，相比于DCA算法，DGCA算法在D2D用户数达到50对时系统平均时延会稍微偏高0.1 ms，但D2D通信主要用于数据传输而非实时业务，因此0.1 ms的延迟对用户并不感知。另外结合图2和图3分析可知DCA算法优先对时延较大的顶点进行着色资源分配，使系统整体时延最小，但是严重牺牲了资源调度的公平性。相比于其他两种算法，DGCA在降低系统时延上则显示出了明显的优势。

图3　不同算法系统时延比较

图4比较了不同算法下的系统吞吐量。从图中可以分析随着系统中D2D用户数的增加，系统吞吐量也逐渐增加。由于TGCA算法仅仅根据顶点饱和度进行着色资源分配，而获得了最大的系统吞吐量。DGCA不仅考虑了顶点饱和度还提高了时延较大顶点的着色优先级，使得丢弃的数据包较少，虽然获得的吞吐量相比于TGCA有平均1.5%的降低，但结合图2、图3和图4综合分析，TGCA获取较高吞吐量的前提则是严重牺牲了用户调度的公平性以及很大程度上增加了系统的时延。

图4　不同算法下系统吞吐量比较

图5比较了不同阈值对系统吞吐量的影响。图中显示随着D2D对数增加，系统吞吐量增加，而阈值越大，系统吞吐量越小。这是因为未达到用户SINR阈值时，系统接入D2D对数随着请求D2D对数增加而增加，从而系统吞吐量也增加，而SINR阈值越大，用户能承受的干扰越小，允许接入的D2D对数越少，系统吞吐量就越小。

图5　SINR阈值对系统吞吐量影响

图6比较了有功率控制和无功率控制时系统总的功率消耗。没有功率控制时，基站和用户均以固定功率发送，而有功率控制时，根据用户SINR最低要求进行功率控制，从而减小了系统功率消耗。

图6　功率控制对系统功耗影响

4　结语

在TD-LTE系统中为D2D用户选择合适的蜂窝用户下行无线资源进行复用。首先根据用不同通信类型户间干扰程度，建立异构干扰图。进一步结合顶点饱和度、等待时延、信道质量、数据量计算加权优先着色顺序。最后根据图着色算法进行无线资源的分配。理论上，改进了现有图着色资源分配算法的不足，并实现了系统最大吞吐量性能。实际上，又将影响无线资源分配的因素全面考虑，具有很强的实际应用价值。

仿真表明，本文算法在系统平均时延、丢包率以及系统吞吐量方面的综合性能最好，同时还减少了系统总功率消耗。

[1]DOPPLER K，RINNE M，WIJTING C，et al. Device-to-device communication as an underlay to LTE-advanced networks[J]. IEEE communications magazine，2009，47(12)：42-49.

[2]SARTORI P，BAGHERI H，DESAI V，et al. Design of a D2D overlay for next generation LTE[C]//Vehicular Technology Conference.[S.l.]： IEEE，2014：1-5.

[3]MOUBAYED A，SHAMI A，LUTFIYYA H. Wireless resource virtualization with device-to-device communication underlaying LTE network[J]. IEEE transactions on broadcasting，2015，61(4)：734-740.

[4]XIN Q，KANG C G. An effective interference alignment approach for device-to-device communication underlaying multi-cell interference network[C]//2012 International Conference on ICT Convergence (ICTC) .[S.l.]：IEEE，2012：219-220.

[5]ZHANG B，WANG Y，JIN Q. Energy-efficient architecture and technologies for device to device (D2D) based proximity service[J]. China communication，2015，12(12)： 32-42.

[6]PHUNCHONGHARN P，HOSSAIN E，KIM D I. Resource allocation for device-to-device communications underlaying LTE-advanced networks[J]. IEEE wireless communications，2013，20(4)：91-100.

[7]TSOLKAS D，LIOTOU E，PASSAS N，et al. A graph-coloring secondary resource allocation for D2D communications in LTE networks[C]//Proc.International Workshop on Computer Aided Modeling & Design of Communication Links & Networks. Barcelona：IEEE，2012：56-60.

[8]BIN WANG，LI CHEN，XIAOHANG CHEN，et al. Resource allocation optimization for device-to-device communication underlaying cellular networks[C]//Proc. Vehicular Technology Conference (VTC Spring).Budapest：IEEE，2011：1-6．

[9]LEE C，OH S M，PARK A S. Interference avoidance resource allocation for D2D communication based on graph-coloring[J]. Journal of Korean institute of communications & information sciences，2014，39A(12)：729-738.

[10]ZHANG H，WANG T，SONG L，et al. Radio resource allocation for physical-layer security in D2D underlay communications[C]//Proc. IEEE International Conference on Communications.Sydney：IEEE，2014：2319-2324.

[11]HAN J，CUI Q，YANG C，et al. Bipartite matching approach to optimal resource allocation in device to device underlaying cellular network[J]. Electronics letters，2014，50(3)： 212-214.

[12]TAB I，FENG Z，LI W，et al. Graph coloring based spectrum allocation for femtocell downlink interference mitigation[C]//Proc. IEEE Wireless Communications & Networking Conference. Cancun：IEEE，2011：1248-1252.

薛建彬(1973— )，教授，博士，主要研究方向为无线通信理论与技术，为本文通信作者；

陈谱滟 (1991— )，硕士，主研无线通信理论与技术。

责任编辑：许盈

Resource allocation algorithm based on graph coloring for weighted priority D2D communication

XUE Jianbin1，2, CHEN Puyan1

(1.SchoolofComputerandCommunication,LanzhouUniversityofTechnology,Lanzhou730050,China;2.NationalMobileCommunicationsResearchLaboratory,SoutheastUniversity,Nanjing210096,China)

In order to solve the co-channel interference problem in heterogeneous network system composed of cellular users and D2D users, a weighted priority D2D resource allocation algorithm based on graph coloring is proposed. This algorithm not only allows multiple D2D users to reuse the radio resource of one cellular user, but also can achieve simple power control. Firstly, the heterogeneous interference pattern is established based on the user equipment in system and the different types of interferences. And then the color priority is calculated, taking into account a variety of factors to improve the practicality of the algorithm. Finally, according to the results of the allocation of resources to control the power of user equipments of the group, to meet the requirements of green communication. Simulation results show that the proposed algorithm can not only reduce the loss rate of user equipments access the system and improve the system throughput, but also reduce the power consumption.

resource allocation; classification heterogeneous; graph coloring; power control; green communication

TN929.5

A

10.16280/j.videoe.2016.09.011

东南大学移动通信国家重点实验室开放研究基金资助课题(2014D13)；甘肃省自然科学基金项目(1310RJZA003)

2016-03-14

文献引用格式：薛建彬，陈谱滟. 基于图着色的加权优先D2D资源分配算法研究[J].电视技术，2016，40(9)：56-61.

XUE J B, CHEN P Y. Resource allocation algorithm based on graph coloring for weighted priority D2D communication [J].Video engineering，2016，40(9)：56-61.