基于免疫遗传算法的5G基站选址规划

谢许凯　程松林

摘  要：基站选址的规划，因其能够提高通信服务质量和降低新建基站成本而一直是学术界和业界关注的问题。文章综合分析了基站选址问题的目标、原则、方法和求解面临的困难，结合遗传算法和人工免疫算法的优点，建立了基站选址的数学模型。为避免遗传算法的“早熟”，在遗传算法中加入免疫的因素，仿真结果表明，该模型算法具有很快的收敛速度，在某一区域内需求已知的条件下可以提供一种有效的基站选址方案。

关键词：遗传算法;免疫算法;基站选址

中圖分类号：TN929.5;TP18       文献标识码：A 文章编号：2096-4706（2020）02-0004-03

Abstract：The planning of base station location，because it can improve the quality of communication service and reduce the cost of new base station，has been the focus of academia and industry. In this paper，the goal，principle，method and the difficulty of solving the location problem of base station are analyzed synthetically. Combining the advantages of genetic algorithm and artificial immune algorithm，the mathematical model of location problem of base station is established. In order to avoid the “precocity” of genetic algorithm，the immune factor is added to the genetic algorithm. The simulation results show that the model algorithm has a fast convergence speed，and can provide an effective base station location scheme when the demand in a certain area is known.

Keywords：genetic algorithm;immune algorithm;base station location

0  引  言

随着通信技术的飞速发展，越来越多的设备和终端接入了移动通信网络。为了满足对于日益增长的移动数据访问的需求，更高带宽和速率的5G技术应运而生。而5G技术的发展，即将带来的不仅仅是简单的网速提升，更标志着科技时代通信行业的又一次重大革新。目前我国大部分地区都建立了大量的4G基站，另外已有少数地区进行了5G网络的商用试点。随着未来接入5G网络的用户数量的增加，如何对5G基站进行选址布局来保证对服务区域进行有效的网络覆盖，从而提供可靠的通信传输服务是需要重点考虑的问题。

目前已有文献对于基站选址规划进行了相关的研究，文献[1]提出了室内、室外及盲区的覆盖方案;文献[2]从不同阶段分析了选址的技术要点;文献[3]建立了基站选址的数学模型，并基于遗传算法进行求解。遗传算法在解决此类大规模问题时容易陷入局部最优解，而免疫算法尽管效率不佳，但具有更好的多峰值搜索能力，特别是在多个极值点的情况下，可以快速地找到所有极值点，从而寻到全局最优解。本文结合了遗传算法的搜索特性和免疫算法的自适应特性，采用免疫遗传算法对于5G基站选址问题进行数学建模和求解，很大程度上避免了过早收敛于局部极值。

1  5G基站选址的数学模型

面对庞大数量的新建基站，网络优化和建设的代价非常大，因此在满足覆盖范围和网络容量的情况下，尽可能地降低建造成本，是基站选址规划的一个重要目标[4]。基站选址的原则是要尽可能满足理想的蜂窝结构，并优先考虑用户需求量大的热点区域[5]。为了方便构建数学模型，在此我们提出以下假设：（1）测试的区域不包括敏感区域，且都是理想的平地，无极端地形;（2）在MATLAB仿真时将基站和被测试点都看作点集，某个测试点被覆盖，则该热点区域被覆盖。

2  5G基站选址的算法流程

2.1  种群的初始化及编码方案

对于本文提出的数学模型，由于待选的基站位置只存在被选择和未被选择两种情况，我们采用二进制编码，抗体编码Ab表示为Ab={b1，b2，b3，…，bN}，其中N是待选基站个数，bi表示第i个基站被选择的情况：

2.2  抗体亲和度评价

上文中数学模型（1）是一个多目标优化模型，为了方便求解，将每个目标函数设置一个权重，将多个目标函数的优化问题转化成为求一个目标函数优化的最优解，即得到[7]：

2.4  选择交叉变异操作

本文在选择操作时采用轮盘赌的方法，即基于适应度权重和浓度权重的选择策略。在进行交叉操作时，新的抗体产生的速度与交叉概率成正比，交叉概率大时会导致搜索范围大，而当交叉概率过小时，可能会因为搜索过慢进而影响计算时长。此方法可以实现自适应交叉概率较优的解继续迭代运算，从而减少计算的时间复杂度[8]。在进行变异操作时，变异算子基于适应度进行调整，当适应度较大时，变异概率应当降低，以抑制变异，当适应度偏小时，应当提高变异概率，从而促进变异操作。

2.5  算法流程

免疫遗传算法流程如图1所示，基于达尔文进化论的自然选择和遗传原理，将问题的解做成一个由经过编码的基因个体组成的种群，在初代种群生成后，按照模拟自然界优胜劣汰的原则，对未满足亲和度要求的种群进行基因的交叉、变异，再加入免疫因素对其进行抗体的选择、抑制操作，生成新的“更适应环境”的种群，即更接近问题要求的近似解。末代种群经过解码后输出结果，即为最接近要求的近似解。

3  仿真实验与结果分析

3.1  仿真参数设置

本文算法仿真基于MATLAB2018b，在5km×5km的方形范围内随机选择31个测试点，测试点位置如图2所示，图中每个点代表一个测试点，并且不同的点对网络的需求量各不相同，假设从左往右、从上往下依次为：20，90，90，60，70，70，40，90，90，70，60，40，40，40，20，80，90，70，100，50，50，50，80，70，80，40，60，90，70，50，30。算法参数选择如下：种群规模为50，记忆库规模为10，迭代次数60次，交叉概率45%，变异概率33%。

3.2  仿真结果分析

采用本文算法进行优化迭代运算选址，最终在测试区域内求得7个最优基站位置，仿真结果如图3所示，其中被方块圈出的点即为可以覆盖31个测试点的基站最佳选址位置，与测试点相连的连线代表这个测试点被哪个基站覆盖。另外，最初假设的需求量不同会导致不同基站所涵盖的测试点数量也不同，需求量小的点和需求量大的点被合理安排，每个基站承担的需求量大致相同。从图3中可以看出，此时的选址方案较为合理，在保证覆盖到每一个测试点的同时，合理分配资源，不会出现某个基站因需求量過大而产生较差的用户体验。

算法收敛曲线如图4所示，由图4结果可知，本文提出的算法收敛速度快，同时具有遗传算法和免疫算法的优点，在保留遗传算法搜索特性的同时，又利用免疫算法的自适应特性，因此在5G基站选址优化问题上具有较好的参考运用价值。

4  结  论

本文讨论分析了5G通信基站选址的数学模型，并结合遗传算法以及免疫算法去求优化问题的解。但是本文模型仅仅考虑了基站建造成本、信号覆盖范围、网络容量这几个因素，在后续研究中可以考虑每个基站的传输半径等因素，使选址模型更加合理和实用。

参考文献：

[1] 张凌志.无线通信网络基站覆盖分析与基站选址设计 [J].通讯世界，2019，26（8）：198-199.

[2] 刘海锋.探析移动通信工程中的微波传输基站勘察选址要点 [J].中国新通信，2017，19（8）：1.

[3] 陈志涛，杨小东，苏钟.基于遗传算法的分时长期演进（TD-LTE）多目标站址选址方法 [J].科学技术与工程，2014，14（7）：29-33+44.

[4] 凌娟.基于混合免疫算法的TD-LTE网络基站选址优化研究 [D].杭州：杭州电子科技大学，2015.

[5] 王春蕾.基于改进粒子群算法的通信基站选址 [D].南京：南京邮电大学，2017.

[6] 李道国，李连杰.基于混合免疫算法的TD-LTE网络基站选址研究 [J].杭州电子科技大学学报（自然科学版），2016，36（5）：57-61.

[7] 牟晓晔.改进的并行遗传算法在基站选址中的应用 [J].电脑知识与技术，2010，6（33）：9529-9532.

[8] 李纪鲁，张晓，朱杰.基于自适应免疫算法的配送中心选址问题研究 [J].中国储运，2019（8）：141-144.

作者简介：谢许凯（1998.06-），男，汉族，上海人，2016级本科生，研究方向：电子信息工程;程松林（1983.05-），男，汉族，湖北黄冈人，讲师，博士，研究方向：网络信息论。