李鴻儒，何 迪

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

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

李鴻儒1，何 迪2

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

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

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

1 引言

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

目前，天線參數(shù)的優(yōu)化方法不僅有按照經(jīng)驗和人工調(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é)天線的下傾角、方位角、導頻功率來求解最優(yōu)的RSRP和SINR，實際上是一個NP完全（NPC，NP Complete）問題，需要指數(shù)級復雜度才能完全求解。

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

2 場景模型

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

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

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

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

3 數(shù)學建模

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

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

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

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

當目標函數(shù)取得最優(yōu)解fbest時，取得最優(yōu)解

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

3.2 RSRP和SINR計算

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

終端的RSRP計算公式如下：

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

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

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

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

4.1 算法選擇

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

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

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

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

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

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

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

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

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

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

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

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

圖4 禁忌搜索算法流程

4.2 局部選擇算法

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

借鑒網(wǎng)格法中的思路，網(wǎng)格中的搜索方向為初始點與其臨近點組成的方向，如二維網(wǎng)格中，每個點有8個方向，分別為上、下、左、右、左上、左下、右上、右下，而在該工程的三維網(wǎng)格中，每個點有26個方向。

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

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

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

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

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

5 仿真結(jié)果

5.1 性能驗證

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

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

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

5.2 魯棒性驗證

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

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

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

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

圖7 魯棒性驗證

6 結(jié)束語

本文討論了現(xiàn)代通信系統(tǒng)中如何得到基站天線最優(yōu)參數(shù)配置的問題。通過建立對應數(shù)學模型，提出了改進的智能TS算法并進行仿真比較，可以驗證所提出的智能算法能有效地逼近全局最優(yōu)值。并且通過魯棒性實驗可以證明算法得到的結(jié)果，在一定誤差存在的情況下并不會大幅度改變目標函數(shù)，這說明該算法非常穩(wěn)定。此外，通過分析基站的位置信息，提出了在基站分布緊密時如何采用聯(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]. 北京: 清華大學出版社, 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]. 北京: 科學出版社, 2010.

[7] 張立衛(wèi). 最優(yōu)化方法[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.★

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

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

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

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

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

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

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

（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

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

2014-12-20

責任編輯：袁婷 yuanting@mbcom.cn