改进禁忌搜索算法在基站天线参数优化中的应用

【摘 要】 现代移动通信系统中，常采用小区覆盖的方案来对整个地区进行信号覆盖，其中水平方位角、垂直下倾角和导频功率是影响基站覆盖范围的重要的天线参数。通过对这3个参数进行数学建模和分析，提出了一种基于网格化的改进智能禁忌算法，使得系统能够获得最优的信号覆盖效果和最佳的天线参数配置。

【关键词】覆盖优化 智能优化算法 改进禁忌搜索

1 引言

在现代移动通信系统中，如目前主流的2G、3G网络，都采取了通过基站来划分小区，以对整个区域进行覆盖的方案，所以基站对所在小区要有尽可能好的覆盖才能提高服务质量。对于基站天线而言，影响小区覆盖的因素主要有：天线下倾角、天线方位角和导频功率。对于移动终端而言，基站的天线参数选择所造成的覆盖质量主要归结为2点：参考信号接收功率（RSRP，Reference Signal Receiving Power）和信噪比（SINR，Signal to Interference plus Noise Ratio）[1]。RSRP表征了移动终端所能获得的信号功率的平均值，它取决于终端所归属的小区天线导频功率和天线传播方向与终端之间的夹角；SINR不同于传播路径中存在的噪声（如AWGN），侧重于不同信号的干扰带来的信噪比下降，主要来自于同一天线发射给不同终端信息间的干扰以及不同天线间信号的干扰。因此，通过天线参数的优化来改善覆盖质量就是要选择合适的天线参数，使得RSRP最大化和SINR最小化。

目前，天线参数的优化方法不仅有按照经验和人工调节的方法或者按照一定的优化算法如Powell搜索法，还有使用智能优化算法如遗传算法（GA，Genetic Algorithm）[2]和禁忌搜索算法（TS，Tabu Search）等[3-4]。人工测定调节需要消耗大量的人力物力，而Powell算法、GA算法和TS算法虽然都能起到良好的优化效果，但是也存在局限性。在特定场景中，通过调节天线的下倾角、方位角、导频功率来求解最优的RSRP和SINR，实际上是一个NP完全（NPC，NP Complete）问题，需要指数级复杂度才能完全求解。

本文主要讨论智能TS算法在天线参数优化问题中的应用，通过对TS算法引入网格化的局部搜索思路，辅以变步长的一维搜索方法，加快了局部搜索速度，再配合上TS算法本身不易于陷入局部极值陷阱的特点来获得全局的极值结果。最后，配合多小区联合调整的研究能获得更好的小区覆盖效果。

2 场景模型

在现代移动通信系统中，通常采用小区覆盖的方式来解决信号覆盖问题。即通过基站的天线覆盖范围，将整个区域划分为若干小区，小区内的终端用户直接与该小区所属基站进行相互通信。在各种小区覆盖方案里，蜂窝网络是一种经典的模型[5]。

如图1所示，在典型的蜂窝网络模型中，每个基站配有3根天线，3根天线各呈120°的夹角，将一个单元划分为3个扇区，每个基站覆盖1个菱形的区域。目前，主流的通信系统如CDMA2000、WCDMA网络的基站以及LTE，都采用了类似的3根天线进行覆盖的方案。

但是在实际的工程应用中，基站覆盖形状以及扇区数量是随着实际需要而调整的。在基站分布不规则的前提下，只能通过调整天线的各种参数来使覆盖范围尽可能最大化。为了简化这一问题的数学模型，一般工程实践中只考虑天线的3个主要参数会对覆盖造成巨大影响：水平方位角ψ、垂直下倾角γ和导频功率C。其中，导频功率C即为参考信号子载波（RS RE）上的发射功率。

3 数学建模

3.1 适应度函数的构造

假设Ω={C1，C2，…，Cn}为所有状态构成的解空间，其中Ci（i=1，2，…，n）表示待规划小区的一种配置，由3个参数（x，y，z）组成，此处的x、y、z分别代表前一节所述的天线下倾角、方位角与参考信号功率，则目标是求得该问题空间的一个最优解，使小区天线参数可以表示为。

在考虑覆盖规划的最优性能时，需要同时考虑基站对整个区域的覆盖面积以及不同基站间的相互干扰问题。在通信领域里，可以使用RSRP与SINR作为指标。在覆盖区域的某点上，当RSRP和SINR的计算值超过某一阈值时，则认为该点被基站有效覆盖。当整个区域被有效覆盖的面积最大时，可以认为该覆盖规划取得了一个最优解，则目标函数定义为：

f=k1×A+k2×B （1）

其中，f表示目标函数；A代表整个规划区域里RSRP超过某个规定阈值的面积占总面积的比值；B代表整个区域中SINR超过某个规定阈值的面积占总面积的比值；k1与k2为权重常量，这里规定k1+k2=1。

当目标函数取得最优解fbest时，取得最优解

可以决定实际调整天线时应取的参数。

3.2 RSRP和SINR计算

按照COST231-Hata传播模型，分别对RSRP和SINR给出定义：

终端的RSRP计算公式如下：

（2）

其中，为本小区i的一个参考信号子载波上的发射功率；为小区i到用户u（即下行）的总的损耗；J为网络中需要考虑的小区总数。则有：

=器材损耗+传播路径损耗-基站的天线增益

（3）

根据前述，基站天线增益（含水平和垂直方向）主要由各自的水平方向角和垂直下倾角决定。综合以上分析，则目标函数f的第一项A主要由ψ、γ和C决定。

假设传输功率是均匀地分布在所有的参考信号子载波上，则终端的参考信号的SINR计算公式如下：

（4）

其中，表示总的下行干扰；J表

示UE能够检测到的在线小区的个数；

表示j小区对用户u的子载波发射功率造成的干扰；PNoise_RE为一个RE上的噪声功率。

4 基于网格化的改进禁忌搜索算法

4.1 算法选择

由上节的定义可知，求解适应度目标函数f是一个NP问题，其复杂度会随着扇区数量增加呈指数型增长，并且无法通过一个显式的多项式来描述f，所以常用的基于导数的优化算法并不适用于本问题。目前解决该优化问题主要有不依赖导数的方法如Powell算法[6-7]，这类方法不要求目标函数有导数，迭代比较简单。但是在这个场景模型中，由于考虑工程天线可调最小刻度有限，Powell算法存在有若干次搜索后搜索方向失去共轭性的问题。实际工程方案一般先对RF参数按照连续的情况进行优化，然后将优化结果取到其最接近的离散值。这种改进后的Powell算法虽然可以不需要求导而快速迭代收敛，但存在容易陷入局部极值的问题。

此外，还可以使用智能算法，如遗传算法就是一种比较常见的智能算法，广泛应用于各种工程领域[8-9]。与Powell算法相比，智能算法的优势在于可以有效求解全局极值，但是收敛速度较慢。

基于以上考虑，选取某一实际工程中的基站场景进行初步的仿真分析，性能对比结果如图2所示。可以看到，遗传算法存在提升速度慢的明显缺点，一般要在几倍于改进Powell算法所需迭代轮数的情况下才能达到相同的收敛程度。

图2 GA算法和Powell算法效率局部对比

观察图3中50轮后遗传算法最终适应度0.963、Powell算法最终适应度0.953，尽管遗传算法比Powell算法有所提升，但是提升结果并不显著。上图验证了遗传算法收敛速度不如Powell算法的猜测，这是由于遗传算法在对子代进行删选时，并不能保证朝最优解快速逼近。对于遗传算法的最终结果相对于Powell算法没有明显提升主要是由于实验仿真的迭代轮数有限，遗传算法在理论上经过无穷多的迭代轮数，是可以达到极值点的。

通过实验分析了智能算法和非智能算法的实际表现，可以得出以下结论：

（1）类似于Powell算法的非智能算法有较好的收敛速度；

（2）非智能的Powell算法的确存在陷入局部极值的问题；

（3）遗传算法存在性能提升缓慢的问题。

综合以上结论，可选择另一种智能算法――禁忌搜索算法（TS）。TS算法作为一种智能算法，也有避免局部极值的特点[10-11]，并且相当多的研究表明TS算法适用于非连续问题的[12-13]。TS算法通过不同的领域构造和搜索规则，使得可以调整向最优解的前进速度，这是遗传算法无法比拟的优势。采用合适的TS算法，可以有效结合2种算法的优点，避免它们的缺点。

禁忌搜索算法流程如图4所示：

图4 禁忌搜索算法流程

4.2 局部选择算法

如图4所示，禁忌算法的思想在于快速获得一个局部极值，并把局部极值置于禁忌表中，进而寻找下一个局部极值。这个搜索要求速度快，所以本文采用了变步长的一维搜索，但是在搜索方向上加以改进。算法详述如下：

由前述该场景解的形式为，

即第i个扇区对应一组参数。如果分别把xi、yi、zi视为三维空间中点的坐标，则当扇区i在领域内进行极值搜索时，其领域的点在该三维空间内形成了网格状的结构。

借鉴网格法中的思路，网格中的搜索方向为初始点与其临近点组成的方向，如二维网格中，每个点有8个方向，分别为上、下、左、右、左上、左下、右上、右下，而在该工程的三维网格中，每个点有26个方向。

确定搜索方向后，在每个方向上必定能找到一个极大值点，所有方向上的极大值点组成候选解，选择一个不在禁忌表中的最大候选解替换最早进入禁忌表的对象，并把这个候选解作为下一轮的初始解，如果这个候选解大于当前最优解，则替换当前最优解。当目标函数f的提升度小于规定值ε后，得到的当前最优解即为算法输出的优化结果。

当确定搜索方向后，寻找极值主要使用的一维搜索，通过智能调整步长使得搜索的次数减少，提高速度。具体流程如图5所示：

图5 变步长的一维搜索流程

其中，d为搜索方向向量；f为所求目标函数值。当沿某方向暂时没有找到可行解时，倍增步长以扩大搜索范围；当寻找到可行解时，在该可行解附近再减小步长进行搜索。

另外，在网格中搜索时，已经搜索过的点可以记录其目标值，当下次再搜到这个点时，可以直接得到目标值而不需要再调用求目标值的函数，以提高效率。

5 仿真结果

5.1 性能验证

随机挑选了挪威的5个实际基站场景，分别采用Powell法和网格禁忌法来计算目标函数，并对它们的最终结果进行统计，可得到如图6所示的结果：

图6 5个场景结果对比

由图6可见，蓝色和绿色的改进方法在5个实际场景中的表现都优于黄色的Powell法。而采用联合调整的禁忌法时，在某些场景蓝色相对于绿色结果有更进一步的提高。但同时也可以看到，联合调整有其局限性。当场景类中基站布局较为稀疏时，采用联合调整并无优势，反而降低了执行效率，直接采用所提出的网格禁忌算法即可。而当场景中有若干基站集中在一小块区域时，则采用联合调整具有优势。但是从所有随机选取的5个场景结果来看，联合调整在最终目标函数上都不小于单独调整的方案。

5.2 鲁棒性验证

鲁棒性（robustness）即指系统的强壮性，当系统发生异常和危险时的可靠性。在所研究的这个问题中，在实际调整天线的方向角和下倾角时，由于调节的误差会导致实际结果与计算值产生偏差，所以需要考察这种情况下SINR和RSRP的变化。

由于实际应用现场调整时不可能准确地调节到优化的参数值，如优化参数为120°，实际调整时由于人为误差等因素可能调整为120.5°。而鲁棒性的验证就是要求在这种误差的存在条件下，系统仍能有稳定的性能表现。

现在根据已经优化过的算法计算结果为基准，随机改变计算结果中某些参数的值，可以是水平角或者下倾角，幅度为±1°，实际应用中调整误差可能小于1°，这里扩大了误差容易验证误差带来的影响。

鲁棒性验证如图7所示，在改变4至8个参数的情况下，各区间归属的百分比变化在0.5%以下，实际现场调整的误差应该在1°之内，那么由误差引起的性能下降更小。则根据实验结果分析，使用本文的优化方法得到的解具有较好的鲁棒性。

图7 鲁棒性验证

6 结束语

本文讨论了现代通信系统中如何得到基站天线最优参数配置的问题。通过建立对应数学模型，提出了改进的智能TS算法并进行仿真比较，可以验证所提出的智能算法能有效地逼近全局最优值。并且通过鲁棒性实验可以证明算法得到的结果，在一定误差存在的情况下并不会大幅度改变目标函数，这说明该算法非常稳定。此外，通过分析基站的位置信息，提出了在基站分布紧密时如何采用联合多站调整的优化流程。

参考文献：

[1] Rodger E Ziemer， William H Tranter. Principles of Communications[M]. John Wiley & Sons Ltd， 2009.

[2] 陈宝林. 最优化理论与算法[M]. 北京： 清华大学出版社， 2005.

[3] F Glover. Tabu Search-Part I[J]. ORSA Journal of Computing， 1989，1（3）： 190-206.

[4] F Glover. Tabu Search-Part II[J]. ORSA Journal of Computing， 1990，2（3）： 4-32.

[5] Rappaport T S. Wireless Communications Principles and Practice[M]. 2nd ed. Prentice Hall， 2002.

[6] Dennis J E. 无约束最优化与非线性方程的数值方法[M]. 北京： 科学出版社， 2010.

[7] 张立卫. 最优化方法[M]. 北京： 科学出版社， 2010.

[8] Mimoun， Younes， Mostefa. Optimal Power Flow Based on Hybrid Genetic Algorithm[J]. Journal of Information Science and Engineering， 2007，23： 1801-1816.

[9] Eva Vallada， Rubén Ruiz. A Genetic Algorithm for the Unrelated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times[J]. European Journal of Operational Research， 2011，211（3）： 612-622.

[10] Chen Lu， Langevin André， Riopel Diane. A Tabu Search Algorithm for the Relocation Problem in a Warehousing System[J]. International Journal of Production Economics， 2011，129（1）： 147-156.

[11] Costamagna Eugenio， Fanni Alessandra， Giacinto Giorgio. A Tabu Search Algorithm for the Optimisation of Telecommunication Networks[J]. European Journal of Operational Research， 1998，106（2）： 357-372.

[12] R G Lanafi. On the Convergence of Tabu Search[J]. Journal of Heuristics， 2004，7（1）： 47-58.

[13] F Glover， S Hanafi. Tabu Search and Finite Convergence[J]. Discrete Applied Mathematics， 2002，199（1-2）： 3-36.