Reduced sampling low power GPS

• US 10,386,490 B2
• Filed: 07/16/2012
• Issued: 08/20/2019
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Liu, Jie, Jin, Yuzhe, Priyantha, Nissanka Arachchige Bodhi, Hart, Edward, de Paula, Amanda Souza
• Primary Examiner(s): Galt, Cassi J
• Application Number:
  US13/550,454
• Publication Number:
  US 20140015713A1
• Time in Patent Office: 2,591 Days
• 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, by one or more communication interfaces of a server, global positioning system (GPS) signal samples including at least a first plurality of GPS signal samples and a corresponding first set of time stamps and a second plurality of GPS signal samples and a corresponding second set of time stamps from a mobile device, wherein the first set of time stamps and the second set of time stamps are separated by a period of time;

identifying, for a selected GPS signal sample, by one or more processors of the server in response to receiving the GPS signal samples, a set of visible satellites and, for each visible satellite of the set of visible satellites, identifying a corresponding Doppler frequency and code phase from the selected GPS signal sample;

requesting, by the one or more processors of the server, ephemeris data from a database;

identifying, for the selected GPS signal sample, by the one or more processors of the server, a set of possible reference locations based at least on the corresponding Doppler frequency or the ephemeris data of at least one visible satellite of the set of visible satellites;

determining, for the selected GPS signal sample, and by the one or more processors of the server, possible locations associated with the selected GPS signal sample, each of the possible locations corresponding to one of the possible reference locations, and the possible locations including a location of the mobile device at a time indicated by the time stamp corresponding to the selected GPS signal sample;

eliminating a possible location by;

requesting, from an additional database, elevation data corresponding to each of the possible locations;

comparing the elevation data to an elevation of the possible location;

determining that the elevation of the possible location does not correspond to elevations included in the elevation data;

eliminating the possible location; and

selecting, as the location of the mobile device at the time indicated by the time stamp corresponding to the selected GPS signal sample, a remaining location that has a least dilution of precision.

2. The method of claim 1, wherein the possible locations include at least one shadow location and the method further comprising eliminating any shadow locations to determine the location of the mobile device.

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

4. The method of claim 1, wherein receiving, by the one or more communication interfaces of the server, the GPS signal samples further comprises receiving the GPS signal samples via a GPS receiver for processing.

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

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

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

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

9. The method of claim 7, wherein the GPS signal samples are compressed in a frequency domain.

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

11. The method of claim 1, wherein identifying the set of visible satellites comprises applying a L1 minimization (Lasso) Solver to identify a presence of a signal of a visible satellite of the set of visible satellites in the GPS signal samples.

18. The method of claim 1, wherein determining the possible locations associated with the selected GPS signal sample is based at least on one of the code phase or the ephemeris data.

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

receive global positioning system (GPS) signal samples including at least a first plurality of GPS signal samples and a corresponding first set of time stamps and a second plurality of GPS signal samples and a corresponding second set of time stamps from a mobile device, wherein the first set of time stamps and the second set of time stamps are separated by a period of time;

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

retrieve ephemeris data of the set of visible satellites;

identify, for the selected GPS signal sample, possible reference locations inferred at least in part from the corresponding Doppler frequency or the ephemeris data of at least one visible satellite of the set of visible satellites;

determine, for the selected GPS signal sample, possible locations associated with the selected GPS signal sample, each of the possible locations corresponding to one of the possible reference locations, the possible locations including a location of the mobile device at a time indicated by the time stamp corresponding to the selected GPS signal sample;

eliminate a possible location by;

retrieving elevation data related to each of the possible locations;

comparing the elevation data to an elevation of the possible location;

determining that the elevation of the possible location does not correspond to elevations included in the elevation data; and

eliminating the possible location; and

select a remaining location that has a least dilution of precision as the location of the mobile device.

17. The computer-readable storage device of claim 12, wherein the possible reference locations are identified in part by calculating the intersections of angles of arrival of satellite signals inferred from the corresponding Doppler frequency of satellite signals received from the set of visible satellites.

19. The computer-readable storage device of claim 12, wherein determining, for the selected GPS signal sample, the possible locations associated with the selected GPS signal sample, is based at least on one of the code phase or the ephemeris data.

13. A server comprising:

one or more processors;

one or more communication interfaces receiving global positioning system (GPS) signal samples including at least a first plurality of GPS signal samples and a corresponding first set of time stamps and a second plurality of GPS signal samples and a corresponding second set of time stamps from a mobile device, wherein the first set of time stamps and the second set of time stamps are separated by a first period of time; and

one or more computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors in response to receiving the GPS signal samples to;

identify, for at least one GPS signal sample, a set of visible satellites;

identify, for each visible satellite of the set of visible satellites, a corresponding Doppler frequency and code phase from the at least one GPS signal sample;

request ephemeris data from a database;

identify, for the at least one GPS signal sample, possible reference locations based at least on the corresponding Doppler frequency or the ephemeris data of at least one visible satellite of the set of visible satellites;

determine possible locations associated with the at least one GPS signal sample based at least in part on the code phase of at least one visible satellite of the set of visible satellites, the ephemeris data, and the possible reference location, the possible locations including a location of the mobile device associated with at least one of a first time stamp from the first set of time stamps or second time stamp from the second set of time stamps;

eliminate a possible location by;

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

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

eliminating at least one of the possible locations if the elevation is not a match; and

select a remaining location that has the least dilution of precision as the location of the mobile device.

14. The server of claim 13, wherein the one or more communication interfaces receiving the GPS signal samples further comprises receiving the GPS signal samples via a GPS receiver of a mobile device for processing.

15. The server of claim 13, wherein eliminating the at least one shadow location is based at least in part on elevation data associated with a possible location of the possible locations.

16. The server of claim 13, wherein eliminating the at least one shadow location comprises restraining the possible locations to a range near the Earth'"'"'s surface.