DBSCAN算法在无线网络优化中的应用

鲁飞，王任，翁维波，陈明，涂志龙

（1.中国移动通信集团浙江有限公司宁波分公司，浙江 宁波 315040；2.杭州华星创业通信技术股份有限公司，浙江 杭州 310052）

1 引言

在无线网络优化中，故障、性能质差、投诉等经常呈现出空间聚集的区域特征，如何及时发现这些问题是网络优化的重点工作。终端用户在通信过程中会产生海量的数据，收集这些数据并从这些数据中发掘出价值信息并应用到网络优化工作中去是一个不错的研究方向。

机器学习算法在各个行业中得到越来越广泛的应用。其中聚类算法是在不清楚数据类别的情况下，根据相似性将数据集划分为不同的类簇，在数据挖掘领域有着广泛的应用。常用的聚类算法包括K_means（K均值聚类）、DBSCAN（密度聚类）、BIRCH（层次聚类）等。其中，DBSCAN算法和其他算法相比，它不需要预先确定类别数量，对噪声不敏感，可以区分任意形状的数据集，适合空间分布密度不同的数据聚类。本文在研究DBSCAN密度聚类算法的基础上，遵循层次聚类的思想，依次应用采样点筛选、数据划分、聚类、统计分析等方法探讨机器学习算法在网络优化中的应用。

以SINR质差为例，干扰及弱覆盖等都会引起SINR质差导致网速降低，进而影响用户感知，传统方法一般采用DT测试或MR性能统计确定质差情况，存在人工耗费大且定位精度差的问题。终端在通信中产生大量包含SINR等测量信息的数据，并通过一些终端APP收集并上报，这些数据能直接反应用户当时所在位置的网络情况，但是现阶段对这类数据的应用还不充分，也缺少这类数据的聚类研究。

2 基于DBSCAN算法的SINR质差聚类

2.1 SINR对下载速率的影响及质差门限

TD-LTE下行SINR是有效参考信号功率和干扰信号及噪声信号的比值，反映无线下行信号质量。SINR决定网络性能，将直接影响到终端的下载速率和用户感知。SINR值和下载速率之间具有明显的正相关性，下载速率会随着SINR的恶化而变差。

TD-LTE网络质量评估测试规范要求覆盖率按照RSRP≥-105 dBm和SINR≥0 dB统计。本文也以0 dB作为SINR的质差门限，如果某个区域SINR低于0 dB的采样点上报的越多，该区域SINR质差的采样点密度越高。

2.2 SINR质差聚类的建模逻辑

手机终端在与无线通信网络进行信息交互的过程中，会不断地检测无线信号强度和质量信息。假设网络内的终端分布均匀，质差区域的质差采样点的密度一定会大于正常区域的密度。应用DBSCAN密度聚类算法可以快速地筛选出SINR质差密度较高区域，然后对目标区域内的样本特性做统计，评估聚类结果的准确度。质差区域聚类流程如图1所示。

（1）DBSCAN算法的技术原理

图1 网络质差聚类流程图

DBSCAN算法的基本思想就是计算某个eps半径范围内采样点的数量是否大于设定值minPts。其中eps和minPts是DBSCAN算法中最重要的两个参数，分别限定算法的区域半径和最少样本点数量。

对于SINR质差定位还有一些概念需要定义，这也是DBSCAN算法的主要概念。

定义1：SINR质差核心点。如果eps邻域内的SINR质差样本点数量大于等于minPts，则邻域内的样本点称为质差核心点。

定义2：SINR质差边界点。如果某个eps邻域内质差样本点数量小于minPts，但是它在其他核心点的邻域内，则称为质差边界点。

定义3：SINR质差噪音点。数据集内既不属于核心点也不属于边界点的质差点。产生噪音数据的原因是由于快衰落等无线传播特性导致的波动或者是用户数据量太少等。

如图2所示，设定minPts=11，数据集X={xi}为采样点，x1的eps邻域内包含12个质差点，则x1为核心质差点；而x2的eps邻域内包含9个质差点，但x2由于在x1的邻域内，其为边界质差点；x3不在其他样本点的邻域内，其自己的邻域内样本点数也少于11，为噪音点。

图2 密度聚类示意图

定义4：直接密度可达。如果某个样本点在核心点x的邻域内，则该样本点从核心点x直接密度可达。

定义5：密度可达。给定样本序列x1, x2, …, xn，设xi=x1，假如从xi直接密度可达xi+1，那么从x1密度可达xn，密度可达满足传递性。

定义6：密度相连。如果某两个样本点通过另外的样本点密度可达，则称这两个样本点密度相连。

定义7：SINR质差簇。由密度相连的所有样本点组成的密度区域，称为一个SINR质差簇，最小半径是eps，不限定最大半径。如图2可以将x3以外的点聚类成一个质差簇。

（2）DBSCAN算法的特点

DBSCAN密度聚类算法可以将满足密度要求的相邻区域连接起来，能有效处理噪声数据，适合用于空间数据的聚类，但是也有比较显著的缺点，主要有以下两个方面：

1）当数据量增大时，需要较大的内存支持，I/O消耗也很大。

2）对于空间密度不均匀的数据，聚类间距相差很大时，聚类质量较差，因为这种情况下参数minPts和eps选取困难。eps设置过大及minPts设置过小说明聚类条件比较宽松，导致噪音点被纳入目标类；反之则聚类条件较严苛，导致目标簇判定为噪声。

2.3 SINR质差聚类的实现

（1）数据采集及数据处理

数据采集和预处理是数据挖掘分析的前提，所采集的数据集是与分析目标相关的总数据的一个子集。某些APP插件在通信中可以自动采集一些网络信息，包括但不限于设备号、服务小区、RSRP及SINR等字段。本文以研究SINR质差定位为目标，所以只采集部分与SINR质差相关的字段，数据格式如表1所示。

手机检测网络信号的速度在毫秒级，APP插件则每10 s采集一次网络信息，众多用户上报的数据量将非常巨大。为了增加数据的可信度，减少数据量，在采集数据的时候设定时间窗口并做均值处理。这里选择1分钟作为时间窗口，表1在时间窗口内被汇聚成一条数据，均值更能反映终端用户所在位置的网络性能特征。

APP上报数据的大部分是正常的，而我们重点关注的是那些质差的采样点，所以在数据处理阶段还可以过滤掉SINR值较好的数据，减少了DBSCAN算法对内存和读写性能的要求。设定SINR≤3 dB，可以过滤掉那些基本不存在质差的网络区域。

（2）DBSCAN算法在SINR质差聚类时的参数选择

eps和minPts是DBSCAN算法的两个重要参数，聚类结果对这两个参数的设置非常敏感。一般会根据K-dist曲线图选择设置eps的大小，对于minPts的设置也有一些文献讨论，并提出了一些自适应设定eps和minPts的方法，即通过分析数据集统计特性来自动确定eps和minPts参数，从而避免了聚类过程的人工干预，实现聚类过程的自动化，但是对于通信数据密度分布不均匀的情况并不理想，参数的设置还是需要结合实际，不断地进行优化直到得到合适值。

LTE终端位置信息的采集精度受GPS卫星信号的影响，室内甚至没有卫星信号，邻域半径设置小于50 m的意义不大，本文设定质差最小统计区域是方圆50 m的范围。即使对于大面积的干扰区域，较小的邻域半径也不影响聚类结果。

由于移动通信用户的分布很不均匀，终端测量数据的空间分布也不均匀。另外SINR样本数据是每天累积起来的，单位区域内的样本点密度会不断增加，这些都影响到minPts的选择。如果对全局采用统一的minPts，则会影响聚类准确度。具体的参数选择按照以下三步进行处理。

表1 数据采集信息表

首先，进行大数据集划分。对于密度不均匀的全局数据，一些文献提出来“分而治之”的改进思想，或提出基于数据划分的方法来选择参数，主体思路都是类似的。本文遵循数据划分和层次聚类的思想将数据集由大化小。如图3（a）将23 km×10 km的区域人工划分为5个密度大致相近的区块（A/B/C/D/E）。也可采用DBSCAN、K-means等算法完成初步聚类，划分出密度类似的较小区块。本文采用DBSCAN算法，eps设置为100 m～500 m，minPts设置为5～15，做迭代运算后选择聚类形态较好且噪声较少的参数值用于数据集划分。根据迭代结果，选择eps=250 m，minPts=8作为数据划分时的参数，全局区域划分如图3（b），颜色代表密度不同的数据集，可以看出不同密度区域基本区分开了且和人为划分结果类似，其中3个区块（A/D/E）为重点关注区域。但是也有些区域划分过小，后续可以采用其他方法对区域进行规整或直接判定为噪音，这里规定噪音不参与后续计算。

图3 SINR样本分布及初步划分区块

其次，对上一步产生的不同区块做密度聚类。根据不同区块的密度特征来设定不同minPts门限，密度较高的区块采用较大的minPts，密度较低的区块采用较小的minPts。区块划分后的密度聚类，可以采用并行方法进行处理，提升算法的数据处理速度。这里选取E区块进一步聚类分析。minPts参数需要选择不同的值做迭代计算，直到找到符合要求的参数值。图4为E区块eps=50 m，minPts选择{10, 25, 30, 40}时的不同聚类结果。其中minPts等于30时的聚类结果形态较好且分类数量符合SINR质差实际分布，所以区块E选择eps=50 m，minPts=30时的结果为质差聚类结果。

最后，随数据集变化的情况调整参数。比如数据集随时间的累积而密度增加，要随数据量的变化及时做minPts参数调整。一个方法是以一周的数据为基础设定minPts的值，然后用累积的数据量和基础数据的时长相比较得到的倍数乘以基础minPts，可以得到变动后的minPts，minPts不符合要求时仍需要及时进行调整。

3 聚类结果准确性提升及验证

3.1 质差评估算法

对于密度不均匀的数据集，即使采用了初步区域划分，较小区域内的样本分布仍不均匀。如果仅凭密度聚类结果就判定是否为质差问题点还不够充分，需要对聚类结果进一步进行分析评估。其主要思想是统计聚类区域内质差采样点的数量占区域内总采样点的数量的比例以及特征均值，质差点比例越高且均值越低，则其为质差问题点的可能性越大，需要优先处理。SINR质差占比和簇内SINR均值的计算公式如下：

图4 E区块不同minPts的聚类结果对比

以E区块聚类结果为例，共得到12个质差簇，其中簇3和簇5的质差占比远大于其他簇，评估结果如表2所示。如果结合区域内的信号强度就可以判断质差是弱覆盖引起的还是干扰引起的，这将对网络优化工作具指导意义。

表2 E区块聚类结果评估及实测

3.2 聚类结果验证

E区块聚类结果的空间分布如图5所示，这些聚类点的现场实测结果如表2实测部分所示，测试结果表明聚类区域内SINR值普遍偏低。虽然有些簇内的SINR测试值高于质差门限，这是因为测试发生在室外道路而用户通信行为一般发生在室内，所以SINR测试值和APP上报值有一定的差别。

图5 E区块聚类结果的分布图

4 结束语

本文主要研究了DBSCAN密度聚类算法在基于大数据的网络优化中的应用，介绍了SINR质差干扰排查思想。针对密度不均匀的数据特性，通过数据处理、分层聚类和性能评估等方法，降低了DBSCAN的参数选择难度，实现了对网络质差区域的排查及定位。实测结果表明：该方法聚类结果准确，区域定位准确性能满足工作要求，但后续还要加强室内APP定位精度的研究及实现minPts参数的自动化选择。