With the development of the Internet of Things (IoT), indoor location-based services (LBSs) have attracted much attention due to their wide range of applications [1], such as pedestrian navigation in stadiums, railway stations, airports, hospitals, and industrial areas [2], parking in underground garages [3], and advertising in large shopping malls [4]. Adopting a real-time indoor localization approach with a low implementation cost, high localization accuracy, and full consideration of complex indoor environment factors is beneficial to effectively realize LBS applications.

Due to the reliance on dedicated hardware devices, several indoor localization methods based on the systems such as the ultra-wide band (UWB) [5], Bluetooth [6], and ZigBee [7] have incredibly minimal applications. Recently, wireless local area network (WLAN) devices have been widely deployed in shopping malls, hospitals, and schools, which makes the WLAN-based method be easily implemented with no hardware and deployment costs, and thus have gained much attention from both academia and industry. The fingerprint is a widely used WLAN-based method that actually aggregates the signal strength and takes into account the multipath effect. This enables fingerprint localization to achieve higher accuracy when the complex environmental factors are considered. Currently, the studies on the fingerprint localization method mainly focus on the optimization analysis of localization accuracy, reliability, and efficiency [8–11]. Despite the fingerprinting-based approach using WLAN has been applied in indoor localization [12], there are still several significant limitations in the previously proposed methods [10,13,14]:

1) Due to the method of manual measurement used for the received signal strength (RSS), it is difficult to build the fingerprint database.

2) The grid size is usually larger than 2 m in fingerprinting-based approaches, which makes the indoor localization accuracy quite low.

3) When the access point (AP) position or obstacle changes, the fingerprint database cannot be updated in real-time, leading to a larger error in indoor localization.

Recently, the AP deployment is realized by computing the path loss at each reference point (RP) [15,16]. It demonstrates that the path loss formula is suitable and reliable for the signal computation. In this paper, a fine-grained grid computing (FGGC) model, which has a low implementation cost, excellent real-time performance, and high localization accuracy, with the full consideration of complex indoor environment factors is proposed for Wi-Fi indoor localization.

The main contributions of this paper are summarized as follows:

1) A method capable of calculating RSS values at each RP in three-dimensional space is proposed, where all the attenuation factors such as the frequency, three-dimensional propagation distance, and walls in complex environments are considered in the path loss formula, and the RSS values at each RP from all APs can be automatically generated. Thus the signals at all RPs can be acquired without manual measurement, and the localization accuracy can be improved.

2) A random forest based algorithm is proposed to predict the grid locations and obtain the approximate locations, thus improving the computation efficiency.

3) An FGGC model based on RSS is proposed to enhance the efficiency and precision of Wi-Fi indoor localization. A mean error of about 0.40 m is realized, which is much smaller than that of previous approaches.

The rest of this paper is organized as follows. The related works are reviewed in Section 2. The architecture design and proposed FGGC model are described in Section 3. The experimental settings and performance evaluation are shown in Section 4. Finally, the work is concluded and prospected in Section 5.

Due to the complex and changeable indoor environment, signal propagation is affected by many obstacles, which leads to low localization accuracy of Wi-Fi based fingerprint localization technology [17]. Therefore, current studies related to Wi-Fi based indoor localization approaches mainly focus on the improvement of localization accuracy and efficiency in complex environments [18–21].

Localization accuracy is one of the most vital factors to be considered in indoor localization. Based on the heuristic AP selection algorithm [22], the localization accuracy of the k-nearest neighbor (KNN) method was significantly improved [13]. An eight-diagram AP selection algorithm was used for indoor localization [23], which achieved considerably higher accuracy than the weighted k-nearest neighbors (WKNN) algorithm [24]. The WKNN based approximate position distance (APD-WKNN) algorithm [25] is a kind of WKNN algorithm based on signal similarity and spatial position, which can significantly improve the localization accuracy of the WKNN algorithm. Reference [26] demonstrates that the proposed algorithms based on one RP or k RPs (kRPs) weighted average positioning show higher localization accuracy than traditional algorithms. In Ref. [27], a hybrid hypothesis approach exploits signal distributions by considering different AP contributions to the Wi-Fi indoor localization accuracy.

As another critical criterion in indoor localization, the localization performance has also been widely investigated [28]. Zheng et al. optimized the AP selection algorithm by reformulating the AP planning with the incorporation of the existence of obstacles, array orientation, and path loss, and demonstrated that both the improved time efficiency and the desired localization accuracy could be simultaneously realized by selecting the minimum number of APs [29]. They also further improved the localization performance through optimizing the AP positions and array orientations [30]. Liu et al. proposed a WKNN localization strategy based on k-means clustering radio mapping to balance the localization accuracy and computational complexity [31]. Wang designed a dynamic time warping k-nearest neighbors (DTW-KNN) model based on the Gaussian kernel function and pointed out the effect of distance calculation on the performance, accuracy, and robustness of the algorithm [32]. The results indicate that the Gaussian kernel distance calculation function performs better than that of the Manhattan distance, and is more robust and flexible during calculation.

However, the above-mentioned optimization methods can only achieve meter-level localization accuracy. The training process for the high-quality fingerprint collection is time-consuming, limiting the efficiency in time. And also the influence of obstacle attenuation and path loss on the localization accuracy and performance in complex indoor environments is seldom considered. A hybrid technique with the combination of maximizing fingerprint difference (MaxFD) and minimizing geometric dilution of precision (MinGDOP) for reliable indoor localization was proposed by Jia et al. [12], where the attenuation of walls and people has been taken into account during the optimization process. Even so, due to the adopted grid spacing of 2 m, the resulted precision is extremely low. In Ref. [33], the Apollonius circle theory is used to calculate the virtual locations of APs under the assumption that neighboring locations share the same attenuation parameter corresponding to the signal attenuation caused by obstacles. This approach improved the accuracy and robustness of the Wi-Fi based fingerprint techniques, and achieved the highest level of performance.

As for the indoor localization and AP selection in three-dimensional environments, the related studies are even fewer. A highly accurate three-dimensional indoor passive localization and identification system is presented in Ref. [34], which is designed to be capable of detecting devices through walls. Reference [35] shows that the localization error can be effectively reduced by eliminating phase ambiguity (PA) in the three-dimensional beamspace matrix pencil (BMP) based localization scheme.

Therefore, the localization performance and accuracy, signal loss through obstacles, path loss, and the three-dimensional positioning model are still challenging for Wi-Fi indoor localization. Wi-Fi fingerprint localization suffers from high implementation overhead, such as heavy initial training and fingerprint map maintenance over time [36]. As a result, the signal strength of all RPs is required to calculate the path loss with the aim to improving the localization efficiency. In addition, the grid size is usually larger than 2 m in traditional fingerprint positioning methods [37], which results in quite low localization accuracy. This paper presents an FGGC model that can achieve decimeter-level positioning accuracy. Moreover, it can build the fingerprint database automatically without manual measurement, thus the efficiency is increased and the cost is reduced. Furthermore, since it takes less time to calculate the approximate grid location by the random forest method and estimates the fine-grained location based on the approximate grid location, higher real-time performance and localization precision are simultaneously achieved.

The proposed FGGC model is schematized in Fig. 1, which mainly contains the generation of RPs, prediction of grid locations, and calculation of estimated locations. RPs are first generated and the corresponding RSS values are calculated from all APs at each point. The RSS value and the data of grid points are then trained by the random forest algorithm, so that the grid location can be obtained by inputting the RSS values. The fine-grained points around the grid location are generated and the estimated location is finally calculated by the RSS Euclidean distance.

In traditional methods, RPs are typically generated by manually measuring the RSS values multiple times at each grid point. This makes it time-consuming to build the fingerprint database. In addition, if the location of AP or the obstacle changes, it is necessary to manually measure RSS values again. In this paper, the rules of path loss are used to calculate the signal values of grid points automatically, which significantly improves the efficiency and accuracy of localization.

To generate RPs, which are the most important information for indoor localization, the number of grid points in the horizontal axis (M) and that in the vertical axis (N) are first calculated by dividing the space into numerous grid points according to the edge length of the square grid (gsize).

$ M=\frac{\mathrm{m}\mathrm{a}\mathrm{p}\mathrm{x}}{\mathrm{g}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}\tag{1a} $ ()

$ N=\frac{\mathrm{m}\mathrm{a}\mathrm{p}\mathrm{y}}{\mathrm{g}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}} \tag{1b}$ ()

where mapx and mapy represent the length and width of the indoor map, respectively.

The RSS values at each grid point can be calculated by (2) and (3). Finally, RPs are generated, which consist of all the RSS values (F(x, y, z)) at the point (x, y, z) from all APs, as shown in (4).

$ F\left(\cdot \right){\mathrm{:}}\;{\mathbb{R}}^{K}\to {\mathbb{R}}^{3} $ (2)

$ F\left( {x{\rm{,}}{\text{ }}y{\rm{,}}{\text{ }}z} \right) = \left( {r_{x{\mathrm{,}}y{\mathrm{,}}z}^1{\rm{,}}{\text{ }}r_{x{\mathrm{,}}y{\mathrm{,}}z}^2{\mathrm{,}}{\text{ }} \cdots {\mathrm{,}}{\text{ }}r_{x{\mathrm{,}}y{\mathrm{,}}z}^K} \right) $ (3)

$ \mathrm{R}\mathrm{P}\mathrm{s}=\left\{F\left(x{\rm{,}}\;y{\rm{,}}\;z\right)\right|0\le x\le M{\rm{,}}\; 0\le x\le N{\rm{,}}\;z=1{\mathrm{.}}5\} {\mathrm{.}} $ (4)

where $ {r}_{x{\rm{,}}y{\rm{,}}z}^{i} $ represents the RSS value of AP_i at each spatial point (x, y, z) on the grid, $ F\left(\cdot \right) $ maps a K-dimensional real space to a three-dimensional real space, and the AP’s height z is defined as 1.5 m.

The RSS value of AP_i ($ 0\le i < K $) can be calculated by

$ {r}_{x{\rm{,}}y{\rm{,}}z}^{i}={P}^{i}-{\Gamma }_{x{\rm{,}}y{\rm{,}}z}^{i} $ (5)

where $ {P}^{i} $ is the power of AP_i and $ {\Gamma }_{x{\rm{,}}y{\rm{,}}z}^{i} $ is the path loss from AP_i to the point (x, y, z).

Here the path loss $ {\Gamma }_{x{\rm{,}}y{\rm{,}}z}^{i} $is calculated by

$ {\Gamma }_{x{\rm{,}}y{\rm{,}}z}^{i}=C+\mathrm{lg}\left(\lambda /2.4\right)+{\Omega }_{x{\rm{,}}y{\rm{,}}z}^{i}+{\Phi }_{x{\rm{,}}y{\rm{,}}z}^{i} $ (6)

where $ C $ is a constant, $ \lambda $ is the frequency band of AP, and $ \mathrm{lg}\left(\lambda /2.4\right) $ represents the frequency loss of AP. Based on the Euclidean distance between the estimated point and AP, $ {\Omega }_{x{\rm{,}}y{\rm{,}}z}^{i} $ represents the path loss of AP_i and $ {\Phi }_{x{\rm{,}}y{\rm{,}}z}^{i} $ represents the signal loss of AP_i through the wall, which can be obtained by (7) and (8), respectively, when the location of AP_i is defined as $ ({a}_{x}^{i}{\rm{,}}\;{a}_{y}^{i}{\rm{,}}\;{a}_{z}^{i}) $.

$ \Omega _{x{\rm{,}}y{\rm{,}}z}^i = 10n {\mathrm{lg}} \left( {\sqrt {{{\left( {x - a_x^i} \right)}^2} + {{\left( {y - a_y^i} \right)}^2} + {{\left( {z - a_z^i} \right)}^2}} } \right) $ (7)

$ \Phi _{x{\rm{,}}y{\rm{,}}z}^i = \sum\limits_{t = 1}^T {{\beta _t}} $ (8)

where n is the coefficient of path loss, t is the number of walls, and $ {\beta }_{t} $ is the signal loss of the tth wall.

Generally, RSS of the two-dimensional plane at a given height is used in the real application. This allows the signal strength to be converted from a three-dimensional plane to a two-dimensional plane. If z = 1.5 m is assigned, the RSS values of all RPs are presented as the dataset D.

$ {\mathbf{D}}{\text{ = }}\left[ {$$\begin{array}{cccc}\left(r_{0,0}^0,r_{0,0}^1,\cdots ,r_{0,0}^K\right)& \left(r_{1,0}^0,r_{1,0}^1,\cdots ,r_{1,0}^K\right)& \cdots & \left(r_{M,0}^0,r_{M,0}^1,\cdots ,r_{M,0}^K\right)\\ \left(r_{0,1}^0,r_{0,1}^1,\cdots ,r_{0,1}^K\right)& \left(r_{1,1}^{\text{0}},r_{1,1}^1,\cdots ,r_{1,1}^K\right)& \cdots & \left(r_{M,1}^0,r_{M,1}^{\text{1}},\cdots ,r_{M,1}^K\right)\\ ⋮& ⋮& \ddots & ⋮\\ \left(r_{0,N}^0,r_{0,N}^{\text{1}},\cdots ,r_{0,N}^K\right)& \left(r_{1,N}^0,r_{1,N}^1,\cdots ,r_{1,N}^K\right)& \cdots & \left(r_{M,N}^0,r_{M,N}^1,\cdots ,r_{M,N}^K\right)\end{array}$$} \right]{\mathrm{.}} $ (9)

Algorithm 1 shown in Table 1 describes the calculation of RPs and the training dataset. First, the output grid RPs are declared and the dataset D is trained. Second, in steps 1–3, the system variables are initialized. The map is split into multiple grid points in steps 4–8, and then the power of AP_i (steps 9 and 10), frequency loss (step 11), path loss (step 12), and wall loss (steps 12–19) can be obtained. Next in steps 20–22, the RSS values for all APs can be calculated and then put into an array. Finally, the feature dataset F, label dataset L (step 23), RSS values of RPs (steps 24–26), and training dataset D (step 27) are formed.

According to Algorithm 1, it is obvious that the training dataset of RPs D consists of a feature dataset F, which represents the RSS value, and a label dataset L, which represents the coordinates of the grid points. This indicates that the dataset D can reveal the relationship between the RSS value and the grid points. By randomly selecting R records from the RP dataset D at a time, a decision tree is trained as shown in Fig. 2. The number of APs that represents the number of features in the training dataset is K, and only f (f < K) features are selected each time to construct the decision tree.

The detailed process for building a decision tree is described as follows:

Step 1: There are Q samples in D, and R samples are randomly selected from D. The selected R samples are used to train the decision tree as the samples of decision root nodes.

Step 2: There are K features in each sample. When a node in the decision tree needs to be split, f features are randomly selected (f < K). Then one feature is selected from the f features according to the information gain as the split feature of the node.

Step 3: In the process of decision tree formation, each node must be split via step 2 until it can no longer be split.

Step 4: Steps 1–3 are repeated to build a large number of decision trees, thus forming a random forest.

After the grid point is obtained by the random forest algorithm, the location of this grid point is taken as the center to produce numerous fine-grained locations, and the location with the minimum Euclidean distance can be found from the predicted RSS values. Here the RSS Euclidean distance is calculated by (10). And accordingly, the minimum distance shown in (11) is the most appropriate location for our prediction.

$ {\text{distanc}}{{\text{e}}_i} = \sqrt {\sum\limits_{i = 0}^K {{{\left( {r_{x{\rm{,}}y{\rm{,}}z}^i - {{r'}^i}} \right)}^2}} } $ (10)

$ {\text{loc}} = {\mathrm{min}} \left\{ {{\text{distanc}}{{\text{e}}_0}{\rm{,}}{\text{ distanc}}{{\text{e}}_1}{\rm{,}}{\text{ }} \cdots {\rm{,}}{\text{ distanc}}{{\text{e}}_K}} \right\} $ (11)

where $ {r'}^i $ is the input value denoting the RSS value of AP_i.

Algorithm 2 shown in Table 2 describes the calculation of the estimated locations. First, the output location of the estimated point is declared. Second, numerous fine-grained locations around the approximate point are produced in steps 1–7, and then the RSS values at each location from all APs are calculated in steps 8–11. In steps 12–14, the Euclidean distance between the RSS value at the fine-grained location and the predicted RSS value is obtained. Finally, the location (x, y) with the minimum Euclidean distance is the estimated point we desired (steps 15–21).

The proposed model is implemented by using Tensorflow 2.4.0 framework on a Dell laptop (Windows 10, 64-bit operating system, Intel(R) Core(TM) i7-8550U CPU@1.80 GHz, 8 GB RAM).

To evaluate the performance of the proposed technique, an indoor map with the length of 40 m and the width of 30 m is considered, as shown in Fig. 3. From the top view, the indoor environment is usually divided into multiple subspaces by the walls with two orientation angles that are perpendicular to each other in most cases. The grid size used here is 1 m.

During the simulation, four APs are placed in the environment. For each AP, the path and signal losses caused by the wall are calculated according to (7) and (8). A unique identification (ID) is defined for each wall. When the signal penetrates from one AP to the grid, the number of walls is the number of IDs on the shortest line connecting these two points.

Besides the frequency loss and the path loss of AP, it is worth noting that the signal loss caused by the wall is also incorporated into the path loss model. The signal loss caused by the wall is assumed to be 10 dB. The parameters used in the simulation are shown in Table 3.

In the simulation, the RSS coverage of APs is rendered in different colours in the heat map. Based on the indoor map shown in Fig. 3 (including the wall and door), the entire space is divided into 1200 grids with a grid size of 1.0 m. Different values of mesh accuracy will have different effects on the localization accuracy, which will be confirmed in the following analysis.

Fig. 4 shows the RSS heat map of four APs at 5.2 GHz. This map clearly shows the signal strength of each coordinate point in the indoor map, the trend in the path loss as the signal propagates, and the attenuation of the signal as it passes through the walls. Obviously, when the signal passes through the wall, the signal strength decreases.

Thirty test points are generated by manual measurement to verify the proposed algorithm. After performing the localization algorithm, the localization error for each of the configurations is calculated by (12), where the Euclidean distance between the estimated location P_Est and the actual location P_Act should be measured first, and s represents the number of estimated locations.

$ {\text{Error}} = \sqrt {\sum\limits_{i = 1}^s {{{\left( {P_{{\text{Act}}}^i - P_{{\text{Est}}}^i} \right)}^2}} } {\mathrm{.}} $ (12)

The calculated results are shown in Table 4. It is obvious that both the mean error and the maximum error of our proposed model are minimal. Its mean error is only 0.36 m, which is much lower than that of MaxFD, MinGDOP, and even their hybrid method reported in Ref. [12]. The proposed FGGC model is further evaluated by comparing with other three methods for indoor localization including adaptive area search (AAS) [26], APD-WKNN [25], and the hybrid hypothesis approach [27]. The mean errors of AAS, APD-WKNN, and the hybrid hypothesis approach are 2.37 m, 2.18 m, and 1.85 m, respectively. Obviously, the localization accuracy of our FGGC model is further improved by 84.81% over AAS, 83.49% over APD-WKNN, and 80.54% over the hybrid hypothesis approach.

The actual and estimated locations of the test points are compared by deploying APs using our proposed model (FGGC), and the results are shown in Fig. 5. Among the thirty test points, the minimum error is 0.10 m and appears at four points (24.0, 7.5), (36.7, 10.0), (21.6, 18.6), and (3.3, 10.0). The maximum error is 0.64 m and occurs at point (23.9, 22.1). Obviously, the estimated locations of most of the test points are almost overlapping with their actual locations, and only a few test points show a slight deviation. For example, only nine test points show a deviation larger than 0.50 m.

For further validation of our proposed model (FGGC), the localization error and running time with different numbers of samples are compared, as shown in Fig. 6. The results show that with the increase in the number of samples, the running time increases, while the mean error per meter remains stable at about 0.40 m. When the number of samples is less than 30, the maximum error is 1.00 m, while when it exceeds 40, the maximum error is increased to 1.60 m. The results indicate that our proposed model (FGGC) can stably maintain a decimeter-level mean error of less than 0.40 m with the increase in the number of samples. Therefore, it can be concluded that our proposed FGGC model can be used as an effective model for indoor localization.

The localization error is also affected by the grid accuracy of the indoor map. Fig. 7 shows the changes in the localization error and running time of our proposed algorithm with different spatial grid sizes. It is obvious that under different grid sizes, the running time is stable within 1 s, while both the mean error and the maximum error increase as the grid size increases. When the grid size is 2.5 m, the mean error is larger than 1.00 m, while the maximum error is 8.00 m. However, the algorithm still maintains high precision and fast running speed even under the large grid size.

In this paper, a fine-grained grid computing model was proposed for Wi-Fi indoor localization. The frequency band, three-dimensional propagation distance, and walls in complex environments were calculated in the path loss formula to improve the accuracy. The estimated locations were calculated step by step from the approximate grid location to the fine-grained location, thus achieving higher efficiency and accuracy. However, the RSS value can be influenced by more factors, such as the shape of obstacles, population size, and channels of APs. One of the future directions of our work is how to take more possible factors into the path loss formula to further improve the accuracy.

The authors declare no conflicts of interest.