文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2018, Vol. 30 Issue (6): 768-775  DOI: 10.3979/j.issn.1673-825X.2018.06.006
0

引用本文 

郑倩, 胡久松, 刘宏立, 肖郭璇, 陈亮, 徐琨. 基于压缩感知的室内定位系统的定位性能分析[J]. 重庆邮电大学学报(自然科学版), 2018, 30(6): 768-775. DOI: 10.3979/j.issn.1673-825X.2018.06.006.
ZHENG Qian, HU Jiusong, LIU Hongli, XIAO Guoxuan, CHEN Liang, XU Kun. Localization performance analysis of indoor positioning system based on compressive sensing[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2018, 30(6): 768-775. DOI: 10.3979/j.issn.1673-825X.2018.06.006.

基金项目

中央国有资本经营预算项目(财企[2013]470号);国家自然科学基金资助项目(61771191);中央高校基本科研项目(1053214004);湖南省自然科学基金项目(2017JJ2052);教育部产学合作协同育人项目(201601004010,201701056026);湖南省普通高校教学改革研究项目(湘教通〔2016〕400号);湖南省研究生创新项目(CX2017B112)

通信作者

刘宏立 hongliliu@hnu.edu.cn

作者简介

郑倩(1994—),硕士研究生,主要研究方向为室内定位。E-mail:qian_enjoy@hnu.edu.cn; 胡久松(1987—),博士研究生,主要研究方向为室内定位、无线传感网络。E-mail:hujiusong2008@163.com; 刘宏立,教授,博士生导师,主要研究方向为智能信息处理与传输技术。E-mail:hongliliu@hnu.edu.cn

文章历史

收稿日期: 2018-01-31
修订日期: 2018-11-20
基于压缩感知的室内定位系统的定位性能分析
郑倩1, 胡久松1, 刘宏立1, 肖郭璇2, 陈亮1, 徐琨1     
1. 湖南大学 电气与信息工程学院,长沙 410082;
2. 国家电网 浙江乐清市供电公司,浙江 乐清 325600
摘要: 随着Wi-Fi技术的普及,Wi-Fi室内定位技术也越来越受到关注。压缩感知(compressive sensing, CS)技术被提出应用于Wi-Fi室内定位,为了研究各类CS算法在室内定位系统中的定位性能,构建出一套基于CS算法的室内位置指纹定位系统。在离线阶段采集数据并构建指纹库,在在线定位阶段采用不同压缩感知算法比较各类算法的定位性能。实验结果表明,设备朝向包含多方向,参考点数据量越多时定位性能更优;CS的算法参数会影响定位性能;在设定的实验环境下,压缩感知中的分段弱正交匹配追踪(stage-wise weak orthogonal matching pursuit, SWOMP)算法的定位精度比K最近邻算法(k-nearest neighbor, KNN)优21.9%;在各类压缩感知算法中,正交匹配追踪(orthogonal matching pursuit, OMP)相较于其他CS算法表现较差,并且这种差距随参考点数据量的增多而愈加明显。
关键词: 室内定位    压缩感知    指纹库    聚类    
Localization performance analysis of indoor positioning system based on compressive sensing
ZHENG Qian1 , HU Jiusong1 , LIU Hongli1 , XIAO Guoxuan2 , CHEN Liang1 , XU Kun1     
1. College of Electrical and Information Engineering, Hunan University, Changsha 410082, P. R. China;
2. State Grid Yueqing Electric Power Supply Company, Zhejiang University, Yueqing, 325600, P. R. China
Foundation Items: The Central State-Owned Capital Management and Budget Project ([2013]470); The National Nature Science Foundation of China(61771191); The Fundamental Research Funds for the Central Universities(1053214004); The Natural Science Foundation of Hunan Province (2017JJ2052); The Ministry of Education Cooperative Education Project(201601004010, 201701056026); The Teaching Reform Project of Hunan Ordinary Colleges and Universities(XJT 2016-400); The Graduate Innovation Project of Hunan Province (CX2017B112)
Abstract: With the popularity of Wi-Fi technology, the WiFi-based indoor positioning technology has fostered growing interests. The compressive sensing (CS) theory has been proposed for the WiFi-based indoor positioning. In order to study the localization performance of the system with various CS algorithms, we construct a CS-based indoor location fingerprinting positioning system. In the system, we collect data and build a fingerprint database firstly in the offline phase, and then in the online phase we use different compressive sensing algorithms to compare the localization performance of the system. Experiments show that: first of all, the larger the reference point data set collected from multiple directions contain, the better the performance of location becomes. Secondly, the algorithm parameters of CS have certain influences on the positioning accuracy. Thirdly, the stage-wise weak orthogonal matching pursuit (SWOMP) algorithm in compressive sensing has a better localization accuracy than the k-nearest neighbor(KNN) algorithm by 21.9% in the experimental environment of the paper. And lastly, among all kinds of compressive sensing algorithms, the orthogonal matching pursuit (OMP) is worse than other CS algorithms, and this difference becomes even more obvious with the growth of reference point data.
Keywords: indoor positioning    compressive sensing    fingerprint database    clustering    
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 室内定位系统框架 Figure 1 Indoor positioning system frame
1.2 离线阶段

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

$ \mathit{\boldsymbol{rs}}{\mathit{\boldsymbol{s}}_i} = {\left( {rs{s_{i1}},rs{s_{i2}}, \cdots ,rs{s_{iL}}} \right)^{\rm{T}}} $ (1)

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

$ \mathit{\boldsymbol{ \boldsymbol{\varPsi} }} = {\left( {\begin{array}{*{20}{c}} {rs{s_{11}}}&{rs{s_{12}}}& \cdots &{rs{s_{1L}}}\\ {rs{s_{21}}}&{rs{s_{22}}}& \cdots &{rs{s_{2L}}}\\ \vdots&\vdots &{}& \vdots \\ {rs{s_{N1}}}&{rs{s_{N2}}}& \cdots &{rs{s_{NL}}} \end{array}} \right)^{\rm{T}}} $ (2)

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

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

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

$ s\left( {i,j} \right) = - \sqrt {{{\left( {\mathit{\boldsymbol{rs}}{\mathit{\boldsymbol{s}}_i} - \mathit{\boldsymbol{rs}}{\mathit{\boldsymbol{s}}_j}} \right)}^2}} $ (3)

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

$ r\left( {i,k} \right) = s\left( {i,k} \right) - \mathop {\max }\limits_{k' \ne k} \left( {a\left( {i,k'} \right) + s\left( {i,k'} \right)} \right) $ (4)

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

$ \begin{array}{*{20}{c}} {a\left( {i,k} \right) = }\\ {\left\{ {\begin{array}{*{20}{c}} {\min \left\{ {0,r\left( {k,k} \right) + \sum\limits_{i' \notin \left\{ {i,k} \right\}} {\max \left( {0,r\left( {i',k} \right)} \right)} } \right\}}&{,i \ne k}\\ {\sum\limits_{i' \notin k} {\max \left( {0,r\left( {i',k} \right)} \right)} }&{,i = k} \end{array}} \right.} \end{array} $ (5)
1.3 在线阶段

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

1.3.1 信号的稀疏表示

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

$ {\mathit{\boldsymbol{\varphi }}_t} = {\left( {rs{s_{t1}},rs{s_{t2}}, \cdots ,rs{s_{tL}}} \right)^{\rm{T}}} $ (6)

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

$ \mathit{\boldsymbol{\theta }} = {\left[ {0, \cdots ,0,1,0, \cdots ,0} \right]^{\rm{T}}} $ (7)

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

$ {\mathit{\boldsymbol{\varphi }}_t} = \mathit{\boldsymbol{ \boldsymbol{\varPsi} \theta }} $

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

$ \mathit{\boldsymbol{\theta }} = {\left[ {0, \cdots ,0,{\lambda _1},0, \cdots ,0,{\lambda _2},0, \cdots ,0,{\lambda _K},0, \cdots ,0} \right]^{\rm{T}}} $ (9)

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

1.3.2 非相干测量

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

$ \mathit{\boldsymbol{y}} = \mathit{\boldsymbol{ \boldsymbol{\varPhi} }}{\mathit{\boldsymbol{\varphi }}_t} = \mathit{\boldsymbol{ \boldsymbol{\varPhi} \boldsymbol{\varPsi} \theta }} $ (10)

可以看出,由于MN,(10)式是一个欠定方程,然而,CS理论解决欠定问题时要求测量基与稀疏基不相干。为解决该问题,文献[11]对测量向量进行正交化预处理

$ \mathit{\boldsymbol{z}} = \mathit{\boldsymbol{Ty}} $ (11)

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

$ \mathit{\boldsymbol{z}} = \mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{R}}^ * } \cdot \mathit{\boldsymbol{ \boldsymbol{\varPhi} \boldsymbol{\varPsi} \theta }} = \mathit{\boldsymbol{Q}}{\mathit{\boldsymbol{R}}^ * } \cdot \mathit{\boldsymbol{R\theta }} = \mathit{\boldsymbol{Q\theta }} $ (12)

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

$ \mathit{\boldsymbol{\hat \theta }} = \arg \min {\left\| \mathit{\boldsymbol{\theta }} \right\|_1}\;\;\;\;{\rm{s}}.{\rm{t}}.\;\;\;\mathit{\boldsymbol{z}} = \mathit{\boldsymbol{Q\theta }} $ (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

② 找到索引,使得:${\lambda _t} = \arg \mathop {\max }\limits_{j = 1,2, \cdots ,N} \left| {\left\langle {{\mathit{\boldsymbol{r}}_{t - 1}},{\mathit{\boldsymbol{q}}_j}} \right\rangle } \right|$

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

④ 求z = 的最小二乘解:

${{\mathit{\boldsymbol{\hat \theta }}}_t} = \arg \mathop {\max }\limits_{{\theta _t}} \left\| {\mathit{\boldsymbol{z}} - {\mathit{\boldsymbol{Q}}_t}{\mathit{\boldsymbol{\theta }}_t}} \right\| = {\left( {\mathit{\boldsymbol{Q}}_t^{\rm{T}}{\mathit{\boldsymbol{Q}}_t}} \right)^{ - 1}}\mathit{\boldsymbol{Q}}_t^{\rm{T}} \cdot \mathit{\boldsymbol{z}}$

⑤ 更新残差rt=z-Qt${{\mathit{\boldsymbol{\hat \theta }}}_t}$=z-Qt(QTtQt)-1QtT·z

t=t+1,如果tK,返回第②步

⑦ 重构所得的${{\mathit{\boldsymbol{\hat \theta }}}_t}$在Λt处有非零项,其值分别为最后一次迭代所得${{\mathit{\boldsymbol{\hat \theta }}}_t}$

贪婪类其他算法是在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 定位区域环境平面图 Figure 2 Environmental plan of interest area

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

2.2 实验结果评估方法

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

$ error = \sqrt {{{\left( {x,y} \right)}^2} - {{\left( {x',y'} \right)}^2}} $ (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 设备面向方向的定位误差 Figure 3 Positioning error of the different orientation of the device
表 1 设备面向方向的定位性能比较 Table 1 Positioning performance of the different orientation of the device

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

2.4 不同参数K, M

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

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

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

图 4 不同K值、M值的定位结果 Figure 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 不同算法的定位结果 Figure 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 不同压缩感知算法的定位性能比较 Table 2 Positioning performance of the different compressed sensing algorithms
图 6 不同压缩感知算法的定位误差累积分布函数图 Figure 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 不同压缩感知算法随参考点数量的变化 Figure 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算法分别应用到室内定位系统中进行性能分析,具体如何优化算法,提高定位系统的定位精度以及减少系统离线工作量是我们下一步的重点研究方向。

参考文献
[1]
WANG X, JIANG M, GUO Z, et al. An Indoor Positioning Method for Smartphones Using Landmarks and PDR[J]. Sensors, 2016, 16(12): 2135. DOI:10.3390/s16122135
[2]
杨小凤, 陈铁军, 黄志文, 等. 基于超宽带的TOA-DOA联合定位方法[J]. 重庆邮电大学学报:自然科学版, 2016, 28(2): 194-198.
YANG Xiaofeng, CHEN Tiejun, HUANG Zhiwen, et al. Joint TOA-DOA estimation for UWB based positioning[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2016, 28(2): 194-198.
[3]
刘辉元, 马金辉, 黄琼. 基于改进克里金插值的室内定位位置指纹库构建方法[J]. 重庆邮电大学学报:自然科学版, 2017, 29(6): 751-757.
LIU Huiyuan, MA Jinhui, HUANG Qiong. Construction method of fingerprint database based on improved Kriging interpolation for indoor location[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2017, 29(6): 751-757.
[4]
ZOU H, JIN M, JIANG H, et al. WinIPS: WiFi-based Non-intrusive Indoor Positioning System with Online Radio Map Construction and Adaptation[J]. IEEE Transactions on Wireless Communications, 2017, 16(12): 8118-8130. DOI:10.1109/TWC.2017.2757472
[5]
田增山, 舒月月, 刘仪瑶, 等. 改进的蜂窝网室内定位匹配算法[J]. 重庆邮电大学学报:自然科学版, 2017, 29(6): 744-750.
TIAN Zengshan, SUH Yueyue, LIU Yiyao, et al. Improved indoor localization matching algorithm for cellular networks[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2017, 29(6): 744-750.
[6]
KAEMARUNGSI K, KRISHNAMURTHY P. Modeling of indoor positioning systems based on location fingerprinting[J]. Proceedings-IEEE INFOCOM, 2004, 2(2): 1012-1022.
[7]
LI B, SALTER J, DEMPSTER A G, et al. Indoor positioning techniques based on wireless LAN[C]//IEEE International Conference on Lan. [S.l.]: [s.n.], 2007: 13-16.
[8]
ROOS T, MYLLYMAKI P, TIRRI H, et al. A Probabilistic Approach to WLAN User Location Estimation[J]. International Journal of Wireless Information Networks, 2002, 9(3): 155-164. DOI:10.1023/A:1016003126882
[9]
IMRAN S, KO Y B. A Novel Indoor Positioning System Using Kernel Local Discriminant Analysis in Internet-of-Things[J]. Wireless Communications & Mobile Computing, 2018(2): 1-9.
[10]
DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306. DOI:10.1109/TIT.2006.871582
[11]
FENG C, AU W S A, VALAEE S, et al. Compressive sensing based positioning using RSS of WLAN access points[C]//IEEE INFOCOM. San Diego, CA, USA: IEEE, 2010: 1-9. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5461981
[12]
何风行, 余志军, 刘海涛. 基于压缩感知的无线传感器网络多目标定位算法[J]. 电子与信息学报, 2012, 34(3): 716-721.
HE Fenghang, YU Zhijun, LIU Haitao. Multiple Target Localization via Compressed Sensing in Wireless Sensor Networks[J]. Journal of Electronics & Information Technology, 2012, 34(3): 716-721.
[13]
RAMADAN R, JWAIFEL A, AL-TOUS H, et al. Compressive sensing with weighted coefficient approach for indoor source localization[C]//International Conference on Telecommunications and Signal Processing. Barcelona, Spai: IEEE, 2017: 243-246.
[14]
BRENDAN J F, DELBERT D. Clustering by passing messages between data points[J]. Science, 2007, 315(1): 972-977.
[15]
BAI S, WU T. Analysis of K-Means algorithm on fingerprint based indoor localization system[J]. Journal of Theoretical Biology, 2007, 246(3): 510-521. DOI:10.1016/j.jtbi.2006.12.033
[16]
石光明, 刘丹华, 高大化, 等. 压缩感知理论及其研究进展[J]. 电子学报, 2009, 37(5): 1070-1081.
SHI Guangming, LIU Danhua, GAO Dahua, et al. A dvances in Theory and Application of Compressed Sensing[J]. Acta Electronica Sinica, 2009, 37(5): 1070-1081. DOI:10.3321/j.issn:0372-2112.2009.05.028
[17]
MALLAT S G, ZAHNG Z. Matching pursuits with time-frequency dictionaries[J]. IEEE Trans on Signal Processing, 1993, 41(12): 3397-3415. DOI:10.1109/78.258082
[18]
LEE J, GIL G T, YONG H L. Channel Estimation via Orthogonal Matching Pursuit for Hybrid MIMO Systems in Millimeter Wave Communications[J]. IEEE Transactions on Communications, 2016, 64(6): 2370-2386. DOI:10.1109/TCOMM.2016.2557791
[19]
NEEDELL D, VERSHYNIN R. Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit[J]. Foundations of Computational Mathematics, 2009, 9(3): 317-334. DOI:10.1007/s10208-008-9031-3
[20]
LI H. Improved analysis of SP and CoSaMP under total perturbations[J]. Eurasip Journal on Advances in Signal Processing, 2016, 2016(1): 112. DOI:10.1186/s13634-016-0412-5
[21]
BLUMENSATH T, Davies M.E. Stagewise Weak Gradient Pursuits[J]. Signal Processing, IEEE Transactions on, 2009, 57(11): 4333-4346. DOI:10.1109/TSP.2009.2025088
[22]
DO T T, LU G, NGUYEN N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//Signals, Systems and Computers, 2008, Asilomar Conference on. Pacific Grove, CA, USA: IEEE, 2009: 581-587. https://ieeexplore.ieee.org/document/5074472
[23]
KIM S J, KOH K, LUSTIG M, et al. An Interior-Point Method for Large-Scale l1-Regularized Least Squares[J]. IEEE Journal of Selected Topics in Signal Processing, 2008, 1(4): 606-617.
[24]
FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597. DOI:10.1109/JSTSP.2007.910281
[25]
LIU X J, XIA S T, FU F W. Reconstruction Guarantee Analysis of Basis Pursuit for Binary Measurement Matrices in Compressed Sensing[J]. IEEE Transactions on Information Theory, 2017, 63(5): 2922-2932.
[26]
CANDES E, ROMBERG J. l1-MAGIC: Recovery of Sparse Signals via Convex Programming[EB/OL]. (2015-05-29) [2017-12-25]. https://download.csdn.net/download/skcsdn28/8751521.