Location-determination method and apparatus

• US 6,525,687 B2
• Filed: 02/12/2001
• Issued: 02/25/2003
• Est. Priority Date: 02/12/2001
• Status: Expired due to Term

• Current Assignee: CSR Technology Holdings Inc. (Qualcomm, Inc.)
• Original Assignee: Enuvis Inc. (Qualcomm, Inc.)
• Inventors: Chou, Andrew, Roy, Benjamin Van, Tsitsiklis, John
• Primary Examiner(s): Phan, Dao
• Application Number:
  US09/782,648
• Publication Number:
  US 20020145557A1
• Time in Patent Office: 743 Days
• Field of Search: 342/357.01, 342/357.02, 342/357.06, 342/357.07, 701/213, 701/215
• US Class Current: 342/357.29
• CPC Class Codes: G01S 19/09 providing processing capability normally carried out by the receiver
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G01S 2205/008 using a mobile telephone network

Abstract

Some embodiments of the invention provide a location-determination system that includes a number of transmitters and at least one receiver. Based on a reference signal received by the receiver, this location-determination system identifies an estimated location of the receiver within a region. In some embodiments, the system selects one or more locations within the region. For each particular selected location, the system calculates a metric value that quantifies the similarity between the received signal and the signal that the receiver could expect to receive at the particular location, in the absence or presence of interference. Based on the calculated metric value or values, the system identifies the estimated location of the receiver.

Claims

1. A method of determining an estimated location of a receiver within a region from a reference signal received by the receiver, the method comprising:

a) selecting a plurality of locations within the region;

b) for each selected location, calculating a metric value that quantifies the similarity between the received signal and an expected signal for the selected location; and

c) identifying the estimated location of the receiver based on the calculations.

2. The method of claim 1 wherein identifying the estimated location of the receiver comprises:

a) identifying the metric value that is the best value among the calculated metric values; and

b) identifying the location resulting in the best metric value as the estimated location of the receiver.

3. The method of claim 1, wherein calculating the metric value for each selected location comprises calculating the difference between the received signal and the expected signal for the selected location.

4. The method of claim 3, wherein identifying the estimated location includes identifying the selected location resulting in the smallest calculated difference as the estimated location of the receiver.

5. The method of claim 1, wherein calculating the metric value for each selected location comprises calculating a log-likelihood ratio based on the received signal and the expected signal for the selected location.

6. The method of claim 5, wherein identifying the estimated location includes identifying the selected location resulting in the maximum calculated log-likelihood ratio as the estimated location of the receiver.

7. The method of claim 1 identifying the estimated location includes:

a) identifying the selected location that resulted in the best calculated metric value;

b) selecting a plurality of additional locations about the identified location;

c) for each particular additional location, calculating a metric value that quantifies the similarity between the received signal and the expected signal for the particular additional location; and

d) based on the additional calculations, identifying the estimated location of the receiver.

8. The method of claim 1, wherein identifying the estimated locations comprises:

a) identifying a plurality of the selected locations that resulted in the best calculated metric values; and

b) using an analytical technique to compute the estimated location from the identified selected locations.

9. The method of claim 8, wherein the analytical technique is an interpolative technique.

10. The method of claim 1, wherein the method is for a location-determination system having a plurality of transmitters and the receiver, wherein the expected signal is a signal that the receiver receives from a set of the transmitters.

11. The method of claim 10 further comprising:

a) generating samples of the received signal;

b) wherein calculating the metric value for the selected location comprises;

1) generating an hypothetical signal for each transmitter in the set of transmitters;

2) when the set of transmitters has more than one transmitter, combining the generated hypothetical signals to generate the expected signal;

3) generating samples of the expected signal;

4) calculating the metric value based on the samples of the received and expected signals.

12. The method of claim 10 further comprising:

a) generating samples of the received signal;

b) wherein calculating the metric value for the selected location comprises;

1) generating an hypothetical signal for each transmitter in the set of transmitters;

2) generating samples of each hypothetical signal;

3) for each particular hypothetical signal, calculating a metric value based on the samples of the received signal and of the particular hypothetical signal to quantify the similarity between the received signal and the particular hypothetical signal; and

4) when the set of transmitters has more than one transmitter, combining the calculated metric values for all hypothetical signals to generate the metric value for the selected location.

13. The method of claim 1, wherein the method is for a global positioning system (“

GPS”

) and the receiver is a GPS receiver.

14. A global positioning method comprising:

a) using a global positioning system (“

GPS”

) receiver to receive a GPS signal; and

b) identifying an estimated location of the GPS receiver from the GPS signal by comparing the received GPS signal with a synthesized GPS signal expected to be received at the estimated location.

29. The method of claim 14, wherein the comparing is performed quantitatively by evaluating a function.

30. The method of claim 29, wherein the function comprises a log-likelihood ratio.

31. The method of claim 29, wherein the function comprises a square of a difference between the received GPS signal and the synthesized GPS signal.

32. The method of claim 31, wherein the synthesized GPS signal is the sum of a plurality of GPS signals expected from a plurality of GPS satellites.

15. For a global positioning system (“

GPS”

) having a plurality of satellites, a method of estimating a location of a GPS receiver within a region from a GPS signal received by the receiver, the method comprising;

a) identifying at least some of the satellites that are over the region;

b) identifying a plurality of locations within the region;

c) for each particular identified location, calculating a metric value that quantifies the similarity between the received GPS signal and an expected signal, the expected signal for each particular identified location is the signal that the receiver is expected to receive at the particular location from the identified satellites; and

d) based on the calculations, estimating the location of the receiver.

16. The method of claim 15 wherein identifying the satellites comprises identifying all the satellites that are over the region.

17. The method of claim 15 wherein identifying the satellites comprises identifying some but not all of the satellites that are over the region.

18. The method of claim 15, wherein the received signal includes a signal from each of the identified satellites, the method further comprising:

a) for each identified satellite, calculating a Doppler shift in the satellite'"'"'s signal due to the motion of the satellite; and

b) using the calculated Doppler shifts in the calculation of the metric value for each location.

19. The method of claim 15,

wherein the metric value for each particular location is calculated by using a metric function that is dependent on an unknown parameter,

wherein identifying the plurality of locations includes specifying a plurality of hypotheses, each hypothesis identifying a location within the region and a value for the unknown parameter;

and

wherein calculating the metric value for each particular location includes calculating, for each particular hypothesis, a metric value that quantifies the similarity between the received signal and an expected signal that the receiver is expected to receive from the identified satellites when the receiver is at the location specified by the particular hypothesis and the unknown parameter has the value specified by the particular hypothesis.

20. The method of claim 19, wherein the unknown parameter relates to operation of the GPS receiver.

21. The method of claim 20, wherein the receiver has a clock with a particular drift, wherein the clock'"'"'s drift introduces a Doppler shift in the received signal, wherein the unknown parameter is the Doppler shift introduced by the clock'"'"'s drift.

22. The method of claim 21 further comprising:

generating samples of the received GPS signal, wherein a first sample is generated at a first-sample time measured according to the receiver'"'"'s clock;

wherein each hypothesis specifies a location, a Doppler-shift value, and a first-sample time value, and the calculated metric value for each hypothesis is a function of the location, Doppler-shift value, and first-sample time value specified by the hypothesis.

23. The method of claim 15 further comprising identifying the region containing the GPS receiver.

24. The method of claim 23 further comprising identifying an approximate location for the GPS receiver, wherein identifying the region includes identifying a region around the identified approximate location.

25. The method of claim 15, wherein calculating the metric value for each identified location comprises calculating the difference between the received GPS signal and the expected signal for the identified location.

26. The method of claim 15, wherein estimating the location of the receiver includes identifying the location resulting in the smallest calculated difference as the location of the receiver.

27. The method of claim 15, wherein calculating the metric value for each identified location comprises calculating a log-likelihood ratio based on the received GPS signal and the expected signal for the identified location.

28. The method of claim 27, wherein estimating the location of the receiver includes identifying the location resulting in the maximum calculated log-likelihood ratio as the location of the receiver.