D 题 移动通信网络站址规划和区域聚类问题

今年D题应该选择的人比较多，是典型的目标优化类题目。这道题难度简单一点，估计很多同学都会选这道题，当然拿奖也会难一点了，可以使用聚类算法，有很多经典算法的。

D题主要工作是对某城市的某区域进行基站信号覆盖，并把这个区域网格化（且只考虑中心点)。数据结构为网格坐标和业务量(traffic)。在基站上，一种是宏基站，覆盖范围大（30），一种是微基站，覆盖范围小，成本低。

目录

背景阐述

移动通信技术规模飞速发展，运营规模也越来越大，导致带来的通信 网络越来越复杂。随着 5G 的发展，通信的带宽越来越大，但基站的能覆盖 范围越来越小，使得覆盖同样的区域，需要的基站数量变的更多。另外， 基站和天线的种类也变多了。这就使得通信网络的规划特别是站址选择的 问题变得越来越复杂。站址选择问题是：根据现网天线的覆盖情况，给出 现网的弱覆盖区域，选择一定数量的点，使得在这些点上新建基站后，可 以解决现网的弱覆盖区域的覆盖问题。 例如，下图为某城市某区域的现网 覆盖情况，其中红色的区域表示为弱覆盖区域。 在实际网络规划中，考虑基站的建设成本和一些其他因素，有时候可 能无法把所有弱覆盖区域都解决，这时候就需要考虑业务量的因素，尽量 优先解决业务量高的弱覆盖区域。 为了便于计算，将给定的区域用很小的栅格进行划分，只考虑每个栅 格的中心点，即任给一个区域，都可以划分成有限个点。每个点有一些属 性值，包括：坐标，是否为弱覆盖点，业务量等。站址也只能选择区域内2 的点。某个点是否被规划基站覆盖可以按如下方法判断：设选择基站的覆盖范围为 d，基站所规划的点的坐标为： ，则对于坐标为的点，若 ，则认为该点被该基站覆盖，否则认为该点没有被该基站覆盖。 同时，实际中还需要考虑一个约束条件，即新建站址之间以及新建站 址和现有站址之间的距离不能小于等于给定门限。

问题 1

描述

给定区域的大小是 2500×2500 个栅格即 2500×2500 个点， 其中横坐标范围是 0 到 2499，纵坐标范围是 0 到 2499。附件 1 中是筛选出 该区域中的弱覆盖点的信息，包括每个点的坐标和业务量。给定 2 种基站，

分别为：

宏基站（覆盖范围 30，成本 10）

微基站（覆盖范围 10，成本 1）

附件 2 中还给出了现网基站的坐标点，新建站址之间以及新建站址和 现有站址之间的距离的门限是 10。 根据给定的信息和附件中的数据，进行站址规划，使得弱覆盖点总业 务量的 90%被规划基站覆盖。给出选择的站址的坐标以及每个站址选择的 基站种类。站址的坐标只能在给定区域内的 2500×2500 个点中选择。

解题思路

第一题给出2500×2500个点，以及需要覆盖的点的网格坐标和业务量，实际可以抽象化为一个整数规划问题，每个点有三种情况，不放基站，放宏基站和微基站。而规划求解问题需要目标函数和约束条件。

目标函数：可以根据你的需要结合成本和覆盖率（达到90即可）
约束条件：
现有基站与后建基站的距离小于10
基站与弱覆盖点距离小于10/30

问题 2

描述

进一步考虑，实际中，每个站并不是完全的圆形覆盖，而是 每个站上有 3 个扇区，每个扇区指向一个方向。每个扇区在主方向上覆盖 范围最大（宏基站为 30，微基站为 10），在主方向左右 60 度的范围内可以覆盖，覆盖范围按线性逐渐缩小，在 60 度的时候，覆盖范围为主方向覆盖 范围的一半。超过 60 度，则无法被该扇区覆盖。

考虑每个站的任意 2 个扇区的主方向之间的夹角不能小于 45 度，同时 仍然考虑上一问中的基站成本等其他条件，问在最优站址和扇区角度的条 件下，新建站能否覆盖弱覆盖点总业务量的 90%。若能，给出最优站址和 扇区角度的结果；否则，给出最优站址和扇区角度的结果，并给出最多可以覆盖的弱覆盖点的总业务量的比例。

解题思路

思路：第二题基本类似第一题，不过需要增加一个限制条件，更偏向实际中信号传播的方法。在基站上要手动选择三个扇区，每个扇区覆盖60度的范围，覆盖范围逐渐缩小。

可以认为覆盖区域为一个菱形，一个基站的覆盖区域变成类似三菱图标的样子，在上面基础上增加两个约束条件即可。

目标函数： 可以根据你的需要结合成本和覆盖率（达到90即可）。

约束条件：

问题 3

描述

实际工作中，为了更好的解决弱覆盖问题，需要对弱覆盖点 进行区域聚类，把距离近的弱覆盖点聚成一类，可以得到弱覆盖区域，这 样可以对不同的弱覆盖区域分开管理使得可以更好的解决弱覆盖问题。

若 2 个弱覆盖点的距离不大于 20，则这 2 个弱覆盖点应聚为一类，并 且考虑聚类性质具有传递性，即若点 A 和点 B 是一类的，点 B 和点 C 是一 类的，则点 A、B 和 C 都是一类的。试对所有弱覆盖点进行聚类，要求聚类所用方法的总时间复杂度尽量低。

解题思路

思路：到第三题直接使用聚类方法进行聚类即可。

如K-means/DBSCAN，可以使用SPSSPRO的聚类模块（K-means）或者python/matlab编程语言进行聚类。

结语

“遇事不决可问春风，春风不语即随本心”的意思是：对一件事犹豫不决，就问春风该如何做，春风给不出答案，就凭自己本心做出决断。“遇事不决可问春风，春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》，其原文是：“遇事不决，可问春风。春风不语，遵循己心”。

来源：容艾