基于非度量多維標(biāo)度的室內(nèi)多標(biāo)簽協(xié)同定位算法*

蔣 悅,馬永濤,宮霄霖,劉開華

(天津大學(xué)微電子學(xué)院,天津 300072)

隨著移動通信與物聯(lián)網(wǎng)技術(shù)的高速發(fā)展,室內(nèi)定位技術(shù)受到人們的廣泛關(guān)注[1]。RFID具有讀寫速度快、標(biāo)簽體積小、價格低廉、部署簡單等優(yōu)勢,使得RFID定位技術(shù)被廣泛應(yīng)用到物流、倉庫管理、圖書管理等相關(guān)應(yīng)用中,并成為目前室內(nèi)定位技術(shù)的研究熱點[2]。

根據(jù)定位過程是否需要進(jìn)行距離測量,室內(nèi)定位方法可以分為測距與非測距的定位算法。測距的定位算法包括接收信號強度RSS(Received Signal Strength)[3]、到達(dá)時間TOA(Time of Arrival)[4]、到達(dá)時間差TDOA(Time Difference of Arrival)[5]、到達(dá)相位差PDOA(Phase Difference of Arrival)[6]等算法。常用的非測距算法包括指紋定位法[7]。指紋定位法分為離線階段與在線階段,在離線階段利用人工或機(jī)器采集每個指紋點處接收到的各個基站的無線信號建立離線指紋庫;在線階段將待定位目標(biāo)所接收到的各個基站的無線信號值與指紋庫中數(shù)據(jù)進(jìn)行匹配,從而計算出待定位目標(biāo)的坐標(biāo)[8]。

RFID標(biāo)簽具有價格低、體積小、容易部署等特點使得目前標(biāo)簽定位受到廣泛的關(guān)注[9-11]。文獻(xiàn)[12]提出了一種適用于非視距和多徑環(huán)境的室內(nèi)定位算法,其利用到達(dá)角度AOA(Angle of Arrival)和PDOA有效降低了無源UHF RFID標(biāo)簽的定位誤差。

多維標(biāo)度是一種統(tǒng)計學(xué)方法,哥倫比亞大學(xué)的Shang Y等人首次將多維標(biāo)度算法應(yīng)用到無線傳感器網(wǎng)絡(luò)定位中并提出MDS-MAP定位算法[13]。多維標(biāo)度算法分為度量多維標(biāo)度和非度量多維標(biāo)度。經(jīng)典多維標(biāo)度是度量多維標(biāo)度中的一種。經(jīng)典多維標(biāo)度采用測距的方式來獲取各個節(jié)點之間的距離信息,從而構(gòu)建與各節(jié)點之間的距離呈線性關(guān)系的相似(異)性矩陣。非度量多維標(biāo)度是一種非測距的算法,只要獲得節(jié)點之間距離大小的順序等級關(guān)系便可進(jìn)行定位。

在物聯(lián)網(wǎng)技術(shù)中,目標(biāo)之間在任何地方和時間都可以進(jìn)行相互協(xié)同作用,協(xié)同作用可以顯著提高不同室內(nèi)定位場景中的定位精度[14]。RFID是物聯(lián)網(wǎng)的關(guān)鍵技術(shù),可用于跟蹤和識別待定位目標(biāo)標(biāo)簽。然而標(biāo)簽只能和閱讀器進(jìn)行通信而標(biāo)簽之間無法進(jìn)行通信[6],因此傳統(tǒng)的定位算法一次只能定位一個標(biāo)簽,此外,利用近似方法得到標(biāo)簽之間的距離也會增加定位誤差。由于有源標(biāo)簽成本較高,或者在一些場景中無法布置參考標(biāo)簽,本文給出了一種室內(nèi)RFID多標(biāo)簽協(xié)同定位算法。該算法擬合了在多徑環(huán)境下PDOA算法的測距誤差模型,并充分利用標(biāo)簽之間的信息,即距離差歐氏距離(distance-difference-based Euclidean distance),結(jié)合非度量多維標(biāo)度算法實現(xiàn)多標(biāo)簽定位。仿真結(jié)果表明本文所提算法相比傳統(tǒng)基于最小二乘和經(jīng)典多維標(biāo)度的定位算法具有更高的定位精度。

1 測距模型

1.1 室內(nèi)多徑傳播

在多徑環(huán)境下,室內(nèi)多標(biāo)簽協(xié)同定位算法的場景如圖1所示。

圖1 室內(nèi)多標(biāo)簽協(xié)同定位場景圖

假設(shè)閱讀器的發(fā)射和接收天線為同一天線,則上行鏈路和下行鏈路相同。閱讀器的接收信號為:

(1)

式中:c是光速,N是閱讀器接收到的路徑條數(shù),d和A分別是待定位標(biāo)簽到閱讀器直視路徑的距離和衰減振幅,di和Ai分別是閱讀器接收到經(jīng)過障礙物反射的第i條路徑的長度和衰減振幅。

在自由空間中,直視路徑的信號幅度衰減服從Rice分布[15]。假設(shè)閱讀器的發(fā)射信號為S(t),則閱讀器接收到的信號為:

(2)

式中:n(t)是加性高斯白噪聲。

1.2 測距誤差模型

在室內(nèi)環(huán)境中無線信號的參數(shù)隨距離變化,因此在已知發(fā)送信號的前提下可以通過接收信號的能量、時間以及相位等參數(shù)來進(jìn)行距離估計。根據(jù)所采用無線信號參數(shù)的不同可以分為多種測距方法。TOA法假設(shè)電磁波以光速傳播,接收信號的到達(dá)時間與距離呈線性關(guān)系。RSS法以電磁波在自由空間傳播的Friis公式為基礎(chǔ),進(jìn)一步通過對數(shù)路徑損耗模型,得到接收信號強度值與距離之間的對數(shù)關(guān)系。PDOA法利用兩個不同頻率的信號在接收端的相位差與距離呈線性關(guān)系的原理進(jìn)行測距。本文采用PDOA法測距[16]:

(3)

式中:閱讀器發(fā)射頻率為f1和f2(f1≠f2)的連續(xù)波,對應(yīng)的閱讀器接收到相位分別是φ1和φ2。

由于室內(nèi)環(huán)境中無線信號傳播會受到多徑、非視距及噪聲的影響,使得測距存在誤差,距離測量模型為:

(4)

(5)

e=emultipath+enoise

(6)

式中:emultipath是多徑造成的測距誤差,enoise是高斯白噪聲造成的測距誤差。我們仿真了在多徑環(huán)境下的測距誤差的概率分布函數(shù),并利用高斯分布曲線擬合仿真的數(shù)據(jù)。

將閱讀器放在(0,0),待定位標(biāo)簽位置為(2.5 m,7.5 m),在多徑環(huán)境下,利用PDOA法得到的距離誤差概率分布曲線及其擬合曲線如圖2所示,測距誤差可以看做是均值為0的高斯白噪聲。

將閱讀器放在(0,0),在場景中4個待定位標(biāo)簽的位置分別為(1,1),(2,8),(9,1),(5,5),單位是米(m),它們的距離誤差概率分布曲線如圖3所示。

圖2 多徑環(huán)境下測距誤差的概率分布函數(shù)

圖3 不同位置標(biāo)簽的概率分布函數(shù)

為了進(jìn)一步驗證PDOA算法在多徑環(huán)境下的測距誤差模型,我們采用矢量網(wǎng)絡(luò)分析儀(Rohde&Schwarz ZNB8)和兩個Laird S9028PCL圓極性寬帶RFID面板天線進(jìn)行實驗。選擇10個頻點,從920 MHz到924.5 MHz,步長為0.5 MHz,兩個閱讀器之間的距離是4.2 m。實驗結(jié)果如圖4所示,從圖中可以看出,測距誤差曲線接近高斯分布曲線,這兩條曲線在其他距離上也很相似。

圖4 實驗測距誤差和高斯分布對比圖

2 基于NMDS的多標(biāo)簽協(xié)同定位

2.1 非度量多維標(biāo)度-NMDS

利用節(jié)點間距離的大小關(guān)系作為相似性矩陣[Pij],運用非度量多維標(biāo)度算法可以從相似性矩陣中求得各個節(jié)點的相對坐標(biāo),由于節(jié)點之間無需進(jìn)行測距而只需要獲得節(jié)點距離的大小關(guān)系,因此非度量多維標(biāo)度具有很好的誤差容忍性。非度量多維標(biāo)度的目的是使脅強系數(shù)STRESS1最小,在得到節(jié)點的相對坐標(biāo)之后再利用錨節(jié)點通過坐標(biāo)系轉(zhuǎn)換算法得到多維空間中待定位節(jié)點的絕對坐標(biāo)值。非度量多維標(biāo)度用脅強系數(shù)STRESS1來表示節(jié)點之間的距離大小關(guān)系與相異性矩陣的擬合程度,脅強系數(shù)表示為[17]:

(7)

2.2 多標(biāo)簽協(xié)同定位算法

本文采用待定位標(biāo)簽之間的距離差歐氏距離來表示相似性矩陣的值,假設(shè)待定位標(biāo)簽之間的距離差歐氏距離與待定位標(biāo)簽間真實距離之間呈正相關(guān)[18]。在場景中放置M個待定位標(biāo)簽,N(N≥4)個閱讀器。第i個標(biāo)簽的坐標(biāo)為xti=[xti,yti]T,i=1,…,M;第j個閱讀器的坐標(biāo)為xrj=[xrj,yrj]T,j=1,…,N,n=N+M。因此得到第i個待定位標(biāo)簽和第j個閱讀器之間的距離為:

(8)

由于閱讀器的位置已知,每個閱讀器到其他閱讀器的距離值所構(gòu)成的向量可以通過閱讀器的坐標(biāo)計算得到:

(9)

式中:i,j=1,…,N。

待定位標(biāo)簽和閱讀器的位置坐標(biāo)構(gòu)成向量X=[xt1,…,xtM,xr1…,xrN]=[x1,…,xn]。

標(biāo)簽i與各個閱讀器之間的距離值構(gòu)成的向量為[dtir1,dtir2,…,dtirN],標(biāo)簽j與各個閱讀器之間的距離值所構(gòu)成的向量為[dtjr1,dtjr2,…,dtjrN],則標(biāo)簽i與標(biāo)簽j之間的距離差歐氏距離為:

(10)

式中:i,j=1,…,M。同理我們可以得到標(biāo)簽i和閱讀器j之間的距離差歐式距離為:

(11)

式中:i=1,…,M,j=1,…,N。閱讀器i和j之間的距離差歐式距離為:

(12)

式中:i,j=1,…,N。利用其構(gòu)建相異性矩陣P作為非度量多維標(biāo)度算法的輸入:

再通過非度量多維標(biāo)度算法得到每個待定位標(biāo)簽與閱讀器之間的相對坐標(biāo),具體算法流程分為以下7個步驟:

②對第k次迭代得到的待定位標(biāo)簽的相對坐標(biāo),計算每個節(jié)點對之間的歐氏距離:

(13)

(14)

(15)

⑦如果STRESS1<ε或者k>kmax時則停止迭代并輸出相對坐標(biāo),否則跳轉(zhuǎn)到第三步繼續(xù)迭代,本文中設(shè)置ε=10-4,kmax=200。

本文中我們選用經(jīng)典多維標(biāo)度的方法來確定初始坐標(biāo)X0,上述算法中設(shè)置kmax是因為非度量多維標(biāo)度是一個經(jīng)過多次迭代對脅強系數(shù)STRESS1取最小值的過程,因此由于初始坐標(biāo)的選取存在誤差,算法可能會落入到局部最小值中,因此kmax的設(shè)定可以避免程序出現(xiàn)死循環(huán)。此時我們得到每個待定位標(biāo)簽與閱讀器之間的相對坐標(biāo),由于閱讀器坐標(biāo)已知,最后通過坐標(biāo)系轉(zhuǎn)換算法得到每個待定位標(biāo)簽的絕對坐標(biāo)。

4 仿真分析

本文仿真的室內(nèi)定位場景設(shè)置在10 m×10 m的房間內(nèi),4個閱讀器分別放置在房間的四個角,設(shè)其坐標(biāo)分別為(0,0)、(0,10)、(10,0)、(10,10)。M個待定位標(biāo)簽隨機(jī)分布在房間內(nèi),假定所有的標(biāo)簽都在閱讀器的通信范圍內(nèi)。測距誤差e的方差取值為2 m2,在定位場景中隨機(jī)散落10個待定位標(biāo)簽,采用本文所提的基于NMDS的多標(biāo)簽協(xié)同定位算法進(jìn)行MATLAB仿真,其定位結(jié)果如圖5所示。

圖5 定位仿真結(jié)果圖

4.1 定位誤差累積分布

為了測試本文提出的多標(biāo)簽協(xié)同定位算法的定位精度,使用累積分布函數(shù)CDF(Cumulative Distribution Function)曲線來對比多標(biāo)簽協(xié)同定位算法、最小二乘定位算法和經(jīng)典多維標(biāo)度定位算法的定位精度。假設(shè)測距誤差e的方差為2 m2,場景中有30個待定位標(biāo)簽,進(jìn)行100次仿真實驗。仿真結(jié)果如圖6所示。

圖6 定位誤差累積分布曲線

從圖6中可以看出本文提出的算法在性能上整體優(yōu)于經(jīng)典多維標(biāo)度算法和最小二乘算法,本文提出算法的定位誤差大約以80%的概率低于1.8 m,而最小二乘算法和經(jīng)典多維標(biāo)度定位算法的定位誤差分別以80%的概率低于2.2 m和2.5 m。本文所提算法的時間復(fù)雜度主要集中在PAV算法的迭代上,PAV算法的復(fù)雜度為O(MN),其中M是待定位標(biāo)簽個數(shù),N是閱讀器個數(shù)。在仿真實驗時,本文所提算法平均定位一個點的時間為5×10-3。

最小二乘算法每次只可以獲得1個待定位標(biāo)簽的位置,實際定位次數(shù)為30×100=3 000次;而本文所提算法只需要進(jìn)行100次非度量多維標(biāo)度計算,每次計算都可同時獲得30個待定位標(biāo)簽的位置。此外,最小二乘算法只是利用了標(biāo)簽和閱讀器之間的距離信息,而本文所提算法加入了標(biāo)簽之間的距離信息,并提升了定位精度,這表明多標(biāo)簽的協(xié)同作用能夠有效提升定位精度。

經(jīng)典多維標(biāo)度算法和本文所提算法均可同時獲得多個標(biāo)簽的位置,經(jīng)典多維標(biāo)度需要利用待定位標(biāo)簽之間的距離值,實際不可直接測得,需要通過近似擬合的方法得到,而本文所提算法無需測得標(biāo)簽之間的距離,直接在相似矩陣中引入了距離大小的順序等級關(guān)系,提高了算法的誤差容忍性,同時使用迭代計算降低了定位誤差。

4.2 測距誤差

為了測試本文提出的多標(biāo)簽協(xié)同定位算法在不同室內(nèi)環(huán)境下的定位精度,令測距誤差的方差從0.5 m2變化到3 m2。在場景中放置30個待定位標(biāo)簽,進(jìn)行100次仿真實驗,對比多標(biāo)簽協(xié)同定位算法、最小二乘算法和經(jīng)典多維標(biāo)度算法的平均定位誤差,仿真結(jié)果如圖7所示。

圖7 不同測距誤差方差下的平均定位誤差

從圖7中可以看出,在不同的測距誤差下多標(biāo)簽協(xié)同定位算法的平均定位誤差均小于經(jīng)典多維標(biāo)度算法和最小二乘算法,即本文所提算法在不同室內(nèi)環(huán)境下的定位效果都比其他兩種定位算法好。在測距誤差的方差為3 m2,本文提出的多標(biāo)簽協(xié)同定位算法的平均定位誤差比最小二乘算法降低約0.3 m,比經(jīng)典多維標(biāo)度算法降低約0.4 m。

4.3 待定位標(biāo)簽數(shù)目

為了測試本文提出的多標(biāo)簽協(xié)同定位算法在不同數(shù)量待定位標(biāo)簽數(shù)目下的定位精度,令待定位標(biāo)簽數(shù)目分別為20、25、30、35、40、45、50,假設(shè)測距誤差e的方差為2 m2,進(jìn)行100次仿真實驗,對比多標(biāo)簽協(xié)同定位算法、最小二乘算法和經(jīng)典多維標(biāo)度算法的平均定位誤差,仿真結(jié)果如圖8所示。

圖8 不同待定位標(biāo)簽數(shù)目下的平均定位誤差

從圖8可以看出,在待定位標(biāo)簽數(shù)目不同的情況下,多標(biāo)簽協(xié)同定位算法的平均定位誤差均小于經(jīng)典多維標(biāo)度算法和最小二乘算法。本文所提算法和最小二乘法的平均定位誤差均不會隨著待定位標(biāo)簽數(shù)目的改變而產(chǎn)生很大波動,本文所提算法的平均定位誤差約為1.24 m,最小二乘算法的平均定位誤差約為1.5 m。而經(jīng)典多維標(biāo)度算法的定位精度會隨著待定位標(biāo)簽數(shù)目的增加而降低,在待定位標(biāo)簽數(shù)目為20時的平均定位誤差約為1.65 m。

5 結(jié)束語

本文提出了一種基于非度量多維標(biāo)度的室內(nèi)RFID多標(biāo)簽協(xié)同定位算法,利用PDOA法擬合在多徑環(huán)境下的測距誤差,將標(biāo)簽及閱讀器之間的距離大小關(guān)系和非度量多維標(biāo)度算法結(jié)合,實現(xiàn)多標(biāo)簽同時定位。該算法主要包括以下三個步驟:首先根據(jù)標(biāo)簽及閱讀器的距離差歐氏距離構(gòu)建相似性矩陣,然后利用非度量多維標(biāo)度算法計算出標(biāo)簽與閱讀器的相對坐標(biāo),最后利用已知的閱讀器坐標(biāo),通過坐標(biāo)系轉(zhuǎn)換算法得到各標(biāo)簽的絕對坐標(biāo)。仿真結(jié)果表明,該算法在測距誤差不同和待定位標(biāo)簽數(shù)目變化的情況下都具有較高的定位精度。