Fingerprint-based Wi-Fi indoor localization using map and inertial sensors

Abstract

It is a common understanding that the localization accuracy can be improved by indoor maps and inertial sensors. However, there is a lack of concrete and generic solutions that combine these two features together and practically demonstrate its validity. This article aims to provide such a solution based on the mainstream fingerprint-based indoor localization approach. First, we introduce the theorem called reference points placement, which gives a theoretical guide to place reference points. Second, we design a Wi-Fi signal propagation-based cluster algorithm to reduce the amount of computation. The paper gives a parameter called reliability to overcome the skewing of inertial sensors. Then we also present Kalman filter and Markov chain to predict the system status. The system is able to provide high-accuracy real-time tracking by integrating indoor map and inertial sensors with Wi-Fi signal strength. Finally, the proposed work is evaluated and compared with the previous Wi-Fi indoor localization systems. In addition, the effect of inertial sensors’ reliability is also discussed. Results are drawn from a campus office building which is about 80 m×140 m with 57 access points.

Keywords

Indoor localization inertial sensors map information

Introduction

In recent years, with the development of Internet of Things (IoT) applications and mobile computing, there is a growing concern about indoor location information. Therefore, indoor localization attracts increasing interest. Although the accuracy can reach to centimeter level through the use of ultra-wideband (UWB),^1,2 infrared,³ radio frequency (RF),⁴ beacon,⁵ multi-antennas,⁶ and so on. Those systems need to deploy extra facilities, such as UWB transmitters and receivers. Nowadays, given that many buildings are equipped with Wi-Fi access points (APs), Wi-Fi localization becomes much acceptable by users.

However, Wi-Fi-based indoor localization is particularly challengeable since the radio signal is affected by many external factors, such as reflection, refraction, multi-path, shadow fading, scattering, and temporal dynamics.^7–10 These interferences lead to a large deviation in pure Wi-Fi-based localization. Therefore, the introduction of other beneficial information for positioning is quite necessary.

Now that mobile terminals (phones, tablets, etc.) own built-in inertial sensors (magnetometer, accelerometer, etc.) which can be included to modify users’ trajectories.¹¹ Since many sites provide their own indoor maps online, the tracking service can achieve a better level (more smoothly by avoiding trajectories to pass-through walls) using the map information.¹² Thus, it is obvious that through indoor maps and inertial sensors, the localization accuracy can be significantly improved.

Nonetheless, there is lack of a mature scheme to fuse map and sensor data with Wi-Fi-based indoor localization. Because of the existing sensor noise, continuous use of inertial sensors causes a great drift.¹³ As a result, utilizing the original data produced by inertial sensors to correct the localization error¹⁴ may not improve the accuracy as well as expected. Sometimes, employing the inertial sensors data with increasing drift may lead to worse results. Thus, the original information from inertial sensors requires further processing. As fixed resolution pictures, maps that used in many previous indoor localization systems provide little information (e.g. hallways, walls).^12,15 Therefore, to offer adequate information, a much more refined map technique is needed.

Researchers also assume that the positioning accuracy of fingerprint-based indoor localization method depends on the number of reference points in the database.¹⁶ A larger database consumes more training time and computational resources. However, this is a pseudo-proposition and we give a theoretically proof in this work.

In this article, we propose that the reference points placement theory in section “Reference points placement theory” to prove localization accuracy will not continue improved by adding new reference points when distances among reference points are less than a lower bound. Leveraging this theory, indoor localization systems can achieve a high accuracy with less training time by setting a minimum distance (noise distance) between reference points.

Although the theory can guide to place reference points, when the indoor environment is large, the fingerprint database can also be huge. As a result, determining the location is a complex calculation process. Facing the heavy computational cost with restricted resources and power, we employ a two-stage model to localize the devices. First, coarse localization, the position is located into a candidate set with a small size. Second, precision localization, the position is finally given from the candidate set.

In the coarse localization and training phase, a cluster technique is utilized to classify Wi-Fi fingerprints. A Wi-Fi signal propagation-based cluster algorithm is proposed in section “Offline phase.” The cluster algorithm reduces the amount of computation and improves the clustering speed compared with the existing ones.^17–19

Our localization system forms a maximum reference point set based on the vector graphic map²⁰ and reference points placement theory. These reference points generate a Markov chain that is used to represent users’ all possible movement routes with the constraint of walls. The phenomenon of trajectories pass-through walls can be avoided through Markov chain. Users’ movement information (such as step lengths, directions) can be obtained from inertial sensors (e.g. accelerometer, magnetometer). In this way, the tracking service can provide a smooth experience.

The main contributions of this article can be briefly summarized as follows:

We propose a reference points placement theory. The theory gives a theoretical guide to place reference points.

We present a Wi-Fi signal propagation-based cluster algorithm. The algorithm reduces the amount of computation by adapting to the propagation nature of Wi-Fi signal.

We present and implement a fingerprint-based Wi-Fi indoor localization approach which fuses map, inertial sensors, and received Wi-Fi signal strength. Considering the drift of the inertial sensors and inaccuracy of Wi-Fi signal, the parameter, reliability, is proposed in the integration to provide a better accuracy system.

The rest of this article is organized as follows: section “Fingerprint-based localization model” describes the fingerprint-based indoor localization method and the improvement we did on the model. In section “Using map and inertial sensors in Wi-Fi indoor localization” and “The integration of map, inertial sensors, and Wi-Fi RSS in tracking phase,” the fusion of map information, inertial sensors, and Wi-Fi indoor positioning system is discussed, and the usage of map information and inertial sensors in the localization system is introduced in detail. The localization accuracy is evaluated and compared with the previous Wi-Fi indoor localization systems in section “Experiment.” Finally, we give a brief conclusion in section “Conclusion.”

Related work

A majority of previous localization systems determine the system status through Wi-Fi signal strength survey. Generally, these systems fall into two categories: model-based and fingerprint-based approaches.

Model-based approach

This kind of approach is widely used in wireless sensor networks.^21–23 They estimate the propagation distances from APs by the measurement of received signal strength (RSS) and a path loss model and then calculate the location using a localization technique such as triangulation. Thus, the locations of APs are required by these systems.^24,25 To improve the accurate, many indoor signal propagation models are presented in previous works.^26,27 Barsocchi et al.²⁸ present an automatic virtual calibration method of the propagation model that does not require human intervention. However, E Elnahrawy et al.²⁹ present a strong evidence that the limits of localization by signal strength in indoor environments are fundamental. Performance of these approaches depends on many conditions,^30,31 and the orientation of antenna is the dominant factor of the signal strength.³² All of the above studies show that the propagation of Wi-Fi signals in a complex indoor environment is unpredictable, which makes it difficult to form a common indoor Wi-Fi signal propagation model. Therefore, signal propagation model-based Wi-Fi indoor localization is not a good choice.

Fingerprint-based approach

Recently, the commonly used RSS-based indoor localization technology is fingerprint-based approach. The main idea of these methods is to match the real-time fingerprint to the recorded fingerprints and get the corresponding coordinate of the matched fingerprint. P Bahl and VN Padmanabhan³³ present RADAR, a RF-based system which is the early fingerprint-based indoor localization system. Then the IEEE802.11 signal is used as the fingerprints.³⁴ Now the accurate of indoor localization can achieve room-level accuracy based on ambiences feature including sound, light, color, Wi-Fi, and so on.³⁵ However, these features (such as light, Wi-Fi) are not static over time. The fluctuations will cause a huge deviation in localizing and tracking. The reference points are considered to be directly linked to each other in the tracking process when there is no other additional information. The lack of restriction leads trajectories to pass-through walls. Therefore, there are also plentiful deficiencies in this method.

To improve the accuracy of pure Wi-Fi-based localization, many kinds of additional information are imported. H Liu et al.³⁵ propose a peer-assisted localization approach to eliminate the errors. This method needs other peer devices to participate and is not realistic to implement. SP Tarzia et al.³⁶ use a sound fingerprint called the acoustic background spectrum to determine the location. However, the acoustic background spectrum is not constant as the time goes on. J Chung et al.³⁷ measure location through disturbances of the Earth’s magnetic field caused by structural steel elements in a building. However, the user of electronic devices can bring heavy interference. E Martin et al.³⁸ use cellular and inertial sensors to correct the accuracy. A Matic et al.³⁹ combine FM and Wi-Fi to make a better indoor localization system. Nonetheless, cellular and FM signals are also inaccurate in indoor environment. Thus, the changeless map and build-in sensors are the first choice to improve the accuracy of Wi-Fi-based localization.

Different from the previous works, the indoor localization system proposed in this article does not rely on specific hardware and propagation model. It not only adopts the fingerprint technique but also introduces map information and inertial sensors to reduce the errors and handles the drift of inertial sensors.

Fingerprint-based localization model

A fingerprint-based indoor localization system consists of two phases: offline phase, in which RSS samples are collected at specific positions called reference points; online phase, in which users’ locations are determined based on matching real-time collection of Wi-Fi RSS to the database.

Reference points placement theory

Before proposing the fingerprint-based indoor localization mechanism, the theory of reference points placement needs to be introduced. Suppose there are n Wi-Fi APs in the building, let $F = [f_{1}, f_{2}, \dots, f_{n}]$ denote the Wi-Fi fingerprint, where $f_{i}$ is the RSS of ith Wi-Fi AP. Let Euclidean distance be the metric of Wi-Fi fingerprints matching. For Wi-Fi fingerprint $F_{1} = [{f_{1}}_{1}, {f_{2}}_{1}, \dots, {f_{n}}_{1}]$ and $F_{2} = [{f_{1}}_{2}, {f_{2}}_{2}, \dots, {f_{n}}_{2}]$ , the Euclidean distance is

d (F_{1}, F_{2}) = \sqrt{\sum_{i = 1}^{n} {({f_{i}}_{1} - {f_{i}}_{2})}^{2}}

(1)

Definition 1

Recognizable

In a noisy environment, we say a Wi-Fi fingerprint $F_{i}$ in the database is recognizable for AP k if for any time we collect a new Wi-Fi fingerprint $F_{i'}$ at the same reference point as F, the inequation

| {f'_{k}}_{i} - {f_{k}}_{i} | < | {f'_{k}}_{i} - {f_{k}}_{j} |, \forall F_{j} \in O, F_{j} \neq F_{i}

(2)

is always held, where O is the Wi-Fi fingerprint database.

To make AP k recognizable, the differences among Wi-Fi fingerprints for AP k denoted as $Δ {F_{i}}_{k}$ should be bigger than the maximum noise. Let $δ$ denote the environment noise, and indoor Wi-Fi signal propagation model is $P_{d} = {P_{d}}_{0} - g (d, d_{0}) - φ$ , where d and $d_{0}$ are distances from AP k, $P_{d}$ and ${P_{d}}_{0}$ are corresponding RSSs, and $φ$ is the wall attenuations. To make the Wi-Fi fingerprints recognizable for any AP, the difference between any two RSS values $P_{d} - {P_{d}}_{0}$ must be larger than $δ$ , which means $g (d, d_{0}) + φ \geq δ$ . We call the minimum value of $d - d_{0}$ that satisfies the inequation as noise distance. Since the function $g (d, d_{0})$ is not a linear function and it exists wall attenuations, the noise distance is not a constant value.

Definition 2

Maximum reference point set

For a set of reference points, if each fingerprint is recognizable to any other fingerprints for at least one AP, and by randomly adding another reference point, the set will not follow the recognizable attribute; we call this set a maximum reference point set.

Obviously, there are many maximum reference point sets for a specific building. Since the noise distance is not constant, the distances among reference points in maximum reference point set may not be uniform.

In many fingerprint-based localization algorithms, it seems the denser the reference points are, the more accurately the system will achieve, but it is a pseudo-proposition.

Theorem 1

Reference points placement

Adding a new reference point to a maximum reference point set will not increase the localization accuracy.

Proof

Assuming the new reference point makes reference point A unrecognizable. The real-time Wi-Fi fingerprint collected at A is $F' = F_{0} + V_{t}$ , where $F_{0}$ is the Wi-Fi fingerprint of this reference point

d (F_{0}, F') \leq d (F_{i}, F'), F_{i} \in {F | F \in O, F \neq F_{0}}

(3)

Only if equation (3) is established, the anchor point can be correctly identified as reference point A. Otherwise, it explains that the presence of the newly added reference point $R ″$ with Wi-Fi fingerprint $F ″$ leads to a drift: $d (F_{0}, F') \geq d (F_{0}, F ″)$ , namely $\sum_{i = 1}^{n} (F'_{i} - {F_{0}}_{i})^{2} = \sum_{i = 1}^{n} {V_{t}}_{i}^{2} > \sum_{i = 1}^{n} (F_{i}^{″} - F'_{i})^{2}$ .

Offline phase

The offline phase can be seen as the database creation phase. A database record can be expressed as $D < R, F >$ , where R denotes the coordinate of a reference point and F is the collected Wi-Fi fingerprint.

After database records are continuously stored into database, the size of database may be extremely large. In order to satisfy the real-time requirement, the calculation should be simplified. Commonly, a two-stage approach is applied.^18,19 The first stage is coarse localization which reduces the number of records into a small candidate set through cluster matching. The second stage, precise localization, gives the final estimation over the candidate set. Coarse localization technology requires that all Wi-Fi fingerprint records are classified and it is easy to tell which categories (may be not one) the real-time Wi-Fi fingerprint belongs to.

In this article, a relatively simple and effective way of Wi-Fi fingerprint clustering method is proposed to offline classify all Wi-Fi fingerprints and tell categories which the real-time Wi-Fi fingerprint belongs to. Considering the nature of signal propagation that the closer to the signal source is the greater RSS will achieve. Therefore, for the fingerprints surrounding AP k, the kth RSS is bigger than the others (the distance to AP k is shorter than the distances to other APs). Then we can use the index of the biggest RSS in a fingerprint as its category. As a result, the fingerprints belonging to category k are closer to AP k than others, which means fingerprints are geographically separated into n pieces. The approach can be described as follows.

Definition 3

Wi-Fi signal propagation-based cluster approach

For Wi-Fi fingerprint $F = [f_{1}, f_{2}, \dots, f_{n}]$ , it belongs to the class C

C = i, st . f_{i} \geq f_{j}, \forall j = 1, 2, \dots, n

(4)

In this approach, only a sorting operation is used to estimate which class a fingerprint belongs to. Thus, the computation complexity is $O (nm)$ where m is the number of the fingerprint records in database.

Online phase

In this phase, mobile devices gather real-time Wi-Fi fingerprint F (due to the instability of the signal, the average of multiple successive measurements can be seen as the collected Wi-Fi fingerprint). The class C which F belongs to can be obtained by our cluster approach. Then a localization algorithm is used to estimate the user’s location over all the elements in class C.

There is a classic fingerprint-based localization algorithm, k-nearest neighbors (kNN).⁴⁰ This algorithm goes through the database and picks up k reference points whose fingerprints match best to the real-time one. “Match best” here means the value of equation (1) is lowest.

Let $N_{k}$ denote the subset picked up by kNN algorithm, and $N_{k}$ can be built with an iterative process as follows

N_{k} = {argmi n_{F_{i} \in O} d (F, F_{i}) | F_{i} \notin N_{k - 1}} \cup N_{k - 1}

(5)

where O represents the entire fingerprints database or fingerprints set acquired from coarse localization stage, and F is the real-time Wi-Fi fingerprint

\frac{d (R, R_{i})}{d (R, R_{j})} = \frac{d (F, F_{i})}{d (F, F_{j})}, i, j = 1, 2, \dots, k

(6)

Ultimately, the coordinate $X (x, y)$ of the user can be calculated by equation (6). As the purpose of this article is to illustrate the use of maps and inertial sensors, the differences between localization algorithms are not considered. The indoor positioning algorithm is not the focus of this article, so we simply employ the standard kNN algorithm for this purpose.

Tracking

Wi-Fi-based indoor tracking can be described as the continuous localization processes for users which is based on a predetermined time sequence real-time Wi-Fi fingerprints $F (t)$ and motion model. The system state can be defined as

S (t) \overset{Δ}{=} {[p_{x}, p_{y}, v_{x}, v_{y}]}^{T}

(7)

where $(p_{x}, p_{y})$ is the coordinate of users at time t, and $(v_{x}, v_{y})$ indicates the user’s velocity at time t.

Tracking process can be divided into two steps: prediction and correction. The prediction phase is to presume current state $\hat{S}$ based on the previous state $S (t - 1)$ and previous prediction $\hat{S} (t - 1)$ , as follows

\hat{S} (t) = f (S (t - 1), \hat{S} (t - 1))

(8)

where f is the prediction function.

Correction is the stage to correct and update the system status by the combination of prediction information $\hat{S}$ at time t, real-time Wi-Fi fingerprint, map information, and inertial sensor information from time $t - 1$ to t

S (t) = h (\hat{S} (t), F (t), G, I (t))

(9)

where h is the correction function, G represents the map, and $I (t)$ is the inertial sensor information from time $t - 1$ to t.

Since the users of tracking service are on the moving, the service is required with high real-time performance. Thus, taking the average of multiple measurements as the Wi-Fi fingerprints is not acceptable because of its huge time consumption. To cope with the significant fluctuation in Wi-Fi fingerprints, a filter technique is introduced. In this article, we use a common filter, Kalman filter, which can be illustrated as

{\begin{matrix} S (t) = A_{t} S (t - 1) + B_{t} U (t) + W_{t} \\ Z (t) = H_{t} S (t - 1) + V_{t} \end{matrix}

(10)

where process noise $W_{t}$ and observation noise $V_{t}$ follow Gaussian distribution, and they are independent to each other, namely $W_{t} ~ (0, Q)$ , $V_{t} ~ (0, R)$ . Q and R can be obtained by experience, and they are not variational with the system changing

A_{t} = {\begin{matrix} 1 & 0 & T_{s} & 0 \\ 0 & 1 & 0 & T_{s} \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}} H_{t} = {\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}}

(11)

where $T_{s}$ is the sampling frequency. With the restriction of the system and hardware, in our experiment, the parameter $T_{s}$ is set to 1 s.

The prediction for system status is

{\begin{matrix} \hat{S} (t) = A_{t} \hat{S} (t - 1) \\ \hat{P} (t) = A_{t} \hat{P} (t) {A_{t}}^{T} + Q \end{matrix}

(12)

The correction for system status is

{\begin{matrix} K (t) = \hat{P} (t) {H_{t}}^{T} {(H_{t} \hat{P} (t) {H_{t}}^{T} + R)}^{- 1} \\ S (t) = S (t - 1) + K (t) (Z (t) - H_{t} \hat{S} (t)) \\ P (t) = (I - K (t) H_{t}) \hat{P} (t) \end{matrix}

(13)

The final position estimation is obtained by the Kalman filter that integrates system state estimation with real-time Wi-Fi fingerprint. The parameter $Z (t)$ is only related to the real-time Wi-Fi fingerprints and is independent on the user’s movement.

The Kalman filter assumes process noise and observation noise follow Gaussian distribution and supposes users’ movements are linear motion models. However, in real life, these noises are not completely Gaussian distributed, and users’ movements are stochastic; therefore, utilizing pure Kalman filter will result in a large deviation.

Using map and inertial sensors in Wi-Fi indoor localization

Since pure Wi-Fi localization causes a huge error, it needs other information for error correction. In this article, vector graphic map and inertial sensors (magnetometer, accelerometer) are leveraged to improve the localization accuracy.

Using map in offline phase

To deploy a high-accurate localization service with fewest training work, there are some rules for placing reference points to obey:

The reference points should be recognizable to each other for at least one AP.

The reference points should be placed at all possible locations that users may walk to.

Reference points placement plan should be generated based on these principles, map information, the locations of APs, and a indoor Wi-Fi signal propagation model.

The algorithm can be expressed as follows.

Algorithm 1. Generate reference points plan.
Input:
the location set of APs P, the grid gap g, the map information m, the Wi-Fi signal propagation model.
Output: the reference points plan.
Grid each room and hallway with the gap g;
for each AP do
for each direction along the grid lines do
draw a virtual line l;
if l is part of the grid lines then
mark the ap point;
while not beyond the map do
mark the point at line l that is noise length away from the previous point.;
else
for mark the first cross point with the grid lines do
if every cross point with grid lines this point is noise length away from the previous marked point then
mark this cross point;
All the marked points are the reference points set.

Using map in tracking phase

Nowadays, indoor maps are available for many public places and company buildings. The main idea of using the map information in tracking phase is to fuse humans behavior model and map information into a filter to form a more realistic filter with less tracking error.

The vector graphic map used in this article is constituted by the following basic structures:

vertex [id, x, y, type];

edge [id, start, end];

location [id, name, vid, polygon].

Vertex is a point structure, containing type, and coordinate field. Vertex can be used to represent the key points for floor layouts, such as the center point for a room, the midpoint for a door, the point in corridor which connects a door, corner of the corridor. Edge is a structure of the connective relation between two rooms (hallways), composed by the start and end points. The start and end points are both vertex structures. Location is the structure that represents rooms and hallways and contains a room label, topology information as vertexes.

The floor plan can be abstracted into an undirected graph. Nodes are rooms and hallways, and links are doors among them. The undirected graph shows all the available paths from the floor plan. Users can only move along the edges in the graph from one room to another or stay in one room. If the user only needs to be located to the reference point in tracking phase, this process can be represented by a Markov chain as Figure 1, and there are five actions in the system: go forward, turn left, turn right, turn back, and stay. Each state in the chain is a reference point. The probability of each action for each reference point can be obtained using a statistic way. When the system is built, the probability of each state for each possible action can be initialized with the same probability.

Figure 1.

The Markov Chain of reference points. The $S_{i}$ represent the ith reference point, and the move of $M_{ij}$ is that the user can move from the reference node i to j. The intuition behind our method is that in indoor environments, user can move from one place directly to another place if there are no barriers: (a) the states change in corridor and (b) the states change in room.

After Wi-Fi fingerprint database is collected, the corresponding Markov chain is also generated. The state space of system’s next state is restricted by the state transfer function which can be denoted as a $m \times m$ matrix M. m is the number of reference points and $M_{ij} = P (R_{t + 1 = i} | R_{t = j})$ . In this way, the state space for time $t + 1$ is $Ω = {R_{i} | R_{t = j}, M_{ji} \neq 0}$ . The possibility for next state in the space W is the corresponding value in transition matrix: $W [R_{i} | R_{j}] \overset{Δ}{=} M_{ji}$ . The greater the weight is, the closer to the current sample the system state is

To make the tracking service more accurate, the possibilities are corrected by real-time Wi-Fi fingerprint $F_{0}$ . For a state from the state space whose corresponding Wi-Fi fingerprint is $F_{i}$ , its possibility is corrected in the following manner

W [R_{i} | R_{j}] = W [R_{i} | R_{j}] \frac{e^{\frac{- \sum_{k = 1}^{n} {({F_{i}}_{k} - {F_{0}}_{k})}^{2}}{2 σ^{2}}}}{\sqrt{2 π} σ}

(14)

Since there exists a fluctuation for RSS over time, we introduce a system parameter $σ$ to represent the confidence for the current measurement. The larger $σ$ is, the less credible the measurement will be.

The system state can be acquired after the final calculation of the possibilities. Meanwhile, the transfer matrix will be updated according to the results

M_{ji} = {\begin{matrix} \frac{a}{b + 1} & R_{t = j}, R_{t + 1} = R_{i} \\ \frac{a + 1}{b + 1} & R_{t = j}, R_{t + 1} \neq R_{i} \end{matrix}

(15)

where b is the number that system state falls on state j, and a is the number that system takes the next movement to state i from state j.

However, for this tracking, when the prediction is wrong, it is hard for the system to turn to the right state. We can leverage inertial sensor data to monitor users’ movements to make a high-accurate prediction.

Using sensors in tracking phase

Because of the existence of barrier walls, the movements of people are constrained in a specific range in indoor environment. The movements can be simply classified as walking forwards and veering (e.g. turn left, turn right, turn around). Thus, heading direction is an important parameter in the system which can be gotten from inertial sensors. The walking patterns (e.g. speed) can also be obtained from them.

These information can be used to correct the filters mentioned above for the Kalman filter

\begin{matrix} \hat{S} (t) = (1 - θ) A_{t} \hat{S} (t - 1) + θ A_{t} U (t) \\ U (t) \overset{Δ}{=} {[{p'}_{x}, {p'}_{y}, {v'}_{x}, {v'}_{y}]}^{T} \\ {p'}_{x} = \hat{S}' (t - 1) [p_{x}] \\ {p'}_{y} = \hat{S}' (t - 1) [p_{y}] \\ {v'}_{x} = \frac{a_{x} \times T_{s}}{2} + \hat{S}' (t - 1) [v_{x}] \\ {v'}_{y} = \frac{a_{y} \times T_{s}}{2} + \hat{S}' (t - 1) [v_{y}] \end{matrix}

(16)

where $a_{x}$ , $a_{y}$ are the accelerations in directions x and y at time $t - 1$ obtained from the accelerometer sensor. $θ$ is the reliability of inertial sensors. The value of $θ$ will increase with the measured noises decreasing, which means the confidence of measurement is enlarged with the value magnifying.

For Markov chain model, the possibility for each transfer action can be corrected by the direction information

\vec{d} = < {R_{i}}_{x} - {R_{t - 1}}_{x}, {R_{i}}_{y} - {R_{t - 1}}_{y} >

(17)

W [R_{i} | R_{j}] = {\begin{matrix} (1 - θ) M_{ji} + θ M_{ji} < \vec{d}, \vec{v} > & \vec{v} \neq \vec{0}, i \neq j \\ (1 - θ) M_{ji} & \vec{v} = \vec{0}, i \neq j \\ (1 - θ) M_{ji} & \vec{v} \neq \vec{0}, i = j \\ θ M_{ji} & \vec{v} = \vec{0}, i = j \end{matrix}

(18)

where $\vec{v}$ is the user’s forward direction measured by the magnetometer sensor at time $t - 1$ .

Since accelerometer and magnetometer sensor data are quite noisy, the deviations caused by these noises are gradually accumulated with the system running. Therefore, it is not accurate to sostenuto use the raw sensor data to estimate thusers’ speeds. An alternative solution is to detect the number of users’ steps and then use a step model to obtain the travel distance.

It is a common sense that each individual may have different body shapes like height and weight that influence the step length estimation. Even for the same person, steps may change over time due to variation in health status, ground types. Therefore, a static pedestrian model will not work well. Here, we propose a reliable step model for step detection and a personalization algorithm to adapt users stride length.

As shown in Figure 2, the acceleration is cyclically fluctuating with users’ walking. Because of the noise and users’ behaviors, the different between top and bottom acceleration $Δ a$ for each step may not be identical as the time $Δ t$ that each step takes. In our algorithm, we employ possible intervals $[Δ t_{\min}, Δ t_{\max}]$ and $[Δ a_{\min}, Δ a_{\max}]$ for the time a step takes and acceleration difference. A step is identified if we detect that acceleration increased first and then decreased; meanwhile, the difference from top to bottom falls in $[Δ a_{\min}, Δ a_{\max}]$ with the time in $[Δ t_{\min}, Δ t_{\max}]$ . In our algorithm, we leverage map information to adapt users stride length by dividing a path into n steps that the user takes.

Figure 2.

An illustration of step detection.

Algorithm 2. Motion analysis.
Input:
The time interval that a step may take $[T_{\min}, T_{\max}]$ .
The upper-lower limit of acceleration difference $[Δ a_{\min}, Δ a_{\max}]$ .
Output: User’s movement state.
while acceleration changes do
Get $(t, a)$ ; if $t = 0$ then
preTS : = t, upFlag : = false, preAc : = a;
continue;
if $a > preAc$ then
if upFlag = false then
minAc : = preAc, minTS : = preTS, upFlag : = true;
else
if upFlag = true then
duration : = t – minTS;
if $duration \in [T_{\min}, T_{\max}]$ then
difference : = preAc – minAc;
if $difference \in [Δ a_{\min}, Δ a_{\max}]$ then
User walks;
Get the result from Integration track;
if user change his direction then
get the distance d the user walked as a line from map;
update user’s step length by $\frac{d}{step}$ ;
step = 0;
else
step : = step + 1;
upFlag : = false;
preTS : = t, preAc : = a

The integration of map, inertial sensors, and Wi-Fi RSS in tracking phase

Supposing users’ movements follow the models mentioned in section “Using sensors in tracking phase,” including walking forwards and veering. Then the users trajectories are composed of lines which is partitioned by veering positions. The main idea to use map information and inertial sensors in indoor tracking system is to find the veering position by inertial sensors raw data. And the linear trajectory is mapped into a path in the map by Wi-Fi RSS matching.

In the linear trajectory, a Kalman filter is used to evaluate the users speed. Initially, the step length is set to a common value, such as 0.75 m. When a veering is detected, we update the step length through dividing trajectory length by step number. The trajectory length can be easily estimated by finding the most possible veering location, and the length is the distance between the started and veering positions.

When a veering occurs, we can use the updated step length and new direction detected by the inertial sensors with magnetometer to reset the Kalman filter. In such approach, it not only keeps the simplicity of Kalman filter, but also overcomes its deficiencies of linear hypothesis.

The key point to fuse map information and inertial sensors is veering-judgment. Turning right/left can only happen at entrances, the corner of the hallway, and room, but turning around can occur anywhere. Veering can be predicted using a particle filter. For simplicity, the particle filter (Markov chain) is considered only at the corner of the hallway or rooms and the entrances of rooms. The system can determine whether there is a turning after receiving the data from inertial sensors and correct the system itself. If there is a turning, the system resets the Kalman filter, updates step length, and starts a new tracking state and then continues this process. “Reset” means starting a new Kalman filter process. The new Kalman filter takes the end point of the old one as the start point and changes the direction of the speed.

Algorithm 3. Integration track.
Input:
The database of all $D < R, F >$ records DB.
The indoor map.
The system state at time $t - 1$ $S (t - 1)$ .
The real-time Wi-Fi fingerprint at time t F.
The inertial sensor information from time $t - 1$ to time t $I (t)$ .
Output: The system state at time t $S (t)$ .
if $S (t - 1)$ is at the corner of the hallway (room) or the entrances of room then
Predict all the possibility states of system by Markov chain model;
else
Predict the system state by Kalman Filter;
Choose all the reachable (in Markov chain) reference points record from DB as the state space $Ω$ ;
Locate the system by localization algorithm in section 3.1 and sample space $Ω$ . The result is $S'$ ;
Obtain the direction and movement from inertial sensor, and then get the position estimation $S ″$
Calculate the location $S = (1 - θ) S' + θ S ″$ ;
if there occurred turning then
Reset the Kalman Filter, use the system state as the initial state of filter, and change the direction of speed;
Update system state;

Experiment

The inherent characteristics of the Wi-Fi signal are introduced and verified in this section, the localization results are compared using different additional information, and the impacts for different values of $θ$ are analyzed. Since Kalman filter–based localization is a common method in indoor localization, we take the Kalman filter–based method as the benchmark here.

Experiment settings

All experiments in this article are conducted at floor 2, CCST (College of Computer Science and Technology) office building, Jilin University which is about a $80 m \times 140 m$ area, as shown in Figure 3. The mobile device is Xiao MI 3. There are 57 APs that can be detected on this floor. All the reference points are selected through the map information. The RSS of each fingerprint record in the database is the average of 1 min of measurements.

Figure 3.

The floor layout and the trajectory of user.

Following the setting of Potortì et al.,⁴¹ the localization error is defined as a statistic associated with the distance between the real position of the user and the estimated position of the application. To this purpose, we add some marks on the pre-defined path. When the user walks pass a mark, he can tap the screen of the smart device and the system logs the evaluated position. To illustrate the error of the trajectory, as shown in Figure 5, we use different colors to display the variance of error.

Inherent characteristics of Wi-Fi signal

Due to the existence of reflection, refraction, multi-path, and shadow fading, the RSS of Wi-Fi signal fluctuates over time, as shown in Figure 4(b). The fluctuation characteristics of Wi-Fi signal result in a great challenge for Wi-Fi indoor localization. Because of the volatility, the Wi-Fi fingerprint for the same place is unstable, which leads to a huge error in indoor localization. And this is the main reason why some other information are needed to improve the localization performance.

Figure 4.

Inherent characteristics of Wi-Fi signal: (a) the signal changes through a wall; the coordinate of wall is 1.7 and the coordinate of the AP is 4.5 and (b) the signal changes over time.

Since the absorption capacity of walls to Wi-Fi signal is greater than air, Wi-Fi signal is easily absorbed by the walls. As shown in Figure 4(a), there is a quite obvious variation when the signal passes through the wall.⁴² Because the indoor environment is divided into rooms by walls, this phenomenon will bring some positive impacts on indoor localization that the users location can be located to different rooms accurately.

Localization accuracy using additional information

Since pure Wi-Fi indoor localization is not accurate, we need some other additional information to improve the accuracy. In this system, the inertial sensors data and an indoor map are utilized to correct Wi-Fi localization. In Figure 5, the trajectories are straight using the map information (align the trajectories with the corridors).

Figure 5.

Trail trajectories: (a) Wi-Fi tracking without any additional information, (b) Wi-Fi tracking with indoor map, and (c) Wi-Fi tracking with indoor map and inertial sensor.

Figure 3 shows a test trajectory, which begins from room 216, then passes through the hallway into another room, and goes out, after a circle around area B, eventually returns to room 216. Figure 5 shows some results of different localization methods. Figure 5(a) illustrates the pure Wi-Fi localization without any other additional information. Figure 5(b) presents the result corrected by map information. Figure 5(c) displays the performance with both map and inertial sensors to reduce the system error.

A Kalman filter is employed in the pure Wi-Fi tracking process. Because of the lack of map information, as shown in Figure 5(a), there are pass-through-wall phenomena at positions 1, 2, 3, 4. Since the system does not know the walking direction and the simple linear assumption, the system may mistake the orientation (such as positions 1, 4, 5, 6 in Figure 5(a)) under the influence of the former state.

Map information can provide additional restrictions for tracking service. As shown in Figure 5(b), the system using Kalman filter and map information avoids the pass-through-wall phenomena in tracking process. We can also observe that the localization error is smaller after turning, which is because the system uses the distance information to improve the estimation of the step size. However, without the direction information, the tracking service may fall in the wrong orientations such as positions 1 and 2 in Figure 5(b).

Inertial sensors can tell the directions that the mobile devices are heading to. Thus, the system with Kalman filter, map, and inertial sensors is much more accurate, as shown in Figure 5(c). The usage of Markov chain can predict all the probability states when the previous state is at a corner, and the inertial sensors can tell which action is the right one; thus, the system avoids the phenomena of pass-through-wall and turning wrong directions.

Figure 6(b) shows the impact on accuracy when using different additional information for indoor localization. The reliability parameter $θ$ takes 0.6 in the tracking process. It can be seen that the accuracy with additional information (either map or inertial sensors) is better than the pure Wi-Fi RSS tracking. And it is more accurate through inertial sensors than map. The most accurate system is the one using both of them. Since the error produced by tracking system which merely uses inertial sensors will continue to increase over time, it is not considered to participate in this comparison.

Figure 6.

CDF for Wi-Fi indoor localization: (a) the effect of θ’s value for tracking and (b) the accuracy using additional information.

Table 1 gives a brief performance description for different systems. It is obvious that compared with the pure Wi-Fi RSS localization, the system with the map information will bring 0.36 m gain, and the system using inertial sensors will bring 0.67 m gain. If the system fuses inertial sensors, map information, and Wi-Fi measurements, it will produce a greater gain of 0.98 m.

Table 1.

The mean error for indoor localization with different additional information.

	Wi-Fi	Wi-Fi+Map	Wi-Fi+INS	Wi-Fi+Map+INS
Mean error $(m)$	2.43	2.07	1.76	1.45

Tracking accuracy with different $θ$

The inertial sensors have a high precision at the beginning and the accuracy is increasingly lowered over time. Thus, the sensors’ raw data need to be adjusted. Meanwhile, correction is also needed by Wi-Fi signals. We use a reliability parameter $θ$ to denote the confidence of them and make them to correct each other. Figure 6(a) shows tracking results with different $θ$ values. It can be seen that the localization accuracy is improved when $θ$ increases from 0 to 0.6. When $θ$ is beyond 0.6, the proportion of small errors (less than 2 m) decreases, but large error increases. This is because the Wi-Fi signal provides a static but rough information, while inertial sensors give dynamic but detail information, and inertial sensors’ data error is cumulating while Wi-Fi tracking error is not accumulated.

Table 2 gives a brief contrast of the performances with different $θ$ values. It is obvious that the reliability of inertial sensors has a great influence on the localization effect. Due to the fact that the reliability of inertial sensors is an empirical value, it may be different for different devices. Therefore, the value must be selected carefully.

Table 2.

The mean error for indoor localization with different values of reliability weight.

$θ$	0	0.2	0.4	0.6	0.8
Mean error $(m)$	2.43	2.16	1.93	1.76	1.87

Conclusion

In many studies, they assume that the more reference points there are, the more accurately the system will achieve, which is proved to be untrue in this article. We give a reference points placement theory that gives a theoretical guide to place reference points.

Focusing on the excessive calculation of cluster algorithms for coarse localization and reference points clustering, the Wi-Fi propagation-based cluster algorithm is proposed. By means of a sorting to replace the complex operations, it reduces the computation and ensures the clustering effect.

The accuracy of Wi-Fi indoor localization results can be improved by importing additional information. In this article, the map information and inertial sensors (magnetometer, accelerometer) information is introduced to reduce the error. The map information does not bring about new error message, but the inertial sensors will cause new error messages. Therefore, the Wi-Fi RSS measurement and sensor data need to be processed. We find that when the reliability parameter of inertial sensor reaches 0.6, it arrives a best accuracy. Tracking service can achieve a 2 m error-bound with 83% probability, and the mean error is 1.45 m.

Footnotes

Handling Editor: Haosheng Huang

Declaration of conflicting interests

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

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Natural Science Foundation of China (NSFC) (grant no. 61772228), National Key Research and Development Program of China (grant no. 2016YFB0201503), Major Special Research Project of Science and Technology Department of Jilin Province (20160203008GX), and Graduate Innovation Fund of Jilin University (2017069).

References

Hao

Xiong

et al . Factor graph-based multipath-assisted indoor passive localization with inaccurate receiver. KSII T Internet Inf 2016; 10: 703–722.

Prorok

Tome

Martinoli

Accommodation of NLOS for ultra-wideband TDOA localization in single- and multi-robot systems. In: International conference on indoor positioning and indoor navigation, Guimaraes, 21–23 September 2011, pp.1–9. New York: IEEE.

Emilsson

Rydell

Chameleon on fire ł thermal infrared indoor positioning. In: IEEE/ION position, location and navigation symposium—PLANS, Monterey, CA, 5–8 May 2014, pp.637–644. New York: IEEE.

Nannuru

Zeng

et al . Radio-frequency tomography for passive indoor multitarget tracking. IEEE T Mobile Comput 2013; 12(12): 2322–2333.

Kajioka

Mori

Uchiya

et al . Experiment of indoor position presumption based on RSSI of bluetooth LE beacon. In: IEEE 3rd global conference on consumer electronics, Tokyo, Japan, 7–10 October 2014, pp.337–339. New York: IEEE.

Xiong

Jamieson

ArrayTrack: a fine-grained indoor location system. In: Proceedings of the 10th USENIX conference on networked systems design and implementation, Lombard, IL, 2–5 April 2013, pp.71–84. Berkeley, CA: USENIX Association.

Yang

Chen

Indoor localization using improved RSS-based lateration methods. In: IEEE global telecommunications conference, Honolulu, HI, 30 November–4 December 2009, pp.1–6. New York: IEEE.

Pan

Zheng

Yang

et al . Transfer learning for WiFi-based indoor localization. Technical report, Association for the Advancement of Artificial Intelligence (AAAI), Chicago, IL, 14 July 2008, pp.43–48.

Yang

Zhou

Liu

From RSSI to CSI: indoor localization via channel response. ACM Comput Surv 2013; 46(2): 25.

10.

Wang

Wei

Liu

et al . Received signal strength-based localization for large space indoor environments. Int J Distrib Sens N. Epub ahead of print 1 January 2017. DOI: 10.1177/1550147716686576.

11.

Yang

Zhou

et al . Mobility increases localizability: a survey on wireless indoor localization using inertial sensors. ACM Comput Surv 2015; 47(3): 54.

12.

Rai

Chintalapudi

Padmanabhan

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

13.

Gilliron

Merminod

. Personal navigation system for indoor applications. In: Proceedings of the 11th IAIN World congress, Berlin, 21–24 October 2003. Citeseer.

14.

Hsu

CH.

An accelerometer based approach for indoor localization. In: Symposia and workshops on ubiquitous, autonomic and trusted computing (UIC-ATC ’09), Brisbane, QLD, Australia, 7–9 July 2009, pp.223–227. New York: IEEE.

15.

Yang

Liu

Smartphones based crowdsourcing for indoor localization. IEEE T Mobile Comput 2015; 14(2): 444–457.

16.

Liu

Geng

Pahlavan

Effects of calibration RFID tags on performance of inertial navigation in indoor environment. In: International conference on computing, networking and communications, Garden Grove, CA, 16–19 February 2015, pp.945–949. New York: IEEE.

17.

Liang

Zhang

Piao

et al . Indoor localization algorithm based on iterative grid clustering and AP scoring. In: IEEE 26th international symposium on personal, indoor, and mobile radio communications, Hong Kong, China, 30 August–2 September 2015, pp.1997–2001. New York: IEEE.

18.

Feng

WSA

Valaee

et al . Compressive sensing based positioning using RSS of WLAN access points. In: Proceedings of IEEE INFOCOM, San Diego, CA, 14–19 March 2010, pp.1–9. New York: IEEE.

19.

Feng

WSA

Valaee

et al . Received-signal-strength-based indoor positioning using compressive sensing. IEEE T Mobile Comput 2012; 11(12): 1983–1993.

20.

Yang

A map-assisted WiFi AP placement algorithm enabling mobile devices indoor positioning. IEEE Syst J 2017; 11: 1467–1475.

21.

Zheng

Huang

Wang

et al . Range-based localization algorithms integrated with the probability of ranging error in wireless sensor networks. Int J Sens Netw 2014; 15(1): 23–31.

22.

Zakra

Yahia Glesk

Path loss measurements and channel modeling of cellular mobile communication at 900 MHz. KSII T Internet Inf 2017.

23.

Liu

Wei

Bai

et al . Autonomous underwater vehicles localisation in mobile underwater networks. Int J Sens Netw 2017; 23(1): 61–71.

24.

Lim

Kung

Hou

et al . Zero-configuration indoor localization over IEEE 802.11 wireless infrastructure. Wirel Netw 2010; 16(2): 405–420.

25.

Biaz

Pandey

et al . ARIADNE: a dynamic indoor signal map construction and localization system. In: Proceedings of the 4th international conference on mobile systems, applications, and services, Uppsala, 19–22 June 2006, pp.151–164. New York: ACM.

26.

Ali

Razak

MRA

Hidayab

et al . Investigation of indoor WiFi radio signal propagation. In: IEEE symposium on industrial electronics and applications, Penang, Malaysia, 3–5 October, pp.117–119. New York: IEEE.

27.

Huang

Zheng

Xiao

et al . Robust localization algorithm based on the RSSI ranging scope. Int J Distrib Sens N. Epub ahead of print 1 January 2015. DOI: 10.1155/2015/587318.

28.

Barsocchi

Lenzi

Chessa

et al . Automatic virtual calibration of range-based indoor localization systems. Wirel Commun Mobile Comput 2012; 12(17): 1546–1557.

29.

Elnahrawy

Martin

RP.

The limits of localization using signal strength: a comparative study. In: First IEEE communications society conference on sensor and ad hoc communications and networks, Santa Clara, CA, 4–7 October 2004, pp.406–414. New York: IEEE.

30.

Langendoen

Reijers

Distributed localization in wireless sensor networks: a quantitative comparison. Comput Netw 2003; 43(4): 499–518.

31.

Whitehouse

Karlof

Culler

A practical evaluation of radio signal strength for ranging-based localization. ACM SIGMOBILE Mobile Comput Commun Rev 2010; 11(1): 41–52.

32.

Lymberopoulos

Lindsey

Savvides

. An empirical characterization of radio signal strength variability in 3-D IEEE 802.15.4 networks using monopole antennas. In: Romer

Karl

Mattern

et al . (eds) Wireless sensor networks. Berlin: Springer, 2006, pp.326–341.

33.

Bahl

Padmanabhan

VN.

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

34.

Chen

Xiu-He

LI.

Signal strength based indoor geolocation. In: IEEE international conference on communications, New York, 28 April–2 May 2002, pp.436–439. New York: IEEE.

35.

Liu

Yang

Sidhom

et al . Accurate WiFi based localization for smartphones using peer assistance. IEEE T Mobile Comput 2014; 13(10): 2199–2214.

36.

Tarzia

Dinda

Dick

et al . Indoor localization without infrastructure using the acoustic background spectrum. In: Proceedings of the 9th international conference on mobile systems, applications, and services, Bethesda, MD, 28 June–1 July 2011, pp.155–168. New York: ACM.

37.

Chung

Donahoe

Schmandt

et al . Indoor location sensing using geo-magnetism. In: Proceedings of the 9th international conference on mobile systems, applications, and services, Bethesda, MD, 28 June–1 July 2011, pp.141–154. New York: ACM.

38.

Martin

Vinyals

Friedland

et al . Precise indoor localization using smart phones. In: Proceedings of the 18th ACM international conference on multimedia, Firenze, 25–29 October 2010, pp.787–790. New York: ACM.

39.

Matic

Papliatseyeu

Osmani

et al . Tuning to your position: FM radio based indoor localization with spontaneous recalibration. In: IEEE international conference on pervasive computing and communications, Mannheim, 29 March–2 April 2010, pp.153–161. New York: IEEE.

40.

Bagosi

Baruch

Indoor localization by WiFi. In: IEEE international conference on intelligent computer communication and processing (ICCP), Cluj-Napoca, 25–27 August 2011, pp.449–452. New York: IEEE.

41.

Potortì

Barsocchi

Girolami

et al . Evaluating indoor localization solutions in large environments through competitive benchmarking: the EvAAL-ETRI competition. In: International conference on indoor positioning and indoor navigation, Banff, AB, Canada, 13–16 October 2015, pp.1–10. New York: IEEE.

42.

Yang

Liu

et al . WILL: wireless indoor localization without site survey. IEEE T Parallel Distr 2012; 24(4): 64–72.

Fingerprint-based Wi-Fi indoor localization using map and inertial sensors

Abstract

Keywords

Introduction

Related work

Model-based approach

Fingerprint-based approach

Fingerprint-based localization model

Reference points placement theory

Definition 1

Recognizable

Definition 2

Maximum reference point set

Theorem 1

Reference points placement

Proof

Offline phase

Definition 3

Wi-Fi signal propagation-based cluster approach

Online phase

Tracking

Using map and inertial sensors in Wi-Fi indoor localization

Using map in offline phase

Using map in tracking phase

Using sensors in tracking phase

The integration of map, inertial sensors, and Wi-Fi RSS in tracking phase

Experiment

Experiment settings

Inherent characteristics of Wi-Fi signal

Localization accuracy using additional information

Tracking accuracy with different θ

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

Tracking accuracy with different $θ$