基于几何算法的无线站址自动规划方法研究及实现

王世魁+张红霞+宋文韬+范云强+王欣玥

【摘 要】为了解决目前对于手动无线站址规划及设计中的错误及误差问题，通过基于三角几何的方式引入多种自动规划方法，介绍了各种规划算法的操作过程及优缺点，选定了外接圆自动规划算法并利用软件加以实现，选取某省市数据试验验证了该算法能够较好地满足实际工作需要。

【关键词】三角几何 无线站址 自动规划

doi：10.3969/j.issn.1006-1010.2017.08.013 中图分类号：TN929.53 文献标志码：A 文章编号：1006-1010（2017）08-0064-05

引用格式：王世魁，张红霞，宋文韬，等. 基于几何算法的无线站址自动规划方法研究及实现[J]. 移动通信， 2017，41（8）： 64-68.

Research and Implementation of Base Station Location Automatic Planning Based on Geometric Algorithm

WANG Shikui ZHANG Hongxia SONG Wentao FAN Yunqiang WANG Xinyue

[Abstract] In order to deal with the mistake and the error in manual wireless site planning and design， the multiple automatic planning methods were introduced based on triangular geometry. The operation processes， advantages and disadvantages of different planning algorithms were introduced. The automatic planning algorithm based on circumcircle was selected and implemented on software. The algorithm was validated by the data in a certain province that it can meet the requirements of practical work.

[Key words]triangular geometry base station location automatic planning

1 引言

目前對于无线站址规划及设计工作，仍以区域预测及手动布点为主，而手动布点势必引入操作错误或误差，为实际的规划设计工作带来诸多不便。交底的无线站表一经确定将难以再做调整或增减，在紧张且有限的时间窗口里，对站点位置的规划提出了很高的要求，手动规划的易错、不够精准等特点造成的站址不合理，只能通过后续的参数设置、网络优化等去消化，同时会进一步加剧网络结构的不合理。

本文通过基于三角几何的方式引入多种自动规划方法，并结合站址分布的实际应用，提出自动规划算法并通过C#编程语言进行了实现，为后续由于其他原因导致的站表调整及修改提供第一版站址原型。

2 无线站址的自动规划

讨论自动规划问题，首先应将具体的实际问题抽象、映射成某种数学问题，单纯地考虑基站位置，可将基站抽象为点，站址结构问题转化为数学几何问题，几何问题的思考势必从三角结构开始。物理站址等效为抽象的点示意图如图1所示。

2.1 构建站址三角网

将现有站点数学抽象为初始点集，通过各离散的点构建三角形网络，三角网的构造有多种方式，这里采用最常用的Delaunay三角网。Delaunay三角网由三个相邻点连接而成，是相互邻接且互不重叠的三角形集合，具有明显的特点。每个三角形的外接圆内不包含其他的离散点，称为空圆特性。

最大化最小角特性，即指两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大，保证构造的三角网最小角最大，此特性使得Delaunay三角网更接近于规则化，如图3所示，右侧三角形构造更优。

按照以上原则进行三角网构造，最终的网络结构结果是唯一的。

新增、删除、移动某一个顶点时只会影响相邻的三角形，即区域性。此特性将为自动规划后的站表手动调整提供理论依据，如图4所示，删除节点8引起红色线段的变化，由2、3、4、5、7节点构成的区域外未引起波动。

2.2 站址自动规划方案比选

在对现有站址完成三角网构造的基础上，将按照一定的原则进行新站址的自动生成，自动规划存在多种方式，每种方法各有其优缺点，下面进行各方案的探讨。

（1）邻边判断法

此方法的主要过程如下：

1）选取任一点作为计算的起始点，并以此点为中心依次判断其与相邻点的距离。

2）若两点距离满足新站址条件，则记录此点或多个点并生成新点，新生成点尽可能选取在两点中间。生成单点时，则位于线段中点，生成n多点时，位置选在线段n-1点上。若两点距离不满足新站址条件，则不作操作并计算下一个相邻点。

3）按照新站址重新构造三角网。

4）重复2）、3）两步，直到所有点均满足距离要求则停止计算。

（2）内切圆法

此方法的主要过程如下：

1）选取任一三角形作为起始计算点，寻找并勾画此三角形内切圆。

2）计算内切圆半径，若半径满足一个站的新站址条件，则新增点的位置就是此内切圆的圆心。若半径不满足新站址条件，则不作操作并计算下一个三角形。

3）按照新站址重新构造三角网。

4）重复2）、3）两步，直到所有点均满足距离要求则停止计算。

（3）外接圆法

此方法的主要过程如下：

1）选取任一三角形作为起始计算点，寻找并勾画此三角形外接圆。

2）计算外接圆半径，若半径满足一个站的新站址条件，则新增点的位置就是此外接圆的圆心。若半径不满足新站址条件，则不作操作并计算下一个三角形。

3）按照新站址重新构造三角网。

4）重复2）、3）两步，直到所有点均满足距离要求则停止计算。

以上几种方法分别具有其数学意义及实际意义。从数学角度看，不同的几何特征进行差值运算，不同的方法复杂程度不同，同时其迭代次数也有差异。从站址规划的实际应用角度看，站址分布的均匀程度越高，则实际价值越大。表1列举了几种方法的优缺点，通过对比，选取外接圆法作为自动规划的算法方案。

无论通过哪种自动规划的算法生成的新站址都需要进行校准，即进行新增点的合理性判断。通过若干次的迭代算法会逐层生成新站址，最后需要对全部的站点进行合并、删除等处理，对于多点的合并采用外接圆逐渐逼近的方式，最后给出唯一点。

对于规划区域的外边界，无论选定的边界如何，均采用最外围基站所构成的凸多边形加设定距离作为实际的边界，目的在于尽可能降低由于边界不合理引起的边界布点错乱。

2.3 站址自动规划的实现及验证

确定了核心的外接圆规划算法，在Microsoft Visual Studio.NET Framework环境下主体采用C#语言进行软件开发及算法实现，形成最终软件，即BePoint。软件采用应用层、业务逻辑层、基础数据层三层架构，单机版开发，考虑实际工作需要，软件支持脱网工作，软件的系统结构如图8所示。

无线站址自动规划功能作为BePoint软件整体功能的重要组成部分，主要包括基础数据处理功能、规划区操作功能、自动规划功能、GIS交互四大部分。基础数据处理实现数据的导入、导出、入库、格式化、清洗等；规划區操作功能实现规划区的绘制、导入、属性编辑、参数设置等；自动规划功能采用内置外接圆算法实现迭代规划；GIS交互提供人机交互界面，实现地图、站址、规划区的放大、缩小、拖拽、新增基站、删除基站、编辑基站、查询、测距等常见GIS功能。

为了验证算法的正确性和有效性，以广州市某区域规划为例，着重考虑规划过程中与算法相关的小区位置因素。收集现网站表数据，现网LTE网络共计1518个小区，均为F频段，对于不同的频段建设集团公司已有相应的建设指导原则和成熟的经验值。软件中此部分可手动进行配置，此次验证中设置为F频段站间距为500 m，软件中通过对规划区的属性——规划区的场景类型来关联此值。规划区的手动绘制采取尽可能贴近站址轮廓的外层边缘，减少算法对空白区域的无效运算，规划区除了5个不集中站点外包括了其他的全部数据。自动规划过程采用无限迭代方式，直到满足站间距设置的停止条件，整个验证过程如图9所示。

对输出新旧站表进行GIS呈现，可见新建站点均匀分布在原站点间，使用标尺测量可保证任意两点间距离大于初始设定的500 m，计算后生成新小区7896个，进一步分析发现原站址分布疏密不均，统一的间距导致原稀疏区域插值较多。而稀疏是由于该区域不适合基站建设，关于此部分，将有三维地图数据进行二次验证并剔除，形成瘦身后站表，此部分功能由地形地貌识别模块完成，不在本文讨论范围内。综合来说，采用外接圆算法能够实现站址的自动规划。

3 结束语

在三角几何的基本思路基础上，通过引入外接圆自动规划算法进行站址的自动规划能够很好地满足自动规划需求，降低手动布点的人为出错率，同时填补了目前市场尚未有自动规划至站址级别算法及软件的空白。后续将持续进行算法的优化并将更多因素纳入到站址规划的考虑范围。

参考文献：

[1] 王映民. TD-LTE技术原理及系统设计[M]. 北京： 人民邮电出版社， 2011.

[2] 谭云婷，熊珊. 基于空间相邻分析的基站数据模型与算法研究[J]. 移动通信， 2016（1）： 34-38.

[3] 应倩岚. 基于蜂窝网实测数据的基站位置与业务空间分布研究[D]. 杭州： 浙江大学， 2015.

[4] 唐宇亮. 基于GIS无线基站可视化系统的设计和实现[D]. 四川： 电子科技大学， 2014.

[5] 孙瑞雪. 蜂窝基站空间分布特性研究[D]. 天津： 南开大学， 2015.

[6] 高峰. TD-LTE技术标准与实践[M]. 北京： 人民邮电出版社， 2011.

[7] 刘宝昌，胡恒杰，朱强. TD-LTE无线网络规划研究[J]. 电信工程技术与标准化， 2010，23（1）： 16-20.

[8] 胡恒杰，赵旭凇，徐德平，等. TD-LTE无线网络规划若干问题探讨[J]. 电信工程技术与标准化， 2010，23（11）： 47-52.

[9] 赵训威. 3GPP长期演进（LTE）系统架构与技术规范[M]. 北京： 人民邮电出版社， 2010.

[10] 张晓. 3GPP LTE部分关键技术研究及系统级仿真验证[D]. 武汉： 武汉理工大学， 2008.

[11] 李树东. 基于博弈论的TD-LTE网络规划[D]. 大连： 大连海事大学， 2011.