基于遗传算法的机动通信站址自动规划方法

冀云刚 霍永华

摘要：针对山区复杂地形环境下机动通信网络站址选择需求，提出了一种基于遗传算法的站址自动规划方法。对机动通信网络站址规划需求进行了分析，确定了机动通信网络站址规划目标，通过对传统遗传算法在初始种群生成、选择操作等方面进行改进，以超短波电台为无线传输手段并结合实际组网实验，对算法进行了验证。结果表明，该算法在山区复杂环境下以超短波为传输手段的站址规划中具有较高的准确率，能够满足机动通信网络站址规划需求。

关键词：站址规划；遗传算法；ITU-R.P 526模型

中图分类号：TP393文献标志码：A文章编号：1008-1739（2022）14-48-6

0引言

机动通信网络是为了满足某种任务而临时开设的通信网络。与固定网络不同，机动通信网络一般不依托固定基础设施，多采用无线通信手段，一般采用“一事一规划”的方式。因此，网络规划是机动通信网络能否满足任务通信保证需求的关键。站址规划作为机动通信网络规划中的关键环节，从根本上决定了网络规划的可行性。站址规划已成为通信保障人员面临的主要任务，特别是在山区等复杂地形环境下，如何快速准确地进行站址选择，已成为通信保障人员亟待解决的关键问题。目前针对该问题，多采用人工规划方式，由通信保障人员利用无线覆盖分析工具，计算不同点位无线覆盖情况，并结合任务需求人工选择站址。整个过程花费时间长，无法有效满足机动通信网络快速规划开通的需求。

传统站址规划方法多基于几何原理来寻找适合的站点位置，如几何中心法[1]和外接圆法[2]等。近年来通过利用模糊推理[3]、聚类[4]和机器学习[5]等技术，使用粒子群算法、遗传算法和模拟退火算法等，将站址规划作为优化问题进行处理，较传统方法在资源使用数量、覆盖效果以及规划效率等方面有了较大的进步。文献[6]在TD-LTE基站规划中将基站数目作为优化目标；文献[7]在指定基站个数的情况下将覆盖率和通信质量加权聚合为优化目标，利用遗传算法进行基站规划优化；文献[8]利用多目标粒子群算法对基站覆盖率、网络效能比、网络负载和建设成本进行优化，解决了LTE混合组网优化问题；文献[9]基于NSGA-II算法实现对机动通信系统的站址规划。这些研究成果尤其是文献[9]中的研究成果对机动通信网络站址规划提供了很好的参考。但由于机动通信网络是面向任务临时开通的网络，与传统网络有着较大的区别，主要体现在所采用的通信手段、部署使用的环境和规划效率等方面。因此，需结合实际情况进行具体分析，选择适合的算法和规划流程，实现机动通信网络站址的快速规划，满足任务快速开通保障的需求。本文从机动通信网络快速规划开通的需求出发，提出了一种基于遗传算法的站址自动规划模型，通过对机动通信网络规划因素进行分析，选择优化目标，并通过参考历史选择结果，实现了一种自动站址选择方法，提升复杂地形环境下机动通信网络站址规划效率。

1机动通信站址规划

1.1站址规划需求

机动通信站址规划是根据任务保障需求，在某个区域内选择合适的点位，利用有无线等各种通信手段形成能够覆盖各用户的骨干网络，满足不同用户间的信息交互需求。

根据组网需求的不同站址规划约束也不相同，大致可分为区域互通和区域覆盖2种。区域互通是根据用户位置选择站点，形成互联网络，满足用户间信息交互需求。区域覆盖是在区域互通基础上的更高要求，除满足用户间信息交互需求外，还可支持用户通过任意站点接入网络。在只考虑区域互通的站址规划中，由于用户位置相對固定，因此通过选择合适的站点和站点间适合的通信手段，实现网络的互联互通即可，不需要考虑各站点的覆盖情况。针对用户机动接入的需求，在满足区域互通的基础上，还需要考虑各站点对用户的覆盖情况。由于区域覆盖可转化为多用户的区域互通，为简单起见在本文中只考虑区域互通需求。

1.2无线覆盖分析

无线覆盖分析是站址规划的基础，基于电子地图和无线电波传播模型，对地图上两点间的无线电波传播损耗进行预测，形成站点的无线覆盖分析结果。本文针对山区复杂地形环境和VHF无线传输手段，采用ITU-R.P 526模型计算直射、反射和绕射路径损耗。

在山区复杂地形环境下，有不同类型的损耗组合，包括直射、绕射和反射。山区环境下传播损耗计算流程如图1所示[10]。

1.3站址规划流程

典型的站址规划流程包括确定规划区域、站点预选和站点选择3个步骤。

（1）确定规划区域

确定规划区域是根据用户位置确定站址规划的区域，即确定站点的选择范围。该步骤一般由规划人员根据地图和实际任务情况进行人工选择。

（2）站址预选

站址预选是规划人员基于电子地图，在规划区域内选定若干个位置作为备选站点。根据任务需求，机动通信网络一般在山区等复杂地理环境下开通，站址选择需要考虑的因素较多，比如是否遮挡、能否到达以及能否展开等。受限于电子地图的精度，一般需要规划人员根据任务具体情况进行站址的人工预选，甚至针对某些特殊的任务，需要进行实地勘测，最终形成备选站址库。

（3）站址选择

站址选择是在备选站址库中选择适合的站址作为此次任务的通信站点，一般根据选择的无线通信手段，采用无线覆盖计算方式，分析各站点的无线覆盖范围，最终确定具体的站址。站址选择实际上是多目标优化问题，即如何从备选站点库中找出满足需求的最优的站点组合，也是本文需要解决的问题。

2遗传算法

遗传算法是一种以遗传进化理论为基础的启发式算法[11]。在遗传算法中，将问题潜在的解集作为初始种群，每个种群都是由一定数量的个体组成，每个个体通过一定的方式进行编码表示。初始种群经过不断迭代，并通过遗传算子的操作产生新种群，通过对当前种群个体的适应度进行评估，将其中优秀个体保留至下一代种群中。经过不断迭代，末代种群中的个体会比前代种群更适应所在环境。最后，末代种群中的最优个体就是目标问题的最优解[12]。遗传算法流程如图2所示。

主要流程包括：

①染色体编码，将问题空间中的解转换为遗传算法能够识别的数字串或字符串，以便于遗传算法中的交叉与选择操作。

②初始化种群，生成第一代种群，设置遗传算法相关参数。

③适应度评价，通过设置的种群适应度函数进行评估，评估当前种群中各个体对环境的适应度。

④通过选择、交叉和变异等操作不断产生新个体。

⑤判断个体的适应值是否满足当前结束条件，如果满足结束条件则结束进化过程，输出当前的最优个体，如果不满足结束条件，则返回步骤③，直到满足结束条件为止。

3基于遗传算法的站址规划算法

3.1问题描述

假设机动通信系统共有个备选站点，所有站点布设的通信车辆相同，即有相同类型的天线和数量，在进行站址规划时不考虑天线和设备之间的差异。根据无线传输设备性能指标、电波传播损耗和接收机灵敏度等参数，站点的最大可覆盖距离为。

3.6交叉变异设计

①选择操作：在本文中选择操作采用轮盘赌选择算子和精英保留策略相结合的方式，既保证每一代种群中优秀的个体有较大的概率优先参与后续操作，又能保证算法朝着最优解方向进化。

②交叉操作：随机选择种群中的2个解作为父代个体，按照一定的概率进行交叉操作。

③变异操作：对子代个体按照变异概率进行0/1取反变异操作。

3.7算法流程

4实验及结果分析

4.1实验准备

本文通过设计实例进行验证分析的方式，按照文中思路采用C++语言设计实现了站址規划原型，并以超短波电台为传输手段，选用山区地形环境进行2次验证，备选站点数量分别为12和17，用户数均为7，最大可用通信车辆数为9。实验环境为Windows7，Intel i5处理器，内存16GB，GIS系统选用国产某地理信息系统，地图比例尺为1：50 000，仅考虑经纬度和高程数据。规划结果结合系统实验进行验证。

4.2实验结果

（1）第1次实验结果

第1次实验选用山区地形环境1，备选站点数量为17，用户数为7，分别选用5辆和9辆通信车辆，站址规划时间分别为27，31 min，生成的规划结果与实际组网拓扑对比如图4和图5所示。（其中图4为5辆通信车辆的规划结果与实际组网拓扑对比，图5为9辆通信车辆的规划结果与实际组网拓扑对比。图中圆圈表示用户节点，空心三角表示备选节点，实心三角表示选中的节点。）

（2）第2次实验结果

第2次实验选用山区地形环境2，备选站点数量为17，用户数为7，分别选用5辆和9辆通信车辆，站址规划时间分别为39，43 min，生成的规划结果与实际组网拓扑对比如图6和图7所示。

经2次规划结果与实际组网结果对比，可以看出站址规划基本可满足实际使用需求，除个别站点由于无线覆盖计算结果不准确导致实际选择与规划不一致外，其余节点均可按规划结果布设通信车辆并开通网络。

（3）运行时间实验结果另外，在相同实验环境下，还针对算法的运行时间进行了实验，分别选用备选站点数量为12，17，21，25，用户数为7，通信车辆数分别为5和9，通过打桩输出方式分别记录无线覆盖计算算法运行时间和总时间。算法运行时间实验结果如表1所示。

站址规划运行时间主要包括无线覆盖计算时间和规划算法运行时间两部分，其中无线覆盖计算运行时间与地图精度有直接关系，与规划算法运行时间相比，无线覆盖计算时间占整个运行时间的70%以上。

5结束语

本文针对山区复杂地形环境下机动通信网络站址规划需求，采用基于电子地图的无线覆盖计算和遗传算法的站址规划模型，实现山区复杂地形环境下机动通信网络站址的自动规划，能够在一定程度上满足山区复杂地形环境下快速站址选择的使用需求。针对算法运行时间长等问题，后续可结合云平台等环境，采用任务并发执行策略，降低算法运行时间，提升整体效率。

参考文献

[1]焦良全，孙宜军，李广平.铁塔公司通信站址规划方法研究（I）[J].中国新通信，2016，18（ 6） ： 23-25.

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

[3] CHANG J Y，LIN Y S. An Efficient Base Station and Relay Station Placement Scheme for Multi-hop Relay Networks[J]. Wireless Personal Communications，2015，82（3）： 1907-1929.

[4]黄骅，江俊.基于聚类的无线网络基站选址优化算法研究[J].现代信息科技，2018，2（9）：50-52.

[5] ROMERO D，LEUS G. Non-cooperative Aerial Base Station Placement via Stochastic Optimization[C]//2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks （MSN）. Shenzhen： IEEE，2019： 131-136.

[6]李月.基于P系统的改进粒子群优化算法及应用[D].济南：山东师范大学，2017.

[7]谢庆喜.基于智能优化算法的基站选址优化问题研究与实现[D].济南：山东师范大学，2018.

[8]董宏成，王腾云. LTE混合组网中基于多目标粒子群的自规划[J].无线电工程，2019，49（10）： 893-898.

[9]颜陆红，郭文普，徐东辉，等.基于NSGA-II算法的机动通信系统站址规划方法[J].计算机应用研究，2022，39（1） ：226-230.

[10]孙威.基于电子地图的地域无线电波传播预测研究[D].西安：西安电子科技大学， 2010.

[11]陶郎.基于遗传算法的复杂背包问题模型优化方法研究[D].安庆：安庆师范大学， 2021.

[12]谢文晴.基于遗传算法的深度学习优化方法研究[D].哈尔滨：黑龍江大学， 2021.