System and method for estimating the probability of movement of access points in a WLAN-based positioning system

• US 9,516,471 B2
• Filed: 12/31/2013
• Issued: 12/06/2016
• Est. Priority Date: 03/24/2010
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: Alizadeh-Shabdiz, Farshid, Ignatyev, Oleksiy
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): KAO, WEI PO ERIC
• Application Number:
  US14/144,988
• Publication Number:
  US 20140187169A1
• Time in Patent Office: 1,071 Days
• Field of Search: 370310-350, 455/404.2, 4554561-457
• US Class Current: 1/1
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• 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 84/12 WLAN [Wireless Local Area Networks]

Abstract

Methods of and systems for estimating the probability of movement of access points in a WLAN-based positioning system are provided. Disclosed are methods to quantify the probability that a particular location estimate of a mobile device made by a Wi-Fi based positioning system is correct to within an arbitrary accuracy. Implementations use observed access point cluster size, age information for access point location determination, and/or the probability that one or more access points detected by the mobile device have relocated based on historic information about the movement of a collection of access points to make the probability determinations.

Claims

1. A method of estimating a likelihood of a Wi-Fi enabled device being located within an estimated geographical area, the method comprising:

identifying at least one Wi-Fi access point in range of the Wi-Fi enabled device based on signals received by the Wi-Fi enabled device transmitted by the at least one Wi-Fi access point;

consulting a reference database to determine for the at least one Wi-Fi access point from which signals were received a last-known position of the at least one Wi-Fi access point and time information associated with said last-known position for describing a most recent time when the at least one Wi-Fi access point was observed to be at the last-known position;

estimating a geographical area in which the Wi-Fi enabled device may be located; and

estimating the likelihood of the Wi-Fi enabled device being located within the estimated geographical area based on a probability that the at least one Wi-Fi access point has relocated, the probability that the at least one Wi-Fi access point has relocated based on at least one of;

the most recent time when the at least one Wi-Fi access point was observed to be at the last-known position as indicated by the associated time information, or

a number of the one or more Wi-Fi access points from which signals were received by the Wi-Fi enabled device,

wherein the likelihood of the Wi-Fi enabled device being located within the estimated geographical area quantifies a probability that the estimate of the geographical area is correct.

2. The method of claim 1, wherein probability that the at least one Wi-Fi access point has relocated is based on the most recent time when the at least one Wi-Fi access point was observed to be at the last-known position.

3. The method of claim 2, further comprising determining information that characterizes a probability that a Wi-Fi access point has moved from its corresponding last-known position.

4. The method of claim 3, wherein the determining the information that characterizes the probability that the Wi-Fi access point has moved from its corresponding last-known position comprises:

determining a set of Wi-Fi access points, each Wi-Fi access point of the set located at a first geographic position for the corresponding Wi-Fi access point at a first point in time, and having moved to a second geographic position for the corresponding Wi-Fi access point at a second point in time; and

based on the set of Wi-Fi access points that moved and based on the amount of time between the first and second points in time, determining information that characterizes the probability that the Wi-Fi access point has moved from its last-known position based on a most recent time when the Wi-Fi access point was observed to be at the last-known position.

5. The method of claim 1, further comprising:

consulting a historical dataset to determine for at least one of the Wi-Fi access points from which signals were received information describing past relocations for the at least one Wi-Fi access point;

wherein the probability that the at least one Wi-Fi access point has relocated is further based on the information describing past relocations for the at least one Wi-Fi access point.

6. The method of claim 5, wherein the information describing past relocations for the at least one Wi-Fi access point includes an average movement frequency for the at least one Wi-Fi access point.

7. The method of claim 5, wherein the information describing past relocations for the at least one Wi-Fi access point includes an aggregate average movement frequency based on a collection of movement data for a plurality of Wi-Fi access points.

8. The method of claim 1, further comprising displaying on a display device information based on the estimated likelihood of the Wi-Fi enabled device being located within the estimated geographical area.

9. A method of estimating a likelihood that a Wi-Fi enabled device is located within an estimated geographical area, the method comprising:

identifying at least one Wi-Fi access point in range of the Wi-Fi enabled device based on signals received by the Wi-Fi enabled device transmitted by the at least one Wi-Fi access point;

consulting a reference database to determine one or more clusters of one or more Wi-Fi access points from the identified at least one Wi-Fi access point, each cluster having a last-known position;

estimating a geographical area in which the Wi-Fi enabled device may be located based on a cluster of the one or more clusters;

estimating the likelihood that the Wi-Fi enabled device is located within the estimated geographical area, the likelihood estimated based on a probability that the cluster has relocated, the probability that the cluster has relocated based on at least one of;

a time when the cluster was last observed to be at the last-known position, or

a cluster size indicating a number of Wi-Fi access points in the cluster,

wherein the likelihood that the Wi-Fi enabled device is located within the estimated geographical area quantifies a probability that the estimate of the geographical area is correct.

10. The method of claim 9, wherein the probability that the estimate of the geographical area is correct is a center probability, and the geographical area is an area centered upon an estimated location having the center probability.

11. The method of claim 9, wherein the one or more clusters include a first cluster and a second cluster that have last-known positions separated by a distance greater than a transmission range of Wi-Fi access points, such that if Wi-Fi access points of both clusters are identified simultaneously by the Wi-Fi enabled device, then at least one last-known position must be incorrect.

12. The method of claim 9, wherein the probability that the cluster has relocated is based on the time when the cluster was last observed, and the estimating provides that a newer cluster with newer observations has a greater likelihood that the Wi-Fi enabled device is located within the estimated geographical area than an older cluster with older observations.

13. The method of claim 9, wherein the probability that the cluster has relocated is based on the cluster size, and the estimating provides that a larger cluster with more Wi-Fi access points has a greater likelihood that the Wi-Fi enabled device is located within the estimated geographical area than a smaller cluster with less Wi-Fi access points.

14. The method of claim 9, wherein the probability that the cluster has relocated is based on a combination of both the time when the cluster was last observed and the cluster size.

15. The method of claim 9, wherein the probability that the cluster has relocated is further based on a number of the one or more clusters.

16. The method of claim 9, wherein the probability that the cluster has relocated is further based on a historical dataset that includes information describing past relocations of at least one Wi-Fi access point in the cluster.

17. The method of claim 16, wherein the information describing past relocations includes an average movement frequency.

18. The method of claim 9, wherein the probability that the cluster has relocated is further based on a number of Wi-Fi accesses points surrounding at least one Wi-Fi access point in the cluster.

19. A system comprising:

a Wi-Fi enabled device configured to identify a plurality of Wi-Fi access points in range of the Wi-Fi enabled device; and

a non-transitory computer readable medium storing program instructions that when executed on the Wi-Fi enabled device or on a server, are operable to;

consult a reference database to determine one or more clusters of one or more Wi-Fi access points from the identified plurality of Wi-Fi access points, each cluster having a last-known position, and

estimate a likelihood that the Wi-Fi enabled device is located within an estimated geographical area based on a probability that a cluster of the one or more clusters has relocated, the probability estimated based on at least one of;

a time when the cluster was last observed to be at the last-known position, or

a cluster size indicating a number of Wi-Fi access points in the cluster,

wherein the likelihood that the Wi-Fi enabled device is located within the estimated geographical area quantifies a probability that the estimate of the geographical area is correct.

20. The system of claim 19, wherein the probability that the estimate of the geographical area is correct is a center probability, and the geographical area is an area centered upon an estimated location having the center probability.