Modeling and location inference based on ordered beacon sets

• US 8,665,154 B2
• Filed: 05/13/2011
• Issued: 03/04/2014
• Est. Priority Date: 05/13/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lin, Jyh-Han, Basu, Pradipta Kumar
• Primary Examiner(s): LIU, HARRY K
• Application Number:
  US13/106,874
• Publication Number:
  US 20120286997A1
• Time in Patent Office: 1,026 Days
• Field of Search: 342/451
• US Class Current: 342/451
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting

Abstract

Embodiments order observed beacons based on relative signal strength to create a correspondence between beacon sets and positions. A computing device such as a mobile device provides a positioned observation including a plurality of observed beacons and a position of the mobile device during observation. The observed beacons are ordered based on quality indicators such as signal strength relative to each other. A set of the beacons are selected based on the ordering (e.g., the beacons with the strongest signal strength are selected in order). The position of the observing mobile device is associated with the beacon set to enable location inference for other devices providing observations including the same beacon set.

Claims

1. A system for inferring location using a beacon set selected based on signal strength, said system comprising:

a memory area associated with a computing device, said memory area storing at least one fingerprint having associated therewith beacons observed by the computing device, said memory area further storing a received signal strength indicator for each of the observed beacons; and

a processor programmed to;

rank the beacons based on the received signal strength indicators;

select, based on the beacon ranking, a beacon set including an ordered plurality of the beacons from the fingerprint stored in the memory area, said ordered plurality of the beacons having a high received signal strength indicator relative among the beacons;

transmit the selected beacon set to a location service via a network, said location service identifying a position associated with the selected beacon set based on a correspondence between positions and beacon sets derived from other computing devices;

receive, from the location service, the identified position associated with the transmitted beacon set; and

define a position of the computing device to be the received, identified position.

2. The system of claim 1, wherein the processor ranks the beacons by eliminating beacons with low received signal strength indicators relative among the beacons.

3. The system of claim 1, wherein the selected beacon set represents a spatial region defined by the beacons associated with the selected beacon set, and wherein the received, identified position represents a centroid of the spatial region.

4. The system of claim 1, wherein the selected beacon set represents a virtual beacon.

5. The system of claim 1, further comprising means for inferring location using the beacon set selected based on the received signal strength indicators.

6. The system of claim 1, further comprising means for creating a beacon store correlating positions with beacon sets each including a plurality of beacons ordered by signal strength.

7. A method comprising:

accessing a positioned observation associated with a computing device, said positioned observation having associated therewith beacons observed by the computing device, one or more quality indicators for each of the observed beacons, and a position of the computing device;

selecting a plurality of the beacons based on the quality indicators relative among the beacons;

associating the position with the selected plurality of the beacons; and

storing the selected plurality of the beacons and associated position in a memory area,

wherein said accessing, said selecting, said associating, and said storing are performed by the computing device or a cloud service.

8. The method of claim 7, wherein the selected beacons are ordered in a decreasing order of quality indicators.

9. The method of claim 7, wherein the quality indicators include relative signal strength, and wherein selecting the plurality of the beacons comprises ordering the beacons based on relative signal strength to identify beacons with strong relative signal strength.

10. The method of claim 7, wherein the quality indicators include relative signal strength, and wherein selecting the plurality of the beacons comprises filtering the beacons based on relative signal strength to eliminate beacons with weak relative signal strength.

11. The method of claim 7, wherein accessing the positioned observation comprises one or more of the following:

receiving the positioned observation from a mobile computing device, observing the beacons, obtaining the positioned observation from a location service, determining the quality indicators associated with each of the beacons, and determining a position of the mobile computing device using a satellite-based location system.

12. The method of claim 7, wherein the cloud service is a location service.

13. The method of claim 7, wherein the quality indicators include relative signal strength, and wherein selecting the plurality of the beacons comprises selecting three beacons having the highest relative signal strength.

14. The method of claim 7, wherein accessing the positioned observation comprises accessing a plurality of positioned observations each associated with one of a plurality of computing devices, and further comprising:

identifying the accessed plurality of positioned observations having the selected plurality of the beacons associated therewith; and

calculating the position of the selected plurality of the beacons based on the positions associated with the identified, accessed plurality of positioned observations.

15. The method of claim 7, wherein the selected plurality of the beacons and associated position are stored in the memory area as entries in a table, and further comprising:

generating permutations of the selected plurality of the beacons; and

associating the position with the generated permutations to create additional entries in the table.

16. The method of claim 7, wherein selecting the plurality of the beacons comprises selecting a plurality of the beacons based on one or more of the following:

error radius associated with each of the beacons, a relative signal strength associated with each of the beacons, and a quantity of observations associated with each of the beacons in a beacon store.

17. One or more computer storage media embodying computer-executable components, said components comprising:

an interface component that when executed causes at least one processor to receive a fingerprint from a computing device, said fingerprint having associated therewith beacons observed by the computing device and a signal strength for each of the observed beacons;

a filter component that when executed causes at least one processor to define, based on the signal strength, an ordered beacon set including a plurality of the beacons ordered according to the signal strength;

a memory component that when executed causes at least one processor to access a memory area storing a correspondence between ordered beacon sets and positions; and

a lookup component that when executed causes at least one processor to identify a position associated with the defined, ordered beacon set based on the correspondence stored by the memory component in the memory area,

wherein the interface component provides the position to the computing device as an inferred location of the computing device.

18. The computer storage media of claim 17, wherein the filter component defines the ordered beacon set by selecting a pre-defined quantity of beacons having a high signal strength relative among the beacons.

19. The computer storage media of claim 17, wherein the memory component creates a table to store the correspondence between the ordered beacon sets and the positions.

20. The computer storage media of claim 17, wherein the interface component, the filter component, the memory component, and the lookup component are associated with a location service that crowd-sources data from a plurality of mobile computing devices.