楊勇明

(上海理工大學 公共實驗中心，上海 200093)

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

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

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

1.1 LANDMARC定位算法

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

(1)

圖1 LANDMARC算法原理圖

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

(2)

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

(3)

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

1.2 LANDMARC定位算法冗余性分析

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

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

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

圖2 位置指紋算法流程圖

2.1 離線訓練階段

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

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

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

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

2.2 在線定位階段

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

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

圖4 細定位原理圖

3 實例驗證

3.1 實驗環(huán)境

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

圖5 實際實驗測試圖

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

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

圖6 無障礙物實驗布置圖

3.2 實驗步驟

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

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

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

3.3 實驗結(jié)果及分析

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

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

實驗中閱讀器的位置代表未知點的位置，依次將閱讀器放在實驗布置圖中的21、22、23、24位置，多次測量求出其平均值。表2匯總了實驗測得的未知點各個標簽的信號強度值。

表2 未知點處各標簽的信號強度

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

表3 未知點處所確定的參考點

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

(4)

式中，(x,y)為實驗測得未知點坐標，(x1,y1)為未知點實際坐標。

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

表4 實驗定位結(jié)果

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

4 結(jié)束語

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