智能节点组网中的基站最优布置研究

Research on Optimal Deployment of Base Stations in SmartPoint Nodes Networking

摘要: 在野外组网过程中，需要通过部署基站，建立与工区中智能节点的通信连接，从而实现智能节点自动回传地震数据的功能。为了节省成本，需要对工区中的基站进行最优化布置。针对无障碍地形，本文用蜂窝覆盖模型进行基站布置，得到无障碍工区所需基站的个数及各个基站的位置坐标；针对有障碍地形，本文在无障碍地形基站布置的基础上，利用贪心算法进一步得到有障碍地形基站布置的结果。本文实现了用最少的基站覆盖工区中所有智能节点的目的，有效减少了预算成本。不同地形情况进行不同的算法设计，使得基站最优布置算法具有更为广泛的适用性。

Abstract: In the process of field networking, it is necessary to deploy the base stations to establish the communication connection with the SmartPoint nodes in the working area, so as to realize the function of automatically sending seismic data back to the SmartPoint nodes. In order to save cost, it is necessary to optimize the base station deployment in the working area. Aiming at the accessible terrain, the paper used the cell coverage model to arrange the base stations, and obtained the number of base stations required by the accessible work area and the position coordinates of each base station. Aiming at the terrain with obstacles, based on the base station deployment of accessible terrain, the paper applied the greedy algorithm to further obtain the result of base station deployment of terrain with obstacles. This paper realizes the purpose of covering all smart points in the working area with the least base stations, and effectively reduces the budget cost. Different methods are used for algorithm design under different terrain conditions, which makes the optimal deployment algorithm of base stations more widely applicable.

1. 引言

为了实现智能节点地震数据的自动回收，终端和智能节点之间的通信需要通过部署基站来建立连接。在野外组网的过程中，合理的基站布置方案尤为重要，若基站的数量过少，会导致信号的覆盖率偏低，不能满足工业需求，若基站的数量过多，则会造成成本浪费。

目前，关于基站选址方法的研究很多，主要可以分为三类：一类是数学规划方法。基站选址问题本质上是一种多目标优化问题，需要全方面兼顾考虑成本、覆盖范围等多个因素，因此研究人员常利用数学规划的方法进行求解，主要方法是利用动态规划方法 [1]、整数规划 [2] 及聚类策略 [3] 等，直接进行数学计算，寻求合适的基站布置方案。另一类则是通过智能计算的方法，如在遗传算法 [4] [5] [6]、免疫算法 [7] [8]、粒子群算法 [9]、模拟退火算法 [10]、鱼群算法 [11] 等算法的基础上，进行进展布选址的相关研究；谢庆喜 [12] 在基站选址的数学模型中，采用METROPOLIS采样与膜计算的微粒群算法进行模型设计。根据研究者的不同需求，采用不同的智能算法进行研究，可以取得良好的效果。还有一类是从电信及通信的角度来分析选址问题，郑俊杰 [13] 从最初的规划布局、到选址的管理及进一步站址规划的优化三个方面进行统筹分析研究，保持网络结构的合理性与稳定性；刘丽萍 [14] 综合考虑覆盖面积、网络连接以及能量消耗等因素，对无线传感器的部署进行探讨；于佳 [15] 提出了一种电力系统中的TD-LTE网络规划流程，并进行了规划仿真。但是这些研究结果大多数都来自于电信相关领域的研究者，这些研究者在研究的过程中，主要将影响基站站址选择的一些专业因素考虑在内，如载波数目、路径损耗、天线方向角、链路预算等 [7]，在实际生产应用中，由于专业性太强造成基站布置方案可行性较差。同时，基站选址中的地形地貌因素也是不可忽视的内容。但目前，在关于基站选址的国内研究中，将地形作为考虑因素的相关研究非常少。国外学者Kamar [16] 在基站部署中，考虑地形、用户分布、用户需求、用户增长率等因素，将一个需要建站的目标区域用三个矩阵来代表，三个矩阵分别用来表示地形、业务需求和建站规划，结合这些因素，提出了一种新的选址方法，但是这种方法步骤繁琐，在实际应用中的可实施性不强。因此，针对不同地形进行基站布置的研究，提出一种便捷可行的最优布置方案是极具价值与意义的。

2. 基站布置模型

随着智能节点的研发逐步推进，投入生产使用还需要进行野外组网等相关工作。为了实现自动回收智能节点采集的地震数据，需要部署基站来实现终端与智能节点之间的通讯。本着节省预算成本的原则，希望用最少的基站覆盖全部的工区，因此建立合理有效的基站布置数学模型是研究组网过程中的基站最优布置的关键。

2.1. 无障碍地形基站布置模型

在无障碍地形上，基站的布置如图1所示，工区内基站的布置问题转化为数学问题，即为：对于给定的 $M\times N$ 矩形区域，用最少半径为 的圆对其进行完全覆盖。

Figure 1. Schematic diagram of networking deployment of accessible terrain

图1. 无障碍地形组网布置示意图

2.1.1. 模型的建立

在满足区域全覆盖的条件下，若想使得所用圆的个数最少，则需要尽可能充分利用每个圆所覆盖的区域范围，尽可能减小圆与圆之间的重叠部分。不失一般地，考虑三个圆相交的情况，如图2(a)中以 ${\text{O}}_1$ 、 ${\text{O}}_2$ 、 ${\text{O}}_3$ 为圆心的圆，目标是要使得其之间相互重合部分面积达到最小，又从图2(b)中可以看出，三圆重叠的面积比图2(a)中三圆重叠的面积更小。

(a) (b)

Figure 2. Schematic diagram of three circles intersecting: (a) Three circles intersect; (b) The covered area reaches the maximum

图2. 三个圆相交示意图：(a) 三个圆相交时；(b) 覆盖面积达到最大时

定理1 若三个半径相同的圆两两相交且覆盖面积最大，则三个圆必相交于一点。

证明：由图2显而易见，证明略。

定理2 若三圆两两相交于一点且三个圆的圆心围成等边三角形，则其覆盖面积最大。

证明：根据定理1，设图3中的圆 ${\text{O}}_1$ 、 ${\text{O}}_2$ 和 ${\text{O}}_3$ 相交于O点，每个圆的圆心到交点的距离均为r，则三圆的圆心必然在以 $\text{O}$ 为圆心r为半径的圆周上。要使得三个圆的覆盖面积最大，即使得阴影部分S1 + S2 + S3最小。又在同一圆中，则有 $\angle {\text{AO}}_1\text{B}+\angle {\text{BO}}_2\text{C}+\angle {\text{CO}}_3\text{A}=2\text{π}$。

$\therefore S_{扇形{\text{AO}}_1\text{B}}+S_{扇形{\text{BO}}_2\text{C}}+S_{扇形{\text{CO}}_3\text{A}}=\text{π}{r}^2=S$，则 $S_1+S_2+S_3=S-S_{六边形{\text{AO}}_1{\text{BO}}_2{\text{CO}}_3}$。要使得阴影部分面积最小，则需让六边形 ${\text{AO}}_1{\text{BO}}_3{\text{CO}}_2$ 面积最大，即使得 $\Delta {\text{O}}_1{\text{O}}_2{\text{O}}_3$ 面积最大。又因为 ${\text{O}}_1$ 、 ${\text{O}}_2$ 、 ${\text{O}}_3$ 共圆，所以当 $\Delta {\text{O}}_1{\text{O}}_2{\text{O}}_3$ 为等边三角形时面积最大，即得证。

Figure 3. Schematic diagram of overlapping area of three circles

图3. 三个圆重叠面积示意图

综上，根据定理2可知，当覆盖的面积达到最大时，三个圆的圆心构成了等边三角形。如图4所示， $\angle {\text{CO}}_7\text{D}=\frac{\text{π}}{3}$，由一个圆与六个相同半径的圆相交构成了一个正六边形，如此相互叠加覆盖便形成了以正六边形为单位的覆盖模型，即蜂窝覆盖模型。

Figure 4. Cellular coverage model

图4. 蜂窝覆盖模型

Figure 5. Flowchart of base station deployment algorithm of accessible terrain

图5. 无障碍地形基站布置算法流程图

2.1.2. 模型的求解

根据上面建立的蜂窝覆盖模型，在 的矩形区域内，求解得横向所需正六边形的个数：

$M=\{\begin{array}{l}\frac{m}{\sqrt{3r}},\frac{m}{\sqrt{3r}}-\left[\frac{m}{\sqrt{3r}}\right]=0\\ \frac{m}{\sqrt{3r}}+1,\frac{m}{\sqrt{3r}}-\left[\frac{m}{\sqrt{3r}}\right]>0\end{array}$ (1)

计算纵向所需正六边形个数：

$N=\{\begin{array}{l}2\times \frac{n}{3r},\frac{n}{3r}-\left[\frac{n}{3r}\right]=0\\ 2\times \left[\frac{n}{3r}\right]+1,\frac{n}{3r}-\left[\frac{n}{3r}\right]\le \frac{1}{3}\\ 2\times \left[\frac{n}{3r}\right]+2,\frac{n}{3r}-\left[\frac{n}{3r}\right]>\frac{1}{3}\end{array}$ (2)

则所需正六边形总个数：

$Q=\{\begin{array}{l}M\times N,0<\frac{m}{\sqrt{3r}}-\left[\frac{m}{\sqrt{3r}}\right]\le \frac{1}{2}\\ M\times N+\{\begin{array}{l}\frac{N}{2},\text{N}为偶数\\ \frac{N-1}{2}\text{,}\text{N}为奇数\end{array}\end{array}$ (3)

在式(1) (2) (3)的基础上，得到覆盖矩形区域所需正六边形的个数以及各个正六边形的中心点坐标。将此结果转化到实际中，即得到工区全覆盖所需基站的个数及各个基站的位置坐标。

根据上述建立的模型，进行C++算法的设计，得到无障碍基站布置的算法流程图(图5)。

2.2. 有障碍地形基站布置模型

在基站的部署过程中，并不都是一马平川的地形。在实际的野外施工现场，经常会遇到地势十分复杂、存在各种地形障碍的工区，如存在河流、大山等无法逾越的障碍，在这些障碍处是无法架设基站的。因此，需要根据实际地形情况，合理布置基站，在节省成本的前提下，尽可能多的覆盖工区中的智能节点，如图6所示。

Figure 6. Schematic diagram of networking deployment of terrain with obstacles

图6. 有障碍地形组网布置示意图

2.2.1. 模型的建立

在解决实际问题的过程中，很多时候只能求得一个近似解，并不能得到一个精确解。而贪心算法是设计近似算法时经常使用的一个方法。贪心算法，又称贪婪算法，在求解问题时，总是做出在当前看来是最好的选择，文献 [17] 中便利用贪心算法对无线可充电传感器的静态充电策略进行动态规划设计，并取得了良好效果。贪心算法作为动态规划的一种方法，它的基本概念 [18] 如下：

首先构建一个解的集合 ，并定义得到集合上的一个适当的势函数 $f(.)$ ；

从 $\text{A}=\text{<menclose notation="updiagonalstrike"> O </menclose>}$ 开始，在 中增加一个能使势函数 $f\left(A\cup \left\{X\right\}\right)$ 达到极值(最大值或最小值)的元素，逐渐扩充 这个解集合；

当 $f\left(A\right)$ 达到极值(最大值或最小值)时，算法终止。

贪心算法在解决问题时，策略者仅根据当前已有的信息做出选择，只要做出了选择，不管将来发生什么，都不会再改变这个选择。当一个问题的最优解包含其子问题的最优解，即此问题具有最优子结构时，便可以用贪心算法来求解。虽然贪心法不是从全局最优的角度考虑问题，它只是在某种程度上的局部最优选择，这种局部最优选择并不能保证最终一定是全局最优解，但在实际应用中，通常能得到较好的近似最优解。由于贪心算法步骤简单，决策高效，因此在实际生产中被广泛应用。

有障碍地形基站的部署问题，显然是一个具有最优子结构的问题，因此便可以依据贪心算法的思想来进行求解，建立有障碍地形基站布置算法模型的具体步骤如下：

步骤1 将有障碍地形看作无障碍地形，利用2.1节中无障碍地形基站布置的算法，得到各个基站的坐标(称为集合A)，再将所求的位于障碍区域中的基站从集合A中去除，得到集合B；

步骤2 找出所有未被任何基站覆盖的节点(称为集合C)及障碍物的边界点(称为集合D)；

步骤3 遍历集合D，找到所有可以作为基站的边界点作为备选基站(称为集合E)；

步骤4 遍历集合E，找出能覆盖最多未覆盖节点的备选基站；

步骤5 将步骤4中找到的备选基站坐标放入集合B，将该基站从集合E中去除，并将该备选基站覆盖的节点从集合C中去除；

步骤6 重复步骤4和步骤5，直到集合C为空或集合个数不再减少，则集合B就是工区全覆盖所需基站的个数及各个基站的位置坐标。

2.2.2. 模型的求解

根据上述建立的模型，进行C++算法的设计，得到有障碍基站布置的算法流程图(图7)。

3. 基站布置仿真结果

3.1. 无障碍地形基站布置结果

无障碍地形基站部署过程中，实际工区四个顶点的大地坐标分别为：

右下：(545882,3254658)；左下：(548849.755809,3259797.04261)；

左上：(569535.179580,3247857.376785)；右上：(566567.423771,3242712.334123)。

基站覆盖半径 $r=1000\text{m}$。

利用2.1节中无障碍地形基站布置模型，运行算法程序可以得出此工区所需基站个数及坐标，具体仿真结果如图8所示。

3.2. 有障碍地形基站布置结果

有障碍地形基站部署过程中，实际工区四个顶点的大地坐标为：

右下：(720492,3229387)；左下：(712262,3234100)；

左上：(718826,3245490)；右上：(726971,3240671)。

基站覆盖半径 $r=4000\text{m}$。

Figure 7. Flowchart of base station deployment algorithm of terrain with obstacles

图7. 有障碍地形基站布置算法流程图

Figure 8. Result diagram of base station deployment of accessible terrain

图8. 无障碍地形基站布置结果图

(a) (b)

Figure 9. Result diagram of base station deployment of terrain with obstacles: (a) Results presentation of hexagon; (b) Results presentation of circular

图9. 有障碍地形基站布置结果图：(a) 正六边形结果显示；(b) 圆形结果显示

利用2.2节中有障碍地形基站布置模型，运行算法程序可以得出此工区所需基站个数及坐标，具体仿真结果如图9所示(四边形阴影区域为障碍地形区域)。

4. 总结与展望

本文从实际角度出发，针对无障碍地形和有障碍地形两种情况，分别考虑基站布置问题。由于用正六边形近似基站发射的信号范围时，两个基站发射信号的重叠部分最小，因此利用蜂窝覆盖模型求解无障碍地形的基站布置。基于贪心算法的思想，进一步设计有障碍地形基站布置的算法，两种算法均达到了用最少的基站覆盖最多智能节点的目的，同时，也进行了相关的软件模块集成，具有明显的实际效果，为野外组网过程中基站的最优布置提供了指导方法，具有一定的实际意义。然而，有障碍地形的算法在设计过程中，需要已知明确的障碍区域，而在实际生活中，障碍区域的精确识别并非易事，也并非所有的障碍物都能在基站布置前被识别并定位出来，因此，此算法还有待进一步改进，设计更加合理、简便的算法，让基站的最优布置方法具有更为广泛的适用性。