改进图着色算法的PCI自动分配方法

刘 为，廖仁波，王 琳

(中国电子科技集团公司第七研究所，广东 广州 510310)

0 引 言

物理小区ID(physical cell ID，PCI)是长期演进(long-term evolution，LTE)系统中终端区分不同小区的无线信号标识，是小区最基本的配置参数。LTE应用的PCI数量为504个，取值范围0-503，分成168组，每组包含3个PCI[1]。现实组网不可避免要对PCI进行复用，可能造成相同PCI由于复用距离过小产生冲突或者混淆[2]。PCI规划的目的就是为每个演进型Node B(evolved node B，eNB)小区分配无冲突、无混淆的PCI。

目前已提出图着色方法应用于LTE PCI分配的方法[3]，但未考虑同频组网时不同小区导频信号之间的干扰控制问题。

本文提出了一种基于改进图着色方法的PCI自动分配方法，既能够保证相邻小区PCI无冲突、无混淆，同时使得同频小区间的导频信号干扰抑制能得到优化。

1 PCI复用和分配原则

小区间复用PCI时应考虑以下情况：

(1)PCI无冲突

两个或以上直接相邻的小区分配相同的PCI，称为PCI冲突，如图1所示。该情况会导致重叠区域中至多只有一个小区会被终端搜索同步，而该小区不一定是最合适的。

图1 PCI冲突

(2)PCI无混淆

小区(ID=B)的两个及以上的相邻小区具有相同的PCI(ID均为A)，称为PCI混淆，如图2所示。此情况下，该小区下的终端请求切换到PCI为m的小区，则小区A无法分辨目标小区，进而导致切换失败。

图2 PCI混淆

(3)同频干扰抑制

LTE系统中，PCI的取值显式地决定了无线传输参考信号(reference signal，RS)的结构[4]。下行方向上，终端与基站间的同步保持依赖于小区的主同步信号(primary synchronous signal，PSS)、辅同步信号(secondary synchronous signal，SSS)和小区参考信号(cell reference signal，CRS)。同频组网时，位于小区边缘的终端可同时接收到多个相邻小区的PSS/SSS同步信号和CRS信号。PCI模三不同时，PSS基于不同的ZC根序列产生，接收端互相关检测性能更好；PCI模六不同时，CRS的频域位置不同，下行同频干扰相对较小[1]。上行方向上，基站依赖终端发送的解调参考信号(demodulation RS，DM-RS)接收数据。LTE系统中，对应PCI模三十不同，定义了30个不同的序列组(sequence groups)用于生成DM-RS，此时DM-RS互相关性能较佳，进而同频小区间上行干扰相对较小[1]。由上述讨论可见，合理分配PCI(即尽量避免模三、模六、模三十相同)可优化同频组网小区间干扰抑制。

此外，PCI分配还需考虑如下原则进行：

(1)共站小区PCI不同；

(2)“邻区”和“邻区的邻区”PCI不同；

(3)同一个站点的多个小区之间尽量保证PCI模三不等，本小区与最近邻区尽量PCI模三不等；

(4)复用PCI的两个小区之间距离尽量远。

2 PCI自动分配设计方案

2.1 总体设计

从全局来看，PCI自优化的所需的信息都在操作维护中心(operation and maintenance center，OMC)，OMC可以全局规划，得出无冲突、无混淆的PCI下发给eNB。eNB只有本地及邻区的信息，负责分布式的PCI冲突和PCI混淆检测。

PCI自动分配方案包括两方面内容：PCI分配和PCI优化。PCI分配指小区初始化阶段从OMC获取有效PCI配置。PCI优化指已有小区在运作过程中对PCI的自我优化过程。其中，PCI优化过程又包括两个阶段：PCI冲突和混淆检测以及PCI重分配。前者是发现问题的过程，执行者为OMC和eNB。后者是解决问题的过程，执行者为OMC。

PCI自动分配方案的总体设计如下：

(1)OMC比eNB更清楚整个网络覆盖的PCI分配，能够从宏观上把握PCI冲突混淆的解决。eNB作为PCI分配的最终执行者，只能从微观的角度判断配置的有效性。因此，eNB只负责PCI冲突混淆的检测，发现冲突或者混淆后上报警报(Alarm)信息给OMC，并不决定如何解决，而OMC负责PCI冲突混淆的解决，在得到Alarm信息之后通过优化算法最终决定PCI更改的方案并且实施。

(2)OMC所采用的PCI优化算法必须保证每次向eNB分配的PCI具有一定的准确性，即PCI配置后发生混淆冲突的几率足够小。

(3)在建立两个eNB之间的逻辑连接(X2连接)的时候，两端的eNB都会进行PCI检测。如果发现冲突或者混淆，两端都上报Alarm给OMC。最终由OMC根据收集到的多个Alarm信息决定PCI更改方案。

2.2 基于图着色的PCI分配设计

基于图着色的PCI分配设计分为3个阶段：网络初始化阶段，网络增长增量分配阶段，以及混淆解决阶段。

(1)网络初始化阶段

在网络初始化阶段，OMC根据已有小区和新加入小区的相关信息，包括地理位置，功率覆盖，邻区关系等因素，进行初始化PCI分配，排除无效PCI，并给出无冲突无混淆的PCI配置，一个小区对应唯一一个PCI配置。

将所有基站映射为图着色节点，每对邻区节点和邻区的邻区节点之间用关系线连接起来。通过使用图着色方法，可保证连接节点之间采用不同的颜色，从而实现PCI合理分配的目的，如图3所示。

图3 图着色PCI分配方法

(2)网络增长增量分配阶段

通过迭代，对小区中每一个PCI节点进行着色，最终使得每对相邻节点采用不用的颜色(即不同PCI ID)。

定义：

一级邻区：当前小区的直接邻区。

二级邻区：当前小区直接邻区的邻区。

三级邻区：当前小区直接邻区的邻区的邻区。

步骤1 检查当前节点的三级邻区PCI集合是否是在一级邻区和二级邻区中未被使用，如果结果非空，从结果中选择PCI集合；如果结果为空，执行下一步；

步骤2 检查在一级邻区和二级邻区中未被使用的PCI集合是否包含在已使用的PCI集合中，如果结果非空，从结果中选择PCI集合；如果结果为空，继续；

步骤3 如果可用的PCI集合和已使用的PCI集合相同，全网重新规划；否则，从可用的PCI集合中(但不在已使用的PCI集合中)选择最小的PCI作为当前节点的PCI。

(3)混淆解决阶段

步骤1 为当前节点的一级邻区中使用相同PCI建立一个列表；

步骤2 将列表中的节点降序排列；

步骤3 从列表中移除最上面的节点；

步骤4 更改列表中剩余节点的PCI。

2.3 PCI冲突和混淆检测流程设计

PCI冲突检测流程设计如图4所示。PCI混淆检测流程设计如图5所示。

图4 PCI冲突检测流程

(1)建立X2连接的两端eNB都检查PCI冲突混淆，发现冲突混淆后上报PCI冲突混淆警报信息给OMC，包括冲突混淆双方的相关信息，时间和触发冲突混淆检测的原因。

(2)OMC在得到PCI冲突混淆警报信息之后，触发对指定eNB进行PCI更改操作。OMC通过邻区关系拓扑，采用改进图着色方法取得合适的PCI，并检测PCI的修改是否会导致现有eNB网络存在PCI冲突混淆。如无冲突混淆，OMC下发指令通知eNB更新小区PCI的配置。否则，重新生成有效PCI。

(3)eNB收到配置指令之后，检查需要更新的PCI是否存在冲突混淆的情况。一般情况下，OMC和eNB邻区关系信息一致，不存在OMC认为某个PCI没有冲突混淆，但eNB检测到冲突混淆的情况。这里eNB进行检测只是进行再次确认而已。

(4)如无冲突混淆，eNB向所有邻区eNB发送X2配置更新消息，更新本小区信息。否则上报PCI冲突混淆警报信息给OMC。

(5)eNB修改PCI配置并通知OMC更新成功。OMC给出解决前后的网络性能变化及解决过程中所造成的用户掉话统计，以及从发现冲突混淆到解决所花费的时间。

2.4 PCI分配设计的进一步改进

对PCI分配方法进行改进，尽量从未使用PCI集合中提取，目的在于使得复用PCI的小区尽可能远离。在分配PCI的时候，优先考虑同一基站(Intra-eNB)下的小区，首先检查可否分配模三不同PCI，其次考虑模六不同PCI，最

图5 PCI混淆检测流程

后考虑模三十不同PCI。对于不同基站(Inter-eNB)的相邻小区，若已经有6个以上邻区采用不同的PCI模六值，则随机选择模六相同的PCI值。中心点的获取是根据待分配PCI队列来选择首位节点。具体流程如图6所示。

其中：

未着色队列：网络中需要进行PCI配置的节点集合。

待着色队列：与当前节点有关联的节点集合。每个节点着色之后，将其所有未着色邻区放入该队列中。

3 仿真实验

本文根据基于改进图着色方法的LTE小区PCI自动分配设计方案进行了仿真实验。假定同一基站站点部署3个小区，仿真将其抽象为3个相邻的圆，按照地理位置和覆盖范围粗略估计邻区关系。结果如下：

(1)根据物理位置和覆盖范围，将基站映射为待着色节点。

(2)根据“邻区”和“邻区的邻区”关系，初始化分配PCI，如图7所示。使用图着色方法，使得每对相邻节点采用不用的颜色作为PCI标识。

(3)对于新加入小区节点引起的PCI混淆，进行自动修复，如图8所示。新小区节点加入后，两个相同PCI的邻区被重新进行分配，解决了PCI混淆问题。

(4)采用改进PCI分配方法，避免模三相同，如图9所示。避免模六相同，如图10所示。该仿真暂未实现邻区PCI模三十不同。

4 结束语

本文设计的基于改进图着色方法的LTE小区PCI自动

图6 改进PCI分配设计流程

图7 PCI初始分配

图8 新加入小区

图10 PCI分配图(模六不同)

分配方案，实现了多小区PCI无冲突、无混淆分配，并支持PCI冲突和混淆的接入网分布式检测以及集中式的重分配处理。该方案的创新性在于同时考虑到PCI取值直接关联到物理层主辅同步信号和小区参考信号的生成与频域位置复用，因此可通过控制模N不同PCI的选取，使得小区间上下行导频信号的同频干扰下降。结合初始和新加入小区分配PCI的用例，仿真实例显示算法实用有效。下一步工作将增强PCI分配算法以支持PCI模三十不同和异构小区组网。

[1]Stefania Sesia,Issam Toufik,Matthew Baker.LTE-The UMTS long term evolution:From theory to practice[M].2nd ed.Chichester,UK:John Wiley & Sons,2011.

[2]3rd Generation Partnership Project.3GPP TS 36.300 technical specification group radio access network;evolved universal terrestrial radio access(E-UTRA) and evolved universal terrestrial radio access network (E-UTRAN);overall description;Stage 2[S].France:3rd Generation Partnership Project,2016:234-237.

[3]Bandh T,Carle G,Sanneck H.Graph coloring based physical-Cell-ID assignment for LTE networks[C]//ACM Internatio-nal Conference on Wireless Communications and Mobile Computing,2009:116-120.

[4]3rd Generation Partnership Project.3GPP TS 36.211 technical specification group radio access network;evolved universal terrestrial radio access (E-UTRA);physical channels and modulation[S].France:3rd Generation Partnership Project,2016:105-130.

[5]Hasan MR,Kawser MT,Islam MR.An automatic GSM neighbor cell list update procedure enhancing SON in LTE[C]//International Conference on Electrical & Computer Engineering,2010:143-146.

[6]LI Qing.Research of TD-LTE PCI planning[J].Radio Communications Technology,2013,39(5):66-68(in Chinese).[李青.TD-LTE系统PCI规划方法研究[J].综合电子信息技术,2013,39(5):66-68.]

[7]Lukasz Chrost,Krzysztof Grochla.Conservative graph coloring:A robust method for automatic PCI assignment in LTE[J].Communications in Computer and Information Science,2013,370:268-276.

[8]Saqib Nawaz M,Fayyaz Awan M.Graph coloring algorithm using adjacency matrices[J].International Journal of Scientific & Engineering Research,2013,4(4):1840-1842.

[9]Basit Shahab M,Abdul Aziz Bhatti.Neural networks based physical cell identity assignment for self organized 3GPP long term evolution[J].International Journal of Advances in Telecommunications,Electrotechnics,Signals and Systems,2013,2(3):104-110.

[10]Labeeb Mohsin Abdullah,Mohd Dani Baba,Sinan Ghassan Abid Ali.Self-configuration concept to solve physical cell ID conflict for SON LTE-based femtocell environment[J].International Journal on Recent Trends in Engineering & Technology,2014,10(2):165-171.

[11]Acedo-Hernandez R,Toril M,Luna-Ramírez S,et al.Analysis of the impact of PCI planning on downlink throughput performance in LTE[J].Computer Networks,2015,76:42-54.

[12]Kreitmair F.Self-configuration in LTE self organizing networks[J].Network,2013,145:145-150.

[13]Furqan Ahmed,Junquan Deng,Olav Tirkkonen.Self-orga-nizing networks for 5G:Directional cell search in MMW networks[C]//IEEE 27th Annual International Symposium on Personal Indoor and Mobile Radio Communications,2016:1-5.

[14]Mhiri F,Sethom K,Bouallegue R.A survey on interference management techniques in femtocell self organizing networks[J].Journal of Network and Computer Applications,2012,36(1):58-65.

[15]Abdullah LM,Baba MD,Ali SGA.Self-configuration concept to solve physical cell ID conflict for SON LTE-based femtocell environment[J].International Journal on Recent Trends in Engineering & Technology,2014,10(2):165.