陳詩軍，王慧強(qiáng)，陳大偉，劉秀兵,胡海婧

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

1 引言

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

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

現(xiàn)有的基站布局優(yōu)化算法主要考慮的是基站的位置和數(shù)量對整體網(wǎng)絡(luò)覆蓋范圍和信號質(zhì)量的影響，優(yōu)化目標(biāo)是在滿足通信網(wǎng)絡(luò)建設(shè)目標(biāo)的前提下，考慮網(wǎng)絡(luò)容量、信號覆蓋范圍、通信質(zhì)量和成本等因素，形成最優(yōu)布局，沒有考慮用戶對室內(nèi)三維定位的需求?，F(xiàn)有基站布局算法可分為兩類：一類是基于隨機(jī)幾何的基站布局算法；另一類是基于多目標(biāo)優(yōu)化的基站布局智能算法。

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

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

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

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

2 禁忌搜索模型

禁忌搜索算法與其他智能優(yōu)化算法的主要區(qū)別是利用臨時記憶引導(dǎo)算法的搜索過程，它模擬了生物的記憶過程。禁忌搜索算法是在鄰域搜索的基礎(chǔ)上，通過禁忌規(guī)則來解鎖一些已禁忌的良好狀態(tài)，從而確保多種有效搜索，最終實(shí)現(xiàn)全局優(yōu)化。

2.1 鄰域搜索

鄰域搜索是基于貪心思想，在當(dāng)前解的鄰域中進(jìn)行搜索，搜索結(jié)果受鄰域產(chǎn)生規(guī)則和初始解的影響較大。鄰域搜索過程如下：

(1)給定初始解x0，該解為當(dāng)前問題的一種可行解；設(shè)置當(dāng)前最優(yōu)解xbest=x0，根據(jù)鄰域產(chǎn)生規(guī)則，產(chǎn)生當(dāng)前可選解的集合T=N(xbest)，其中N(xbest)為xbest的鄰域；之后執(zhí)行步驟(2)。

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

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

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

2.2 禁忌與解禁策略

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

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

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

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

3 改進(jìn)禁忌搜索的基站布局優(yōu)化算法

3.1 參數(shù)設(shè)計

(1)初始解。

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

(2)代價函數(shù)。

(3)鄰域產(chǎn)生規(guī)則。

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

(4)禁忌表。

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

Table 1 Properties of tabu objects

禁忌表記錄了最近搜索過程中已出現(xiàn)的解，禁止這些解在近期內(nèi)重復(fù)出現(xiàn)，從而避免陷入局部最優(yōu)解。在達(dá)到一定迭代次數(shù)后，禁忌表會依次釋放這些禁忌對象，禁忌對象被釋放后，可重新參與計算。因此，禁忌表的數(shù)據(jù)結(jié)構(gòu)設(shè)計為一定長度的先進(jìn)先出隊列。禁忌表的屬性如表2所示。

Table 2 Attributes of tabu table

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

(5)解禁規(guī)則。

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

(6)終止規(guī)則。

終止規(guī)則用來判斷算法是否可結(jié)束。本文中終止規(guī)則定為達(dá)到指定最大迭代次數(shù)。

(7)重復(fù)初始化。

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

3.2 算法設(shè)計

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

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

根據(jù)室內(nèi)三維定位需要，還另需要至少一層水平方向平面上的基站，這些基站同樣在水平方向平面上呈正六邊形“蜂窩”結(jié)構(gòu)。

當(dāng)前初始基站布局方案記為x0，記當(dāng)前最優(yōu)布局為xbest=x0，并根據(jù)當(dāng)前最優(yōu)布局產(chǎn)生可移動布局N(xbest)，候選布局隊列T=N(xbest)，其中N(xbest)表示xbest的可移動布局?；究稍谌S空間中x,y,z三個坐標(biāo)軸上進(jìn)行共計6種方向的單位移動，包括(-1,0,0)，(1,0,0)，(0,-1,0)，(0,1,0)，(0,0,-1)，(0,0,1)，其中0表示對應(yīng)的坐標(biāo)值不變，1表示對應(yīng)的坐標(biāo)向?qū)?yīng)坐標(biāo)軸正方向移動1單位距離move_dis，-1表示對應(yīng)的坐標(biāo)向?qū)?yīng)的坐標(biāo)軸負(fù)方向移動1單位距離move_dis。

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

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

4 算法仿真結(jié)果

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

4.1 仿真場景設(shè)置

驗證基站布局優(yōu)化算法的仿真場景如圖2所示，室內(nèi)環(huán)境為兩層，每層房間總長度為15.8 m，寬度為6.4 m，高度為6.3 m。設(shè)置墻體厚度為0.2 m，地板與天花板的厚度為0.1 m。其中，設(shè)置每個房間的長為5 m，寬為6 m，高為3 m?；静贾?2個，分為兩層布局，每層數(shù)量為6個。內(nèi)層基站之間的距離25 m，內(nèi)層和外層對應(yīng)基站的距離同樣為25 m。

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

4.2 實(shí)驗?zāi)康?/h3>

(1) 驗證ITSA算法的有效性。比較基站布局優(yōu)化算法前、改進(jìn)禁忌搜索算法和RFID讀寫器布局算法優(yōu)化后的數(shù)據(jù)，分析室內(nèi)三維定位算法的定位結(jié)果優(yōu)化情況，并根據(jù)實(shí)驗所得的定位誤差統(tǒng)計結(jié)果進(jìn)行分析。

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

4.3 仿真實(shí)驗分析

實(shí)驗1驗證ITSA算法的有效性。

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

Figure 3 Statistics of positioning error 圖3 定位誤差統(tǒng)計結(jié)果

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

進(jìn)行10 000次基站布局優(yōu)化定位算法，基站布局優(yōu)化前、ITSA算法優(yōu)化后和RFID讀寫器布局算法的定位算法統(tǒng)計特征值如表3所示。

Table 3 Statistical features of the positioning algorithm

實(shí)驗2考察ITSA算法的性能。

Figure 4 Statistics of placement optimization results 圖4 布局優(yōu)化結(jié)果統(tǒng)計

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

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

Table 4 GDOP positioning algorithm statistical features

5 結(jié)束語

本文提出的一種改進(jìn)禁忌搜索的基站布局優(yōu)化算法，改進(jìn)了代價函數(shù)、鄰域產(chǎn)生規(guī)則和解禁規(guī)則。在相同的室內(nèi)場景中，通過仿真實(shí)驗，相比RFID讀寫器部署優(yōu)化算法，該算法能夠更好地降低定位區(qū)域的整體誤差。ITSA算法對定位算法進(jìn)行基站布局優(yōu)化后，2.5～3 m的較大誤差范圍內(nèi)的定位結(jié)果比例降低了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.

附中文參考文獻(xiàn)：

[1] 謝代軍.無線局域網(wǎng)室內(nèi)定位技術(shù)研究[D].鄭州：解放軍信息工程大學(xué),2013:22-30.

[11] 鄧娜.基于隨機(jī)幾何的異構(gòu)蜂窩網(wǎng)建模分析與設(shè)計[D].合肥：中國科學(xué)技術(shù)大學(xué),2015:21-29.

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