Prediction of indoor level and location using a three stage process

• US 8,700,054 B2
• Filed: 06/10/2011
• Issued: 04/15/2014
• Est. Priority Date: 06/10/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed
• Primary Examiner(s): Kincaid, Lester
• Assistant Examiner(s): Lai, Daniel
• Application Number:
  US13/157,802
• Publication Number:
  US 20120315918A1
• Time in Patent Office: 1,040 Days
• Field of Search: 4554561-457, 701400-541, 340988-996, 342450-465
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A mobile computing device may be localized in an indoor area based on the strength of wireless network signals accessible in the indoor area from different access points. For efficiency, the localization may be performed in stages. In a first stage, a general geographic area, such as an “island” as will be described below, in which the mobile device is located is identified. In a second stage, an altitude or building level of the mobile device is identified. In a third stage, a position of the mobile device on the identified building level is determined. At least some of these stages of localization may utilize information received at the mobile device from surrounding access points. For example, the island on which the user is located may be determined by identifying at least one access point on that island. Further, decision trees may be executed using input related to a received signal strength from the surrounding access points, and outputs of the decision trees may indicate the device'"'"'s location.

Claims

1. A method, comprising:

defining one or more islands, each island being a subdivision of a geographical region and including one or more access points, where any access point in an island is likely not visible outside that island;

maintaining identifiers of the access points associated with each island;

building for each island, using a processor, a first classifier, the first classifier including one or more decision trees executable using at least one signal received by a mobile device, the output of the one or more decision trees of the first classifier indicating a level of the indoor area; and

building for each level, using the processor, a second classifier, a second classifier including one or more decision trees executable using the at least one signal received by the mobile device, the output of the one or more decision trees of the second classifier indicating a position on the level.

2. The method of claim 1, wherein the islands comprise groups of floors in a building.

3. The method of claim 1, wherein the islands comprise individual buildings.

4. The method of claim 1, wherein the islands comprise groups of buildings.

5. The method of claim 1, wherein the one or more decision trees included in the first and second classifiers comprise:

starting nodes, the starting nodes presenting first questions related to received signal strengths of access points; and

intermediate nodes, each intermediate node presenting an additional question related to the received signal strengths of access points.

6. The method of claim 5, wherein the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values.

7. The method of claim 1, further comprising:

building a plurality of first decision trees for inclusion in the first classifier; and

averaging results from the plurality of first decision trees.

8. The method of claim 1, further comprising:

building a plurality of second decision trees for inclusion in the second classifier; and

averaging results from the plurality of second decision trees.

9. The method of claim 1, further comprising:

receiving from a mobile device an identifier of at least one access point;

comparing the received identifier to the maintained identifiers to determine the island in which the mobile device is located.

10. The method of claim 1, wherein the position indicated by the second classifier is a latitude or longitude.

11. The method of claim 1, wherein the position indicated by the second classifier is provided as coordinates relative to a layout of the indoor area.

12. The method of claim 1, wherein the position indicated by the second classifier is provided graphically on a display.

13. The method of claim 1, further comprising:

receiving at a mobile device signals from one or more access points;

determining, using the received signals, the access point island in which the mobile device is located;

downloading to the mobile device the first classifier;

executing the first classifier using the received signals;

downloading to the mobile device the second classifier; and

executing the second classifier using the received signals.

14. A system for determining a location of a mobile device within an indoor area, comprising:

a memory storing identifiers of a set of access points associated with an island, where the access points in an island are likely not visible outside that island; and

a processor configured to;

build, for each island, a first classifier including one or more decision trees executable using a signal by a mobile device, the output of the one or more decision trees of the first classifier indicating a level of the indoor area; and

build, for each level, a second classifier including one or more decision trees executable using the signal received by the mobile device, the output of the one or more decision trees of the second classifier indicating a position on the level.

15. The system of claim 14, wherein the island comprises a group of floors in a building.

16. The system of claim 14, wherein the island comprises a building.

17. The system of claim 14, wherein the island comprises a group of buildings.

18. The system of claim 14, wherein the one or more decision trees included in the first and second classifiers comprise:

starting nodes, the starting nodes presenting first questions related to received signal strengths of access points;

and intermediate nodes, each intermediate node presenting an additional question related to the received signal strengths of access points.

19. The system of claim 18, wherein the first and additional questions ask whether the received signal strength of one or more particular access points is above or below one or more predetermined values.

20. The system of claim 14, wherein the processor is further configured to:

build a plurality of first decision trees for inclusion in the first classifier; and

average results from the plurality of first decision trees.

21. The system of claim 14, wherein the processor is further configured to:

build a plurality of second decision trees for inclusion in the second classifier; and

average results from the plurality of second decision trees.

22. A method for predicting location of a mobile device in an indoor area, comprising:

receiving signals from one or more access points;

determining, using the received signals, an access point island in which the mobile device is located;

downloading a first decision tree corresponding to the access point island, wherein an output of the first decision tree indicates a level of the indoor area; and

executing the first decision tree using the received signals;

downloading a second decision tree corresponding to the level of the indoor area, wherein an output of the second decision tree indicates a position on the level; and

executing the second decision tree using the received signals.