分层组网场景下小基站ID分配算法研究

魏垚，韩斌

（1.中国电信股份有限公司广州研究院，广东 广州 510630；2.中国电信股份有限公司技术创新中心，北京 100031）

1 引言

分层异构组网技术是后4G时代用于增强网络容量的重要手段。在LTE-B、LTE-C版本增强了组网技术的研究，其容量增益预测将远高于其他关键技术[1]。如图1所示，小型化网络节点将分层部署，六扇区裂变、HEW（High Efficiency WLAN）、C-RAN等新型无线接入和组网技术重叠覆盖以增强室内容量。然而，LTE系统中小区ID资源有限，过于密集的小基站组网对小区ID的规划分配是新的挑战。

图1 分层异构组网场景示意图

LTE系统中采用物理小区标识（PCI，Physical Cell Identity）区分小区[2]。与传统的蜂窝无线通信系统不同，LTE系统不再采用小区半径和基站距离来规划ID，而使用邻区关系作为判决单位：互为邻区的两个小区避免使用相同ID；一个小区避免同时与两个相同ID的小区互为邻区，即所谓的“冲突”和“混淆”[3]。在超密集的组网场景中，冲突和混淆是极易发生的，例如在一个半径为500m的宏基站覆盖下，不能同时存在配置相同ID的两个小基站与宏基站互为邻区，否则将发生“混淆”。

目前，PCI配置算法主要基于分布式的协商、复用熵以及地理位置信息等方法[4-5]。采用图理论解决PCI配置问题也是常用的方法之一，一种启发式的算法[6]将PCI配置问题转化为图着色问题，该算法通过将相邻的小区用直线相连，然后为每个节点着色，凡是存在同一条边相连的节点着不同颜色。该算法采用集中式的算法有效地避免了ID冲突和混淆问题。但是在网络环境动态变化的情况下，仍然无法保证小区与第三级邻区的冲突和混淆问题。因此，一种改进的算法[7]提出了超图着色的方法（ HGCBA，Hypergraph Coloring based Algorithm），该方法在上一个算法的基础上，通过使用“度”的概念来定义小区相隔的个数，即直接相邻的度为1，邻区的邻区其度为2，以此类推。通过对度的动态调节，可以保持PCI的复用距离足够远，有效地降低网络环境动态变化引起的冲突和混淆，同时也可以控制ID复用距离不至于太远，节约PCI的使用。

本文面向4G无线接入系统，针对密集分层异构组网场景，提出一种基于图理论的小区ID交换配置算法（GIDSA，Graph based ID Switching Algorithm），通过搜索当前局部最优解逐步实现全局最优化，有效减少ID复用冲突混淆概率。仿真部分详细地评估了所提算法的用户载干比、ID冲突混淆概率等性能指标，并验证了该算法的有效性和优越性。

2 系统模型

随机部署场景示意图如图2所示：

图2 随机部署场景示意图

将多层的网络拓扑抽象成扁平的无向连通平面图G=G(V,E)，如图2所示，其中三角形、十字形和点分别表示宏基站、小基站和终端。图G 含网络节点顶点集合V 和边集合E，边定义为顶点间的邻区关系。在组网规划初期，由于没有更多的终端支持，基站间的邻区关系依靠点到点的信号估计进行。这种评估通过一个基站到达另一个基站站点的信号强弱来判断。信号由一个发送端xj发出，到一个接收端xk截止，并根据不同的无线信道环境进行衰落，那么发送端xj到接收端xk的干扰功率Ijk可定义为：

其中，Pj为发送端xj的发射功率；α为路径损耗因子；jk为随机的服从对数为正态分布的阴影衰落所造成的信号损耗。在异构组网场景中，小基站发射功率没有宏基站大，考虑到圆桶矮边效应，它们与宏基站是否存在邻区关系取决于功率大的一边。因此，基站间是否存在邻区关系可由rjk定义：

其中，Thweight是邻区关系的判决门限，判断两基站间的接收信号高于该门限，则rjk=1存在邻区关系，不同顶点之间邻区关系rjk组成网络邻区关系矩阵R。另外，PCI复用指示矩阵P表示基站间配置ID的冲突情况，基站xj与基站xk若配置了相同的ID，则pj,k=1，否则pj,k=0。那么，网络中所有基站之间的ID冲突可以通过邻区关系矩阵R和PCI复用指示矩阵P的Hadamard乘积计算得到：

其中，cj,k=rj,k×pj,k，取值为0或1。当cj,k=1时，基站xj与基站xk不仅存在邻区关系，而且ID冲突。引入代价函数定义为：

式（4）定义了当前解S 下网络冲突数量，那么算法的目标是找出最小代价解，即：

3 基于图论的PCI交换算法

对于一个一定规模基站数量为N 的网络来说，PCI配置的解空间是PCI数量M 的节点数量N 次方，通过穷举法求解显然需要浪费大量的计算资源。GIDSA能在较少的迭代次数和较低的计算代价下使结果收敛于最优解，具体算法步骤如下：

（1）在配置解空间中随机选取任一初始状态S 作为初始解，通过邻区关系矩阵R和PCI复用指示矩阵P计算当前状态下的冲突矩阵C。

（2）计算每个节点冲突数量并排序，交换冲突最多的节点ID，得到新解S’并进行评估：

◆若当前状态下代价函数满足COST(S’)

◆否则，返回步骤（2）重新寻找冲突次多的节点进行ID交换。

（3）以新解S’作为当前状态解并进行下一次迭代，直到无法满足代价函数，则将该解作为最终值。

以图3 为例， 假设图中网络的点集合包括V={1,2,3,4,5,6,7,8}，可供使用的PCI资源集合为PCI={A,B,C}。算法初期，在初始状态解S 中，由于配置得不合理，具有邻区关系的节点使用相同的ID，图中由虚线变为实线。算法的目标是通过某两个节点ID的交换减少网络中ID冲突的个数。

图3 冲突节点 的PCI置换示意图

表1（a）、（b）截取了节点3和节点7的邻区关系矩阵R 及PCI 复用指示矩阵P，通过这2 个矩阵Hadamard乘积后得到网络PCI冲突数量，表1（c）的冲突矩阵C显示节点3和节点7分别存在3个及2个ID冲突。因此，优先对这2个节点进行交换得到新解S’，通过代价函数评估得到COST(S)>COST(S’)，满足新解状态优于初始解，交换后更新PCI复用指示矩阵P’、冲突矩阵C’如表1（d）和（e）所示。

表1 小区3和 小区7的R、P、C矩阵

PCI的交换方法在特定的场景中并不适用，极端情况下，如网络中全部使用一个ID，仅依靠交换是无法解决，因此还需要有替换过程进行补充，即在算法步骤（2）中选择引起冲突最多的节点并使其替换成其他PCI。PCI的选择可从PCI池中找出使用频率最低的，替换要满足代价函数要求。交换和替换过程分别应对由于拓扑结构性的失误及数量上的不均匀而引起的PCI配置不合理问题。算法通过反复的迭代计算，优先调整网络中冲突最多的ID，逐步优化ID分配结构。算法的结束必然是算法无法再找到更优解，此时网络ID冲突已经收敛于一个稳态，网络中无冲突存在；亦或是网络中冲突仍然存在，但此时的矛盾在于过少的PCI资源和过于密集的网络部署，只能通过增加PCI数量来解决。

GIDSA初始配置可以从任何状态开始，甚至从随机撒点状态开始，或者从其他算法的结果获得粗略的配置出发，减少迭代次数并缩短算法运行需要的时间。算法通过对网络节点使用ID进行调整，能均匀地进行配置，有效地实现网络干扰冲突总量最小化。

4 仿真验证

本文将利用MATLAB计算机静态仿真平台验证所提算法GIDSA和对比算法HGCBA的性能，包括PCI冲突概率、PCI混淆概率和用户载干比CIR等性能。仿真场景主要考虑大规模小基站部署场景，分别采用泰森多边形随机网络（见图2）和正六边形网络进行对比。在泰森多边形网络场景中，宏基站与小基站均为撒点部署，小基站根据信号电平值与宏小区互为邻区，同时与信号估计超过设定门限的其他小基站互为邻区。用户同样随机生成，按照接收信号功率强度接入最强的基站。具体的仿真参数设置如表2所示：

表2 系统仿真参数设置

从算法的配置结果来看，图4 给出了GIDSA、HGCBA的PCI冲突和混淆概率。总体来说，算法的冲突率和混淆率都随着PCI资源的增加呈现下降趋势。冲突率在PCI数量为5个时基本趋于0，而混淆率由于要求两圈邻区PCI不复用，因此收敛速度明显偏慢，当PCI资源达到25个时，资源相对充足，此时小区的平均二级邻区在25个左右，数量与PCI数基本持平，混淆率下降至0.5；伴随着PCI资源的继续增长，密集地区也能得到充足资源，混淆率进一步降低。相对而言，GIDSA在相同资源条件下效果比HGCBA更优，这是由于GIDSA是通过交换和替换进行PCI配置的优化，当轮询的次数达到一定数量时，配置结果接近理论最优化。

图 4 GIDSA和HGCBA算法的冲突混淆率

图5、图6则给出了泰森多边形随机网络场景和正六边形蜂窝网络场景下GIDSA、HGCBA及随机分配算法的用户载干比CDF曲线。仿真结果显示，在PCI=10/30/50这3种数量条件下，GIDSA算法的CDF曲线最靠右，性能也最优，且与其他算法性能差异随着资源数量的增加而不断扩大，这主要是因为在资源数量少的情况下，算法受限于资源数目，算法性能用户总体载干比性能接近；当资源数量富裕时，GIDSA算法性能优势变得明显，此时用户载干比受接近最优化的算法机制影响；相比正六边形规章场景，HGCBA并不适用于随机部署场景，即使在PCI数量为50时，性能与GIDSA还相差3dB。另外，随机配置给出了在相同场景下没有优化的性能比较。从图中配置结果来看，在PCI资源数量缺乏时，信干比性能更多地受限于资源数量，随机分配算法性能接近于其他算法。而在PCI数量充足的情况下，CIR性能受限于能否合理地保证相同ID的复用距离足够远，因此随机分配算法性能远远落后于其他算法。

图5 泰森多边形随机网络场景下的用户CIR性能

图6 正六边形蜂窝网络场景下的用户CIR性能

5 结束语

本文将分层异构场景下小基站的ID分配问题转化为平面图问题，并提出了基于图理论的小区ID交换配置算法。该算法通过引入代价函数将配置不合理的ID进行交换和替换，从当前最优解逐步迭代最终达到全局最优化的效果。仿真验证结果显示，所提算法能有效降低网络PCI冲突和混淆概率，在相同PCI资源数量的情况下具有更高用户信干比性能增益，实现基站ID的准确识别。

[1] E Dahlman, S Parkvall, J Sköld, et al. 3G Evolution-HSPA and LTE for Mobile Broadband[J]. Elsevier, 2007.

[2] 3GPP TR 36.211 V10.2.0. Physical Channels and Modulation[S]. 2011.

[3] 3GPP TR 36.902 V9.3.1. Self-Configuring and Self-Optimizing Network (SON) Use Cases and Solutions[S]. 2011.

[4] R3-080376. SON Use Case: Cell Physical ID Automated Configuration[S]. 3GPP RAN3 #59, 2008.

[5] R3-080812. Configuration of Physical Cell Identity Use Case[S]. 3GPP RAN3 #59bis, 2008.

[6] Tobias Bandh, Georg Carle. Graph Coloring Based Physical Cell ID Assignment for LTE Network[A]. International Conference on Communications and Mobile Computing[C]. 2009: 116-120.

[7] Haitao Xu, Xianwei Zhou, Yuan Li. Model of Hypergraph Colouring for Self-Configuration in LTE Networks[J]. Information Management, Innovation Management and Industrial Engineering (ICIII), 2011(1): 393-396.★