Sage Journals: Discover world-class research

Abstract

Fingerprint-based indoor localization has become one of the most attractive and promising techniques; however, one primary concern for this technology to be fully practical is to maintain the fingerprint database to combat harsh indoor environmental dynamics, especially in the large-scale and long-term deployment. In this article, focusing on three key problems now existing in fingerprint database updating approaches such as the mechanism for triggering updates, the collection of new fingerprints and determination of fingerprints’ location information, we propose a fuzzy map mechanism and decision methods of neighbours’ fingerprints in response to all kinds of changes in indoor environments. Meanwhile, we design a static data collecting mechanism to filter reliable information from numerous users’ inputs and propose a neighbours’ fingerprint-assisted technique to calculate the location of fingerprints. Experimental results demonstrate that the proposed solution not only improves the performance of updating the fingerprint database in real time and robustness by 40% and 50%, respectively, but also reduces the update frequency and improves mean location accuracy by over 40%.

Keywords

Indoor location crowd-sourcing automatic fingerprint update deterministic techniques

Introduction

With the growing deployment of wireless local area network (WLAN) in indoor environments and the widespread use of mobile devices such as mobile phones, WLAN-based fingerprinting indoor localization has become one of the most attractive techniques and been intensively researched in both academia and industry.^1–6 The mostly used fingerprint is based on the received signal strength indicators (RSSIs) from the access points (APs) of WLANs due to their wide deployment and availability.

Typically, these methods consist of an offline phase followed by an online phase.⁷ In the off-line phase, a fingerprint database is built to fingerprint the surrounding signatures at every location in the areas of interests. In the online phase, the location is estimated by mapping the measured fingerprints against the database. However, a key enabler to make it fully practical still remains unsolved: fingerprint database updating. It is well-known that the RSSI value of an AP at a certain location can change over time due to a number of reasons including but not limited to network changes such as the removal of any existing APs or the installation of new APs and environment interferences like variations of temperature, light, humidity and weather conditions. As a consequence, the fingerprint database may deteriorate or even break down, leading to grossly inaccurate location estimation. To overcome this problem, in traditional methods, expert surveyors must repeat the site survey procedure, which is labour-intensive and time-consuming.

Currently, mobile phones possess powerful computing, communicating and sensing capability and act as an increasingly important information interface between humans and environments.⁸ Meanwhile, the crowd-sourcing method has been shown to be a promising approach to solving these problems.^8–19 These advances lay solid foundations of breakthrough technology for fingerprint database updating in WLAN-based location systems. In a crowd-sourcing-based system, each user can contribute to the updating of the fingerprint database;¹⁹ where the expert surveying is replaced by the individual end-user, these findings significantly reduce the recalibration cost. However, new challenges have been raised:

These methods often trigger updates by receiving user indication periodically. These practices are not well suited for complex indoor environments and will cause problems such as accuracy, too fast update frequency and malicious interference. How to achieve the process reasonably and practicably is challenging.

These methods maintain the fingerprint database by leveraging collaborations among end users. How to filter reliable and useful information from numerous users’ inputs is challenging.

These methods associate new fingerprints with their corresponding location by user feedback or sensor measurements. How to locate the fingerprints accurately and automatically is challenging.

In response to these challenges, we have developed the following algorithms:

A fuzzy map mechanism and a decision method of neighbours’ fingerprints in response to all different kinds of changes in indoor environments.

A dissimilarity-based RSSI clustering algorithm and static data collecting mechanism that solve the problem of data redundancy and ensure the accuracy and reliability of fingerprints newly captured by automatically collecting data without active user participation.

A neighbours’ fingerprints-assisted technique that labels measured data with corresponding location information without the explicit participation of users or complex computes.

We have evaluated our methods by conducting experiments in some real-world indoor wireless environments. The results show that our methods are an automatic, robust and effective database updating approach, which can significantly improve the performance of updating the fingerprint database in real time and robustness, and obtain a good balance between update frequency and location accuracy. In our test environments, compared with existing approaches, our methods improve the performance in real time and mean location accuracy and reduce update frequency by over 40%, and the performance in robustness is improved by about 50%.

The rest of this article is organized as follows. Section “Related work” briefly summarizes various previous works and analyses the key problems to be solved. Section “The mechanism for triggering updates” discusses the mechanism for triggering updates. Section “The update process of fingerprint database” presents the update process of fingerprint database. Section “Evaluations” evaluates the proposed techniques. Finally, section “Conclusion and future work” concludes the study and gives directions for future work.

Related work

With the growing deployment of WLAN in indoor environments and the widespread use of mobile devices such as smart phones, WLAN-based fingerprinting indoor location methods are getting popular due to their low deployment cost and relatively high localization accuracy.¹⁹ Scholars have put forward many alternatives to realize fingerprint database construction and maintenance. Generally, they witness two phases of development: static fingerprint-based techniques and adaptive updating techniques.

Static fingerprint-based techniques

Most of the existing fingerprint-based approaches are based on a common assumption that the fingerprint database built in the offline phase does not change much later in the online phase. Depending on how the static fingerprint database is built, these approaches can be classified into deterministic techniques and probabilistic techniques. Deterministic techniques apply deterministic inference to estimate a client’s locations, and the general form of location estimation is achieved through selecting reference points (RPs) whose fingerprints are the closest to the online RSSI measurements. For example, the RADAR system⁷ uses the nearest neighbour (NN) method to infer a user’s locations. If instead of selecting a single RP with the least distance, a set of closest RPs are selected, and the method is known as K-nearest neighbourhood (KNN).²⁰ In KNN, the user position is usually the centroid of a set of K RPs with the least distances. In addition, median filtering has also been used to improve the robustness of the KNN method to unusual fingerprint readings.

Considering a single RSS fingerprint may not be a sufficient representation of the data because of the time-varying nature of indoor propagation. Localization probabilistic approach²¹ utilized to improve the performance by calculating probability density function values of each common relation that is found between user retrieved beacons and database beacons. Then, for every position, it sums up that probability density function values and divides it with the amount of relations with respect of discarding positions that have fewer relations compared to receiving signal.²²

In summary, the probabilistic methods have the higher accuracy than deterministic algorithms. But deterministic algorithms are better fit for use in the mobile computing due to its simplicity and real time; therefore, the focus is drawn to the deterministic algorithms in this article.

Adaptive updating techniques in previous works

Motivated by the success of crowd-sourcing-based web sites like Wikipedia, recent approaches focus on shifting the tedious recalibration efforts from professional surveyors to common users.²³ As a new collaborative paradigm that leverages the power of tens of thousands of participants to accomplish one specific task, the adoption of crowd-sourcing technique is a rising trend among the recent efforts in indoor localization. Several researchers^8,10–18 have proposed and carried on the beneficial exploration to enable adaptive database update when environment changes. However, there are still many limitations.

First, in practice, RSSI samples measured in the online phase may significantly deviate from those stored in the fingerprint database. Generally speaking, there were two major reasons. On one hand, it is well-known that RSSI is vulnerable to environment dynamics, including transient interferences such as moving subjects, door opening and closing and prolonged changes like variations of light, temperature, humidity and weather conditions.⁸ On the other hand, the accuracy of fingerprints may gradually deteriorate when the network environment changes such as the removal of any existing APs or the installation of new APs. Most existing studies detect environment dynamics mainly by using the corrections made by users on their estimated positions ^10,11,14or by a periodic update simply,^8,18 and it might be too intrusive to some users with undesirable interruptions and cause some errors significantly to compromise accuracy. Besides, some score mechanisms of an AP^9,11 are introduced to detect network environment changes. These methods turned out to be effective in some situations, but it is too simple to cover various situations in reality. Hence, how to monitor such changes accurately in real time is the primary issue to be considered.

Second, different from the traditional ways, newly captured fingerprints come in the form of feedback from end users. Typical user feedback is not only the RSSI information but also the corresponding actual localization information. Here, according to the pattern of user feedback, updating techniques crowd-sourcing-based can be classified into two categories: active and passive updating.¹⁸ Active updating techniques require the user to explicitly bind the RSSI measured with the recognized localization. However, these interrupt users’ work routines and increase the errors caused by users’ malicious inputs. Inertial sensors (INSs) are commonly used in passive techniques, and their readings are simultaneously recorded with the RSSI measurements. Movement trajectories can be extracted from sensor measurements, which are then matched to physical indoor localization as fingerprint annotation.¹⁵ However, there are still some practical flaws; for instance, it is difficult to trace the trajectory of user precisely for user behaviour is unconstrained and the noise of the INSs in complex indoor environments. Hence, how to filter reliable and useful user feedback from numerous inputs is another key problem.

Third, it will be very difficult and demanding to perform the recalibration survey all over again every time it changes for the environments in a real system could constantly change, but actually the researches about how to trigger the updating procedure are scant. Meanwhile, another often overlooked problem is that the whole database should be re-configured even slight variations occur. It is cost-prohibitive to be implemented in large environments, especially referring to the problem about fingerprint dimension diversity and collection device diversity. Hence, the third issue required to research is how to correctly and effectively update the newly captured fingerprints into the database.

Analysation of RSSI dynamics

In this subsection, the consequences of RSSI dynamics on the indoor location estimation is analysed on emphasis.

As above, a static radio map may gradually deteriorate or even break down due to setup changes. Here, the changes can be categorized as Table 1 in the following.

Table 1.

The categories of changes in indoor environment.

The categories of changes		Examples
Environmental changes	Transient changes	People moving and door opening or closing
Environmental changes	Prolonged changes	The changes of light, temperature and humidity
Network changes		The removal of any existing APs and the installation of new APs

Then, we investigate the impacts of such changes on deterministic location estimation techniques, by using the most widely used NN algorithm as an example.

In NN, the user position is the location of RP with the least distances. The distance used here is the Euclidean distance between the vectors sent by the user, and each of the vectors recorded in the database.

Formally, assuming there are n locations in a region, the fingerprints recorded in the database can be represented as ${F_{1}, F_{2}, \dots, F_{n}}$ , where $F_{i} = (r_{1}^{i}, r_{2}^{i}, \dots, r_{m}^{i})$ and $r_{m}^{i}$ is the average values of RSSIs received from mth AP in location l_i. When the user requests its location, the phone sends a vector of RSSI to the server of the form $S = (s_{1}, s_{2}, \dots, s_{m})$ , where $s_{m}$ is the value of RSSI received from mth AP. The Euclidean distance between them is defined as

dist (S, F_{i}) = \sqrt{\sum_{j = 1}^{m} {(s_{j} - r_{j})}^{2}}

(1)

Then, the location of user L is calculated as

L = min dist (S, F_{i})

(2)

Note that in practice, the dimension m of AP detected between users and database is usually inconsistent, and the RSSI from AP only existing in one set is normally just set to zero or a minimum. Based on the above analysis, we draws some conclusions as follows:

Regardless of what happens, the deterministic algorithm can return a location estimated eventually, whether the result is accurate or not.

When the network changes, such as the removal of an existing AP, this AP cannot be detected by users but still exists in database, so the distance between them may increase and the location accuracy deteriorates significantly. And the result is similar when a new AP is deployed.

When the environment changes due to some prolonged interferences, such as the changes in light, temperature and humidity, all the RSSIs recorded in this region may fluctuate, so the distance between them may change and the location accuracy deteriorates gradually.

When the environment changes due to some transient interferences, such as moving subjects and door opening and closing, and considering that the average of RSSIs is recorded, the distance between them changes slightly and the location accuracy deteriorates slowly.

In another improved deterministic algorithm KNN, the user location is usually the centroid of a set of K RPs with the least distances, and the result is similar when such changes occur.

At present, existing methods still have a lot of limitations in commercialization and dissemination. For instance, some methods execute the update operations until users point out their estimated location errors, which is poor in time effectiveness and affect user’s experience. Besides, as the form or style of many private APs in a building varies enormously, the ‘score’ mechanisms introduced cannot detect network environment changes effectively and accurately.

In this article, we present an automatic, robust and effective database updating approach–based crowd-sourcing technique to resolve three key problems: the mechanism for triggering updates, the collection of new fingerprints and determination of fingerprints’ location information.

Lots of researches^24,25 have shown that after a period of fluctuation, the average of RSSI changes to stabilize, and the change of RSSI in the sampling points close to the AP is big in the first 10 s (see Figure 1). Therefore, to improve the accuracy of fingerprint database in this article, the average values of RSSI detected during stationary periods are recorded as new fingerprints. Recently, accelerometer-based detection of motion status has been a popular research topic in the context of activity recognition,^25–28 and the method in Jiang et al.²⁶ is adopted to recognize the users’ motion status according to the acceleration data using only the 5 Hz sampling frequency.

Considering that different kinds of changes have different effects on location estimation, first we propose an integrity check algorithm and fuzzy map mechanism in response to network changes accurately and timely and then monitor the environment changes reasonably by the neighbours’ fingerprints-assisted technique.

Considering that it is often difficult to determine the location information of new fingerprints directly, we switch our mindset to update the database when it is still correct, and then, the location information of new fingerprints is easily calculated by existing location algorithms.

Figure 1.

The variation of averaged RSSI from four APs in the same sampling position (sampling frequency = 1 Hz).

In conclusion, the entire update process of fingerprint database is described as in Figure 2. Different from most existing solutions, it has the following advantages:

It is a practical, flexible and accurate fingerprint database updating approach without complex algorithm and explicit users’ participation.

It is better to deal with the problems caused by network changes in real time and robustness.

It obtains a good balance between update frequency and location accuracy when dealing with the problems caused by environmental changes.

Figure 2.

Fingerprints updating processing.

The mechanism for triggering updates

As an important link of the fingerprint database updating, the researches on how to trigger an updating procedure to adapt the current environment are thin. In this section, the mechanism for triggering updates needs to be deployed in response to all kinds of changes in indoor environments reasonably and accurately.

Generally, the fingerprint database contains tuples of fingerprint–location relationships over all sample points in the region of interests. The physical area of interest is sampled as a finite location space $L = {l_{1}, l_{2}, \dots, l_{n}}$ where n is the total number of RPs and each location is attached with coordinates $l_{i} = (x_{i}, y_{i})$ , where $1 \leq i \leq n$ . Correspondingly, the signal space is $F = {F_{1}, F_{2}, \dots, F_{n}}$ and $F_{i} = (r_{1}^{i}, r_{2}^{i}, \dots, r_{m}^{i})$ is the fingerprint record corresponding to RP l_i. Here, for the convenience of computing, 6 APs with the highest observed RSSIs are collected normally.

The triggering mechanism for network changes

In this subsection, we introduce a new form of data storage in fingerprint database to solve the problem caused by network changes, which has the supreme effect on location estimation.

Due to the wide adoption of WLAN, there are many RSSI information received from different APs detected in an RP, and some researches^24,25 have shown that they are independent, irrelevant and do not interfere with each other, which can be proved by correlation coefficient functions, as given by

γ_{A P_{i,} A P_{j}} = \frac{cov (r_{i}, r_{j})}{σ_{i} σ_{j}} = \frac{\frac{1}{n} \sum_{k = 1}^{n} (r_{ik} - μ_{i}) (r_{jk} - μ_{j})}{σ_{i} σ_{j}}

(3)

where cov(r_i, r_j) is the covariance of the RSSI between ith AP and jth AP, $μ$ is the mean value, $σ$ is the standard deviation and n is the number of sample points. We select seven APs that are most widely covered in a building and sampled 50 times from each AP and then compute the correlation coefficient between one AP and others. As shown in Figure 3, the result can prove the conclusion above, and note that the AP₃ and AP₆ are irrelevant even they use the same channels.

Figure 3.

An example of RSSI correlation between AP₃ and other APs.

Based on the irrelevant characteristics of different APs, we introduce the ‘fuzzy map’ in LANDMARC algorithm²¹ instead of traditional fingerprints storage form. Meanwhile, considering the different characteristics between WLAN and the radio frequency identification technology (RFID), the construction of fuzzy map is improved as follows.

In order to solve the problem of AP redundancy, the APs with the highest observed RSSIs are collected normally. Based on the simulation experiment results in Zhang,²⁴ which indicates that the location accuracy is improved by increasing the number of APs recorded in an RP, the effect is not significantly improved when the number of APs recorded is more than 5. Hence, to enhance the robustness, the RSSIs of 6 APs with the highest observed values are first recorded in database from each RP. Formally, $F_{i} = (r_{1}^{i}, r_{2}^{i}, \dots, r_{6}^{i})$ .

In order to solve the problem of AP coverage in large-scale deployment, as long as an AP is recorded once in an RP, the RSSIs of this AP from all the RPs need be recorded. Meanwhile, when some APs cannot be detected in an RP, the RSSI of them is set to −80 dBm, which is identified as the threshold for most network interface cards’ sensitivity.^24,27 Formally, there are 6n APs detected from n RPs, assuming the number of APs is k after eliminating duplicates from the result set, and then, $F_{i} = (r_{1}^{i}, r_{2}^{i}, \dots, r_{k}^{i})$ .

The next aim is to establish the grid. Theoretically, the distributions of RPs are uniform, because the location accuracy is best in this case. Assuming that there are a RPs in the row and b RPs in the column, obviously $n = a \times b$ , and then, $a \times b$ equal-sized virtual grid cells is established and the RP is the centre of each virtual grid cell.

Then, the virtual map for each AP is established. The coordinates of the virtual map cell is the coordinates of each RP in it, and the RSSI value of each virtual map cell is the RSSI value from this AP recorded in the RP. At last, k virtual maps are established.

Finally, in the online phase, the flow of location estimation is improved. When the RSSI value of a location target is obtained, we will mark those regions as 1 if the difference of RSSI values between the virtual map cell and location target is smaller than a threshold ε₁, or that more than the threshold value is marked as 0. Those places marked as 1 form a fuzzy map (see in Figure 4), and the user location is usually the centroid of places marked as 1.

Figure 4.

An example of fuzzy map in WLAN.

Then, we identify whether an F_i exists where the APs detected are completely consistent with the APs in S. If it does not exist, the triggering mechanism for network changes need to be activated immediately; otherwise, the triggering mechanism for environmental changes need to keep running.

By introducing the fuzzy map method, when it encounters network changes, the accuracy and robustness of location estimation are improved significantly for the following reasons.

When the user requests its location, the server selects the corresponding virtual maps in accordance with the RSSI vector sent by user. It reduces the errors caused by the inconsistent fingerprint dimension between user sides and database.

In general, there are two possibilities when some AP cannot be detected by users: it is removed or closed for some reason, such as its owner is away during that period. In either case, the fuzzy map method can deal with it immediately. Moreover, the virtual map of this AP can be saved in database for some time without affecting the location accuracy. Hence, this method is better than ‘score’ mechanisms in real time and robustness.

When some new APs are deployed, it only add a new virtual map without spending time on modifying the whole database.

The triggering mechanism for environmental changes

Then, we need another method to solve the problem caused by environmental changes. The fuzzy map method proposed above can partially improve the robustness to RSSI fluctuation, but it still needs a method to check the location estimation for accuracy.

Most existing methods solve this problem by user feedback or trajectory-matching technique. It is not a good idea to solve this problem in physical space especially considering the users’ malicious inputs and the accumulated error in INSs, so we try to solve it in the signal space. Meanwhile, considering that the dimension problem is vanished in such situations and the location changes slightly, a check algorithm based on the relationship between geographical neighbours is designed as follows.

When the server receives a new RSSI vector S sent by user, it first merges the RSSI vector S and a fingerprint F_i in database with the least distance into a cluster z. Here, we define a function count(z) to make statistics the number of RSSI vectors received in a cluster z.

After some time, all the clusters generated are sorted in descending count(z). Formally, let Q is the sequence of clusters, $Q = (z_{q 1}, z_{q 2}, \dots, z_{qn})$ with $count (z_{qx}) \geq count (z_{qy})$ , where $1 \leq x \leq y \leq n$ . Then, we define a parameter percent, and the clusters in the top percent are handled in the subsequent flows.

Finally, we check to see whether the locations of these clusters are still not changed. Note that according to the database, a cluster corresponds to a location l_i, and four fingerprints of its neighbours can be determined (see the green regions in Figure 2), and then, we try to obtain the real adjacent fingerprints of this cluster and the method details are described in section “Parameter settings.” Hence, the accuracy of location estimation is fully known by matching the similarity among these fingerprints.

Compared with most existing solutions, the main contributions of this method proposed are as follows:

The dissimilarity-based RSSI clustering algorithm used is simple and easy to operate, and it suffices general application, and it also has well practicality.

It obtains a good balance between update frequency and location accuracy.

It checks the accuracy of location estimation in the signal space, which simplifies the execution flow without affecting the location accuracy.

The update process of fingerprint database

In this section, we focus on how to filter reliable and useful information from numerous users’ inputs and further how to update the database effectively.

The identification for effective RSSI fingerprints

As described in section “Static fingerprint-based techniques,” due to characteristics of RSSI, the RSSIs received at a fixed location may change over time, and the average value of RSSIs continuously measured at a fixed location is more accurate than those measured instantly. Therefore, the RSSI fingerprints recorded during a stationary period are preserved as referenced fingerprints for updating the database, which is better in accuracy. Based on the analysis above, the key development lies in the detection of devices’ mobility.

Recently, accelerometer-based detection of motion status has been a popular research topic in the context of activity recognition.^8,25,26 In this subsection, we select the appropriate algorithm on the basis of the following principles.

Our research emphasizes the stability of the device rather than the activity of the person. Therefore, the algorithm for the independent direction of mobile devices needs to be applied to enhance the adaptability of the method.

Meanwhile, considering that a user’s motion status can change at any time, the detection process needs to be constantly active. The key challenge is to find a happy medium between battery consumption and the frequency of accelerometer readings.

Finally, with an overall consideration of all the factors, the method in Jiang et al.²⁶ is adopted. This algorithm recognizes the users’ motion status according to the acceleration data as long as they simply carry a mobile device with a build-in triaxial accelerometer and using only the 5-Hz acceleration sampling frequency and a 3-s window. The algorithm is based on the principle that when a person is moving, the average of the absolute acceleration changes within a short period is large, but the average of the acceleration changes is small (and vice versa). The engineering practice shows that the accuracy and energy consumption are satisfactory.

Note that once an RSSI fingerprint is recorded and sent to the server, it is first used to judge which change occurs by the integrity check. If network changes occur, the update process of fingerprint database is simple (as described in section “The identification for effective RSSI fingerprints”). Otherwise, the main update process is as follows.

The determination for neighbours of RSSI fingerprints

As above, the RSSI fingerprints of each stationary point can be recorded, but it is difficult to calculate the location of these isolated RSSI fingerprints. Wu et al.²⁹ proposed fingerprint spatial gradient (FSG), which exploits the spatial relationships among the RSSI fingerprints of multiple neighbouring locations. Experimental results show FSG as a spatially relative form and are more resistant to RSS uncertainties. On the same principle, we design a more convenient and practicable algorithm to determinate the RSSI fingerprints of its neighbours, and more importantly, it can be implemented by crowd-sourcing users.

In this subsection, the RSSI fingerprint of single stationary point is extended by adding the information of its neighbours, and the main work is as follows:

We define a new fingerprint as $F'_{i} = (f_{i}, {f_{i}}^{↑}, {f_{i}}^{↓}, {f_{i}}^{\leftarrow}, {f_{i}}^{\to})$ , where $({f_{i}}^{↑}, {f_{i}}^{↓}, {f_{i}}^{\leftarrow}, {f_{i}}^{\to})$ represent the fingerprints of its neighbours in up, down, left and right directions, respectively.

Then, we employ gyroscope to monitor relative direction, which has been demonstrated to be remarkably accurate as indicated in Zhao et al.²⁸ and Mingxin and Jianli.³⁰ Furthermore, the direction is normalized and limited to four directions (up, down, left or right).

The next task is to infer footstep counting from acceleration data. In this article, we adopt a finite-state machine-based algorithm proposed in Mingxin and Jianli,³⁰ which can provide step counting as accurate as up to 98%. The rationality is that the accelerations exhibit periodically repetitive patterns, which arise from the nature rhythmic of human walking. Moreover, we define a footstep counting parameter ε₂ to ensure the users are moved to the nearby neighbourhood.

Finally, we incorporate a clustering procedure to partition the RSSI fingerprints in the same direction into a cluster. Considering the disadvantage of these RSSI fingerprints in accuracy, the clustering algorithm is improved as follows.

Formally, we define two fingerprints A and B and identify fingerprints A and B in the same physical location cell when they satisfy the following conditions:

The number of common APs in each fingerprint exceeds a threshold ε₃.

The absolute value of $ρ_{s}$ exceeds a threshold ε₄. Spearman’s rank correlation $ρ_{s}$ can be calculated as follows.

We assume that the AP sets in common are

{(A P_{\cap 1}, s_{\cap 1}^{u}, s_{\cap 1}^{v}), \dots, (A P_{\cap w}, s_{\cap w}^{u}, s_{\cap w}^{v})}

where w is the number of APs in common and $s_{\cap Δ}^{u}$ and $s_{\cap Δ}^{v}$ are the RSSI value of Δth common AP detected at positions u and v, respectively. The sequence in position u $(s_{\cap 1}^{u}, s_{\cap 2}^{u}, \dots, s_{\cap w}^{u})$ is listed in ascending order and the hierarchical rank is described as $(r_{1}^{u}, r_{2}^{u}, \dots, r_{w}^{u})$ . Then

ρ_{s} = \frac{\sum_{Δ} (r_{Δ}^{(u)} - \overset{(u)}{\bar{r}}) (r_{Δ}^{(v)} - \overset{(v)}{\bar{r}})}{\sqrt{\sum_{Δ} \overset{2}{(r_{Δ}^{(u)} - \overset{(u)}{\bar{r}})}} \sqrt{\sum_{Δ} \overset{2}{(r_{Δ}^{(v)} - \overset{(v)}{\bar{r}})}}}

(4)

Note that this algorithm can not only identify fingerprints in the same physical location cell, but it can also match the similarity among different neighbour fingerprints. Moreover, compared with most existing solutions, it has the following advantages:

The accumulated error in INSs is reduced significantly by normalizing the direction and counting footstep roughly.

The inaccuracy of the RSSI fingerprints recorded during moving is effectively solved, by adopting Spearman’s rank correlation coefficient instead of the absolute RSSI values.

The calculation for location of RSSI fingerprints

When the fingerprint and its neighbours are confirmed, the next key challenge is how to associate the fingerprint with its locations in the floor plan.

In this subsection, we provide an algorithm that label measured RSSI fingerprints with corresponding location without complex algorithm and explicit users’ participation.

First, as described in section “The triggering mechanism for environmental changes,” the location accuracy deteriorates slightly when the environment changes. That is, the actual location is near the location estimated; hence, when the server receive a new RSSI vector S sent by user, we initially determine its location in accordance with the fingerprint recorded in database with the least distance.

Second, we extend the potential target space around the location estimated initially and match the similarity with its neighbour fingerprints in this target space. Moreover, we will mark those regions as 1 if the similarity between the neighbour fingerprint and location target satisfy the condition described in section “Parameter settings,” otherwise the regions are marked as 0.

Finally, we obtained four maps of the potential target space marked 0 and 1 and estimate the actual location of the fingerprint by merging these four maps into one. Then, we update the new fingerprint into the location calculated in database.

Evaluations

Experiment setup

This section presents a case study to evaluate the quality of the proposed approach. We evaluate the performance of the approach by applying it to a typical environment with 802.11b WLAN infrastructure. Test bed (see in Figure 5) is a recently constructed shopping mall that consists of metal-studded dry wall, wooden doors, metal tiled floor with polypropylene carpet tiles and a metal ceiling with suspended mineral fibre tiles, and further details are given in Table 2. During the initial phase, we survey the test bed with a sampling density of about 2 m × 2 m; for convenience, two representative areas A and B are collected as the research object (see in Figure 5) and produce around 200 sample locations.

Figure 5.

Layout of TB.

Table 2.

Test bed details.

Parameter	TB (4181.22 m²)
Length (m)	80.1
Width (m)	52.2
Ceiling height (m)	3.1
Number of rooms	65
Number of APs deployed	39

TB: test bed; AP: access points.

Then, we have successfully recruited 10 participants every day for 1 month and implemented our prototype on their own mobile phones, including Android and Apple iOS devices. The motion detection, orientation reckoning and step counting algorithm are implemented on the mobile phones. The update- processing method is implemented on the server side. In addition, the fingerprint database is built using MySQL. A web server receives RSSI fingerprints from mobile phones and delivers room localization services. Here, each volunteer simply works and live routinely as they commonly do. Then, we examine the approach in three steps. First, we determine the parameters introduced in this article. Second, we demonstrate the effect on location accuracy of the network changes. Finally, we show the effect on location accuracy of environmental changes.

Parameter settings

Several parameters in this article need to be determined: (1) the fuzzy map threshold ε₁, (2) the location identified scale parameter percent, (3) the footstep counting parameter ε₂ and (4) the similarity parameters of neighbour fingerprints ε₃ and ε₄.

To improve the location accuracy, an appropriate threshold ε₁ needs to be employed. In our test (see in Figure 6), the location accuracy can achieve ideal global optimum result when we set ε₁ from 8 to 10 dBm. On one hand, the average location error continues to increase if we reduce the threshold, for part of the effective NN, RPs are missed. On the other hand, the average location error continues to increase with the threshold increasing, for we cannot effectively remove redundant location information. Here, we set ε₁ to 10 in terms of the robustness of database.

Figure 6.

The location accuracy versus threshold of ε₁.

To obtain a good balance between update frequency and location accuracy, an appropriate parameter percent need to be employed. In our test, we set percent to 10%, 30% and 100% and check the location accuracy in 1 month. The result in Figure 7 has shown that the location accuracy is similar when percent is set to 30% and 100%, so the parameter percent set to 30% is acceptable and reasonable.

Figure 7.

The location accuracy versus different percent.

The set of footstep counting parameter ε₂ is to ensure that the users are moving to the nearby grid cell rather than pacing back and forth in a cell. Lots of research has shown that the normal footstep is about 0.5 m, suppose the length of cell is r, then

⌈ \frac{r}{0.5} ⌉ \leq ε_{2} \leq ⌊ \frac{2 r}{0.5} ⌋

(5)

In the dissimilarity-based RSSI clustering algorithm, Figure 8 has shown that there is no significant difference among clustering results when we set ε₃ to 5; Spearman correlation coefficient is a non-parametric indicator commonly used to measure the dependence of two variables, similarly when the value of two fingerprints sorted exceeds 0.6, the recognition result is good and the improvement is limited as the value increases (Figure 9). Here, we set ε₄ conservatively to 0.7.

Figure 8.

The clustering accuracy versus threshold of common APs.

Figure 9.

The clustering accuracy versus threshold of Spearman’s rank correlation.

Impact of network changes

In this subsection, we check whether this approach proposed can achieve accurate location estimation when network changes. To do that, we first deploy two new APs in region A that are not recorded before, and 400 samples are taken in each of 10 RPs randomly selected in region A. Meanwhile, the feedback is provided whenever the system returns a location that does not match the true location of the user. Then, we show the changes in terms of accuracy when using the approach proposed and compare it with the typical approach using user feedback⁹ and another passive updating techniques ACMU (ACMU employs ordinary users’ mobile devices as movable reference points to collect the newest fingerprints when the devices are static at specific locations, and locate these reference points based on trajectory matching) in Wu et al.⁸

As illustrated in Figure 10, when using the approach proposed in this article, the average location error stabilizes at around 2 m even for a small number of sampling. In contrast, when using the ACMU in Wu et al.⁸ after 15 rounds of sampling, the error decreased from about 5.6 to 2.9 m, and the minimal error may reach 2.3 m, when using the approach proposed in Luo et al.⁹ after 20 rounds of collecting user feedback, the error decreased from 6.5 to 2.8 m, and the minimal error may reach 2.4 m.

Figure 10.

The location accuracy versus different approaches when deploying new APs.

Second, we switch off two APs deployed in region B and repeat the above-mentioned tests. From the result in Figure 11, we can observe some similar situations, such as the average location error stabilizes at around 2 m throughout the whole process when using the approach proposed, but the location accuracy is poor for a small number of sampling when using the feedback algorithm in Luo et al.⁹ and ACMU in Wu et al.⁸ Note that in these cases, the users are knowledgeable and helpful and always suggest positive feedback; meanwhile, the walking trajectory is optimized. But even so, the improved fuzzy map approach proposed in this article can achieve the better performance in real time.

Figure 11.

The location accuracy versus different approaches when deployed APs are switched off.

Third, we test the robustness of approach by gradually increasing the new APs in region A and decreasing the existing APs in region B; another little instruction is 6 APs already exists in regions A and B. As illustrated in Figure 12, when the number of APs changed is less than 3, more than 80% location error is less than 2 m. That is when the APs changed is less than half of APs deployed in location region, the improved fuzzy map approach proposed in this article can still achieve encouraging performance and have stronger robustness.

Figure 12.

The location accuracy versus the number of APs changed.

Impact of environmental changes

In this subsection, we explore whether this approach proposed can achieve accurate location estimation in long-term deployment. First, 10 RPs are randomly selected in regions A and B, respectively, and users collect fingerprints for each RP every 3 days and locate users based on the fingerprints collected. During remaining time of 1 month, the approach proposed is continuously running, and network changes are allowed too.

Figure 13 shows that the average location error stabilizes at around 2 m, and even the localization service has run for a long term. That is, the approach proposed can achieve remarkable accuracy improvement, regardless of the running time. Then, we further inspect the location accuracy after long-term deployment and compare it with the typical approach using feedback algorithm in Luo et al.⁹ and passive updating techniques ACMU in Wu et al.,⁸ which both solve the problem of updating database in physical space. Figure 14 depicts the cumulative distribution function (CDF) by using the updated database when deployed for 3 days, and we can see that compared with algorithm in Wu et al.⁸ and Luo et al.,⁹ the 80th percentile accuracy is improved by about 50% and 100%, respectively. Figure 15 shows that more than 40% enhancements are still gained using the database updated by the approach proposed in this article after a 1-month running.

Figure 13.

The location accuracy versus times.

Figure 14.

CDF of location error versus different approaches for 3 days.

Figure 15.

CDF of location error versus different approaches for 30 days.

Second, we examine the average update frequency of the fingerprints for each RP, which reflects the robustness of the fingerprint database updated. Considering that there exist some problems such as subjectivity and randomness in the approach using user feedback, we only compared with another passive updating techniques ACMU in Wu et al.⁸ as illustrated in Figure 16, and the average update frequency in this article can be reduced by 45.7%.

Figure 16.

Comparison of update frequency in two techniques.

We further examine the average frequency of sending updated data in a mobile phone. In general, the process of updating data once has focused on three main parts: data acquisition, transmission and algorithm compute, which directly affects energy efficiency imposed on the mobile phones. As illustrated in Figure 17, compared with another passive updating techniques ACMU in Wu et al.,⁸ the average frequency in this article can be reduced by 46.1%.

Figure 17.

Comparison of sending data frequency in two techniques.

Conclusion and future work

In practice, we find that the changes in indoor environments can be categorized by two kinds and have different effects on location estimation. Therefore, we propose a fuzzy map mechanism to deal with the problems caused by network changes, which satisfy the requirements of real time and robustness. Meanwhile, we monitor the environmental changes by the neighbours’ fingerprints-assisted technique proposed, without complex algorithm and explicit users’ participation. Besides, the approach obtains a good balance between update frequency and location accuracy in the large-scale and long-term deployment. By applying it into the typical business scenario, we see encouraging results.

In this article, we focus on the ideal environments, where the RPs are distributed uniformly. How to construct the grid map of RSSI in the non-ideal state has not been sufficiently studied. Moreover, the leakage of the privacy problem extensively exists when the participants provide their fingerprint data, and how to ensure their security and privacy is another direction for future work.

Footnotes

Handling Editor: Amiya Nayak

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the science and technology major project of Education Department of Guangdong province (2017KZDXM052); the Guangdong Science and Technology major project (2017B030305004, 2016 B090918110 and 2015B010135006); the special fund of Guangdong Frontier and Key Technology Innovation (2016B010108005) and the Guangdong province applied R&D special fund for projects (2016B020243011 and 2016 B010125001).

ORCID iD

Xi Liu

References

Shen

Chen

Zhang

et al . Walkie-Markie: indoor pathway mapping made easy. In: Proceedings of the 10th USENIX conference on networked systems design and implementation, Lombard, IL, 2–5 April 2013. New York: ACM.

Yang

Liu

. Locating in fingerprint space: wireless indoor localization with little human intervention. In: Proceedings of the 18th annual international conference on mobile computing and networking, Istanbul, 22–26 August 2012. New York: ACM.

Skyhook Wireless. Location technology and intelligence, June 2018, http://www.skyhookwireless.com

Niemegeers

. A survey of indoor positioning systems for wireless personal networks. IEEE Commun Surv Tut 2009; 11(1): 13–32.

Harle

. A survey of indoor inertial positioning systems for pedestrians. IEEE Commun Surv Tut 2013; 15(3): 1281–1293.

Chan

S-HG

. Wi-Fi fingerprint-based indoor positioning: recent advances and comparisons. IEEE Commun Surv Tut 2016; 18(1): 466–490.

Bahl

Padmanabhan

. RADAR: an in-building RF-based user location and tracking system. In: Proceedings of the 19th annual joint conference of the IEEE computer and communications societies, vol. 2, Tel Aviv, 26–30 March 2000, pp.775–784. New York: IEEE.

Yang

Xiao

et al . Static power of mobile devices: self-updating fingerprint databases for wireless indoor localization. Comput Commun 2015; 30(6): 2497–2505.

Luo

Chen

Hoeber

. Wi-Fi-Based indoor positioning using human-centric collaborative feedback. IEEE Int Conf Commun 2011; 4(57): 1–6.

10.

Bhasker

Brown

Griswold

. Employing user feedback for fast, accurate, low-maintenance geolocationing. In: Proceedings of the Second IEEE annual conference on pervasive computing and communications, Orlando, FL, 17 March 2004. New York: IEEE.

11.

Gallagher

Dempster

et al . Database updating through user feedback in fingerprinting-based Wi-Fi location systems. In: Proceedings of the 2010 ubiquitous positioning indoor navigation and location based service, Kirkkonummi, 14–15 October 2010, pp.1–8. New York: IEEE.

12.

Bolliger

. Redpin-adaptive, zero-configuration indoor localization through user collaboration. In Proceedings of the first ACM international workshop on mobile entity localization and tracking in GPS-less environments, San Francisco, CA, 19 September 2008, pp.55–60. New York: ACM.

13.

Hansen

Wind

Jensen

et al . Algorithmic strategies for adapting to environmental changes in 802.11 location fingerprinting. In: Proceedings of the 2010 international conference on indoor positioning and indoor navigation, Zurich, 15–17 September 2010. New York: IEEE.

14.

Park

J-G

Charrow

Curtis

et al . Growing an organic indoor location system. In: Proceedings of the 8th international conference on Mobile systems, applications, and services, San Francisco, CA, 15–18 June 2010, pp.271–284. New York: ACM.

15.

Anshul

Krishna Kant

Venkata

et al . Zee: zero-effort crowdsourcing for indoor localization. In: Proceedings of the 18th annual international conference on mobile computing and networking, Istanbul, 22–26 August 2012, pp.293–304. New York: ACM.

16.

Lim

Jang

Yoon

et al . Radio map update automation for WiFi positioning systems. IEEE Commun Lett 2013; 17(4): 693–696.

17.

Lemelson

Kopf

King

et al . Improvements for 802.11-based location fingerprinting systems. In: Proceedings of the 33rd annual IEEE international computer software and applications conference, Seattle, WA, 20–24 July 2016, pp.21–28. New York: IEEE.

18.

Chen

Wang

. FinCCM: fingerprint crowdsourcing, clustering and matching for indoor subarea localization. IEEE Wirel Commun Lett 2015; 4(6): 677–680.

19.

Zhang

Valaee

Bin Xu

et al . Graph-based semi-supervised learning for indoor localization using crowdsourced data. Appl Sci 2017; 5(7): 467–489.

20.

Liu

Darabi

Banerjee

et al . Survey of wireless indoor positioning techniques and systems. IEEE Trans Mob Comput 2013; 14(2): 444–457.

21.

Liu

Lau

Y C.

Patil

A P.

LANDMARC: indoor location sensing using active RFID. In: Proceedings of the 1st IEEE international conference on pervasive computing and communications, Fort Worth, TX, 26 March 2003, pp.407–415. New York: IEEE.

22.

Khalajmehrabadi

Gatsis

Akopian

. Modern WLAN fingerprinting indoor positioning methods and deployment challenges. IEEE Commun Surv Tut 2017; 19(3): 1974–2002.

23.

Lee

Jung

Lee

et al . Elekspot: a platform for urban place recognition via crowdsourcing. In: Proceedings of the 2012 IEEE/IPSJ 12th international symposium on applications and the internet, Izmir, 16–20 July 2012, pp.190–195. New York: IEEE.

24.

Zhang

. Study on WLAN based indoor location estimation technology. PhD Dissertation, Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China, 2009.

25.

Feng

. Research and implementation of a compressive sensing-based indoor positioning system using RSSI. PhD Dissertation, Department Communication and Information System, Beijing Jiao Tong University, Beijing, China, 2010.

26.

Jiang

Pan

et al . Ariel: automatic Wi-Fi based room fingerprinting for indoor localization. In: Proceedings of the 2012 ACM conference on ubiquitous computing, Pittsburgh, PA, 5–8 September 2012, pp.441–450. New York: IEEE.

27.

Wang

Sen

Elgohary

et al . No need to war-drive: unsupervised indoor localization. In: Proceedings of the 10th international conference on Mobile systems, applications, and services, Low Wood Bay, 25–29 June 2012. New York: ACM.

28.

Zhao

Han

et al . Crowdsourcing and multi-source fusion based fingerprint sensing in smartphone localization. IEEE Sensors J 2018; 18: 3236–3247.

29.

Yang

et al . Human mobility enhances global positioning accuracy for mobile phone localization. IEEE Trans Parallel Distribut Syst 2015; 26(1): 131–141.

30.

Mingxin

Jianli

. Design and implementation of WLAN indoor positioning system model based on energy efficiency. Chin J Sci Instrum 2014; 35(5): l169–1177.

An efficient crowd-sourcing-based approach for fingerprint database updating

Abstract

Keywords

Introduction

Related work

Static fingerprint-based techniques

Adaptive updating techniques in previous works

Analysation of RSSI dynamics

The mechanism for triggering updates

The triggering mechanism for network changes

The triggering mechanism for environmental changes

The update process of fingerprint database

The identification for effective RSSI fingerprints

The determination for neighbours of RSSI fingerprints

The calculation for location of RSSI fingerprints

Evaluations

Experiment setup

Parameter settings

Impact of network changes

Impact of environmental changes

Conclusion and future work

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References