Indoor localization of mobile devices

• US 8,599,758 B1
• Filed: 04/20/2011
• Issued: 12/03/2013
• Est. Priority Date: 04/20/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ogale, Abhijit, Rivlin, Ehud
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): LOPATA, ROBERT J
• Application Number:
  US13/090,710
• Time in Patent Office: 958 Days
• Field of Search: 370/310, 370/328, 370/338, 455/403, 455/422.1, 455/456.1, 455/456.2
• US Class Current: 370/328
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 4/38 for collecting sensor information

Abstract

Aspects of this disclosure provide systems and methods for generating models of a wireless network environment in an indoor space which may be used to predict an indoor location. The disclosure relates to collecting wireless network access point identifier information and power level observed at various locations are collected to generate various signal maps. The signal maps may be used to generate models of the indoor space. In one example, a voting model may use a probability distribution of a plurality of signal maps in order to identify a location with a highest probability of overlap with current signals received at a client device. Once a location has been identified, it may be used to assist with any number of navigational functions, such as providing turn by turn directions to another indoor location, for example, a conference room or exit, or simply providing information about the current location.

Claims

1. A method comprising:

receiving a set of voting maps, each voting map of the set of voting maps including a wireless network access point identifier and signal strength data;

scanning for wireless network signals to identify scan results including one or more wireless network access point identifiers and associated signal strengths;

associating the scan results with a timestamp;

quantizing, by a processor, the signal strengths of the identified one or more wireless network access point identifiers to obtain quantized identified signal strengths;

selecting one or more voting maps of the set of received voting maps based upon the identified one or more wireless network access point identifiers;

combining the selected one or more voting maps into a cumulative voting map;

normalizing the cumulative voting map to obtain a probability distribution over location;

propagating the probability distribution from a previous timestamp using a motion model; and

identifying, by the processor, the current location of a client device based on the propagated distribution.

2. The method of claim 1, wherein identifying the current location of the client device is based on a previous location of the client device and the motion model is an isotropic diffusion model.

3. The method of claim 1, wherein identifying the current location of the client device is based on a previous location of the client device and the motion model is an anisotropic diffusion model based on directional motion information.

4. The method of claim 3, further comprising receiving input from a directional device, wherein the anisotropic diffusion model is based on the received input.

5. The method of claim 1, wherein the set of voting maps is associated with a floor of a building.

6. The method of claim 1, wherein the motion model is based on sensor input received from an accelerometer.

7. The method of claim 1, wherein the motion model is based on sensor input received from a gyroscope.

8. The method of claim 1, further comprising combining the propagated distribution with a current probability distribution to obtain a combined probability distribution, and wherein the current location of the client device is identified based on the combined probability distribution.

9. The method of claim 1, wherein the wireless network access point identifiers is a MAC address.

10. A device for determining a current location of the device, the device comprising:

memory;

a processor to;

collect one or more wireless network access point identifiers and signal strengths associated with the one or more wireless network access point identifiers for an indoor geographic area;

quantize the collected signal strengths into a plurality of quantized collected signal strengths for each associated wireless network access point identifiers;

generate a voting map for each wireless network access point identifier and quantized collected signal strength;

store each voting map in the memory;

scan for wireless network signals to identify scan results including one or more wireless network access point identifiers and associated signal strengths;

associate the scan results with a timestamp;

quantize the signal strengths of the identified one or more wireless network access point identifiers to obtain quantized identified signal strengths;

select one or more voting maps based upon the identified one or more wireless network access point identifiers;

combine the selected one or more voting maps into a cumulative voting map;

normalize the cumulative voting map to obtain a probability distribution over location;

propagate the probability distribution from a previous timestamp using a motion model; and

identify the current location of the device based on the propagated distribution.

11. A device for determining a current location of the device, the device comprising:

memory storing a set of voting maps, each voting map of the set of voting maps including a wireless network access point identifier and signal strength data; and

a processor to;

scan for wireless network signals to identify scan results including one or more wireless network access point identifiers and associated signal strengths;

associate the scan results with a timestamp;

quantize the signal strengths of the identified one or more wireless network access point identifiers to obtain quantized identified signal strengths;

select one or more voting maps based upon the identified one or more wireless network access point identifiers;

combine the selected one or more voting maps into a cumulative voting map;

normalize the cumulative voting map to obtain a probability distribution over location;

propagate the probability distribution from a previous timestamp using a motion model; and

identify the current location of the device based on the propagated distribution.

12. The device of claim 11, wherein the processor identifies the current location of the device based on a previous location of the device and the motion model is an isotropic diffusion model.

13. The device of claim 11, wherein the processor identifies the current location of the device based on a previous location of the device and the motion model is an anisotropic diffusion model based on directional motion information.

14. The device of claim 13, wherein the processor receives input from a directional device and the anisotropic diffusion model is based on the received input.

15. The device of claim 11, wherein the set of voting maps is associated with a floor of a building.

16. The device of claim 11, wherein the motion model is based on sensor input received from an accelerometer.

17. The device of claim 11, wherein the processor combines the propagated distribution with a current probability distribution to obtain a combined probability distribution, and the processor identifies the current location of the device based on the combined probability distribution.

18. The device of claim 11, wherein the wireless network access point identifiers is a MAC address.