System and method for estimating the probability of movement of access points in a WLAN-based positioning system
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.
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.