Method for optimal search scheduling in satellite acquisition

• US 20030197641A1
• Filed: 04/19/2002
• Published: 10/23/2003
• Est. Priority Date: 04/19/2002
• Status: Active Grant

• Current Assignee: CSR Technology Incorporated (Qualcomm, Inc.)
• Original Assignee: Enuvis Inc. (Qualcomm, Inc.)
• Inventors: Chou, Andrew, Stone, Jesse, Mann, Wallace
• Granted Patent: US 6,836,241 B2
• Time in Patent Office: Days
• US Class Current: 342/357.63
• CPC Class Codes: G01S 19/24 Acquisition or tracking or demodulation of signals transmitted by the system synchronisation aspects of direct sequence spread spectrum modulation H04B1/7073
• CPC Class Codes: G01S 19/28 Satellite selection
• CPC Class Codes: G01S 19/29 carrier including Doppler, related G01S19/246 takes precedence
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence

Abstract

A method in a Global Positioning System (GPS) receiver achieves enhanced performance by scheduling searches in the Doppler search space according to a cost function. The cost function relates to both the cost of building a 3-dimensional correlation grid and the cost of searching satellite, code phase, Doppler and integration time interval spaces for values that provide a maximum in the correlation grid. In one embodiment, after the clock Doppler is determined upon acquiring one satellite, the Doppler search range associated with a cell in the grid is dominated by the receiver'"'"'s own motion. The scheduler schedules searching of the Doppler search space using search ranges determined empirically by the expected receiver velocity. In one embodiment, the scheduler increases integration times before changing Doppler search ranges, which require a recalculation of the grid.

Claims

17-1. A method as in claim 2, wherein said cost relates to searching said search region.

20. A method for signal detection by searching for values of a plurality of parameters that provide a match to a received signal, comprising:

receiving a set of optimization criteria;

for each parameter, receiving a cost function relating to searching a range of values for said parameter;

receiving a probabilistic model of signal detection for each parameter;

based on said optimization criteria, said cost functions and said probabilistic models, determining a schedule for searching for said values; and

performing signal detection in accordance with said schedule.

1. In a location determination apparatus, a method for scheduling a search of a parameter space, comprising:

dividing the parameter space into a plurality of search regions;

computing a figure of merit associated with each search region; and

scheduling a search of said search regions by optimizing said figure of merit.

2. A method as in claim 1, wherein said figure of merit relates to a cost, and wherein said scheduling schedules in increasing order of cost.

3. A method as in claim 1, further comprising:

calculating a reward and a cost for each search region; and

calculating as said figure a function of said reward and said cost.

4. A method as in claim 3, wherein said reward is determined according to a probability distribution.

5. A method as in claim 4, wherein said location determination system comprises a GPS receiver and wherein said probability distribution relates to the probability of acquiring a signal of a satellite.

6. A method as in claim 1, wherein said parameter space comprises numerous code phase values.

7. A method as in claim 1, wherein said parameter space comprises a Doppler frequency range.

8. A method as in claim 1, wherein said parameter space comprises a range of integration time intervals.

9. A method as in claim 8, wherein said method comprises finding a code phase and a Doppler value in said Doppler frequency range such that an ambiguity function exceeds a predetermined value.

10. A method as in claim 9, wherein said method evaluates said ambiguity function for multiple integration time intervals.

11. A method as in claim 8, wherein each of said search regions is associated with a maximum velocity of said location determination apparatus.

12. A method as in claim 11, wherein said scheduler schedules said search of said search regions with preference given to search region associated with smaller maximum velocities as integration time increases.

13. A method as in claim 10, wherein said location determination system comprises a GPS receiver, and wherein a correlation grid is created for each search region of said Doppler frequency range to acquire a signal of a satellite, said correlation grid being further associated with a code phase range, and wherein said scheduling schedules, for each of said search regions, evaluation of said ambiguity function for said multiple integration time intervals before searching another one of said search regions.

14. A method as in claim 13, wherein a stacking technique is applied in evaluating said ambiguity function.

15. A method as in claim 13, wherein each search region is associated with a sub-range of said Doppler frequency range, and wherein said scheduling schedules said search regions in order of increasing sub-ranges.

16. A method as in claim 15 wherein, in said scheduling, each successive sub-range is greater the previous sub-range by a factor of 4.

17. A method as in claim 1, wherein said scheduling schedules search regions having a cost less than a predetermined value.

18. A method as in claim 2, wherein said cost relates to building said grid.

21. A method as in claim 20, wherein said schedule specifies the order in which said parameters are searched.

22. A method as in claim 21, wherein said optimization criteria comprises a value function.

23. A method as in claim 21, wherein optimization criteria comprises system constraints.

24. A method as in claim 23, wherein said system constraints comprise a maximum run time.

25. A method as in claim 24, wherein said system constraints comprise a maximum memory size.

26. A method as in claim 20, wherein said cost function comprises a cost of building a search data structure.

27. A method as in claim 26, wherein said cost function further comprises a cost of searching said search data structure.

28. A method as in claim 20, wherein signal detection relate to detecting a GPS signal sent from a satellite, wherein said parameters comprise code phase.

29. A method as in claim 20, wherein signal detection relate to detecting a GPS signal sent from a satellite, wherein said parameters comprise a Doppler frequency.

30. A method as in claim 27, wherein said ranges of said parameters are adjusted using a linear programming method.

27-2. A method as in claim 20, further comprises, upon successfully detecting a signal, using values of said parameters found to adjust said ranges of said parameters.

28-3. A method as in claim 20, wherein one of said probabilistic models comprises a probability distribution function.

29-4. A method as in claim 20, wherein one of said probabilistic models comprises an interval of values representing a predetermined level of confidence.