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

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

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

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.