免疫优化算法在农村5G 基站选址中的应用

陈东园，刘 芬，冯立营，高雪苹，李保胜，刘晓倩

（天津职业技术师范大学电子工程学院，天津 300222）

近年来，我国大力发展第五代移动通信（5G）技术，基站建设数量以及用户数量一直位于世界前列。随着网络直播深入农村，网络作为直播带货最基础的“必需品”，必须要得到有效保障。5G 网络具有传输速度快、延时低等优势。5G 网络覆盖乡镇有助于推动乡镇经济发展，在振兴农村经济中起着至关重要的作用。目前，5G 信号在我国大城市覆盖范围广，但在农村等地势复杂的地方，因选址不易而导致5G 网络覆盖率并不高。因此，农村地区的5G 基站选址是一项难度较高、但又是极其重要的任务。

基站选址属于多目标优化问题，不仅要尽可能多地覆盖用户，还要考虑降低成本。针对选址问题，目前许多学者已经做了相关的研究。文献[1]针对原粒子群优化算法存在的早熟收敛和局部优化能力差的缺点，提出了一种改进的粒子群优化算法，并将其应用于通信基站的定位。实验表明，在考虑人口密集分布情况下，改进后的算法能够发掘出合理的基站坐标点。文献[2]提出利用贪婪算法求解基站规划问题，但贪婪算法存在易陷入局部极值的缺点，很难达到全局最优解。文献[3]提出了一种基于遗传算法的通信基站规划方法，对选址原则和影响因素进行分析，利用遗传算法寻找最佳建址位置，并在具体区域进行仿真模拟，验证了遗传算法的有效性。文献[4]分析了基站选址的优化目标和约束条件，采用了加权最小模理想点法，求解5G 网络基站的选址问题，主要思想是将优化目标代入算法进行仿真研究，根据权重的不同得出不同的建址方案，从而实现对选址优化问题的求解。多目标优化问题通常的处理方式有蚁群算法（ACO）[5]、粒子群算法（PSO）[6]、遗传算法（GA）[7]等群智能算法，但这些算法在迭代后期往往存在种群多样性减少的问题，而免疫算法具有自我调节功能，能有效保持种群的多样性，可以避免算法在寻优后期陷入局部极值。鉴于此，本文提出一种基于免疫优化算法的寻址方案。

1 农村5G 基站选址模型的建立

1.1 问题描述

5G 技术在经济发达的城镇地区普及较广，但在地形复杂，如山地、丘陵较多的农村地区覆盖率并不高。当前在农村地区普及5G 通信技术，要在指定区域内建立基站，需要提前开展基站选址工作。选址原则不仅要求基站总数尽量少，还要保证尽可能多地覆盖指定区域内的测试点（村庄）。

1.2 模型建立

在5G 基站选址模型中做如下假设：①5G 基站选址都在建设用地范围之内；②5G 基站选址已满足网络结构合理、网络覆盖原则以及安全性原则；③在Matlab 仿真时，把农村点和基站当作点集，任意1 个农村点被网络覆盖代表该农村点整个地方都已被网络覆盖。

基于以上假设，建立选址模型。从某一区域内的n个农村找出最适合建设基站的目标农村点，使资源合理分配，在满足5G 网络覆盖率高的情况下，尽可能降低成本。在本模型中，目标函数为建设基站所需费用与基站到各农村点的距离的乘积之和，其最小值即为问题的最优解，目标函数公式为

式中：N={1，2，3，…，31}为农村点的序号集合；i∈N，Mi⊆N；wi为建设基站所需费用；dij为从农村点i 到离其最近的基站中心j 的距离；Zij为属于0～1 的变量，代表农村点和基站之间的分配关系，当Zij=1 时，为农村点i 的网络由基站j 覆盖，否则Zij=0。

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

2.1 免疫优化算法

免疫优化算法（immune optimization algorithm，IA）是模仿生物免疫系统的工作原理提出一种智能搜索算法，最早由Farmer 等[8]提出有关免疫概念，并将免疫系统与其他人工智能方法联系起来。免疫优化算法具备良好的学习能力、记忆能力和模式识别能力，被广泛应用于无人机协同目标搜索[9]、车辆调度路线优化问题[10]、无线传感网络部署[11]等领域。本文利用免疫优化算法解决基站选址问题，在一定程度上扩大了其应用范围。应用免疫算法求解基站选址问题时，将选址问题当作免疫系统中的抗原，把可行性解看作免疫系统中的抗体（B 细胞），把可行解的质量看作生物免疫系统中免疫细胞与抗原的亲和力。文献[12]给出了免疫优化算法的实现过程，该算法同时具备保持种群多样性、全局搜索能力强、鲁棒性好的优势，在解决多峰函数问题时，可以有效防止陷入局部极值的问题，采用免疫优化算法进行农村5G 基站选址时，能够更合理且更快速地找出最优预测解。

2.2 初始抗体群的产生和编码

针对本文案例所提出的数学模型，抗原等同于要解决的问题，抗原识别等同于问题识别，对需要解决的问题仔细分析后，可以设计出满足问题的所有表达式。本文采用的编码方法为：将抗体编码表示为AV=（v1，v2，v3，…，vr），其中，vr（r∈N），N 表示基站数量。将每个5G 基站选址方案都可以看作一个长度为N 的抗体，每个抗体代表5G 基站选址选择的序列。选择一个模型包含35 个需求点，从中选择10 个作为5G 基站位置，如代表需求点，则抗体[4，8，9，13，15，20，25，28，30，35]代表1 个可行解向量，其表示4、8、9、13、15、20、25、28、30、35 被选为5G 基站选址位置。

2.3 抗体亲和度评价

本文为了使数学模型方便求解，需要将式（1）的多目标求解问题转化为单目标优化问题。则抗体亲和度函数[13]为

式中：Fv为目标函数；C 为较大的正数。

2.4 评价解的浓度

计算出抗体的浓度Cv，因为在免疫优化算法中，抗体浓度求解是至关重要的，直接影响到能否找到最优解。抗体浓度Cv表达式[14]为

2.5 期望繁殖概率

本文采用函数excellence 计算个体繁殖概率。在免疫优化算法中，在抑制高浓度个体时，容易导致最优解的丢失，因此采用精英保留策略[15]。每个个体的期望繁殖概率由2 个因素决定，一个是抗体之间的亲和力Av，另一个是抗体浓度Cv，表达式为[16]

式中：β 为常数。

根据以上公式可得出：个体的适合度与预期的繁殖概率成正比；个体浓度与预期的繁殖概率成反比。

3 仿真实验与分析

3.1 实验参数设置

依据农村5G 基站选址优化模型，本文在Window10系统、AMD 处理器4GB 内存的运行环境下，使用Matlab 2016B 版本绘图工具[17]进行仿真实验。为了验证免疫优化算法和数学模型的有效性，每一个农村坐标数据和用户的网络需求量数据都经过规范处理，但并不代表真实坐标和真实用户量。表1 详细列出了农村点的假设相对坐标及用户的网络需求。

本实验模拟了31 个农村位置，将表1 数据导入Matlab 软件中运行，用圆圈代表农村点，从这31 个农村坐标中选取适合做5G 基站选址的7 个坐标，以求达到减少选址成本、提高覆盖率的要求。模型按照免疫优化算法的步骤求解，参数设置为：种群大小sizepop=50，记忆库容量over best=10，最大迭代次数MAXGEN=70，交叉概率0.5，变异概率0.4，多样性评估参数90%。

表1 农村点相对坐标及用户用网需求量

3.2 实验结果分析

为了验证本文提出的免疫优化算法在基站选址问题中的实用性和有效性，本研究与基于遗传算法的基站选址方法进行了对比。5G 基站位置与农村点之间的关系如表2 所示。

表2 5G 基站位置与农村点之间的关系

基于免疫优化算法的选址方法得出的目标函数值（成本）为5.093 8×105，而基于遗传算法的选址方法得出的目标函数值（成本）为2.818 0×106。5G 基站选址最佳方案为[2，4，5，15，20，27，31]。基于免疫算法和基于遗传算法的仿真结果分别如图1 和图2所示。

图1 基于免疫算法的仿真结果

图2 基于遗传算法的仿真结果

图1（a）和图2（a）中分别被大圆圈和方框覆盖的点，即为农村5G 基站的最佳选址位置。从这2 幅图中可以看出，基于免疫优化算法的选址方案比基于遗传算法的选址方案更优。2 种方案虽然都能实现农村点全覆盖，但从图1（a）中可以看出，每个基站都被合理利用，基站到被覆盖农村点的距离最短，成本更低。而从图2（a）可以看出，基于遗传算法的选址方案存在资源浪费的现象，建设在村庄7 处的基站仅覆盖了2 个村庄，建设在村庄5 处的基站到村庄1 的距离太远，可能会导致村庄1 接收的网络信号较差等问题，从而使用户上网体验感较差。故采用本研究选用的免疫优化算法进行农村点5G 基站选址方案相对来说更好。

4 结 语

本文基于影响农村5G 网络选址相关因素及其特点，构建了农村5G 基站选址优化数学模型，采用免疫优化算法（IOA）对模型求解。从仿真结果可以看出，本研究算法具有较快的收敛速度，能够提供相对合理的农村5G 基站选址方案，为农村用户提供更满意的网络体验。本文在对农村5G 基站选址分析中，仅考虑了影响农村5G 基站选址的2 个因素，即基站建设成本和农村5G 网络覆盖程度，为了使模型更加贴近实际，影响基站选址的其他因素有待进一步研究。