Smartphone Indoor Positioning Using WiFi, PDR, Magetic Fingerprints and Particle Filtering

Abstract

The evolution of an existing o ine algorithm for smartphone based indoor localization is outlined, discussed and evaluated. The existing algorithm performs dead reckoning using accelerometer-, compassand gyroscope data as well as WiFi ngerprinting. Steps are detected using accelerometer data. Compass and gyroscope are used for heading estimation. Drift compensation and step length estimation is performed by a particle lter using map information as well as WiFi information. Floor detection is based on RSSI (Radio signal strength indicator) evaluation and on map information. The evolution comprises a PDR-enhanced radio map generation algorithm, the particle lter with motion parameter adjustment by WiFi data, and Magnetic ngerprinting. The modi cations are described and discussed. The performance is evaluated against a publicly available database.

-

Smartphone Indoor positioning, particularly in public environments, is a highly demanded technology. As of today, it is yet a topic of ongoing intense research in information- and communication technology elds. WiFi RSSI (received signal strength indicator) indoor positioning using smartphones is a commonly applied technology and dates back to 2001 ([ 2 ]). RSSI algorithms are typically based on ngerprinting. However, depending on circumstances like unavailability of a radio map or reduced accuracy requirements, other methods like proximity, centroid, multilateration, radio tomography, and more have been successfully deployed. Smartphone based localization may be performed even if the WiFi installation has not been speci cally prepared for that use case and, for example, characteristics and positions of the WiFi access points are unknown. Unfortunately, in typical scenarios the obtainable accuracy of pure RSSI localization is limited to some meters [ 3, 8, 11 ], as for example observed in the EvAAL-ETRI 2015 competitions on indoor localization in large environments [ 16 ] or the Smartphone-based O -Line Indoor Location Competition at IPIN 2016 [ 15 ].

Contemporary smart phone positioning algorithms typically combine RSSI information and further smartphone sensor data, mainly inertial measurement data from gyro- and acceleration sensors, compass data, as well as magnetic data. Using dynamic ltering, for example particle- and Kalman lter, the obtained accuracies can be increased signi cantly. [ 17, 4, 12 ].

In the paper the design of a WiFi ngerprinting- an dead reckoning algorithm with oor plan based particle ltering is outlined. The proposed algorithm is an evolution based on the authors algorithm applied in the last IPIN competitions (2016, 2017 and 2018). A new feature of the algorithm is the inclusion of magnetic ngerprinting. 2

Exisiting algorithm

The HFTS algorithm used in the 2018 competition is based on WiFi and pedestrian dead reckoning (PDR), and a particle lter (PF). It is an evolution of the algorithm deployed at the 2016 competition [ 7 ] and the 2017 Competition [ 6 ].

For dead reckoning, heading estimation is performed using compass and gyroscope data. The gyroscope is able to detect heading changes quite accurately on a short timescale, but will drift in the long-term. In contrast, compass heading is subject to strong local magnetic perturbations but shows no drift on a long-term scale. Therefore, gyroscope data is used for detection of immediate heading changes. The heading relaxes to the compass direction with a certain time constant of some seconds. Step detection is performed by peak detection of the accelerometer data.

WiFi positioning is performed using the scalar product correlation ngerprinting algorithm [ 8 ] which is based on k-nn and the cosine similarity. Prior to the estimation of the unknown competition track, a radio map is obtained by evaluating the reference data provided by the competition organizers. These data are enriched with true ground positions and RSS readings. Therefore obtained RSS vectors can be related to a position. As the true ground readings occur only rarely, the actual reference position between two reference points is interpolated by PDR.

The actual positioning process comprises 2 phases. In the rst phase RSS positioning is performed employing the radio map. RSS readings are obtained at a rate of one reading every 4 seconds. For each reading a position is estimated. Also the oor is estimated by RSS. If the actor is moving, the position will change considerably in the 4 seconds between two subsequent RSS readings. Therefore, the position between the two readings is interpolated based on dead reckoning. The heading o set and the actual step length is not known at this stage. However, as for the start- and the endpoint of the 4 second track a RSS position estimation exists, the step length and heading o set are adjusted such that the track connects the two points.

In the second phase, positioning is performed employing PDR and a particle lter. Step length estimation and heading error- and drift compensation are performed by the particle lter using the information of oor plans to detect the most likely path (see also [ 5, 17 ]). The particle lter contains a constant number of particles. Besides the position, a particle state also comprises individual step length and heading o set values. The lter is updated each time a step is detected: All particles are moved according to the estimated heading, individually modi ed by the particle speci c o sets. Resampling is performed as follows: particles which collide with, for example, a wall, are replaced by a new ones. For collision detection the provided oor plans are used. New particles are seeded at the position of an existing particle, but with an own randomized step length and heading o set value. The global heading and step length are recalculated by averaging the heading values and step length of all particles. The reported PDR position is the averaged position of all particles.

Depending on the building layout, e.g open spaces, corridors, room sizes etc. the PF results alone may not be su cient for absolute position determination. Therefore, the step length and heading are also adjusted by the obtained WiFi position from phase 1: After each step the longitudinal- and the lateral displacement between WiFi and PF position are evaluated and a con gurable fraction of the displacement is added to the movement vector. 3 3.1

Magnetic ngerprinting

Principle

The geomagnetic eld inside a modern building is disturbed for example by steel in the building structure or by furniture. This holds for both, the direction and the amplitude of the eld vector. The magnetic disturbances typically are quite constant over time and have been used as reliable landmarks for positioning purposes [ 14, 10, 13 ]. The positioning procedure, while often referred to as \magnetic ngerprinting", di ers considerably from WiFi ngerprinting methods [ 2, 9 ]. A WiFi ngerprint database comprises ngerprints from certain positions of the building. Positioning is performed by comparing a ngerprint from an unknown position with the ngerprints in the database. As WiFi signals contain an identi cation of the transmitter, the comparison is spatially unambiguously, similar ngerprints only occur within neighbor positions. Magnetic ngerprinting uses only one access point, the earth. So ngerprints can only obtained by recording the magnetic eld along a path, and ngerprinting is performed by comparing a recorded path of a certain length with a database of several prerecorded path. It can be assumed that, if the ngerprints match, it is likely that the same path has been passed. If several path share certain features, the comparison is not unambiguously, and further information like for example WiFi positioning or PDR history has to be used for selecting which magnetic ngerprint is the most closest one to the estimated position. In the following sections, referring to the magnetic eld or the magnetic signal means referring to the amplitude of the magnetic eld vector. Of course, also other information like the z-component of the eld or combinations could be employed for ngerprinting. 3.2

Correlation

In Fig. 1 the situation is shown for the datasets of the Atlantis shopping mall, Nantes, France, which have been created for the IPIN 2018 indoor localization competition, Track 3 (smartphone o -site) [ 1 ]. Inset (a) is a magnetic trace of the evaluation dataset, plotted over walking time of the actor, who is recording data with a smartphone with a logging app. As it can be seen, the magnetic eld exhibits quite some features and is far from being constant. The low value at 140{180 s is attributed to a ride in an elevator. Obviously, the eld is shielded by the metal construction. The reasons for other features are not obvious, as it is common for magnetic ngerprinting. For inset (b) and (c), some low- and high pass ltering was applied. (b) presents a zoom of (a) at about 700 s of walking time. Inset (c) presents a path of a training le. The training les are enriched with true ground information, at a number of reference points. The marked 40 s long record is regarded as a ngerprint of the reference point xed at t =270 s. Inset (d) shows the folding of the 40 s long ngerprint in (c) with with the magnetic trace (a).

A strong peak is clearly visible and can be identi ed with an accuracy of some tenth of seconds. The peak indicates the position where the 40 s ngerprint ts best into the trace (a). Assuming that the ngerprint was recorded along the same path and with the same walking speed, the position in (a) at the end of the folding interval (t =713.3 s) should be the same as in (c) at t =270 s. For the given case that is true as the same reference point was visited 0.2{0.3 secs before the end of the interval, in both cases. In the displayed case the di erence in time between the visit of the reference point is below 0.2 secs, which relates to a spatial closeness well below 0.5 meters. Of course, generally it can not be assumed that the walking speed is constant and equal to the walking speed. 3.3

Proposed Magnetic Matching

A common way to compare map magnetic ngerprints is to use the \dynamic time warping" (DTW) algorithm, for adjusting the time values of the record to nd the best match with a ngerprint [ 14 ]. It was found that for the carefully recorded data of the IPIN 2018 Track3 even without DTW a reasonable matching can be performed.

In the the proposed algorithm, anyways a di erent approach is used: As PDR already delivers a position estimate at each half step of the actor, the magnetic readings are remapped to \meters of passed track". This makes the magnetic information to some extent independent of stops in the actors movement or di erent walking and changing speeds. Of course, the accuracy of the PDR algorithm has to be considered.

The magnetic ngerprinting is most helpful if the ngerprints can accurately be mapped to a true ground reference point. The training- and valuation datasets of the IPIN 2018 Competition Track 3 use 41 accurately surveyed true ground reference positions. The reference points are visited in several combinations and directions. Each time a reference point is visited, the magnetic data for the last 40 meters is stored as a magnetic ngerprint. The record is annotated with the true ground position at the end and with the nal heading of the actor.

In the positioning phase, the magnetic data is continuously recorded and mapped to the path length. after each detected half-step, e.g. every 30{40 cm, the latest 20 meters of data are compared to selected ngerprints in the database. The selection process selects those database ngerprints, which have a true ground endpoint within a certain distance of the current PDR/Wi estimated position. A further selection step selects only those ngerprints, which match the estimated heading within a +/-45 degree window. The heading matching ensures for example, that symmetric ngerprints which are recorded in inverse direction, are not considered.

While for Figure 1 the comparison was performed by convolution, it turned out that even more accurate results will be obtained by using the root of the summed squared di erence as measure for correlation. In Fig. 2 squared di erence correlation results are shown between a measured trace and four di erent

1 lan 0.8 g i sd 0.6 e z i la 0.4 m r on 0.2 reference tracks. The reference tracks all end at the same true point point, at t=20 s. Refs. 2 and 4 have a nice down-peak indicating the best correlation with the measured track and indicate the same distance to the true ground point of about 4 seconds. 4

Results and Outlook

The inclusion of a magnetic ngerprint algorithm into an existing positioning algorithm has been proposed, explained and discussed. The algorithm feasibility has been tested using the dataset of the IPIN 2018 competition track 3: Magnetic ngerprints have been generated and applied in the positioning phase for selected phases of the evaluation track. From the preliminary results we deduct that, at regions where feature-carrying magnetic data is available and is close to trueground references, an unknown path may be matched with a spatial accuracy in the range of 1 meter or better. Next steps will be to fully implement the positioning phase and to evaluate its feasibility in a lab setup and with publicly available evaluation data.

References

1. The ipin 2018 competition ( 2018 ), http://ipin2018.ifsttar.fr

2. Bahl , P. , Padmanabhan , V.N.: RADAR : An in-building RF-based user location and tracking system . In: INFOCOM (2) . pp. 775 { 784 ( 2000 )

3. Berkvens , R. , Weyn , M. , Peremans , H.: Localization performance quanti cation by conditional entropy . In: Indoor Positioning and Indoor Navigation (IPIN) , 2015 International Conference on. pp. 1 { 7 (Oct 2015 ). https://doi.org/10.1109/IPIN. 2015 .7346969

4. Ebner , F. , Fetzer , T. , Deinzer , F. , Kping , L. , Grzegorzek , M.: Multi sensor 3d indoor localisation . In: Indoor Positioning and Indoor Navigation (IPIN) , 2015 International Conference on. pp. 1 { 11 (Oct 2015 ). https://doi.org/10.1109/IPIN. 2015 .7346772

5. Kang , W., Han, Y .: Smartpdr: Smartphone-based pedestrian dead reckoning for indoor localization . IEEE Sensors Journal 15 ( 5 ), 2906 {2916 (May 2015 ). https://doi.org/10.1109/JSEN. 2014 .2382568

6. Knauth , S. : Smartphone pdr positioning in large environments employing wi , particle lter, and backward optimization . In: 2017 International Conference on Indoor Positioning and Indoor Navigation (IPIN) . pp. 1 { 6 (Sept 2017 ). https://doi.org/10.1109/IPIN. 2017 .8115918

7. Knauth , S. , Kouko kis , A.: Smartphone positioning in large environments by sensor data fusion, particle lter and fcwc . In: 2016 International Conference on Indoor Positioning and Indoor Navigation (IPIN) . pp. 1 { 5 (Oct 2016 ). https://doi.org/10.1109/IPIN. 2016 .7743706

8. Knauth , S. , Storz , M. , Dastageeri , H. , Kouko kis , A., Mhser-Hipp , N.A. : Fingerprint calibrated centroid and scalar product correlation rssi positioning in large environments . In: Indoor Positioning and Indoor Navigation (IPIN) , 2015 International Conference on. pp. 1 { 6 (Oct 2015 ). https://doi.org/10.1109/IPIN. 2015 .7346968

9. Knauth , S.: 8 - study and evaluation of selected rssi-based positioning algorithms . In: Conesa, J. , Prez-Navarro , A. , Torres-Sospedra , J. , Montoliu , R . (eds.) Geographical and Fingerprinting Data to Create Systems for Indoor Positioning and Indoor/Outdoor Navigation, pp. 147 { 167 . Intelligent Data-Centric Systems , Academic Press ( 2019 ). https://doi.org/https://doi.org/10.1016/B978-0 -12-813189-3 . 00006 -X, http://www.sciencedirect.com/science/article/pii/B978012813189300006X

10. Mirowski , P. , Ho , T.K. , Saehoon Yi , MacDonald, M.: Signalslam: Simultaneous localization and mapping with mixed wi , bluetooth, lte and magnetic signals . In: International Conference on Indoor Positioning and Indoor Navigation . pp. 1 { 10 (Oct 2013 ). https://doi.org/10.1109/IPIN. 2013 .6817853

11. Moreira , A. , Nicolau , M.J. , Meneses , F. , Costa , A. : Wi- ngerprinting in the real world - rtls@um at the evaal competition . In: Indoor Positioning and Indoor Navigation (IPIN) , 2015 International Conference on. pp. 1 { 10 (Oct 2015 ). https://doi.org/10.1109/IPIN. 2015 .7346967

12. Nurminen , H. , Ristimki , A. , Ali-Lytty , S. , Pich , R.: Particle lter and smoother for indoor localization . In: Indoor Positioning and Indoor Navigation (IPIN) , 2013 International Conference on. pp. 1 { 10 (Oct 2013 )

13. Robertson , P. , Frassl , M. , Angermann , M. , Doniec , M. , Julian , B.J. , Garcia Puyol , M. , Khider , M. , Lichtenstern , M. , Bruno , L. : Simultaneous localization and mapping for pedestrians using distortions of the local magnetic eld intensity in large indoor environments . In: International Conference on Indoor Positioning and Indoor Navigation . pp. 1 { 10 (Oct 2013 ). https://doi.org/10.1109/IPIN. 2013 .6817910

14. Subbu , K.P. , Gozick , B. , Dantu , R.: Locateme: Magnetic- elds-based indoor localization using smartphones . ACM Trans. Intell. Syst. Technol . 4 ( 4 ), 73 :1{ 73 :27 (Oct 2013 ). https://doi.org/10.1145/2508037.2508054

15. Torres-Sospedra , J. , Jimnez , A.R. , Knauth , S. , Moreira , A. , Beer , Y. , Fetzer , T. , Ta , V.C. , Montoliu , R. , Seco , F. , Mendoza-Silva , G.M. , Belmonte , O. , Kouko kis , A., Nicolau , M.J. , Costa , A. , Meneses , F. , Ebner , F. , Deinzer , F. , Vaufreydaz , D. , Dao , T.K. , Castelli , E. : The smartphone-based o ine indoor location competition at ipin 2016: Analysis and future work . Sensors 17 ( 3 ) ( 2017 ). https://doi.org/10.3390/s17030557, http://www.mdpi.com/1424-8220/17/3/557

16. Torres-Sospedra , J. , Moreira , A. , Knauth , S. , Berkvens , R. , Montoliu , R. , Belmonte , O. , Trilles , S. , Nicolau , M.J. , Meneses , F. , Costa , A. , Kouko kis , A., Weyn , M. , Peremans , H.: A realistic evaluation of indoor positioning systems based on wingerprinting: The 2015 evaal-etri competition . Journal of Ambient Intelligence and Smart Environments 9 ( 2 ), 263 { 279 ( 2017 ), http://dx.doi.org/10.3233/AIS170421

17. Willemsen , T. , Keller, F., Sternberg , H.: A topological approach with mems in smartphones based on routing-graph . In: Indoor Positioning and Indoor Navigation (IPIN) , 2015 International Conference on. pp. 1 { 6 (Oct 2015 ). https://doi.org/10.1109/IPIN. 2015 .7346952