High efficient construction of location fingerprint database based on matrix completion improved by backtracking search optimization

doi:10.11772/j.issn.1001-9081.2017.07.1893

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1893-1899.DOI: 10.11772/j.issn.1001-9081.2017.07.1893

Previous Articles Next Articles

High efficient construction of location fingerprint database based on matrix completion improved by backtracking search optimization

LI Lina¹, LI Wenhao^1,2, YOU Hongxiang¹, WANG Yue¹

1. College of Physics, Liaoning University, Shenyang Liaoning 110036, China;
2. The 715 th Research Institute of China Shipbuilding Industry Corporation, Hangzhou Zhejiang 310023, China

Received:2016-12-02 Revised:2017-02-05 Online:2017-07-10 Published:2017-07-18
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61403176), Science and Technology Research Project of Liaoning Province Education Department (L2013003).

回溯搜索优化改进矩阵填充的高效位置指纹库构建

李丽娜¹, 李文浩^1,2, 尤洪祥¹, 王越¹

1. 辽宁大学物理学院, 沈阳 110036;
2. 中国船舶重工集团公司第七一五研究所, 杭州 310023

通讯作者: 李丽娜
作者简介:李丽娜(1973-),女,辽宁本溪人,副教授,博士,主要研究方向:室内定位、导航技术;李文浩(1990-),男,甘肃会宁人,硕士研究生,主要研究方向:RFID室内定位;尤洪祥(1991-),男,山东临沂人,硕士研究生,主要研究方向:无线室内定位;王越(1993-),男,辽宁本溪人,硕士研究生,主要研究方向:无线传感网络。
基金资助:
国家自然科学基金资助项目（61403176）；辽宁省教育厅科学技术研究项目（L2013003）。

Abstract

Abstract: To solve the problems existing in the off-line construction method of location fingerprint database for location fingerprint positioning based on Received Signal Strength Indication (RSSI), including large workload of collecting all the fingerprint information in the location, low construction efficiency of the location fingerprint database, and the limited precision of interpolation, a high efficient off-line construction method of the location fingerprint database based on the Singular Value Thresholding (SVT) Matrix Completion (MC) algorithm improved by the Backtracking Search optimization Algorithm (BSA) was proposed. Firstly, using the collected location fingerprint data of some reference nodes, a low-rank matrix completion model was established. Then the model was solved by the low rank MC algorithm based on the SVT. Finally, the complete location fingerprint database could be reconstructed in the location area. At the same time, the BSA was introduced to improve the optimization process of MC algorithm with the minimum kernel norm as the fitness function to solve the problem of the fuzzy optimal solution and the poor smoothness of the traditional MC theory, which could further improve the accuracy of the solution. The experimental results show that the average error between the location fingerprint database constructed by the proposed method and the actual collected location fingerprint database is only 2.7054 dB, and the average positioning error is only 0.0863 m, but nearly 50% of the off-line collection workload can be saved. The above results show that the proposed off-line construction method of the location fingerprint database can effectively reduce the workload of off-line collection stage while ensuring the accuracy, significantly improve the construction efficiency of location fingerprint database, and improve the practicability of fingerprint positioning method to a certain extent.

Key words: Matrix Completion (MC), Singular Value Thresholding (SVT), Backtracking Search optimization Algorithm (BSA), location fingerprint database, indoor positioning

摘要： 针对基于信号强度指示（RSSI）的位置指纹定位过程中用于其离线位置指纹库构建的全采法采集工作量较大、位置指纹库构建效率较低、而插值法通常精度有限等问题，提出一种基于回溯搜索优化算法改进奇异值阈值（SVT）矩阵填充（MC）算法的离线位置指纹库高效构建方法。首先，利用定位区域内采集到的部分参考点的位置指纹数据建立低秩矩阵填充模型；然后通过基于奇异值阈值的低秩矩阵填充算法来求解该模型，进而快速准确重构出完整的位置指纹数据库；同时，针对传统矩阵填充算法最优解模糊及平滑性欠佳的问题，引入回溯搜索优化算法，以核范数最小建立适应度函数，对矩阵填充算法的寻优过程进行改进，进一步提高了求解精度。实验结果表明，利用所提方法构建的位置指纹库与实际采集的位置指纹库之间的平均误差仅为2.7054 dB，平均定位误差仅相差0.0863 m，但却节约了近50%的离线采集工作量。上述结果表明所提算法用于离线位置指纹库构建可以在保证精度的基础上，有效降低离线采集阶段的工作量，显著提高位置指纹库构建效率，在一定程度上提高位置指纹定位方法的实用性。

关键词: 矩阵填充, 奇异值阈值, 回溯搜索优化算法, 位置指纹数据库, 室内定位

CLC Number:

TP391.4

LI Lina, LI Wenhao, YOU Hongxiang, WANG Yue. High efficient construction of location fingerprint database based on matrix completion improved by backtracking search optimization[J]. Journal of Computer Applications, 2017, 37(7): 1893-1899.

李丽娜, 李文浩, 尤洪祥, 王越. 回溯搜索优化改进矩阵填充的高效位置指纹库构建[J]. 计算机应用, 2017, 37(7): 1893-1899.

References

[1] YU F J, M H, L J. Improved AdaBoost-based fingerprint algorithm for WiFi indoor localization[C]//Proceedings of the 2014 IEEE 7th Joint International Information Technology and Artificial Intelligence Conference. Piscataway, NJ:IEEE, 2014:4-5.
[2] JAIN V K, TAPASWI S. SHUKLA A. RSS fingerprints based Distributed Semi-Supervised Locally Linear Embedding (DSSLLE) location estimation system for indoor WLAN[J]. Wireless Personal Communications, 2013, 71(2):1175-1192.
[3] EZPELETA S, CLAVER J M, PÉREZ-SOLANO J J, et al. RF-based location using interpolation functions to reduce fingerprint mapping[J]. Sensors, 2015, 15(10):27322-27340.
[4] 曾碧,毛勤.改进的构建Wi-Fi位置指纹库算法研究[J].广东工业大学学报,2016,33(2):51-56.(ZENG B, MAO Q. A research on algorithm of building Wi-Fi location fingerprint database[J]. Journal of Guangdong University of Technology, 2016, 33(2):51-56.)
[5] CANDES E J, RECHT B. Exact matrix completion via convex optimization[J]. Communications of the ACM, 2012, 55(6):111-119.
[6] MA R, BARZIGAR N, ROOZGARD A, et al. Decomposition approach for low-rank matrix completion and its applications[J]. IEEE Transactions on Signal Processing, 2014, 62(7):1671-1683.
[7] 韦仙.基于矩阵填充技术重构低秩密度矩阵[J].武汉工程大学学报,2015,37(2):72-76.(WEI X. Reconstructing low-rank density matrix via matrix completion[J]. Journal of Wuhan Institute of Technology, 2015, 37(2):72-76.)
[8] MAJUMDAR A, WARD R K. Some empirical advances in matrix completion[J]. Signal Processing, 2011, 91(5):1334-1338.
[9] 李文浩,李丽娜,徐攀峰,等.基于矩阵填充的室内定位位置指纹库构建[J].辽宁大学学报(自然科学版),2015,42(4):325-329.(LI W H, LI L N, XU P F, et al. Construction of indoor location fingerprint database based on matrix completion[J]. Journal of Liaoning University (Natural Science Edition), 2015, 42(4):325-329.)
[10] 王萍,蔡思佳,刘宇.基于随机投影技术的矩阵填充算法的改进[J].计算机应用,2014,34(6):1587-1590.(WANG P, CAI S J, LIU Y. Improvement of matrix completion algorithm based on random projection[J]. Journal of Computer Applications, 2014, 34(6):1587-1590.)
[11] CANDES E J, TAO T. The power of convex relaxation:near-optimal matrix completion[J]. IEEE Transactions on Information Theory, 2010, 56(5):2053-2080.
[12] CANDES E J, PLAN Y. Matrix completion with noise[J]. Pro-ceedings of the IEEE, 2010, 98(6):925-936.
[13] ZHANG Z L, ZHANG H X, JIA J, et al. Low-rank matrix recovery with discriminant regularization[C]//PAKDD 2013:Proceedings of the 17th Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 7819. Berlin:Springer, 2013:437-448.
[14] CAI J F, CANDES E J, SHEN Z W. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4):1956-1982.
[15] CIVICIOGLU P. Backtracking search optimization algorithm for numerical optimization problems[J]. Applied Mathematics and Computation, 2013,219(15):8121-8144.
[16] 王晓娟,刘三阳,田文凯.带高效变异尺度系数和贪婪交叉策略的回溯搜索优化算法[J].计算机应用,2014,34(9):2543-2546.(WANG X J, LIU S Y, TIAN W K. Improved backtracking search optimization algorithm with new effective mutation scale factor and greedy crossover strategy[J]. Journal of Computer Applications, 2014, 34(9):2543-2546.)
[17] 缪鹏彬,余娟,史乐峰,等.基于改进非参数核密度估计和拉丁超立方抽样的电动公共客车负荷模型[J].电工技术学报,2016,31(4):187-193.(MIU P B, YU J, SHI L F, et al. Electric public bus load model based on improved kernel density estimation and Latin hypercube sampling[J]. Transactions of China Electrotechnical Society, 2016, 31(4):187-193.)
[18] 吴哲夫,许丽敏,陈滨,等.基于贝叶斯压缩感知多目标定位算法[J].哈尔滨工程大学学报,2014,35(10):1282-1287.(WU Z F, XU L M, CHEN B, et al. Bayesian compressive sensing algorithm for multiple target localization[J]. Journal of Harbin Engineering University, 2014, 35(10):1282-1287.)

High efficient construction of location fingerprint database based on matrix completion improved by backtracking search optimization

回溯搜索优化改进矩阵填充的高效位置指纹库构建

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics

[1]	ZHANG Jianming, SHI Yuanhao, XU Zhengyi, WEI Jianming. Adaptive UWB/PDR fusion positioning algorithm based on error prediction [J]. Journal of Computer Applications, 2020, 40(6): 1755-1762.
[2]	ZHANG Bang, ZHU Jinxin, XU Zhengyi, LIU Pan, WEI Jianming. Bayesian network-based floor localization algorithm [J]. Journal of Computer Applications, 2019, 39(8): 2468-2474.
[3]	ZHOU Fei, XIA Pengcheng. Signal strength difference fingerprint localization algorithm based on principal component analysis and chi-square distance [J]. Journal of Computer Applications, 2019, 39(5): 1405-1410.
[4]	DING Jianli, MU Tao, WANG Huaichao. Fast indoor positioning algorithm of airport terminal based on spectral regression kernel discriminant analysis [J]. Journal of Computer Applications, 2019, 39(1): 256-261.
[5]	SUN Wange, XIA Kewen, LAN Pu. Regularized weighted incomplete robust principal component analysis method and its application in fitting trajectory of wireless sensor network nodes [J]. Journal of Computer Applications, 2018, 38(6): 1709-1714.
[6]	HAO Dehua, GUAN Weiguo, ZOU Linjie, JIAO Meng. Fast virtual grid matching localization algorithm based on Pearson correlation coefficient [J]. Journal of Computer Applications, 2018, 38(3): 763-768.
[7]	LIU Pan, ZHANG Bang, HUANG Chao, YANG Weijun, XU Zhengyi. Pedestrian heading particle filter correction method with indoor environment constraints [J]. Journal of Computer Applications, 2018, 38(12): 3360-3366.
[8]	ZHANG Tao, MA Lei, MEI Lingyu. Indoor positioning method of warehouse mobile robot based on monocular vision [J]. Journal of Computer Applications, 2017, 37(9): 2491-2495.
[9]	BIAN Jiaxing, ZHU Rong, CHEN Xuan. Ultra wideband localization system based on improved two-way ranging and time difference of arrival positioning algorithm [J]. Journal of Computer Applications, 2017, 37(9): 2496-2500.
[10]	WANG Xuqiao, WANG Jinkun. Integrated indoor positioning algorithm based on D-S evidence theory [J]. Journal of Computer Applications, 2017, 37(4): 1198-1201.
[11]	LI Xinchun, HOU Yue. Indoor positioning technology based on improved access point selection and K nearest neighbor algorithm [J]. Journal of Computer Applications, 2017, 37(11): 3276-3280.
[12]	ZHOU Rui, LI Zhiqiang, LUO Lei. WiFi-pedestrian dead reckoning fused indoor positioning based on particle filtering [J]. Journal of Computer Applications, 2016, 36(5): 1188-1191.
[13]	WANG Yufan, AI Haojun, TU Weiping. Wi-Fi fingerprinting clustering for indoor place of interest positioning [J]. Journal of Computer Applications, 2016, 36(2): 488-491.
[14]	LI Yinuo, XIAO Ruliang, NI Youcong, SU Xiaomin, DU Xin, CAI Shengzhen. Indoor positioning algorithm with dynamic environment attenuation based on particle filtering [J]. Journal of Computer Applications, 2015, 35(9): 2465-2469.