Hybrid GNSS and TDOA wireless location system

• US 8,199,050 B2
• Filed: 09/22/2011
• Issued: 06/12/2012
• Est. Priority Date: 12/13/2007
• Status: Active Grant

• Current Assignee: Skyhook Holding, Inc. (Liberty Broadband Corp.)
• Original Assignee: TruePosition Incorporated
• Inventors: Boyer, Pete A., Lefever, Ronald, Mia, Rashidus S., Anderson, Robert J.
• Primary Examiner(s): Batista, Marcos
• Application Number:
  US13/240,964
• Publication Number:
  US 20120015670A1
• Time in Patent Office: 264 Days
• Field of Search: 455/456.1, 370/338
• US Class Current: 342/357.29
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type

Abstract

A method and apparatus for position determination is provided using measurements from both Global Positioning System (GPS) receivers and terrestrial-based Uplink Time Difference of Arrival (UTDOA) receivers. The method involves the transformation of downlink satellite measurements into equivalent UTDOA measurements by computing comparable cross-correlation coefficients and time differences of arrival with respect to a UTDOA reference station. The method includes a weighting operation whereby the relative weights of the UTDOA measurements and the relative weights of the GPS measurements are adjusted based on a theoretical scaling followed by empirical adjustments. The method further involves the efficient computation and combining of metrics that are used to minimize the weighted error between candidate location solutions and the UTDOA and GPS measurements.

Claims

1. A method for use in locating a mobile device, wherein the mobile device is configured to obtain pseudorange measurements based on signals received from one or more satellites, wherein said one or more satellites are satellites of at least one of a Global Navigation Satellite System (GNSS) or Global Positioning System (GPS), and to compute GPS time difference of arrival (G-TDOA) values based on the GPS pseudorange measurements, said G-TDOA values representing baselines between the mobile device and the GPS/GNSS satellites, comprising:

obtaining an uplink time difference of arrival (U-TDOA) measurement representing a first baseline between first and second terrestrial receivers;

providing hybrid GPS/U-TDOA baselines;

computing weightings for the hybrid GPS/U-TDOA baselines; and

estimating the location of the mobile device using the hybrid GPS/U-TDOA baselines and the weightings.

2. A method as recited in claim 1, wherein the step of computing weightings comprises an iterative downweighting method including determining a hybrid position estimate using a current baseline weighting, and then downweighting the U-TDOA baselines and G-TDOA baselines, until either a first or second prescribed stopping condition is met.

3. A method as recited in claim 2, wherein the first stopping condition is deemed to be met when the number of iterations exceeds a predetermined maximum.

4. A method as recited in claim 3, wherein a last location solution is used as the estimate of the location of the mobile device when the first stopping condition is met.

5. A method as recited in claim 2, further comprising determining a geometric dilution of precision (GDOP) value, wherein the second stopping condition is deemed to be met when the GDOP exceeds a predetermined threshold.

6. A method as recited in claim 5, wherein a location solution from a previous iteration is used as the estimate of the location of the mobile device when the second stopping condition is met.

7. A method as recited in claim 1, wherein the method is carried out in a hybrid wireless location system comprising a U-TDOA wireless location network and an assisted-GPS (A-GPS) network.

8. A method as recited in claim 7, wherein radio data streams from at least one satellite of the Global Positioning System or Global Navigation Satellite System are received by the mobile device, a reference receiver and at least one cooperating receiver in the U-TDOA location subsystem, said data streams including Almanac and Ephemeris Data in a pre-established format, wherein the mobile device is enabled to potentially self locate with an estimate of the geodetic or ellipsoidal altitude.

9. A method as recited in claim 8, wherein the U-TDOA wireless location network comprises a network of geographically distributed receivers and a position determining entity (PDE) configured to use uplink transmissions from the mobile device and a time base provided by radio transmissions from at least one satellite of the Global Positioning System or Global Navigation Satellite System to detect the time difference of arrival between the reference receiver and at least two cooperating receivers, and to calculate a position estimate using a multi-lateration algorithm.

10. A method as recited in claim 1, wherein the step of computing G-TDOA values comprises employing a process for transforming GPS pseudoranges to U-TDOA values, said process comprising:

comparing GPS pseudoranges with geometric distances to a reference station of a U-TDOA wireless location network and computing a time difference of arrival (TDOA) value for the satellite signal received at the mobile device and the reference station, respectively, wherein the positions of the satellite and the reference station are known, and wherein the computed TDOA value represents the G-TDOA value.

11. A method as recited in claim 10, wherein said process for transforming GPS pseudoranges to u-TDOA values further comprises identifying the reference station and computing TDOA values for each satellite, including, for each satellite:

(i) finding the position of the satellite and making corrections to the pseudoranges so that they reflect geometric distances;

(ii) computing the propagation delay between the satellite and the reference station;

(iii) computing the measured propagation time between the satellite and the mobile device, the computed time including a receiver clock error bias;

(iv) computing the G-TDOA value as the difference between the propagation time from the satellite to the mobile device and the propagation delay from the satellite to the reference station;

(v) computing a correlation coefficient for a cross-correlation between a received pseudorandom noise (PRN) signal at the mobile device and a hypothetical reception of the PRN at the reference station;

(vi) determining that the signal-to-noise ratio (SNR) at the reference station is large relative to the SNR at the mobile device;

(vii) using the SNR to obtain a measure of quality of the pseudorange measurement; and

(viii) repeating the procedure for each satellite whose signals are received by the mobile device.

12. A method as recited in claim 11, further comprising obtaining a measure of a correlation coefficient for the G-TDOA value using the SNR at the mobile device.

13. A method as recited in claim 12, wherein the correlation coefficient for an i-th pseudorange measurement (ρ

₁) associated with a G-TDOA value generally satisfies the following relationship with the SNR at the mobile device;

ρ

_i=1/(1+1/SNR_i)^1/2.

14. A method as recited in claim 1, further comprising a process for weighting pseudorange measurements, said process comprising weighting pseudorange measurements based on a signal-to-noise ratio (SNR) reported by the GPS receiver used to obtain the pseudorange measurements.

15. A method as recited in claim 14, wherein said process for weighting pseudorange measurements comprises the use of an iterative downweighting process for scaling GPS and U-TDOA weights based on prescribed factors, including measurement error distribution for U-TDOA and GPS, the number of GPS measurements available, and the number of U-TDOA measurements available.

16. A method as recited in claim 14, wherein said process for weighting pseudorange measurements comprises computing, for each GPS baseline, an initial weighting based on a theoretical time difference of arrival (TDOA) RMS error.

17. A method as recited in claim 16, wherein the theoretical Additive White Gaussian Noise (AWGN) TDOA RMS error (aTDOA_rms—

_i) is based on the air interface and computed for each GPS baseline using the GPS SNR and air interface parameters for the U-TDOA measurements.

18. A method as recited in claim 16, wherein the TDOA RMS error is increased by multipath effects (σ

<sub>M—

i</sub>) and computed for each GPS baseline using the GPS SNR and air interface parameters for the U-TDOA measurements.

19. A method as recited in claim 17, further comprising computation of a weight (W_ai) as an inverse function of the RMS error squared,

20. A method as recited in claim 17, wherein said process for weighting pseudorange measurements further comprises scaling the theoretical weighting measurement data.

21. A method as recited in claim 14, wherein said process for weighting pseudorange measurements further comprises employing a database of GPS baseline measurement errors and a database of U-TDOA measurement errors compiled from past GPS and U-TDOA location measurements.

22. A method as recited in claim 21, wherein said process for weighting pseudorange measurements further comprises employing a coarse scaling factor (S_c), wherein said coarse scaling factor, S_c, represents a ratio of RMS error averaged over said GPS baseline measurement errors and said U-TDOA measurement errors.

23. A method as recited in claim 22, wherein said coarse scaling factor, S_c, is defined as

24. A method as recited in claim 23, wherein said process for weighting pseudorange measurements further comprises assigning, as an initial weighting for each GPS baseline, a product of the coarse scaling factor and the weight from the theoretical GPS TDOA.

25. A method as recited in claim 24, wherein said product assigned as an initial weighting is defined as

26. A method as recited in claim 21, wherein said process for weighting pseudorange measurements further comprises employing a fine scale factor (S_f) computed using hybrid GPS/U-TDOA measurements.

27. A method as recited in claim 26, wherein said fine scale factor is employed to derive a final measurement weight as follows:

W_Gi=SW_ai

where S=S_fS_c.

28. A method as recited in claim 1, further comprising employing a hybrid weighted least squares algorithm, said algorithm providing an analytical solution for biases in the GPS and U-TDOA contributions, including performing transformation of GPS pseudorange contributions and combining the transformed and weighted GPS contributions with computed GPS time difference of arrival (TDOA) values obtained from the pseudorange measurements.

29. A method as recited in claim 28, wherein said hybrid weighted least squares algorithm further comprises performing a three-dimensional search for GPS baselines.

30. A method as recited in claim 29, wherein said hybrid weighted least squares algorithm further comprises the computation of TDOA values assuming test locations of the mobile device and searching until a prescribed stopping condition is met, including computing chi-square metrics and summing said metrics for each test location.

31. A method as recited in claim 30, wherein said hybrid weighted least squares algorithm further comprises computation of a combined chi-square metric including separate bias values for GPS and U-TDOA.

32. A method as recited in claim 31, wherein said hybrid weighted least squares algorithm further comprises determining a minimum chi square metric and corresponding test location, wherein the stopping condition is deemed to be met when the minimum is found at a predetermined highest resolution.

33. A method as recited in claim 30, wherein a U-TDOA search is performed in three dimensions that includes the transformed GPS/U-TDOA baselines, said U-TDOA search comprising first searching for a minimum chi square metric over all GPS baselines in two dimensions (x, y) and then employing a z-search algorithm to search in a third dimension (z).

34. A method as recited in claim 30, wherein a prescribed stopping condition includes a continuation of the search at the current resolution when the minimum location solution falls on the edge of the search space.

35. A method as recited in claim 34, wherein a prescribed stopping condition includes a continuation of the search at the current map resolution when the minimum location solution falls on the edge of the search space.

36. A method as recited in claim 33, wherein said z-search algorithm comprises the use of an initial estimation of the mobile device'"'"'s altitude, a coarse search, a fine search, and steering criteria.

37. A method as recited in claim 36, wherein said z-search algorithm further comprises finding an initial search position in the z-dimension with respect to a U-TDOA coordinate system;

wherein said coarse search comprises computing and using an initial estimate, Zo, representing the position of the mobile device at a typical height above ground level;

wherein said steering criteria includes selecting the coarse search for resolutions below a predetermined resolution threshold, and performing the fine search once the resolution threshold is reached.

38. A wireless location system for use in locating a mobile device configured to obtain pseudorange measurements based on signals received from one or more satellites, wherein said one or more satellites are satellites of at least one of a Global Navigation Satellite System (GNSS) or Global Positioning System (GPS), and to compute GPS time difference of arrival (G-TDOA) values based on the GPS pseudorange measurements, said G-TDOA values representing baselines between the mobile device and the GPS/GNSS satellites, comprising:

means for communicating with the mobile device and obtaining from said mobile device pseudorange measurements;

means for computing G-TDOA values based on the GPS pseudorange measurements, said G-TDOA values representing baselines between the mobile device and the GPS/GNSS satellites;

means for obtaining an uplink time difference of arrival (U-TDOA) measurement representing a first baseline between first and second terrestrial receivers;

means for providing hybrid GPS/U-TDOA baselines;

means for computing weightings for the hybrid GPS/U-TDOA baselines; and

means for estimating the location of the mobile device using the hybrid GPS/U-TDOA baselines and the weightings.

39. A system as recited in claim 38, wherein the means for computing weightings comprises means for carrying out an iterative downweighting including determining a hybrid position estimate using a current baseline weighting, and then downweighting the U-TDOA baselines and G-TDOA baselines, until either a first or second prescribed stopping condition is met.

40. A system as recited in claim 39, wherein the first stopping condition is deemed to be met when the number of iterations exceeds a predetermined maximum.

41. A system as recited in claim 40, wherein a last location solution is used as the estimate of the location of the mobile device when the first stopping condition is met.

42. A system as recited in claim 39, further comprising means for determining a geometric dilution of precision (GDOP) value, wherein the second stopping condition is deemed to be met when the GDOP exceeds a predetermined threshold.

43. A system as recited in claim 42, wherein a location solution from a previous iteration is used as the estimate of the location of the mobile device when the second stopping condition is met.

44. A system as recited in claim 38, wherein the system is a hybrid wireless location system comprising a U-TDOA wireless location network and an assisted-GPS (A-GPS) network.

45. A system as recited in claim 44, wherein radio data streams from at least one satellite of the Global Positioning System or Global Navigation Satellite System are received by the mobile device, a reference receiver and at least one cooperating receiver in the U-TDOA location subsystem, said data streams including Almanac and Ephemeris Data in a pre-established format, wherein the mobile device is enabled to potentially self locate with an estimate of the geodetic or ellipsoidal altitude.

46. A system as recited in claim 45, wherein the U-TDOA wireless location network comprises a network of geographically distributed receivers and a position determining entity (PDE) configured to use uplink transmissions from the mobile device and a time base provided by radio transmissions from at least one satellite of the Global Positioning System or Global Navigation Satellite System to detect the time difference of arrival between the reference receiver and at least two cooperating receivers, and to calculate a position estimate using a multi-lateration algorithm.

47. A system as recited in claim 38, wherein the means for computing G-TDOA values employs a process for transforming GPS pseudoranges to U-TDOA values, said process comprising:

comparing GPS pseudoranges with geometric distances to a reference station of a U-TDOA wireless location network and computing a time difference of arrival (TDOA) value for the satellite signal received at the mobile device and the reference station, respectively, wherein the positions of the satellite and the reference station are known, and wherein the computed TDOA value represents the G-TDOA value.

48. A system as recited in claim 47, wherein said process for transforming GPS pseudoranges to U-TDOA values further comprises identifying the reference station and computing TDOA values for each satellite, including, for each satellite:

(i) finding the position of the satellite and making corrections to the pseudoranges so that they reflect geometric distances;

(ii) computing the propagation delay between the satellite and the reference station;

(iii) computing the measured propagation time between the satellite and the mobile device, the computed time including a receiver clock error bias;

(iv) computing the G-TDOA value as the difference between the propagation time from the satellite to the mobile device and the propagation delay from the satellite to the reference station;

(v) computing a correlation coefficient for a cross-correlation between a received pseudorandom noise (PRN) signal at the mobile device and a hypothetical reception of the PRN at the reference station;

(vii) determining that the signal-to-noise ratio (SNR) at the reference station is large relative to the SNR at the mobile device;

(vii) using the SNR to obtain a measure of quality of the pseudorange measurement; and

(viii) repeating the procedure for each satellite whose signals are received by the mobile device.

49. A system as recited in claim 48, further comprising means for obtaining a measure of a correlation coefficient for the G-TDOA value using the SNR at the mobile device.

50. A system as recited in claim 49, wherein the correlation coefficient for an i-th pseudorange measurement (ρ

_i) associated with a G-TDOA value generally satisfies the following relationship with the SNR at the mobile device;

ρ

_i=1/(1+1/SNR_i)^1/2.

51. A system as recited in claim 38, further comprising means for performing a process for weighting pseudorange measurements, said process comprising weighting pseudorange measurements based on a signal-to-noise ratio (SNR) reported by the GPS receiver used to obtain the pseudorange measurements.

52. A system as recited in claim 51, wherein said process for weighting pseudorange measurements comprises the use of an iterative downweighting process for scaling GPS and U-TDOA weights based on prescribed factors, including measurement error distribution for U-TDOA and GPS, the number of GPS measurements available, and the number of U-TDOA measurements available.

53. A system as recited in claim 51, wherein said process for weighting pseudorange measurements comprises computing, for each GPS baseline, an initial weighting based on a theoretical time difference of arrival (TDOA) RMS error.

54. A system as recited in claim 53, wherein the theoretical Additive White Gaussian Noise (AWGN) TDOA RMS error (aTDOA_rms—

_i) is based on the air interface and computed for each GPS baseline using the GPS SNR and air interface parameters for the U-TDOA measurements.

55. A system as recited in claim 53, wherein the TDOA RMS error is increased by multipath effects (σ

<sub>M—

i</sub>) and computed for each GPS baseline using the GPS SNR and air interface parameters for the U-TDOA measurements.

56. A system as recited in claim 54, further comprising means for performing computation of a weight (W_ai) as an inverse function of the RMS error squared,

57. A system as recited in claim 54, wherein said process for weighting pseudorange measurements further comprises means for scaling the theoretical weighting measurement data.

58. A system as recited in claim 51, wherein said process for weighting pseudorange measurements employs a database of GPS baseline measurement errors and a database of U-TDOA measurement errors compiled from past GPS and U-TDOA location measurements.

59. A system as recited in claim 58, wherein said process for weighting pseudorange measurements employs a coarse scaling factor (S_c), wherein said coarse scaling factor, S_c, represents a ratio of RMS error averaged over said GPS baseline measurement errors and said U-TDOA measurement errors.

60. A system as recited in claim 59, wherein said coarse scaling factor, S_c, is defined as

61. A system as recited in claim 60, wherein said process for weighting pseudorange measurements assigns, as an initial weighting for each GPS baseline, a product of the coarse scaling factor and the weight from the theoretical GPS TDOA.

62. A system as recited in claim 61, wherein said product assigned as an initial weighting is defined as

63. A system as recited in claim 58, wherein said process for weighting pseudorange measurements employs a fine scale factor (S_f) computed using hybrid GPS/U-TDOA measurements.

64. A system as recited in claim 63, wherein said fine scale factor is employed to derive a final measurement weight as follows:

W_Gi=SW_ai

where S=S_fS_c.

65. A system as recited in claim 38, further comprising means for employing a hybrid weighted least squares algorithm, said algorithm providing an analytical solution for biases in the GPS and U-TDOA contributions, including performing transformation of GPS pseudorange contributions and combining the transformed and weighted GPS contributions with computed GPS time difference of arrival (TDOA) values obtained from the pseudorange measurements.

66. A system as recited in claim 65, wherein said hybrid weighted least squares algorithm further comprises performing a three-dimensional search for GPS baselines.

67. A system as recited in claim 66, wherein said hybrid weighted least squares algorithm further comprises the computation of TDOA values assuming test locations of the mobile device and searching until a prescribed stopping condition is met, including computing chi-square metrics and summing said metrics for each test location.

68. A system as recited in claim 67, wherein said hybrid weighted least squares algorithm further comprises computation of a combined chi-square metric including separate bias values for GPS and U-TDOA.

69. A system as recited in claim 68, wherein said hybrid weighted least squares algorithm further comprises determining a minimum chi square metric and corresponding test location, wherein the stopping condition is deemed to be met when the minimum is found at a predetermined highest resolution.

70. A system as recited in claim 67, further comprising means for performing a U-TDOA search in three dimensions, said U-TDOA search comprising first searching transformed GPS/U-TDOA baselines for a minimum chi square metric over all GPS baselines in two dimensions (x, y) and then employing a z-search algorithm to search in a third dimension (z).

71. A system as recited in claim 67, wherein a prescribed stopping condition includes a continuation of the search at the current resolution when the minimum location solution falls on the edge of the search space.

72. A system as recited in claim 69, wherein a prescribed stopping condition includes a continuation of the search at the current map resolution when the minimum location solution falls on the edge of the search space.

73. A system as recited in claim 70, wherein said z-search algorithm comprises the use of an initial estimation of the mobile device'"'"'s altitude, a coarse search, a fine search, and steering criteria.

74. A system as recited in claim 73, wherein said z-search algorithm further comprises finding an initial search position in the z-dimension with respect to a U-TDOA coordinate system;

wherein said coarse search comprises computing and using an initial estimate, Zo, representing the position of the mobile device at a typical height above ground level;

wherein said steering criteria includes selecting the coarse search for resolutions below a predetermined resolution threshold, and performing the fine search once the resolution threshold is reached.

75. A non-transitory computer readable medium containing computer readable instructions for carrying out a computer-implemented method for use in locating a mobile device, wherein the mobile device is configured to obtain pseudorange measurements based on signals received from one or more satellites, wherein said one or more satellites are satellites of at least one of a Global Navigation Satellite System (GNSS) or Global Positioning System (GPS), and to compute GPS time difference of arrival (G-TDOA) values based on the GPS pseudorange measurements, said G-TDOA values representing baselines between the mobile device and the GPS/GNSS satellites, comprising:

instructions for communicating with the mobile device and obtaining from said mobile device pseudorange measurements;

instructions for computing G-TDOA values based on the GPS pseudorange measurements, said G-TDOA values representing baselines between the mobile device and the GPS/GNSS satellites;

instructions for obtaining an uplink time difference of arrival (U-TDOA) measurement representing a first baseline between first and second terrestrial receivers;

instructions for providing hybrid GPS/U-TDOA baselines;

instructions for computing weightings for the hybrid GPS/U-TDOA baselines; and

instructions for estimating the location of the mobile device using the hybrid GPS/U-TDOA baselines and the weightings.