队伍编号
MC2202085
题号
（D）
基于 K 均值聚类算法的选址规划
摘 要
站址选择问题是：根据现网天线的覆盖情况，给出现网的弱覆盖区域，选择一定数
量的点，使得在这些点上新建基站后，可以解决现网的弱覆盖区域的覆盖问题。本文建
立相关数学规划模型并使用相关算法对问题进行求解。
针对问题一，我们先清洗数据，根据题目要求：新建站址和现有站址之间的距离不
能小于等于给定门限 10，清除已经被覆盖的弱覆盖点。之后我们采用 K 均值聚类算法对
剩余的弱覆盖点进行分类，最终得到 827 个聚类中心点。然后秉持覆盖面积尽量大，总
成本尽量小的原则建立判断标准，比较两种基站的总业务量。最终求解出我们需要建立
428 个宏基站，423 个微基站，业务覆盖量为总业务量的 90.26%
针对问题二，我们在问题一选址的基础上再次进行规划，秉持覆盖区域尽可能大的
原则，计算出使覆盖区域面积最大的扇形组合图形，让该图形逆时针旋转，采用贪心算
法，计算每次覆盖的弱覆盖点之和取最大值，最终得出了满足 88.23%业务量各个基站坐
标以及最佳的扇区角度。
针对问题三，我们首先在距离小于 20 的弱覆盖点之间建立无向边，从而建立一张
无向图，进而使用并查集算法求出该无向图的连通分量总数，将得到的连通分量个数作
为聚类的簇个数，使用 k-means 聚类算法进行聚类分析，并对算法进行相应优化，最终
得到不同类弱覆盖点的分布图。
关键词：图论；
K-Means
聚类；贪心算法；遍历；模拟
目录
一、问题重述............................................................................................................................ 1
1.1 问题背景 .................................................................. 1
1.2 问题重述 .................................................................. 1
二、问题分析 ..............................................................1
2.1 问题一的分析 .............................................................. 1
2.2 问题二的分析 .............................................................. 1
2.3 问题三的分析 .............................................................. 1
三、模型假设 ..............................................................2
四、符号说明 ..............................................................3
五、问题一模型的建立与求解 ................................................3
5.1 问题的分析 ................................................................ 3
5.2 数据清洗 .................................................................. 3
5.3 模型的建立求解 ............................................................ 4
六、问题二模型的建立与求解 ................................................7
6.1 问题的分析 ................................................................ 7
6.2 模型的建立和求解 .......................................................... 7
七、问题三模型的建立与求解 ...............................................10
7.1 问题的分析 ............................................................... 10
7.2 模型的建立和求解 ......................................................... 10
八、模型的评价 ...........................................................14
8.1 模型的优点 ............................................................... 14
8.2 模型的缺点 ............................................................... 14
九、参考文献 .............................................................14
十、附录 .................................................................14
第
1
页 共
24
页
一、问题重述
1.1 问题背景
随着科技的不断进步，移动通信技术在飞速发展，整体规模也越来越大。截至目前
我国已建成全球最大的 5G 独立组网网络，共开通 5G 基站 96.1 万个，其中共建共享基
站超过 40 万个。根据工信部计划，到 2023 年每万人均拥有 18 个 5G 基站，按照 14 亿
人口计算，大概需要建设 252 万基站。按照目前大概 96 万 5G 基站来算，未来两年半时
间还要新增 156 万 5G 基站。另外，基站的种类也在变多了，不同类型的基站其成本和
覆盖面积也有所差异。如何在合适的位置建立基站，是眼下迫切需要解决的问题。
1.2 问题重述
根据题目中所给的信息和数据，对基站地址和选择类型进行规划，使得弱覆盖点的
总业务量 90%被覆盖。得出新建基站的位置以及每个新建基站的种类。新建基站的坐标
只能在给定区域内的 2500×2500 个点中选择。
注意每个站的任意 2 个扇区的主方向之间的夹角不能小于 45 度且一共有三个扇
区，同时仍然考虑上一问中的基站成本等其他条件，问在最优站址和扇区角度的条件下，
新建站能否覆盖弱覆盖点总业务量的 90%。若能，给出最优站址和扇区角度的结果；否
则，给出给出最优站址和扇区角度的结果，并给出最多可以覆盖的弱覆盖点的总业务量
的比例。
若 2 个弱覆盖点的距离不大于 20，则这 2 个弱覆盖点应聚为一类，并且考虑聚
类性质具有传递性，即若点 A 和点 B 是一类的，点 B 和点 C 是一类的，则点 A、B 和
C 都是一类的。试对所有弱覆盖点进行聚类，要求聚类所用方法的总时间复杂度尽量低。
二、问题分析
2.1 问题一的分析
问题一要求我们对基站的位置和类别进行选择，我们先清理数据，根据 K 均值聚类
算法求出坐标，最后进行基站种类判断。
第一步分析：题目中已经给了我们现有基站的坐标，由题目要求：新建站址和现有
站址之间的距离不能小于等于给定门限 10，我们遍历以已建基站为圆心半径为 10 的所
有区域，标记该区域内不可以建立基站。同时假设原先基站的覆盖半径为 30，标记这一
区域内所有点都被覆盖。
第二步分析：对于在已建基站覆盖区以外的弱覆盖点，使用 K 均值聚类算法对这些
点进行分类，最终得到 827 个聚类中心点的位置坐标，
第三步分析：秉持覆盖面积尽量大，总成本尽量小的原则建立判断标准，比较两种
基站的总业务量满足标准中的哪一种，再具体进行判别。求得总业务量，观察是否大于
90%。
2.2 问题二的分析
问题二需要我们在问题一的基础上对所选基站的坐标进行深入分析，覆盖区域由原
来的圆形变成三个扇形区域，对角度变化范围进行判断，观察总服务量是否仍然大于
90%。
第
2
页 共
24
页
第一步分析：确定新的覆盖区域，根据题目所给条件，可以得到六个角度和半径的
极坐标方程，画出大致的图像。
第二部分析：计算出覆盖区域内的弱覆盖点的总业务量，逆时针转动覆盖区域，得
到总业务量的最大值。
第三步分析：所有新建基站的总业务量最大值累加，得到整体的业务量，观察其是
否为全体业务量的 90%。
2.3 问题三的分析
第三问我们需要对弱覆盖点进行区域聚类，把距离近的弱覆盖点聚成一类，以得到
弱覆盖区域，题目所规定若 2 个弱覆盖点的距离不大于 20，则这 2 个弱覆盖点应聚为一
类，且聚类点具有传递性。题中附件所给的数据，为 2500*2500 二维网格下，182807
个点的 X、Y 轴的坐标
第一步分析：聚类的簇个数 k 即为弱覆盖点的总的类别数量。我们可以基于图论的
思想，当 2 个弱覆盖点的距离不大于 20 时，在该两点之间建立一条无向边。这 182807
个点构成的图内连通分量的个数，即为弱覆盖点的总的类别数量，即可以作为聚类的簇
个数 k。
第二步分析：所以问题转化为：当弱覆盖点间的距离不大于 20 时，建立两点间的无
向边，从而构建一张无向图。根据图论思想建立数学模型，计算出该图中的连通分量总
数。进而再将该图中的连通分量总数作为聚类的簇个数 k，由聚类算法建立数学模型，
对所有点进行聚类。
三、模型假设
假设已经存在的基站的覆盖半径为 30，即距离现存基站距离小于 30 的点都被覆
盖。
四、符号说明
符号
说明
r
半径
角度
R
初始半径
n
业务量
第
3
页 共
24
页
五、问题一模型的建立与求解
5.1 问题的分析
问题一要求我们对基站的位置和类型进行规划。首先我们使用 k 均值聚类算法，找
到我们要进行建站的坐标。在选择基站类型的时候，我们的规划目标为覆盖面积尽可能
大，成本开销尽可能小，为此我们设计判断标准，确定每一个基站类型的选择。
5.2 数据清洗
题目附件一种给定了弱覆盖点的坐标和吞吐量，附件二中给了已建立的结点的坐标
和 id，题目中要求坐标范围为（0，2500），我们先遍历所有点的坐标，检测坐标点是
否越界。
之后我们对附件一中的数据进行清洗。我们假设已经建好的基站的半径为 10，建立
2500*2500 的矩阵，采用遍历算法，设计双层循环将附件二中所有的坐标点在以该点为
圆心，半径为 10 的区域内进行标记。使用标记后的矩阵判断附件一中的坐标是否已经
被覆盖，排除被覆盖的点，将未被覆盖的点存储在一张如下表格当中。
x
y
value
932
2210
18680.96094
972
1238
15063.48242
1229
1894
12733.10254
1611
2233
11579.5166
1370
2333
9875.611328
1371
2333
9726.910156
802
1302
9111
1338
1124
8126.308105
1060
1861
7900
806
1302
7794
1258
1465
7231.84668
2238
1788
7186.233887
1258
1466
7169.891113
204
1754
7156.300293
1010
1156
6944.081543
1052
1182
6934.246094
827
1551
6788.858398
828
1551
6788.858398
1529
2401
6581.398926
1379
2312
6026.120117
662
2326
5503.69873
1338
1392
4840.562012
1338
1393
4838.427734
1342
1399
4838.412598
1323
1389
4837.79248
654
2321
4100.165527
449
1593
4028.841309
1611
2234
3734.764404
- 1
- 2
- 3
- 4
- 5
- 6
前往页