Dealing with Insufficient Location Fingerprints in Wi-Fi Based Indoor Location Fingerprinting

Abstract

The development of the Internet of Things has accelerated research in the indoor location fingerprinting technique, which provides value-added localization services for existing WLAN infrastructures without the need for any specialized hardware. The deployment of a fingerprinting based localization system requires an extremely large amount of measurements on received signal strength information to generate a location fingerprint database. Nonetheless, this requirement can rarely be satisfied in most indoor environments. In this paper, we target one but common situation when the collected measurements on received signal strength information are insufficient, and show limitations of existing location fingerprinting methods in dealing with inadequate location fingerprints. We also introduce a novel method to reduce noise in measuring the received signal strength based on the maximum likelihood estimation, and compute locations from inadequate location fingerprints by using the stochastic gradient descent algorithm. Our experiment results show that our proposed method can achieve better localization performance even when only a small quantity of RSS measurements is available. Especially when the number of observations at each location is small, our proposed method has evident superiority in localization accuracy.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

With the development of the Internet of Things (IoT) and the popularization of mobile devices such as smart phones, a variety of mobile applications have changed people’s lifestyles tremendously. These applications enable users to access a plenty of services at any time in any place and often use their location information in order to provide them with personalized experiences.

The global positioning system (GPS) can achieve meter-level accuracy in outdoor environments. However, GPS works poorly inside buildings due to the signal attenuation caused by roofs, walls, and other objects. During the past decades, a variety of indoor positioning systems (IPS) have been introduced. Since wireless information access is now widely available, many of these approaches tap into wireless signals for estimating locations.

In the last couple of years, the location fingerprinting (LF) technique using existing wireless local area network (WLAN) infrastructure has been suggested for indoor areas. Location fingerprinting estimates the target location by matching online measurements of received signal strength (RSS) with the closest offline features (i.e., the location fingerprints) composed of location coordinates and respective RSS values. It is relatively simple to deploy, compared to the other wireless indoor positioning techniques using Bluetooth beacons [1] or RFID tags [2], which can achieve higher location accuracy.

To deploy a traditional LF-based indoor positioning system, the positioning server should generate the location fingerprints by performing site survey of the RSS information from multiple access points (APs). With these fingerprints, the positioning server is able to localize a mobile device based on its RSS measurements. The site survey is extremely time-consuming and labor-intensive, which raises the cost of initiating an LP-based localization service. Furthermore, the positioning server should periodically reperform this site survey to update the fingerprints so as to control errors in the changeable Wi-Fi environment, which also raises the cost of maintaining the localization service.

Benefiting from cloud computing and big data techniques, the LF system may also be deployed without an offline site survey. Following [3], much work has been done to enable the collection of fingerprints based on crowdsourced solutions. In these solutions, users are required to continuously upload their RSS measurements to the positioning server as the training data. In the meanwhile, an additional incentive mechanism is required to guarantee the number of volunteering users.

In the situation when the crowdsourced fingerprints are insufficient to deploy an LF system, the offline site survey is still required to refine the fingerprint database. Suppose an indoor environment as an example; there are some locations which have never been occupied by any volunteering users. Thus, no RSS fingerprints of these locations are generated. To ensure the functionality of the location service, the service provider may still need to perform an offline site survey at these locations.

Regardless of whether the RSS measurements are collected via a traditional site survey or a crowdsourced approach, it is a widely existing fact that sufficient RSS measurements cannot be collected (periodically for maintaining fingerprints) in most indoor environments. Ways of collecting RSS measurements are not the focus of this paper. We are interested in the following several issues which may be interesting and useful but, however, rarely studied by existing researches:

(i)

At a given location, how many RSS measurements are required to generate an accurate online location or offline fingerprint?

(ii)

Most importantly, when the collected RSS measurements are insufficient to generate an accurate location fingerprint database, how do we perform localization in this situation?

Although the answers to these questions may vary in different indoor environments, the readers should take into account the instructive significance of deeply analyzing these issues in a certain indoor application scenario. In this paper, we propose a novel localization method which reduces noise in measuring the received signal strength based on the maximum likelihood estimation and estimates locations from inadequate location fingerprints by using the stochastic gradient descent algorithm. We also use an open dataset to evaluate our proposed method by comparing it with the most commonly used location fingerprinting methods and investigate the number of RSS measurements required to deploy an LF system. The results show that our proposed method can achieve better localization accuracy when only a small quantity of RSS measurements is available.

This paper is organized as follows. Section 2 surveys existing location fingerprinting methods. Section 3 introduces two major problems that arise from insufficient RSS measurements in deploying a location fingerprinting system. Section 4 describes our basic idea in solving these problems, and the detailed solution is presented in Section 5. We evaluate our proposed method in Section 6. At last, we conclude this paper in Section 7.

2. Related Work

To reduce the cost of deploying an indoor localization system, many researches leverage existing Wi-Fi infrastructures and introduce location fingerprinting based on the RSS measurements of the Wi-Fi signals. The deployment of location fingerprinting systems is often divided into two phases: an offline phase, in which a site survey of the RSS from multiple APs is collected, and an online phase, in which a location can be computed based on the currently observed RSS measurements by using a matching algorithm.

2.1. Collecting Online and Offline RSS Measurements

At least four key factors can decide the accuracy of an LF technique.

The first is the density of the offline observing locations where RSS measurements are collected to generate fingerprints: a higher accuracy in LF requires higher intensity of the observing locations, which leads to heavier workload in collecting and updating the fingerprints.

The second is the quantity of available information, including the number of RSS observations used to generate fingerprints and the number of dimensions (observed APs) in each RSS observation. Existing approaches use channel state information [4, 5] or environmental information such as light [6], sound [7, 8], temperature, humidity, magnetic, or pressure data to improve location accuracy. Both of these factors deal with the sufficiency of RSS measurements.

2.2. Reducing Noises and Generating Fingerprints

The third key factor deciding the accuracy of localization is the algorithm used to reduce noises. It can be used in both the offline and the online phases.

The most common way in denoising RSS measurements is to observe multiple times at the same location and average multiple observations so that noises can be reduced. With multiple observations at the same location, one can also make sure that all observable APs are observed. The tricky part is how to deal with situations when some APs are missed from some (but not all) observations. A common but also naive approach is to simply set the RSS to unobserved APs to $-\mathrm{100}\hspace{0.17em}\mathrm{d}\mathrm{B}\mathrm{m}$. Some other approaches assume that only APs far away from the observing location can be missed (we will show that this assumption is wrong) and make a threshold (e.g., $-\mathrm{80}\hspace{0.17em}\mathrm{d}\mathrm{B}\mathrm{m}$) to consider only RSS measurements larger than this threshold. There are also approaches that use a complex algorithm to reduce noises [9–11]; however, most of these approaches require a large quantity of RSS observations at the same location. Some approaches use a lightweight machine learning method to generate limited location fingerprints [12], or variations of fingerprints such as RSS differences between every pair of APs [13], or do not need to generate location fingerprints [14]; however, they suffer from relatively low localization accuracy.

By only reducing the measurement errors, it is still difficult to achieve a high localization accuracy. With sufficient RSS measurements, localization accuracy is mainly decided by the fourth factor.

2.3. Matching Algorithm

The fourth key factor deciding the accuracy of localization is the matching algorithm used in the online phase, which outputs the final location by comparing the online RSS observations with the location fingerprints. By now, most LF systems mainly use, but are not limited to, the following types of matching algorithms.

2.3.1. Probabilistic Method

The probabilistic method treats the matching problem as a classical classification problem. It computes the probabilities that the online observing location belongs to every offline candidate location and finally performs matching from the candidate location based on the probabilities. The result of the localization can be either the candidate location with the highest probability or an averaged value calculated from every candidate location weighted by its corresponding probability.

2.3.2. $k$-Nearest Neighbors

Based on the context information collected at the observing location, $k$ nearest neighbors are defined as the $k$ offline candidate locations which have the most similar context information. The locations of the $k$-nearest neighbors (KNN) contribute to the result of the localization by direct averaging or weighted averaging in weighted KNN (WKNN). It must be taken into consideration that the context information can be of various kinds (e.g., wireless signal strength, brightness, temperature, and humidity), and the metric quantifying the distance between the vectors of context information should be carefully designed. In the situation where only wireless signal strength is used, the Euclidean distance in the wireless signal strength space is often used as the metric. Locations which have smaller distance with the observing location are the $k$-nearest neighbors, and the distances can be used to compute the weights in WKNN.

2.3.3. Other Machine Learning Methods

Existing machine learning methods can be used in matching the online location to those offline locations. A neural network can be created in the offline phase, which takes as input the context information collected at the observing online location, takes as object the location of the fingerprint, learns the weight matrix for each dimension of the context information, and finally outputs the localization result. The support vector machine can be used in small sampled, nonlinear, and high dimensional pattern recognition. The matching and localization can be accomplished by treating the location fingerprint information of candidate locations as support vectors and by performing classification and regression analysis on the context information collected at the target observing location. Other machine learning methods may also be used in location fingerprinting.

2.4. Localization without Site Survey

The site survey in the offline phase can be extremely time-consuming and labor-intensive. Recently, many researches introduced crowdsourcing based systems [3, 15–20] which require the users to continuously observe their RSS measurements and upload the data to the positioning server. These approaches do not require the site survey to be performed, and they do not require the map of the floorplan. However, additional incentive mechanisms are required to attract enough participation, since the one who uploads his observed RSS measurements cannot obtain any benefits like positioning accuracy but will definitely take the privacy risk and the transmission cost. In our previous work [21], we propose a novel indoor navigation mechanism for shopping mall environments, which requires only few shop owners as RSS information contributors. Compared with our previous work, this work improves the method by adjusting it to more general indoor location fingerprinting scenarios and also evaluates our proposed method by comparing it with existing location fingerprinting techniques. Furthermore, we do not focus on ways of collecting RSS measurements. We are only interested in the quantity of the RSS measurements, regardless of whether they are collected via a traditional site survey or a crowdsourced approach.

3. Problem Definition

There are so many situations in our real life when we are asking or being asked a question like “How can I go to?” or “Where is?” For instance, a consumer may want to find a certain shop in a shopping mall, or a patient may want to find the correct consulting room in a hospital. Nowadays, most indoor environments like the aforementioned shopping malls or hospitals always have WLAN infrastructures; however, localization in these environments is still unavailable. The key reason deals with the cost in building and maintaining the fingerprint database. Existing techniques highly rely on an assumption that sufficient RSS measurements can be collected, either by a site survey, which is extremely time-consuming and labor-intensive, or by a crowdsourced approach, which requires too many collaborative contributors.

Here is an example showing how much time one should spend in collecting “sufficient” RSS measurements. Consider a very tiny shopping mall with a total area of only 5,000 m² that includes all the floors. The offline observations are collected every 1 m², and at every observing location, at least $\mathrm{10}$ observations have to be collected. After each observation, a time interval of, for example, about $\mathrm{3}$ seconds is spent so as to obtain a next observation. Suppose one spends no time moving from one observing location to another, and the observations can never fail. We can compute that he should spend at least 150,000 seconds (i.e., $\mathrm{41.67}$ hours) to perform a site survey. If the fingerprint database needs to be updated every day, then we need at least 5 long-term employees, each of whom works for 8 hours a day with no weekend and must not rest during working. Remember that that is only for tiny shopping malls. For large shopping malls, the workload can be incredibly heavy. Perhaps this is the reason why building owners always choose to deploy infrastructures to provide localization, not the “infrastructure-free” location fingerprinting.

So, our problem is, when the RSS measurements collected are not sufficient, how do we perform localization? At least the following two problems should be addressed.

3.1. Measurement Noises

One problem arising from insufficient RSS measurements deals with noises in the RSS measurements. RSS values can change greatly in different observations even at the same location to the same AP, as shown in Figure 1. In this example, the standard deviation is $\mathrm{13.66}$. Without denoising the RSS measurements, no accurate fingerprints can be generated and no accurate localization can be performed.

[figure omitted; refer to PDF]

One may think of an intuitive solution by averaging different observations at neighboring locations. This idea is not always correct as illustrated in Figure 2. Suppose three observing locations $L_{\mathrm{1}}$, $L_{\mathrm{2}}$, and $L_{\mathrm{3}}$ are in a line, and $L_{\mathrm{2}}$ lies in between $L_{\mathrm{1}}$ and $L_{\mathrm{3}}$. The simple but incorrect solution denoises the observation at $L_{\mathrm{2}}$ by weighted-averaging the observations at $L_{\mathrm{1}}$ and $L_{\mathrm{3}}$, and the weights can be computed from the distances $d_{\mathrm{12}}$ and $d_{\mathrm{23}}$. However, this denoising method is not always correct (if not always incorrect), since it relies on a totally wrong hypothesis that the RSS to different locations in a 2D or 3D space can be modeled by a linear function. In Figure 2, suppose the AP is located closer to $L_{\mathrm{2}}$; we can find that the RSS to this AP observed at $L_{\mathrm{2}}$ should be larger than those observed at $L_{\mathrm{1}}$ and $L_{\mathrm{3}}$. So, the denoising method will definitely reduce the value of $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{2}}$.

[figure omitted; refer to PDF]

3.2. Missed APs

Another problem deals with dimensional mismatches between different RSS observations in the signal space. When the Wi-Fi scan operations are performed frequently, many APs can be missed in the RSS observations. As a result, even RSS observations from very nearby locations may observe different APs. Since the distance between different RSS observations is computed in a high dimensional signal space where each AP is a dimension, the missed APs will cause dimensional mismatches. If the RSS measurements are not sufficient, dimensional mismatches can always occur. The dimensional mismatches can cause localization failures and errors, and we call this problem the missed AP problem.

We use an open dataset to show how frequently an AP can be missed in an arbitrary observation. The dataset is the Mannheim/compass dataset [22] which contains Wi-Fi observations of different locations. Our experiments described in Section 6 are also based on this dataset. For a given RSS observation, the APs can be classified into the following three categories as shown in Figure 3:

(i)

Observed APs. Those are observed in the record. Reversely, the unobserved APs are those not observed in the record.

(ii)

Unobservable APs. Those cannot be observed at the observing location. An AP is unobservable if no records at this location ever observed this AP. The unobservable APs must be unobserved APs, but unobserved APs may be observable.

(iii)

Missed APs. Those are observable but unobserved in this record.

[figure omitted; refer to PDF]

The proportions of the observed APs, the unobservable APs, and the missed APs are shown in Figure 4. One interesting finding is that the probability of missing an AP is not obviously related to the averaged RSS value. According to this finding, it is not reasonable to treat RSS to a missed AP (i.e., an unobserved but observable AP) as $-\mathrm{100}\hspace{0.17em}\mathrm{d}\mathrm{B}\mathrm{m}$, since $-\mathrm{100}\hspace{0.17em}\mathrm{d}\mathrm{B}\mathrm{m}$ means the AP is unobservable.

[figure omitted; refer to PDF]

4. Basic Idea

In the following, we present how our proposed method deals with the missed APs and the measurement noises.

4.1. Dealing with Missed APs

Consider an indoor environment as illustrated in Figure 5. There are 4 APs denoted as $\mathrm{A}{\mathrm{P}}_{\mathrm{1}}$, $\mathrm{A}{\mathrm{P}}_{\mathrm{2}}$, $\mathrm{A}{\mathrm{P}}_{\mathrm{3}}$, and $\mathrm{A}{\mathrm{P}}_{\mathrm{4}}$ and 4 observing locations denoted as $L_{\mathrm{1}}$, $L_{\mathrm{2}}$, $L_{\mathrm{3}}$, and $L_{\mathrm{4}}$. At each observing location, we perform an RSS observation; and within each observation, a specific AP is missed. We can further suppose that the location of an arbitrary observation is unknown and needs to be localized. In this situation, we find that it is difficult to perform traditional localization, since these observations observe different APs. And if we discard the dimensions of the missed APs to avoid dimensional mismatches, we will find that no dimensions are left in the signal space. As a result, none of these observations can be used for traditional localization techniques.

[figure omitted; refer to PDF]

Our idea to solve the missed AP problem is straightforward. The observations with missed APs really cannot be directly used for location fingerprinting; however, the information within the observations is valuable, since it tells the relationship between the relative locations of all APs and observations. Back to our example in Figure 5, $\mathrm{A}{\mathrm{P}}_{\mathrm{3}}$ is missed in the observation at $L_{\mathrm{2}}$. Our idea is to compute $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{3}}$ for $L_{\mathrm{2}}$ based on the values of other RSS measurements at other locations. The RSS to all other missed APs can also be computed in a similar way. If we can compute a theoretical RSS value for each of the missed APs in all observations, the dimensional mismatches can be avoided and localization can be performed. The detailed algorithm is presented in Section 5.

4.2. Reducing Measurement Noises

Our idea in denoising the RSS measurements is to some extent related to our solution to the missed AP problem. As shown in Figure 5, after we compute $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{4}}$ for $L_{\mathrm{1}}$, $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{3}}$ for $L_{\mathrm{2}}$, $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{2}}$ for $L_{\mathrm{3}}$, and $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{1}}$ for $L_{\mathrm{4}}$, finally we have 4 observations each of which contains RSS measurements to all the 4 APs. Now, the localization can be performed by matching the RSS observation distance in the 4D signal space to the locational distance in the 2D physical space. However, the output of this localization process is far from accurate, since every RSS measurement in every observation is noisy. Without sufficient RSS measurements at the same location, traditional localization techniques cannot reduce the noises effectively.

Again, we make use of all RSS measurements to compute the relationship between the relative locations of all APs and observations. Back to our example in Figure 5, this relationship can be primarily computed based on the primary localization result. With this relationship, $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{1}}$ for $L_{\mathrm{3}}$ and $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{1}}$ for $L_{\mathrm{4}}$ can be used to modify $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{1}}$ for $L_{\mathrm{1}}$, and every other RSS measurement can also be denoised by carefully computing the weights of the measurements to the same AP, no matter at the same location or other locations. Then, the newly denoised RSS measurements can be used to improve the accuracy of the previous localization and thus will output more accurate locations. Our proposed method iterates denoising the RSS measurements and refining the locations until convergence. The detailed algorithm is presented in Section 5.

5. Designing Details

We now introduce our proposed localization method in detail. In the Notations, we summarize the main notations introduced throughout this article.

Suppose there are $N$ APs within an area, denoted as $$\begin{array}{}\text{(1)}& \mathrm{A}\mathrm{P}=\left\{\mathrm{A}{\mathrm{P}}_{\mathrm{1}},\mathrm{A}{\mathrm{P}}_{\mathrm{2}},\dots ,\mathrm{A}{\mathrm{P}}_N\right\};\end{array}$$the $\mathrm{R}\mathrm{S}\mathrm{S}$ information collected at one location can be described as an $N$-dimensional vector: $$\begin{array}{}\text{(2)}& \mathrm{R}\mathrm{S}\mathrm{S}=⟨\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{A}{\mathrm{P}}_{\mathrm{1}}},\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{A}{\mathrm{P}}_{\mathrm{2}}},\dots ,\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{A}{\mathrm{P}}_N}⟩,\end{array}$$where each dimension corresponds to the RSS information of an AP. If an AP is not observed, the RSS value is $-\infty$ and is marked as $\mathrm{0}$.

For situations when the RSS observations are insufficient, we suppose the location fingerprinting algorithm takes as input $M$ offline RSS observations at different locations and one online RSS observation and outputs the online observing location. The RSS information can be collected as a sparse matrix, denoted as $$\begin{array}{}\text{(3)}& S=\left[\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{1}},\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{2}},\dots ,\mathrm{R}\mathrm{S}{\mathrm{S}}_M,\mathrm{R}\mathrm{S}{\mathrm{S}}_{M+\mathrm{1}}\right].\end{array}$$We denoise RSS information in this sparse matrix based on the following two assumptions:

(i)

The value of RSS (in dBm) follows the Gaussian distribution: $$\begin{array}{}\text{(4)}& \mathrm{R}\mathrm{S}\mathrm{S}~\mathrm{G}\mathrm{a}\mathrm{u}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{a}\mathrm{n}\left(\widetilde{\mathrm{R}\mathrm{S}\mathrm{S}},{\sigma }^{\mathrm{2}}\right).\end{array}$$

(ii)

The signal propagation path loss varies exponentially with distance: $$\begin{array}{}\text{(5)}& \mathrm{P}\mathrm{L}=\mathrm{P}{\mathrm{L}}_{\mathrm{0}}+\mathrm{10}n\hspace{0.17em}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{10}}\left(\frac{d}{d_{\mathrm{0}}}\right)+X_g,\end{array}$$

 

where $\mathrm{P}{\mathrm{L}}_{\mathrm{0}}$ is the path loss at unit distance $d_{\mathrm{0}}$, $n$ is the propagation path loss exponent, and $X_g$ is a Gaussian random variable with $\mathrm{0}$ mean.

Let $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}$ denote the observed value of $\mathrm{R}\mathrm{S}\mathrm{S}$ of the $j$th AP at $d_{\mathrm{0}}=\mathrm{1}\hspace{0.17em}\mathrm{m}$; we can obtain the relationship between the value of the RSS and the distance by $$\begin{array}{}\text{(6)}& \mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}=-\mathrm{10}n\lg d_{i,j}+\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}.\end{array}$$Moreover, the relationship among the location of the $i$th observing location ($L_i$), the location of the $j$th AP ($A_j$), and the distance between $L_i$ and $A_j$ can be formulated as $$\begin{array}{}\text{(7)}& d_{i,j}={‖L_i-A_j‖}_{\mathrm{2}}.\end{array}$$

The above assumptions are also made in our previous work in [21] and many other approaches. With these assumptions, we can compute the RSS values for the missed APs and fill in the blank items in the sparse matrix of RSS by using the maximum likelihood estimate with probability density function: $$\begin{array}{}\text{(8)}& f_{\mathrm{R}\mathrm{S}\mathrm{S}}\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}\right)-\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi \sigma }}\exp \left\{-\frac{{\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-{\widetilde{\mathrm{R}\mathrm{S}\mathrm{S}}}_{i,j}\right)}^{\mathrm{2}}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right\}.\end{array}$$Under the independent and identical distribution hypothesis on $L$, $A$, and $\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0}}$, the maximum probability of RSS is observed as $$\begin{array}{}\text{(9)}& p\left(L,A,\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0}}\mid \mathrm{R}\mathrm{S}\mathrm{S}\right)={\displaystyle \prod }_{i,j}{f}_{\mathrm{R}\mathrm{S}\mathrm{S}}\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}\right).\end{array}$$This is equivalent to minimizing$$\begin{array}{}\text{(10)}& F\left(S\parallel \tilde{S}\right)={\displaystyle \sum }_{i,j}{\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-{\widetilde{\mathrm{R}\mathrm{S}\mathrm{S}}}_{i,j}\right)}^{\mathrm{2}}\text{(11)}& ={\displaystyle \sum }_{i,j}{\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}+\mathrm{10}n\lg {‖L_i-A_j‖}_{\mathrm{2}}\right)}^{\mathrm{2}}.\end{array}$$

We define the estimation error as $$\begin{array}{}\text{(12)}& E_{i,j}=\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-{\widetilde{\mathrm{R}\mathrm{S}\mathrm{S}}}_{i,j}=\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}+\mathrm{10}n\lg {‖L_i-A_j‖}_2\right).\end{array}$$The process of fitting can be achieved by using the stochastic gradient descent method: $$\begin{array}{c}\text{(13)}& L_i≔L_i-\alpha ·\frac{\partial F}{\partial L}=L_i-\mathrm{2}\alpha ·\frac{\mathrm{10}n·\left(L_i-A_j\right)E_{i,j}}{\ln \mathrm{10}·{‖L_i-A_j‖}_{\mathrm{2}}},A_j≔A_j-\alpha ·\frac{\partial F}{\partial A}=A_j+\mathrm{2}\alpha ·\frac{\mathrm{10}n·\left(L_i-A_j\right)E_{i,j}}{\ln \mathrm{10}·{‖L_i-A_j‖}_{\mathrm{2}}},\\ \mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}≔\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}-\alpha ·\frac{\partial F}{\partial \mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0}}}=\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}+\mathrm{2}\alpha E_{i,j},\end{array}$$where $\alpha$ is the length of step.

This fitting process is hoping to compute a large number of unknown data (i.e., the RSS values to the missed APs) from only a little amount of given data. As a result, the convergence of this fitting process is generally describing the random error or noise instead of the underlying relationship between the RSS and the location information. To address this problem, a typical solution is to use regularization, which modifies the objective function as $$\begin{array}{}\text{(14)}& \underset{L_i,A_j,\mathrm{RS}{\mathrm{S}}_{\mathrm{0},j}}{\min }{\displaystyle \sum }_{i,j}{\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}-\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}+\mathrm{10}\mathrm{n}\lg {‖L_i-A_j‖}_{\mathrm{2}}\right)}^{\mathrm{2}}+R\left(w\right),\end{array}$$where $w$ is the weight vector and $R\left(w\right)$ is the regularization term. Take $L\mathrm{2}$ regularization as an example; $R\left(w\right)$ can be defined as $$\begin{array}{}\text{(15)}& R\left(w\right)=\lambda ·\left[{‖L_i‖}^{\mathrm{2}}+{‖A_j‖}^{\mathrm{2}}+{\left(\mathrm{R}\mathrm{S}{\mathrm{S}}_{\mathrm{0},j}-{\stackrel{-}{\mathrm{R}\mathrm{S}\mathrm{S}}}_{\mathrm{0},j}\right)}^{\mathrm{2}}\right],\end{array}$$where $\lambda$ is a free parameter, which needs to be adjusted by methods like cross-validation. And in our experiment, we find that, for most APs, ${\stackrel{-}{\mathrm{R}\mathrm{S}\mathrm{S}}}_{\mathrm{0},j}=-\mathrm{36}\hspace{0.17em}\mathrm{d}\mathrm{b}\mathrm{m}$. It is worth noting that it is usually difficult to use the cross-validation method, so an early exit strategy can also be used.

6. Evaluation

In this section, we evaluate our proposed localization method and compare it with some most commonly used location fingerprinting methods.

6.1. Benchmark

In the following, we detail the benchmark used in our experiments.

6.1.1. Dataset

We use an open dataset, the Mannheim/compass dataset [22], to perform our experiments. It records traces of signal strength of 802.11 APs and contains data in both an offline training phase and an online positioning phase, in an area of about 35 meters in width and 60 meters in length. The offline fingerprinting data contains 14,300 measurement records for 130 locations (110 records each), and the online positioning data contains 5,060 measurement records for 46 locations (110 records each).

6.1.2. Compared Methods

We choose three most commonly used location fingerprinting methods for comparison. All the three methods generate the same location fingerprint database by simply averaging observations at the same location.

(i)

The weighted $K$-nearest neighbor (WKNN) method [23] is a deterministic method which computes the estimate location by weighted-averaging the fingerprint locations: $$\begin{array}{}\text{(16)}& \widehat{L_x}={\displaystyle \sum }_{i=\mathrm{1}}^M\frac{w_i}{{\sum }_{j=\mathrm{1}}^M{w}_j}{L}_i,\end{array}$$

 

where $w_i$ represents the weight of the fingerprint location $L_i$. It can be computed by $$\begin{array}{}\text{(17)}& w_i=\frac{\mathrm{1}}{{‖O_x-O_i‖}_{\mathrm{2}}}.\end{array}$$

 

Here, the Euclidean norm (2-norm) is used. WKNN keeps $K$ biggest weights and sets the others to zero.

(ii)

The $K$-nearest neighbor (KNN) method [24] is a simplified version of WKNN which sets the $K$ biggest weights to $\mathrm{1}/K$ and others to zero.

(iii)

The histogram method [25] is a probabilistic method, which computes the probability that an RSS observation $O_x$ can be observed at the location $L_x$ by using Bayes’ rule: $$\begin{array}{}\text{(18)}& p\left(L_x\mid O_x\right)=\frac{p\left(O_x\mid L_x\right)p\left(L_x\right)}{p\left(O_x\right)},\end{array}$$

 

where $p(O_x)$ is a normalized constant and $p(L_x)$ and $p(O_x\mid L_x)$ can be computed as follows: $$\begin{array}{c}\text{(19)}& p\left(L_x\right)=\frac{{\sum }_{i=\mathrm{1}}^M\chi B_i\left(L_x\right)}{{\sum }_{j=\mathrm{1}}^M\left|B_j\right|},p\left(O_x\mid L_x\right)={\displaystyle \sum }_{i=\mathrm{1}}^{M}p\left(O_x\mid i\right)\chi B_i\left(L_x\right),\end{array}$$

 

where $\left|B_i\right|$ is the volume of $B_i$ and $$\begin{array}{c}\text{(20)}& \chi B_i\left(x\right)=\left\{\begin{array}{cc}\mathrm{1},\hfill & x\in B_i\hfill \\ \mathrm{0},\hfill & x\notin B_i,\hfill \end{array}\right.p\left(O_x\mid i\right)\approx {\displaystyle \prod }_{j=\mathrm{1}}^N{H}_{v_{ij}}\left(O_{xj}-O_{ij}\right),\end{array}$$

 

where $v_i=O_x-O_i$ and $H_{v_{ij}}(L_x)$ is the normalized centralized histogram.

6.1.3. Experiment Settings

We use a program to randomly choose the RSS observations based on two parameters. $y$ represents the number of observations selected in each observing location (for both offline and online); $z$ represents the size of a cell where one offline observing location is selected (i.e., the volume of the observing location). For example, when $y=\mathrm{8}$ and $z=\mathrm{36}\times \mathrm{2.25}=\mathrm{81}$ m², this means that, for every $\mathrm{81}$ m² area, there should be no more or no less than one offline observing location, and at this location, 8 RSS observations are selected. An online observing location is then randomly selected, and again at this location, 8 RSS observations are selected. Using these online and offline data, the location is estimated by using each of the three comparing methods and also our proposed method. We let $y\in \{\mathrm{1,2},\mathrm{4,8},\mathrm{16,32,64}\}$ and $z\in \{\mathrm{1,4},\mathrm{9,16,25,36}\}\times \mathrm{2.25}\hspace{0.17em}$m² (the distance between two nearby blue dots in Figure 6 is $\mathrm{1.5}$ m in real world, so $\mathrm{2.25}\hspace{0.17em}$m² is the minimum value for $z$). The experiment is performed 100 times for each pair of $⟨y,z⟩$.

[figure omitted; refer to PDF]

6.1.4. Comparing Metrics

Two metrics are used for comparing the performance of different localization methods: the mean localization error and the mean squared localization error.

6.2. Results and Analysis

The results are shown in Figures 7 and 8. With different settings on $y$ and $z$, we illustrate the mean localization error in Figures 7(a)–7(f) and the mean squared localization error in Figures 8(a)–8(f), for all the compared localization methods.

[figures omitted; refer to PDF]

[figures omitted; refer to PDF]

It is worth noting that the experiment results provide a direct answer to the questions we listed in the Introduction. From Figure 7(a), we can see that KNN and WKNN can output accurate locations (i.e., the mean localization error is about 2 m) when we can observe at least 4 RSS measurements within an area of 2.5 m² in size. From Figure 7(b), we can see that 16 RSS measurements are required for a 10 m² area. This means that, on average, one should observe at least 1.6 RSS measurements per square meter to achieve accurate localization. This is the answer to the question “How many RSS measurements are required to compute an accurate location?” with our experiment settings.

The results also show that our proposed method may be an answer to the question “How do we locate accurately with insufficient RSS measurements?” We can see that, whatever the values of $y$ and $z$, our propose method achieves smaller mean localization errors and smaller mean squared localization errors, especially when $z$ (the number of observing locations) is relatively large and $y$ (the number of observations at each location) is relatively small. This is reasonable since traditional methods can denoise RSS measurements at the same location, so our proposed method does not have evident superiority with a large $y$ and a small $z$. However, with a small $y$ and a large $z$, our proposed method can (while the compared methods cannot) address the missed AP problem and denoise the RSS measurements at different observing locations.

The performances of KNN and WKNN are nearly the same, and the performance of the histogram method is not as good as other methods. It is always with a large mean localization error and a large mean squared error. Besides, the histogram method can fail to estimate a location when the RSS measurements are not sufficient. The failure rate is as shown in Figure 9.

[figure omitted; refer to PDF]

7. Conclusion

This paper investigates the problem of localization arising from insufficient RSS measurements, that is, the missed AP problem and the RSS measurement noise problem. Traditional location fingerprinting methods rely on a large quantity of RSS observations at the same location to finally observe all the APs so that no APs can be missed from the location fingerprints and to denoise RSS measurements by averaging RSS observations at the same location. We propose a novel localization method which uses the maximum likelihood estimation and the stochastic gradient descent to estimate locations in case the RSS measurements are insufficient to generate accurate location fingerprints. The results show that our proposed method can achieve better localization accuracy than most commonly used location fingerprinting methods like the KNN, WKNN, and histogram methods. Especially when the number of observations at each location is relatively small, our proposed method has evident superiority.

Conflicts of Interest

The authors declare no conflicts of interest.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants 61602111, 61320106007, 61402104, 61502100, 61532013, 61572130, and 61632008, by the Jiangsu Provincial Natural Science Foundation of China under Grants BK20150628, BK20140648, and BK20150637, and by the Collaborative Innovation Center of Novel Software Technology and Industrialization.

Glossary

Notations

$\mathrm{R}\mathrm{S}{\mathrm{S}}_{i,j}$:RSS measurement at the $j$th location to the $j$th AP

$L_i$:Coordinates of the $j$th observing location

$A_j$:Coordinates of the $j$th AP’s location

$d_{i,j}$:Distance between $L_i$ and $A_j$

$S$:The set of all RSS measurements

$E$:The estimation error

$O$:Observation of RSS measurements

$M$:The number of observing locations

$N$:The number of APs

$y$:The number of observations per location

$z$:The volume of each observing location.

References

[1] R. Faragher, R. Harle, "Location fingerprinting with bluetooth low energy beacons," IEEE Journal on Selected Areas in Communications, vol. 33 no. 11, pp. 2418-2428, DOI: 10.1109/JSAC.2015.2430281, 2015.

[2] P. Yang, W. Wu, M. Moniri, C. C. Chibelushi, "Efficient object localization using sparsely distributed passive RFID tags," IEEE Transactions on Industrial Electronics, vol. 60 no. 12, pp. 5914-5924, DOI: 10.1109/TIE.2012.2230596, 2013.

[3] K. Chintalapudi, A. P. Iyer, V. N. Padmanabhan, "Indoor localization without the pain," Proceedings of the 16th Annual Conference on Mobile Computing and Networking (MobiCom '10), pp. 173-184, DOI: 10.1145/1859995.1860016, .

[4] K. Wu, J. Xiao, Y. Yi, D. Chen, X. Luo, L. M. Ni, "CSI-based indoor localization," IEEE Transactions on Parallel and Distributed Systems, vol. 24 no. 7, pp. 1300-1309, DOI: 10.1109/TPDS.2012.214, 2013.

[5] Z. Yang, Z. Zhou, Y. Liu, "From RSSI to CSI: indoor localization via channel response," ACM Computing Surveys, vol. 46 no. 2, article 25,DOI: 10.1145/2543581.2543592, 2013.

[6] F. Yang, Q. Zhai, G. Chen, A. C. Champion, J. Zhu, D. Xuan, "Flash-Loc: Flashing mobile phones for accurate indoor localization," Proceedings of the 35th Annual IEEE International Conference on Computer Communications, IEEE INFOCOM 2016,DOI: 10.1109/INFOCOM.2016.7524391, .

[7] W. Wang, A. X. Liuy, K. Sun, "Device-free gesture tracking using acoustic signals," Proceedings of the 22nd Annual International Conference on Mobile Computing and Networking, MobiCom 2016, pp. 82-94, DOI: 10.1145/2973750.2973764, .

[8] W. Mao, J. He, L. Qiu, "CAT: High-precision acoustic motion tracking," Proceedings of the 22nd Annual International Conference on Mobile Computing and Networking, MobiCom 2016, pp. 69-81, DOI: 10.1145/2973750.2973755, .

[9] S. He, S.-H. Gary Chan, L. Yu, N. Liu, "Fusing noisy fingerprints with distance bounds for indoor localization," pp. 2506-2514, DOI: 10.1109/infocom.2015.7218640, .

[10] Y. Wen, X. Tian, X. Wang, S. Lu, "Fundamental limits of RSS fingerprinting based indoor localization," Proceedings of the IEEE Conference on Computer Communications (INFOCOM '15), pp. 2479-2487, DOI: 10.1109/infocom.2015.7218637, .

[11] P. Barsocchi, S. Lenzi, S. Chessa, F. Furfari, "Automatic virtual calibration of range-based indoor localization systems," Wireless Communications and Mobile Computing, vol. 12 no. 17, pp. 1546-1557, DOI: 10.1002/wcm.1085, 2012.

[12] L. Li, W. Yang, M. Z. Alam Bhuiyan, G. Wang, "Unsupervised learning of indoor localization based on received signal strength," Wireless Communications and Mobile Computing, vol. 16 no. 15, pp. 2225-2237, DOI: 10.1002/wcm.2678, 2016.

[13] J. Jun, S. Chakraborty, L. He, Y. Gu, D. P. Agrawal, "Robust and undemanding wifi-fingerprint based indoor localization with independent access points," Proceedings of the Microsoft Indoor Localization Competition (IPSN), pp. 13-17, .

[14] Q. Zhang, Z. Zhou, W. Xu, J. Qi, C. Guo, P. Yi, T. Zhu, S. Xiao, "Fingerprint-free tracking with dynamic enhanced field division," Proceedings of the 34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015, pp. 2785-2793, DOI: 10.1109/INFOCOM.2015.7218671, .

[15] A. Rai, K. K. Chintalapudi, V. N. Padmanabhan, R. Sen, "Zee: Zero-effort crowdsourcing for indoor localization," Proceedings of the 18th annual international conference on Mobile computing and networking (Mobicom '12), pp. 293-304, DOI: 10.1145/2348543.2348580, .

[16] H. Wang, S. Sen, A. Elgohary, M. Farid, M. Youssef, R. R. Choudhury, "No need to war-drive: unsupervised indoor localization," pp. 197-210, DOI: 10.1145/2307636.2307655, .

[17] Z. Yang, C. Wu, Y. Liu, "Locating in fingerprint space: wireless indoor localization with little human intervention," Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (Mobicom '12), pp. 269-280, DOI: 10.1145/2348543.2348578, .

[18] A. Purohit, Z. Sun, S. Pan, P. Zhang, "SugarTrail: Indoor navigation in retail environments without surveys and maps," Proceedings of the 2013 10th Annual IEEE Communications Society Conference on Sensing and Communication in Wireless Networks, SECON 2013, pp. 300-308, DOI: 10.1109/SAHCN.2013.6644999, .

[19] K. Sheng, Z. Gu, X. Mao, X. Tian, W. Wu, X. Gan, X. Wang, "The collocation of measurement points in large open indoor environment," Proceedings of the 34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015, pp. 2488-2496, DOI: 10.1109/INFOCOM.2015.7218638, .

[20] C. Wu, Z. Yang, C. Xiao, C. Yang, Y. Liu, M. Liu, "Static power of mobile devices: Self-updating radio maps for wireless indoor localization," Proceedings of the 34th IEEE Annual Conference on Computer Communications and Networks, IEEE INFOCOM 2015, pp. 2497-2505, DOI: 10.1109/INFOCOM.2015.7218639, .

[21] K. Dong, W. Wu, H. Ye, M. Yang, Z. Ling, W. Yu, "Canoe: an autonomous infrastructure-free indoor navigation system," Sensors, vol. 17, article 996 no. 5, 2017.

[22] T. King, S. Kopf, T. Haenselmann, C. Lubberger, W. Effelsberg, . CRAWDAD data set mannheim/compass (v. 2008-04-11), Downloaded from http://crawdad.org/mannheim/compass/ , Apr. 2008

[23] B. Li, J. Salter, A. G. Dempster, C. Rizos, "Indoor positioning techniques based on wireless lan," Proceedings in the LAN, first IEEE international conference on wireless broadband and ultra wideband communications, Citeseer, .

[24] P. Bahl, V. N. Padmanabhan, "Radar: an in-building rf-based user location and tracking system," Proceedings in the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), vol. 2, pp. 775-784, .

[25] T. Roos, P. Myllymäki, H. Tirri, P. Misikangas, J. Sievänen, "A Probabilistic Approach to WLAN User Location Estimation," International Journal of Wireless Information Networks, vol. 9 no. 3, pp. 155-164, DOI: 10.1023/A:1016003126882, 2002.