Optimization of Sampling Cell Size for Fingerprint Positioning

Abstract

The fingerprint positioning based on received signal strength has a widespread development in many applications since the technology does not depend on additional hardware deployment. However, the site survey process which is executed before fingerprint positioning is time consuming and labor intensive. Sampling cell size directly affects the localization precision and the survey workload. We propose a sampling cell size optimization method to release the survey workload while holding the precision. We adopted the Gaussian process model to estimate the received signal strength based on some samples and used the inherent maximum Euclidean error of fingerprint vectors to compute the optimal cell size. We conduct some experiments to validate the efficiency of the mechanism. And the results show that our method can largely reduce the workload of the site survey process.

1. Introduction

Indoor positioning is a critical enabler for location based services and applications. In many scenarios (e.g., shopping malls, supermarkets, and airport terminals), the location can provide the shopping guide, commodity promotion, and path navigation. Since the GPS technology is not available in the building, various wireless signal technologies (e.g., Zigbee, RFID, Bluetooth, UWB, and WiFi) have been applied to indoor positioning. However, accuracy and the overhead limit the feasibility of indoor localization system. Various positioning systems can achieve a high accuracy at a cost of additional hardware. For example, the systems based on the time of arrival (ToA) measurement need accurate time synchronization or specific hardware to compute the arriving time.

The fingerprint positioning is a promising indoor localization method which requires no additional hardware. Therefore, fingerprint positioning has been widely applied in many applications [1–3]. However, fingerprint positioning needs an additional site survey process to record the RSS fingerprints at every point of the interested area to build the fingerprints database. Meanwhile, sampling cell size (i.e., cell area) also needs to be defined before the site survey. This process is time consuming and labor intensive. Furthermore, the fingerprint database needs to be updated with the changing of environments. Much research has focused on avoiding the tedious presurvey. In some work, the crowdsourcing method is adopted to assemble the fingerprint information from masses of location based services’ users [4, 5]. This can reduce the individual labor through many people's cooperation. But the sampling cell size still needs to be determined.

Larger sampling cell size implies the fewer survey workload but the lower positioning accuracy. Thus, we need to find the optimal sampling cell size to achieve a balance between the survey workload and positioning accuracy. The traditional methods adopt the default empirical values (e.g., 1 m × 1 m or 2 m × 2 m) [6, 7] or the users’ stride in the crowdsourcing. In this paper, we adopted the Gaussian process model to estimate the received signal strength based on some samples. Then we used the inherent maximum Euclidean error of fingerprint vectors to compute the optimal cell size. The experimental results show the availability of Gaussian processes and the efficiency of optimal cell size.

2. Performance Analysis of Different Sampling Cell Sizes

During the fingerprint positioning, the interested area is first divided into some equal cells, where the RSSs from WiFi access points (APs) are sampled to construct the fingerprint database. Cell size affects the fingerprint database scale and localization performance. To study the impact of the sampling cell size on the localization performance, we conducted three experiments where the cell sizes are set to 1 m × 1 m, 2 m × 2 m, and 3 m × 3 m, respectively, in a 30 m × 24 m office room with 8 deployed APs. Obviously, the workload is increased as the cell size decreases.

2.1. Methodology

After dividing the interested area into small cells, we need to sample the RSSs of APs in each cell. Assume the WiFi fingerprint RSS values at location $x_i$ are denoted by $(r_{\mathrm{1}}^i,r_{\mathrm{2}}^i,\dots ,r_m^i)$ in which $r_m^i$ is the RSS value collected from the mth AP. When the user has to be localized, the similarity between the user's fingerprint and the fingerprints in the database is used as the localization metric. Generally, the Euclidean distance is used as the similarity of fingerprint vectors which is represented as follows:

$$\begin{array}{cc}& E_{ij}=\sqrt{{\displaystyle \sum }_{k=\mathrm{1}}^m‍{\left[\left(r_k^i-r_k^j\right)\right]}^{\mathrm{2}}},\end{array}$$

(1)

where the $E_{ij}$ represents the Euclidean distance between fingerprint vectors in locations $x_i$ and $x_j$ .

In the localization process, the K-nearest neighbors (KNN) are selected to estimate the user's location; for example, the centroid of the K-nearest neighbors is regarded as the user's current location. In the above three experiments, we adopt the KNN method.

In various positioning applications, the mobile phone has grown up to be a primary localization facility. We use GS1011 WiFi module from American Gainspan company as the test platform. This is because GS1011 module has a low-power property which can support a long time test. Additionally, to avoid the existing obstacles such as the office tables and chairs in the test room, we just experimented in the corridor cells to sample the fingerprints. According to the above dividing results, 120, 60, and 40 sampling sites are generated, respectively. After creating the fingerprint database, we select 60 random locations to evaluate the localization performance, where some locations may be far away from the sampling sites. As shown in Figure 1, we can find the 2 m × 2 m scenario has the comparable localization accuracy with 1 m × 1 m's. But when the sampling cell size is 3 m × 3 m, the localization performance declines dramatically. In other words, the localization accuracy has not always been improved with subdividing of sampling cell.

Figure 1

The localization performance of three tests.

2.2. Root Cause Analysis

To pursue the cause of above experimental results, we designed another test for WiFi signal attenuation with 4 m, 8 m, and 12 m distance away from APs. In Figure 2, the received signal strength is reducing with the distance increasing, while the signal variation is augmenting as well. This indicates the RSSs measured in the same sampling cell have a certain error. This is because complex indoor environment will bring about shadowing and multipath of radio signals. Therefore, during the KNN matching, the Euclidean distance between fingerprint vectors has some fluctuation due to the existing of RSS measurement errors. Smaller sampling cell size will lead to more influence from the Euclidean distance fluctuation. Therefore, we have to find the balance between the RSS measurement error and the sampling cell size.

Figure 2

The signal strength changes with distance.

3. Sampling Cell Size Optimization

In order to find the balance between the RSS measurement error and the sampling cell size, we defined the Euclidean distance of fingerprint vectors between sampling cells as fingerprint granularity. The fingerprint granularity represents the fuzzy degree of two sampling fingerprints. The bigger fuzzy degree indicates a higher similarity of the fingerprints. Meanwhile, the RSS measurement error also affects the fingerprint Euclidean distance. For example, supposing the RSS measurement error follows normal distributions with zero mean and ɛ error variance, then the fingerprints in the same sampling cell have an inherent maximum Euclidean error as follows:

$$\begin{array}{cc}& e_{\max }=\sqrt{{\displaystyle \sum }_{i=\mathrm{1}}^m‍{\left[\left(r_i+\varepsilon \right)-\left(r_i-\varepsilon \right)\right]}^{\mathrm{2}}}=\mathrm{2}\varepsilon \sqrt{m},\end{array}$$

(2)

where m represents the number of APs. In addition, according to the results in Figure 2, the value of ɛ will be changing with the distance away from APs. When the fuzzy degree of any two adjacent sampling cell fingerprints is over the maximum Euclidean error $e_{\max }$ , the fingerprint positioning algorithm can not distinguish two adjacent sampling sites. With the further reduction of the sampling cell size, the localization performance will not be clearly improved. This is the critical point that the performance is improved through reducing the optimal sampling cell size.

However, we can not compute the fingerprint granularity between any two adjacent sampling cells before the site survey. Meanwhile, the survey of an interesting area first needs to divide the area into the same cells. So the sampling cell size needs to be obtained in advance. This becomes a classic chicken-and-egg problem. To solve this difficulty, the existing techniques mostly assume knowledge of the APs locations and then adopt the signal propagation model to estimate each cell signal strength based on the distance from the APs [8, 9]. But the estimated value has lots of inaccuracy due to the ambient interferences. In this paper, we introduce the Gaussian processes (GPs) for modeling signal strength measurements to address these limitations. Based on fewer precalibration data, we can use Gaussian processes to generate a fingerprint database corresponding to all cells. In the following, we will show how Gaussian processes work on signal strength measurements.

3.1. Preliminaries

GPs can be derived in the function-space ways described in [10]. Let $D=(x_{\mathrm{1}},y_{\mathrm{1}}),(x_{\mathrm{2}},y_{\mathrm{2}}),\dots ,(x_n,y_n)$ be a set of samples at all cells with a noisy process. n is the number of cells. Consider

$$\begin{array}{cc}& y_i=f\left(x_i\right)+ϵ,\end{array}$$

(3)

where $y_i$ represents a fingerprint vector at location $x_i$ which is an input sample and the fingerprint vector $y_i$ is a target value. ϵ is zero mean, additive Gaussian noise with known variance ${\sigma }_m^{\mathrm{2}}$ . For notational convenience, we aggregate the n input value $x_i$ into a matrix X with n row and d column, where d is the coordinate dimensions, and target values $y_i$ into the vector denoted Y.

GPs use precalibration data as the input values to estimate posterior distribution of fingerprint vectors through the functions f. But a key idea underlying GPs is the requirement that the function values at different cells are correlated, where the covariance between two functions $f(x_p)$ and $f(x_q)$ depends on the input values, $x_p$ and $x_q$ . The dependency can be specified via an arbitrary covariance function or kernel $k(x_p,x_q)$ . The Gaussian kernel is widely used as a choice of kernel function as follows:

$$\begin{array}{cc}& k\left(x_p,x_q\right)={\sigma }_f^{\mathrm{2}}\exp \left(-\frac{\mathrm{1}}{\mathrm{2}{l}^{\mathrm{2}}}{\left|x_p-x_q\right|}^{\mathrm{2}}\right),\end{array}$$

(4)

where $k(x_p,x_q)$ represents covariance between two functions $f(x_p)$ and $f(x_q)$ . The ${\sigma }_f^{\mathrm{2}}$ is the signal variance which is different from the signal error variance ɛ. l is a length scale that describes how strongly the dropping of the correlation between input values. These parameters control the smoothness of the functions estimated by GPs. Seen from (4), the larger distance between two cells will lead to the lower covariance value.

During this Gaussian processes model, we do not consider the specific function value. Conversely we just focus on the covariance between arbitrarily two functions. So it is necessary to consider the corresponding observation noise covariance. The observation noise covariance between both cells can be described as follows:

$$\begin{array}{cc}& \mathrm{cov}\left(y_p,y_q\right)=k\left(x_p,x_q\right)+{\sigma }_n^{\mathrm{2}}{\delta }_{pq},\end{array}$$

(5)

where ${\sigma }_n^{\mathrm{2}}$ is the Gaussian observation noise. When the p and q are the same cell, the ${\delta }_{pq}$ is one and zero otherwise. For applying to the entire input values X, the above covariance can be further modified to a general formulation. Consider

$$\begin{array}{cc}& \mathrm{cov}\left(Y\right)=K+{\sigma }_n^{\mathrm{2}}I.\end{array}$$

(6)

Here, K is the $n\times n$ covariance matrix of the input values X. For example, $K(p,q)=k(x_p,x_q)$ .

3.2. Optimal Sampling Cell Design

Based on the input values X and corresponding observation Y, we can construct the above covariance. That is, the calibration data Y is jointly Gaussian with $Y~\mathcal{N}(\mathrm{0},K+{\sigma }_n^{\mathrm{2}}I)$ . Here, we can predict the function value at an arbitrary cell $x_{*}$ , conditioned on the calibration data $X,Y$ . Known from (4), the posterior over function values are Gaussian with mean ${\mu }_{x_{*}}$ at point $x_{*}$ [11]:

$$\begin{array}{cc}& {\mu }_{x_{*}}=k_{*}^T{\left(K+{\sigma }_n^{\mathrm{2}}I\right)}^{-\mathrm{1}}Y,\end{array}$$

(7)

where $k_{*}$ is the $n\times \mathrm{1}$ vector of covariances between $x_{*}$ and all n input values X, and K is the covariance matrix of X. We can find that (7) shows a linear combination of the calibration values Y. During the signal strength modeling, the input values X represent the cell locations, and target value Y corresponds to the fingerprint vector. So the above mean ${\mu }_{x_{*}}$ is the signal strength fingerprint vector at location $x_{*}$ . Then the Euclidean distance of arbitrary two adjacent cells corresponding to fingerprint vector can be represented as shown below:

$$\begin{array}{l}{\mu }_{x_i}-{\mu }_{x_j}=k_{x_i}^T{\left(K+{\sigma }_n^{\mathrm{2}}I\right)}^{-\mathrm{1}}Y-k_{x_j}^T{\left(K+{\sigma }_n^{\mathrm{2}}I\right)}^{-\mathrm{1}}Y\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}={\left(k_{x_i}-k_{x_j}\right)}^T{\left(K+{\sigma }_n^{\mathrm{2}}I\right)}^{-\mathrm{1}}Y\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\ge \mathrm{2}\varepsilon \sqrt{m},\end{array}$$

(8)

where the $k_{x_i}-k_{x_j}$ is the weight of each observation y constructing Euclidean distance of fingerprint vector between locations $x_i$ and $x_j$ . When the above Euclidean distance is less than the maximum Euclidean error $\mathrm{2}\varepsilon \sqrt{m}$ , the two adjacent cells will not be distinguished by the fingerprint positioning algorithm. Meanwhile, the $k_{x_i}-k_{x_j}$ can be further expanded as follows:

$$\begin{array}{l}{W}_{ij}=k_{x_i}-k_{x_j}\\ \hspace{1em}\hspace{0.17em}=k(x_i,x_{\mathrm{1}})-k(x_j,x_{\mathrm{1}}),\dots ,k\left(x_i,x_k\right)-k\left(x_j,x_k\right),\end{array}$$

(9)

where k is $\mathrm{1,2},\dots ,n$ and n is the number of inputs X. $k(x_i,x_k)$ is also denoted by physical distance between $x_i$ and $x_k$ which is a function of cell side length. According to (8), we can compute a bound value of cell side length, that is, the optimal cell size to obtain better localization performance and less sampling effort. Before computing the optimal cell size, we firstly learn of these parameters based on the calibration data. The parameters include ${\sigma }_n^{\mathrm{2}}$ , l, ${\sigma }_f^{\mathrm{2}}$ denoted by the hyperparameters, which can be estimated by maximizing the log likelihood of the fingerprint vector y. Since the calibration data Y is jointly Gaussian, we can maximize its log likelihood using conjugate gradient descent (LBFGS) [12].

4. Experiments Evaluation

In the experiments, we evaluate the performance of GPs and the optimal sampling cell size using WiFi fingerprint data in our lab office.

4.1. Setup of Experiments

Our test scenario is an open office room with 30 m × 24 m, which consists of the workstations, corridors, and cement columns. To collect calibration data, we still select GS1011 WiFi module as the measurement platform. When the surrounding APs send beacon packets, the GS1011 model can receive signals and measure the received signal strengths. The calibration data were collected by manual mobile survey with handheld GS1011 model. The number of APs is still 8. We sampled 72 data records at 72 cells in the test room. At every cell, we sampled 20 times to compute the mean of RSSs without considering the body interference. Additionally, we randomly selected some data records to estimate the hyperparameters of the GPs. Then we used the estimated hyperparameters to construct the GPs. According to the constructed GPs, we computed the optimal sampling cell size through (8).

4.2. Experimental Results

To validate the feasibility of GPs model, we selected 15 sampled records to compute hyperparameters and construct GPs. Then another 15 cells were selected to estimate the RSS fingerprint vectors according to the newly constructed GPs. On one AP, the measurement RSSs and estimated values at above 15 cells were shown in Figure 3. The box chart represents the measurement sample and the black rectangle represents the estimated value by GPs model. From this figure, we can find the measurement RSS values have a bigger variance when the RSS values become weak. It is consistent with our results in Figure 2. Meanwhile, the estimated value also deviates from measurement mean with the fading of signal strength. This indicates the GPs model is suitable for estimating the stable data. On the other hand, the experimental results also indicate that the GPs model can be implemented to signal strength modeling.

Figure 3

The measurement RSSs and estimated value.

Then we changed the number of sample records to recompute hyperparameters and GPs model. The relation between sample numbers and estimated errors was shown in Figure 4. We selected 5, 10, 15, 20, 25, and 30 samples to test the estimated errors in two random cells. The means of measured RSSs in two cells are $-\mathrm{49}\hspace{0.17em}$ db and $-\mathrm{72}\hspace{0.17em}$ db, respectively. From the experimental results, we can find the estimated errors will reduce with the increasing of sample numbers. Meanwhile, for the same samples, the lower measured RSSs lead to a bigger estimated error. This is because the lower RSSs have a bigger variance.

Figure 4

The different sample numbers.

The AP number is another main factor to affect the estimated errors from GPs model. We selected 2, 4, and 8 of the test APs to estimate the RSS corresponding to the 10, 20, and 30 samples, respectively. The results were shown in Figure 5. The increasing of AP numbers will lead to the enlarging of the estimated mean errors about RSS. This is because more APs will accumulate the estimated errors. Besides, the samples also affect the estimated accuracy of GPs model corresponding to Figure 4.

Figure 5

The different APs and sample numbers.

However, less APs are likewise no better, because less APs will reduce the dimensions of fingerprint vector so as to increase the fingerprint fuzziness. We design another test to verify the APs affection for two adjacent sampling cell fingerprints. 30 adjacent fingerprints with 2 m × 2 m cell size are selected to compute the Euclidean distance between each other. The computed results of 2, 4, 6, and 8 APs are shown in Figure 6. More APs will increase the mean of Euclidean distance. Then the fingerprint fuzziness will be reduced.

Figure 6

The APs affection for fingerprint fuzziness.

According to (8), we can compute the optimal cell size from GPs model based on some samples. In our experiments, we adopted the 30 samples and the optimal cell size is computed as 1.8 m * 1.8 m. Then we compared the performance of cell size 1.8 m * 1.8 m with the above three scenarios 1 m * 1 m, 2 m * 2 m, and 3 m * 3 m as shown in Figure 7. We can find that the positioning performance of 1.8 m * 1.8 m falls in between 1 m * 1 m and 2 m * 2 m. But the interest area is difficult to be divided into 1.8 m * 1.8 m cells. For survey convenience, we usually select the 2 m * 2 m cell to sample the received signal strengths as the fingerprint vectors.

Figure 7

The positioning performance using optimal cell size.

5. Conclusions

In this paper, we first analyze the influence of the sampling cell size for fingerprint positioning performances and find the root cause of the similarity between 1 m × 1 m and 2 m × 2 m scenarios. In order to achieve the optimal sampling cell size, we adopted the Gaussian process model to estimate the received signal strengths based on a few samples. Then we used the inherent maximum Euclidean error of fingerprint vectors to compute the optimal cell size. The experiment results also show the availability of Gaussian processes and the efficiency of optimal cell size.