遗传算法在UMTS自动小区规划中的应用

刘计永, 张　蕾

(1.中国移动 河北分公司，河北 石家庄 050000；2.北京邮电大学 信息与通信工程学院，北京 100876)



遗传算法在UMTS自动小区规划中的应用

刘计永1, 张蕾2

(1.中国移动 河北分公司，河北 石家庄 050000；2.北京邮电大学 信息与通信工程学院，北京 100876)

针对需要高维优化的通用移动通信系统(UMTS)无线网络自动小区规划(ACP)问题，应用了改进的遗传算法。该算法用特殊的正交方法产生初始解，采用精英选择策略，并自适应地改变交叉概率和变异概率的值。仿真结果显示:相对于其他遗传算法，该算法的性能有较大的提升，可以更加有效地找到高维UMTS-ACP问题的优化解。

无线网络优化； 通用移动通信系统； 遗传算法

0　引　言

通用移动通信系统(universal mobile telecommunications system,UMTS)无线网络中由于基站天线参数配置不合理容易使网络出现诸如弱覆盖、导频污染等覆盖质量问题，使某些区域的信号质量不能满足用户的服务质量(QoS)需求，因此，进行无线网络优化是一项重要的工作。但是，随着无线网络规模的日益庞大和维护工作的日益复杂，网络维护优化的难度在不断加大，选取一种新的适当的方法来解决网络优化的问题是很有必要的[1]。近几年，利用自动小区规划(automatic cell planning,ACP)进行无线网络的优化是一项研究热点[2,3]，它可以解决最大化网络性能问题。

无线网络优化问题实质上是一个NP-hard问题，解决这类问题一个有效的方法就是采用智能算法，目前常用的智能算法有遗传算法、模拟退火算法、粒子群算法、蚁群算法等[4～6]，其中，遗传算法的应用较为广泛。但由于标准遗传算法收敛速度慢，且有易于收敛到局部最优解的缺陷[7～9]。文献[7]提出了一种基于精英选择的改进遗传算法，精英种群中的最优解即为所求问题的解。文献[8]提出了一种自适应遗传算法，对交叉概率和变异概率给出了改进的公式。文献[9]提出了一种大规模全局优化问题的初始解产生方法，用一种特殊的正交方法产生问题的初始解，使初始解在搜索空间均匀地分布。

本文结合文献[7]的精英选择策略、文献[8]的自适应改变交叉概率和变异概率的算法以及文献[9]提出的一种特殊的正交方法产生问题的初始解，得到一种改进的遗传算法，本文采用改进的遗传算法来解决高维的UMTS-ACP问题。

1　遗传算法

标准遗传算法的运算流程如图1。

图1　标准遗传算法流程图Fig 1　Flow chart of standard genetic algorithm

图1中,Gen为迭代次数。

标准遗传算法在对许多复杂的问题进行优化时，很难收敛到全局最优解；经过若干次迭代之后，种群相似度提高，这会降低交叉算子的效率，新的优质个体的产生效率就会下降。

2　UMTS-ACP问题的算法设计方案

UMTS-ACP系统可以通过调整天线参数(包括机械下倾角、电子下倾角、方位角、发射功率、天线类型)，通过对MR数据、工参数据等工程参数进行分析，利用改进的遗传算法进行优化，实现所选地区的各项指标的优化。

具体的优化指标包括接收信号码功率(RSCP)、导频信道信噪比(Ec/Io)，1st-Nth 导频污染。将RSCP作为优化目标是为了优化接收功率，将Ec/Io作为优化目标是为了优化接收质量，将1st-Nth导频污染作为优化目标是为了抑制导频污染和越区覆盖。

实际的UMTS网络中，相邻小区之间的关联很密切，需要同时对几百个小区进行优化。如果每个小区有5个参数可以调整，对500个小区的这5个优化参数进行优化，优化问题的维数将达到2 500维，这是一个高维的优化问题。

UMTS-ACP问题的目标函数的表示为

f(k→)=∑wRSCP·U(RSCP(k→))+wEcIo·U(EcIo(k→))+

w1st-Nth·U(ΔRSCP1st-Nth(k→))+wLoad·U(ΔLoad(k→))

(1)

式中变量k→是由机械下倾角、方位角、电子下倾角、天线类型五个变量组成的向量。U(RSCP(k)),U(EcIo(k)),U(ΔRSCP1st-Nth(k)),U(ΔLoad(k))为各优化目标的目标函数；wRSCP,wEcIo,w1st-Nth,wLoad是各优化目标的权重。

UMTS-ACP问题的约束条件是优化成本和负载均衡等，这里的优化成本是指天线的参数调整时所花费的人工成本，考虑负载均衡作为约束条件是为了在优化过程中保证小区之间的负载均衡。

可以看出，这类优化问题就是在满足优化成本和负载均衡的约束条件下，最大化网络性能的问题，这是一个单目标带约束的高维优化问题。

UMTS-ACP问题的优化过程就是目标函数的迭代优化过程，每次迭代修改变量 ，使目标函数的值不断优化，同时要满足约束条件，达到最大迭代次数时，迭代终止。

采用改进的遗传算法此类问题的具体流程如下:

1)首先,产生UMTS-ACP问题的初始解，问题的解就是式(1)中的向量 。算法采用一种特殊的正交方法得到问题的初始解，即将所有变量的定义域分别划分成N个子区间，N为种群中个体的数量，每个初始解的每个变量逐个在子区间内随机地取值，这样每个解所在的子区间是正交的，使得解在搜索空间分布的更加均匀，加强了种群的多样性。根据文献[9]，对生成的正交解采用相对位学习法求解它们的相对位，形成了一组新解，将新旧解的适应度值进行对比，保留适应度值较大的解。这样不仅使初始解在搜索空间均匀地分布，而且可以选择较有潜力的区域进行后续的搜索。

2)复制种群:对复制的种群进行自适应交叉操作，交叉概率的计算公式为[11]

(2)

式中favg为种群中所有个体的平均适应度，favg是种群中最大的个体适应度，f′是两个待交叉的个体中适应度函数值较大的个体的适应度值，pc1>pc2>pc3,A=9.903 438,r为一个很小的正数。交叉概率随适应度函数的增大而渐渐变小，在进化的初期基因种类比较丰富，但是缺乏优良的个体，所以要增大交叉概率，进化的后期基因种类趋于一致，优良的个体比较多，所以要减小交叉概率，防止破坏优良的个体。

3)交叉操作后，评估每个解的适应度值，然后进行自适应变异操作，变异概率的计算公式为[8]

(3)

式中f为要变异个体的适应度值，pm1>pm2>pm3，变异概率随适应度函数值的增大而逐渐增大。进化初期基因种类丰富，所以要减小变异概率，进化后期基因种类趋于一致，种群的多样性减小，所以,要增大变异概率增加种群的多样性。

4)评估变异操作后的解，用精英种群代替最差的M个解，找到当前的全局最优解，更新全局最优解，选出适应度值较大的前N个解，迭代次数加1。

5)判断是否达到最大迭代次数或者到达，到达最大迭代次数算法结束，输出最优解;否则，返回到B继续进行迭代。

改进算法的流程图如图2。

图2　改进遗传算法流程图Fig 2　Flow chart of improved genetic algorithm

3　仿真结果与分析

3.1仿真场景

用一个UMTS现网中的数据进行仿真，该区域有454个小区，每个小区有机械下倾角、方位角、电子下倾角、发射功率、天线类型五个变量，整个优化问题的维度高达2 000多维，搜索空间巨大。仿真区域包含1 590 000多条MR数据，218种天线信息。地图的最小分辨率为20 m×20 m，为一个栅格的大小，数据经过地理平均后，地图上的栅格有205 650个。优化目标有RSCP，Ec/Io，1st-Nth 导频污染，各目标的权重设置为1。本文采用标准遗传算法和文献[8]中提出的自适应遗传算法进行对比，标准遗传算法的交叉概率和变异概率为固定值，分别为0.8和0.1。式(2)中，pc1=0.9，pc2=0.8，pc3=0.6，式(3)中，pm1=0.1，pm2=0.05，pm3=0.01。

仿真过程中的其他参数配置：N阶RSCP的N值为4;RSCP达标门限值为-80 dBm;Ec/Io达标门限值为-8 dB;1st RSRP～4th RSRP达标门限值为5 dB;负载均衡的约束值为0.8 dB;负载达标的门限值为0.05 dB。

3.2仿真结果与分析

将本文提出的改进的遗传算法与标准遗传算法和文献[8]中自适应遗传算法进行比较，如图3所示。

图3　改进的遗传算法与其他遗传算法对比Fig 3　Comparison of improved genetic algorithm and other genetic algorithms

图3中可以看出：在算法前期，标准遗传算法的效果比较好，但是很快陷入局部最优，出现早熟现象，在18代之后就停止进化了。自适应算法前期有一段时间进化很慢，陷入局部最优，但经过多次迭代之后可以跳出局部最优，到中后期速度开始变快，经过100次的迭代之后，性能值接近0.89，而本文提出的改进的遗传算法在整个迭代过程中表现得较好，没有明显陷入局部最优解，这是因为在算法初始化时，采用了正交方法获得问题的初始解，经过100次的迭代，性能值接近0.9，得到的结果更加理想。

图4是采用改进的遗传算法优化前后栅格RSCP的累计分布曲线(CDF曲线)。优化前RSCP小于等于-80 dB的栅格为70 %，优化后RSCP小于等于-80 dB的栅格为25 %，说明优化后大多数栅格的RSCP值变大，优化指标RSCP在优化后有很大的改善。图5是采用改进的遗传算法优化前后栅格Ec/Io的累计分布曲线。优化前Ec/Io小于等于-4 dB的栅格为60 %，优化后Ec/Io小于等于-4 dB的栅格为40 %，说明优化后大多数栅格的Ec/Io值变大，优化指标Ec/Io在优化后有很大的改善。

图4　优化前后累计分布曲线-RSCPFig 4　Cumulative distribution curve before and after optimization-RSCP

图5　优化前后累计分布曲线Fig 5　Cumulative distribution curve before and after optimization

4　结束语

为了解决ACP-UMTS无线网络优化的问题，本文采用了改进的遗传算法，该算法用一种特殊的正交方法产生初始解，采用精英种群策略，并自适应地改变交叉概率和变异概率。仿真结果表明：与其他遗传算法相比，改进的遗传算法能够很好地处理ACP问题，它避免算法陷入局部最优，能达到良好的优化效果。

[1]程敏.自动小区规划在LTE小区射频控制中的应用[J].移动通信，2014，3(4):30-37.

[2]欧阳晖.自动小区规划的实际应用考虑[J].现代电信科技，2012，8(8):71-76.

[3]沈亮，周俊.自动规划工具对无线规划设计的影响[J].电信工程技术与标准化，2008(5):51-55.

[4]Guo Pengfei,Wang Xuezhi,Han Yingshi.The enhanced genetic algorithms for the optimization design[C]∥International Confe-rence on Biomedical Engineering and Informatics (BMEI),2010:2990-2994.

[5]Zhao Xin,Xiu Chunbo.New genetic algorithm improved and its applications[C]∥International Conference on Electronics Communications and Control (ICECC),2011:926-928.

[6]Zheng Jiezhen,Wang Zhijun,Wang Shiyun.BP neural network optimize based on improved genetic algorithm[C]∥International Conference on Computer Engineering and Technology(ICCET),2010:526-529.

[7]祁荣宾,钱锋,杜文莉,等.基于精英选择和个体迁移的多目标遗传算法[J].控制与决策，2007，22(2):164-168.

[8]李延梅.一种改进的遗传算法及应用 [D].广州:华南理工大学，2012.

[9]Kazimipour Borhan,Li Xiaodong,Qin A K.Initialization methods for large scale global optimization[C]∥2013 IEEE Congress on Evolutionary Computation (CEC),2013:2750-2757.

Application of genetic algorithm in UMTS automatic cell planning

LIU Ji-yong1, ZHANG Lei2

(1.Hebei Branch，China Mobile,Shijiazhuang 050000,China；2.School of Information and Communication Engineering,Beijing University of Posts and Telecommunications，Beijing 100876,China)

Aiming at problem of wireless network automatic cell planning (ACP) of a high-dimensionally optimizing universal mobile telecommunications system (UMTS),is used improved genetic algorithm This algorithm adopts a special orthogonal method to give initial solutions,use the elitist selection strategy and adaptively changes the values of crossover probabilities and mutation probabilities.The simulation results show that the performance of the algorithm is significantly upgraded compared with other genetic algorithms,and the optimal solutions to high-dimensional UMTS-ACP issue can be found more effectively.

wireless network optimization; universal mobile telecommunications system(UMTS); genetic algorithm

2015—10—12

TN 929.5

B

1000—9787(2016)08—0148—03

刘计永(1974-)，男，河北馆陶人，通信工程师，从事无线通信、管理信息化研究工作。

DOI:10.13873/J.1000—9787(2016)08—0148—03