摘 要：本文针对现有基站选址优化方法存在的问题，提出一种基于聚类的无线网络基站选址优化算法。建立包括节点利用率和覆盖率的优化模型，引入聚类策略对初始解集合进行优化，采用基于二进制编码的差分进化算法求解优化模型，得到最优覆盖方案。试验结果表明，本文提出的方法能够有效提升优化效果，具有一定的实用性。
关键词：基站选址；聚类；差分进化；二进制编码
中图分类号：TN929.5 文献标识码：A 文章编号：2096-4706（2018）09-0050-03
Abstract：This paper aims at the problems of the existing base station location optimization method，a clustering based optimization algorithm for the location of wireless network base stations is proposed. The optimization model is established，which includes the utilization rate and coverage rate of nodes. The clustering strategy is introduced to optimize the initial solution set. The optimal model is solved by using the differential evolution algorithm based on binary coding，and the optimal coverage scheme is obtained. The experimental results show that the method proposed in this paper can effectively enhance the optimization effect and is practical.
Keywords：base station location；clustering；differential evolution；binary coding
0 引 言
基站选址优化是无线网络规划的一项重要内容，即在综合考虑信号质量、建设代价、覆盖约束以及其他网络约束的条件下，规划基站的数目和位置。随着无线通信网络的进一步发展，这一问题引起了学术界和工业界的广泛重视。Zhang[1]等将全局优化问题分解为多个子问题，以求解大范围区域内的基站选址问题。朱思峰[2]等提出了基于免疫计算的选址优化方案，并给出了对应的算法框架。张宏远[3]等基于预测控制中的滚动优化原理设计了基于滚动窗口的基站选址优化方法。马宝罗[4]等提出了一种基于矢量距离免疫计算的基站选址问题求解方案，结合了基于矢量距离的抗体浓度计算方法和反学习的种群初始化策略，具有较好的应用价值。另外，基站选址优化多采用智能演化算法[5，6]，随机生成初始解集。在实际场景中，通信业务量分布往往是不均匀的，例如住宅小区业务量往往较大，在基站建设的时候需要优先考虑此类区域。采用随机生成初始解集的方式往往会导致收敛缓慢，甚至陷入局部最优。
为解决上述问题，本文提出一种基于聚类的无线网络基站选址优化算法。通过引入聚类策略对初始解集合进行优化，并引入差分进化算法求解。试验结果表明：该方法能够以较小的建设代价满足覆盖要求，收敛速度较快，具有一定的应用价值。
1 预备知识
为了方便理解本文提出的算法，本节介绍以下基本概念和原理，分别是差分进化算法、峰值密度聚合和基站选址优化模型。
1.1 差分进化算法
差分进化（Differential Evolution，DE）是一种基于群体演化的算法，通过种群内个体间的合作与竞争来实现对优化问题的求解。算法的基本思想是对当前种群进行变异和交叉操作，产生另一个新种群，然后利用基于贪婪思想的选择操作对这两个种群进行一对一地选择，产生最终种群。
1.2 峰值密度聚类算法
本文算法需要对测试点集合进行聚类运算，因此选取合适的聚类算法至关重要。目前广泛运用的经典聚类算法普遍存在参数敏感、计算量大、难以处理、不均匀分布数据集等问题。密度峰值聚类算法（Clustering by fast Search and Find of Density Peaks，CFSFDP），是一种基于密度的聚类方法，不需要预先确定聚类数目，参数变化鲁棒性较好，适合本文中的场景。
1.3 基站选址优化模型
完成种群初始化之后，进行变异、进化以及选择操作，算法的终止条件为达到最大进化代数Gm。
3 试验分析
3.1 试验环境设定
设定检测区域为边长20km的正方形，候选基站集合 S={s1，s2，…，s60}，P={p1，p2，…，p120}为测试点集合，基站和测试点的分布如图1所示，其中星号表示测试点，模拟实际话务分布情况，圆形代表候选基站地址。
算法参数设置如下：种群规模popSize=50，最大进化代数Gm=200，K=0.2，λ=0.05，采用二进制编码，交叉概率CR为0.1，目标函数中的系数w1和w2分别为0.35，0.65。
3.2 结果分析
首先采用算法1对测试点集合进行聚类运算，得到聚类中心。分别采用DE算法和本文算法对该优化模型进行求解，运行次数为30次，取平均值，优化效果如图1所示。
由图1可以看出，针对本文提出的例子，DE算法大约在120代收敛，本文算法大约在80代收敛。采用聚类算法引入较优解，因此本文算法收敛更快，能够更快搜索到最优解。综合来看，本文提出的算法优于DE算法，具有一定的实用价值。
4 结 论
基站选址优化是无线网络规划的重点和难点之一，本文对无线网络基站选址问题进行了分析，以覆盖率和和节点利用率为指标建立了最优化模型，并提出一种基于聚类策略的二进制编码差分进化算法，求解最优覆盖方案。试验结果表明，本文提出的方法能够有效提升优化效果，具有一定的实用性。
参考文献：
[1] ZHANG H Y，XI Y G，GU H Y. A rolling window optimization method for large-scale WCDMA base stations planning problems [J].European Journal of Operational Research，2007，183（2）：370-383.
[2] 朱思峰，刘芳，柴争义.基于免疫计算的WCDMA网络基站选址优化 [J].电子与信息学报，2011，33（6）：1492-1495.
[3] 张宏远，席裕庚，谷寒雨.基于滚动窗口的WCDMA无线网络规划 [J].自动化学报，2007，33（4）：432-434.
[4] 马宝罗，贾振红，覃锡忠，等.改进免疫算法在无线网络基站选址优化中的应用 [J].传感器与微系统，2016，35（5）：154-157+160.
[5] 沈海洋.基于遗传PSO的无线传感网络覆盖优化算法研究 [J].微电子学与计算机，2013，30（3）：148-151.
[6] 朱思峰.基于免疫计算的无线通信网络资源优化 [D].西安：西安电子科技大学，2012.
作者简介：黄骅（1983-），通迅作者，男，博士。研究方向：人工智能、自然语言处理；江俊（1983-），男，讲师，博士。研究方向：人工智能、多数据融合。