Location determination based on weighted received signal strengths

• US 8,559,975 B2
• Filed: 10/04/2011
• Issued: 10/15/2013
• Est. Priority Date: 07/22/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Jyh-Han, Basu, Pradipta Kumar
• Primary Examiner(s): Htun, San
• Assistant Examiner(s): Elhag, Magdi
• Application Number:
  US13/252,605
• Publication Number:
  US 20130023282A1
• Time in Patent Office: 742 Days
• Field of Search: 455/456.1, 455/404.2, 455/41.2, 34235731-35749
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/02525 Gathering the radio frequency fingerprints

Abstract

Training datasets and test datasets consisting of observations (i.e., RSS measurements) partitioned per a mapping tile system are used to evaluate possible RSS weighting functions for each such tile. The observations from the training dataset are used to determine an optimal weighting function based on the training dataset that minimizes the error for the test data, wherein the error may be a function of the deltas between GPS positions of observations in the test dataset and predicted positions from the RSS weighted functions applied to test data. The accuracy of the optimal weighted function for each tile is characterized to determine whether to use the weighted function or an alternative (such as a non-weighted function) for subsequent inquiries.

Claims

1. A method of location determination for performance by a device comprising a processor, the method comprising:

dividing a plurality of crowd-sourced location observations into a training dataset and a test dataset, each of the crowd-sourced location observations comprising an observation location corresponding to each device from among a plurality of computing devices;

assigning the crowd-sourced location observations to at least one geographic area of a plurality of geographic areas based on the observation locations associated with each of the crowd-sourced location observations and a corresponding location associated with each of the geographic areas;

determining a plurality of possible received signal strength (RSS)-based weighted functions for each geographic area based on at least one crowd-sourced location observation corresponding to each geographic area; and

determining an optimal weighted function from among the plurality of possible RSS-based weighted functions based on the training dataset and the testing dataset.

2. The method of claim 1, wherein the at least one crowd-sourced location observation comprises an RSS measurement.

3. The method of claim 1, further comprising comparing a determined device location estimate to the observation location of the device corresponding to the crowd-sourced location observation in the test dataset to calculate an accuracy value.

4. The method of claim 3, further comprising discarding the optimal weighted function based on a threshold limit.

5. The method of claim 1, wherein each of the crowd-sourced location observations further comprises a set of beacons observed by each device from among the plurality of computing devices, and wherein each RSS measurement is for each beacon among each set of beacons, the method further comprising, prior to the dividing, confirming that each RSS value is both available and validated.

6. The method of claim 1, further comprising, prior to the assigning, filtering each crowd-sourced location observation to remove any RSS value that does not meet a predetermined minimum threshold.

7. The method of claim 1, further comprising utilizing the optimal weighted function to determine a location for a request device.

8. A system for determining a location of a device, the system comprising:

a memory area associated with a computing device, said memory area storing location data comprising a plurality of crowd-sourced location observations, each of the crowd-sourced location observations including a set of beacons observed by one of a plurality of mobile computing devices and a received signal strength (RSS) measurement for each beacon and an observation location of the mobile computing device, said location data including training data and test data; and

a processor programmed to;

divide the location data into a training dataset and a test dataset;

assign the location data to at least one geographic area based on the observation locations associated with each of the crowd-sourced location observations and a location associated with each of the geographic areas;

determine a plurality of possible RSS-based weighted functions for each geographic area based on the crowd-sourced location observations corresponding to each geographic area; and

determine an optimal weighted function from among the plurality of possible RSS-based weighted functions based on the training dataset and the testing dataset.

9. The system of claim 8, wherein the at least one geographic area is a mapping tile system.

10. The system of claim 8, wherein the optimal weighted function is a weighted function from among the plurality of possible RSS-based weighted functions that has a lowest error.

11. The system of claim 10, wherein the error is calculated as a function of deltas between a plurality of RSS data comprising the test dataset.

12. The system of claim 8, wherein the optimal weighted function gives the greatest weight to a beacon with the strongest RSS.

13. The system of claim 8, wherein the optimal weighted function is derived using only RSS values that exceed a predetermined minimum threshold.

14. The system of claim 8, wherein the optimal weighted function is derived using only locations from a GPS receiver.