基于非度量多維標度的室內多標簽協同定位算法*

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

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

隨著移動通信與物聯網技術的高速發展,室內定位技術受到人們的廣泛關注[1]。RFID具有讀寫速度快、標簽體積小、價格低廉、部署簡單等優勢,使得RFID定位技術被廣泛應用到物流、倉庫管理、圖書管理等相關應用中,并成為目前室內定位技術的研究熱點[2]。

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

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

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

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

1 測距模型

1.1 室內多徑傳播

在多徑環境下,室內多標簽協同定位算法的場景如圖1所示。

圖1 室內多標簽協同定位場景圖

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

(1)

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

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

(2)

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

1.2 測距誤差模型

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

(3)

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

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

(4)

(5)

e=emultipath+enoise

(6)

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

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

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

圖2 多徑環境下測距誤差的概率分布函數

圖3 不同位置標簽的概率分布函數

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

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

2 基于NMDS的多標簽協同定位

2.1 非度量多維標度-NMDS

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

(7)

2.2 多標簽協同定位算法

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

(8)

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

(9)

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

待定位標簽和閱讀器的位置坐標構成向量X=[xt1,…,xtM,xr1…,xrN]=[x1,…,xn]。

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

(10)

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

(11)

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

(12)

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

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

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

(13)

(14)

(15)

⑦如果STRESS1<ε或者k>kmax時則停止迭代并輸出相對坐標,否則跳轉到第三步繼續迭代,本文中設置ε=10-4,kmax=200。

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

4 仿真分析

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

圖5 定位仿真結果圖

4.1 定位誤差累積分布

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

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

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

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

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

4.2 測距誤差

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

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

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

4.3 待定位標簽數目

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

圖8 不同待定位標簽數目下的平均定位誤差

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

5 結束語

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