結合位置指紋和行人航跡的室內定位技術①

羅思奇,羅笑玲,李敏澄,李志鋒,陳建城,周嫻瑋,潘家輝

(華南師范大學 軟件學院,南海 528225)

結合位置指紋和行人航跡的室內定位技術①

羅思奇,羅笑玲,李敏澄,李志鋒,陳建城,周嫻瑋,潘家輝

(華南師范大學 軟件學院,南海 528225)

主要對室內定位技術展開研究,首先通過手持智能設備收集指定范圍樣本點的坐標及wifi熱點信息;然后應用位置指紋定位方法進行絕對定位;為了提高行走過程中定位的準確性和實時性,采用行人航跡推算算法,即通過手機傳感器采集并經(jīng)處理的數(shù)據(jù)進行步頻檢測、步長估算和方向檢測,實現(xiàn)相對位置變化的估算.行人航跡算法克服位置指紋定位的不穩(wěn)定性,而位置指紋定位算法及時調整行人航跡算法帶來的累積誤差.實驗結果表明兩種室內定位技術的結合有效提高了室內定位的準確性,能充分應用到實際生活中.

室內定位;安卓平臺;wifi;位置指紋定位;行人航跡推算

1 引言

1.1 研究背景

現(xiàn)今社會,全球衛(wèi)星導航系統(tǒng)已經(jīng)得到了廣泛應用.然而,隨著巨型建筑物的增加和人們對導航系統(tǒng)的要求不斷增多,全球衛(wèi)星導航系統(tǒng)的局限性逐漸顯露:由于衛(wèi)星定位精度低和無法穿透建筑物等問題,導致了全球衛(wèi)星導航系統(tǒng)無法進行室內定位.因此,室內導航系統(tǒng)有巨大的市場潛力及發(fā)展空間.

隨著Android智能手機硬件的發(fā)展,絕大多數(shù)手機都自帶慣性傳感器,為室內導航提供了基本的條件.國外在室內導航技術方面研究得比較早,但實際應用還在進一步研究當中;國內還沒有出現(xiàn)成熟的大規(guī)模室內導航研究應用.

1.2 研究現(xiàn)狀

早前,已經(jīng)初步取得成果的是Google[1]、NOKIA[2]和富士通[3]的室內定位研究,Google是通過事前的大量數(shù)據(jù)收集,通過wifi等設備來獲取用戶在室內的位置;NOKIA是利用分布在空間上方的定位發(fā)射器,基于藍牙設備運用三角定位方法對用戶進行定位;富士通則是通過超寬帶無線電(UWB)技術來實現(xiàn)的.而近年來越來越多的公司對室內定位進行了大量的研究,例如基于移動通信網(wǎng)絡的輔助GPS(A-GPS)、偽衛(wèi)星(Pseudolite)、射頻標簽(RFID)室內定位、ZigBee室內定位、手機自主慣性傳感器定位導航、紅外室內定位、計算機視覺室內定位、光跟蹤定位、超聲波室內定位等[4].

現(xiàn)階段各種主要的室內定位技術的概述如下:

(1)藍牙技術

藍牙技術通過測量信號強度進行定位.這是一種短距離低功耗的無線傳輸技術,需要用戶開啟藍牙設備,與周圍的藍牙設備連成藍牙局域網(wǎng).藍牙局域網(wǎng)內藍牙設備通過交換數(shù)據(jù),就可以獲得用戶的位置信息.藍牙技術主要應用于小范圍定位,優(yōu)點是設備體積小,易于攜帶,容易推廣.其不足是,藍牙器件和設備的價格比較昂貴,而且對于復雜的空間環(huán)境,藍牙系統(tǒng)的穩(wěn)定性稍差,受噪聲信號干擾大.

(2)射頻識別技術

射頻識別技術通過無線電訊號識別特定目標并交換數(shù)據(jù)以達到識別和定位的目的.這種技術作用距離短,一般最長為幾十米.但它可以在幾毫秒內得到厘米級定位精度的信息,且傳輸范圍很大,成本較低.同時由于其非接觸和非視距等優(yōu)點,可望成為優(yōu)選的室內定位技術.優(yōu)點是標識的體積比較小,造價比較低,但是作用距離近,不具有通信能力,而且不便于整合到其他系統(tǒng)之中.

(3)wifi技術

wifi定位技術是通過采集周圍的wifi熱點的信號,進行信息匹配得到位置信息.由于wifi熱點廉價、布設容易,很容易通過增加wifi熱點來提高室內定位精度.當前比較流行的wifi定位是無線局域網(wǎng)絡系列標準之IEEE802.11的一種定位解決方案,采用經(jīng)驗測試和信號傳播模型相結合的方式,易于安裝,需要的基站不多,可以采用相同的底層無線網(wǎng)絡結構,精度總體較高.它的優(yōu)點是使用與范圍小的室內環(huán)境,成本低,只要周圍的熱點設備布置合理,定位的精度可以得到保證.缺點是很容易受到其他信號的干擾,從而影響其精度,定位器的能耗也較高.

(4)ZigBee技術

ZigBee是介于射頻識別和藍牙之間的一種新興的短距離、低速率無線網(wǎng)絡技術,也可以用于室內定位.在距離短、功耗低且傳輸速率不高的各種電子設備之間進行數(shù)據(jù)傳輸,從而獲得具體位置信息,實現(xiàn)定位.其優(yōu)點是通信效率高,而且低功耗.不足是ZigBee的信號傳輸受多徑效應和移動的影響都很大,而且定位精度取決于信道物理品質、信號源密度、環(huán)境和算法的準確性,造成定位軟件的成本較高.

各種室內定位技術都有其優(yōu)缺點,根據(jù)不同的應用環(huán)境選擇不同的技術.本文的研究重點是:基于wifi的室內定位技術的原理,以及詳細介紹位置指紋定位技術的實現(xiàn)方法;實現(xiàn)精確定位之后,運用行人航跡推算技術進行位置估算,提高定位的實時性.主要闡述基于wifi室內定位技術和行人航跡推算技術相結合的室內定位方案.

2 位置指紋定位基本原理和實現(xiàn)

2.1 無線信號強度基于物理位置的唯一性

位置指紋[5]是基于無線信號強度信號RSSI的定位方法.由于環(huán)境因素的影響,在不同位置搜集的同一個wifi熱點的信號強度都不相同,具有唯一性.具體來說,需要收集特定位置的所有wifi熱點信號強度存儲到指紋數(shù)據(jù)庫,基于其信號強度唯一性,對比手機移動端接收到的wifi熱點信號與指紋數(shù)據(jù)庫,通過某個匹配算法算出當前移動端最匹配的位置.

2.2 KNN算法設計

基于wifi環(huán)境下的位置指紋定位技術[13],采用的算法為K近鄰法[6](KNN,K Nearest Neighborhood).這是最近鄰算法(NN,Nearest Neighborhood)的改進型算法,兩者的區(qū)別在于,NN算法是選取最小距離的矢量值,KNN算法是從最小距離開始選取K(K>=2)個最接近的數(shù)據(jù),再求平均值,求出的平均坐標值為待測目標的位置.

此算法如公式(1)所示,假設存放某區(qū)域內的wifi熱點AP的信號強度數(shù)據(jù)庫中,共有m個參考坐標,n個wifi熱點AP.

其中i=1,2,……,m;j=1,2,……,n.bj表示移動者在特定位置接收的第j個wifi熱點的信號強度.Bij表示在數(shù)據(jù)庫中第i個參考坐標的第j個wifi熱點信號的強度.當a=1時,dis為曼哈頓距離;a=2時,dis為歐幾里徳距離.

從結果中選擇K個dis值最小的樣本坐標值,取這K個坐標值的均值作為待測點的坐標.公式如下,在本文中設a=1,K=5.

KNN近鄰算法用平均距離減少了誤差,提高了精確度,而且實現(xiàn)起來比較容易操作.

2.3 wifi信號采集和定位

位置指紋定位需要兩個階段:數(shù)據(jù)采集和定位階段[6][7].數(shù)據(jù)采集首先通過手機端收集wifi信號,上傳到服務器,存儲到數(shù)據(jù)庫.室內定位階段則是先采集所在位置的wifi熱點信息,通過與數(shù)據(jù)庫中的wifi數(shù)據(jù)作匹配[8].

圖1 指紋定位實現(xiàn)流程圖

圖2 定位流程圖

3 行人航跡推算算法基本原理和實現(xiàn)

行人航跡推算(PDR,以下簡稱PDR)[9]技術是一種基于傳感器信息計算行人相對位置的定位技術[10],它首先通過傳感器檢測行人的步數(shù)并估算出步長,然后通過磁阻傳感器和陀螺儀計算出行人的方位角,最后獲取人體移動的相對位置從而實現(xiàn)定位.手機自包含的傳感器包括:慣性傳感器(加速度傳感器和陀螺儀傳感器)、數(shù)字羅盤、氣壓計、視覺傳感器等.行走航跡推算技術是通過跨步時的生理特征,通過傳感器的值估計出行人的跨步和步長,相較于其他室內定位方法, PDR不受外界環(huán)境影響,定位精度較高,但只能獲取相對位置信息.

3.1 基于卡爾曼濾波算法的慣性導航技術的原理

卡爾曼濾波是以最小均方誤差為估計的最佳準則,來尋求一套遞推估計的算法,其基本思想是:采用信號與噪聲的狀態(tài)空間模型,利用前一時刻的估計值和現(xiàn)時刻的觀測值來更新對狀態(tài)變量的估計,求出現(xiàn)時刻的估計值.其核心思想是“預測”+“測量反饋”,通過對上一個結果卡爾曼濾波計算和加權平均預測出下一個結果.

現(xiàn)設線性時變系統(tǒng)的離散狀態(tài)防城和觀測方程為:

其中,X(k)和Y(k)分別是k時刻的狀態(tài)矢量和觀測矢量, F(k,k-1)為狀態(tài)轉移矩陣,U(k)為k時刻動態(tài)噪聲, T(k,k-1)為系統(tǒng)控制矩陣,H(k)為k時刻觀測矩陣,N(k)為k時刻觀測噪聲.則卡爾曼濾波的算法流程為:

1)預估計

2)計算預估計協(xié)方差矩陣

3)計算卡爾曼增益矩陣

4)更新估計

5)計算更新后估計協(xié)防差矩陣

重復以上步驟.

3.2 基于卡爾曼濾波算法的慣性導航技術與PDR技術的比較

兩種技術都需要實時獲取手機傳感器的數(shù)據(jù),再通過一定計算得到結果.基于卡爾曼濾波算法的慣性導航技術普遍適用于一切運動對象,但是實現(xiàn)測量反饋需要傳感器實時獲取數(shù)據(jù)并計算,這需要比較高的計算能力和數(shù)據(jù)采集率,要求高精度的傳感器.而且卡爾曼濾波算法的流程復雜,計算量較大,其計算是一個遞推的過程,隨著濾波步數(shù)的增加,舍入誤差逐漸積累,可能使增益矩陣的計算值逐漸失去加權作用而導致濾波發(fā)散.而PDR技術是利用行人運動特征,通過檢測行人是否行走一步和估算行人一步的步長來獲得行人位置的變化.為了便于技術的推廣,必須考慮到硬件成本和軟件實現(xiàn)的復雜度.手機上的傳感器往往無法滿足慣性導航的要求.相較于慣性導航技術, PDR技術利用行人運動特征,降低了對加速度傳感器精度的要求,同時也降低了算法的復雜度,在現(xiàn)有的安卓手機上PDR技術更容易實現(xiàn).

3.3 PDR算法基本原理

PDR算法,即從一個已知的坐標位置開始,通過傳感器獲取行人在該位置的運動方向、速度等數(shù)據(jù)來推算行人在下一時刻出現(xiàn)的位置的過程.由于其定位過程不受環(huán)境因素的影響,能夠隨時隨地提供連續(xù)的二維位置信息.PDR的原理[14]如圖3所示.

圖3 相對位置定位技術原理圖

設某一時刻行人的位置在Pn-1(En-1,Nn-1),運動了d距離后到達Pn(En,Nn),兩個位置偏離的角度為ɑ,則Pn-1和Pn之間的關系如下:

3.4 PDR算法流程

PDR技術包括四大重要核心:步頻檢測、步長估算、方向檢測和位置估算.圖4清晰地展示了行人航跡推算機制的算法流程,探測行人行走時的加速度值,通過濾波模型等有關模型推算出步長以及行走的方向,從而得出行人的位置、距離、速度和方向等信息.

圖4 行人航跡推算算法流程圖

3.4.1 信號采集

系統(tǒng)需要使用手機上的加速計采集三軸加速度的值[11].由于最后需要得到行人行走的總加速度,所以得通過以下公式得出總加速度:

3.4.2 步頻檢測和步長估算

(1)閾值判斷方法和加速度信號峰值檢測

① 滑動查找窗口大小設置

大多數(shù)文獻中根據(jù)斜率的正負轉折點來查找雙峰值[12],但因為實際上的各種誤差,使得峰值會因受到微小震蕩而出現(xiàn)誤差.因此,我們采用閾值判斷方法,通過設置滑動查找窗口的大小來控制峰值檢測結果.滑動查找窗口大小的設置對于峰值檢測結果有著舉足輕重的作用,若窗口值設置得太大,會使很多正確的峰值被舍棄掉;若窗口值設置的過小,則會受到嚴重的誤差干擾,將細微的波動當做是峰值.

② 峰值檢測

通過滑動查找窗口值的約束,根據(jù)斜率的變化來確定峰頂和峰谷.本文的的峰值查找思想如下:

a.通過三軸加速計采集加速度值,經(jīng)過濾波處理后,然后進行峰值檢測;

b.計算該值與上一次峰值的物理差值和時間差值,如果物理差值超過閾值或者時間差值不在時間窗口范圍內,則轉第一步執(zhí)行;否則將該結果作為峰值按序存儲.

③ 時間窗口的設定

根據(jù)人走路的時間估計每一步需要走多長的時間,從而排除不合理的步伐.通過大量實驗并且根據(jù)人體的極限行走速度分析,時間窗口的范圍為0.2s-2s之間.時間窗口值得設定對于步頻檢測的準確性有著重要的影響,如果時間窗口值范圍設得太大,很可能導致步數(shù)的誤判.因此,我們需要不斷調整時間窗口的大小,適應不同的變化,使之達到合理的范圍.

(2)步頻檢測

確定了步頻檢測的各個參數(shù)后,接下來處理的問題是實現(xiàn)算法流程.步頻檢測需要實時采集數(shù)據(jù),實時計算,實時顯示.算法流程如圖5所示:

圖5 步頻檢測算法流程圖

(3)步長估算

PDR定位精確度與步長估算的精確度有著極大的聯(lián)系,因此實現(xiàn)PDR的一大重點是實現(xiàn)步長估算.在Android平臺上實現(xiàn)PDR,本文通過一種非線性步長估算模型,提高不同步長下步長估算的精度,公式為:

3.4.3 方向檢測

在實現(xiàn)PDR技術[9]的過程中,需要獲取行人在行走過程中的方向,繼而通過方向和行走的距離推算出行人所處的具體位置.

在Android智能手機平臺上,檢測手機的方向角是通過獲取地磁場傳感器的數(shù)值和加速度傳感器的數(shù)值來計算的.與此同時,由于手機朝向的不同,所檢測出的方向角也會相對不同,因此,在行走過程中,要保持手機的朝向盡可能穩(wěn)定,才能得到相對準確的數(shù)據(jù).

3.4.4 位置估算

獲取行人的步頻、步長和方向角后,最后就是進行位置估算[9,12].本課題通過基于WiFi網(wǎng)絡的室內定位技術獲取了行人的初始位置,那么,通過步頻、步長和方向角和初始位置就可以推算出行人行走后的大致位置.具體位置的計算公式分為X軸方向的公式和Y軸方向的公式:

4 系統(tǒng)測試結果與分析

本次實驗于校圖書館四樓進行,實驗過程中實驗人員手持Android智能手機從特地位置出發(fā),按照預設路線行走.其中,第一組數(shù)據(jù)僅通過PDR算法來實現(xiàn)定位,因而實驗數(shù)據(jù)的起始點與預設路線起點一致;第二組數(shù)據(jù)是僅通過指紋定位算法實現(xiàn);第三組數(shù)據(jù)是使用PDR與指紋定位相結合的算法實現(xiàn).在實驗過程當中,記錄每次實驗的實際數(shù)據(jù),存儲到數(shù)據(jù)庫,計算得到三組與正確數(shù)據(jù)的誤差值,用matlab將三組軌跡繪制出來如圖6所示.其中,x軸表示坐標編號,y軸表示誤差值;圖7為使用PDR和位置指紋定位算法結合得到的行人軌跡和實際行人軌跡的對比圖;圖8為采樣點與wifi熱點位置的分布圖.

圖6 三組算法誤差對比圖

圖7 行人實際位置與實驗位置對比圖

圖8 采樣點與wifi熱點位置分布圖

1)圖6實線代表僅用PDR算法定位得到的誤差,由于PDR的起點與實際起點一致,因此在起點的誤差為0.通過圖像可知,隨著時間的延長,PDR存在的累積誤差將越來越大.僅靠PDR算法,適用于短時間,短距離內的定位,但是不滿足實際需求,因此不可取.

2)圖6紅色虛線代表僅用wifi位置指紋定位得到的誤差,其平均誤差為11.38米.從圖像可知,位置指紋定位的誤差的跳躍性非常大,圖中誤差的震蕩區(qū)間為[1.0,21.5].實驗數(shù)據(jù)中最大誤差距離達到21.5米,對于在圖書館內的導航,如果誤差超過了20米,那么導航的意義微乎其微.對比PDR算法定位,其優(yōu)勢并不明顯.由于環(huán)境、天氣因素均對wifi信號強度有很大的影響,所以僅用位置指紋定位對于實際需求很難滿足.

3)圖6藍色虛線是結合了位置指紋定位算法和PDR算法得到的誤差值,其平均誤差為6.74米.從圖中可以看出,對比紅色虛線,其趨勢比較平滑、穩(wěn)定.對比實線,前6個點,其誤差值大于PDR算法.但從第7個點開始,PDR算法的誤差開始大于聯(lián)合定位的誤差,而聯(lián)合定位的誤差值繼續(xù)趨向穩(wěn)定.因此,對于長距離和長時間的定位,聯(lián)合定位明顯優(yōu)于PDR算法,而且其平均誤差比位置指紋定位算法的誤差小,對于實際情況的應用更加合適.

4)圖7中藍色實線是由實驗數(shù)據(jù)得到的行人軌跡,紅色實線則是行人實際的軌跡,兩條軌跡中選取了12個坐標點進行比較.其中藍色軌跡在方向上與紅色軌跡大致一致,但存在著一定誤差.

綜上所述,采用位置指紋與PDR算法聯(lián)合使用的定位算法,達到PDR算法克服位置指紋定位的不穩(wěn)定性,又通過位置指紋定位算法的絕對性調整具體位置,消除PDR算法的累積誤差.說明結合位置指紋和行人航跡算法的室內定位技術具有一定的可行性.

5 總結

本文針對wifi室內定位技術和PDR技術的組合,就如何降低定位誤差進行了深入的思考.本文特色在于通過wifi室內定位技術和PDR技術的相輔相成,很大程度上減少了定位的偶然誤差.

但與市場上商業(yè)化的,成熟的室內定位技術相比,依舊存在很多不足,本文采用的wifi室內定位技術需要大量的室內wifi信號數(shù)據(jù),為系統(tǒng)投入使用的前期準備工作帶來了一定的困難,但一旦數(shù)據(jù)齊全,定位的準確性也比較高.

1谷歌升級 Android版谷歌地圖,新增室內導航功能. http://www.36kr.com/p/63722.html.

2 諾基亞室內導航地圖.http://www.cnbeta.com/articles/ 164013.htm.

3日本富士通室內導航系統(tǒng).http://www.cnbeta.com/articles/ 195110.htm.

4國家測繪地理信息局.介紹幾種室內定位技術. http://www.sbsm.gov.cn/article/zszygx/zjlt/200812/20081200 045814.shtml.2008.

5李昊.位置指紋定位技術.山西電子技術,2007,(5):84–87.

6陳偉.基于GPS和自包含傳感器的行人室內外無縫定位算法研究[碩士學位論文].合肥:中國科學技術大學,2010.

7陳聰傳,程良倫.區(qū)域細化的RFID室內定位算法.計算機應用與軟件,2011,28(1):50–52.

8王立劍.基于Android平臺的手機室內定位及導航系統(tǒng)的設計與實現(xiàn)[碩士學位論文].青島:中國海洋大學,2013.

9徐偉.基于Android手機的室內定位技術研究與實現(xiàn)[碩士學位論文].武漢:華中師范大學,2014.

10裘昕,朱林.行走航跡推算技術的研究.http://www.paper. edu.cn/releasepaper/content/201111-410.[2011-11-24].

11葉震.數(shù)字信號處理中的矩陣運算化簡.合肥工業(yè)大學學報,1985,(1):44–48.

12謝如花.步數(shù)檢測方法及在手腕式計步器中的應用研究[碩士學位論文].蘭州:蘭州交通大學,2013.

13 Li B,Wang Y,Lee HK,Dempster A.Method for yielding a database of location fingerprints in WLAN.IEEE Proc. Communications,2005,152(5):580–586.

14 Beauregard S,Haas H.Pedestrian dead reckoning:A basis for personal positioning.Proc.of the 3rd Workshop on Positioning,Navigation and Communication.2006.27–35.

Indoor Positioning Technology Based on Location Fingerprint and Pedestrian Track

LUO Si-Qi,LUO Xiao-Ling,LI Min-Cheng,LI Zhi-Feng,CHEN Jian-Cheng,ZHOU Xian-Wei,PAN Jia-Hui

(School of Software,South China Normal University,Nanhai 528225,China)

On this paper,the research mainly focuses on the technology of indoor location.First,we collect coordinates of sample spots by handheld smart device in the specified range and information of wifi wireless hotspot,with which the location fingerprint technique is applied to absolute positioning;In order to improve the real-time performance and accuracy of indoor positioning,the pedestrian dead reckoning algorithm which will measure stride frequency,estimate step size and detect the direction with data collected and processed by the mobile phone sensor is used to achieve relative position estimation.The pedestrian dead reckoning algorithm can overcome the instability of the location fingerprint technique and the latter can reduce the cumulative error that the former brings.The result shows the combination of the two technologies is able to effectively improve the accuracy of indoor location and be fully used in the real world.

indoor positioning;Android platform;wifi;location fingerprinting technique;pedestrian dead reckoning

廣東大學生科技創(chuàng)新培育專項資金(“攀登計劃”專項資金)(pdjh2016b0129);國家自然科學基金青年科學基金(61503143);廣東省自然科學基金博士科研啟動項目(2014A030310244)

2016-09-04;收到修改稿時間:2016-11-03

10.15888/j.cnki.csa.005784