BigLoc: A Two-Stage Positioning Method for Large Indoor Space

Abstract

With the rapid development of WLAN infrastructure, fingerprint-based positioning using signal strength has become a promising localization solution in indoor space. Commonly fingerprint-based positioning methods face two challenges in large indoor space, one is floor recognition in large building with multifloor, and the other is signal strength variance due to heterogeneous devices and environmental factors. In this paper, we propose a novel two-stage positioning approach to address these challenges of fingerprint-based positioning methods in large indoor space. Firstly, we design a floor-level recognition feature based on WiFi access points and the RSS values to recognize floor. For solving the signal strength variance problem, we propose a new metric to capture the similarity of location fingerprints probability distribution using KL Divergence. To demonstrate the utility of our approach, we have performed comprehensive experiments in a large indoor building.

1. Introduction

With the increasing number of positioning innovations and the popularity of mobile devices, indoor location-based services, that is, indoor navigation [1], recommendation [2], and mobile advertising [3], are expected to witness a significant growth in the next decade. Currently, positioning method using WiFi received signal strength (RSS) has become a promising solution in indoor space, which is mainly attributed to the widespread deployment of WLAN infrastructure. Commonly used methods of indoor positioning using WiFi RSS have mainly gone into two categories. One is geometric positioning scheme (e.g., TOA [4] and AOA [5]), which estimates the unknown location using the geometry relationship between an unknown location and more than two reference locations. Another is fingerprint-based positioning scheme using RSS values [6, 7], which usually includes two steps. (1) Constructing location fingerprint map: typically, the step divides indoor space into a few small grids and associates each grid with the scanned RSS values from surrounding WiFi access points (APs). The RSS values scanned from a grid are regarded as its location fingerprint. (2) Online positioning: this step aims to find the best match between the unknown fingerprint and the fingerprint map. Then, the location of the best match fingerprint is regarded as positioning result. Since geometric positioning scheme lacks scalability because prior knowledge of anchor nodes (AP) or costly infrastructure predeployment is necessary, fingerprint-based positioning scheme has attracted increasing attention due to cost-effectiveness and reasonable positioning accuracy.

Conventional literatures of fingerprint-based positioning mainly focus on two research fields. The first is improving the positioning accuracy by designing robust location fingerprint [8, 9] or using improved online matching algorithm [7, 10, 11]. The other is reducing the enormous cost of constructing fingerprint map, such as using both user motions and RF signal characteristics to construct radio floor plan [12] or constructing fingerprint map by crowdsourcing [13]. However, application scenarios of most existing works are in a small space, and few involved large indoor space with multifloor. Existing fingerprint-based positioning method will suffer significant challenges in large indoor space (e.g., multibuilding or multifloor) due to the following factors:

• (i)

Large indoor space with multifloor usually has hundreds of available WiFi access points (e.g., there are over 200 WiFi APs in our experiment); how to select the RSS values of appropriate APs as location fingerprint is a major challenge.

(ii)

Location fingerprint using numerous WiFi APs will suffer dimension disaster in online positioning, which is time-consuming and energy-consuming for mobile devices. In addition, the RSS variance problem is even more serious in large indoor space due to complex indoor layout or people walk. To address this problem, we design a novel floor-level feature to recognize floor, which is used to reduce the number of APs to be considered in fingerprint-based positioning.

(iii)

Floor-level positioning error will bring a huge impact on overall positioning performance. Typically, meters positioning error is acceptable but floor-level positioning error will significantly reduce users experience.

In this paper, we present a two-stage indoor positioning method for large indoor environment with multifloor. Firstly, we design a floor-level recognition feature to recognize floor by utilizing both WiFi APs information and RSS values. In stage two, we utilize KL Divergence of location fingerprints probability distribution to smooth the RSS variance between heterogeneous devices. In a nutshell, the main contributions of our work are threefold:

• (i)

We study the problem of positioning in complex large indoor environment, which usually includes multifloor and has hundreds of available WiFi APs. We design a novel floor-level feature to recognize floor.

(ii)

We solve the RSS variance problem by using KL Divergence of location fingerprints probability distribution.

(iii)

We establish a real testing environment that includes three floors. Using real world data with over 4000 records, we perform extensive experiments to demonstrate the effectiveness of our proposed method.

The rest of this paper is structured as follows. Section 2 surveys related work on fingerprint-based positioning using WiFi RSS values in indoor space. Section 3 describes our positioning approach in detail. Section 4 reports our experimental result and discussion. Finally, we present our conclusion and future work in Section 5.

2. Related Work

In this section, we survey some commonly used methods for indoor positioning using WiFi RSS as location fingerprint and discuss how these works differ from our work. In general, existing study on this topic can be divided into two categories.

(1) Solutions for Solving WiFi RSS Variance Problem. Due to lack of standard WiFi implementation for diverse mobile devices, the RSS values scanned at the same location may be significantly different, namely, the RSS variance problem [7]. Commonly used methods have proposed several effective solutions to address this problem. For example, Laoudias et al. [14] demonstrated that the RSS difference value is more stable than original RSS values and Dong et al. [8] constructed location fingerprint using the RSS differences between pairs of APs; Mahtab Hossain and Soh [15] further analyzed the Cramer-Rao Lower Bound of positioning error using RSS differences as location fingerprint. In addition, Laoudias et al. [16] proposed a self-calibration solution by fitting a linear mapping between the histograms of fingerprint map; Yang et al. [9] utilized the overall relationships of RSS values to construct fingerprint map; Chen et al. [17] utilized the order of WiFi RSS values to design location fingerprint. However, Park et al. [18] demonstrated that merely linear transformation is not enough for solving linear correlation of RSS values differences and proposed a kernel estimation to reduce positioning error. Deng et al. [19] utilized kernel direct discriminant analysis to extract the nonlinear and uncertainty feature of WiFi RSS values for indoor positioning.

(2) Solutions for Constructing Location Fingerprint Map. Since constructing location fingerprint map is time-consuming and needs to be updated dynamically, some methods have been proposed to automatically construct or dynamically calibrate fingerprinting map. For instance, Yoon et al. [20] utilized the signals transmitted from commercial FM radio stations to estimate RSS distribution; Niu et al. [13] used crowdsourcing way to construct the fingerprint map by recording user motions and WiFi signals; Figuera et al. [21] demonstrated that the time and space sampling rates can be utilized to calibrate the RSS variance among heterogeneous devices; He et al. [22] utilized mutual distance information to fuse noisy fingerprint with a convex-optimization formulation.

Typically, large indoor space with multifloor usually has hundreds of available WiFi APs, which will bring serious challenge for designing appropriate location fingerprint. Recently, several studies are proposed to address indoor multifloor localization; for example, Bozkurt et al. [23] proposed a floor-level localization method by fusing information from WiFi, Bluetooth, and magnetic field measurements, Shen et al. [24] exploited WiFi RSS and barometric pressure for floor-level localization, and Wang et al. [25] proposed a multifloor localization method based on the assumption that the plans of different floors in a building are similar. Table 1 shows the application scenario and experimental environment of a few studies, including localization method for one floor or multifloor. We can see from Table 1 that the application scenarios of most existing studies are usually in a small indoor environment with several available WiFi APs. By contrast, we focus on positioning in large indoor space with multifloor in this study.

Table 1

Application scenarios of some commonly used methods for indoor positioning.

Reference	Floors	Area	Fingerprint	APs	Grids
[8]	1	510 m2	WLAN	7	161
[21]	1	559 m2	WLAN	Unknown	254
[19]	Unknown	192 m2	WLAN	8	100
[17]	One floor	1512 m2	WLAN	15	144
[23]	2	800 m2	WLAN + Bluetooth + magnetic	7	486
[25]	3	2400 m2	WLAN	>200	354
[26]	14	108703 m2	WLAN	520	933

3. Two-Stage Indoor Positioning Method

Typically, large indoor space (e.g., shopping mall, office building, and airport) usually has hundreds of WiFi APs to provide WiFi service. Due to complex propagation effects in indoor environment, the RSS values scanned from a fixed AP may be similar even at different floors. Therefore, conventional fingerprint-based methods may suffer floor-level positioning error in multifloor environment. For solving this problem, our approach designs a floor-level feature to recognize the floor where the user currently located in.

3.1. The First Stage: Floor Recognition

Several factors can influence the propagation of radio signal in multifloor environment, such as multiple diffraction from window frames and reflection of scattered signals from adjacent buildings. Typically, one floor may reduce WiFi RSS values between 15 dBm and 35 dBm [27]. In order to investigate the floor effect for radio signal propagation, we have collected the RSS values from two WiFi APs ( $\mathrm{A}\mathrm{P}\mathrm{1}$ and $\mathrm{A}\mathrm{P}\mathrm{2}$ ) for 153 reference points, where $\mathrm{A}\mathrm{P}\mathrm{1}$ located in floor 1 and $\mathrm{A}\mathrm{P}\mathrm{2}$ located in floor 2. The result of floor effect in our test is shown Table 2. It can be inferred that a user has a great probability of locating in floor 1 if the RSS value of $\mathrm{A}\mathrm{P}\mathrm{1}$ is in [−40, −85], while being in floor 2 if the RSS value of $\mathrm{A}\mathrm{P}\mathrm{2}$ is in [−40, −85].

Table 2

The RSS statistics from two WiFi APs at different floors.

Statistics	AP1 at floor one	AP1 at floor two	AP2 at floor one	AP2 at floor two
$[-\mathrm{55},-\mathrm{40}]$	65	2	5	46
$[-\mathrm{70},-\mathrm{55})$	42	6	11	53
$[-\mathrm{85},-\mathrm{70})$	23	15	21	18
$[-\mathrm{100},-\mathrm{85})$	7	6	8	11

Therefore, we can see that the range of RSS values from a specific AP is useful for floor recognition in Table 2.

3.1.1. Problem Formulation

We design a floor-level feature based on both WiFi APs information and the RSS values to recognize floor. The floor-level feature design is formally described as follows.

Motivated by typical WiFi RSS partition used in literatures [28, 29], we partition the RSS values into 4 levels (as showed in Table 3): level 1, which represents that WiFi signal is excellent and the RSS values are in range [−55, 0]; level 2, which represents that WiFi signal is good and the RSS values are in range [−70, −55); level 3, which represents that WiFi signal is poor and the RSS values are in range [−85, −70); level 4, which represents that WiFi signal is bad and the RSS values are in range [−100, −85).

Table 3

The RSS strength level.

RSS values	Level
$[-\mathrm{55,0}]$	1
$[-\mathrm{70},-\mathrm{55})$	2
$[-\mathrm{85},-\mathrm{70})$	3
$[-\mathrm{100},-\mathrm{85})$	4

Definition 1 (RSS term).

One defines RSS term $R(p,q)$ which represents the scanned signal strength level of $\mathrm{A}{\mathrm{P}}_p$ , $\mathrm{1}⩽p⩽K$ and $\mathrm{1}⩽q⩽\mathrm{4}$ , where K represent the number of all scanned APs in indoor space.

Definition 2 (RSS Term Frequency).

One defines RSS Term Frequency $\mathrm{R}\mathrm{T}\mathrm{F}(i,j)$ as the frequency of RSS term i which appears in floor j. $\mathrm{R}\mathrm{T}\mathrm{F}(i,j)$ is calculated in

$$\begin{array}{cc}& \mathrm{R}\mathrm{T}\mathrm{F}\left(i,j\right)=\frac{n_{i,j}}{{\sum }_{k=\mathrm{1}}^M{n}_{k,j}},\end{array}$$

(1)

where $n_{i,j}$ represent the count of RSS term i which appears in floor j, M is the floors in indoor space, and ${\sum }_{k=\mathrm{1}}^M{n}_{k,j}$ represent the number of all RSS terms appearing in floor j.

Definition 3 (inverse floor frequency).

One defines the inverse floor frequency $\mathrm{I}\mathrm{F}{\mathrm{F}}_i$ to indicate the importance of RSS term i for all floors, and $\mathrm{I}\mathrm{F}{\mathrm{F}}_i$ is calculated in

$$\begin{array}{cc}& \mathrm{I}\mathrm{F}{\mathrm{F}}_i=\log \frac{M}{\mathrm{1}+\left|j,i\in j\right|},\end{array}$$

(2)

where M is the floors of indoor space and $|j,i\in j|$ represent the number of floors that include RSS term i.

Definition 4 (RTF-IFF correlation).

One defines the correlation of RSS term i and floor j as $\mathrm{R}\mathrm{T}\mathrm{F}\text{-}\mathrm{I}\mathrm{F}\mathrm{F}(i,j)$ , which is calculated in

$$\begin{array}{cc}& \mathrm{R}\mathrm{T}\mathrm{F}\text{-}\mathrm{I}\mathrm{F}\mathrm{F}\left(i,j\right)=\mathrm{R}\mathrm{T}\mathrm{F}\left(i,j\right)\times \mathrm{I}\mathrm{F}{\mathrm{F}}_i.\end{array}$$

(3)

Definition 5 (location fingerprint).

The location fingerprint of location $L_i$ is denoted by $\mathrm{L}{\mathrm{F}}_i=\{R_i^{\mathrm{1}},R_i^{\mathrm{2}},\dots ,R_i^j,\dots ,R_i^m\}$ , where $R_i^j$ is the scanned RSS values from WiFi $\mathrm{A}{\mathrm{P}}_j$ at location $L_i$ , m is the number of all scanned APs, and $L_i(x,y,k)$ represents the current location coordinate of the user, where $(x,y)$ is the two-dimensional coordinate of location and k is the floor.

Definition 6 (correlation between location fingerprint and floor).

The correlation between location fingerprint $\mathrm{L}{\mathrm{F}}_i=\{R_i^{\mathrm{1}},R_i^{\mathrm{2}},\dots ,R_i^j,\dots ,R_i^m\}$ and floor f is defined as (4), where $R(j,i)$ is the RSS term of $R_i^j$ :

$$\begin{array}{cc}& \mathrm{C}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\left(\mathrm{L}{\mathrm{F}}_i,f\right)={\displaystyle \sum }_{j=\mathrm{1}}^M\mathrm{R}\mathrm{T}\mathrm{F}-\mathrm{I}\mathrm{F}\mathrm{F}\left(R\left(j,i\right),f\right).\end{array}$$

(4)

Based on the above definition, the problem of floor recognition can be formally described as follows: Given the location fingerprint $\mathrm{L}{\mathrm{F}}_u$ scanned by users mobile device, recognize the floor $F_u$ of the users current location.

3.1.2. Solving Approach

Algorithm 1 describes the approach for recognition of the floor of users current location. First, as showed in Lines $\mathrm{1}~\mathrm{4}$ , we first obtain the RSS term according to 4-level definition in Table 3. Then, we calculate the RTF-IFF correlation of all RSS terms in fingerprint map as showed in Lines $\mathrm{5}~\mathrm{8}$ . Later, we calculate the correlation between users location fingerprint and all floors as shown in Lines $\mathrm{12}~\mathrm{14}$ . Finally, we choose the floor that holds the highest correlation with users location fingerprint as users current floor.

Algorithm 1: Floor recognition algorithm using RTF-IFF correlation.

Require: ( $\mathit{1}$ ) Location Fingerprint Map $\mathrm{L}\mathrm{F}=\left\{{\mathrm{L}\mathrm{F}}_{\mathrm{1}},{\mathrm{L}\mathrm{F}}_{\mathrm{2}},\dots ,{\mathrm{L}\mathrm{F}}_i,\dots ,{\mathrm{L}\mathrm{F}}_N\right\}$ , where

     ${\mathrm{L}\mathrm{F}}_i=\left\{R_i^{\mathrm{1}},R_i^{\mathrm{2}},\dots ,R_i^j,\dots ,R_i^m\right\}$ represents the location fingerprint at $L_i$ , $i=\mathrm{1,2},\dots ,N$

    and   $j=\mathrm{1,2},\dots ,m$ ; ( $\mathit{2}$ ) User's Location Fingerprint ${\mathrm{L}\mathrm{F}}_u=\left\{R_u^{\mathrm{1}},R_u^{\mathrm{2}},\dots ,R_u^j,\dots \right\}$ .

Ensure: Floor ${\widehat{F}}_u$ of user's current location.

  ( $\mathit{1}$ ) for $i=\mathrm{1}$ to N do

  ( $\mathit{2}$ )  Initial $M=\mathrm{Num}({\mathrm{L}\mathrm{F}}_i)$ .

  ( $\mathit{3}$ )  for $j=\mathrm{1}$ to M do

  ( $\mathit{4}$ )   Obtain RSS term $R(i,j)$ according to Table 3.

  ( $\mathit{5}$ )   Calculate $\mathrm{I}\mathrm{F}\mathrm{F}(R(i,j))$ according to (2).

  ( $\mathit{6}$ )   for $f=\mathrm{1}$ to F do

  ( $\mathit{7}$ )    Calculate $\mathrm{R}\mathrm{T}\mathrm{F}(R(i,j),f)$ according to (1).

  ( $\mathit{8}$ )    Calculate $\text{RTF-IFF}(R(i,j),f)$ according to (3).

  ( $\mathit{9}$ )   end for

  ( $\mathit{10}$ )   end for

  ( $\mathit{11}$ ) end for

  ( $\mathit{12}$ ) for $f=\mathrm{1}$ to F do

  ( $\mathit{13}$ )   Calculate $\mathrm{C}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}({\mathrm{L}\mathrm{F}}_u,f)$ according to (4).

  ( $\mathit{14}$ ) end for

  ( $\mathit{15}$ ) return $F_u=\arg \max \mathrm{C}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}({\mathrm{L}\mathrm{F}}_u,f)$ .

3.2. The Second Stage: Indoor Positioning Using WiFi RSS Values

According to [7], one major challenge of fingerprint-based positioning is the RSS variance problem, which means the RSS values collected at the same location may be different due to heterogeneous devices or environmental changes. To illustrate this phenomenon, we perform two experiments as showed in Figures 1 and 2. The device orientations are random when collecting RSS values in the two experiments.

Figure 1

The RSS values scanned by 4 heterogeneous devices at a fixed location.

Figure 2

The RSS histograms of 4 heterogeneous devices with 5 dBm interval.

Figure 1 shows the RSS values collected from a fixed location by 4 heterogeneous mobile devices, each bar in this figure is the average of 100 collected RSS samples with sampling rate of 1 Hz, and we also add standard error to Figure 1. From Figure 1, we can see that the collected RSS values of HTC Desire 816 and GALAXY S4 are very different, which means merely linear transformation is not enough to solve the RSS variance problem among the two devices.

We show the histogram of RSS values with 5 dBm interval from the same AP with 4 devices in Figure 2. It can be seen from Figure 2 that the RSS values difference between MI 2S and MI 3S is smaller, while the RSS values of GALAXY S4 are greatly different from other devices. Therefore, linear transformation is not effective for the RSS variance of GALAXY S4.

Obviously, the RSS values from the same AP at a fixed location are uncertain due to many factors, that is, heterogeneous devices, indoor layout changes, and weather condition. Since Euclidean distance is not enough to measure the similarity of uncertainty data, we use both Euclidean distance and Kullback-Leibler (KL) Divergence [30] to measure the similarity between two location fingerprints.

For location fingerprint $\mathrm{L}{\mathrm{F}}_i=\{R_i^{\mathrm{1}},R_i^{\mathrm{2}},\dots ,R_i^j,\dots ,R_i^m\}$ of location $L_i(x_i,y_i,k)$ , we define $P_j(R_i^j)$ as the probability distribution of RSS value $R_i^j$ from $\mathrm{A}{\mathrm{P}}_j$ in location $L_i(x_i,y_i,k)$ , as shown in

$$\begin{array}{cc}& \overline{P_j}\left(R_i^j\right)=\frac{P_j\left(R_i^j\right)+\delta }{\mathrm{1}+\delta \left|D\right|},\end{array}$$

(5)

where $P_j(R_i^j)$ is defined in (6), $\mathrm{0}<\delta <\mathrm{1}$ :

$$\begin{array}{cc}& P_j\left(R_i^j\right)=\frac{\left|p~D\mid p=R_i^j\right|}{\left|D\right|},\end{array}$$

(6)

where $p~D$ is an observed value of uncertain object D; D represents the possible scanned RSS values (usually in $[-\mathrm{100,0}]$ ) from $\mathrm{A}{\mathrm{P}}_j$ in location $L_i$ .

Since the probability distribution of RSS values from different APs is independent, the probability distribution difference between location fingerprint $\mathrm{L}{\mathrm{F}}_p$ and $\mathrm{L}{\mathrm{F}}_q$ can be calculated using KL Divergence, as showed in

$$\begin{array}{cc}& \mathrm{K}\mathrm{L}\left(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q\right)={\displaystyle \sum }_{i=\mathrm{1}}^N{P}_p\left(R_p^i\right)\log \frac{P_p\left(R_p^i\right)}{P_q\left(R_q^i\right)}.\end{array}$$

(7)

Because KL Divergence is nonsymmetric, we further define the KL distance between $\mathrm{L}{\mathrm{F}}_p$ and $\mathrm{L}{\mathrm{F}}_q$ as showed in

$$\begin{array}{cc}& D_{\mathrm{K}\mathrm{L}}\left(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q\right)=\mathrm{K}\mathrm{L}\left(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q\right)+\mathrm{K}\mathrm{L}\left(\mathrm{L}{\mathrm{F}}_q,\mathrm{L}{\mathrm{F}}_p\right).\end{array}$$

(8)

Then, the overall distance of a pair location fingerprint can be calculated using

$$\begin{array}{cc}& \mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}\left(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q\right)=\lambda D_{\mathrm{K}\mathrm{L}}\left(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q\right)+\left(\mathrm{1}-\lambda \right)D_e\left(\mathrm{L}{\mathrm{F}}_q,\mathrm{L}{\mathrm{F}}_p\right),\end{array}$$

(9)

where $D_e(\mathrm{L}{\mathrm{F}}_p,\mathrm{L}{\mathrm{F}}_q)$ is the Euclidean distance of location fingerprints $\mathrm{L}{\mathrm{F}}_p$ and $\mathrm{L}{\mathrm{F}}_q$ and $\lambda \in [\mathrm{0,1}]$ is a regulator factor, which effects the weight of KL distance and Euclidean distance on location fingerprints.

Our positioning method uses nearest neighbor to estimate location, the coordinate of the best match location fingerprint is regarded as positioning result, and the positioning method details are shown in Algorithm 2.

Algorithm 2: Indoor positioning using nearest neighbor.

Require: ( $\mathit{1}$ ) Location Fingerprint Map $\mathrm{L}\mathrm{F}=\left\{{\mathrm{L}\mathrm{F}}_{\mathrm{1}},{\mathrm{L}\mathrm{F}}_{\mathrm{2}},\dots ,{\mathrm{L}\mathrm{F}}_i,\dots ,{\mathrm{L}\mathrm{F}}_N\right\}$ , where

   ${\mathrm{L}\mathrm{F}}_i=\left\{R_i^{\mathrm{1}},R_i^{\mathrm{2}},\dots ,R_i^j,\dots ,R_i^m\right\}$ represents the location fingerprint at $L_i$ , $i=\mathrm{1,2},\dots ,N$

  and $j=\mathrm{1,2},\dots ,m$ ; ( $\mathit{2}$ ) User's Location Fingerprint ${\mathrm{L}\mathrm{F}}_u=\left\{R_u^{\mathrm{1}},R_u^{\mathrm{2}},\dots ,R_u^j,\dots \right\}$ ;

  ( $\mathit{3}$ ) Regulator factor λ

Ensure: User's current location ${\widehat{L}}_u$ .

  ( $\mathit{1}$ ) for $i=\mathrm{1}$ to N do

  ( $\mathit{2}$ ) Calculate KL distance $D_{\mathrm{K}\mathrm{L}}({\mathrm{L}\mathrm{F}}_i,{\mathrm{L}\mathrm{F}}_u)$ according to (8).

  ( $\mathit{3}$ ) Calculate total distance $\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}({\mathrm{L}\mathrm{F}}_i,{\mathrm{L}\mathrm{F}}_u)$ according to (9).

  ( $\mathit{4}$ ) Update the minimum distance and the corresponding location fingerprint ${\mathrm{L}\mathrm{F}}_i$ .

  ( $\mathit{5}$ ) end for

  ( $\mathit{6}$ ) return ${\widehat{L}}_u=\arg {\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}}_{\mathrm{m}\mathrm{i}\mathrm{n}}({\mathrm{L}\mathrm{F}}_i)$ .

4. Experiment Evaluation

In this section, we report the experimental studies on positioning location in a large indoor space with multifloor. We will first describe the experimental setup and then report and discuss experimental results.

4.1. Experimental Settings and Data Collection

We perform extensive experiments in a large shopping mall with three floors and each floor is about 55 m × 30 m. In each floor, we divided the indoor space into 350 grids and the mean distance between two grids is 2 meters; most grids (about 80%) are in the room and several in the corridor.

We use four kinds of heterogeneous mobile devices (HTC Desire 816, GALAXY S4, MI 2S, and MI 3S) to scan WiFi RSS values and recorded one instance with three-field information: the MAC address of mobile device, the MAC addresses and RSS values of all scanned WiFi APs, and the scan time. In offline phase, we record instances once 1 second in 1 minute window for all grids; then the 60 samples are used to calculate the probability distribution of location fingerprint. We average 60 samples of each grid as its location fingerprint to construct the fingerprint map in offline phase. The details of experimental dataset are shown in Table 4. It can be observed that the WiFi APs of different floors vary significantly and there are 218 WiFi APs in the shopping mall in total.

Table 4

Experimental dataset.

Floor	WiFi APs	Instances
1	97	1400
2	75	1400
3	46	1400

4.2. Experiment Results and Discussion

For evaluating the performance of our proposed method, we compare our methodology with three pervious methods: (1) RSS-NN, which uses the RSS values as location fingerprint and nearest neighbor as online positioning method; (2) DIFF-NN [8], which uses the difference of RSS values within each pair of WiFi APs as location fingerprint; (3) HIST-NN [16], which uses a linear transformation to fit the RSS histograms of heterogeneous devices for solving RSS variance problem.

The floor recognition solution of our approach is shown in Algorithm 1; the other three methods use nearest neighbor to recognize floor. For each floor, 65% of collected instances are used to train recognition model and the remaining 35% instances are used to test performance. Figure 3 shows the floor recognition accuracy for three floors with the four positioning methods, respectively. It can be seen that the proposed floor recognition method achieves better performance than the three methods. Specifically, the average accuracy of our proposed approach is over 90%, about 85% by DIFF-NN and HIST- NN, while being only 82% by RAW-NN.

Figure 3

The floor recognition accuracy.

In addition, we also evaluate the recognition time for the four methods, as showed in Figure 4. In this figure, we can see that DIFF-NN and HIST-NN are very time-consuming compared with our method. The reason is that DIFF-NN will suffer the curse of dimensionality with numerous WiFi APs, the location fingerprint dimension of DIFF-NN is $O(m\ast m)$ , and m is the available APs. Although HIST-NN does not have the curse of dimensionality problem, it needs an additional linear transformation to calibrate the fingerprint map of different devices.

Figure 4

The operation time of floor recognition.

4.2.1. Evaluation of Positioning Accuracy

In this subsection, we describe the experimental settings for mining indoor trajectory using WiFi RSSI including comparative approaches and the evaluation metric.

In order to verify the effect of solving the RSS variance using the four methods, we evaluate the positioning performance with homogeneous and heterogeneous devices in this subsection. We first describe the evaluation metric for positioning performance and then report the results of our proposed and the three baseline methods.

(1) Evaluation Metric. We use localization error to evaluate the positioning results. Assume the coordinate of ground truth location is $L(x_{\mathrm{1}},y_{\mathrm{1}},k_{\mathrm{1}})$ and the coordinate of positioning result is $\widehat{L}(x_{\mathrm{2}},y_{\mathrm{2}},k_{\mathrm{2}})$ ; the localization error E between L and $\widehat{L}$ is calculated as shown in

$$\begin{array}{cc}& E\left(L,\widehat{L}\right)=\sqrt{{\left(x_{\mathrm{1}}-x_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(y_{\mathrm{1}}-y_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left[d\ast \left(k_{\mathrm{1}}-k_{\mathrm{2}}\right)\right]}^{\mathrm{2}}},\end{array}$$

(10)

where $k_{\mathrm{1}}$ and $k_{\mathrm{2}}$ are the floors of L and $\widehat{L}$ , respectively. d is the height of one floor, and we set d = 3 m in our experiment.

(2) Experiment Results. Figures 5 and 6 show the positioning performance with the same devices as both training device and test device. In Figures 5 and 6, we use HTC Desire 816 and MI 2S as training device to construct fingerprint map, respectively. We can see that the positioning performance is similar for the other three methods, which indicate the RSS variance problem can be ignored with homogeneous devices. Our method outperforms other methods in the two experiments. More exactly, three-meter location accuracy of our method is 68%, 61% for DIFF-NN, 58% for HIST-NN, and 55% for RAW-NN. The reason that our method achieves better performance is that the floor accuracy of our method is the highest, as demonstrated in Figure 3.

Figure 5

The cumulative positioning distribution with HTC Desire 816.

Figure 6

The cumulative positioning distribution with MI 2S.

Figure 7 shows the positioning accuracy in meters with using MI 2S as training device and the other three devices as test devices. In this figure, we can see that the average positioning accuracy of RAW-NN is much worse than the other three methods due to the RSS variance problem. In addition, our method performs much better than DIFF-NN and HIST-NN with using HTC Desire 816 and GALAXY S4 as test devices, while it has no significant difference using MI 3S as test devices. The reason is that the RSS variance between MI 2S and the two devices (HTC Desire 816 and GALAXY S4) cannot be solved by linear mapping, while the RSS values difference between MI 2S and MI 3S can be mapped using a linear transformation. Figure 8 shows the positioning accuracy in meters with using HTC Desire 816 as training device and the other three devices as test device. Similarly, RAW-NN achieves the worst performance and our method outperforms the other three methods. The experimental results indicate our method can solve the RSS variances problem even when the variance cannot be mapped using linear transformation.

Figure 7

The localization accuracy with MI 2S acts as training device and the other three devices act as test devices.

Figure 8

The localization accuracy with HTC Desire 816 acts as training device and the other three devices act as test devices.

5. Conclusion

In this paper, a two-stage positioning approach for large indoor space was presented. Firstly, we design a floor-level feature to recognize the floor based on the WiFi APs and RSS values. For solving the RSS variance problem, we utilize the KL Divergence to measure the probability distribution of RSS values and then calculate the location fingerprint similarity using weighted Euclidean distance and KL Divergence. Finally, we test our positioning method in a large indoor building with multifloor and compare our method with three well-known fingerprint-based positioning techniques. Experimental results show that our method can solve the RSS variance problem and effectively recognize floor. More exactly, our method achieves average positioning accuracy of 2.67 m and 95% accuracy of floor recognition with enormous experimental samples.

As future work, we plan to implement some indoor location services (e.g., indoor POI recommendation or mobile advertising) based on our positioning method.