基于混合遗传优化算法基站的最优分布

邓德鑫，葛寅辰，冯经纬，林若希，程乾开昱

（1.江南大学物联网工程学院，无锡 214000；2.江南大学商学院，无锡 214000）

1 引言

21世纪是一个信息技术快速发展的时代，第五代移动通信（5G）也悄然进入人们的视野。从第一代移动通信的基站还是现如今的第五代移动通信。移动通信的基站虽然发生了巨大的变化，但在基站的不断变化中，基站的合理分布始终是任意一个移动通信时代不得不考虑的一个问题。

基站是固定在一个地方的高功率多信道双向无线电发送机，被广泛地应用于低功率信道双向无线通信。随着通信技术的迅速发展，为了取得更快的通信速度和更好的通信质量，通信网络需要在原有的基础上不断的延伸和扩展，因此必须建设新的基站并且在原有基站上进行改造。基站的分布决定着通信的速度、质量以及建设的成本。合理的基站分布规划可以有效地降低成本、提高服务质量。

基站最优分布问题实质上也是多目标规划问题。目前国内外研究人员提出了很多方法来解决多目标规划问题。文献[1]采用传统的遗传算法对天线进行最优分布求解。虽然具有全局寻找最优的能力，但存在容易陷入局部最优解的问题。文献[2]采用NSGA-II算法解决基站分布优化问题，降低了算法的复杂度，但在交叉、变异过程中同代之间容易产生相同个体，从而限制了算法的搜索能力导致算法寻找结果很容易是局部最优解。

文献[3]采用了蚁群算法求解多目标规划问题，虽然蚁群算法具有较强的全局搜索能力但蚁群算法需要较长的搜索时间易出现早熟停滞现象。文献[4]采用改进的NSGA算法求解多目标规划问题，比原有的方法种群收敛性更好。差分进化算法（简称：DE算法）是一种以群体只能理论为基础模拟生物进化的优化算法，简单且高效的将适应环境的个体保存下来。差分进化以其较强的收敛能力、鲁棒性和强大的全局寻优能力使得该算法得到广泛的应用。

由于基站的分布问题较为复杂，容易陷入局部最优解所以本文结合了INSGA-II算法和DE算法的优点，使将两者的混合算法对基站最优分布进行求解，从而更有效的搜索最优解。

2 基于混合遗传算法的基站分布规划建模

在保证一块区域内可建基站的位置不变的情况下，怎样选择基站的坐落位置，从而使覆盖率最大，成本最低是一个多目标规划的问题。本文注重分析解决GPS基站分布规划问题。

2.1 基站分布规划模型建立

2.1.1 基站分布规划问题综述

基站分布规划问题实质上是一个多目标规划的问题。多目标规划就是多个优化目标在约束条件下同时得到最佳的解 。基于混合改进遗传算法和DE算法对问题进行求解，解决了INSGA和传统遗传算法的缺点，并且使算法在分布性和收敛性有所提高，搜索能力也有所提升[5]。

2.1.2 基站规划的理想假设

对于GPS基站的分布优化问题，为了方便分析问题的本质，注重主要因素，忽略次要因素作如下假设：

（1）基站发生的是以电磁波的方式向外辐射，电磁波主要以直射波的方式进行传播，在这里不考虑电磁波受到空气中的尘埃等物质影响下的反射和散射。电磁波在自由空间的传播损耗符合式（1）：

经过计算5G基站的覆盖半径大约100-300米左右，假设每一个5G基站的辐射范围是相等的为了方便计算均取值为200米。在一个基站辐射范围内的各点接受到该GPS基站信号强度是相同的。基站规划的区域假设为一个二维平面。在这个二维平面上随机设置基站的初始位置。在该区域内设置N个基站。设区域内的任意点为基站的坐标集合为则两点之间的距离为用的取值来表示B点是否被第i个基站所覆盖。如果点被覆盖则为1，如果点未覆盖则取值为0。即公式（2）：

只要点在任意一个基站半径范围内，则认为这点被覆盖，这些点的集合为P，则未被基站覆盖的点为则P点的构成的面积为Q。假设这块区域总的面积为S，则覆盖率为式（3）所示：

（2）在发射机和接受机之间因障碍物的复杂的地形，会产生多路径效应，不同的地形之间多路径效应的不同。位于地势较为平坦开阔的接收机多路径效应较小。又因为不同区域基站周围的环境不同，信号的噪声功率也不一样等。这些不确定因素影响着基站的性能。现将基站的性能进行性能假设，随机产生50-100之间的随机数来表示基站的性能。

（3）基站是一个物理设备，随着时间的推移，部分产品会产生老化损坏的现象。在较为恶劣的环境下，设备的更换周期较良好环境下短。经调研发现基站的建设资金相差不是悬殊。为了方便计算，将基站现实成本归化到5到15的数值。最后随机产生N个数值表示基站的成本。每一个点的成本记为

2.1.3 建立数学模型

混合遗传算法优化目标包括最小成本，最大覆盖率，SL表示表示基站的部署方案。

优化目标1：最小化基站建设维修的成本如式（4）所示：

优化目标2：最大化基站的覆盖率如式（5）所示：

最终找出可实行的方案如式（6）所示：

2.1.4 多目标进化个体之间的支配关系

设p和q是进化群体中的任意两个不同的个体，若满足对所有子目标函数，p不比q差，即且至少存在一个子目标函数，是的p比q好。即，使得其中m为子目标的个数。则称p为非支配的，q为被支配的。

2.2 算法实现

混合改进遗传算法的流程图如图1所示。

图1 混合INSGA-II和DE算法流程图流程图

步骤1：群体初始化：群体每个个体是在初始范围内的随机二进制数组合，使种群在演化时有充分的搜索范围。利用编码映射，建立种群。初始种群有M个体组成，每个个体的染色体由N个基因片段构成。

即初始化种群为

步骤2：对每一代内各体进行非支配排序。

步骤3：利用DE算法的交叉变异和复制。

交叉：为了增加干扰参数向量的多样性，引入交叉操作。则试验向量变为：

选择：为决定试验向量是否会成为下一代中的成员，DE按照贪婪准则将试验向量与当前种群中的目标向量进行比较。如果目标函数要被最小化，那么具有较小目标函数值的向量将在下一代种群中占有优势，下一代中的所有个体都比当前种群的对应个体更佳或者至少一样好。

步骤4：去除重复的种群个体，然后重组种群，再进行步骤3直到种群满足条件，退出循环，该种群就是最优解。

3 仿真结果与分析

为了验证算法的解决问题的能力，本文对于1000m×1000m的目标区域进行规划，为了简化分析，假设目标区域内平坦，采用全向天线覆盖面积为圆形，经过计算基站的覆盖区域为半径200米的圆形区域。参数如表1所示。

表1 仿真的部分参数

经过进化200代仿真结果如图2所示。

图2 混合遗传算法得到的基站分布

通过图1我们可以看出基于DE和NSGA算法求得基站位置分布合理，通过计算覆盖率高达93%。

图3 退火法得到的基站分布

在相同的实验仿真环境下，传统的退火法得到的结果如图3所示，经计算覆盖率只有85%。

为了验证混合遗传算法的处理基站分布问题的能力，在覆盖率和成本两个方面将它与传统的模拟退火法进行对比。

表2 不同迭代次数下两种算法基站成本及覆盖率

通过仿真结果对比可以看出，混合遗传算法在成本和覆盖率两个方面性能都优于传统退火算法。因此该方法具有很好的解决效果。

4 结束语

为了能保证更好的通信质量，本文采用一种基于混合DE和NSGA算法的基站规划优化的方法。该方法在基站分布规划中同时考虑了信号衰减，成本和覆盖率三个因素，设计了具体的实现流程，进行了仿真实验并与传统的模拟退火法进行了比较。仿真结果展示了基于混合DE和NSGA算法的方法的有效性。混合遗传算法能有找到最优的5G基站的分布方案。并且具有全局寻优的优势。合理的基站分布使得通信质量得到显著提高。因此基于混合DE和NSGA算法的基站规划的方法具有十分重要的实用价值和进一步的研究意义。