基于压缩感知的室内定位系统的定位性能分析

郑 倩，胡久松，刘宏立，肖郭璇，陈 亮，徐 琨

(1.湖南大学 电气与信息工程学院，长沙 410082; 2.国家电网 浙江乐清市供电公司，浙江 乐清 325600)

0 引 言

随着无线网络、通信技术的迅速发展以及智能终端的广泛应用，使得应用Wi-Fi基础设施为室内定位服务(location-based service, LBS)提供个人和商业应用成为可能[1]。但是，由于室内环境的复杂性，大多数定位应用通常难以提供令人满意的准确度。因此，设计一个容易部署、硬件简单且准确的室内定位系统是目前研究的热点。与其他测量算法相比(例如，超宽带(ultra-wideband, UWB)信号的到达时间(time of arrival, TOA)或到达角度(angle of arrival, AOA)测量)[2]，接收信号强度(received signal strength, RSS)可以通过已有的Wi-Fi接入点(access points, APs)获取，无其他硬件要求，所以基于RSS的定位算法作为室内定位系统的解决方案已被广泛研究[3-5]。

Wi-Fi定位技术通常采用指纹定位的方法，通过在线RSS与离线指纹库匹配完成位置估计[6]。其中，比较简单的方法是采用K最近邻算法(K-nearest neighbor, KNN)[7]，它通过计算K个欧几里得距离最小的点的质心来估计在线用户的位置。这种算法容易实现，但是位置估计准确度不高。另外，常采用的方法是通过概率统计方法，使用贝叶斯理论或核函数对每个潜在的定位位置的概率进行分析[8-9]，然而在实际环境中，RSS分布并不是完全服从高斯分布，因此，概率性算法会有很高的计算复杂度。

压缩感知(compressive sensing, CS)提供了一个新的框架，它通过开发信号的稀疏特性，在远小于奈奎斯特采样率的条件下，用随机采样获取信号的离散样本，然后通过求解一个l1范数最小化问题以高概率精确地重建信号[10]。空间域中定位的稀疏性激发了不少学者将CS应用到室内定位系统中[11-13]。然而，大多数文献都是采用压缩感知算法中的正交匹配追踪(orthogonal matching pursuit, OMP)算法进行定位，对CS中的其他算法应用较少，没有系统地比较不同CS算法的定位性能，也没有考虑算法参数对CS的影响。

针对上述问题，本文基于RSS的Wi-Fi室内定位技术，构建室内定位系统，首先通过实验确定压缩感知算法最优参数，然后在线定位阶段采用不同压缩感知算法比较各类算法的定位性能。实验结果表明压缩感知可以应用于室内定位并得到良好的定位精度；从东南西北多方向采集更多的数据从而得到完备的数据库，可以提高压缩感知算法的定位精度；无论参考点数据量的多少， CS中的其他算法，特别是分段弱正交匹配追踪(stage-wise weak orthogonal matching pursuit, SWOMP)、基追踪(basis pursuit, BP)、基追踪降噪(basis pursuit de-noising, BPDN)算法相比OMP算法能得到更好的定位性能，并且他们的差距随着参考点数据量的增加而增加。

1 定位系统

1.1 室内定位框架

图1为基于RSS的Wi-Fi室内定位系统框架，分为离线阶段和在线阶段。离线阶段分为数据采集、指纹库构建、仿射传播聚类(affine propagation, AP)[14]3步，即包括前期参考点(reference points, RPs)和测试点(test points, TPs)处的RSS与物理位置等信息的数据采集工作，指纹库的建立，并对构建好的指纹库进行AP聚类处理且保存到数据库。在线阶段分为定位查询、基于AP聚类的粗定位过程和基于CS的精定位过程3步。首先获取定位点的RSS信息，本系统先采集测试点用作定位点进行实验；接着测试点与数据库中已形成的聚类进行指纹相似度匹配，定位到某一类中，即粗定位过程；最终应用压缩感知完成系统的精定位过程。

1.2 离线阶段

指纹定位法在离线阶段需构建完备的指纹库。在定位区域，设共采集指纹点N个，所能接收到接入点的信号的最大个数为L，则第i个指纹点的接受信号强度向量为

rssi=(rssi1,rssi2,…,rssiL)T

(1)

由N个指纹点的接收信号强度向量组合在一起便形成一张形如电子地图的矩阵，表示为

(2)

用Ψo表示设备面向方向o(o∈O={E,W,S,N},即东南西北4个方向)的电子地图。实验时，每个参考点采集40次，取RSS的平均值存入指纹库，而对于未接收到接入点APs信号的点，其强度统一用-100 dBm表示。

图1 室内定位系统框架Fig.1 Indoor positioning system frame

得到指纹库，再对其进行聚类处理，可以有效降低定位匹配的复杂度及减少因RSS时变特性带来的影响。经典的K-Means聚类算法[15]必须预先确定好聚类总数目，并且算法的收敛性与收敛速度很大程度上取决于初值选取。本文选定的仿射传播聚类算法[14]不需要事先指定聚类数目，对初值的选取不敏感，对距离矩阵的对称性没要求。

具体地，AP聚类根据N个数据点之间的相似度进行聚类，即参考点RPi与RPj的相似度组成N×N的相似度矩阵s(i,j)(N为数据点个数)。本系统中采用负的欧氏距离计算两者的相似度，计算公式为

(3)

通过传递2种类型的消息即吸引度(responsibility)和归属度(availability)，不断迭代更新产生聚类及聚类中心。其中，吸引度r(i,k)表示从点i发送到候选聚类中心k的数值消息，反映k点是否适合作为i点的聚类中心。迭代更新公式为

(4)

归属度a(i,k)则表示从候选聚类中心k发送到i的数值消息，反映i点是否选择k作为其聚类中心。迭代更新公式为

a(i,k)=

(5)

1.3 在线阶段

在线阶段，首先需获取定位点的RSS信息，本次实验中用提前采集的测试点TPs代替定位点。先与聚类进行粗定位，缩小定位区域，再进行精定位过程，其中,定位匹配采用的是压缩感知算法。

1.3.1 信号的稀疏表示

压缩感知理论的基础是原始信号可以稀疏表示。在线定位时，原始信号即用户定位位置处的接收信号强度RSS信息，用向量φt(L×1)表示为

φt=(rsst1,rsst2,…,rsstL)T

(6)

理想情况下，用户位于任意某个参考点上，即φt与离线阶段收集的电子地图矩阵Ψ(L×N)的某一列唯一对应，因此，用户的位置可以在基Ψ上用一个1稀疏向量θ(N×1)表示为

θ=[0,…,0,1,0,…,0]T

(7)

(7)式中，Ψ代表稀疏基，则原始信号可以表达为

φt=Ψθ

但实际中，指纹库是间隔采集的，用户位置可能不是与某一参考点精准匹配而是在少数几个参考点上有较大的匹配度，此时向量θ应该是在匹配到的少数参考点的索引位置取匹配程度值，其余未匹配到的索引位置取零，表示为

θ=[0,…,0,λ1,0,…,0,λ2,0,…,0,λK,0,…,0]T

(9)

(9)式中，匹配到的少数参考点的个数为向量θ的稀疏度K。

1.3.2 非相干测量

CS理论中，原始信号通过测量基投影得到测量向量。定位系统中，定义测量基Φ(M×L)为接入点APs选择矩阵，通过最强接收信号强度的选择原则(M

y=Φφt=ΦΨθ

(10)

可以看出，由于M

z=Ty

(11)

定义T=QR*为一个线性变换算子，R=ΦΨ，Q=orth(RT)T，其中，R*表示R的伪逆矩阵，RT表示R的转置，orth(R)表示对R的规范正交化。通过上述处理，结合(10)式和(11)式可得

z=QR*·ΦΨθ=QR*·Rθ=Qθ

(12)

则根据CS理论，定位问题可转化为如下范数l1最优化的求解

(13)

1.3.3 重构算法

压缩感知依据 (13) 式重构信号的算法主要分为三大类：贪婪算法、凸优化算法与组合算法[16]。贪婪算法是通过不断迭代选择与测量值最相关的列向量来实现信号重构。贪婪算法主要包括匹配追踪(matching pursuit, MP)[17]，OMP[18]、正则化正交匹配追踪(regularized orthogonal matching pursuit, ROMP)[19]、压缩采样匹配追踪(compressive sampling matching pursuit, CoSaMP)[20]、子空间追踪(subspace pursuit, SP)[20]、分段弱正交匹配追踪(SWOMP)[21]、稀疏度自适应匹配追踪(sparsity adaptive matching pursuit, SAMP)[22]等；凸优化算法是求解全局最优解，主要包括内点法[23]、梯度法[24]、基追踪(BP)[25]、基追踪降噪(BPDN)[26]；组合算法有傅里叶采样、HHS追踪[16]。

贪婪类的早期算法是OMP，下面是OMP的算法原理流程。

①初始化r0=y,Λ0=∅,Q0=∅,t=1

③令Λt=Λt-1∪{λt};Qt=Qt-1∪qλ

④求z=Qθ的最小二乘解:

⑥t=t+1，如果t≤K，返回第②步

贪婪类其他算法是在OMP基础上进行改进，区别为OMP每次只选择与残差内积绝对值最大的一个原子，而ROMP则是先选出内积绝对值最大的K个原子(若所有内积中不够K个非零值则将内积值非零的原子全部选出)，然后再从这K个原子中按正则化标准再选择一遍；CoSaMP每次迭代选择2K个原子，除了原子的选择标准之外，它有一点不同于OMP与ROMP，OMP与ROMP每次迭代已经选择的原子会一直保留，而CoSaMP每次迭代选择的原子在下次迭代中可能会被抛弃；SP与CoSaMP唯一不同的是每次选择K个原子；SWOMP每次迭代可以选择多个原子，原子个数由内积值与门限比较决定；SAMP不需要已知信号的稀疏度，它通过步长估计稀疏度来选择原子的个数。

凸优化算法中的BP算法是通过将(13)式等价转化为线性规划形式，再利用MATLAB的l1-MAGIC工具箱进行最终求解；BPDN则是考虑了噪声加入，更符合实际情况，并将(13)式等价转化为二次规划问题进行求解。

2 实验与结果分析

2.1 实验环境

本次实验数据采集的环境是湖南大学某实验楼的7层，如图2所示，实验区域面积为50 m×18 m，共包括一个走廊、2个楼梯及22间实验室。实验室主要物品有实验桌、椅子、电脑、空调等。实验楼中接入点的位置未知，在定位区域以0.9 m的间隔收集参考点位置的RSS，并记录下其物理地址(xi,yi)，对受障碍物影响不能保证0.9 m间隔的点作调整后再测量。图2中标记的点为离线阶段采集的参考点位置。实验中共采集538个参考点，每个点面向东南西北4个方向收集数据。同样地，在定位区域随机地收集测试点位置的RSS及其物理位置。实验时再在随机位置及设备面向随机方向共采集1 036个测试点。

图2 定位区域环境平面图Fig.2 Environmental plan of interest area

定位系统采用的终端设备为华为荣耀4c，操作系统为Android4.4.2，通过自主开发的一款APP进行离线收集工作。

2.2 实验结果评估方法

实验中，测试点的真实位置为(x,y)，通过定位系统计算得到的位置为(x′,y′)，则可得到定位误差为

(14)

本文主要通过测试点的定位误差的概率统计来评估各类算法性能，内容包括平均定位误差、最大定位误差、误差累积分布函数(cumulative distrilbution function, CDF)对应误差在1 m以内、2 m以内、3 m以内的百分比等。

2.3 设备面向方向

指纹库收集过程中，由于人体对RSS信号的影响，设备的朝向会影响定位系统的定位性能。为研究设备面向方向对定位系统的影响，实验分别从东南西北(E，S，W，N) 4个方向采集数据，同时得到4个方向的总数据(ALL)，分别形成E，S，W，N，ALL数据对应的指纹库并用于定位。最后的定位误差如图3所示(K=3，M=40，CS为OMP)。同时，从是否对指纹库进行聚类处理作对比。由图3可以看出，未对指纹库进行聚类处理的定位性能差于对指纹库进行了聚类处理的。当数据库完成聚类处理时，从设备朝向分析，E，S，W，N 4个方向的定位误差差别较小，在1.92～2.12 m，而由 4个方向合并的总数据形成的指纹库的定位误差得到很大提高，达到1.54 m，ALL优于E方向20.2%。这另一方面也说明当参考点数据增多时能提高定位精度。其中，对指纹库进行了聚类处理的各设备面向方向的定位性能如表1所示，ALL各项指标都优于单方向，特别是误差在1 m以内的百分比从31%提升到43%。因此，对多方向和多个参考点采集数据可以提高压缩感知的定位精度。

图3 设备面向方向的定位误差Fig.3 Positioning error of the different orientation of the device

基于设备朝向的实验结果，选择由4个方向合并的总数据ALL形成的指纹库进行后阶段的实验。

2.4 不同参数K,M

对数据点的RSS进行收集时，每个数据点处能检测到众多的接入点的信号，选取的接入点APs个数(M)太多会增加数据量，降低定位系统的效率；太少则会影响定位精度。因此，参数M需要选择一个合适值。

表1 设备面向方向的定位性能比较

定位系统对测试点进行定位，结果可能不是与指纹库中的单个参考点匹配，而是与几个参考点进行综合匹配，称匹配的参考点的个数为定位算法的稀疏度K，参数K的取值对定位精度也有着比较大的影响。

根据对参数K，M的选取进行实验，得到平均定位误差变化如图4所示(CS为OMP)，当M<25时，定位精度受参数M影响严重，但定位精度随着M的增大而得到提高，当M>35后，平均定位误差趋于平稳不再变化，因此，可以取M=40，减少运算数据量的同时保证定位精度。从图4可以看出，定位精度几乎随稀疏度K的增大而提高，但提升的幅度不是很大，最大差距在0.3 m之内。另一方面，随着稀疏度增大，算法的稳定性变差，因此，为保证相同条件，本文后续实验取K=2进行。由以上实验可知，在本系统中优化压缩感知算法的参数，可以提高定位精度和系统的稳定性。

图4 不同K值、M值的定位结果Fig.4 Position results using different value of K，M

2.5 压缩感知算法

2.5.1 CS对比KNN及其性能分析

随着压缩感知理论的提出，各种压缩感知算法也相继提出并应用。然而这些算法是在图像处理等其他领域应用广泛，而在室内定位领域应用较少，目前，室内定位多数只是应用压缩感知中的OMP算法。为了研究各类CS算法的定位性能，本文针对贪婪类算法和凸优化算法进行实验，并将其与传统方法KNN对比。实验使用MATLAB进行仿真，平均定位误差结果如图5所示。从图5中可以看出，当曲线稳定后，压缩感知算法中OMP，CoSaMP，SP的曲线位于KNN曲线的上方； SWOMP，SAMP，BP，BPDN的曲线位于KNN曲线的下方。

图5 不同算法的定位结果Fig.5 Positioning results of different algorithms

图5中，当M=40时，OMP，ROMP，CoSaMP，SP，SWOMP，SAMP，BP，BPDN与KNN的平均定位误差分别为1.51，1.39，1.40，1.43，1.14，1.29，1.26，1.25，1.39 m。则KNN的定位误差分别优于OMP，CoSaMP，SP仅7.9%，0.7%，2.8%；而KNN差于SWOMP，SAMP，BP，BPDN可达21.9%，7.8%，10.3%，11.2%。可以看出，在本文的实验环境中，OMP，CoSaMP，SP压缩感知算法的定位效果比KNN差。结合文献[11]的研究结果表明，OMP压缩感知算法的定位效果不稳定，所以，在定位领域中对各种优化的压缩感知算法进行研究以获取更佳的定位结果具有较大的意义。

由图5可知，8种压缩感知算法中，SWOMP的定位精度最好，BPDN次之，依次为BP，SAMP，ROMP，CoSaMP，SP，OMP定位精度最差。

当接入点APs的个数取M=40时，各种压缩感知的定位性能如表2所示，误差累积分布函数图如图6所示。结合表2和图6可以看出，各种压缩感知算法的定位性能都存在差异，平均定位误差在1.14～1.51 m， OMP算法误差在1 m, 2 m，3 m的累积百分比分别为44.5%，70.0%，84.0%，而SWOMP算法分别达到56.1%，79.6%，90.5%，其他算法也要比OMP效果好。因此，OMP算法定位性能不如其他CS算法，SWOMP算法的平均定位精度要比OMP高25%。

表2 不同压缩感知算法的定位性能比较

图6 不同压缩感知算法的定位误差累积分布函数图Fig.6 CDF of the location error of different compressed sensing algorithms

2.5.2 参考点数据量减少时各类压缩感知的比较

为了比较参考点减少时各类压缩感知算法的性能，取原始参考点数据量的3/4，2/4，1/4时各CS算法的平均定位误差比较如图7所示。可以看出，总体上，随着参考点数据量的增加，定位性能呈现更好的趋势，即指纹数据库越完备，定位精度越高。就压缩感知算法而言，比较了8种不同的CS算法，OMP的定位效果一直是较差的，并且随着参考点数据增多，OMP与其他CS算法的差距也随之增大。

图7 不同压缩感知算法随参考点数量的变化Fig.7 Location error of different compressed sensing algorithms vary with reference points

3 结束语

本文基于压缩感知的RSS室内定位系统进行研究，分别从设备朝向、算法参数、不同压缩感知算法种类和改变参考点数据量对CS算法定位情况进行对比实验。得出如下结论：设备朝向包含多方向时定位性能更优；系统的算法参数会影响定位性能，可以通过实验找到最优参数值；在本文的实验环境下，压缩感知中SWOMP算法的定位精度比KNN优21.9%，各类压缩感知算法中，SWOMP，BP，BPDN算法性能比OMP得到提高，其中，SWOMP的定位精度比OMP高25%，并且这种差距随参考点数据量的增多而明显。以上研究主要将各类CS算法分别应用到室内定位系统中进行性能分析，具体如何优化算法，提高定位系统的定位精度以及减少系统离线工作量是我们下一步的重点研究方向。