2.1. Fingerprint positioning algorithm

The Wi-Fi fingerprinting method is the most widely used and most practical algorithm of all the indoor positioning algorithms, and is mainly dependent on the RSSI data and the spatial coordinate of the RP. Figure 1 shows the framework of the FP algorithm.

Figure 1.

Framework of the FP algorithm.

In the offline stage, the main task is to establish a fingerprint database. First, some points in the location area are selected as the RPs and the spatial coordinates of these RPs are known. At each RP, some information of the AP is recorded by utilising the Wi-Fi signal collector, including the basic service set identifier (BSSID) and RSSI. The BSSID of an AP can be used to distinguish different signal sources, the RSSI vector with length q received from AP_j at RP_i is indicated by $\{ \mbox{rssi}_{i, j} ( t), \; \ t=1, \; 2, \; \ldots, \; q, \; q\ge 1\}$. The mean value of AP's RSSI vector tends to be stable when q ≥ 30 (Kaemarungsi and Prashant, Reference Kaemarungsi and Krishnamurthy2012). To obtain an appropriate number of samples, different numbers of fingerprints are collected at each RP. Through experiments, the conclusion can be obtained that when q = 60, the positioning error is the lowest. Therefore, the value of q is set to 60 in this paper.

The coordinates of all RPs and the average value of all APs' RSSI vectors $\mbox{RSSI}_{i, j} =( 1/q) \sum_{t=1}^{q} {\mbox{rssi}_{i, j} ( t) }$ are saved into the fingerprint database. Here DB _{m, n} is used to represent the fingerprint database created in the offline stage and the fingerprint database DB _{m, n} can be expressed as

(1)$$DB_{m,n} =\left[ {{\begin{matrix} {(x_1,y_1 )} & {\mbox{RSSI}_{1,1} } & {\mbox{RSSI}_{1,2} } & \cdots & {\mbox{RSSI}_{1,n} } \\ {(x_2,y_2 )} & {\mbox{RSSI}_{2,1} } & {\mbox{RSSI}_{2,2} } & \cdots & {\mbox{RSSI}_{2,n} } \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ {(x_m,y_m )} & {\mbox{RSSI}_{m,1} } & {\mbox{RSSI}_{m,2} } & \cdots & {\mbox{RSSI}_{m,n} } \\ \end{matrix} }} \right]$$

Suppose that there are m RPs and n APs in the location area, $( {x_{i}, \; y_{i} } ) $ represents the spatial coordinate of RP_i. Here $\mbox{RSSI}_{i, j}$ denotes the average value of the RSSI vector of AP_j detected at RP_i. When the AP_j cannot be detected at RP_i (i.e. the signal of AP_j is too weak to detected), a minimum fixed value is assigned to $\mbox{RSSI}_{i, j} $ and the fixed value is set to −100 (dBm).

In the online stage, the real-time RSSI values of APs are collected and matched with the RSSI vector in the fingerprint database, then the current position can be calculated by the matching algorithm, e.g., the WKNN algorithm.

In the WKNN algorithm, the characteristic distance is used to indicate the positioning distance between the target point and each RP, and the characteristic distance between the real-time measured RSSI vector and the RSSI vector in the fingerprint database can be expressed as

(2)$$L_i =\left( {\sum\limits_{j=1}^n {\vert {\mbox{rssi}_j -\mbox{RSSI}_{i,j} } \vert^p} } \right)^{1/p}$$

where L _i is the characteristic distance, also called the characteristic distance between the target point and the RP_i. Here rssi_j represents the real-time measured RSSI value of AP_j. When p = 1 and 2, L _i represents the Manhattan distance and Euclidean distance, respectively.

After calculating the characteristic distance between the target point and the RPs in the fingerprint database, the first k RPs with the smallest characteristic distance are selected for positioning, the target point's coordinate can be calculated from the weighted average of the k RPs' coordinates, given by

(3)$$( {\hat {x},\hat {y}} ) =\frac{\sum_{i=1}^k {W_i \cdot ( {x_i,y_i } ) } }{\sum_{i=1}^k {W_i } }$$

where $( {\hat {x}, \; \hat {y}} ) $ is the estimation coordinate of the target point and W _i denotes the weighting coefficient of RP_i. In general, W _i is equal to the reciprocal of the characteristic distance in most fingerprint algorithms.

The positioning accuracy of the WKNN algorithm is dependent on the value of k: different values of k lead to different positioning accuracies. In fact, it has been shown that the WKNN algorithm has the smallest positioning error when k = 5 (Shin et al., Reference Shin, Lee, Lee and Kim2012). As such, we choose k = 5 when using the WKNN algorithm for positioning.

2.2. Fingerprint algorithm with segment characteristic distance

The Euclidean distance is mostly used in the fingerprint algorithms, but the Manhattan distance can also be used to calculate the characteristic distance. Li et al. (Reference Li, Qiu and Liu2017) simulated the effect of the Manhattan distance and Euclidean distance on the accuracy of the WKNN algorithm and discussed the relationship between the RSSI and the actual distance. Finally, a fingerprint algorithm with segment characteristic distance was proposed to improve the positioning accuracy. The characteristic distance can be expressed as

(4)$$L_i =\begin{cases} \displaystyle\sum_{j=1}^n {\gamma \cdot \vert {\mbox{rssi}_j -\mbox{RSSI}_{i,j} } \vert, \vert {\mbox{rssi}_j -\mbox{RSSI}_{i,j} } \vert \ge d} \\ \noalign{\vskip6pt} \displaystyle\sum_{j=1}^n {\frac{1}{\gamma }\cdot \vert {\mbox{rssi}_j -\mbox{RSSI}_{i,j} } \vert, \vert {\mbox{rssi}_j -\mbox{RSSI}_{i,j} } \vert < d} \end{cases}$$

where γ and d are the undetermined variables. For each AP, when the difference between the real-time RSSI vector measured at the target point and the RSSI vector in the database is greater than the constant d, the difference is expanded by γ times. In contrast, when the RSSI difference is less than or equal to the constant d, the difference is reduced by γ. Some simulations have been performed in different indoor environments and the mean error of the WKNN algorithm was the smallest when γ = 5, d = 3.

Although the fingerprint algorithm with segment characteristic distance (FP-SCD) performs well in terms of positioning accuracy, the impact of the AP on the positioning accuracy in the offline stage has not been considered by researches, so the FP-SCD requires complicated calculations and the time spent for positioning would be long. The idea of improving the characteristic distance has been adopted in our proposed algorithm and the FP-SCD was used for comparison with the proposed algorithm.

3.1. AP selection strategy

Each AP in the experimental area generates wireless signals that radiate outwards. When the signals propagate in space, they gradually decline owing to multipath effects. The signal distribution of each AP in space is different because of the complex indoor environment. Figure 2 shows the distribution of wireless signals from two different APs.

Figure 2.

RSSI distribution curves of two different APs at each RP.

As shown in Figure 2, the RSSI values of AP1's wireless signal is widely distributed in the range of [−90, −40] (dBm) and may not be detected at some RPs, which means that the wireless signal of AP1 decays rapidly in the experimental area. At different RPs, the RSSI values detected by the Wi-Fi signal collector are different, so the spatial location can be distinguished with the wireless signal of AP1. While the RSSI values of AP2 are concentrated in the range of [−90, −60] (dBm), this implies that the attenuation of AP2's wireless signal in the experimental area is lower than AP1's. At different RPs, the RSSI values are similar, so it is difficult to distinguish different spatial positions by using the RSSI value of AP2.

The spatial distributions of wireless signals at different APs are different. The space difference between the wireless signals of some APs is obvious, whereas the space difference between the wireless signals of some other APs is not obvious. Therefore, it is unreasonable to distinguish different APs according to the values of the signal strength. In the AP selection strategy, the variance of RSSI values is selected to describe the spatial discrimination of APs.

For an AP, the variance of RSSI represents the variance of the signal strength at all RPs. It represents the degree of dispersion of the signal strength at all RPs and it can be used to indicate the amount of position information provided by the AP.

The signal strength of AP _j at all RPs can be expressed as

(5)$$V_j =[\mbox{RSSI}_{1,j},\mbox{RSSI}_{2,j},\ldots,\mbox{RSSI}_{i,j},\ldots,\mbox{RSSI}_{M,j}],\quad i=1,2,\ldots,M$$

where M denotes the number of RPs and $\mbox{RSSI}_{i, j}$ represents the average signal strength of AP_j at RP_i. Then the variance $\sigma_{Vj}^{2} $ can be expressed as

(6)$$\sigma _{Vj}^2 =\frac{(\mbox{RSSI}_{1,j} -\overrightarrow {\mbox{RSSI}} )^2+(\mbox{RSSI}_{2,j} -\overrightarrow {\mbox{RSSI}} )^2+\cdots +(\mbox{RSSI}_{M,j} -\overrightarrow {\mbox{RSSI}} )^2}{M}$$

where $\overrightarrow {\mbox{RSSI}}$ indicates the average signal strengths of AP_j at all RPs and the variance of AP_j can be calculated by formula (6).

The variance of an AP can be obtained by calculating the signal strength of the AP at all RPs, after calculating the variance of all APs, and the variance distribution of all APs is shown in Figure 3. Table 1 shows the signal strength variance distribution of all APs. The variance of most APs is low, this means that spatial discrimination of most APs is low. The ratio of the signal strength variance being less than 50 is 73·19%, which means that if the AP whose signal strength variance is less than 50 is screened out, the total number of APs in the fingerprint database can be reduced by 73·19%.

Figure 3.

The variance distribution of all APs.

Table 1.

The variance distribution of all APs.

Figure 4 shows the positioning error of fingerprint algorithm after screening out the AP whose variance is less than the variance threshold σ². Any point on the curve in Figure 4 indicates that the average estimation error of the WKNN algorithm is the value corresponding to the ordinate after screening out the APs with variance less than the value corresponding to the abscissa. As the variance threshold σ² increases, the average estimation error of the algorithm increases. The greater the number of APs screened out, the higher the positioning error. Figure 5 shows the average positioning error of fingerprint algorithm after screening out the APs the variance beyond the variance threshold σ². Any point on the curve in Figure 5 indicates that the average estimation error of the WKNN algorithm is the value corresponding to the ordinate after screening out APs with variance exceeding the value corresponding to the abscissa. As the variance threshold σ² increases, the average estimation error of the algorithm decreases.

Figure 4.

The positioning effect of the fingerprint algorithm after screening out the APs with variance below a certain threshold.

Figure 5.

The positioning effect of fingerprint algorithm after screening out the APs with variance beyond a certain threshold.

If the APs with low spatial discriminability were screened out, they would not be saved into the fingerprint database, the number of APs used to calculate the characteristic distance in the online stage would decrease, and the amount of location information provided by these APs would also decrease. That is why the positioning error increases. On the other hand, if these APs were screened out, the final positioning result would not change too much. This is why the positioning error grows so slowly as the variance threshold increases. The same observations can be made in Figure 5.

The APs saved into the database in the offline stage are referred to as the offline APs: the higher the number of offline APs, the larger the database. The APs used to calculate the characteristic distance in the online stage are referred to as the online APs. Figures 6 and 7 show the relationship between the number of offline/online APs and the variance threshold.

Figure 6.

The relationship between the variance threshold and the number of offline APs.

Figure 7.

The relationship between the variance threshold and the number of online APs.

As shown in Figures 6 and 7, the number of offline APs and online APs decrease gradually as the variance threshold increases. Any point on the curve in Figures 6 and 7 indicates that the number of offline/online APs is the value corresponding to the ordinate after screening out APs with variance lower than the value corresponding to the abscissa and the fingerprint database is reconstructed. As the variance threshold increases, the stricter the conditions for screening APs become and the fewer APs remain. The relationship between the number of online APs 2 and the positioning error is shown in Figure 8.

Figure 8.

The relationship between the number of online APs and the average positioning.

Figure 8 shows that the average positioning error decreases gradually as the number of online APs increases. This is because a large number of online APs and a longer RSSI vector lead to higher accuracy of the positioning matching. As the number of online APs increases, the more location information these APs can provide, the more accurate the positioning result can be obtained. However, when the number of online AP reaches a certain level, the positioning accuracy of the fingerprint algorithm approaches a fixed value. The reason is that the location information provided by online APs is sufficient for positioning. The fixed value and the number of APs can be obtained from Table 3. The fixed average positioning error is 1·34 m and the number of online APs is 104.

From the above analysis, the larger the variance threshold, the fewer online APs remain after the AP selection strategy. Correspondingly, the fingerprint database would be smaller and the positioning error would be higher. Therefore, it is necessary to find a suitable variance threshold to balance the database size and the positioning accuracy.

Figure 4 and Table 2 show that when the variance threshold changes from 0 dBm² to 50 dBm², the positioning error of the fingerprint algorithm is almost unchanged. When the positioning error of the fingerprint algorithm is a constant, the maximum variance threshold is selected as the suitable variance threshold in the AP selection strategy. This ensures that the minimum positioning error can be achieved and the APs are filtered out as much as possible to reduce the size of the fingerprint database. To obtain a suitable variance threshold, 60 sets of data collected at each test point in the online stage were used in this experiment. At each test point, each set of data corresponds to one positioning result and there are 100 test points in the experiment area. Therefore, a total of 6,000 tests were carried out. The average positioning error was obtained by 6,000 tests. The relationship between the variance threshold and the average positioning error is listed in Table 3.

Table 2.

The result after the AP selection strategy.

Table 3.

The variance threshold and the average positioning error data.

Table 3 lists the maximum value of the variance threshold as 29 dBm² when the average positioning error achieves its minimum, 1·34 m. When the variance threshold is 29 dBm², the positioning error is minimal and the size of the fingerprint database can be reduced. Therefore, the variance threshold in the AP selection strategy is set to 29 dBm².

3.2. The Kalman filter algorithm

The Kalman filter algorithm is an algorithm for optimally estimating the state of the system by inputting and outputting observation data on the basis of the state equation of the linear system. Each iteration includes two stages of prediction and correction, and each iteration only needs to record the last system state and error covariance, thus the Kalman filter algorithm has a better denoising effect than the other filter algorithms. Therefore, the Kalman filter algorithm has been widely used.

For a linear system, it can be described by an equation of state and observation equation. At time k, $x( k ) $ represents the system state, $u( k ) $ denotes the control amount, $w( k ) $ represents the process noise, $z( k ) $ indicates the observation value of the system and y(k) represents the measurement noise. Here A and B are the system parameters and H is the parameter of the measurement system. The state equation and observation equation can be expressed as

(7)$$\begin{aligned} x(k)&=A\bullet x(k-1)+B\bullet u(k)+w(k) \\ z(k)&=H\bullet x(k)+y(k) \end{aligned}$$

In the prediction stage, $\hat {x}( k\vert k-1) $ represents the state variable at time k, $\hat {P}( k\vert k-1) $ denotes the predicted value of the error covariance at time k and $P( {k-1} ) $ indicates the error covariance at time k − 1. The entire prediction process can be expressed as

(8)$$\begin{cases} {\hat {x}(k\vert k-1)=A\bullet x(k-1)+B\bullet u(k)} \\ {\hat {P}(k\vert k-1)=A\bullet P(k-1)+Q} \end{cases}$$

In the correction stage, the process of entire predication can be expressed as

(9)$$\begin{cases} K(\mbox{k})=\hat {P}(k\vert k-1)\bullet H^T\bullet ((H\bullet \hat{P}(k\vert k-1)\bullet H^T+R)^{-1} \\ {x(k)=\hat {x}(k\vert k-1)+K(k)\bullet (z(k)-H\bullet \hat {x}(k\vert k-1))} \\ {P(k)=(I-K(k)\bullet H)\bullet \hat {P}(k\vert k-1)} \end{cases}$$

where $K( k ) $ represents the Kalman gain at time k, and I represents the identity matrix. This paper considers the use of the Kalman filter algorithm to process the RSSI values collected in the online stage. The Kalman filter algorithm can be simplified according to the actual situation. In indoor positioning, when the experimenter collects data at the target point, their positioning is basically unchanged, so the control amount can be set to 0. In addition, when the Kalman filter algorithm is only used to process single-signal data, A and H can be set to 1. Then, the formula in the prediction and correction stage can be expressed as

(10)$$\begin{cases} {K(x)=\hat {P}(k\vert k-1)/\hat {P}(k\vert k-1)+R} \\ {x(k)=x(k-1)+K(k)\bullet (z(k)-x(k-1))} \\ {\hat {P}(k+1\vert k)=(1-K(k))\bullet \hat {P}(k\vert k-1)+Q} \end{cases}$$

The Minkowski distance is mainly used to calculate the distance between two points. Assuming that the coordinate of point P is $( {x_{1}, \; x_{2}, \; \ldots, \; x_{n} } ) $ and the coordinate of point Q is $( {y_{1}, \; y_{2}, \; \ldots, \; y_{n} } ) $, then the distance between two points can be expressed as

(11)$$D=\left( {\sum_{i=1}^n {\vert {x_i -y_i } \vert^p} } \right)^{1/p}$$

When p = 1 and 2, D represents the Manhattan distance and Euclidean distance, respectively. In the WKNN algorithm, the Minkowski distance is used to calculate the characteristic distance of two points. When the parameter p takes different values, the characteristic distance between two points is different, then the positioning result would be different.

In the WKNN algorithm, the Kalman filter algorithm is used to process signal strength data in the online stage. The average estimation error before and after filtering is listed in Table 4. When the value of p is 1·5 or 2, the positioning error is minimal, when p is equal to 1·5, the calculation of characteristic distance on computer would be very complicated, so the Euclidean distance is chosen as the characteristic distance for the positioning in this paper.

Table 4.

The average estimation error before and after filtering.

Table 4 demonstrates that after the signal strength data are processed by the Kalman filter algorithm, the average estimation error becomes lower. We conclude that it is feasible to use the Kalman filter algorithm in the online stage.

3.3. RP selection strategy

For the selection strategy of the RPs, Xue et al. (Reference Xue, Hua, Li, Yu and Qiu2018) showed that the k RPs with the smallest characteristic distance were not the k RPs closest to the target point and an improved neighbouring RPs selection method for Wi-Fi-based indoor localisation was proposed. To avoid selected RPs being on one side of the test point, the physical distances between the neighbouring RPs and the test point were exploited for clustering these KNNs. However, the selection process is too simple and the effect of the selection strategy is imperfect.

In the fingerprint algorithm, the actual distance between the target point and each RP can be expressed by the characteristic distance. However, the actual distance and the characteristic distance are not linearly correlated. Figure 9 shows the relationship between the actual distance and the characteristic distance in a positioning process.

Figure 9.

The relationship between the actual distance and the characteristic distance.

Figure 9 shows that the actual distance and the characteristic distance are not strictly positively related: some RPs with large actual distance have small characteristic distance. If these RPs are selected for positioning, the estimated position would deviate greatly from the true position of the target point. To solve this problem, an RP selection strategy based on spatial subregions and regional characteristic distances is proposed.

In the offline stage, the target area here is square with RPs distributed uniformly. A square area is defined as a spatial subregion and the regional characteristic distance of the spatial subregion can be calculated by adding the characteristic distances of the four RPs that make up the spatial subregion.

Figure 10 shows the structure of the spatial subregion. The spatial subregion 1 is surrounded by RP₁, RP₂, RP₄ and RP₅, the regional characteristic distance of spatial subregion 1 can be calculated by the formula $RL_{1} =L_{1} +L_{2} +L_{4} +L_{5} $, where L ₁, L ₂, L ₄ and L ₅ denote the characteristic distance of RP₁, RP₂, RP₄ and RP₅, respectively.

Figure 10.

Spatial subregion.

After calculating the regional characteristic distance of each spatial subregion, one or more spatial subregions with the smallest regional characteristic distance are selected as a result of the regional estimation. After the test points are determined into one or more spatial subregions, the RPs outside these spatial subregions are filtered out and the k RPs with smallest characteristic distance from the remaining RPs are selected for positioning. Finally, the position of the target point can be calculated by the WKNN algorithm.

In the RP selection strategy, the final positioning error is dependent on the number of spatial subregions contained in the regional estimation, Figure 11 shows the relationship between the positioning error and the number of spatial subregions contained in the regional estimation.

Figure 11.

The relationship between positioning error and the number of spatial subregions.

Figure 11 shows that the average positioning error first decreases then increases as the number of spatial subregions increases. When the number of spatial subregions is 2, the positioning error is the lowest. This indicates that the effect of the RP selection strategy is best when the number of subregions is 2. The explanation for this observation is as follows. The WKNN algorithm has the smallest positioning error when k = 5 (Shin et al., Reference Shin, Lee, Lee and Kim2012). When the number of subregions is 1, only 4 RPs are left after the other RPs are screened out, and the positioning accuracy is not improved significantly. When the number of subregions is 2, 6 RPs can be left after the other RPs are screened out. Since the WKNN algorithm has the lowest positioning error when k = 5, when the number of subregions is 2, the positioning error is the lowest. To verify the accuracy of this conclusion and make it more convincing, the same experiment was repeated 60 times in the real experimental scenario, but, in the end, the same conclusion was obtained: when the number of subregions is 2, the positioning error is the lowest. Therefore, the number of spatial regions contained in the regional estimation is set to 2 in the RP selection strategy.

3.4. The proposed FP algorithm

The proposed FP algorithm is as follows: