Selecting beacons for location inference

• US 8,618,984 B2
• Filed: 03/19/2010
• Issued: 12/31/2013
• Est. Priority Date: 03/19/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Jyh-Han, Chu, Lon-Chan, Seshadri, Aravind Krishnamachari, Ghosal, Prasanta, Rice, Christopher Russell, Pachlag, Anup Kashinath
• Primary Examiner(s): Issing, Gregory C
• Application Number:
  US12/727,901
• Publication Number:
  US 20110227791A1
• Time in Patent Office: 1,383 Days
• Field of Search: 342/386, 342/450, 342/451, 342/463, 342/464
• US Class Current: 342/451
• CPC Class Codes: G01S 5/02529 not involving signal parameters, i.e. only involving identifiers
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

Location inference using selected beacons. Data is received representing a set of beacons observed by a computing device. The beacons are located within a first geographic area. A subset (e.g., a clique) of the beacons is selected based on a coverage area of each of the beacons, where each of the beacons in the selected subset has a coverage area that overlaps with the coverage area of each of the other beacons in the selected subset. Using known or estimated positions of the beacons, a second geographic area is defined based on the selected subset of beacons and the beacon reference data and the coverage areas associated therewith. The second geographic area, smaller than the first geographic area, represents an approximate location of the computing device. In some embodiments, the computing device is calculated to be within the second geographic area with 95% probability.

Claims

1. A system for selecting beacons from which to infer a location of a mobile computing device, said system comprising:

a memory area for storing a set of beacon identifiers, said beacon identifiers corresponding to beacons observed by a mobile computing device, said beacons being located within a first geographic area as observed by the mobile computing device, said memory area further storing beacon reference data and a confidence circle associated with each of the beacon identifiers, the confidence circle representing a degree of confidence in the beacon reference data corresponding to the beacon; and

a processor programmed to;

receive the set of beacon identifiers from the mobile computing device;

identify, based on the beacon reference data stored in the memory area, one or more of the beacon identifiers corresponding to outlying beacons located on an edge of the first geographic area, the outlying beacons being identified based on the beacon reference data associated with the beacons;

remove the identified beacon identifiers from the set of beacon identifiers stored in the memory area;

select, from the set of beacon identifiers and based on the confidence circles associated therewith stored in the memory area, a subset of beacon identifiers corresponding to beacons whose confidence circles each overlap with each other; and

determine a second geographic area based on the selected beacon identifiers and the beacon reference data and the confidence circles associated therewith, said mobile computing device being within the second geographic area, wherein the second geographic area is smaller than the first geographic area.

2. The system of claim 1, wherein each confidence circle stored in the memory area corresponds to a radius of a circle associated with at least one of the beacon identifiers.

3. The system of claim 2, wherein the circle represents an inferred location of the mobile computing device with the degree of confidence.

4. The system of claim 1, wherein the processor is programmed to determine the second geographic area by triangulation when the second geographic area is determined from at least three beacons.

5. The system of claim 1, wherein the processor is programmed to select the subset of beacon identifiers by determining a maximum complete clique of the beacon identifiers.

6. The system of claim 1, wherein the processor is programmed to provide the determined second geographic area to the mobile computing device.

7. The system of claim 1, wherein the processor is programmed to determine the second geographic area by inferring a smallest circle based on the selected subset of beacon identifiers and the beacon reference data and the confidence circles associated therewith, the smallest circle being inferred from the overlapping confidence circles of the beacons.

19. The system of claim 1, wherein the processor is programmed to determine a center of the second geographic area and provide to the mobile computing device as an approximate location of the mobile computing device.

8. A method comprising:

receiving data representing a set of beacons from a computing device, said beacons being observed by the computing device, said beacons being located within a first geographic area as observed by the computing device;

selecting a subset of the beacons based on confidence circles of each of the beacons, wherein the confidence circles of each of the beacons in the selected subset overlap with each other, the confidence circles representing a degree of confidence in beacon reference data corresponding to the respective beacon;

accessing the beacon reference data associated with each of the beacons; and

defining a second geographic area based on the selected subset of beacons and the beacon reference data and the confidence circles associated therewith, said computing device being within the second geographic area, wherein the second geographic area is smaller than the first geographic area.

9. The method of claim 8, further comprising providing the defined geographic area to the computing device as an approximate location of the computing device.

10. The method of claim 8, further comprising:

identifying, based on the accessed beacon reference data, one or more beacons from the set of beacons corresponding to outlying beacons located on an edge of the first geographic area, the outlying beacons being identified based on the beacon reference data associated with the beacons; and

removing the identified beacons from the set of beacons.

11. The method of claim 8, further comprising identifying, from the set of beacons based on the beacon reference data, one or more beacons corresponding to beacons located near a center of the first geographic area, and wherein selecting the subset of the beacons comprises selecting a subset of the identified beacons.

12. The method of claim 8, wherein selecting the subset of the beacons comprises determining a maximally complete set of the beacon identifiers, the maximally complete set of the beacon identifiers representing a clique with the most beacons relative to other cliques of beacons.

13. The method of claim 8, wherein selecting the subset of the beacons comprises determining a clique of the beacon identifiers.

14. The method of claim 8, further comprising storing the defined second geographic area as a location of the computing device.

15. The method of claim 8, wherein defining the second geographic area comprises inferring a smallest circle based on the selected subset of beacons and the beacon reference data and the confidence circles associated therewith, the smallest circle being inferred from the overlapping confidence circles of the selected subset of beacons.

16. One or more computer storage media storing computer-executable components, said components comprising:

an interface component that when executed by at least one processor causes the at least one processor to receive data representing a set of beacons, said beacons being observed by a computing device, said beacons being located within a first geographic area as observed by the computing device, said beacons having beacon reference data associated therewith describing a location of the beacons;

a filter component that when executed by at least one processor causes the at least one processor to select no more than a first predefined quantity of the beacons based on a confidence circle of each of the beacons, the confidence circle representing a degree of confidence with which the computing device is located in the confidence circle;

a clique component that when executed by at least one processor causes the at least one processor to identify no more than a second predefined quantity of the selected beacons whose confidence circles each overlap with each other; and

an inference component that when executed by at least one processor causes the at least one processor to define a second geographic area based on the identified beacons and the beacon reference data and the confidence circles associated therewith, said computing device being within the defined second geographic area, and wherein the second geographic area is smaller than the first geographic area.

17. The computer storage media of claim 16, wherein the first predefined quantity is seven and the second predefined quantity is three.

18. The computer storage media of claim 16, wherein the clique component determines a maximally complete set of the selected beacons.

20. The computer storage media of claim 16, wherein the filter component selects the first predefined quantity of the beacons having the smallest confidence circles.