前晉， 陳淑榮

(上海海事大學 信息工程學院，上海 201306)

0 引言

隨著商場、地下停車場、機場等大型室內(nèi)場館的興建，手機室內(nèi)定位及導航需求日趨強烈，如商場中基于位置信息給予用戶手機特定的商品消息推送，地下停車場智能尋車，機場室內(nèi)位置導航等。目前手機室內(nèi)定位技術主要通過藍牙iBeacon和Wi-Fi來實現(xiàn)，文獻[1][2]使用Wi-Fi指紋定位算法，將接收Wi-Fi信號的RSSI值與已建立的指紋數(shù)據(jù)庫進行對比實現(xiàn)定位；文獻[3][4]使用iBeacon定位技術，首先建立iBeacon信號強度與距離之間的關系，再通過三邊定位算法實現(xiàn)定位。以上兩種定位技術均能滿足商場室內(nèi)定位精度需求，但商場人流較大，商鋪位置易變動，導致Wi-Fi指紋庫需要時常更新維護，人工成本較大，相比之下iBeacon技術更適用于商場環(huán)境。

導航是手機位置信息服務的一種，可轉(zhuǎn)化為找尋定位點與目的地之間的最短可行路徑。常用的路徑規(guī)劃算法包括Dijkstra算法、A*搜索算法、蟻群算法等。文獻[5]指出Dijstra算法搜索全局空間，難以滿足快速規(guī)劃路徑的需求，而通過改進A*算法建立平滑的A*模型,其性能優(yōu)于蟻群算法，且能處理障礙物隨機分布的復雜環(huán)境下的路徑規(guī)劃問題?？梢夾*算法更適用于障礙物較多的室內(nèi)環(huán)境。

本文利用藍牙iBeacon技術實現(xiàn)手機室內(nèi)定位及導航功能，首先在室內(nèi)部署ibeacon設備，測量室內(nèi)環(huán)境中各點的RSSI值，得出信號強度與距離之間的關系，建立iBeacon距離-RSSI損耗模型；其次手機接收iBeacon的RSSI值，上傳至服務器，利用上述模型和三邊質(zhì)心法計算手機位置坐標；服務器端按照用戶輸入的目的地，采用引入回退機制的A*算法計算最優(yōu)路徑，并在手機端自制的商場地圖上標示最優(yōu)導航路徑。

1 系統(tǒng)概述

系統(tǒng)主要由3個部分組成：iBeacon設備、Android智能手機、服務器，如圖1所示。

多個已知位置坐標的iBeacon部署在室內(nèi)空間中，周期性地向外界廣播信號。

手機應用由Android Studio開發(fā)環(huán)境搭建而成，其功能包括接收iBeacon信號并上傳iBeacon的Major值及對應RSSI值至服務器；上傳用戶輸入的目的地；接受返回信息并在室內(nèi)地圖標示當前位置；顯示服務器返回的最優(yōu)導航路徑。

圖1 系統(tǒng)結構

服務器由MyEclipse結合Apache Tomcat搭建而成，內(nèi)部存儲了iBeacon信息和地圖信息，采用基于HTTP協(xié)議的doPost方式與手機端進行數(shù)據(jù)交互，功能包括接收手機端上傳的RSSI值，運行iBeacon距離-RSSI損耗模型確定手機與iBeacon的距離；利用三邊質(zhì)心法計算手機位置坐標；接收輸入的目的地信息，并運行引入回退機制的A*算法規(guī)劃最優(yōu)導航路徑。

2 系統(tǒng)實現(xiàn)的關鍵技術

2.1 iBeacon室內(nèi)定位

采用iBecaon進行室內(nèi)定位，需先建立iBeacon距離-RSSI損耗模型，獲取手機與最近的3個iBeacon之間的距離，再通過三邊質(zhì)心法計算手機位置坐標，實現(xiàn)定位。算法步驟如下：

第一步：RSSI值采集預處理。部署iBeacon應選取周圍無遮擋物的位置降低信號損耗，在信號穩(wěn)定后采集RSSI值以防其它信號干擾，減少環(huán)境誤差；在同一地點采集多個RSSI值采用均值濾波預處理，以減少測量誤差，如式(1)。

(1)

第二步：建立iBeacon距離-RSSI損耗模型。已有實驗數(shù)據(jù)表明無線信號強度與距離存在對數(shù)關系[3-6]，如式(2)。

(2)

其中，PL(d)、PL(d0)分別表示無線信號在d和d0米處的信號強度損耗，n為環(huán)境變量因子，Xσ是方差為σ的正態(tài)隨機分布，單位為dB。設d0=1 m， (2)式變?yōu)槭?3)。

Rssi(d)=R1+10nlg(d)+Xσ

(3)

式中，Rssi(d)表示d米處的無線信號強度值，R1表示iBeacon與手機相距1 m時的無線信號強度值。距離d和信號強度Rssi(d)由實際測量得到，n和R1為模型的待定參數(shù)。

第三步：參數(shù)R1和n的最優(yōu)估計。采用最小二乘法[7]，利用最小化誤差的平方和尋找數(shù)據(jù)的最佳匹配函數(shù)，從而確定最優(yōu)參數(shù)值。誤差函數(shù)如式(4)。

(4)

(5)

其中α為梯度因子，取α=0.02，使J(R1,n)達到最小即可求得所需的R1和n。根據(jù)最優(yōu)參數(shù)建立的iBeacon距離-RSSI損耗模型如式(6)。

(6)

將手機端接收的RSSI值代入式(6)即可得出手機與iBeacon的距離d。

第四步：獲取手機位置坐標。采用三邊質(zhì)心法[6]，如圖2所示。

圖2 三邊質(zhì)心法計算手機坐標示意圖

其中，A、B、C三點代表iBeacon設備位置，r1、r2、r3表示通過式(6)模型求得手機與離其最近的三個iBeacon設備的距離d。陰影三角形的三個頂點坐標分別為D(xd,yd)、E(xe,ye)、f(xf,yf)，三角形的質(zhì)心坐標P(x,y)即為確定的手機位置坐標，如式(7)。

(7)

2.2 商場室內(nèi)導航

導航作為室內(nèi)位置服務的重要部分，實質(zhì)是尋找定位點和用戶搜索目的地之間的最短可行路徑。如圖3所示。

(a)

(b)

以上海正大廣場1層為例，如圖3(a)所示，導航算法步驟如下：

第一步：室內(nèi)地圖建模。將商場地圖的所有可行走路徑轉(zhuǎn)化為節(jié)點圖，如圖3(b)所示。每一節(jié)點代表一個地點，線段代表可行路徑。節(jié)點信息如下：

(1)N：整數(shù)型節(jié)點標識符，以數(shù)字形式標識節(jié)點。

(2) Floor：整數(shù)型樓層標識符，記錄該節(jié)點樓層信息。

(3) Name：字符型，記錄節(jié)點名稱，一般為對應地圖所在地名稱。

(4)X、Y：double型，記錄該節(jié)點對應地圖所在位置的二維坐標值。

(5) Next：數(shù)組型，記錄該節(jié)點可到達的下一個節(jié)點的N值。

以1節(jié)點為例，其中N=1，F(xiàn)loor=1，Name=“扶梯”，X=450，Y=330，Next=[2,3,4,5]。

第二步：建立最優(yōu)路徑搜索算法。在A*算法的基礎上引入回退機制實現(xiàn)室內(nèi)最優(yōu)路徑規(guī)劃，流程如圖4所示，其中p，q分別為手機定位點和用戶輸入的目的節(jié)點，path為路徑節(jié)點集，close為已搜索節(jié)點集。搜索下一節(jié)點時，取出下一節(jié)點集Next中的所有值，若其屬于close，則跳過，否則計算其評估函數(shù)f(n)[5]，并加入close；當遍歷完Next中所有值后，將f(n)值最小的節(jié)點作為新的p，并加入到path中，依次循環(huán)，直至p=q后，輸出最優(yōu)路徑集path。節(jié)點x的評估函數(shù)f(n)如式(8)。

f(n)=g(n)+h(n)

(8)

其中，g(n)表示初始節(jié)點p到節(jié)點x的代價函數(shù)，表示節(jié)點x到目的節(jié)點q的啟發(fā)式函數(shù)，采用標準的曼哈頓距離，如式(9)。

h(n)=(|x1-x2|+|y1-y2|)

(9)

式中，x1、y1表示該節(jié)點x的二維坐標，x2、y2表示目的節(jié)點q的二維坐標。

第三步：引入回退機制的路徑選取策略。在搜索節(jié)點時，會遇到死節(jié)點，即除了上一節(jié)點沒有其它連接節(jié)點，如圖3(b)中，若以1節(jié)點為p，6節(jié)點為q，根據(jù)傳統(tǒng)的A*算法下一節(jié)點會選擇4節(jié)點，此時4節(jié)點即死節(jié)點，為了應對這種異常情況，算法增加了回退機制，如圖4中虛框所示。

遇到死節(jié)點時將已搜索節(jié)點集close回退到上一狀態(tài)，并加入死節(jié)點，使再次搜索路徑時忽略該節(jié)點，避免錯誤發(fā)生；另外將路徑節(jié)點集中的末值賦給p，使p恢復到上一狀態(tài)，從而實現(xiàn)回退過程?；赝藱C制消除了死節(jié)點的影響，增加了算法運行的穩(wěn)定性。

3 實驗結果與分析

3.1 iBeacon距離-RSSI損耗模型參數(shù)選取實驗

為確定模型的待定參數(shù)n和R1，在室內(nèi)距離iBeacon設備0.1 m、0.7 m、1.3 m、1.9 m……處，選取13個點，按照定位算法步驟一對采集的RSSI值進行均值濾波，再根據(jù)步驟二運用最小二乘法選取最優(yōu)參數(shù)，得出具體數(shù)值如式(10)。

(10)

為了驗證參數(shù)選取的最優(yōu)性，式(5)中誤差函數(shù)J(R1,n)值的漸變情況如圖5所示。

圖4 最優(yōu)路徑搜索流程

圖5 誤差函數(shù)J(R1,n)的漸變圖

可見當循環(huán)次數(shù)達到2 000次以上時，誤差函數(shù)值已基本趨于平穩(wěn)且接近于零，表明參數(shù)和的估計已達到最優(yōu)。

為了驗證模型的有效性，將建立的iBeacon距離-RSSI損耗模型曲線與實際測量數(shù)據(jù)進行對比，如圖6所示。

圖6 模型曲線與實際數(shù)據(jù)對比圖

其中×點表示實際測量數(shù)據(jù)，圖6中顯示曲線能有效反映iBeacon信號強度與距離之間的關系。

由上可知，模型參數(shù)選取已達最優(yōu)，建立的iBeacon距離-RSSI損耗模型有效可行。

3.2 定位實驗

為了測量定位算法的誤差，在5.4*16.2室內(nèi)部署3個iBeacon設備，二維坐標分別為A(0,7.2)、B(2.7,0)、C(2.3,16.2)，單位為m。 隨機選擇30個采樣點，將采集數(shù)據(jù)代入iBeacon距離-RSSI損耗模型，再根據(jù)定位步驟三計算出手機位置坐標，與實際測量的坐標數(shù)據(jù)比較，得出定位誤差值如圖7所示。

圖7 手機室內(nèi)定位誤差圖

其中最大定位誤差在3米以內(nèi)，且誤差值在2米內(nèi)有24次，定位精度較好。

10組實際坐標與模擬坐標的對比圖，如圖8所示。

圖8 實際坐標與模擬坐標對比圖

圖中可以看出在定位點距離墻壁較近時，藍牙信號發(fā)生反射，折射，產(chǎn)生多徑效應[6]，定位誤差較大，而在室內(nèi)中心區(qū)域則定位誤差較小。

以上10組定位算法計算總時間為6.777 s，平均每次定位算法實現(xiàn)時間為0.677 7 s，滿足實時定位的需求。

3.3 商場室內(nèi)導航實驗

根據(jù)服務器計算的定位坐標，在手機端的商場地圖上標示當前位置，當用戶輸入目的地，手機上傳輸入信息，服務器根據(jù)改進的A*導航算法規(guī)劃出最優(yōu)路徑并返回至手機，結果如圖9所示。

其中綠點代表起點，藍點代表終點，紅線標示為最優(yōu)導航路徑。

4 總結

針對商場手機定位和導航應用，首先通過實驗建立iBeacon距離-RSSI損耗模型，利用三邊質(zhì)心法實現(xiàn)手機室內(nèi)定位，在此基礎上實現(xiàn)了C/S架構的商場室內(nèi)手機定位導航系統(tǒng)。手機端通過接收iBeacon信號并上傳服務器，后臺運行定位算法，計算手機的位置信息；并按照用戶輸入的目的地址，運行路徑搜索算法，返回最優(yōu)可行路徑，實現(xiàn)商場室內(nèi)導航。實驗結果表明，定位最大誤差在3 m以內(nèi)，導航路徑精確，能滿足大型室內(nèi)場館手機定位導航需求。

圖9 最優(yōu)導航路徑結果圖