[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Effects of Baffle Configuration on Mixing in a T-Shaped Micro-Channel
Next Article in Special Issue
PDR/INS/WiFi Integration Based on Handheld Devices for Indoor Pedestrian Navigation
Previous Article in Journal
Towards Improved Airborne Fire Detection Systems Using Beetle Inspired Infrared Detection and Fire Searching Strategies
Previous Article in Special Issue
Reciprocal Estimation of Pedestrian Location and Motion State toward a Smartphone Geo-Context Computing Solution
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Micromachines
Volume 6
Issue 6
10.3390/mi6060747
micromachines-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

WiFi-Aided Magnetic Matching for Indoor Navigation with Consumer Portable Devices

by
You Li
1,2,*,
Yuan Zhuang
1,
Haiyu Lan
1,
Peng Zhang
2,
Xiaoji Niu
2 and
Naser El-Sheimy
1
1
Department of Geomatics Engineering, University of Calgary, Calgary, AB T2N 1N4, Canada
2
GNSS Research Center, Wuhan University, Wuhan 430079, China
*
Author to whom correspondence should be addressed.
Micromachines 2015, 6(6), 747-764; https://doi.org/10.3390/mi6060747
Submission received: 30 May 2015 / Revised: 10 June 2015 / Accepted: 10 June 2015 / Published: 16 June 2015
(This article belongs to the Special Issue Next Generation MEMS-Based Navigation—Systems and Applications)
Browse Figures
Figure 1
<p>Algorithm architecture.</p> "> Figure 2
<p>Procedure of training phases for magnetic matching and WiFi fingerprinting.</p> "> Figure 3
<p>Using WiFi positioning results to limit search space for magnetic matching.</p> "> Figure 4
<p>Trajectories used to generate WiFi and magnetic databases (DBs) at the Energy Environment Experiential Learning (EEEL).</p> "> Figure 5
<p>WiFi signal distribution at EEEL.</p> "> Figure 6
<p>Magnetic distribution at EEEL.</p> "> Figure 7
<p>Test trajectory at EEEL (with abundant WiFi and magnetic information).</p> "> Figure 8
<p>Magnetic matching (MM) result at EEEL.</p> "> Figure 9
<p>WiFi fingerprinting result at EEEL.</p> "> Figure 10
<p>WiFi-aided MM result at EEEL.</p> "> Figure 11
<p>MM position errors at EEEL.</p> "> Figure 12
<p>WiFi position errors at EEEL.</p> "> Figure 13
<p>WiFi-aided MM position errors at EEEL.</p> "> Figure 14
<p>WiFi signal distribution at the Engineering building (ENB).</p> "> Figure 15
<p>Magnetic distribution at ENB.</p> "> Figure 16
<p>MM result at ENB.</p> "> Figure 17
<p>WiFi fingerprinting result at ENB.</p> "> Figure 18
<p>WiFi-aided MM result at ENB.</p> "> Figure 19
<p>MM position errors at ENB.</p> "> Figure 20
<p>WiFi position errors at ENB.</p> "> Figure 21
<p>WiFi-aided MM position errors at ENB.</p> ">
Versions Notes

Abstract

:
This paper presents a WiFi-aided magnetic matching (MM) algorithm for indoor pedestrian navigation with consumer portable devices. This algorithm reduces both the mismatching rate (i.e., the rate of matching to an incorrect point that is more than 20 m away from the true value) and computational load of MM by using WiFi positioning solutions to limit the MM search space. Walking tests with Samsung Galaxy S3 and S4 smartphones in two different indoor environments (i.e., Environment #1 with abundant WiFi APs and significant magnetic features, and Environment #2 with less WiFi and magnetic information) were conducted to evaluate the proposed algorithm. It was found that WiFi fingerprinting accuracy is related to the signal distributions. MM provided results with small fluctuations but had a significant mismatch rate; when aided by WiFi, MM’s robustness was significantly improved. The outcome of this research indicates that WiFi and MM have complementary characteristics as the former is a point-by-point matching approach and the latter is based on profile-matching. Furthermore, performance improvement through integrating WiFi and MM depends on the environment (e.g., the signal distributions of magnetic intensity and WiFi RSS): In Environment #1 tests, WiFi-aided MM and WiFi provided similar results; in Environment #2 tests, the former was approximately 41.6% better. Our results supported that the WiFi-aided MM algorithm provided more reliable solutions than both WiFi and MM in the areas that have poor WiFi signal distribution or indistinctive magnetic-gradient features.

1. Introduction

While Global Navigation Satellite Systems (GNSS) based outdoor navigation has greatly advanced over the past few decades, positioning and navigation in indoor and deep urban areas are still open issues [1]. The challenges include unavailable or degraded GNSS signals, complex indoor environments, necessity of using low-grade devices, etc. Wireless positioning technologies have been applied to provide long-term absolute positions [2]. Especially, as WiFi receivers are ubiquitous in consumer devices such as smartphones, it is feasible to implement WiFi positioning in public areas with existing WiFi infrastructures. WiFi fingerprinting approaches based on received signal strengths (RSS) have gained a large amount of attention, as they can provide position without any knowledge of the access point (AP) location or signal-propagation model [3]. However, the utilization of WiFi requires the creation and maintenance of a network. Furthermore, RSS fluctuate significantly due to obstructions, reflections [4], and multipath effects [5]. Fluctuations of RSS have limited the promotion of wireless positioning technologies [6].
Advances in Micro-Electro-Mechanical Systems (MEMS) technology have made it possible to produce chip-based sensors, such as inertial sensors (i.e., accelerometers and gyros) and magnetometers. MEMS sensors have become appropriate candidates for motion tracking and navigation applications because they are small and lightweight, consume little power, and are extremely low-cost [7]. Especially, inertial sensors are ideal for providing continuous information in indoor/outdoor environments because they are not dependent on the transmission or reception of signals from an external source [8]. However, inertial sensors provide only short-term accuracy and suffer from accuracy degradation over time due to the existence of sensor errors [9]. Calibration is a useful way to remove many deterministic sensor errors and improve sensor-based navigation [10]; however, MEMS inertial sensors suffer from significant run-to-run biases and thermal drifts [11]. Especially, the heading error will grow when there is no aiding information [12]. Magnetometers can assist the heading estimation by sensing the geomagnetic field [13]. Nevertheless, the local magnetic field is susceptible to interferences from man-made infrastructure in indoor or urban environments [14], which makes magnetometer-derived heading angle unreliable. Magnetic interference is a critical issue when magnetometers are used as a compass indoors.
However, the indoor magnetic interference can also be exploited as an advantage by leveraging the magnetic abnormalities as fingerprints [15,16]. The magnetic matching (MM) approach has been proposed based on the hypothesis that the indoor magnetic field is stable over time and non-uniform (i.e., changes significantly) with location [17,18]. MM is achieved in two phases (steps): The offline training (pre-survey) phase and the online positioning phase. The training phase is conducted to build or update a “location, magnetic intensity” database (DB) that consists of a set of reference points (RPs) with known coordinates and the magnetic intensity on these RPs, while the positioning step is implemented to find the closest match between the features of the measured magnetic intensity and those stored in the DB. While MM utilizes a similar idea to WiFi fingerprinting, it is independent from any infrastructure, as the magnetic field is omnipresent. The challenge for MM is that magnetic data only consists of three components. Because the heading is generally unknown, it is only feasible to extract two components with the help of accelerometers, i.e., vertical magnetic intensity and horizontal magnetic intensity (or total magnetic intensity and inclination). To increase the magnetic fingerprint dimension without extra sensors, the profile-matching method has been proposed [19]. A sequence of observations are saved in the memory and then compared with the candidate profiles stored in the DB. There are well-developed profile-matching methods such as terrain contour matching (TERCOM) [18,19] and iterative closest contour point (ICCP) [20]. To obtain the optimal match, the profile length should be long enough to show the profile feature; moreover, the length of the measured profile should be the same as that of the stored profiles. However, for indoor cases, sensors are low-end and there is no effective constraint if the device is not fixed on the body (e.g., on-foot or in-belt). Thus, the sensor-based navigation error will accumulate quickly and make it difficult to measure the accurate moving distance [21]. In this paper, we calculate the rough length of the measured profile using the steps detected by accelerometers. Because accurate and real-time step-length estimation is still an open issue in pedestrian navigation, we utilize the dynamic time warping (DTW) algorithm for matching with inaccurate profile length [22].
This paper presents a WiFi-aided MM navigation algorithm that uses off-the-shelf sensors in consumer portable devices and existing WiFi infrastructures. The basic idea is using WiFi results to limit the MM search space, so as to reduce both the mismatching rate and the computational load. This algorithm was designed after comparing WiFi and MM, and taking advantage of the merits of each technology. We found that MM results had small error fluctuations but had a significant mismatch rate (i.e., the rate of matching to an incorrect point that was more than 20 m away from the true value). In contrast, WiFi fingerprinting can provided results with low mismatch rate; however, the WiFi fingerprinting accuracy strongly depended on the signal distributions. Finally, the proposed WiFi-aided MM provided more reliable results than either the independent use of WiFi or MM and had a lower mismatch rate.
The paper is organized as follows: Section 2 outlines the architecture of the WiFi-aid magnetic matching algorithm and a detailed description of each component; Section 3 investigates the navigation performance of different technologies; and Section 4 draws the conclusions.

2. WiFi-Aided Magnetic Matching Algorithm

The block diagram of the algorithm architecture is shown in Figure 1. This section first describes the principle of magnetic matching and WiFi fingerprinting, and then it introduces the WiFi-aided magnetic matching algorithm.
Micromachines 06 00747 g001 1024
Figure 1. Algorithm architecture.
Figure 1. Algorithm architecture.
Micromachines 06 00747 g001
MM and WiFi fingerprinting utilize similar ideas and both consist of the training phase and the positioning phase. This section introduces these two phases separately.

2.1. Training Phase for WiFi Fingerprinting and Magnetic Matching

The purpose of training is to build or update a “location, RSS” DB and a “location, magnetic intensity” DB. The key to generating reliable DBs is obtaining accurate RP coordinates. The choice of the DB training method is a trade-off between cost and accuracy. Different training approaches have been researched according to various requirements. The first approach is to survey at every RP and record its fingerprint. This point-by-point method can improve the DB reliability by averaging the measurements (RSS or magnetic intensity) at each RP [23] and even provide a rough estimate of orientation [24]. However, it is time- and labor-consuming when dense RPs are selected to cover an entire area of interest, and a surveyor needs to mark the position of all RPs manually [25]. The point-by-point training can take up to several hours even for a small building [26].
To reduce the time and labor costs, we adopt the walk-survey method. The walk-survey method is used based on landmarks (i.e., points with known coordinates) or floor plans (i.e., the true positions of corners and intersections and the true orientation of corridors) and a constant-speed assumption. A surveyor has to walk with a constant speed along each link between landmarks, such as corners or intersections, over the pre-designed path. The positions of landmarks are determined on a digital map, while those of other RPs and the links between landmarks are calculated by the arrival time and the distance between landmarks. Although the DB generated by walk-survey tends to be less accurate than that from the point-by-point approach, walk-survey is significantly more time-effective. Furthermore, with inertial sensors on smartphones, we utilize the steps detected by accelerometers to replace the constant-speed assumption by a constant-step-length assumption, and we use the heading changes calculated from gyros to remove the requirement for straight walking. The procedure of training and positioning is shown in Figure 2.
Micromachines 06 00747 g002 1024
Figure 2. Procedure of training phases for magnetic matching and WiFi fingerprinting.
Figure 2. Procedure of training phases for magnetic matching and WiFi fingerprinting.
Micromachines 06 00747 g002
Magnetometers on smartphones have a higher sampling rate (commonly more than 10 Hz). Therefore, we store every step as a RP. Furthermore, we assume that the device moves with a constant speed within each step; thus, we calculate the magnetic intensity at a set of points within this step through interpolation. The interpolated points are also stored as MM RPs. The MM fingerprint at the k-th RP is recorded as:
F M k = { p o s k ,   σ p o s k ,   m k }
where posk and σposk are the location of RPk and its accuracy, mk is the magnetic intensity vector at RPk. The approach for determining the σpos values is related with the DB training method used. According to the DB training method we use, we calculate the value σpos for the step points on the i-th link (or arc) by σ p o s ,   p = α ⋅ L i N i , where Li is the length of the i-th link, Ni is the number of steps on this link, and α is a scale factor. σpos is an optional parameter. If there is no σpos in the fingerprints, all RPs have the same weight in the DB. The fingerprints on the interpolated points between two adjacent step points (e.g., m1 and m2) are set by the following method: Assuming the fingerprints at m1 and m2 are FMm1 and FMm2, and there are n interpolated points between m1 and m2, then the fingerprints at the i-th interpolated point is F M m 1 + i n + 1 ( F M m 2 − F M m 1 ) , where 1 ≤ i ≤ n .
In general, more elements in each fingerprint are better for matching. With accelerometers on smartphones, we detect the roll and pitch angles and in turn extract the vertical and horizontal magnetic intensities. The roll and pitch angles are calculated as:
ϕ = a tan 2 ( − f y ,   − f z ) θ = a tan 2 ( f x ,   f y 2 + f z 2 )
where Φ and θ are the roll and pitch angles, fi (i = x, y, z) is the accelerometer-measured specific force along the i-th axis.
We can transfer the magnetic vector in body-frame (i.e., the magnetometer measurements) to that in navigation frame (i.e., the local magnetic vector) by using [27]:
B n = C b n B b
where C b n is the direction cosine matrix (DCM), which can be represented by the roll, pitch, and heading angles as:
C b n = [ c θ c ψ − c ϕ s ψ + s ϕ s θ c ψ s ϕ s ψ + c ϕ s θ c ψ c θ s ψ c ϕ c ψ + s ϕ s θ s ψ − s ϕ c ψ + c ϕ s θ s ψ − s θ s ϕ c θ c ϕ c θ ]
where Ψ is the heading angle. s and c are the shorthand notations of sin( ) and cos( ), respectively.
Let B b = [ B x B y B z ] T and B n = [ B N B E B D ] T , the vertical magnetic intensity can be calculated by:
B D = − sin θ ⋅ B x + sin ϕ cos θ ⋅ B y + cos ϕ cos θ ⋅ B z
Therefore, we construct the magnetic intensity vector as m = [ B B D B H ] , where B = | B b | is the total magnetic intensity, and B H = B 2 − B D 2 is the horizontal magnetic intensity.
Compared with WiFi, android smartphones commonly have low WiFi update rates (e.g., approximate 0.3 Hz for Samsung Galaxy smartphones). Thus, we combine the RSS and the coordinates of the latest step as a fingerprint when the RSS is updated. The WiFi fingerprint at the i-th RP is recorded as:
F W i = { p o s i ,   σ p o s i ,   ( m a c i , 1 , R S S i , 1 ) ,    ( m a c i , 2 , R S S i , 2 ) ,   ⋯ ,   ( m a c i , m i , R S S i , m i ) }
where posi and σposi are the coordinate of RPk and its accuracy, maci,j and RSSi,j are the MAC address and RSS of the j-th AP received at RPi, and mi is the number of available APs at RPi.

2.2. Positioning Phase for WiFi Fingerprinting and Magnetic Matching

MM is a profile-matching method, while WiFi fingerprinting is based on point-by-point matching. Therefore, these two techniques are described separately.

2.2.1. Magnetic Matching

The basic idea of MM is calculating the difference between the measured profile and the candidate profiles in the DB, and finding the best match. The “match” can be indicated by the minimum value of a given formula such as mean absolute difference (MAD) [19]:
M A D = 1 N ∑ i = 1 N | S i − M i |
where Si is the measured profile, Mi is the profile in the DB, and N is the profile length.
To obtain the optimal match, the profile length should be long enough to show the profile feature; additionally, it is preferred that the length of the measured profile and the candidate profile should be the same. We utilize the steps detected by accelerometers to calculate the rough length of the measured profile. Because accurate and real-time step-length estimation is still an open issue in pedestrian navigation, we use the dynamic time warping (DTW) algorithm, which is originally used in the speech recognition area, for matching with inaccurate profile length.
The technique in DTW [22] is to compress or stretch the time axis of one (or both) sequences to achieve a better alignment. The goal is to find the best match between two sequences, S = { s 1 ,   s 2 ,   ... ,   s A } and M = { m 1 ,   m 2 ,   ... ,   m B } , of different lengths. The best match is found by obtaining the optimal warping path w. The warping path is given by w = w ( 1 ) ,   w ( 2 ) ,   ... ,   w ( n ) , where w ( i ) = [ i ( n ) ,   j ( n ) ] is a set of matched samples, where i and j are the time-axes of two sequences, respectively. The objective of the warping function is to minimize the overall cost function given by D = ∑ n = 1 N δ ( w ( n ) ) , where ∑ n = 1 N δ ( w ( n ) ) = ( i ( n ) − j ( n ) ) 2 is the squared distance between the sample points.
To generate a warping path, a cost matrix is constructed. This matrix represents the minimum cost required to reach a particular point (i, j) from (1, 1). This minimization problem is usually solved using the dynamic programming approach, whereby a cumulative distance γ (i, j) is computed as the sum of the distance obtained from the current set of points δ ( w ( n ) ) and the minimum of the cumulative distances of the adjacent elements or neighbors by:
γ ( i ,   j ) = δ ( w ( n ) ) + min [ γ ( i − 1 ,   j ) , γ ( i − 1 ,   j − 1 ) , γ ( i ,   j − 1 ) ]

2.2.2. WiFi Fingerprinting

The user location is estimated by finding the closest match between the measured RSS vector with those stored in the DB. The most typical WiFi fingerprinting approaches are the Nearest Neighbor (NN) method and the probabilistic estimation approach [28]. The NN method selects the RP that has the minimal signal strength distance as the user’s estimated position by using [23]:
d i = | S S r e c , l u − S S D B , i | ,   i ∈ I R P
where, di is the signal strength distance at RPi, lu is the position to be determined, S S r e c , l u is the measured RSS vector at lu, SSDB,i is the RSS vector at RPi, and IRP is the location index set of RPs in the DB. After this, the location of RPi which satisfies the condition d i * = min ( d i | i ∈ I R P ) is determined as the position estimate of lu.
To mitigate the impact of blunders and obtain a more reliable position, the k-NN method is considered [29]. The k-NN method estimates the position according to the k RPs that have the smallest distances. The position estimate is obtained by a weighed sum of the position of these RPs by:
r ^ = ∑ i = 1 k c i C r i
where c i = 1 / d i , C = ∑ i = 1 k c i , r i is the position of the i-th nearest RP, and r ^ is the estimated position.

2.2.3. WiFi-Aided Magnetic Matching

Compared with WiFi, MM results have smaller fluctuations but more mismatches. Thus, we use WiFi positioning result to limit the MM search space to reduce both the mismatch rate and the computational load. The search space is limited to a circle around the WiFi results, as shown in Figure 3. The radius of the circle is set according to the WiFi accuracy.
Furthermore, a multi-level quality control mechanism is applied to make WiFi solutions robust. The first level is on WiFi fingerprinting. Several methods are used to detect WiFi blunders. The first is on the measurement level, where a threshold value ThRSS is set to filter out APs with weak RSS. The second is based on the minimal signal strength distance. If the minimal signal strength distance at a certain epoch is larger than the value Thd1, the WiFi results at this epoch will be regarded as a point outside the DB.
Micromachines 06 00747 g003 1024
Figure 3. Using WiFi positioning results to limit search space for magnetic matching.
Figure 3. Using WiFi positioning results to limit search space for magnetic matching.
Micromachines 06 00747 g003
This methodology can also be extended to Bluetooth or other techniques. Since Bluetooth can be used in a similar way as WiFi (either fingerprinting or trilateration), it is feasible to use Bluetooth to determine a region first, and then use magnetic matching to determine the position. When both WiFi and Bluetooth are available, both a WiFi result and a Bluetooth result can determine a region. If this is the case, the position uncertainty of the integrated use of WiFi and Bluetooth can be smaller than that of the independent use of WiFi or Bluetooth. Accordingly, the position accuracy can be further improved.
Tests and results of WiFi, MM, and WiFi-aided MM are demonstrated in Section 3.

3. Tests and Analysis

Two sets of tests were conducted at the University of Calgary, one on the main floor of the Energy Environment Experiential Learning (EEEL) building, and the other is on the lower main floor of the Engineering building (ENB). These two buildings were chosen because they have different types of indoor environments. EEEL is a relatively new building with well-equipped infrastructure. Accordingly, there are more WiFi APs (the average number of RSS was over 15 in this building) and severe magnetic interferences (the change of magnetic intensity reached 0.4 Gauss). In contrast, the lower main floor of ENB is mainly used for walking; thus, there are less APs (the average number of RSS was nearly seven) and less magnetic interferences (the change of magnetic intensity was below 0.25 Gauss). The sizes of tested areas in EEEL and ENB were around 120 × 40 m2 and 140 × 60 m2, respectively. The tests were performed with Samsung Galaxy S3 and S4 (S3 for training and S4 for positioning) smartphones. We conducted the tests in this paper with the handheld mode to focus on the hybrid navigation.

3.1. Tests at EEEL

3.1.1. Training Phase

We generated the magnetic and WiFi DBs inside the EEEL building using four different trajectories. The true trajectories are shown in Figure 4. Each trajectory lasted for 5–10 min. The coordinates of the landmarks (i.e., the start and end points and corners and intersections) and the orientations of corridors were obtained from Google Earth and utilized as constraints to generate the DBs.
Micromachines 06 00747 g004 1024
Figure 4. Trajectories used to generate WiFi and magnetic databases (DBs) at the Energy Environment Experiential Learning (EEEL).
Figure 4. Trajectories used to generate WiFi and magnetic databases (DBs) at the Energy Environment Experiential Learning (EEEL).
Micromachines 06 00747 g004
When the WiFi RSS information was updated, it was combined with the coordinate of the surveyor’s latest step as a fingerprint only. The WiFi update rate on tested smartphones was about 0.3 Hz; thus, the distance between two WiFi RPs was approximate 3 m. The RPs in the magnetic DB included all steps and interpolation points. The interpolation distance was set at 0.1 m. The scale factor α was set at 0.2. The RPs in the WiFi and magnetic DBs are shown in Figure 5 and Figure 6, respectively. The x- and y-axes indicate the length in the west–east and south–north directions. The colors in Figure 5 and Figure 6 indicate the weighted AP number and the magnetic strength. Over 15 RSS were available in the middle indoor area, and over 10 were available in the marginal indoor areas. The magnetic intensity varied from 0.3 Gauss to 0.8 Gauss indoors. The weighted AP number at RPi was calculated by:
W A P i = ∑ j = 1 n i a i , j ,    i ∈ I R P
where ni is the number of WiFi signals received at RPi, IRP is the location index set of RPs in the DB. The value of ai,j is determine according to RSSi,j (i.e., the RSS of APj at RPi) by the following rule: If RSSi,j > −60 dBm, ai,j = 1; else, if −70 dBm < RSSi,j < −60 dBm, ai,j = 0.75; else, if −85 dBm < RSSi,j < −70 dBm, ai,j = 0.25; else, if RSSi,j < −85 dBm, ai,j =0.
Figure 5 shows that the available WiFi signals were abundant in the middle area of EEEL, less in the marginal indoor areas, and even less in outdoor areas. Figure 6 indicates that the magnetic intensity was within 0.5–0.6 G (the geomagnetic intensity at Calgary is 0.57 G) at most of the outdoor RPs; however, the magnetic intensity varied significantly indoors.
Micromachines 06 00747 g005 1024
Figure 5. WiFi signal distribution at EEEL.
Figure 5. WiFi signal distribution at EEEL.
Micromachines 06 00747 g005
Micromachines 06 00747 g006 1024
Figure 6. Magnetic distribution at EEEL.
Figure 6. Magnetic distribution at EEEL.
Micromachines 06 00747 g006

3.1.2. Positioning Phase

Figure 7 shows the trajectory for the positioning test, which was different from the training trajectories. The walking directions on the majority of the main corridors were also different from those on the training trajectories.
The threshold value for available WiFi RSS was set at ThRSS = −85 dBm. The number k was set at 4 for the k-NN approach. The profile length for MM was 10 steps: The MM process began after the user had walked for 10 steps; after this, the magnetic fingerprints within the latest 10 steps were used for matching. The radius of the MM search space determined by the WiFi results was set at R = 15 m. The test results are shown in the next subsection.
Micromachines 06 00747 g007 1024
Figure 7. Test trajectory at EEEL (with abundant WiFi and magnetic information).
Figure 7. Test trajectory at EEEL (with abundant WiFi and magnetic information).
Micromachines 06 00747 g007

3.1.3. EEEL Test Results

Navigation solutions with pedestrian dead-reckoning (PDR)-only, WiFi-only, MM-only, and WiFi-aided MM are shown in this subsection. We first trace the trajectory provided by each technology or combination. After this, statistical results are provided. The MM, WiFi, and WiFi-aided MM solutions are demonstrated in Figure 8, Figure 9 and Figure 10, respectively.
WiFi provided absolute positions with a low mismatch rate in this test. As there were abundant WiFi APs in EEEL, the ambiguity issue was not evident. However, the WiFi results had significant fluctuations. RSS fluctuation is an issue inherent to any technology based on RSS.
Compared with WiFi, the matched MM results were more accurate and had smaller fluctuations. Nevertheless, MM had a significantly larger mismatch rate. Thus, it is preferable to use other technologies to aid MM and detect the mismatches. Figure 10 shows that the majority of the mismatches in MM were eliminated by limiting the search space using the WiFi results.
To further evaluate the positioning errors, the error distances (i.e., the distance between the estimated user position and the corresponding true position) were calculated. The true positions were obtained by using the floor plan to correct the PDR solution, which was similar to the work in the training phase. Figure 11, Figure 12 and Figure 13 demonstrate the position errors of MM, WiFi, and WiFi-aided MM, respectively. The left plot in each figure shows the time series of error distances. The root mean square (RMS) value of the error distances is also shown as a magenta line. The yellow and blue lines on the x-axis indicate indoors and outdoors, respectively. The right plot in each figure is the statistical error cumulative distribution function (CDF). The red line indicates the error within which the probability is 80%.
Micromachines 06 00747 g008 1024
Figure 8. Magnetic matching (MM) result at EEEL.
Figure 8. Magnetic matching (MM) result at EEEL.
Micromachines 06 00747 g008
Micromachines 06 00747 g009 1024
Figure 9. WiFi fingerprinting result at EEEL.
Figure 9. WiFi fingerprinting result at EEEL.
Micromachines 06 00747 g009
Micromachines 06 00747 g010 1024
Figure 10. WiFi-aided MM result at EEEL.
Figure 10. WiFi-aided MM result at EEEL.
Micromachines 06 00747 g010
Micromachines 06 00747 g011 1024
Figure 11. MM position errors at EEEL.
Figure 11. MM position errors at EEEL.
Micromachines 06 00747 g011
Micromachines 06 00747 g012 1024
Figure 12. WiFi position errors at EEEL.
Figure 12. WiFi position errors at EEEL.
Micromachines 06 00747 g012
Micromachines 06 00747 g013 1024
Figure 13. WiFi-aided MM position errors at EEEL.
Figure 13. WiFi-aided MM position errors at EEEL.
Micromachines 06 00747 g013
By using the WiFi solutions to limit the search space, the MM errors were reduced significantly. On several occasions, a sequence of MM results was more than 20 m away from the true positions. When aided by WiFi, these MM errors were controlled effectively. The max error reduced from more than 60 m to less than 20 m. Also, the 80% reduced from approximate 7 m to below 5 m.
Comparing with the WiFi-only results, the WiFi-aided MM results had a smaller 80% error. However, the max error of the WiFi-aided MM solution is larger than that in the WiFi results. The statistical values of navigation errors are shown in Table 1. The first column shows the used technologies, and Column 2–4 are the max, RMS values, and errors within which the probability is 80%.
Table
Table 1. Statistical values of navigation errors at the Energy Environment Experiential Learning (EEEL).
Table 1. Statistical values of navigation errors at the Energy Environment Experiential Learning (EEEL).
TechniqueMax (m)RMS (m)80% (m)
WiFi10.24.35.8
MM61.512.27.0
WiFi-aided MM18.34.54.2
The RMS of WiFi positioning errors was 4.3 m. This was a medium accuracy for WiFi with consumer portable devices and with walk-survey. 80% of MM errors were within 7.0 m, but the RMS was 12.2 m. This is because there were several large mismatches. The RMS of MM errors was reduced to 4.5 m when using WiFi results to limit the search space.
Although the 80% error of WiFi-aided MM was 1.6 m less than that of WiFi, both the max error and the error RMS of the former were larger. This might due to the fact that WiFi results were already accurate (with a RMS of 4.3 m) because there were over 10 WiFi signals in most of the tested area at EEEL. This outcome indicates the performance improvement by combing WiFi and MM depends on signal distributions of both magnetic intensity and WiFi RSS. The following tests at ENB show the performance of the WiFi-aided MM algorithm when there were less WiFi signals.

3.2. Tests at ENB

The corridors in ENB are narrow and straight, which are different from those in EEEL. The RSS and magnetic distributions on the tested trajectory are shown in Figure 14 and Figure 15, respectively. The average number of RSS was approximately seven, and the change of magnetic intensity was below 0.25 Gauss. There were less WiFi APs and less magnetic perturbations at ENB. Therefore, it was expected that the WiFi and MM accuracy would probably be lower than that at EEEL.
The MM, WiFi, and, WiFi-aided MM trajectories are demonstrated in Figure 16, Figure 17 and Figure 18, respectively.
Not only the MM results but also the WiFi results had several significant mismatches. This outcome met our expectation, as the WiFi signal distribution was poorer at ENB.
Figure 19, Figure 20 and Figure 21 demonstrate the position errors of MM, WiFi, and WiFi-aided MM, respectively. The left plot in each figure shows the time series of error distances. The root mean square (RMS) value of the error distances is also shown as a magenta line. The yellow and blue lines on the x-axis indicate indoors and outdoors. The right plot in each figure is the statistical error cumulative distribution function (CDF). The red line indicates the error within which the probability is 80%.
Micromachines 06 00747 g014 1024
Figure 14. WiFi signal distribution at the Engineering building (ENB).
Figure 14. WiFi signal distribution at the Engineering building (ENB).
Micromachines 06 00747 g014
Micromachines 06 00747 g015 1024
Figure 15. Magnetic distribution at ENB.
Figure 15. Magnetic distribution at ENB.
Micromachines 06 00747 g015
Micromachines 06 00747 g016 1024
Figure 16. MM result at ENB.
Figure 16. MM result at ENB.
Micromachines 06 00747 g016
Micromachines 06 00747 g017 1024
Figure 17. WiFi fingerprinting result at ENB.
Figure 17. WiFi fingerprinting result at ENB.
Micromachines 06 00747 g017
Micromachines 06 00747 g018 1024
Figure 18. WiFi-aided MM result at ENB.
Figure 18. WiFi-aided MM result at ENB.
Micromachines 06 00747 g018
Micromachines 06 00747 g019 1024
Figure 19. MM position errors at ENB.
Figure 19. MM position errors at ENB.
Micromachines 06 00747 g019
Micromachines 06 00747 g020 1024
Figure 20. WiFi position errors at ENB.
Figure 20. WiFi position errors at ENB.
Micromachines 06 00747 g020
Micromachines 06 00747 g021 1024
Figure 21. WiFi-aided MM position errors at ENB.
Figure 21. WiFi-aided MM position errors at ENB.
Micromachines 06 00747 g021
The RMS of MM errors was 16.6 m at ENB, which was larger than that at EEEL (12.2 m). Also, the WiFi errors were more significant and had a max error of 35 m. Even with such large WiFi errors, the WiFi-aided MM results had a much smaller max error and RMS than both the WiFi and MM results. The statistics of navigation errors are shown in Table 2.
Table
Table 2. Statistical values of navigation errors at ENB.
Table 2. Statistical values of navigation errors at ENB.
TechniqueMax (m)RMS (m)80% (m)
WiFi37.87.26.3
MM61.016.617.3
WiFi-aided MM17.84.24.0
In the ENB tests, MM provided the worst navigation solution with an RMS of 16.6 m. However, when aided by WiFi, the RMS reduced to 4.2 m. Therefore, although MM was not reliable, it could provide high accuracy when there was no mismatch. Therefore, it is feasible to combine MM with other technologies to provide accurate solutions. The key is to remove the MM mismatches using information from other technologies. When comparing the RMS value of the position errors for WiFi-aided MM with that for WiFi, an improvement of 41.6% was observed.
The WiFi and MM position errors at ENB (RMS 7.2 and 16.6 m, respectively) were more significant than those at EEEL (RMS 4.3 and 12.2 m, respectively). However, the position errors of WiFi-aided MM were similar for two buildings (RMS 4.5 m at EEEL and 4.2 m at ENB). This result indicates the potential of integrating WiFi and MM to provide more reliable navigation results, especially at the environments with poor WiFi RSS or magnetic intensity information. However, Figure 21 demonstrates that there were still several errors that were larger than 15 m. This may probably due to the accuracy limit of both WiFi and MM in a short time period. Therefore, PDR, which provided accurate short-term solutions but suffers from increasing drifts, may be an appropriate candidate to integrate with the WiFi-aided approach. This will be an important issue in our future research.

4. Conclusions

This paper presents a WiFi-aided magnetic matching (MM) navigation algorithm that maximizes the advantage and minimizes the disadvantage of WiFi and MM. By using WiFi to reduce the MM search space, this algorithm can significantly reduce the mismatching rate and computational load of MM. The algorithms were tested with smartphones in different indoor environments (i.e., Environment #1 with abundant WiFi APs and significant magnetic changes, and Environment #2 with less WiFi and magnetic information).
The WiFi and MM databases were generated simultaneously within half an hour using the walk-survey method. WiFi fingerprinting errors were not significant in Environment #1 (RMS 4.3 m and max 10.2 m) but significant in Environment #2 (RMS 7.2 m and max 37.8 m). In general, WiFi results had a low mismatch rate in both environments.
MM had significant mismatch rates. The RMS values of MM errors reached 12.2 m (Environment #1) and 16.6 m (Environment #2). However, when we used WiFi to limit the MM search space, the RMS reduced to below 4.5 m. Therefore, the key to obtaining accurate MM solutions is to remove the mismatches using information from other technologies.
WiFi-aided MM provided more reliable results than MM, which indicates the effectiveness of introducing the WiFi information. Comparing with WiFi-only results, the WiFi-aided MM solution was similar in Environment #1 but approximately 41.6% better in Environment #2. This outcome demonstrates that integrating WiFi and MM can also enhance the WiFi fingerprinting results in environments with poor WiFi signal distributions.
The proposed WiFi-aided magnetic matching algorithm uses off-the-shelf sensors available in consumer portable devices and existing WiFi infrastructure, which need no additional hardware cost or extra manpower cost. Future work will focus on introducing other technologies, such as PDR, to integrate with the WiFi-aided approach and provide continuous and reliable solutions.

Acknowledgments

This work was supported in part by National Natural Science Foundation of China (41174028) and the research funding from Naser El-Sheimy. The first author (Y.L.) would also thank the China Scholarship Council for its support (No. 201306270139).

Author Contributions

You Li, Naser El-Sheimy, and Xiaoji Niu conceived and designed the research; You Li, Haiyu Lan, and Yuan Zhuang performed the research; Peng Zhang, Yuan Zhuang and Haiyu Lan analyzed the data; Yuan Zhuang, Xiaoji Niu, and Naser El-Sheimy contributed materials; You Li, Yuan Zhuang, and Peng Zhang wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Li, X.; Wang, J.; Li, T. Seamless positioning and navigation by using Geo-referenced images and multi-sensor data. Sensors 2013, 13, 9047–9069. [Google Scholar] [CrossRef] [PubMed]
  2. Fallah, N.; Apostolopoulos, I.; Bekris, K.; Folmer, E. Indoor human navigation systems: A survey. Interact. Comput. 2013, 25, 21–33. [Google Scholar]
  3. Bahl, P.; Padmanabhan, V.N. RADAR: An in-Building RF-Based User Location and Tracking System. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2000), Tel Aviv, Israel, 26–30 Match 2000.
  4. Torres-Solis, J.; Falk, T.H.; Chau, T. A review of indoor localization technologies: Towards navigational assistance for topographical disorientation. Ambient Intell. 2010, 3, 51–84. [Google Scholar]
  5. Bose, A.; Foh, C.H. A practical path loss model for indoor WiFi positioning enhancement. In Proceedings of 2007 6th International Conference on Information, Communications & Signal Processing, Singapore, 10–13 December 2007.
  6. Zhuang, Y.; Syed, Z.; Georgy, J.; El-Sheimy, N. Autonomous smartphone based WiFi positioning system by using access points localization and crowdsourcing. Pervasive Mob. Comput. 2015, 18, 118–136. [Google Scholar] [CrossRef]
  7. El-Sheimy, N.; Niu, X. The Promise of MEMS to the Navigation Community. GNSS 2007, 2, 26–56. [Google Scholar]
  8. Li, Y.; Georgy, J.; Niu, X.; Goodall, C.; El-Sheimy, N. A Automatic Multi-level Gyro Calibration Architecture for Consumer Portable Devices. In Proceedings of the International Conference on Indoor Positioning and Indoor Navigation (IPIN), Busan, Korea, 27–30 October 2004.
  9. Titterton, D.H.; Weston, J.L. Strapdown Inertial Navigation Technology, 2nd ed.; The Institution of Electrical Engineers: London, UK, 2004. [Google Scholar]
  10. Li, Y.; Niu, X.; Zhang, Q.; Zhang, H.; Shi, C. An in situ hand calibration method using a pseudo-observation scheme for low-end inertial measurement units. Meas. Sci. Technol. 2012, 23, 105104. [Google Scholar] [CrossRef]
  11. Niu, X.; Li, Y.; Zhang, H.; Wang, Q.; Ban, Y. Fast Thermal Calibration of Low-Grade Inertial Sensors and Inertial Measurement Units. Sensors 2013, 13, 12192–12217. [Google Scholar] [CrossRef] [PubMed]
  12. Niu, X.; Li, Y.; Zhang, Q.; Cheng, Y.; Shi, C. Observability Analysis of Non-Holonomic Constraints for Land-Vehicle Navigation Systems. J. Glob. Position. Syst. 2012, 11, 80–88. [Google Scholar] [CrossRef]
  13. Searcy, J.D.; Pernicka, H.J. Magnetometer-Only Attitude Determination Using Novel Two-Step Kalman Filter Approach. J. Guid. Control Dyn. 2012, 35, 1693–1701. [Google Scholar] [CrossRef]
  14. Afzal, M.H.; Renaudin, V.; Lachapelle, G. Use of earth’s magnetic field for mitigating gyroscope errors regardless of magnetic perturbation. Sensors 2011, 11, 11390–11414. [Google Scholar] [CrossRef] [PubMed]
  15. Xie, H.; Gu, T.; Tao, X.; Ye, H.; Lv, J. MaLoc: A practical magnetic fingerprinting approach to indoor localization using smartphones. In Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Seattle, WA, USA, 13–17 September 2014.
  16. Subbu, K.P.; Gozick, B.; Dantu, R. LocateMe: Magnetic-fields-based indoor localization using smartphones. ACM Transact. Intell. Sys. Technol. 2013, 4, 73. [Google Scholar] [CrossRef]
  17. Zhang, C.; Subbu, K.; Luo, J.; Wu, J. GROPING: Geomagnetism and cROwdsensing Powered Indoor NaviGation. IEEE Trans. Mob. Comput. 2014, 14, 387–400. [Google Scholar] [CrossRef]
  18. Gozick, B.; Subbu, K.P.; Dantu, R.; Maeshiro, T. Magnetic maps for indoor navigation. IEEE Trans. Instrum. Meas. 2011, 60, 3883–3891. [Google Scholar] [CrossRef]
  19. Golden, J.P. Terrain contour matching (TERCOM): A cruise missile guidance aid. Image Process. Missile Guid. 1980, 238, 10–18. [Google Scholar]
  20. Yan, L.; Cui, C. A new algorithm of gravity matching aided navigation. In Proceedings of the 2nd International Conference on Spatial Information Technology, Wuhan, China, 10–11 November 2007.
  21. Zhuang, Y.; Chang, H.W.; El-Sheimy, N. A MEMS Multi-Sensors System for Pedestrian Navigation. In Proceedings of the China Satellite Navigation Conference (CSNC), Wuhan, China, 15–17 May 2013.
  22. Subbu, K.P.; Gozick, B.; Dantu, R. Indoor localization through dynamic time warping. In Proceedings of the Systems, Man, and Cybernetics (SMC), Anchorage, AK, USA, 9–12 October 2011.
  23. Cheng, J.; Yang, L.; Li, Y.; Zhang, W. Seamless outdoor/indoor navigation with WIFI/GPS aided low cost Inertial Navigation System. Phys. Commun. 2014, 13, 31–43. [Google Scholar] [CrossRef]
  24. Xiang, Z.; Song, S.; Chen, J.; Wang, H.; Huang, J.; Gao, X. A wireless LAN-based indoor positioning technology. IBM J. Res. Dev. 2004, 48, 617–626. [Google Scholar] [CrossRef]
  25. Lin, H.; Zhang, Y.; Griss, M.; Landa, I. WASP: An enhanced indoor locationing algorithm for a congested Wi-Fi environment. In Mobile Entity Localization and Tracking in GPS-less Environnments; Springer: Berlin, Germany, 2009; pp. 183–196. [Google Scholar]
  26. Bolliger, P. 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, USA, 14–19 September 2008.
  27. Shin, E.H. Estimation Techniques for Low-Cost Inertial Navigation. PhD Thesis, University of Calgary, Calgary, Canada, May 2005. [Google Scholar]
  28. Lassabe, F.; Canalda, P.; Chatonnay, P.; Spies, F. Indoor Wi-Fi positioning: Techniques and systems. Ann. Telecommun. 2009, 64, 651–664. [Google Scholar] [CrossRef]
  29. Peng, J.; Zhu, M.; Zhang, K. New algorithms based on sigma point Kalman filter technique for multi-sensor integrated RFID indoor/outdoor positioning. In Proceedings of the 2011 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Guimaraes, Portugal, 21–23 September 2011.

Share and Cite

MDPI and ACS Style

Li, Y.; Zhuang, Y.; Lan, H.; Zhang, P.; Niu, X.; El-Sheimy, N. WiFi-Aided Magnetic Matching for Indoor Navigation with Consumer Portable Devices. Micromachines 2015, 6, 747-764. https://doi.org/10.3390/mi6060747

AMA Style

Li Y, Zhuang Y, Lan H, Zhang P, Niu X, El-Sheimy N. WiFi-Aided Magnetic Matching for Indoor Navigation with Consumer Portable Devices. Micromachines. 2015; 6(6):747-764. https://doi.org/10.3390/mi6060747

Chicago/Turabian Style

Li, You, Yuan Zhuang, Haiyu Lan, Peng Zhang, Xiaoji Niu, and Naser El-Sheimy. 2015. "WiFi-Aided Magnetic Matching for Indoor Navigation with Consumer Portable Devices" Micromachines 6, no. 6: 747-764. https://doi.org/10.3390/mi6060747

APA Style

Li, Y., Zhuang, Y., Lan, H., Zhang, P., Niu, X., & El-Sheimy, N. (2015). WiFi-Aided Magnetic Matching for Indoor Navigation with Consumer Portable Devices. Micromachines, 6(6), 747-764. https://doi.org/10.3390/mi6060747

Article Metrics

Back to TopTop