敬遠(yuǎn)兵，李 奎

室內(nèi)導(dǎo)航改進(jìn)算法探究

敬遠(yuǎn)兵1，李 奎2

（1. 內(nèi)江師范學(xué)院 地理與資源科學(xué)學(xué)院，四川 內(nèi)江 641112；2. 西南交通大學(xué) 地球科學(xué)與環(huán)境工程學(xué)院，成都 611756）

針對室內(nèi)導(dǎo)航最優(yōu)路徑傳統(tǒng)A*算法研究絕大部分以2維空間路徑規(guī)劃為切入點，存在諸多局限且尚未解決室內(nèi)3維空間（多樓層）復(fù)雜環(huán)境下導(dǎo)航定位的最優(yōu)路徑規(guī)劃的問題，提出一種室內(nèi)導(dǎo)航改進(jìn)算法：在WiFi、二維碼等技術(shù)應(yīng)用于室內(nèi)導(dǎo)航定位的基礎(chǔ)上預(yù)先對室內(nèi)興趣點（POI）進(jìn)行分層分類處理，并通過映射建立POI與尋路節(jié)點的聯(lián)系；然后賦予電梯和樓梯聯(lián)通節(jié)點不同的權(quán)重，采用2種數(shù)據(jù)結(jié)構(gòu)來描述各層的尋路節(jié)點。實驗結(jié)果表明：改進(jìn)后的A*算法在室內(nèi)多層空間節(jié)點導(dǎo)航中具有普適性和可靠性，可保證復(fù)雜地圖環(huán)境下最優(yōu)路徑規(guī)劃導(dǎo)航的唯一性，能夠滿足室內(nèi)多層空間最優(yōu)路徑規(guī)劃導(dǎo)航及其個性化的需求。

室內(nèi)導(dǎo)航定位；最優(yōu)路徑；分層A*算法

0 引言

位置服務(wù)正迎來從室外導(dǎo)航向室內(nèi)外無縫定位導(dǎo)航發(fā)展的新紀(jì)元，融合導(dǎo)航衛(wèi)星與地面網(wǎng)絡(luò)的天地一體化室內(nèi)外無縫導(dǎo)航系統(tǒng)成為了國家重大發(fā)展戰(zhàn)略[1]。目前，室內(nèi)外高精度無縫導(dǎo)航定位已成為國內(nèi)外研究熱點，國內(nèi)外眾多學(xué)者在該領(lǐng)域進(jìn)行了大量研究，其中部分關(guān)鍵技術(shù)已取得一定突破，提出了一些普適性較強的解決方案和算法[2-4]。雖然文獻(xiàn)[5]對Okumura-Hata、Motley等多種適用性較好的室內(nèi)無線定位信號源傳播模型進(jìn)行了詳細(xì)介紹；但在室內(nèi)環(huán)境，無線定位信號主要通過衍射、散射等形式傳播，而樓層數(shù)量增加、墻壁類型的多樣化，使得信號衰減明顯，同時易受多徑傳播干擾，導(dǎo)致導(dǎo)航定位誤差加大，繼而起不到預(yù)想效果。因此，室內(nèi)導(dǎo)航定位受到定位時間、精度以及復(fù)雜室內(nèi)環(huán)境等條件限制，也受到多路徑的影響，室內(nèi)導(dǎo)航定位特別是個性化位置服務(wù)還存在諸多難題需要不斷研究加以解決。近年來，在室內(nèi)導(dǎo)航最優(yōu)路徑搜尋方面，文獻(xiàn)[6-7]提出通過對節(jié)點歸一化權(quán)值處理、調(diào)整A*算法代價函數(shù)值、增加尋路過程中用戶感興趣點備選可能性的方法提高室內(nèi)導(dǎo)航定位精度；文獻(xiàn)[8]提出了適用于不規(guī)則城市路網(wǎng)尋路的改進(jìn)A*算法，該方法亮點是該算法克服了死循環(huán)搜索問題；文獻(xiàn)[9-11]研究了搜尋多條最短路徑問題和對其他不同應(yīng)用環(huán)境分別提出了改進(jìn)的A*算法。但上述文獻(xiàn)大多針對電競游戲和城市道路網(wǎng)尋路問題而主要在2維平面路徑規(guī)劃方面進(jìn)行研究，故本文將室內(nèi)3維空間跨樓層環(huán)境下的路徑規(guī)劃導(dǎo)航算法作為探究的重點。

1 室內(nèi)無線定位方法

傳統(tǒng)室內(nèi)定位技術(shù)[12-13]定位原理主要為到達(dá)角(arrival of angle, AOA)、到達(dá)時(time of arrival, TOA)定位以及到達(dá)時間差(time difference of arrival, TDOA)定位；但在無線局域網(wǎng)(wireless local area networks, WLAN)環(huán)境中，由于無線信號接入點(access point, AP)密度較大，信號傳輸時延短，對終端探測設(shè)備靈敏度要求高，并且室內(nèi)信號傳播環(huán)境復(fù)雜，測量到的是在相位角和幅度有較大失真的復(fù)合信號，因此，上述定位方法均存在較大非視距誤差(no line of sight error, NLOS)。當(dāng)前，解決這一難題的主要方法是提交信號強度指示(received signal strength indication, RSSI)位置指紋匹配定位技術(shù)[14]，該方法首先在室內(nèi)位置提取來自AP點的信號強度，通過去噪處理后，連同采樣點位置信息一起作為特征參數(shù)存入指紋庫，定位終端測量其接收到的信號強度，與指紋庫進(jìn)行匹配計算，進(jìn)而計算出終端位置信息。這種方法最大的不足在于輸出的結(jié)果存在不連續(xù)和不穩(wěn)定問題，要實現(xiàn)對終端的連續(xù)平滑導(dǎo)航定位，需進(jìn)一步對結(jié)果后端濾波處理。另一方面，智能手機大多帶有慣性傳感器，如加速度計、羅盤等，這使得融合WLAN與行人航跡推算(pedestrian dead reckoning, PDR)的組合室內(nèi)導(dǎo)航定位成為可能，將顯著提高定位精度和可靠性。此外，2維碼技術(shù)近年來應(yīng)用于室內(nèi)導(dǎo)航定位，有效提升了終端初始化位置計算速度和精度，其提供的絕對位置信息直接解決了室內(nèi)定位誤差累計問題。對于室內(nèi)用戶而言，終端所處的高程（樓層信息）是一個短期不變量，在關(guān)鍵位置布設(shè)樓層切換信標(biāo)節(jié)點，利用所接收到的RSSI信號，采用基于信號強度遲滯輔助的算法就能實現(xiàn)無縫樓層切換，當(dāng)樓層信息確定后，終端的運動只需考慮和2個運動方向。完整的室內(nèi)個性化位置服務(wù)包括定位和導(dǎo)航2個方面，而定位方面近年來的研究基本解決，其導(dǎo)航方面的關(guān)鍵是為用戶快速規(guī)劃出室內(nèi)最優(yōu)路徑提供選擇性服務(wù)，這是本文將探究解決的主要內(nèi)容。

2 室內(nèi)最優(yōu)路徑導(dǎo)航算法

2.1 A*算法

路徑規(guī)劃算法核心思路主要是計算尋路節(jié)點圖中當(dāng)前節(jié)點(CN)與起始節(jié)點(IN)和目標(biāo)節(jié)點(GN)通路估價函數(shù)值。在個性化導(dǎo)航中，估價函數(shù)考慮用戶特定需求計算出綜合加權(quán)值；因此本文討論最優(yōu)路徑。常用尋路算法有2類：①只計算CN到IN代價函數(shù)，如Dijkstra、Floy算法；②帶有啟發(fā)式搜索算法，當(dāng)前最適合室內(nèi)導(dǎo)航的A*算法屬于這一類。其估價函數(shù)為

2.2 啟發(fā)函數(shù)特性分析

2.3 改進(jìn)的分層A*算法

傳統(tǒng)A*算法中，啟發(fā)函數(shù)通常采用的曼哈頓或歐式距離無法實現(xiàn)室內(nèi)個性化尋路，其對復(fù)雜室內(nèi)地圖環(huán)境適應(yīng)性較弱，同時存在搜索速率不高等缺陷。為實現(xiàn)室內(nèi)多層空間最優(yōu)路徑規(guī)劃，在此提出改進(jìn)的同時含有方向和距離約束的分層A*算法，其計算方法為

3 室內(nèi)地圖數(shù)據(jù)處理

表1 節(jié)點表數(shù)據(jù)結(jié)構(gòu)

4 實驗與結(jié)果分析

4.1 算法搜索步驟

4.2 模擬計算

利用搜集的某辦公樓建筑平面計算機輔助設(shè)計(computer aided design, CAD)圖為實驗對象（如圖1），在CAD圖上預(yù)先標(biāo)記POI點，根據(jù)室內(nèi)地圖的復(fù)雜程度與POI點密集程度定義尋路節(jié)點，根據(jù)POI點與尋路節(jié)點的相對位置確定映射關(guān)系，即各POI點映射在與之距離最近的尋路節(jié)點中。在統(tǒng)一平面坐標(biāo)系下制作室內(nèi)多層尋路節(jié)點圖（如圖2），使之在有效覆蓋整個地圖的同時，最大限度減少尋路節(jié)點數(shù)據(jù)量，把POI點與尋路節(jié)點分開表示，并通過映射關(guān)系聯(lián)系，以此達(dá)到降低尋路圖規(guī)模和提高搜索速率的目的。

圖1 樓層平面圖

在尋路節(jié)點圖中選取起點01009、終點04018，利用改進(jìn)后的分層A*算法計算與驗證。本次采用Python3.4編程計算結(jié)果：第一層計算完成后，OPEN集合給出的最優(yōu)路徑需要通過的聯(lián)通節(jié)點為[01009, 01017, 04017, 04018]；第二層計算執(zhí)行后，OPEN集合分別給出的節(jié)點為[01009, 01008, 01021, 01020, 01019, 01018, 01017]；[04017, 04018]。經(jīng)過節(jié)點回溯，最終路徑為：01009→01008→01021→01020→ 01019→01017→01017→04017→ 04018。

4.3 結(jié)果分析

為進(jìn)一步檢驗算法魯棒性和適用性，選取同樓層不同位置起終節(jié)點、跨單樓層不同位置起終節(jié)點和跨多樓層不同位置起終節(jié)點多次計算，將現(xiàn)場規(guī)劃出的最優(yōu)路徑與改進(jìn)后A*算法計算得到的路徑相比較，發(fā)現(xiàn)改進(jìn)后的分層A*算法總能快速搜尋一條通路，其尋得的路徑與人工實地預(yù)設(shè)的最優(yōu)路徑基本一致。圖3給出了改進(jìn)后分層A*算法尋得的4條代表性最優(yōu)路徑計算結(jié)果。

圖3 仿真結(jié)果

僅以距離約束方面考慮（由圖2可知），01009點到01017點還存在另一條最優(yōu)路徑：01009→ 01008→01007→01006→01005→01004→01017，該條路徑相較于前者，在01009點和01004點有2次直角轉(zhuǎn)向，而前者只在01021點有一次直角轉(zhuǎn)向。由于改進(jìn)的啟發(fā)函數(shù)包含方向約束信息，使得第二條路徑的估價函數(shù)值大于第一條，從而最終計算出的最優(yōu)路徑為第一條。對于01002點到02002點的尋路結(jié)果，因為起終點均靠近樓梯節(jié)點且只跨單樓層，算法給出的聯(lián)通節(jié)點不是與起終點距離較遠(yuǎn)的電梯節(jié)點。可以看出：本次實驗對電梯和樓梯節(jié)點賦予的權(quán)重是合理有效的。通過實驗結(jié)果分析得出改進(jìn)后算法具有以下基本優(yōu)點：

1）在估價函數(shù)中加入方向約束后，有效保證了最優(yōu)路徑的唯一性，同時實現(xiàn)了復(fù)雜室內(nèi)地圖環(huán)境下用戶直行的個性化需求，進(jìn)一步增強了算法對復(fù)雜室內(nèi)地圖環(huán)境的適應(yīng)性。

2）傳統(tǒng)A*算法啟發(fā)函數(shù)通常只考慮距離啟發(fā)信息且均采用單次計算，其應(yīng)用主要為2維平面的尋路，改進(jìn)后的A*算法采用分層計算的思想，實現(xiàn)了室內(nèi)3維空間跨樓層的最優(yōu)路徑尋路。

5 結(jié)束語

本文通過分析傳統(tǒng)導(dǎo)航算法，對3維空間下多樓層最優(yōu)路徑導(dǎo)航算法進(jìn)行改進(jìn)探究，采用改進(jìn)的分層A*算法進(jìn)行了仿真模擬實驗導(dǎo)航，解決了跨樓層節(jié)點最優(yōu)路徑規(guī)劃問題；綜合室內(nèi)復(fù)雜地圖環(huán)境下用戶對距離最短和直行的需求，在第二層計算中，引入同時考慮方向和距離啟發(fā)信息的啟發(fā)函數(shù)，把POI點與尋路節(jié)點分開處理，以映射的方式建立聯(lián)系，有效避免了直接搜尋POI節(jié)點數(shù)據(jù)量大、速率低的問題。仿真實驗結(jié)果表明，改進(jìn)的分層A*算法能以較好的魯棒性應(yīng)用于跨樓層最優(yōu)路徑規(guī)劃，具有較強可靠性，無論是改進(jìn)前還是改進(jìn)后的算法，其運算速率取決于節(jié)點的數(shù)量和算法本身的復(fù)雜度。本次實驗僅對室內(nèi)地圖數(shù)據(jù)進(jìn)行合理的處理，建立POI點與尋路節(jié)點映射關(guān)系后，較好地提高了A*算法搜索速率。對于室內(nèi)POI點密集程度高且不規(guī)則的大型城市建筑而言，其POI點和尋路節(jié)點數(shù)多達(dá)數(shù)千個，如何提高室內(nèi)尋路算法運算速率還需進(jìn)一步研究。

[1] PRIYANTHA N B, CHAKRABORTY A, BALAKRISHNAN H. The cricket location-support system[C]//Association for Computing Machinery(ACM).Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. Boston,Massachusetts:Association for Computing Machinery,Inc., 2000:32-43.

[2] KUSHKI A, PLATANIOTIS K N, VENETSANOPOULOS A N. Kernel-based positioning in wireless local area networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(6): 689-705.

[3] FANG S H, LIN T N, LIN P C.Location fingerprinting in a decorrelated space[J].IEEE Transactions on Knowledge and Data Engineering, 2008, 20(5): 685-691.

[4] FANG S H, LIN T N. Projection-based location system via multiple discriminant analysis in wireless local area networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(9): 5009-5019.

[5] 鄧中亮, 余彥培, 徐連明, 等. 室內(nèi)外無線定位與導(dǎo)航[M]. 北京: 北京郵電大學(xué)出版社,2013.

[6] 卞維駿. 個性化室內(nèi)導(dǎo)航研究[D]. 武漢: 武漢理工大學(xué), 2015.

[7] 史輝, 曹聞. A*算法的改進(jìn)及其在路徑規(guī)劃中的應(yīng)用[J]. 測繪與空間地理信息, 2012, 32(6): 209-211.

[8] 漆陽華, 楊戰(zhàn)平. A*的改進(jìn)路徑規(guī)劃算法[J]. 信息與電子工程, 2009, 7(4): 327-329.

[9] 王樹西, 李安渝. Dijkstra算法中的多鄰接點與多條最短路徑問題[J]. 計算機科學(xué), 2014,41(6): 217-221.

[10] 譚寶成, 王培. A*路徑規(guī)劃算法的改進(jìn)及實現(xiàn)[J].西安工業(yè)大學(xué)學(xué)報, 2012, 32(4):325-329.

[11] 武雪玲, 李清泉, 任副.基于分層分塊數(shù)據(jù)組織的雙向A*算法[J]. 測繪信息工程, 2006, 31(6): 1-3.

[12] 顏俊杰. 基于WIFI的室內(nèi)定位技術(shù)研究[D]. 廣州:華南理工大學(xué), 2013.

[13] 范霄. 基于WIFI的無線室內(nèi)定位[D]. 青島: 山東科技大學(xué), 2013.

[14] BAHL P, PADMANABHAN V N.Radar:an in-building RF-based user location and tracking system[C]//The Institute of Electrical and Electronic Engineers(IEEE).Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv, Israel: IEEE, 2000: 775-784.

[15] 熊偉, 張仁平. A*算法及其在地理信息系統(tǒng)中的應(yīng)用[J]. 計算機系統(tǒng)應(yīng)用, 2007, 22(4): 15-17.

[16] 鐘敏. A*算法估價函數(shù)特性分析[J]. 武漢工程職業(yè)技術(shù)學(xué)院學(xué)報, 2006, 18(2): 32-33.

Discussion on improved algorithm of indoor navigation

JING Yuanbing1, LI Kui2

（1.Shcool of Geography and Resources Science, Neijiang Normal University, Neijiang, Sichuan 641112, China;2.Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chendu 611756, China）

Aiming at the problems that there exists limitation in the study on traditional A* algorithm for the optimal path-planning of indoor navigation which usually starts from two-dimensional spatial path-planning, and it is still unsolved for optimal path-planning of indoor navigation under the complex environment of three-dimensional space (multi-floor), the paper proposed an improved algorithm of indoor navigation: the hierarchical classification of indoor POI nodes was carried out with the technology of WiFi and QR-code, and the connection between POI points and route-seeking nodes was established by mapping; by assigning different weights to elevator and staircase connection nodes respectively, two kinds of data structures were used to describe the path finding nodes of each layer. Experimental result showed that the improved A* algorithm would be universal and reliable in the indoor navigation with multi-layer space nodes, and the uniqueness of the optimal path-planning navigation under complex map environment could be guaranteed, which could meet the requirements of optimal path-planning navigation in indoor multi-layer space for personalized needs.

indoor navigation and positioning; optimal path; hierarchical A* algorithm

P228

A

2095-4999(2019)04-0037-05

敬遠(yuǎn)兵，李奎.室內(nèi)導(dǎo)航改進(jìn)算法探究[J].導(dǎo)航定位學(xué)報,2019,7(4): 37-41.（JING Yuanbing，LI Kui.Discussion on improved algorithm of indoor navigation[J].Journal of Navigation and Positioning,2019,7(4): 37-41.）

10.16547/j.cnki.10-1096.20190407.

2019-02-16

四川省教育廳資助科研項目（18ZB0320)。

敬遠(yuǎn)兵（1977—），四川安岳人，本科，高級工程師，研究方向為衛(wèi)星導(dǎo)航定位應(yīng)用。