基于模拟退火法的基站选址优化问题——模拟退火法在0-1规划的数学规划模型上的应用

Base Station Location Optimization Problem Based on Simulated Annealing Method—Application of Simulated Annealing Method to Mathematical Programming Model of 0-1 Programming

摘要: 随着5G技术的全面普及，通信所需的带宽越来越大，原有基站能够覆盖的范围越来越小，从而需要建立新基站减少弱覆盖区域。本文主要是建立基于0-1规划的数学规划模型，采用模拟退火法对规划模型进行求解，以研究解决当前网络弱覆盖区域的覆盖问题。根据当前网络天线的覆盖情况，给出当前网络信号的弱覆盖区域，选择一定数量的点，使得在这些点上新建基站后，可以优化当前网络的弱覆盖区域的覆盖问题，使得弱覆盖区域尽可能小。本文先进行数据清洗，筛选掉现有基站与弱覆盖点之间的欧式距离小于门限10的弱覆盖点与业务量小于1的弱覆盖点。将选址问题确定为0-1规划的数学规划问题，接着用模拟退火算法对模型进行全局求最优解。

Abstract: With the comprehensive popularization of 5G technology, the bandwidth required for communica-tion is getting larger and larger, and the coverage range of the original base station is getting smaller and smaller, so it is necessary to build new base stations to reduce the weak coverage area. In this paper, the mathematical programming model based on 0-1 programming is established, and the simulated annealing method is used to solve the programming model, so as to solve the cover-age problem of the weak coverage area of the current network. According to the coverage of the current network antenna, the weak coverage area of the current network signal is given, and a cer-tain number of points are selected so that the coverage problem of the weak coverage area of the current network can be optimized after the new base station is built on these points, making the weak coverage area as small as possible. In this paper, data cleaning is carried out first to screen out weak coverage points whose Euclide-distance between the existing base station and weak coverage points is less than the threshold 10 and weak coverage points whose traffic volume is less than 1. The problem of location selection is determined as a mathematical planning problem of 0-1 pro-gramming. Then the simulated annealing algorithm is used to find the global optimal solution of the model.

1. 引言

移动通信技术发展迅速，运营规模越来越大，通信网络的进步更是日新月异。随着移动通信技术规模与5G技术的飞速发展，通信的带宽也越来越大，基站和天线的种类也更丰富，但是随之而来的技术缺陷是：基站能覆盖的范围越来越小，如此一来，在同样的覆盖区域内，对基站的数量的要求也越来越多，这无疑增加了成本。这使得通信网络的规划尤其是站址选择的问题变得更加复杂，要考虑的因素也更加多元。如何在有限成本的条件下实现基站覆盖范围以及信号强度最大成为了炙手可热的议题。

2. 建模前的准备

2.1. 数据准备

在建立模型之前，将收集到的弱覆盖点数据进行统计，弱覆盖点业务量区间分布表为表1所示。

Table 1. Weak coverage point traffic interval distribution

表1. 弱覆盖点业务量区间分布

从表1可以看出，96%以上的业务量集中在前1/3的弱覆盖点中，另外2/3的弱覆盖点提供了仅4%的业务量。为使得弱覆盖点的总部业务量达到90%以上，且简化后续模型的建立复杂度，本文将业务量小于10的弱覆盖点全部剔除。在剔除之后，剩余业务总量为96%，达到总业务量的90%以上。剩余弱覆盖点业务量分布热力图如图1所示：

Figure 1. Weak cover point traffic distribution heat map

图1. 弱覆盖点业务量分布热力图

为控制成本，我们规定新建站址与现有站址之间的门限应大于10，同时根据收集到的材料，绘制现有的基站分布图如图2所示。且对于每一个现有基站，以现网站址坐标为圆心以10和30分别为半径画圆，该区域即代表新建站址所不能出现的区域。

Figure 2. Current base station distribution map

图2. 当前基站分布图

通过观察图1和图2可以看到确实存在若干弱覆盖点被现有站址所覆盖的情况，故要使弱覆盖点总业务量的90%被规划基站所覆盖，则必须将现有基站与新建基站综合考虑，即规划基站中包含了现有基站与新建基站。

因此根据欧氏距离公式，计算二维平面上的距离。以现有基站为第一入手点，去除与现有基站距离小于10的弱覆盖点。

$\Vert b-b_0\Vert =\sqrt{{\left(x-x_0\right)}^2+{\left(y-y_0\right)}^2}\le 10$ (1)

2.2. 基于0-1规划数学规划模型的建立

基于0-1规划。建立带约束的基站规划模型：

决策变量：新建基站的坐标(x, y)。

目标函数：新建基站的总成本最低。

$\min f={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(10v_i{a}_i+v_i{b}_i\right)}$ (2)

其中v_i，a_i，b_i三者以及相互联系的含义如下所示：

$v_i=\{\begin{array}{l}0\left(候选基站i被选中\right)\\ 1\left(候选基站i没被选中\right)\end{array}$ (3)

$a_i=\{\begin{array}{l}0\left(候选基站i被选中\right)\\ 1\left(候选基站i没被选中\right)\end{array}$ (4)

$b_i=\{\begin{array}{l}0\left(候选基站i被选中\right)\\ 1\left(候选基站i没被选中\right)\end{array}$ (5)

约束条件：将现有基站与新建基站综合考虑，满足建立基站的基本要求

$a_i+b_i=1$ (6)

$\sqrt{{\left(x-x_i\right)}^2+{\left(y-y_i\right)}^2}>10$ (7)

$\sqrt{{\left(x-x_i\right)}^2+{\left(y-y_i\right)}^2}\le 30$ (8)

$\Sigma w_h=6350607$ (9)

基于以上条件，建立0-1规划数学规划模型。

3. 模拟退火法求动态规划模型

3.1. 模型建立

模拟退火算法是局部搜索算法的拓展，也是一种通用概率演算法，从理论上来说，它是一个全局最优算法 [1] 。利用模拟退火法讨论基站选址的最优解问题，因为在面对弱覆盖点较多，基站选址较多时，动态规划模型求解的过程变得复杂，计算结果变得繁多，因此我们优先选用模拟退火法。

求解最优基站选址的模拟退火算法模型如下描述：

1、通过循环反复迭代产生新解，在降温的过程任一温度下通过随机扰动产生新解，并计算目标函数值的变化，决定是否被接受 [2] 。

2、再一次通过循环，为缓慢降低温度的循环迭代过程，指在步骤1结束的情况下将固定温度缓慢降低而得到的新的迭代解。

3、在步骤1中我们应该提高初始温度，使得在E增大时，初始解能够有更大的概率被接受为正确解，排除边缘最小值，得到更加准确的解。当然我们也不排除范围边缘也存在符合要求且较优的点，但是根据题目只需要找出全局最优解即可，因此在输出时只需将边缘最小值得到的解与多次迭代产生的最优解进行比较，输出最优解。

模拟退火算法与初始值无关，算法求得的解与初始解状态(算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。但是退火的过程却由一组初始参数(即冷却进度表)密切调控，目的时在较短时间内接近最优解。冷却进度表包括：

• 控制参数的温度初值T₀：温度初值；

• 控制温度参数T的衰减函数：退火过程中一系列温度取值函数；

• Markov链的长度L：即温度T的迭代次数；

• 控制温度参数T的终值。

• 模拟退火法求解流程图如下图3所示。

Figure 3. Simulated annealing method to solve the flow chart

图3. 模拟退火法求解流程图

收敛的一般性条件：

• 初始温度足够高(阈值不同，要根据具体问题具体分析)；

• 热平衡时间足够长；

• 终止温度足够低；

• 降温过程足够缓慢。

3.2. 模型求解

冷却进度表的初值设置(表2)：

Table 2. Cooling schedule

表2. 冷却进度表

利用MATLAB进行编程求解，进行模拟退火法迭代求解，迭代结果如图4所示：

Figure 4. Iterative results of simulated annealing method

图4. 模拟退火法迭代结果

经规划，现有基站与新建基站共覆盖弱覆盖点总业务量为6,365,476.37，占弱覆盖点总业务量的90.21%。规划基站共有1012个，其中现有基站有805个，新建基站的数量为207个。各规划基站坐标如表3所示。

Table 3. Partial site coordinates

表3. 部分站址坐标

微基站与宏基站选址建立后的可视化如图5与图6所示。

Figure 5. Macro station distribution visualization

图5. 宏基站分布可视化

4. 模型的改进

4.1. 模拟退火法模型的缺点

• 模拟退火算法收敛速度慢，执行时间长，算法性能与初始值有关。由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。整体比较耗时 [3] 。

• 模拟退火算法有可能陷入局部最优。

经了解，模拟退火法仍存在一定的缺陷，为弥补此类缺陷，可以将模拟退火法进行一定优化，引入人工鱼群算法，将无线网覆盖模拟为鱼群觅食行为。

Figure 6. Microbase station distribution visualization

图6. 微基站分布可视化

4.2. 改进人工鱼群模型的建立

人工鱼群算法是李晓磊等人在2002年提出的群智能优化算法 [4] ，该算法的核心本水域中营养物质最多的地方也就是鱼群最多的地方，该算法根据模拟水域中鱼群的觅食行为从而实现寻优。将该算法应用于本题其核心即变为：弱覆盖点最多的地方也就是基站最多的地方。由李晓磊等人提出的传统的人工鱼群算法包括鱼的觅食、聚群以及追尾行为，但本文除了需要考虑新建基站的覆盖范围与成本、弱覆盖点的分布以外还需考虑到各站点之间的门限应大于10。

传统的人工鱼群算法通过觅食、聚群以及追尾行为并不能解决站址之间门限大于10这个要求，于是本文改进了传统的人工鱼群算法，仿照李晓磊等人的研究引入了鱼群的逃逸行为来满足各站址之间的门限大于10。

5. 结论

随着互联网时代的快速发展，信号覆盖已经成为一个备受关注的问题，只有找到更合适的方法，优化信号覆盖问题，在控制成本的情况下建立更少的信号站且拥有更大的覆盖比例与覆盖范围可以有效地满足人们的日常生活的必要，并且可以有效地提升基站网络服务质量。

基金项目

北京市级大学生创新创业训练计划课题(10805136023XN262-289, 10805136023XN262-295)。