ENERGY-EFFICIENT POSITIONING SYSTEM FOR SMARTPHONE USING CELL-ID SEQUENCE MATCHING

• US 20120149400A1
• Filed: 11/11/2011
• Published: 06/14/2012
• Est. Priority Date: 12/08/2010
• Status: Active Grant

• Current Assignee: Deutsche Telekom AG
• Original Assignee: Deutsche Telekom AG
• Inventors: Kim, Kyu-Han, Singh, Jatinder Pal, Paek, Jeongyeup
• Granted Patent: US 8,521,193 B2
• Time in Patent Office: Days
• US Class Current: 455/457
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01S 19/48 by combining or switching between position solutions derived from the satellite radio beacon positioning system and position solutions derived from a further system
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method for navigation based on a cellid-aided positioning system includes: determining, at a cellid-aided positioning system-compatible device, that a user has moved through a sequence of cellids, wherein moving through a sequence of cellids comprises moving from a first region corresponding to a first cellid to a second region corresponding to a second cellid; accessing previously stored route information corresponding to the sequence of cellids, wherein the previously stored route information includes previously recorded sequences of cellids and global positioning system (GPS) information; estimating a current position of the user based on the previously stored route information; and displaying the current position of the user.

Claims

1. A method for navigation based on a cellid-aided positioning system, the method comprising:

determining, at a cellid-aided positioning system-compatible device, that a user has moved through a sequence of cellids, wherein moving through a sequence of cellids comprises moving from a first region corresponding to a first cellid to a second region corresponding to a second cellid;

accessing previously stored route information corresponding to the sequence of cellids, wherein the previously stored route information includes previously recorded sequences of cellids and global positioning system (GPS) information;

estimating a current position of the user based on the previously stored route information; and

displaying the current position of the user.

2. The method of claim 1, wherein the estimating the current position of the user comprises searching the previously stored route information to determine whether the sequence of cellids matches a previously recorded sequence of cellids.

3. The method of claim 2, wherein the searching the previously stored route information so as to determine whether the sequence of cellids matches a previously recorded sequence of cellids comprises determining a best match for estimating current position based on at least one of:

a length of record that matches the sequence of cellids;

a time of day;

a frequency; and

whether the record corresponds to a current cellid corresponding to the user.

4. The method of claim 2, wherein the searching the previously stored route information so as to determine whether the sequence of cellids matches a previously recorded sequence of cellids comprises applying the Smith-Waterman Algorithm to the sequence of cellids and the previously recorded sequence of cellids with penalty for gaps and mismatches and with a requirement that the current cellid corresponding to the user be in the previously recorded sequence of cellids.

5. The method of claim 2, wherein the previously stored route information further includes a time, a GPS coordinate, and a cellid corresponding to the time.

6. The method of claim 1, wherein the estimating a current position of the user is based on an amount of time elapsed since the user entered a current cellid corresponding to the user.

7. The method of claim 1, wherein the cellid-aided positioning system utilizes GPS positioning to determine the current position of the user when the cellid-aided positioning system is unable to estimate the current position of the user based on the previously stored route information.

8. The method of claim 7, wherein the current position of the user determined by utilizing GPS positioning is stored at the cellid-aided positioning system and subsequently used as previously stored route information.

9. The method of claim 1, wherein the sequence of cellids is segmented when the user moves back to a cellid that is part of the sequence of cellids.

10. The method of claim 1, wherein the cellid-aided positioning system-compatible device is a smartphone.

11. A device for navigation based on a cellid-aided positioning system, the device having a tangible, non-transient computer-readable medium with computer-executable instructions stored thereon, the computer-executable instructions comprising:

instructions for determining that a user has moved through a sequence of cellids, wherein moving through a sequence of cellids comprises moving from a first region corresponding to a first cellid to a second region corresponding to a second cellid;

instructions for accessing previously stored route information corresponding to the sequence of cellids, wherein the previously stored route information includes previously recorded sequences of cellids and global positioning system (GPS) information;

instructions for estimating a current position of the user based on the previously stored route information; and

instructions for displaying the current position of the user.

12. The device of claim 11, wherein the instructions for estimating the current position of the user comprise instructions for searching the previously stored route information to determine whether the sequence of cellids matches a previously recorded sequence of cellids.

13. The device of claim 12, wherein the instructions for searching the previously stored route information so as to determine whether the sequence of cellids matches a previously recorded sequence of cellids comprise instructions for determining a best match for estimating current position based on at least one of:

a length of record that matches the sequence of cellids;

a time of day;

a frequency; and

whether the record corresponds to a current cellid corresponding to the user.

14. The device of claim 12, wherein the instructions for searching the previously stored route information so as to determine whether the sequence of cellids matches a previously recorded sequence of cellids comprise instructions for applying the Smith-Waterman Algorithm to the sequence of cellids and the previously recorded sequence of cellids with penalty for gaps and mismatches and with a requirement that the current cellid corresponding to the user be in the previously recorded sequence of cellids.

15. The device of claim 12, wherein the previously stored route information further includes a time, a GPS coordinate and a cellid corresponding to time.

16. The device of claim 11, wherein the instructions for estimating a current position of the user are further based on the amount of time elapsed since the user entered a current cellid corresponding to the user.

17. The device of claim 11, further comprising:

instructions for utilizing GPS positioning to determine the current position of the user when the device is unable to estimate the current position of the user based on the previously stored route information.

18. The device of claim 17, further comprising:

instructions for storing the current position of the user determined by utilizing GPS positioning for subsequent use as previously stored route information.

19. The device of claim 11, further comprising:

instructions for segmenting the sequence of cellids when the user moves back to a cellid that is part of the sequence of cellids.

20. The device of claim 11, wherein the device is a smartphone.