Multifloor Wi-Fi Localization System with Floor Identification

Abstract

Indoor localization is of great importance in pervasive applications and RSS fingerprint is known as a quite effective indoor location method. Floor attenuation might not give enough margin discrepancy to classify two neighboring floors, such as windows nearby or ring structure. Fingerprint location using the nearest Euclidean distance to the reference point can be interfered by the neighboring floor. In this paper, a multifloor localization framework with floor identification is proposed. The discriminative floor model is trained to maximize between-class scatter and floor identification is triggered by stair walk and elevator events. In experiments, a real dataset is collected in the building of six floors to evaluate our method. The results show that our method can identify accurate location in multifloor environment.

1. Introduction

Indoor localization is of great importance in pervasive applications. Most localization methods based on Wi-Fi RSS have been proposed in the past decades [1–5]. Typical procedure of these methods is RSS fingerprints (e.g., Wi-Fi signal strengths from multiple access points) which have been recorded at preset locations and a reference fingerprint database is built. Localization algorithms retrieve the fingerprint database and return the best matched fingerprint as well as its corresponding location. Fingerprint-based indoor localization works well in signal floor environment. However, in multifloor environment, the building architecture is more complex and RSS fingerprint patterns of one floor will be interfered by the neighboring floors, for example, windows nearby or ring structure shown in Figure 9. Therefore, multifloor localization is still a great challenge.

In this paper, a novel and effective multifloor localization scheme is proposed. Our contributions are summarized as follows: firstly, the weakness of fingerprint location without floor identification in multifloor environment is stated and a discriminative floor model is proposed. Secondly, a framework of fingerprint-based location system with floor identification is designed. Floor identification is triggered by stair walk and elevator events. Finally, a real dataset is collected in the building of six floors to evaluate our method. The experiment results show that our method can identify accurate location in multifloor environment.

2. Related Work

Indoor localization researches in multifloor environment always fall into two categories: without floor identification [1, 6–9] and with floor identification [10–13]. Without floor identification methods assume that RSS fingerprints at each floor are quite different or unique and the closest distance to reference fingerprint in natural space can identify the location. Komar and Ersoy [1] used fingerprints and Euclidean distance to location in multifloor environment. Letchner et al. [6] proposed a hierarchical Bayesian network for large-scale wireless localization. The additional information of building graph model, known AP parameters, and motion tracking was required in sensor model learning. Wang et al. [7] coembedded different floors’ data in some common low-dimensional manifold by labeled data on one floor, which assumed that the floor plans in a building are similar. Al-Ahmadi et al. [8] designed a Bayesian graphical model to estimate RSS strength in two-floor environment. There is also other work on how to track in a multifloor building, such as Woodman and Harle [9], who applied IMU sensors to track stair walking.

In floor identification methods, which floor the pedestrian is on is always identified before accurate floor localization. Alsehly et al. [10] found the nearest reference WAP by k-nearest neighbor algorithm to estimate the floor number. Varshavsky et al. [11] designed a GSM fingerprints localization system known as SkyLoc, to identify which floor a mobile phone user is on in multifloor buildings. GSM fingerprints were collected at each floor and floor classification is measured by Euclidean distance between testing fingerprint and training fingerprint. The fingerprint features selected for classification would improve classification accuracy. Liu and Yang [12] estimated floor number according to the average distance to the sampling fingerprints on one floor. Campos et al. [13] used backpropagation artificial neural networks with one competitive layer to identify the floor. However, backpropagation ANNs can suffer from local minima problem [14]. Besides, Ye et al. [15] used the accelerometer to identify the floor level. The stair walking style and velocity are uncertain factors for floor estimation. If a wrong floor level estimation occurs, then the later estimations are also always wrong.

3. Multifloor Localization Framework

Our multifloor localization framework has three main parts: (1) floor identification (blue block in Figure 1), (2) pedestrian state recognition (grey block in Figure 1), and (3) Wi-Fi fingerprint matching (red block in Figure 1). Wi-Fi fingerprint database consists of network identifier (SSID, Sever Set ID), the AP MAC (Medium Access Control) address, and RSS (Received Signal Strength) signal sampled from reference points in each floor. From this sampling database, discriminative floor model has been trained by FLD (Fisher's Linear Discriminant). Acceleration signals are periodically sampled from accelerometer and matched with some pedestrian patterns, such as walk, up- or downstairs, elevator, and stop. While stair walk or elevator pattern is found, the floor that the pedestrian is on might be changed and the floor number should be reestimated by discriminative floor model using runtime Wi-Fi fingerprint. Pedestrian is located by searching the most similar fingerprint among reference fingerprints at one floor using runtime Wi-Fi fingerprint. Detailed descriptions about these three parts in the framework are discussed in the following three sections.

Figure 1

Multifloor localization framework.

4. Floor Identification

4.1. Problems in Multifloor Buildings

Without floor identification methods usually consider that fingerprints collected at the same floor are similar and will group together. However, due to the inherent complexity of radio-wave propagation in indoor environments, such assumption sometimes fails. In multifloor environment, the building architecture is more complex than single floor environment. The RSS from the same AP in two different rooms on the same floor may vary similar to the different floors. In other words, the RSS from neighboring floor can confuse the one from neighboring room in the RSS Euclidean space where most of the fingerprint-based localization methods search nearest neighboring fingerprints [1–3, 6, 7]. Figure 2 shows an example of multifloor environment and Figure 3 shows the RSS fingerprints records from locations A, B, C, D, E, and F from two Wi-Fi APs. Floor classification margin of E and F is not large enough to be separated from upper floor $\left\{\mathrm{A},\mathrm{B}\right\}$ and lower floor $\left\{\mathrm{C},\mathrm{D}\right\}$ .

Figure 2

Example of multifloor environment.

Figure 3

Fingerprints distribution of Figure 2 in Euclidean space.

There is another fact in multifloor environment. A concrete floor may reduce the RSS between 15 dB and 35 dB [16] and the floor attenuation factor (FAF) at locations near to the window frames is about 20 dB [8]. However, RSS values that are scanned by the same devices vary over time at a fixed location [17, 18] since the radio signals are affected due to the environment. The variance of RSS values in this phenomenon can be 10 dB [17]. That is, the rise of RSS values can reduce floor attenuation and makes inference from adjacent floor greater.

4.2. Discriminative Floor Model

Let $r_i$ denote the RSS from $\mathrm{A}{\mathrm{P}}_i$ . A Wi-Fi fingerprint can be defined as a vector

$$\begin{array}{cc}& \overrightarrow{f}=\left\{r_1,\dots ,r_n\right\},\end{array}$$

(1)

where n is the number of APs in a building. The reference fingerprints are collected during the training phase and stored in the Wi-Fi fingerprint database. Fisher's Linear Discriminant (FLD) [19] is a class specific method. It can not only reduce feature dimensionality, but also be made as classifiers in the reduced feature space.

FLD selects W in [19] in such a way that the ratio of the between-class scatter and the within-class scatter is maximized. Let the between-class scatter matrix be defined as

$$\begin{array}{cc}& S_B={\displaystyle \sum }_{i=1}^c{N}_i\left({\mu }_i-\stackrel{-}{\mu }\right){\left({\mu }_i-\stackrel{-}{\mu }\right)}^T\end{array}$$

(2)

and let the within-class scatter matrix be defined as

$$\begin{array}{cc}& S_W={\displaystyle \sum }_{i=1}^c\hspace{0.17em}{\displaystyle \sum }_{{\overrightarrow{f}}_k\in F_i}\left({\overrightarrow{f}}_k-{\mu }_i\right){\left({\overrightarrow{f}}_k-{\mu }_i\right)}^T,\end{array}$$

(3)

where ${\mu }_i$ is the mean of fingerprint vectors in ith floor $F_i$ , $N_i$ is the number of reference points in ith floor $F_i$ , and $\stackrel{-}{\mu }$ is the mean of ${\mu }_i$ . The optimal projection $W_{\mathrm{o}\mathrm{p}\mathrm{t}}$ is chosen to maximize the ratio of the determinant of the between-class scatter matrix of the projected samples to the determinant of the within-class scatter matrix of the projected samples,

$$\begin{array}{cc}& W_{\mathrm{o}\mathrm{p}\mathrm{t}}=\underset{W}{\arg \hspace{0.17em}\max }\frac{\left|W^T{S}_{B}W\right|}{\left|W^T{S}_{W}W\right|}.\end{array}$$

(4)

The solution of $W_{\mathrm{o}\mathrm{p}\mathrm{t}}=\left[w_1,\dots ,w_m\right]$ [19], where ${\{w_i\}}_{i=1,\dots ,m}$ is the set of eigenvectors of $S_B$ and $S_W$ corresponding to the m largest eigenvalues ${\{{\lambda }_i\}}_{i=1,\dots ,m}$ ,

$$\begin{array}{cc}& S_B{w}_i={{\lambda }_{i}S}_W{w}_i,i=\mathrm{1},\dots ,m.\end{array}$$

(5)

Since $S_B$ is of rank $c-1$ at most, so an upper bound on m is $c-1$ , where c is the number of floors.

Then the new fingerprint vector by $W_{\mathrm{o}\mathrm{p}\mathrm{t}}^T$ projection is

$$\begin{array}{cc}& W_{\mathrm{o}\mathrm{p}\mathrm{t}}^T\overrightarrow{\mathrm{r}\mathrm{f}},\end{array}$$

(6)

where $\overrightarrow{\mathrm{r}\mathrm{f}}$ is a runtime fingerprint for testing. The floor that the pedestrian stands on is classified by a majority vote of its neighbors, which is reference fingerprints in the database. This classification procedure is like kNN (k-nearest neighbor) algorithm.

Fisher's Linear Discriminant finds a subspace to maximize the distance of two classes and minimize the distance within one class. Figure 4 shows the FLD space projection of Figure 3. The symbols on the solid line correspond to the symbols projected by the direction of dashed line in Figure 2. FLD achieves greater between-class scatter than original Euclidean space.

Figure 4

The FLD projection of Figure 3.

5. Pedestrian State Recognition

5.1. Pedestrian Patterns

The rich sensors on smartphones, such as accelerometer, gyroscope, and compass, can measure acceleration, angular velocity, and absolute direction. The behavior of pedestrian can be estimated and considered as location context to help localization system [20, 21]. A few errors in continuous floor identification will make the user ambiguous. Therefore, in our multifloor localization system, floor identification is only reestimated when floor change event may occur. Two pedestrian states may cause floor change event, one is up- or downstairs and another is in the elevator. Figure 5 shows the acceleration signal pattern when pedestrian is in the elevator. Figure 6 shows the acceleration signal pattern when pedestrian is walking on the stairs slowly, normally, and quickly.

Figure 5

Acceleration signal patterns in the elevator: (a) elevator up, (b) elevator down.

Figure 6

Acceleration signal patterns when pedestrian is walking on the stairs slowly (a), normally (b), and quickly (c).

Typical pedestrian state transformation diagram is shown in Figure 7. While pedestrian state goes through Walk→Stair→Walk or Walk→Elevator→Walk, floor change event may occur.

Figure 7

Pedestrian state transformation diagram.

5.2. Pedestrian Patterns Recognition

Since speed of walk may vary, two temporal sequences are compared by DTW (Dynamic Time Warping) [22]. A well-known DTW application has been automatic speech recognition. DTW is able to eliminate the effect of different walking speed.

Given two acceleration signal profiles A and B with lengths of M and N samples, a warping path $P=\left(p_1,\dots ,p_L\right)$ defines an alignment between two sequences $A=\left(a_1,\dots ,a_M\right)$ and $B=\left(b_1,\dots ,b_N\right)$ by assigning the element $a_{p_i}$ of A to the element $b_{p_i}$ of B. The cost $C(A,B)$ of a warping path P between X and Y is defined as

$$\begin{array}{cc}& C\left(X,Y\right)={\displaystyle \sum }_{i=1}^{L}d\left(a_{p_i},b_{p_i}\right),\\ d\left(a_{p_i},b_{p_i}\right)={\left(a_{p_i}-b_{p_i}\right)}^2.\end{array}$$

(7)

The optimal warping path between A and B is a warping path $P^{\ast }$ having minimal total cost among all possible warping paths.

After DTW, pedestrian pattern similarity score is calculated as

$$\begin{array}{cc}& \mathrm{s}\mathrm{c}\mathrm{o}\mathrm{r}\mathrm{e}=\frac{{\sum }_{l=1}^L{a}_{p_i}{b}_{p_i}}{\sqrt{{\sum }_{l=1}^L{a}_{p_i}{a}_{p_i}}\sqrt{{\sum }_{l=1}^L{b}_{p_i}{b}_{p_i}}}.\end{array}$$

(8)

Figure 8 shows DTW matching result between Figures 6(a) and 6(c) and similarity score is 0.997.

Figure 8

DTW matching result between Figures 6(a) and 6(c).

Figure 9

The layout environment in which we performed our experiments: (a) the 1st floor, (b) the 2nd to the 6th floor.

5.3. Fingerprint Matching

In our system, location can be estimated by searching optimal reference location on a floor in the fingerprint database. To reduce the effect of heterogeneous devices and environment, the weight-RSS location algorithm in [17] is applied. The weight-RSS on location $l_j$ is defined as

$$\begin{array}{cc}& D_j=\left\{\left(r_j^1,s\left(r_j^1\right)\right),\left(r_j^2,s\left(r_j^2\right)\right),\dots ,\left(r_j^m,s\left(r_j^m\right)\right)\right\},\end{array}$$

(9)

where $s(r_j^i)$ is the index of $r_j^i$ after $R_j$ is sorted as descending order.

For $D_{\mathrm{t}\mathrm{r}}$ from fingerprint map and $D_{\mathrm{t}\mathrm{e}}$ from a test device, their weighting factor $W_{\mathrm{t}\mathrm{r},\mathrm{t}\mathrm{e}}$ is calculated as

$$\begin{array}{cc}& W_{\mathrm{t}\mathrm{r},\mathrm{t}\mathrm{e}}=\left\{w_{\mathrm{1}},w_{\mathrm{2}},\dots ,w_m\right\},\end{array}$$

(10)

where $w_i$ is calculated as

$$\begin{array}{cc}& w_i=\mathrm{1}-\frac{\left|s\left(R_{\mathrm{t}\mathrm{r}}^i\right)-s\left(R_{\mathrm{t}\mathrm{e}}^i\right)\right|}{\max \left\{s\left(R_{\mathrm{t}\mathrm{r}}^i\right),s\left(R_{\mathrm{t}\mathrm{e}}^i\right)\right\}},\mathrm{1}\le i\le m.\end{array}$$

(11)

Then, the Euclidean distance $\mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}(D_{\mathrm{t}\mathrm{r}},D_{\mathrm{t}\mathrm{e}})$ between $D_{\mathrm{t}\mathrm{r}}$ and $D_{\mathrm{t}\mathrm{e}}$ can be calculated as

$$\begin{array}{cc}& \mathrm{D}\mathrm{i}\mathrm{s}\mathrm{t}\left(D_{\mathrm{t}\mathrm{r},}{D}_{\mathrm{t}\mathrm{e}}\right)=\sqrt{{\displaystyle \sum }_{i=\mathrm{1}}^m{w}_i{\left(r_{\mathrm{t}\mathrm{r}}^i-r_{\mathrm{t}\mathrm{e}}^i\right)}^{\mathrm{2}}}.\end{array}$$

(12)

The optimal reference location is searching by k-nearest neighbor algorithm on weight-RSS distance and the coordinates of the best match location are regarded as positioning result.

6. Experiments

6.1. Fingerprint Database Collection

The experiments are carried out on the building of six floors in Zhejiang University City College, as shown in Figure 9. The 1st floor and the 2nd to the 6th floor plans are shown in Figure 8. There are 160 grids for collecting the reference fingerprint in the 1st floor and 131 grids in the 2nd to the 6th floor. The distance between two adjacent grids is 1.6 meters. Four heterogeneous devices including 3 smartphones and 1 Tablet PC participated in this experiment, as shown in Table 1. The RSS fingerprints on one grid are collected 5 times and averaged to reduce the effect of random noise. To evaluate floor identification, 100 random locations on each floor are also sampled. The ground truth of these random locations is the nearest reference location.

Table 1

Devices used for experiments.

Devices	Manufacturer	Embedded OS
GALAXY S3	Samsung	Android 4.04
Ascend P6	Huawei	Android 4.2
MI 2S	Xiaomi Tech	Android 4.1
Nexus 7	Asus	Android 4

6.2. Floor Identification

Floor discriminative model has been trained by the reference location fingerprints labeled with floor number in the database and random location sampling fingerprints are tested. Average distance [12], k-nearest neighbor [10], and one-layer ANNs classifier [13] are also tested to be compared with FLD. Table 2 shows floor identification accuracy of our discriminative floor model and others. ANNs and our method, which are classifiers by training, are better than single distance measure without training. The results show that FLD archives 94.3% accuracy in floor identification.

Table 2

Floor identification accuracy.

	Floor ID accuracy (%)	Floor acc. within ±1 (%)
FLD	94.3	100
Average distance [12]	71.1	78.2
k-NN [10]	78.4	85.2
ANNs [13]	85.6	91.6

6.3. Motion Recognition

To evaluate the stair walking and elevator motion recognition, motion acceleration database has been built. The database has 10 individuals. Each person has four kinds of motions: upstairs, downstairs, elevator up, and elevator down. Each motion has been sampled twice. Stair walking has also been sampled in three different kinds of walking speed, for example, slow, normal, and fast. The position of smartphone is in hand, pants, and bag, respectively. Totally $10\ast 2\ast 2\ast 3=120$ stair walking and $10\ast 2\ast 2=40$ elevator motion acceleration samples are collected. Two individuals are considered as motion templates and the rest of the eight for testing. When the pattern similarity score is bigger than a threshold, motion template is matched. $10\ast 2\ast 3=60$ normal walking samples in different walking speed have also been collected for recognition test. Figure 10 shows ROC (Receiver Operating Characteristic) curves of motion recognition. Since the acceleration signal pattern of upstairs and downstairs are quite similar and both of them can trigger floor change event, up- and downstairs are considered together as one stair walking motion. The results show that elevator motion recognition is better than stair walking. At about 20% false positive rate, 92% elevator motion and 82% stair walking can be discovered.

Figure 10

ROC curves of stair walking and elevator motion recognition.

6.4. Localization Results

The random location sampling fingerprints are tested to evaluate localization accuracy. The sampling position is located by the matching method discussed in Section 6 and the location error is the distance between nearest fingerprint location in reference fingerprint database and the ground truth of sampling location. Table 3 shows the average location error and floor error percentage of fingerprint location with and without floor identification. The fingerprint matching algorithm has been discussed in Section 5.3. 19.6% floor errors happen in single fingerprints-based location. After floor identification, about 13.9% floor location errors are corrected and the average location distance error has been reduced from 4.8 to 1.2 meters.

Table 3

Location accuracy with and without floor identification.

	Average location error	Floor error percentage
With floor identification	1.2 meters	5.7%
Without floor identification	4.8 meters	19.6%

7. Conclusion

In this paper, a novel and effective multifloor localization scheme is proposed. The weakness of fingerprint location without floor identification in multifloor environment is stated. To maximize margin discrepancy between two neighboring floors in fingerprints space, a discriminative floor model is trained. Stair walking and elevator events recognition trigger the floor change event to reestimate floor number. To evaluate our method, experiments were done at a ring architecture building. About 800 reference fingerprint locations are collected in the building of six floors. The results show that our method can identify accurate location in multifloor environment. After floor identification, about 13.9% floor location errors are corrected and the average location distance error has been reduced from 4.8 to 1.2 meters.