Location determination using generalized fingerprinting

• US 9,020,869 B2
• Filed: 10/15/2013
• Issued: 04/28/2015
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Sundararajan, Arjun, Lin, Jyh-Han
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US14/053,807
• Publication Number:
  US 20140040175A1
• Time in Patent Office: 560 Days
• Field of Search: None
• US Class Current: 706/15
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G06F 30/23 using finite element methods [FEM] or finite difference methods [FDM]
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: H04L 12/6418 Hybrid transport

Abstract

An RF fingerprinting methodology is generalized to include non-RF related factors. For each fingerprinted tile, there is an associated distance function between two fingerprints (the training fingerprint and the test fingerprint) from within that tile which may be a linear or non-linear combination of the deltas between multiple factors of the two fingerprints. The distance function for each tile is derived from a training dataset corresponding to that specific tile, and optimized to minimize the total difference between real distances and predicted distances. Upon receipt of an inference request, a result is derived from a combination of the fingerprints from the training dataset having the least distance per application of the distance function. Likely error for the tile is also determined to ascertain whether to rely on other location methods.

Claims

1. A method comprising:

constructing a training data set and a test data set by using input data comprising location information and non-location related information;

using the training data set and the test data set to generate a first set of performance analytics, the first set of performance analytics generated by executing a first location determination procedure;

using the training data set and the test data set to generate a second set of performance analytics, the second set of performance analytics generated by executing a second location determination procedure; and

determining from at least the first set of performance analytics and the second set of performance analytics that one of the first location determination procedure or the second location determination procedure performs better than the other of the first location determination procedure or the second location determination procedure.

2. The method of claim 1, wherein the location information comprises RF-based location information, and wherein the non-location related information comprises non-RF related factors.

3. The method of claim 2, wherein the non-RF related factors include one or more of horizontal estimated position error information, device type information, client identification data, device speed, or an operating system.

4. The method of claim 1, further comprising:

generating pairwise analytics data from the first set of performance analytics and the second set of performance analytics; and

determining that one of the first location determination procedure or the second location determination procedure performs better than the other of the first location determination procedure or the second location determination procedure based on the pairwise analytics data.

5. The method of claim 4, wherein analyzing the pairwise analytics data comprises analyzing an error difference in one or more tiles of a grid representing a location.

6. The method of claim 5, wherein analyzing the pairwise analytics data indicates an anomaly.

7. The method of claim 6, wherein upon detecting the anomaly, at least one parameter used in at least one of the first location determination procedure or the second location determination procedure is changed to a different parameter prior to re-executing the at least one of the first location determination procedure or the second location determination procedure.

8. The method of claim 6, wherein upon detecting the anomaly, raw data associated with the location information is debugged.

9. The method of claim 1, wherein executing the first location determination procedure comprises running a first algorithm, and wherein executing the second location determination procedure comprises running a second algorithm that is different than the first algorithm.

10. The method of claim 1, wherein the location information is a crowd-sourced location observation.

11. A system comprising:

a memory associated with a computing device, said memory storing data comprising one or more location observations and one or more non-RF related factors; and

a processor programmed to;

execute a dataset constructor to construct a training data set and a test data set using the one or more location observations and the one or more non-RF related factors;

execute a plurality of experiments to generate comparative analytics, wherein executing a first experiment of the plurality of experiments comprises;

applying a first modeling algorithm and a first location inference algorithm to at least a portion of the test data set; and

generating a first set of accuracy analytics from applying the first modeling algorithm and the first location inference algorithm to the at least a portion of the test data set;

 

and further wherein executing a second experiment of the plurality of experiments comprises;

applying a second modeling algorithm and a second location inference algorithm to the at least a portion of the test data set; and

generating a second set of accuracy analytics from applying the second modeling algorithm and the second location inference algorithm to the at least a portion of the test data set; and

execute one or more analytic scripts on each of the first and the second set of accuracy analytics to obtain respective location, tile, and world accuracy analytics.

12. The system of claim 11, wherein the processor is further programmed to execute one or more of a multi-way comparative analysis, a pairwise comparative analysis, a delta comparative analysis, or a correlation comparative analysis on the respective location, tile, and world accuracy analytics.

13. The system of claim 11, wherein the one or more non-RF related factors include one or more of horizontal estimated position error information, device type information, client identification data, device speed, or an operating system.

14. The system of claim 11, wherein the one or more location observations include a crowd-sourced location observation.

15. A system comprising:

a memory associated with a computing device, the memory storing data comprising a training data set and a test data set constructed by using input data comprising location information and non-location related information; and

a processor programmed to;

use the training data set and the test data set to generate a first set of performance analytics, the first set of performance analytics generated by executing a first location determination procedure;

use the training data set and the test data set to generate a second set of performance analytics, the second set of performance analytics generated by executing a second location determination procedure; and

determine from at least the first set of performance analytics and the second set of performance analytics that one of the first location determination procedure or the second location determination procedure performs better than the other of the first location determination procedure or the second location determination procedure.

16. The system of claim 15, wherein the location information comprises RF-based location information, and wherein the non-location related information comprises non-RF related factors.

17. The system of claim 16, wherein the non-RF related factors include one or more of horizontal estimated position error information, device type information, client identification data, device speed, or an operating system.

18. The system of claim 15, wherein the processor is further programmed to:

generate pairwise analytics data from the first set of performance analytics and the second set of performance analytics; and

determine that one of the first location determination procedure or the second location determination procedure performs better than the other of the first location determination procedure or the second location determination procedure based on the pairwise analytics data.

19. The system of claim 18, wherein analyzing the pairwise analytics data comprises analyzing an error difference in one or more tiles of a grid representing a location.

20. The system of claim 15, wherein the location information is a crowd-sourced location observation.