Extended Kalman Filter Model for Gps and Indoor Positioning System

Extended Kalman Filter Model for GPS and Indoor Positioning System Long Kam-Kim Department of Telecommunications Engineering, Faculty of Electrical and Electronics Engineering HCM City University of Technology, Ho Chi Minh City, Vietnam Tuan Do-Hong Department of Telecommunications Engineering, Faculty of Electrical and Electronics Engineering HCM City University of Technology, Ho Chi Minh City, Vietnam Abstract – Object positioning is an old subject. It’s being used more and more in many areas, especially in military, traffic, social security and civil services.The most popular positioning system in the world is Global Positioning System (GPS). However, GPS has limited degree of accuracy for low priority users. This paper proposes a solution for solving these limitations by using Extended Kalman Filter (EKF). Moreover, GPS is almost invalid in indoor environments. The paper also introduces an indoor positioning system model based on GPS ideology and EKF algorithm. Beca use of the similarity in ideology, it’s easier for handoff procedure between outdoor and indoor environments and brings back the spatial continuous in positioning.The simulation results show that with the EKF, the accuracy of positioning is improved significantly in both outdoor and indoor environments. Keywords- GPS, Kalman filter, RFID, RSSI, EKF, indoor positioning. I. INTRODUCTION II. EKF MODEL FOR GPS Generally, Kalman algorithm is a group of mathematical equations described an efficient recurrence method for state estimation of process that it is optimal in the sense that it minimizes the estimated error covariance, when some presumed conditions are met [2]. EKF is an extension of Kalman filter for non-linear systems.A. Global Positioning System (GPS) In order to positioning, it requested that user’s receivers get signals from at least 4 GPS satellites. Distances between user and satellites are determined by using pseudorange code. At the same time, satellites an d receiver transmit a same pseudorange code. Because of propagation delay, signal received from satellites have phases delay than signal of receiver. By compared their phase, the distances can calculate. This method is called Time of Arrival (TOA). [1] B. Problem ExpressionPositioning based on GPS is affected by many noise sources, such as propagated errors, satellite and receiver caused errors, other errors from Selective Availability, dilution of precision, interference etc [1]. Several techniques are used to improve the accuracy of positioning in GPS, for example, DGPS (Differential GPS), Smart Antenna, Kalman Filter etc. This paper focuses on Extended Kalman Filter (EKF) solution, in order to introduce one way to model GPS system and sources of error. Nowadays, positioning applications in indoor environment are being extended.Especially, it becomes necessary in tunnels, supper huge plants, very high buildings, etc. The paper introduces a kind of Indoor Positioning System based o n GPS’s ideology and using EKF algorithm to help this system improve the accuracy of positioning. Assume that GPS system is tracking a mobile object. It is a uniform speed motion in 3D space with attendance of random acceleration events. GPS receiver puts on object updates its position continuously. However, the location is affected by measurement noises and propagation noises.Therefore, the calculating position and the real position are different. In order to improve the accuracy of position, we use EKF to model system and noises so that it diminishes the effect of noises. C. Modeling of system Defining the sate vector of system as follow: ? RX ( n ) ? ? RY ( n ) ? ? ? ? RZ ( n ) ? X (n) = ? ? ? VX ( n ) ? ?VY ( n ) ? ? ? ?VZ ( n ) ? where RX(n),RY(n),RZ(n) are coordinates of user at nth sample, VX(n), VY(n), VZ(n)) are x, y, z – components of user’s velocity at nth sample.Following [3], the characteristic equations for system can be extended as RX(n+1) = RX(n) + VX(n)T + ax(n)T 2 RY(n+1) = RY(n) + VY(n)T + ay(n)T 2 RZ(n+1) = RZ(n) + VZ(n)T + az(n)T 2 VX(n+1) = VX(n) + ax(n)T VY(n+1) = VY(n) + ay(n)T VZ(n+1) = VZ(n) + az(n)T (1) (2) (3) (4) where VX(n), VY(n), VZ(n)) are x, y, z – components of user’s velocity at nth sample, bf = ? bu/? t, dPRi is called delta-pseudorange correlated with user and ith satellite. [4] In order to reducing effect of errors, the EKF is used to model state noise vectors and measurement noise vectors.After characteristic matrixes are calculated, EKF iteration loops are started. The EKF algorithm will calculate estimation of the state vector by minimizing the estimated error covariance (between estimated values and real values). D. Simulation results for outdoor-EKF GPS Data for simulation on Matlab7. 8. 0(R2009a) †¢ †¢ †¢ User’s initial velocity: (3,6,2) meters/second Sampling rate: 1000 samples/second Iteration steps: 500 Process noise vector: W = 5* NORMRND (0, 500, 3, 1) Pr ocess noise variance: Q = 50* eye (3) Measurement noise vector: V = 5 * NORMRND (0, 500, 2, 1) Measurement noise variance: R = 50 * eye (2) (5) (6) here ax(n), ay(n), az(n) represent acceleration events at nth sample ( it is referred to state noises or process noises). According to [4], User’s positions are determined base on distances between user and four satellites. PRi= +bu, i=1,2,3,4 (7) †¢ Fig. 1 shows the simulation results for Lagrange iteration and EKF iteration compared with the true position values. In geographic coordinates, PRi is the distance between the user and the ith satellite, (SXi,SYi,SZi) are coordinates of ith satellite, (RX,RY,RZ) are coordinates of the user; bu=c. t with t is receiver clock offset compared to GPS time and c is the speed of light.PRis are determined by GPS’s receiver. Coordinates of satellites are obtained by decoding satellite report, while (RX, RY, RZ) and bu are unknowns. With system of equations (7) above, the root [RX,R Y,RZ,bu,] can be calculated by using Lagrange iteration [4]. However, measurement values PRi are affected by noises (measurement noises). Therefore the root of system of equations is not accuracy. After differentiating equations (7), we obtain dPRi = (RX ? SXi)? RX + (RY ? SYi)? RY + (RZ ? SZi)? RZ (RX ? SXi)2 + (RY ? SYi)2 + (RZ ? SZi)2 + ? bu = (RX ? SXi). VRX +(RY ? SYi). VRY +(RZ ?SZi). VRZ +bf PRi ? bu Figure 1. Simulate tracking User’s trajectory in outdoor environment (8) In Fig. 1, red curve simulates user’s motion,Green curve simulates calculated trajectory of user receiver without EKF, blue curve simulates calculated trajectory of user receiver in EKF model. Based on GPS’s ideology, this paper introduces an indoor positioning model using EKF, called Indoor-EKF GPS. Indoor-EKF GPS is hoped that it makes over easier with GPS, in such a way, we just use a handle equipment to keep the continuous positioning while moving between indooroutdoor environments.I n Fig. 3, an arranged system of equipments in space can be recognized as pseudo-satellites. Indoor spaces are complicated environments for wave propagation. Distances between user and pseudo-satellites cannot be determined using TOA technique like in outdoor GPS. Here, TOA technique is replaced by RSS (Received Signal Strength) technique. This technique measures the path loss and calculates the distance between source and receiver. Figure 2. Errors in outdoor positioning. Red points: positioning errors without EKF. Green points: positioning errors in EKF model.Comments on simulation results: †¢ The maximum error is about 5 meters in case using EKF model, whereas 25 meters in case without EKF. Trajectory of user receiver in EKF model is closer to trajectory of user’s motion than trajectory of user receiver without EKF. The average estimation error of EKF is very small than without EKF case. However, several points in curve are under suddenly changing errors. Figure 3. Ind oor positioning system. †¢ According to IEEE 802. 11 recommended channel model, the relation between free space path loss and distance d in breakpoint radius is given by [5] LFS(d) = L0 + 10? 1lg(d), 0 < d ? BP (9) †¢ According to the result, it shows that the positioning errors are reduced significantly. III. A. INDOOR POSITIONING SYSTEM where ? 1 is called distance-power-gradient up to breakpoint distance dBP, Lo represents the path loss in decibels at one meter distance. The overall path los for any distance is modeled as [5] Indoor-EKF GPS Recent years, indoor environment has been extended so that indoor positioning demands are extended, too. Furthermore, it becomes necessary in tunnels, supper huge plants, very high buildings etc, and giving convenient for absent minder when household equipments are positioning.However, GPS is almost invalid in indoor environment. The reason is that GPS signal has low power. Even GPS signal can be received, the error positioning of GP S is not appropriate with Indoor applications. ?LFS (d ) +W, d ? dBP ? L(d ) = ? ? d ? ?LFS (dBP ) +10? 2 lg ? d ? +W, d > dBP ? BP ? ? (10) where ? 2 is distance-power-gradient over break-point distance dBP. It’s required at least four distances form user to pseudosatellites are determined for calculating the user’s coordinates. Fig. 4 shows calculation process for user position. Figure 6. The second model. Figure 4. User’s coordinates calculation.B. In the next section, the RFID (Radio Frequency Identification) technology will be used to implement this system. There are two implementation models: The first model: (Fig. 5) The RFID active chips are pseudo-satellites, and readers will be used as GPS’s receivers. Modeling of system Definition of the sate vector and the characteristic equations for system are similar with outdoor case above. However, because of difference on distances calculating method, equation (7) and equation (8) are not used here. This equation below is replaced equation (7) LPi=L0 + 10? lg (di) , i=1? 4 (11) here di is distance between user and ith pseudo-satellite, LPi is value of path loss on distance di. W appears as representative of noises and interferences. Here, we assume that it is Gaussian distribution, ? is distance-power-gradient (we have not examined its change yet. Here, we assume that it is constant). After differentiating equations (11), we obtain dLPi = Figure 5. The first model. 10? ( RX ? SRXi ). VX + ( RY ? SRYi). VY + ( RZ ? SRZi). VZ . ln10 di 2 + ? Wi , i=1,2,3,4 (12) The RFID active chips will transmit these data to readers: †¢ †¢ †¢ The chip’s coordinates (in local coordinates) and its identification.The nominal value of transmitting power. The parameters in IEEE 802. 11 that supporting to correct distance measurements in each specific environment. where (SXi,SYi,SZi) are coordinates of ith pseudo-satellite, (RX,RY,RZ)are coordinates of the user, VX, VY, VZ are x, y, z – components of user’s velocity, dLPi means the variation of path loss on distance di . We imply that the values are taken at nth sample. C. Simulation results for indoor-EKF GPS Data for simulation on Matlab7. 8. 0(R2009a) The second model: (Fig. 8) The RFID active chips will be attached to users. Users will move in space that arranged with RFID readers.These readers will be connected to data fusion center. This center will determine user’s coordinates and send the result to user’s receiver by other channel link. †¢ †¢ †¢ User’s initial velocity: (1,2,1) meters/second Sampling rate: 1000 samples/second Iteration steps: 500 Process noise vector: W = 5* NORMRND (0, 120, 3, 1) Process noise variance: Q = 50* eye (3) †¢ Measurement noise vector: V = 5 * NORMRND (0, 0. 4, 2, 1) Measurement noise variance: R = eye (8) This simulation was repeated 100 times. †¢ The maximum error is about 0. 5 meters in case using EKF model, wh ereas 4. 5 meters in case without EKF.Trajectory of user receiver in EKF model is not closed to trajectory of user’s motion correlative with appreciably positioning error. However the error reduces very quickly by exponential curve. The average estimation error of EKF is very small than without EKF case. However, several points in curve are under suddenly changing errors. IV. CONCLUSION Fig. 7 shows the simulation results for Newton iteration and EKF iteration compared with the true position values. †¢ †¢ In positioning systems, the accuracy of positioning is very important. It must be appropriated with the positioning applications.The paper recommends one way to improve the accuracy of positioning using the EKF. The results of simulations show that the EKF reduce effect of noises on the accuracy of positioning significantly in both outdoor and indoor positioning systems. The Indoor-EKF GPS system is a suggestion model for the future indoor positioning. It is easy f or implementation and expansion, since RFID is very popular and cheap today. Moreover, the Indoor-EKF GPS system has the same structure with GPS system, wherefore the handle equipment can be designed to keep the continuous positioning while moving between indoor-outdoor environments.REFERENCES [1]. Ahmed EI-Rabbany, â€Å"Introduction to GPS†, Artech House, Inc, ISBN 1-58053-183-0, 2002, pp. 13-25,2741. [2]. Grey Welch and Gary Bishop, â€Å"An introduction to the Kalman filter†, Technical Report TR 95-041, 2001. [3]. Jorge Quijano, â€Å"Estimation of the position of a moving target using Extended Kalman Filter†,term paper for the class ECE 510 Statistical Signal Processing, winter 2006. [4]. James Bao-Yen TSui, â€Å"Fundamentals of Global Positioning System Receivers: A Software Approach†, John Wiley & Sons , Inc, ISBN 0-471-20054-9, 2000, pp. 9-15, 230-231. [5].Ahmad Hatami, â€Å"Application of Channel Modeling for Indoor Location Using TOA and RSSà ¢â‚¬ , PhD Thesis, Worcester Polytechnic Institute, 2006, pp. 14-19. Figure 8. Errors in indoor positioning. Figure 7. Simulate tracking User’s trajectory in indoor environment. In Fig. 7, red curve simulates user’s motion, green curve simulates calculated trajectory of user receiver without EKF, blue curve simulates calculated trajectory of user receiver in EKF model. Red points: positioning errors without EKF. Green points: positioning errors in EKF model. Comments on simulation results: