An Indoor Pedestrian Localization Algorithm Based on Multi-Sensor Information Fusion

Show more

1. Introduction

The indoor positioning navigation system can provide navigation service for users in public places such as large complex buildings, and has wide application prospect [1] [2]. There has been a growing interest in indoor positioning technology that relies on the existing senor, like the Wi-Fi, Zigbee, Pedestrian dead reckoning (PDR), Received signal strength indication (RSSI) and Radio Frequency Identification (RFID). As the PDR positioning systems can only provide relative position information, error will accumulate over time, it is necessary to provide absolute position information to correct the error [3]. RSSI positioning algorithm is simple, can provide absolute location information without adding additional hardware, Therefore, the fusion algorithm based on PDR and RSSI has been widespread concern. Paper [4] discussed Indoor Location Algorithm based on the RSSI fingerprint information, and this algorithm has high accuracy only in low noise environment, it is not suitable for high noise environment. Paper [5] analyzes the influence of path attenuation coefficient on location accuracy in order to improve the accuracy in the high noise environment. In paper [6], we propose a method to calculate the path fading exponent by measuring the node energy and the geometric relationship among nodes.

In recent decades, with the rapid development of integrated circuits, smart phones had made great progress in data storage and data processing, and embedded many micro-sensors, such as the accelerometer, the gyroscopes, and the magnetometers and so on [9]. The rapid development of smartphones provides a new platform and opportunity to achieve an economical and friendly positioning system in today’s indoor environment.

This paper mainly studies a particle filter algorithm based on multi-sensor fusion indoor pedestrian localization, and combines the smartphone with the traditional positioning technology. The first step, the sensors built-in smartphone can predict the user’s movement and observation status, as Bayesian estimates of the movement model and observation model, and establish the fingerprint database of indoor environment. The second step, the particle filter algorithm can filter and fusion the movement model and the observation model. The last step, the localization results will be uploaded to the server in time, and the location fingerprint database will be built incrementally, which can adapt the dynamic transform of the indoor environment.

2. Related Work

2.1. Indoor Location Algorithm Based on Multi-Sensor Information

The sensors built-in smartphone, such as acceleration sensors, gyroscopes, gravitational acceleration and magnetometers, can track the location of the pedestrian in the indoor environment. Figure 1 shows the overall system block diagram.

The wireless module and other sensors built-in the smartphone can predict the pedestrian’s environment state and the pedestrian’s movement state. The proposed algorithm can fuse information of the pedestrian’s movement and observation, and upload the pedestrian’s location information to the application layer.

2.2. Wi-Fi Fingerprint Location Algorithm

This algorithm is usually divided into two stages: the offline training phase and online positioning phase. In the first stage, we should set many reference points

Figure 1. Algorithm architecture.

in this stage and collect the reference data from Wi-Fi access point (AP), such as signal strength, arrival angle, and frequency and so on. Next, we store the reference data with the location information into the database as a set of fingerprint data. In the second stage, we use the smartphone to detect the signal data received at the location to be determined, and then compare the signal data with the database through the corresponding algorithm. Next, we get the user’s actual location information. Figure 2 shows the process of Wi-Fi fingerprint orientation. Table 1 shows fingerprint database with class labels.

The authors in [7] proposed that the number and locations of APs, physical layout, and mean of RSSs at RPs have significant impact on localization precision. To optimize the AP placement, the authors in [8] proposed a novel approach by using a small number of APs to provide full coverage while locating the mobile device within an area with limited size. Wang and Lin [9] proposed a goal programming-driven model which is intergraded with a genetic algorithm and an embedded mask mechanism to resolve the problems of multiple objective AP deployment construction and enhancement. Therefore, the error bounds analysis under different signal distributions in Wi-Fi environments remains an open problem.

3. Particle Filter Based Multi-Sensor Fusion

This paper improves the positioning precision of PDR system by fusion pedestrian gait information, indoor environment information and RSSI, because of PDR system cannot get absolute position information. We assume the pedestrian’s initial position, and get the relative position information from PDR system. We improve the positioning precision of the proposed algorithm by combine the indoor environment to filter the positioning results. But the above problem is a typical nonlinear problem, this means that the conventional linear fusion algorithm cannot get outstanding results. To solve those problems, we select the particle filter algorithm to fuse the multi-sensor data, which not only has

Figure 2. Wi-Fi fingerprint orientation.

Table 1. Fingerprint database with class labels.

better flexibility, extensive practicality, but also can improve the positioning precision.

3.1. Basic Mathematical Model

The pedestrian’s localization is described as dynamic system state estimation problem [10] in the indoor environment, the state space equation is defined as follows:

Motion equation:

(1)

Observation equation:

(2)

where and are nonlinear functions, and are independent of the noise sequence, respectively the process noise and observation noise, is the movement information at time t, is the observation information at time t. According to Bayesian estimates, the state estimation problem is to deduce from at time, the estimated.

In this paper, the particle filter can achieve the integration of location information to avoid the integral operation in Bayesian estimation, and provide location data for indoor location-based services.

3.2. Movement Model

Due to the complexity of the pedestrian walk and the low cost of the positioning system in the indoor environment, we use the triangulation of step and azimuth to obtain the relative position information of pedestrians in this paper.

(3)

where and represent the coordinates in the two-dimensional coordinate system, represents the step size at time, indicates the direction of movement at time.

Which mainly need to solve three problems: step numbers, step length and motion detection.

The pedestrian’s movement behavior includes the movement direction and the movement distance. The data of the acceleration and the angular velocity will transform when person in the process of walking [11].

In this paper, we use the acceleration sensors, gyroscopes, gravitational acceleration and magnetometers to perceive the user’s motion behavior. The acceleration sensors are able to determine the changes in pedestrian’s acceleration, it is represented by the acceleration component of the three-dimensional direction. The human body step model is established by data which is collected by acceleration sensors filtering and feature extraction. The direction sensor can capture changes in the direction of motion of the pedestrian. This paper uses the empirical formula to calculate the step size, and correct the user’s step size dynamically [12].

3.3. Observation Model

The KNN localization algorithm calculates the cosine similarity of the RSSI vector measured at the anchor point and the RSSI vector measured at each RP point. The cosine similarity of the two vectors is shown below:

(4)

And then through the query fingerprint library to find the most similar fingerprint data. That each RSSI vector in the fingerprint library uniquely corresponds to the location information of a reference point. The position of the final anchor is estimated as the weight of the reference points, the weight of reference point is.

(5)

is cosine similarity of the reference point and current point. The position of the final anchor is estimated:

(6)

3.4. Particle Filter Based Multi-Sensor Fusion

In this paper, particle filter [13] is used to approximate the probability density function of the user’s position, and filter the movement direction.

It is assumed that each particle has the following state information:

(7)

The user’s position of the map is, is the weight of particle, is the movement direction, is step length, therefore, The state transition equation is shown below:

(8)

is the particle number, is gait cycle, are Gaussian white noise with zero mean.

3.4.1. Initialization

Assume that the user’s initial position is, the number of particle is N, and each particle contains the user’s location information, direction, and particle weight, as discussed in (7). We can obtain the weight of particle is, the sum of the weights is 1. Each particle represents a possible movement state of pedestrian, that is, a possible location of pedestrian [14] [15].

3.4.2. Particle State Transition

It is the user’s location with the update process over time. In the process of pedestrian movement, introducing the weight of particle as the smooth factor of PDR system. As we know, different particle weights will produce different paths.

(9)

is the pedestrian direction, is the pedestrian direction with smooth factor.

3.4.3. Particle Update

By observing the environment in which each particle spreads, to verify that the propagation of the particles is reasonable, and observe the degree of similarity between the possible position of pedestrians represented by each particle and the actual location of pedestrians. The particles closer to the true position of the pedestrian will be given a larger weight, and vice versa. The particle weight is calculated as follows:

(10)

is the possible position of pedestrians represented by i-th particle, is the location which is calculated by the fingerprint algorithm.

Normalized weight calculation:

(11)

3.4.4. Position Calculation

Pedestrian location determination can be based on two criteria: Maximum posterior probability and Weighted Criteria. This paper uses the second method to calculate the position.

(12)

3.4.5. Resampling

With the increase of filtering time, the degradation of particles will occur, the importance of weight may be concentrated to a small number of particles, the need for its resampling, increase the weight of the larger number of particles.

3.4.6. Algorithm Flowchart

Based on the above, an indoor localization algorithm based on multi-sensor fusion is proposed, as shown in Figure 3.

Figure 3. Algorithm flowchart.

4. Experimental Design and Result Analysis

In order to test the positioning performance of the proposed algorithm in this paper, a lot of experiments are carried out. Here are the specific experimental contents of testing the positioning performance based on the solution to realize pedestrian indoor positioning, and analyze the experimental results.

This paper chooses the eighth teaching building of Guilin University of Electronic Science and Technology as an experimental site. The experimental site is 21 meters long and 18 meters wide, and four wireless routers were installed in this experimental site. Experimental site structure shown in Figure 4.

In this experiment, the experimental site will be divided into 50 * 50 small squares according to the laying of floor tiles, 150 small squares in the horizontal direction and 201 in the vertical direction. The size of each small lattice is 0.5 m * 0.5 m.

Data acquisition of acceleration, direction, and Wi-Fi signal strength is achieved by programming based on Android 4.5. The experimenter who hand-

Figure 4. Experimental site structure.

held Huawei mobile phone is walking at the normal pace in the experimental site according to the expected trajectory, and this phone has built-in Acceleration sensors, gyroscopes, gravitational acceleration and magnetometers.

4.1. Step Detection

In order to verify the effectiveness of the pedometer, the experimenter performed 50 times experiments on 100 step numbers. The pedometer results is shown in Figure 5.

Figure 5 shows the accuracy of step numbers can reach more than 73%, and the error of step numbers are mostly in one step.

4.2. Build Fingerprint Database

In the positioning algorithm validation process, the result of location and Wireless signal strength will be uploaded to the database in time, and the location fingerprint database will be built incrementally. The fingerprint data table of location fingerprint database is shown in Table 2.

In this paper, the result of location will be counted by the localization algorithm based on multi-sensor information fusion, and the result of location will be updated the original information in the database, and add the time stamp.

In this experiment, 1000 sets of fingerprint data were collected at each observation point, and the collected data is processed by Gaussian filtering in order to improve the accuracy of fingerprint data.

4.3. Location Experiment

The experimenter is walking in the experimental site with expected trajectory, and collecting the information include acceleration, direction and Wi-Fi signal strength.

Figure 5. Pedometer results histogram.

Table 2. Fingerprint data table of location fingerprint database.

Figure 6 and Figure 7 shows the results of particle filter localization algorithm based on multi-sensor fusion and fingerprint positioning algorithm, and the localization errors are shown in Figure 8 and Figure 9. After the particles converge, the positioning results are analyzed as follows. Simulation result by particle filter localization algorithm based on multi-sensor fusion is lower in stability and accuracy than the fingerprint positioning algorithm, and the error of pedestal dead reckoning is effectively converged. The average error using multi-sensor fusion is above 0.35 meters compared to the fingerprint positioning data’s above 1.65 meters. 93.9% of the localization errors are lower than 0.5 meter by particle filter localization algorithm based on multi-sensor fusion but the fingerprint positioning algorithm data’s 52.3%.The average errors are shown in Table 3.

Figure 6. Localization test trajectory Diagram (N = 100).

Figure 7. Localization test trajectory Diagram (N = 1000).

Figure 8. Error analysis of different particle numbers.

Figure 9. Error analysis of PDR with RSSI and RSSI.

Table 3. Average error comparison of the estimated path and true path.

Compared with Figure 6 and Figure 7 we can see that with the increase of the number of particles, the positioning precision is improved further, the average error when N = 100 is above 0.35 meters, and when N = 1000 is above 0.27 meter, however, increasing the number of particles means increasing the amount of data processed and the running time of the program. When the number of particles is 100, the program running time is approximately 3.781 seconds, and when the number of particles is 1000, the time increased by approximately 5.332 seconds. This poses a great impact on positioning real-time.

4.4. Robustness Verification

In Section 4.3, the experimenter walked at normal speed, and took the smart phone in his hand. In the next experiment, the experimenter will walk slowly, run or put the smart phone in pocket. Under the above three experimental conditions, the average errors are shown in Table 4.

Table 4 shows that the above three cases will impact the accuracy of the position algorithm which proposed in this paper. Compared with the algorithm based on multi-senor fusion and Wi-Fi we can see that with the increase of the number of the senor, the positioning precision is improved further. But the average errors will be increased because the sensor noise will be increased in those scenarios. The noise is corrected by the particle filter algorithm, which further reduces the influence on the positioning accuracy and improves the robustness of the algorithm in this paper.

5. Conclusion

Due to the existing indoor positioning technology which has many deficiencies, such as high cost, low positioning accuracy and low sensor utilization, an indoor pedestrian localization algorithm based on multi-sensor information fusion is proposed in this paper. The sensor built-in smartphone can obtain pedestrian’s movement information, such as acceleration, step size, direction and so on. The proposed algorithm fused PDR and RSSI can improve the accuracy and the stability. From the above experimental results, the average error of the proposed method is above 0.35 meters in the range of, which is better than the location algorithm based on Wi-Fi with the average error of 1.65 meters. The proposed algorithm can improve the accuracy, stability and real-time of positioning, and achieve good positioning effect. In the proposed method, the way to hold the phone must be consistent in order to ensure the accuracy of data processing and collection in the process of collecting fingerprint data. Some further work will be done to overcome the impact of the attitude angle of the phone on the indoor localization algorithm.

Table 4. Robustness verification

Acknowledgement

This work is supported by the National Natural Science Foundation of China (No.61371107), the Guangxi Experiment Center of Information Science (No.LD16061X), the Guangxi Natural Science Foundation (No.2016GXNSFBA38014), and the China Postdoctoral Science Foundation (No.2016M602921XB) and the Opening Project of Guangxi Key Laboratory of UAV Remote Sensing (No. WRJ2016KF01).

References

[1] Harle, R. (2013) A Survey of Indoor Inertial Positioning Systems for Pedestrians. Communications Surveys & Tutorials IEEE, 15, 1281-1293.
https://doi.org/10.1109/SURV.2012.121912.00075

[2] Zhang, Z., Lu, Z., Saakian, V., et al. (2014) Item-Level Indoor Localization With Passive UHF RFID Based on Tag Interaction Analysis. IEEE Transactions on Industrial Electronics, 61, 2122-2135. https://doi.org/10.1109/TIE.2013.2264785

[3] Zampella, F., Jimenez, R.A.R. and Seco, F. (2013) Robust Indoor Positioning Fusing PDR and RF Technologies: The RFID and UWB Case.

[4] Cheng, L., Wu, C.D. and Zhang, Y.Z. (2011) Indoor Robot Localization Based on Wireless Sensor Networks. IEEE Transactions on Consumer Electronics, 57, 1099-1104. https://doi.org/10.1109/TCE.2011.6018861

[5] Yang, L., Chen, H., Cui, Q., et al. (2015) Probabilistic-KNN: A Novel Algorithm for Passive Indoor-Localization Scenario. Vehicular Technology Conference. IEEE, 1-5.

[6] Mao, G., Anderson, B.D.O. and Fidan, B. (2007) Path Loss Exponent Estimation for Wireless Sensor Network Localization. Computer Networks, 51, 2467-2483.

[7] Baala, O., Zheng, Y. and Caminada, A. (2009) The Impact of AP Placement in WLAN-Based Indoor Positioning System. Eighth International Conference on Networks. IEEE Computer Society, 12-17.

[8] Liao, L., Chen, W., Zhang, C., Zhang, L., Xuan, D. and Jia, W. (2011) Two Birds with One Stone: Wireless Access Point Deployment for Both Coverage and Localization. IEEE Trans. Veh. Technol., 60, 2239–2252.
https://doi.org/10.1109/TVT.2011.2109405

[9] Wang, C.S. and Lin, S.L. (2015) An Integrated Optimization Model for Wireless Access Point Deployment Construction, and Enhancement. IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, NETWORKING and Parallel/Distributed Computing. IEEE, 1-6.

[10] Shin, H., Chon, Y. and Cha, H. (2012) Unsuper-vised Construction of an Indoor Floor Plan Using a Smartphone. IEEE Transactions on Systems Man & Cybernetics Part C Applica-tions & Reviews, 42, 889-898.
https://doi.org/10.1109/TSMCC.2011.2169403

[11] Arvikar, S.A. (1975) The Prediction of Muscular Load Sharing and Joint Forces in the Lower Extremities during Walking. Journal of Biomechanics, 8, 89-102.

[12] Kim, J.W., Han, J.J., Hwang, D.H., et al. (2004) A Step, Strideand Heading Determination for the Pedestrian Navigation System. J Glob Position Sys., 3, 273-279.
https://doi.org/10.5081/jgps.3.1.273

[13] Carpenter, J., Clifford, P. and Fearnhead, P. (1999) Improved Particle Filter for Nonlinear Problems. 146, 2-7.

[14] Damodaran, P. and Vélez-Gallego, M.C. (2012) A Simulated Annealing Algorithm to Minimize Makespan of Parallel Batch Processing Machines with Unequal Job Ready Times. Expert Systems with Applications, 39, 1451-1458.

[15] Alasti, H., Xu, K. and Dang, Z. (2009) Efficient Experimental Path Loss Exponent Measurement for Uniformly Attenuated Indoor Radio Channels. Southeastcon, SOUTHEASTCON '09. IEEE, 255-260.