一种基于视距路径识别的设备无关室内定位算法

严淑萍，段桂华，张士庚

(中南大学信息科学与工程学院,湖南 长沙 410083)

1 引言

近年来，随着物联网的发展和智能终端设备的普及，无线室内定位技术成了人们研究的焦点[1]。在很多领域，特别是在基于位置的服务LBS(Location Based Services)中，无线室内定位技术是一种必不可少的支撑技术。比如，在智能仓库中，人们需要准确了解货物的存放位置，以便对货物进行高效管理[2]。在大型商场或者博物馆里，人们可以通过定位技术来进行智能导购或者导航[3]。在老人健康护理应用中，人们需要实时对老人的目标位置进行监测，以便判断目标对象是否处在正常状态。无线室内定位技术在其它很多方面也有着广泛的应用，如机器人室内导航、室内游戏、智能人机交互系统等。由于无线室内定位技术的重要性，特别是随着Wi-Fi设备的普及和广泛部署，近年来人们提出了很多基于Wi-Fi的室内定位技术，如文献[4-8]。

基于Wi-Fi的室内定位方法主要可以分为两种：基于设备的定位方法(也称为主动式定位)和设备无关的定位方法(也称为被动式定位、非绑定式定位)，这两种定位方法的主要区别在于定位过程中是否需要目标对象主动参与其中。主动式定位方法需要目标对象携带某种设备，所携带的设备能够与监测设备进行数据通信，并根据信号或相位的变化来推断目标对象所处的位置，精度最高可达0.5 m。而被动式定位则根据目标本身对无线通信链路信号产生的干扰，通过测量受干扰链路上的信号衰减程度来判断目标的位置。基于信号强度信息RSSI(Received Signal Strength Information)设计分析并部署的被动式定位系统Nuzzer[8]，利用概率统计技术实现了室内多径环境下对单目标的定位，平均误差可控制在2 m以内。

已有的基于Wi-Fi的被动式定位需要事先进行训练，例如，美国微软研究院在RADAR系统[9]中首次提出了基于指纹匹配的定位方法。该系统首先在离线阶段采集特定参考点与固定的接入点AP(Access Point)之间的信号强度，并将信息存入数据库中，然后在实时定位阶段根据RSSI在数据库中进行信息匹配以计算目标的位置。Youssef等人[10]在Horus系统中进一步提出利用信号强度的分布信息作为指纹来提高定位精度。文献[11]提出了分层次细化区域的方法，通过测量少数的参考点信息以实现更准确的定位。文献[12]通过在不同参考位置之间对信号强度进行插值来重建指纹数据库，并利用贝叶斯估计算法来提高定位精度。但是，这些方法均需要在初始状态(即监测区域没有目标)时采集参考点的信息进行离线训练，其性能容易受室内复杂多变的环境干扰，从而导致定位精度随时间下降。

因此，为避免定位在训练阶段产生额外的人力开销，本文提出了一种新的设备无关定位算法。我们首先将监测区域划分成若干个大小相同的小方格，并在区域周围部署多组无线收发设备，任意一组收发节点间都可以互相通信。假设我们事先能够识别某条通信链路是否为视距LoS(Line of Sight)路径，若为非视距则说明该链路上存在目标对象，通过计算该链路的菲涅耳区域找出其对应的小方格并为它们投上一票(即将小方格的值加1)。通过判断监测区域内所有通信链路，最终获得票数最多的小方格(即累计值最大的小方格)为目标最可能的位置。本算法基于视距路径识别的基础，根据菲涅耳区域对链路产生的影响来确定目标位置，因此无需事先进行离线训练来获取网络的初始状态，具有较强的实时性。

本文组织如下：第2节介绍相关工作；第3节为核心内容，详细介绍了本文提出的算法；第4节为仿真结果；第5节通过真实实验来验证本文所提算法的有效性；最后一节总结全文。

2 相关工作

被动式定位以其无需携带任何设备的特点成为专家学者的研究重点。例如，Han等人[13]利用无线信号的衰减变化来判断室内人员的活动状态并检测是否有人摔倒的情况。Zhou等人[14,15]利用目标对象的随机运动来增加信号传播路径的不确定性，以此来识别视距与非视距，用于实现目标对象的定位。文献[16]利用信号强度的均值变化情况来对目标对象的位置进行成像定位。Sen等人[17]通过在室外和室内的离线训练中识别不受室内多径影响的信道，利用这些信道上的信道状态信息CSI(Channel State Information)实现室内目标定位。文献[18]利用信道状态信息的时域变化，提出了基于距离估计的定位算法。然而，这些被动式定位算法均需要事先进行训练来获取定位的初始状态，会产生额外的采集开销，并且容易受到复杂室内环境的影响。

主动式定位通常需要被测目标携带某种设备来实现目标定位。文献[19]需要测试者随身携带移动设备，借助于设备的惯性传感器来实时记录测试者行走过程中的方向及运动速度，以此来定位目标的位置。Wu等人[20]提出一个基于室内现成的Wi-Fi基础设施与移动手机集成的定位系统，该系统将用户室内日常行走路线及对应的RSSI信息作为指纹信息，利用手机传感器与用户行为构建一个室内地图，通过指纹信息匹配来实现目标的定位。Cao等人[21]提出了基于Android平台的人体跌倒检测系统。该检测方法需要被测目标随身携带智能手机，利用突然大幅度动作对手机的加速度传感器会产生较大的变化度值这一现象来进行人员的安全检测。这些需要目标对象携带某种设备的定位技术，在很多场合中并不适用,比如患有健忘症的老人，又或者在某些需要监测有无人员闯入特定区域的场景中，因此其应用具有一定的局限性。

3 基于视距路径识别的定位算法

3.1 算法思想

Figure 1 Target in one link图1 目标在一条通信链路上

Figure 2 Target in two links图2 目标在两条通信链路上

首先，我们在监测区域周围部署多组无线收发设备。当有目标出现在一组收发设备的直线上时，我们认为此时的通信链路为非视距，如图1所示。那么，我们只需要通过两条非视距的通信链路，并找出这两条非视距路径经过的重叠区域，便可以确定目标所在的位置，如图2所示。但是，由于视距并不一定只是在收发端两个节点的直线上，也就是说，目标在收发端两节点所形成的某个区域内均会对通信链路产生影响。因此，我们在此算法中引入了菲涅耳区域的概念(在接下来的3.3节会详细介绍)，结合菲涅耳区域对链路产生的影响来实现目标的定位。由于该算法是基于视距路径识别，然而视距的识别并不一定能够达到完全准确，于是我们需要加入多组节点，利用节点的冗余性来提高定位精度。

3.2 视距路径的识别

目前已经有一些工作能够完成视距路径的识别[14,22]。本文采用PhaseU方法[22]来识别视距路径，该方法是利用无线设备多天线的相位差信息来实现视距路径识别的。由于室内多径的影响，无论信号传播路径为视距或非视距，接收端在接收信号的过程中均会产生不同程度的相位偏移，为了解决这种由接收端引起的测量误差问题，本文引入了一个新的信道相位特征——双天线相位差，通过双天线相位差来消除相位测量误差，保留反映多信道状态特征的信息。PhaseU识别算法主要分为两阶段：离线训练阶段——在进行视距路径识别之前，先分别在有目标和没有目标的监测区域采集信息，计算在不同环境下天线相位的变化范围，训练出一个能够分离出视距与非视距路径的阈值；视距路径识别阶段——实时计算双天线相位差，并用二元假设检验来判断该相位差属于视距或非视距的相位差范围。

3.2.1 信道状态信息

信道状态信息(CSI)解决了信号强度信息不稳定、易受到多径影响的局限性。利用现有的Intel 5300无线网卡和商用支持802.11n的AP，可以获得信道状态信息。每个CSI表示的是各个子载波的振幅和相位：

H(fk)=‖H(fk)‖ej∠H(fk)

(1)

其中，H(fk)表示载波中心频率fk的CSI，‖H(fk)‖和∠H(fk)分别表示其振幅和相位信息。

3.2.2 提取相位信息

(2)

3.2.3 视距识别

通过获取M个数据包的一系列CSI样本，本文提出了利用ρ因子来表示相位的变化值：

(3)

然后利用二元假设检验LoS(Η0)和NLoS(Η1)，即:

(4)

其中ρth为阈值。

PhaseU的总体流程如图3所示。

Figure 3 Flow chart of PhaseU图3 PhaseU流程图

3.3 菲涅耳区域

当收发节点之间有障碍物时，可用菲涅耳区域来解释路径差函数的绕射耗损现象。菲涅耳区域是在收发天线之间，由电波的直线路径与折线路径的行程差为nλ/2的折点(反射点)形成的、以收发天线位置为焦点、以直线路径为轴的椭球面，如图4所示。其中λ表示信息的波长，n为自然数。n=1的区域(图中的椭圆形区域)是对信号有主要贡献的区域，称为第一菲涅耳区域[23]。由于第一菲涅耳区域对信号变化比较敏感，因此本文中考虑的均是第一菲涅耳区域。

Figure 4 Target in Fresnel zone图4 目标在菲涅耳区域内

当目标对象位于收发端链路上的第一菲涅耳区域内时，权值为1，否则为0。

(5)

其中，dit表示接收端i到目标t之间的距离，djt表示发送端j到目标t的距离，d代表接收端i到发送端j之间的距离，ωij是指在第i条链路上方格j的权重值，λ指波长，此时考虑的是第一菲涅耳区域，因此n=1。

3.4 算法描述

算法描述如下：

步骤1将监测区域划分为若干个小方格，每个方格的初始值设为0。

步骤2判断接收端之间的通信链路是否为视距路径。

步骤3若为非视距，则计算该链路的菲涅耳区域，将菲涅耳区域内所有的方格值加1。

步骤4遍历所有的通信链路，找出拥有最大值的方格，则该方格的位置为目标对象最可能的位置；如若有多个方格，则取多个方格位置的中心。

假设在监测区域周围部署了4个节点，并将区域划分为3×3的方格，如图5所示，已经知道链路AP1→AP4和链路AP2→AP3为非视距，则目标定位过程如图5所示。

Figure 5 One intsance of the algorithm图5 算法实例图

算法伪代码如下所示：

将检测区域所划分小方格的初始值设为0；/*如图5a所示*/

Fori=1 toN-1 do

Forj=i+1 toNdo

判断链路L(i,j)是否为NLoS，若为NLoS则将NLoS置为1；

If(NLoS==1)do

Forgrid=1 toMdo /*M表示划分的方格个数*/

判断该方格是否在链路的菲涅耳区域内，若是，则将该方格的值加1；/*如图5b和图5c所示*/

END

END

END

END

找出拥有最大值的方格，该方格对应的位置则为目标对象最可能的位置，若有多个方格，则取多个方格的中心位置。

4 仿真实验

在本文中，我们在能够识别视距路径的基础之上，根据第一菲涅耳区域对链路的影响实现目标的定位。已有工作PhaseU[22]通过分析多天线的相位差来识别视距路径,可以达到94%的准确率，因此本文主要考虑的是方格大小、视距路径判断率及无线节点的个数对本文定位算法的影响。通过测量任意节点链路之间的信道状态信息判断是否为视距环境，若检测到链路间有障碍物阻拦，就认为目标对象有可能位于该链路上的第一菲涅耳区域中，则将此链路的第一菲涅耳区域上方格的值加1，通过遍历所有的链路，值最大的方格对应为目标最可能的位置。我们在PhaseU的基础上，利用Matlab进行仿真实验来分析方格大小、视距判断的准确率以及无线节点个数对定位精度的影响。

4.1 不同的方格大小对定位精度的影响

假设在监测区域周围部署了10个无线节点，并且可以准确识别每组收发节点之间的视距路径。现在我们来考虑不同的方格大小g对定位精度的影响。在固定大小的监测区域内，若g的取值越小，则可划分的格子个数就越多，因此计算量越大，定位也越精确。我们在0.1 m～0.5 m的范围内对g的大小分别取值进行实验，在不同取值下，方格大小所产生的平均定位误差如图6所示。

Figure 6 Effect of the size of grid on localization accuracy图6 方格的大小对定位精度的影响

根据图6可以看出，格子宽度的大小不同，定位精度也会产生一定的变化。方格宽度越小，定位误差也越小。当方格大小设为0.5 m*0.5 m时，平均误差为0.74 m，当方格为0.1 m*0.1 m时，平均误差降至0.27 m。然而，当监测区域固定时，方格越小则可划分的个数越多，所产生的计算开销也越大，因此在设定g的大小时,除了定位应在可接受的误差范围之内外，还应考虑算法的计算代价。我们认为当g的取值为0.2 m时，该算法的性能最佳，平均误差为0.32 m，相比利用椭圆模型的射频层析成像RTI(Radio Tomographic Imaging)算法，平均误差降低了0.18 m，定位更精确。

4.2 视距识别正确率对定位精度的影响

本文的定位算法基于视距路径的识别，当收发端链路节点之间为非视距时，则认为目标可能在该链路的第一菲涅耳区域内，因此视距路径是否能够准确辨别是实现室内目标定位的关键因素。我们仍然假设在监测区域周围部署了10个无线收发节点，并且将方格的大小设为0.2 m×0.2 m，通过仿真实验，我们结合不同的视距识别率对其影响进行了分析，其关系如图7所示。

Figure 7 Relationship between LoS identification rate and localization accuracy图7 视距识别率与定位精度的关系

从图7可以发现，视距路径的识别率也会对目标的定位精度产生影响。视距路径识别越准确，则定位也越准确。当视距的识别准确率达到95%时，平均误差为0.47 m，因此视距路径的识别率也是室内定位的关键因素。

4.3 通信节点数量对定位精度的影响

在室内定位系统中，室内部署的节点个数也会对定位精度产生影响。一般来说，节点部署越密集，定位精度也越高；反之，定位精度也会因节点个数的减少而下降，如图8所示。在同等实验环境下，随着节点数量的增加，产生的节点费用会增多，计算开销也会越大，如图9所示。

Figure 8 Effect of the number of nodes on accuracy图8 节点个数对精度的影响

Figure 9 Running time cost vs. the number of nodes图9 不同节点个数产生的计算时间

5 实际实验

为了验证本文算法的有效性，本文进行了相关实验。实验使用无线路由器作为数据发送端，如图10所示，用安装有Intel 5300网卡的笔记本作为接收端。实验环境部署在计算机楼一个空旷的实验室，监测区域为3.5 m×3.5 m，监测区域周围共部署了10个无线节点，每个节点之间的距离为0.2 m。我们测量任意节点链路之间的信道状态信息并利用PhaseU方法判断是否为视距路径，若检测到链路间有障碍物阻拦，就认为目标对象有可能位于该链路上的第一菲涅耳区域(利用式(5)来计算链路的菲涅耳区)，则将此链路的第一菲涅耳区域对应方格的值加1，图像中方格的值越大，表示目标在该区域的可能性越大。实验中利用商用Intel 5300网卡收集CSI信息，如图11所示，利用Matlab对实验数据进行处理，实验结果如图12和图13所示。图12为实验场景中目标所在的位置，图13通过采集监测区域内的信息，利用Matlab对数据进行处理后反向推出的目标位置。通过对人体的定位，平均误差控制在0.5 m范围内，基本实现了目标对象的室内定位。

Figure 10 Transmitter图10 数据发送器

Figure 11 CSI information collection图11 采集CSI信息

图12和图13为单个目标的定位结果，在本文中，考虑的均是对单个目标的定位。然而，在实际场景中，监测区域内可能不仅仅只存在一个目标，目前已有相关工作解决了多目标的定位，文献[24]提出了一个视距无线电图匹配的MODLOC方法，该方法保留视距路径的节点信号，根据视距信息构建一个视距无线电地图。

Figure 12 Location of the target in the experiment图12 实验场景中目标所在位置

Figure 13 Possible location of the target图13 实验结果中目标可能出现的位置

在实现目标定位之前，MODLOC首先需要在监测区域内对多个参考点位置进行初始信息采集，利用频率分集来消除多径信号的影响，然后将定位信息与初始状态信息进行比较来实现多目标的定位。文献[25]利用信号在传输过程中遇到目标会发生反射这一现象来实现多目标的定位。接收端接收到从人体反射回来的无线信号后，通过相应算法将信号传输时间转换成人体各部分的距离信息。当监测区域部署多组收、发装置时，如果区域内存在多个目标，根据其反射信息的交叉区域，可以完成多目标的定位。在接下来的工作中，我们将考虑监测区域内存在多目标的情况，并对多个目标对象进行定位。

6 结束语

本文基于视距路径识别提出了一个新的设备无关定位算法，其优点是无需进行离线训练，节省了人力开销，并且具有一定的实时性。其次，本文算法结合菲涅耳区域分析了目标在该区域时对通信链路产生的影响，分析了不同方格的大小与视距路径识别率对定位精度的影响。最后通过仿真和真实实验验证了本文算法的有效性，并且由于其不需要目标携带任何设备，在紧急情况或光线不明的环境下均可以使用，具有广阔的应用前景。