基于蛛網(wǎng)結構和雙曲線的定位算法

歐陽林群,阮承治

(武夷學院機電工程學院，福建 武夷山 354300)

基于蛛網(wǎng)結構和雙曲線的定位算法

歐陽林群,阮承治

(武夷學院機電工程學院，福建 武夷山 354300)

為提高蛛網(wǎng)定位算法的精度，提出了一種基于蛛網(wǎng)結構和雙曲線的定位算法。首先按照蛛網(wǎng)拓撲結構放置射頻參考標簽，在蛛網(wǎng)中心安裝閱讀器；然后對蛛網(wǎng)結構的主弦和輔弦節(jié)點分別構造同心圓，找出距離待測標簽最近的同心圓；接著采用最近同心圓上參考標簽坐標和待測標簽坐標的雙曲線關系，利用最大似然估計法求出待測標簽坐標；最后對提出算法的精度進行計算，與當前流行的蛛網(wǎng)定位算法進行對比試驗，驗證了該算法的有效性。

射頻識別；蛛網(wǎng)拓撲結構；雙曲線；定位算法

隨著物聯(lián)網(wǎng)技術的不斷發(fā)展，目標定位技術越來越受到人們的關注，定位精度的要求也越來越高。射頻識別(Radio Frequency Identification,RFID)是物聯(lián)網(wǎng)領域的核心技術，是一種利用射頻方式進行非接觸雙向通信的自動識別技術。RFID基本系統(tǒng)包括閱讀器和電子標簽，閱讀器和標簽通過閱讀器天線和標簽天線的耦合完成信號的傳輸[1]。相比于紅外、藍牙、超聲波、Global Position System(GPS)等技術，射頻識別技術具有非視距、非接觸、定位精度高、成本低等優(yōu)點，成為室內(nèi)定位的首選[2]。隨著室內(nèi)定位技術的發(fā)展，出現(xiàn)了大量的定位算法，主要分為到達時間法(Time of Arrival，TOA)、到達角度法(Angle of Arrival，AOA)、接收信號強度法(Received Signal Strength Indicator，RSSI)和到達時間差法(Time Difference of Arrival，TDOA)4類。對于室內(nèi)多徑效應產(chǎn)生的信號干擾，接收信號強度法表現(xiàn)出優(yōu)于其他3種方法的抗干擾性能，因此更適合于室內(nèi)環(huán)境的定位[3]。

目前典型的RFID定位系統(tǒng)主要有Spoton系統(tǒng)，Virtual Reference Elimination (VIRE)和LocAtioN iDentification based on dynaMic Active Rfid Calibration (LANDMARC)系統(tǒng)等。在LANDMARC系統(tǒng)中，選取最接近待測標簽信號強度的參考標簽，運用權重質(zhì)心法計算待測標簽坐標[4]。在LANDMARC 系統(tǒng)的基礎上，李綱等提出了蛛網(wǎng)定位算法用于改進定位精度，該方法采用最接近待測標簽信號強度的相似環(huán)中參考標簽坐標估算待測標簽坐標[5]。為進一步提高蛛網(wǎng)算法的定位精度和實現(xiàn)更小距離的精確定位，筆者提出了一種基于蛛網(wǎng)結構和雙曲線的定位算法。

圖1 蛛網(wǎng)結構圖

1 基于RFID的蛛網(wǎng)結構

通過RFID定位系統(tǒng)發(fā)現(xiàn)，為精簡標簽和閱讀器數(shù)目以實現(xiàn)系統(tǒng)的高效定位，定位參考標簽往往按照一定的拓撲結構分布[6]。受蜘蛛結網(wǎng)獵取食物的啟發(fā)，將射頻閱讀器作為蛛網(wǎng)的中心，在蛛網(wǎng)的節(jié)點處安裝射頻參考標簽，如圖1(a)所示。黑色實心點為蛛網(wǎng)主弦上均勻分布的節(jié)點，空心點為蛛網(wǎng)輔弦上均勻分布的節(jié)點，該結構能夠有效減少參考標簽的數(shù)量且實現(xiàn)定位。將圖1(a)的蛛網(wǎng)拓撲結構分布到整個待定位區(qū)域，能夠?qū)崿F(xiàn)定位區(qū)域間的無縫連接和定位系統(tǒng)的實時定位[7]，如圖1(b)所示。

2 定位算法

2.1 最近同心圓的選取

圖2 閱讀器和標簽位置示意圖

圖2為蛛網(wǎng)結構中的閱讀器和標簽位置示意圖，實心點和空心點代表蛛網(wǎng)結構中的參考標簽，五角星代表待測標簽，方框代表閱讀器。其中，每6個一組實心點和每6個一組空心點構成不同半徑的同心圓。

為了初步確定待測標簽的位置，需要找出與待測標簽距離最近的同心圓。將閱讀器接收到的參考標簽的信號強度設置為矩陣A：

(1)

將閱讀器接收到的待測標簽的信號強度設置為矩陣B：

B=[B1，B2，…，BL]

(2)

其中，Aij(i=1,2,…,m;j=1,2,…,n)表示第i個同心圓的第j個參考標簽的信號強度；Bk(k=1,2,…,L)表示第k個待測標簽的信號強度。

將式(1)中的矩陣A每一項減去Bk，得到的矩陣Mk中均值最小的一行對應的參考標簽組成第k個待測標簽的最近同心圓。矩陣Mk為：

(3)

通過式(3)可求解并找出與待測標簽最近的同心圓。

2.2 待測標簽的定位

圖3 雙曲線定位原理圖

基于第k個待測標簽與其最近同心圓中的6個節(jié)點的位置關系，采用雙曲線定位求出待測標簽的坐標。雙曲線定位原理如圖3所示，其基本原理如下：實心五角星為待測標簽，T1、T2和T3分別為第k個待測標簽與其最近同心圓中的6個節(jié)點中的3個；待測標簽與參考節(jié)點標簽(T1、T2和T3)之間的距離分別為d1、d2和d3；待測標簽與參考標簽T1和T2的距離差為d21,則被測標簽一定處于以T1和T2為焦點，焦距為d21的雙曲線上；同樣地，待測標簽與參考標簽T1和T3的距離差為d31,則被測標簽一定處于以T1和T3為焦點，焦距為d31的雙曲線上；2組雙曲線的交點S就是待測標簽的坐標(如圖3中的五角星)。

假設待測標簽的坐標為(x,y)，T1、T2和T3的坐標分別為(x1,y1)，(x2,y2)， (x3,y3)，則有：

(4)

該方程屬于高次方程，理論上存在s和s′這2個解，可通過Matlab中的指令求解方程。然而，現(xiàn)實情況下該方程只有1個解。通過參考信息和一定經(jīng)驗可以消除掉運動位置不確定點，筆者采用式(3)去驗證所求待定位標簽坐標點是否滿足最近同心圓條件，達到去除點s′的目的。

若使用多參考標簽進行定位，則待測標簽的求解就轉(zhuǎn)化成一個概率分布問題，采用極大似然估計算法確定待測標簽的最可能坐標[8]。已知m個參考標簽的坐標是(xi,yi)(i=2,3,…,n;j=1,2,…,m,i>j)，其與待定位標簽的距離為dij可表示為：

(5)

為求出待定位標簽坐標(x,y)，將式(5)寫成AX=B的形式[9]。已知dm(m-1)為dm和d(m-1)的矢量差，則式(5)可以轉(zhuǎn)化為：

(6)

將式(6)轉(zhuǎn)化為通式形式：

(7)

(8)

將式(6)轉(zhuǎn)化成矩陣AX=b的形式，則：

X=(ATA)-1ATb

其中：

3 試驗結果與分析

為了對筆者提出算法的精度進行驗證，將筆者提出的基于蛛網(wǎng)結構和雙曲線的定位算法(記為H-CLA)與蛛網(wǎng)定位算法(記為CLA)[5]進行比較。文獻[5]中將待測標簽分為3類，如圖4所示。3類待測標簽分別可表示為：

1) 只有1個參考標簽靠近待測標簽S1，令待測標簽坐標等于該參考標簽坐標，即(x,y)=(x1,y1)；

圖4 CLA算法標簽分布圖

2) 只有2個參考標簽靠近待測標簽S2，待測標簽坐標等于這2個參考標簽坐標的中點，即(x,y)=；

3)待測標簽S3位于3個參考標簽中間，采用LANDMARK算法求出待測標簽坐標，如式(9)：

(9)

筆者采用如圖2所示的蛛網(wǎng)結構在拓撲結構中分布24個參考標簽和1個閱讀器，放入10個待測標簽進行仿真。設定參考標簽的距離為1.85m，參考標簽的掃描半徑為1.2m。圖5為H-CLA算法和CLA算法的定位坐標與待測標簽真實坐標的對比圖，紅色圈表示待測標簽真實坐標，綠色星號表示CLA算法的定位坐標。藍色五角星表示H-CLA算法的定位坐標。由圖5可見，藍色五角星比綠色星號更接近紅色圈，表明采用筆者提出算法得出的待測標簽的坐標更加接近真實坐標，其誤差更小。

采用H-CLA和CLA算法分別對待測標簽的坐標進行定位仿真，采用定位誤差累計分布函數(shù)(Cumulative Distribution Function, CDF)評價H-CLA算法和CLA算法[10]。仿真100次，2種算法的CDF曲線如圖6所示。CLA算法的最小誤差為0.284m，最大誤差為0.783m，50%的誤差小于0.575m；H-CLA算法的最小誤差為0.157m，最大誤差為0.368m，50%的誤差小于0.229m。從結果來看，H-CLA算法定位存在明顯的優(yōu)勢。

圖5 H-CLA和CLA算法的定位坐標與真實坐標對比圖 圖6 H-CLA和CLA算法的CDF對比曲線

為研究參考標簽距離與定位精度之間的關系，由誤差公式：

(10)

可得出待測標簽的誤差平均值：

(11)

仿真得到H-CLA和CLA算法的參考標簽距離與平均誤差之間的關系曲線如圖7所示，采用CLA算法平均誤差較小且平滑的區(qū)間落在1.2～3.3m，而H-CLA算法的平均誤差較小且平滑的區(qū)間落在0.2～4.8m。結果表明，H-CLA算法比CLA算法更能應用于精度要求較高的近距離定位，在較大的參考標簽距離內(nèi)保持定位誤差平均值較小且穩(wěn)定，能有效減少蛛網(wǎng)節(jié)點的標簽個數(shù)，優(yōu)化蛛網(wǎng)拓撲結構和減少系統(tǒng)成本。

4 結論

1)在算法設計方面，傳統(tǒng)的蛛網(wǎng)算法是采

用就近距離的參考標簽坐標作為待測標簽坐標，是一種近似的思想。筆者分析就近同心圓中參考節(jié)點與待測標簽之間的雙曲線關系，采用最大似然估計法求解出更加精確的待測標簽坐標。

2)在硬件成本方面，筆者提出的算法在每個蛛網(wǎng)拓撲結構中只用了1個閱讀器，且參考標簽的數(shù)量比CLA算法有所減少。因此，該算法具有硬件成本低，易于系統(tǒng)擴展等優(yōu)點。

3)在應用方面，相對于CLA算法，筆者提出的算法的定位精度得到一定改進，且實現(xiàn)了更大的參考標簽距離的精確定位，不僅使得該算法能夠應用于定位精度要求較高的小距離定位，而且使得相同個數(shù)的參考標簽實現(xiàn)更大區(qū)域內(nèi)的待測標簽的定位。

4)研究只討論了單個蛛網(wǎng)結構中的待測標簽的定位問題，并未涉及多個蛛網(wǎng)結構的合并導致的信號干擾以及多個蛛網(wǎng)結構合并的模型優(yōu)化，這也是該研究下一步的工作。

[1]閆保中, 姜琛, 尹偉偉. 基于RFID技術的室內(nèi)定位算法研究[J]. 計算機仿真, 2010, 27(2)：320～324.

[2] 張健. 基于射頻識別RFID技術室內(nèi)定位系統(tǒng)研究[D]. 廣州：中山大學, 2010.

[3] 李緝熙. 射頻電路工程設計[M]. 北京：電子工業(yè)出版社, 2011:78～80.

[4] 俱瑩. 基于RFID的室內(nèi)定位算法研究[D]. 天津：天津大學, 2010.

[5] 李綱, 張少輝, 唐迪. 基于RFID的蛛網(wǎng)模型定位算法設計[J]. 軟件, 2012, 33(4)：9～12.

[6] 韓江洪, 祝滿拳, 馬學森, 等. 基于RSSI的極大似然與加權質(zhì)心混合定位算法[J].電子測量與儀器學報, 2013, 27(10)：937～943.

[7] Astrid M H. 蜘蛛位置對成功捕獲獵物和球型網(wǎng)圖案的影響(英文)[J]. 動物學報, 2004, 50(4)：559～565.

[8] Ni L M, Liu Y, Lau Y C, et al. LANDMARC: indoor location sensing using active RFID [J]. Wireless Networks, 2004, 10(6)：701～710.

[9] 周玲, 康志偉, 何怡剛. 基于三角不等式的加權雙曲線定位DV-HOP算法[J]. 電子測量與儀器學報, 2013, 27(5)：389～395.

[10] 王勇, 曾慶凱. 一種內(nèi)存錯誤的動態(tài)檢測方法[J]. 計算機應用研究, 2008, 25(5)：1550～1552.

[編輯] 洪云飛

2016-12-29

福建省教育廳科技項目(JAT160506)；武夷學院校科研基金項目(XD201504)。

歐陽林群(1971-)，男，碩士，副教授，現(xiàn)主要從事電子信息、自動控制方面的教學與研究工作，wyolq@foxmail.com。

TP391.44

A

1673-1409(2017)05-0006-05

[引著格式]歐陽林群,阮承治.基于蛛網(wǎng)結構和雙曲線的定位算法[J].長江大學學報(自科版)，2017,14(5)：6～10.