Reduced Sampling Low Power GPS

• US 20140015713A1
• Filed: 07/16/2012
• Published: 01/16/2014
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Jie, Priyantha, Nissanka Arachchige Bodhi, Hart, Edward, Jin, Yuzhe, de Paula, Amanda Souza
• Granted Patent: US 10,386,490 B2
• Time in Patent Office: Days
• US Class Current: 342/357.69
• CPC Class Codes: G01S 19/09 providing processing capability normally carried out by the receiver
• CPC Class Codes: G01S 19/254 relating to Doppler shift of satellite signals
• CPC Class Codes: G01S 19/258 relating to the satellite constellation, e.g. almanac, ephemeris data, lists of satellites in view
• CPC Class Codes: G01S 19/34 Power consumption
• CPC Class Codes: G01S 19/42 Determining position
• CPC Class Codes: G01S 5/0036 of measured values, i.e. measurement on mobile and position calculation on base station

Abstract

Some implementations provide low power reduced sampling of global positioning system (GPS) locations. A server may be configured to assist a mobile device in determining a location from a plurality of GPS signal samples and corresponding time stamps provided by the mobile device, such as by identifying a set of possible reference locations, which may be used to calculate a location of the mobile device. In another example, the mobile device may sample GPS signals using a GPS receiver, compress the samples, and provide the compressed samples to the server for processing.

Claims

1. A method comprising:

receiving a plurality of global positioning system (GPS) signal samples and corresponding time stamps from a mobile device;

identifying, by one or more processors, a set of visible satellites and for each visible satellite a corresponding Doppler frequency and code phase from the GPS signal samples;

requesting ephemeris data from a database;

identifying a set of possible reference locations; and

determining a set of possible locations corresponding to the received sample signals, each of the possible locations corresponding to one of the references locations identified, the set of possible locations including a location of the mobile device.

7. The method of claim 1, wherein the set of possible reference locations is identified in part by calculating the intersections of angles of arrival of satellite signals inferred from the Doppler frequency of received satellite signals.

8. The method of claim 1, wherein the GPS signal samples are compressed according to compressed sensing theory.

9. The method of claim 8, wherein the GPS signal samples are compressed in the time domain.

10. The method of claim 8, wherein the GPS signal samples are compressed in the frequency domain.

11. The method of claim 1, wherein identifying the set of visible satellites comprises applying a sparse signal recovery solver to a compressed GPS signals.

12. The method of claim 1, wherein identifying the set of visible satellites comprises applying a L1 minimization (Lasso) Solver to find each visible satellite signal'"'"'s presence in a compressed GPS signals.

2. The method of claim 2, wherein the set of possible locations includes at least one shadow location and further comprising eliminating any shadow locations to determine the location.

3. The method of claim 2, wherein determining a set of possible locations comprises applying a coarse time navigation (CTN) method to each of the reference locations.

4. The method of claim 2, wherein eliminating the shadow locations comprises eliminating a possible location of the set of possible locations when the CTN calculation for each of the visible satellites does not converge.

5. The method of claim 2, wherein eliminating the shadow locations comprises restraining the set of possible locations to a range near the Earth'"'"'s surface.

6. The method of claim 2, wherein eliminating the shadow locations comprises:

requesting elevation data from a database corresponding to each of the possible locations;

comparing the elevation data to an elevation of each of the possible locations;

eliminating each of the possible locations if the elevations are not a match; and

selecting the remaining location that has the least dilution of precision.

13. A device comprising:

one or more processors;

one or more computer-readable media maintaining instructions executable by the one or more processors to perform operations that include;

receiving a global position system (GPS) signal;

compressing the GPS signal, according to compressed sensing theory to generate a plurality of compressed GPS signals; and

providing the plurality of compressed GPS signal samples and the time stamps to a computer.

14. The device as recited in claim 13, wherein the one or more computer-readable media maintains additional instructions that when executed by the one or more processors further cause the one or more processors to perform operations that include:

generating a plurality of GPS signal samples from the GPS signal;

applying a time stamp to each of the plurality of GPS signal samples; and

wherein the compressing the GPS signal comprises compressing the GPS signal samples.

15. The device as recited in claim 13, wherein the GPS signal is compressed in the time domain.

16. The device as recited in claim 13, wherein the GPS signal is compressed in the frequency domain.

17. The device as recited in claim 13, wherein the compressing the GPS signal according to compressed sensing theory comprises:

expressing the GPS signal as a matrix enumerated over possible shifted Doppler frequencies and code phases; and

rewriting the expression as a compressed sensing model including a coefficient vector of the weighted averages of each column.

18. The device as recited in claim 13, wherein the compressing the GPS signal according to compressed sensing theory comprises:

fixing a set of possible Doppler frequencies;

expressing the GPS signal as a matrix enumerated over possible shifted code phases and the fixed set of Doppler frequencies; and

rewriting the expression as a compressed sensing model including a coefficient vector of the weighted averages of each column.

19. The device as recited in claim 13, wherein the compressing the GPS signal according to compressed sensing theory comprises:

performing a discrete Fourier transform (DFT) on the GPS signal;

expressing coefficients resulting from the DTF as a matrix enumerated over possible Doppler frequencies; and

rewriting the expression as a compressed sensing model including a coefficient vector of the weighted averages of each column.

20. A computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to:

receive a plurality of global positioning system (GPS) signal samples and corresponding time stamps, the GPS signal samples compressed according to compressed sensing theory;

identify a set of visible satellites and for each visible satellite a corresponding Doppler frequency and code phase from the GPS signal samples;

retrieve ephemeris of the visible satellites;

identify a set of possible reference locations inferred at least in part from the Doppler frequency of received satellite signals;

determine a set of possible locations by applying a coarse time navigation (CTN) calculation to each of the reference locations, each of the possible locations corresponding to one of the references locations identified, the set of possible locations including an actual location and at least one shadow location;

retrieve elevation data related to each of the possible locations; and

eliminate the shadow locations in part by using elevation data.