基于DBSCAN聚类的基站选址与扇区角度规划研究

盛屹涛，郑晓璇

（江苏师范大学 敬文书院，江苏 徐州 221116）

随着5G网络大规模发展，用户业务对于频段资源的需求也随之快速增长。从技术标准层次分析，5G网络工作处于3 000～5 000 MHz频段，远高于2G、3G、4G网络。频率越高，信号在实际传播进程中的衰减也越大[1]，使得通信网络规划特别是站址选择变得越来越困难。在实际网络规划与基站建设中，考虑建设成本和其他因素，应尽量优先解决业务量高的弱覆盖问题，同时兼顾基站建设成本最低化与业务量最大化。本文针对2022年MathorCup高校数学建模挑战赛D题[2]，给出基站建设规划的最优化方案，拟解决两方面问题：一是通过设计聚类算法，使运算量最小化；二是设计基站种类、位置及扇区主方向，使得弱覆盖点总业务量的90%被基站覆盖。

1 数据预处理

1.1 数据描述与分析

数据来源于赛题附件1和附件2，其中附件1给出了某地弱覆盖点的位置和业务量，附件2给出了现有基站的位置。2种基站和其覆盖范围、建设成本如表1。

表1 可建设基站的种类、覆盖范围与成本

1.2 数据处理

首先，寻找已被现有基站覆盖的弱覆盖点。考虑基站有三个扇区，且扇区主方向角度是变化的[3]，为使覆盖区域最大化，首先需对不同角度下基站的辐射距离进行讨论，再通过距离计算，剔除可能受影响的点，得到极弱覆盖区域。筛选不能受任何现有基站辐射的区域，在聚类中心铺设基站，可优先解决此类地区的极弱覆盖问题，也能避免因基站部署密集造成终端来回切换导致的信号差、资源浪费等现象[4]。

1.3 基站扇区主方向与覆盖半径的关系

根据赛题条件，一个基站只有3个扇区进行覆盖，因此各基站扇区的主方向不同时，其所覆盖的坐标点各不相同。根据要求建立站址间、新建站址与现有站址间的距离门限是10，各站中任意两个主方向间的夹角不能小于π/4，设置限制条件，且考虑基站成本等因素进行规划。

首先，建立基站半径函数。设基站辐射半径为R，坐标点和基站间连线和其中一个主方向的夹角为θ，且此时坐标点与基站间连线的距离为r。利用插值法[5]，计算半径随角度线性变化的系数，由此确定半径和夹角关系式如下：

在基站规划中，任意两扇区间的主方向夹角要大于π/4，同时每个基站只有3个扇区，进一步分析不同扇区主方向间角度β变化后的基站覆盖半径r与夹角θ的关系式。为方便表示，以其中一个扇区的主方向为极轴，讨论该扇区与另一扇区的辐射半径，3个扇区的情况可类比得到。由于每个扇区主方向左右π/3的范围内都能起覆盖作用，考虑两个扇区间的重叠部分，需分三种情况对两个扇区间的夹角β进行讨论。

根据上述任意两个扇区形状所覆盖的半径随着θ变化的函数表达式，选定扇区主方向角度最小的方向所在直线为极轴，再通过旋转正方向β角度，就可得到第二个主方向。依次类推，可构造出一个基站的三个主方向之间的夹角关系，从而得到该基站在任意角度的辐射半径。

2 基站扇区主方向角度规划

首先，根据基站建设要求，每个站的任意两扇区的主方向间的夹角不能小于π/4，每个基站有三个扇区，且每个扇区指向一个方向时，设第i个基站的三个扇区主方向角度分别为φi，1、φi，2、φi，3，其关系如下：

为优化算法，考虑扇区的主方向时，分别计算各点和基站连线与x轴正方向的夹角，以距离最远的点与基站的连线作为其基站中一个扇区所指方向，记为φi，far，根据覆盖点到基站的距离，采用条件期望[6]对剩下两扇区所指方向进行规划。设该基站能辐射的弱覆盖点中最小角度为φi，min，最大角度为φi，max，与极轴正方向的角度为φi，j，分三种情况讨论。

（1）当φi，far=φi，min时，记集合{φi，1，φi，2，φi，3，…}的中位数为φi，mid，取φi，1=φi，far。对于剩余的两个扇区，考察其与中位数φi，mid的关系，对于该基站能辐射到的弱覆盖点，若φi，j＜φi，mid，根据其到基站的距离计算条件期望，并注意的限制条件，可得

若φi，j≥φi，mid，根据距离计算条件期望，注意到取所对应的角度

（3）当φi，far=φi，max时，同理可得，

根据上述扇区的主方向，可求得现有基站对于已知弱覆盖点的覆盖范围，经筛选即可得到未被覆盖点的集合。

3 基于DBSCAN聚类算法的基站站址规划

3.1 基于DBSCAN的弱覆盖点聚类

使用聚类算法可以较好地筛选数据，在聚类中心位置建设基站可全面覆盖周围区域，使每个类的每个点都被覆盖。聚类算法主要有K-means算法[7]、系统（层次）聚类算法[8]和DBSCAN聚类算法[9-10]三种。由于具体需聚类的数量未知，与K-means比较而言，DBSCAN不需输入要划分的聚类个数[11]，但样本数过大时，如随机指定聚类数量不科学，且会增加计算量，过小则不能很好体现弱覆盖点间关系。考虑弱覆盖点是坐标形式，因此通过DBSCAN聚类的两个参数EPS和Minpts体现其关系，根据基站辐射半径和基站间的门限要求设置EPS。同时，基于密度定义，能处理任意形状和大小的簇也可在聚类的同时发现异常点，异常点可视为偏远地区。如果该点处业务量较大，可通过设立基站解决弱覆盖问题。综上可知，DBSCAN算法更适用于弱覆盖点的聚类。

DBSCAN算法聚类执行过程为：在已筛选的143 528组数据中随机选取某个对象点X，查询X的EPS邻域半径内所有密度可达点是否大于MinPts，如果大于，则创建一个以该点为核心的聚类簇；然后，迭代聚集核心点密度可达的所有对象，该过程可能会将已经形成的簇进行合并，在算法执行过程中，某些核心点的密度可达对象会被重复查询验证是否在一簇里；完成一个簇聚类后，选取下一个点开始聚类，直至没有任何新的点添加到任一簇时，聚类结束。

3.2 已有基站扇区的主方向规划

找到剩下143 528数据中不能被任何现有基站辐射的极弱覆盖区域，对现有基站扇区主方向角度进行规划，得到所有弱覆盖点业务量的覆盖率，达38.73%。表2给出了部分现有基站的主方向角度规划。

表2 现有基站的主方向角度规划

3.3 聚类中心处基站扇区的主方向规划

对极弱覆盖区域进行DBSCAN聚类，参数EPS[12]为5，最少样本数目设置为1，得到4 942类，栅格的聚类情况如图4。由图4可发现，同一类内部的坐标位置都相对较近，表明这些坐标在同一类中心的覆盖下出现次数较多，即DBSCAN聚类作用下分类情况较好，能最大限度地覆盖这些坐标点。

图4 聚类效果可视化结果

在聚类中心建立基站还需满足基站间门限大于10，记聚类中心为Ui，i=1，2，3…，已建立基站为Pj，j=1，2，3…，于是对∀i∈{1，2，3…}，对∀j∈{1，2，3…}，满足‖Ui-Pj‖＞10；还要满足新建立的基站间门限也大于10，对∀i∈{1，2，3…}，对∀k∈{1，2，3，…，i-1}，满足‖Ui-Uk‖>10。考虑聚类中心周围的点较为密集，为使覆盖率尽可能大，在所有聚类中心处考虑建立宏基站[13]。在满足门限条件下，共建立宏基站1 877个。根据主方向角度的规划，求得此时覆盖率达72.76%。在聚类中心建立的部分宏基站位置和主方向角度规划如表3所示。

表3 在聚类中心建立的宏基站位置和主方向角度规划

3.4 极弱覆盖点处建立基站的扇区主方向规划

上文在聚类中心建立宏基站覆盖率虽达72.76%，仍未达90%，因此，考虑在极弱覆盖点处建立微基站，以确保成本最低化，同时获得较高的覆盖率。在门限大于10的条件下，根据基站扇区主方向角度规划，得到覆盖率为89.56%，此时建立微基站2 292个。求解与所建宏基站之间覆盖率相差最大的基站，并将其排序，覆盖率小于90%时，将差距最大的微基站改为宏基站。最终，将两个微基站改为宏基站，即可使覆盖率达90.21%。两个基站修改后得到的坐标和三个扇区主方向角度规划如表4所示，其余部分微基站的位置和主方向角度规划如表5所示。

表4 极弱覆盖点处微基站修改成宏基站的位置和主方向角度规划

表5 建立的微基站位置和主方向角度规划

4 结 语

本文针对线性递减情况，通过求解扇区辐射半径与角度关系，根据弱覆盖点到基站的距离，对扇区主方向角度进行规划，再用DBSCAN聚类模型对极弱覆盖点进行聚类，最终共计建立1 879个宏基站和2 290个微基站，覆盖率达90.21%。此外，对已有基站的三个扇区主方向进行规划，假定扇区主方向角度均为0、2π/3、4π/3，覆盖率只能达26.82%，而采用聚类法，覆盖率可达38.73%，表明在考虑优化算法复杂度情况下，聚类较为有效。