改進(jìn)禁忌搜索算法在基站天線參數(shù)優(yōu)化中的應(yīng)用

李鴻儒，何 迪

（1.北京華龍通科技有限公司，北京 100083；2.上海交通大學(xué)電信學(xué)院信息技術(shù)與電氣工程研究院，上海 200240）

改進(jìn)禁忌搜索算法在基站天線參數(shù)優(yōu)化中的應(yīng)用

李鴻儒1，何 迪2

（1.北京華龍通科技有限公司，北京 100083；2.上海交通大學(xué)電信學(xué)院信息技術(shù)與電氣工程研究院，上海 200240）

現(xiàn)代移動通信系統(tǒng)中，常采用小區(qū)覆蓋的方案來對整個(gè)地區(qū)進(jìn)行信號覆蓋，其中水平方位角、垂直下傾角和導(dǎo)頻功率是影響基站覆蓋范圍的重要的天線參數(shù)。通過對這3個(gè)參數(shù)進(jìn)行數(shù)學(xué)建模和分析，提出了一種基于網(wǎng)格化的改進(jìn)智能禁忌算法，使得系統(tǒng)能夠獲得最優(yōu)的信號覆蓋效果和最佳的天線參數(shù)配置。

覆蓋優(yōu)化 智能優(yōu)化算法 改進(jìn)禁忌搜索

1 引言

在現(xiàn)代移動通信系統(tǒng)中，如目前主流的2G、3G網(wǎng)絡(luò)，都采取了通過基站來劃分小區(qū)，以對整個(gè)區(qū)域進(jìn)行覆蓋的方案，所以基站對所在小區(qū)要有盡可能好的覆蓋才能提高服務(wù)質(zhì)量。對于基站天線而言，影響小區(qū)覆蓋的因素主要有：天線下傾角、天線方位角和導(dǎo)頻功率。對于移動終端而言，基站的天線參數(shù)選擇所造成的覆蓋質(zhì)量主要?dú)w結(jié)為2點(diǎn)：參考信號接收功率（RSRP，Reference Signal Receiving Power）和信噪比（SINR，Signal to Interference plus Noise Ratio）[1]。RSRP表征了移動終端所能獲得的信號功率的平均值，它取決于終端所歸屬的小區(qū)天線導(dǎo)頻功率和天線傳播方向與終端之間的夾角；SINR不同于傳播路徑中存在的噪聲（如AWGN），側(cè)重于不同信號的干擾帶來的信噪比下降，主要來自于同一天線發(fā)射給不同終端信息間的干擾以及不同天線間信號的干擾。因此，通過天線參數(shù)的優(yōu)化來改善覆蓋質(zhì)量就是要選擇合適的天線參數(shù)，使得RSRP最大化和SINR最小化。

目前，天線參數(shù)的優(yōu)化方法不僅有按照經(jīng)驗(yàn)和人工調(diào)節(jié)的方法或者按照一定的優(yōu)化算法如Powell搜索法，還有使用智能優(yōu)化算法如遺傳算法（GA，Genetic Algorithm）[2]和禁忌搜索算法（TS，Tabu Search）等[3-4]。人工測定調(diào)節(jié)需要消耗大量的人力物力，而Powell算法、GA算法和TS算法雖然都能起到良好的優(yōu)化效果，但是也存在局限性。在特定場景中，通過調(diào)節(jié)天線的下傾角、方位角、導(dǎo)頻功率來求解最優(yōu)的RSRP和SINR，實(shí)際上是一個(gè)NP完全（NPC，NP Complete）問題，需要指數(shù)級復(fù)雜度才能完全求解。

本文主要討論智能TS算法在天線參數(shù)優(yōu)化問題中的應(yīng)用，通過對TS算法引入網(wǎng)格化的局部搜索思路，輔以變步長的一維搜索方法，加快了局部搜索速度，再配合上TS算法本身不易于陷入局部極值陷阱的特點(diǎn)來獲得全局的極值結(jié)果。最后，配合多小區(qū)聯(lián)合調(diào)整的研究能獲得更好的小區(qū)覆蓋效果。

2 場景模型

在現(xiàn)代移動通信系統(tǒng)中，通常采用小區(qū)覆蓋的方式來解決信號覆蓋問題。即通過基站的天線覆蓋范圍，將整個(gè)區(qū)域劃分為若干小區(qū)，小區(qū)內(nèi)的終端用戶直接與該小區(qū)所屬基站進(jìn)行相互通信。在各種小區(qū)覆蓋方案里，蜂窩網(wǎng)絡(luò)是一種經(jīng)典的模型[5]。

如圖1所示，在典型的蜂窩網(wǎng)絡(luò)模型中，每個(gè)基站配有3根天線，3根天線各呈120°的夾角，將一個(gè)單元劃分為3個(gè)扇區(qū)，每個(gè)基站覆蓋1個(gè)菱形的區(qū)域。目前，主流的通信系統(tǒng)如CDMA2000、WCDMA網(wǎng)絡(luò)的基站以及LTE，都采用了類似的3根天線進(jìn)行覆蓋的方案。

但是在實(shí)際的工程應(yīng)用中，基站覆蓋形狀以及扇區(qū)數(shù)量是隨著實(shí)際需要而調(diào)整的。在基站分布不規(guī)則的前提下，只能通過調(diào)整天線的各種參數(shù)來使覆蓋范圍盡可能最大化。為了簡化這一問題的數(shù)學(xué)模型，一般工程實(shí)踐中只考慮天線的3個(gè)主要參數(shù)會對覆蓋造成巨大影響：水平方位角ψ、垂直下傾角γ和導(dǎo)頻功率C。其中，導(dǎo)頻功率C即為參考信號子載波（RS RE）上的發(fā)射功率。

圖1 一個(gè)典型的蜂窩網(wǎng)絡(luò)單元

3 數(shù)學(xué)建模

3.1 適應(yīng)度函數(shù)的構(gòu)造

假設(shè)Ω={C1,C2,…,Cn}為所有狀態(tài)構(gòu)成的解空間，其中Ci（i=1,2,…,n）表示待規(guī)劃小區(qū)的一種配置，由3個(gè)參數(shù)（x,y,z）組成，此處的x、y、z分別代表前一節(jié)所述的天線下傾角、方位角與參考信號功率，則目標(biāo)是求得該問題空間的一個(gè)最優(yōu)解，使小區(qū)天線參數(shù)可以表示為。

在考慮覆蓋規(guī)劃的最優(yōu)性能時(shí)，需要同時(shí)考慮基站對整個(gè)區(qū)域的覆蓋面積以及不同基站間的相互干擾問題。在通信領(lǐng)域里，可以使用RSRP與SINR作為指標(biāo)。在覆蓋區(qū)域的某點(diǎn)上，當(dāng)RSRP和SINR的計(jì)算值超過某一閾值時(shí)，則認(rèn)為該點(diǎn)被基站有效覆蓋。當(dāng)整個(gè)區(qū)域被有效覆蓋的面積最大時(shí)，可以認(rèn)為該覆蓋規(guī)劃取得了一個(gè)最優(yōu)解，則目標(biāo)函數(shù)定義為：

其中，f表示目標(biāo)函數(shù)；A代表整個(gè)規(guī)劃區(qū)域里RSRP超過某個(gè)規(guī)定閾值的面積占總面積的比值；B代表整個(gè)區(qū)域中SINR超過某個(gè)規(guī)定閾值的面積占總面積的比值；k1與k2為權(quán)重常量，這里規(guī)定k1+k2=1。

當(dāng)目標(biāo)函數(shù)取得最優(yōu)解fbest時(shí)，取得最優(yōu)解

可以決定實(shí)際調(diào)整天線時(shí)應(yīng)取的參數(shù)。

3.2 RSRP和SINR計(jì)算

按照COST231-Hata傳播模型，分別對RSRP和SINR給出定義：

終端的RSRP計(jì)算公式如下：

根據(jù)前述，基站天線增益（含水平和垂直方向）主要由各自的水平方向角和垂直下傾角決定。綜合以上分析，則目標(biāo)函數(shù)f的第一項(xiàng)A主要由ψ、γ和C決定。

假設(shè)傳輸功率是均勻地分布在所有的參考信號子載波上，則終端的參考信號的SINR計(jì)算公式如下：表示總的下行干擾；J表示UE能夠檢測到的在線小區(qū)的個(gè)數(shù)；

其中，表示j小區(qū)對用戶u的子載波發(fā)射功率造成的干擾；PNoise_RE為一個(gè)RE上的噪聲功率。

4 基于網(wǎng)格化的改進(jìn)禁忌搜索算法

4.1 算法選擇

由上節(jié)的定義可知，求解適應(yīng)度目標(biāo)函數(shù)f是一個(gè)NP問題，其復(fù)雜度會隨著扇區(qū)數(shù)量增加呈指數(shù)型增長，并且無法通過一個(gè)顯式的多項(xiàng)式來描述f，所以常用的基于導(dǎo)數(shù)的優(yōu)化算法并不適用于本問題。目前解決該優(yōu)化問題主要有不依賴導(dǎo)數(shù)的方法如Powell算法[6-7]，這類方法不要求目標(biāo)函數(shù)有導(dǎo)數(shù)，迭代比較簡單。但是在這個(gè)場景模型中，由于考慮工程天線可調(diào)最小刻度有限，Powell算法存在有若干次搜索后搜索方向失去共軛性的問題。實(shí)際工程方案一般先對RF參數(shù)按照連續(xù)的情況進(jìn)行優(yōu)化，然后將優(yōu)化結(jié)果取到其最接近的離散值。這種改進(jìn)后的Powell算法雖然可以不需要求導(dǎo)而快速迭代收斂，但存在容易陷入局部極值的問題。

此外，還可以使用智能算法，如遺傳算法就是一種比較常見的智能算法，廣泛應(yīng)用于各種工程領(lǐng)域[8-9]。與Powell算法相比，智能算法的優(yōu)勢在于可以有效求解全局極值，但是收斂速度較慢。

基于以上考慮，選取某一實(shí)際工程中的基站場景進(jìn)行初步的仿真分析，性能對比結(jié)果如圖2所示。可以看到，遺傳算法存在提升速度慢的明顯缺點(diǎn)，一般要在幾倍于改進(jìn)Powell算法所需迭代輪數(shù)的情況下才能達(dá)到相同的收斂程度。

圖2 GA算法和Powell算法效率局部對比

觀察圖3中50輪后遺傳算法最終適應(yīng)度0.963、Powell算法最終適應(yīng)度0.953，盡管遺傳算法比Powell算法有所提升，但是提升結(jié)果并不顯著。上圖驗(yàn)證了遺傳算法收斂速度不如Powell算法的猜測，這是由于遺傳算法在對子代進(jìn)行刪選時(shí)，并不能保證朝最優(yōu)解快速逼近。對于遺傳算法的最終結(jié)果相對于Powell算法沒有明顯提升主要是由于實(shí)驗(yàn)仿真的迭代輪數(shù)有限，遺傳算法在理論上經(jīng)過無窮多的迭代輪數(shù)，是可以達(dá)到極值點(diǎn)的。

通過實(shí)驗(yàn)分析了智能算法和非智能算法的實(shí)際表現(xiàn)，可以得出以下結(jié)論：

（1）類似于Powell算法的非智能算法有較好的收斂速度；

（2）非智能的Powell算法的確存在陷入局部極值的問題；

（3）遺傳算法存在性能提升緩慢的問題。

綜合以上結(jié)論，可選擇另一種智能算法——禁忌搜索算法（TS）。TS算法作為一種智能算法，也有避免局部極值的特點(diǎn)[10-11]，并且相當(dāng)多的研究表明TS算法適用于非連續(xù)問題的[12-13]。TS算法通過不同的領(lǐng)域構(gòu)造和搜索規(guī)則，使得可以調(diào)整向最優(yōu)解的前進(jìn)速度，這是遺傳算法無法比擬的優(yōu)勢。采用合適的TS算法，可以有效結(jié)合2種算法的優(yōu)點(diǎn)，避免它們的缺點(diǎn)。

圖3 GA算法和Powell算法完整對比

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

圖4 禁忌搜索算法流程

4.2 局部選擇算法

如圖4所示，禁忌算法的思想在于快速獲得一個(gè)局部極值，并把局部極值置于禁忌表中，進(jìn)而尋找下一個(gè)局部極值。這個(gè)搜索要求速度快，所以本文采用了變步長的一維搜索，但是在搜索方向上加以改進(jìn)。算法詳述如下：

借鑒網(wǎng)格法中的思路，網(wǎng)格中的搜索方向?yàn)槌跏键c(diǎn)與其臨近點(diǎn)組成的方向，如二維網(wǎng)格中，每個(gè)點(diǎn)有8個(gè)方向，分別為上、下、左、右、左上、左下、右上、右下，而在該工程的三維網(wǎng)格中，每個(gè)點(diǎn)有26個(gè)方向。

確定搜索方向后，在每個(gè)方向上必定能找到一個(gè)極大值點(diǎn)，所有方向上的極大值點(diǎn)組成候選解，選擇一個(gè)不在禁忌表中的最大候選解替換最早進(jìn)入禁忌表的對象，并把這個(gè)候選解作為下一輪的初始解，如果這個(gè)候選解大于當(dāng)前最優(yōu)解，則替換當(dāng)前最優(yōu)解。當(dāng)目標(biāo)函數(shù)f的提升度小于規(guī)定值ε后，得到的當(dāng)前最優(yōu)解即為算法輸出的優(yōu)化結(jié)果。

當(dāng)確定搜索方向后，尋找極值主要使用的一維搜索，通過智能調(diào)整步長使得搜索的次數(shù)減少，提高速度。具體流程如圖5所示：

圖5 變步長的一維搜索流程

其中，d為搜索方向向量；f為所求目標(biāo)函數(shù)值。當(dāng)沿某方向暫時(shí)沒有找到可行解時(shí)，倍增步長以擴(kuò)大搜索范圍；當(dāng)尋找到可行解時(shí)，在該可行解附近再減小步長進(jìn)行搜索。

另外，在網(wǎng)格中搜索時(shí)，已經(jīng)搜索過的點(diǎn)可以記錄其目標(biāo)值，當(dāng)下次再搜到這個(gè)點(diǎn)時(shí)，可以直接得到目標(biāo)值而不需要再調(diào)用求目標(biāo)值的函數(shù)，以提高效率。

5 仿真結(jié)果

5.1 性能驗(yàn)證

隨機(jī)挑選了挪威的5個(gè)實(shí)際基站場景，分別采用Powell法和網(wǎng)格禁忌法來計(jì)算目標(biāo)函數(shù)，并對它們的最終結(jié)果進(jìn)行統(tǒng)計(jì)，可得到如圖6所示的結(jié)果：

圖6 5個(gè)場景結(jié)果對比

由圖6可見，藍(lán)色和綠色的改進(jìn)方法在5個(gè)實(shí)際場景中的表現(xiàn)都優(yōu)于黃色的Powell法。而采用聯(lián)合調(diào)整的禁忌法時(shí)，在某些場景藍(lán)色相對于綠色結(jié)果有更進(jìn)一步的提高。但同時(shí)也可以看到，聯(lián)合調(diào)整有其局限性。當(dāng)場景類中基站布局較為稀疏時(shí)，采用聯(lián)合調(diào)整并無優(yōu)勢，反而降低了執(zhí)行效率，直接采用所提出的網(wǎng)格禁忌算法即可。而當(dāng)場景中有若干基站集中在一小塊區(qū)域時(shí)，則采用聯(lián)合調(diào)整具有優(yōu)勢。但是從所有隨機(jī)選取的5個(gè)場景結(jié)果來看，聯(lián)合調(diào)整在最終目標(biāo)函數(shù)上都不小于單獨(dú)調(diào)整的方案。

5.2 魯棒性驗(yàn)證

魯棒性（robustness）即指系統(tǒng)的強(qiáng)壯性，當(dāng)系統(tǒng)發(fā)生異常和危險(xiǎn)時(shí)的可靠性。在所研究的這個(gè)問題中，在實(shí)際調(diào)整天線的方向角和下傾角時(shí)，由于調(diào)節(jié)的誤差會導(dǎo)致實(shí)際結(jié)果與計(jì)算值產(chǎn)生偏差，所以需要考察這種情況下SINR和RSRP的變化。

由于實(shí)際應(yīng)用現(xiàn)場調(diào)整時(shí)不可能準(zhǔn)確地調(diào)節(jié)到優(yōu)化的參數(shù)值，如優(yōu)化參數(shù)為120°，實(shí)際調(diào)整時(shí)由于人為誤差等因素可能調(diào)整為120.5°。而魯棒性的驗(yàn)證就是要求在這種誤差的存在條件下，系統(tǒng)仍能有穩(wěn)定的性能表現(xiàn)。

現(xiàn)在根據(jù)已經(jīng)優(yōu)化過的算法計(jì)算結(jié)果為基準(zhǔn)，隨機(jī)改變計(jì)算結(jié)果中某些參數(shù)的值，可以是水平角或者下傾角，幅度為±1°，實(shí)際應(yīng)用中調(diào)整誤差可能小于1°，這里擴(kuò)大了誤差容易驗(yàn)證誤差帶來的影響。

魯棒性驗(yàn)證如圖7所示，在改變4至8個(gè)參數(shù)的情況下，各區(qū)間歸屬的百分比變化在0.5%以下，實(shí)際現(xiàn)場調(diào)整的誤差應(yīng)該在1°之內(nèi)，那么由誤差引起的性能下降更小。則根據(jù)實(shí)驗(yàn)結(jié)果分析，使用本文的優(yōu)化方法得到的解具有較好的魯棒性。

圖7 魯棒性驗(yàn)證

6 結(jié)束語

本文討論了現(xiàn)代通信系統(tǒng)中如何得到基站天線最優(yōu)參數(shù)配置的問題。通過建立對應(yīng)數(shù)學(xué)模型，提出了改進(jìn)的智能TS算法并進(jìn)行仿真比較，可以驗(yàn)證所提出的智能算法能有效地逼近全局最優(yōu)值。并且通過魯棒性實(shí)驗(yàn)可以證明算法得到的結(jié)果，在一定誤差存在的情況下并不會大幅度改變目標(biāo)函數(shù)，這說明該算法非常穩(wěn)定。此外，通過分析基站的位置信息，提出了在基站分布緊密時(shí)如何采用聯(lián)合多站調(diào)整的優(yōu)化流程。

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

[2] 陳寶林. 最優(yōu)化理論與算法[M]. 北京: 清華大學(xué)出版社, 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. 無約束最優(yōu)化與非線性方程的數(shù)值方法[M]. 北京: 科學(xué)出版社, 2010.

[7] 張立衛(wèi). 最優(yōu)化方法[M]. 北京: 科學(xué)出版社, 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.★

李鴻儒：博士畢業(yè)于上海交通大學(xué)，現(xiàn)任職于北京華龍通科技有限公司，主要研究方向?yàn)闊o線通信。

何迪：博士畢業(yè)于上海交通大學(xué)，現(xiàn)任職于上海交通大學(xué)，主要研究方向?yàn)闊o線通信。

工信部規(guī)范無人機(jī)頻段

為滿足應(yīng)急救災(zāi)、森林防火、環(huán)境監(jiān)測、科研實(shí)驗(yàn)等對無人駕駛航空器系統(tǒng)的需求，工信部對無人駕駛航空器使用頻段進(jìn)行了規(guī)定，劃出840—845MHz、1 430—1 444MHz和2 408—2 440MHz頻段用于無人駕駛航空器系統(tǒng)。

根據(jù)此次工信部要求，其中1 430—1 438MHz頻段將用于警用無人駕駛航空器和直升機(jī)視頻傳輸，而2 408—2 440MHz頻段可作為無人駕駛航空器系統(tǒng)上行遙控、下行遙測與信息傳輸鏈路的備份頻段。

據(jù)無人機(jī)生產(chǎn)商億航科技戰(zhàn)略合作總監(jiān)李智源介紹，在此次工信部出臺相關(guān)頻段規(guī)定前，并沒有專門的無人機(jī)專用頻段。

他指出，由于2.4GHz上解決方案相對比較成熟，目前國內(nèi)大多數(shù)無人機(jī)都是采用2.4GHz信號的無線電遙控器控制，所以此次頻段規(guī)劃并不會影響現(xiàn)有無人機(jī)的使用。

（C114中國通信網(wǎng)）

Application of Improved Tabu Search Algorithm in BS Antenna Parameter Optimization

LI Hong-ru1, HE Di2

(1. Beijing Hualongtong Technology Co., Ltd., Beijing 100083, China; 2. Academy of Information Technology and Electrical Engineering, School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

In modern mobile system, cell coverage is adopted to cover large areas that horizontal angle, vertical angle and pilot power are the important antenna parameters affecting base station (BS) coverage. Modeling the three parameters, an improved intelligent tabu search algorithm based on grid is proposed in this paper, which provides optimal signal coverage and antenna parameter confi guration.

coverage optimization intelligent optimization algorithm improved tabu search

10.3969/j.issn.1006-1010.2015.08.006

TN929

A

1006-1010(2015)08-0026-06

李鴻儒,何迪. 改進(jìn)禁忌搜索算法在基站天線參數(shù)優(yōu)化中的應(yīng)用[J]. 移動通信, 2015,39(8): 26-31.

2014-12-20

責(zé)任編輯：袁婷 yuanting@mbcom.cn