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

• US 20050020277A1
• Filed: 12/19/2003
• Published: 01/27/2005
• Est. Priority Date: 07/22/2003
• Status: Active Grant

• 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.
• Granted Patent: US 7,738,881 B2
• Time in Patent Office: Days
• US Class Current: 455/456.100
• CPC Class Codes: G01C 21/28 with correlation of data from several navigational instruments
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G01S 5/02521 using a radio-map
• 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 present 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 another instance of the present invention, a system utilizes learning and inference methods that are applied to rank vector of signal strength vectors. Moving to such rank orderings leads to systems that bypass consideration of absolute signal strengths in location calculations. The present invention facilitates approximations for locating a device by providing a system that does not require a substantial number of available ambient signal strengths while still providing useful location inferences in determining locations.

Claims

1. A system that facilitates determining location of a device, comprising:

a component that receives at least one ambient signal; and

an analysis component that infers at least one approximate location of a device based, in part, on relative signal strengths of at least a subset of the ambient signals.

2. The system of claim 1, the approximate location inferred by the analysis component being utilized by an entity in real-time.

3. The system of claim 1, the analysis component provides smoothing of at least one inferred approximate location of the device.

4. The system of claim 3, the smoothing comprising obtaining a most frequently inferred location over a variable number of prior signal strength scans.

5. The system of claim 4, the variable number comprising a temporal window, K, representing a number of signal scans over a period of time.

6. The system of claim 1, the analysis component provides optimization of the subset of ambient signals to substantially reduce their number.

7. The system of claim 6, the optimization utilizes a degree of correlation to facilitate in number reduction.

8. The system of claim 7, the degree of correlation comprising a Pearson'"'"'s correlation coefficient between pairs of ambient signals based on at least one spatially corresponding signal source location.

9. The system of claim 7, the optimization employs at least one correlation threshold value, ρ

.

10. The system of claim 9, the correlation threshold value is approximately equal to 0.95.

11. The system of claim 1, the ambient signal comprising at least one radio frequency (RF) signal.

12. The system of claim 11, the device can only receive RF signals.

13. The system of claim 11, the RF signals comprising at least one selected from the group consisting of 802.11 signals, amplitude modulation (AM) radio signals, frequency modulation (FM) radio signals, television broadcast signals, commercial radio signals, and military radio signals.

14. The system of claim 1, the ambient signal comprising at least one selected from the group consisting of an infrared signal, an x-ray signal, an infrasonic signal, a sonic signal, and an ultrasonic signal.

15. The system of claim 1 further comprising a ranking component that computes a rank vector of at least the subset of the ambient signals.

16. The system of claim 15, the ranking component generates a unique rank hash code for each permutation of respective signal strengths.

17. The system of claim 16, the analysis component utilizes at least one histogram of at least one rank hash code to facilitate in classifying the approximate location of the device.

18. The system of claim 17, the analysis component utilizes a smoothing technique on at least one histogram.

19. The system of claim 18, the smoothing technique comprising a process employing at least one Spearman correlation coefficient relating to at least one histogram.

20. The system of claim 18, the smoothing technique utilizes a correlation threshold value, ρ

_s.

21. The system of claim 20, the correlation threshold value is approximately equal to 0.9.

22. The system of claim 1, the analysis component approximates a discrete probability distribution of hash codes obtained at a particular location.

23. The system of claim 1, the analysis component utilizes, in a statistical analysis, at least one selected from the group consisting of time varying signal strengths from one or more signal emitters and static signal strengths from one or more signal emitters.

24. The system of claim 1, the analysis component utilizing at least one propagation model.

25. The system of claim 24, the propagation model comprising at least, in part, a terrain sensitive radio propagation model.

26. The system of claim 1 further comprising a global positioning system component (GPS).

27. The system of claim 1 further comprising a velocity component that determines or infers velocity of the device based, in part, on relative signal strengths of the subset of the ambient signals.

28. The system of claim 1 further comprising adaptively downloadable look-up tables.

29. The system of claim 1 further comprising a signal strength simulation component.

30. The system of claim 29, the signal strength simulation component provides signal strength data for at least one desired area to the analysis component.

31. The system of claim 30, the signal strength data comprising data based on grid system overlying the desired area.

32. The system of claim 1, the analysis component further utilizing at least one time-based information source to facilitate in determining the approximate location of the device.

36. A computer readable medium having stored thereon computer executable components of the system of claim 1.

37. A device employing the system 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.

33. A system that facilitates determining location of a device, comprising:

means for receiving device signals; and

means for inferring an approximate location of a device based, in part, on relative signal strengths of at least one ambient signal.

34. The system of claim 33, the ambient signal comprising a radio frequency (RF) signal.

35. A data packet transmitted between two or more computer components that facilitate locating a device, the data packet is comprised of, at least in part, information relating to a locating system that determines, based on at least one ambient frequency signal indicator, an approximation of a location of the device.