Source: http://www.google.nl/patents/US20070171124
Timestamp: 2017-12-13 16:46:27
Document Index: 223455267

Matched Legal Cases: ['art 2010', 'art 2006', 'art 2012', 'art 2006', 'art 2009', 'art 2009', 'art 2012', 'art 2012', 'art 2014', 'art 2012']

Patent US20070171124 - Process for accurate location determination in GPS positioning system - Google Patenten
A process is provided for accurate location determination in assisted satellite-based positioning systems in which a base station (server) transmits assisting information to the user's receiver (rover). Signals from at least 5 satellites are used for 3-dimensional positioning. Pseudorange measurements...http://www.google.nl/patents/US20070171124?utm_source=gb-gplus-sharePatent US20070171124 - Process for accurate location determination in GPS positioning system
Publicatienummer US20070171124 A1
Aanvraagnummer US 11/103,499
Publicatiedatum 26 juli 2007
Aanvraagdatum 12 april 2005
Prioriteitsdatum 12 april 2005
Ook gepubliceerd als US7362265
Publicatienummer 103499, 11103499, US 2007/0171124 A1, US 2007/171124 A1, US 20070171124 A1, US 20070171124A1, US 2007171124 A1, US 2007171124A1, US-A1-20070171124, US-A1-2007171124, US2007/0171124A1, US2007/171124A1, US20070171124 A1, US20070171124A1, US2007171124 A1, US2007171124A1
Uitvinders Lawrence Weill
Oorspronkelijke patenteigenaar Magellan Systems Japan Inc.
Patentcitaties (3), Verwijzingen naar dit patent (23), Classificaties (9), Juridische gebeurtenissen (5)
Process for accurate location determination in GPS positioning system
US 20070171124 A1
A process is provided for accurate location determination in assisted satellite-based positioning systems in which a base station (server) transmits assisting information to the user's receiver (rover). Signals from at least 5 satellites are used for 3-dimensional positioning. Pseudorange measurements are made in a system of equations having a minimum set of unknowns X,Y,Z, and T. (X,Y,Z) is the 3D rover position in a predefined coordinate system, and T is the time at which simultaneous measurements are made to determine pseudoranges to all satellites. The position of each satellite is a vector-valued function fk (T) of said time T, where fk is determined from satellite ephemeris data or its equivalent, sent to the rover over a communication link, as well as from knowledge of the approximate position of the rover.
1. A process for accurate location determination in an assisted GPS positioning system requiring at a minimum the transmission of ephemeris, satellite clock correction data, and approximate position information, or equivalent data, from the server or other information source to the rover, the process comprising:
(D1) where in said system of equations the position of each satellite is a vector-valued function fk(T) of said time T, where fk is determined from satellite ephemeris data or its equivalent, sent to the rover over a communication link, as well as from knowledge of the approximate position of the rover.
2. The process as set forth in claim 1, in which a communication link is used for communication between the server or other information source and the rover, and said communication link is any one, or a combination of communication means including, cellular telephone networks, wired or wireless internet access, or telephone land lines.
3. The process as set forth in claim 1, further including the determination of accurate but ambiguous pseudorange differences by using the knowledge that the epochs of the GPS C/A pseudorandom code are transmitted at integer millisecond values of space vehicle (SV) time, which are corrected to GPS time using said satellite clock correction data.
4. The process as set forth in claim 1, further including the resolution of ambiguity in the said pseudorange differences by using said knowledge of the approximate position of the rover, provided to the rover by the server or other source.
5. The process as set forth in claim 4, wherein a least-squares interactive algorithm used for solving the solution of said system of equations starts with an initial solution estimate x=[X Y Z T]T, and each subsequent pass through the algorithm starts with the previous solution estimate, said algorithm consisting of the following steps, the sequence of steps being repeated until convergence of the solution is obtained:
(A5) Use the ephemeris data, or its equivalent, received from the server to calculate the satellite positions (xk, yk, zk) at time T;
H = [ ∂ ρ 12 ∂ X ∂ ρ 12 ∂ Y ∂ ρ 12 ∂ Z ∂ ρ 12 ∂ T ∂ ρ 13 ∂ X ∂ ρ 13 ∂ Y ∂ ρ 13 ∂ Z ∂ ρ 13 ∂ T ⋮ ⋮ ⋮ ⋮ ∂ ρ 1 n ∂ X ∂ ρ 1 n ∂ Y ∂ ρ 1 n ∂ Z ∂ ρ 1 n ∂ T ] = [ u _ 2 - u _ 1 u _ 1 • v _ 1 - u _ 2 • v _ 2 u _ 3 - u _ 1 u _ 1 • v _ 1 - u _ 3 • v _ 3 ⋮ ⋮ u _ n - u _ 1 u _ 1 • v _ 1 - u _ n • v _ n ]
(G5) Using the rk previously obtained in Step D5, calculate the vector dr=[r1-r2 r1-r3 . . . r1-rn]T of range differences that would result using the current solution estimate x;
(H5) Calculate the vector Δ dρ= dρ− dr of change between the measured pseudorange differences provided by the receiver and the calculated range differences from Step G5, where dρ=[ρ12 ρ13 ρ1n]T the ρ1k are calculated as
ρ1k =c(n k-n 1)+c(εk-ε1)+c(τk-τ1),
τk is the measurement of received code phase for the kth satellite, εk is the satellite clock correction for the kth satellite as received from the server, and the unknown integers nk-n1 are resolved according to the calculation
n k - n 1 = c int [ r 1 - r k c - ( X k - X 1 ) - ( ɛ k - ɛ 1 ) ] ;
6. The process as set forth in claim 5, in which the steps of said iterative algorithm are the same, except that the quantities are suitably modified for the purpose of 2D positioning.
13. Use the pseudorange to each satellite (Step 11) and the satellite positions (Step 12) to compute the position of the user=s receiver and very accurate time.
In a standard GPS receiver the above sequence of operations can be quite time consuming; In particular, the search for satellites in Step 3 may require several minutes or even more, depending on a number of conditions. At the start of the search the Doppler shift of the signal from each satellite may not be accurately known, so time must be taken to explore a window of frequencies in order to find a signal. This window must be wide enough to encompass the frequency uncertainty of the signal. Before the first satellite is acquired, a major source of this uncertainty is the frequency uncertainty in the reference oscillator of the user=s receiver, which might be on the order of 1 part per million, or ±1575 Hz at the GPS L1 carrier frequency of 1575.42 MHz. A second source of frequency uncertainty occurs when the receiver does not have recent (no more than 2 hours old) ephemeris data, or does not have sufficiently accurate approximate a-priori knowledge of its position to know what signal Doppler shift to expect (the Doppler shift can change by approximately 1 Hz/km worst case).
In addition to the possibility of a lengthy search to acquire the satellites, the demodulation of the navigation data stream from each satellite to obtain ephemeris and time information in Step 8 also can take a considerable length of time. Ephemeris data from each satellite is used to determine the position of that satellite at the time of signal transmission obtained in Step 10. The ephemeris data is basically a formula, or more accurately, a parameterized algorithm, into which the transmission time can be substituted in order to calculate the satellite position at that time. In standard (non-assisted) GPS positioning, the ephemeris data is obtained from the 50 bit/second GPS navigation data received directly from the satellite by the user. The navigation data stream consists of sequentially transmitted 1500-bit frames of duration 30 seconds (1500 bits÷50 bits/sec), each of which contains five 300-bit subframes. The first three subframes consist of time and ephemeris data. The ephemeris data is repeated at the frame repetition rate, except for occasional updates. Thus, the reception of a complete sample of ephemeris data from a single satellite may take as long as 30 seconds, depending on when the user=s receiver begins to look for such data within a received frame.
A more serious problem in extracting the time and ephemeris data from the navigation message occurs when the GPS signal is too weak to permit reliable demodulation of the navigation message data bits. This problem manifests itself at a C/No of approximately 25 dB-Hz. In urban canyons and inside buildings the C/No can easily fall below this value, rendering the user=s standard GPS receiver inoperative because it can no longer obtain error-free ephemeris and time data needed for positioning.
For the reasons described above the standard method of GPS positioning with an autonomous (unassisted) receiver is not suitable in applications where rapid and reliable position determination is needed, particularly in weak signal environments.
The above limitations of standard positioning methods can be overcome by using assisted positioning. In assisted positioning, a base station (the server) sends information to the user=s receiver (the rover). Although this information may vary somewhat for different assisted systems, typical information is as follows:
1. The server can send a very accurate frequency reference to the rover, which is used to calibrate the reference oscillator in the rover receiver. The carrier frequency of the server-rover communication link is often used for this purpose. Once the frequency uncertainty of the rover=s reference oscillator has been removed, the time required for the acquisition of the first satellite by the rover receiver is considerably reduced because the width of the search frequency window can be made much smaller.
2. In many cases the server can determine the approximate location of the rover relative to the server. For example, if the rover receiver is embedded in a cellular telephone (a common practice in an emergency location system), the location of the cellular tower that receives the strongest cell phone signal will serve this purpose. Knowledge of the approximate location of the rover, in conjunction with ephemeris data collected by the server, further narrows down the frequency uncertainty in searching for satellite signals. Additionally, if the server can determine the rover=s approximate location to within approximately 100-200 km, the rover does not need to extract the highly accurate time information from the satellites=navigation data message (Step 10 above), which normally would be necessary in order to determine pseudorange.
3. Ephemeris and satellite clock correction data from each satellite can be collected by the server and transmitted to the rover. This is very advantageous, because the rover does not have to spend precious time (at least 30 seconds) to receive the data directly from the satellites. Because the server is located in clear view of the satellites, the satellite signals will be strong enough at that location to reliably demodulate the ephemeris data. The server can then easily transmit the data to the rover at a data rate much higher than the GPS 50 bps rate, and with a power high enough to penetrate into areas where the rover would otherwise not be able to receive the ephemeris data directly from the satellites.
Fortunately, it is possible for the rover to know an ambiguous form of signal transmission time from a GPS satellite without demodulating the navigation data message. This is possible because the epochs of the GPS C/A code are transmitted by each satellite precisely at each whole millisecond of satellite vehicle (SV) time, which differs from GPS time by an error term contained in the navigation message available at the server and transmitted to the rover (GPS time is a precise time to which all satellites are synchronized). The rover=s receiver can identify the code epochs by correlating the received signal with a replica of the C/A code. This can be done reliably even with weak signals, because correlating over long periods of time can provide large amounts of processing gain. However, the transmission times of the epochs have a 1 millisecond ambiguity, i.e., it is only known that a specific epoch was transmitted at a SV time equal to an integer number of milliseconds, but the value of the integer is unknown. Thus, the pseudoranges to each satellite are subject to the same ambiguity, which in space is approximately 300 km. When these ambiguous times are used in the positioning equations, the solution of the equations results in a three-dimensional lattice, or grid, of possible rover positions with a spacing on the order of 300 km (the actual spacing will deviate from this value due to satellite-receiver geometry). However, if the rover=s approximate position is known within approximately 100-200 km, the position ambiguity can be resolved. However, the 1-millisecond time ambiguity remains unresolved.
ρ=f(X, Y, Z, B), (1)
where ρ=[ρ1 ρ2 . . . ρn]T is the vector of pseudorange measurements from the n observed satellites, (X,Y,Z) is the receiver position, B is the receiver clock bias, and f is a known function. The goal of positioning is to determine the navigation solution x=[X Y Z B]T, given the measurements ρ. The function f is defined by the following system of equations:
ρ1=√{square root over ((x 1-X)2+(y 1-Y)2+(z-Z)2)}+B
ρ2=√{square root over ((x 2-X)2+(y 2-Y)2+(z 2-Z)2)}+B
ρn=√{square root over ((x n-X)2+(y n-Y)2+(z-Z)2)}+b (2)
where the position of the kth satellite at its time of transmission is (xk, yk, zk) and the pseudorange measurement for that satellite is ρk. It is assumed that B is in seconds and the satellite and server positions are expressed in meters using a local East-North-Up (ENU) coordinate system in which the East-North plane is tangent to the Earth's surface, so that Z and zk respectively denote the altitudes of the rover and the kto satellite above a datum representing the Earth's surface. However, other coordinate systems can be used.
ρ12=√{square root over ((x 1-X)2+(y 1-Y)2+(z 1-Z)2)}−√{square root over ((x 2-X)2+(y 2-Y)2+(z 2-Z)2)}
ρ13=√{square root over ((x 1-X)2+(y 1-Y)2+(z 1-Z)2)}−√{square root over ((x 3-X)2+(y 3-Y)2+(z 3-Z)2)}
ρ1n=√{square root over ((x 1-X)2+(y 1-Y)2+(z 1-Z)2)}−√{square root over ((x 1-X)2+(y n-Y)2+(z n-Z)2)} (3)
where ρ1k=ρ1−ρk. In this system the satellite positions (xk,yk,zk) are represented as functions of the a new time variable T, which is defined as the time of simultaneously making range measurements to each of the n satellites:
(x k ,y k ,z k)=f k(T) k=1, 2, . . . , n (4)
where the function fk is evaluated by inserting T minus the estimated signal propagation time into the ephemeris equation for the kth satellite (this will be explained in more detail later). The system (3), where the satellite positions are the functions of T given by (4), now has the more compact form
dρ=g(X,Y,Z,T)=g( x ) (5)
ρk =c(T 0 −t k)=c(T 0 −n k−εk−τk) (7)
In the preferred embodiment of the present invention the measurements of the code phases τk are used to form the pseudorange differences ρ1k as follows: ρ 1 k = ρ 1 - ρ k = c ( T 0 - t 1 ) - c ( T 0 - t k ) = c ( t k - t 1 ) = c ( n k + ɛ k + τ k ) - c ( n 1 + ɛ 1 + τ 1 ) = c ( n k - n 1 ) + c ( ɛ k - ɛ 1 ) + c ( τ k - τ 1 ) ( 8 )
The pseudorange differences in (8) suffer an ambiguity because the integers nk-n1 are not initially known. However, the ambiguity can be resolved if the position of the rover is known to within 100-200 kilometers and the initial estimate of the time of measuring the code phases τk is accurate to within 10 seconds or so. Ambiguity resolution is achieved by first estimating the ranges rk from the rover to the satellites from knowledge of the approximate rover position and the positions of the satellites at the approximate time (within 10 seconds or so) that the pseudorange measurements are made. The estimated range differences r1-rk are then substituted into (8) in place of the actual pseudorange difference measurements ρ1k, and the integers nk-n1 are computed as n k - n 1 = c int [ r 1 - r k c - ( τ k - τ 1 ) - ( ɛ k - ɛ 1 ) ] , ( 9 )
The solution of the navigation equations is a solution for the four variables X, Y, Z, and T. The solution for the time T of range difference measurements is usually expressed in seconds, and the solution (X,Y,Z) for rover position is typically expressed in meters using a local ENU (East-North-Up) coordinate system in which the East-North plane is tangent to the Earth's surface.
∥ dρ−g( x )∥2. (10)
where H = [ ∂ ρ 12 ∂ X ∂ ρ 12 ∂ Y ∂ ρ 12 ∂ Z ∂ ρ 12 ∂ T ∂ ρ 13 ∂ X ∂ ρ 13 ∂ Y ∂ ρ 13 ∂ Z ∂ ρ 13 ∂ T ⋮ ⋮ ⋮ ⋮ ∂ ρ 1 n ∂ X ∂ ρ 1 n ∂ Y ∂ ρ 1 n ∂ Z ∂ ρ 1 n ∂ T ] = [ u _ 2 - u _ 1 u _ 1 • v _ 1 - u _ 2 • v _ 2 u _ 3 - u _ 1 u _ 1 • v _ 1 - u _ 3 • v _ 3 ⋮ ⋮ u _ n - u _ 1 u _ 1 • v _ 1 - u _ n • v _ n ] ( 12 )
In (12) the vectors u _ k = [ ∂ r k ∂ X ∂ r k ∂ Y ∂ r k ∂ Z ]
Referring now to FIGS. 1 and 2, the least-squares solution for x (not Δ x) is found by the following iterative procedure. The looping index is j. The first pass through the loop starts with the an initial solution estimate x=[X Y Z T] obtained from knowledge of approximate rover position and time, and refines this solution to provide a better solution estimate. Subsequent passes start with the most current estimate and further refine it. In the steps below the index k runs from 1 to the number n of observed satellites:
E. Calculate the rover-to-satellite unit vectors u _ k = [ ∂ r k ∂ X ∂ r k ∂ Y ∂ r k ∂ Z ]
G. Using the rk previously obtained in Step D, calculate the vector dr=[r1-r2 r1-r3, . . . r1-rn]T of range differences that would result using the current solution estimate x.
To determine GDOP for the present invention, it is assumed that the quantities cτk have independent, zero mean, unit variance noise components δk, where τk is expressed in milliseconds and c is the speed of light in meters per millisecond. It is seen from (7) that δk is also the noise component of ρk, so that from (8) the noise component of the pseudorange difference measurement ρ1k=ρ1−ρk is therefore δ1-δk. Thus, the noise component of the vector dρ=[ρ12 ρ13 . . . ρ1n]T of pseudorange difference measurements is the vector δ dρ given by δ _ d ρ _ = [ δ 1 - δ 2 δ 1 - δ 3 ⋮ δ 1 - δ n ] = [ 1 - 1 0 0 ⋯ 0 1 0 - 1 0 ⋯ 0 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 1 0 0 0 ⋯ - 1 ] ︸ D [ δ 1 δ 2 ⋮ δ n ] ︸ δ _ ρ _ = D δ _ ρ _ ( 14 )
δ x =(H T H)−1 H T δ dρ . (15)
The covariance matrix C of δ x is C = E { δ _ x _ δ _ x _ T } = E { ( H T H ) - 1 H T δ _ d ρ _ δ _ d ρ _ T H ( H T H ) - T } = E { ( H T H ) - 1 H T D δ _ ρ _ δ _ ρ _ T D T H ( H T H ) - T } = ( H T H ) - 1 H T D E { δ _ d ρ _ δ _ d ρ _ T } ︷ I n × n D T H ( H T H ) - T = ( H T H ) - 1 H T D D T H ( H T H ) - T ( 16 )
where E{ } denotes expectation, and we have used the fact that E { δ _ d ρ _ δ _ d ρ _ T } = I n × n ,
PDOP=√{square root over (C11+C22+C33)}
HDOP=√{square root over (C11+C22)}
TDOP=√{square root over (C44)} (17)
RMS 3D RMS Error in Time Number of Trials
Position T of Pseudorange in PDOP
PDOP Category Error (m) Measurement (msec) Category
PDOP < 5 3.8 2.7 6332
5 ≦ PDOP < 10 7.1 5.2 6485
10 ≦ PDOP < 20 14.1 10.5 3404
20 ≦ PDOP < 40 27.7 22.1 1741
(D1) where in said system of equations the position of each satellite is a vector-valued function fk(T) of said time T. where fk is determined from satellite ephemeris data or its equivalent, sent to the rover over a communication link, as well as from knowledge of the approximate position of the rover.
(E5) Calculate the rover-to-satellite unit vectors u _ k = [ ∂ r k ∂ X ∂ r k ∂ Y ∂ r k ∂ Z ]
(F5) Form the matrix H defined by H = [ ∂ ρ 12 ∂ X ∂ ρ 12 ∂ Y ∂ ρ 12 ∂ Z ∂ ρ 12 ∂ T ∂ ρ 13 ∂ X ∂ ρ 13 ∂ Y ∂ ρ 13 ∂ Z ∂ ρ 13 ∂ T ⋮ ⋮ ⋮ ⋮ ∂ ρ 1 n ∂ X ∂ ρ 1 n ∂ Y ∂ ρ 1 n ∂ Z ∂ ρ 1 n ∂ T ] = [ u _ 2 - u _ 1 u _ 1 • v _ 1 - u _ 2 • v _ 2 u _ 3 - u _ 1 u _ 1 • v _ 1 - u _ 3 • v _ 3 ⋮ ⋮ u _ n - u _ 1 u _ 1 • v _ 1 - u _ n • v _ n ]
(G5) Using the rk previously obtained in Step D5, calculate the vector dr=[r1-r2 r1-r3 . . . r1-rn]T of range differences that would result using the current solution estimate x.
τk is the measurement of received code phase for the kth satellite, εk is the satellite clock correction for the kth satellite as received from the server, and the unknown integers nk-n1 are resolved according to the calculation n k - n 1 = c int [ r 1 - r k c - ( X k - X 1 ) - ( ɛ k - ɛ 1 ) ] .
(15) Calculate the correction Δ x=(HTH)−1HΔ dρ to be applied to the current solution estimate.
US5535278 * 2 mei 1994 9 juli 1996 Magnavox Electronic Systems Company Global positioning system (GPS) receiver for recovery and tracking of signals modulated with P-code
US7679554 * 3 juli 2008 16 maart 2010 Rockwell Collins, Inc. Communications link time transfer to improve navigation system accuracy
US7706976 * 26 juli 2006 27 april 2010 Trimble Navigation, Ltd. Position based velocity estimator
US7739032 * 21 maart 2006 15 juni 2010 Broadcom Corporation Method and apparatus for generating and using a regional-terrain model
US7893869 * 19 juli 2007 22 feb 2011 Qualcomm Incorporated Global navigation satellite system
US7920072 21 nov 2008 5 april 2011 Microsoft Corporation Virtual earth rooftop overlay and bounding
US8843309 * 7 okt 2005 23 sept 2014 Microsoft Corporation Virtual earth mapping
US8850011 7 okt 2005 30 sept 2014 Microsoft Corporation Obtaining and displaying virtual earth images
US9262487 * 4 nov 2013 16 feb 2016 Samsung Electronics Co., Ltd Method and apparatus for guided acquisition and tracking in global navigation satellite system receivers
US9383206 26 feb 2014 5 juli 2016 Microsoft Technology Licensing, Llc Obtaining and displaying virtual earth images
US9541650 * 14 dec 2012 10 jan 2017 Institute For Information Industry Satellite positioning method, satellite pseudorange calculation apparatus and satellite pseudorange calculation method
US9562975 19 maart 2012 7 feb 2017 Trimble Inc. GNSS signal processing with delta phase for incorrect starting position
US20060238379 * 7 okt 2005 26 okt 2006 Microsoft Corporation Obtaining and displaying virtual earth images
US20060238380 * 19 jan 2006 26 okt 2006 Microsoft Corporation Maintaining user privacy in a virtual earth environment
US20060241860 * 7 okt 2005 26 okt 2006 Microsoft Corporation Virtual earth mapping
US20080183384 * 19 juli 2007 31 juli 2008 Peter Gaal Global Navigation Satellite System
US20090066576 * 21 maart 2006 12 maart 2009 Global Locate, Inc. Method and apparatus for generating and using a regional-terrain model
US20090073191 * 21 nov 2008 19 maart 2009 Microsoft Corporation Virtual earth rooftop overlay and bounding
US20140152500 * 14 dec 2012 5 juni 2014 Institute For Information Industry Satellite positioning method, satellite pesudorange calculation apparatus and satellite pesudorange calculation method
US20150032371 * 4 nov 2013 29 jan 2015 Samsung Electronics Co., Ltd. Method and apparatus for guided acquisition and tracking in global navigation satellite system receivers
EP2689267A1 * 19 maart 2012 29 jan 2014 Trimble Navigation Limited Gnss signal processing with delta phase
EP2689267A4 * 19 maart 2012 18 feb 2015 Trimble Navigation Ltd Gnss signal processing with delta phase
EP2703839A1 * 6 aug 2013 5 maart 2014 O2 Micro, Inc. Method and apparatus for synchronizing navigation data
WO2012151006A1 19 maart 2012 8 nov 2012 Trimble Navigation Limited Gnss signal processing with delta phase
Classificatie in de VS 342/357.25, 342/357.64
Internationale classificatie G01S19/42, G01S19/25, G01S5/14
Coöperatieve classificatie G01S19/42, G01S19/258
Europese classificatie G01S19/25D, G01S19/42
12 april 2005 AS Assignment
Free format text: CHANGE OF ASSIGNEE S ADDRESS;ASSIGNOR:MAGELLAN SYSTEMS JAPAN INC.;REEL/FRAME:020508/0222
20 okt 2011 FPAY Fee payment
21 okt 2015 FPAY Fee payment