Abstract
With the development of information technology, indoor positioning technology has been rapidly evolving. Due to the advantages of high positioning accuracy, low cost, and wide coverage simultaneously, received signal strength- (RSS-) based WLAN indoor positioning technology has become one of the mainstream technologies. A radio map is the basis for the realization of the WLAN positioning system. However, by reasons of the huge workload of RSS collection, the instability of wireless signal strength, and the disappearance of signals caused by the occlusion of people and objects, the construction of a radio map is time-consuming and inefficient. In order to rapidly deploy the WLAN indoor positioning system, an improved low-rank matrix completion method is proposed to construct the radio map. Firstly, we evenly arrange a small number of reference points (RP) in the positioning area and collect RSS data on the RP to construct the radio map. Then, the low-rank matrix completion method is used to fill a small amount of data in the radio map into a complete database. The Frobenius parameter (F-parameter) is introduced into the traditional low-rank matrix completion model to control the instability of the model solution when filling the data. To solve the noise problem caused by environment and equipment, a low-rank matrix recovery algorithm is used to eliminate noise. The experimental results show that the improved algorithm achieves the expected goal.
1. Introduction
Location-based services (LBS) play an indispensable role in the information technology industry. As one of the key technologies of LBS, indoor positioning technology has also attracted widespread attention with the rapid development of mobile Internet and the popularity of smartphones in recent years [1–3]. An indoor positioning system is the continuation of the outdoor positioning system, which largely fills the vacancy of traditional positioning technology and has broad application prospects, such as navigation to specific stores in large shopping malls and indoor personnel positioning in fire scenes. Although outdoor positioning has already had very mature technologies such as Beidou and Global Positioning System (GPS), in the indoor environment, because of the interference of many factors, such as object occlusion, personnel walking, multipath effect in the process of signal propagation, and other noises, the difficulty of realizing indoor positioning technology is increased [4].
In order to achieve accurate indoor positioning, a variety of positioning systems have been proposed by researchers, such as positioning systems based on WLAN, RFID, and other technologies [5–7]. Since there is no need to add special sensors to the fingerprint-based WLAN indoor positioning system, we use the existing WLAN system and the user’s intelligent mobile terminal as the hardware platform and develop software on the intelligent mobile terminal to provide positioning services for users. Therefore, the WLAN indoor positioning system has the value of large-scale promotion and application. The fingerprint-based WLAN indoor positioning system is divided into two phases: offline phase and online phase. In the offline phase, we uniformly set a large number of reference points (RP) in the positioning environment and collect RSS values from access points (AP) on the RPs. Each fingerprint is obtained by combining RSS with its corresponding coordinate, and the set of all fingerprints is the radio map. In the online phase, users’ locations can be calculated by matching the real-time collected RSS with the RSS in the radio map [8].
For the fingerprint-based WLAN indoor positioning system, the radio map is the basis for realizing the system [9]. The radio map keeps the mapping relationship between the signal space and location space. In the traditional radio map establishment method, a large number of reference points need to be set in the target area and multiple measurements need to be taken at each reference point to improve the positioning accuracy [10]. This approach consumes a lot of labor and time costs. Therefore, to reduce the time and labor cost of radio map establishment, many effective methods have been proposed. In Reference [11], a hybrid radio map construction method called Hidden Environment Model (HEM) is proposed. In HEM, an Environment Factor Matrix (EFM) is built to model the distinct effects of the indoor environment on signal attenuation, and the EFM is constructed using theoretical interpolations and approximations combined with on-site signal measurements. A precise Indoor Locating System (PILS) is proposed in Reference [12], and the self-correlation between RSS data of reference points is used to interpolate the radio map, which increases the number of reference points and reduces the workload of offline acquisition. However, the interpolation method cannot achieve accurate RSS value estimation in the complex electromagnetic environment indoors. Reference [13] used unlabeled user trajectories for radio map building and achieved interpolation of the radio map by labeling the unlabeled data using the Bayesian theory and hidden Markov model. The paper [14] investigates the influence of signal change on the radio map and obtains the intrinsic relationship of RSS data at different times by a linear model, which effectively reduces the updating workload of the radio map. However, this method requires additional equipment, which reduces the effectiveness of the method. The semisupervised learning algorithm is proposed in Reference [15] to construct a radio map. A small amount of labeled data and a large number of unlabeled data are collected in the offline phase, and the label propagation is calculated on the unlabeled data by a semisupervised learning algorithm. A variety of machine learning algorithms and the collected labeled data are used to calculate the label of unlabeled data and expand the radio map; as a result, the purpose of reducing the radio map construction workload was achieved. These algorithms give us many hints. For example, the widely used reference point expansion methods are spatial interpolation methods, including inverse distance weighted interpolation [16], linear interpolation [17], kriging interpolation [18], and spline interpolation [19]. However, the spatial interpolation methods utilize the local information of the data rather than the global information, and the interpolation results are affected by the order of data arrangement, so the global optimal solution cannot be obtained by the spatial interpolation methods. In 2006, Donoho proposed compressed sensing theory in Reference [20], which has become one of the research hotspots in signal processing, data acquisition, and other related fields. By mining the sparse characteristics of massive signals, under the condition of far less than the Nyquist sampling rate, the original signal can be reconstructed accurately by the compressed sensing algorithm. The development of compressed sensing theory in the matrix space is matrix completion. The matrix completion algorithm uses the low rank of matrix singular value to recover the original matrix by sampling some elements of the matrix. In order to achieve accurate matrix completion, a series of efficient solution algorithms have been proposed. Among these algorithms, the fixed point algorithm proposed in Reference [21] and the inaccurate Lagrange multiplier method proposed in Reference [22] can achieve excellent completion results.
Inspired from the above articles, an improved low-rank matrix completion method is proposed to fast construct the radio map in the indoor positioning system. Because the RSS data matrix in the radio map has a low-rank characteristic, the construction problem of the radio map can be modeled as a low-rank matrix completion problem. Therefore, we only need to collect RSS data at some reference points, and the complete radio map can be filled by the matrix completion algorithm. To eliminate the noise in the RSS data, the F-parameter and the sparse noise term are introduced to the traditional matrix completion model, and an improved algorithm is obtained. In the process of solving the model, the solution is performed by the alternating direction multiplier method (ADMM).
The main contributions of this paper are as follows: (1)The low-rank matrix completion model is proposed to achieve the fast establishment of the radio map, while the F-parameter is used to eliminate the instability of the model solution
To construct a complete radio map, the accuracy of the data used for filling needs to be guaranteed. When collecting data, due to the influence of the environment (such as human walking and wall blocking), the collected RSS data contain a lot of noise. In the traditional model, only the kernel function is considered by the low-rank matrix complete model, and the low rankness of the model is guaranteed by the kernel parameters. In this paper, the regularization term is introduced into the traditional low-rank matrix completion model, and the F-parameter is used to eliminate the model instability. (2)A sparse term is introduced to the low-rank matrix completion model to eliminate the sparse noise in RSS data
Due to the influence of the environment, RSS data not only brings Gaussian noise but also contains a small amount of outliers, called sparse noise. In the low-rank completion model, the F-parameter only has a good processing effect on Gaussian noise, but it does not solve the problem caused by outliers. Inspired by the low-rank recovery matrix model, we introduce the sparse term of the recovery model to solve the problem of outliers. Therefore, using the new L1 parameter to characterize the sparse noise can effectively solve the instability problem caused by outliers.
The remainder of this paper is organized as follows. The related works are discussed in Section 2. In Section 3, the fingerprint-based WLAN indoor positioning system is introduced, and the framework of the fast construction algorithm of the radio map is given. In Section 4, we theoretically derive and realize this method. The experimental results and analysis are presented in Section 5. Finally, Section 6 draws the conclusion of this paper.
2. Related Works
In order to reduce the acquisition workload in the offline phase, various low-rank completion methods have been proposed in recent years.
Assuming that the data matrix has low-rank characteristics, the matrix completion algorithm can be used to estimate the value of missing data, and the synthesis matrix closest to the target matrix is obtained under the constraint conditions. However, the robustness of most matrix completion algorithms is not satisfactory when Gaussian noise is added. Li et al. [23] proposed a new robust matrix completion method. The method has better robustness and accuracy when the data are destroyed by Gaussian noise. Zhang and Tan introduced a total variance constraint term based on the original kernel parametric constraint for low-rank matrices [24]. A weighting algorithm was introduced to improve the low rankness of the low-rank matrix and the sparsity of the sparse matrix. This method not only ensures the detailed information of low-rank completion but also ensures the denoising effect.
The above researches on low-rank matrix completion are only optimized in static aspects, and Song and Wang applied the matrix completion model to the field of data mining according to the structural characteristics of web links [25]. Mapping the data into a high-dimensional space makes the nonlinear relationships in dynamic links convert to linear relationships, thus making the model more complete of handling complex network structures. Besides, Reference [26] proposes an efficient algorithm for alternate iterative solution of subproblems for low-rank completion models. The algorithm uses the nonlocal self-similarity of data to propose an interpolation method for the nonlocal low-rank reconstruction model. Reference [27] proposed a weighted kernel parametric minimum model with initial value bootstrap. By constructing weights of opposite magnitude to the singular values, the approximation matrix is made to approximate the original matrix well. Second, the linear search is improved to accelerate the proximal gradient algorithm solution model, which improves the convergence speed of the algorithm.
After continuous optimization, the low-rank matrix completion model has achieved better results. In recent years, improved low-rank matrix completion algorithms have also been widely used in the construction of the radio map. Hu et al. [28] represented the RSS data space as a low-rank matrix and constructed a complete radio map from sparse measurements by the improved low-rank matrix completion method. Experiments proved that the method effectively reduced the number of collected RSS data. An experimental model for constructing a radio map was proposed by Xue et al. in Reference [29]. Based on the indoor RSS map, the signal feature points are proposed and the radio map is reconstructed using the grid points in a geometric space and the signal feature points in an RSS space. The model is significantly better than the traditional positioning method. Tan et al. [30] proposed an improved optimization model based on the traditional matrix completion model. The optimized model converts the kernel parameter into a weighted kernel parameter and introduces both the L1 parameter and F-parameter to recover the unknown data more accurately. Ma et al. [31] proposed a radio map recovery method based on the inexact incremental Lagrange multiplier (IALM) algorithm, which accurately recovered the RSS data in the radio map and effectively reduced the noise. In addition, Ma et al. [32] proposed a radio map noise reduction method using the Hankel matrix. The special structure of the Hankel matrix is used to effectively separate the noise from the signal. This method can achieve a better noise reduction effect and thus improve the localization accuracy. Zhang and Ma [33] proposed a method based on sparse representation and low-rank matrix recovery in order to update the radio map accurately. The method combines the fingerprint correlation of sparse representation with the low rank of the fingerprint matrix to update the radio map more accurately.
3. System Model
The typical fingerprint-based WLAN positioning system includes two phases. In the offline phase, the main task is to construct a radio map to realize the mapping between RSS data and position coordinates. In the online phase, the user’s location is calculated using the radio map. The block diagram of the WLAN indoor positioning system is shown in Figure 1. Suppose APs and RPs are deployed in the location area. In order to build the radio map, we collect RSS values from all APs on each RP, and a dimension RSS vector can be gotten after preprocessing on each RP, where is the received signal strength measured on the -th RP from the -th AP. The -th fingerprint is obtained combining with its corresponding coordinates . The set of all fingerprints is the radio map, as shown in Figure 1. In the online phase, the user’s location can be calculated by matching the collected RSS with the RSS data in the radio map.
For this positioning system, in order to get accurate positioning results, we need to construct an accurate radio map. Therefore, it is necessary to set as many RPs as possible in the indoor positioning area to collect more RSS data. Therefore, the positioning accuracy depends on the accuracy of the radio map and the number of fingerprints in the radio map. However, two problems hinder the establishment of an accurate radio map. First, collecting RSS data on all RPs takes a lot of time and labor costs. Secondly, due to the complex indoor electromagnetic environment, the collected RSS data contain a lot of noise. According to the signal propagation model, WLAN signal strength decreases with the increase in distance. The wireless signal propagation model is shown in [34] where denotes the distance between the location of the collected signal and the AP, represents the received signal strength of AP, is the transmit power of AP, and represents the received signal strength at a distance of . is a known parameter that represents the path loss.
Since the received signal strength decreases with the increase in distance and the distance between the adjacent reference point and AP is close, the adjacent reference point has highly similar signal strength. As a result, there is a spatial correlation between RSS data, and the RSS matrix in the radio map has low-rank characteristics. Using the low-rank characteristic of the RSS matrix, we only need to collect a small amount of RSS data at some reference points, and the complete RSS matrix can be obtained by the low-rank matrix completion algorithm. Then, the low-rank matrix recovery algorithm is used to separate RSS data from noise, so as to reduce the noise in the radio map and improve the accuracy of the radio map. Therefore, the construction process of the complete radio map is shown in Figure 2.
4. Methods
4.1. Low-Rank Matrix Completion with the F-Parameter
With the explosive growth of data volume, the dimension of data is increasing, and there is more correlation between high-dimensional data. Therefore, the growth of information content of the data itself is slower than that of the data dimension. For example, after feature extraction, a large number of the same features of the image will be discarded. After the wave transformation, only a small number of coefficients are relatively significant in numerical size. If the image is regarded as a pixel matrix, after singular value decomposition, a small number of singular values often contain 90% of the information of the whole image. These examples show that in high-dimensional data, there are often varying degrees of correlation, which can greatly reduce the storage space of data.
Assume that the original data matrix is low-rank, but the matrix contains many unknown elements. Completion of an incomplete matrix into a complete matrix is called a low-rank matrix completion problem. The low-rank matrix completion model is shown in Figure 3.
The matrix completion problem is aimed at estimating the information of unknown elements through partial observation data of the matrix. Without other constraints, such problems are completely unsolvable. However, if the data matrix has some special properties, it will make the matrix completion problem possible. Low rank is such a property. If the matrix is known to be low-rank in advance, the matrix completion problem can be formulated as the following optimization problem. where is the set of observable sample subscripts, is the matrix filled by the low-rank completion algorithm, is the true matrix with missing elements, is the element of the -th row and -th column of the matrix, and is the element of the -th row and -th column of the matrix.
If we set the data on the RP outside the coordinate set to 0, we get
The above problem is NP-hard. The complexity of the problem increases with the increase in matrix dimension, and the convex hull of function is the kernel norm of matrix , that is, the sum of all singular values of matrix , so the problem is converted into a convex optimization problem.
In Reference [35], the authors point out that the solution of equation (4) is equivalent to the solution of under strong incoherent conditions. Reference [36] has proven that the kernel norm is a convex hull with a spectral norm of 1. Therefore, this is a convex relaxation problem of NP-hard problems. If the position of reference points of the collected data is randomly uniformly distributed, then when , the observation matrix has a great probability to receive the optimal solution for the optimization problem, where is the constraint parameter, is the rank of the matrix , satisfying , and is a positive constant.
Although the model can produce low-rank solutions, the kernel norm of the matrix to be filled is only considered by the model, which may lead to the instability of the solution obtained by the completion problem of the matrix with a strong correlation. Therefore, on the basis of this model, the F-parameter of the matrix to be filled is introduced as a new regularization term, and a joint regularization term is formed with the original kernel norm [22]. Therefore, the uniqueness and low rank of the solution are controlled by the kernel norm, and the stability of the solution is controlled by the F-parameter. The regularized model is where . When , the optimal solution of the above optimization problem converges to the optimal solution of the kernel function. Define as the projection operator; . Construct the Lagrange function of the optimization problem after the regularization model: where the Lagrange multiplier . Let be defined by where and are orthogonal matrices, is a diagonal matrix, and the elements on the diagonal are singular values of the matrix . There are three properties of singular values.
Property 1: nonnegativity, i.e., singular values .
Property 2: the number of nonzero singular values of the matrix is equal to the rank of the matrix.
Property 3: the maximum singular value of the matrix is equal to the spectral norm, i.e., .
For , , and for each , we have where is the soft threshold operation, refers to the diagonal elements of the singular value matrix, and indicates that the singular value is guaranteed to be nonnegative when it tends to 0. It is defined as follows:
Since the above operation is an approximation of the kernel function, the above equation can be converted to
The optimization problem is solved using alternating iterations, and the specific iteration format of which can be simply stated as follows: where is the auxiliary matrix, is the measurement matrix (containing missing values), is the position of the known elements, and is the iteration step. The object of is the matrix which can be specifically described as the following equation:
The final convergence discriminant is
4.2. Low-Rank Matrix Recovery
Large-scale data processing is often accompanied by data missing, damage, and other issues. For example, in the face recognition model, the face images to be recognized in the training set contain shadows, highlight, occlusion, deformation, etc. In structure from motion (SFM) problems, large matching errors often exist in feature extraction and feature matching. Correct and efficient recovery of original data from damaged data is crucial for the analysis and processing of modern large-scale data. Assume that the original data matrix is low rank and the matrix elements contain a lot of noise. To recover a complete low-rank matrix from a matrix containing noise is a low-rank matrix recovery problem. The recovery framework of the low-rank matrix is shown in Figure 4.
When there is no noise or Gaussian noise in the data, the classical data recovery method is principal component analysis [37]. where is the observation matrix, is a low-rank matrix, and is a Gaussian matrix with the independent identical distribution. However, when the matrix does not satisfy the Gaussian distribution but a sparse noise matrix, the principal component analysis method is no longer applicable to solve this problem. In this case, the matrix is decomposed into a low-rank matrix part and a sparse noise matrix part .
Because the noise is sparse, it can be characterized by the L0 norm. The original sparse noise problem can then be modeled as the following optimization problem. where and is the observation matrix. Since this problem is NP-hard, the L0 norm of the matrix is relaxed to the L1 norm, and the following equation is obtained:
The method to solve this problem is called robust principal component analysis. If the singular value distribution of the low-rank matrix is reasonable and the nonzero elements of the coefficient matrix are evenly distributed, the original low-rank matrix can be recovered from any unknown error by the convex optimization problem with the probability of close to 1.
The augmented Lagrangian function was constructed for the optimization problem in equation (17).
When and , the optimization problem is solved using the inexact Lagrange multiplier method:
Then, the update equation of and is where is singular value operations, regarding equation (14). are soft threshold operations as follows:
Then, the update equation of the matrix is
The formula for parameter is as follows: where is a constant and is a small positive number.
4.3. Indoor Positioning System with Low-Rank Completion
According to the above theory, if the matrix has low-rank characteristics, the missing elements of the matrix can be filled by the low-rank matrix completion algorithm. When collecting data, due to personnel movement, mobile phone orientation, and other reasons, the collected RSS value contains a lot of environmental noise, and the internal sensors of the equipment also produce equipment noise. Therefore, the established radio map contains a lot of noise. Because of the existence of noise, the low-rank matrix completion algorithm cannot achieve ideal results. In order to solve the above problem, we add a sparse noise term to the matrix completion model, and the proposed algorithm combines the completion and recovery algorithms of the low-rank matrix, which is more stable and robust than the original model. The indoor positioning system framework with the low-rank completion and recovery algorithm is shown in Figure 5.
The improved model is
The nonconvex problem in equation (24) can be transformed into the following convex optimization problem.
For the optimization problem in equation (25), the augmented Lagrange function is constructed as follows:
The optimal solution of the problem is solved by using the alternating direction multiplier method.
In order to facilitate the derivation of the formula, is used to replace the regularization term of the F-parameter to distinguish the kernel parameter and the F-parameter. We can get
Since two constraints are added, the impact should be divided into two parts. Therefore, the penalty factor is divided into two parts. Let and , and reestablish the Lagrange function as follows.
Equation (29) was further rewritten as follows:
The formulas are updated by alternating variables for iterative solutions. The formulas for each variable are listed below.
The solution of can be expressed by the singular value threshold operator, so that the solution of is
The solution of can be obtained optimally by finding the partial derivative.
The solution of can be expressed by the soft threshold operator, so that the solution of is
Finally, update and .
5. Experimental Results and Analysis
This section provides details on the experimental results of the proposed method using both simulations and implementations. The positioning area is located in the 4th floor of building 9 at Shandong University of Technology. In this location area, we divide the whole location area into several grids, and each grid spacing is 0.5 m, with a total of 342 reference points, as shown in Figure 6.
A total of 26 APs are installed in this positioning area, and a Redmi K30 Pro mobile phone is used to collect RSS values. In order to verify the effectiveness of our algorithm, we construct a database without missing elements. We collected 100 RSS data at each reference point, removed the singular values, and used the remaining RSS values to calculate the average. Using the average value to establish the radio map can effectively improve the positioning accuracy. However, it took us weeks and a lot of manpower costs to build the radio map. The complete radio map is shown in Figure 7. In Figure 7, horizontal coordinates represent different APs and ordinates represent different RPs, and different colors represent the intensity of the RSS.
In order to quickly establish the radio map, we reduce the scale of data collection and only collect RSS data at 40% RPs. The obtained incomplete radio map is shown in Figure 8. Then, the low-rank matrix completion method is used to expand the RP data, and the complete radio map is obtained. The experimental results are shown in Figure 9.
To demonstrate the completion effect after completion, we define the difference between the complete radio map and the radio map filled from the 40% data using the proposed completion algorithm as the completion error, and the definition equation is where denotes the complete radio map and denotes the result of completion of the radio map constructed from 40% data using the proposed completion algorithm. denotes the completion error. That is, the smaller the value is, the closer the completion result is to the ideal radio map and the better the completion effect is. The completion error result is shown in Figure 10. As illustrated in Figure 10, most completion errors are less than 3 dBm.
As shown in Figure 10, the RSS values at unmeasured RPs can be filled effectively by the improved low-rank matrix completion algorithm, and the completion effect is satisfactory. In order to further show the completion effect of the algorithm, we use a cubic spline interpolation method to interpolate the incomplete radio map and calculate the completion error. The results are shown in Table 1.
It can be seen from Table 1 that since the interpolation algorithm is greatly affected by the data arrangement, the completion effect is not ideal by using the interpolation method. When the low-rank completion algorithm is used to fill the reference point, the inherent relationship between the low-rank characteristics of the RSS matrix and the RSS value between adjacent reference points is used, so the radio map obtained has high accuracy and small completion error. In order to show the influence of the algorithm on the actual positioning results, the complete radio map, the incomplete radio map, and the radio map filled with the proposed algorithm and the cubic spline interpolation algorithm are used as the fingerprint database in the offline training phase. In the online positioning phase, we use the classic KNN algorithm () to calculate the user location, and the cumulative distribution function curves of positioning error for different algorithms are shown in Figure 11.
It can be seen from Figure 9 that when the incomplete radio map is directly used for positioning, the probability of error within 2 m is 63%, and the positioning accuracy cannot meet the actual requirements. When the reference points are arranged according to the distance from the -axis, the -axis, and the distance from the origin, the interpolation method is used to expand the reference point, which can improve the positioning accuracy to a certain extent. The probability of error within 2 m is increased to 78%, 77%, and 67%, respectively. When the reference points are arranged according to the distance from the -axis, the -axis, and the origin, the interpolation method is used to fill the radio map, and the filled radio map is used to analyze the positioning error. The probability of error within 2 m is increased to about 78%, 77%, and 67%, respectively. However, the completion effect of the radio map is affected by the order of RPs. Since it is impossible to know how to arrange before completion to ensure the strongest correlation between RSS data, it is difficult to achieve the best completion effect and positioning accuracy. The improved low-rank completion algorithm uses the low-rank characteristics of the RSS matrix and the correlation between RSS data to fill the radio map, and the completion result has a unique solution. Therefore, the probability of positioning error within 2 m is increased to more than 90%, and the positioning accuracy is higher than that of the interpolation method.
In summary, the low-rank matrix completion algorithm proposed in this paper can significantly reduce the workload of building a radio map while ensuring high positioning accuracy.
6. Conclusions
In this paper, an improved low-rank matrix completion method is proposed to realize the rapid establishment of the radio map. To reduce the workload of building the radio map in the offline phase, the matrix completion algorithm is introduced to build the radio map by using the low-rank characteristic of the RSS matrix. The F-parameter is introduced to the traditional low-rank matrix completion model to improve the stability of the algorithm, and the sparse noise term is also introduced to solve the noise interference due to environmental factors. The experimental results show that under the premise of ensuring the same positioning accuracy, the time and labor cost of radio map establishment in the offline phase can be effectively reduced and the influence of noise on the radio map is eliminated simultaneously.
Data Availability
The radio map data used to support the findings of this study were supplied by Liye Zhang under license and so cannot be made freely available. Requests for access to these data should be made to Liye Zhang ([email protected]).
Conflicts of Interest
The authors declare that they have no competing interests.
Acknowledgments
This work is supported by School of Computer Science and Technology, Shandong University of Technology. This paper is supported by the Shandong Provincial Natural Science Foundation, China (grant number ZR2019BF022), and National Natural Science Foundation of China (grant number 62001272).