基于聚类算法的5G 网络覆盖问题智能定位

朱佳佳，马 昱，杨洁艳，田元兵，（.中国联通研究院，北京 0076；.中国联合网络通信集团有限公司，北京 00033）

1 应用背景

随着5G无线网络的发展，多种先进技术和大量微基站的引入，网络设备云化和智能化同时带来了大量的维护和优化工作，这使得网络管理更加复杂。在此背景下，自组织网络（SON）作为5G 系统与人工智能技术结合的一个关键领域，获得了越来越多的关注。自组织网络的目的是降低运维成本，提高网络效率，提高网络的性能和稳定性，实现网络自配置、网络自优化和网络自愈3个目标。自配置指对新入网的网元部署自动化，并为这些网元确定适当的参数配置；自优化是指当网络处于运行状态时，不需要人工干预的情况下，在覆盖范围、容量和用户感知等方面自动优化，如移动负载平衡、切换优化、自动邻区关系、覆盖和容量优化、小区间干扰协调和节能等；自愈指故障管理和故障纠正过程的自动化，以保持网络的正常运行。在建网前期，自配置技术可以实现基站的即插即用，随着网络运行数据越来越多，借助人工智能算法就可以一定程度上实现自优化和自愈。

最小化路测技术（MDT）是SON 中的关键技术，主要通过移动终端上报测量报告或者网络侧其他测量数据来分析网络性能，以达到降低运营商网络优化维护成本的目的。3GPP Release 17 在2020 年的规划中，着重提出：SON 中的MDT 是2020年Q2和Q3考虑的重点，而MDT 中的一个重要应用就是实现覆盖智能优化。现阶段使用的MDT 数据主要是带经纬度的原始MR数据。

本文将重点讨论利用5G 中MDT 数据，结合聚类算法，实现网络自组织技术中的覆盖问题智能定位。

2 5G覆盖问题智能定位

覆盖问题智能定位的目标是将网络中能反映覆盖的指标数据，通过人工智能算法，定位网络中的问题，同时获取问题所在的地理位置。主要分为2 个阶段：第1阶段，利用5G中的MDT数据进行聚类，得到覆盖问题点；第2阶段，将覆盖问题点基于经纬度进行聚类，得到地理范围上较为密集的区域，为问题解决提供优先级。在2 个阶段中根据不同的目标需求，分别采用不同的聚类算法。

常见的聚类算法可以大致分成几类：

a）基于划分的聚类方法：将数据集分裂成K个分组，每一个分组是一个类。大部分基于划分的聚类算法是基于样本点间的距离，同一个类内的对象尽可能相近，不同类内的对象尽可能远离。K-Means 算法是最典型的基于划分的聚类方法。

b）基于密度的聚类方法：与其他方法的聚类算法根本区别在于，它不是基于样本点间的距离，而是基于密度的，这样就可以发现数据集中的疏密关系。DBSCAN算法是最典型的基于密度的聚类方法。

c）基于模型的聚类方法：假定每一个聚类符合一个模型的分布，然后去寻找能够很好满足这个模型的数据集。高斯混合模型算法是最典型的基于模型的聚类算法。

本文中，基于聚类算法的覆盖问题划分，是希望利用聚类算法，根据采样点的覆盖指标获取表现较差的采样点，故采用基于相似度的划分聚类方法。而对于覆盖差点的地理聚类，目标是找到覆盖差点的连片或密度集中区域，则选择基于密度的聚类方法。下面将分两节来分别阐述覆盖问题智能定位的2个阶段。

2.1 基于聚类算法的覆盖问题划分

在5G 中评价覆盖质量的指标是RSRP 和RSRQ，3GPP TS 38.215中提出的覆盖指标包括SS-RSRP、SSRSRQ、CSI-RSRP 和CSI-RSRQ。SS-RSRP 定义为承载辅同步信号（SS）的资源单元的功率的线性平均值。SS-RSRP 测量时间位于SS／PBCH 块测量时间配置（SMTC）窗口持续时间内。终端支持RRC-Connected、RRC-IDLE 和RRC-Inactive 态的同频和异频测量。CSI-RSRP 定义为在所配置的CSI中，在其测量频率带宽范围内，承载用于RSRP测量的CSI参考信号的资源单元的功率线性平均值。终端支持RRC-Connected态的同频和异频测量。截至2020 年2 月，终端还未支持CSI-RSRP 的上报。综合对比应用情况、资源开销，以及目前的芯片支持情况，在现阶段建议将SS-RSRP 和SS-RSRQ 作为5G 网络覆盖情况的评价标准。SSRSRP和CSI-RSRP的对比见表1。

随着5G 网络拓扑的复杂化，针对不同的场景、区域及业务情况，设定绝对门限，简单地将采样点分成覆盖好坏2 类或者优良中差4 类的“一刀切”方法是不合适的。另外，建网初期，缺乏对RSRP 评估门限的经验值，难以对采集到的原始数据基于一个理论的绝对门限值来评价覆盖的好坏。随着网络的运行数据源增多，也可将评价标准扩展到RSRP 和RSRQ 以外，综合考虑速率等用户感知情况，结合多维数据对网络覆盖情况进行评价。

聚类算法的初衷是对没有先验知识的数据进行聚集，故使用5G MR 中的RSRP、RSRQ 作为聚类的输入向量的维度，对原始的MR 采样点进行聚类，得到目标区域中覆盖相对较差的采样点。不事先设定聚类的类数，而是通过聚类算法自动地将采样点分成若干类，计算分成不同类的聚类结果评价系数，确定覆盖采样点最终的分类个数，也就是让网络智能、自动地去发现区域内相对的覆盖差点。

AP 算法（Affinity Propagation Algorithm）是通过数据点之间的消息传递来发现聚类，并在很短的时间内发现带有更低误差的聚类结果。它将一对数据点之间的相似度作为输入，在数据点之间交换有真实价值的消息（real-valued messages），直到一个最优的类代表点集合和聚类逐渐形成。此时，所有的数据点到其最近的类代表点的相似度之和最大。对于给定数据集合D={X1,X2...,XN}，计算各点之间的相似度矩阵。利用欧式距离来反映2点之间的相似度，任意2 点之间的相似度为2 点欧氏距离平方的负数。对于点Xi和点Xk，

每一个数据点k需要预先设定其参数s(k,k)=pk(k=1,2,...,N)，初始pk越大，说明相应数据点k被选中为类代表点的可能性越大。假设所有数据点被选中成为类代表点的可能性相同，即s(k,k)取相同值p。该算法中有2 种消息交换，即响应度矩阵R=和效应度矩阵。响应度矩阵描述数据点k适合作为点i的类样本的程度；效应度矩阵描述数据点i选择点k作为其类样本的适合程度。AP算法循环迭代并更新这2种消息，更新公式如下：

为避免迭代过程的震荡发生并促进收敛，引入阻尼系数λ，在每一次循环迭代中，r(i,k)和a(i,k)被设置为：

迭代过程中，当r(k,k)+a(k,k)＞0，则选择数据点k为类样本点，设聚类标记为，则AP 算法可看作一个搜索能量函数最小值的方法，即

当算法收敛（即能量函数最小化）或达到最大迭代次数，则算法停止并输出聚类结果。

AP 算法输出的聚类数目依赖于输入的参数p，但对给定的数据集，p取何值能获得最佳聚类质量却是未知的。所以引入自适应的AP 算法来确定最优分类。首先确定参数p的搜索范围，其对应的分类结果分别为将全部数据点分为一类以及将全部数据点分为若干类。设定2 种调整步长：分别用于逃离震荡以及调整分类个数。算法从p=pmax开始运算，若分类结果无法收敛，则下降一个步长pstep1，如此直到算法可以收敛。之后，下降步长pstep2，以逐渐减少分类个数。

在聚类结束后，采用Calinski-Harabaz 分数来评价不同聚类的好坏，该评价公式为：

式中：

Bk——类间协方差平均值

Wk——类内协方差

Tr——矩阵的迹

N——聚类的采样点数

K——经过聚类算法得到的类数

类内的协方差越小越好，类间的协方差越大越好，所以对于该评价公式来说，得分越高表示分类效果越好。通过调整AP 聚类算法的参数p，将原始采样点分成一类到若干类，通过Calinski-Harabaz 分数评价将原始采样点分成几类时为最优分类。

2.2 覆盖问题地理化聚类

通过聚类算法得到网络中存在的覆盖问题点后，若将覆盖问题点根据经纬度撒在地图中，会出现很多零散的点，难以用肉眼去判断每个区域内的问题点分布密度，也就难以为优化工作综合统筹，提供一个解决问题的优先级。故利用覆盖问题点的经纬度进行聚类，即可得到所关心的区域中，弱覆盖问题点的密集区域。

在上文提到的基于划分、密度和模型的聚类算法中，考虑到此处聚类的目标是发现采样点的密集区域，选取DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法对弱覆盖采样点进行聚类。DBSCAN 算法可以找到样本点的全部密集区域，并把这些密集区域聚成一个一个的类，其他稀疏的点会被当作噪声点分成一类。DBSCAN 的优势在于对远离密度核心的噪声点具有鲁棒性，无需知道聚类簇的数量，可以发现任意形状的聚类簇，完全符合基于经纬度的聚类需求。

DBSCAN 算法需要设定2 个参数，邻域E和最小样本点MinPts，以下是算法的一些基本概念：

a）邻域E：对于任意样本i和给定距离E，样本i的E邻域是指所有与样本i距离不大于E的样本集合。

b）核心对象：若样本i的E邻域中至少包含MinPts个样本，则i是一个核心对象。

c）密度直达：若样本j在样本i的E邻域中，且i是核心对象，则称样本j由样本i密度直达。

d）密度可达：对于样本i和样本j，如果存在样本序列p1，p2，...，pn，其中p1=i，pn=j，并且pm由pm-1 密度直达，则称样本i与样本j密度可达。

e）密度相连：对于样本i和样本j，若存在样本k使得i与j均由k密度可达，则称i与j密度相连。

基于以上概念，DBSCAN 将类定义为：由密度可达关系导出的最大的密度相连的样本点集合。算法具体流程如图1所示。

图1 DBSCAN算法流程

3 应用效果

针对第2 章描述的覆盖智能定位的2 个阶段，利用5G 现网中的真实数据进行数据分析。由于目前5G网络暂无收集到带经纬度的MR 数据，故在此利用北京各环路上的5G 测试数据来模拟5G 的原始MR 采样点数据。

首先，将数据中的RSRP 和RSRQ 组成向量，通过调整AP 聚类算法中的参数p，将采样点聚类成了2～10类，并利用Calinski-Harabaz评价算法来评价将采样点分成不同个数的类的聚类效果。图2是将采样点分成2～10 类，不同的分类结果下，Calinski-Harabaz 系数的得分。由于选取的聚类评价指标值越大说明聚类质量越高，也就是意味着类内越紧凑，类间可分度越高。从图2 中可以看出把北京各环路上收集到的RSRP 和RSRQ 采样点组成的数据向量分为6 类为最优分类。

图2 聚类质量评价指标曲线

图3 覆盖采样点最优分类

按照最优分类，将RSRP 和RSRQ 组成的向量，分成6 类，如图3 所示。这样就得到了在分析的目标区域中覆盖较差的一类采样点，也就是图3 中紫色的采样点类。进入第2 阶段，将重点关注覆盖较差的采样点的密集区域。

将弱覆盖的点的经纬度撒到地图中，如图4 中的红点所示，可以看出采样点较为分散，难以区分优化整改的优先级，所以对弱覆盖的点进行地理化处理，基于DBSCAN算法对其经纬度进行聚类。

图4 覆盖问题点地理化

首先计算经纬度之间的球面距离，作为DBSCAN聚类算法的相似度矩阵输入。DBSCAN 算法有2 个关键的参数，即邻域距离E和邻域最小样本个数MinPts。考虑在测试过程中，车速为60 km/h 左右，一秒一个采样点，故理论上采样点之间的距离在16 m 左右。所以，在为DBSCAN 设定参数时，将邻域距离E设置为0.5 km，最小样本个数设置为5，10，15。通过设定邻域内最小样本个数，可以控制聚类得到的有效类的采样点密度，对应到实际意义，也就是控制聚集的弱覆盖区域内弱覆盖采样点的密度。图5～图7为不同参数配置下所有弱覆盖的点在北京的5个环路的分布。浅蓝色的点为噪声点，也就是弱覆盖的稀疏点，其他彩色的点是聚类得到的有效点，也就是弱覆盖点比较密集的需要优先考虑整改的区域。在此不采用评价系数来评价聚类算法，一方面是由于常用的聚类算法普遍是用来评价基于凸的簇，对基于密度的簇评价普遍不好。另一方面是由于DBSCAN 算法调参，是可以控制聚类得到的区域密度，根据一线优化人员的需要，来确定需要整改的区域大小及密度。

图5 DBSCAN算法参数配置1

图6 DBSCAN算法参数配置2

图7 DBSCAN算法参数配置3

4 结束语

本文在介绍了5G 与SON 技术后，首先提出了基于聚类算法的覆盖问题划分，通过5G中的路测数据模拟MR 数据，利用AP 聚类算法动态调整系数，得到不同的分类结果，并利用评价公式对聚类结果进行评价，得到最优分类。基于最优分类发现网络中的覆盖问题点。第2 步根据覆盖问题点的经纬度，利用DBSCAN 算法，对经纬度进行聚类，通过调整参数，得到网络中不同密度的覆盖问题区域。随着5G 网络数据采集的逐渐成熟，该算法可以针对网络中更多丰富的数据源做扩展应用，提升问题定位的准确性，提升网络维护和优化效率。