基于非度量多维标度的室内多标签协同定位算法*

蒋 悦,马永涛,宫霄霖,刘开华

(天津大学微电子学院,天津 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法拟合在多径环境下的测距误差,将标签及阅读器之间的距离大小关系和非度量多维标度算法结合,实现多标签同时定位。该算法主要包括以下三个步骤:首先根据标签及阅读器的距离差欧氏距离构建相似性矩阵,然后利用非度量多维标度算法计算出标签与阅读器的相对坐标,最后利用已知的阅读器坐标,通过坐标系转换算法得到各标签的绝对坐标。仿真结果表明,该算法在测距误差不同和待定位标签数目变化的情况下都具有较高的定位精度。