Systems for and methods of determining likelihood of reference point identity duplication in a positioning system

• US 8,996,032 B2
• Filed: 01/09/2014
• Issued: 03/31/2015
• Est. Priority Date: 06/11/2010
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: Alizadeh-Shabdiz, Farshid, Brachet, Nicolas, Cavanaugh, Gerald, Dancus, Andrei, Jones, Russel K., Steger, Christopher
• Primary Examiner(s): TRAN, CONGVAN
• Application Number:
  US14/151,159
• Publication Number:
  US 20140248902A1
• Time in Patent Office: 446 Days
• Field of Search: 455/456.1, 455/456.3, 455/404.2, 455/9
• US Class Current: 455/456.1
• CPC Class Codes: G01S 1/024 of beacon transmitters
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0252 Radio frequency fingerprinting
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Systems for and methods of determining likelihood of reference point identity duplication in a positioning system are disclosed. A method of determining a measure of likelihood that a designated identifier is shared by wireless devices includes determining reference points associated with any wireless device having a designated identifier. The reference points are a geographic position at which signals from any of the wireless devices were detected and/or wireless devices from which signals were also detected within a selected period of time during which the signals from any of the wireless devices having the designated identifier were detected. The method also includes determining statistical information about a temporal distribution of detection of signals of reference points, a spatial distribution of the reference points, and/or a cardinality of the reference points and determining a measure of likelihood that the designated identifier is shared by wireless devices is based on the statistical information.

Claims

1. A method of determining that a single designated identifier is shared by at least two wireless devices and using the determination that the single designated identifier is shared by at least two wireless devices in a wireless positioning system, the method comprising:

determining a set of reference points associated with any wireless devices having the single designated identifier, each reference point being (i) a geographic position at which signals from any of the wireless devices having the designated identifier were detected or (ii) a neighbor wireless device from which signals were also detected by a receiver within a selected period of time during which the signals from any of the wireless devices having the designated identifier were detected by the receiver;

clustering, by the wireless positioning system, reference points of the set of reference points into at least two clusters;

determining a property for each cluster of the at least two clusters;

based on the property for each cluster, determining that the single designated identifier is shared by at least two wireless devices; and

in response to the determination that the single designated identifier is shared by at least two wireless devices, excluding any wireless devices using the single designated identifier from being used by the wireless positioning system as a beacon for estimating a position of a client device.

3. The method of claim 1, wherein each reference point is a neighbor wireless device from which signals were also detected by the receiver within a selected period of time during which the signals having the identifier were detected by the receiver.

4. The method of claim 3, wherein the at least two clusters are spatial clusters based on geographic positions of selected neighbor wireless devices.

5. The method of claim 4, wherein the selected neighbor wireless devices have a stability above a first threshold and a relationship quality with a wireless device using the single designated identifier above a second threshold.

6. The method of claim 5, wherein the property for each cluster is an observation interval, and the method further comprises:

defining the observation interval for each cluster; and

in response to any clusters having overlapping observation intervals, determining that the single designated identifier is shared by at least two wireless devices.

7. The method of claim 4, wherein each neighbor wireless device has an associated quiet time, wherein the quiet time is a length of time since a last observation of a neighbor wireless device, and the method further comprises:

determining a minimum quiet time for each cluster;

determining a number of clusters that have a determined minimum quiet time that is less than a first threshold and that include a number of neighbor wireless devices greater than a second threshold;

determining an identity of a manufacturer of wireless devices using the single designated identifier; and

in response to the number of clusters and the identity of the manufacturer, determining that the single designated identifier is shared by at least two wireless devices.

8. The method of claim 1, wherein each reference point is a geographic position at which signals having the single designated identifier were detected.

9. The method of claim 8, wherein the at least two clusters are spatial clusters based on the geographic positions at which signals having the single designated identifier were detected.

10. The method of claim 9, further comprising:

determining a velocity required to move from each cluster of the least two clusters to a next cluster of the at least two cluster; and

in response to any velocity exceeding a threshold, determining that the single designated identifier is shared by at least two wireless devices.

11. The method of claim 1, wherein the wireless devices are Wi-Fi access points, and the wireless positioning system is a Wi-Fi positioning system.

2. A wireless positioning system configured to determine that a single designated identifier is shared by at least two wireless devices and use the determination that the single designated identifier is shared by at least two wireless devices in a wireless positioning system, the wireless positioning system comprising:

a computer system configured to estimate a position of a client device based on one or more beacons whose signals are observed by the client device; and

a computer readable media including instructions that when executed by the computer system cause the computer system to;

determine a set of reference points associated with any wireless devices having the single designated identifier, each reference point being (i) a geographic position at which signals from any of the wireless devices having the designated identifier were detected or (ii) a neighbor wireless device from which signals were also detected by a receiver within a selected period of time during which the signals from any of the wireless devices having the designated identifier were detected by the receiver;

cluster reference points of the set of reference points into at least two clusters;

determine a property for each cluster of the at least two clusters;

based on the property for each cluster, determine that the single designated identifier is shared by at least two wireless devices; and

in response to the determination that the single designated identifier is shared by at least two wireless devices, exclude any wireless devices using the single designated identifier from being used by the wireless positioning system as a beacon for estimating the position of the client device.

14. The wireless positioning system of claim 2, wherein each reference point is a neighbor wireless device from which signals were also detected by the receiver within a selected period of time during which the signals having the identifier were detected by the receiver.

15. The wireless positioning system of claim 14, wherein the at least two clusters are spatial clusters based on geographic positions of selected neighbor wireless devices.

16. The wireless positioning system of claim 15, wherein the property for each cluster is an observation interval, and the instructions when executed by the computer system further cause the computer system to:

define the observation interval for each cluster; and

in response to any clusters having overlapping observation intervals, determine the single designated identifier is shared by at least two wireless devices.

17. The wireless positioning system of claim 14, wherein each neighbor wireless device has an associated quiet time, wherein the quiet time is a length of time since a last observation of a neighbor wireless device, and the instructions when executed by the computer system further cause the computer system to:

determine a minimum quiet time for each cluster;

determine a number of clusters having minimum quiet time less than a first threshold and neighbor wireless devices greater than a second threshold;

determine an identity of a manufacturer of any wireless devices using the single designated identifier; and

in response to the number of clusters and the identity of the manufacturer, determine the single designated identifier is shared by at least two wireless devices.

18. The wireless positioning system of claim 2, wherein each reference point is a geographic position at which signals having the single designated identifier were detected.

19. The wireless positioning system of claim 18, wherein the instructions when executed by the computer system further cause the computer system to:

determine a velocity required to move from each cluster of the least two clusters to a next cluster of the at least two cluster; and

in response to any velocity exceeding a threshold, determine the single designated identifier is shared by at least two wireless devices.

20. The wireless positioning system of claim 2, wherein the wireless devices are Wi-Fi access points, and the wireless positioning system is a Wi-Fi positioning system.

12. A method of determining that a single designated identifier is shared by at least two wireless devices and using the determination that the single designated identifier is shared by at least two wireless devices in a wireless positioning system, the method comprising:

retrieving attributes of any wireless device having the single designated identifier, the attributes including at least the single designated identifier or an identity of a manufacturer associated with the single designated identifier;

comparing, by the wireless positioning system, the attributes to a ubiquity black list;

based on the comparison to the ubiquity black list, determining that the single designated identifier is shared by at least two wireless devices; and

in response to the determination that the single designated identifier is shared by at least two wireless devices, excluding any wireless devices using the single designated identifier from being used by the wireless positioning system as a beacon for estimating a position of a client device.

13. The method of claim 12, wherein the wireless devices are Wi-Fi access points, and the wireless positioning system is a Wi-Fi positioning system.