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

李 盟，楊 靜，邵薪儒

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

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

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

李 盟，楊 靜，邵薪儒

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

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

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

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

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

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

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

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

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

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

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

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

導(dǎo)航信息服務(wù)器硬件原理圖和實(shí)物分別如圖3-4所示．4個(gè)USB接口分別用于連接無(wú)線網(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è)備的實(shí)時(shí)性要求，具有高可靠性、適應(yīng)性和成熟的開(kāi)發(fā)工具．另外，小巧的內(nèi)核可以滿足存儲(chǔ)空間的容量[5]．

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

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

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

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

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

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

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

3.1.1 定位算法

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

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

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

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

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

式中：Pfi為第i個(gè)指紋點(diǎn)處的信號(hào)強(qiáng)度；Pr為待測(cè)點(diǎn)處的信號(hào)強(qiáng)度；n為指紋點(diǎn)個(gè)數(shù)．

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

圖7 三種算法誤差分布對(duì)比實(shí)驗(yàn)結(jié)果

3.1.2 路徑規(guī)劃

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

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

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

輸出：繼承點(diǎn)序列

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

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

(3)通過(guò)從繼承點(diǎn)開(kāi)始進(jìn)行固定深度搜索，計(jì)算每個(gè)繼承點(diǎn)的值；

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

(5)返回步驟(2)．

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

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

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

圖8 軟件流程

移動(dòng)客戶端軟件部分功能界面如圖9所示．

圖9 移動(dòng)客戶端界面

4 結(jié) 論

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

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

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

(3)根據(jù)算法進(jìn)行基于智能移動(dòng)設(shè)備的導(dǎo)航軟件的設(shè)計(jì)，完成了基于智能移動(dòng)設(shè)備的室內(nèi)導(dǎo)航系統(tǒng)的開(kāi)發(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)行軟件開(kāi)發(fā)的特點(diǎn)及優(yōu)勢(shì)[J]. 電腦開(kāi)發(fā)與應(yīng)用，2001，14(7)：13-15.

［6］ 劉建業(yè). 基于WLAN的室內(nèi)定位技術(shù)的研究與實(shí)現(xiàn)[D]. 昆明：云南財(cái)經(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

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

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