基于分步的位置指紋定位算法研究

楊勇明

(上海理工大學(xué) 公共實(shí)驗(yàn)中心，上海 200093)

當(dāng)今，高層建筑越來(lái)越多，在這些人口密集的場(chǎng)所，由于受到障礙物的阻擋，GPS信號(hào)強(qiáng)度大大減弱，其定位精度遠(yuǎn)不及室外；而缺少室內(nèi)地圖，也導(dǎo)致了城市 “盲區(qū)”的出現(xiàn)。在人口密集的場(chǎng)所，諸如兒童看護(hù)、應(yīng)急救援、商場(chǎng)導(dǎo)購(gòu)等領(lǐng)域，對(duì)基于定位的服務(wù)[1](Location Based Services，LBS)需求量越來(lái)越大。此外，物聯(lián)網(wǎng)與智慧城市[2]概念的提出推動(dòng)了室內(nèi)定位技術(shù)及其應(yīng)用市場(chǎng)的迅速發(fā)展。射頻識(shí)別技術(shù)(Radio Frequency Identification，RFID)以非視距、非接觸、多目標(biāo)讀寫(xiě)、可重復(fù)使用等優(yōu)點(diǎn)[3]成為目前室內(nèi)定位的首選技術(shù)。

常用的室內(nèi)定位算法主要包括基于測(cè)距的三邊定位算法和基于非測(cè)距的位置指紋定位算法。由于受環(huán)境因素影響較小[4]，位置指紋定位算法成為諸多學(xué)者研究的焦點(diǎn)。LANDMARC定位算法由文獻(xiàn)[5]提出，是基于非測(cè)距的經(jīng)典算法。

1 傳統(tǒng)LANDMARC定位算法

1.1 LANDMARC定位算法

LANDMARC定位算法原理圖[6]如圖1所示，假設(shè)定位系統(tǒng)中有m個(gè)閱讀器、n個(gè)參考點(diǎn)標(biāo)簽、p個(gè)未知點(diǎn)：第一步，令θr,j表示第r個(gè)參考點(diǎn)標(biāo)簽在第j個(gè)閱讀器上測(cè)得的信號(hào)強(qiáng)度值，其中r=1,2,3,4,…,n,j=1,2,3,4,…,m；第二步，令si,j表示第i個(gè)未知點(diǎn)在第j個(gè)閱讀器上測(cè)得的信號(hào)強(qiáng)度值，其中i=1,2,3,4,…,p；第三步，對(duì)未知點(diǎn)測(cè)得的信號(hào)強(qiáng)度與數(shù)據(jù)庫(kù)中對(duì)應(yīng)參考點(diǎn)標(biāo)簽的RSSI((Received Signal Strength Indicator))值進(jìn)行關(guān)聯(lián)程度計(jì)算，即進(jìn)行si,j和θr,j相似度計(jì)算，以式(1)所示的信號(hào)強(qiáng)度均方差表示

(1)

圖1 LANDMARC算法原理圖

Ei,r表示歐幾里得距離[7]，根據(jù)式(1)，當(dāng)未知點(diǎn)RSSI值與數(shù)據(jù)庫(kù)中對(duì)應(yīng)參考點(diǎn)標(biāo)簽的RSSI值接近時(shí)，表示未知點(diǎn)與參考標(biāo)簽的位置十分接近。由于數(shù)據(jù)庫(kù)中有n個(gè)參考點(diǎn)標(biāo)簽，故將未知點(diǎn)與參考點(diǎn)標(biāo)簽一一進(jìn)行相似度計(jì)算，并按照歐式距離的大小進(jìn)行排序。為減小定位誤差，通常選取距離最相近的k個(gè)參考點(diǎn)標(biāo)簽進(jìn)行計(jì)算[8]，如式(2)所示，每個(gè)參考點(diǎn)標(biāo)簽坐標(biāo)都要添加權(quán)值，權(quán)值的取值和歐式距離的大小有關(guān)。當(dāng)未知點(diǎn)離參考點(diǎn)標(biāo)簽的實(shí)際位置較近時(shí)，權(quán)值較大；未知點(diǎn)與參考點(diǎn)距離較遠(yuǎn)時(shí)權(quán)值較小。

(2)

結(jié)合已知參考點(diǎn)標(biāo)簽的坐標(biāo)，根據(jù)公式(3)進(jìn)行未知坐標(biāo)計(jì)算

(3)

式中(x,y)表示未知點(diǎn)的坐標(biāo)，(xi,yi)表示已知參考點(diǎn)標(biāo)簽的位置坐標(biāo)。

1.2 LANDMARC定位算法冗余性分析

LANDMARC定位算法中，選定的k個(gè)參考點(diǎn)標(biāo)簽坐標(biāo)決定了LANDMARC得定位精度。其余參考點(diǎn)坐標(biāo)也參與定位過(guò)程，不僅增加系統(tǒng)的復(fù)雜度，也增加了錯(cuò)誤的產(chǎn)生率，進(jìn)而產(chǎn)生數(shù)據(jù)冗余現(xiàn)象[9]，導(dǎo)致系統(tǒng)效率和實(shí)時(shí)性下降，影響用戶(hù)體驗(yàn)。針對(duì)此問(wèn)題，本文提出基于分步的位置指紋定位算法。在離線(xiàn)訓(xùn)練階段，進(jìn)行粗粒度的定位(粗略定位)，確定未知點(diǎn)所在的區(qū)域，排除不可能的區(qū)域點(diǎn)；在在線(xiàn)定位階段，進(jìn)行細(xì)粒度的定位(精確定位)。

2 基于分步的位置指紋定位算法

使用基于分步的位置指紋定位算法進(jìn)行距離估算時(shí)，不依賴(lài)精確的室內(nèi)傳播模型，可以減小環(huán)境因素對(duì)定位精度的影響；此外使用粗粒度與細(xì)粒度的概念，有利于實(shí)現(xiàn)粗定位和精定位。基于分步的位置指紋定位算法流程圖如圖2所示。

圖2 位置指紋算法流程圖

2.1 離線(xiàn)訓(xùn)練階段

環(huán)境分析[11]是基于分步的位置指紋定位算法的第一步，也是關(guān)鍵一步。良好的環(huán)境分析有助于定位區(qū)域的合理規(guī)劃、參考節(jié)點(diǎn)位置和數(shù)量的確定，能夠減少閱讀器和標(biāo)簽的使用數(shù)量、節(jié)省系統(tǒng)成本，還可以減少部分?jǐn)?shù)據(jù)的計(jì)算量。

參考點(diǎn)包括粗粒度參考點(diǎn)和細(xì)粒度參考點(diǎn)。粗粒度點(diǎn)主要負(fù)責(zé)大致確定未知點(diǎn)所在的區(qū)域，描述待定位區(qū)域的大致輪廓。粗粒度點(diǎn)設(shè)置合理可快速的確定未知點(diǎn)所在的區(qū)域，避開(kāi)一些不必要參考點(diǎn)的計(jì)算。通常將粗粒度點(diǎn)設(shè)置在幾何圖形的中心位置，如正方形或者三角形的中心。粗粒度點(diǎn)確定后就需要確定細(xì)粒度點(diǎn)位置，細(xì)粒度點(diǎn)數(shù)量較多，通常圍繞著粗粒度點(diǎn)呈放射狀或者矩形狀?；诜植降奈恢弥讣y定位算法原理圖如圖3所示。

圖3 基于分步的位置指紋算法原理圖

建立位置-信號(hào)強(qiáng)度指紋庫(kù)[12]，在各個(gè)參考點(diǎn)處測(cè)得每一個(gè)標(biāo)簽的信號(hào)強(qiáng)度值，建立位置-信號(hào)強(qiáng)度指紋數(shù)據(jù)庫(kù)。各個(gè)參考點(diǎn)接收到的信息按照標(biāo)簽1、標(biāo)簽2、標(biāo)簽3、…、標(biāo)簽n的規(guī)律建立數(shù)據(jù)庫(kù)，例如共有m個(gè)參考點(diǎn)，n個(gè)標(biāo)簽，參考點(diǎn)的坐標(biāo)為(xi,yi)，第i個(gè)參考點(diǎn)處接收到第t個(gè)標(biāo)簽的信號(hào)強(qiáng)度表示為RSSi,t,則任意一個(gè)參考點(diǎn)在指紋庫(kù)中表示為(xi,yi,RSSi,1,RSSi,2,RSSi,3……RSSi,n)。

2.2 在線(xiàn)定位階段

分步定位主要應(yīng)用于在線(xiàn)定位階段，在未知點(diǎn)處實(shí)時(shí)測(cè)得各個(gè)標(biāo)簽信號(hào)強(qiáng)度值，進(jìn)行多次測(cè)量求取平均值，完成第一步粗定位。在縮小未知點(diǎn)所在區(qū)域時(shí)，將求得的平均值與粗粒度點(diǎn)進(jìn)行矢量匹配性分析，計(jì)算出未知點(diǎn)與粗粒度點(diǎn)之間的相似度。如圖3所示，將待定位區(qū)域劃分為A、B、C、D、E、F、G、H、I9個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)粗粒度點(diǎn)，用紅色五角星表示。計(jì)算完歐氏距離后，選取歐式距離最小的粗粒度點(diǎn)所包含的區(qū)域作為定位區(qū)域的粗定位區(qū)間，與圖3中9個(gè)參考粗粒度點(diǎn)進(jìn)行對(duì)比后確定未知點(diǎn)所在的區(qū)域?yàn)镋，則下一步在區(qū)域E進(jìn)行精確定位。

如圖4所示，精確定位時(shí)，舍棄與定位結(jié)果無(wú)關(guān)的A、B、C、D、F、G、H、I區(qū)域內(nèi)的參考點(diǎn)，只將未知點(diǎn)的信號(hào)強(qiáng)度與定位區(qū)域E內(nèi)4個(gè)細(xì)粒度參考點(diǎn)進(jìn)行相似度匹配即可：首先根據(jù)粗粒度點(diǎn)確定細(xì)粒度點(diǎn)，并將其利用到第二步精確定位；然后通過(guò)與參考細(xì)粒度點(diǎn)運(yùn)用加權(quán)K近鄰算法進(jìn)行未知點(diǎn)坐標(biāo)值計(jì)算。該算法大大減少計(jì)算量，提高了定位效率。

圖4 細(xì)定位原理圖

3 實(shí)例驗(yàn)證

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

實(shí)驗(yàn)環(huán)境選擇上海理工大學(xué)機(jī)械創(chuàng)新實(shí)驗(yàn)樓的一樓大廳，測(cè)試范圍為長(zhǎng)3.6 m，寬3.6 m的區(qū)域，實(shí)驗(yàn)儀器選擇2.4 GHz遠(yuǎn)距離RFID閱讀器和有源RFID電子標(biāo)簽。基于RFID的應(yīng)用主要分為標(biāo)簽的移動(dòng)和閱讀器的移動(dòng)[13]，本次實(shí)驗(yàn)選擇閱讀器移動(dòng)，該方法的優(yōu)勢(shì)是數(shù)量較多、價(jià)格較便宜的標(biāo)簽被放置在已知位置點(diǎn)，僅需使用一個(gè)閱讀器即可完成，費(fèi)用較低。實(shí)驗(yàn)開(kāi)始前，檢查筆記本與閱讀器之間的通信連接狀況，檢查所有的有源標(biāo)簽的紐扣電子是否電量充足，定義實(shí)驗(yàn)中閱讀器的位置代表未知點(diǎn)的位置。

圖5 實(shí)際實(shí)驗(yàn)測(cè)試圖

圖5為實(shí)際實(shí)驗(yàn)的測(cè)試圖，圖6為實(shí)驗(yàn)布置圖。圖6中按照如圖所示的方式選定坐標(biāo)原點(diǎn)，建立坐標(biāo)系，布置好標(biāo)簽，圖中每個(gè)小正方形的邊長(zhǎng)為0.6 m，實(shí)驗(yàn)選擇的有源標(biāo)簽數(shù)量共計(jì)4個(gè)，用五角星表示。離線(xiàn)訓(xùn)練階段，需要建立的數(shù)據(jù)點(diǎn)用圓表示，并進(jìn)行阿拉伯?dāng)?shù)字編號(hào)，有源標(biāo)簽點(diǎn)處需要進(jìn)行數(shù)據(jù)點(diǎn)的測(cè)量，用于粗粒度點(diǎn)數(shù)據(jù)庫(kù)的建立。

圖6中，1～4為有源標(biāo)簽的位置，放置在地板磚的中心位置，并且標(biāo)簽要豎直放置以便閱讀器的天線(xiàn)與標(biāo)簽處于同一高度，保證閱讀器更有效的接收標(biāo)簽信號(hào)強(qiáng)度。閱讀器的位置代表未知點(diǎn)位置，當(dāng)閱讀器在1～4有源標(biāo)簽位置時(shí)，測(cè)得各個(gè)標(biāo)簽的信號(hào)強(qiáng)度。該條件下建立的數(shù)據(jù)庫(kù)點(diǎn)為粗粒度點(diǎn)，而粗粒度點(diǎn)也是部分細(xì)粒度點(diǎn)的中心。21～24為未知點(diǎn)，1～20為訓(xùn)練階段建立位置信號(hào)強(qiáng)度數(shù)據(jù)庫(kù)時(shí)所需要測(cè)量的數(shù)據(jù)點(diǎn)。在此過(guò)程中有源標(biāo)簽的擺放位置要精確，有源標(biāo)簽的方向也要保持一致。閱讀器在每個(gè)位置測(cè)量有源標(biāo)簽的信號(hào)強(qiáng)度時(shí)，若天線(xiàn)朝向始終保持一致，則可有效減小其它因素對(duì)實(shí)驗(yàn)結(jié)果的影響。

圖6 無(wú)障礙物實(shí)驗(yàn)布置圖

3.2 實(shí)驗(yàn)步驟

(1)離線(xiàn)訓(xùn)練階段。確定坐標(biāo)原點(diǎn)后，依次把閱讀器放在1～20號(hào)數(shù)據(jù)點(diǎn)處，閱讀器的中心放置在地板磚的中心位置，在各點(diǎn)處閱讀器的天線(xiàn)朝向保持一致。由于受其它環(huán)境因素的影響[14-15]，信號(hào)強(qiáng)度并不穩(wěn)定，為了克服信號(hào)強(qiáng)度不穩(wěn)定對(duì)定位的影響，減小實(shí)驗(yàn)誤差，通常在每個(gè)參考點(diǎn)多次測(cè)量取平均值，每個(gè)數(shù)據(jù)點(diǎn)測(cè)量100次。獲得數(shù)據(jù)后，首先建立粗粒度數(shù)據(jù)庫(kù)，然后根據(jù)各點(diǎn)的歸屬，在粗粒度點(diǎn)下建立細(xì)粒度數(shù)據(jù)庫(kù)，數(shù)據(jù)點(diǎn)存儲(chǔ)格式為(xi,yi,RSSI1,RSSI2,RSSI3,RSSI4)，RSSIi表示接收到的第i個(gè)標(biāo)簽的信號(hào)強(qiáng)度值，例如標(biāo)號(hào)為5的位置點(diǎn)存儲(chǔ)格式為 (0.3,0.3,-65,-71,-60,-69)。

(2)在線(xiàn)定位階段。閱讀器的位置代表未知點(diǎn)的位置，在未知點(diǎn)處依次讀取到標(biāo)簽1、標(biāo)簽2、標(biāo)簽3、標(biāo)簽4的信號(hào)強(qiáng)度，接下來(lái)進(jìn)行算法的實(shí)現(xiàn)和對(duì)比分析。基于分步的位置指紋定位算法測(cè)得未知點(diǎn)處的各個(gè)標(biāo)簽信號(hào)強(qiáng)度之后，先和粗粒度點(diǎn)1、2、3、4進(jìn)行匹配性分析。LANDMARC定位算法僅需要與第(1)階段建立的所有指紋點(diǎn)即1～20進(jìn)行匹配性分析?；诜植降奈恢弥讣y定位算法和LANDMARC定位算法選用加權(quán)K近鄰算法，K取值為4。采用圖7所示的基于分步的位置指紋定位GUI界面，完成分步的位置指紋定位算法和LANDMARC定位算法效率的對(duì)比與分析，其中根據(jù)定位所需的時(shí)間長(zhǎng)短對(duì)效率對(duì)比進(jìn)行評(píng)價(jià)[16]。

圖7 基于分步的位置指紋定位GUI界面

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

表1是離線(xiàn)訓(xùn)練階段建立的數(shù)據(jù)庫(kù)，其中1、2、3、4號(hào)位置點(diǎn)為粗粒度中心，每個(gè)粗粒度中心包括多個(gè)細(xì)粒度的數(shù)據(jù)點(diǎn)，例如1號(hào)粗粒度中心包括5、6、9、10共4個(gè)細(xì)粒度數(shù)據(jù)點(diǎn)。同理，由實(shí)驗(yàn)布置圖可知其余的粗粒度中心及其包括的細(xì)粒度點(diǎn)。

表1 訓(xùn)練階段建立的數(shù)據(jù)庫(kù)

實(shí)驗(yàn)中閱讀器的位置代表未知點(diǎn)的位置，依次將閱讀器放在實(shí)驗(yàn)布置圖中的21、22、23、24位置，多次測(cè)量求出其平均值。表2匯總了實(shí)驗(yàn)測(cè)得的未知點(diǎn)各個(gè)標(biāo)簽的信號(hào)強(qiáng)度值。

表2 未知點(diǎn)處各標(biāo)簽的信號(hào)強(qiáng)度

基于分步的位置指紋定位算法通過(guò)計(jì)算歐式距離，確定最小距離所在的點(diǎn)為粗粒度點(diǎn)，LANDMARC定位算法中計(jì)算出所有的歐式距離，選取最小的4個(gè)點(diǎn)來(lái)參與未知點(diǎn)位置的計(jì)算。表3為基于分步的位置指紋算法和LANDMARC定位算法所確定的參考點(diǎn)情況。

表3 未知點(diǎn)處所確定的參考點(diǎn)

采用式(4)來(lái)計(jì)算定位誤差[17]

(4)

式中，(x,y)為實(shí)驗(yàn)測(cè)得未知點(diǎn)坐標(biāo)，(x1,y1)為未知點(diǎn)實(shí)際坐標(biāo)。

表4為基于分步的位置指紋定位算法與LANDMARC定位算法的定位結(jié)果對(duì)比，包括定位所需的時(shí)間及其定位精度。

表4 實(shí)驗(yàn)定位結(jié)果

根據(jù)表4可知，基于分步的位置指紋定位算法在保證定位精度與LANDMARC定位算法的定位精度相當(dāng)?shù)幕A(chǔ)上，提高了定位效率。這是由于先粗略定位后精確定位的思想減小了較大一部分的數(shù)據(jù)計(jì)算量，有效避免了數(shù)據(jù)的冗余。而LANDMARC定位算法在未知點(diǎn)處測(cè)得各個(gè)標(biāo)簽的信號(hào)強(qiáng)度值之后，還需要與第一步建立的指紋庫(kù)中的全部點(diǎn)進(jìn)行匹配分析，眾多的數(shù)據(jù)影響了算法的復(fù)雜度，而且在一一匹配分析時(shí)較多次數(shù)的計(jì)算也增加了定位結(jié)果出錯(cuò)的可能性。

4 結(jié)束語(yǔ)

分步的位置指紋定位算法，運(yùn)用分步定位的思想，先進(jìn)行粗定位，后進(jìn)行精定位。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的LANDMARC定位算法相比，本文提出的定位算法在保證定位精度的同時(shí)，降低了數(shù)據(jù)的傳輸量與計(jì)算量，有效地提高定位效率。新算法可以應(yīng)用于室內(nèi)機(jī)器人定位、消防員實(shí)時(shí)定位、商品查找、立體倉(cāng)庫(kù)定位等領(lǐng)域。