石 柯, 宋小妹, 王信達(dá), 呼文彪

(華中科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,湖北 武漢 430074)

成熟的室外定位和基于位置的服務(wù)(location-based service,簡稱LBS)技術(shù)的興起,在方便人們生活的同時(shí),加大了人們對(duì)于定位服務(wù)的依賴.然而到目前為止,室內(nèi)環(huán)境中還沒有成熟和廣泛適用的定位技術(shù).針于室內(nèi)環(huán)境,人們相繼提出了使用超聲波、紅外線、藍(lán)牙等技術(shù)的一系列定位方法,但其應(yīng)用都有嚴(yán)重的局限性,難以達(dá)到室內(nèi)定位和導(dǎo)航的要求.目前,大型公共場所幾乎已經(jīng)全面覆蓋WiFi 網(wǎng)絡(luò),這給室內(nèi)定位技術(shù)帶來新的契機(jī).WiFi 信號(hào)在傳播過程中強(qiáng)度會(huì)逐漸減弱,根據(jù)信號(hào)強(qiáng)度與傳播距離之間的數(shù)學(xué)模型,通過測量信號(hào)的強(qiáng)度可計(jì)算得到接入點(diǎn)與目標(biāo)之間的距離,再根據(jù)三邊測量法可得到目標(biāo)位置.但這種方法只有在視距、無障礙、無反射等良好的環(huán)境下才能達(dá)到較高的精度.室內(nèi)環(huán)境難以滿足這種要求,因此其定位效果不甚理想.

考慮到實(shí)際的室內(nèi)環(huán)境難以建立通用的信號(hào)強(qiáng)度與距離之間的數(shù)學(xué)模型[1],人們提出了基于經(jīng)驗(yàn)的信號(hào)指紋方法.在離線階段,先對(duì)場景進(jìn)行勘測,即在各個(gè)參考點(diǎn)(reference point,簡稱RP)進(jìn)行采樣,得到參考點(diǎn)的位置特征(信號(hào)指紋),并建立位置-指紋數(shù)據(jù)庫;在定位階段,將目標(biāo)測得的信號(hào)指紋與數(shù)據(jù)庫存儲(chǔ)的數(shù)據(jù)進(jìn)行匹配,得到匹配度較高的參考點(diǎn)位置,以此確定目標(biāo)位置.在此方法中,WiFi 信號(hào)強(qiáng)度特征RSSI(received signal strength indication)常常被用作位置指紋.鑒于室內(nèi)環(huán)境復(fù)雜多變,無線信號(hào)傳播易受反射、陰影衰落(shadowing)、多徑效應(yīng)(multipath effect)等因素的影響,離線階段采集的信號(hào)指紋和在線階段獲取的RSSI 數(shù)據(jù)可能存在偏差,會(huì)導(dǎo)致位置匹配出現(xiàn)較大誤差.因此,為進(jìn)一步提高室內(nèi)定位的精度,并應(yīng)對(duì)環(huán)境變化帶來的不利影響,本文提出了多傳感器輔助的WiFi 指紋定位方法,在記錄WiFi 信號(hào)強(qiáng)度的同時(shí),利用智能設(shè)備內(nèi)置的加速計(jì)、陀螺儀等多種傳感器預(yù)估用戶移動(dòng)軌跡信息,將軌跡信息跟信號(hào)指紋信息按一定權(quán)重結(jié)合起來建立綜合概率模型,得到各個(gè)參考點(diǎn)的綜合匹配概率,從而提高位置匹配的精度.

1 相關(guān)工作

最早提出的信號(hào)指紋定位模型RADAR[2,3]是一個(gè)基于確定性匹配策略的系統(tǒng).在離線階段,目標(biāo)和基站的時(shí)鐘進(jìn)行同步;目標(biāo)在各個(gè)參考點(diǎn)發(fā)射信號(hào),同時(shí)記錄時(shí)間、參考點(diǎn)坐標(biāo)和身體朝向;各基站接收到信號(hào),記錄下接收時(shí)間、基站自身編號(hào)和信號(hào)強(qiáng)度;基于同步的時(shí)鐘,將參考點(diǎn)坐標(biāo)和各基站接收到的信號(hào)強(qiáng)度關(guān)聯(lián)起來,以此為基礎(chǔ)建立指紋數(shù)據(jù)庫.在實(shí)時(shí)定位階段,將各基站接收到的信號(hào)強(qiáng)度信息與數(shù)據(jù)庫中存儲(chǔ)的信息進(jìn)行匹配,根據(jù)K最近鄰(Knearest neighbor,簡稱KNN)算法找到K個(gè)指紋最相似的參考點(diǎn),對(duì)這K個(gè)參考點(diǎn)坐標(biāo)取均值得到定位結(jié)果.

另一個(gè)典型的指紋定位系統(tǒng)是Horus[4],與RADAR 不同的是,在離線階段,Horus 讓基站發(fā)送信號(hào),在參考點(diǎn)接收信號(hào),信號(hào)傳播方向正好相反,但這不會(huì)影響定位精度[2].另外,Horus 對(duì)RADAR 進(jìn)行了改進(jìn),使用基于統(tǒng)計(jì)的方法進(jìn)行位置匹配,在指紋數(shù)據(jù)庫中建立指紋的高斯分布;在定位階段,以指紋匹配概率作為各參考點(diǎn)權(quán)重計(jì)算定位結(jié)果.

隨著手機(jī)和平板電腦等智能設(shè)備計(jì)算性能的改進(jìn)和集成傳感器種類的增多,GSM、FM、地磁場等信息也被用來進(jìn)行定位.He 等人使用GSM 信號(hào)作為位置指紋[5],定位精度達(dá)到了4m,對(duì)樓層的識(shí)別正確率達(dá)到60%.文獻(xiàn)[6,7]使用FM 信號(hào)強(qiáng)度進(jìn)行定位,其中,文獻(xiàn)[6]達(dá)到了3m 左右的精度,已接近WiFi 定位的精度.利用室內(nèi)環(huán)境對(duì)于地磁場的影響,文獻(xiàn)[8]將地磁場作為位置指紋,將定位精度提升到1m 左右.但該方法需要進(jìn)行大量的指紋勘測,且需要用戶佩戴專用硬件設(shè)備,因此不利于普及使用.為了減少離線階段的工作量,Yoon 等人提出了基于RM 信號(hào)的指紋定位技術(shù)ACMI[7].由于RM 信號(hào)進(jìn)入室內(nèi)的主要途徑是門窗,因此根據(jù)建筑平面圖即可得到室內(nèi)的信號(hào)分布,無需進(jìn)行人工采樣.但該方法的精度并不理想,在使用8 個(gè)FM 基站的情況下,ACMI 只能達(dá)到6m 的平均精度.因此,ACMI 只適合門窗較多且對(duì)定位精度要求不高的環(huán)境.

目前,智能手機(jī)基本都集成了加速計(jì)和陀螺儀等傳感器,能夠?qū)崿F(xiàn)基于慣性導(dǎo)航(inertial navigation system,簡稱INS)原理的PDR(pedestrian dead reckoning),但存在較大的距離(步數(shù))累計(jì)誤差.文獻(xiàn)[9]將PDR 和WiFi 指紋定位結(jié)合起來,使用粒子濾波器,利用傳感器數(shù)據(jù)來平滑WiFi 信號(hào)指紋,使用Kalman 濾波器,利用WiFi 指紋定位的軌跡來減小PDR 過程中的漂移誤差,最終達(dá)到了1.53m 的定位精度.但由于粒子濾波器計(jì)算量大,且耗費(fèi)時(shí)間長,因此不適用于智能手機(jī)上的實(shí)時(shí)定位.為了實(shí)現(xiàn)實(shí)時(shí)定位并減小PDR 定位過程中的累積誤差,Chen 等人利用傳感器數(shù)據(jù)識(shí)別轉(zhuǎn)向、門、樓梯等作為地標(biāo)[10],為重新啟動(dòng)PDR 算法提供更準(zhǔn)確的新起點(diǎn);為了減小計(jì)算成本,采用輕量級(jí)的Kalman 濾波器將PDR 定位與WiFi 定位結(jié)合起來建立模型,其平均定位精度達(dá)到了1m.在實(shí)際環(huán)境中,準(zhǔn)確的RSSI 位置測量模型和隨機(jī)噪聲信號(hào)的統(tǒng)計(jì)特性難以得到,使得Kalman 濾波器在實(shí)際應(yīng)用中存在局限性.Deng 等人將PDR 和WiFi 定位結(jié)果用擴(kuò)展Kalman 濾波器(EKF)結(jié)合起來[11],在WiFi 定位階段,采用核密度估計(jì)方法動(dòng)態(tài)地測定噪聲;在PDR 定位階段,采用另一個(gè)EKF 將陀螺儀與加速度計(jì)的數(shù)據(jù)結(jié)合起來測定行人的前進(jìn)方向.與單獨(dú)使用PDR 定位方法和WiFi 定位方法相比,大幅度提高了定位精度.在此基礎(chǔ)上,文獻(xiàn)[12]除了在定位階段融合了門、樓梯等地標(biāo)信息,用以重新校準(zhǔn)定位結(jié)果之外,在PDR 定位時(shí),也用EKF將陀螺儀、加速度計(jì)、磁力計(jì)和地標(biāo)的數(shù)據(jù)融合起來測定航向,并在WiFi 定位階段又提出了定位可信域來檢測RSSI 測量的異常值,以提高定位精度.結(jié)果表明,該方法90%的定位精度達(dá)到了1.35m.上述算法在離線階段均需進(jìn)行大量的人工測量工作,為了減少離線階段的工作量,如何利用用戶的移動(dòng)性實(shí)現(xiàn)無需人工勘測的室內(nèi)定位,成為研究的熱點(diǎn).在WILL 系統(tǒng)[13]中,測量人員攜帶手機(jī)在不同的房間穿梭走動(dòng),手機(jī)同時(shí)對(duì)信號(hào)指紋和運(yùn)動(dòng)數(shù)據(jù)進(jìn)行測量.指紋信息進(jìn)行聚類生成虛擬房間,分析運(yùn)動(dòng)數(shù)據(jù)可得出虛擬房間之間的可達(dá)性,從而形成邏輯平面圖.邏輯平面圖與建筑的物理平面圖進(jìn)行匹配,即可得到各個(gè)房間的指紋信息.該方法建立的指紋數(shù)據(jù)庫可以實(shí)現(xiàn)房間級(jí)別的定位精度.文獻(xiàn)[14]中提出了基于群智感知的室內(nèi)定位算法.該算法不需要用戶顯式地參與定位,采用NSAC(normalized auto-correlation-based step counting)和增強(qiáng)粒子濾波器實(shí)現(xiàn)了設(shè)備位置無關(guān)的運(yùn)動(dòng)估計(jì),即便設(shè)備位于口袋、背包,其運(yùn)動(dòng)方向與設(shè)備朝向不一致,依然可以進(jìn)行定位.

此外,盡管基于RSSI 指紋的室內(nèi)定位技術(shù)可以達(dá)到米級(jí)的定位精度,但在復(fù)雜場景中,由于多徑效應(yīng)等多因素的影響,其性能將會(huì)急劇下降.為實(shí)現(xiàn)魯棒性更好的定位,CSI(信道狀態(tài)信息)作為一種細(xì)粒度的信道評(píng)估指標(biāo)被應(yīng)用到室內(nèi)定位中,以減少多徑效應(yīng)帶來的干擾.CSI 攜帶更豐富的反應(yīng)信道狀態(tài)和特性的信息,能夠直接區(qū)分直接路徑和反射路徑.由于原始CSI 存在很多冗余信息,不能直接進(jìn)行特征提取,可以采用Hampel 濾波器[15]對(duì)原始信號(hào)進(jìn)行濾波,采用線性變換[16]消除隨機(jī)相位噪聲的影響以及同步誤差.文獻(xiàn)[17]采用CSI 作為指紋,建立CSI 值和距離關(guān)系的數(shù)學(xué)模型,在定位階段,尋找3 個(gè)距離最近的信號(hào)值,采用三角測量方法進(jìn)行目標(biāo)的確定.文獻(xiàn)[18]提出了基于CSI 的穿墻檢測方法,采用基于PCA 的濾波算法替代傳統(tǒng)的低通濾波來處理數(shù)據(jù),并利用不同子載波之間的相關(guān)變化,提出了以特征向量一階差分的均值作為特征值的方法.與文獻(xiàn)[16]強(qiáng)烈依賴于環(huán)境閾值的設(shè)定不同,此算法不需要預(yù)先標(biāo)定閾值.

雖然基于CSI 的室內(nèi)定位技術(shù)擁有更高的魯棒性,但是CSI 信息的獲取更復(fù)雜,需要專用的底層驅(qū)動(dòng),成本較高.因此,本文仍采用基于RSSI 的室內(nèi)定位算法.地標(biāo)信息的獲取會(huì)給測量等來更大的工作量,因此本文未使用地標(biāo)信息.與其他RSSI 指紋定位算法不同,本文致力于利用用戶的軌跡數(shù)據(jù)提高實(shí)時(shí)定位階段RSSI 指紋匹配的精度:首先,利用軌跡預(yù)估技術(shù),基于傳感器數(shù)據(jù)估計(jì)用戶的運(yùn)動(dòng)軌跡作為WiFi 定位的輔助信息,并計(jì)算預(yù)估軌跡的可信度;然后,將軌跡信息與RSSI 指紋信息按權(quán)重結(jié)合起來建立綜合概率模型進(jìn)行用戶位置匹配,確定最近參考點(diǎn).

2 軌跡預(yù)估

軌跡預(yù)估利用智能設(shè)備內(nèi)置的傳感器獲取數(shù)據(jù)計(jì)算行人運(yùn)動(dòng)軌跡,本節(jié)主要介紹預(yù)估用戶行動(dòng)方向和距離的方法,獲取用戶軌跡,并提出了預(yù)估軌跡可信度的計(jì)算方法.

2.1 基于陀螺儀、加速度計(jì)的軌跡預(yù)估方法

大量研究表明,用戶運(yùn)動(dòng)時(shí),從陀螺儀、加速度計(jì)獲得的數(shù)據(jù)具有一定的規(guī)律性,可以通過對(duì)其進(jìn)行處理與分析得到用戶的相對(duì)運(yùn)動(dòng)軌跡.對(duì)加速計(jì)測得的數(shù)據(jù)進(jìn)行二次積分就可以得到距離,但這種計(jì)算方法的誤差會(huì)隨著時(shí)間積累[19].由于在用戶行走時(shí),加速度計(jì)可以測得其身體呈現(xiàn)的周期性變化,如后文圖1 所示,因此本文通過統(tǒng)計(jì)加速度信號(hào)的波谷數(shù)來計(jì)算行走步數(shù),然后將步數(shù)與步幅相乘計(jì)算用戶行進(jìn)的距離.實(shí)驗(yàn)證明,步幅與設(shè)備垂直方向運(yùn)動(dòng)距離成正比關(guān)系[20],而設(shè)備垂直運(yùn)動(dòng)的距離可以通過加速度計(jì)體現(xiàn)出來.加速度計(jì)測得的總加速度〈ax,ay,az〉是由重力加速度〈gx,gy,gz〉跟用戶施加的力引起的加速度的總和,而設(shè)備垂直運(yùn)動(dòng)的距離與平行于重力的加速度分量變化成比例關(guān)系,因此采用總加速度在重力加速度方向上投影的標(biāo)準(zhǔn)差作為設(shè)備的垂直運(yùn)動(dòng)因子:

利用相同設(shè)備垂直運(yùn)動(dòng)因子下步頻與步幅的線性關(guān)系,即可求出步幅,其中,步頻可根據(jù)一段時(shí)間內(nèi)的步數(shù)求得[20].

由于陀螺儀的采樣頻率很高,且對(duì)角度變化可以進(jìn)行靈敏準(zhǔn)確的識(shí)別,因此本文利用陀螺儀進(jìn)行偏轉(zhuǎn)角度的估計(jì).基于陀螺儀獲取的角速度數(shù)據(jù),進(jìn)行對(duì)時(shí)間的一次積分可以得到偏轉(zhuǎn)角.根據(jù)文獻(xiàn)[21]的研究,其平均誤差為10.9°,在550m 的圓形軌道上測試,運(yùn)動(dòng)一周后,估計(jì)位置偏差為11.7%.A.Jimenez 等人在文獻(xiàn)[22]中將距離和方向變化結(jié)合起來進(jìn)行相對(duì)位置定位,研究結(jié)果表明,無論對(duì)于室內(nèi)環(huán)境還是室外環(huán)境,其大部分情況下?lián)碛休^高精度,誤差都小于5%.

2.2 預(yù)估軌跡可信度

根據(jù)傳感器數(shù)據(jù)預(yù)估軌跡受外界環(huán)境變化的影響較小,但容易造成漂移誤差積累,因此需要建立相應(yīng)的模型來評(píng)估誤差的大小,進(jìn)而評(píng)價(jià)預(yù)估軌跡的可信度.實(shí)驗(yàn)結(jié)果表明:運(yùn)動(dòng)速度越穩(wěn)定,預(yù)估軌跡就越接近真實(shí)軌跡,測量誤差也就越小;當(dāng)速度變化時(shí),尤其在起步或停止的階段,測量誤差較大.圖1 描述了在勻速、變速兩種運(yùn)動(dòng)狀態(tài)下各步行30 步的加速度計(jì)測量的數(shù)據(jù).可以看出,勻速運(yùn)動(dòng)時(shí)加速度變化較為規(guī)律,而變速運(yùn)動(dòng)時(shí)加速度的變化較為劇烈,規(guī)律性差.

Fig.1 Data obtained by accelerometers over different motion patterns圖1 不同運(yùn)動(dòng)模式下的加速度計(jì)獲取的數(shù)據(jù)

為了評(píng)價(jià)利用內(nèi)部傳感器測量用戶軌跡的可靠程度,提出了預(yù)估軌跡可信度的概念,記為φ,如公式(1)所示.

其中,μ表示用戶運(yùn)動(dòng)的平均速度,δ表示所有速度的均方差,代表速度的均勻程度.δ值越小,速度越均勻,可信度越高,預(yù)估軌跡越精確,其誤差越小.因此,誤差與可信度成反比關(guān)系.

為了研究誤差與可信度的關(guān)系,我們以不同路徑和速度從點(diǎn)A移動(dòng)到點(diǎn)B,記錄下兩點(diǎn)間的加速度計(jì)數(shù)據(jù),共進(jìn)行20 次實(shí)驗(yàn).圖2 顯示了3 條實(shí)驗(yàn)路徑,點(diǎn)A和B相距5m.為避免起步和停止時(shí)的速度變化對(duì)實(shí)驗(yàn)造成影響,我們在A點(diǎn)之前起步,在B點(diǎn)之后停止,中間經(jīng)過A,B兩點(diǎn).

根據(jù)傳感器數(shù)據(jù)計(jì)算得到的誤差和可信度倒數(shù)關(guān)系如圖3 所示,可以看出,誤差與可信度倒數(shù)大致符合線性關(guān)系.由此,我們可以假設(shè)在移動(dòng)一定距離時(shí),有:

其中,ε為誤差,φ為預(yù)估軌跡可信度,a,b的值與具體的軌跡計(jì)算算法和移動(dòng)距離相關(guān).

Fig.2 Experimental paths圖2 實(shí)驗(yàn)路徑

Fig.3 Relationship between error and confidential degree圖3 誤差與可信度關(guān)系

3 概率性位置確定

至此,我們已根據(jù)傳感器數(shù)據(jù)預(yù)估了用戶軌跡,并給出了預(yù)估軌跡可信度的計(jì)算方法.下面我們將利用這些數(shù)據(jù)對(duì)經(jīng)典的信號(hào)指紋定位方法進(jìn)行改進(jìn),基于概率模型來確定候選點(diǎn)的位置,提高指紋定位的精度.

3.1 概率模型

概率模型將預(yù)估軌跡概率跟信號(hào)指紋確定的位置概率按合理的權(quán)值進(jìn)行綜合計(jì)算,首先計(jì)算預(yù)估軌跡概率,再確定這兩部分的權(quán)值.

根據(jù)第2 節(jié)提出的軌跡預(yù)估方法可知:主要根據(jù)加速度計(jì)預(yù)估距離,根據(jù)陀螺儀預(yù)估方向,即距離與方向的數(shù)據(jù)分別來自不同的傳感器.因此,我們可以假定距離概率和方向概率是相互獨(dú)立的,故有軌跡概率,即

最后,我們假設(shè)用戶從已知位置O點(diǎn)出發(fā),到達(dá)目的地A點(diǎn).此時(shí)預(yù)估軌跡為,在A處測得的指紋為sA,RA是通過指紋匹配得到的一個(gè)候選參考點(diǎn),如圖5 所示.

Fig.4 Estimated trajectory圖4 預(yù)估軌跡

Fig.5 Probabilistic model圖5 概率模型

至此,我們就可以將軌跡概率和傳統(tǒng)的基于RSSI 的指紋定位概率相結(jié)合,得到最終的概率模型,如公式(6)所示.

其中,α表示軌跡概率對(duì)綜合概率的貢獻(xiàn),與預(yù)估軌跡的可信度φ定義相關(guān).為引入α與φ的數(shù)學(xué)關(guān)系,我們設(shè)信號(hào)指紋定位誤差為εfp,預(yù)估軌跡誤差為εdis,兩種定位模型的權(quán)重應(yīng)與誤差反相關(guān),即.目前,經(jīng)典的指紋定位平均誤差大都為1m 左右,不妨記為定值εfp=1;再根據(jù)預(yù)估軌跡誤差與可信度的關(guān)系,可得:

3.2 候選參考點(diǎn)概率性位置確定

至此僅建立了一段路徑的綜合概率模型,在實(shí)際在線位置確定時(shí),設(shè)備對(duì)WiFi 信號(hào)進(jìn)行n次測量,每次均會(huì)得到概率最高的k個(gè)候選參考點(diǎn),如圖6 所示.當(dāng)順序鏈接不同的候選參考點(diǎn)時(shí),得到多個(gè)候選路徑,如路徑path=[p1,p2,…,pn],其中,pi是第i次測量的候選點(diǎn),將其表示為向量的形式.對(duì)應(yīng)路徑中的路段,預(yù)估的軌跡為ai.

Fig.6 Path probability圖6 路徑概率

由于每次測量是相互獨(dú)立的,因此可以認(rèn)為路徑中各段之間相互獨(dú)立.根據(jù)前面綜合概率的討論,候選路徑path的概率為

其中,n表示定位的次數(shù),Ppf(p1/s1)是點(diǎn)p1的指紋匹配概率.為了統(tǒng)一表達(dá),我們對(duì)于沒有前趨節(jié)點(diǎn)的參考點(diǎn)p1指定一個(gè)虛擬前趨節(jié)點(diǎn)p0,并令相應(yīng)的參數(shù)α1=0,則有:

其中,PATH(R)為所有以R為終點(diǎn)的候選路徑的集合.如果直接計(jì)算,該公式的時(shí)間復(fù)雜度為O(kn-1)(k為候選點(diǎn)個(gè)數(shù),n為歷史測量次數(shù))并且存在大量重復(fù)計(jì)算.為了簡化計(jì)算,我們將保留之前計(jì)算的路徑概率,然后拼接最后一段路徑,假設(shè)Rn-1,i是第n-1 次測量的候選參考點(diǎn),Rn-1,i是第n次測量的一個(gè)參考點(diǎn),于是有:

因此,每一次測量時(shí)都要保存k個(gè)參考點(diǎn)的指紋概率和路徑概率,算法的空間復(fù)雜度為O(kn).其中,P(Rn-1,i)在第n-1 次測量時(shí)已經(jīng)計(jì)算過,因此,P(Rn,j)復(fù)雜度降為O(k).由于第n次測量一共有k個(gè)候選點(diǎn),所以最終的時(shí)間復(fù)雜度為O(k2).

3.3 實(shí)例分析

本節(jié)通過實(shí)例分析概率模型對(duì)定位精度的影響.連續(xù)兩次測量匹配得到的候選參考點(diǎn)如圖7 所示,其中,紅色叉號(hào)是單純根據(jù)指紋匹配得到的定位結(jié)果,如Opf;藍(lán)色叉號(hào)是綜合了軌跡信息得到的結(jié)果,如O.表1 和表2分別為第n次和第n+1 次測量各候選參考點(diǎn)的信息;兩次測量間預(yù)估軌跡αn+1=(4,1),其權(quán)重為αn+1=0.5.

Fig.7 Comprehensive probability model based positioning圖7 綜合模型定位

Table 1 Reference points in the nth measurement表1 第n 次測量參考點(diǎn)

Table 2 Reference points in the (n+1)th measurement表2 第n+1 次測量參考點(diǎn)

根據(jù)表1 和表2 計(jì)算得到的軌跡概率見表3,其中,第i行第j列表示向量的軌跡概率.

Table 3 Trajectory probabilities of reference points表3 參考點(diǎn)軌跡概率

根據(jù)之前的結(jié)論,Rn+1,j的概率計(jì)算公式為

其中,第1 項(xiàng)為指紋匹配概率的貢獻(xiàn),第2 項(xiàng)為軌跡概率的貢獻(xiàn).

從表3 中可以看出,每列中第1 行的數(shù)值都是最小值,即每列中的值最小.因此在和式中,Rn,1的貢獻(xiàn)是最小的.可見,在第n+1 次定位程中,我們通過軌跡概率對(duì)偏差點(diǎn)Rn,1的影響進(jìn)行了降低,同時(shí)對(duì)其他點(diǎn)進(jìn)行相應(yīng)提升,從而提高了定位精度.

分析圖7 可以看出,概率模型可以弱化環(huán)境變化對(duì)定位結(jié)果的負(fù)面影響.圖中第n次測量指紋定位與綜合模型定位的位置相差很大,這是因?yàn)橛捎诃h(huán)境變化,當(dāng)前定位出現(xiàn)了偏差較大的候選點(diǎn)Rn,1時(shí),若僅采用指紋匹配算法選擇匹配度較高的候選點(diǎn),會(huì)產(chǎn)生很大偏差,且會(huì)對(duì)后續(xù)定位產(chǎn)生誤差積累,對(duì)最終結(jié)果產(chǎn)生較大的影響.但通過軌跡信息,便將Rn,1對(duì)綜合定位的貢獻(xiàn)大幅度降低,使偏差點(diǎn)并不會(huì)對(duì)后續(xù)定位產(chǎn)生太大的影響.當(dāng)前測量各候選參考點(diǎn)都正常時(shí),由于后續(xù)定位中考慮到更多的參考點(diǎn)有利于均衡誤差,因此會(huì)對(duì)后續(xù)定位產(chǎn)生積極的影響,有利于提高定位的精度.

4 性能分析評(píng)價(jià)

本文在真實(shí)數(shù)據(jù)的基礎(chǔ)上對(duì)算法進(jìn)行實(shí)驗(yàn)分析,通過與其他定位算法進(jìn)行比較,分析傳感器信息對(duì)定位精度提高的貢獻(xiàn),并詳細(xì)分析了預(yù)估軌跡精度、候選參考點(diǎn)個(gè)數(shù)和路徑長度對(duì)算法精度的影響.

4.1 實(shí)驗(yàn)環(huán)境

進(jìn)行實(shí)驗(yàn)的樓層平面圖如圖8 所示.平面圖中,黃色的點(diǎn)為WiFi 接入點(diǎn),藍(lán)色的點(diǎn)表示參考點(diǎn),參考點(diǎn)之間的間隔是1.5m;紅色的點(diǎn)是實(shí)時(shí)測量階段隨機(jī)選取的測量點(diǎn),用來測試算法精度.在每個(gè)參考點(diǎn)和測量點(diǎn)都重復(fù)采樣110 次,采樣周期為250ms.

考慮到用戶軌跡,本文通過仿真算法隨機(jī)生成100 條用戶的運(yùn)動(dòng)路徑,具體算法如下:在平面圖中隨機(jī)選取一個(gè)測量點(diǎn)作為起始位置,然后在附近測量點(diǎn)中隨機(jī)選擇一個(gè)作為下一個(gè)點(diǎn);考慮到人的真實(shí)運(yùn)動(dòng)軌跡,會(huì)以較大的概率前進(jìn),較小的概率轉(zhuǎn)向和后退,且在較短的時(shí)間內(nèi)移動(dòng)距離一般不會(huì)超過10m,所以將10m 范圍內(nèi)所有測量點(diǎn)按偏轉(zhuǎn)角度排序,依次進(jìn)行判定,第1 個(gè)點(diǎn)被選中的概率為1/2,第2 個(gè)點(diǎn)的選中概率為1/3,依次類推,若直到最后一個(gè)點(diǎn)仍未選中,則直接選擇第1 個(gè)點(diǎn);若路徑長度超過50,則算法停止.為了充分利用所有測量點(diǎn)樣本,即要求每個(gè)測量點(diǎn)在路徑中出現(xiàn)的次數(shù)大致相同,我們按照測量點(diǎn)參與次數(shù)排序,再生成100 條路徑,共200 條隨機(jī)路徑進(jìn)行仿真實(shí)驗(yàn).圖8 顯示了其中一條路徑.在實(shí)驗(yàn)中,實(shí)驗(yàn)人員持智能手機(jī)沿該生成的路徑行走10 次,獲取傳感器數(shù)據(jù).

假定信號(hào)指紋定位精度為1m,預(yù)估位置誤差為ε,相應(yīng)的預(yù)估軌跡權(quán)重α的計(jì)算如公式(13)所示.

本文用定位坐標(biāo)與實(shí)際坐標(biāo)的歐幾里德距離作為定位精度的評(píng)價(jià)標(biāo)準(zhǔn),即

其中,(x,y)是位置計(jì)算結(jié)果,(x0,y0)是測量點(diǎn)實(shí)際位置.

Fig.8 Experimental environment圖8 實(shí)驗(yàn)環(huán)境

4.2 性能分析與測試

圖9 描述了RADAR、Horus、WiFi+INS[9]以及本文提出的多傳感器輔助定位方法的性能.

Fig.9 Cumulative distribution function of positioning error圖9 定位誤差累積分布函數(shù)

RADAR 系統(tǒng)定位精度最差,平均誤差達(dá)到2.57m;Horus 系統(tǒng)遠(yuǎn)遠(yuǎn)優(yōu)于RADAR,平均誤差為1.18m;WiFi+INS 方法平均誤差為1.1m;本文提出的多傳感器輔助定位的方法優(yōu)于其他3 種方法,平均誤差為0.97m.RADAR之所以最差,是因?yàn)槠渌褂玫腒NN 算法只是簡單地對(duì)候選參考點(diǎn)取均值,沒有考慮各參考點(diǎn)的權(quán)重.Horus 和本文算法在建立數(shù)據(jù)庫和指紋匹配時(shí)都是基于統(tǒng)計(jì)概率,因此更精確.相對(duì)于Horus 系統(tǒng),當(dāng)誤差大于1.5m 后,本文算法的優(yōu)勢極為明顯.這是因?yàn)檎`差越大,指紋匹配概率對(duì)綜合概率計(jì)算的貢獻(xiàn)就越低,而預(yù)估軌跡信息的貢獻(xiàn)提高,提高了定位的精度.這說明定位時(shí)使用軌跡信息,可以有效地提高整體定位精度,尤其是可以減小定位出現(xiàn)較大誤差的概率.粒子濾波器的時(shí)間復(fù)雜度為O(n2),直接受限于重采樣的復(fù)雜度[23],其中,n為粒子數(shù).本文算法的時(shí)間復(fù)雜度為O(k2),其中,k為選取的高匹配概率的項(xiàng)數(shù),即選取前k個(gè)高匹配概率.為了保證算法精確度,隨著參考點(diǎn)個(gè)數(shù)的增加,粒子數(shù)n隨之增加,而k相對(duì)較小且相對(duì)固定,所以粒子濾波器的時(shí)間復(fù)雜度遠(yuǎn)大于本文算法的時(shí)間復(fù)雜度.因此,即使誤差大于1.5m 時(shí),WiFi+INS 的方法與本文方法的累積誤差概率相當(dāng),但鑒于粒子濾波器計(jì)算量大、耗時(shí)長,并不適合于實(shí)時(shí)定位.

本文算法中使用預(yù)估軌跡輔助定位,因此其精度將直接影響到算法精度.圖10(a)通過改變路徑上各點(diǎn)間預(yù)估軌跡精度來對(duì)比分析其對(duì)算法的影響,利用預(yù)估軌跡生成算法隨機(jī)生成8 組預(yù)估軌跡和相應(yīng)的權(quán)重信息.從圖中可以看出,隨著軌跡精度的提升,定位精度也相應(yīng)得到提升.這是因?yàn)楦鶕?jù)公式(13),預(yù)估軌跡的誤差越小,其權(quán)重α越大,對(duì)綜合概率的貢獻(xiàn)越高,定位也越精確.當(dāng)平均預(yù)估軌跡誤差達(dá)到0.7m 時(shí),平均定位精度相應(yīng)達(dá)到了0.97m;但當(dāng)預(yù)估軌跡平均誤差小于0.5m 后,由于權(quán)值α的大小逐漸穩(wěn)定,預(yù)估軌跡信息對(duì)綜合概率的貢獻(xiàn)逐漸穩(wěn)定,其對(duì)定位精度的影響就不再明顯.

Fig.10 Factors having effects on positioning accuracy圖10 影響定位精度的因素

圖10(b)描述了不同候選參考點(diǎn)個(gè)數(shù)對(duì)算法的影響.可以看出,當(dāng)參考點(diǎn)個(gè)數(shù)n=1 時(shí),定位效果最差.因?yàn)橹皇褂闷ヅ涠茸畲蟮狞c(diǎn)作為定位結(jié)果很容易引入較大誤差,尤其是在環(huán)境變化較大時(shí),極可能出現(xiàn)偏差大的參考點(diǎn)匹配概率反而高的情況.隨著參考點(diǎn)個(gè)數(shù)的增加,定位精度逐漸提升,當(dāng)n>6 時(shí),精度反而有所下降,與文獻(xiàn)[2]的實(shí)驗(yàn)結(jié)果一致.這是因?yàn)殡S著參考點(diǎn)個(gè)數(shù)的不斷提升,偏差較大的參考點(diǎn)也被引入到綜合概率的計(jì)算中,反而對(duì)最終結(jié)果引入了較大的誤差,降低了定位精度.所以候選點(diǎn)個(gè)數(shù)不是越多越好,其值要根據(jù)實(shí)際環(huán)境以經(jīng)驗(yàn)方式來確定.

我們還以平均誤差作為評(píng)價(jià)標(biāo)準(zhǔn),分析路徑長度與定位精度的關(guān)系.對(duì)所有路徑中各參考點(diǎn)按序號(hào)進(jìn)行歸類,即將各路徑中的第i個(gè)參考點(diǎn)歸為一類,統(tǒng)計(jì)所有路徑的平均定位誤差.從圖10(c)中可以看出,起始點(diǎn)平均誤差較大,達(dá)到1.16m,與Horus 的定位精度比較接近.這種情況相當(dāng)于僅測量一次的結(jié)果,存在極大的偶然性,這是因?yàn)楫?dāng)路徑長度為1 時(shí),傳感器的預(yù)估軌跡信息對(duì)綜合模型的貢獻(xiàn)為0,結(jié)果僅由經(jīng)典的指紋匹配算法確定,只使用匹配度最大的點(diǎn)作為定位結(jié)果,很容易引入較大誤差,尤其是在環(huán)境變化較大時(shí).隨著路徑變長,預(yù)估軌跡信息以一定權(quán)重對(duì)綜合模型做出貢獻(xiàn),均衡定位的誤差,定位精度逐漸提升.當(dāng)路徑長度為8 時(shí),定位精度達(dá)到0.97m.之后,誤差值基本維持在這個(gè)精度.這說明,隨著測量次數(shù)的增加,環(huán)境變化對(duì)定位結(jié)果的影響已經(jīng)很低了,因此,綜合模型可以削弱環(huán)境變化帶來的不利影響.

5 總結(jié)

由于室內(nèi)環(huán)境復(fù)雜多變,而WiFi 信號(hào)的傳輸易受環(huán)境變化影響,因此僅使用指紋定位可能存在大的偏差.為了提高定位精度并減小環(huán)境因素帶來的不利影響,本文提出了智能手機(jī)內(nèi)置傳感器輔助WiFi 信號(hào)指紋定位的方法,即要利用智能設(shè)備上內(nèi)置的傳感器如加速計(jì)、陀螺儀等采集數(shù)據(jù),預(yù)估得到用戶軌跡信息,并提出預(yù)估軌跡可信度概念用以評(píng)估預(yù)估軌跡的精確程度;然后,將軌跡信息與信號(hào)指紋信息按權(quán)重結(jié)合起來建立綜合概率模型,進(jìn)行位置匹配,確定最近參考點(diǎn).實(shí)驗(yàn)結(jié)果表明,與經(jīng)典指紋匹配算法RADAR、Horus 以及WiFi+INS 的方法相比,我們的方法利用傳感器數(shù)據(jù)能夠有效地提高定位精度,且可以減弱環(huán)境變化對(duì)定位造成的不利影響.