多传感器辅助的WiFi 信号指纹室内定位技术∗

石 柯, 宋小妹, 王信达, 呼文彪

(华中科技大学 计算机科学与技术学院,湖北 武汉 430074)

成熟的室外定位和基于位置的服务(location-based service,简称LBS)技术的兴起,在方便人们生活的同时,加大了人们对于定位服务的依赖.然而到目前为止,室内环境中还没有成熟和广泛适用的定位技术.针于室内环境,人们相继提出了使用超声波、红外线、蓝牙等技术的一系列定位方法,但其应用都有严重的局限性,难以达到室内定位和导航的要求.目前,大型公共场所几乎已经全面覆盖WiFi 网络,这给室内定位技术带来新的契机.WiFi 信号在传播过程中强度会逐渐减弱,根据信号强度与传播距离之间的数学模型,通过测量信号的强度可计算得到接入点与目标之间的距离,再根据三边测量法可得到目标位置.但这种方法只有在视距、无障碍、无反射等良好的环境下才能达到较高的精度.室内环境难以满足这种要求,因此其定位效果不甚理想.

考虑到实际的室内环境难以建立通用的信号强度与距离之间的数学模型[1],人们提出了基于经验的信号指纹方法.在离线阶段,先对场景进行勘测,即在各个参考点(reference point,简称RP)进行采样,得到参考点的位置特征(信号指纹),并建立位置-指纹数据库;在定位阶段,将目标测得的信号指纹与数据库存储的数据进行匹配,得到匹配度较高的参考点位置,以此确定目标位置.在此方法中,WiFi 信号强度特征RSSI(received signal strength indication)常常被用作位置指纹.鉴于室内环境复杂多变,无线信号传播易受反射、阴影衰落(shadowing)、多径效应(multipath effect)等因素的影响,离线阶段采集的信号指纹和在线阶段获取的RSSI 数据可能存在偏差,会导致位置匹配出现较大误差.因此,为进一步提高室内定位的精度,并应对环境变化带来的不利影响,本文提出了多传感器辅助的WiFi 指纹定位方法,在记录WiFi 信号强度的同时,利用智能设备内置的加速计、陀螺仪等多种传感器预估用户移动轨迹信息,将轨迹信息跟信号指纹信息按一定权重结合起来建立综合概率模型,得到各个参考点的综合匹配概率,从而提高位置匹配的精度.

1 相关工作

最早提出的信号指纹定位模型RADAR[2,3]是一个基于确定性匹配策略的系统.在离线阶段,目标和基站的时钟进行同步;目标在各个参考点发射信号,同时记录时间、参考点坐标和身体朝向;各基站接收到信号,记录下接收时间、基站自身编号和信号强度;基于同步的时钟,将参考点坐标和各基站接收到的信号强度关联起来,以此为基础建立指纹数据库.在实时定位阶段,将各基站接收到的信号强度信息与数据库中存储的信息进行匹配,根据K最近邻(Knearest neighbor,简称KNN)算法找到K个指纹最相似的参考点,对这K个参考点坐标取均值得到定位结果.

另一个典型的指纹定位系统是Horus[4],与RADAR 不同的是,在离线阶段,Horus 让基站发送信号,在参考点接收信号,信号传播方向正好相反,但这不会影响定位精度[2].另外,Horus 对RADAR 进行了改进,使用基于统计的方法进行位置匹配,在指纹数据库中建立指纹的高斯分布;在定位阶段,以指纹匹配概率作为各参考点权重计算定位结果.

随着手机和平板电脑等智能设备计算性能的改进和集成传感器种类的增多,GSM、FM、地磁场等信息也被用来进行定位.He 等人使用GSM 信号作为位置指纹[5],定位精度达到了4m,对楼层的识别正确率达到60%.文献[6,7]使用FM 信号强度进行定位,其中,文献[6]达到了3m 左右的精度,已接近WiFi 定位的精度.利用室内环境对于地磁场的影响,文献[8]将地磁场作为位置指纹,将定位精度提升到1m 左右.但该方法需要进行大量的指纹勘测,且需要用户佩戴专用硬件设备,因此不利于普及使用.为了减少离线阶段的工作量,Yoon 等人提出了基于RM 信号的指纹定位技术ACMI[7].由于RM 信号进入室内的主要途径是门窗,因此根据建筑平面图即可得到室内的信号分布,无需进行人工采样.但该方法的精度并不理想,在使用8 个FM 基站的情况下,ACMI 只能达到6m 的平均精度.因此,ACMI 只适合门窗较多且对定位精度要求不高的环境.

目前,智能手机基本都集成了加速计和陀螺仪等传感器,能够实现基于惯性导航(inertial navigation system,简称INS)原理的PDR(pedestrian dead reckoning),但存在较大的距离(步数)累计误差.文献[9]将PDR 和WiFi 指纹定位结合起来,使用粒子滤波器,利用传感器数据来平滑WiFi 信号指纹,使用Kalman 滤波器,利用WiFi 指纹定位的轨迹来减小PDR 过程中的漂移误差,最终达到了1.53m 的定位精度.但由于粒子滤波器计算量大,且耗费时间长,因此不适用于智能手机上的实时定位.为了实现实时定位并减小PDR 定位过程中的累积误差,Chen 等人利用传感器数据识别转向、门、楼梯等作为地标[10],为重新启动PDR 算法提供更准确的新起点;为了减小计算成本,采用轻量级的Kalman 滤波器将PDR 定位与WiFi 定位结合起来建立模型,其平均定位精度达到了1m.在实际环境中,准确的RSSI 位置测量模型和随机噪声信号的统计特性难以得到,使得Kalman 滤波器在实际应用中存在局限性.Deng 等人将PDR 和WiFi 定位结果用扩展Kalman 滤波器(EKF)结合起来[11],在WiFi 定位阶段,采用核密度估计方法动态地测定噪声;在PDR 定位阶段,采用另一个EKF 将陀螺仪与加速度计的数据结合起来测定行人的前进方向.与单独使用PDR 定位方法和WiFi 定位方法相比,大幅度提高了定位精度.在此基础上,文献[12]除了在定位阶段融合了门、楼梯等地标信息,用以重新校准定位结果之外,在PDR 定位时,也用EKF将陀螺仪、加速度计、磁力计和地标的数据融合起来测定航向,并在WiFi 定位阶段又提出了定位可信域来检测RSSI 测量的异常值,以提高定位精度.结果表明,该方法90%的定位精度达到了1.35m.上述算法在离线阶段均需进行大量的人工测量工作,为了减少离线阶段的工作量,如何利用用户的移动性实现无需人工勘测的室内定位,成为研究的热点.在WILL 系统[13]中,测量人员携带手机在不同的房间穿梭走动,手机同时对信号指纹和运动数据进行测量.指纹信息进行聚类生成虚拟房间,分析运动数据可得出虚拟房间之间的可达性,从而形成逻辑平面图.逻辑平面图与建筑的物理平面图进行匹配,即可得到各个房间的指纹信息.该方法建立的指纹数据库可以实现房间级别的定位精度.文献[14]中提出了基于群智感知的室内定位算法.该算法不需要用户显式地参与定位,采用NSAC(normalized auto-correlation-based step counting)和增强粒子滤波器实现了设备位置无关的运动估计,即便设备位于口袋、背包,其运动方向与设备朝向不一致,依然可以进行定位.

此外,尽管基于RSSI 指纹的室内定位技术可以达到米级的定位精度,但在复杂场景中,由于多径效应等多因素的影响,其性能将会急剧下降.为实现鲁棒性更好的定位,CSI(信道状态信息)作为一种细粒度的信道评估指标被应用到室内定位中,以减少多径效应带来的干扰.CSI 携带更丰富的反应信道状态和特性的信息,能够直接区分直接路径和反射路径.由于原始CSI 存在很多冗余信息,不能直接进行特征提取,可以采用Hampel 滤波器[15]对原始信号进行滤波,采用线性变换[16]消除随机相位噪声的影响以及同步误差.文献[17]采用CSI 作为指纹,建立CSI 值和距离关系的数学模型,在定位阶段,寻找3 个距离最近的信号值,采用三角测量方法进行目标的确定.文献[18]提出了基于CSI 的穿墙检测方法,采用基于PCA 的滤波算法替代传统的低通滤波来处理数据,并利用不同子载波之间的相关变化,提出了以特征向量一阶差分的均值作为特征值的方法.与文献[16]强烈依赖于环境阈值的设定不同,此算法不需要预先标定阈值.

虽然基于CSI 的室内定位技术拥有更高的鲁棒性,但是CSI 信息的获取更复杂,需要专用的底层驱动,成本较高.因此,本文仍采用基于RSSI 的室内定位算法.地标信息的获取会给测量等来更大的工作量,因此本文未使用地标信息.与其他RSSI 指纹定位算法不同,本文致力于利用用户的轨迹数据提高实时定位阶段RSSI 指纹匹配的精度:首先,利用轨迹预估技术,基于传感器数据估计用户的运动轨迹作为WiFi 定位的辅助信息,并计算预估轨迹的可信度;然后,将轨迹信息与RSSI 指纹信息按权重结合起来建立综合概率模型进行用户位置匹配,确定最近参考点.

2 轨迹预估

轨迹预估利用智能设备内置的传感器获取数据计算行人运动轨迹,本节主要介绍预估用户行动方向和距离的方法,获取用户轨迹,并提出了预估轨迹可信度的计算方法.

2.1 基于陀螺仪、加速度计的轨迹预估方法

大量研究表明,用户运动时,从陀螺仪、加速度计获得的数据具有一定的规律性,可以通过对其进行处理与分析得到用户的相对运动轨迹.对加速计测得的数据进行二次积分就可以得到距离,但这种计算方法的误差会随着时间积累[19].由于在用户行走时,加速度计可以测得其身体呈现的周期性变化,如后文图1 所示,因此本文通过统计加速度信号的波谷数来计算行走步数,然后将步数与步幅相乘计算用户行进的距离.实验证明,步幅与设备垂直方向运动距离成正比关系[20],而设备垂直运动的距离可以通过加速度计体现出来.加速度计测得的总加速度〈ax,ay,az〉是由重力加速度〈gx,gy,gz〉跟用户施加的力引起的加速度的总和,而设备垂直运动的距离与平行于重力的加速度分量变化成比例关系,因此采用总加速度在重力加速度方向上投影的标准差作为设备的垂直运动因子:

利用相同设备垂直运动因子下步频与步幅的线性关系,即可求出步幅,其中,步频可根据一段时间内的步数求得[20].

由于陀螺仪的采样频率很高,且对角度变化可以进行灵敏准确的识别,因此本文利用陀螺仪进行偏转角度的估计.基于陀螺仪获取的角速度数据,进行对时间的一次积分可以得到偏转角.根据文献[21]的研究,其平均误差为10.9°,在550m 的圆形轨道上测试,运动一周后,估计位置偏差为11.7%.A.Jimenez 等人在文献[22]中将距离和方向变化结合起来进行相对位置定位,研究结果表明,无论对于室内环境还是室外环境,其大部分情况下拥有较高精度,误差都小于5%.

2.2 预估轨迹可信度

根据传感器数据预估轨迹受外界环境变化的影响较小,但容易造成漂移误差积累,因此需要建立相应的模型来评估误差的大小,进而评价预估轨迹的可信度.实验结果表明:运动速度越稳定,预估轨迹就越接近真实轨迹,测量误差也就越小;当速度变化时,尤其在起步或停止的阶段,测量误差较大.图1 描述了在匀速、变速两种运动状态下各步行30 步的加速度计测量的数据.可以看出,匀速运动时加速度变化较为规律,而变速运动时加速度的变化较为剧烈,规律性差.

Fig.1 Data obtained by accelerometers over different motion patterns图1 不同运动模式下的加速度计获取的数据

为了评价利用内部传感器测量用户轨迹的可靠程度,提出了预估轨迹可信度的概念,记为φ,如公式(1)所示.

其中,μ表示用户运动的平均速度,δ表示所有速度的均方差,代表速度的均匀程度.δ值越小,速度越均匀,可信度越高,预估轨迹越精确,其误差越小.因此,误差与可信度成反比关系.

为了研究误差与可信度的关系,我们以不同路径和速度从点A移动到点B,记录下两点间的加速度计数据,共进行20 次实验.图2 显示了3 条实验路径,点A和B相距5m.为避免起步和停止时的速度变化对实验造成影响,我们在A点之前起步,在B点之后停止,中间经过A,B两点.

根据传感器数据计算得到的误差和可信度倒数关系如图3 所示,可以看出,误差与可信度倒数大致符合线性关系.由此,我们可以假设在移动一定距离时,有:

其中,ε为误差,φ为预估轨迹可信度,a,b的值与具体的轨迹计算算法和移动距离相关.

Fig.2 Experimental paths图2 实验路径

Fig.3 Relationship between error and confidential degree图3 误差与可信度关系

3 概率性位置确定

至此,我们已根据传感器数据预估了用户轨迹,并给出了预估轨迹可信度的计算方法.下面我们将利用这些数据对经典的信号指纹定位方法进行改进,基于概率模型来确定候选点的位置,提高指纹定位的精度.

3.1 概率模型

概率模型将预估轨迹概率跟信号指纹确定的位置概率按合理的权值进行综合计算,首先计算预估轨迹概率,再确定这两部分的权值.

根据第2 节提出的轨迹预估方法可知:主要根据加速度计预估距离,根据陀螺仪预估方向,即距离与方向的数据分别来自不同的传感器.因此,我们可以假定距离概率和方向概率是相互独立的,故有轨迹概率,即

最后,我们假设用户从已知位置O点出发,到达目的地A点.此时预估轨迹为,在A处测得的指纹为sA,RA是通过指纹匹配得到的一个候选参考点,如图5 所示.

Fig.4 Estimated trajectory图4 预估轨迹

Fig.5 Probabilistic model图5 概率模型

至此,我们就可以将轨迹概率和传统的基于RSSI 的指纹定位概率相结合,得到最终的概率模型,如公式(6)所示.

其中,α表示轨迹概率对综合概率的贡献,与预估轨迹的可信度φ定义相关.为引入α与φ的数学关系,我们设信号指纹定位误差为εfp,预估轨迹误差为εdis,两种定位模型的权重应与误差反相关,即.目前,经典的指纹定位平均误差大都为1m 左右,不妨记为定值εfp=1;再根据预估轨迹误差与可信度的关系,可得:

3.2 候选参考点概率性位置确定

至此仅建立了一段路径的综合概率模型,在实际在线位置确定时,设备对WiFi 信号进行n次测量,每次均会得到概率最高的k个候选参考点,如图6 所示.当顺序链接不同的候选参考点时,得到多个候选路径,如路径path=[p1,p2,…,pn],其中,pi是第i次测量的候选点,将其表示为向量的形式.对应路径中的路段,预估的轨迹为ai.

Fig.6 Path probability图6 路径概率

由于每次测量是相互独立的,因此可以认为路径中各段之间相互独立.根据前面综合概率的讨论,候选路径path的概率为

其中,n表示定位的次数,Ppf(p1/s1)是点p1的指纹匹配概率.为了统一表达,我们对于没有前趋节点的参考点p1指定一个虚拟前趋节点p0,并令相应的参数α1=0,则有:

其中,PATH(R)为所有以R为终点的候选路径的集合.如果直接计算,该公式的时间复杂度为O(kn-1)(k为候选点个数,n为历史测量次数)并且存在大量重复计算.为了简化计算,我们将保留之前计算的路径概率,然后拼接最后一段路径,假设Rn-1,i是第n-1 次测量的候选参考点,Rn-1,i是第n次测量的一个参考点,于是有:

因此,每一次测量时都要保存k个参考点的指纹概率和路径概率,算法的空间复杂度为O(kn).其中,P(Rn-1,i)在第n-1 次测量时已经计算过,因此,P(Rn,j)复杂度降为O(k).由于第n次测量一共有k个候选点,所以最终的时间复杂度为O(k2).

3.3 实例分析

本节通过实例分析概率模型对定位精度的影响.连续两次测量匹配得到的候选参考点如图7 所示,其中,红色叉号是单纯根据指纹匹配得到的定位结果,如Opf;蓝色叉号是综合了轨迹信息得到的结果,如O.表1 和表2分别为第n次和第n+1 次测量各候选参考点的信息;两次测量间预估轨迹αn+1=(4,1),其权重为αn+1=0.5.

Fig.7 Comprehensive probability model based positioning图7 综合模型定位

Table 1 Reference points in the nth measurement表1 第n 次测量参考点

Table 2 Reference points in the (n+1)th measurement表2 第n+1 次测量参考点

根据表1 和表2 计算得到的轨迹概率见表3,其中,第i行第j列表示向量的轨迹概率.

Table 3 Trajectory probabilities of reference points表3 参考点轨迹概率

根据之前的结论,Rn+1,j的概率计算公式为

其中,第1 项为指纹匹配概率的贡献,第2 项为轨迹概率的贡献.

从表3 中可以看出,每列中第1 行的数值都是最小值,即每列中的值最小.因此在和式中,Rn,1的贡献是最小的.可见,在第n+1 次定位程中,我们通过轨迹概率对偏差点Rn,1的影响进行了降低,同时对其他点进行相应提升,从而提高了定位精度.

分析图7 可以看出,概率模型可以弱化环境变化对定位结果的负面影响.图中第n次测量指纹定位与综合模型定位的位置相差很大,这是因为由于环境变化,当前定位出现了偏差较大的候选点Rn,1时,若仅采用指纹匹配算法选择匹配度较高的候选点,会产生很大偏差,且会对后续定位产生误差积累,对最终结果产生较大的影响.但通过轨迹信息,便将Rn,1对综合定位的贡献大幅度降低,使偏差点并不会对后续定位产生太大的影响.当前测量各候选参考点都正常时,由于后续定位中考虑到更多的参考点有利于均衡误差,因此会对后续定位产生积极的影响,有利于提高定位的精度.

4 性能分析评价

本文在真实数据的基础上对算法进行实验分析,通过与其他定位算法进行比较,分析传感器信息对定位精度提高的贡献,并详细分析了预估轨迹精度、候选参考点个数和路径长度对算法精度的影响.

4.1 实验环境

进行实验的楼层平面图如图8 所示.平面图中,黄色的点为WiFi 接入点,蓝色的点表示参考点,参考点之间的间隔是1.5m;红色的点是实时测量阶段随机选取的测量点,用来测试算法精度.在每个参考点和测量点都重复采样110 次,采样周期为250ms.

考虑到用户轨迹,本文通过仿真算法随机生成100 条用户的运动路径,具体算法如下:在平面图中随机选取一个测量点作为起始位置,然后在附近测量点中随机选择一个作为下一个点;考虑到人的真实运动轨迹,会以较大的概率前进,较小的概率转向和后退,且在较短的时间内移动距离一般不会超过10m,所以将10m 范围内所有测量点按偏转角度排序,依次进行判定,第1 个点被选中的概率为1/2,第2 个点的选中概率为1/3,依次类推,若直到最后一个点仍未选中,则直接选择第1 个点;若路径长度超过50,则算法停止.为了充分利用所有测量点样本,即要求每个测量点在路径中出现的次数大致相同,我们按照测量点参与次数排序,再生成100 条路径,共200 条随机路径进行仿真实验.图8 显示了其中一条路径.在实验中,实验人员持智能手机沿该生成的路径行走10 次,获取传感器数据.

假定信号指纹定位精度为1m,预估位置误差为ε,相应的预估轨迹权重α的计算如公式(13)所示.

本文用定位坐标与实际坐标的欧几里德距离作为定位精度的评价标准,即

其中,(x,y)是位置计算结果,(x0,y0)是测量点实际位置.

Fig.8 Experimental environment图8 实验环境

4.2 性能分析与测试

图9 描述了RADAR、Horus、WiFi+INS[9]以及本文提出的多传感器辅助定位方法的性能.

Fig.9 Cumulative distribution function of positioning error图9 定位误差累积分布函数

RADAR 系统定位精度最差,平均误差达到2.57m;Horus 系统远远优于RADAR,平均误差为1.18m;WiFi+INS 方法平均误差为1.1m;本文提出的多传感器辅助定位的方法优于其他3 种方法,平均误差为0.97m.RADAR之所以最差,是因为其所使用的KNN 算法只是简单地对候选参考点取均值,没有考虑各参考点的权重.Horus 和本文算法在建立数据库和指纹匹配时都是基于统计概率,因此更精确.相对于Horus 系统,当误差大于1.5m 后,本文算法的优势极为明显.这是因为误差越大,指纹匹配概率对综合概率计算的贡献就越低,而预估轨迹信息的贡献提高,提高了定位的精度.这说明定位时使用轨迹信息,可以有效地提高整体定位精度,尤其是可以减小定位出现较大误差的概率.粒子滤波器的时间复杂度为O(n2),直接受限于重采样的复杂度[23],其中,n为粒子数.本文算法的时间复杂度为O(k2),其中,k为选取的高匹配概率的项数,即选取前k个高匹配概率.为了保证算法精确度,随着参考点个数的增加,粒子数n随之增加,而k相对较小且相对固定,所以粒子滤波器的时间复杂度远大于本文算法的时间复杂度.因此,即使误差大于1.5m 时,WiFi+INS 的方法与本文方法的累积误差概率相当,但鉴于粒子滤波器计算量大、耗时长,并不适合于实时定位.

本文算法中使用预估轨迹辅助定位,因此其精度将直接影响到算法精度.图10(a)通过改变路径上各点间预估轨迹精度来对比分析其对算法的影响,利用预估轨迹生成算法随机生成8 组预估轨迹和相应的权重信息.从图中可以看出,随着轨迹精度的提升,定位精度也相应得到提升.这是因为根据公式(13),预估轨迹的误差越小,其权重α越大,对综合概率的贡献越高,定位也越精确.当平均预估轨迹误差达到0.7m 时,平均定位精度相应达到了0.97m;但当预估轨迹平均误差小于0.5m 后,由于权值α的大小逐渐稳定,预估轨迹信息对综合概率的贡献逐渐稳定,其对定位精度的影响就不再明显.

Fig.10 Factors having effects on positioning accuracy图10 影响定位精度的因素

图10(b)描述了不同候选参考点个数对算法的影响.可以看出,当参考点个数n=1 时,定位效果最差.因为只使用匹配度最大的点作为定位结果很容易引入较大误差,尤其是在环境变化较大时,极可能出现偏差大的参考点匹配概率反而高的情况.随着参考点个数的增加,定位精度逐渐提升,当n>6 时,精度反而有所下降,与文献[2]的实验结果一致.这是因为随着参考点个数的不断提升,偏差较大的参考点也被引入到综合概率的计算中,反而对最终结果引入了较大的误差,降低了定位精度.所以候选点个数不是越多越好,其值要根据实际环境以经验方式来确定.

我们还以平均误差作为评价标准,分析路径长度与定位精度的关系.对所有路径中各参考点按序号进行归类,即将各路径中的第i个参考点归为一类,统计所有路径的平均定位误差.从图10(c)中可以看出,起始点平均误差较大,达到1.16m,与Horus 的定位精度比较接近.这种情况相当于仅测量一次的结果,存在极大的偶然性,这是因为当路径长度为1 时,传感器的预估轨迹信息对综合模型的贡献为0,结果仅由经典的指纹匹配算法确定,只使用匹配度最大的点作为定位结果,很容易引入较大误差,尤其是在环境变化较大时.随着路径变长,预估轨迹信息以一定权重对综合模型做出贡献,均衡定位的误差,定位精度逐渐提升.当路径长度为8 时,定位精度达到0.97m.之后,误差值基本维持在这个精度.这说明,随着测量次数的增加,环境变化对定位结果的影响已经很低了,因此,综合模型可以削弱环境变化带来的不利影响.

5 总结

由于室内环境复杂多变,而WiFi 信号的传输易受环境变化影响,因此仅使用指纹定位可能存在大的偏差.为了提高定位精度并减小环境因素带来的不利影响,本文提出了智能手机内置传感器辅助WiFi 信号指纹定位的方法,即要利用智能设备上内置的传感器如加速计、陀螺仪等采集数据,预估得到用户轨迹信息,并提出预估轨迹可信度概念用以评估预估轨迹的精确程度;然后,将轨迹信息与信号指纹信息按权重结合起来建立综合概率模型,进行位置匹配,确定最近参考点.实验结果表明,与经典指纹匹配算法RADAR、Horus 以及WiFi+INS 的方法相比,我们的方法利用传感器数据能够有效地提高定位精度,且可以减弱环境变化对定位造成的不利影响.