基于改進禁忌搜索的基站布局優化算法

陳詩軍，王慧強，陳大偉，劉秀兵,胡海婧

(1.中興通訊股份有限公司無線預研部，廣東 深圳 518055；2.哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150001)

1 引言

隨著社會的快速發展，人們更多時間是在室內活動，對室內位置服務的需求與日俱增。美國通信委員會的E-911 條例強制性要求公共網絡在任何時間、地點，都能通過無線信號追蹤到用戶的位置[1]。用戶對位置服務的需求不斷提高。目前GPS、北斗等衛星定位方式的室外定位精度在十幾米到幾十米之間，而藍牙、WIFI、UWB(Ultra-Wide Band)定位的使用場景受限，大量研究都認為在即將到來的5G時代，蜂窩網將是室內外一體化定位的首選技術[2]。鑒于室內環境的非視距等諸多特性，基站布局的目的就是在不增加硬件設施成本的同時擴大信號覆蓋面積，從而提高定位精度，合理的基站布局顯得尤為重要。

基站布局的優化能夠大大提高定位終端的定位精度，根據基站選擇算法來選擇到定位點有首徑信號的基站[3]，可以縮小定位誤差，得到更好的定位精度。

現有的基站布局優化算法主要考慮的是基站的位置和數量對整體網絡覆蓋范圍和信號質量的影響，優化目標是在滿足通信網絡建設目標的前提下，考慮網絡容量、信號覆蓋范圍、通信質量和成本等因素，形成最優布局，沒有考慮用戶對室內三維定位的需求。現有基站布局算法可分為兩類：一類是基于隨機幾何的基站布局算法；另一類是基于多目標優化的基站布局智能算法。

在隨機幾何方面，Andrews[4]首次用齊次泊松點過程建模蜂窩網絡的布局，并分析了覆蓋率、可達速率這兩個性能指標。但是，齊次泊松點過程仍不是一個理想的模型，用該方案建模蜂窩網絡中的基站位置則意味著所部署的基站相互間是完全獨立的[5]。隨著蜂窩網絡逐漸向多層異構通信網絡的方向進行演變，為了更準確地建模蜂窩網絡的站點排布，近年來出現了許多新興的點過程,例如硬核過程HCP(Hard-Core Processes)[6]、泊松簇過程PCP(Poisson Cluster Process) 以及擾動格型PL(Perturbed Lattice)[7]等等。這些點過程最主要的缺陷就是難以用于分析，限制了它們在無線網絡中的進一步應用。

基于多目標優化的基站布局智能算法由于適應性較強，易于建模等優勢更為常用，對此國內外學者提出了許多智能算法。文獻[8]提出了基于模擬退火SA(Simulated Annealing)算法的解決方案，但模擬退火算法中的“溫度”初始值以及下降速率需要重復多次實驗才能確定。文獻[9]的粒子群算法又稱蟻群算法，基于群智能優化的思想，在應用到基站優化問題時，易于修改目標函數，并且可并行實現，可擴展性較優，但由于種群在搜索空間中丟失了較多的多樣性信息，易陷入局部最優解。文獻[10]提出了基于傳統遺傳算法GA(Genetic Algorithm)布局方案，引入Pareto最優域，提出了高性能的NSGA-II 算法，該算法屬于啟發式搜索算法，也易于改寫為并行處理版本，但全局搜索能力不強，易陷入局部最優解[11]。

文獻[12]為解決WSN(Wireless Sensor Network)中RFID(Radio Frequency IDentification) 定位場景中的讀寫器布局問題，提出了一種RFID讀寫器部署算法，該方法基于禁忌搜索算法，考察了讀寫器布局對定位精度的影響，并結合禁忌搜索策略來尋找最優布局方案，但是沒有考慮覆蓋區域存在障礙物的情況，如果使用在室內現實情況，定位誤差會大大提高。

基于以上研究與分析，本文提出一種改進禁忌搜索算法應用于基站布局優化，該算法基于禁忌搜索模型，迭代更新候選基站布局列表，實現基站布局的局部尋優過程。為驗證改進禁忌搜索算法的有效性，該算法與文獻[12]提出的RFID讀寫器布局算法進行了性能對比實驗。

2 禁忌搜索模型

禁忌搜索算法與其他智能優化算法的主要區別是利用臨時記憶引導算法的搜索過程，它模擬了生物的記憶過程。禁忌搜索算法是在鄰域搜索的基礎上，通過禁忌規則來解鎖一些已禁忌的良好狀態，從而確保多種有效搜索，最終實現全局優化。

2.1 鄰域搜索

鄰域搜索是基于貪心思想，在當前解的鄰域中進行搜索，搜索結果受鄰域產生規則和初始解的影響較大。鄰域搜索過程如下：

(1)給定初始解x0，該解為當前問題的一種可行解；設置當前最優解xbest=x0，根據鄰域產生規則，產生當前可選解的集合T=N(xbest)，其中N(xbest)為xbest的鄰域；之后執行步驟(2)。

(2)當T-xbest=?，即當前可選解僅包含當前最優解一個元素時，或滿足其他停止運算規則(例如最大迭代次數的限制等規則)時，輸出當前最優解xbest，停止運算；否則，執行步驟(3)。

(3)從T中選取集合S，并獲取S中的最優解作為當前評估解xnow；若f(xnow)

步驟(1)中的初始解可隨機生成，也可根據經驗或其他算法得到；N(xbest)為xbest的鄰域，鄰域指的是當前最優解經過一定范圍內的變化，形成一組可選解，這種變化稱為“移動”，該組解是否可行需要執行后續步驟來判斷。步驟(2)中的停止運算規則，一般包括T為空、達到規定最大迭代次數、超過規定最大運行時間等。步驟(3)中的S的集合選取方式較為靈活，S可選取為全部T，也可以只選T中的最優解。S的元素多，則迭代過程中的計算量將增大，但產生的可選解較多；S的元素少，則計算量將減少，但產生的可選解很少。針對問題的不同場景，可采取不同的選擇方式。

2.2 禁忌與解禁策略

鄰域搜索基于貪心思想，導致搜索結果比較依賴初始解的設置和鄰域產生規則，若初始解的代價值過高，或鄰域產生的可選范圍較小，則最終搜索結果會比較差，搜索過程中易陷入局部最優解。為了實現全局尋優，算法采取“禁止最近已訪問解”的禁忌策略，并接受一些次優解，避免在局部最優解中死循環。

禁忌策略是一種“記憶”過程，記錄已經進行過的優化過程，加入到禁忌表中。禁忌表中保存了最近迭代過程中已經進行過的“移動”，位于禁忌表中的移動作為禁忌對象，在當前的迭代過程中是不能作為可選解或是最優解被訪問的。這種禁忌策略可防止局部最優解的死循環。

為了盡可能達到可產生最優解的移動，禁忌搜索還引入了“解禁策略”。對當前最優解xbest，在其鄰域范圍內進行移動產生一組可選解，從可選解中選出最優可選解xnow，并將該最優可選解的代價f(xnow) 與best_so_far進行比較，若f(xnow)優于best_so_far，則將xnow解禁，并用xnow替代xbest，f(xnow)替代best_so_far，更新禁忌表中禁忌對象的禁忌長度，然后將xnow加入禁忌表。

如果不存在代價值優于best_so_far的可選解，則從當前可選解中獲取未禁忌的最優解，并將該解作為當前解，不與當前最優解進行比較，更新禁忌表中禁忌對象的禁忌長度，然后將該解加入禁忌表。

3 改進禁忌搜索的基站布局優化算法

3.1 參數設計

(1)初始解。

本文中初始解表示初始基站布局，初始基站布局在水平方向呈正六邊形“蜂窩”結構均勻分布。在垂直方向上，根據定位場景的空間范圍，每一定高度都布局一層這種“蜂窩”結構均勻分布的基站。為防止初始解代價過高，通過執行多次禁忌搜索算法，將上一次得到的優化布局作為下一次禁忌搜索的初始解，從而擴大可選解范圍，避免陷入局部最優。

(2)代價函數。

(3)鄰域產生規則。

本文中的鄰域產生規則是對基站進行各方向上的移動。具體指的是基站三維空間中x,y,z三個坐標軸方向上可進行共計6種方向的單位移動，包括(-1,0,0)，(1,0,0)，(0,-1,0)，(0,1,0)，(0,0,-1)，(0,0,1)，其中0表示對應的坐標值不變，1表示對應的坐標向對應坐標軸正方向移動1個單位距離。

(4)禁忌表。

本文所指的禁忌對象屬性如表1所示。

Table 1 Properties of tabu objects

禁忌表記錄了最近搜索過程中已出現的解，禁止這些解在近期內重復出現，從而避免陷入局部最優解。在達到一定迭代次數后，禁忌表會依次釋放這些禁忌對象，禁忌對象被釋放后，可重新參與計算。因此，禁忌表的數據結構設計為一定長度的先進先出隊列。禁忌表的屬性如表2所示。

Table 2 Attributes of tabu table

解在加入禁忌表時，均需要設置禁忌長度。在解加入禁忌表的同時，需要為其初始化禁忌長度，并記錄加入禁忌表時該解的代價值，算法每次操作禁忌表(加入禁忌對象、解禁禁忌對象)時，將更新一次禁忌表已有元素，已有元素的禁忌長度自動減1，當元素的禁忌長度為0時，將自動從禁忌表中移除。

(5)解禁規則。

在本文中，解禁規則考慮了適配值以及搜索方向兩種因素，當優于best_so_far狀態的可選解已被禁忌時，解禁此可選解，并將best_so_far狀態替換為該可選解。否則若所有可選解均被解禁，也不存在優于best_so_far的可選解，則選擇代價值對比禁忌表中代價值有所降低的可選解進行解禁；否則若不存在代價已降低的可選解，則在禁忌表中找到代價最低的解進行解禁。

(6)終止規則。

終止規則用來判斷算法是否可結束。本文中終止規則定為達到指定最大迭代次數。

(7)重復初始化。

每一次執行算法時，初始布局是前一次產生的最優布局。在很多情況下，重新初始化后產生的可選解空間將與上一次的可選解空間不同，因此能夠更好地避免陷入局部最優解。

3.2 算法設計

(1)選定一個初始基站布局方案，并設定最大迭代次數、定位區域、定位請求次數request_num、基站單位移動距離move_dis、已計算布局隊列最大長度H_length，當前迭代次數初始化為0，已計算布局隊列H初始化為空。初始基站布局中，在水平方向平面上各個基站呈正六邊形“蜂窩”結構，使定位區域包含在基站的覆蓋范圍內。根據基站數量不同，初始基站布局示例如圖1所示。

Figure 1 Example of an initial base station placement scenario圖1 初始基站布局方案示例

根據室內三維定位需要，還另需要至少一層水平方向平面上的基站，這些基站同樣在水平方向平面上呈正六邊形“蜂窩”結構。

當前初始基站布局方案記為x0，記當前最優布局為xbest=x0，并根據當前最優布局產生可移動布局N(xbest)，候選布局隊列T=N(xbest)，其中N(xbest)表示xbest的可移動布局。基站可在三維空間中x,y,z三個坐標軸上進行共計6種方向的單位移動，包括(-1,0,0)，(1,0,0)，(0,-1,0)，(0,1,0)，(0,0,-1)，(0,0,1)，其中0表示對應的坐標值不變，1表示對應的坐標向對應坐標軸正方向移動1單位距離move_dis，-1表示對應的坐標向對應的坐標軸負方向移動1單位距離move_dis。

(2)從候選布局隊列中取出最優布局方案，并將最優布局方案從候選布局隊列中刪除。最優布局方案指的是在候選布局隊列中，產生的定位結果平均定位誤差最小的方案，即為各基站的三維坐標，記為xnow。平均定位誤差指的是在request_num次定位請求中，待定位節點定位結果與真實坐標的歐氏距離的平均值，記xnow的平均定位誤差為f(xnow) 。此時若達到最大迭代次數，或候選布局隊列為空時，輸出當前最優布局，停止運算；否則，轉(3)。

(3)考察候選布局隊列中最優的布局方案xnow的誤差，若f(xnow)f(xbest)，則執行(1)，繼續迭代過程。

4 算法仿真結果

為驗證ITSA(Improved Tabu Search Algorithm)算法的有效性，并評估其性能，本文利用MatLab模擬室內場景對基站布局優化算法進行仿真，測試其功能，并與現有的基站布局算法進行對比，驗證ITSA算法的性能。

4.1 仿真場景設置

驗證基站布局優化算法的仿真場景如圖2所示，室內環境為兩層，每層房間總長度為15.8 m，寬度為6.4 m，高度為6.3 m。設置墻體厚度為0.2 m，地板與天花板的厚度為0.1 m。其中，設置每個房間的長為5 m，寬為6 m，高為3 m。基站布置12個，分為兩層布局，每層數量為6個。內層基站之間的距離25 m，內層和外層對應基站的距離同樣為25 m。

Figure 2 Positioning the simulation scenario圖2 定位仿真場景

4.2 實驗目的

(1) 驗證ITSA算法的有效性。比較基站布局優化算法前、改進禁忌搜索算法和RFID讀寫器布局算法優化后的數據，分析室內三維定位算法的定位結果優化情況，并根據實驗所得的定位誤差統計結果進行分析。

(2) 考察ITSA算法的性能。將本文提出的基站布局優化算法與文獻[12]提出的RFID讀寫器部署算法進行性能對比，并根據實驗所得的幾何精度因子GDOP(Geometric Dilution Precision)[13]特征值對定位結果進行分析。

4.3 仿真實驗分析

實驗1驗證ITSA算法的有效性。

按照4.1節中介紹的定位場景，設定位區域為基站覆蓋的房屋內部，根據房屋的空間限制，設置用戶設備的可移動范圍為x軸0.2～15 m，y軸0.2～6 m，z軸0.2～6 m。默認測距信息噪聲服從均值為0，方差為1的高斯分布，比較基站布局優化算法前和使用兩種優化算法后的結果，隨機抽取定位區域中的10 000個點進行定位，得到的定位誤差統計結果如圖3所示。

Figure 3 Statistics of positioning error 圖3 定位誤差統計結果

由圖3可知，基站布局優化前得到的定位結果均大部分處于1.5～2 m的誤差范圍，但在基站優化前，有34.15%的定位結果處于2～2.5 m的誤差范圍內，且處于1～1.5 m的較小誤差范圍內的定位結果僅占12.39%；經過ITSA算法優化后，1～1.5 m誤差范圍內的定位結果比例提高了28.6%，相比RFID讀寫器布局算法提高了9.09%，2.5～3 m的較大誤差范圍內的定位結果比例降低了17.65%。

進行10 000次基站布局優化定位算法，基站布局優化前、ITSA算法優化后和RFID讀寫器布局算法的定位算法統計特征值如表3所示。

Table 3 Statistical features of the positioning algorithm

實驗2考察ITSA算法的性能。

Figure 4 Statistics of placement optimization results 圖4 布局優化結果統計

圖4中，圓點表示基站，上三角點表示對應位置的GDOP值在1.2以下，方塊點表示GDOP值在1.2～1.3，下三角點表示GDOP在1.3～1.4，六芒星點表示GDOP值在1.4以上。對比三種布局，GDOP值的分布情況總結如表4所示。

由表4可知，相比RFID讀寫器部署優化算法，本文提出的布局優化算法整體降低了GDOP值，與優化前的布局相比,GDOP≤1.2的比例提升了1.3%,GDOP>1.4的比例降低了2.13%；與RFID讀寫器部署優化算法相比,GDOP≤1.2的比例提升了0.1%,GDOP>1.4的比例降低了6.7%，說明ITSA算法能夠較好地提升定位效果。

Table 4 GDOP positioning algorithm statistical features

5 結束語

本文提出的一種改進禁忌搜索的基站布局優化算法，改進了代價函數、鄰域產生規則和解禁規則。在相同的室內場景中，通過仿真實驗，相比RFID讀寫器部署優化算法，該算法能夠更好地降低定位區域的整體誤差。ITSA算法對定位算法進行基站布局優化后，2.5～3 m的較大誤差范圍內的定位結果比例降低了17.65%。

[1] Xie Dai-jun. Research on indoor localization technology of wireless local area network[D].Zhengzhou:People’s Liberation Army Information Engineering University,2013:22-30.(in Chinese)

[2] Zhou Y F, Zhao Z F, Zhang H G. Towards 5G:Heterogeneous cellular network architecture design based on intelligent SDN paradigm[J].Telecommunications Science,2016,32(6):28.

[3] Liu J,Yang Q,Simon G.Optimal and practical algorithms for implementing wireless CDN based on base stations[C]∥Proc of 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring),2016:article 331,1-5.

[4] Andrews J G, Baccelli F, Ganti R K. A tractable approach to coverage and rate in cellular networks[J]. IEEE Transactions on Communications, 2011, 59(11): 3122-3134.

[5] Andrews J G,Gupta A K,Dhillon H S.A primer on cellular network analysis using stochastic geometry[J].arXiv preprint arXiv:1604.03183v2,2016.

[6] Chen M,Hu Y,Yin C.Tri-sectoring and power allocation of macro base stations in heterogeneous cellular networks with Matern Hard-Core Processes[C]∥Proc of 2016 IEEE 83rd Vehicular Technology Conference (VTC Spring),2016:article 461,1-5.

[7] Banani S A,Adve R S,Eckford A W.A perturbed hexagonal lattice to model base station locations in real-world cellular networks[C]∥Proc of Globecom Workshops (GC Wkshps),2015:1-6.

[8] Zhang H,Zhang S,Bu W.A clustering routing protocol for energy balance of wireless sensor network based on simulated annealing and genetic algorithm[J].International Journal of Hybrid Information Technology,2014,7(2):71-82.

[9] Pereira M B,Cavalcanti F R P,Maciel T F.Particle swarm optimization for base station placement[C]∥Proc of the 2014 International Conference on Telecommunications Symposium (ITS),2014:1-5.

[10] Meng H,Long F,Guo L,et al.Cooperrating base station location optimization using genetic algorithm[C]∥Proc of 2016 IEEE Conference on Control and Decision(CCDC),2016:4820-4824.

[11] Deng Na.Modeling and design of heterogeneous cellular networks based on random geometry[D].Hefei:China University of Science and Technology,2015:21-29.(in Chinese)

[12] Wang Yong-hua, Yang Jian,Zhan Yi-ju, et al. RFID networks planning based on tabu search algorithms[J]. Application Research of Computers,2011,28(6):2116-2119.(in Chinese)

[13] Feng G,Shen C,Long C,et al.GDOP index in UWB indoor location system experiment[C]∥Proc of SENSORS’15,2015:1-4.

附中文參考文獻：

[1] 謝代軍.無線局域網室內定位技術研究[D].鄭州：解放軍信息工程大學,2013:22-30.

[11] 鄧娜.基于隨機幾何的異構蜂窩網建模分析與設計[D].合肥：中國科學技術大學,2015:21-29.

[12] 王永華,楊健,詹宜巨,等.一種基于禁忌搜索的 RFID 讀寫器部署算法[J].計算機應用研究,2011,28(6):2116-2119.