Queries as data for revising and extending a sensor-based location service

• US 8,244,240 B2
• Filed: 06/29/2006
• Issued: 08/14/2012
• Est. Priority Date: 06/29/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Achlioptas, Dimitris, Krumm, John C., Horvitz, Eric J.
• Primary Examiner(s): BALAOING, ARIEL A
• Application Number:
  US11/427,778
• Publication Number:
  US 20080004037A1
• Time in Patent Office: 2,238 Days
• Field of Search: 455/433, 455/414.2, 455/456.2, 701/207, 701/213
• US Class Current: 455/433
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: H04W 16/00 Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition

Abstract

The claimed subject matter provides systems and/or methods that facilitate automatically maintaining a database of base stations. A location component can obtain a query that includes a listing of detected base stations. Additionally, the location component can identify whether the detected base stations are included in a base station database. Further, the location component can generate an estimated location related to the query. Moreover, a database update component can modify the base station database based at least in part upon the query.

Claims

1. A system that facilitates automatically maintaining a base station database, comprising:

a processor;

a location component configured to be operated by the processor that receives a query that includes a listing of detected base stations from a mobile radio;

a query store that retains the query in a log of queries received from mobile radio(s); and

a database update component configured to be operated by the processor that updates the base station database to include an entry for one of the detected base stations listed in the query that was identified as not being included in the base station database, the updating including determining position-related data for the entry by utilizing message passing on data included in the log of queries, the determining further including constructing a graph of nodes corresponding to locations to be determined and locations of detected based stations contained in the log of queries and by performing message passing between the nodes in the graph.

2. The system of claim 1, wherein the location component being implemented upon a central server that communicates with at least one mobile radio or other mobile sensor.

3. The system of claim 1, wherein the database update component adds and/or removes data related to one or more of the detected base stations from the base station database.

4. The system of claim 1, wherein the database update component utilizes a message passing algorithm to analyze accumulated queries.

5. The system of claim 4, wherein the database update component employs variables representing a state of the system and observations representing measurements.

6. The system of claim 1, further comprising the mobile radio that detects the base stations and provides the query to the location component.

7. The system of claim 1, wherein the base station database includes latitude and longitude information related to known base stations.

8. The system of claim 1, wherein the detected base stations include at least one of a Wi-Fi access point, a cellular tower, and an FM radio station.

17. The system of claim 1, wherein the location component is further configured to generate an estimated location for the mobile radio responsive to the query, the estimated location being generated based on identified locations related to one or more of the detected base stations included in the base station database.

18. The system of claim 1, wherein the position-related data is determined based at least in part on the estimated location for the mobile radio.

9. A method that facilitates maintaining a database of base station related information, comprising:

receiving a query that includes a listing of detected base stations from a mobile radio;

storing the query in a log of queries received from mobile radio(s);

updating the database to include an entry for one of the detected base stations listed in the query that was identified as not being included in the base station database, the updating including determining position-related data for the entry by utilizing message passing on data included in the log of queries, the determining further including constructing a graph of nodes corresponding to locations to be determined and locations of detected based stations contained in the log of queries and by performing message passing between the nodes in the graph.

10. The method of claim 9, wherein message passing further comprises:

estimating a state of one of the nodes;

passing an outgoing message along a connection between one of the nodes representing an observation and another of the nodes representing a variable, the variable corresponding to a location to be determined and the observation corresponding to a location of a detected base station;

re-estimating the state of the node having the estimated state;

recomputing the outgoing message; and

passing the recomputed message along the connection.

11. The method of claim 10, further comprising continuing to pass the message for a predetermined number of iterations.

12. The method of claim 10, further comprising terminating message passing after the state converges.

13. The method of claim 9, wherein the plurality of nodes include at least one node representing an observation and another node representing a variable, the variable corresponding to a location to be determined and the observation corresponding to a location of a detected base station.

14. The method of claim 13, wherein the state of the variable node is a corresponding location represented as a two dimensional grid.

19. The method of claim 9, further comprising:

identifying locations of the detected base stations determined to be included in the database of base station related information; and

generating an estimated location of the mobile radio based on the identified locations included in the database.

15. A system that passively updates a database, comprising:

a processor;

means operable by the processor for receiving a query that includes a listing of detected base stations from a mobile radio;

means operable by the processor for storing the query in a log of queries received from mobile radio(s); and

means operable by the processor for updating the database to include an entry for one of the detected base stations listed in the query that was identified as not being included in the base station database, the updating including determining position-related data for the entry by utilizing message passing on data included in the log of queries, the determining further including constructing a graph of nodes corresponding to locations to be determined and locations of detected based stations contained in the log of queries and by performing message passing between the nodes in the graph.

16. The system of claim 15, wherein the location component is configured to generate the estimated location by utilizing a triangulation technique.