System and method for resolving multiple location estimate conflicts in a WLAN-positioning system

• US 9,253,605 B2
• Filed: 04/15/2010
• Issued: 02/02/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:
  US12/760,777
• Publication Number:
  US 20110235532A1
• Time in Patent Office: 2,119 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 resolving multiple location estimate conflicts in a WLAN-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 cumulative distribution functions that characterize the conditional probability that one or more access points detected by the mobile device have relocated within a specified time interval 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 determined by a positioning system, the method comprising:

identifying Wi-Fi access points in range of the Wi-Fi enabled device based on signals received by the Wi-Fi enabled device transmitted by the Wi-Fi access points;

consulting a reference database to determine for each of a plurality of the Wi-Fi access points for which signals were received a last-known estimated position of the Wi-Fi access point;

determining that at least a first set of the Wi-Fi access points for which signals were received have potentially moved from their corresponding last-known estimated positions based on the last-known estimated positions for at least a second set of Wi-Fi access points for which signals were received, each access point of the second set of Wi-Fi access points being different from each access point of the first set of Wi-Fi access points; and

estimating, based on the number of Wi-Fi access points of the first set and the number of Wi-Fi access points of the second set, the likelihood of the Wi-Fi enabled device being located within the estimated geographical area.

2. The method of claim 1, further comprising:

estimating, based on the number of Wi-Fi access points of the first set and the number of Wi-Fi access points of the second set, a plurality of likelihoods of the Wi-Fi enabled device being located within a corresponding plurality of estimated geographical areas; and

displaying on a display device information based on the plurality of estimated likelihoods of the Wi-Fi enabled device being located within the corresponding plurality of estimated geographical areas.

3. The method of claim 1, wherein each of the Wi-Fi access points of the first set has a last-known estimated position that is within a first predetermined distance from the last-known estimated positions of other Wi-Fi access points of the first set, and each of the Wi-Fi access points of the second set has a last-known estimated position that is within a second predetermined distance from the last-known estimated positions of the other Wi-Fi access points of the second set.

4. The method of claim 1, wherein the number of Wi-Fi access points of the first set is less than the number of Wi-Fi access points of the second set.

5. The method of claim 1, wherein estimating the likelihood of the Wi-Fi enabled device being located within the estimated geographical area is further based on information that characterizes the conditional probability that the Wi-Fi access points of the first set have moved from their corresponding last-known position, the conditional probability being based on the number of Wi-Fi access points of the first set and the number of Wi-Fi access points of the second set, and wherein the conditional probability relies on a determination that last-known positions of a first Wi-Fi access point and a second Wi-Fi access point from which signals were received are in conflict.

6. The method of claim 5, wherein the determination that the last-known positions of the first Wi-Fi access point and the second Wi-Fi access point from which signals were received are in conflict is based on the last known positions of the first Wi-Fi access point and second Wi-Fi access point being separated by more than a threshold distance.

7. The method of claim 5, further comprising determining the conditional probability that at least one of the Wi-Fi access points of the first set has moved from its corresponding last-known position.

8. The method of claim 7, wherein the determining the information that characterizes the conditional probability that at least one of the Wi-Fi access points has moved from its corresponding last-known position comprises:

determining a first collection of Wi-Fi access points that moved from a first geographic area to a second geographic area;

determining a second collection of Wi-Fi access points in the second geographic area, each access point of the Wi-Fi access points of the second collection being different Wi-Fi access points than each access point of the Wi-Fi access points of the first collection; and

based on the number of Wi-Fi access points of the first collection and the number of access points of the second collection, determining information that characterizes the conditional probability that a Wi-Fi access point has moved from its last-known position based on the number of Wi-Fi access points of the first set and the number of Wi-Fi access points of the second set.

9. The method of claim 8, further comprising:

determining a third collection of Wi-Fi access points, each Wi-Fi access point of the third collection having a corresponding actual position that permits radio signals transmitted from said Wi-Fi access points to be received by a device capable of receiving Wi-Fi radio signals; and

determining that each Wi-Fi access point of a subset of the Wi-Fi access points of the third collection has moved from its corresponding last-known position based on a comparison of the last-known positions corresponding to each of the Wi-Fi access points of the third collection;

the determining information that characterizes the conditional probability that a Wi-Fi access point has moved from its last-known position being further based on the number of Wi-Fi access points of the subset and the number of Wi-Fi access points of the third collection not included in the subset.

10. The method of claim 1, further comprising:

consulting the reference database to determine for at least a first Wi-Fi access point from which signals were received a last-known estimated position of the first Wi-Fi access point and time information associated with the last-known position for describing the age of the last-known position relative to other information in the reference database; and

the estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area being further based on the last-known position and associated time information of the first Wi-Fi access point.

11. The method of claim 10, wherein the estimating the likelihood of the Wi-Fi enabled device being located within the estimated geographical area is further based on information that characterizes the conditional probability that a Wi-Fi access point has moved from its corresponding last-known position, the conditional probability being based on the relative age of said last-known position, and wherein the conditional probability relies on a determination that last-known positions of a first Wi-Fi access point and a second Wi-Fi access point from which signals were received are in conflict.

12. The method of claim 11, wherein the determination that the last-known positions of the first Wi-Fi access point and the second Wi-Fi access point from which signals were received are in conflict is based on the last known positions of the first Wi-Fi access point and second Wi-Fi access point being separated by more than a threshold distance.

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

14. The method of claim 13, wherein the determining the information that characterizes the conditional probability that a Wi-Fi access point has moved from its corresponding last-known position based on the relative age of said 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 conditional probability that a Wi-Fi access point has moved from its last-known position based on the relative age of said last-known position.

15. The method of claim 10, further comprising:

estimating, based on the last-known position and associated time information, a plurality of likelihoods of the Wi-Fi enabled device being located within a corresponding plurality of estimated geographical areas; and

displaying on a display device information based on the plurality of estimated likelihoods of the Wi-Fi enabled device being located within the corresponding plurality of estimated geographical areas.

16. The method of claim 1, further comprising:

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

wherein estimating the likelihood of the Wi-Fi enabled device being located within the estimated geographical area is further based on the information describing past relocations for the at least one Wi-Fi access point.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

19. The method of claim 1, further comprising:

extracting information from the signals received that identifies at least one Wi-Fi access point from which signals were received;

consulting a reference database to determine for the at least one Wi-Fi access point from which signals were received a set of information identifying a corresponding set of Wi-Fi access points from which signals are expected to be received when the Wi-Fi enabled device receives signals from the at least one Wi-Fi access point of the plurality; and

the estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area being further based on a comparison of the information identifying Wi-Fi access points from which signals were received and the set of information identifying the corresponding set of Wi-Fi access points from which signals are expected to be received.

20. The method of claim 19, wherein the estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area further comprises comparing a first number of Wi-Fi access points from which signals were received and for which information was found in the reference database to a second number of Wi-Fi access points from which signals are expected to be received when the Wi-Fi enabled device receives signals from the at least one Wi-Fi access point of the plurality.

21. The method of claim 19, wherein the estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area further comprises comparing a first number of Wi-Fi access points from which signals were received and for which no identification information was found in the reference database to a second number of Wi-Fi access points from which signals are expected to be received when the Wi-Fi enabled device receives signals from the at least one Wi-Fi access point of the plurality.

22. The method of claim 19, wherein the Wi-Fi access points from which signals are expected to be received when the Wi-Fi enabled device receives signals from the at least one Wi-Fi access point of the plurality are identified based on a history of one or more Wi-Fi enabled devices receiving signals from the expected Wi-Fi access points when receiving signals from the at least one Wi-Fi access point.

23. 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.

24. A system comprising:

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

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

determine for each of a plurality of identified Wi-Fi access points a last-known estimated position of the Wi-Fi access point,

form at least a first cluster of one or more Wi-Fi access points and a second cluster of one or more Wi-Fi access points from the plurality of identified Wi-Fi access points, each access point of the first cluster of Wi-Fi access points being different from each access point of the second cluster of Wi-Fi access points,

determine that at least the first cluster of the Wi-Fi access points have potentially moved from their corresponding last-known estimated positions based on the last-known estimated positions for at least the second cluster of Wi-Fi access points, and

provide an estimated likelihood that the Wi-Fi enabled mobile device is located within an estimated geographical area determined by a positioning system, based on the number of Wi-Fi access points in the first cluster of Wi-Fi access points and the number of Wi-Fi access points in the second cluster Wi-Fi access points.

25. The system of claim 24, wherein each of the Wi-Fi access points of the first cluster of Wi-Fi access points has a last-known estimated position that is within a first predetermined distance from the last-known estimated positions of other Wi-Fi access points of the first cluster of Wi-Fi access points, and each of the Wi-Fi access points of the second cluster of Wi-Fi access points has a last-known estimated position that is within a second predetermined distance from the last-known estimated positions of the other Wi-Fi access points of the second cluster of Wi-Fi access points.

26. The system of claim 24, wherein the estimated likelihood is further based on a determination of a conditional probability that at least one of the Wi-Fi access points of the first cluster of Wi-Fi access points has moved from the Wi-Fi access point'"'"'s corresponding last-known position.

27. The system of claim 24, wherein the estimated likelihood is further based on an age of the last-known position the Wi-Fi access points in the first cluster of Wi-Fi access points.

28. The system of claim 24, wherein the estimated likelihood is further based on information describing past relocations for the Wi-Fi access points in the first cluster of Wi-Fi access points.

29. The system of claim 24, further comprising:

a display device configured to display information based on the estimated likelihood.

30. A method of estimating a likelihood of a Wi-Fi enabled device being located within an estimated geographical area determined by a positioning system, the method comprising:

identifying a plurality of Wi-Fi access points in range of the Wi-Fi enabled device based on signals received by the Wi-Fi enabled device transmitted by the Wi-Fi access points;

consulting a reference database to determine for each of the plurality of identified Wi-Fi access points a last-known estimated position of the Wi-Fi access point;

forming at least a first cluster of one or more Wi-Fi access points and a second cluster of one or more Wi-Fi access points from the plurality of identified Wi-Fi access points, each access point of the first cluster of Wi-Fi access points being different from each access point of the second cluster of Wi-Fi access points; and

determining that at least the first cluster of Wi-Fi access points has potentially moved from their corresponding last-known estimated positions based on the last-known estimated positions for at least the second cluster of Wi-Fi access points; and

providing an estimated likelihood that the Wi-Fi enabled mobile device is located within the estimated geographical area based on an age of the last-known position of the Wi-Fi access points in the first cluster of Wi-Fi access points.

31. The method of claim 30, wherein the estimated likelihood that the Wi-Fi enabled mobile device is located within the estimated geographical area is further based on the number of Wi-Fi access points in the first cluster of Wi-Fi access points and the number of Wi-Fi access points in the second cluster Wi-Fi access points.

32. The method of claim 30, wherein the estimated likelihood is further based on information describing past relocations for the Wi-Fi access points in the first cluster of Wi-Fi access points.

33. The method of claim 30, wherein the estimated likelihood is a center probability, and the estimated geographical area is an area centered upon an estimated location determined by the positioning system.