A hierarchical positioning model for WiFi-based indoor localization in large-scale complex environments

2.1. The development of fingerprint data acquisition system

The fingerprint data acquisition system mainly completes the location fingerprint map establishment task in the offline stage. To ensure data availability, a fingerprint data acquisition system with good performance is very necessary. According to the characteristics of mobile and continuous operation, mobile devices were chosen to collect the received signal strength indicator. Meanwhile, the Android platform was chosen to develop localized application software as it opens an application programming interface that scans information related to Wi-Fi. The acquisition of localized Android application software can be divided into three tiers, including the presentation tier, business logic tier and data access tier, as shown in Figure 1.

Figure 1. The structure of acquisition of localized Android application software.

The presentation tier mainly presents specific business data to users, such as tips for preparing or completing the collection, and collects user input information and operations, such as each reference point’s physical location information. The business logic tier mainly provides related business logic for the client layer, such as calling interface to scan information related to Wi-Fi, uploading collection data, releasing collection result, and other related business services. The data service tier mainly provides the data support for the operation of the system, such as the storage of data resources, processing of collected data, generation of location fingerprint map files, and other related data services.

2.2. The development of real-time positioning system

The real-time positioning system mainly completes the positioning task by estimating the physical location of the point to be located. To ensure the stability of the system, the real-time positioning system adopts the Android platform to develop client application software and adopts Java programming language to develop service application software. Besides, the positioning model is built by the integrated development environment of Anaconda software, including Python 3.6, numpy, pandas and Scikit-learn. The real-time positioning system can be divided into two parts: client and server, as shown in Figure 2.

Figure 2. The structure of real-time positioning system.

The client mainly collects Wi-Fi fingerprint data at the point to be located and uploads it to the server. After the server processing is completed, the client presents the estimated location result at the point to be located and shows it on the map. The server mainly provides the functions of receiving Wi-Fi fingerprint data from client, processing Wi-Fi fingerprint data, connecting and reading server database, executing fingerprint matching algorithm and releasing fingerprint matching results to client. Besides, the server database provides the data support for the operation of the system, including the location fingerprint map file established by the aforementioned acquisition localized android application software, and other related data source.

3.1. Offline training phase

The offline training phase comprises two procedures: the construction of regional classifier and the construction of secondary classifier. Firstly, the GMM regional classifier is introduced to partition the to-be-located region into several non-overlapping sub-regions, where the Wi-Fi signal strength distributions are similar to each other. For those sub-regions obtained by the GMM regional classifier, we utilize data samples belonging to same sub-regions to train random forest classifiers, thus achieving specific random forest Classifiers for different sub-regions.

3.1.1. The construction of regional classifier

Theoretical research and experimental results show that, the received signal and the propagation distance are logarithmic^[21] and the path loss conforms to the logarithmic distance path loss model^[22]. After observing the received signal strength vectors obtained at multiple sampling points, it can be found that the spatial distribution model of wireless signals transmitted by each access point (AP) is approximately a two-dimensional Gaussian distribution model, as shown in Figure 4. In addition, Wi-Fi location fingerprint is mainly composed of received signal strength from multiple APs, which can be regarded as a multi-dimensional vector. As a result, the location fingerprint can be assumed to be a mixture of several multi-dimensional Gaussian distributions, each of which describes the distribution characteristics of the received signal strength of a group of sampling points.

Figure 4. Wi-Fi propagation characteristic and Gaussian distribution.

In this paper, the GMM regional classifier is adopted to acquire several non-overlapping sub-regions in the to-be-located region. GMM is a probabilistic model used to represent the distribution of data composed of multiple Gaussian (normal) distributions. This approach is particularly effective for capturing multi-modal data characteristics and is well-suited for clustering analysis of heterogeneous datasets or probability density estimation tasks. Assuming that the data point in the space of received signal strength is a sample that submits to k Gaussian probability density mixture distributions^[23], and then its combined probability distribution can be expressed in

(1) $$ f(x)=\sum_{k=1}^K\alpha _kf_k(x;\beta _k)=\sum_{k=1}^K\alpha _kp(x;\mu _k,\sum_k), $$

in which α_k is the weight, satisfying $$ \sum_{k=1}^K $$α_k = 1 and 0 ≤ α_k ≤ 1; p(x; μ_k, Σ_k) represents the k-th Gaussian density function and its probability distribution can be expressed as:

(2) $$ p(x;\mu _k,\sum_k)=\frac{1}{(2\pi)^{\frac{d}{2}}(\sum_k)^{\frac{1}{2}}}\cdot \mathrm{exp}\left ( \frac{1}{2}(x-\mu _k)^T\sum_k^{-1}(x-\mu _k) \right ), $$

in which d is the dimension of the received signal strength vector, μ_k is the mean value and Σ_k is the covariance function.

To sweep out the GMM region classifier, the E-M algorithm is adopted as it has been proven to be an effective approach for estimating weight of GMM α_k, mean value μ_k and covariance functions Σ_k, which is partitioned into steps of Expectation and Maximum^[24,25].

Expectation-step: the purpose of this step is to obtain hidden variables, which can be expressed as the posterior probability p(k|x_i, Φ^(t)) of x_i in class k. Given the optimal numbers of GMM component X = {x₁, x₂, …, x_n} and initial parameter Φ⁽⁰⁾ or estimated parameter Φ^(t) = (α^(t), β^(t)) in step t, among which β^(t) = (μ^(t), Σ^(t)), the hidden variable p(k|x_i, Φ^(t)) can be expressed as:

(3) $$ p(k|x_i,\Phi^{(t)})=\frac{\alpha _k^{(t)}p_k(x_i|\beta _k^{(t)})}{\sum_{j=1}^K\alpha _j^{(t)}p_j(x_i|\beta_k^{(t)})}, $$

Maximum-step: the purpose of this step is to obtain MLE estimator parameters of the (t + 1) iteration, the hidden variable obtained in the previous step is substituted into MLE estimator of α_k, μ_k and Σ_k. Therefore, MLE estimator parameters of the (t + 1) iteration can be expressed as:

(4) $$ \alpha_{k}^{(t+1)}=\frac{1}{n} \sum_{i=1}^{n} p\left(k \mid x_{i}, \Phi^{(t)}\right), $$

(5) $$ \mu_{k}^{(t+1)}=\frac{1}{n \alpha_{k}^{(t+1)}} \sum_{i=1}^{n} x_{i} p\left(k \mid x_{i}, \Phi^{(t)}\right), $$

(6) $$ \sum_{k}^{(t+1)}=\frac{1}{n \alpha_{k}^{(t+1)}} \sum_{i=1}^{n}\left(x_{i}-\mu_{k}^{(t+1)}\right)^{2} p\left(k \mid x_{i}, \Phi^{(t)}\right), $$

Then it is about to judge the termination condition ||Φ_k^(t+1) - Φ_k^(t)|| $$ \prec $$ ε, in which ε is set to a value small enough. If the condition is satisfied, the iteration is terminated; otherwise, execute Expectation-step all over again. Deduce from the above analysis, given the optimal numbers of GMM component and initial parameter value, the parameter (α_k, μ_k, Σ_k) of GMM region classifier can be obtained through iterative calculation.

3.1.2. The construction of secondary classifier

On the basis of the several non-overlapping sub-regions is established in the previous step, secondary classifier can be selected and applied in each sub-regions. Considering that the data set at the same sub-region have similar characteristics, we choose random forest algorithm to perform as the algorithm of secondary classifier as it has better robustness and fault tolerance for the similar dataset^[26]. The random forest algorithm is an integrated classifier composed of a set of decision tree classifiers, and each generated decision tree is conducted in a random manner. Specifically, each decision tree acquires the classification results respectively, and then vote on these classification results, the category having the greatest Number of Votes shall be the prediction results of random forest^[27]. The construction process of random forest secondary classifier is shown in Figure 5.

Figure 5. The construction process of random forest secondary classifier.

The construction method of random forest secondary classifier in each sub-regions adopts a special bagging method, which uses decision tree as the model in bagging. Firstly, the bootstrap sampling method is used for random sampling of N groups of sample data, M samples are extracted to construct M basic decision trees and the remaining N-M samples are used as out of bag data to verify the accuracy of M decision trees. Secondly, in the construction process of the M basic decision tree, the sub attribute set is randomly generated from the attribute set of the node, and the optimal sub attribute is selected to construct the decision tree^[28]. After that, each decision tree begins to branch recursively from top to bottom, and the minimum size of leaf node is set as the termination condition of decision tree growth, which ensures the accuracy of model construction. In the end, M decision tree is used as the basic classifier set, and the voting method is combined with strategy to make the final decision.

3.2. Online positioning phase

The online positioning phase comprises two procedures: online regional identification and online secondary classification. For the signal strength of the access points at the point to be located comes from, the GMM region classifier is used to obtain online region estimation and the corresponding random forest classifier is employed to obtain online location estimation.

4.1. Description of experimental environment

To evaluate the proposed hierarchical positioning model effectively in a large-scale and complex indoor environment, we specially selected an indoor parking lot of large shopping center to carry out the experiment, as it has the characteristics of irregular indoor layout, numerous solid walls, scattered distribution of access points and intermittent electromagnetic interference. The indoor parking lot selected covers a total region of 2,000 square meters and included 150 parking spaces. Meanwhile, we detected that there were 16 access points installed in the indoor parking lot intending to provide customers with Internet access. The real indoor parking lot and AP device are shown in Figure 6. In order to make the interior plan more concise and obvious, the top view of the indoor parking lot employed for the experiment is shown in Figure 7, in which the small rectangular grid represents a real parking space with a size of 2.0 m × 5.0 m and the sign of signal source represents an access point.

Figure 6. The real indoor parking lot and AP device (photograph taken by the authors).

Figure 7. The top view of the indoor parking lot employed for the experiment.

4.2. Preparation for the experimental samples

Considering that the Wi-Fi signal is particularly sensitive to the surrounding body, scene change and mobile phone types^[30,31], some sample collection strategy must be considered when we prepare the experimental samples. Firstly, in order to alleviate the influence of the human body orientation on the Wi-Fi signals, the observer with the smartphone should face east, south, west and north in turn to collect samples in each direction. Secondly, in order to solve the problem of scene change, as it takes too long to create an RSSI fingerprint map in practical applications, we collect the training samples and test samples in different periods, which avoids the high similarity of samples in the same period and improves the practical application effect of the algorithm. Finally, in order to abate the impact of the mobile phones of various models on the Wi-Fi signals, the Wi-Fi data from multiple mobile phones of different models ought to be collected in each direction at each reference point.

On the basis of the above collection strategy, in this paper, three different mobile phones of Huawei Honor 3C, Xiaomi MIX2, and 360N5 were chosen to collect samples in the experiment. Then we used each mobile phone to collect 400 training samples in each parking space, with 100 training samples in each direction multiplied by four directions. A week later, we used each mobile phone to collect 40 test samples in each parking space using this method, with 10 test samples in each direction multiplied by four directions. The data storage structure is shown in Figure 8.

Figure 8. The data storage structure.

4.3. Discussion on the experimental evaluation method

To more comprehensively reflect the performances of various positioning algorithms in a large-scale and complex environment, the experimental evaluation method has great significance, and two evaluation standards of accuracy and average error distance are introduced.

As described above, the selected indoor parking lot covers a total region of 2,000 square meters and included 150 parking spaces. The Accuracy represents the correct rate between the estimated parking space number and its actual parking space number. For example, ten predictions and nine predictions can get correct parking space number, then its accuracy rate is 90%. The higher the accuracy, the better the positioning effect, and vice versa.

The average error distance represents the real physical distance between the estimated positioning point and its actual positioning point. To construct the vector map of the indoor parking lot and obtain the two-dimensional vector coordinates of each parking space, the top view of indoor parking lot is divided into 1.5 m × 1.5 m small blocks, and there are 670 small blocks in this region. By the mathematical methods of vector rotation and vector coordinate transform, the two-dimensional vector coordinates of each parking space are recorded. Assuming that the estimated coordinates is (x₁, y₁) and its actual coordinates is (x₂, y₂), then the average error distance can be defined as L = $$ \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} $$ × 1.5. The smaller the average error distance, the better the positioning effect, and vice versa.

4.4. Discussion on the experimental process

To better reflect the advantages of hierarchical positioning model in a large-scale and complex indoor environment, the classification results from a single classifier such as SVM, DT, GNB, Adaboost, Bagging, MLP, and RF, etc., are employed as the baseline of classification result indicator. We have used the implementations of SVM, DT, GNB, Adaboost, Bagging and RF provided by the Scikit-learn tool and the MLP implementation provided by Keras. Figures 9 and 10 show the positioning results obtained by the aforementioned single classifiers to cover all the indoor parking lot, including the accuracy and average error distance.

Figure 9. Comparison of accuracy of single classifiers.

Figure 10. Comparison of average error distance of single classifiers.

As we can see intuitively from Figure 9, the accuracy of the MLP classifier is the highest among the seven algorithms about 23.12%, while the accuracy of the RF classifier is the secondly among the seven algorithms about 20.62%. As for another indicator from Figure 10, the average error distance of the RF classifier has a best performance among the seven algorithms about 2.82 m; at the same time, the accuracy of the RF classifier has a secondly performance among the seven algorithms about 2.88 m. The conclusion we can draw from our experimental data set is that the accuracy and average error distance achieved by RF and MLP outperform those of other classifiers. So, only RF and MLP will be discussed as secondly classifier when the hierarchical positioning model is applied.

Firstly, the GMM regional classifier is introduced to partition the to-be-located region into several non-overlapping sub-regions, where the Wi-Fi signal strength distributions in all are similar to each other. The K-means regional classifier is adopted to conduct a comparative experiment. The effects of regional classification of the GMM regional classifier and the K-means regional classifier both depend on the clustering index CH and Silhouette. Ch index represents the ratio of separation degree and compactness degree, where compactness degree is the sum of square distances between each point in the region and the center of the region, and separation degree is the sum of square distances between the center of the region and the center of the data set. The larger the CH index become, the closer the region itself is, and the more dispersed the regions are, which means the better regional classification effect. Silhouette index represents the contour coefficient, which can be used to measure the similarity between a point and its region compared with other regions. The value range of Silhouette index is -1 to 1. The larger the value becomes, the better regional classification effect is. Figure 11 shows comparison of the clustering index CH and Silhouette through the GMM regional classifier and the K-means regional classifier under different number of regions.

Figure 11. Comparison of the clustering index CH and Silhouette.

As we can see from Figure 11, with the continuous increase of the number of sub-regions, the clustering index CH and Silhouette of the GMM regional classifier and the K-means regional classifier both first gradually decrease and then slowly increase. Meanwhile, under the same number of regions, the clustering index CH and Silhouette of the GMM region classifier are larger than those of the K-means regional classifier. It is pointed out that the clustering index CH and Silhouette of the GMM region classifier get the maximum value when K equals five, where the CH value is 320 and the Silhouette value is 0.5. The conclusion we can draw from our experimental data set is that the GMM regional classifier has the better performance rather than the K-means regional classifier, and when the number of regions is five, the GMM regional classifier has the optimum performance. So, only GMM regional classifier will be discussed as in depth in the next experiment when the hierarchical positioning model is applied.

For those sub-regions obtained by the GMM regional classifier, we utilize data samples belonging to the same regions to train a second classifier. As mentioned above, only RF and MLP will be selected as the second classifier. Figures 12 and 13 show the accuracy and average error distance obtained by the hierarchical positioning model in different sub-regions, including GMM + RF and GMM + MLP.

Figure 12. The accuracy obtained by hierarchical positioning model in different sub-regions.

Figure 13. The average error distance obtained by hierarchical positioning model in different sub-regions.

As we can see from Figures 12 and 13, under the different sub-regions, the accuracy and average error distance of GMM + RF hierarchical positioning model or GMM + MLP hierarchical positioning model can be very different from each other. Taking GMM + RF hierarchical positioning model for example, the accuracy from lowest 21.25% achieved by region 2 to highest 36.67% achieved by region 1. It can be shown that the sub-region itself is very close, and different sub-regions are very dispersed. And it is also proved that GMM regional classifier can partition the to-be-located region into several non-overlapping sub-regions effectively.

Furthermore, under the same sub-region, the accuracy and average error distance of the GMM + RF hierarchical positioning model are better than the GMM + MLP hierarchical positioning model. The reason is that the sub-region itself is very close and data set itself is similar, MLP will get stuck at local optima easily and learning is not enough. On the other side, by introducing two randomness strategies, RF is not easy to fall into over fitting, and has a certain anti-noise ability. The conclusion we can draw from our experimental data set is that the data set at the same sub-region have similar characteristics, RF has better robustness and fault tolerance for the same sub-region of data set. To summarize, our proposed GMM + RF hierarchical positioning model has the better performance rather than the GMM + MLP hierarchical positioning model.

To verify the effectiveness of the proposed hierarchical positioning model in improving the average error and reducing the average error distance, the classification results from a single classifier such as SVM, DT, GNB, Adaboost, Bagging, MLP, RF, etc., are also employed as the baseline of classification result indicator. We have used the implementations of hierarchical positioning model GMM + RF and GMM + MLP provided by the above methods. Figures 14 and 15 show the positioning results obtained by the aforementioned single classifiers and hierarchical positioning model to cover all the indoor parking lot, including the accuracy and average error distance.

Figure 14. Comparison of the accuracy between the proposed hierarchical positioning model and the other existing classifiers.

Figure 15. Comparison of the average error distance between the proposed hierarchical positioning model and the other existing classifiers.

It can be sighted that in terms of two proposed measurement standards, the proposed hierarchical positioning model GMM + RF is superior to other existing classifiers. As mentioned above, the accuracy of the MLP classifier is the highest among the seven single classifiers about 23.12%, and the average error distance of the RF classifier has a best performance among the seven single classifiers about 2.82 m. Taking GMM + RF hierarchical positioning model for a comparison, the accuracy increases from 23.12% to 30.94% while compared with MLP, and the mean error distance decreases from 2.82 to 2.52 m while compared with RF. These specific experiment results show that in terms of two proposed measurement standards, the proposed GMM + RF hierarchical positioning model is superior to other existing classifiers.