基于流形插值数据库构建的WLAN室内定位算法

周 牧 唐云霞 田增山 卫亚聪



基于流形插值数据库构建的WLAN室内定位算法

周 牧①②唐云霞*①田增山①卫亚聪①

①(重庆邮电大学移动通信技术重庆市重点实验室 重庆 400065)②(天津师范大学天津市无线移动通信与无线电能传输重点实验室 天津 300387)

针对传统无线局域网(WLAN)室内定位系统中因参考点密集分布及逐点信号采集所带来的位置指纹数据库构建工作量繁重的问题，该文提出一种基于混合半监督流形学习和3次样条插值的数据库构建方法。该方法利用少量标记数据和大量未标记数据求解定位目标函数的最优解，同时根据高维信号强度空间与低维物理位置空间的映射关系，实现对未标记数据的位置标定。大量实验结果表明，该方法能够在保证较高定位精度的同时，显著降低位置指纹数据库的构建开销。

无线局域网；位置指纹；半监督学习；流形对齐；3次样条插值

1 引言

随着移动设备的便携化发展，人们对于室内基于位置信息的服务需求与日俱增[1]。全球定位系统(Global Positioning System, GPS)和蜂窝定位系统虽然在室外环境中能达到较高的定位精度，但在室内环境中信号容易受到建筑物或设施的遮挡，使得上述定位系统无法提供精确的位置服务。与此同时，由于无线局域网(Wireless Local Area Network, WLAN)具有易安装、易扩展、保密性和抗干扰能力强等优点，基于WLAN接收信号强度(Received Signal Strength, RSS)的位置指纹定位方法备受关注[2,3]，该方法与基于信号到达时间(Time Of Arrival, TOA)[4]和到达角度(Angle Of Arrival, AOA)[5]的WLAN定位方法相比，前者仅利用现有WLAN网络且无需硬件设备的升级改造，同时具有较高的定位精度，从而可以有效满足人们在复杂室内环境中的定位需求。

位置指纹定位是一种基于模式分类的定位方法，其利用RSS样本与位置坐标的映射关系来实现用户的位置估计。该方法通常分为两个阶段：离线阶段和在线阶段。在离线阶段，需在目标区域内标记若干参考点(Reference Point, RP)，并在每个参考点处采集来自多个接入点(Access Point, AP)的RSS样本(即位置指纹)，建立目标区域所对应的指纹数据库。考虑室内无线信号的波动性，在每个参考点处需采集多个RSS样本以刻画参考点的信号统计特性。在在线阶段，利用相应的信号空间搜索匹配算法，将用户新采集的RSS样本与预先存储的指纹数据库进行匹配，选择若干邻近参考点来实现对用户的位置估计。

由此可见，传统位置指纹定位需在离线阶段采集每个参考点处的RSS样本，从而得到大量具有位置标定的数据(即标记数据)，该过程的人力及时间开销随着目标区域的增大而显著增加。为了解决这一问题，文献[6-8]利用易于采集的大量未标记RSS数据与少量RSS标记数据来构建指纹数据库，以降低离线阶段的工作量。但是，这类方法未考虑室内无线信号的波动性问题，即一旦出现因多径效应等因素所造成的RSS样本剧烈畸变，则无法实现有效的位置指纹匹配，从而造成定位精度的严重恶化。

针对上述问题，本文提出基于混合半监督流形学习和3次样条插值的数据库构建方法，其利用大量未标记物理位置的用户路径数据，并结合用户路径的RSS样本时间戳及标记数据的物理位置邻近信息来增强高维空间邻近RSS数据的相关性，从而保证较高的定位精度。此外，采用施行特征函数来估计能够有效刻画每个参考点处信号统计特征所需的最少标记RSS样本个数(即样本容量)，以降低指纹数据库的构建开销。

2 数据库构建

2.1 算法流程

图1给出了本文所提混合半监督流形学习和3次样条插值的数据库的构建过程。首先，利用假设检验方法估计每个参考点处所需采集的RSS样本容量，并通过随机采集大量未标记物理位置的用户路径数据，构建相应的稀疏指纹数据库。其次，采用3次样条插值方法扩充稀疏指纹数据库，并基于流形学习算法将未标记数据与指纹数据进行信息融合，实现对未标记数据的物理位置标定，进而完成对指纹数据库的拓展；最后，利用K近邻(K-Nearest Neighbor, KNN)算法，实现对用户的位置估计。

2.2 样本容量

由于室内无线信号的波动性，传统指纹定位需在每个参考点处采集大量RSS样本，并计算其统计量(如均值)作为该参考点的位置指纹，从而指纹数据库的构建需要耗费大量的人力和时间开销。针对这一问题，本文提出采用假设检验方法来估计能够有效刻画每个参考点处信号统计特征所需的最少RSS样本容量，以降低指纹数据库的构建开销。

图1 本文所提混合数据库构建过程

假设每个参考点处RSS样本的理想均值、总体均值和样本均值[9]分别为,和，则根据法则，得到RSS样本均值误差的接受范围为。为了降低第1类错误的影响，本文通过设定显著性水平()，使得犯此类错误的概率不超过。由于犯第2类错误的概率依赖于RSS样本容量，所以本文利用施行特征函数来确定样本容量，使得犯第2类错误的概率不超过。由文献[10]可知，。基于此，本文双边假设检验问题定义为

2.3样本插值

插值方法在定位领域经常被用来提高定位精度[12]，图2为不同插值方法(3次样条插值(CUBIC)、线性插值(Linear)、径向基插值(RBF))与无插值(KNN)时的性能对比。从图2可知，3次样条插值的定位性能与稳定性都优于其他插值方法，故本文利用3次样条插值方法对未标记参考点处的RSS均值进行插值。具体方法如下：首先，令目标区域内的参考点、标记参考点和未标记参考点的位置集分别为,和，其中，；其次，对于第个未标记参考点处来自第个接入点的RSS均值，通过计算距离找到其所对应的个近邻标记参考点及其对应的来自第个接入点的RSS均值；最后，利用个近邻标记参考点估计RSS均值。

图2 不同插值方法的定位性能比较

(4)

3 数据库拓展

3.1 拉普拉斯特征映射

本文利用拉普拉斯特征映射(LaplacianEigenmap, LE)[13]算法，对高维信号样本进行位置标定。该算法保证在高维信号空间中距离邻近的样本映射到低维空间中也邻近[14]。对应于WLAN室内定位系统，若接收到的高维RSS样本相似，则所对应的目标用户位置在低维空间中邻近。算法将数据分为两类：标记数据和未标记数据。两类数据的主要区别是：前者为每个参考点处真实采集或插值估计得到的数据，其包含位置信息；而后者为未标记物理位置的用户路径数据，其仅含有RSS和时间戳信息。

(6)

(8)

3.2 高维数据标定

为了求解上述最小化问题且保持高维空间中邻近RSS数据的相关性，权值矩阵和拉普拉斯矩阵的计算过程如下：假设目标区域内存在个接入点，分别对高维RSS样本、路径的未标记数据时间戳和标记数据位置建立邻接矩阵,和，其所包含的第行列元素分别为

(12)

3.3核参数校准

(16)

4 实验测试及性能分析

4.1实验环境

实验环境如图3所示，65.0 m×18.5 m典型WLAN室内环境，其包括走廊和大厅的4个子区域。环境中布置5个接入点，选用三星S7568手机和自主开发的WLAN信号采集软件采集RSS样本(采样频率1 Hz)。环境中均匀标记327个参考点且在每个参考点处采集20个RSS样本(即样本容量20)，同时随机选择10条未标记位置信息的用户路径并采集1210个未标记RSS样本。

4.2参数比较

4.2.1样本容量 图4给出了在不同样本容量条件下利用皮尔逊相关系数[18]得到的子区域3中每个参考点处采集来自不同接入点的RSS值的信号相似度。以所有参考点接收到AP3的RSS值为例，样本容量10和100所对应的信号热度图相似度仅为75.82%，而样本容量20和100所对应的信号热度图相似度可提高到91.93%。从而，验证了本文所选样本容量20能够有效刻画每个参考点处采集信号的变化特征。

图5比较了在不同样本容量条件下的定位误差。可见，当样本容量增加时定位误差降低，此外，当样本容量大于20时定位误差变化不明显。

图3 实验环境平面图

图4 子区域3的皮尔逊相关系数

图5 不同样本容量条件下的定位误差

4.2.3时间戳 由于同一RSS序列所包含的时间戳信息能够有效刻画权重矩阵中不同RSS样本之间的邻近关系，图7比较了考虑和不考虑时间戳信息的混合位置指纹数据库所对应的定位误差。可见，前者所对应定位误差在3 m内的置信概率为74.35%，其高于后者近10%。

4.3定位性能

图8比较了不同数据库所对应的定位误差，图9比较了分别利用传统数据库[2]、流形数据库[6]和本文数据库所得到的测试点估计位置和真实位置，其中，对应位置间用线段连接。可见，本文数据库在降低整体定位误差的同时，还可有效剔除大误差点(即减小拖尾误差概率)。图10给出了不同标记RSS样本数条件下的平均定位误差。可见，当标记RSS样本数较多时，3种数据库所对应的定位误差相近，而当标记RSS样本数较少时，3种数据库所对应的定位误差均呈上升趋势，且传统数据库的性能最为恶化。由此可知，本文数据库具有最优的定位性能，且在标记RSS样本数较少的情况下具有较好的稳定性。

4.4 数据库构建开销

图11比较了不同参考点数条件下数据库构建所需的时间开销。可见，当参考点个数为327时，构建流形和本文数据库所需的时间开销仅为传统数据库的10%左右。此外，由于构建传统数据库需要在每个参考点处采集400个RSS样本且采样频率为1 Hz，于是RSS采集时间为。然而，流形和混合数据库的构建仅需在每个参考点处采集20个RSS样本，同时随机采集10条用户路径以得到1210个未标记RSS样本，所需时间开销为，其相对于传统数据库的构建减少约34.1 h的RSS采集时间。综上所述，本文数据库能够在保证较高定位精度的同时，显著降低位置指纹数据库的构建开销。

图6 不同和值条件下的核校准结果

图7 时间戳信息对定位误差的影响

图8 不同数据库所对应的定位误差

图9 不同数据库所对应的测试点估计位置

图10 不同标记RSS样本数条件下的平均定位误差

图11 不同参考点数条件下的数据库构建开销

5 结束语

本文所提基于混合半监督流形学习和3次样条插值的指纹库构建方法相比于传统方法的改进内容如下：首先，利用假设检验方法对每个参考点处需要采集的RSS样本容量进行优化，以降低标记数据的采集开销；其次，结合未标记位置信息的用户路径数据，采用流形学习方法拓展位置指纹数据库以提高系统的定位性能；最后，通过考虑用户路径数据中所包含的时间戳信息，进一步提高数据库的定位精度和稳定性。实验结果表明，本文所提数据库构建方法无需改变现有WLAN网络硬件设施，且能够在保证较高定位精度的同时，显著降低离线阶段数据库的构建开销。

[1] KASHIF A, TAYYAB J, HOSSAM S H,. Non-audible acoustic communication and its application in indoor location-based services[C]. IEEE Wireless Communications and Networking Conference, Doha, Qatar, 2016: 1-6.

[2] 周牧, 蒲巧林, 田增山. 室内WLAN定位中位置指纹优化的接入点部署方法[J]. 通信学报, 2015, 36(Z1): 30-41. doi: 10.11959/j.issn.1000-436x.2015279.

ZHOU Mu, PU Qiaolin, and TIAN Zengshan. Location fingerprint optimization based access point deployment in indoor WLAN localization[J]., 2015, 36(Z1): 30-41. doi: 10.11959/j.issn.1000-436x.2015279.

[3] 陈兵, 杨小玲. 一种基于概率密度的WLAN接入点定位的算法[J]. 电子与信息学报, 2015, 37(4): 855-862. doi: 10.11999/ JEIT140661.

CHEN Bing and YANG Xiaoling. A WLAN access point localization algorithm based on probability density[J].&, 2015, 37(4): 855-862. doi: 10.11999/JEIT140661.

[4] HE Jie, LI Shen, PAHLAVAN Kaveh,. A realtime testbed for performance evaluation of indoor TOA location system[C]. IEEE International Conference on Communications, Ottawa, Canada, 2012: 482-486.

[5] TAPONECCO L, AMICO A D, and MENGALI U. Joint TOA and AOA estimation for UWB localization applications [J]., 2011, 10(7): 2207-2217. doi: 10.1109/TWC.2011.042211.100966.

[6] ZHANG Liye, MA Lin, and XU Yubin. A semi-supervised indoor localization method based on l1-graph algorithm[J].(), 2015, 22(4): 55-61.

[7] OUYANG R, WONG A, LEA C,. Indoor location estimation with reduced calibration exploiting unlabeled data via hybrid generative/discriminative learning[J]., 2011, 11(11): 1613-1626. doi: 10.1109/TMC.2011.193.

[8] PAN J J, PAN S J, YIN J,.Tracking mobile users in wireless networks via semi-supervised colocalization[J]., 2012, 34(3): 587-600. doi: 10.1109/TPAMI.2011.165.

[9] 励晶晶, 郭文. 两类错误条件下的样本容量选择[J]. 统计与决策, 2010, (15): 14-18.

LI Jingjing and GUO Wen. Select the sample size under two types of error conditions[J]., 2010, (15): 14-18.

[10] 贾俊平. 统计学[M]. 北京. 中国人民大学出版社. 2011: 220-224.

JIA Junping. Statistics[M]. Beijing, China Renmin University Press, 2011: 220-224.

[11] 彭小辉, 晏政, 李艳军, 等. 一种基于解析冗余关系的半定性故障隔离方法在航天器推进系统中的应用[J]. 国防科技大学学报. 2012, 34(6): 104-110. doi: 10.3969/j.issn.1001-2486. 2012.06.018.

PENG Xiaohui, YAN Zheng, LI Yanjun,. A semi- qualitative fault isolation method based on analytical redundancy relations for spacecraft propulsion system[J]., 2012, 34(6): 104-110. doi: 10.3969/j.issn.1001-2486.2012.06.018.

[12] 陈家琪, 严梓乘. 一种Newton插值的RFID室内定位改进算法[J]. 计算机系统应用, 2012, (1): 45-48. doi: 10.3969/j.issn. 1003-3254.2012.01.010.

CHEN Jiaqi and YAN Zicheng. Improvement algorithm of Newton interpolation for RFID indoor positioning[J].&, 2012, (1): 45-48. doi: 10. 3969/j.issn.1003-3254.2012.01.010.

[13] BELKIN M and NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation[J]., 2003, 15(6): 1373-1396. doi: 10.1162/ 089976603321780317.

[14] SHI Lei, ZHANG Lefei, ZHAO Lingli,. Adaptive Laplacian eigenmap-based dimension reduction for ocean target discrimination[J]., 2016, 13(7): 902-906. doi: 10.1109/LGRS. 2016.2553046.

[15] ZHANG Yanming, HUANG Kaizhu, HOU Xinwen,. Learning locality preserving graph from data[J]., 2014, 44(11): 2088-2098.doi: 10.1109/TCYB.2014.2300489.

[16] 曾孝平, 刘刈, 刘国金. 基于图谱理论和随机游走核的图像去噪[J]. 通信学报. 2010, 31(7): 116-121. doi: 10.3969/j.issn. 1000-436X.2010.07.017.

ZENG Xiaoping, LIU Yi, and LIU Guojin. Image denoising based on spectral graph theory and random walk kernel[J]., 2010, 31(7): 116-121. doi: 10.3969/j.issn.1000-436X. 2010. 07.017.

[17] 金珠. 改进的支持向量机分类算法及其在煤矿人因事故安全评价中的应用[D]. [博士论文], 中国矿业大学, 2011, 81-89. JIN Zhu. Improved support vector machine classification algorithm and application for human factors of coal mine accidents safety evaluation[D]. [Ph.D. dissertation], China University of Mining, 2011, 81-89.

[18] RENAN S, PASCAL D C, RICHARD P,. Human step detection from a piezoelectric polymer floor sensor using normalization algorithms[C].IEEE Sensors 2014, Valencia, Spain, 2014: 1169-1172.

WLAN Indoor Localization Algorithm Based on Manifold Interpolation Database Construction

ZHOU Mu①②TANG Yunxia①TIAN Zengshan①WEI Yacong①

①(,,400065,)②(,,300387,)

To deal with the high cost involved in the location fingerprint database construction due to the dense Reference Points (RPs) distribution and point-by-point Received Signal Strength (RSS) collection in the conventional Wireless Local Area Network (WLAN) indoor localization systems, a new database construction approach based on the integrated semi-supervised manifold learning and cubic spline interpolation is proposed. The proposed approach utilizes a small amount of labeled data and a massive amount of unlabeled data to find the optimal solution to localization target function, and meanwhile relies on the mapping relations between the high-dimensional signal strength space and low-dimensional physical location space to calibrate the unlabeled data with location coordinates. The extensive experiments demonstrate that the proposed approach is able to guarantee the high localization accuracy, as well as significantly reduce the cost involved in location fingerprint database construction.

Wireless Local Area Network (WLAN); Location fingerprint; Semi-supervised learning; Manifold alignment; Cubic spline interpolation

TN929.5

A

1009-5896(2017)08-1826-09

10.11999/JEIT161269

2016-11-24；

改回日期：2017-03-20；

2017-05-02

唐云霞 13629735505@139.com

国家自然科学基金(61301126)，长江学者和创新团队发展计划(IRT1299)，重庆市科委重点实验室专项经费，重庆邮电大学青年科学研究项目(A2013-31)

The National Natural Science Foundation of China (61301126), The Program for Changjiang Scholars and Innovative Research Team in University (IRT1299), The Special Fund of Chongqing Key Laboratory (CSTC), Young Scientific Research Program of CUPT (A2013-31)

周 牧： 男，1984年生，教授，博士后，研究方向为无线定位与导航技术、信号侦察与检测技术、凸优化与深度学习理论等.

唐云霞： 女，1994年生，硕士生，研究方向为无线定位技术、机器学习.

田增山： 男，1968年生，教授，博士生导师，研究方向为移动通信、个人通信、GPS及蜂窝网定位技术等.

卫亚聪： 女，1993年生，硕士生，研究方向为无线定位技术、数值分析.