基于稀疏表示和位置相關(guān)性的室內(nèi)定位算法*

周紅亮,周先存,陳孟元

(1.安徽工程大學(xué)安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室,安徽 蕪湖 241000;2.皖西學(xué)院網(wǎng)絡(luò)中心,安徽 六安 237012)

近年來(lái)隨著位置信息的服務(wù)越來(lái)越被人們所重視。[1]人們80%以上的時(shí)間在室內(nèi)環(huán)境中度過(guò),餐飲、購(gòu)物、娛樂、地鐵交通成為人們生活的重要生活方式。此外,在商業(yè)中通過(guò)定位技術(shù)與產(chǎn)品數(shù)據(jù)信息結(jié)合已經(jīng)成為傳統(tǒng)零售業(yè)整合線上線下進(jìn)行精準(zhǔn)營(yíng)銷的利器。復(fù)雜的多徑效應(yīng),室內(nèi)環(huán)境全球定位系統(tǒng)GPS(Global Position System)信號(hào)弱等原因使得GPS技術(shù)無(wú)法滿足室內(nèi)定位的需求。[2-3]隨著人們的研究深入,基于接收信號(hào)強(qiáng)度指數(shù)RSSI(Received Signal Strength Index)的WIFI定位技術(shù)因其具有不需要額外的硬件設(shè)備、易部署、能做到近乎純軟件實(shí)現(xiàn)等特點(diǎn),而被人們所普遍接受。

基于RSSI的室內(nèi)定位技術(shù)主要分為基于信道模型[4-5]和基于指紋定位[6-8]的兩類主流算法?；谛诺滥Ｐ偷氖覂?nèi)定位易于部署,但是由于復(fù)雜豐富的多徑效應(yīng),基于信道模型的無(wú)線定位精度常停留在房間尺度。由于室內(nèi)無(wú)線接入點(diǎn)部署密度日益增大,且基于指紋的無(wú)線定位不依賴信道模型,因此基于指紋的定位精度往往更高?；谖恢弥讣y架構(gòu)的方法一般分為兩個(gè)階段[9-10]:離線階段和在線階段。離線階段,采集定位區(qū)域內(nèi)各參考點(diǎn)RP(Reference Point)位置各個(gè)各無(wú)線接入節(jié)點(diǎn)AP(Access Point)的RSS信號(hào),利用無(wú)線信號(hào)在地理位置上的空間差異性,將空間在特定位置上的特定RSS信號(hào)特征作為該位置的指紋,建立位置-指紋數(shù)據(jù)庫(kù),在線階段,采集到待測(cè)點(diǎn)的在線位置指紋數(shù)據(jù),利用匹配算法與位置指紋數(shù)據(jù)庫(kù)中的位置信息相匹配,從而估計(jì)出待測(cè)用戶的位置。

為進(jìn)一步提高指紋的無(wú)線定位技術(shù)的易用性,研究人員從各方面降低基于指紋定位的部署負(fù)擔(dān),并提高其定位精度。文獻(xiàn)[11]中構(gòu)建了RADAR系統(tǒng),利用K-近鄰方法實(shí)現(xiàn)位置匹配,推斷用戶的位置,但是它容易受到動(dòng)態(tài)環(huán)境的影響,定位精度不高。文獻(xiàn)[12]中Youssef等人提出了Horus系統(tǒng),Horus改進(jìn)了采用確定性匹配策略的RADAR系統(tǒng),提出了基于統(tǒng)計(jì)的方法,將每一個(gè)位置上的無(wú)線指紋建模為一個(gè)高斯分布,并通過(guò)最大似然估計(jì)的方法來(lái)進(jìn)行指紋匹配。文獻(xiàn)[13]進(jìn)一步拓展了指紋的概念,將WiFi信號(hào)、聲音等作為混合指紋,是位置指紋具有語(yǔ)義信息,從而將定位的外延從物理位置拓展到邏輯位置。文獻(xiàn)[14]考慮到信道狀態(tài)信息可以更細(xì)粒度的刻畫多徑傳播信息的特性,將其代替接收信號(hào)強(qiáng)度作為參數(shù),利用物理層信息細(xì)粒度位置指紋,實(shí)現(xiàn)了米級(jí)的定位。文獻(xiàn)[15]針對(duì)位置指紋定位算法在室內(nèi)環(huán)境復(fù)雜時(shí)的定位性能,提出一種以位置指紋離散度作為權(quán)值參考的改進(jìn)加權(quán)K近鄰位置指紋定位算法,定位波動(dòng)降低。文獻(xiàn)[16]提出在線測(cè)量接收強(qiáng)度實(shí)時(shí)構(gòu)建包含環(huán)境的動(dòng)態(tài)性的指紋地圖,并利用截?cái)嗟钠娈愔捣纸饧夹g(shù)降低測(cè)量的誤差干擾,從而進(jìn)一步提高基于指紋的定位精度。

目前基于無(wú)線信號(hào)的室內(nèi)定位算法取得了一定的成果和進(jìn)步,但是RSS作為指紋仍然存在以下的問題:一是無(wú)線信號(hào)傳播過(guò)程中,環(huán)境對(duì)其造成的多徑、衰減等干擾使得RSS信號(hào)具有時(shí)變性,二是構(gòu)建離線數(shù)據(jù)庫(kù)勘測(cè)成本較大。因此,本文提出一種基于稀疏表示和位置相關(guān)性的指紋定位技術(shù),在離線階段利用壓縮感知的理論來(lái)構(gòu)建離線數(shù)據(jù)庫(kù),以降低離線采集的復(fù)雜度,在線定位階段利用向量相似性理論來(lái)提高定位的精度問題。實(shí)驗(yàn)結(jié)果表明,基于稀疏表示的室內(nèi)定位算法具有良好的定位性能,且相較與其他算法,在不同環(huán)境下具有更好的穩(wěn)定性,適用于室內(nèi)靜態(tài)定位。

1 基于稀疏表示的室內(nèi)定位算法

1.1 相關(guān)背景知識(shí)

1.1.1 壓縮感知理論

將文獻(xiàn)[17]提出的特征臉技術(shù)原理應(yīng)用到室內(nèi)指紋定位,我們利用提取的指紋特征數(shù)據(jù)來(lái)對(duì)指紋進(jìn)行分類。稀疏表示方法具有測(cè)量數(shù)據(jù)少、計(jì)算速度快、有效去除噪聲影響等優(yōu)點(diǎn),因此十分適用于室內(nèi)定位環(huán)境。我們利用稀疏表示的方法提取測(cè)量指紋數(shù)據(jù)特征,達(dá)到定位的目的。

特征信號(hào)可以由同一組Ψj表示出來(lái)。而噪聲信號(hào)由于其本身的隨機(jī)性無(wú)法被同一組Ψj表示出來(lái),因此不具有稀疏性。因此,稀疏表示在給信號(hào)指紋分類的同時(shí),又可以通過(guò)稀疏分解的過(guò)程有效降低噪聲對(duì)于定位精度的影響。

1.1.2 皮爾遜相關(guān)系數(shù)

皮爾遜相關(guān)系數(shù)(Pearson Correlation Coefficient)本質(zhì)上來(lái)說(shuō)是余弦相似性的加權(quán),它描述2個(gè)定距變量間聯(lián)系的相似程度,用于度量2個(gè)變量X和Y之間的相關(guān)(線性相關(guān)),其值介于-1與1之間,一般用r表示,計(jì)算公式為

式中:N為樣本量,X、Y分別為2個(gè)變量的觀測(cè)值。若rxy>0,表明變量是正相關(guān),變量Y的值隨變量X的值增大而增大;若rxy<0,表明變量是負(fù)相關(guān),即變量Y的值隨變量X的值增大而減小。rXY的絕對(duì)值越大表明相關(guān)性越強(qiáng)。

1.1.3 指紋稀疏性分析

指紋信號(hào)在時(shí)域上并非是稀疏的,為了驗(yàn)證指紋具有稀疏性,引入主成分分析驗(yàn)證指紋具有稀疏性PCA(Principal Component Analysis)來(lái)驗(yàn)證指紋具有稀疏性。將原信號(hào)進(jìn)行基的旋轉(zhuǎn)變換,旋轉(zhuǎn)變換后的重要基變量即為原信號(hào)的主要成分。主成分的方向越少,信號(hào)越稀疏。文獻(xiàn)[12]指出在變換維維度上僅有一個(gè)主成分貢獻(xiàn)率達(dá)0.9的主成分。所以指紋數(shù)據(jù)具有稀疏性。

據(jù)此將指紋矢量分為主指紋矢量和指紋變量?jī)刹糠?主指紋矢量是在該特定坐標(biāo)下多次采集指紋信號(hào)所共有的部分,是區(qū)別于別的參考點(diǎn)的主要特征,可以近似以常量表示;指紋變量是指紋矢量中除去主指紋矢量的部分,在各個(gè)方向上的能量分布很平均,可以表示為隨機(jī)變量。表達(dá)式如下:

式中:f表示在線指紋,fm表示主指紋矢量,v表示指紋變量。αi表示某一個(gè)位置的指紋矢量,也作為該位置特征字典的基,ki表示該組基下對(duì)應(yīng)的系數(shù)。

1.2 基于稀疏表示和位置相關(guān)性的室內(nèi)指紋定位算法

本文提出的算法共分為兩個(gè)階段:離線訓(xùn)練階段、在線定位階段。

1.2.1 離線訓(xùn)練階段

離線訓(xùn)練階段主要作用是建立離線指紋數(shù)據(jù)庫(kù)。包含參考點(diǎn)選擇、采集訓(xùn)練指紋、建立指紋數(shù)據(jù)庫(kù)3個(gè)部分。當(dāng)WIFI部署完畢后,我們?cè)谑覂?nèi)等距離的設(shè)置參考點(diǎn),共設(shè)置N個(gè)。樣本點(diǎn)的位置坐標(biāo)記為(xi,yi),天線個(gè)數(shù)為P個(gè)。所以測(cè)試點(diǎn)的指紋信息Fi=[Rss1,Rss2,…,Rssp],每個(gè)參考點(diǎn)共采集N條指紋A=[Fi1,Fi2,…,FiM],問題可以抽象為y=Ax。在信號(hào)可壓縮的前提下,求解欠定方程y=Ax的問題可以轉(zhuǎn)化為最小0-范數(shù)問題:

min‖Ψx‖0s.t.Ax=ΦΨx=y

本文采用分段正交匹配追蹤算法(StOMP)來(lái)重構(gòu)出稀疏字典,對(duì)于不同場(chǎng)景的室內(nèi)具有一般性求解的優(yōu)點(diǎn)。

輸入Fi1Fi2…FiM,S=10,ts=2.5,ε

輸出 稀疏字典D

Step 2 計(jì)算u=|〈rt-1,FiN〉|(1≤N≤M),將u中大于門限值的值對(duì)應(yīng)A的列序號(hào)j構(gòu)成集合J0;

Step 3 令Λt=Λt-1∪J0,At=At-1∪aj(for allj∈J0)。若Λt=Λt-1(即無(wú)新列被選中),則停止迭代進(jìn)入Step7;

Step 6t=t+1.如果t≤S,則返回Step 2迭代或ri=0則停止迭代進(jìn)入Step 7;

其中,r0表示指紋的均值,Fij表示在參考點(diǎn)i第j次測(cè)量的指紋數(shù)據(jù),Λt表示第t次的索引集,At表示按第t次索引找出的列集合,u表示rt-1和FiN的內(nèi)積。

1.2.2 在線定位階段

式中:X表示待測(cè)點(diǎn)的定位結(jié)果橫坐標(biāo)值,Y表示待測(cè)點(diǎn)的定位結(jié)果縱坐標(biāo)值,N表示選擇的參考點(diǎn)的個(gè)數(shù),ρ表示按皮爾遜相關(guān)系數(shù)測(cè)得的參考點(diǎn)選擇權(quán)重,xi表示按權(quán)重大小選取的前N個(gè)參考點(diǎn)的第i個(gè)橫坐標(biāo)值,yi表示按權(quán)重大小選取的前N個(gè)參考點(diǎn)的第i個(gè)縱坐標(biāo)值。

2 實(shí)驗(yàn)環(huán)境及實(shí)驗(yàn)結(jié)果

2.1 實(shí)驗(yàn)設(shè)計(jì)

室內(nèi)定位實(shí)驗(yàn)場(chǎng)地選在皖西學(xué)院信息工程學(xué)院辦公樓5樓,共布置有17個(gè)AP,使用的都是普通型號(hào)的路由器DIR-629。仿真模擬出兩種不同多徑影響的環(huán)境,實(shí)驗(yàn)場(chǎng)景如圖1所示。

圖1中,場(chǎng)景1為6.5 m×8 m的辦公室環(huán)境,共設(shè)置38個(gè)參考點(diǎn),布置3個(gè)AP;場(chǎng)景2為8 m×11 m 的實(shí)驗(yàn)室環(huán)境,共設(shè)置42個(gè)參考點(diǎn),布置3個(gè)AP;每個(gè)實(shí)驗(yàn)的每個(gè)參考點(diǎn)采集80條指紋信息用于訓(xùn)練指紋。

所有AP及參考點(diǎn)位置均在圖中標(biāo)注出來(lái)。仿真實(shí)驗(yàn)數(shù)據(jù)使用MEIZU Pro6s手機(jī)進(jìn)行訓(xùn)練和測(cè)試。其定位結(jié)果如圖2所示。在相同的條件下,我們將算法與貝葉斯定位算法、KNN算法進(jìn)行比較,實(shí)驗(yàn)結(jié)果及分析詳見3.2節(jié)。

圖1 場(chǎng)景仿真

圖2 定位結(jié)果

2.2 實(shí)驗(yàn)結(jié)果分析

定位算法的定位結(jié)果對(duì)比,對(duì)于情景1和情景2,我們分別在MATLAB中用RADAR系統(tǒng)(2000),HORUS系統(tǒng)(2004),CENTUAR系統(tǒng)(2012),WKNN算法(加權(quán)K-近鄰算法)4種定位方法作為對(duì)比來(lái)檢驗(yàn)算法的定位準(zhǔn)確性,圖3為從誤差累計(jì)概率密度函數(shù)角度得出的誤差累積分布圖(CDF),橫軸為距離,縱軸為距離對(duì)應(yīng)的誤差累積分布概率,曲線代表誤差達(dá)到橫坐標(biāo)值時(shí)對(duì)應(yīng)的概率值,圖4為幾種算法在誤差為30%,50%,80%所對(duì)應(yīng)的定位精度,橫軸為圖4中定位誤差概率在30%、50%、80% 3種情況,縱軸為對(duì)應(yīng)的誤差距離。直觀上顯示出幾種算法的精確性。

圖3 定位結(jié)果累積誤差分布圖

圖4 定位誤差直方圖

經(jīng)過(guò)多次重復(fù)仿真實(shí)驗(yàn),我們得出如下結(jié)論(以WKNN算法、Horus系統(tǒng)為代表作對(duì)比):場(chǎng)景1情況下,多徑影響較小,本文提出的算法平均誤差為1.052 6 m,相較于WKNN、Horus提升了9.8%,36.4%,場(chǎng)景2情況下,多徑影響較大,本文提出的算法平均誤差為1.411 7 m,相較于WKNN、Horus提升了20.0%,36.8%。

外在誤差來(lái)源于測(cè)量信道的物理因素,例如存在障礙物、多徑和陰影效應(yīng),以及環(huán)境變化導(dǎo)致的信號(hào)傳播速度變化等。指紋定位算法的定位精度呈現(xiàn)出不同,主要的原因是由于無(wú)線信號(hào)強(qiáng)度容易受到環(huán)境因素所干擾,當(dāng)處于多徑效應(yīng)強(qiáng)的環(huán)境下,定位精度有所降低。同時(shí),本文提出的算法能夠有效的降低噪聲對(duì)于實(shí)驗(yàn)結(jié)果的影響,故本文提出的算法能夠有效提高定位精度。

基于稀疏表示和位置相關(guān)性的室內(nèi)定位算法相比于幾種對(duì)比算法,有著更好的定位精度及抗噪性,包括以下兩種原因:(1)RADAR系統(tǒng)采用的算法為K-近鄰(KNN)算法,每個(gè)參考點(diǎn)僅保存有一個(gè)平均指紋,也就是保存了該位置上的主指紋矢量,在實(shí)際定位的時(shí)候,在線定位時(shí)沒有消除指紋變量對(duì)定位結(jié)果的影響。Horus及Centaur系統(tǒng)運(yùn)用的算法基于概率性的算法,在一些位置區(qū)分性明顯的點(diǎn),算法的定位性能表現(xiàn)較好,但是當(dāng)位置之間的區(qū)分度較低或者多徑影響較重的定位點(diǎn),概率性算法的定位效果下降明顯,穩(wěn)定性較差。WKNN算法是加權(quán)的KNN算法,分類結(jié)果依賴權(quán)重值,需要通過(guò)多次調(diào)整權(quán)重值來(lái)達(dá)到更好的分類效果。而本文的算法在每個(gè)參考點(diǎn)雖然也僅保存了平均指紋,但是在構(gòu)建數(shù)據(jù)庫(kù)過(guò)程中,卻應(yīng)用了多個(gè)指紋信息,相當(dāng)于是一個(gè)指紋集合。(2)稀疏表示分類算法在構(gòu)建離線數(shù)據(jù)庫(kù)的過(guò)程中,將主指紋矢量和指紋變量區(qū)分開來(lái),削弱了由環(huán)境因素干擾引起的指紋變量對(duì)定位結(jié)果的影響,而反應(yīng)定位點(diǎn)位置特征的主指紋矢量成為影響定位結(jié)果的主要因素。因此,定位精度得到了提高。

3 結(jié)論

本文系統(tǒng)地研究了基于稀疏表示和相似性檢測(cè)的室內(nèi)精準(zhǔn)定位問題,離線階段采集訓(xùn)練指紋,利用分段正交匹配算法建立了環(huán)境的稀疏字典,提高了分類的抗噪性,在線階段利用皮爾遜相關(guān)性檢測(cè)原理來(lái)匹配實(shí)時(shí)指紋,實(shí)現(xiàn)在線精準(zhǔn)定位,通過(guò)實(shí)驗(yàn)得出,定位精度得到了較好的提高。與此同時(shí),雖然此文的算法在室內(nèi)定位精度等方面有提升,但是本算法是在先驗(yàn)知識(shí)及基礎(chǔ)架構(gòu)下支撐的,當(dāng)環(huán)境因素發(fā)生變化時(shí),指紋的時(shí)效性問題就會(huì)凸顯出來(lái),所以本算法在位置指紋數(shù)據(jù)庫(kù)的建立和維護(hù)方面還有待改進(jìn)。

[1] Xiong J,Jamieson K. Array Track:A Fine-Grained Indoor Location System[C]//Usenix Conference on Networked Systems Design and Implementation. USENIX Association,2013:71-84.

[2] 洪雁. 基于稀疏表示的室內(nèi)定位算法研究[D]. 中國(guó)科學(xué)技術(shù)大學(xué),2013.

[3] 鄧中亮,余彥培,袁協(xié),等. 室內(nèi)定位現(xiàn)狀與發(fā)展趨勢(shì)研究[J]. 中國(guó)通信(英文版),2013,10(3):50-63.

[4] 王千,金光,鈕俊. 一種基于RSSI的混合定位算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(12):1823-1829.

[5] 石欣,印愛民,陳曦. 基于RSSI的多維標(biāo)度室內(nèi)定位算法[J]. 儀器儀表學(xué)報(bào),2014,35(2):261-268.

[6] 崔琪楣,鄧金剛,張雪菲. 基于壓縮感知的室內(nèi)場(chǎng)景無(wú)線定位算法(英文)[J]. China Communications,2012(4):1-12.

[7] Sen S,Choudhury R R,Nelakuditi S. SpinLoc:Spin Once to Know Your Location[C]//Twelfth Workshop on Mobile Computing Systems and Applications. ACM,2012:12.

[8] 李麗娜,馬俊,龍躍,等. 基于LANDMARC與壓縮感知的雙段式室內(nèi)定位算法[J]. 電子與信息學(xué)報(bào),2016,38(7):1631-1637.

[9] Wang H,Sen S,Mariakakis A,et al. Video:Unsupervised Indoor Localization(UnLoc):Beyond the Prototype[C]//International Conference on Mobile Systems,Applications,and Services. ACM,2014:393-393.

[10] Wu C,Yang Z,Liu Y,et al. WILL:Wireless Indoor Localization without Site Survey[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(4):839-848.

[11] Bahl P,Padmanabhan V N. RADAR:An In-Building RF-based User Location and Tracking System[C]//INFOCOM 2000. Nineteenth Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE Xplore,2000:775-784 vol.2.

[12] Youssef M,Agrawala A. Handling Samples Correlation in the Horus System[J]. Proceedings-IEEE INFOCOM,2003,2:1023-1031.

[13] Azizyan M,Constandache I,Choudhury R R. SurroundSense:Mobile Phone Localization Via Ambience Fingerprinting[C]//International Conference on Mobile Computing and Networking,MOBICOM 2009,Beijing,China,September. DBLP,2009:261-272.

[14] Sen S,Choudhury R R,Minka T. You are Facing the Mona Lisa:Spot Localization Using PHY Layer Information[C]//International Conference on Mobile Systems,Applications,and Services. ACM,2012:183-196.

[15] 田洪亮,錢志鴻,梁瀟,等. 離散度WKNN位置指紋Wi-Fi定位算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào),2017(5):94-99.

[16] Lim H,Kung L C,Hou J C,et al. Zero-Configuration,Robust Indoor Localization:Theory and Experimentation[C]//INFOCOM 2006. IEEE International Conference on Computer Communications. Proceedings. IEEE,2007:1-12.

[17] Wright J,Yang A Y,Ganesh A,et al. Robust Face Recognition Via Sparse Representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2):210-227.