众包室内定位系统中基于多维尺度变换的接收信号强度平滑理论

张立晔，王 壮，房 超，孟晓亮，田爱奎

(山东理工大学计算机科学与技术学院，淄博 255000)

定位与导航服务在人们的日常生活中发挥着举足轻重的作用。近年来，随着移动终端和无线局域网(wireless local area network，WLAN)的普及，在移动终端实现基于位置的服务(location based service，LBS)已经逐渐改变了人们的生活和工作方式。越来越多的应用程序开始利用位置信息为用户提供服务，其中既有如E911的传统救援服务，也包含以智慧城市和物联网为代表的全新应用领域[1-3]。为了获取用户的位置信息，众多定位系统已经完成部署。在户外，以中国北斗定位系统和美国全球定位系统(global positioning system,GPS)为代表的卫星定位系统已经可以为用户提供精确的位置信息。然而，由于楼体的遮挡，卫星信号接收设备不能在室内和卫星被高楼阻挡的地区使用。因此，人们提出了多种室内定位解决方案用于替代卫星定位系统。

基于Wi-Fi的WLAN技术经过多年的研究，已广泛部署在校园、机场、商场等公共场所，WLAN技术的普及为使用WiFi信号进行位置估计创造了机会。由于在公共区域中的所有可见接入点(access points,APs)都可以利用移动终端查看，并且移动终端还可以测量每个AP的接收信号强度(received signal strength,RSS)，因此利用Wi-Fi的RSS进行用户位置估计成为常用的方法之一[4]。

基于RSS的位置指纹定位方法分为两个阶段：离线训练阶段和在线定位阶段[5]。在离线训练阶段，在室内空间中设置大量参考点(reference point,RP)，并在参考点上采集来自所有AP的RSS数据，将RSS值与对应RP的位置空间坐标组成位置指纹数据库radio map，radio map是位置指纹技术的基础，其保存了信号空间到位置空间的映射。在在线阶段，用户利用移动终端采集所有AP的RSS值，并将用户接收到的RSS值与radio map中的RSS信号空间进行匹配，进而得出用户的当前位置[6-7]。

近年来，众包技术以其出色的表现引起了室内定位领域的关注[7-8]。在众包技术中，radio map不再由专业人员建立，而是将复杂烦琐的工作化整为零，由众多志愿者分别采集数据汇总而成。众包技术大大减少了技术人员在训练阶段收集的RSS值的数量。当志愿者在进行日常活动时，移动终端采集各种传感器数据用于建立radio map，例如，加速度计数据可用于计算两次RSS采样之间的相对位移；磁力计或陀螺仪用于测量方位变化等。最后，这些众包数据经过处理之后组合在一起，构成无radio map。

为了更加规范地进行数据采集，技术人员在室内的设置起点和终点，手持移动终端从起点移动到终点，在移动过程中采集RSS数据和传感器数据。利用加速度计和陀螺仪等传感器计算两个连续RSS样本之间的相对位移，每一个采集RSS数据的位置即为参考点(reference point,RP)。通过同时收集RSS值和传感器数据，可以快速构建无线电地图。

在上述数据采集方法中，在每个RP上只能采集一个RSS数据，考虑到RSS值会受到噪声和信道衰落的影响，单个RSS数据很难准确反映该位置的实际的RSS分布。为了消除噪声对radio map的影响，中外专家学者提出了多种噪声抑制算法。文献[9]提出了相关时间窗滤波(sliding correlation time window,SCTW)算法对radio map进行平滑，在采集数据时，利用一段时间内采集的RSS数据对实时采集的RSS数据进行滤波，从而消除RSS数据的波动。文献[10]提出了一种基于Hankel矩阵的radio map噪声消除算法，该算法从radio map中提取不同AP对应的信号向量来构造Hankel矩阵，对Hankel矩阵进行求解从而实现信号和噪声的分离。文献[11]提出利用轻量级深度学习算法在基于信道状态信息的室内定位系统中实现噪声消除和降维，本算法对批量数据点多项式回归，从而滤除噪声。文献[12]提出在同一RP上采集不同AP的RSS值，并计算不同AP的RSS值的差值，并将该差值与原始RSS数据融合作为指纹特征生成radio map，最后利用神经网络算法进行用户位置的解算。文献[13]提出了WiDeep系统，该系统结合了堆叠式去噪自编码器深度学习模型和概率框架来处理接收到的WiFi信号中的噪声，同时得到RSS数据与相应RP位置之间的关系。文献[14]提出了一种基于稀疏表示和低秩矩阵恢复的无线电地图更新方法，该算法将RSS矩阵的低秩特性和稀疏先验结合起来，处理指纹缺失和稀疏噪声。从以上算法可以看出，现阶段研究主要利用radio map中的部分数据之间的相关性实现对噪声的抑制，而其他数据的信息被忽略了，因此无法实现最优的噪声抑制效果。

受到这些算法的启发，现研究一种多维尺度变换(multidimensional scaling,MDS)算法，对离线阶段利用众包技术采集的RSS值进行平滑处理。MDS算法是在一组数据对象上分析其相似性或非相似性的一种技术。在MDS算法中，由于APs和RPs的位置固定，在不同RPs处采集的RSS值具有内在关系，用相似矩阵表示[15-17]。基于信号传播模型，考虑APs和RPs位置，可以计算得到在两个RPs上采集的RSS数据的相似性距离。在离线训练阶段，利用MDS算法和相似度矩阵能够降低噪声和测量误差对RSS数据的影响，从而实现对radio map的平滑处理，最终提高定位精度。

1 问题分析

考虑典型的Wi-Fi室内定位场景，其中用户携带一个装有Wi-Fi适配器的移动设备，在室内环境中从Wi-Fi AP采集RSS数据。在离线训练阶段，实验人员在n个参考点上采集来自m个AP的RSS值，所有RSS数据与其对应的坐标信息构建成一个radio map。第i指纹(ri,ci)是由一个m×1维的RSS向量ri和相对应的坐标ci组成，其中ri为在第i个RP采集的来自m个AP的RSS值，第i个RP的坐标ci=(xi,yi)T。在传统的Wi-Fi定位方法中，通常会在每一个RP采集数百个RSS数据，并计算这些RSS数据的平均值，利用该平均值最终得到无线电地图。无线电地图可以用矩阵形式表示为

(1)

式(1)中：rij为在第i个RP上采集的来自第j个AP的RSS平均值。在在线定位阶段，用户利用移动设备在某未知位置Sj处采集来自AP的RSS值rj，然后通过比较rj与radio map中的RSS数据来估计用户所处的位置。在基本的定位理论中，如果所采集的rj与radio map中的ri相似，则认为用户的位置Sj必定靠近Si。

众包定位系统存在的一个问题是在离线训练阶段和在线定位阶段会有大量不同品牌不同型号的移动终端在定位系统中运行。由于不同移动终端设备中配置的Wi-Fi信号接收器不同，而对于同一个AP，不同Wi-Fi信号接收器接收到的RSS强度有较大差别，从而得到不同的数据分布。大量研究表明，由于硬件的差异，不同设备采集的RSS差异甚至超过25 dBm[18-19]。因此，由于不同设备采集的RSS数据波动较大，造成定位系统的定位精度大大降低。针对上述问题，在文献[20]中提出了基于线性回归(linear regression，LR)算法的设备多样性消除算法，该算法解决了设备多样性问题，在离线训练阶段和在线定位阶段都得到了具有一致性的RSS数据。

室内定位的另一个问题是移动设备在室内环境中采集的RSS值波动较大。首先，RSS数据会受到多种噪声源的影响，例如路径损耗、多径和阴影；第二，AP的发射功率会随着时间的不同而不同；第三，对于所有可用的AP，移动设备可能无法扫描整个频谱采集RSS数据。因此，用来建立radio map的RSS数据必然包含大量环境噪声和测量误差。为了说明这一点，从多伦多大学Bahen大楼的某个位置采集了100个RSS值，并在图1中绘制了直方图。如图1所示，虽然利用同一设备在同一位置采集来自同一个AP的这些RSS数据，但是所采集的RSS数据的功率分布在-70～-50 dBm的较大区间内。

图2所示为Bahen大楼4楼走廊的RSS数据分布(不包括异常值-110 dBm)。在图2中，每一个色块代表在该RP上采集的来自某一AP的RSS值，为了便于显示该值，对所有RSS值加110，使所有RSS值都大于0 dBm，取值范围变为(0～110 dBm)，而颜色越偏红色代表RSS值越大，颜色越偏蓝色代表RSS值越小，后续radio map分布都遵从该范围。因此图中显示的RSS值范围从图2中可以看出，虽然在整个走廊中，RSS数据的信号分布在一定程度上符合信号传播模型，但是RSS数据在某些位置却有较大的差异。利用这种包含大量波动的RSS数据进行定位会导致较大的位置估计误差。

图2 多伦多大学Bahen楼4楼走廊某AP的信号分布Fig.2 Signal distribution in corridor of 4th floor of Bahen building at University of Toronto

如上所述，可以得到室内定位系统中一个关键的挑战：如何处理众包定位系统采集的RSS数据，使其更接近理论值？采用MDS算法来抑制RSS值的波动，从而得到更加平滑的radio map。

定义D为AP与RP之间距离的矩阵，表达式为

D=[d(Si,APk)]n×m

(2)

式(2)中：d(Si,APk)为参考点Si与接入点APk之间的欧氏距离，即

d(Si,APk)=‖ci-cAPk‖2

(3)

式(3)中：cAPk为第k个AP的坐标。

定义R=[r(Si,Sj)]n×n为在参考点Si和Sj上采集的RSS数据的相似性矩阵，值得注意的是，RPs与参考点Si和Sj之间的相对RSS值与欧氏距离有关，公式为

r(Si,Sj)≈F[d(Si,APk)]

(4)

式(4)中：F为室内环境中的电磁波传播模型。

2 基于MDS算法的RSS平滑理论

如前文所述，利用众包技术获得的RSS数据是在室内环境中正常行走时测量得到的，因此建立的radio map中RSS数据包含大量噪声。利用MDS算法，根据采集点之间的相对距离、已知AP位置和信号传播模型实现对radio map数据的平滑。

2.1 经典MDS算法

在离线训练阶段构建radio map时，数据空间中所有数据点之间的相似性距离的平方r2(Si,Sj),其中，i,j=1,2,…,n，由式(5)计算得到，即

(5)

然后得到数据空间中的平方相似矩阵为

(6)

在MDS算法中，相对点RSS′由R计算，计算过程如下。

首先，对相似性矩阵进行双定心处理，表达式为

(7)

给出J的定义为

(8)

用奇异值分解(singular value decomposition,SVD)对B进行分解，即

B=UΛUT

(9)

式(9)中：Λ=diag(λ1,λ2,…,λm)为B的特征值的对角矩阵，λ1≥λ2≥…≥λn≥0；U=[u1,u2,…,un]，为一个正交矩阵，其中每一列是特征值对应的特征向量。

假设需要得到m维的解，用矩阵Λm表示前m个最大特征值，Um表示矩阵U的前m列，则经典尺度变换的坐标矩阵为

(10)

2.2 估计r2(Si,Sj)

为了平滑radio map中的RSS值，需要精确的相似距离矩阵。当在RPSi上采集的RSS值包含噪声时，使用信号传播模型来计算相似性距离r(Si,Sj)。如图3所示，考虑在室内区域中安装的第k(k=1,2,…,m)个AP。利用文献[21]中的CS方法可以精确地估计AP的位置cAP，因此将其位置视为已知。利用文献[22]中的室内信号传播模型来模拟无线信号在环境中的传播。

图3 一个AP的典型Wi-Fi网络Fig.3 A typical Wi-Fi network with one AP

那么从在位置Si处接收到的来自第k(k=1,2,…,m)个AP的RSS值，可以表示为

(11)

式(11)中：dik为第k个AP与测量位置之间的距离；P为AP的传输功率；αi为环境中的传播损耗指数；hjk为包含路径损耗、衰落和阴影的衰减。

使用式(11)的模型和文献[15]的方法，可以得到

(12)

定义r(Si,Sj)为在位置Si和Sj上采集的来自所有AP的RSS值的差值矩阵。r(Si,Sj)的第k个元素为在位置Si和Sj上采集的来自第k个AP的RSS值的差值，可以表示为

rk(Si,Sj)=rik-rjk

(13)

r(Si,Sj)的欧氏距离范数可以写为

(14)

r(Si,Sj)的欧氏距离范数可以写为

(15)

2.3 MDS算法的应用

在室内区域的n个RP上采集来自m个AP的RSS值，得到一个n×m阶的radio map。由于在RSS矩阵RSS中，含有噪声的RSS值是未知的，因此假设在RPSi上采集的RSS值ri是含有噪声的，利用MDS算法，基于坐标矩阵C和RSS矩阵中除ri之外的RSS值可以实现对ri平滑。利用该方法，其余RP上的RSS值可以一一实现平滑处理。radio map可以通过以下步骤进行平滑。

步骤1利用式(14)计算RPSi与其他RPs在数据空间中的相似距离。其余的相似距离由RSS值计算，最终，MDS算法所需的相似性距离矩阵由这两部分相似距离组成。

步骤2对距离矩阵应用MDS，保留前m个最大的特征值和特征向量，构建m维相对RSS矩阵。

步骤3利用线性变换(可能包括缩放、旋转和反射)，基于除ri外的矩阵RSS将相对RSS矩阵转换为绝对RSS矩阵。

3 实验结果与分析

利用仿真和实验对基于MDS算法的RSS平滑进行了验证。离线训练阶段，利用移动终端在多伦多大学Bahen中心4楼采集RSS数据和传感器数据，然后利用传感器数据和计步算法自动计算RPs的坐标。在实验过程中，由于在每个RP只采集5个RSS值，结合计算得到的与RSS值对应的坐标，在30 min内构建了一个radio map。在线定位阶段，实验人员手持移动终端从房间4000(图4的顶部)移动到房间4148(图4的底部)，在该路径上共收集到35个测试点的序列。

图4 测试点实际位置Fig.4 Actual locations of Test Points

由于室内环境的复杂性，在不同区域的衰减是不同的。因此，在室内环境的不同位置采用不同的传播损耗指数α值，以获得更好的定位结果。当AP在RP的视线范围内时，设α=3.5。当RP位于角落附近时，设置α=1.5来模拟由墙壁反射造成的信号衰减的减小。当从AP到RP中间有遮挡，即不在视线范围时，设α=5，同时，如果信号传播路径中有更多障碍物时，该值会继续增大。

如图5(a)所示，尽管AP在室内环境中RSS的信号分布值与信号传播模型基本一致，但是大量的噪声和测量误差使得radio map中某些RP上的RSS值出现剧烈波动。利用原始的radio map，得到如图6所示的定位结果。可以看到，与图4中的实际位置相比，定位结果存在明显的误差。此外，某些不同的测试点被错误地定位到相同的位置。

为了提高定位精度，在离线训练阶段，采用提出的MDS算法平滑接收到的RSS值。图5(b)为平滑后的radio map信号分布，可以看到，经过MDS算法平滑之后，原始radio map中的RSS数据去除了很多噪声和测量误差，得到的radio map更符合室内信号模型。图6为利用原始radio map进行定位测试得到的定位结果，可以看出，很多不同位置的测试点被错误地定位在同一位置。而图7为利用平滑后的radio map进行定位得到的定位结果，从图7可以看出，利用平滑之后的radio map进行定位得到的定位精度明显提高，在图6中堆积在一起的定位结果被定位在不同位置，并且更接近它们的实际位置。因此，提出的MDS算法能够提供更高质量的位置服务。

图5 radio map信号分布比较Fig.5 Comparison of signal distribution of radio map

图6 利用原始radio map的定位结果Fig.6 Positioning results using original radio map

图7 利用MDS算法后的定位结果Fig.7 Positioning results using the MDS algorithm

MDS算法定位误差的累计分布曲线如图8所示。作为对比，还利用文献[8]中提出的光滑CHKS函数孪生(smooth twin CHKS support，SCTW)算法对radio map进行平滑，并利用该radio map和原始数据进行了定位测试。由于SCTW方法只使用了少量的无线电地图RSS值，大部分radio map信息都被舍弃了，因此无法获得更优的radio map。由于所提出的MDS算法得到了更加精确的radio map，因此与其他方法相比，利用MDS算法进行radio map平滑处理可以得到更高的定位精度，从测试结果可以看出，利用MDS算法对radio map进行平滑使得最大定位误差由10 m减小到4 m，平均误差由2.89 m减小到2.11 m。

图8 定位误差累计分布函数Fig.8 Cumulative distribution function of Positioning error

4 结论

提出了一种基于MDS算法的RSS平滑方法，在基于指纹的众包室内定位系统中，由于RPs的固定位置，不同RPs之间的RSS值有内在的关系，利用MDS算法，可以挖掘不同RP上采集的RSS之间的内在关系，从而有效校正有噪声的RSS值，得到更平滑的radio map。在多伦多大学Bahen中心测试了该方法，实验结果表明该方法能显著提高定位精度。