System and Method for Estimating the Probability of Movement of Access Points in a WLAN-based Positioning System

• US 20110235623A1
• Filed: 04/15/2010
• Published: 09/29/2011
• 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
• Granted Patent: US 8,619,643 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• 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 the likelihood of a Wi-Fi enabled device being located within an estimated geographical area, the method comprising:

the Wi-Fi enabled device receiving signals transmitted by at least one Wi-Fi access point in range of the Wi-Fi enabled device;

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

estimating, based on at least one of the last-known positions, associated time information, and number of Wi-Fi access points from which signals were received, the likelihood of the Wi-Fi enabled device being located within an estimated geographical area; and

displaying on a display device information based on the estimated likelihood of the Wi-Fi enabled device being located within the estimated geographical area.

2. 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 probability that a Wi-Fi access point has moved from its corresponding last-known position, the probability being based on the relative age of said last-known position.

3. The method of claim 2, further comprising determining the information that characterizes the 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 a Wi-Fi access points 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 probability that a Wi-Fi access point has moved from its last-known position based on the relative age of said last-known position.

5. The method of claim 1, further comprising:

consulting an historical dataset to determine for at least one of the Wi-Fi access points from which signals were received information describing past relocations for said 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.

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. A method of estimating the likelihood of a Wi-Fi enabled device being located within an estimated geographical area, the method comprising:

the Wi-Fi enabled device receiving signals transmitted by at least one Wi-Fi access point in range of the Wi-Fi enabled device;

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

consulting a reference database to determine for at least one of the Wi-Fi access points 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;

estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area 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; and

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

10. The method of claim 8, 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.

11. The method of claim 8, 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.

12. The method of claim 8, further comprising:

consulting an historical dataset to determine for at least one of the 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.

13. The method of claim 12, 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.

14. The method of claim 12, 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.

15. The method of claim 8, further comprising:

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

wherein the estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area is further based on at least one of the last-known positions and associated time information.

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

the Wi-Fi enabled device receiving signals transmitted by Wi-Fi access points in range of the Wi-Fi enabled device;

extracting information from the signals received that identify each of a plurality of the Wi-Fi access points from which signals were received;

consulting a reference database to determine if the identity of each of the plurality of the identified Wi-Fi access points from which signals were received are present in the reference database;

estimating the likelihood of the Wi-Fi enabled device being located within an estimated geographical area based on the number of Wi-Fi access points from which signals were received and for which identities are present in the reference database; and

displaying on a display device information based on the estimated likelihood of the Wi-Fi enabled device being located within the estimated geographical area.

17. The method of claim 16, wherein the estimating the likelihood of a Wi-Fi enabled device being located within an estimated geographical area further comprises comparing the number of Wi-Fi access points from which signals were received and for which identities are present in the reference database to a number of Wi-Fi access points from which signals were received and for which identities are not present in the reference database.

18. The method of claim 16, further comprising:

consulting an 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.

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

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