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

• US 7,738,881 B2
• Filed: 12/19/2003
• Issued: 06/15/2010
• Est. Priority Date: 07/22/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cermak, Gerald F., Youssef, Adel Amin AbdelAzim, Miller, Edward C., Horvitz, Eric J., Krumm, John C.
• Primary Examiner(s): Phan; Huy
• Assistant Examiner(s): Heiber; Shantell
• Application Number:
  US10/741,783
• Publication Number:
  US 20050020277A1
• Time in Patent Office: 2,370 Days
• Field of Search: 455/456.1, 455/456.2, 455/456.3, 455/456.5, 455/456.6, 455/404.2, 455/63.4, 455/556, 342/357, 342/450, 342/457, 342/451, 342/357.01, 342/357.08, 340/993
• US Class Current: 455/456.1
• 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, comprising:

a signal component that receives a plurality of ambient signals from a plurality of commercial FM radio station transmitters that each provide at least one ambient signal used by a device to determine at least one approximate location of the device;

a ranking component that computes a rank vector of at least the subset of the ambient signals based at least in part on relative signal strengths between the subset of ambient signals and maps the rank vector to an integer;

an analysis component that infers the at least one approximate location of the device based, in part, on comparing the integer to a plurality of hash codes related to one or more disparate permutations of the rank vector; and

a training component for training the analysis component based at least in part on the one or more hash codes corresponding to the one or more permutations of the rank vector and a related location, the one or more rank vectors are computed based at least in part on relative signal strength of the ambient radio signals at the related location;

wherein each ambient signal is associated with a commercial FM radio station.

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, the ranking component generates a unique rank hash code for each permutation of respective signal strengths.

16. The system of claim 15, 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.

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

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

19. The system of claim 17, the smoothing technique utilizes a correlation threshold value, ρ

_s.

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

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

22. 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.

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

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

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

26. 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.

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

28. The system of claim 1, the one or more disparate permutations of the rank vector relate to rank vectors computed from at least the subset of ambient signals at a plurality of corresponding locations.

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

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

31. 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.

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

35. 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.

32. A system, comprising:

means for receiving a plurality of disparate ambient radio signals, the disparate ambient radio signals are from a plurality of commercial FM radio station transmitters that each provide at least one ambient signal used by a device to determine at least one approximate location of the device;

means for computing a rank vector based at least in part on relative strength of the disparate ambient radio signals and mapping the rank vector to an integer;

means for inferring the approximate location of the device based, in part, on comparing the integer to one or more hash codes corresponding to one or more permutations of the rank vector; and

means for training the means for inferring based at least in part on the one or more hash codes corresponding to the one or more permutations of the rank vector and a related location, the one or more rank vectors are computed based at least in part on relative signal strength of the disparate ambient radio signals at the related location.

33. The system of claim 32, the disparate ambient radio signals comprising at least one radio frequency (RF) signal.

36. A system, comprising:

a signal component that receives a plurality of ambient signals from a plurality of commercial FM radio station transmitters that each provide at least one ambient signal used by a device to determine at least one approximate location of the device;

a ranking component that computes a rank vector of at least the subset of the ambient signals based at least in part on relative signal strengths between the subset of ambient signals and maps the rank vector to an integer;

an analysis component that infers the at least one approximate location of the device based, in part, on comparing the integer to a plurality of hash codes related to one or more disparate permutations of the rank vector; and

a training component for training the analysis component based at least in part on the one or more hash codes corresponding to the one or more permutations of the rank vector and a related location, the one or more rank vectors are computed based at least in part on relative signal strength of the ambient radio signals at the related location.