徐雯琪 黃玉春 劉亞奇 單 杰

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

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

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

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

1 方法原理與流程

1.1 手機Wi Fi指紋定位算法

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

1）構建Wi Fi指紋地圖。實地采集指定Wi Fi熱點設備的接收信號強度（received signal strength，RSS）值，得到Wi Fi指紋。同時記錄該位置的空間信息，如平面坐標、樓層等，即可得到WiFi指紋地圖。

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

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

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

KNN是當前最常見的匹配算法，該算法直接計算采集的信號向量與指紋向量的歐氏距離，等同對待每個指紋對定位結果的貢獻。加權KNN（weighted KNN，WKNN）算法在定位過程中，不僅能計算出前k個歐氏距離最小的指紋向量，還能對不同指紋位置設置不同的權重，這k個位置的平均值計算公式如下：

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

當前指紋向量與手機采集的信號向量間的歐氏距離越小，該指紋的重要性權重就越大。由于每個指紋對定位結果的貢獻不同，而不能等同對待。本文用WKNN算法來實現(xiàn)手機Wi Fi指紋定位。

1.2 基于手機傳感器的PDR算法

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

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

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

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

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

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

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

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

人在正常行走時，速度的變化不會太大，在整體上是一個漸變的過程，這個過程中前后兩步之間的步長雖然不同，但差異不大，因此可以在非線性步長估算的基礎上對每一步進行微調。本文采用卡爾曼濾波對非線性步長估計模型進行改進。

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

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

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

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

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

圖3 基于卡爾曼濾波的步長估計Fig.3 Step Estimation Based on Kalman Filter

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

1.3 PDR定位結果糾正

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

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

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

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

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

圖4 粒子權重抑制示意圖Fig.4 Diagram of Particle Weight Suppression

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

在PDR算法中應用粒子濾波時，有大量的粒子參與計算，造成粒子少時算法不穩(wěn)定、粒子多時算法效率低兩個弊端。為了能得到一種穩(wěn)定的、能用于實時定位的算法，本文在標準粒子濾波算法的基礎上提出了一種簡化的粒子濾波算法。

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

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

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

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

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

2 手機室內定位系統(tǒng)實現(xiàn)和實驗分析

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

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

2.2 實驗分析

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

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

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

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

圖7 真實軌跡及對比點分布Fig.7 Real Trajectories and Distribution of Contrast Points

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

5個對比點誤差都在3 m以內，誤差最大的是在二樓中對比點5，由于行人到達該點時經歷了一段較長距離的直行，誤差不斷積累，最終達到2.44 m。因此在長距離直行時，由于無法有效地融合地圖結構信息，PDR算法的誤差無法及時降低。而在一樓的對比點1使用粒子濾波糾正“穿墻”結果后，在對比點2處的誤差有一定降低，只有0.78 m。

3 結束語

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