面向大型建筑物的室內導航系統開發

李 盟，楊 靜，邵薪儒

(天津城建大學 控制與機械工程學院，天津300384)

信息科學與技術

面向大型建筑物的室內導航系統開發

李 盟，楊 靜，邵薪儒

(天津城建大學 控制與機械工程學院，天津300384)

為提高大型建筑物內資源利用效率，針對建筑物內環境復雜、無法利用衛星導航信號等因素導致的導航精度差的問題，利用建筑物內已覆蓋的無線網絡信號，開發一套基于無線網絡定位技術的室內導航系統．為滿足大型公共建筑物內導航精度的要求，提出一種加入信號傳播模型修正的加權K近鄰算法，以提高傳統位置指紋定位方法的定位精度；為提高路徑規劃與導航的效率，采用一種改進的實時A*算法，將時間較優指標引入到評價指標中，節省軟件開銷．基于ARM-Linux嵌入式系統開發了導航服務器，并在智能移動設備上進行客戶端的開發，使用戶可利用智能設備查詢自己在建筑物內的位置、目的地信息，并自動規劃路線．該系統可廣泛應用于商場、博物館、圖書館、交通樞紐等大型公共建筑物內．

大型建筑物；室內導航；無線網絡；綜合信息系統

隨著建筑技術的發展和人們生活水平的提高，公共建筑物的規模不斷擴大、功能日趨復雜，因此在公交樞紐、商場、圖書館等大型公共建筑物內進行導航逐漸成為必要．然而，由于室內環境限制，無法利用GPS等信號進行定位．隨著無線局域網(wireless local area networks，簡稱WLAN)在室內環境的廣泛部署，IEEE802.11系列協議的成熟完善，以及手機等移動智能設備的普及應用，基于WLAN室內定位技術迅速發展起來．近年來，國內外很多高校和科研院所都開展了室內定位技術研究：如英國劍橋ORL實驗室的Active Badge系統[1]，美國Microsoft公司的RADAR定位系統、麻省理工大學的Cricket系統[2]、加利福尼亞大學的Calamari系統[3]等．基于WLAN的室內定位技術，充分利用現有的WLAN設備而無須增加額外的硬件設備，具有部署成本低、易于實現等優勢，成為目前室內定位技術研究的主流方向[4]．

針對大型建筑物內導航的特點，利用無線網絡定位技術，在智能設備上實現室內定位、導航、信息查詢等功能，可廣泛運用于商場、博物館、圖書館、交通樞紐等大型公共建筑物內．

1 系統結構

系統硬件組成包括導航信息服務器、無線網絡熱點、智能移動設備等部分．其中無線網絡熱點利用建筑物中已有的無線路由器，無須增加硬件設備；智能移動設備可選用智能手機、平板電腦、智能穿戴設備等．系統結構如圖1所示．

智能設備同時接收到幾個熱點發出的信號，利用基于Wifi的信號強度的定位算法，可以對當前位置進行估計，并根據地圖信息進行路徑規劃．采用基于ARM9的Linux嵌入式系統開發導航信息服務器，包含地圖信息數據庫，實現信息采集、分析、管理和發布的功能．服務器可獲取智能設備的位置信息，接收其發來的請求指令，并對智能設備的信息進行分析、存儲，同時發送廣播信息．

圖1 系統結構

2 導航信息服務器開發

2.1 導航信息服務器硬件結構

導航信息服務器采用基于ARM9的嵌入式系統，其硬件基本組成如圖2所示．服務器的核心為一片AT91RM9200處理器．采用一片同步動態存儲器SDRAM作為內存、一片FLASH存儲器用于存儲系統文件，通過USB接口連接外部存儲設備，Jtag接口用于系統的維護和調試．外部設備包括一個LCD屏，用于顯示系統狀態；一個Wifi模塊，用于通訊．另外還有電源管理電路保障電源供應，復位電路用于特殊情況下的復位．

導航信息服務器硬件原理圖和實物分別如圖3-4所示．4個USB接口分別用于連接無線網卡和其他外設；以太網口用于連接有線局域網絡；HDMI接口用于連接顯示設備，可以進行系統調試．

圖2 導航信息服務器硬件結構

圖3 導航服務器硬件原理圖

圖4 導航服務器硬件

2.2 導航信息服務器軟件結構

導航信息服務器軟件采用嵌入式Linux操作系統．它充分滿足硬件設備的實時性要求，具有高可靠性、適應性和成熟的開發工具．另外，小巧的內核可以滿足存儲空間的容量[5]．

應用程序主要用于處理和儲存信息，軟件結構如圖5所示．管理模塊是應用程序的核心，它用于對其他模塊進行監視和管理；通訊模塊用于收發數據，并將收到的數據發送給數據庫管理模塊，同時通過數據庫管理模塊讀取數據庫數據，并發送給客戶端．數據庫管理模塊用于對數據庫信息進行管理和操作．數據庫分為兩部分：一個是固定數據庫，其中儲存所在場所的地圖和局部的基本信息，其數據維護需要特定的權限，一般用戶只能請求其數據，但不能對數據內容進行修改；另一個是動態數據庫，隨時記錄用戶使用偏好等信息，用于后續的分析工作．服務器端界面如圖6所示．

圖5 導航信息服務器軟件結構

圖6 服務器端界面

3 智能設備應用軟件開發

3.1 基于無線局域網的導航算法

基于WLAN的導航是本系統的核心功能．考慮到大型建筑物內GPS信號不穩定，且基于GPS的定位方法在垂直方向上精度較低，難以在建筑物內部準確定位，因此需要在建筑物內部布設信號點，代替導航衛星進行定位．目前，無線局域網在公共建筑物內的部署日益廣泛，采用基于WLAN的導航技術無須增加硬件，相對于基于藍牙等其他設備的定位方法更加經濟，且容易實現．同時，由于智能手機的飛速發展，智能移動設備本身的信息接口滿足在其上開發導航軟件的需要，因此本系統采用基于WLAN的導航方法．

基于無線局域網的導航方法，主要需要解決的問題包括：復雜環境下基于WLAN信號強度的定位精度問題和基于建筑物內布局與人流密度的時間最優路徑規劃算法問題．

3.1.1 定位算法

在大型公共建筑物內，由于建筑物結構復雜、電氣設備多等特點，對WLAN信號造成一定的干擾．目前，基于WLAN的室內定位技術主要方法有：到達時間(time of arrival，簡稱TOA)法、到達角度(angle of arrival，簡稱AOA)法、到達時間差(time difference of arrival，簡稱TDOA)法、信號傳播模型法、最近接入點(access point，簡稱AP)法以及位置指紋法等[6]．各種方法的特性如表1所示．采用傳統的基于信號傳播模型的算法魯棒性較差，無法滿足定位精度的需要；位置指紋法具有成本低廉、不需要添加外部硬件、定位精度較高等特點，適合在公共建筑物內使用．雖然文獻[7]中的實驗表明，位置指紋法依賴于建筑物的結構，但由于公共建筑物結構相對穩定，且在前期調試時易于修正，因此可采取基于WLAN信號強度的位置指紋法作為定位算法．

表1 基于WLAN的室內定位技術主要方法比較

位置指紋定位算法的基本原理：通過測量不同位置的無線網絡信號強度向量，建立信號強度位置指紋數據庫，并通過將設備實時采集的無線網絡信號強度與數據庫中的數據進行匹配，實現定位[8]．

常用的匹配算法有最近鄰法(nearest neighborhood，簡稱NN)、K最近鄰匹配算法(K-nearest neighborhood，簡稱KNN)、加權K近鄰法(weight K-nearest neighborhood，簡稱WKNN)等．NN算法的實質是將待測點的信號強度和指紋數據庫中各個指紋點處的信號強度進行匹配，求出待測點相對每個指紋點的偏移量，將其中偏移量最小的指紋點的坐標作為該待測點的坐標；KNN算法與NN算法類似，區別在于KNN算法進行信號強度匹配后，是將偏移量最小的k個指紋點坐標取平均值，得到待測點的實際坐標，其難點是確定k的值；WKNN算法是對KNN算法的改進，它將偏移量最小的k個指紋點的坐標取加權平均值，即

式中：Xi為按信號強度進行排序后的第i個指紋點的坐標Xi＝(xi，yi)；?X為當前待測點坐標的估計值；wi為指紋點坐標的權值，該權值由指紋點處的信號強度值定義：

式中：Pfi為第i個指紋點處的信號強度；Pr為待測點處的信號強度；n為指紋點個數．

WKNN算法與NN和KNN算法的對比實驗結果如圖7所示．顯然，WKNN算法的精度明顯高于NN和KNN算法．

圖7 三種算法誤差分布對比實驗結果

3.1.2 路徑規劃

在路徑規劃問題上，已經有許多成熟的算法．傳統上有模擬退火算法、人工勢場法、模糊邏輯算法、禁忌搜索算法等．近年來，也出現了一些智能仿生學算法，如蟻群算法、神經網絡算法、遺傳算法、粒子群算法等[9]．

A*算法是導航路徑計算中的標準算法．但考慮到系統所采用的嵌入式硬件，其性能和內存有一定的限制與要求，難以直接使用A*算法計算路徑，所以需要對傳統的A*算法進行改進．本系統采用一種改進的實時A*算法[10]．考慮建筑物內實際環境情況，將時間較優指標引入到評價指標中，提高導航的效率，同時節省軟件開銷．算法流程如下：

輸入：起始點和目標點坐標

輸出：繼承點序列

(1)設置一個節點作為起始點；

(2)為節點建立繼承點，如果任一繼承點為目標點，則退出；

(3)通過從繼承點開始進行固定深度搜索，計算每個繼承點的值；

(4)將節點移到得分最低的繼承點上，將上一節點與次優繼承點的啟發代價存儲到一個表中；

(5)返回步驟(2)．

步驟(3)中，使用A*啟發式函數f＝g＋h′評價所有葉節點，其中g為根節點到葉節點的距離，h′為葉節點到目標點的預測距離．每個中間節點的f值都被設定為其子節點的最小值，以此在搜索樹上通過啟發式估計．由于步驟(4)的做法，在同一點處不會兩次采取相同的策略，而避免落入死循環．若該節點再次由步驟(2)生成，只需在步驟(3)中的表中查找，而無須重做固定深度搜索，減少算法的時間成本．

3.2 軟件結構

針對智能移動設備開發客戶端程序．客戶端通過對上述定位和路徑規劃算法的實現，完成用戶導航功能，同時與服務器端進行通訊，調用服務器端的信息，并將用戶數據反饋服務器端．軟件流程如圖8所示．

圖8 軟件流程

移動客戶端軟件部分功能界面如圖9所示．

圖9 移動客戶端界面

4 結 論

針對大型公共建筑物內導航及資源高效利用的問題，設計了大型公共建筑物室內導航系統．

(1)進行了服務器端的軟、硬件設計，采用ARM-Linux嵌入式架構，通過應用層的開發，實現客戶端與服務器之間的通訊，以及對服務器數據庫的讀寫功能．

(2)進行了基于智能移動設備的客戶端軟件設計．首先研究了基于WLAN的定位方法，解決了大型建筑物內無法使用GPS信號進行導航的問題，通過對不同定位算法的研究，采用了改進的WKNN算法，保證定位的精度；再通過采用改進的實時A*算法進行路徑規劃，實現對路徑的最優選擇．

(3)根據算法進行基于智能移動設備的導航軟件的設計，完成了基于智能移動設備的室內導航系統的開發．

［1］ WANT R，HOPPER A，FALCAO V，et al. The active badge location system[J]. Acm Transactions on Information Systems，1992，10(1)：91-102.

［2］ SHEN M，YANG X，JUN W U. A method of identifying beacons of cricket system based on phase superposition[J]. Chinese Journal of Sensors & Actuators， 2013，26(7)：981-985.

［3］ WHITEHOUSE C D. The design of calamari：an ad-hoc 788 localization system for sensor networks[D]. Berkeley：University of California at Berkeley，2002.

［4］ ZANDBERGEN P A. Accuracy of iPhone locations：a comparison of assisted GPS，WiFi and cellular positioning[J]. Transactions in Gis，2009，13(Suppl1)：5-25.

［5］ 沈 可. 使用嵌入式Linux操作系統進行軟件開發的特點及優勢[J]. 電腦開發與應用，2001，14(7)：13-15.

［6］ 劉建業. 基于WLAN的室內定位技術的研究與實現[D]. 昆明：云南財經大學，2013：11-17.

［7］ FARSHAD A，LI J，MARINA M K，et al. A microscopic look at WiFi fingerprinting for indoor mobile phone localization in diverse environments[C]// IPIN. 2013 International Conference on IEEE，Busan：[s.n.]，2013：1-10.

［8］ LUO Y，HOEBER O，CHEN Y. Enhancing Wi-Fi fingerprinting for indoor positioning using human-centric collaborative feedback[J]. Human-centric Computing and Information Sciences，2013，3(1)：1-23.

［9］ 張廣林，胡小梅，柴劍飛，等. 路徑規劃算法及其應用綜述[J]. 現代機械，2011(5)：85-90.

［10］ DAS P K，BEHERA H S，PRADHAN S K，et al. A modified real time A* algorithm and its performance analysis for improved path planning of mobile robot[J]. Smart Innovation，Systems and Technologies，2015，32：221-234.

Development of the Indoor Navigation System in Large Public Buildings

LI Meng，YANG Jing，SHAO Xinru
(School of Control and Mechanical Engineering，TCU，Tianjin 300384，China)

A navigation and integrated information system is designed and developed based on the wireless network signals，which can be used to improve the efficient use of resources and solve indoor navigation problem in large public buildings. A fingerprint positioning method based on WLAN signal along with modified weighting K nearest neighbor algorithm and signal propagation model is proposed to meet the requirement of indoor navigation. A modified real-time A* algorithm which introduces the time optimal index into the evaluation index is used to improve navigation efficiency. A navigation server is designed based on ARM-linux embedded system，and a client is developed on smart mobile devices. The users can easily inquire their location and the information of the destination on their smart mobile devices，which can also plan the route automatically. This system will be widely used in large public buildings such as market，museum，library and transport hubs.

large public buildings；indoor navigation；wireless network；integrated information system

TN966

A

2095-719X(2016)06-0460-05

2015-11-23；

2016-03-29

國家級大學生創新創業訓練計劃(201510792013)

李 盟（1985—），女，天津人，天津城建大學助教，碩士.