一种使用信号强度排序集合的单信标定位算法

李栋孟，罗海勇，吴 彬，陈自力

(1.中国科学院计算技术研究所 移动计算与新型终端北京市重点实验室，北京 100190；2.北京三星通信研究院，北京 100028)

1 引言

随着无线网络的广泛部署和应用，以及基于位置服务的应用程序如社交网络、个性化推荐等的蓬勃发展，基于无线保真(wireless fidelity，WiFi)的室内定位技术得到了研究人员的广泛关注。现如今广泛使用的基于WiFi指纹的定位方法都是利用接收信号强度(received signal strength indicator，RSSI)作为度量[1-2]，但是由于室内环境中的反射、衍射、散射等多径效应的影响，使得在同一位置的RSSI会有很大区别[3]，如图1所示，在同一位置上的RSSI差别可以达到14 dB左右，RSSI的巨大的波动性导致了定位性能不理想。所以，寻求一个更可靠的度量迫在眉睫。这个度量应该更稳定，并且有可以区分多径效应的能力。现如今，被广泛应用的正交频分复用技术(orthogonal frequency division multiplexing，OFDM)中，数据被调制在不同的频率的副载波上，并且同时传输，这很好地表现了多径效应。而在802.11n标准中，信道响应可以以信道状态信息(channel state information，CSI)的形式从OFDM系统中抽取出来，它反映了每一个子载波的幅度和相位。和一个数据包只能接收到一个RSSI值相比，可以得到多个CSI值，并且这些值随时间变化很小。基于CSI，本文利用信道与信道之间的关系，提出了一个使用信号层次化排序集合的单信标定位算法，本文的算法包括两个部分：首先用一个简单并且有效的算法从单个信标的各个信道中提取出CSI特征值，利用该特征值来建立指纹库；然后，利用指纹匹配算法进行相关计算来确定位置。

图1 RSSI概率分布图

2 相关研究

由于OFDM技术的使用，在802.11n中，信道响应可以从OFDM接受器中以CSI的形式提取出来[4-5]。CSI描述了一个信号从发射端到接收端不同传播路径的信息，是散射、衍射以及衰减等的结合效应。目前，基于CSI的室内定位已经吸引了很多研究人员的兴趣，一些先前的研究已经可以达到亚米甚至厘米级的定位精度。

文献[6]利用细粒度CSI的频率差异性建立了基于CSI的信号传播衰减模型FIFS，尽管在定位精度上有很大提升，但是由于现如今WiFi协议的宽带限制，导致在单个路径上的区分性还不是很理想。

文献[7]建立了基于CSI的指纹匹配算法PinLoc，通过计算每个位置的混合高斯分布，来建立指纹库进行定位，但是没有利用AP的一个重要的特性：空间差异性。

文献[8]则充分利用信标的空间差异性和频率差异性建立了一个基于概率模型的指纹定位算法，将每个位置的不同信道的CSI通过处理得到有效CSI，然后通过计算贝叶斯后验概率得到估计位置。

以上研究都只是通过抽取多径分量的射频功率作为测距或者射频指纹，并没有探究多个信道之间的关系。本文从不同信道之间的关系出发，提出了一种使用CSI的单信标指纹定位算法，实验结果表明只使用一个信标的定位精度明显优于基于RSSI的算法的定位精度，平均精度可以达到0.95 m。

3 使用信号强度排序集合的单信标定位算法

使用信号强度排序集合的单信标定位算法包含以下两个步骤：

1)离线训练阶段：处理从一个信标接收到的30个信道的原始CSI信息，找到每一个信道CSI的特征值；然后，基于信道与信道之间特征值的关系构建指纹库；

2)在线定位阶段：基于测试样本信道与信道之间CSI特征值的关系，比较它们与指纹库中数据的相似性，找到最相似的K个，求取这K个位置的加权质心[9]，即为目标位置。

3.1 离线训练阶段

构建指纹库需要两个步骤。

1)信道特征值提取

图2为第3信道的信号变化情况，实验中，通过在一个固定位置采集同一个信标的第3信道的CSI值，并画出CSI的概率分布图，图2(a)总共采集50次CSI值，图2(b)总共采集100次，图2(c)总共采集200次，采集间隔均为3 s，因为终端的扫描间隔是1 s，间隔3 s采一次可以保证每次的CSI都是新的。

图2 CSI概率分布图

从图2中可以看出，无论采集时间的长短，那些出现频率很高的CSI值总是非常接近的，基于这个发现，提出了一个新的描述单一信道特征值的方法为

(1)

式(1)中，cValue表示每一个独立信道的特征值。CSIpeak是这个信道出现频率最大的CSI的幅度的值，如果测量获得信道幅度值出现的概率都一样，则选取CSI值最大的那个作为特征值，因为值越大，这个值就越有意义。式(1)是比较理想化的，因为在实际中wL和wR并不好确定，所以在实际中使用的公式为

(2)

将式(1)中的wL和wR设为同一个值，于是就变成了式(2)，相比式(1)而言，式(2)可以很方便地通过多次测算，找到最优的w。

2) 指纹库构建

构建指纹库是基于指纹的定位方法最关键的部分，构建指纹库的方式不同，也就构成了不同定位算法。

图3 不同信道CSI对比图

图3表示的是信道2和信道15的60次采样的CSI幅度变化情况，虽然在某一信道上的CSI值会有所变化，但是不同信道之间的CSI差值基本保持稳定。基于信道与信道之间的关系，本文构建指纹库为

fpIDCor{IDCor，(KEY0θ，VALUE0θ，...，
KEYnθ，VALUEnθ)}

(3)

式(3)中，fpIDCor表示的是在IDCor(基准点坐标)处的指纹库，KEYn表示信道n，而VALUEnθ表示的是在位置IDCor处其他信道的幅度值小于信道n处θ个db的所有信道的集合。式(3)中的θ是最关键的参数，因为每一个信道处的CSI幅度都有一定的波动，所以θ的选取要略大于这个波动值[10]。例如，在位置x测量到了6个信道的CSI值，按照式(2)计算每个信道的特征值，如表1所示。得到每个信道的特征值后按照式(3)构建位置x的指纹，(此处θ的值取3)，最后建立的指纹库如表2所示。

表1 信道特征值

这种构建指纹库的方式实质是建立信道和信道之间的关系，使用这种关系来表示某一特定位置的特征，在定位阶段通过这种关系的相似度来进行定位。

表2 信道指纹库

3.2 在线定位算法

在线定位阶段，需要用接收到的CSI的值与离线阶段训练得到的指纹库相比较，找到最为相似的作为定位位置。具体来说就是使用式(3)将在某个位置实时接受到的CSI值构建一条未知的指纹cpUnknown，然后在离线训练阶段构建的指纹库里面去匹配找到最相似的指纹，该指纹对应的位置即是定位位置。具体的匹配算法如表3所示。

简单来说，匹配算法就是遍历指纹库里每一个基准点的指纹，然后针对每一条指纹查找那些与未知指纹中具有相同key的集合，查找两个集合中相同信道的数目，累计起来，把这个累计的数作为这个位置的得分，得分最高的那个位置即是预测的位置。由于单一位置会出现风险较大的情况，这里选取得分最高的K个位置，然后利用加权最近邻算法(k weighted nearest neighbors，KWNN)求出目标位置，实验结果表明，用KWNN方法定位精度比用最高分作为目标位置要高。

4 实验结果及分析

4.1 实验设置

为了评估算法的定位精度，在中国科学院计算技术研究所科研楼7层的部分区域进行定位实验，具体部署环境如图4所示，定位区域面积为6 m×6 m，定位区域划分为12个网格，网格间间隔是1 m，红色五角星处为发射信标。实验中使用TP-LINK的路由器，利用装配有Intel WiFi Link 5300 802.11n 网络接口卡的Thinkpad x200作为接收端。实验中修改了驱动来接受CSI的值[11]。采集阶段，在每个网格采样100次，作为训练数据。定位阶段每个点采取20次作为测试样本。

图4 实验环境布局

实验对定位区域不同θ的影响、不同K值的影响、时间迁移性的影响以及CSI与RSSI的比较等进行实验，并基于累计误差分布函数(cumulative distribution function，CDF)图来表示定位性能。

4.2 不同θ值比较

指纹库建立采用不同θ值的实验评估，不同θ的选取对定位精度有一定的影响，如图5及图6所示，实验分别对θ大小从1至6进行测试，结果表明在θ值为3时，定位精度最高，在误差1.5 m时，定位精度约为90%。分析其原因是每个信道的CSI值有一定的波动性，当θ值略大于该波动性时候，才能区分不同信道，指纹库的构建才有意义。

图5 不同θ的定位精度的CDF图(θ=1，2，3)

图6 不同θ的定位精度CDF图(θ=3，4，5)

4.3 不同K值比较

对KWNN中不同数目K的实验，K为选取最相似的点的个数，通过对不同的K值得选取，和不使用KWNN(即K=1，利用得分最高的为定位位置)，分别进行实验并对结果分析比较，实验结果如图7所示。

图7 不同K值定位精度的CDF图

从图7可以看出，K=3和K=4时，定位精度最高，在1.5 m误差的定位精度大于90%。但是随着K的增大，定位精度反而下降。分析其原因是随着K的增加，偏离正确位置的点的数目也相应增多，所以最终加权得到的位置偏离实际位置会相应增大，最终导致定位精度下降。因此，利用KWNN，可以提高定位精度，并且在这里K最好取3，因为K=3和K=4定位效果相当，但随着K增加，算法计算复杂度增加，所以选取3比较合理。

4.4 时间迁移性

不同时间段定位性能的稳定性是室内定位需要考虑的一个重要问题，为此我们分别在早上8点、下午5点、晚上9点对目标位置进行采样评估，实验结果如图8所示，从图中可以看出，不同时间段的定位性能差别不大，在1.5 m误差的定位精度基本都可以达到90%，这表明基于CSI的单信标指纹定位算法比较稳定，非常适合于室内定位。

图8 时变性定位精度的CDF图

4.5 CSI与RSSI比较

实验还对RSSI和CSI做了比较，本文采用同样方法，利用任意10个信标对RSSI进行同样的实验，来与CSI作对比，结果如图9所示，从图中可以看出仅仅用1个信标的CSI的定位效果也要比使用10个信标的RSSI的定位效果好。

图9 CSI与RSSI定位性能比较

4.6 算法复杂度分析

基于CSI的单信标指纹定位算法的复杂度主要来源于两个方面，一方面是离线阶段指纹库的构建，其复杂度是O(n2)，n是信道的数目；另一方面是在线定位阶段的匹配过程，其复杂度是O(n×m)，n是信道的数目，m是指纹库中信道k对应的指纹，且0≤m≤n。

5 结束语

本文提出了一种使用信号强度排序集合的单信标定位算法。离线训练阶段先提取出样本中每一个信道的特征值，利用不同信道的特征值构建指纹库；在线定位阶段利用接受到的不同信道的CSI值之间的关系，与指纹库中的相匹配，得到最匹配的K个点，利用KWNN算法得到目标位置。然后，通过对θ值、K数目、时间迁移性以及与RSSI对比等方面实验进行实验评估，实验结果表明利用单个信标的基于CSI的指纹定位算法的平均定位精度可以达到0.95 m，适合室内定位。下一步研究可以在以下方向进行，一方面，可以利用多个信标来改善定位精度；另一方面，由于如今的智能手机已经装配有802.11n芯片，所以可以尝试在手机上实现本文的定位算法。

[1] KUSHKI A，PLATANIOTIS K N，VENETSANOPOULOS A N.Kernel-based Positioning in Wireless Local Area Networks[J].IEEE Transactions on Mobile Computing，2007，Montreal，2007，6(6)：689-705.

[2] MIKKEL B K，GEORG T，CLAUDIA L.Zone-based RSS Reporting for Location Fringerprinting[C]//Proceedings of the 5th International Conference on Pervasive Computing.Toronto：Springer Berlin Heidelberg，2007：316-333.

[3] MOUSTAFA Y，ASHOK A.The Horus WLAN Location Determination System[EB/OL].[2014-08-02].http：//www.cs.umd.edu/～moustafa/papers/horus_usenix.pdf.

[4] DANIEL H，HU Wen-jun，ANMOL S，et al.Predictable 802.11 Packet Delivery from Wireless Channel Measurements[EB/OL].[2014-08-02].http：//homes.cs.washington.edu/～dhalperi/pubs/comm356s-halperin.pdf.

[5] APURV B，CHEN Yi-chao，SWATI R，et al.Harnessing Frequency Diversity in Wi-Fi Networks[EB/OL].[2014-08-02].//http：//www.cs.utexas.edu/～swati/freq-div-mob11.pdf.

[6] WU Kai-shun，XIAO Jiang，YI You-wen，et al.Fila：Fine-grained Indoor Localization[C]//Proceedings of the 31st IEEE Conference on Computer Communications.Orlando，Florida：IEEE，2012：2210-2218.

[7] SOUVIK S，ROMIT R C，SRIHARI N.SpinLoc：Spin once to Know Your Location[EB/OL].[2014-08-02].http：//www.cse.sc.edu/～srihari/pubs/SpinLoc_HotMobile12.pdf.

[8] XIAO Jiang，WU Kai-shun，YI You-wen，et al.Fimd：Fine-grained Device-free Motion Detection[C]//Proceedings of the 18th IEEE International Conference on Parallel and Distributed Systems.Singapore：IEEE，2012：229-235.

[9] BAHL P，PADMANABHAN V N.Radar：an In-building RF-based User Location and Tracking System[C]//Proceedings of 19th Annual Joint Conference of the IEEE Computer and Communications Societies.Tel Aviv：IEEE，2000：775-784.

[10] SUNGWON Y，DESSAI P，VERMA M，et al.FreeLoc：Calibration-free Crowdsourced Indoor Localization[C]//Proceedings of the 32nd IEEE International Conference on Computer Communications.Turin：IEEE，2013：2481-2489.

[11] DANIEL H，HU Wen-jun，ANMOL S.Tool Release：Gathering 802.11n Traces with Channel State Information[C]//Proceedings of the ACM SIGCOMM Computer Communication Review.New York：ACM，2011：53-53.