室內導航改進算法探究

敬遠兵，李 奎

室內導航改進算法探究

敬遠兵1，李 奎2

（1. 內江師范學院 地理與資源科學學院，四川 內江 641112；2. 西南交通大學 地球科學與環境工程學院，成都 611756）

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

室內導航定位；最優路徑；分層A*算法

0 引言

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

1 室內無線定位方法

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

2 室內最優路徑導航算法

2.1 A*算法

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

2.2 啟發函數特性分析

2.3 改進的分層A*算法

傳統A*算法中，啟發函數通常采用的曼哈頓或歐式距離無法實現室內個性化尋路，其對復雜室內地圖環境適應性較弱，同時存在搜索速率不高等缺陷。為實現室內多層空間最優路徑規劃，在此提出改進的同時含有方向和距離約束的分層A*算法，其計算方法為

3 室內地圖數據處理

表1 節點表數據結構

4 實驗與結果分析

4.1 算法搜索步驟

4.2 模擬計算

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

圖1 樓層平面圖

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

4.3 結果分析

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

圖3 仿真結果

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

1）在估價函數中加入方向約束后，有效保證了最優路徑的唯一性，同時實現了復雜室內地圖環境下用戶直行的個性化需求，進一步增強了算法對復雜室內地圖環境的適應性。

2）傳統A*算法啟發函數通常只考慮距離啟發信息且均采用單次計算，其應用主要為2維平面的尋路，改進后的A*算法采用分層計算的思想，實現了室內3維空間跨樓層的最優路徑尋路。

5 結束語

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

[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] 鄧中亮, 余彥培, 徐連明, 等. 室內外無線定位與導航[M]. 北京: 北京郵電大學出版社,2013.

[6] 卞維駿. 個性化室內導航研究[D]. 武漢: 武漢理工大學, 2015.

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

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

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

[10] 譚寶成, 王培. A*路徑規劃算法的改進及實現[J].西安工業大學學報, 2012, 32(4):325-329.

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

[12] 顏俊杰. 基于WIFI的室內定位技術研究[D]. 廣州:華南理工大學, 2013.

[13] 范霄. 基于WIFI的無線室內定位[D]. 青島: 山東科技大學, 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*算法及其在地理信息系統中的應用[J]. 計算機系統應用, 2007, 22(4): 15-17.

[16] 鐘敏. A*算法估價函數特性分析[J]. 武漢工程職業技術學院學報, 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

敬遠兵，李奎.室內導航改進算法探究[J].導航定位學報,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)。

敬遠兵（1977—），四川安岳人，本科，高級工程師，研究方向為衛星導航定位應用。