楊勇明

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

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

常用的室內(nèi)定位算法主要包括基于測距的三邊定位算法和基于非測距的位置指紋定位算法。由于受環(huán)境因素影響較小[4]，位置指紋定位算法成為諸多學(xué)者研究的焦點(diǎn)。LANDMARC定位算法由文獻(xiàn)[5]提出，是基于非測距的經(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è)閱讀器上測得的信號強(qiáng)度值，其中r=1,2,3,4,…,n,j=1,2,3,4,…,m；第二步，令si,j表示第i個(gè)未知點(diǎn)在第j個(gè)閱讀器上測得的信號強(qiáng)度值，其中i=1,2,3,4,…,p；第三步，對未知點(diǎn)測得的信號強(qiáng)度與數(shù)據(jù)庫中對應(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)所示的信號強(qiáng)度均方差表示

(1)

圖1 LANDMARC算法原理圖

Ei,r表示歐幾里得距離[7]，根據(jù)式(1)，當(dāng)未知點(diǎn)RSSI值與數(shù)據(jù)庫中對應(yīng)參考點(diǎn)標(biāo)簽的RSSI值接近時(shí)，表示未知點(diǎn)與參考標(biāo)簽的位置十分接近。由于數(shù)據(jù)庫中有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)也參與定位過程，不僅增加系統(tǒng)的復(fù)雜度，也增加了錯(cuò)誤的產(chǎn)生率，進(jìn)而產(chǎn)生數(shù)據(jù)冗余現(xiàn)象[9]，導(dǎo)致系統(tǒng)效率和實(shí)時(shí)性下降，影響用戶體驗(yàn)。針對此問題，本文提出基于分步的位置指紋定位算法。在離線訓(xùn)練階段，進(jìn)行粗粒度的定位(粗略定位)，確定未知點(diǎn)所在的區(qū)域，排除不可能的區(qū)域點(diǎn)；在在線定位階段，進(jìn)行細(xì)粒度的定位(精確定位)。

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

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

圖2 位置指紋算法流程圖

2.1 離線訓(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ū)域，避開一些不必要參考點(diǎn)的計(jì)算。通常將粗粒度點(diǎn)設(shè)置在幾何圖形的中心位置，如正方形或者三角形的中心。粗粒度點(diǎn)確定后就需要確定細(xì)粒度點(diǎn)位置，細(xì)粒度點(diǎn)數(shù)量較多，通常圍繞著粗粒度點(diǎn)呈放射狀或者矩形狀。基于分步的位置指紋定位算法原理圖如圖3所示。

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

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

2.2 在線定位階段

分步定位主要應(yīng)用于在線定位階段，在未知點(diǎn)處實(shí)時(shí)測得各個(gè)標(biāo)簽信號強(qiáng)度值，進(jìn)行多次測量求取平均值，完成第一步粗定位。在縮小未知點(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)行對比后確定未知點(diǎn)所在的區(qū)域?yàn)镋，則下一步在區(qū)域E進(jìn)行精確定位。

如圖4所示，精確定位時(shí)，舍棄與定位結(jié)果無關(guān)的A、B、C、D、F、G、H、I區(qū)域內(nèi)的參考點(diǎn)，只將未知點(diǎn)的信號強(qiáng)度與定位區(qū)域E內(nèi)4個(gè)細(xì)粒度參考點(diǎn)進(jìn)行相似度匹配即可：首先根據(jù)粗粒度點(diǎn)確定細(xì)粒度點(diǎn)，并將其利用到第二步精確定位；然后通過與參考細(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)樓的一樓大廳，測試范圍為長3.6 m，寬3.6 m的區(qū)域，實(shí)驗(yàn)儀器選擇2.4 GHz遠(yuǎn)距離RFID閱讀器和有源RFID電子標(biāo)簽?；赗FID的應(yīng)用主要分為標(biāo)簽的移動(dòng)和閱讀器的移動(dòng)[13]，本次實(shí)驗(yàn)選擇閱讀器移動(dòng)，該方法的優(yōu)勢是數(shù)量較多、價(jià)格較便宜的標(biāo)簽被放置在已知位置點(diǎn)，僅需使用一個(gè)閱讀器即可完成，費(fèi)用較低。實(shí)驗(yàn)開始前，檢查筆記本與閱讀器之間的通信連接狀況，檢查所有的有源標(biāo)簽的紐扣電子是否電量充足，定義實(shí)驗(yàn)中閱讀器的位置代表未知點(diǎn)的位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

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

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

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

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

4 結(jié)束語

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