基于子區域劃分的室內定位算法研究

郭曉鳳，徐志良

（南京機電職業技術學院 江蘇南京 211135）

基于子區域劃分的室內定位算法研究

郭曉鳳，徐志良

（南京機電職業技術學院 江蘇南京 211135）

文中基于提高射頻識別定位系統中定位精度的目的，提出了一種改進的IMLANDMARC算法，該算法通過對待定位標簽所在區域進行子區域劃分，并增加虛擬參考標簽的方法，對LANDMARC算法進行改進，使用Matlab軟件對算法進行仿真試驗，與射頻識別定位系統中常用的LANDMARC算法、VIRE算法和BVIRE算法比較，結果表明在耗時增加較小情況下該算法有效的提高了定位精度。

LANDMARC算法；劃分子區域；IMLANDMARC算法；定位精度

室內定位是指在室內環境中實現位置定位，主要應用在礦山救援、倉庫貨品定位、車庫車輛位置定位等方面。采用的方法有超聲波[1]、紅外[2]、超寬帶[3]、基于射頻識別等定位技術[4]。射頻識別技術（Radio Frequency Identification，RFID）具有非接觸、非視距、成本低、定位精度高等優點，因此成為了優選的室內定位技術[5]。基于RFID定位[6-9]的典型算法主要有LANDMARC算法、VIRE算法、BVIRE算法。

文中在LANDMARC算法的基礎上，通過劃分子區域的方式，對LANDMARC算法進行了改進[9-14]（簡稱IMLANDMARC算法），并且進行了仿真，把仿真結果與LANDMARC算法、VIRE算法和BVIRE算法進行比較，結果表明相同條件下IMLANDMARC算法的定位精度較高。

1 LANDMARC算法簡介

LANDMARC[15]算法采用參考標簽來進行輔助定位，通過參考標簽的信號強度值與待定位標簽的信號強度值之間的比較，采用“最近鄰距離”權重思想，計算出待定位各標簽的坐標。

假設有M個參考標簽，K個閱讀器，和N個目標標簽，（圖1所示為M=25，N=5，K=4）。N個目標標簽隨機布置在M個參考標簽周圍。

圖1 定位系統圖例

WI是第I個鄰居的權重（I=1，2，3，…，n＜M，n是M個歐氏距離EJ中最小的n個鄰居，WI可根據經驗公式得到：

定義誤差:

其中（x，y）為估計出的待定位標簽位置，（x0，y0）為待定位標簽的實際位置。

LANDMARC算法的優點如下：

①參考標簽的引入降低了閱讀器的數量，進而減少了定位成本；

②參考標簽和待定位標簽處于同樣的環境中，可以大大抵消很多環境因素的影響；

③定位的信息更加準確。

LANDMARC算法的不足：

①參考標簽的分布直接影響到定位的精度；

②較高的定位精度完全依賴于較高的參考標簽密度，而高的標簽密度勢必帶來大的干擾，同時也會增加成本。

2 對LANDMARC算法的改進

從LANDMARC算法的優缺點可以看出，參考標簽的密度對定位的精度影響較大。本文是在LANDMARC算法基礎上做了改進，主要思路如下：

1）首先使用LANDMARC算法對待定位標簽進行初步的位置估計，獲取該定位標簽對應的4個臨近參考標簽（矩形區域）；

2）將參考標簽的區域劃分成4個相同大小的子區域，如圖2所示。

圖2 子區域劃分圖

3）根據估計位置估算待定位標簽所在的子區域，如圖3所示，然后在選定子區域內將另外3個頂點作為虛擬參考標簽，并根據3個參考虛擬標簽和一個實體的參考標簽來估算待定位標簽的位置。

圖3 參考標簽選擇

主要的定位流程如圖4所示。

圖4 改進后的定位算法流程

3 仿真結果分析

3.1 改進的IMLANDMARC算法

文中采用了500個隨機樣本進行了仿真（空間大小：12 m*12 m，M=25，N=500，K=4），并將結果與LANDMARC算法，VIRE算法，BVIRE算法進行了比較，IMLANDMARC算法的定位精度較LANDMARC算法，VIRE算法，BVIRE算法有所提高，如圖5所示。

圖5 4種算法誤差比較圖

從定位每個標簽的時間耗時上來看IMLANDMRAC算法稍高于LANDMARC算法，但是明顯低于VIRE算法和BVIRE算法。如圖6所示。

圖6 4種算法耗費時間比較

在測試過程中，每種算法選取整個定位區域內的500個點作為測試點，使用累計分布函數（Cumulative distribution function，CDF）對比分析4種算法獲得的值，結果表1所示。

從表1可以看出，IMLANDMARC算法的誤差累計分部最靠近縱軸，所以其定位精度相比LANDMARC算法，VIRE算法，BVIRE算法較高。

表1 誤差累積分布比例

3.2 IMLANDMARC算法參考標簽間隔的研究

在定位區域不變的情況下，對參考標簽的間隔大小進行了測試，并且對參考標簽不同間隔定位結果與LANDMARC算法，VIRE算法，BVIRE算法做了比較。

將參考標簽的間隔由原來的2 m分別增加到3 m和4 m，定位誤差的比較如圖7和圖8所示，從定位誤差的結果可以看出：當參考標簽間隔為3 m的時候，如表2所示，IMLANDMARC算法的誤差要稍高于BVIRE算法（平均誤差約高于BVIRE算法0.04 m），但是優于LANDMARC算法（平均誤差約低于LANDMARC算法0.05 m），VIRE算法（平均誤差約低于VIRE算法0.09 m）。

當參考標簽間隔為4m的時候，如表3所示，IMLANDMARC算法的誤差比較大，明顯高于LANDMARC算法，VIRE算法，BVIRE算法。

誤差累計分布（Cumulative distribution function，CDF）比較如表 2、表3所示，從誤差累計結果可以看出[16]：當參考標簽間隔為3 m的時候，小于0.3 m的比例，IMLANDMARC算法約為83%，低于BVIRE算法93%，但是高于LANDMARC算法78%，VIRE算法55%。

圖7 4種算法誤差比較-參考標簽間隔為3 m

圖8 4種算法誤差比較-參考標簽間隔為4 m

表2 誤差累積分布比例-參考標簽間隔為3m

當參考標簽間隔為4 m的時候，小于0.3 m的比例，IMLANDMARC算法約為27%，低于BVIRE算法93%，LANDMARC算法78%，VIRE算法55%。

表3 誤差累積分布比例-參考標簽間隔為4 m

從前面仿真結果可以看出，參考標簽的間隔在3 m左右的時候，IMLANDMARC算法定位精度較BVIRE算法要差一些（平均誤差約高于BVIRE算法 0.04 m，誤差小于0.3 m的占比約低于BVIRE算法7%左右），但是好于LANDMARC算法和VIRE算法，如果要降低參考標簽的數量又兼顧定位精度，IMLANDMARC算法也具有一定的使用價值。

參考標簽的間隔在4M左右的時候，IMLANDMARC算法定位精度較LANDMARC算法、VIRE算法和BVIRE算法3種算法要差一些，不建議采用。

4 結束語

文中提出的IMLANDMARC算法從仿真結果上來看，在相同參考標簽間隔的情況下，IMLANDMARC算法定位精度相對于LANDMARC算法有所提升，雖然耗時也相對增加一些，但是明顯低于VIRE算法和BVIRE算法；當參考標簽的間隔是LANDMARC算法、VIRE算法和BVIRE算法3種算法1.5倍的時候，仍具有較好的精度，可以在一定程度上降低工程實施的成本；綜上，IMLANDMARC算法具有一定的參考價值和工程可實施性。

[1]Sanpechuda T， Kovavisaruch L.A review ofRFID localization: applications and techniques [C].Electrical Engineering/Electronics，Computer，Telecommunications and Information Technology，2008.ECTI-CON 2008.5th International Conference on 2008.

[2]蔣婷婷，鄭國莘，鄭瑞杰．IR-UWB測距在多徑信道下的時延性能分析[J]應用科學學報，2007，25（3）:327-330.

[3]Curran K，Furey E，Lunney T，et al.An evaluation of indoor location determination technologies[J].Journal of Location Based Services，2011，5（2）:61-78.

[4]Tesoriero R， TebarR， Gallud J.Improving location awareness in indoor spaces using RFID technology[J].Expert Systems with Applications，2010，37（1）:894-898.

[5]周悖，胡方明，胡華鵬，等.基于牛頓插值的RFID室內定位算法.電子科技，2015，26（9）:34-40.

[6]蔣華勤，李靜.基于LANDMARC的RFID室內定位算法優化[J].科技通報，2013，29（6）:206-207

[7]俱瑩.基于RFID的室內定位算法研究[D].天津大學，2010.

[8]王遠哲，毛陸虹，劉輝，等.基于參考標簽的射頻識別定位算法研究與應用[J].通信學報.2010，31（2）:86-92.

[10]李軍懷，張果謀，于蕾，等.具有環境自適應性的虛擬參考標簽定位方法[J].應用科學學報，2013，31（4）:402-410.

[11]陳家琪，嚴梓乘.一種Newton插值的RFID室內定位改進算法[J].計算機系統應用，2011，21（1）:45-48.

[12]李鵬，馬寧，楊擁軍，等.基于RFID的邊界虛擬參考標簽改進算法[J].計算機應用研究，2013，30（1）:158-160.

[13]段本亮，李建雄，陳明省，等.改進的RFID室內定位算法[J].天津工業大學學報，2013，32（4）:66-70.

[14]楊輝，蔡堅勇，高杰星，等.基于LANDMARC定位算法復雜度的分區算法改進[J].計算機系統應用，2012，22（5）:103-106.

[15]Lionel MN，Liu Yun Hao，Lau Y C，et a1.LANDMARC: Indoor location sensing using active RFID[J].WirelessNetworks，2004，10（6）:701-710.

[16]雷震，李怡，付琳琳.液氧主容器溫度測量誤差分析與改進方法[J].火箭推進，2015(6)：105.

Research on indoor localization algorithm based on dividing sub-area

GUO Xiao-feng，XU Zhi-liang
（Nanjing Institute of Mechatronic Technology，Nanjing 211135，China）

Based on the purpose of improving the positioning accuracy of radio frequency identification system，an improved IMLANDMARC algorithm is proposed.This algorithm is improved by dividing sub-area of target tag area and adding virtual reference tags.The Matlab is being used to simulate the algorithm，IMLANDMARC algorithm effectively enhances the localization accuracy with shorter time consumption increase by comparing with LANDMARC algorithm，VIRE algorithm and BVIRE algorithm.

LANDMARC algorithm；dividing sub-area；IMLANDMARC algorithm；localization accuracy

TN99

A

1674－6236（2016）24-0025-04

2015-12-11 稿件編號：201512134

江蘇省高等職業院校國內高級訪問學者計劃資助項目（2014FX043）

郭曉鳳（1979—），女，遼寧葫蘆島建昌人，碩士研究生，講師。研究方向：電子信息技術。