Energy-efficient positioning system for smartphone using cell-id sequence matching

• US 8,521,193 B2
• Filed: 11/11/2011
• Issued: 08/27/2013
• Est. Priority Date: 12/08/2010
• Status: Active Grant

• Current Assignee: Deutsche Telekom AG
• Original Assignee: Deutsche Telekom AG
• Inventors: Singh, Jatinder Pal, Paek, Jeongyeup, Kim, Kyu-Han
• Primary Examiner(s): SIVJI, NIZAR N
• Application Number:
  US13/294,280
• Publication Number:
  US 20120149400A1
• Time in Patent Office: 655 Days
• Field of Search: 705/1, 455/457, 455/456, 455/432
• 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:

detecting, at a cellid-aided positioning system-compatible device, movements of the device between cellids while monitoring global positioning system (GPS) coordinates of the device, and based thereon, storing a plurality of routes traversed by the device, wherein each of the plurality of routes comprises a sequence of cellids and global positioning system (GPS) coordinates corresponding to the device as the device traversed through the route;

determining that the device has moved through a particular sequence of cellids, wherein moving through the particular sequence of cellids comprises moving from a first region corresponding to a first cellid to a second region corresponding to a second cellid;

matching the particular sequence of the cellids with a sequence of cellids in a previously stored route;

estimating a current position of the device based on the previously stored GPS coordinates corresponding to the device as the device traversed through the previously stored route and further based on an amount of time elapsed since the device entered a current cellid corresponding to the device; and

displaying the current position of the device.

2. The method of claim 1, wherein matching the particular sequence of the cellids with a sequence of cellids in a previously stored route comprises:

determining a best match based on at least one of;

a length of record that matches the particular sequence of cellids;

a time of day;

a frequency; and

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

3. The method of claim 1, wherein matching the particular sequence of the cellids with a sequence of cellids in a previously stored route comprises:

applying the Smith-Waterman Algorithm to the particular sequence of cellids and the previously stored route with penalty for gaps and mismatches and with a requirement that the current cellid corresponding to the device be in the previously recorded sequence of cellids.

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

5. 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:

detecting movements of the device between cellids while monitoring global positioning system (GPS) coordinates of the device, and based thereon, storing a plurality of routes traversed by the device, wherein each of the plurality of routes comprises a sequence of cellids and global positioning system (GPS) coordinates corresponding to the device as the device traversed through the route;

determining that the device has moved through a particular sequence of cellids, wherein moving through the particular sequence of cellids comprises moving from a first region corresponding to a first cellid to a second region corresponding to a second cellid;

matching the particular sequence of the cellids with a sequence of cellids in a previously stored route;

estimating a current position of the device based on the previously stored GPS coordinates corresponding to the device as the device traversed through the previously stored route and further based on an amount of time elapsed since the device entered a current cellid corresponding to the device; and

displaying the current position of the device.

6. The device of claim 5, wherein the instructions for matching the particular sequence of the cellids with a sequence of cellids in a previously stored route further comprise instructions for:

determining a best match based on at least one of;

a length of record that matches the particular sequence of cellids;

a time of day;

a frequency; and

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

7. The device of claim 5, wherein the instructions for matching the particular sequence of the cellids with a sequence of cellids in a previously stored route further comprise instructions for:

applying the Smith-Waterman Algorithm to the particular sequence of cellids and the previously stored route with penalty for gaps and mismatches and with a requirement that the current cellid corresponding to the device be in the previously recorded sequence of cellids.

8. The device of claim 5, wherein the device is a smartphone.