一种最大化吞吐量增益的D2D通信资源分配算法

郑相全 张先禄 何香

【摘 要】D2D通信用户与蜂窝用户复用相同的时频资源，能成倍地提升蜂窝小区的系统吞吐量，但蜂窝用户会付出复用代价，如功耗、速率等性能恶化。从兼顾D2D用户性能提升与蜂窝用户性能损失的角度出发，提出一种最大化吞吐量增益的资源分配算法。算法分为两个步骤：为单个D2D用户与单个蜂窝用户复用计算最大复用增益；为多个D2D用户和多个蜂窝用户执行二部图的最大权值匹配。理论研究和仿真结果表明，提出的算法能获得较大的吞吐量增益，且减少了系统总功耗，降低了蜂窝用户的复用代价。

【关键词】D2D通信；复用代价；资源分配；吞吐量增益

1 引言

D2D（Device-to-Device，D2D）通信[1]是指蜂窝网络中的终端直接通信而无需经过基站，这种通信方式可降低传输时延、提升传输速率，并能增加小区可承载的用户数量，是未来移动蜂窝网络实现高速率、近距离通信的重要方式。在多用户广播[2]、视频分发[3]、小区流量卸载[4]、机器对机器（Machine to Machine，M2M）[5]等应用场景将发挥重要作用。

合理的资源分配[6-7]是D2D通信的关键。目前D2D通信的资源分配技术，主要是在约束服务质量（Quality of Service，QoS）、发射功率、通信距离等条件下，优化系统吞吐量、能效、功耗等指标[8]。

针对单个D2D链路与单个蜂窝链路复用相同资源的情况，Doppler[9]等以最大化吞吐量的方式进行资源优化分配，并同时保证蜂窝用户QoS需求。对多个D2D链路与多个蜂窝链路进行资源复用，文献[10]研究了使得全網吞吐量最大的方法，为保障蜂窝用户和D2D用户的QoS需求，通过接入控制、功率分配及二部图的最大权值匹配三个步骤进行资源优化分配。上述文献及其发展方法虽能使得系统吞吐量达到最大，且满足D2D用户和蜂窝用户的QoS需求，但未考虑D2D链路复用蜂窝链路带来的容量变化，也未考虑复用D2D势必会导致蜂窝用户性能恶化的影响。文献[8]提出一种基于主从对策的分布式资源分配和功率分配方案，通过判断复用D2D链路能否带来吞吐量增益来划分D2D链路集合，利用基于主从对策的功率分配来最大化复用后的吞吐量，但其并未保证D2D用户的QoS需求，也未考虑对蜂窝用户带来的性能损失。

本文在满足D2D用户与蜂窝用户QoS需求的前提下，提出一种最大化吞吐量增益（Maximize Throughput Gain，MTG）的资源分配算法，在获得较高吞吐量增益提升的同时，降低整个小区的功耗，减少蜂窝用户性能损失。

2 系统模型

考虑同时存在蜂窝用户和D2D用户的混合网络，如图1所示，系统采用时分双工的工作方式，以D2D用户复用蜂窝小区上行链路的时频资源的情况进行分析。图1中，有N个蜂窝用户，表示为CE={C1， C2， …， CN}，有M个D2D用户（发端和收端的用户统称），表示为DD={D1， D2， …， DM}。假设小区内有N个可用的正交频率资源块（Resource Block，RB），基站对全部链路的信道状态信息（Channel State Information，CSI）具有感知能力，采用传统的蜂窝资源分配算法分配给N个蜂窝用户。M个D2D用户与蜂窝用户复用相同的RB，且一个D2D用户只能复用一个RB。网络中，蜂窝用户和D2D用户均受到来自对方的干扰，用虚线表示干扰，实线表示通信链路。

图1 D2D用户复用蜂窝用户的干扰示意图

路径损耗模型采用文献[10]中采用的信道模型。节点之间的链路增益可以表示为：

Gij=Jhi， jZi， jγi， j-α （1）

其中，Gij表示节点i到j的链路增益，J表示由系统影响的常数，hi， j表示节点i到j的多径衰落，Zi， j表示节点i到j的阴影衰落，γi， j表示节点i到j的距离，α表示路径损耗因子。D2D链路LD， D的路径增益表示为GLD， D，小区用户到基站的链路LU， B的路径增益表示为GLU， B，D2D发端到基站的链路LD， B路径增益表示为GLD， B，小区用户到D2D收端的链路LU， D的路径增益表示为GLU， D。

3 问题描述

本文要解决的问题是：多个D2D用户复用多个蜂窝用户资源，在满足D2D用户与蜂窝用户QoS需求的情况下，提升D2D用户的性能增益并降低蜂窝用户的性能损失。蜂窝用户的性能损失可体现为复用所需要的代价，简称为复用代价，用速率代价和功率代价来度量。速率代价与功率代价可表示为不与D2D用户复用资源和与D2D用户复用资源所带来的速率或功耗的性能损失，用式（2）和式（3）表示：

（2）

（3）

其中，Sr即为速率损失，Sp即为功耗损失。SINRUbefore、SINRU分别表示蜂窝用户复用前后获得的信干噪比（Signal Interference Noise Ratio，SINR），PUbefore、PU分别表示蜂窝用户复用前后的发射功率。SINRUbefore、SINRU与PUbefore、PU的关系为：

（4）

（5）

其中，PD为D2D用户的发射功率；为高斯白噪声的方差。

为便于分析，可假设复用前后速率相等或发射功率相等。现假设复用前后发射功率相同，此时Sp=0，代价函数只剩下Sr，即速率损失。因此降低复用后蜂窝用户的性能损失问题可转变为降低蜂窝用户的速率损失。同时为确保D2D用户速率增益，在单对D2D链路和蜂窝链路复用同一资源时，优化问题表述为：

（6）

（7）

其中，SINRD为D2D用户复用蜂窝用户资源后获得的SINR，且。

因上述问题为多目标优化问题，只能求得其非劣解。可采用评价函数法来求解，现采用线性加权法来构造评价函数，如式（8）所示：

（8）

为使各目标函数的求解方向一致，令λ1=1，λ2=-1，将各优化问题都转换为最大化问题。该函数的含义可以理解为最大化系统吞吐量增益，其考虑的是D2D链路复用蜂窝链路后，对全网吞吐量增益的最大化，而不是全网吞吐量最大化。对该问题的解为原最优化问题的一个次优解，因此最大化系统吞吐量增益可以兼顾对D2D用户的性能增益和蜂窝用户的性能损失。

考虑到整个蜂窝小区内存在多对D2D链路与多对蜂窝链路进行资源复用，该问题最终描述为：

（9）

其中，SINRU， min和SINRD， min分别为小区用户的最低SINR需求和D2D用户的最低SINR需求。SINRU、SINRD、SINRDbefore、SINRUbefore分别表示小区用户获得的SINR，D2D复用后获得的SINR以及小区用户复用之前的SINR。tD，U为资源复用的标识，当D2D用户D与蜂窝用户U复用同一资源时，tD，U=1，否则tD，U=0。由公式可知该表达式为一个非凸非线性的最优化问题，直接对其求解是NP-hard问题。本文将该问题分解为两个子问题进行求解。

4 资源分配

对整个小区进行最大化吞吐量增益的资源优化分配，需要极高的计算量，不利于实现，为此，本文将其划分为两个子问题进行求解。第一个子问题：针对单个D2D用户与单个蜂窝用户复用的情况，通过功率分配获得最大复用增益，只有在最大复用增益大于零的情况下才允许其接入。第二个子问题，对多个D2D链路复用多个蜂窝用户复用资源的情况，以一对一复用的资源优化分配为原则，利用二部图的最大加权匹配解决最大化吞吐量增益为目标的配对问题。

4.1 基于复用增益的接入控制

现有D2D用户D想与蜂窝用户U进行资源复用，且D2D链路与蜂窝链路均应满足QoS约束，即：

（10）

在上式等号成立的情况下，联合求解可得一组功率解：

（11）

在功率约束的条件下，需要满足：

（12）

若成立，即D2D用户D具有接入资格，可为D2D用户D执行功率分配；若不成立，则D2D用户D失去复用小区用户U的资格。

当满足约束条件时，功率分配的原则是使复用速率增益最大化。即在功率约束和QoS约束情况下获得可行解范围内的功率分配，该分配能够获得最大速率增益，问题表述为：

（13）

该问题为一个非线性规划问题，设其可行解范围为Γ。若该D2D复用小区用户U资源可行，功率分配存在于可行解范围Γ的下边界处。将该结论应用到原最优化问题时，可缩小可行解范围Γ到下边界处，可将原最优化问题通过如下等式进行转换，即：

（14）

转换后存在常数项log2（1+SINRD，min），但其不影响对问题的求解，因此忽略常数项。原最优化问题转换为：

（15）

令：

（16）

通过对该函数求导数得到：

（17）

其中，

令，可以得到Q（PU）的极值点：

（18）

其零点中有一解为负，另一解为正。故在范围处正解可能为其极值点，由于，此时极值处的解可以简化为：

（19）

若可行解范围内存在极值，则最大值为极值，若可行解范围内不存在极值，则最大值为边界处。因此最优功率分配的解为：

（20）

其中，Pa为式（11）中求得的，为式（19）求得的极值点，Pb为可行解边界的交点解，因可行解范围的变动而不同，需要分情况进行讨论。QoS与功率约束获得的可行解可能存在的解范围如图2所示。

（1）当可行解如图2（a）和图2（c）情况时，可行解范围PU∈[Pa， Pb]，如图标注所示。因此。

（2）当可行解如图（b）情况时，可行解范围PU∈[Pa， PU， max]，如图标注所示。因此Pb=PU， max。

通过式（20）可求得最优功率分配对。获得最优功率分配的可行解之后还需要确认该复用链路是否能带来吞吐量的增益，即将获得的功率分配值代入式子（21）得到，通过判断是否大于零，确定D2D用户D是否真正具备复用该小区用户U的资格。

（21）

4.2 多个D2D用户复用多个蜂窝用户资源

在获得单对D2D用户与单个蜂窝用户复用后的最大吞吐量增益后，现需要解决多个D2D用户复用多个蜂窝用户的全网吞吐量增益最大问题。现对D2D用户集合中的每个D2D用户寻找可以复用的蜂窝用户集合，即复用后可以带来吞吐量增益的组合。此集合表示为，即D2D用户D与其复用可以带来增益的蜂窝用户集合。现需要为可接入的D2D用户选择使得全网吞吐量增益最大的蜂窩用户组合。该问题可采用二部图的最大加权匹配来解决，则最优化问题可描述为：

（22）

DD?表示可接入的D2D用户集合。可采用文献[11]中的Kuhn-Munkres算法求解上述问题，过程不再描述。

整个MTG资源分配的伪代码描述如表1所示：

5 算法仿真及验证

为了验证本算法的性能，采用文献[12]提出的启发式算法（简称Heuristic算法）和文献[10]的基于最大化系统吞吐量的资源分配算法（简称MT算法）进行对比。

Heuristic算法[12]是一种由接入控制、固定功率分配和启发式信道分配组成的启发式算法，其思路是：基站优先选择信道增益好的蜂窝链路、对蜂窝链路干扰最小的D2D通信链路，两者复用相同信道。该算法实现简单，D2D链路对蜂窝链路的干扰较小，但由于没有将D2D用户功率与蜂窝用户功率进行优化分配，没有充分提升D2D通信的性能。

MT算法[10]是基于最大化系統吞吐量的资源分配算法，其三大核心步骤分别是：基于距离的接入控制、最大化吞吐量的功率分配以及最大化吞吐量的最优信道分配。该算法并未考虑蜂窝用户的性能损失。MT算法的吞吐量增益定义为引入D2D后带来的最大吞吐量增加，即小区用户复用D2D用户后获得的最大速率之和减去复用之前小区用户获得的最大速率。其公式如下：

（23）

本文的吞吐量增益定义为按最大吞吐量增益进行功率分配所获得的增益：

（24）

为了对比公平，将文献[10]中MT算法的速率增益修改为式（25）：

（25）

其中，即最优功率分配执行后分配给小区用户的在没有干扰时的发射功率。

仿真参数设置如表2所示，参数选取与文献[10]相同。其中多径衰落是服从指数分布，阴影衰落服从对数正态分布。

图3至图6分别比较了三种算法在D2D链路个数为100时，接入率、总速率损失、总吞吐量、总吞吐量增益随D2D最大发射功率变化的关系曲线图。其中，接入率是实际接入的D2D用户个数与计划接入的D2D用户个数的比值。从图3可以看出，Heuristic算法的接入率最差，本文所提算法（MTG算法）的接入率略低于MT算法，这是由于当D2D链路的接入没有带来吞吐量增益时，MTG算法不允许其接入，启发式算法忽略了功率协作带来的接入率增加。随着D2D用户最大发射功率的增大，MT算法和本文算法的接入率保持稳定，而Heuristic算法的接入率随着最大发射功率的增加而下降。从图4可以看出，本文提出的MTG算法具有最小的总速率损失，随着D2D用户最大发射功率的增大，MT算法和Heuristic算法的蜂窝用户损失随之而增加，而MTG算法总能维持较低的总速率损失。

由图5可知，MTG算法的系统总吞吐量高于Heuristic算法但低于MT算法，其原因是MT算法的总吞吐量的增加是建立在总功率增加的前提下。而本文采取的MTG算法大大降低了蜂窝小区的总功耗。从图6可知，MTG算法具有最大的吞吐量增益，这与本文的理论推导一致。从图5和图6可以看出，MT算法和本文算法的吞吐量和吞吐量增益均随着D2D用户最大发射功率的增大而略有增加，而Heuristic算法性能有所下降，这是因为Heuristic算法中没有将D2D用户及蜂窝用户的发射功率进行协作优化分配，故而导致了性能的下降。

综上所述，本文提出的MTG算法可以有效降低蜂窝用户的速率损失和提高D2D用户的性能增益。但作为代价，本文提出的MTG算法复杂度高于Heuristic算法，D2D用户的接入率和系统总吞吐量低于MT算法。

6 结束语

D2D用户与蜂窝用户复用相同时频资源时，会对蜂窝用户带来性能损失。本文引入代表蜂窝用户的速率损失复用代价函数，通过兼顾D2D用户的速率提升与蜂窝用户的速率损失，提出一种最大化吞吐量增益的资源分配算法，在保证D2D链路与蜂窝链路的QoS需求的情况下，获得整体吞吐量增益最大，并且降低了整个小区的功耗，减小蜂窝用户的速率损失。

参考文献：

[1] Asadi A， Wang Q， Mancuso V. A Survey on Device-to-Device Communication in Cellular Networks[J]. Communications Surveys & Tutorials IEEE， 2013，16（4）： 1801-1819.

[2] Du J， Zhu W， Xu J， et al. A Compressed HARQ Feedback for Device-to-Device Multicast Communications[C]//Vehicular Technology Conference， 2012： 1-5.

[3] Golrezaei N， Dimakis A G， Molisch A F. Device-to-device collaboration through distributed storage[C]//Global Communications Conference， 2012： 2397-2402.

[4] Yu S， Ejaz W， Guan L， et al. Resource Allocation Schemes in D2D Communications： Overview， Classification， and Challenges[J]. Wireless Personal Communications， 2017，96（1）： 1-20.

[5] Pratas N K， Popovski P. Low-Rate Machine-Type Communication via Wireless Device-to-Device （D2D） Links[J]. Computer Science， 2013.

[6] Chen B， Zheng J， Zhang Y. A time division scheduling resource allocation algorithm for D2D communication in cellular networks[C]//IEEE International Conference on Communications， 2015： 5429-5434.

[7] Huang J W， Liu X J. Design of resource allocation scheme for D2D based on Kuhn-Munkres optimal matching[J]. Application Research of Computers， 2015.

[8] Chen X， Hu R Q， Qian Y. Distributed resource and power allocation for device-to-device communications underlaying cellular network[C]//Global Communications Conference， 2014： 4947-4952.

[9] Yu C H， Doppler K， Ribeiro C B， et al. Resource Sharing Optimization for Device-to-Device Communication Underlaying Cellular Networks[J]. IEEE Transactions on Wireless Communications， 2011，10（8）： 2752-2763.

[10] Feng D， Lu L， Yi Y W， et al. Device-to-Device Communica-tions Underlaying Cellular Networks[J]. IEEE Transactions on Communications， 2013，61（8）： 3541-3551.

[11] Chen N， Tian H， Wang Z. Resource allocation for intra-cluster D2D communications based on Kuhn-Munkres algorithm[C]//IEEE Vehicular Technology Conference， 2014： 1-5.

[12] Zulhasnine M， Huang C， Srinivasan A. Efficient resource allocation for device-to-device communication underlaying LTE network[C]//IEEE International Conference on Wireless and Mobile Computing， NETWORKING and Communications， 2010： 368-375.