基于超图的D2D多对多资源分配方案

刘 辉，颜 飙+，陈永丽

(1.重庆邮电大学 通信新技术应用研究中心，重庆 400065；2.重庆信科设计有限公司，重庆 400012)

0 引 言

D2D通信作为解决传统蜂窝网络中短距离通信问题的有效途径，越来越受到人们的关注[1]，目前已被列为第五代移动通信(5-generation，5G)的关键技术之一[2]。D2D用户在复用模式下与蜂窝用户共享相同的频谱资源，频谱资源的利用率得到较大提升，但也带来了严重的干扰问题，因此干扰管理问题变得尤为重要[3,4]。文献[5,6]应用拍卖算法分配频谱资源，有效缓解了用户间的干扰问题。文献[7]提出一种以容量为导向的资源分配机制，以此来降低蜂窝用户所受干扰。文献[8]提出一种联合功率与频谱资源分配方式，在保证低计算复杂度的同时，得到一个次优解。文献[9]中，系统被映射为一个加权二分图，同时将资源分配问题转化为最大容量匹配问题。文献[10]提出一种基于QoS的分簇信道分配方法，根据信道状况将用户分簇后再分配频谱资源。但上述文献未能反映多个用户复用相同频谱资源时的累加干扰问题。文献[11]提出一种基于二部超图的资源分配方式，以较低的复杂度实现较高的系统总速率。文献[12]提出基于超图理论的信道分配方案，利用超图着色来对D2D用户间的累加干扰建模，但文献[11,12]中一个D2D用户只能复用一个蜂窝用户的频谱资源，当系统中的可用频谱资源较多时，无法充分利用剩余频谱资源。

本文提出一种基于超图的多对多资源分配算法，在考虑累加干扰的同时，允许一个D2D用户复用多个蜂窝用户的频谱资源，并且一个蜂窝用户的频谱资源可以共享给多个D2D用户，以此来提升系统频谱资源的利用率并提高系统吞吐量。

1 系统模型

1.1 场景描述

图1 系统模型

1.2 数学模型

包含D2D用户的蜂窝系统中存在多种干扰，包括D2D发射端对基站的干扰，蜂窝用户对复用相同频谱资源的D2D接收端的干扰以及复用相同频谱资源的D2D用户之间的干扰。令AN×M=[αij]为蜂窝用户与D2D用户的匹配矩阵，当αij=1时，表示D2D用户Dj复用蜂窝用户Ci的频谱资源，当αij=0时，则意味着D2D用户Dj没有复用蜂窝用户Ci的频谱资源。因此本文最终的优化目标就是找到一个最优的匹配矩阵，使得系统中的蜂窝用户及D2D用户在满足给定条件的情况下，尽可能提高系统的总吞吐量，即

(1)

(2)

其中，SINR(signal to interference plus noise ratio)为用户的信干噪比，B0为单个资源块的带宽。如式(2)所示条件，本文并不限制D2D用户所能复用频谱资源的数量，而D2D作为传统蜂窝系统的补充，只有在蜂窝用户的信干噪比大于最小信干噪比阈值时，才能将该用户的频谱资源分配给D2D用户。同时，为了保证被分配频谱资源的D2D用户能有较好的通信质量，需要保证D2D用户的信干噪比大于其所需最小信干噪比，即

(3)

(4)

2 基于超图的多对多资源分配

在基于传统的图的方法中，一条边连接两个顶点的方式无法充分反映系统中的干扰情况，因为复用相同频谱资源的用户间会产生累加干扰，多个较弱的干扰累加在一起可能会严重影响链路的质量。而在超图中，一条超边可以包含多个顶点，更方便对系统中的干扰建模。

2.1 超图简介

相对于传统的图，超图是一种广义上的图，在超图中，一条边可以包含任意多个顶点，而不再限于传统图中的两个顶点。

定义V={v1,v2,…,vn}为一个有限的集合，E={e1,e2,…,eλ}中的元素e均为集合V的一个子集，并且满足下列约束条件

生物丁醇，作为新一代的生物燃料，比乙醇热值高、挥发性低，备受关注。早在许多年前，就有人预测利用菊芋生产丁醇，而目前此研究也有了进展。Sarchami T等人[47]优化了菊芋中菊糖的酶法水解工艺并使菊糖转换率最大达到94.5%，该研究利用分布发酵法，生产丁醇的产率达到了9.6 g/L。陈丽杰等人[48]利用丙酮丁醇梭菌（Clostridium acetobutylicum）L7发酵菊芋水解液生产丁醇，结果显示丁醇产量达到11.2 g/L，发酵液中丁醇、丙酮和乙醇的比例为0.64∶0.29∶0.05。

(5)

则称二元关系H=(V,E)为一个超图，V={v1,v2,…,vn}为超图的顶点，E={e1,e2,…,eλ}为超图的超边，如图2所示。在超图H中，如果一条超边e中存在两个顶点vi，vj，则称这两个顶点相邻，并称超边e与顶点vi或vj相关联。用e表示与超边e相关联的顶点数量。如果一个顶点与多条超边相关联，则称其为超边的端点，否则，称其为超边的内点，如图2中，v2，v3，v5为超边e2的端点，v4为超边e2的内点。

图2 超图模型

2.2 构建超图

在应用超图方式进行信道资源分配之前，首先要根据系统中的干扰情况构建超图。超图的构建分成两个步骤：

步骤1 首先根据系统中终端用户对距离，将一定范围内的用户构建超边，而为了防止系统中超边数量过多，不能够遍历所有用户并检查其周围一定范围内的用户。因此本文设计了一种超边构建的规则，即：

(1)依次遍历系统中的蜂窝用户，将以其为中心，δ为半径的范围内的用户相关联，构建为超边。

(2)遍历系统中的D2D用户，如果该用户未被包含入已构建的超边中，则将以其为中心，δ为半径内的终端用户相关联，构建为超边。

步骤2 检查系统中不在同一超边内，而又不满足式(3)和式(4)所给定的信干噪比条件的用户构建一对一的边。

由于超边是以某个用户为中心，关联一定范围内的用户进行构建的，因此定义中心用户为其所在超边的基准顶点。

2.3 多对多资源分配算法

由于频谱资源的分配是一个NP难问题，很难确定一个最优解，因此在将干扰图构建完毕后，本文将通过图论中图着色的方式，根据贪心算法，为超图进行着色。如传统图着色算法一样，图的顶点代表系统中的用户，要着的颜色则为系统中的频谱资源。

(6)

一个超边相关联的顶点数量越多，表明这一范围内的用户密度越大，因此如果有复用相同资源的用户的话，之间的干扰也会更复杂更强烈。在本文所提算法中，首先选择一条相关联顶点最多的超边，然后选择一定数量的可用资源，分配给超边内的用户。该算法的详细过程见表1。

表1 基于超图的多对多资源分配算法

与文献[12]中基于超图的资源分配方案相比，本文所提算法在构建超图时是根据距离来建立超边的，而在文献[12]所提算法中，是选取固定的Q个用户，然后计算信干噪比，以此来决定是否加入超边，但如果在用户密度较大的情况下，多于Q个用户距离较近时，可能会使距离较近用户复用相同频谱资源。此外，本文允许蜂窝用户所占频谱资源与D2D用户间进行多对多的复用，在保证蜂窝用户服务质量的同时，最大化利用系统中的频谱资源，提高系统吞吐量。

3 仿真分析

3.1 仿真参数

为了验证本文所提资源分配算法的性能，针对系统总吞吐量与用户吞吐率累积分布基于MATLAB平台进行仿真分析，仿真中的主要参数见表2。

表2 仿真参数

3.2 仿真结果

本文选取了两种资源分配方式与本文所提算法来进行比较，分别为传统的图着色多对多资源分配算法和文献[12]中所提的基于超图的资源分配算法，同时本文算法对δ=70和δ=100两种情况进行对比。在传统图着色方式的多对多资源分配中，对复用相同频谱资源的D2D用户间的累加干扰考虑欠缺，虽然能让一个用户获得更多的频谱资源，但在每个资源上的干扰也较大。而文献[12]中基于超图的资源分配方案在超边构建过程中，以固定用户数量来计算干扰，并没有考虑用户密度较大的情况，同时在该算法中，只允许一个D2D用户复用一个蜂窝用户的频谱资源，因此，系统中总的吞吐量相较于前两种算法会偏低。

图3描述了D2D用户数量为100时，不同资源分配方案的系统吞吐量在不同蜂窝用户数量下的变化曲线。通过比较可以发现，本文所提算法与使用传统图着色算法的多对多资源分配，相比于文献[12]所提基于超图的一对多资源分配算法，系统总的吞吐量都有显著提升。在蜂窝用户数量较少时，本文所提算法在δ=100的条件下，系统吞吐量相比传统图着色算法是略高的，而随着蜂窝用户数量的增多，由于要在所有蜂窝用户范围内构件超边，对D2D用户资源分配的限制较高，系统总吞吐量渐渐低于传统图着色算法。

图3 不同蜂窝用户数量下的系统吞吐量(N=100)

图4描述了蜂窝用户数量为10时，不同算法的系统吞吐量在不同D2D用户数量下的变化曲线。从图中可以看出，由于本文所提算法与传统图着色算法允许一个D2D用户复用多个蜂窝用户的频谱资源，相比文献[12]所提算法系统总的吞吐量都有大幅度的提升。在D2D用户数量较小时，本文所提算法在δ=70与δ=100的情况下吞吐量相差很小，而随着D2D用户数量的增加，两种情况的差距逐渐增大，但是都高于传统图着色方式的资源分配，因为在可用频谱资源较少时，传统图着色分配方式用户间对频谱的争抢较严重，虽然每个用户可能占用更多资源，但频谱间的干扰却更严重。

图4 不同D2D用户数量下的系统吞吐量(M=10)

图5描述了不同算法在蜂窝用户为10，D2D用户数量为50，带宽为1 Hz条件下D2D用户吞吐率的累积分布函数(cumulative distribution function，CDF)曲线。由于本文算法与传统图着色算法允许一个D2D用户占用多个蜂窝用户的频谱，因此图中所表现出的吞吐率是在某些D2D用户占用了多个带宽为1 Hz的频谱资源情况下得出的。从图中可以看出，文献[12]所提算法由于一个用户只占用一个蜂窝用户的频谱资源，因此用户的吞吐率大多集中在5-15 bit/s之间，相比其它算法要低。本文所提算法与传统图着色算法D2D的吞吐率都集中在10-25 bit/s，相比于传统图着色算法，本文所提算法吞吐率分布更为均衡。

图5 D2D用户吞吐率的CDF(M=10，N=50)

图6描述了不同算法在蜂窝用户数量为30，D2D用户数量为50，带宽为1 Hz时蜂窝用户吞吐率的CDF曲线。从图中可以看出，由于本文所提算法在δ=100时可复用相同频谱资源的用户较少，对蜂窝用户造成的累加干扰相对较小，因此比δ=70时蜂窝用户的吞吐率更高，但都优于传统图着色算法。而文献[12]所提算法由于一个蜂窝用户的频谱资源只分配给一个D2D用户，对蜂窝用户的干扰最小，因此相比其它算法，蜂窝用户的服务质量更好。

图6 蜂窝用户吞吐率的CDF(M=30，N=50)

4 结束语

为了使蜂窝系统能容纳更多的D2D用户，同时尽可能利用系统中的频谱资源，本文提出一种基于超图的资源分配方案，允许一个蜂窝用户的频谱资源分配给多个D2D用户，同时，一个D2D用户可以占用多个蜂窝用户的频谱资源。为了应对系统中复杂的干扰，本文在构建超图时，优先对所有蜂窝用户建立超边，以此来保证可复用资源的频谱质量，其次应用两阶段资源分配方式，减少D2D用户间的累积干扰，并提升频谱资源利用率。仿真结果表明，相比传统的一对多资源分配方案，本文所提方案能够在保证蜂窝用户服务质量的同时，提高系统总的吞吐量。本文所假设场景是在单小区下，并没有考虑多小区情况下的系统干扰，因此还可在此基础上做进一步研究。