Method for optimal search scheduling in satellite acquisition
First Claim
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, each search region comprising multiple parameter values within the parameter space;
for each search region, computing a figure of merit associated with that search region; and
scheduling searches of said search regions according to an ordering of said figures of merit.
2 Assignments
0 Petitions
Accused Products
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.
24 Citations
33 Claims
-
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, each search region comprising multiple parameter values within the parameter space;
for each search region, computing a figure of merit associated with that search region; and
scheduling searches of said search regions according to an ordering of said figures of merit. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
calculating a reward and a cost for each search region; and
calculating as said figure of merit 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 searching said search region.
-
19. A method as in claim 13, wherein said cost relates to building said correlation grid.
-
20. A method for signal detection by searching 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. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33)
-
Specification