一种基于双层干扰图着色的资源分配算法

张家波，陈美铃，余 攀

(重庆邮电大学移动通信技术重庆市重点实验室，重庆400065)

0 引言

频谱资源稀缺是通信中一直存在的问题。随着移动通信以及由其带动的移动互联网、智能终端等相关产业的快速发展，加上公众对带宽无线业务需求的爆发式增长，导致终端对无线频谱资源的需求量越来越大。频谱复用被作为提高频谱利用率［1－3］的一种常用方法，同时被用来解决当前频谱资源紧张的问题。短距离通信作为长期演进(long term evolution，LTE)系统中一种有效的通信方式，能够复用蜂窝资源进行短距离范围内的直接通信，减轻基站的负载，提高系统吞吐量和频谱利用率［4－7］。例如，在当前LTE系统下的密集活动中，需要进行数据共享的两终端距离较近，称之为短距离终端，并且离基站和其他蜂窝终端较远，短距离终端通过复用蜂窝终端的频谱资源进行短距离通信传输数据实现即时可靠传输数据。当场景中有大量短距离终端要进行数据传输时，由于频谱资源的稀缺，部分终端需要排队等待其他终端释放占用的信道资源后才能继续使用这些信道资源传输数据。然而，小区中的不同终端复用相同的信道资源，会对小区中其他终端产生同频干扰(co－channel interference，CCI)，从而影响用户的通信质量和系统性能［8］。因此，需要合理地进行资源分配来协调同频干扰。

在资源分配算法中采用图论的思想是一种常见的方法，因为图能清晰地反映不同顶点间的相互关系［9－13］。文献［9］提出基于图论中最优匹配为短距离终端和蜂窝终端分配信道资源，虽然提高了系统容量，但该算法复杂度较大。文献［10］提出基于动态图着色的信道资源复用算法，该算法假设宏用户和家庭用户使用正交的信道资源，但是该算法没有考虑到基站和家庭用户的跨层干扰。文献［11］提出基于图着色的认知频谱分配算法，该算法通过将系统带宽划分为多个子信道，再分配给用户，从而最小化带宽需求，但是该方法先给干扰严重的用户分配信道资源，不能最大化系统吞吐量。文献［12］基于干扰图着色对资源进行分配，该算法虽然提高了系统性能，但是没有考虑到信道资源不足时的处理方法。文献［13］基于图着色提出无干扰的二次资源分配算法，提高了上行频谱利用率，但是该算法要求终端能够自行检查干扰并提供干扰信息。此外，目前存在图着色资源分配方法几乎都是基于平面干扰图分析这个问题。然而，平面干扰图不能有效地体现出蜂窝终端和短距离终端在实际网络中的重要程度，同时，干扰图中边的权值仅考虑了终端间的相互干扰，忽略了终端获得信道资源的概率。

针对上述存在的问题，本文主要基于LTE系统下的密集活动，短距离终端复用蜂窝信道资源并且信道资源不能满足所有数据传输需求的场景，提出了一种双层干扰图着色资源分配算法。该算法首先结合排队论和终端服务等级以及终端获得资源概率，建立双层干扰图，然后，对双层干扰图进行分层着色，最后，根据着色结果为链路分配信道资源。仿真结果表明，该算法在保证终端通信质量前提下，能取得更好的平均吞吐量和系统满意度。

1 系统模型

各链路干扰情况如图1所示。使用相同信道资源的终端间会产生同频干扰，影响通信质量。为此，需要对频谱资源进行合理分配来抑制同频干扰。

图1中，在LTE系统小区中密集活动的场景下，R1，R2，R3，R4，R5，T1，T4，T5均是活动中的短距离终端，短距离终端需要共享数据，要进行数据传输的两短距离终端距离较近，但T4和R4离基站和蜂窝终端C1和C2都较远。假设蜂窝终端间使用正交信道资源，短距离通信终端通过时分复用模式复用蜂窝通信终端下行信道资源传输数据。基站(base station，BS)调度器在终端请求信道资源时已确定了通信链路以及收发双方。同时假设，当前可用信道为s，并且最多可以满足n个终端服务请求，前一分配时刻未分配到信道资源的请求终端和当前请求的终端数为m(包括蜂窝终端和短距离终端)。另外，用LC表示蜂窝链路的集合;LS表示所有短距离通信链路的集合;S表示信道资源集合;Ci表示蜂窝终端;Ti表示第i条短距离链路的发送端;Ri表示第i条短距离链路的接收端。

图1 干扰分析模型Fig.1 Interference analysis model

2 图着色资源分配算法

2.1 干扰分析

当终端采用蜂窝通信时，由于蜂窝终端间使用相互正交的信道资源，蜂窝终端受到的干扰仅来自于短距离通信发送终端和信道噪声，Ci在信道k上收到的信号与干扰和噪声比(signal to interference plus noise ratio，SINR)表示为

由于短距离通信终端复用蜂窝通信终端信道资源，短距离通信终端的干扰来自于同信道的蜂窝终端和其他短距离终端以及信道噪声，短距离通信终端Rj在信道k收到的SINR表示为

(1)-(2)式中:P0k表示基站在第k个子信道上的发送功率;PkTj表示第j个短距离发送端在子信道k上的发送功率;G0k，Ci表示基站到蜂窝终端Ci的信道增益;GkTj，Ci表示第j个短距离发送端到蜂窝终端Ci的信道增益;GkTj，Rj表示第j个短距离发送端到第j个短距离接收端的信道增益;η表示均值为0，方差为σ2的高斯白噪声。

任意2个终端i，j的信道增益进一步表示为

(3)式中:PLkij表示在子信道k上终端间的路径损失;τkij表示对应的阴影衰落。

设 (θi，ri)是终端 i的极坐标。i(θi，ri)，j(θj，rj)的位置距离在极坐标下表示为

基站到终端的路损模型表示为

终端到终端的路损模型表示为

(5)-(6)式中，d表示对应基站到终端或终端到终端的距离，单位为km。

2.2 排队模型

在LTE系统下密集活动的小区中，当信道资源不足以满足活动中进行数据传输的短距离终端需要时，部分终端将排队等待另一部分终端释放信道资源后才能进行数据传输，通过引入排队理论可以解决该情况。设小区内音乐会中终端信道资源请求服从参数为λ的泊松分布，信道资源被占用的时间服从参数为 μ的负指数分布。根据排队论中M/M/n/∞ 模型，由状态流图在系统处于平衡时，可根据K氏方程求出相应平稳分布:

(7)式中:pk表示有k个信道资源被占用转变成k+1个被占用的概率;表示系统的负荷水平或强度;，表示系统平均强度;

此时，系统信道资源请求终端必须排队的概率，即爱尔兰C公式，表示为

(10)式中，n'表示获得信道资源服务的终端个数。随着终端逐渐获得信道资源服务，排队的概率一直在变化。

一般地，当一个终端请求时刻越早、期望速率越高、话务量强度越大则分配到资源的优先级越高，分配资源机会就越大。这里引入GoS(grade of service)表征终端获得信道资源的服务等级，GoS越大，分到资源的概率就越大，定义第i个终端的GoS为

(11)式中:ti表示终端i资源请求到达的时刻;vi表示终端i期望得到的服务速率;λi表示终端i资源请求的到达速率;μi表示终端i获得服务的时间。

在当前共m个信道资源请求终端时，终端i得到服务优先级表示为

终端i分配到到资源的概率为

基于上述分析，我们的目标是找到一种资源分配方式，在给定信道资源和满足通信质量(用SINR表征)的前提下，可以最大限度地利用可用频谱资源，同时使链路平均吞吐量最大化，即

(14)式中:s表示信道数;n表示当前分配到信道资源的终端数。

2.3 双层干扰图建立

将小区中当前所有链路以及用户间干扰关系构造成一个双层干扰图G。其中，每条链路抽象为图中的一个顶点，将所有顶点按要求分为2层。所有蜂窝链路抽象成顶点集合V1，位于双层干扰图第1层;所有短距离链路抽象成顶点集合V2，位于双层干扰图第2层，V1和V2一起组成图中所有顶点的集合V，分别为双层干扰图的第1层和第2层的顶点按序从1开始编号。从而可以建立双层干扰图G(V(V1，V2)，E)。其中，E表示顶点间的边的集合，边的建立在后面给出。

在图G中，定义顶点i对顶点j的干扰表示为

(15)式中:PkTi表示第i条链路发送端的发送功率;GkTi.Rj表示第i条链路发送端到第j条链路接收端的路径增益。

为了保证终端通信质量，预设蜂窝终端SINR阈值为γth1;短距离接收终端SINR阈值为γth2，中断概率的门限为εth。蜂窝终端i中断概率定义为

蜂窝终端正常通信的条件为

如果 SINRi≤γth1，则P(SINRi＞ γth1)=0;否则:

(16)-(18)式中，SINRi表示链路i的信干噪比;VIi表示对i产生干扰的顶点集合;Pi表示顶点i(链路i)获得资源服务的概率。

同理，根据(16)(18)式可得到短距离终端的中断概率和正常通信的条件。

干扰图的建立规则如下，这里我们不仅考虑顶点间的干扰情况，还考虑了终端获得信道资源服务的情况如下。

1)从第1层顶点编号最小的顶点i开始，计算SINRi;

2)如果P(SINRi＞γth1)＜εth，则找到顶点i的干扰集合(对顶点i产生干扰的顶点集合)中对i干扰最大的顶点j，建立一条j→i的有向边，边的大小为Iji，同时把j从i的干扰集合中去除;

3)重新计算SINRi，并更新P(SINRi＞γth1)。如果满足(16)式，重复步骤2)，否则执行步骤4);

4)计算下一个顶点i=i+1。再执行步骤2);直到第一层所有的顶点满足P(SINRi＞γth1)≥εth;

5)同理，从第2层编号最小的顶点i'开始，计算SINRi';

6)如果P(SINRi'＞γth2)＜εth，找到顶点i'的干扰集合中对i'干扰最大的顶点j'，建立一条j'→i'的有向边，有向边的大小为Ij'i'，同时把j'从i'的干扰集合中去除;

7)重新计算SINRi'更新P(SINRi'＞γth2)，如果满足中断条件，执行步骤6)，否则执行步骤8);

8)计算i'=i'+1的SINRi'，重复步骤6)，直到第2层所有顶点都满足阈值条件P(SINRi'＞γth2)≥εth。从而建立带权有向双层同频干扰图G’;

9)将带权有向的双层同频干扰图转换为无向双层同频干扰图G。将有向边变为无向边，边的权值为Wij，从而建立带权无向双层同频干扰图G。其中:

由于蜂窝链路间使用的是正交信道资源，那么

由此，建立无向带权双层同频干扰图G。

2.4 图着色分配资源

由于在LTE系统中，蜂窝通信为主要的通信模式，而短距离通信只是一种用于数据传输的辅助通信模式，因此，在基于双层干扰图着色算法进行资源分配时需要优先对蜂窝链路抽象的图的第1层顶点(简称第1层)着色，再对短距离通信链路抽象的图的第2层顶点(简称第2层)着色来保证蜂窝通信用户的通信质量。

2.4.1 第1层顶点着色

在对双层干扰图第1层顶点进行着色时，主要考虑终端的服务优先等级。由(11)式得

(21)式中，Colori表示第i个终端的着色优先级。对于第1层未着色顶点，服务等级越高，越先被着色分配到信道资源。

2.4.2 第2层顶点着色

由于双层干扰图的第1层顶点与第2层顶点的干扰程度比第2层顶点之间干扰程度更大，我们定义第2层顶点i的饱和度为

(22)式需满足:

着色过程中，相邻顶点不能使用相同的颜色，每种颜色代表一个可用信道资源，根据着色结果进行信道资源分配。着色流程如图2所示。

图2 图着色流程Fig.2 Graph coloring process

具体步骤如下。

1)将第2层顶点按饱和度从小到大排序;

2)将所有颜色从1开始编号;

3)根据着色规则，初始化所有未着色顶点的可用颜色列表;

4)判断是否有未着色顶点，若有，执行步骤6);否则检查是否有颜色剩余，若有，执行步骤5)，否则结束;

5)将剩余的颜色按照终端服务优先等级从第1层到第2层逐个分配给各终端，直至颜色用完;

6)计算未着色顶点饱和度，并按从小到大排序;

7)从未着色顶点中选择饱和度最小的顶点i开始着色;

8)首先检查i的颜色列表中是否有可用颜色，若有，执行步骤9)，否则i将排队等候下一时刻着色，同时i=i+1对下一个顶点着色，执行步骤8);

9)着色时选取当前可用颜色中对自己干扰最小的颜色，若干扰相等，着编号最小的颜色，然后执行步骤10);

10)更新未着色顶点的可用颜色列表:找到i的相邻顶点，从它们的可用颜色列表中去掉i使用过的颜色;并将该顶点及相关边从图中去掉，执行步骤6)。

现在进行算法的复杂度分析。当蜂窝链路抽象的顶点数为M1，短距离抽象成的顶点数为M2，采用本文分层着色的复杂度为O(M1+M22)，而基于平面干扰图着色分配资源，并且都按饱和度大小着色的复杂度为O((M1+M2)2)。由此可见，本文采用的算法复杂度更低。

为了更好地评价系统性能，这里我们定义系统满意度Q为

(24)式中:N'表示当前被服务的信道资源请求终端中速率满足终端要求的数量;N表示当前系统中得到信道资源请求的终端总数。

3 仿真分析

为了评估本文提出的信道资源分配算法，这里主要针对LTE系统下行链路，终端在小区中位置服从均匀分布，以LTE系统中密集活动的小区场景为例进行仿真说明，仿真中用户的速率要求由系统随机产生，其余仿真参数设置如表1所示。由于所有终端随机均匀分布在小区中，仿真时通过200次重复取平均值，这样得到的值更接近实际值。同时，我们将以随机资源分配和传统图着色资源分配算法作为参考，对比本文的分配方法，重点考察对系统平均吞吐量和系统满意度方面的影响。

图3显示了当请求信道资源的终端数越少，从饱和度越小的开始着色分配资源，系统的平均吞吐量越高，随着终端数的增加，系统平均吞吐量减小。当终端达到一定数量时，平均吞吐量趋于饱和。但是着色从饱和度最大和最小开始得到的系统平均吞吐量差异并不明显。

表1 仿真参数设置表Tab.1 Simulation parameters set

图4比较了在不同终端数情况下，3种算法的平均吞吐量。3种算法的平均吞吐量随着终端数增加而下降，排队分配的平均吞吐量最高。因为终端请求数越多，受到的干扰越严重，SINR下降，平均吞吐量下降。考虑到随机资源分配和传统图着色资源分配算法未充分考虑终端间干扰限制，SINR较低，平均吞吐量较低;排队信道资源分配不仅考虑了终端间的干扰，还考虑了终端分配到信道资源的概率，满足复用条件则复用信道资源，否则，剩余的终端排队等待下一个分配时刻，这样每个终端都满足SINR条件，平均吞吐量也较同等情况下的其他算法高。

图5是平均吞吐量的累计分布函数(cumulative distribution function，CDF)曲线，图 5 中，随机分配平均吞吐量主要集中在3～9 Mbit/s，约66%，传统的分配方法平均吞吐量集中在3～27 Mbit/s，约67%，排队分配平均吞吐量集中在7～27.5 Mbit/s，约80%。

图6在不同终端数的情况下，比较了3种算法的系统满意度。3种算法的系统满意度随着终端数增加而下降，而排队分配的满意度最高。因为每个信道资源复用的终端数增多，终端间干扰增加，SINR减小，所以，导致获得的实际速率减小。然而，随机分配和传统图着色资源分配算法没有充分考虑终端通信质量要求，从而SINR较小，终端获得速率较小，而排队等候分配法，在信道资源不足时，在满足SINR阈值前提下才进行资源分配，剩下的终端等待下一个分配时刻继续分配，这样带来的干扰相对较小，终端获得的速率相对其他2种方法较高，满足请求速率的终端也相对较多，系统满意度也较高。

图7比较了在不同SINR阈值和终端数情况下双层干扰图着色平均吞吐量。当终端请求数越少，SINR阈值越高时，平均吞吐量越大，随着终端请求数增多，平均吞吐量下降。因为终端请求数越多，复用信道资源的终端数越多，终端受到的干扰越大，SINR越小，平均吞吐量越小。同时，终端是在满足SINR前提下进行信道分配，SINR阈值越大，复用相同信道资源的终端越少，平均吞吐量越大。

图3 从不同饱和度开始着色的平均吞吐量比较Fig.3 Comparison of average throughput with coloring start from different saturations

图4 平均吞吐量比较Fig.4 Comparison of average throughput

图5 平均吞吐量的CDF Fig.5 Cumulative distribution function of average throughput

图6 系统满意度比较Fig.6 Comparison of system satisfaction degree

图7 SINR值和平均吞吐量的关系Fig.7 Relation between SINR value and average throughput

4 总结

本文针对LTE系统下密集活动中短距离复用蜂窝终端资源通信，且信道资源有限的场景，提出了一种基于双层干扰图着色分配资源的算法，该算法根据蜂窝终端和短距离终端间的双层同频干扰关系，考虑信道资源是否充足以及终端获得信道资源服务的优先等级，在满足通信质量前提下，建立双层干扰图，再基于双层干扰图进行分层着色分配信道资源。理论分析表明该算法复杂度降低。仿真结果表明，双层干扰图着色排队分配较随机分配和传统图着色分配对系统平均吞吐量和满意度都有提高。

但本文仅考虑了蜂窝终端间使用正交信道资源，一个蜂窝终端的信道资源被多个D2D终端复用的情况。为了进一步提高频谱资源利用率和系统性能，后续研究可结合D2D模式选择，考虑一个D2D可复用多个蜂窝终端信道资源，同时一个蜂窝信道资源可被多个D2D终端复用的情况。

［1］ZHU D H，WANG J H，SWINDLEHURST A L，et al.Downlink resource reuse for Device－to－Device communications underlaying cellular networks［J］.IEEE Signal Processing Letters，2014，5(21):531－534.

［2］MAHMUD A，HAMDI K A.Hybrid femtocell resource allocation strategy in fractional frequency reuse［C］//IEEE Wireless Communications and Networking Conference(WCNC).Shanghai:IEEE Press，2013:2283－2288.

［3］DONG H L，KAE W C，WHA S J，et al.Resource allocation scheme for device－to－device communication for maximizing sPatial reuse［C］//IEEE Wireless Communications and Networking Conference(WCNC).Shanghai:IEEE Press，2013:112－117.

［4］张祖凡，易印雪.分层异构移动云接入架构研究［J］.重庆邮电大学学报:自然科学版，2013，25(3):285－291.ZHANG Zufan，YI Yinxue.Layered heterogeneous mobile cloud accessarchitecture research［J］.Journalof Chongqing University of Posts and Telecommunications:Natural Science Edition，2013，25(3):285－291.

［5］PHUMCHONGHARN P，HOSSAIN E，KIM D I.Resource allocation for device－to－device communications underlaying LTE－advanced networks［J］.IEEE Wireless Communications，2013，4(20):91－100.

［6］CHEN X H，CHEN L，ZENG M X，et al.Downlink resource allocation for Device－to－Device communication underlaying cellular networks［C］//IEEE 23rdInternational Symposium Personal Indoor and Mobile Radio Communications(PIMRC).Sydney，NSW:IEEE Press，2012:232－237.

［7］LIU Q，JIANG Y X.Adaptive resource allocation and grouping for device－to－device communicateons underlying cellular works［C］//IEEE/CIC International Conference on Communications in China－Workshops(CIC/ICCC).Xi’an:IEEE Press，2013:115－119.

［8］FENG C，CUI H Y，MA M，et al.On statistical properties of co－channel interference in OFDM systems［J］.IEEE Communications Letters，2013:17(12):2328－2331.

［9］ZHANG H L，WANG T Y，SONG L Y，et al.Graph－based resource allocation for D2D communications underlaying cellular networks［C］//IEEE/CIC International Conference on Communications in China－Workshops(CIC/ICCC).Xi’an:IEEE Press，2013:187－192.

［10］SERKAN U，GUNTHER A，BHARUCHA Z.Graph－based dynamic frequency reuse in femtocell networks［C］//IEEE 73rdVehicular Technology Conference(VTC Spring).Yokohama:IEEE Press，2011:1－6.

［11］TAN L，FENG Z Y，JING Z，et al.Graph coloring based spectrum allocation for femtocell downlink interference mitigation［C］//Wireless Communications and Networking Conference(WCNC).Cancun，Quintana Roo:IEEE Press，2011:1248－1252.

［12］ZHANG R Q，CHENG X，YANG L Q，et al.Interferencea ware graph based resource sharing for device－to－device communications underlaying cellular networks［C］//Wireless Communications and Networking Conference(WCNC).Shanghai:IEEE Press，2013:140－145.

［13］DIMITRIS T，EIRINI L，NIKOS P，et al.A graph－coloring secondary resource allocation for D2D communications in LTE networks［C］//IEEE 17thInternational Workshop on Computer Aided Modeling and Design of Communication Links and Networks(CAMAD).Barcelona:IEEE Press，2012:56－60.