Received signal strength–based localization for large space indoor environments

Abstract

WiFi-based indoor localization has attracted recent research attention. Large space layout is a special and more complex indoor environment. Most existing indoor localization methods lead to poor accuracy and many of them are not suitable for large space environments. In this article, we propose a novel approach for indoor localization and navigation. In our approach, the expensive training is avoided by utilizing the concept of pre-scheduled path and automatically mapping the WiFi fingerprints to it. For online tracing, we utilize historical sensor data to delineate users’ trajectory and calculate the similarity to all possible paths on the map, then the system chooses the most similar one as the result. The proposed work is evaluated and compared with previous methods. The results show that our approach improves accuracy by 80%.

Keywords

Indoor localization large space environment

Introduction

In recent years, with the development of ubiquitous computing and mobile computing, there is a growing use of location-based services (LBS). As the precondition of indoor LBS, mobile indoor localization attracts increasing interests. Although the accuracy of previous methods can reach to the centimeter level using ultra wideband (UWB),^1,2 infrared and radio frequency (RF),^3,4 beacon,⁵ and multi-antennas,⁶ those systems need to deploy extra facilities, such as UWB senders and receivers. Given that many buildings are equipped with WiFi access points (APs), WiFi-based localization system becomes widely acceptable by users.

However, WiFi-based localization is particularly challenging since the radio signal is often affected by some external factors, such as reflection, refraction, multi-path, shadow fading, scattering, and temporal dynamics.^7–9 In a large space indoor environment, these effects lead to poor accuracy if previous indoor localization methods are used for large space environments.

Currently, large space indoor layout (such as super market and shopping malls) is common in companies due to the need for large space utilization and flexible decoration. However, the large space also causes incomprehensive position cognition when an unfamiliar visitor enters. For many large space indoor environments, unfamiliar visitors generally desiderate navigation or localization service to help them perceive surroundings. Therefore, solving the localization problem in large space indoor environments is of significant value.

In most buildings, signals may encounter a considerable drop when passing through a wall.¹⁰ Owing to the fact that the received signal strength (RSS) values of the same AP are significantly different in different rooms, and the diversity of RSS can be used to distinguish different rooms. In large space indoor environments, such approach is not possible because of lacking of walls.

Compared with other indoor conditions, indoor localization is more necessary for large space environments. In general buildings, rooms are labeled by interrelated room id/name (e.g. continuous numbers). A person can identify his location by the label when he is in the corridor, as long as the room is not too large to tell the exact location. For large space buildings, there often exists obstructions (such as containers, bookshelves, and people), thus it is difficult to tell the location for a new visitor.

In many indoor localization systems, there is a simplification that the collected WiFi fingerprint database is static. The generated data set will be used forever. However, in the real world, the WiFi signal strength will change over temperatures,¹¹ devices,⁸ and even the human body that can also absorb signals.¹² Therefore, the RSS value varies with different temperatures, human traffic, and devices.

The static database cannot adapt the fickle RSS values and will lead to a huge positioning error. To achieve a high-accuracy localization, the fingerprint database should be updated frequently. However, updating the fingerprint database is very costly. There are also a lot of indoor positioning systems without training. For instance, Bisio et al.¹³ generate the database through finite-difference time-domain (FDTD) simulations of the electromagnetic propagation that needs to measure the dielectric properties of all the materials in the indoor environment. Redpin¹⁴ is also a training-less indoor localization system which relies heavily on users’ interaction. WILL is used to map WiFi fingerprints to rooms in a wall-partitioned indoor environment only, but not fitting large space areas.¹⁰ Hence, a high-accuracy indoor localization without training is necessary for large space environments.

In this study, we obtain users’ motion by analyzing the sensor raw data from mobile phones. By mapping the motion to a map, we successfully remove the labeling process of traditional approaches. To achieve competitive localization accuracy, we leverage the trajectory mapping and fingerprint set matching. As a result, our approach is not desired for labeling measured data with corresponding locations and get a good localization accuracy. Our contributions can be summarized as follows:

We present a low-cost indoor localization system by avoiding the data collection phase by making pre-scheduled paths. When collectors walk along the path, the system automatically collects WiFi fingerprints and then maps them to the floor plan.

We propose a high-accuracy indoor localization algorithm for large space environments. The localization in this algorithm is computed by a trajectory mapping method. The trajectory is formed through measuring the inertial measurement unit (IMU).

We implement a demo system to evaluate the performance of our method. Our results show a substantial improvement in accuracy.

The rest of this article is organized as follows. In section “Related work,” we present the basic techniques of estimation of position using a WiFi device. We introduce our system design and present the detailed algorithm in section “System design.” In section “Simulation,” we describe the system implementation and report evaluation results. Finally, section “Conclusion and future work” concludes the article with future directions.

Related work

Previous WiFi-based indoor localization mechanisms (Figure 1) are generally divided into two categories: fingerprinting based and model based.

Figure 1.

Taxonomy of indoor localization systems.

The fingerprinting-based approach contains two stages, offline stage and online stage. In the offline stage, the RSS collector needs to take a mobile device and walk through the building to mark locations and collect RSS values. Then, store RSS values and corresponding coordinates into fingerprint database. In the online stage, the mobile device collects the real-time RSS values and matches them to the RSS values stored in the fingerprint database and then determines the location of the user. Most of these methods utilize RF signals. Radio detection and ranging (RADAR)¹⁵ is an early system using this technique. Horus¹⁶ improves upon RADAR by employing a stochastic description of the RSS-location relationships and using a maximum likelihood–based method to estimate locations. However, this technique faces a great deficiency that it is pretty costly to collect and label the training data in a large scale building.

The model-based method applies a geometrical way to work out locations, and the information used in the location calculation contains RF propagation distances and all AP locations. These approaches assume the signal strength is consistent with a specific model (such as log-distance path loss model). Due to the effects of multi-path and shadow fading, the WiFi strength is quite noisy and highly depends upon environment. Although some previous works have been introduced, for instance, Wang et al.¹⁷ present a curve right–based indoor localization approach to construct a fitted RSS-distance function for each transmitter, PinPoint,¹⁸ Cricket,⁵ and VOR,¹⁹ there is always a large error for this kind of method.

There are many studies presented to improve the accuracy of fingerprint-based indoor localization. Since smartphones have been equipped with a number of sensors, leveraging inertial sensors to improve localization accuracy is gradually possible. Based on the inertial sensor data, we are able to know and record users’ movements, such as sitting, walking, and running.^20–23 The combination of IMU and the WiFi RSS is introduced by Yang et al.,²⁴ and Zhang et al.^25,26 make a fusion of WiFi RSS, IMU, and map information to get a better accuracy. Also, the filter technique is widely used to improve accuracy, such as Chen et al.²⁷ and Evennou and Marx.²⁸ utilize Kalman filter with WiFi RSS and IMU for precision localization. Sheng et al.²⁹ recognize that RSS measurement points cannot be collected densely in large open indoor environments. However, they do not deal with the complexity in large space environments.

Different from the previous works, our indoor localization approach is a combination of WiFi RSS, IMU, and map information and adapts the large space layout (also fits for general environment) without the expensive training. Thus, users will not be involved in data collection.

System design

Motivation

The most costly and error-prone stage in the RSS-based system is the offline fingerprint database manual collection. Because of the time varying characteristic of WiFi signal (as shown in Figure 2), the labeled data are often the average value of many samples at the same position.³⁰ For orientation aware scenario, the labeled data at known locations should be collected toward different orientations.³¹ Assuming that once the collection and labeling job for a collector takes a minute, the distance among reference points is 2 m. For a building which has five floors and each floor is 200 m×100 m, there will be at least 416 h of collection work to training a fingerprint database, which is evidently a huge labor time. Therefore, the RSS-based indoor localization method without or with a little survey is more efficient and interesting.

Figure 2.

RSS value changes over time.

Because of the expensive cost, when the fingerprint database is generated, it is rarely updated, which cannot fit the change caused by variable environments (temperature, human density, devices, etc.), and will lead to low localization accuracy.

For the large space layout building, owing to lacking of walls, the considerable drop while passing through a wall is missing. This makes it more challenging for the large space indoor localization system.

Taking the above into consideration, we present an indoor localization approach for accurate positioning and navigation for large space indoor environments.

System architecture

In this work, as shown in Figure 3, the localization approach consists of four components: coarse trajectory forming (CTF), fingerprint mapping (FM), tracking service (TS), and WiFi fingerprint database. In this section, we present high-level architecture of our method.

Figure 3.

System architecture.

There is little value to localize a user at an independent time point, but the trajectory with time property is valuable for both users and organizations who want to analyze user behavior. Consequently, the temporal and spatial attributes of user’s localization are essential for an indoor localization system.

In this view, we should solve tracking problem instead of localization problem, and the tracking task is not a simple combination of independent localization tasks in a consecutive time point.

Due to the randomness of human movement, the well-known Kalman filter that is well used in a linear situation is not appropriate for indoor tracking. In this work, we record a fixed size of historical information for tracking user trajectory.

CTF is the foundation of FM and TS. During the movement, collectors/users do not need to collect data on purpose, just carry mobile devices (such as cell phone and tablet) and turn on WiFi switch, then system will auto-collect WiFi signal strength, accelerometer sensor data, and magnetometer sensor data with timestamp. Then, the component forming a coarse trajectory can be constructed by the sensor data.

Definition 1. Pre-schedule path. A pre-schedule path is a path that a specified collector will walk along as the administrator pre-planned.

FM is used by collectors who only move around the building (this role can be carried out by security guards, cleaning staff, etc.). These collectors need to wander along the pre-scheduled path and walk around the building periodically. Figure 4 shows an example of pre-scheduled path for librarian in Library of Jilin University. The coarse trajectory generated in this walking will be mapped onto the pre-scheduled path. Then, the corresponding WiFi fingerprints in the trajectory are mapped onto the floor plan. Eventually, every point in the floor plan owns a fingerprint. The database will be updated when the new data belonging to an existing pre-scheduled path come.

Figure 4.

An example of pre-scheduled path for librarian in JLU library.

TS is utilized by users who want to employ the localization service. The system collects the WiFi signal strength with sensor data and then stores these data temporarily. By historical sensor data, the system can form the user’s trajectory and then consult the database to obtain the most possible path.

Fingerprint database is the fundamental component for FM and TS. It stores the output of FM that are fingerprints with corresponding coordinates and is the input of TS. Updating fingerprint database is triggered by FM and TS.

In our approach, training work is greatly simplified by removing the location labeling. Collectors only need to carry their mobile devices and walk along the pre-scheduled paths. Then, the fingerprint database will be auto-generated. We use tracking to replace localizing to achieve temporal and spatial consecutiveness. Since our approach achieves a good localization accuracy in a more complex large space indoor environment, it will also fit for more general scenarios.

CTF

WiFi RSS values, accelerometer sensor data, and magnetometer sensor data are collected by collectors’ mobile devices. The record can be represented as $R_{t} = 〈 F, A, M 〉$ , where t is the timestamp, F indicates the WiFi fingerprint vector, A is the accelerometer data, and M denotes the magnetometer value. Assume there are n APs in the building, then the WiFi fingerprint vector can be defined as

F = [f_{1}, f_{2}, \dots, f_{n}]

(1)

where $f_{i} (0 < i \leq n)$ is the RSS value of ith AP.

We can get the length of user’s trajectory by the accelerometer raw data with timestamp. However, high-performance sensors are prohibitively expensive, and due to the existing noise from sensor raw data, error accumulation is also large.³² Fortunately, we can adopt the time-labeled accelerometer raw data to count steps. Then, the steps can be utilized to estimate the walking distance.³³

We consider the case that user’s trajectory T can be separated into a set of lines ${L}$ . The direction $L_{d}$ of each line is different from its adjacent lines, $L_{d}^{i} \neq L_{d}^{i + 1}$ . The trajectory can be formed by analyzing sensor raw data. First, we convert the accelerometer data ${A}$ to continuous steps S and then mark the orientation $S_{d}^{i}$ of each step through processing the magnetometer data ${M}$ . Finally, the steps ${S}$ can be connected together to get the coarse trajectory T.

Since the directions of steps are obtained by magnetometer sensor data and there may be an angle a between the mobile devices in hand and facing direction, the measured direction $M_{i}$ may not exactly match the walking orientation $S_{d}^{i}$ . Thus, a correction angle $- a$ should be added to the measurement. The value of correction can be obtained by pre-measure or learning in the stage of fingerprints collection.

The CTF algorithm is presented for forming the coarse trajectory. The input in CTF algorithm is the original records of sensor data, and output is the coarse trajectory of users. There are two for loops in CTF. The outer loop processes each record, and the inner loop transforms the raw accelerometer data to steps and deals with the steps in each record. Therefore, the algorithm can be done in O(n) time, n is the total step number. Let $S^{i} = < l_{i}, S_{d}^{i} >$ denote the ith step, where $l_{i}$ is the length of ith step. Using CTF, the coarse trajectory $T = {S_{i}}$ is generated. However, $l_{i}$ is unknown.

Mapping fingerprints

The coarse trajectory cannot be directly used for localization because the component $l_{i}$ of $S^{i}$ is not clear. Different people have different step lengths, so we cannot assign a constant value to $l_{i}$ . We need to finger out the accurate length of each line in the trajectory.

Since the coarse trajectory from a collector is a tracking of pre-scheduled path, each line from this trajectory can be mapped to a real line in the floor plan. According to the $S_{d}^{i}$ component, we can separate the steps of the coarse trajectory into different continuous step sets in which the steps compose to a straight line. Let $[x_{s}, y_{s}]$ and $[x_{e}, y_{e}]$ denote the starting coordinate and ending coordinate of a real linear path in the map which is mapped from the trajectory.

Assuming a user walks along this line with a fixed step length, then the length of each step in this line is

\frac{\sqrt{{(x_{e} - x_{s})}^{2} + {(y_{e} - y_{s})}^{2}}}{n}

(2)

where n is the step number in this line. Then, the coordinate of starting point for ith step is

[x_{s} + (i - 1) \times \frac{x_{e} - x_{s}}{n}, y_{s} + (i - 1) \times \frac{y_{e} - y_{s}}{n}]

(3)

and the coordinate of ending point for ith step is

[x_{s} + i \times \frac{x_{e} - x_{s}}{n}, y_{s} + i \times \frac{y_{e} - y_{s}}{n}]

(4)

Algorithm 1: Coarse trajectory forming (CTF).
Input: ${R_{t}}$
Output: trajectory
Initial trajectory to null;
p = 1;
j = 1;
for $R_{k}$ do
transform ${A_{k}}$ to continuous steps ${S'}$ ;
$S ↢ S'$ ;
i = p;
for $S_{d}^{i}$ do
if $S_{d}^{i} \neq S_{d}^{i - 1}$ then
$L_{j} ↢ {S^{p}, \dots, S^{i - 1}}$ ;
$T ↢ L_{j}$ ;
j++;
p = i;
end
end
end
$L_{j} ↢ {S^{p}, \dots, S^{\max}}$ ;
$T ↢ L_{j}$ ;

Algorithm 2: Fingerprint mapping (FM).
Input: ${R_{t}}$ , path
Output: D
T = CTF( ${R_{t}}$ );
for $L_{j} \in T$ do
$n = \| S^{i} \in L_{j} \|$ ;
calculate the step length in this line as
$l = \frac{\sqrt{{(x_{e} - x_{s})}^{2} + {(y_{e} - y_{s})}^{2}}}{n}$ ;
for $R_{i} \in L_{j}$ do
$C_{i} = [x_{s} + i \times \frac{x_{e} - x_{s}}{n}, y_{s} + i \times \frac{y_{e} - y_{s}}{n}]$ ;
end
end

Then, the coordinate of WiFi signal’s fingerprint can be obtained by its corresponding record. The mapping relationship of fingerprint and coordinate can be stored in database as $D_{i} = < F_{i}, C_{i} >$ , where $F_{i}$ indicates the WiFi fingerprint vector and $C_{i}$ is the corresponding coordinate in the floor plan.

Since the RSS value varies with external factors (human density, temperature, etc.), to achieve an accurate localization result, the fingerprint database should be updated with the change of environment. Because the mapping fingerprint operation occurs as long as the collectors wander around periodically, the update is triggered frequently. When the TS is available for users, the query data are not only used for localization but also updates the fingerprint database. Therefore, the fingerprint database is suitable for environments.

The following FM algorithm is presented for mapping the WiFi signal fingerprints to the coordinate of the floor plan. In FM, the input is the pre-scheduled path with its coordinate, the collected records of WiFi fingerprints, and sensor data, and the output is the map set of fingerprint and coordinate. If there are some similar pre-scheduled paths (as shown in Figure 5, the shapes of these paths are same but part of the length of lines are different), the approach cannot distinguish from the correct mapping. Therefore, the pre-scheduled path should be one of the inputs of FM. There are two for loops in this algorithm; from line 2 to line 6, that is, the outer loop and each loop processes one virtual line from the trajectory. The inner loop, from line 5 to line 6, deals with one single virtual line, and each loop handles one record in $R_{t}$ . Therefore, FM is an O( $n \times m$ ) complexity time algorithm, where n is the records number and m indicates the maximum step number of virtual lines.

Figure 5.

An example of similar pre-scheduled paths.

TS

Different from the traditional ways, fingerprints obtained from FM are not the average value of multiple measurements. To overcome this shortcoming about inaccurate fingerprints, we leverage the trajectory matching to fetch all similar path sets. Then, we adopt the fingerprints matching to find out the most possible path from the path set.

The TS stores a fixed size of historical records $R_{t}$ . The record set is continuously updated. When historical records of WiFi fingerprints are renewed, the new virtual trajectory of this user can be generated by CTF algorithm. In our indoor localization approach, the positioning problem can be settled by means of mapping a virtual trajectory to a path in the floor plan.

Assuming users walk in a constant step length, the possible length is from $l_{\min}$ to $l_{\max}$ . Then, the virtual coarse trajectory formed by algorithm CTF can be transformed to a possible trajectory set $T = {t_{i}}$ through setting the step length from $l_{\min}$ to $l_{\max}$ .

For each $t_{i}$ from T there are a set of possible mapping trajectories in the floor plan. Let ${{\hat{t}}_{i}}$ denote the set. Then, each WiFi signal fingerprint $F_{j}$ from historical records corresponds to a fingerprint ${\hat{F}}_{j}$ from the database. We can use interpolation technique to generate the missing fingerprint which is corresponding to $F_{j}$ .

Then, the tracking mapping problem can be described as follows

argmi n_{\hat{t_{i}}} {\sum_{j = 1}^{n} d (F_{j}, \hat{F_{j}}) F_{j} \in t_{i}, \hat{F_{j}} \in \hat{t_{i}}}

(5)

where $d (F_{j}, {\hat{F}}_{j})$ is the difference function of two vectors. Simply, we can use the Euclidean distance.

Essentially, TS in our approach is a graph mapping problem. The fingerprints are the nodes, and edges are the geographical links with orientation attribute. The problem can be described as mapping a sub-graph to the whole graph and tell which is the corresponding newest node.

The graph mapping problem is NP-hard. Thus, there are many possibilities for a specific trajectory and the calculation of likelihood is costly. Therefore, we need to narrow down the number of possible trajectories. Here, a cluster technique is presented to classify the WiFi fingerprints.

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 cluster of a fingerprint F is k if

\forall j, f_{k} \geq f_{j}, n \geq j, k > 0

(6)

Algorithm 3: Tracking service (TS).
Input: ${R_{t}}$ , D, map
Output: trajectory
T = CTF( ${R_{t}}$ );
$c = argma x_{k} {f_{i}^{t}}$ ;
for $l_{\min} \leq l \leq l_{\max}$ do
forall possible trajectory in floor plando
ifthe cluster of trajectory is cthen
$p = \sum_{j = 1}^{n} d (F_{j}, \hat{F_{j}})$ $F_{j} \in t_{i}, \hat{F_{j}} \in \hat{t_{i}}$ ;
end
end
$T ↢ T^{k}$ , $T^{k}$ with the maximum $T_{p}$ ;
end
choose the most likely trajectory in T as the trajectory;

In this approach, only a sorting operation is used to estimate which cluster a fingerprint belongs to. Thus, our cluster approach is much less complex than the ones proposed before (such as the approaches by Frey and Dueck³⁴ and Feng et al.^30,35).

Since the cluster function is a deterministic function, the cluster of each WiFi fingerprint will not be changed after it is measured. To expedite online tracking, clustering can be done offline.

In our approach, the possible trajectory is filtrated considering whether the last fingerprint and the ending record’s fingerprint fall into the same cluster. If they belong to the same cluster, then add the trajectory to the possible trajectory set.

Another way to reduce the potential trajectories is to narrow down the gap of $l_{\min}$ to $l_{\max}$ . We can use the historical information of step length from a same user calculated in TS and then after execution for a period of time, choose the minimum value as $l_{\min}$ and the maximum value as $l_{\max}$ .

The TS algorithm is presented for localizing the users’ positions. The inputs of this algorithm are the floor plan of the building, the historical records, and the WiFi fingerprint database, and the output is the trajectory which is corresponding to the historical tracking data. In this algorithm, there is a double-deck loop. The outer loop iteratively finds out the most likely length of user’s steps. The inner loop fetches the most likely trajectory for the given length of a step. The variable c in TS denotes the cluster of $R_{t}$ . Eventually, TS figures out user’s trajectory for the tracking data. It is an O( $n \times m$ ) time complexity algorithm, where n is the number of possible lengths of a step and m is the maximum number of a trajectory in the same cluster.

The WiFi fingerprints measured by TS are not only used to localize mobile devices but also update fingerprint database to keep the database latest with the environment varying.

Simulation

Simulation setup

All experiments in this article are conducted in part of second floor in the Library of Jilin University. We deploy 12 APs in the 20 m×20 m area. The distribution of clusters generated by clustering is demonstrated in this section. We illustrate how the AP number, update period, and historical time effect the positioning accuracy. And the stability and performance are also considered in this section.

Comparison schema

In many indoor localization approaches, K-nearest neighbors (KNN) and Kalman filter based are two classic indoor localization approaches and used in many research works.^27,36

KNN goes through the fingerprint database and picks up k reference points whose fingerprints match best to the real-time one.

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}

(7)

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

Kalman filter 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}

(8)

where process noise $W_{t}$ and observation noise $V_{t}$ follow Gaussian distribution, and they are independent on each other, namely, $W_{t} ~ (0, Q)$ , $V_{t} ~ (0, R)$ . Q and R can be obtained by experience, and they are invariable 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}}

(9)

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}

(10)

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}

(11)

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

Localization accuracy

Since we choose the strongest RSS index as the indicator to cluster fingerprints, and the nearer the reference point to the AP, the stronger the RSS value, the fingerprints belonging to the same cluster are geographically adjacent. Moreover, the area of one cluster is related to the corresponding AP’s power. The clustering result is shown in Figure 6. Each colored point is a fingerprint, and the fingerprints with the same color belong to the same cluster.

Figure 6.

Cluster of WiFi fingerprints at JLU library.

In a complex indoor environment, the coverage range of a single AP is limited, and the weak RSS will lead to a poor result. Thus, we evaluate relationship between the number of APs and the localization accuracy. Figure 7 shows that the mean errors of systems, respectively, using KNN, Kalman filter, and TS sharply drop as the AP number varies from 3 to 6, and then the downtrend of mean error decreases slowly. To further study their relationship, we use the concept of WiFi density.

Figure 7.

AP number versus mean error, update period 0.5 h.

Definition 2. WiFi density. WiFi density for a location is the accessible AP number at this position.

As shown in Figure 8, with the strengthening of WiFi density, the mean error of the localization systems goes down. As one AP may not cover the whole field, the minimum WiFi density and the AP number are not in linear correlation. Here, we use a homogeneous deployment way to maximize the minimum WiFi density. As the result indicates, the curves almost match the tail of Figure 7.

Figure 8.

Density versus mean error, update period 0.5 h.

The RSS value is effected by temperature and human traffic; thus, the localization accuracy is correlative with the freshness of WiFi fingerprints. As shown in Figure 9, when the update period is exponentially enlarging, the mean errors nearly linearly increase. As the time goes on, since the variation of temperature and human traffic will not exceed the maximum value, the mean errors decline is almost stable. From Figure 9, we can see whether the WiFi fingerprints update timely, and the localization accuracy can improve about 10%.

Figure 9.

Update period versus mean error, nine APs.

The TS stores a fixed number of historical records, and the records are used to describe the trajectory of users. Thus, the more records there are, the less particular information can be used which leads to less matched paths. Since TS compares the likelihood of the whole historical fingerprints with the possible trajectory fingerprints stored in database, the longer the fixed number is, the less influence caused by RSS fluctuating will be. As illustrated in Figure 10, the mean errors go down as the historical time magnifies. Particularly, when there is only one record, the approach degenerates to be KNN.

Figure 10.

Mean error versus historical time.

Stability is also an importance attribute for the localization approach. Figure 11 shows a 10-min execution for TS. Let $m_{t_{i}}$ denote the mean error of time $t_{i}$ , then $M_{t_{i}} = 1 / n \sum_{t} m_{t_{i}}$ , where n is the number of total time till $t_{i}$ . Here, the mean error is $M_{t_{i}}$ . At the first minute, the mean errors exponentially decrease, which is owing to the missing of historical records. Then, the mean errors are almost stable as the number of historical records reaches the predetermined fixed size.

Figure 11.

Mean error versus execution time, historical time 5 s.

Reducing the training time is an effective way for service providers to cut their cost. Comparing with the traditional way, as illustrated in Figure 12, our approach is much less costly in training. The traditional training method needs to label the location and collect the average RSS value which cost about a minute for an reference point (RP). In our approach, the collector only needs to walk by. Although, we do not use the average RSS value, we still get a high localization accuracy because of the trajectory matching.

Figure 12.

Training time.

We further compare our approach with the KNN method and Kalman Filter method. The KNN is just a connection of individual localization results. Kalman Filter method uses the Kalman filter in the tracking. The cumulative distribution function (CDF) is shown in Figure 13. The results of all methods are Laplace distributed, and TS has a smaller $μ$ and b, which means TS achieves a better accuracy. As illustrated in Figure 13, TS improves the accuracy by 80%.

Figure 13.

CDF of mean error, update period 0.5 h, nine APs.

Conclusion and future work

In this work, we propose a training-less indoor localization approach by automatically collecting the WiFi RSS and sensor data and then mapping the WiFi fingerprints to the coordinates in the corresponding pre-scheduled path. Through calculating the likelihoods with all possible trajectories formed by historical sensor data and then choosing the most similar one as the localization result, TS achieves an accurate positioning approach for the large space environment which is prevalent in modern buildings. Since our approach achieves a good localization accuracy in a more complex large space indoor environment, it will also fit for more general scenarios.

In this work, we assume users always hold the mobile device in hand, but he or she may put it in his pocket and watch it when necessary, which makes the magnetometer sensor useless. Therefore, in the future, we will consider the relationship of the value of sensor data with the step length and the situation with missing magnetometer data.

Footnotes

Academic Editor: Gang Wang

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 Key Research and Development Program of China (Grant Nos 2016YF B0201503 and 2016YFB0701101), National Natural Science Foundation of China (NSFC) (Grant Nos 61602205, 51627805, and 61170004), Specialized Research Fund for the Doctoral Program of Higher Education (20130061110052), Major Special Research Project of Science and Technology Department of Jilin Province (20160203008GX), Key Science and Technology Research Project of Science and Technology Department of Jilin Province (20140204013GX), and EUFP7 Projects EVANS (GA-2010-269323) and MONICA (GA-2011-295222).

References

Gezici

Tian

Giannakis

. Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks. IEEE Signal Proc Mag 2005; 22(4): 70–84.

Prorok

Tomé

Alcherio

Accommodation of NLOS for ultra-wideband TDOA localization in single- and multi-robot systems. In: Proceedings of the international conference on indoor positioning and indoor navigation (EPFL-CONF-168216), Guimarães, 21–23 September 2011.

Kolodziej

Hjelm

Local positioning systems: LBS applications and services . Boca Raton, FL: CRC Press, 2006.

Liu

Darabi

Banerjee

. Survey of wireless indoor positioning techniques and systems. IEEE T Syst Man Cy C 2007; 37(6): 1067–1080.

Priyantha

Chakraborty

Balakrishnan

The cricket location-support system. In: Proceedings of the 6th annual international conference on mobile computing and networking, Boston, MA, 6–11 August 2000, pp.32–43. New York: ACM.

Xiong

Jamieson

Arraytrack: a fine-grained indoor location system. In: Proceedings of the 10th USENIX symposium on networked systems design and implementation (NSDI 13), Lombard, IL, 2–5 April 2013, pp.71–84.

Yang

Chen

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

Pan

Zheng

Yang

. Transfer learning for WiFi-based indoor localization. In: Proceedings of the association for the advancement of artificial intelligence (AAAI) workshop, Chicago, IL, 13–17 July 2008, p.6

Yang

Zhou

Liu

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

10.

Yang

Liu

. WILL: wireless indoor localization without site survey. IEEE T Parall Distr 2013; 24(4): 839–848.

11.

Yin

Yang

Adaptive temporal radio maps for indoor location estimation. In: Proceedings of the third IEEE international conference on pervasive computing and communications (PerCom 2005), Kauai Island, HI, 8–12 March 2005, pp.85–94. New York: IEEE.

12.

Wessapan

Rattanadecho

Numerical analysis of specific absorption rate and heat transfer in human head subjected to mobile phone radiation: effects of user age and radiated power. J Heat Transf 2012; 134(12): 121101.

13.

Bisio

Cerruti

Lavagetto

. A trainingless WiFi fingerprint positioning approach over mobile devices. IEEE Antenn Wirel Pr 2014; 13: 832–835.

14.

Bolliger

Redpin-adaptive, zero-configuration indoor localization through user collaboration. In: Proceedings of the first ACM international workshop on mobile entity localization and tracking in GPS-less environments, San Francisco, CA, 14–19 September 2008, pp.55–60. New York: ACM.

15.

Bahl

Padmanabhan

VN.

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

16.

Youssef

Agrawala

The Horus WLAN location determination system. In: Proceedings of the 3rd international conference on mobile systems, applications, and services, Seattle, WA, 6–8 June 2005, pp.205–218. New York: ACM.

17.

Wang

Zhou

Liu

. Indoor localization based on curve fitting and location search using received signal strength. IEEE T Ind Electron 2015; 62(1): 572–582.

18.

Youssef

Rieger

. PinPoint: an asynchronous time-based location determination system. In: Proceedings of the 4th international conference on mobile systems, applications and services, Uppsala, 19–22 June 2006, pp.165–176. New York: ACM.

19.

Niculescu

Nath

VOR base stations for indoor 802.11 positioning. In: Proceedings of the 10th annual international conference on mobile computing and networking, Philadelphia, PA, 26 September–1 October 2004, pp.58–69. New York: ACM.

20.

Brajdic

Harle

. Walk detection and step counting on unconstrained smartphones. In: Proceedings of the 2013 ACM international joint conference on pervasive and ubiquitous computing, Zurich, 8–12 September 2013, pp.225–234. New York: ACM.

21.

Park

Shin

Cha

Smartphone-based pedestrian tracking in indoor corridor environments. Pers Ubiquit Comput 2013; 17(2): 359–370.

22.

Park

Patel

Curtis

. Online pose classification and walking speed estimation using handheld devices. In: Proceedings of the 2012 ACM conference on ubiquitous computing, Pittsburgh, PA, 5–8 September 2012, pp.113–122. New York: ACM.

23.

Yang

Zhao

. Footprints elicit the truth: improving global positioning accuracy via local mobility. In: Proceedings of the IEEE INFOCOM, Turin, 14–19 April 2013, pp.490–494. New York: IEEE.

24.

Yang

Zhou

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

25.

Zhang

Dai

. An area state-aided indoor localization algorithm and its implementation. In: Proceedings of the IEEE international conference on communication workshop (ICCW), London, 8–12 June 2015, pp.736–741. New York: IEEE.

26.

Zhang

Dai

. Indoor localization algorithm for smartphones (arXiv preprint arXiv: 150307628), 2015, https://arxiv.org/abs/1503.07628

27.

Chen

Zou

Jiang

. Fusion of WiFi, smartphone sensors and landmarks using the Kalman filter for indoor localization. Sensors 2015; 15(1): 715–732.

28.

Evennou

Marx

Advanced integration of WiFi and inertial navigation systems for indoor mobile positioning. EURASIP J Adv Sig Pr 2006; 2006: 164.

29.

Sheng

Mao

. The collocation of measurement points in large open indoor environment. In: Proceedings of the IEEE conference on computer communications (INFOCOM), Hong Kong, 26 April–1 May 2015, pp.2488–2496. New York: IEEE.

30.

Feng

WSA

Valaee

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

31.

Feng

WSA

Valaee

. Orientation-aware indoor localization using affinity propagation and compressive sensing. In: Proceedings of the 3rd IEEE international workshop on computational advances in multi-sensor adaptive processing (CAMSAP), Noord, Aruba, 13–16 December 2009, pp.261–264. New York: IEEE.

32.

Woodman

Harle

Pedestrian localisation for indoor environments. In: Proceedings of the 10th international conference on ubiquitous computing, Seoul, Korea, 21–24 September 2008, pp.114–123. New York: ACM.

33.

Jimenez

Seco

Prieto

. A comparison of pedestrian dead-reckoning algorithms using a low-cost MEMS IMU. In: Proceedings of the IEEE international symposium on intelligent signal processing (WISP 2009), Budapest, 26–28 August 2009, pp.37–42. New York: IEEE.

34.

Frey

Dueck

Clustering by passing messages between data points. Science 2007; 315(5814): 972–976.

35.

Feng

WSA

Valaee

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

36.

Yang

A map-assisted WiFi AP placement algorithm enabling mobile device’s indoor positioning. IEEE Syst J 2016; PP(99): 1–9.