徐雯琪 黃玉春 劉亞奇 單 杰

1 武漢大學(xué)遙感信息工程學(xué)院，湖北武漢，430079

2 廣州汽車集團(tuán)股份有限公司汽車工程研究院，廣東廣州，511434

在室內(nèi)場(chǎng)景中，由于建筑物的遮擋、室內(nèi)結(jié)構(gòu)復(fù)雜，全球?qū)Ш叫l(wèi)星系統(tǒng)(global navigation satellite sys?tem，GNSS）常受到信號(hào)干擾，難以提供精確的定位導(dǎo)航信息。因此，實(shí)現(xiàn)室內(nèi)環(huán)境定位服務(wù)顯得尤為重要。為達(dá)到這一目標(biāo)，研究人員提出了許多室內(nèi)定位技術(shù)，如ZigBee定位［1］、射頻識(shí)別技術(shù)［2］、紅外定位［3］、超聲波定位［4］、超寬帶無線電技術(shù)［5］、Wi Fi定位［6］、航位推算定位［7］、地磁定位［8］等。這些定位技術(shù)都存在各自的優(yōu)缺點(diǎn)，使用場(chǎng)景也各有不同，至今沒有一種通用的室內(nèi)定位技術(shù)大范圍推廣。

手機(jī)上集成了加速度計(jì)、陀螺儀、磁力計(jì)等多種傳感器，這使得利用手機(jī)進(jìn)行航位推算成為可能［9］。同時(shí)，由于Wi Fi的普及，如商場(chǎng)、機(jī)場(chǎng)等室內(nèi)環(huán)境大多分布了覆蓋率較高的Wi Fi，基于手機(jī)Wi Fi的定位方式成為一種熱門的室內(nèi)定位方案。Wi Fi定位的成本較低，但精度易受環(huán)境影響；行人航位推算（pedes?trian dead reckoning，PDR）定位精度不受外界影響，但只能獲取相對(duì)位置，且存在累計(jì)誤差。故本文提出聯(lián)合Wi Fi指紋定位和PDR算法的室內(nèi)定位方法。

1 方法原理與流程

1.1 手機(jī)Wi Fi指紋定位算法

Wi Fi指紋定位利用多個(gè)Wi Fi熱點(diǎn)在定位環(huán)境中形成具有唯一性的信號(hào)強(qiáng)度序列進(jìn)行定位。這種信號(hào)強(qiáng)度序列被稱為Wi Fi指紋。整個(gè)定位技術(shù)包含訓(xùn)練和服務(wù)兩個(gè)階段。訓(xùn)練階段主要包括Wi Fi指紋的采集與處理、定位模型的確定；服務(wù)階段是指利用手機(jī)Wi Fi模塊和定位模型確定手機(jī)位置的過程。

1）構(gòu)建Wi Fi指紋地圖。實(shí)地采集指定Wi Fi熱點(diǎn)設(shè)備的接收信號(hào)強(qiáng)度（received signal strength，RSS）值，得到Wi Fi指紋。同時(shí)記錄該位置的空間信息，如平面坐標(biāo)、樓層等，即可得到WiFi指紋地圖。

圖1展示了某一地點(diǎn)RSS值的分布與高斯模型。同一位置不同Wi Fi熱點(diǎn)的信號(hào)強(qiáng)度分布類似高斯分布，用采集到的數(shù)據(jù)構(gòu)建高斯模型，并用高斯模型選出高概率數(shù)據(jù)，對(duì)這些數(shù)據(jù)求平均值，將其作為各個(gè)位置的每個(gè)熱點(diǎn)濾波后的信號(hào)強(qiáng)度值，再錄入指紋地圖數(shù)據(jù)庫(kù)，減少異常信號(hào)數(shù)據(jù)對(duì)定位結(jié)果的影響［10］。

圖1 RSS值分布與高斯模型Fig.1 Distribution of RSS Values and Gaussian Model

2）建立Wi Fi指紋匹配算法。利用Wi Fi指紋進(jìn)行定位起源于RADAR算法［11］，該算法使用k最近鄰（k?nearest neighborhood，KNN）算法去推斷用戶位置。將定位時(shí)采集到的信號(hào)向量與指紋地圖數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行比較，選出相似度最接近的一個(gè)或多個(gè)Wi Fi指紋，綜合這些指紋的位置信息，便可得到Wi Fi定位的估計(jì)位置。

KNN是當(dāng)前最常見的匹配算法，該算法直接計(jì)算采集的信號(hào)向量與指紋向量的歐氏距離，等同對(duì)待每個(gè)指紋對(duì)定位結(jié)果的貢獻(xiàn)。加權(quán)KNN（weighted KNN，WKNN）算法在定位過程中，不僅能計(jì)算出前k個(gè)歐氏距離最小的指紋向量，還能對(duì)不同指紋位置設(shè)置不同的權(quán)重，這k個(gè)位置的平均值計(jì)算公式如下：

式中，di為向量的歐氏距離。

當(dāng)前指紋向量與手機(jī)采集的信號(hào)向量間的歐氏距離越小，該指紋的重要性權(quán)重就越大。由于每個(gè)指紋對(duì)定位結(jié)果的貢獻(xiàn)不同，而不能等同對(duì)待。本文用WKNN算法來實(shí)現(xiàn)手機(jī)Wi Fi指紋定位。

1.2 基于手機(jī)傳感器的PDR算法

PDR算法通過將體積小、精度低的慣性傳感器固定在行人身上，檢測(cè)行人步數(shù)、步長(zhǎng)、步行方向，從而實(shí)現(xiàn)位置推算［12］。

利用手機(jī)加速度計(jì)的數(shù)據(jù)分析行人步行狀態(tài)，實(shí)現(xiàn)步伐檢測(cè)，根據(jù)一步過程中的加速度特征，使用步長(zhǎng)估算模型計(jì)算行人步行距離，再結(jié)合手機(jī)的加速度計(jì)和磁力計(jì)算出步行方向。于是，在每一步結(jié)束的時(shí)刻，可以根據(jù)步長(zhǎng)和方向計(jì)算步行相對(duì)坐標(biāo)，再不斷遞推，最終達(dá)到行人定位的目的。因此，手機(jī)PDR算法的核心在于步伐檢測(cè)、步長(zhǎng)估計(jì)、方向角確定3個(gè)方面。

1）步伐檢測(cè)。手機(jī)步伐檢測(cè)采用的傳感器是手機(jī)加速度計(jì)，對(duì)手機(jī)加速度計(jì)的數(shù)據(jù)進(jìn)行預(yù)處理，可將步伐檢測(cè)問題轉(zhuǎn)化為加速度變化周期檢測(cè)問題。

本文采用的是改進(jìn)的峰值檢測(cè)法。人在行走過程中，行走的速度會(huì)影響到加速度變化周期，而手機(jī)的無規(guī)律抖動(dòng)，或步行過程中使用手機(jī)，會(huì)導(dǎo)致加速度中出現(xiàn)一些偽波峰，如圖2所示。

圖2 偽波峰現(xiàn)象Fig.2 Pseudo Crest Phenomenon

手機(jī)開啟加速度監(jiān)聽后，不斷采集加速度數(shù)據(jù)，對(duì)于原始加速度數(shù)據(jù)，需要對(duì)其合加速度進(jìn)行均值濾波，再進(jìn)行峰值檢測(cè)。檢測(cè)到峰值后需要計(jì)算3個(gè)特征值，分別是相鄰波峰時(shí)間間隔、波峰的加速度值、兩個(gè)波峰的差值，只有這3個(gè)特征值同時(shí)滿足閾值約束時(shí)，才能判定行人當(dāng)前已行走一步。

2）步長(zhǎng)估計(jì)。非線性模型主要通過對(duì)人步行過程中的加速度觀測(cè)值采用統(tǒng)計(jì)分析方法建立數(shù)學(xué)模型。Weinberg［13］提出了一種簡(jiǎn)單的非線性模型：

式中，S為行人步長(zhǎng)；Amax、Amin分別代表一步過程中Z軸方向的最大、最小加速度；a為常量，代表模型系數(shù)。

人在正常行走時(shí)，速度的變化不會(huì)太大，在整體上是一個(gè)漸變的過程，這個(gè)過程中前后兩步之間的步長(zhǎng)雖然不同，但差異不大，因此可以在非線性步長(zhǎng)估算的基礎(chǔ)上對(duì)每一步進(jìn)行微調(diào)。本文采用卡爾曼濾波對(duì)非線性步長(zhǎng)估計(jì)模型進(jìn)行改進(jìn)。

在步長(zhǎng)估算中，將t時(shí)刻每一步的步長(zhǎng)作為系統(tǒng)狀態(tài)xt，則系統(tǒng)變化規(guī)律可用以下線性狀態(tài)方程描述：

式中，F(xiàn)t表示系統(tǒng)從t?1時(shí)刻演化到t時(shí)刻的狀態(tài)轉(zhuǎn)移矩陣；Bt是作用在控制器向量ut上的輸入，即控制模型；wt是過程噪聲，并服從N(0，Q)分布。令Ft=1，即令前后兩步步長(zhǎng)相等，由于系統(tǒng)沒有控制輸入，所以不存在Bt ut項(xiàng)，則wt的意義就是前后兩步的步長(zhǎng)變化。

將非線性步長(zhǎng)估算模型的計(jì)算結(jié)果作為系統(tǒng)的觀測(cè)zt，觀測(cè)值與系統(tǒng)狀態(tài)值之間的關(guān)系可以用線性測(cè)量方程表示：

式中，Ht為測(cè)量矩陣；vt為觀測(cè)噪聲，服從N(0，Q)分布，且與過程噪聲互不相關(guān)。

由于Weinberg模型需要事先確定各自的模型系數(shù)a，所以在實(shí)驗(yàn)前，在走廊中正常行走100 m，利用步伐檢測(cè)計(jì)算步數(shù)，根據(jù)每一步的加速度特征計(jì)算a。圖3展示了步長(zhǎng)估計(jì)結(jié)果，可以看出，使用卡爾曼濾波對(duì)非線性模型進(jìn)行改進(jìn)后，步長(zhǎng)估計(jì)結(jié)果比原模型算法的結(jié)果更加穩(wěn)定、準(zhǔn)確。

圖3 基于卡爾曼濾波的步長(zhǎng)估計(jì)Fig.3 Step Estimation Based on Kalman Filter

3）方向角確定。本文利用手機(jī)中陀螺儀和電子羅盤數(shù)據(jù)，采用互補(bǔ)濾波器進(jìn)行方向角確定。

1.3 PDR定位結(jié)果糾正

考慮到行人行走具有連續(xù)性，并且始終在當(dāng)前位置可達(dá)的區(qū)域行走，需要利用地圖結(jié)構(gòu)糾正PDR計(jì)算結(jié)果。在融合地圖信息時(shí)，可以使用粒子濾波算法對(duì)行人運(yùn)動(dòng)特征進(jìn)行約束，對(duì)處于不可達(dá)的區(qū)域的粒子，將其權(quán)值降低，使得位置估計(jì)更準(zhǔn)確。

粒子濾波算法通過尋找一組在狀態(tài)空間中傳播的樣本來近似表示概率密度函數(shù)［14］，用樣本均值代替積分運(yùn)算，進(jìn)而獲得系統(tǒng)狀態(tài)最小方差估計(jì)。

在本文PDR算法中，算法的輸入為手機(jī)加速度A、磁場(chǎng)強(qiáng)度M、上一時(shí)刻位置xt?1，算法輸出為當(dāng)前位置xt，則系統(tǒng)的狀態(tài)方程可以表達(dá)為如下形式：

對(duì)于粒子濾波中的每一個(gè)粒子，在計(jì)算其重要性權(quán)值時(shí)，可以使用如下重要性密度函數(shù)：

式中，σ為位置估計(jì)標(biāo)準(zhǔn)差；xt為利用上一時(shí)刻位置估算結(jié)果進(jìn)行預(yù)測(cè)的位置；xit為利用上一時(shí)刻第i個(gè)粒子的位置進(jìn)行預(yù)測(cè)的結(jié)果，兩者都由式（6）計(jì)算。由于整個(gè)粒子群的初始化是在初始位置附近采樣，后續(xù)定位計(jì)算中可能出現(xiàn)部分粒子的預(yù)測(cè)結(jié)果與上一時(shí)刻的位置形成“穿墻而過”的現(xiàn)象，因此需要對(duì)這一類粒子的權(quán)重進(jìn)行抑制。如圖4所示，圖中黑色圓點(diǎn)為上一時(shí)刻位置估算結(jié)果，上方粒子和下方粒子為粒子群的預(yù)測(cè)位置，由于圖中上方粒子與上一步位置估算結(jié)果的連線與墻相交，則認(rèn)為這部分粒子的預(yù)測(cè)結(jié)果不合理，將其重要性權(quán)重降低。

圖4 粒子權(quán)重抑制示意圖Fig.4 Diagram of Particle Weight Suppression

本文利用PostgreSQL空間查詢插件PostGIS中的ST_Intersects函數(shù)完成“穿墻”檢測(cè)?；谶@一思路，每個(gè)粒子的重要性權(quán)值wt(xit)的遞推更新公式可表示為如下形式：

在PDR算法中應(yīng)用粒子濾波時(shí)，有大量的粒子參與計(jì)算，造成粒子少時(shí)算法不穩(wěn)定、粒子多時(shí)算法效率低兩個(gè)弊端。為了能得到一種穩(wěn)定的、能用于實(shí)時(shí)定位的算法，本文在標(biāo)準(zhǔn)粒子濾波算法的基礎(chǔ)上提出了一種簡(jiǎn)化的粒子濾波算法。

首先，粒子數(shù)量過多導(dǎo)致算法時(shí)間復(fù)雜度較高，而在實(shí)際運(yùn)算過程中，粒子不可避免地會(huì)發(fā)生權(quán)重衰減，大部分粒子的權(quán)重都非常低，它們卻使得數(shù)據(jù)庫(kù)交互次數(shù)大大增加。為了降低計(jì)算成本，本文采用25個(gè)粒子進(jìn)行遞推計(jì)算。這25個(gè)粒子在初始化時(shí)，以當(dāng)前定位位置為中心，往X、Y方向以1 m為間隔形成一個(gè)5×5大小的點(diǎn)陣，如圖5所示，圖中黑點(diǎn)為當(dāng)前位置。每次初始化或重采樣時(shí)都按照這種規(guī)則設(shè)置粒子，避免隨機(jī)采樣導(dǎo)致算法性能不穩(wěn)定的問題。

圖5 粒子分布示意圖Fig.5 Diagram of Distribution of Particles

其次，采用的粒子數(shù)量只有25個(gè)，對(duì)其進(jìn)行加權(quán)求和運(yùn)算并不能逼近貝葉斯濾波中的積分運(yùn)算，得到的計(jì)算結(jié)果與實(shí)際位置間會(huì)存在較大偏差。因此，在利用粒子估算當(dāng)前時(shí)刻位置時(shí)，本文沒有采用粒子位置的加權(quán)和進(jìn)行計(jì)算，而是直接使用重要性權(quán)值最大的粒子的位置作為本次定位優(yōu)化結(jié)果。這會(huì)使得定位軌跡盡量保持原始PDR定位軌跡的原貌。而在標(biāo)準(zhǔn)粒子濾波算法中，由于加權(quán)和受到很多粒子的影響，會(huì)對(duì)每一步的定位結(jié)果都進(jìn)行修改，比如在走廊中靠墻行走時(shí)，標(biāo)準(zhǔn)粒子濾波算法會(huì)使軌跡更加靠近走廊中間。使用簡(jiǎn)化的粒子濾波算法，粒子對(duì)軌跡的影響不大，當(dāng)軌跡發(fā)生“穿墻”現(xiàn)象時(shí)，重要性權(quán)值最大的粒子會(huì)對(duì)定位結(jié)果進(jìn)行改正。

除了以上兩點(diǎn)簡(jiǎn)化操作，其他步驟如重要性權(quán)值更新、粒子退化檢測(cè)等都與粒子濾波算法保持一致。針對(duì)PDR算法，采用簡(jiǎn)化粒子濾波算法后的計(jì)算結(jié)果如圖6所示，圖中的軌跡與原PDR算法計(jì)算的軌跡基本一致，在原PDR軌跡第一次發(fā)生“穿墻”現(xiàn)象的位置，圖中的軌跡有明顯的不連續(xù)“跳動(dòng)”，避免了定位結(jié)果落入不可達(dá)區(qū)域，這就是由權(quán)值最大的粒子對(duì)定位結(jié)果進(jìn)行改正的結(jié)果。

圖6 采用簡(jiǎn)化粒子濾波前后的軌跡Fig.6 Trajectories Before and After Using Simplified Particle Filter

2 手機(jī)室內(nèi)定位系統(tǒng)實(shí)現(xiàn)和實(shí)驗(yàn)分析

2.1 系統(tǒng)實(shí)現(xiàn)

本文室內(nèi)定位系統(tǒng)包含3個(gè)部分：手機(jī)客戶端、服務(wù)器端和Wi Fi基站。系統(tǒng)采用的是客戶端?服務(wù)器（client/server，C/S）和瀏覽器?服務(wù)器（browser/server，B/S）混合結(jié)構(gòu)模式。其中，在訓(xùn)練階段完成Wi Fi指紋地圖構(gòu)建和定位算法的確定。服務(wù)階段中服務(wù)器端使用PDR定位模塊和Wi Fi定位模塊計(jì)算出定位結(jié)果并將其返回手機(jī)端，手機(jī)端獲取定位結(jié)果后會(huì)更新到手機(jī)界面的地圖上。

2.2 實(shí)驗(yàn)分析

本文以武漢大學(xué)信息學(xué)部5號(hào)樓的一樓和二樓為實(shí)驗(yàn)區(qū)域進(jìn)行了一組行人定位實(shí)驗(yàn)。實(shí)驗(yàn)所在走廊面積約190 m2，東西方向的走廊長(zhǎng)約62 m，寬約2.5 m；南北方向的走廊長(zhǎng)約15 m，寬約3.7 m，實(shí)驗(yàn)設(shè)備為紅米4手機(jī)。

首先構(gòu)建Wi Fi指紋地圖，沿著實(shí)驗(yàn)區(qū)域的走廊中間位置，以1 m為間隔采集了62個(gè)位置的Wi Fi指紋，每個(gè)位置指紋約有50個(gè)Wi Fi熱點(diǎn)信號(hào)，在每個(gè)位置采集信號(hào)的時(shí)間約5 min，采集的次數(shù)為10 000次。將處理后的Wi Fi指紋與位置信息一同存入數(shù)據(jù)庫(kù)，每個(gè)位置都對(duì)應(yīng)唯一的Wi Fi指紋信息。

實(shí)驗(yàn)過程中，行人手持實(shí)驗(yàn)設(shè)備從5號(hào)樓正門出發(fā)，沿一樓走廊直行后上樓梯到二樓，并繼續(xù)直行，整個(gè)軌跡長(zhǎng)約110 m。為了得到系統(tǒng)的定位精度，行人在行走過程中選擇5個(gè)地點(diǎn)作為對(duì)比點(diǎn)，記錄該位置的實(shí)際坐標(biāo)和定位結(jié)果。對(duì)比點(diǎn)1、2、3、4、5的定位誤差分別為1.80 m、0.78 m、1.89 m、1.43 m、2.44 m。

真實(shí)軌跡及對(duì)比點(diǎn)分布見圖7。由圖8定位軌跡可以發(fā)現(xiàn)，步行方向的穩(wěn)定對(duì)于PDR算法尤為重要。圖7（a）中，在上樓過程中手機(jī)抖動(dòng)劇烈，手機(jī)檢測(cè)到的方向角存在較大誤差，因此，樓梯部分定位結(jié)果與實(shí)際軌跡偏差較大。此外，由于對(duì)比點(diǎn)1附近方向檢測(cè)的噪聲較大，軌跡方向與實(shí)際情況偏差較大。在該處轉(zhuǎn)彎時(shí)，PDR算法發(fā)生了“穿墻”，而本文采用的簡(jiǎn)化粒子濾波算法能在“穿墻”點(diǎn)附近找到一個(gè)合適的定位結(jié)果，從而保證PDR算法的正常遞推。在對(duì)比點(diǎn)3附近，由于Wi Fi定位模塊檢測(cè)到樓層發(fā)生切換，使得PDR算法重新設(shè)置初始位置，并在二樓進(jìn)行遞推計(jì)算。

圖7 真實(shí)軌跡及對(duì)比點(diǎn)分布Fig.7 Real Trajectories and Distribution of Contrast Points

圖8 系統(tǒng)定位結(jié)果Fig.8 System Positioning Results

5個(gè)對(duì)比點(diǎn)誤差都在3 m以內(nèi)，誤差最大的是在二樓中對(duì)比點(diǎn)5，由于行人到達(dá)該點(diǎn)時(shí)經(jīng)歷了一段較長(zhǎng)距離的直行，誤差不斷積累，最終達(dá)到2.44 m。因此在長(zhǎng)距離直行時(shí)，由于無法有效地融合地圖結(jié)構(gòu)信息，PDR算法的誤差無法及時(shí)降低。而在一樓的對(duì)比點(diǎn)1使用粒子濾波糾正“穿墻”結(jié)果后，在對(duì)比點(diǎn)2處的誤差有一定降低，只有0.78 m。

3 結(jié)束語

本文使用的簡(jiǎn)化粒子濾波融合地圖信息能有效降低PDR算法的累積誤差，而Wi Fi指紋定位既能為PDR算法提供初始值，又能檢測(cè)樓層切換，從而實(shí)現(xiàn)定位系統(tǒng)的跨樓層定位，使得室內(nèi)定位系統(tǒng)的適應(yīng)性更強(qiáng)，為其他室內(nèi)聯(lián)合定位方案提供了參考。