SYSTEMS FOR AND METHODS OF DETERMINING LIKELIHOOD OF RELOCATION OF REFERENCE POINTS IN A POSITIONING SYSTEM

• US 20110306359A1
• Filed: 06/09/2011
• Published: 12/15/2011
• 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
• Granted Patent: US 8,700,053 B2
• Time in Patent Office: Days
• 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 relocation of reference points in a positioning system are disclosed. A method of determining a measure of likelihood that an estimated geographic location of a designated wireless device is not its accurate present location includes determining a set of reference points associated with the device, which are a geographic position at which signals from the device were detected and/or other devices having a relationship with the designated device. The existence of the relationship is based on the devices being within signal reception range of a same position within a selected period of time. The method includes retrieving attributes of the reference points and/or of the relationships and determining a measure of likelihood that an estimated geographic location associated with the designated device is not its present location based on the attributes of the reference points of the set and/or of the relationships.

Claims

1. A method of determining a measure of likelihood that an estimated geographic location associated with a designated wireless device is not an accurate present location of the wireless device, the method comprising:

determining a set of one or more reference points associated with a designated wireless device, one or more of the reference points being at least one of (i) a geographic position at which signals from the designated wireless device were detected and (ii) another wireless device having a relationship with the designated wireless device, the existence of the relationship being based on the designated wireless device and the another wireless device being within signal reception range of a same position within a selected period of time;

retrieving at least one of (i) attributes of the reference points of the set and (ii) attributes of the relationships between the designated wireless device and the one or more other wireless devices of the set; and

determining a measure of likelihood that an estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device based on at least one of (i) the attributes of the reference points of the set and (ii) the attributes of the relationships between the designated wireless device and the other wireless devices of the set.

2. The method of claim 1, the measure of likelihood being a probability.

3. The method of claim 1, the attributes of the reference points of the set including an estimated geographic location associated with the reference point of the set, and further comprising:

determining a quality measure associated with at least one of the reference points of the set based on a likelihood that the corresponding reference point continues to be a reference point according to the original criteria under which it was identified as a reference point; and

determining an estimated distance between the designated wireless device and at least one of the reference points of the set;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on the quality measures and the estimated distances.

4. The method of claim 3, the quality measure being based on a most recent time at which the corresponding reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point.

5. The method of claim 3, further comprising:

selecting reference points of the set associated with a quality measure exceeding a first threshold value;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on a determination that any of the selected reference points has an estimated distance between the selected reference point and the designated wireless device exceeding a second threshold value.

6. The method of claim 1, the attributes of the reference points of the set including:

location information associated with a corresponding reference point; and

information for determining a stability measure associated with the corresponding reference point of the set, the stability measure indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set.

7. The method of claim 1, the method further comprising:

retrieving the estimated geographic location associated with the designated wireless device;

grouping each reference point of the set into clusters of at least one reference point based on location information associated with the corresponding reference point;

selecting which cluster among the clusters corresponds to the estimated geographic position of the designated wireless device; and

determining a stability measure for the selected cluster based on at least one of (i) a count of the reference points grouped into the cluster and (ii) a stability measure associated with at least one of the reference points of the set grouped into the cluster, the stability measure associated with the reference point indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on the stability measure of the selected cluster.

8. The method of claim 1, the method further comprising:

retrieving the estimated geographic location associated with the designated wireless device;

grouping each reference point of the set into clusters of at least one reference point based on location information associated with the corresponding reference point;

determining a stability measure for each of the clusters based on at least one of (i) a count of the reference points grouped into the cluster, (ii) a stability measure associated with at least one of the reference points of the set grouped into the cluster, the stability measure associated with the reference point indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set, and (iii) a most recent time at which any of the reference points of the cluster were confirmed as a reference point according to the original criteria under which it was identified as a reference point;

for each of the clusters, estimating a distance between the cluster and the designated wireless device; and

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on any cluster (i) having the distance between the cluster and the designated wireless device exceeding a first threshold value and (ii) having the stability measure for the cluster exceeding a second threshold value.

9. The method of claim 1, the attributes of the reference points of the set including a most recent time at which a corresponding reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point.

10. The method of claim 9, further comprising:

for each reference point of the set, estimating a distance between the designated wireless device and the reference point;

determine a count of the number of reference points of the set having an estimated distance less than a first threshold value; and

for each reference point of the set having an estimated distance less than the first threshold value, retrieving the most recent time at which the reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on (i) the count of the number of reference points of the set having an estimated distance less than the first threshold value and (ii) the most recent time at which each of the reference points were confirmed as a reference point.

11. The method of claim 9, further comprising:

for each reference point of the set, estimating a distance between the designated wireless device and the reference point of the set;

determining a weighted distance for each reference point based on the most recent time the corresponding reference point was confirmed as a reference point and the estimated distance between the reference point and designated wireless device, reference points having relatively more recent times receiving relatively higher weights than reference points having relatively less recent times;

determining a first weighted distance among each of the weighted distances that corresponds to a selected percentile; and

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on the first weighted distance exceeding a threshold value.

12. The method of claim 1, the designated wireless device having an identifier and the method further comprising associating, in a reference database, the identifier with an indication of the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device.

13. The method of claim 1, the measure of likelihood being a binary decision.

14. The method of claim 13, the designated wireless device having a first identifier and the method further comprising inferring that an estimated geographic location associated with a second designated wireless device is not an accurate present location of the second wireless device based on a comparison of the first identifier and a second identifier associated with the second designated wireless device.

15. The method of claim 1, the designated wireless device being a WiFi-enabled access point.

16. The method of claim 1, the designated wireless device being a mobile telephone transceiver installation.

17. The method of claim 1, for reference points of the set that are another wireless device, the another wireless device of the set being at least one of a WiFi-enabled access point and a mobile telephone transceiver installation.

18. The method of claim 1, the attributes of the reference points of the set including an amount of time that has passed after a most recent reception of signals from the designated wireless device.

19. A method of determining a measure of likelihood that an estimated geographic location associated with a designated wireless device is not an accurate present location of the wireless device, the method comprising:

determining a first set of one or more wireless devices that have a relationship with a designated wireless device, the existence of the relationship being based on the designated wireless device and the wireless devices of the set being within signal reception range of a same position within a selected period of time;

determining pairwise connections between the wireless devices of the set based on at least one of (i) estimated distances between the wireless devices of a corresponding pair and (ii) relationships between the wireless devices of a corresponding pair, the existence of the relationship being based on the corresponding pair of wireless devices being within signal reception range of a same position within a selected period of time;

partitioning the wireless devices into groups based on a count of a number of pairwise connections crossing any partition;

determining a count of the number of wireless devices in each group; and

determining a measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device based on the counts of the number of wireless device in each group and based on the group of which the designated wireless device is a member.

20. The method of claim 19, further comprising inferring that the location information associated with the designated wireless device is not an accurate present location of the wireless device based on the determined measure of likelihood.

21. The method of claim 19, the determining the measure of likelihood that the location information associated with the designated wireless device is not an accurate present location of the wireless device being based on the designated wireless device being a member of the group having a lower count of wireless devices relative to the other group.

22. A system for determining a measure of likelihood that an estimated geographic location associated with a designated wireless device is not an accurate present location of the wireless device, the system comprising:

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

determine a set of one or more reference points associated with a designated wireless device, one or more of the reference points being at least one of (i) a geographic position at which signals from the designated wireless device were detected and (ii) another wireless device having a relationship with the designated wireless device, the existence of the relationship being based on the designated wireless device and the another wireless device being within signal reception range of a same position within a selected period of time;

retrieve at least one of (i) attributes of the reference points of the set and (ii) attributes of the relationships between the designated wireless device and the one or more other wireless devices of the set; and

determine a measure of likelihood that an estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device based on at least one of (i) the attributes of the reference points of the set and (ii) the attributes of the relationships between the designated wireless device and the other wireless devices of the set.

23. The system of claim 22, the measure of likelihood being a probability.

24. The system of claim 22, wherein:

the attributes of the reference points of the set include an estimated geographic location associated with the reference point of the set;

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

determine a quality measure associated with at least one of the reference points of the set based on a likelihood that the corresponding reference point continues to be a reference point according to the original criteria under which it was identified as a reference point; and

determine an estimated distance between the designated wireless device and at least one of the reference points of the set;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device is based on the quality measures and the estimated distances.

25. The method of claim 24, the quality measure being based on a most recent time at which the corresponding reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point.

26. The method of claim 24, the computer readable media further including instructions that when executed by a computer system cause the computer system to select reference points of the set associated with a quality measure exceeding a first threshold value, and the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device being based on a determination that any of the selected reference points has an estimated distance between the selected reference point and the designated wireless device exceeding a second threshold value.

27. The system of claim 22, the attributes of the reference points of the set including:

location information associated with a corresponding reference point; and

information for determining a stability measure associated with the corresponding reference point of the set, the stability measure indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set.

28. The system of claim 22, wherein:

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

retrieve the estimated geographic location associated with the designated wireless device;

group each reference point of the set into clusters of at least one reference point based on location information associated with the corresponding reference point;

select which cluster among the clusters corresponds to the estimated geographic position of the designated wireless device; and

determine a stability measure for the selected cluster based on at least one of (i) a count of the reference points grouped into the cluster and (ii) a stability measure associated with at least one of the reference points of the set grouped into the cluster, the stability measure associated with the reference point indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device is based on the stability measure of the selected cluster.

29. The system of claim 22, wherein:

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

retrieve the estimated geographic location associated with the designated wireless device;

group each reference point of the set into clusters of at least one reference point based on location information associated with the corresponding reference point;

determine a stability measure for each of the clusters based on at least one of (i) a count of the reference points grouped into the cluster, (ii) a stability measure associated with at least one of the reference points of the set grouped into the cluster, the stability measure associated with the reference point indicating a relative likelihood that the location information associated with the corresponding reference point of the set is the current geographic location of the reference point of the set, and (iii) a most recent time at which any of the reference points of the cluster were confirmed as a reference point according to the original criteria under which it was identified as a reference point;

for each of the clusters, estimate a distance between the cluster and the designated wireless device; and

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device is based on any cluster (i) having the distance between the cluster and the designated wireless device exceeding a first threshold value and (ii) having the stability measure for the cluster exceeding a second threshold value.

30. The system of claim 22, the attributes of the reference points of the set including a most recent time at which a corresponding reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point.

31. The system of claim 30, wherein:

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

for each reference point of the set, estimate a distance between the designated wireless device and the reference point;

determine a count of the number of reference points of the set having an estimated distance less than a first threshold value; and

for each reference point of the set having an estimated distance less than the first threshold value, retrieve the most recent time at which the reference point was confirmed as a reference point according to the original criteria under which it was identified as a reference point;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device is based on (i) the count of the number of reference points of the set having an estimated distance less than the first threshold value and (ii) the most recent time at which each of the reference points were confirmed as a reference point.

32. The system of claim 30, wherein:

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

for each reference point of the set, estimate a distance between the designated wireless device and the reference point of the set;

determine a weighted distance for each reference point based on the most recent time the corresponding reference point was confirmed as a reference point and the estimated distance between the reference point and designated wireless device, reference points having relatively more recent times receiving relatively higher weights than reference points having relatively less recent times; and

determine a first weighted distance among each of the weighted distances that corresponds to a selected percentile;

the determining the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device is based on the first weighted distance exceeding a threshold value.

33. The system of claim 22, the designated wireless device having an identifier and the computer readable media further including instructions that when executed by a computer system cause the computer system to associate, in a reference database, the identifier with an indication of the measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device.

34. The system of claim 22, the measure of likelihood being a binary decision.

35. The system of claim 34, the designated wireless device having a first identifier and the computer readable media further including instructions that when executed by a computer system cause the computer system to infer that an estimated geographic location associated with a second designated wireless device is not an accurate present location of the second wireless device based on a comparison of the first identifier and a second identifier associated with the second designated wireless device.

36. The system of claim 22, the designated wireless device being a WiFi-enabled access point.

37. The system of claim 22, the designated wireless device being a mobile telephone transceiver installation.

38. The system of claim 22, for reference points of the set that are another wireless device, the another wireless device of the set being at least one of a WiFi-enabled access point and a mobile telephone transceiver installation.

39. The system of claim 22, the attributes of the reference points of the set including an amount of time that has passed after a most recent reception of signals from the designated wireless device.

40. A system for determining a measure of likelihood that an estimated geographic location associated with a designated wireless device is not an accurate present location of the wireless device, the system comprising:

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

determine a first set of one or more wireless devices that have a relationship with a designated wireless device, the existence of the relationship being based on the designated wireless device and the wireless devices of the set being within signal reception range of a same position within a selected period of time;

determine pairwise connections between the wireless devices of the set based on at least one of (i) estimated distances between the wireless devices of a corresponding pair and (ii) relationships between the wireless devices of a corresponding pair, the existence of the relationship being based on the corresponding pair of wireless devices being within signal reception range of a same position within a selected period of time;

partition the wireless devices into groups based on a count of a number of pairwise connections crossing any partition;

determine a count of the number of wireless devices in each group; and

determine a measure of likelihood that the estimated geographic location associated with the designated wireless device is not an accurate present location of the wireless device based on the counts of the number of wireless device in each group and based on the group of which the designated wireless device is a member.

41. The system of claim 40, the computer readable media further including instructions that when executed by a computer system cause the computer system to infer that the location information associated with the designated wireless device is not an accurate present location of the wireless device based on the determined measure of likelihood.

42. The system of claim 40, the determining the measure of likelihood that the location information associated with the designated wireless device is not an accurate present location of the wireless device being based on the designated wireless device being a member of the group having a lower count of wireless devices relative to the other group.