超密集网络中小小区分簇和子载波分配算法

黄俊伟1，2，周朋光1，张仁迟1，滕得阳1，徐  浩1

(1.重庆邮电大学 通信与信息工程学院，重庆400065；2.重庆邮电大学 新一代宽带移动通信重点实验室，重庆400065)


    摘  要： 超密集网络中，严重的小区间干扰制约了终端用户尤其是边缘用户的数据速率。有效地对干扰进行管理、提升边缘用户的数据速率是超密集网络中的研究难点。在超密集网络架构的基础上，提出一种基于图论的不完全染色算法，对网络架构中的基站划分簇，同簇内的不同基站共享频带资源。同时，提出一种子载波分配算法，优先为边缘用户分配信道增益较优的子载波。通过仿真表明，不完全染色算法能够有效地减小小区间干扰，提升系统吞吐量，子载波分配算法在不影响系统吞吐量的基础上能够优化边缘用户的吞吐量。

    关键词： 超密集网络；干扰协调；分簇；子载波分配

    中图分类号： TN929.5

    文献标识码： A

    DOI：10.16157/j.issn.0258-7998.2017.07.027


    中文引用格式： 黄俊伟，周朋光，张仁迟，等. 超密集网络中小小区分簇和子载波分配算法[J].电子技术应用，2017，43(7)：104-109.

    英文引用格式： Huang Junwei，Zhou Pengguang，Zhang Renchi，et al. Small cell clustering and subcarrier allocation algorithm in ultra dense network[J].Application of Electronic Technique，2017，43(7)：104-109.

0 引言

    第五代通信系统（5G）面向2020年商用的新一代通信系统，为了实现5G网络要达到数据流量密度提升一千倍和设备数量增加十到一百倍的目标，最有效的实现方法之一就是超密集网络技术[1-2]。在密集基站的网络部署下，将会导致严重的小区间干扰，虽然基站与终端的路径损耗有所降低，但在提升有益信号的同时也增大了干扰信号。因此超密集网络中对于管理小区间干扰的问题就俞显重要[3]。

    现阶段国内外学者对超密集网络中干扰协调、小区间干扰等问题进行了研究探索[4-12]。文献[4]中提出基于图论中极大独立集的资源分配方法，通过调整频率重用因子来均衡平均用户与边缘用户之间的数据率。文献[5]提出一种超密集网络中基于分簇的分布式节能资源分配方案，该方案能够有效地改善系统的吞吐量和能效。文献[6]提出了一种利用选举簇头节点对簇中节点进行子信道和功率分配算法。文献[7]提出一种小区干扰协调和分簇相结合的算法，通过为基站动态分配最佳的功率来减少干扰，使得系统的网络吞吐量最大化。文献[8]基于博弈论对能量效率进行研究，提出一种小蜂窝网的功率频谱分配算法。文献[9]中以基站随机部署为前提，分析了基于随机干扰协调的系统平均用户数据速率。文献[10]以发射功率最小为目的，设计了一种分布式功率频谱分配算法，算法考虑了用户的最低吞吐量。文献[11]提出一种基于染色分簇的资源分配(Graph-based Clustering Resource Allocation，GCRA)方案，该方案是基于完全染色算法将所有的基站划分入相互独立的簇中，然后再通过为不同的簇分配相互正交的频带资源来解决干扰的问题。文献[12]提出一种最差子载波避免（Worst Subcarrier Avoiding，WSA）算法，目的是防止给终端用户分配了信道增益较差的子载波并且同时提升系统容量，但是该算法并没有考虑用户的公平性问题。

    本文在超密集网络架构的基础上提出一种基于图论的不完全染色分簇算法，该设计思想是将某一范围内的小区进行不完全染色操作，有网络通信的小区染彩色，即参与分簇和分配频带资源，无网络通信的小区不染色，即不参与分簇和不分配频带资源。另外本文考虑边缘用户受干扰较强、数据速率低的问题，设计出一种边缘用户频带资源分配结构，既减小了小区间的干扰，又能够提升频带的利用率，并在此基础上提出一种子载波分配算法，该算法的设计思想主要是在保证系统总体的吞吐量的情况下，优先为边缘用户分配信道增益较好的子载波。

1 系统模型

    本文主要考虑超密集网络架构，如图1所示，系统中由N个基站、X个终端构成超密集网络。为了减小小区间干扰，本文秉承优化网络性能的宗旨，首先提出一种基于图论的不完全染色分簇算法，在同一个簇内的不同基站可以共同使用相同的频谱资源。

tx3-t1.gif

tx3-gs1.gif

    所以，终端用户x在基站n的信道链路上的传输速率为：

    tx3-gs2.gif

2 基于不完全染色的分簇算法

    分簇的目的是为了有效地解决小区之间的干扰问题，在分簇结束后，被分到同一个簇中的基站可以作为一个共同体对待，复用相同的频谱资源。不完全染色分簇算法是以图论为基础的频带资源分配方案，该算法有以下两个步骤：(1)根据小区间的干扰信息形成干扰网络拓扑，该拓扑表示的是各个基站之间的干扰关系；(2)根据成型的干扰网络拓扑，依据不完全染色算法将基站进行分簇操作，将基站分成一定数量的簇，簇中的用户可以复用相同的频带资源。

2.1 形成网络拓扑

    假设有如图2的基站部署结构，基站与用户终端的实线连接表示正常的通信链路，而虚线代表基站对用户终端的干扰，则图2可以直观地简化为图3所示。

tx3-t2+t3.gif

    建立一个无向图G：G=(V，ε)，其中V={1，2，…，V}表示干扰拓扑图的各个顶点的集合，具体的组成是一定范围内所有的小区；ε表示干扰拓扑图的边集，代表不同的小区之间的干扰关系，由于不同的小区之间难免会存在干扰问题，所以相互干扰的小区不能使用相同的频带资源。

2.2 不完全染色算法

    基于图论的不完全染色算法首先是对小区进行编号处理，定义顶点V={1，2，…，v}，定义集合Cv为顶点V的可用颜色（彩色）集。Cv中不包含白色，白色为特殊颜色，代表不参与分簇和不分配频带资源，其余不同的颜色代表分簇和资源分配的存在差异。

    算法一：不完全染色算法

tx3-sf1-x1.gif

tx3-gs3.gif

    取图3基站结构部署简化图的基站1、2、3、4进行分析，如图4(a)的GCRA算法染色情况，为避免小区间干扰，所需颜色集为{红色，蓝色，紫色}，而图4(b)中不完全染色算法会根据小区随机暂停的情况进行染色操作，所需颜色集仅为{红色，蓝色}，由式(3)计算可知，GCRA算法的平均颜色复用率Average_v=4/3，不完全染色算法的平均颜色复用率Average_v=3/2。

tx3-t4.gif

2.3 分簇

    现假设图3中基站 4、5无数据传输，利用算法一(取其中一种情况)与GCRA算法进行染色分簇，如图5。

tx3-t5.gif

    首先按照GCRA算法进行染色操作，从基站1～基站7依次选择与邻边基站不相同的颜色进行染色操作，如图5(a)可以发现基站1、5、6同染蓝色，分为同一簇，基站2、3、7同染红色，划分到同一簇，剩下4单独一个簇，即簇1={1，5，6}，簇2={2，3，7}，簇3={4}。下面按照算法一进行染色操作，取其中一种染色情况如图5(b)所示，可以分簇为：簇1={1，6，7}，簇2={2，3}。

3 子载波分配算法

3.1 用户划分

    根据网络的干扰拓扑以及系统状态选择一个阈值Si，根据各用户反馈的Sj来判断用户属于的类型。当Si≤Sj时，可判断用户为中心用户Uc，若Si≥Sj时，可判断用户为边缘用户Ue，划分后如图6(a)，如此划分中心用户(中心空白处)和边缘用户(边缘阴影处)，然后分配频带资源时，显然在小区交界处很容易造成对边缘用户的干扰，但如果为每个小区的边缘用户都分配不同的正交频带资源，虽然会降低干扰，但是会造成大量的频带资源的浪费。为此，本文设计出一种边缘用户频带资源的分配方法，如图6(b)所示，将每个边缘区域沿对角分开，即分配给边缘区域的频带资源被划分为2个部分，使得相邻的边缘区域使用相互正交的频带的资源，这样有效地防止了对边缘用户造成干扰问题。

tx3-t6.gif

    图6中的频带资源分配方案是将分配给小区的频带资源划分为三部分，其中边缘区域的两部分使用功率较高的主子载波，中心区域使用功率较低的主子载波。图6(a)中对应的子载波的分配如图7(a)，经过不完全染色分簇和中心与边缘区域的划分之后，图6(b)子载波的分配如图7(b)。分析可知，由于采用了不完全染色算法，同一簇内的1，6，7能够用r1，6，7作为其对应的主子载波，另外2，3能够使用r2，3作为其对应的主子载波；另外采用了边缘与中心区域划分方案，使得边缘区域分别使用ra和rb即可，不需要每个边缘区域都分配正交的频带资源，能够节省了系统的频带资源，有助于提升系统的整体吞吐量。

tx3-t7.gif

3.2 子载波分配算法

    假设可分配资源的小区内每个终端用户只能分配到一个子载波，而且每个终端用户都能估计出信道状态信息[12]，定义：(1)M={1，2…m}为子载波个数的集合，m为不同子载波的序列号；(2)p(0<p<1)为边缘用户所占总用户数量的百分比；(3)信道的增益矩阵为H；(4)U={1，2…u}为终端用户的序列号。

    算法二：子载波分配算法

    (1)重新规划信道的增益矩阵H，tx3-sf2-x1.gif为H中第m列的最大值，并且按照每列的最大值tx3-sf2-x1.gif从小到大(若最大值相同，则比较次大值，依此类推)的顺序排列。为了能够保证边缘用户能够选择较好信道增益的子载波，重新调整的H=[H1，H2，H3…Hm]，其中H1、H2、H3等表示增益矩阵H中不同的列向量。

    (2)从增益矩阵H中从后面开始取fix(pM)列，重新组成新的矩阵H′，用于边缘用户的信道增益矩阵，剩下的m-fix(pM)列组成中心用户的信道增益矩阵H″。

    (3)首先给边缘用户分配子载波，即从m列开始依次向前，找出每一列的最大值所对应的终端用户u，为其分配该子载波，再从m-1列中找最大值对应的终端用户，若此时最大值对应的用户也为u，则选择m-1列中次大值对应的终端用户进行子载波分配。直到分配到H′的第一列结束。其次为中心用户分配子载波，此时应从信道增益矩阵H″的最后一列开始分配，分配方法同边缘用户。

    以为边缘用户分配子载波为例：假设信道增益矩阵H为：

    tx3-gs4.gif

tx3-gs5.gif

4 仿真结果与分析

    将本文提出的不完全染色算法和文献[11]中的GCRA算法，以及子载波算法和文献[12]中的WSA算法进行仿真对比，论证本文的算法是否行之有效。具体仿真参数如表1。

tx3-b1.gif

    如图8所示，随着基站数量不断增多，系统的平均吞吐量也随之增大。但在基站数目达到40左右时，系统的吞吐量却趋于平缓，这是由于基站密度的增加，导致系统有限的频带资源无法满足需求，同时对用户间的干扰也会相应的增大。在基站数目为20～40时，本文的不完全染色算法中系统平均吞吐量增长显著，这是因为系统中可能存在的空闲基站染白色，即接收未分配频带资源，使得系统的频带利用率得以提升，同时也保证了系统平均吞吐量的质量。通过比较可以看出，不完全染色算法由于通过为空闲基站染白色的方案，能够为其他基站提供更多频带资源选择的机会，在平均吞吐量方面也有较好的效果。

tx3-t8.gif

    如图9所示，随着基站密度的不断增加，终端用户的掉线率也随之呈现上升的趋势。图9中对比GCRA算法和本文的不完全染色算法可以发现，当基站密度较低时，系统中终端用户也比较少，所以此时的系统频带资源充沛，二者的掉线率都处于较低的范围。但是当增加基站数量和基站的分布密度时，由于系统内的频带资源相对有限和各小区之间干扰的不断加大，使得二者的掉线率上涨幅度较大。由图8可以得出，GCRA算法在基站密度较低时，其终端用户的掉线率比较有优势，但是在密度较高时，本文的不完全染色算法可以提高系统的频带利用率，掉线率明显低于GCRA算法。

tx3-t9.gif

    随着子载波数量的不断增多，本文的子载波分配算法和WSA算法对边缘用户和系统平均吞吐量的对比结果如图10。在图10中，显然可以看到本文算法和WSA算法在不同的子载波数目的情况下，边缘用户的吞吐量提升明显。分析可知，在分配子载波时，本文算法优先保证了边缘用户对信道增益较高的子载波进行选择，秉承对边缘用户优先考虑的原则，使得边缘用户的吞吐量能够得以提升。

tx3-t10.gif

    图11中，本文算法和WSA算法下系统总吞吐量十分接近，没有明显的区别。分析可知，由于在照顾边缘用户的子载波选择中，忽略了对部分中心用户的考虑，牺牲了部分中心用户的平均吞吐量，从而导致本文算法下系统的平均吞吐量并不是特别突出。

tx3-t11.gif

5 总结

    本文在超密集网络的环境下，提出一种基于不完全染色的分簇算法，根据所染颜色类型的不同，将基站进行分簇操作，同一簇内的基站共享频带资源。另外本文设计一种边缘用户和中心用户的区分方案，并在此基础上提出一种子载波分配算法，优先考虑给边缘用户提供信道增益较好的子载波。经仿真实验结果显示，不完全染色算法能够有效地分配频带资源，减小干扰，对系统平均吞吐量提升较为显著，子载波分配算法对提升边缘用户的吞吐量作用明显。

谢谢楼主分享

超密集网络中小小区分簇和子载波分配算法

超密集网络中小小区分簇和子载波分配算法

~~~~~~~~~~~~~~~

超密集网络中小小区分簇和子载波分配算法