基于改进Welsh Powell的NPRACH子载波偏置自配置算法

黄炎水，谢佳锐

（中国移动通信集团广东有限公司揭阳分公司，广东 揭阳 522000）

1 引言

随着3GPP标准的制定及智慧城市智能家居等产业的不断发展，物联网也迅猛发展。基于蜂窝网络的NB-IoT（Narrow Band Internet of Things，窄带物联网）技术由于具备了广覆盖、大连接、低功耗和低成本的特点，在业界备受瞩目。

与LTE不同，NB-IoT主要应用于低时延敏感性、低速率、小包业务场景，同时支持大连接，这样的业务特点对网络的接入性能提出了更高的要求。在LTE中，终端接入网络时采用不同的前导序列，用于基站标识不同终端。但是在NB-IoT中，终端接入网络时采用相同的前导码，基站标识不同终端是通过终端接入时所采用的时频资源。不同覆盖等级的终端接入时采用不同的时域资源，同一覆盖等级下的终端接入采用不同的频域资源。终端所采用的时频资源取决于小区的NPRACH（NB-IoT Physical Random Access Channel，NB-IoT物理随机接入信道）配置，包括起始时间和子载波偏置配置。本文从子载波偏置配置入手，研究子载波偏置配置对NB-IoT终端接入的影响并提出可行的配置方法。

2 NPRACH子载波偏置

从时域上看，如图1所示，NB-IoT的NPRACH由4个符号组构成，每个符号组由1个CP（Cyclic Period，循环前缀）和5个符号组成，C P长度分为两种：66.7 μs和266.7μs。不同CP长度用于支持不同的覆盖距离，66.7 μs的CP长度支持低于8 km的小区半径。

图1 NPRACH时域结构

从频域上看，NPRACH采用single-tone方式传输，子载波间隔3.75 kHz，180 kHz的带宽分为48个子载波。NPRACH的传输采用跳频的方式，分为两层跳频，一个是NPRACH中4个符号组的跳频与重复发送时的跳频。符号组之间的跳频分成两个层次，第一层次相差1个子载波，第二层次相差6个子载波，即22.5 kHz，用于第二个符号组与第三个符号组之间，如图2所示。而重复发送时的跳频是通过伪随机序列来决定重复发送时的频域起始位置。

NPRACH的初始频域位置通过NPRACH的子载波偏置和子载波数量来决定。根据3GPP协议关于NB-IoT随机接入信道子载波偏置的规定，子载波偏置有7种配置SC_0/SC_12/SC_24/SC_36/SC_2/SC_18/SC_34，而子载波数量有4种配置12/24/36/48，不同的子载波偏置可配置的子载波数量对应关系如表1所示：

表1 NPRACH频域配置

由表1可知，同频组网的情况下，相邻小区配置相同的子载波偏置时，位于两个小区重叠覆盖区域的用户在发起随机接入时，会导致用户的初始频域位置落在邻小区NPRACH检测频域范围内，造成邻小区的误判，从而浪费邻小区的时频资源，同时也影响邻小区用户的接入。相邻小区同子载波偏置情况如图3所示。

图2 NPRACH跳频传输

图3 相邻小区同子载波偏置情况

通过测试验证了相邻小区同子载波偏置的影响，选取了同站点两个小区，测试参数如表2所示。

在上述测试环境下，测试一个小时的随机接入，统计后台指标，两个小区随机前导数量和冲突解决消息数量如表3所示：

表3 子载波偏置影响测试结果

由表3的测试结果可知，冲突的前导数量在修改后降低了65%，由此可见，邻区配置相同子载波偏置的情况下，邻区误判的情况比较严重，因此，需要在规划阶段对NPRACH的子载波偏置进行合理规划。由表1可知，不同的子载波偏置配置使用不同范围的子载波，同时又存在不同程度的交叠。现网中，为了更好地利用48个子载波，同时减少冲突的数量，采用12个子载波数量更为合理，本文以12个子载波数量为例，提出基于改进Welsh Powell染色的子载波偏置自配置算法。

3 子载波偏置自配置算法

3.1 问题描述

在大规模建网的情况下，子载波偏置必须进行复用，同时，需要保证使用相同子载波偏置的小区距离足够远，尽可能避免重叠覆盖。实际应用中，功率参数、工作频率、覆盖区域的地理地貌等会直接影响复用的距离，可类比于LTE中的PCI复用距离。根据Walfisch-Ikegami模型与NB-IoT的覆盖增强特性，以及UE发射最大功率和基站接收NPRACH的检测门限，可计算得出复用距离，在复用距离内的其它小区不能采用相同的子载波偏置。

按照使用相同频点的相邻小区不能使用相同子载波偏置的原则，子载波偏置问题可以抽象为图的顶点着色问题。给定图G=(V, E)，称映射φ： V→{1, 2, 3, …,k}为G的一个k-点着色，称{1, 2, 3, …, k}为色集。若对G中任意两个相邻顶点u和v均满足φ(u)≠φ(v)，则称该着色为正常的。顶点着色问题是一个NP-Hard问题，传统的解决算法有回溯算法、Welsh Powell算法等。

3.2 算法流程

子载波偏置问题可以抽象为7-点着色问题，但是又略有不同，子载波偏置问题是存在限制条件的顶点着色问题。子载波偏置问题的限制条件在于7个子载波偏置配置中存在冲突的情况，如子载波偏置0与子载波偏置2存在频域交叠，因此偏置0与偏置2不能相邻，而在实际网络中，又存在无法避免冲突的情况。传统的Welsh Powell算法无法解决这一问题，因此本文提出了改进的Welsh Powell算法。改进后的算法分成两步，将原本的7-点着色问题分解为4-点着色问题和基于权值的3-点着色。

第一步，由于SC_0/SC_12/SC_24/SC_36这4个子载波偏置的频域资源相互正交，因此采用Welsh Powell算法按照4-点着色的方式进行着色；第二步，对于未着色的节点，通过基于权值的3-点着色算法解决，具体算法流程如图4所示。

算法流程具体如下：

（1）根据网络拓扑与各个站点间的距离，站点复用距离内的其它站点视为相邻顶点，生成节点的关联矩阵V，距离矩阵D，将子载波偏置{SC_0, SC_12,SC_24, SC_36, SC_2, SC_18, SC_34}，记为集合c，根据各个子载波偏置对应的交叠子载波个数通过矩阵的形式表示，得到子载波冲突矩阵，记为Ccorrupt，可以得到：

表2 子载波偏置影响测试参数

图4 基于树值的3-点着色算法流程

（2）根据关联矩阵V计算节点关联度数，将网络拓扑中的站点按照节点度数由大到小排序，生成排列s。

（3）对于排列s，先按照Welsh Powell算法进行4-点着色。

◆取出SC_0，对第一节点进行着色，并按排列顺序对与前面着色节点不相邻的每一节点都着上同样的颜色；

◆对未着色的节点重新进行排序，取出SC_12对尚未着色的节点重复步骤（3）的第一步，再取出SC_24与SC_36继续着色。

（4）如果排列s中还存在尚未着色的节点，依次取出节点sk，计算c中7个子载波偏置的权值，记采用子载波偏置ci（0＜i≤7）且与sk相邻的节点集合为b，则子载波偏置ci（0＜i≤7）的权值计算如下：

3.3 仿真验证

为了对比算法的实际效果，本文定义了子载波平均复用距离，通过每个子载波的最小复用距离的均值来衡量子载波冲突的程度。改进算法与原始的Welsh Powell算法进行对比，根据现实中的实际站点分布，采用Matlab工具仿真配置的结果。

仿真验证分为两步，第一步是针对站点分布较为稀疏的情况，仿真13个站点分布的情况。对于站点分布较为稀疏的区域，基本通过第一步4-点着色可以完成区域的子载波偏置配置，稀疏区域的配置两个算法结果相同，符合预期。图5是稀疏区域的站点配置示意图。

第二步对于站点密集分布的区域，冲突情况无法避免，通过权重来决定所使用的子载波偏置配置，分别对存在23个节点的区域和151个节点的区域进行仿真，原始算法得到的结果如图6和图8所示，改进后的算法配置结果如图7和图9所示。

图5 稀疏区域的站点配置

图6 原始算法下23个节点密集区域的站点配置

图7 改进算法下23个节点密集区域的站点配置

由两个例子可以看出，在站点密集的情况下，尽管局部区域存在冲突，但是颜色总体布局合理，充分利用了不同的子载波偏置配置有效降低子载波偏置所带来的冲突。计算子载波平均复用距离，得到表4的结果。

图8 原始算法下151个节点密集区域的站点配置

图9 改进算法下151个节点密集区域的站点配置

表4 密集区域下不同配置算法仿真结果

从表4的结果可以看出，改进算法对比原始算法有所提升，通过计算权重的方式可以有效地减少子载波冲突的情况。

4 结束语

本文将NB-IoT中随机接入信道的子载波偏置配置问题抽象成了图论中的顶点着色问题，又根据协议和现实情况对这一问题进行了研究，通过改进的Welsh Powell算法来解决这一特定的着色问题。本文算法可用于实际工程中NB-IoT网络随机接入信道的子载波偏置配置，可以减少时频资源的浪费，提高资源的利用率，同时避免冲突导致的用户接入失败以及由此引发的接入重试。同时，在算法中子载波偏置的权值采用系数法，可以通过修改系数来适用NB-IoT不同应用场景下的配置，提高了算法的鲁棒性。对于存在部分子载波偏置无法配置的情况，该算法也可以通过改变子载波冲突矩阵来实现自适应。