改进遗传算法在站址与小区工参联合优化中的应用

马力鹏，冀涵叶

（中国移动通信集团设计院有限公司，北京 100083）

0 引言

随着5G 技术标准的不断完善，以及大规模商用的不断推进，5G 无线通信技术正在逐步走进人们的生活中。作为新一代的通信技术，5G 将从传统的人与人之间的互联扩展到人与物、物与物之间的互联。相信随着应用方式的不断拓展，5G 技术在未来几年将会为个人、企业以及社会带来巨大的收益[1-2]。

相比于LTE 而言，5G 使用了更高的频段，导致信号传播损耗更高、衍射能力变弱，而解决这个问题的首选方式即为大规模的密集建站，去弥补覆盖上的缺陷[3-4]。而对于大规模建站，以及同时完成小区工参配置而言，一个好的站址规划与工参联合优化算法方案能够为运营商大大降低建站成本。本文针对这个问题给出了一种基于改进的遗传算法完成站址规划和小区工参联合优化配置模型。

在已有的文献中，基站站址规划问题得到了广泛的讨论与研究[5-9]。优化模型通常是通过生成初始随机解，然后利用邻近区域来完成的。如果相邻的解决方案优于当前的解决方案，则它采用该解决方案。否则，通过一定的规则从之前的解决方案中选取一组。基站选址的常用优化模型是基于元启发式方法，包括模拟退火（SA,Simulated Annealing）、禁忌搜索（TS,Tabu Search）、遗传算法（GA,Genetic Algorithm）和粒子群优化技术（PSO,Particle Swarm Optimization）等。

在基站站址优化中，模拟退火算法已被证明是一个好的方法[10-11]。SA 算法在搜索过程中，将基站在x 坐标和y 坐标方向上进行随机移动。当且仅当该新位置的价值函数更大时，才会接受该新位置。当所有基站具有新的可接受位置时，形成新的系统“状态”。该算法从新的状态开始继续进行迭代优化，并不断估计与该状态相关联的价值。然而对于高维搜索空间，尤其是多种物理量维度组成的高维空间，模拟退火算法收敛需要耗费大量的时间。

禁忌搜索同样也能够执行基站站址规划[12]。在对基站位置的局部搜索算法的比较中，TS 在多次运行中提供了最恒定的最终目标函数值。它以最少的基站数量最大化覆盖。然而，其极易陷入局部最优解，对于高维空间更是如此，故仅适合维度较低的组合解求解。

基于粒子群算法的基站站址规划，将目标区域分为若干个更小的区域，并为每个小区域编码，然后拼接形成代表大区域的粒子个体，通过迭代得出建站位置[13]，这种方法需要对地理区域进行细化分，才能满足5G 大规模建站需要。然而细分意味着组合解向量维度更高，对于大规模的离散组合问题，粒子群算法极易陷入局部最优。

基于聚类的遗传算法首先通过聚类完成初始种群选取，然后使用遗传算法完成站址规划[14]，这种方法局限于初始随机种群的优劣以及量纲单一的问题，仅对站址位置优化有效，无法完成对站址和小区朝向等不同物理量的参数联合优化，也即多量纲参数联合优化。

综上，对于已有的站址规划文献，仅仅是对于建站位置进行了组合求解。然而受限于高维度组合解的困难寻优，对于基站站址、小区工参等多种物理量参数进行联合优化的问题并没有给出相应的方案。本文借鉴最大期望算法的思想[15]，以及模拟退火局部搜索的思想，并结合遗传算法，将由不同物理含义或者不同量纲参数组成的染色体分步变异、分步交叉，迭代求解最优组合，以期达到覆盖和干扰的联合优化。在本文中，该算法简称为GAEM。为了能够在达到覆盖和干扰联合最优的基础上，同时满足小区容量需求，本文算法方案在每次完成覆盖的同时，还需要对容量进行评估。

1 大规模站址与小区工参联合优化方案简述

在无线通信网络中，一方面，对终端用户而言，信号覆盖强度（RSRP）以及覆盖区域信号的质量（SINR）对于感知非常重要，而决定这两个指标的关键有两点：（1）区域内每一个基站的建站位置；（2）区域内每一个小区的扇区朝向。而另一方面，于运营商而言，为了降低成本，同一区域内，基站的数量越少越好。如何寻求这二者之间的平衡，显得尤为重要。

假设一个基站有3 个小区，每一个小区均配备相同的波束，那么对于一个基站而言，需要优化的参数如下：(x,y,z,α1,θ1,α2,θ2,α3,θ3)，其中(x,y)表示基站的平面坐标，z表示基站小区的高度，(αi,θi)表示小区的方向角和下倾角。综上，对于一个配备3 个小区的基站，需要优化的参数有8 个，其中z轴不在优化范围内，为设定值。

针对这种高维向量优化问题，本文提出了一种基于遗传算法的改进算法，用以求解大规模站址寻优及小区工参联合优化问题。仿真实验表明该算法对高维向量、且对各维度物理量不一致的问题表现良好。同时，考虑到小区容量也对用户感知异常重要，所以本文也给出了一个估计容量的简单方法。站址与小区工参联合规划流程图如图1 所示：

图1 站址规划方案流程图

2 基于改进遗传算法的站址与小区工参联合优化

GAEM 算法完成站址规划的主要步骤如下所示：

（1）栅格化。获取目标区域地理位置信息，对于目标区域进行栅格化划分。一般情况下，室外栅格大小为建筑物栅格大小的整数倍，假设室内栅格大小为d×d，室外栅格的大小为kd×kd，其中k为整数；栅格的高度为1.5 m，对于建筑物，仅取每一楼层相对高度为1.5 m 以内的空间进行栅格划分。

（2）预规划。根据目标区域的大小预估计需要的基站数量，此步骤根据每一小区覆盖有效范围估算。

（3）基因编码。在本文中直接采用实数方式完成编码，编码方式示例如下：x1,y1,...,xn,yn,α11,α12,α13,...,αn3,θ11,θθ12,θ13,...,θn3，其中xi,yi表示基站i的坐标，i∈[1,n]，αi,j表示基站i的第j个小区的方向角，θi,j表示基站i的第j个小区的天线下倾角，本文中j∈[1,3]。

（4）种群初始化。假设通过预规划得到需要的基站数量为n，那么根据栅格化后的数据，随机为每一个基站分配不重复的位置；同时，初始化时固定每个基站小区的方向角为0、120、240，下倾角均为5°。拼接到一起形成一个单独的染色体个体，不断重复这个操作，最后得到整个种群，数量为2N。每个个体表示如下[x1,y1,…xn,yn,0,120,240,…5,5,5,…]。每一个小区的纵坐标值可通过栅格信息完成映射，非建筑物时，z=30 m，对于候选位置在建筑物内的栅格，如果建筑物高度超过30 m，那么z取建筑物高度，否则z=30 m。

（5）目标函数值。在站址规划任务中，以覆盖最优、信噪比最高为目标，目标函数表示为区域内所有栅格的平均RSRP 和SINR 值的加权平均，表示如下：

其中，γ表示RSRP 的权重，取值为0～1,；m为栅格数量。RSRPi和SINRi分别表示栅格i处的接收电平值以及信噪比值。默认，同一基站的三个小区覆盖栅格之间并无干扰。

（6）计算种群中每一个个体的目标函数值，并按照降序取最好的N个个体作为待优化的种群。

（7）变异。

对于传统的遗传算法，将编码后的染色体上的每一个基因进行变异，并作为新的个体，但这种方式仅针对基因之间物理量参数相同的情况有效，对于个体是由多种不同量纲物理量参数实数编码组成的情况效果一般。针对这种情况，本文提出了一种改进方式，也即分步变异，具体如下：

1）对于每一个个体，将基站坐标和小区方向角下倾角分成两部分，或者分为三部分：基站坐标、小区方向角、小区下倾角。如[(x1,y1,...,xn,yn),(α11,...,αn3,θ11,...,θn3)]或[(x1,y1,...,xn,yn),(α11,...,αn3),(θ11,...,θn3)]。

2）根据实际设置的迭代步数分为2k段或者3k段，k为整数。以2k段为例，假设迭代步数为100，那么可分为每20 步为一段，那么在这20 步内，前10 步迭代保持小区朝向角度不变，仅对基站坐标进行变异；后10 步迭代保持基站坐标不变，仅对小区角度进行变异。同时每次变异完之后保证新个体并不在种群中。如此迭代5 轮，输出结果。

3）对于坐标变异采取如下方式：生成-10d:10d:d的21 个数，随机选取两个数作为基站横纵坐标的变异量，同理随机生成-10:10:2 的11 个角度数，随机选取2 个作为小区方位角和下倾角的变异量，此处使用了模拟退火算法局部搜索的思想。

4）将变异得到的新个体和原来的个体合并为一个大小为2N的种群，计算每一个个体的目标函数值，并保留最好的N个作为下一步操作的对象。

（8）交叉。交叉过程同样遵循分步交叉法，对于每一个个体先保持小区工参（如无特别说明，本文指代小区天线方向角和下倾角）不变，随机选取个体的基因点位，然后在除自身外的种群中随机选取一个个体，并完成相同基因点位的交换；小区工参的交叉规则同样按此方式处理。

（9）当达到预设的迭代步数还未完成覆盖目标，如弱覆盖占比大于某一阈值，则自动增加1 个站，重新迭代计算；当弱覆盖占比小于某一阈值时，则停止站址和小区工参联合规划，然后进行容量评估工作。

3 容量评估

当站址规划完成后，需要对小区容量进行评估，以满足区域内终端用户的容量需求，小区容量计算的具体步骤如下：

（1）根据广播波束确定栅格的归属。对于每一个栅格，均需要计算出接收到每一个小区的RSRP 强度，然后选择RSRP 值最大的那个小区作为这个栅格的归属小区，当所有栅格均计算完毕后，即可得到每一个小区覆盖区域。

（2）根据业务波束计算栅格处的RSRP 值以及栅格受到邻区的干扰。对于每一个栅格均需要计算其接收到主服务小区的RSRP 值以及邻区的RSRP 值，并分别计算上行干扰和下行干扰。对于下行干扰，按照如下方式计算第i个栅格处的SINR：

其中，Si表示栅格i处接收到的主服务小区的RSRP 值，表示栅格i处接收到的j邻区的RSRP 值，N表示噪声。对于上行干扰，按照如下方式计算第i个栅格处的SINR：

其中表示j小区覆盖区域的几何中心到i栅格主服务小区的干扰功率。

（3）得到每个小区上行和下行的覆盖每一个栅格的SINR 值后，将其分别折算到MCS 等级表[16]中，得到流数v、调制阶数Qm以及目标码率R，并进一步计算得到小区每符号全带宽传输数据量大小：Ncell_sbl=NPRB×12*η*R*Qm*v，其中NPRB是物理资源块的数量，为定值。，表示考虑系统开销的业务信道资源。

（4）根据典型业务平均需求速率，折算小区用户每符号包的大小NUE_sbl，如表1 所示。

表1 业务类型数据表

表2 中，μ为速率均值，λ为间隔参数期望的倒数，均可从典型业务平均速率表中获得。

表2 每符号包大小转换表

（5）根据小区每符号包的大小和用户在典型业务中的每符号包的大小，即可得到小区每符号包容纳的用户数：

（6）小区覆盖区域内，使用用户密度乘以栅格个数估计小区覆盖区域的用户数，然后与计算得到的容量相比，即可确定小区容量是否满足。如果不满足，则加站重新进行站址规划，否则输出站址规划结果以及小区方向角和下倾角的参数配置。

4 仿真实验

4.1 仿真场景设计与参数配置

在本文方案验证过程中，设计了一个包含两栋建筑的区域。如图2 所示：

图2 仿真场景

图2 中，假设建筑物部分已经完成室内规划，在本文中并不考虑室内覆盖，故建筑物仅做信号遮挡作用。图2 中，覆盖区域为基站建站的区域，优化的任务是目标函数V最大化。本文中，站址规划阶段，采用区域栅格化的方式完成；在容量评估阶段，采用撒点的方式模拟终端，主要分为三部分用于小区容量评估，分别是轨迹用户、固定用户和随机用户。其中轨迹用户的移动轨迹为随机分配，且取轨迹中最差的30%样本点参与容量评估；固定用户是根据区域内用户终端位置分布统计得到的结果，在仿真中位置固定不变；随机用户是在覆盖区域内的非建筑物部分随机撒点。在仿真过程中，固定用户、随机用户和轨迹用户总数设置为1 000 或2 000，按照统计分布完成用户类型数的分配。仿真实验部分参数如表3 所示：

表3 算法模型仿真部分参数[17]

表3 中，频率、带宽、上下行时隙、SCS、小区天下发射功率、终端发射功率等均为固定参数值。RSRP 弱覆盖门限用于衡量弱覆盖比例，当弱覆盖占比小于1% 即可认为覆盖良好，并提前中断站址规划算法，进行容量评估。

4.2 结果与分析

在容量评估阶段，对于每个小区需要容纳的用户数可使用小区服务的栅格数与终端密度的乘积得到，在本文中分别对设置需要容纳用户数为1 000 和2 000 的情况进行容量评估。首先对于用户数为1 000 时，算法模型目标函数V随着迭代次数的仿真迭代结果如图3 所示：

图3 目标函数值V随着迭代次数的仿真变化图

图3 是GAEM 算法在站址和小区工参联合寻优达到满足覆盖（小于-110 dB 的栅格数比例小于1%）和容量的迭代结果图，同时也给出了目前主流的元启发式智能算法在任务中的表现。GA 图像和GA_ 算法图像均经过了平滑处理。从图3 可知，本文GAEM 方法可在短时间内达到一个稳定值，这主要归因于站址和小区工参分步变异、分布交叉的结果，这种方式相比于传统的GA 方式，在解空间维度较大的情况下，降低了陷入局部极值点的风险。其次，对于SA 算法，根据图像趋势，在迭代很长时间后，其结果有可能较GAEM 方法更优，但很明显产生了很大的时间消耗。TS 算法，由于其依赖于初始条件和邻域映射关系，更容易限于局部最优。对于PSO 而言，其本身更适合与连续型变量求解，对于离散的高维组合解，效果较差。在仿真过程中，当目标函数值V>0.85时，覆盖与容量已经满足了要求，按照这一指标，只有GAEM 方法和SA 算法能够达到要求，然而SA 算法所需时间更长。而其他算法，只能通过加站操作完成。表4 中给出了主要迭代节点的目标函数值对比表，仿真过程中，发现当目标函数V值达到0.85 时，覆盖和容量已经满足要求。对于各算法模型，仅GAEM 方法和SA 算法能够在迭代停止前完成最少基站的建站要求，而其他算法需要增加基站个数才能完成任务。对于本文所研究任务而言，从表5 中亦可明显看出各算法的优劣，取稳定阶段的目标函数值作为衡量性能的依据，本文所提算法比SA 算法提升4.7%，比传统的GA 算法性能提升9.8%。对于1 000用户的容纳需求，3 小区的最终优化结果，基站容量计算值为1 146，可满足。具体的基站站址、小区朝向和覆盖效果如图4 所示。

表4 不同算法在不同迭代次数时的目标函数值比较

表5 设置1 000个用户时站址和小区工参联合规划结果

图4 设置1 000个用户时的覆盖图

当设置用户数为2 000 时，使用本文给出的算法模型得到目标函数V随着迭代次数的仿真迭代结果如图5 所示：

图5 设置总用户数为2 000时的仿真迭代图

图5 表示增加用户数到2 000 时，算法迭代过程中不断加站、优化的过程图。从图5 中明显能够看到有三个不同的阶段。首先，在第一个阶段，此时基站数量只有一个，当完成站址规划时，容量评估并不满足要求，所以进行了加站操作。然后，加站完成后并达到稳定时，可以看到V值有一个很明显的降低，这是因为此时干扰在增加，导致V值降低。最后，增加到3 个基站且稳定时，可进一步看到干扰在增大，总的V值在降低。最终结果显示，由于干扰增大，2 个基站最终只能容纳1 887 个用户，所以只能增加基站数量满足要求。图6 为最终的基站站址和小区工参联合优化的区域覆盖图。

图6 三个基站完成场景覆盖时的效果图

图6 展示的是3 个基站覆盖目标区域的效果图。在图6 中，可以看到一个基站的三个扇区，部分出现了重叠，这并不是由于小区朝向一致造成的，而是渲染工具中，扇面设置较大导致的，具体的站址和小区工参规划结果数据如表6 所示：

表6 设置2 000个用户时站址与小区工参联合规划结果

5 结束语

本文提出了一种改进型的遗传算法用以解决大规模站址和小区工参的联合优化。该算法相对于传统的遗传算法变异和交叉阶段，采用最大期望算法思想，使用分步变异、分步交叉迭代的方式，分别对不同物理量参数依照设置条件交替完成变异、交叉迭代。在算法中，使用了邻域搜索，使得算法在寻优过程中高效、稳定。该方法对于不同物理量参数形成的高维组合解的求解非常有效，且能够将这一方式扩展到其他启发式智能算法中。同时为了能够在达到覆盖最优的同时，保证小区的容量能够容纳覆盖范围内的用户，给出了一种简单的容量评估方式。仿真结果表明，在进行高维度空间搜索时，本文所提采用最大期望思想的方法完成遗传算法中的变异交叉过程，能够快速收敛，并达到一个准最优值；SA 算法虽然也能够达到要求，但是其收敛速度较慢，而其他启发式算法在高维物理量不同的离散空间搜索任务中，结果较差。本文所提方案相对于传统的GA 算法，目标函数值提升9.8%，相对于使用站址规划最多的SA 算法，目标函数值提升4.7%，但收敛时间约为SA 的五分之一。该算法方案能够在有效解决规模站址和小区工参联合优化问题的同时保证小区能够接入覆盖区域的所有用户，提高用户感知。