李 盟，楊 靜，邵薪儒

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

信息科學(xué)與技術(shù)

面向大型建筑物的室內(nèi)導(dǎo)航系統(tǒng)開發(fā)

李 盟，楊 靜，邵薪儒

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

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

大型建筑物；室內(nèi)導(dǎo)航；無線網(wǎng)絡(luò)；綜合信息系統(tǒng)

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

針對大型建筑物內(nèi)導(dǎo)航的特點，利用無線網(wǎng)絡(luò)定位技術(shù)，在智能設(shè)備上實現(xiàn)室內(nèi)定位、導(dǎo)航、信息查詢等功能，可廣泛運用于商場、博物館、圖書館、交通樞紐等大型公共建筑物內(nèi)．

1 系統(tǒng)結(jié)構(gòu)

系統(tǒng)硬件組成包括導(dǎo)航信息服務(wù)器、無線網(wǎng)絡(luò)熱點、智能移動設(shè)備等部分．其中無線網(wǎng)絡(luò)熱點利用建筑物中已有的無線路由器，無須增加硬件設(shè)備；智能移動設(shè)備可選用智能手機(jī)、平板電腦、智能穿戴設(shè)備等．系統(tǒng)結(jié)構(gòu)如圖1所示．

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

圖1 系統(tǒng)結(jié)構(gòu)

2 導(dǎo)航信息服務(wù)器開發(fā)

2.1 導(dǎo)航信息服務(wù)器硬件結(jié)構(gòu)

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

導(dǎo)航信息服務(wù)器硬件原理圖和實物分別如圖3-4所示．4個USB接口分別用于連接無線網(wǎng)卡和其他外設(shè)；以太網(wǎng)口用于連接有線局域網(wǎng)絡(luò)；HDMI接口用于連接顯示設(shè)備，可以進(jìn)行系統(tǒng)調(diào)試．

圖2 導(dǎo)航信息服務(wù)器硬件結(jié)構(gòu)

圖3 導(dǎo)航服務(wù)器硬件原理圖

圖4 導(dǎo)航服務(wù)器硬件

2.2 導(dǎo)航信息服務(wù)器軟件結(jié)構(gòu)

導(dǎo)航信息服務(wù)器軟件采用嵌入式Linux操作系統(tǒng)．它充分滿足硬件設(shè)備的實時性要求，具有高可靠性、適應(yīng)性和成熟的開發(fā)工具．另外，小巧的內(nèi)核可以滿足存儲空間的容量[5]．

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

圖5 導(dǎo)航信息服務(wù)器軟件結(jié)構(gòu)

圖6 服務(wù)器端界面

3 智能設(shè)備應(yīng)用軟件開發(fā)

3.1 基于無線局域網(wǎng)的導(dǎo)航算法

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

基于無線局域網(wǎng)的導(dǎo)航方法，主要需要解決的問題包括：復(fù)雜環(huán)境下基于WLAN信號強度的定位精度問題和基于建筑物內(nèi)布局與人流密度的時間最優(yōu)路徑規(guī)劃算法問題．

3.1.1 定位算法

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

表1 基于WLAN的室內(nèi)定位技術(shù)主要方法比較

位置指紋定位算法的基本原理：通過測量不同位置的無線網(wǎng)絡(luò)信號強度向量，建立信號強度位置指紋數(shù)據(jù)庫，并通過將設(shè)備實時采集的無線網(wǎng)絡(luò)信號強度與數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行匹配，實現(xiàn)定位[8]．

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

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

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

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

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

3.1.2 路徑規(guī)劃

在路徑規(guī)劃問題上，已經(jīng)有許多成熟的算法．傳統(tǒng)上有模擬退火算法、人工勢場法、模糊邏輯算法、禁忌搜索算法等．近年來，也出現(xiàn)了一些智能仿生學(xué)算法，如蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、粒子群算法等[9]．

A*算法是導(dǎo)航路徑計算中的標(biāo)準(zhǔn)算法．但考慮到系統(tǒng)所采用的嵌入式硬件，其性能和內(nèi)存有一定的限制與要求，難以直接使用A*算法計算路徑，所以需要對傳統(tǒng)的A*算法進(jìn)行改進(jìn)．本系統(tǒng)采用一種改進(jìn)的實時A*算法[10]．考慮建筑物內(nèi)實際環(huán)境情況，將時間較優(yōu)指標(biāo)引入到評價指標(biāo)中，提高導(dǎo)航的效率，同時節(jié)省軟件開銷．算法流程如下：

輸入：起始點和目標(biāo)點坐標(biāo)

輸出：繼承點序列

(1)設(shè)置一個節(jié)點作為起始點；

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

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

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

(5)返回步驟(2)．

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

3.2 軟件結(jié)構(gòu)

針對智能移動設(shè)備開發(fā)客戶端程序．客戶端通過對上述定位和路徑規(guī)劃算法的實現(xiàn)，完成用戶導(dǎo)航功能，同時與服務(wù)器端進(jìn)行通訊，調(diào)用服務(wù)器端的信息，并將用戶數(shù)據(jù)反饋服務(wù)器端．軟件流程如圖8所示．

圖8 軟件流程

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

圖9 移動客戶端界面

4 結(jié) 論

針對大型公共建筑物內(nèi)導(dǎo)航及資源高效利用的問題，設(shè)計了大型公共建筑物室內(nèi)導(dǎo)航系統(tǒng)．

(1)進(jìn)行了服務(wù)器端的軟、硬件設(shè)計，采用ARM-Linux嵌入式架構(gòu)，通過應(yīng)用層的開發(fā)，實現(xiàn)客戶端與服務(wù)器之間的通訊，以及對服務(wù)器數(shù)據(jù)庫的讀寫功能．

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

(3)根據(jù)算法進(jìn)行基于智能移動設(shè)備的導(dǎo)航軟件的設(shè)計，完成了基于智能移動設(shè)備的室內(nèi)導(dǎo)航系統(tǒng)的開發(fā)．

［1］ WANT R，HOPPER A，F(xiàn)ALCAO 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操作系統(tǒng)進(jìn)行軟件開發(fā)的特點及優(yōu)勢[J]. 電腦開發(fā)與應(yīng)用，2001，14(7)：13-15.

［6］ 劉建業(yè). 基于WLAN的室內(nèi)定位技術(shù)的研究與實現(xiàn)[D]. 昆明：云南財經(jīng)大學(xué)，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］ 張廣林，胡小梅，柴劍飛，等. 路徑規(guī)劃算法及其應(yīng)用綜述[J]. 現(xiàn)代機(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

國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃(201510792013)

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