一種基于區域分割和目標搜索的室內定位方法

向祖權　靳　超　郭純軒　許慧文

(武漢理工大學高性能船舶技術教育部重點實驗室1)　武漢　430063)　(武漢理工大學交通學院2)　武漢　430063)

?

一種基于區域分割和目標搜索的室內定位方法

向祖權1,2)靳超1,2)郭純軒1,2)許慧文2)

(武漢理工大學高性能船舶技術教育部重點實驗室1)武漢430063)(武漢理工大學交通學院2)武漢430063)

基于參考標簽的最近鄰居思想提出區域分割和目標點搜索方法，對室內平面物體進行定位.對最近鄰居參考標簽圍成的矩形定位區域進行兩次連續分割，縮小定位區域范圍，選取該范圍中心點作為起始點，向x，y軸正負方向以規定步長進行目標搜索，找出與待定位標簽信號強度值之間的歐氏距離滿足精度要求的點作為最終定位點.仿真實驗結果表明，在不改變硬件條件的基礎上，改進算法的定位精度比傳統LANDMARC方法提高了64%.

區域分割；目標搜索；射頻識別；參考標簽；室內定位

0　引　　言

室內定位技術是指在室內環境下對物品進行定位.由于建筑物的遮蔽，考慮到定位精度、成本等方面，GPS等室外定位方式不再適用[1]，需要一種新的定位方法來滿足室內環境的要求.

射頻識別(radio frequency identification，RFID)技術因其數據傳遞快、識別距離遠、非接觸數據傳遞等特點[2]，正在逐步被應用到室內定位中.Ling等[3]提出了一種基于RFID技術利用參考標簽進行輔助定位的LANDMARC(location identification based on dynamic active rfid calibration)定位系統，但是該系統定位精度受到自身硬件條件的限制有一個上限值[4]，在定位精度要求較高的情況下此種定位方法不能夠滿足定位要求.

文中通過對最鄰近參考標簽所組成的定位區間進行分割[5]，在分割后區間內對目標點進行搜索，引入“距離-損耗”模型[6-8]，對區間內的點進行虛擬信號強度賦值，選出信號強度與待定位標簽信號強度相同的點作為最終的定位結果.

1　LANDMARC定位系統

LANDMAC定位系統布置見圖1.它通過引入參考標簽進行輔助定位(參考標簽坐標已知)提出“最近鄰居”思想，通過與待定位標簽鄰近的若干參考標簽的坐標進行加權運算得到待定位標簽的坐標.現假設有m個閱讀器，n個參考標簽，p個待定位標簽，每個閱讀器都可以讀到參考標簽和待定位標簽的信號強度(receive signal strength identification，RSSI)值.

圖1　LANDMAC定位系統示意圖

記某個待定位標簽Pi在各個閱讀器上的RSSI值構成如下矢量:Pi=(PiM1,PiM2,…,PiMm)

式中：PiMs為該待定位標簽Pi在第s個閱讀器上的RSSI值，i∈(1,p)，s∈(1,m).

記某個參考標簽Rj在各個閱讀器上的RSSI值構成如下矢量:Rj=(RjM1,RjM2,…,RjMm)

式中：RjMs為該參考標簽Ri在第s個閱讀器上的RSSI值，j∈(1,n)，s∈(1,m).

待定位標簽PiMs與參考標簽RjMs之間RSSI值的歐式距離為

(1)

因為需要選出與待定位標簽Pi鄰近的若干個參考標簽，所以對于待定位標簽Pi來說，需要計算n個參考標簽與其之間RSSI值的歐氏距離，它們組成一個集合Di.

(2)

比較Di,j的大小，選出k個與待定位標簽鄰近的參考標簽，通過計算可以得到待定位標簽的坐標為

(3)

式中：j∈(1,k)，(xj,yj)為參考標簽坐標，wj為第j個參考標簽的權重，可通過下式計算得到.

(4)

系統的定位誤差可以通過待定位標簽的真實坐標與計算坐標進行比較得出

(5)

式中：(x,y)為計算坐標，(x0,y0)為真實坐標.

2　改進LANDMARC算法

2.1RSSI損耗模型

在不考慮室內環境干擾的情況下，閱讀器接收到的標簽的信號強度會因傳播距離和信號到達角度而產生的損耗.RSSI損耗值為

(6)

式中：PL(d)為傳播路徑損耗，L(θ)為到達角度損耗.

閱讀器接收到的RSSI值為

(7)

式中：Pt為標簽發射信號強度.

為了減少因信號到達角度而產生的損耗，可以擴大閱讀器天線接收信號的角度，將閱讀器的天線設計成球面.這樣就可以忽略信號到達角度產生的損耗，將RSSI損耗模型簡化為“路徑-損耗”損耗模型.

(8)

(9)

式中：PL(d0)為傳播距離為d0時，信號在自由空間中的路徑損耗；Xσ為陰影衰落(遮蔽因子)，它是均值為0，方差為σ的高斯隨機變量；n為路徑損耗指數，與所處環境相關.

2.2定位方法

首先利用LANDMARC定位系統可以得到k個與待定位標簽最鄰近的參考標簽，取k=4，見圖2，待定位標簽位于a，b，c，d四個參考標簽組成的區域中.以下分析中假設這4個參考標簽與待定位標簽之間RSSI值歐氏距離大小排序為：Da

圖2　空間分割示意圖

記正方形anom4個頂點的坐標為：{(xa,ya),(xn,yn),(xo,yo),(xm,ym)},其中：xn=(xa+xd)/2，yn=(ya+yd)/2；xo=(xa+xb)/2，yo=(ya+yd)/2；xm=xa，ym=(ya+yd)/2.取正方形中心點(x′,y′)作為搜索的初始點，其中：

(10)

(11)

以(x′,y′)為中心，s為步長，分別向坐標軸x，y的正負方向搜索，得到4個點，見圖3，它們坐標分別是：{(x′+s,y′),(x′,y′+s),(x′-s,y′),(x′,y′-s)}.每個點與各個閱讀器之間的距離通過兩點之間距離公式可以得到，將距離帶入公式(9)可以得到該點在閱讀器上的虛擬RSSI值.

圖3　目標點搜索示意圖

例：點(x+s,y)與各個閱讀器之間的距離為{d1,d2,…,dm}，將di帶入式(9)可以得到點(x′+s,y′)在閱讀器i上的虛擬RSSI值Prec(i)，同理可以得到其在每個閱讀器上的RSSI值，記為：{Prec(1),Prec(2),…,Prec(m)}，計算該點與待定位標簽之間RSSI值之間的歐氏距離.對其余3個點重復上述計算，選出4個點中與待定位標簽之間RSSI的歐氏距離最小的點作為下次搜索的起點.不斷重復上述步驟，直到搜索出的點與待定位標簽之間RSSI值歐氏距離滿足精度要求e為止，該點即為最后的定位點.改進算法流程見圖4.

圖4　改進算法流程圖

3　仿真實驗及分析

仿真實驗環境設置為11 m×11 m的室內空間，見圖5，布置有36個參考標簽(相鄰2個參考標簽之間間距2 m)，4個閱讀器(相鄰2個閱讀器之間間距4 m).取最近鄰參考標簽為4個，即k=4；搜索步長為0.01，即s=0.01；定位精度要求為1，即e=1.現對該環境中的10個參考標簽(坐標見表1)，分別利用LANDMARC算法和改進算法進行定位計算，并比較2種算法的定位誤差和標注差.

(12)

圖5　仿真實驗環境布置

表1　待定位標簽坐標

利用LANDMARC算法和改進算法對待定位標簽進行定位仿真的結果見圖6～7.對比兩圖可以看出改進算法的定位結果比LANDMARC算法更接近待定位標簽的實際坐標.改進算法中目標點搜索過程見圖8.

由圖9可知，LANDMARC算法定位誤差在0.14～0.74 m之間波動；改進算法的定位誤差在0.01～0.18 m之間波動，由圖9中可知改進算法在定位誤差范圍方面優于LANDMARC定位算法.

圖6　LANDMARC算法定位結果

圖7　改進算法定位結果

對10個待定位標簽進行計算，利用LANDMARC算法定位的平均誤差為0.39，標準差為0.21；利用改進算法定位的平均誤差為0.14，標準差為0.05.從計算結果可以看出改進算法定位精度和定位穩定性都要優于傳統的LANDMARC算法.

圖8　改進算法目標點搜索過程

圖9　定位誤差

4　結 束 語

文中提出的算法在傳統的LANDMARC算法基礎上，對最近鄰參考標簽圍成的定位區域進行兩次連續分割，在分割后的區域中進行目標點搜索，找出目標點虛擬RSSI值與待定位標簽RSSI值之間歐氏距離最小的點作為最終的定位結果.通過對比分析，該算法在不改變傳統LANDMARC定位算法硬件系統的基礎上，通過對算法的改進，將定位精度提高了64%，擴大了定位系統的應用范圍.

[1]ALI M, OSAMA M. RFID indoor location identification for construction projects[J]. Automation in Construction.,2014,39(1):167-179.

[2]NAN L, BURCIN B G. Performance-based evaluation of RFID- based indoor location sensing solutions of the built environment[J]. Advanced Engineering Informatics,2011,24(3):535-546.

[3]LING W, LI Y H. Improvement of location methods based on RFID[J]. The Journal of China Universities of Posts and Telecommunications,2013,20(6):36-41.

[4]李婧.RFID室內三維定位算法研究[D].成都：電子科技大學,2010.

[5]高銳,程良倫,胡莘.一種基于空間分割的無源RFID室內定位方法[J].計算機應用研究,2012,9(1):184-186.

[6]SAMER S S, ZAHI S. A standalone RFID indoor positioning system using passive tags[J]. Ieee Transactions on Industrial Electronics,2011,58(5):1961-1970.

[7]陳勇,石南,陳永光.基于RFID和無線傳感的礦井實時定位預警系統[J].電子設計工程,2012(21):55-58.

[8]黃雙歡,程良倫.一種拓撲約束的RFID三維定位方法[J].計算機應用研究,2012(1):77-80.

An Indoor Positioning Method Based on the Region Division and Target Search

XIANG Zuquan1,2)JIN Chao1,2)GUO Chunxuan1,2)XU Huiwen2)

(KeyLaboratoryofHighPerformanceShipTechnology,WuhanUniversityofTechnology,MinistryofEducation,Wuhan430063,China)1)(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063,China)2)

Based on the nearest neighboring theory, a method of region division and target searching is proposed for the positioning of interior plane objects. Firstly, two consecutive divisions of the rectangular region enclosed by the nearest neighboring reference labels are conducted to reduce the searching ranges. By picking the central point of the range as the starting point, target searching is conducted in both positive and negative directions ofxandyaxes with a fixed step. Finally, the final positioning point is determined based on the condition that the Euclid distance of signal intensity between the label to be positioned and the final positioning point meets the accuracy requirement. Simulation results show that the algorithm in this paper improves the positioning accuracy of about 64% compared to the traditional LANDMARC methods without changing the hardware conditions.

region division; target search; RFID; reference label; indoor positioning

2016-05-30

TP399

10.3963/j.issn.2095-3844.2016.04.022

向祖權(1973- )：男，博士，副教授，主要研究領域為船舶先進制造