Location-based services that choose location algorithms based on number of detected access points within range of user device

• US 8,965,412 B2
• Filed: 03/08/2013
• Issued: 02/24/2015
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Original Assignee: Skyhook Wireless Incorporated (Liberty Broadband Corp.)
• Inventors: Alizadeh-Shabdiz, Farshid, Jones, Russel K., Morgan, Edward J., Shean, Michael G.
• Primary Examiner(s): LE, DANH C
• Application Number:
  US13/790,517
• Publication Number:
  US 20130184003A1
• Time in Patent Office: 718 Days
• Field of Search: 455/456.5, 455/456.1
• US Class Current: 455/456.5
• CPC Class Codes: G01S 19/13 Receivers
• CPC Class Codes: G01S 19/14 specially adapted for specific applications
• CPC Class Codes: G01S 19/46 the supplementary measurement being of a radio-wave signal type
• CPC Class Codes: G01S 5/0205 Details
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0226 Transmitters
• 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/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: G01S 5/0284 Relative positioning
• CPC Class Codes: G06Q 10/0875 Itemisation or classification of parts, supplies or services, e.g. bill of materials
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: H04W 16/18 Network planning tools
• 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 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• 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 64/003 locating network equipment
• CPC Class Codes: H04W 84/10 Small scale networks; Flat hierarchical networks
• CPC Class Codes: H04W 84/12 : WLAN [Wireless Local Area Networks]
• CPC Class Codes: H04W 88/06 : adapted for operation in multiple networks or having at least two operational modes, e.g. multi-mode terminals
• CPC Class Codes: H04W 88/08 : Access point devices
• CPC Class Codes: Y10S 707/99936 : Pattern matching access

Abstract

In one embodiment, in response to a user application request to determine a location of a user-device having a Wi-Fi radio, the Wi-Fi radio is triggered to transmit a request to Wi-Fi access points within range. Messages are received from the Wi-Fi access points, each message identifying the Wi-Fi access point sending the message. Signal strength of the messages received from the Wi-Fi access points is calculated. A reference database of stored locations for Wi-Fi access points in a target area is accessed to obtain the stored locations for the identified Wi-Fi access points. Based on the number of the identified Wi-Fi access points identified via received messages, a corresponding location-determination algorithm is chosen from a plurality of location-determination algorithms. The location of the user-device is determined using the stored locations for the identified Wi-Fi access points, the signal strengths of the received messages and the chosen location-determination algorithm.

Claims

1. A method of locating a user-device having a Wi-Fi radio, comprising:

in response to a user application request to determine a location of a user-device having a Wi-Fi radio, triggering the Wi-Fi radio to transmit a request to Wi-Fi access points within range of the Wi-Fi device;

receiving messages from the Wi-Fi access points within range of the Wi-Fi device, each message identifying the Wi-Fi access point sending the message;

calculating signal strength of the messages received from the Wi-Fi access points;

accessing a reference database of stored locations for Wi-Fi access points in a target area to obtain the stored locations for the identified Wi-Fi access points;

based on the number of the identified Wi-Fi access points identified via received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms;

using the stored locations for the identified Wi-Fi access points, the signal strengths of the received messages and the chosen location-determination algorithm to determine the location of the user-device.

2. The method of claim 1 wherein the stored locations for the identified Wi-Fi access points are filtered to determine whether the corresponding Wi-Fi access points have moved since a time the stored locations of the Wi-Fi access points were included in the reference database.

3. The method of claim 1 wherein the reference database is located locally relative to the user-device.

4. The method of claim 1 wherein the reference database is located remotely relative to the user-device.

5. The method of claim 1 wherein the location of the user device is provided with latitude and longitude coordinates.

6. The method of claim 1 wherein the plurality of location-determination algorithms includes a signal strength weighted average model.

7. The method of claim 1 wherein the plurality of location-determination algorithms includes a nearest neighbor model.

8. The method of claim 1 wherein the plurality of location-determination algorithms includes a triangulation technique.

9. The method of claim 1 wherein the plurality of location-determination algorithms includes an adaptive smoothing technique based on device velocity.

10. The method of claim 1 wherein the choosing the corresponding location-determination algorithm is further based on the user application making the user application request.

11. The method of claim 1 wherein the stored locations for Wi-Fi access points are obtained, at least in part, using a Random Model scanning methodology.

12. The method of claim 1 wherein the stored locations for Wi-Fi access points are obtained, at least in part, using a Chinese Postman routing algorithm.

13. A method of locating a user-device having a Wi-Fi radio, comprising:

in response to a user application request to determine a location of a user-device having a Wi-Fi radio, receiving messages from Wi-Fi access points within range of the Wi-Fi device, each message identifying the Wi-Fi access point sending the message;

determining attributes of the messages received by the Wi-Fi radio;

accessing a reference database of information about Wi-Fi access points in a target area to obtain information about the identified Wi-Fi access points;

based on the number of the identified Wi-Fi access points identified via received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms; and

using the information about the identified Wi-Fi access points, the determined attributes of the received messages and the chosen location-determination algorithm to determine the location of the user-device.

14. The method of claim 13 wherein a first location-determination algorithm of the plurality of location-determination algorithms uses a first set of information about the identified Wi-Fi access points and a second location-determination algorithm of the plurality of location-determination algorithms uses a second set of information about the identified Wi-Fi access points, the first set of information differing from the second set of information.

15. The method of claim 13 wherein the information about the identified Wi-Fi access points is filtered to determine whether the corresponding Wi-Fi access points have moved since the time the information about the Wi-Fi access points was included in the reference database.

16. The method of claim 13 wherein the reference database is located locally relative to the user-device.

17. The method of claim 13 wherein the reference database is located remotely relative to the user-device.

18. The method of claim 13 wherein the location of the user device is provided with latitude and longitude coordinates.

19. The method of claim 13 wherein the plurality of location-determination algorithms includes a signal strength weighted average model.

20. The method of claim 13 wherein the plurality of location-determination algorithms includes a nearest neighbor model.

21. The method of claim 13 wherein the plurality of location-determination algorithms includes a triangulation technique.

22. The method of claim 13 wherein the plurality of location-determination algorithms includes an adaptive smoothing technique based on device velocity.

23. The method of claim 13 wherein the choosing the corresponding location-determination algorithm is further based on the user application making the user application request.

24. The method of claim 13 wherein the information about at least one of the Wi-Fi access points of the reference database includes signal fingerprint information of the Wi-Fi access point, the signal fingerprint information including a plurality of expected signal strength readings of messages transmitted by the Wi-Fi access point at a corresponding plurality of expected locations where the messages are received.

25. The method of claim 24 wherein the plurality of location-determination algorithms includes a technique based on signal fingerprints for more than one Wi-Fi access point.

26. The method of claim 25 wherein the technique includes determining a location by:

calculating signal strength of messages received by the Wi-Fi radio;

comparing the calculated signal strength with the expected signal strengths of the signal fingerprint information for the more than one Wi-Fi access point to find expected signal strengths that most closely match the calculated signal strength; and

determining the location of the user-device based on expected locations that correspond to the expected signal strengths most closely matching the calculated signal strength.

27. The method of claim 13 wherein more than one location-determination algorithm from the plurality of location-determination algorithms is used to determine the location of the user-device.

28. A method of locating a user-device having a wireless signal receiver, comprising:

receiving messages transmitted by wireless signal stations within range of the wireless signal receiver, each message identifying the wireless signal station sending the message;

calculating signal strength of the messages received by the wireless signal receiver;

accessing a reference database of locations of wireless signal stations in a target area to obtain the locations for the identified wireless signal stations;

based on the number of the identified wireless signal stations identified via received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms; and

using the locations for the identified wireless signal stations, the signal strengths of said received messages, and the chosen location-determination algorithm to determine the location of the user-device.

29. The method of claim 28 wherein the wireless signal stations are terrestrially based.

30. The method of claim 29 wherein the wireless signal stations are for transmitting wireless signals to and receiving wireless signals transmitted from a plurality of terrestrially based wireless radio devices.

31. The method of claim 28 wherein the locations for the identified wireless signal stations are filtered to determine whether the corresponding wireless signal stations have moved since the time the information about the wireless signal stations was included in the reference database.

32. The method of claim 28 wherein the reference database is located locally relative to the user-device.

33. The method of claim 28 wherein the reference database is located remotely relative to the user-device.

34. The method of claim 28 wherein the location of the user device is provided with latitude and longitude coordinates.

35. The method of claim 28 wherein the plurality of location-determination algorithms includes a signal strength weighted average model.

36. The method of claim 28 wherein the plurality of location-determination algorithms includes a nearest neighbor model.

37. The method of claim 28 wherein the plurality of location-determination algorithms includes a triangulation technique.

38. The method of claim 28 wherein the plurality of location-determination algorithms includes an adaptive smoothing technique based on device velocity.

39. The method of claim 28 wherein the choosing the corresponding location-determination algorithm is further based on the user application making the user application request.

40. The method of claim 28 wherein reference database of locations further includes signal fingerprint information of at least one of the wireless signal stations, the signal fingerprint information including a plurality of expected signal strength readings of messages transmitted by the wireless signal station at a corresponding plurality of expected locations where the messages are received.

41. The method of claim 40 wherein the plurality of location-determination algorithms includes a technique based on signal fingerprint information for more than one wireless signal station.

42. The method of claim 41 wherein the technique includes determining a location by:

calculating signal strength of messages received by the wireless signal receiver;

comparing the calculated signal strength with the expected signal strengths of the signal fingerprint information for the more than one wireless signal station to find expected signal strengths that most closely match the calculated signal strength; and

determining the location of the user-device based on expected locations that correspond to the expected signal strengths most closely matching the calculated signal strength.

43. The method of claim 28 wherein more than one location-determination algorithm from the plurality of location-determination algorithms is used to determine the location of the user-device.

44. The method of claim 28 wherein the locations for the identified wireless signal stations are obtained, at least in part, using a Random Model scanning methodology.

45. The method of claim 28 wherein the locations for the identified wireless signal stations are obtained, at least in part, using a Chinese Postman routing algorithm.

46. A method of locating a user-device having a wireless signal receiver, comprising:

in response to a user application request to determine a location of a user-device having a wireless signal receiver, receiving messages from wireless signal stations within range of the wireless signal receiver, each message identifying the wireless signal station sending the message;

determining attributes of the messages received by the wireless signal receiver;

accessing the reference database of wireless signal station information about wireless signal stations in a target area to obtain information about the identified wireless signal stations;

based on the number of the identified wireless signal stations identified via received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms; and

using the information about the identified wireless signal stations, the determined attributes of the received messages and the chosen location-determination algorithm to determine the location of the user-device.

47. The method of claim 46, wherein a first location-determination algorithm of the plurality of location-determination algorithms uses a first set of information about the identified wireless signal stations and a second location-determination algorithm of the plurality of location-determination algorithms uses a second set of information about the identified wireless signal stations, the first set of information differing from the second set of information.