Clustering crowd-sourced data for determining beacon positions

• US 8,542,637 B2
• Filed: 01/18/2011
• Issued: 09/24/2013
• Est. Priority Date: 01/18/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bandhakavi, Sindhura, Liu, Weili
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): BHATTI, HASHIM S
• Application Number:
  US13/008,034
• Publication Number:
  US 20120182933A1
• Time in Patent Office: 980 Days
• Field of Search: 370/328, 455/456.1, 715/723
• US Class Current: 370/328
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes 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 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Embodiments analyze crowd-sourced data to identify a moved or moving beacon. The crowd-sourced data for the beacon is grouped into a plurality of clusters based on spatial distance. Timestamps associated with the crowd-sourced data in the clusters are compared to select one of the clusters. The crowd-sourced data associated with the selected cluster is used to determine position information for the beacon.

Claims

1. A system for determining a position for a beacon using a clustering analysis, said system comprising:

a memory area associated with a computing device, said memory area storing a plurality of position observations for one beacon, each of said position observations having a timestamp associated therewith; and

a processor programmed to;

determine, for the beacon, a position and associated error radius based on the plurality of position observations stored in the memory area;

compare the determined error radius with a pre-defined threshold radius; and

based on the comparison, calculate a revised position for the beacon by;

grouping the position observations for the beacon into a plurality of clusters based on spatial distance;

selecting one of the plurality of clusters based on the timestamps; and

determining the revised position for the beacon based on the position observations corresponding to the selected cluster.

2. The system of claim 1, wherein the processor is programmed to calculate the revised position if the determined error radius exceeds the pre-defined threshold radius.

3. The system of claim 1, wherein the processor is further programmed to receive the position observations from a plurality of computing devices.

4. The system of claim 1, wherein the plurality of position observations comprise crowd-sourced records each identifying one or more beacons observed by one of a plurality of mobile computing devices.

5. The system of claim 1, further comprising means for determining whether the beacon is a moved beacon or a moving beacon using a clustering analysis.

6. The system of claim 1, further comprising means for performing a clustering analysis to define the plurality of clusters.

7. A method comprising:

grouping, by a computing device, position observations for one beacon into a plurality of clusters based on spatial distance, each of said position observations having a timestamp associated therewith;

selecting, by a computing device, one of the plurality of clusters based on the timestamps associated with the position observations corresponding to the clusters; and

calculating, by a computing device, a position for the beacon based on the position observations corresponding to the selected cluster.

8. The method of claim 7, wherein selecting one of the plurality of clusters comprises selecting one of the clusters having position observations with the most recent timestamps.

9. The method of claim 7, wherein grouping the position observations into the plurality of clusters comprises identifying one or more of the following:

a beacon identifier, a cluster number, a location of the beacon, a radius of the beacon, a maximum time stamp associated with the position observations, and a minimum time stamp associated with the position observations.

10. The method of claim 7, wherein grouping the position observations into the plurality of clusters comprises performing a k-means clustering analysis with spatial distance as a partition dimension.

11. The method of claim 7, further comprising receiving the position observations, wherein receiving the position observations comprises receiving, from a mobile computing device, a location of the mobile computing device and a set of beacons observed by the mobile computing device.

12. The method of claim 7, further comprising comparing the timestamps associated with the position observations in a first cluster with the timestamps associated with the position observations in a second cluster.

13. The method of claim 12, further comprising defining the beacon as a moved beacon if the timestamps associated with the position observations in the first cluster are mutually exclusive to the timestamps associated with the position observations in the second cluster.

14. The method of claim 12, further comprising defining the beacon as a moving beacon if the timestamps associated with the position observations in the first cluster are not mutually exclusive to the timestamps associated with the position observations in the second cluster.

15. The method of claim 7, further comprising determining a position and an error radius for the beacon based on the position observations, and wherein said grouping, said selecting, and said calculating are performed only if the determined error radius exceeds a pre-defined threshold radius.

16. The method of claim 15, wherein the threshold radius is defined based on a type of the beacon.

17. One or more computer memories having computer-executable components, said components comprising:

a cluster component that when executed by at least one processor causes the at least one processor to group position observations for one beacon into a plurality of clusters based on spatial distance, each of said position observations having a timestamp associated therewith; and

a filter component that when executed by at least one processor causes the at least one processor to analyze the timestamps associated with the position observations corresponding to the clusters from the cluster component to determine whether the timestamps associated with each cluster overlap with timestamps associated with any other cluster; and

a classification component that when executed by at least one processor causes the at least one processor to define the beacon as a moved beacon or a moving beacon based on the comparison performed by the filter component.

18. The computer memories of claim 17, further comprising a refiner component that when executed by at least one processor causes the at least one processor to calculate a position for the beacon based on the position observations corresponding to a cluster selected based on the timestamps by the filter component.

19. The computer memories of claim 17, wherein the spatial distance includes elevation.

20. The computer memories of claim 17, wherein the cluster component, the filter component, and the classification component are executed by a cloud-based service.