Methods for determining the approximate location of a device from ambient signals

• US 7,319,877 B2
• Filed: 12/19/2003
• Issued: 01/15/2008
• Est. Priority Date: 07/22/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Horvitz, Eric J., Krumm, John C., Cermak, Gerald F., Youssef, Adel Amin AbdelAzim, Miller, Edward C.
• Primary Examiner(s): Anderson; Matthew
• Assistant Examiner(s): Pan; Yuwen
• Application Number:
  US10/742,208
• Publication Number:
  US 20050020278A1
• Time in Patent Office: 1,488 Days
• Field of Search: 4554561- 6, 455/457, 342/387, 342/357.1
• US Class Current: 455/456.3
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G08G 1/0962 having an indicator mounted inside the vehicle, e.g. giving voice messages
• CPC Class Codes: G08G 1/0967 Systems involving transmission of highway information, e.g. weather, speed limits transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/096716 where the received information does not generate an automatic action on the vehicle control
• CPC Class Codes: G08G 1/096741 where the source of the transmitted information selects which information to transmit to each vehicle
• CPC Class Codes: G08G 1/096775 where the origin of the information is a central station

Abstract

The present invention leverages changes in the sensed strength of radio signals at different locations to determine a device'"'"'s location. In one instance of the invention, inference procedures are used to process ambient commercial radio signals, to estimate a location or a probability distribution over the locations of a device. In an instance of the invention, learning and inference methods are applied to rank vector of signal strength vectors. Moving to such rank orderings leads to methods that bypass consideration of absolute signal strengths in location calculations. The invention facilitates approximations for locating a device by providing a method that does not require a substantial number of available ambient signal strengths while still providing useful location inferences in determining locations.

Claims

1. A method for determining device location, comprising:

receiving a plurality of ambient signal strengths;

optimizing at least one subset of the ambient signal strengths to substantially reduce their number, optimizing the ambient signal strengths comprises calculating at least one Pearson'"'"'s correlation coefficient between pairs of ambient signals based on spatially corresponding signal sources, selecting a correlation threshold value, determining groups of signals that correlate greater than the correlation threshold value and choosing an ambient signal from each group with a highest average signal strength to represent that group; and

determining an approximate location of a device based, in part, upon relative signal strengths of at least the optimized subset of the ambient signal strengths.

2. The method of claim 1, determining the approximate location of the device further comprising:

computing at least one rank vector of at least one subset of the ambient signal strengths to establish relative ranking;

generating a unique rank hash code from the rank vector for each permutation of respective ambient signal strengths; and

compiling at least one histogram of at least one rank hash code to facilitate in classifying the approximate location of the device.

3. The method of claim 2, computing the rank vector based on a sort routine.

4. The method of claim 2, further comprising:

utilizing a smoothing technique on at least one histogram.

5. The method of claim 4, the smoothing technique comprising:

obtaining fine grid cell information relating to the ambient signal strengths for an area of interest;

computing at least one coarse grid cell histogram based on underlying fine grid cells;

normalizing the coarse grid cell histograms;

selecting a correlation threshold value, ρ

_s, to facilitate smoothing;

determining which bins of the coarse grid cell histograms have Spearman correlation coefficients above the correlation threshold value;

locating a maximum value over all the histogram bins that have a Spearman correlation coefficient above the correlation threshold value; and

replacing the histogram bin'"'"'s value in each histogram bin above the correlation threshold value with the maximum value.

6. The method of claim 5, the correlation threshold value is approximately equal to 0.9.

7. The method of claim 5, the fine grid cell information is obtained from an ambient signal strength simulation component.

8. The method of claim 7, the ambient signal strength simulation component comprising RadioSoft'"'"'s ComStudy program.

9. The method of claim 5, the fine grid cell information obtained from transporting the device to each fine grid cell of interest.

10. The method of claim 1 the correlation threshold value is approximately equal to 0.95.

11. The method of claim 1 further comprising:

storing the approximate location of the device in a retrievable space;

selecting a variable smoothing value for the device location representative of a set of prior signal strength scans; and

utilizing a most frequently inferred location over the set of prior signal strength scans as the current approximate location of the device.

12. The method of claim 11, the variable smoothing value comprising a temporal window, K, representing a number of signal scans over a period of time.

13. The method of claim 1, determining a location further comprising:

approximating a discrete probability distribution of signal strength information obtained from a particular location.

14. The method of claim 13, determining a location further comprising:

inferring an approximate location of the device based, in part, on the approximated discrete probability distribution.

15. The method of claim 13, approximating a discrete probability distribution further comprising:

positioning a device in a particular location;

obtaining ambient signal strengths from at least one signal emitter;

computing ranking information of at least a subset of the ambient signal strengths; and

determining a normalized histogram of the ranking information at the particular location.

16. The method of claim 15, the ranking information comprising rank hash codes.

17. The method of claim 1, the ambient signal strengths comprising radio frequency (RF) signal strengths.

18. The method of claim 1, determining the approximate location of the device further based, at least in part, on utilizing at least one input from at least one user.

19. The method of claim 18, the inputs comprising at least one selected from the group consisting of at least one user constraint and at least one user feedback.

20. The method of claim 19, the user constraint comprising at least one geographical area.

21. The method of claim 19, the user feedback comprising at least one indication by at least one user as to correctness of the approximate location of the device.

22. The method of claim 1, further comprising:

utilizing signal strength simulation to facilitate in determining the approximate location of the device.

23. The method of claim 22, further comprising:

employing statistical classifiers to facilitate in compensating for pertinent characteristics of the signal strength simulation.

24. The method of claim 23, the pertinent characteristics comprising at least one selected from the group consisting of reliability, biases between actual sensed signal strengths and simulated values, and behavior with regard to topological features and structures.

25. The method of claim 1, further comprising:

employing persistence information to facilitate in determining the approximate location of the device.

26. The method of claim 25, the persistence information comprising a last known confident inference of the approximate location of the device and a time since the last known confident inference was determined.

27. The method of claim 26, further comprising:

utilizing the last known confident inference as the approximate location of the device when the time since the last known confident inference is below a threshold time value.

28. A device employing the method of claim 1 comprising at least one selected from the group consisting of a computer, a server, a wearable electronic device, an affixable electronic device, and a handheld electronic device.