Accuracy assessment for location estimation systems

• US 8,521,429 B2
• Filed: 06/17/2009
• Issued: 08/27/2013
• Est. Priority Date: 06/17/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sundararajan, Arjun, Barto, Michael
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): FIGUEROA, JAIME
• Application Number:
  US12/485,951
• Publication Number:
  US 20100324813A1
• Time in Patent Office: 1,532 Days
• Field of Search: 701/208, 701/532, 455/115.1, 455/115.3, 455/226.2, 455/404.2, 455/414.2, 455/456.1, 455/456.2, 455/457, 342/357, 342/385, 342/420, 342/446, 342/450, 342/451
• US Class Current: 701/532
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/02527 Detecting or resolving anomalies in the radio frequency fingerprints of the radio-map
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location

Abstract

Assessing the accuracy of location estimation systems. A mobile computing device provides location information including a device location (e.g., via GPS) and one or more wireless network beacons accessible by the computing device at the device location. The wireless network beacons accessible by the computing device are compared to stored post information including a plurality of beacon lists. An estimated device location is determined based on the comparison. The estimated device location is compared to the known device location. A difference between the estimated device location and the received device location is determined based on the comparison. An analysis of the determined difference is performed to generate accuracy maps and other insight into the relationship between accuracy and geographic area for the location estimation systems.

Claims

1. A system for assessing the accuracy of a location estimation system, said system comprising:

a memory area for storing post information including a plurality of locations each having a list of wireless network beacons accessible therefrom; and

a processor programmed to;

receive, from a mobile computing device, location information comprising a known device location associated with the mobile computing device, said location information further identifying one or more wireless network beacons accessible by the mobile computing device at the known device location;

search the post information stored in the memory area based on the identified wireless network beacons to identify one or more of the plurality of locations, the one or more of the plurality of locations being identified by comparing the received location information with the lists of wireless network beacons in the stored post information;

determine a location for the mobile computing device based on the identified one or more of the plurality of locations;

compare the determined location with the received known device location;

determine a difference between the determined location and the received known device location based on said comparing; and

modify the post information in the memory area as a function of the determined difference.

2. The system of claim 1, wherein the processor is further programmed to store the received known location information in the memory area as part of the post information.

3. The system of claim 1, wherein the processor is further programmed to:

quantify the determined difference; and

generate an accuracy map having represented thereon the quantified difference associated with the received known device location, the accuracy map being used in deciding deployment of location-based services at the received known device location.

4. The system of claim 1, further comprising means for using crowd-sourced data to determine the accuracy of the location estimation system.

5. The system of claim 1, further comprising means for obtaining the post information.

6. A method comprising:

receiving, from a computing device, location information comprising a device location associated with the computing device, said location information further identifying one or more wireless network beacons accessible by the computing device at the device location;

maintaining post information including a plurality of locations each having a list of wireless network beacons accessible therefrom;

comparing the received location information with the maintained post information to determine an estimated device location by comparing the identified wireless network beacons with the lists of wireless network beacons to determine the estimated device location;

comparing the estimated device location with the received device location;

determining a difference between the estimated device location and the received device location based on said comparing the estimated device location with the received device location; and

modifying said maintained post information based on said determined difference, the modifying comprising modifying one or more of the plurality of locations included in the maintained post information.

7. The method of claim 6, further comprising generating an accuracy map having represented thereon the determined difference associated with the received device location.

8. The method of claim 6, wherein receiving the location information comprises receiving one or more of the following:

crowd-sourced data and war driving data.

9. The method of claim 6, wherein the estimated device location is determined from a matched beacon list from the post information, the matched beacon list comprising data related to a pre-defined threshold quantity of beacons.

10. The method of claim 6, wherein comparing the received location information with the maintained post information comprises:

defining a location for each of the identified wireless network beacons based at least on the maintained post information; and

determining the estimated device location based on the defined locations.

11. The method of claim 10, wherein determining the estimated device location comprises triangulating the estimated device location based on the defined locations.

12. The method of claim 6, wherein determining the difference comprises defining an error distance between the received device location and the estimated device location.

13. The method of claim 6, further comprising defining an average accuracy radius for the received device location based on the maintained post information.

14. The method of claim 6, wherein receiving the location information comprises receiving a list of one or more wireless network beacons comprising one or more of the following:

a cellular network tower, a router, a wireless access point, and a network access point.

15. One or more computer memories storing computer-executable components, said components comprising:

an interface component that when executed by at least one processor causes the at least one processor to receive, from a computing device, location information comprising a device location associated with the computing device, said location information further identifying one or more wireless network beacons accessible by the computing device at the device location;

a memory component that when executed by at least one processor causes the at least one processor to maintain post information including a plurality of locations each having a list of wireless network beacons accessible therefrom;

an estimator component that when executed by at least one processor causes the at least one processor to define a location for each of the identified wireless network beacons based at least on the post information maintained by the memory component, said estimator component further determining an estimated device location based on the defined locations by comparing the identified wireless network beacons with the lists of wireless network beacons to determine the estimated device location;

an analytic component for comparing the estimated device location with the received device location to determine a difference between the estimated device location and the received device location; and

a feedback component for modifying said maintained post information based on said determined difference.

16. The computer memories of claim 15, wherein the memory component includes a post service.

17. The computer memories of claim 15, wherein the estimator component includes a query service.

18. The computer memories of claim 15, wherein the analytic component includes one or more performance counters.

19. The computer memories of claim 15, wherein the interface component receives the location information from a plurality of mobile computing devices, wherein the location information represents crowd-sourced data.

20. The computer memories of claim 15, wherein the analytic component ranks the plurality of locations based on said determined difference.