Zengshan Tian, Haifeng Cong and Mu Zhou

(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

Abstract: Fingerprint-based Bluetooth positioning is a popular indoor positioning technology. However, the change of indoor environment and Bluetooth anchor locations has significant impact on signal distribution, which will result in the decline of positioning accuracy. The widespread extension of Bluetooth positioning is limited by the need of manual effort to collect the fingerprints with position labels for fingerprint database construction and updating. To address this problem, this paper presents an adaptive fingerprint database updating approach. First, the crowdsourced data including the Bluetooth Received Signal Strength (RSS) sequences and the speed and heading of the pedestrian were recorded. Second, the recorded crowdsourced data were fused by the Kalman Filtering (KF), and then fed into the trajectory validity analysis model with the purpose of assigning the unlabeled RSS data with position labels to generate candidate fingerprints. Third, after enough candidate fingerprints were obtained at each Reference Point (RP), the Density-based Spatial Clustering of Applications with Noise (DBSCAN) approach was conducted on both the original and the candidate fingerprints to filter out the fingerprints which had been identified as the noise, and then the mean of fingerprints in the cluster with the largest data volume was selected as the updated fingerprint of the corresponding RP. Finally, the extensive experimental results show that with the increase of the number of candidate fingerprints and update iterations, the fingerprint-based Bluetooth positioning accuracy can be effectively improved.

Keywords: indoor positioning; fingerprint database updating; crowdsourced data; Bluetooth; DBSCAN

1 Introduction

With the rapid development of mobile computing, the wireless communication network brings a strong impetus for personal positioning applications. In this circumstance, the Location-based Service (LBS)[1]has caught extensive attention. At present, the Global Navigation Satellite System (GNSS)[2]can basically meet the demand of outdoor positioning accuracy, whereas the signal from the satellites is easily blocked by the buildings, which will consequently deteriorate the positioning accuracy of the GNSS. However, there is no such problem for Bluetooth[3], Wireless Local Area Network (WLAN)[4-5], Ultra Wideband (UWB)[6], Radio Frequency Identification (RFID)[7], and magnetic[8]positioning technologies, which are much applicable to indoor environments.

The Bluetooth positioning technology is featured with the characteristics of low-power, low-cost, and high positioning accuracy. Among the existing Bluetooth positioning approaches, fingerprint-based Bluetooth positioning approach[9]is the most favored because of its low computational complexity, no extra hardware requirement, and strong environmental adaptability. However, this approach normally requires laborious and time-consuming manual process of collecting fingerprints with position labels[10-11]to construct and update fingerprint database. What is more difficult to accept is that this manual process needs to be repeated whenever the fingerprint database becomes outdated[12]due to the environmental change.

To overcome this limitation, this paper proposes a new fingerprint database updating approach, which enables users to participate in the process of fingerprint database construction and updating with low labor and time costs. Three main contributions of this paper are summarized as follows. First, the Bluetooth and Micro-Electro-Mechanical System (MEMS) fusion positioning algorithm was designed to assign the unlabeled Received Signal Strength (RSS) data with position labels and generate candidate fingerprints. This approach is based on the advantages of Bluetooth module and MEMS sensors to eliminate the accumulated error of the Pedestrian Dead Reckoning (PDR) and the jump error of the fingerprint-based Bluetooth positioning respectively. Second, by considering the error of the Bluetooth and MEMS fusion positioning algorithm which may lead to the mismatch between the candidate fingerprints and the reference points (RPs), the Density-based Spatial Clustering of Applications with Noise (DBSCAN) approach was conducted on both the original and the candidate fingerprints to filter out the fingerprints which had been identified as the noise, and then the mean of fingerprints in the cluster with the largest data volume (or simply called the largest cluster) at each RP was selected to update fingerprint database. Third, the effectiveness and efficiency of the proposed approach were verified by using our own-designed hardware platform in an actual indoor environment.

The rest of this paper is organized as follows. Section 2 reviews some related work on fingerprint database construction and updating in indoor positioning. Section 3 describes the proposed approach in detail, and the corresponding experimental results are illustrated in Section 4. Finally, Section 5 concludes the paper and provides some future research directions.

2 Related Work

To maintain the performance of fingerprint-based positioning, the fingerprint database construction and updating process has caught significant attention. The authors in Ref. [13] proposed a new fingerprint database updating approach, OIL, which provides an interactive interface for users to actively participate in updating fingerprints. In this approach, almost no manual effort is involved in the fingerprint database updating process, whereas the users have to be frequently bothered when they first start the system, which increases the burden of the users. Luo et al.[14]proposed a voting mechanism and a fingerprint database update method. The mutual cooperation between reference anchor nodes was used to update the fingerprint database, which can reduce the burden of the users.

To avoid the subjective error caused by user participation, many approaches utilize the data from the MEMS sensors embedded in smartphones and the topological structure of the target area to physically label the unlabeled RSS data. Most of the existing popular systems such as Zee[15], UnLoc[16], WILL[17], and LiFS[18]depend on the MEMS sensors to update fingerprint database. Although these systems are capable of updating the fingerprint database to some extent, many problems arise due to the imperfection of MEMS sensors. For example, the error of MEMS sensors results in the accumulated error of the PDR and leads to the deterioration of positioning accuracy. To avoid such problem, researchers[19-20]installed a smartphone on robots for collecting fingerprints by Simultaneous Localization and Mapping (SLAM) technology.

Many other approaches adopt the concept of semi-supervised learning[21-22]to update the fingerprint database based on a small amount of labeled RSS data. Most of them depend on specific optimization algorithms (such as manifold learning[23]and interpolation[24]) to estimate the position labels of the unlabeled RSS data. For example, the approach in Ref. [25] is dependent on the dimensionality reduction migration learning, which uses the manifold alignment to estimate the position labels of the crowdsourced unlabeled RSS data with low effort. However, the performance of these approaches is determined by the initial model which is constructed from a few labeled RSS data, and therefore it could be poor when the labeled RSS data are not enough or ineffective. To solve this problem, Jung and Han[26]proposed to use the concept of unsupervised learning to update the fingerprint database by considering the hidden internal relations between the unlabeled RSS data. Researchers in Ref. [27] adopted active learning scheme with uncertainty selective sampling algorithm to maximize cost-efficiency of the update phase.

Different from the approaches above, this paper uses the Bluetooth and MEMS fusion positioning algorithm to assign the unlabeled RSS data with position labels instead of using the MEMS sensors solely. In addition, as one of the most representative unsupervised learning algorithms, the DBSCAN approach is applied without constructing any specific initial model to filter out the fingerprints which have been identified as the noise, and then the mean of fingerprints is used in the largest cluster at each RP to update the fingerprint database.

3 System Description

3.1 System Framework

The overall system structure consists of two main modules (i.e., data preprocessing module and database updating module), as shown in Fig.1. First of all, the crowdsourced data including the Bluetooth RSS sequences and the speed and heading data from the MEMS sensors are forwarded to the server. Second, the wave peaks which are discriminated from the RSS sequences are combined with the result of the Kalman Filtering (KF) to perform the trajectory validity analysis. Then, the candidate fingerprints are generated by assigning the position labels to the unlabeled RSS data from the result of RPs matching. Finally, with enough candidate fingerprints obtained, both the original and the candidate fingerprints at each RP are clustered by the DBSCAN approach, and the mean of the fingerprints in the largest cluster is selected as the updated fingerprint of the corresponding RP. In addition, the remaining fingerprints after noise filtering are set as the new original fingerprints for the next clustering.

Fig.1 System structure

3.2 KF Model

The PDR is a popular algorithm using the 9-axis MEMS sensor data to estimate the positions of a pedestrian[28]. Since most of the commercial smartphones are equipped with low-cost MEMS sensors, the speed and heading data from the MEMS sensors are normally affected by the accumulated error over time, which may lead to the deviation of the estimated positions gradually from the real ones. The fingerprint-based positioning algorithms[29](e.g., Weighted K-nearest Neighbor (WKNN)) are independent of the accumulated error because each positioning result is determined by the matching between the current RSS data and the pre-constructed fingerprint database. Therefore, we utilized the KF model[30]to fuse the results of the PDR and the fingerprint-based positioning to improve the accuracy of the unlabeled candidate fingerprints labeling.

The KF model is known as a state estimation approach with minimum variance. Specifically, it is based on the state transition equation to combine the state estimation at the previous moment and the observation result at the current moment to infer the new state value, as expressed in Eqs. (1) and (2). This approach has the advantage of no need for storing a large amount of data.

xt+1=Fxt+ωt

(1)

yt=Hxt+vt

(2)

wherextandytare the state and observed variables at the momentt.ωtandvtare the process and observation noise, and the corresponding covariance matrices are notated asQandRrespectively.FandHare the state transition and observation matrices. Based on the KF model, the optimal estimation process is described in Eqs. (3)-(7).

(3)

(4)

(5)

(6)

(7)

(8)

(9)

where the notationE(·) represents the expectation operation.

To build the KF model, we first employed the PDR to construct the state transition equation as

(10)

(11)

Then, by taking the fingerprint-based positioning result as well as the speed and heading data from the MEMS sensors as the observations, the observation equation is constructed as

(12)

3.3 Trajectory Validity Analysis

Due to the excessive jump errors in the Bluetooth and MEMS positioning results, the performance of Bluetooth and MEMS fusion positioning algorithm is not always satisfactory. Figs.2(a) and 2(b) provide two examples of the results of Bluetooth and MEMS fusion positioning. It can be concluded that if the poor matching between the estimated and the real trajectories occurs, the position labels cannot be precisely assigned to the real associated unlabeled RSS data, which will consequently deteriorate the performance of the fingerprint database. To address this problem and to guarantee the effectiveness of the physical labeling process, we conducted the trajectory validity analysis to eliminate the estimated positions which deviate a lot from the real ones.

Therefore, the propagation model with respect to the Bluetooth signal is constructed as

RSS=-10nlogd-A

(13)

whereAis the RSS value at the location with 1 m from the anchor,dis the distance from the anchor to the target, RSS is the RSS value at the target location, andnis the path loss exponent which is estimated from the labeled RSS data. On the basis of the signal propagation property in Eq. (13), we proposed an approach to judge whether a newly-collected piece of RSS data can be used to update the fingerprint database.

Fig.2 Result of Bluetooth and MEMS fusion positioning

An example of the RSS variation from two different anchors in an actual straight corridor environment is shown in Fig.3, from which we can find that there was a peak of the RSS values (defined as a local maximum of RSS values larger than -55 dBm) when the pedestrian is passed by an anchor. Based on this, we recorded each moment at which a peak appeared and selected the position of the corresponding anchor as the real position of the pedestrian at this moment. Then, we calculated the Euclidean distance between the real and the estimated positions by the Bluetooth and MEMS fusion positioning, according to which we judged whether this newly-collected piece of RSS data can be used for fingerprint database updating. For example, as shown in Fig.4, if the peak of RSS values from Anchor1 is obtained at the momentt, the location of Anchor1 is selected as the real position of the pedestrian (xAP,yAP) at this moment. When the distance between (xAP,yAP) and the estimated position (xfusion,yfusion) is not larger than the threshold distancemax, the RSS data can be used to update the fingerprint database. Here, the threshold distancemaxis set to be twice of RP interval in our system.

Fig.3 An example of RSS variation from two different anchors

Fig.4 Trajectory validity analysis

3.4 Position Labels Assignment

After the trajectory validity analysis, the coordinate of the RP with the smallest distance to the estimated position of the pedestrian (or the matched RP), (xRF,yRF), was selected as the physical label of the corresponding unlabeled RSS data to generate a candidate fingerprint as follows

(14)

(15)

Fig.6 shows the architecture diagram from the input crowdsourced data to candidate fingerprints generation. When a sufficient amount of crowdsourced data is collected, enough candidate fingerprints can be obtained at each RP for the next fingerprint database updating.

Fig.5 RPs matching

3.5 Fingerprint Database Updating

With enough candidate fingerprints obtained, the fingerprint database updating can be started by conducting the DBSCAN approach[31]on both the original and the candidate fingerprints.

Fig.6 Candidate fingerprints generation

3.5.1DBSCAN

The trajectory validity analysis helps much to filter out the pedestrian trajectories which deviate a lot from the real ones, but the error of the estimated positions leads to the bias of assigning position labels to candidate fingerprints and results in the wrong matching of candidate fingerprints to the RPs which they do not actually belong to. Besides, the RSS data at each RP involve the noise more or less due to the instability of devices and the interference during the data acquisition. Figs.7-10 show an example of considering only three RPs (A,B, andC) and the corresponding matching results in both physical and signal spaces. Here,ai,bi, andcistand for the fingerprints which belong toA,B, andC, andniis the noise. By takingAas an example,b8,b9,b10andc7were wrongly matched toA.

In order to choose the appropriate clustering approach to increase the probability of correct matching with respect to candidate fingerprints, we illustrate the two main properties of the candidate fingerprints at each RP as follows:

1) The candidate fingerprints at each RP normally involve a small amount of wrongly-matched fingerprints and noises, which should be filtered out during the fingerprint database updating.

2) With the accumulation of crowdsourced data, the number of the candidate fingerprints at each RP increases, which results in the difficulty of choosing the appropriate number of clusters for candidate fingerprints.

By considering the properties of the candidate fingerprints above, the DBSCAN approach is appropriate for the candidate fingerprints clustering because it can filter out the noise and generate the clusters automatically based on the density of the candidate fingerprints without manually setting the number of clusters in advance. By takingAas an example, it was difficult to discriminate the wrongly-matched fingerprints and filter out the noise in physical space, but they deviated a lot from the candidate fingerprints which actually belong toA, as shown in Figs.8-10. Based on this, we conducted the DBSCAN approach on candidate fingerprints in signal space, and selected the mean of fingerprints in the largest cluster to update the fingerprint database.

Fig.7 Candidate fingerprints belonging to each RP

Fig.8 Signal space at RP A

Fig.9 Signal space at RP B

Fig.10 Signal space at RP C

To facilitate the interpretation of conducting the DBSCAN approach on candidate fingerprints, we constructed the set of candidate fingerprints at each RP as

CandidateFingerprints={f1,…fi,…,fm}

(16)

wherefiis thei-th candidate fingerprint. Then define the terms used in the DBSCAN approach as

1)ε-neighborhood: For each candidate fingerprintfi∈CandidateFingerprints, itsε-neighborhood,Nε(fi), consists of the candidate fingerprints with the distance fromfinot larger thanε, which is expressed as

N(fi)={fj∈CandidateFingerprints|dist(fi,fj)≤ε}

(17)

where dist(fi,fj) indicates the Euclidean distance betweenfiandfj.

2) Core candidate fingerprint: If theε-neighborhood officontains at least MinFts candidate fingerprints (i.e., |Nε(fi)|≥MinFts), where |Nε(fi)| is the number of elements inNε(fi), thenfiis a core candidate fingerprint.

3) Directly density-reachable: Iffjis a core candidate fingerprint andfjis in theε-neighborhood offi,fjis directly density-reachable fromfi.

4) Density-reachable: Forfiandfj, if there is a sequence {p1,p2,…，pn} satisfying the relations thatp1=fi,pn=fj, andpi+1is directly density-reachable frompi, thenfjis density-reachable tofi.

5) Density-connected: Forfiandfj, if there isfkfrom which bothfiandfjare density-reachable,fiis density-connected withfj.

Fig.11 shows an example to illustrate the terms defined above, whereε=3,ε-neighborhood is represented as the dotted red circle, andx1is a core candidate fingerprint. It was found thatx2was directly density-reachable fromx1andx3, and density-connected withx4.

Fig.11 Illustration of the terms used in the DBSCAN

As we know, the aim of the DBSCAN approach is to generate the cluster containing the largest number of candidate fingerprints which are directly density-reachable or density-reachable between each other. From the pseudo-code of the DBSCAN approach in Table 1, it can be seen that from lines 3 to 12, if the relations of |Nε(fi)|≥MinFts for each candidate fingerprintfiis satisfied, thenfiis determined as a core candidate fingerprint, otherwise it is determined as the noise. From lines 17 to 27, the cluster containing only core candidate fingerprints is expanded by adding the associated density-connected candidate fingerprints. Finally, from lines 15 to 16, the clusterCRealcontaining the largest number of candidate fingerprints is selected as the output of the DBSCAN approach.

Fig.12 shows the architecture diagram of the DBSCAN conducted on both the original and the candidate fingerprints at each RP, in which the fingerprints which have been identified as the noise are filtered out, and the mean of fingerprints in the largest cluster to update the fingerprint database is selected.

3.5.2Parametersoptimization

Based on the discussion above, the performance of the DBSCAN approach significantly depends on the parametersεand MinFts. During the testing, if the valueεis appropriately selected, the value |Nε(fi)| for different candidate fingerprints is much different, otherwise the value |Nε(fi)| tends to be the same. For example, when the valueεis too small, the value |Nε(fi)| approaches 1, while when the valueεis too large, the value |Nε(fi)| approachesn, wherenis the number of candidate fingerprints. Hence, we utilized the information entropy[32]to convert the parameterεoptimization problem into the problem of minimizing the information entropy in Eq.(18). To solve this problem, we used the simulated annealing approach[33]to obtain the optimal valueεcorresponding to the minimal information entropy. Here, we set the optimal value MinFts equal to the mean of |Nε(fi)| under the optimal valueε.

Table 1 Pseudo-code of the DBSCAN approach

Fig.12 Fingerprint database updating at each RP

(18)

4 Experimental Results

4.1 Environmental Layout

Fig.13 shows the target environment (with the dimension of 65 m by 17 m), in which there is a hall and a straight corridor. In this figure, the red triangles and the black dots stand for the locations of anchors and RPs respectively. A photo of the target environment is shown in Fig.14.

Fig.13 Topological structure of the target environment

Fig.14 Photo of the target environment

Fig.15 shows the hardware platform, which involves a smartphone terminal used for data acquisition, a Java-based data processing server, and several Bluetooth anchors based on TI’s CC2540 chip. The platform was utilized to collect the Bluetooth RSS data and the data from the magnetometer, gyroscope, and accelerometer simultaneously.

4.2 Result of DBSCAN

Fig.16 shows an example of the clustering result of the candidate fingerprints at a RP by the DBSCAN approach. In this figure, the horizontal and vertical axes stand for the anchor ID and RSS value respectively, and each candidate fingerprint is represented as a polyline, where the black polylines are the noise and the blue, red, and green ones stand for the candidate fingerprints belonging to clusters 1, 2, and 3, respectively. Since cluster 1 contains the largest number of candidate fingerprints, the mean of the candidate fingerprints in this cluster was used to update the fingerprint at this RP.

Fig.15 Hardware platform

Fig.16 Clustering result of candidate fingerprints at a RP

4.3 Results of Fingerprint Database Updating

Because of the large area of the experimental environment, a lot of data needed to be collected to update the fingerprint database. Therefore, the tester walked around the positioning area for about 3 h a day and collected data to update the fingerprint database. The experiment was carried out for five days, and the data collected in the first three days effectively improved the positioning accuracy. While the data collected on the fourth and fifth days basically had no effect on the improvement of the positioning accuracy. Therefore, we mainly display and analyze the positioning results of the first three fingerprint database updating.

To investigate the performance of the proposed fingerprint database updating approach, three paths in the target environment were selected for the testing. The results of Bluetooth positioning on these paths are shown in Figs.17-19, in which the black, blue, and red polylines stand for the real path and the paths estimated by the Bluetooth positioning before and after fingerprint database updating, respectively. By taking a length of the straight path circled in red in Fig.17 as an example, the estimated positions after the fingerprint database updating were more in accordance with the motion behavior of the pedestrian since they were more evenly distributed compared with those before the fingerprint database updating. In addition, we took the line segments labeled with ①, ②, and ③ in Fig.18 and Fig.19 as another example. It was found that after the fingerprint database updating, the distribution of the estimated positions changed from disorder to order, which further verified the effectiveness of the proposed fingerprint database updating approach.

Fig.17 Bluetooth positioning on path 1

Fig.18 Bluetooth positioning on path 2

The box-whisker plots of positioning errors on the selected three paths before and afterngerprint database updating are shown in Figs.20-22, where the horizontal and vertical axes stand for the updating times of fingerprint database and positioning errors. With the increase of the number ofngerprint database updating, the median of positioning errors generally decreased, and meanwhile the number of outliers decreased. It demonstrates that the process ofngerprint database updating can help a lot in improving the accuracy of Bluetooth positioning. Moreover, Figs.23-25 show the corresponding three-dimensional stem graphs of positioning errors before and afterngerprint database updating. Here, thex,y, andzaxes stand for the number ofngerprint database updating (including before updating), timestamps of the walking on each path, and positioning errors. Obviously, the increase of the number ofngerprint database updating generally decreased the positioning errors as expected.

Fig.19 Bluetooth positioning on path 3

Fig.20 Box-whisker plot on path 1

Fig.21 Box-whisker plot on path 2

Fig.22 Box-whisker plot on path 3

Fig.23 Positioning errors on path 1

Fig.24 Positioning errors on path 2

Fig.25 Positioning errors on path 3

Finally, the Cumulative Distribution Functions (CDFs) of the positioning errors before and after fingerprint database updating are shown in Fig.26, and the corresponding percentile errors are illustrated in Table 2. From these results, we can find that the process of fingerprint database updating was able to reduce the median of positioning errors from 1.6 m to 1.1 m and tailing error (i.e., 90% error) from 6.0 m to 2.8 m. Meanwhile, the fourth and fifth updates had little effect on the positioning accuracy of fingerprint database. Therefore, when the amount of updated data is sufficient and there are enough candidate fingerprints at each RP, the positioning errors fluctuate near the optimal result.

Fig.26 CDFs of positioning errors

Table 2 Positioning errors under different percentile values

5 Conclusions

Aiming at the purpose that the fingerprint database needs to be updated from the change of environment to improve indoor Bluetooth positioning accuracy, this paper proposes a new system which depends on the crowdsourced data to achieve the adaptive fingerprint database updating. Experimental results show that the proposed system can update fingerprint database in the constantly-changing signal environment with high positioning accuracy. In addition, the proposed system uses positioning result to update fingerprint database without the manual effort of re-collecting the location fingerprints at each RP. Compared with the conventional fingerprint database updating systems which require the participation of professionals, the proposed system has high positioning accuracy, needs low manpower, and is easier to operate. However, the way to simultaneously construct and update the fingerprint database in a cost-efficient manner forms an interesting future research direction.