LOCATION DETERMINATION BASED ON WEIGHTED RECEIVED SIGNAL STRENGTHS

• US 20130023282A1
• Filed: 10/04/2011
• Published: 01/24/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
• Granted Patent: US 8,559,975 B2
• Time in Patent Office: Days
• 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 a device, the method comprising:

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

assigning the observations to at least one geographic area of a plurality of geographic areas based on the observation locations associated with each of the 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 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 observation comprises an RSS measurement.

3. The method of claim 1, further comprising comparing the determined device location estimate to the observation location of the device corresponding to the 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 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 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 observations, each of the 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 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 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 8, 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.

15. A computer-readable medium comprising computer readable instructions for determining the location of a device, the computer-readable instructions comprising instructions that:

construct a training data set and a test data set from location data comprising a plurality of observations;

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

create a model from the training data set and the optimal weighted function; and

service an inference request corresponding to the plurality of tiles using the distance function.

16. The computer-readable medium of claim 15, wherein the instructions that service the inference request further comprise instructions that select a subset of beacons from the model that corresponds to the inference request.

17. The computer-readable medium of claim 15, further comprising instructions that determine an error curve based on a weighted function and the test data.

18. The computer-readable medium of claim 17, further comprising instructions that determine if the error curve indicates either inadequate accuracy or adequate accuracy.

19. The computer-readable medium of claim 18, further comprising instructions that, if determined that the error curve indicates inadequate accuracy, falls back to a non-weighted function.

20. The computer-readable medium of claim 18, further comprising instructions that, if determined that the error curve indicates adequate accuracy, creates cache data for a device.