Cloud-offloaded global satellite positioning

• US 10,317,538 B2
• Filed: 08/27/2013
• Issued: 06/11/2019
• Est. Priority Date: 08/27/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Liu, Jie, Jin, Yuzhe, Hart, Ted C.
• Primary Examiner(s): Magloire, Vladimir
• Assistant Examiner(s): Seraydaryan, Helena H
• Application Number:
  US14/011,140
• Publication Number:
  US 20150061934A1
• Time in Patent Office: 2,114 Days
• Field of Search: 34235769
• CPC Class Codes: G01S 19/09 providing processing capability normally carried out by the receiver
• CPC Class Codes: G01S 19/21 Interference related issues ; Issues related to cross-correlation, spoofing or other methods of denial of service
• CPC Class Codes: G01S 19/28 Satellite selection
• CPC Class Codes: G01S 19/30 code related G01S19/246 takes precedence

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 small GPS signal chunks and corresponding time stamps. For instance, the server may identify a set of satellites from each of the GPS signal chunks and by comparing the set of satellites for each of the GPS signal chunks to each other to determine a second set of satellites. The server may then estimate a location of the mobile based on the second set of satellites.

Claims

1. A computing device comprising:

one or more processors; and

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

receiving a plurality of chunks of global positioning system (GPS) signals, wherein individual chunks of the plurality of chunks are representative of a segment of a GPS signal, wherein individual chunks of the plurality of chunks are spaced by an interval of time, and wherein each chunk of the plurality of chunks is 1 to 2 milliseconds in length;

searching for satellite specific Coarse/Acquisition (C/A) codes in the plurality of chunks over code phase and Doppler frequency combinations to identify visible satellites;

calculating, for each of the visible satellites, a difference between a first code phase and a second code phase, the first code phase associated with a first one of the plurality of chunks and the second code phase associated with a second one of the plurality of chunks;

identifying a first satellite from the plurality of GPS signal chunks by searching for satellite specific Coarse/Acquisition (C/A) codes in each GPS signal chunk of the plurality of GPS signal chunks over code phase and Doppler frequency combinations;

remove signals associated with the first satellite from the plurality of GPS signal chunks by performing a projection onto an appropriate signal subspace determined by C/A code templates of the identified first satellite;

adding each visible satellite for which the difference is less than a threshold difference to a set of satellites; and

estimating a location based on the set of satellites.

2. The computing device as recited in claim 1, wherein:

adding a visible satellite to the set of satellites is based at least partly on data related to the location; and

the operations further comprise re-estimating the location based in part on the added satellites.

3. The computing device as recited in claim 1, wherein the searching for the satellite specific C/A codes is performed independently on each chunk of the plurality of chunks.

4. The computing device as recited in claim 1, wherein each chunk of the plurality of chunks is 1 millisecond in length.

5. The computing device as recited in claim 1, wherein the location is estimated based on the time over which the plurality of chunks were collected, the set of satellites, ephemeris data, and pseudorange data related to each satellite of the set of satellites.

6. The computing device as recited in claim 1, wherein the searching for the satellite specific C/A codes is performed iteratively until a stopping criteria is achieved.

7. The computing device as recited in claim 6, wherein the stopping criteria is at least one of:

a predetermined number of iterations;

or

the computing device is unable to identify any additional satellites from the chunk.

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

receive data related to a plurality of satellites identified from a plurality of global positioning system (GPS) signal chunks, wherein;

individual chunks of the plurality of GPS signal chunks comprise a portion of a GPS signal sample of a plurality of GPS signal samples,

the data includes a plurality of code phases,

each of the plurality of code phases is associated with one of the plurality of satellites and one of the plurality of GPS signal chunks,

individual chunks of the plurality of GPS signal chunks are spaced by intervals of time,

individual ones of the intervals of time are not equal, and

individual chunks of the plurality of chunks include a time over which the individual chunk was sampled;

calculate, for each satellite of the plurality of satellites, differences between individual code phases of the plurality of code phases for each of the plurality of GPS signal chunks;

determine that a majority of the differences for a satellite of the plurality of satellites is less than a threshold difference;

add the satellite to a set of satellites;

receive the plurality of GPS signal chunks;

identify a first satellite from the plurality of GPS signal chunks by searching for satellite specific Coarse/Acquisition (C/A) codes in each GPS signal chunk of the plurality of GPS signal chunks over code phase and Doppler frequency combinations;

remove signals associated with the first satellite from the plurality of GPS signal chunks by performing a projection onto an appropriate signal subspace determined by C/A code templates of the identified first satellite; and

output the set of satellites.

9. The computer-readable storage device as recited in claim 8, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to:

receive the plurality of GPS signal chunks; and

identify a second satellite from the plurality of GPS signal chunks by re-searching for the satellite specific C/A codes in each GPS signal sample of the plurality of GPS signal samples over the code phase and Doppler frequency combinations,

wherein the data related to the plurality of satellites is data related to the first satellite and the second satellite.

10. The computer-readable storage device as recited in claim 8, wherein the plurality of GPS signal chunks are 1 millisecond to 2 milliseconds in length.

11. The computer-readable storage device as recited in claim 8, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to:

estimate a first location based on the set of satellites.

12. The computer-readable storage device as recited in claim 11, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to:

determine that the differences between individual code phases of the plurality of code phases for an additional satellite of the plurality of satellites are greater than the threshold difference;

adding the additional satellite to the set of satellites based on data related to the first location;

estimate a second location based in part on the additional satellite; and

output the second location.

13. A method comprising:

receiving a first global positioning system (GPS) signal chunk and a second GPS signal chunk, the first GPS signal chunk and the second GPS signal chunk spaced by an interval of time, and wherein the first GPS signal chunk and the second GPS signal chunk are each representative of a segment of a GPS signal, each of first GPS signal chunk and the second GPS signal chunk includes a time over which the individual chunk was collected;

identifying a first satellite from the first GPS signal chunk by searching for satellite specific Coarse/Acquisition (C/A) codes in the first GPS signal chunk over code phase and Doppler frequency combinations;

adding the first satellite to a set of satellites;

removing signals associated with the first satellite from the first GPS signal chunk by performing a projection onto an appropriate signal subspace determined by C/A code templates of the identified first satellite;

identifying a second satellite from the first GPS signal chunk by searching for the satellite specific C/A codes in the first GPS signal chunk over the code phase and Doppler frequency combinations;

adding the second satellite to the set of satellites; and

outputting the set of satellites.

14. The method as recited in claim 13, further comprising:

removing signals associated with the second satellite from the first GPS signal chunk;

identifying a third satellite from the first GPS signal chunk by searching for the satellite specific C/A codes in the first GPS signal chunk over the code phase and Doppler frequency combinations; and

adding the third satellite to the set of satellites before outputting the set of satellites.

15. The method as recited in claim 13, further comprising:

identifying a first additional satellite from the second GPS signal chunk by searching for the satellite specific C/A codes in the second GPS signal chunk over the code phase and Doppler frequency combinations;

adding the first satellite identified in the second GPS signal chunk to a second set of satellites;

removing signals associated with the first satellite identified in the second GPS signal chunk from the second GPS signal chunk;

identifying a second satellite from the second GPS signal chunk by searching for the satellite specific C/A codes in the GPS signal chunk over the code phase and Doppler frequency combinations;

adding the second satellite identified in the second GPS signal chunk to the set of satellites; and

outputting the second set of satellites.

16. The method as recited in claim 15, further comprising:

determining a difference between a first code phase associated the first GPS signal chunk and a second code phase associated with the second GPS signal chunk, the first and second code phases associated with one satellite;

comparing the difference to a threshold difference;

determining that the difference is less than the threshold difference; and

estimating a location based at least in part on data related to the first satellite.

17. The method as recited in claim 15, wherein the first satellite identified in the first GPS signal chunk is the same as the first additional satellite identified in the second GPS signal chunk.

18. The method as recited in claim 13, wherein the first GPS signal chunk and the second GPS signal chunk are 1 millisecond to 2 milliseconds in length.

19. The method as recited in claim 13, wherein the signals associated with the first satellite are detected and removed from the GPS signal chunk by performing a matching pursuit calculation.

20. The method as recited in claim 13, wherein the signals associated with the first satellite are detected and removed from the GPS signal chunk by performing an orthogonal matching pursuit calculation.