加速遗传算法在移动通信基站规划中的应用∗

晁迎，覃锡忠，曹传玲，邓磊，刘汉兴

(1.新疆大学信息科学与工程学院，新疆乌鲁木齐830046；2.中国移动通信集团新疆有限公司，新疆乌鲁木齐830063)

0 引言

移动互联网迅速发展，移动用户数量飞速增长，为了获得更好的通信服务质量，移动通信网络需要不断的扩展和延伸，必须建设大量的新基站，基站分布的规划优化成了一个重要的问题.合理的分布规划能够降低成本、提高服务质量.

目前国内外研究人员提出了很多方法来优化基站分布.文献[1]提出了一种基于粒子群算法（Particle Swarm Optimization Algorithm,PSO）的规划方法，该算法应用在较小网络规模上能提高优化效率，但对于较大网络规模的规划效果不理想.文献[2]采用了传统遗传算法，虽然传统遗传算法解决了多目标优化规划问题，具有全局寻优的优势，但是也存在容易陷入局部最优解的问题，算法运行的速度慢造成算法效率较低.文献[3]提出一种将多目标优化问题转化为单目标的方法，考虑覆盖率、业务量和成本等影响因素，但是没有考虑环境干扰因素，得出的规划方案不能满足实际要求.文献[4]提出了基于免疫计算的方法,虽具有全局寻优的优势，但是该算法的优化时间性能较差.这些算法的应用虽然为基站位置分布优化研究奠定了一定的基矗 但是在优化精度、效率方面仍有不足，算法容易陷入局部最优，不易找到全局最优值，全局优化稳健性不高.文献[5]提出一种网络基站选址优化方案，虽然算法有效，较小的建站成本，但是不能获得更高的网络覆盖率.

加速遗传算法是遗传算法的改进，表现出比遗传算法更好的特性，用于多目标优化具有很强的优势.加速遗传算法在解决非线性问题时与其它算法相比具有寻优速度快，不易陷入局部最优，优化精度高，全局稳健性高等优点.文章利用加速遗传算法在解决多目标优化问题上的灵活性，提出了一种网络基站分布规划方法.为了设计出更符合工程实际的规划方法，本文在综合考虑网络覆盖和干扰因素影响的基础上，设计了基站规划多目标组合优化模型，并利用加速遗传算法求解最优规划方案.仿真表明，加速遗传算法在解决复杂优化问题时是极其有效的，能够得到较优的基站位置分布方案.

1 基于加速遗传算法的基站分布规划建模

1.1 加速遗传算法

加速遗传算法(Accelerating Genetic Algorithm,AGA)是一种仿生学算法，其原理是模仿生物界中的“物竞天择，适者生存”的演化法则，拥有搜索能力强、收敛性好等优点，同时算法对建立数学模型的要求较低，已经广泛应用于实际优化问题中[6].遗传算法的基本思想是在初始变化区间内随机生成一组父代个体作为初始解，经过选择、杂交及变异，生成子代个体，通过目标函数评价个体的好坏，优胜劣汰产生优秀个体，并作为新的父代个体，如此循环迭代，使个体的适应度能力不断提高，不断向最优点逼近.加速遗传算法是遗传算法的改进算法，增强了遗传算法的自适应寻优功能，它克服了遗传算法对搜索空间差、计算量大、容易出现早熟收敛、全局优化速度较慢等实际问题.它利用在运行过程中产生的优秀个体，逐步调整优化变量搜索范围[6,7].本文基于加速遗传算法建立基站分布规划模型.

1.2 基站分布规划模型的建立

在保证网络覆盖的前提下，如何尽可能降低成本是网络规划问题的关键.本文着重分析移动通信网络中的基站分布规划问题.

(1)基站分布规划问题：多目标优化问题是多个优化目标在约束条件下同时得到最佳的解[8]，基站分布规划就是要寻找各种影响因素的最优组合解，即在所有的待定参数中找到满足约束条件的解.考虑到多目标优化问题的复杂性，将总体目标函数设置为各种影响因素的加权，这样就简化为单目标优化问题.因此如果算法在得到较大目标函数值的同时时间复杂度越校 说明算法越合理.在基站选址过程中，合理的基站分布是保证网络性能和服务质量的关键，同时要充分兼顾未来网络的发展，以便于分期建设满足不同时期用户的需求.目前，考虑的影响因素有建网成本、网络覆盖率、业务量、信号频率等.网络覆盖率越高，网络性能越好.外界电磁干扰如微波通信、直放站等是影响网络质量的一个重要因素，会产生通话质量差、上网速度慢的问题.因此，外界电磁干扰和覆盖率是基站分布规划问题的首要考虑因素，要求网络具有最小干扰和最大覆盖率.加速遗传算法能够利用种群进化在问题空间中进行大规模搜索，在较短的时间内找到最优解，目前已经被应用在各个领域.

(2)基站分布规划的建模

随机设置基站初始位置，通过加速遗传算法的寻优过程，在适应度函数取得最优解时得到每个基站分布参数.基站规划区域是二维平面，在该区域上规划N个基站，且半径均为r,每个基站的覆盖模型可以表示为以节点坐标为圆心，r为半径的圆.基站点集为Ci=(c1,c2,...,cN)，其中ci为第i个基站的覆盖模型，(xj,yj)是第j个基站的坐标，将点(x,y)被基站所覆盖的事件定义为ri,该事件发生的概率P{ri}为点(x,y)被基站所覆盖的概率p{ri}=p(x,y,ci),此概率为一个二值函数，即

若点(x,y)到第i个基站的距离不大于r,该点(x,y)被基站覆盖，且：

其中为ri的补，表示(x,y)没有被基站i所覆盖这一事件，如果ri和rj无关，则：

只要有一个基站覆盖了点(x,y)，就认为该点被覆盖.所以，点(x,y)被基站集覆盖的概率为ri的并集，则基站集C的覆盖率可以用(4)式表示计算：

式(4)表明，如果所有的基站都没有覆盖到点(x,y),点(x,y)为未被覆盖点，否则，便认为点(x,y)被基站集覆盖.

其中，∆S为网格单位面积，S为网格总面积之和，N为网络的节点数.

电磁波的速度采用光速c，在真空中的传播速度约为3×108m/s，其计算公式如下：

电磁波在自由空间传输时，其强度因能量的扩散而衰减，在距离d2l.i处，天线的辐射功率密度ρ为：

接收天线所接收的发射点之和，其计算方法如公式(7)：

其中N为节点总数，Pi为节点i所受到其它发射节点干扰之和，Pt为节点发射功率，Gtx为增益系数且为1为发射节点与节点i之间的欧氏距离.区域干扰定义为

N为发射、接收两节点连线所经过的区域的个数.

干扰率目标函数为

本文适应度函数如下：

其中w1为覆盖率的权重系数；w2为覆盖区域的干扰的权重系数.

1.3 算法实现

加速遗传算法包括以下几个步骤：

步骤1：初始化空间的离散与编码：a为编码的长度，则a位二进制串,可以表示2a个数，将定义范围离散为2a均等的区域.经编码后，变量的搜索范围离散成了(2a)b个网格点,它对应b个变量的可能的一种取值状态.

步骤2:群体初始化：群体每个个体参数是在初始范围内产生的随机数，使得在演化迭代前期保持充分搜索范围.利用编码映射，建立加速遗传算法中的初始群体.设目标区域为:

其中，L和W分别为目标区域的长和宽.种群由M个体组成，算法中的每个个体的染色体均由N个基因组构成.

初始化种群为：

步骤3:复制和选择：在复制过程中个体位串根据目标函数进行自我复制.复制的第一步是计算适应度.本文中每个个体的适值即是其目标函数，如式(8)所示.在简单遗传算法中，通常采用随机选择法，本文采用轮盘赌法，其结构如下：独立的候选解围成一个圈，每个个体被挑选的概率与个体的适值成正比.

步骤4:交叉：将产生的个体位串随机两两配对；随机选择交叉点，对配对的位串进行交叉繁殖，产生一对新的位串.首先我们设置一个10位的二进制比特串，10位代表位置划分为十个格子（通过算法，可以反推出二维空间的位置），1代表在这个格子上有基站分布.那么有基站的位置序号为：父本为2,4,5,8,9,母本为3,4,6,8,10.随机生成一个数（0-1）小于交叉概率Pc，则进行交叉，交叉点这样设置找出位置序号重合的位置序号.比如位置8，然后进行交叉.

父本

母本

父本为2,4,5,8,10，母本为3,4,6,8,9，则变为：

父本

母本

步骤5：变异：从一个旧种群中选择生命力弱（选择概率校 的个体位串产生新种群的过程.

生成一个随机数，如果小于变异系数，则我们任意挑选为1的基站序号，如1,2,8,9中的5，让5的网格为0再剩下为0网格的位置任意挑选一个变成1.生成新序列为：

步骤6：加速循环：标准遗传算法受初始区间影响很大，假如能随进化而逐渐缩小搜索范围可使搜索速率加快.加速遗传算法就是搜索到的优秀个体的子群体来调整搜索范围的.每一次加速循环中，根据目标函数值，选出优秀个体的百分之二十，交叉然后生成子代再变异.

2 仿真结果与分析

为了验证算法的正确性，对100km×100km目标区域进行规划.每个基站覆盖区域为圆形，采用自由空间传播模型，经计算可得出覆盖半径为11km.算法的参数设置为：种群规模为100，进化代数为100，交叉概率为0.9，变异概率为0.1，w1和w2为相应的目标函数对应的权值，对于不同的应用场合可以选取不同的权值[3]，w1+w2=1[4]，根据选取的不同权值，通过式(11)评价基站分布方案优劣，目标函数f1的权重系数为0.9，目标函数f2的权重系数为0.1.仿真结果如图1，图2.

图1 传统算法优化的基站分布

图2 加速遗传算法优化的基站分布

为了验证加速遗传算法的性能，将它与传统退火算法进行对比实验，在同样实验仿真环境下，两种算法的目标函数值迭代次数的变化比较如图3所示.

图3 加速遗传算法和传统算法适应度比较

图4 两种算法的50次最优值的比较

从图1，2可以看出，传统算法优化的基站的覆盖率很低，加速遗传算法优化基站的覆盖率比较高，说明应用加速遗传算法得到的基站位置分布更合理；从图3可以看出，加速遗传算法的适应度值比传统算法的适应度值明显高很多，说明其全局寻优能力强，不易陷入局部最优；从图3可以看出，加速遗传算法的收敛速度比传统算法的收敛速度快，最优适应值较大，能够找到与网络建设要求相符合的最优规划方案；从图4可以看出，经过50次最优值的比较，加速遗传算法的适应度值大，最优解比较稳定.

3 结论

为了能够获得更好的通信网络服务质量，本文提出一种基于加速遗传算法的基站规划优化方法，该方法在基站分布规划中同时考虑覆盖率和干扰两个因素，设计了具体的实现流程，在同样的参数条件下，进行了仿真和对比试验.加速遗传算法的优化过程包含了复制、交叉、变异等，使得搜索效率提高了许多，迅速的得到最优解.仿真结果表明规划方法的有效性，加速遗传算法能够找到与无线网络建设要求相符合的基站位置分布方案，与传统规划优化方法相比，基于加速遗传算法的基站分布规划得到的适应度值更大，收敛速度更快，具有全局寻优优势，优化时间性能较好，优化方案中的基站分布更合理，网络服务质量得到显著提高，具有重要的实用价值和进一步研究的意义.