Pedestrian Dead Reckoning with correction points for indoor positioning and Wi-Fi fingerprint mapping

Abstract

Existing smartphones have many built-in sensors which allow various indoor positioning techniques (IPS) to be developed without the need of additional hardware. Among the techniques, Pedestrian Dead Reckoning (PDR) is one of the more suitable ones for continouos positioning tracking. Through the accelerometer, magnetometer and gyroscope sensors, the number of steps and the direction of those taken steps can be captured and the position of the user can be inferred from a known starting point. Despite the PDR technique is simple, the implementation is not so straight forward as there are some challenges involved. Some of the notable challenges include i) the positioning error accumulates over time; ii) sensors from different phones models produce inconsistent measurement data; iii) walking gaits and step lengths vary greatly for different users. To overcome the error accumulation of PDR, many existing works use beacons to correct a user’s position estimation when the user is close to a beacon. Instead of using beacons, this work introduces the concept of correction points, which are logical points where their locations are known. Besides inferring the user’s position, the proposed solution also use the correction points to recalibrate user’s PDR step length and improves the overall positioning accuracy. From the experimental results, the proposed solution with correction points is able to perform continuous position tracking on three different smartphone models with more than 50% of accuracy improvement compared to IPS that only uses PDR alone. On top of that, we also show how the proposed system can be utilized to perform Wi-Fi fingerprint mapping, which can reduce the effort for system maintenance.

Keywords

Indoor positioning system Pedestrian dead reckoning (PDR)correction points Wi-Fi fingerprinting

1 Introduction

There are many indoor positioning systems (IPS) proposed for the past few years, including some notable examples like active badge [1] and Google’s virtual positioning service (VPS) [2]. Unfortunately, these highly accurate positioning systems often require users to use additional device other than the existing smartphones. For instance, Google’s VPS requires mobile devices with built-in depth sensors which is supported by Google’s Tango augmented reality (AR) computing platform [3]. Similarly, the combination of foot-mounted inertial sensor with Wi-Fi fingerprinting is able to provide better positioning accuracy but it requires users to have shoes with mounted inertial measurement unit (IMU) sensor [3]. Having additional devices on smartphones is not desirable in many occasions, because it not only incur additional deployment cost but also not convenient to be used by end users.

Therefore, in recent years, IPS techniques such as Wi-Fi fingerprinting [4 –7] and Pedestrian Dead Reckoning (PDR) [8 –11] are becoming the mainstream despite of inferior accuracy compared to the aforementioned IPS that requires additional and dedicated hardware. There are many existing works attempted to improve the accuracy of Wi-Fi fingerprinting and PDR [12 –14]; some of them even propose to use additional sensors like magnetic sensor [15] and Bluetooth beacons [16] to improve the accuracy of IPS.

In this paper, we focus on improving the accuracy of PDR based IPS, which can provide continuous position tracking. PDR positioning error accumulates very fast over time; small error in estimating the length of each steps will accumulate and cause large positioning error. Therefore, this work introduces the concept of correction points to improve the accuracy of the PDR based IPS. Correction points are a pair of logical points where their exact positions are known a priori and the smartphones can detect them when it is placed within close proximity (sub-meter range). Correction points can be implemented using Wi-Fi AP or Bluetooth beacons. The contributions of such correction points are twofold:-

Smartphone can identify their locations when it is near to any of these correction points with accuracy up to sub-meter range. A correction point can be a new starting point for PDR to pinpoint its location.

A pair of correction points can be used to calibrate positioning measurements to reduce its cumulative errors. This means that with the PDR users can travel further with better positioning accuracy.

The details of correction points and its benefits are elaborated in Section III.

On top of that, the proposed solution can also be used to perform Wi-Fi fingerprint mapping for IPS based Wi-Fi fingerprinting techniques. When the user uses PDR to perform positioning, the Wi-Fi RSSI value is also recorded and stored in the fingerprint database, which reduces the effort of maintaining the fingerprint database manually from time to time. This can be useful for situations where PDR has to be used together with Wi-Fi fingerprinting for indoor localization. For example, some indoor environment do not have many straight pathways, then PDR may not work well as the user’s step length may vary for different turning. Moreover, the user may not always walk in straight line; if there are too many turnings made, PDR will also fail to provide good positioning, due to the error accumulation effect. Hence, it is good to have another IPS to function under such circumstances to allow good user experience. However, the integration of PDR and Wi-Fi fingerprinting is not discussed in this paper and we intend to defer this as our future work. We only focus on the development of PDR with correction points and its usefulness in this paper.

The rest of this paper is organized as follows. In Section II, we review the related work. Section III provides the architectural concept of our work. We present our experimental setting and results analysis in Section IV and conclude this work in the last section.

2 Related work

Indoor positioning is not new and many approaches had been explored for indoor positioning besides the aforementioned. Some notable examples include ultra-wideband (UWB) [17], radio-frequency identification (RFID) [18] and foot-mounted inertial measurement unit (IMU) [3]. While these approaches are better in terms of positioning accuracy, the implementation of such IPS for public area such as shopping complexes are often difficult because it involves additional hardware that is not widely available to the users. Moreover, it can be inconvenient to carry/wear additional device just for the purpose of indoor positioning. Therefore, IPS techniques such as Wi-Fi fingerprinting and PDR are gaining popularity because almost every smartphones have Wi-Fi connection and equipped with various sensors (e.g. accelerometer, magnetometer and gyroscope sensors).

2.1 Wi-Fi Fingerprinting technique

In general, the deployment of Wi-Fi fingerprinting technique is divided into two stages; offline mapping and online positioning. During the offline stage, the RSSI of all access points (APs) in every locations (RPs) are collected to build a fingerprint database of a particular building. During the online stage, the RSSI values of different access points (AP) observed from the users’ smartphones are then compared with the fingerprint database for location estimation [6, 7].

Unfortunately the positioning accuracy of the Wi-Fi fingerprinting approach is affected by the grid granularity used to create the fingerprint database. On top of that, Wi-Fi signal strength fluctuates and changes depending on its environment [6], [7]. As such the fingerprinting database must be maintained frequently to ensure the accuracy of Wi-Fi fingerprinting technique. Last but not least, different smartphones may not be able to use the same Wi-Fi fingerprinting database for accurate positioning performance, because every smartphone model may use different Wi-Fi chipset with antenna design that varies significantly. Therefore, it is difficult to obtain accurate positioning by using Wi-Fi fingerprinting technique alone. Due to the inherent characteristic of Wi-Fi signal, it is even more challenging to perform continuous position tracking using Wi-Fi fingerprinting technique.

2.2 Pedestrian dead reckoning (PDR)

The PDR approach works by acquiring raw data from smartphone sensors such as accelerometer, gyroscope and magnetometer to estimate the step length and heading orientation of pedestrians [9]. Then, the current position of pedestrians were estimated by counting the number of steps walked since their previously known position as shown in Fig. 1.

Fig.1

Process of PDR approach.

This approach is practical for continuous position tracking because each step taken is being tracked. Moreover, the required sensors are available in most smartphones, no additional hardware such as the INS unit [19] or MEMS unit [20] are needed. The PDR process can be divided into four steps: step detection, step length estimation, heading orientation and current position estimation, which can be expressed as $S_{n} = S_{n - 1} + L_{n} (\frac{\sin θ_{n}}{\cos θ_{n}})$ (1) where S_n is the current position estimation of the pedestrian, S_n-1 is the previous position estimated, L_n is the step length estimation calculated and θ_n is the heading orientation at time step n. With the parameters estimated through the PDR technique, it is able to provide continuous positioning because the pedestrian’s position is an estimation based on every step taken after leaving the starting position. However, as the PDR technique depends on previous position for estimating current position, many small step length estimation errors will eventually accumulate and create a large position drift. Unfortunately the errors are not produced only by inaccurate step length estimation, but also affected by varying sensor chipsets used in different smartphones and distinct walking gaits by varioususers.

2.3 Summary

Wi-Fi fingerprinting techniques have proven their practicality in IPS [4 –7] and are gaining popularity. Unfortunately, due to the inherent characteristic of Wi-Fi (i.e. path loss effect), these technique will not be suitable for continuous positioning tracking. While the PDR technique is able to provide continuous position tracking, its error accumulates very fast. At the same time, the positioning accuracy is also affected by pedestrians’ walking gaits and differences in sensors from various smartphone models.

Jun et al.[21] improved the conventional Wi-Fi fingerprinting technique by directly assigning a unique sequence to each region for every smartphone respectively. This approach effectively reduces the effect of inconsistency in Wi-Fi signal measurement for various smartphone models (due to the chipset and antenna used are different). However, continuous position tracking is still not possible by using the proposed Wi-Fi fingerprinitng alone.

The concept of reference points (i.e. beacons, correction points) for IPS is not new. Similar concept has been explored by Danqing et al. [16] and Chen et al. [11]; they proposed the usage of an iBeacon to improve on positioning accuracy for Wi-Fi fingerprinting and PDR techniques respectively. However, the benefits of beacons are not fully explored. On the contrary, our proposed correction points are logical points which may not need real physical beacons; they are points where the actual location is known to the smartphones. Our proposed correction points not only provide absolute location information for smartphones to improve their positioning accuracy, but also can be used to recalibrate the users’ step length measurements so that the accumulated error in PDR is greatly reduced.

3 The proposed solution

In this section, the concept of correction points and its integration with PDR based IPS are described in more detail.

3.1 The concept of "correction points"

Correction points are logical points with known location without ambiguity for smartphones to detect when they are within the sub-meter proximity. Other than being a point to pinpoint the location of a user, a single correction point can be used as a reference for the PDR to adjust the position accuracy of all the future steps which improves the accuracy of overall continuous positioning tracking.

In addition to that, a pair of correction points can be used to calibrate the positioning measurements. This is because the speed and duration taken to travel from one point to another point can be accurately captured. Such information can then be served as the ground truth to recalibrate the readings captured from the mobile phones. Using PDR as an example, the direction and the number of steps taken to travel between two points can be used to recalibrate the readings captured from the mobile phone. Hence, the drift errors of PDR can be greatly reduced, everytime the user walk past a pair of correction points. The use of correction points solves not only the issues of different smartphone models but also different pedestrians’ walking gaits.

3.2 Pedestrian dead reckoning (PDR) correction

The PDR correction in this work is done by recalibrating the most influential parameters in PDR: the step length estimation. A pair of correction points is set up similar to that in Fig. 2 with the set distance, d_c. Recalibration will only be done at the second correction point and the smartphone is required to be detected by both correction points. The correction in PDR progresses as follow:

Fig.2

Set up of correction points in a pair.

When Dev01 enters the proximity of correction point A, it records the accumulated steps taken by the pedestrian.

Dev01 continues positioning and when it enters the proximity of correction point B, the accumulated steps taken by the pedestrian is recorded again.

With the known distance, d_c of the correction points and the total steps taken (from point A to point B), recalibration towards the step length estimation can be expressed as,

L_{n} = \frac{d_{c}}{N}

(2) Where L_n is the corrected step length, d_c is the distance between correction point A and point B, N is the number of steps recorded from correction point A to point B. The proposed PDR also uses the heading direction of each steps to ensure that the users are indeed walking directly from point A to point B to avoid inaccurate recalibration.

4 Experimental results

This section presents the experimental setup and results on the proposed PDR correction. In first experiment, PDR with different step length approximation techniques are compared. In the second experiment, the proposed correction points for PDR are implemented in a real environment.

4.1 Experiment on PDR correction

In this experiment, two Intel^® Edison boards are deployed as correction points and experiment is set up as shown in Fig. 3. The distance, d_c between a pair of correction points is fixed at 10m. Then, the distance from the next nearest correction point, d, is set to a variation of 10m, 20m, 30m and 40m. The positioning accuracy is determined by calculating the error between d (actual distance) and the estimated distance through PDR approach (with and without correction points).

Fig.3

Experimental Set up.

Evaluations were performed on different smartphone models; Samsung S6, Samsung S3 Mini and One Plus 3T with 5 pedestrians (4 male and 1 female). Positioning errors were compared between the use of existing step length estimation methods (i.e. constant, height input and Weinberg [22])) with our proposed PDR correction in step length estimation. The definition of each methods are listed below:

Constant step length: This method uses constant step length for all users regardless of its walking speed and height. We fixed the step length as 78cm for male and 70cm female.

Height input: The step length can also be estimated based on the height of different persons, which can provide more accurate results. To calculate the step length, equation below is being used: $L_{1} \approx k \times height$ (3) where k is a constant value and it is different for male and female. In this experiment, we fixed k = 0.415 for male and k = 0.413 for female, which are the same as other researchers for fair benchmarking purpose [23].

Weinberg approach: According to the proposal from Weinberg [22], vertical acceleration was applied to the user’s hip when he/she moves in order to determine the walking distance. As such, the estimated walking distance was adjusted by a unit conversion, which is represented by the equation below: $L_{1} \approx K_{1} \times \sqrt[4]{A_{\max} - A_{\min}}$ (4) where A_max and A_min are the maximum and minimum acceleration values, measured on the Z-axis on one stride. It is calculated online when the user walks, and it depends heavily on the walking behaviour. K₁ is the unit conversion constant (i.e., feet or meters travelled), which is set as K = 0.41 in this paper; this value is also used by other researchers [23].

Correction Points: Our proposed method starts with an initial step length estimation using Weinberg approach. Once the user passes the correction points, the step length will be updated and no longer using Weinberg approach.

Experimental results are shown and discussed as follows. Figure 4 shows the graph of absolute mean distance error observed for different PDR approaches at increasing distances, d. As the PDR technique uses previous location to estimate for current location, the PDR suffers from error accumulation as the distance increases. For example, the step length estimation with height input shows 3m of positioning error after travelling for 40m. Our proposed solution of PDR correction has the lowest error accumulation, wherein after travelling for 40m, the positioning error is reduced to 2m compared to other PDR which uses different step length estimation approaches. Compared to the next best method (with height input), the improvement in accuracy is 50%.

Fig.4

Graph of mean distance error for different PDR approaches in Samsung S6 smartphone.

Figures 5 and 6 show the absolute mean distance error using three different smartphone models after travelling 10m and 40m starting from the Correction Point 2 respectively. It is important to note that distance error is affected by different users’ walking gaits and smartphones models. This experiment showed that, the proposed correction point for PDR is able to reduce the distance error more than 50% compared to the other techniques with correction points. The PDR calibrated with the proposed correction points can estimate distance travel more accurately and users can travel further before the error becomes significantly large.

Fig.5

Mean distance error and standard deviation for three different smartphone models at 10m.

Fig.6

Mean distance error and standard deviation for three different smartphone models at 40m.

4.2 Experiment for adjustment and improvement on PDR map

In this experiment, five Intel^® Edison boards are deployed in the building as correction points and experiment is set up as shown in Fig. 7. This experiment is conducted to show the adjustment and improvement on the drift of PDR map when single mode of correction point is detected. PDR map was constructed when pedestrian walked from the starting point at CP1 to CP5 and a total of four walking trials were recorded. To maintain good readability, only two trials are shown in Figs. 8 and 9. The results of PDR positioning before and after adjustment by the correction points were shown in Figs. 8 and 9 respectively.

Fig.7

Floor plan and the positions of correction points.

Fig.8

PDR positioningap before adjustment.

Fig.9

PDR positioningap after adjustment.

From Fig. 8, the tracked PDR map shows great drift from the floor plan path while in Fig. 9, the drift of PDR map is improved with the help of correction point’s detection.

5 Wi-Fi Fingerprint mapping with corrected PDR

This section is to elaborate on the motivation of adjusting the positioning accuracy of previous steps taken by the users. As mentioned in section 2.1, Wi-Fi fingerprinting requires a mapping stage where all the RSSI values of multiple access points at every location in a building has to be collected to build a Wi-Fi fingerprint database. Unfortunately, RSSI values fluctuate from time to time due to the natural characteristic of radio waves (path loss). Therefore, an accurate and fine-grained Wi-Fi fingerprint database is often very costly to build and maintain, as it needs to be re-mapped from time to time.

In this work, we show that the PDR with correction points can be extended to perform Wi-Fi fingerprint mapping. When the user walks around a building with PDR IPS, the position of each steps can be traced accurately as the user walks past a pair of correction points. As such, the proposed PDR can be used to perform fine-grain Wi-Fi fingerprint mapping simply by recording the Wi-Fi fingerprint for each step that he/she has taken. Hence, when a user is using Wi-Fi fingerprinting technique to perform indoor positioning, the sampled RSSI value can then be mapped with the Wi-Fi fingerprint which corresponds to the steps taken previously.

The aforementioned approached has been implemented and Fig. 10 is the result. The Wi-Fi signal of the corridoor is fingerprinted by walking to and fro for five times. The Wi-Fi fingerprint of each steps are recorded when the user perform PDR positioning. Subsequently, the position of the steps are adjusted as the user walk pass a pair of correction points.

Fig.10

Wi-Fi Fingerprinting IPS using PDR map after adjustment.

In Fig. 10, IPS trials refers to the attempts to perform indoor positioning using Wi-Fi fingerprinting technique. Dots with the same colour refers to the steps with Wi-Fi fingerprint that matches with the user existing position. From this experiment, it is clear that our proposed PDR approached can be used to reduce the challenges of Wi-Fi fingerprint mapping. On the other hand, it also shows that it is difficult to uniquely distinguish each steps with Wi-Fi fingerprinting because the RSSI value fluctuates; it is possible for two or more locations share the same Wi-Fi fingerprint.

6 Conclusion and future work

PDR technique is able to provide continuous position tracking but its positioning error accumulates very quickly to be useful. The errors are mainly from inaccurate step length estimation, which can be caused by different model of smartphones and also pedestrian walking gaits. Therefore, this work introduces the concept of correction points to improve the accuracy of PDR. The correction points are different from existing beacon based solutions [11] because the proposed correction points do not only correct the current location of the users but also the step length estimation for improving the accuracy of subsequent PDR positioning. From the experimental results, single correction point detection allows adjustment on PDR map which reduces the overall drift of the PDR. On top of that, a pair of correction points detection allows PDR to recalibrate the users’ step length. The experimental results show that the proposed PDR is able to provide better positioning accuracy even for different smartphone models and pedestrians. Besides that, we also show that the proposed solution can be used to perform Wi-Fi fingerprint mapping while the user is using PDR for positioning. This greatly reduces the effort to manually re-build the fingerprint database from time to time, which is required by many Wi-Fi fingerprint based IPS. In future, we intend to combine both Wi-Fi fingerprint and PDR techniques with the correction points for more challenging indoor environment that do not provide many straight pathways.

Footnotes

Acknowledgement

This research work is supported by Malyasia CREST Fund “Cyber Physical System with Collaborative Indoor Localization and Mapping” with project number P02C3-14.

References

Want

, Hopper

, Falcao

and Gibbons

, The active badge location system, ACM Trans Inf Syst, 10(1) (1992), 91–102.

Tango Concepts, 2017. [Online]. Available: https://developers.google.com/tango/overview/concepts. [Accessed: 20-Dec-2017].

, Zhou

, Wieser

and Zhou

, Pedestrian positioning using WiFi fingerprints and a foot-mounted inertial sensor, 2017 Eur Navig Conf ENC 2017, , no. 1, 2017, pp. 91–99.

, Guo

, Wu

and Yang

, A novel radio map construction method to reduce collection effort for indoor localization, Meas, J Int Meas Confed, 94 (2016), 423–431.

Schussel

and Pregizer

, Coverage gaps in fingerprinting based indoor positioning: The use of hybrid Gaussian Processes, 2015 Int Conf Indoor Position Indoor Navig IPIN 2015, 2015.

Jedari

, Wu

, Rashidzadeh

and Saif

, Wi-Fi based indoor location positioning employing random forest classifier, 2015 Int Conf Indoor Position Indoor Navig IPIN 2015, , no. October, 2015, pp. 13–16.

Boonsriwai

and Apavatjrut

, Indoor WIFI localization on mobile devices, 2013 10th Int Conf Electr Eng Comput Telecommun Inf Technol ECTI-CON 2013, 2013.

Pasku

, et al., A magnetic ranging-aided dead-reckoning positioning system for pedestrian applications, IEEE Trans Instrum Meas, 66(5) (2017), 953–963.

Kang

and Han

, SmartPDR: Smartphone-based pedestrian dead reckoning for indoor localization, IEEE Sens J, 15(5) (2015), 2906–2916.

10.

Akeila

, Salcic

and Swain

, Reducing low-cost INS error accumulation in distance estimation using self-resetting, IEEE Trans Instrum Meas, 63(1) (2014), 177–184.

11.

Chen

, Zhu

and Chai Soh

, Smartphone inertial sensor based indoor localization and tracking with iBeacon corrections, IEEE Trans Ind Informatics, 3203(c) (2016), 1–1.

12.

Radu

and Marina

M.K.

, HiMLoc: Indoor smartphone localization via activity aware pedestrian dead reckoning with selective crowdsourced WiFi fingerprinting, 2013 Int Conf Indoor Position Indoor Navig IPIN 2013, , no. October, 2013, pp. 28–31.

13.

Zhuang

, Li

, Qi

, Lan

, Yang

and El-Sheimy

, A two-filter integration of MEMS sensors and WiFi fingerprinting for indoor positioning, IEEE Sens J, 16(13) (2016), 5125–5126.

14.

Chen

, Wu

E.H.

, Jin

and Chen

, Intelligent fusion of Wi-Fi and inertial sensor-based positioning systems for indoor pedestrian ngation, IEEE Sens J, 14(11) (2014), 4034–4042.

15.

, He

, Nielsen

and Lachapelle

, Magnetic Wifi, 2015 Int Conf Indoor Position Indoor Navig IPIN 2015, 2015.

16.

Danqing Shi

, Xinhong Wang

, Tao Peng

, and Chao Wang

,Hybrid wireless indoor positioning with ibeacon and wi-fi, 11th Int Conf Wirel Commun Netw Mob Comput (WiCOM 2015), 2015, pp. 5–5.

17.

Granja

F.S.

, UWB location systems: Indoor performance analysis, IEEE Trans Instrum Meas, 66(8) (2017), 1–12.

18.

J.-Q.

, Zhang

S.-P.

, Lei

, Fu

X.-H.

, Zhong

and Gang

, Accurate RFID localization algorithm with particle swarm optimization based on reference tags, Journal of Intelligent & Fuzzy Systems, 31(5) (2016), 2697–2706.

19.

Harle

, A survey of indoor inertial positioning systems for pedestrians, IEEE Commun Surv Tutorials, 15(3) (2013), 1281–1293.

20.

and Lin

, Apply Pedestrian Dead Reckoning to indoor Wi-Fi positioning based on fingerprinting, Int Conf Commun Technol Proceedings, ICCT, 2013, pp. 206–210.

21.

Jun

, et al., Low-overhead WiFi fingerprinting, IEEE Trans Mob Comput, 1233(c) (2017), 1–14.

22.

Weinberg

, Using the ADXL202 in Pedometer and Personal Ngation Applications, Analog Devices, Inc., Norwood, MA, USA, 2002.

23.

Pratama

and Widyawan

R.H.

, Smartphone-based Pedestrian Dead Reckoning as an indoor positioning system, International Conference on System Engineering and Technology (ICSET), 2012, pp. 1–6, 11–12.