Feature Learning for Fingerprint-Based Positioning in Indoor Environment

Abstract

Recent years have witnessed a growing interest in using Wi-Fi received signal strength for indoor fingerprint-based positioning. However, previous study about this problem has primarily faced two main challenges. One is that positioning fingerprint feature using received signal strength is unstable due to heterogeneous devices and dynamic environment status, which will greatly degrade the positioning accuracy. Another is that some improved positioning fingerprint features will suffer the curse of dimensionality in online positioning. In this paper, we designed a novel positioning fingerprint feature using the segment similarity of Wi-Fi access points, considering both the received signal strength value and the Wi-Fi access point. Based on this designed fingerprint feature, we proposed a two-stage positioning algorithm for indoor fingerprint-based positioning. Experiment results indicate that our proposed positioning methodology can not only achieve better positioning performance but also consume less positioning time compared to three baseline methods.

1. Introduction

Indoor location-based services are attracting more and more attention with the increasing popularity of mobile devices [1, 2] and the rapid development of mobile marketing [3]. Location is essential context information for many indoor location-based services, such as mobile social network [4] and Lifemap [1]. Since the global positioning system signal cannot penetrate indoor buildings and the positioning accuracy of cellular-based method is too low [5], the main outdoor positioning methods are not suitable for indoor positioning. Recently, indoor positioning scheme based on WLAN technology has attracted extensive attention, because of the widespread deployment of WLAN infrastructures and most mobile devices (i.e., smart phone, tablet and PDA, etc.) being equipped with Wi-Fi interface.

Previous positioning methods using Wi-Fi technology are based on geometric properties of triangles [6, 7], which evaluated the location of unknown point with three known reference points. In general, the Wi-Fi network access points (APs) usually work as reference point and three methods can be used to evaluate the distance between unknown point and reference point, namely, received signal strength indicator (RSSI) [8, 9], angle of arrival [10], and time of arrival [11]. However, positioning methods using angle or time of arrival need special hardware to accurately measure the arrival time or angle, which is impractical for common devices. Since Wi-Fi RSSI is affected by many factors (e.g., interior layout, people walking, and weather conditions), the positioning accuracy is very low for triangulation-based positioning using RSSI [12].

Fortunately, fingerprint-based positioning scheme [13] using Wi-Fi RSSI has proved to have better performance and attracted extensive attention in recent years. Typically, this kind of positioning method includes two steps, namely, offline constructing positioning fingerprint map and online positioning. For constructing positioning fingerprint map, the indoor space will be firstly divided into several small cells; then some expert surveyors will collect the Wi-Fi RSSI of each cell as its positioning fingerprint. In online positioning, comparing the positioning fingerprint of unknown location with fingerprint map using specific matching algorithm, finally, the location with the best match will be chosen as the positioning result.

However, previous indoor fingerprint-based positioning scheme faces two major challenges. One is that constructing the fingerprint map is time-consuming and needs to be updated dynamically for maintaining positioning accuracy. Previous literature has proposed some effective solutions to address this challenge. For instance, Bayesian regression [14], compress sensing [15], spatial-temporal correlation model [16], and triangulation-based [17] positioning have been used to dynamically calibrated fingerprinting map. Another challenge is that the Wi-Fi RSSI is very unstable [18, 19], which will dramatically decrease the positioning accuracy. According to Zheng et al. [20], current solutions for this problem can be mainly divided into two categories; one is manual calibration approach based on device mapping and the other is calibration-free approach based on new positioning fingerprint. The manual calibration approach uses an additional learning phase to find the linear transformation between the survey device and the test device, which is impractical for increasing new devices. On the contrary, the calibration-free approach constructs a new positioning fingerprint to solve the RSSI variance, such as DIFF [21] and HLF [22].

As for a classification task [23], the keys to successful fingerprint-based positioning are (i) the design of suitable classifiers and (ii) appropriately designed positioning fingerprint feature. Since Wi-Fi RSSI is unstable and variable, positioning fingerprint based on raw Wi-Fi RSSI has become the bottleneck for further improving the positioning accuracy. For solving this problem, we firstly observed and analyzed some inherent characteristics of Wi-Fi RSSI. Based on the analysis, we designed a new positioning fingerprint feature using the segment similarity of Wi-Fi APs, which is more stable and robust than the raw RSSI. We also proposed a two-stage positioning algorithm based on the designed fingerprint feature. To evaluate the performance of our proposed method, we defined a case study in the Zhejiang University City College (ZUCC) and have done several experiments at several floors. Experimental results indicate that our proposed method can not only achieve better positioning performance but also be less time-consuming compared to three baseline methods.

The rest of this paper is organized as follows. Section 2 firstly introduces related work about Wi-Fi-based indoor positioning. Section 3 describes our designed positioning fingerprint feature in detail. Section 4 introduces the proposed two-stage positioning algorithm using our designed positioning feature. Section 5 reports and discusses our experimental results. Finally, we present our conclusions and future works in Section 6.

2. Related Work

In this section, we survey some studies that address indoor positioning using Wi-Fi RSSI. Since triangulation-based method using Wi-Fi RSSI typically has large positioning error (usually larger than 10 m [24]), which is unacceptable for many indoor location-based applications, therefore we focus on discussing fingerprint-based method and analyze how these studies differ from our work.

Fingerprinting-based method is proposed to improve the positioning accuracy by using statistical theory. In offline training phase, the received Wi-Fi RSSI from surround environment is selected as the classification feature. Then, online positioning usually uses a classification model for positioning, such as KNN [8], neural network [25], and Adaboost [26]. In addition, several methods have been proposed instead of traditional classification model for reducing computational burden [27, 28] or improving positioning accuracy [9].

However, the positioning accuracy of fingerprinting-based positioning method will degrade significantly [20, 29] due to Wi-Fi RSSI variation caused by many factors [19], such as indoor building layout, the mobility of people, and even the weather conditions. Existing techniques for solving this variation problem can be divided into three categories.

2.1. Construct Robust Positioning Fingerprint Feature

The basic idea of this technique is to design new robust positioning fingerprint feature instead of the raw Wi-Fi RSSI to reduce the impact of variation. Currently, the proposed feature can be divided into two categories.

2.1.1. Positioning Fingerprint Feature Using Wi-Fi RSSI

This kind of feature only used Wi-Fi RSSI information to extract positioning fingerprint feature. For instance, Dong et al. [30] utilized the RSSI differences between pairs of Wi-Fi APs instead of raw RSSI as fingerprinting feature. Kaemarungsi and Krishnamurthy [31] utilized the ratio of RSSI as fingerprint feature to overcome the variation challenge. Unfortunately, this kind of feature will suffer the curse of dimensionality [20] in online positioning. Moreover, this kind of feature may lose the discriminative information related to homogeneous devices, since it constructs new fingerprint instead of the raw RSSI.

2.1.2. Positioning Fingerprint Feature Using Multidimensional Information

This kind of feature constructs novel fingerprint feature based on Wi-Fi RSSI and other information, such as magnetic field [32, 33], Bluetooth [34, 35], UWB signaling [36], and inertial sensors [37]. Specifically, these features usually use particle filter [26, 36, 38] or Kalman filter [39] to fuse Wi-Fi RSSI and other information. However, this approach is unreliable due to being heavily affected by motion estimation errors and has strong restrictions on smart phone, such as fixed phone orientation.

2.2. Design Novel Online Positioning Method

This kind of technique aims to use an additional learning phase to reduce the RSSI variation among heterogeneous devices. Zou et al. [40] used online sequential extreme learning machine to address the RSSI variation caused by environmental dynamics. Chen et al. [41] proposed a fuzzy logic-based system to solve this problem. Suárez et al. [42] proposed a linear regression model to predict Wi-Fi RSSI with considering different situations (e.g., heterogeneous devices, drivers, and operating systems). Obviously, this approach is impractical for rapidly increasing new kinds of devices.

3. Fingerprint Learning for Indoor Positioning

Due to lack of standardization and normalization in hardware and software, Wi-Fi RSSI scanned at the same location may be significantly different for diverse devices.

3.1. Observation and Analysis of Wi-Fi RSS Characteristics

We can observe clearly the variation between three different devices (GT-I19308, MI 2S, and P6-T00) in Figure 1(a). Additionally, the environment status changes, such as when some Wi-Fi APs may become invalid or people walk around, can also lead the scanned RSSI to be inconsistent at offline phase and online phase, which is shown in Figure 1(b), and it can be seen clearly that the five records collected at different time in a fixed location are variable. Therefore, fingerprint-based method using raw RSSI will suffer a significant positioning error due to the variation.

Figure 1

The RSS variance caused by diverse devices (a) and environment changes (b).

We observed that the Wi-Fi access points in different ranges in a fixed location are very consistent and stable, which we called the segmentation similarity of Wi-Fi access points (SSAP). For instance, the SSAP of Figures 1(a) and 1(b) are described in Tables 1 and 2, respectively. Table 1 shows that the three records scanned by different devices can be divided into three segments by the RSSI range; the Wi-Fi APs for each segment are the same; for example, the Wi-Fi APs in [−65, −54] are ${A P_{6}, A P_{7}}$ for all records. The same situation is shown in Table 2; all the five records scanned at different times can be divided into 3 segments and the APs of each segment are the same.

Table 1

The SSAP of Figure 1(a).

The RSS range	$[- 65, - 54]$	$[- 75, - 67]$	$[- 100, - 81]$
GT-I9308	$\{A P_{6}, A P_{7}\}$	$\{A P_{4}, A P_{9}\}$	$\{{AP}_{1}, {AP}_{2}, {AP}_{3}, {AP}_{5}, {AP}_{8}, {AP}_{10}, {AP}_{11}, {AP}_{12}, {AP}_{13}, {AP}_{14}, {AP}_{15}\}$
MI 2S	$\{A P_{6}, A P_{7}\}$	$\{A P_{4}, A P_{9}\}$	$\{{AP}_{1}, {AP}_{2}, {AP}_{3}, {AP}_{5}, {AP}_{8}, {AP}_{10}, {AP}_{11}, {AP}_{12}, {AP}_{13}, {AP}_{14}, {AP}_{15}\}$
P6-T00	$\{A P_{6}, A P_{7}\}$	$\{{AP}_{5}, A P_{9}\}$	$\{{AP}_{1}, {AP}_{2}, {AP}_{3}, {AP}_{4}, {AP}_{8}, {AP}_{10}, {AP}_{11}, {AP}_{12}, {AP}_{13}, {AP}_{14}, {AP}_{15}\}$

Table 2

The SSAP of Figure 1(b).

The RSS range	$[- 53, - 49]$	$[- 82, - 69]$	$[- 100, - 89]$
$S 1$	$\{A P_{5}, A P_{6}\}$	$\{A P_{1}, A P_{2}, A P_{3}, A P_{4}, A P_{10}, A P_{11}, A P_{12}, A P_{13}, A P_{14}, A P_{15}\}$	$\{A P_{7}, A P_{8}, A P_{9}\}$
$S 2$	$\{A P_{5}, A P_{6}\}$	$\{A P_{1}, A P_{2}, A P_{3}, A P_{4}, A P_{10}, A P_{11}, A P_{12}, A P_{13}, A P_{14}, A P_{15}\}$	$\{A P_{7}, A P_{8}, A P_{9}\}$
$S 3$	$\{A P_{5}, A P_{6}\}$	$\{A P_{1}, A P_{2}, A P_{3}, A P_{4}, A P_{10}, A P_{11}, A P_{12}, A P_{13}, A P_{14}, A P_{15}\}$	$\{A P_{7}, A P_{8}, A P_{9}\}$
$S 4$	$\{A P_{5}, A P_{6}\}$	$\{A P_{1}, A P_{2}, A P_{3}, A P_{4}, A P_{10}, A P_{11}, A P_{12}, A P_{13}, A P_{14}, A P_{15}\}$	$\{A P_{7}, A P_{8}, A P_{9}\}$
$S 5$	$\{A P_{5}, A P_{6}\}$	$\{A P_{1}, A P_{2}, A P_{3}, A P_{4}, A P_{10}, A P_{11}, A P_{12}, A P_{13}, A P_{14}, A P_{15}\}$	$\{A P_{7}, A P_{8}, A P_{9}\}$

To verify whether the SSAP is universal to different devices, we have evaluated our dataset using the similarity of RSSI histogram bins. Firstly, we grouped each sample using K-means for drawing the histogram bins. Secondly, we calculated the similarity distance of two histogram bins according to Bhattacharyya distance [43]. The calculation process includes two steps.

Step 1.

Calculate the bin similarity, as shown in (1). The bin similarity considers the Wi-Fi APs similarity using Jaccard distance:

\begin{matrix} S i m (H_{1}^{i}, H_{2}^{i}) = \frac{|s (H_{1}^{i}) \cap s (H_{2}^{i})|}{|s (H_{1}^{i}) \cup s (H_{2}^{i})|}, \end{matrix}

(1)

where

s (H_{1}^{i})

and

s (H_{2}^{i})

are the Wi-Fi APs of bins

H_{1}^{i}

and

H_{2}^{i}, 1 \leq i \leq N

, and N is the number of histogram bins.

Step 2.

Calculate the histogram similarity distance, as shown in

\begin{matrix} S i m (H_{1}, H_{2}) = W \cdot \sqrt{1 - \sum_{i} \frac{\sqrt{H_{1}^{i} \cdot H_{2}^{i}}}{\sqrt{\sum_{i} H_{1}^{i} \cdot \sum_{i} H_{2}^{i}}}}, \end{matrix}

(2)

where

H_{1}

and

H_{2}

are the two histograms,

1 \leq i \leq N

, and W represents the bin similarity, as shown in

\begin{matrix} W = \frac{\sum_{i} S i m (H_{1}^{i}, H_{2}^{i})}{N} . \end{matrix}

(3)

The evaluation dataset includes 1179 Wi-Fi RSSI samples for 393 locations in total, and each location includes 3 samples scanned by 3 different devices (GT-I9308, Huawei, and MI 2S). Then, we calculated the histogram bins similarity distance of RSSI according to (2). Figure 2 shows cumulative distribution function (CDF) of histogram bins distance with different devices. For the three devices, we can see that the histogram bins similarity distance less than 0.2 holds for more than 94.7% in total samples, which indicates that the SSAP is universal to heterogeneous devices.

Figure 2

The cumulative distribution function (CDF) for RSSI histogram bins distance.

3.2. Fingerprint Feature Design for Indoor Positioning

In view of the above analysis, this paper designed a new fingerprint feature based on the segmentation similarity of Wi-Fi access points according to the scanned Wi-Fi RSSI. Our designed feature does not require prearranged special Wi-Fi APs and instead only utilizes the scanned Wi-Fi information of surround environment. The fingerprint feature design is formally described as follows.

Definition 1 (location).

The physical space of an indoor building is divided into a set of small grids, which are represented as $L = {L_{1} (x_{1}, y_{1}), L_{2} (x_{2}, y_{2}), \dots, L_{i} (x_{i}, y_{i}), \dots, L_{N} (x_{N}, y_{N})}$ , where $(x_{i}, y_{i})$ is the two-dimensional coordinate of location $L_{i}, 1 \leq i \leq N$ .

Definition 2 (raw RSSI).

The scanned raw RSSI of location $L_{i}$ is represented as $T_{i} = {(R_{1}^{i}, A P_{1}), (R_{2}^{i}, A P_{2}), \dots, (R_{j}^{i}, A P_{j}), \dots, (R_{m}^{i}, A P_{m})}$ , where $R_{j}^{i}$ is the detected RSSI from Wi-Fi $A P_{j}$ at location $L_{i}, 1 \leq i \leq N, 1 \leq j \leq m$ . Specifically, the collected dataset for all locations is represented as $T = {T_{1}, T_{2}, \dots, T_{i}, \dots, T_{N}}$ .

Algorithm 1 describes the framework for designing the fingerprint feature SSAP; the basic idea is to group the Wi-Fi APs with similar RSSI together. Firstly, as showed in Lines (2)~(4) of Algorithm 1, we sorted descending raw RSSI $T_{i}$ . Secondly, we split the sorted $T_{i}$ to several small segments, as depicted in Lines (5)~(14) of Algorithm 1. The split principle is that if the difference of two adjacent RSSI is large enough (e.g., larger than a threshold α), then the index between the two adjacent RSSI is chosen as the split location. This is according to the fact that the scanned RSSI from Wi-Fi AP may change by diverse devices or at different times in a fixed location, but the variance of RSSI is usually in a small range. Each segment is represented as triple-array $S = {R_{i}^{l e f t}, R_{i}^{r i g h t}, ({A P}_{l e f t}, \dots, {A P}_{r i g h t})}$ , where $({A P}_{l e f t}, \dots, {A P}_{r i g h t})$ represent all the Wi-Fi APs whose RSSI is between $R_{i}^{l e f t}$ and $R_{i}^{r i g h t}$ , where $R_{i}^{l e f t}, R_{i}^{r i g h t}$ are the RSSI of the start and end AP of segment S, respectively. Finally, we regarded all the segments represented with triple-array as fingerprint feature. Taking record $S 1$ in Table 2 as an example, the scanned raw RSSI is $T_{S 1} = {(- 75, {A P}_{1}), (- 76, {A P}_{2}), (- 75, {A P}_{3})$ , $(- 74, {A P}_{4}), (- 49, {A P}_{5}), (- 49, {A P}_{6}), (- 95, {A P}_{7}), (- 95, {A P}_{8}), (- 95, {A P}_{9}), (- 73, {A P}_{10}), (- 73, {A P}_{11}), (- 74, {A P}_{12})$ , $(- 76, {A P}_{13})}$ . In Step 1, we sorted descending $T_{S 1}$ by the RSSI values, and the sorted record is represented as $s o r t (T_{S 1}) = {(- 49, {A P}_{5}), (- 49, {A P}_{6}), (- 73, {A P}_{10}), (- 73, {A P}_{11}), (- 74, {A P}_{4}), (- 74, {A P}_{12}), (- 75, {A P}_{1}), (- 75, {A P}_{3})$ , $(- 76, {A P}_{2}), (- 76, {A P}_{13}), (- 95, {A P}_{7}), (- 95, {A P}_{8}), (- 95, {A P}_{9})}$ . Then, we divided $s o r t (T_{S 1})$ into several segments with a threshold $α = 12$ . Therefore, two split locations are selected; one is the index between $(- 49, {A P}_{6})$ and $(- 73, {A P}_{10})$ and another is the index between $(- 76, {A P}_{13})$ and $(- 95, {A P}_{7})$ . Finally, $s o r t (T_{S 1})$ is divided into three segments according to the two split locations, and the triple-array representation is $f_{S 1} = {[- 49, - 49, ({A P}_{5}, {A P}_{6})], [- 73, - 76, ({A P}_{10}, {A P}_{11}, {A P}_{4}, {A P}_{12}, {A P}_{1}, {A P}_{3}, {A P}_{2}, {A P}_{13})],$ $[- 95, - 95, ({A P}_{7}, {A P}_{8}, {A P}_{9})]}$ , which is regarded as the fingerprint feature of raw RSSI record $S 1$ .

Algorithm 1: Positioning fingerprint feature design.

Input: The collected raw dataset $T = {T_{1}, T_{2}, \dots, T_{i}, \dots, T_{N}}$ , where

$T_{i} = {(R_{1}^{i}, A P_{1}), (R_{2}^{i}, A P_{2}), \dots, (R_{j}^{i}, A P_{j}), \dots, (R_{m}^{i}, A P_{m})}$ and represent all the

scanned Wi-Fi RSSI values at location $L_{i}$ , $i = 1,2, \dots, N$ and $j = 1,2, \dots, m$ .

Output: The SSAP Positioning Fingerprint Map $F = {f_{i}, f_{2}, \dots, f_{i}, \dots, f_{N}}$

(1) Initialize $F = ⌀$ and the similarity threshold α.

(2) for $i = 1 \to N$ do

(3) Obtain all the scanned AP mun m at location $L_{i}$

(4) Sort Descending $T_{i}$ by the RSSI

(5) for $j = 1 \to m$ do

(6) Set $left \leftarrow j$

(7) for $k = j + 1 \to m$ do

(8) Compute the absolute difference $d = ‖ R_{j}^{i} - R_{k}^{i} ‖$

(9) Repeat Step (7) until $d > α$ , Set $right \leftarrow k$

(10) Set $S \leftarrow {R_{i}^{left}, R_{i}^{right}, ({AP}_{left}, \dots, A P_{right})}$

(11) Add S to $f_{i}$

(12) Set $j \leftarrow right + 1$ , go to Step (5)

(13) end for

(14) end for

(15) Add $f_{i}$ to F

(16) end for

From the above example, we can see that the designed fingerprint feature cluster Wi-Fi APs to similar RSSI. Therefore, it is more stable than the raw RSSI for small variance. Additionally, the dimension of our designed fingerprint feature is limited (usually less than 10). On the other hand, the designed fingerprint feature can utilize all the scanned Wi-Fi as information rather than just selecting a subset of Wi-Fi APs for positioning, which means that our method does not need prearranged Wi-Fi infrastructure for indoor positioning.

4. Positioning Algorithm Using SSAP Feature

Based on the designed fingerprint feature in Section 3.2, we proposed a two-stage positioning algorithm as described in Algorithm 2. The first stage of this positioning algorithm is to select a candidate set based on the similarity of SSAP fingerprint feature; thus the relatively close locations have more probability to be selected into the same candidate set. The second stage evaluates positioning result by the RSSI similarity for all elements in the candidate set. We will define clearly the similarity of the SSAP fingerprint feature and the raw RSSI positioning fingerprint as follows.

Algorithm 2: Two-stage positioning algorithm using SSAP fingerprint.

Input: The SSAP Positioning Fingerprint Map $F = \{f_{i}, f_{2}, \dots, f_{i}, \dots, f_{N}\}$ ,

the SSAP Fingerprint $f_{x}$ need to be positioned.

Output: The location $\hat{l o c}$ that $f_{x}$ was collected.

(1) Initialize fragmentation threshold β, $\max = 0$ , $sum = 0$ , $S = ⌀$

(2) for $i = 1 \to N$ do

(3) Set p ← the segments of $f_{i}$

(4) Set q ← the segments of $f_{x}$

(5) Set $k \leftarrow \min (p, q)$

(6) Set $sum \leftarrow 0$

(7) for $j = 1 \to k$ do

(8) Set $v_{j} \leftarrow (R_{j}^{right} + R_{j}^{left}) / 2$

(9) Set $v_{x} \leftarrow (R_{x}^{right} + R_{x}^{left}) / 2$

(10) if $|v_{j} - v_{x}| < β$ then

(11) Compute Jacob Distance $dist = |(s_{i}^{j} \cap s_{i}^{x}) / (s_{i}^{j} \cup s_{i}^{x})|$

(12) $sum \leftarrow sum + dist$

(13) end if

(14) end for

(15) if $sum > \max$ then

(16) $\max \leftarrow sum$

(17) $S \leftarrow {loc}_{i}$

(18) end if

(19) end for

(20) if $S . length > 0$ then

(21) Initialize $\min = 100 * S . length$

(22) for $j = 1 \to S . length$ do

(23) $d = |{RSS}_{S_{j}} - {RSS}_{f_{x}}|$

(24) if $d < \min$ then

(25) $\min \leftarrow {RSS}_{S_{j}}$

(26) $\hat{l o c} \leftarrow {loc}_{i}$

(27) end if

(28) end for

(29) end if

Definition 3 (the similarity of SSAP fingerprint feature).

The similarity of two SSAP features $f_{i}$ and $f_{j}$ is calculated in (4). Consider the following:

\begin{matrix} s i m (f_{i}, f_{j}) = \sum_{k = 1}^{l e n} s i m (s_{i}^{k}, s_{j}^{k}), \end{matrix}

(4)

where

l e n

is the minimal length of positioning features

f_{i}

and

f_{j}

; the similarity of two small segments

s_{i}^{k}

and

s_{j}^{k}

is defined as their Jacob Distance, which is shown in (5). Consider the following:

\begin{matrix} s i m (s_{i}^{k}, s_{j}^{k}) = \{\begin{cases} |\frac{(s_{i}^{j} \cap s_{i}^{x})}{(s_{i}^{j} \cup s_{i}^{x})}|, & if |u_{j} - u_{i}| < β, \\ 0, & otherwise, \end{cases} \end{matrix}

(5)

where

u_{j} = (s_{j}^{k} {r i g h t} + s_{j}^{k} {l e f t}) / 2, u_{i} = (s_{i}^{k} {r i g h t} + s_{i}^{k} {l e f t}) / 2

Definition 4 (the similarity of raw RSSI fingerprints).

The similarity calculation of two raw RSSI features $R S S_{i}$ and $R S S_{j}$ fingerprints is shown in (6). Consider the following:

\begin{matrix} s i m (R S S_{i}, R S S_{j}) = \sqrt{\sum_{k = 1}^{m} {({R S S}_{i}^{k} - {R S S}_{j}^{k})}^{2}} . \end{matrix}

(6)

At stage one, the closest one or more matches in positioning fingerprint map are selected as candidate set according to the similarity of SSAP fingerprint feature, as shown in Lines (1)~(19) of Algorithm 2. Then, if there is more than one element in the candidate set, the final positioning result is obtained according to the similarity of raw RSSI, as depicted in (20)~(29) of Algorithm 2.

5. Experiment Evaluation

5.1. Experiment Setup

For evaluating the performance of the proposed methodology, we conducted several experiments in three floors (2nd floor, 4th floor, and 5th floor) of the science building at Zhengzhou University City College (ZUCCHINI). Each floor is divided into 131 grids and the mean distance between two grids is 1.5 meters, most of the grids are in the corridor and some are in classroom or laboratory, and the detailed layouts of these grids are shown in Figure 9. In our experiment, three different mobile phones are used to collect Wi-Fi RSSI and the device details are shown in Table 3. We further programmed a mobile APP to scan the surrounding Wi-Fi RSSI based on Android PI once every 0.2 seconds. Each collected record includes three fields of information: the mobile phone's MAC address, the MAC addresses and RSSI of all scanned Wi-Fi APs, and the collection time.

Table 3

Mobile phones used for experiment.

Devices	Manufacturer	Embedded OS
GT-I9308	Samsung Electronics	Android 4.0
P6-T00	Huawei	Android 4.2
MI 2S	Xiaomi Tech	Android 4.1

In the offline phase, we collected the experiment data for constructing positioning fingerprint map on each floor and the dataset is shown in Table 4. It can be seen that the number of scanned Wi-Fi APs is different for each floor and usually not all the Wi-Fi APs can be detected in each scan. For undetected AP, its RSS value is set to 100 (dBm). We used 66% collected records (TrainSet) for constructing the fingerprint map in offline phase and 34% collected records (TestSet) for evaluating performance in online positioning phase.

Table 4

Experiment data description.

	APs number	TrainSet	TestSet	Dataset
2nd floor	28	1281	660	1941
4th floor	37	1280	660	1940
5th floor	24	1277	658	1935

5.2. Experiment Results and Discussion

In these experiments, we compared our proposed positioning methodology with three baseline methods: (1) RAW-NN, which uses the raw RSSI as positioning fingerprint feature; (2) DIFF-NN [21], which uses the difference of RSSI between each pair of Wi-Fi APs as positioning fingerprint feature; and (3) HLF-NN [31], which uses the ratio of RSSI between each pair of Wi-Fi APs as positioning fingerprint feature. The evaluation metric includes positioning error and positioning time. The positioning error is defined as the Euclidean distance between the estimated location and the actual location, and the positioning time refers to the positioning time of online positioning phase.

5.2.1. Evaluation of Positioning Error

Figure 3 shows the cumulative distribution function (CDF) of positioning error for the second floor (2nd floor) by the three positioning methods, respectively. In this figure, we can see that the proposed two-stage positioning algorithm using SSAP fingerprint feature outperforms the other two methods. More exactly, our method achieved the best positioning performance and the second is DIFF-NN, while the worst performance is achieved by RAW-NN. For instance, the probability of error distance under 3 meters is 87% by our method, 76% by DIFF-NN, and 64% by RAW-NN. Figures 4 and 5 show the CDF of the fourth floor (4th floor) and fifth floor (5th floor), respectively. It can be seen that our method performs the best among the three algorithms in total. In Figure 4, the positioning performance for error distance more than 4.5 meters is quite close for SSAP-NN and DIFF-NN. In Figure 6, the curves of all methods are very close for the positioning error distance less than 3 meters.

Figure 3

The cumulative error distribution of 2nd floor.

Figure 4

The cumulative error distribution of 4th floor.

Figure 5

The cumulative error distribution of 5th floor.

Figure 6

The cumulative error distribution of all floors.

We combined the three datasets to evaluate the whole positioning performance and the different number of Wi-Fi APs for the combined dataset is 49. Similarly, we used 66% (3838 records) of data for training model and the remaining 34% (1978 records) of data for validating the performance. The CDF is shown in Figure 6; obviously, SSAP-NN achieved the best positioning performance. Consider the 80% probability of CDF as an example; the SSAP-NN algorithm has an error distance under 4 meters. In contrast, the error distances by DIFF-NN and RAW-NN are 4.5 meters and 5.5 meters for the same probability, respectively.

Figure 7 shows the mean positioning error distance by the four methods. It can be seen that our proposed method achieves minimum mean positioning error for all the experiment scenarios. Specifically, the mean positioning error distance by SSAP-NN for all experiment scenarios is 2.12 meters; the positioning performance increases more than 13% compared to DIFF-NN and HLF-NN and more than 21% compared to RAW-NN.

Figure 7

Mean positioning error distance.

From the above results, it is clearly indicated that SSAP fingerprint feature performs in more stable and robust way than the other three positioning fingerprints. The reason is that the positioning fingerprint of DIFF-NN, HLF-NN, and RAW-NN is based on the raw RSSI without considering the Wi-Fi APs, which are variable due to heterogeneous devices or dynamic environments. On the contrary, the SSAP fingerprint feature considers both the raw RAW values and the scanned Wi-Fi APs information, which is robust for Wi-Fi RSSI variance in a small range, and all the experiments show the superiority of SSAP-NN.

5.2.2. Evaluation of Positioning Time

In this experiment, we defined the positioning time as the average time in seconds required to obtain the precise location for one positioning fingerprint. Positioning time plays a vital role for a successful indoor positioning system, since less positioning time means less energy consumption for user's mobile device. We used the dataset of the second floor for evaluating the positioning time; one positioning fingerprint includes 28 attributes as described in Table 4. Figure 8 shows the positioning time comparison with different number of instances using the dataset; the running time is obtained after repeating the experiments 10 times on Intel's Core i5 based computer. From Figure 8, it can be seen that SSAP-NN and RSS-NN consume nearly the same positioning time at online positioning, while DIFF-NN and HLF-NN spend much more time for the same test instances. The mean running time for one positioning fingerprint is 18.1 ms (SSAP-NN), 28.1 ms (RSS-NN), 337.2 ms (DIFF-NN), and 393 ms (HLF-NN). That is because the fingerprint feature dimension of SSAP-NN is constant (usually less than 10), and RAW-NN is $O (n)$ for n Wi-Fi APs, while the fingerprint feature dimension of DIFF-NN and HLF-NN is $O (n * n)$ due to calculating the difference or ratio of RSSI between each pair of Wi-Fi APs.

Figure 8

Running time for the three positioning methods.

Figure 9

The indoor layout of the experimental environment.

6. Conclusion

In this paper, we observed that Wi-Fi APs in a small RSSI range at the same location are very consistent and stable, namely, segmentation similarity of Wi-Fi access points (SSAP). Moreover, we evaluated the fact that this SSAP is ubiquitous to different devices based on the similarity of RSSI histogram bins. Then, we firstly designed a novel fingerprint feature using SSAP and proposed a two-stage positioning algorithm for online positioning. The basic advantage of our method is that it is more robust and stable than raw RSSI, which can solve the RSSI variance with a calibration-free approach. In addition, the proposed fingerprint feature has much less dimension than fingerprint feature using the raw RSSI or using the difference of RSSI. Another important advantage of the proposed method is the ability to use all scanned Wi-Fi APs' information instead of only selecting a subset of Wi-Fi APs for indoor positioning. This makes our method suitable for large environment, such as airport or super shopping mall, where the different Wi-Fi APs usually are hundreds but the scanned APs at a location may only include several available APs. Experiments in three floors were conducted, and the results demonstrate that our proposed method performs better than three baseline methods, which not only achieved high positioning accuracy but also consumed less positioning time.

As future work, we plan to improve our indoor positioning system with built-in sensors of mobile devices. Firstly, we will leverage human motions based on built-in sensors to build positioning fingerprint map, which involves intensive costs on manpower and time before. Secondly, we will utilize human motions to calibrate obvious positioning error.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This work has been supported by Hangzhou Key Laboratory for IoT Technology & Application.

References

Chon

Cha

LifeMap: a smartphone-based context provider for location-based services

IEEE Pervasive Computing 2011 10 2 58 67

10.1109/mprv.2011.13

2-s2.0-79954535761

Shin

Chon

Kim

Cha

A participatory service platform for indoor location-based services

IEEE Pervasive Computing 2015 14 1 62 69

10.1109/MPRV.2015.1

2-s2.0-84922792588

Hopkins

Turner

Go Mobile: Location-Based Marketing, Apps, Mobile Optimized Ad Campaigns, 2D Codes and Other Mobile Strategies to Grow Your Business 2012

John Wiley & Sons

Elhamshary

Youssef

Checkinside: a fine-grained indoor location-based social network

Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing

September 2014

ACM

607 618

10.1145/2632048.2632051

2-s2.0-84908583785

Otsason

Varshavsky

LaMarca

De Lara

Accurate GSM indoor localization

UbiComp 2005: Ubiquitous Computing 2005

Springer

141 158

Ren

A rssi localization algorithm and implementation for indoor wireless sensor networks

Adhoc & Sensor Wireless Networks 2014 22 3

Garcia

Tomas

Boronat

Lloret

The development of two systems for indoor wireless sensors self-location

Ad-Hoc and Sensor Wireless Networks 2009 8 3-4 235 258

2-s2.0-77951445148

Górski

Groth

Kulas

Ł.

A multi-building wifi-based indoor positioning system

Proceedings of the 20th International Conference on Microwaves, Radar and Wireless Communications (MIKON ′14)

June 2014

IEEE

1 4

10.1109/mikon.2014.6899970

2-s2.0-84908636824

Le Dortz

Gain

Zetterberg

WiFi fingerprint indoor positioning system using probability distribution comparison

Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP ′12)

March 2012

2301 2304

10.1109/icassp.2012.6288374

2-s2.0-84867621369

10.

Wong

Klukas

Messier

Using WLAN infrastructure for angle-of-arrival indoor user location

Proceedings of the 68th Semi-Annual IEEE Vehicular Technology (VTC ′08)

September 2008

IEEE

1 5

10.1109/vetecf.2008.146

2-s2.0-58149114485

11.

Alavi

Pahlavan

Modeling of the TOA-based distance measurement error using UWB indoor radio measurements

IEEE Communications Letters 2006 10 4 275 277

10.1109/lcomm.2006.1613745

2-s2.0-33645800393

12.

Chang

Rashidzadeh

Ahmadi

Robust indoor positioning using differential Wi-Fi access points

IEEE Transactions on Consumer Electronics 2010 56 3 1860 1867

10.1109/tce.2010.5606338

2-s2.0-78149243430

13.

Kaemarungsi

Krishnamurthy

Modeling of indoor positioning systems based on location fingerprinting

Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′04)

March 2004

IEEE

1012 1022

10.1109/INFCOM.2004.1356988

14.

Atia

M. M.

Noureldin

Korenberg

M. J.

Dynamic online-calibrated radio maps for indoor positioning in wireless local area networks

IEEE Transactions on Mobile Computing 2013 12 9 1774 1787

10.1109/TMC.2012.143

2-s2.0-84880984203

15.

Feng

W. S. A.

Valaee

Tan

Received-signal-strength-based indoor positioning using compressive sensing

IEEE Transactions on Mobile Computing 2012 11 12 1983 1993

10.1109/TMC.2011.216

2-s2.0-84867888352

16.

Zhu

J. Y.

Zheng

A. X.

V. O.

Spatio-temporal (S-T) similarity model for constructing WIFI-based RSSI fingerprinting map for indoor localization

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN ′14)

October 2014

17.

Shen

Zhao

Moscibroda

Lin

J.-H.

Zhao

Experiencing and handling the diversity in data density and environmental locality in an indoor positioning service

Proceedings of the 20th Annual International Conference on Mobile Computing and Networking

September 2014

ACM

459 470

10.1145/2639108.2639118

2-s2.0-84907816846

18.

Fang

S.-H.

Wang

C.-H.

Chiou

S.-M.

Lin

Calibration-free approaches for robust Wi-Fi positioning against device diversity: a performance comparison

Proceedings of the 75th IEEE Vehicular Technology Conference (VTC ′12)

June 2012

Yokohama, China

1 5

10.1109/vetecs.2012.6240088

2-s2.0-84864982559

19.

Lui

Gallagher

Dempster

A. G.

Rizos

Differences in RSSI readings made by different Wi-Fi chipsets: a limitation of WLAN localization

Proceedings of the International Conference on Localization and GNSS (ICL-GNSS ′11)

June 2011

IEEE

53 57

10.1109/icl-gnss.2011.5955283

2-s2.0-80051984844

20.

Zheng

Chen

Weight-RSS: a calibration-free and robust method for wlan-based indoor positioning

International Journal of Distributed Sensor Networks 2015 2015 7

573582

10.1155/2015/573582

21.

Dong

Chen

Liu

Ning

Piao

A calibration-free localization solution for handling signal strength variance

MobileEntity Localization and Tracking in GPS-Less Environments 2009

Springer

79 90

22.

Kjærgaard

M. B.

Indoor location fingerprinting with heterogeneous clients

Pervasive and Mobile Computing 2011 7 1 31 43

10.1016/j.pmcj.2010.04.005

2-s2.0-78650739066

23.

Brunato

Battiti

Statistical learning theory for location fingerprinting in wireless LANs

Computer Networks 2005 47 6 825 845

10.1016/j.comnet.2004.09.004

2-s2.0-14644436970

24.

Chintalapudi

Iyer

A. P.

Padmanabhan

V. N.

Indoor localization without the pain

Proceedings of the 16th Annual Conference on Mobile Computing and Networking

September 2010

ACM

173 184

10.1145/1859995.1860016

2-s2.0-78649291578

25.

Garcia

Martinez

Tomas

Lloret

Wireless sensors self-location in an indoor WLAN environment

Proceedings of the International Conference on Sensor Technologies and Applications (SensorComm ′07)

October 2007

Valencia, Spain

IEEE

146 151

10.1109/sensorcomm.2007.4394912

2-s2.0-46449133306

26.

Sakib

M. S. R.

Quyum

M. A.

Andersson

Synnes

Korner

Improving Wi-Fi based indoor positioning using particle filter based on signal strength

Proceedings of the 9th IEEE International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP ′14)

April 2014

1 6

10.1109/issnip.2014.6827597

2-s2.0-84903724241

27.

Bisio

Lavagetto

Marchese

Sciarrone

Energy efficient wifi-based fingerprinting for indoor positioning with smartphones

Proceedings of the IEEE Global Communications Conference (GLOBECOM ′13)

December 2013

Atlanta, Ga, USA

IEEE

4639 4643

10.1109/GLOCOMW.2013.6855683

28.

Lloret

Tomas

Garcia

Canovas

A hybrid stochastic approach for self-location of wireless sensors in indoor environments

Sensors 2009 9 5 3695 3712

10.3390/s90503695

2-s2.0-70849089573

29.

Farshad

Marina

M. K.

Garcia

F. J.

A microscopic look at WiFi fingerprinting for indoor mobile phone localization in diverse environments

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN ′13)

October 2013

IEEE

1 10

10.1109/ipin.2013.6817920

2-s2.0-84902138489

30.

Dong

Lin

Luo

Zhang

FMA-RRSS: fingerprint matching algorithm based on relative received signal strength in indoor wi-fi positioning

Proceedings of the IEEE 17th International Conference on Computational Science and Engineering (CSE ′14)

December 2014

Chengdu, China

1071 1077

10.1109/cse.2014.212

31.

Kaemarungsi

Krishnamurthy

Analysis of WLAN's received signal strength indication for indoor location fingerprinting

Pervasive and Mobile Computing 2012 8 2 292 316

10.1016/j.pmcj.2011.09.003

2-s2.0-84858151531

32.

Ban

Kaji

Hiroi

Kawaguchi

Indoor positioning method integrating pedestrian Dead Reckoning with magnetic field and WiFi fingerprints

Proceedings of the 8th International Conference on Mobile Computing and Ubiquitous Networking (ICMU ′15)

January 2015

Hakodate, Japan

IEEE

167 172

10.1109/icmu.2015.7061061

33.

Shu

Shen

Zhao

Magicol: indoor localization using pervasive magnetic field and opportunistic wifi sensing

IEEE Journal on Selected Areas in Communications 2015 33 7 1443 1457

10.1109/jsac.2015.2430274

34.

Iglesias

H. J. P.

Barral

Escudero

C. J.

Indoor person localization system through RSSI Bluetooth fingerprinting

Proceedings of the 19th International Conference on Systems, Signals and Image Processing (IWSSIP ′12)

April 2012

IEEE

40 43

2-s2.0-84863950084

35.

Mirowski

T. K.

MacDonald

SignalSLAM: simultaneous localization and mapping with mixed WiFi, bluetooth, LTE and magnetic signals

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN ′13)

October 2013

1 10

10.1109/ipin.2013.6817853

2-s2.0-84902169613

36.

Bargshady

Pahlavan

Alsindi

N. A.

Hybrid WiFi/UWB, cooperative localization using particle filter

Proceedings of the International Conference on Computing, Networking and Communications (ICNC ′15)

February 2015

Garden Grove, Calif, USA

IEEE

1055 1060

10.1109/ICCNC.2015.7069494

37.

Khan

M. I.

Syrjarinne

Investigating effective methods for integration of building's map with low cost inertial sensors and wifi-based positioning

Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN ′13)

October 2013

IEEE

1 8

10.1109/ipin.2013.6817847

2-s2.0-84902147230

38.

Hilsenbeck

Bobkov

Schroth

Huitl

Steinbach

Graph-based data fusion of pedometer and WiFi measurements for mobile indoor positioning

Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing

September 2014

ACM

147 158

10.1145/2632048.2636079

2-s2.0-84908569022

39.

Lee

Cho

Koo

Ryu

Choi

Kim

Kalman filter-based indoor position tracking with self-calibration for RSS variation mitigation

International Journal of Distributed Sensor Networks 2015 2015 10

674635

10.1155/2015/674635

40.

Zou

Jiang

Xie

An online sequential extreme learning machine approach to WiFi based indoor positioning

Proceedings of the IEEE World Forum on Internet of Things (WF-IoT ′14)

March 2014

IEEE

111 116

10.1109/wf-iot.2014.6803130

2-s2.0-84900404092

41.

Chen

Liu

Xiong

Duan

Zhu

A fuzzy similarity elimination algorithm for indoor fingerprint positioning

International Journal of Distributed Sensor Networks 2015 2015 10

753191

10.1155/2015/753191

42.

Suárez

Santana

J. A.

Macias-Lopez

E. M.

Mena

V. E.

Canino

J. M.

Marrero

Rssi prediction in wifi considering realistic heterogeneous restrictions

Network Protocols and Algorithms 2014 6 4 19 40

10.5296/npa.v6i4.6066

43.

Cha

S.-H.

Srihari

S. N.

On measuring the distance between histograms

Pattern Recognition 2002 35 6 1355 1370

10.1016/S0031-3203(01)00118-2

ZBL0997.68123

2-s2.0-0036604863