Wireless network-based location approximation

• US 20100020776A1
• Filed: 11/26/2008
• Published: 01/28/2010
• Est. Priority Date: 11/27/2007
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Youssef, Adel Amin, Liang, Sam, Jain, Ravi, Mishra, Arunesh, Chu, Michael
• Application Number:
  US12/315,079
• Publication Number:
  US 20100020776A1
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

The invention pertains to location approximation of devices, e.g., wireless access points and client devices in a wireless network. Location estimates may be obtained by observation/analysis of packets transmitted or received by the access point. For instance, data rate information associated with a packet is used to approximate the distance between a client device and the access point. This may be coupled with known positioning information to arrive at an approximate location for the access point. Confidence information and metrics about whether a device is an access point and the location of that device may also be determined. Accuracy of the location determination may be affected by factors including propagation and environmental factors, transmit power, antenna gain and diversity, etc. A location information database of access points may employ measurements from various devices over time. Such information may identify the location of client devices and provide location-based services to them.

Claims

1. A computer-implemented method of estimating the location of a wireless device, the method comprising:

obtaining a packet of data transmitted from a first wireless device to a second wireless device;

determining whether one of the first and second wireless devices is a wireless access point;

determining the data rate of the transmitted data packet;

if one of the first and second wireless devices is the wireless access point, then evaluating the determined data rate against a predetermined criterion; and

assigning an estimated location to the wireless access point based upon the evaluation.

2. The method of claim 1, wherein the predetermined criterion is stored in a look-up table and the evaluation includes identifying a distance in the look-up table associated with the determined data rate.

3. The method of claim 1, wherein:

the transmitted data packet is obtained by a client device; and

the method further includes identifying a distance associated with the data rate, wherein the distance is used as a separation between the first wireless device and the client device.

4. The method of claim 3, wherein the client device is at a known location and the method further comprises:

assigning a distance between the wireless access point and the client device to be the same as the distance between the first wireless device and the client device; and

triangulating a position of the wireless access device using the known location of the client device, the distance between the first wireless device and the client device and the distance between the wireless access point and the client device to obtain the estimated location.

5. The method of claim 4, wherein the client device uses a GPS receiver to obtain the known location.

6. The method of claim 1, wherein the predetermined criterion includes a worst-case distance estimate based upon at least one parameter.

7. The method of claim 6, wherein the at least one parameter includes one or more of a channel propagation characteristic, a transmitter characteristic and a receiver characteristic.

8. The method of claim 1, further comprising revising the estimated location of the wireless access point based upon multiple data packets sent or received by the wireless access point.

9. The method of claim 1, further comprising:

determining a position of the client device based upon the estimated location of the wireless access point; and

providing a location-based service to the client device based on the determined position.

10. A computer-implemented method of estimating confidence in a status of a wireless device, the method comprising:

obtaining one or more packets of data transmitted from a first wireless device to a second wireless device;

evaluating the one or more transmitted data packets to identify a frame type for each respective data packet;

identifying the first wireless device or the second wireless device as a wireless access point based upon the identified frame type for at least one of the data packets; and

assigning a confidence value to the identification of the wireless access point.

11. The method of claim 10, wherein:

if the frame type of at least one of the respective data packets is a management frame, then identifying the first wireless device as a wireless access point; and

setting the confidence value for the identification of the wireless access point to a maximum confidence value.

12. The method of claim 11, wherein:

if the frame type of at least one of the respective data packets is not the management frame, then evaluating whether the frame type of any of the respective data packets is a control frame;

if the frame type of at least one of the respective data packets is the control frame, then identifying the first wireless device as the wireless access point; and

setting the confidence value for the identification of the wireless access point to a value between the maximum confidence value and a minimum confidence value.

13. The method of claim 10, wherein identifying the first wireless device or the second wireless device as the wireless access point further includes analyzing a number of frames transmitted or received by each device.

14. A computer-implemented method of estimating confidence in a location of a wireless device, the method comprising:

obtaining one or more packets of data transmitted from a first wireless device to a second wireless device;

determining that the first or second wireless device is a wireless access point based upon the transmitted packets;

determining an estimated location of the wireless access point; and

assigning a confidence value to the estimated location.

15. The method of claim 14, wherein the confidence value represents a percentage likelihood that the wireless access point is contained within a specified area of interest.

16. The method of claim 14, wherein the estimated location is based on multiple data points.

17. The method of claim 16, wherein a confidence code is applied to each data point.

18. The method of claim 17, wherein the confidence code for each data point is calculated using a weighted function.

19. The method of claim 17, wherein the confidence code for each data point represents a likelihood that that data point is valid or an outlier.

20. An apparatus including a processor operable to estimate the location of a wireless device, the processor executing a process to:

obtain a packet of data transmitted from a first wireless device to a second wireless device;

determine whether one of the first and second wireless devices is a wireless access point;

determine the data rate of the transmitted data packet;

if one of the first and second wireless devices is the wireless access point, then evaluate the determined data rate against a predetermined criterion; and

assign an estimated location to the wireless access point based upon the evaluation.

21. A computer-readable recording medium recorded with a computer program for use by a processor to perform a process of estimating the location of a wireless device, the process comprising:

obtaining a packet of data transmitted from a first wireless device to a second wireless device;

determining whether one of the first and second wireless devices is a wireless access point;

determining the data rate of the transmitted data packet;

if one of the first and second wireless devices is the wireless access point, then evaluating the determined data rate against a predetermined criterion; and

assigning an estimated location to the wireless access point based upon the evaluation.

22. An apparatus including a processor operable to estimate confidence in a status of a wireless device, the processor executing a process to:

obtain one or more packets of data transmitted from a first wireless device to a second wireless device;

evaluate the one or more transmitted data packets to identify a frame type for each respective data packet;

identify the first wireless device or the second wireless device as a wireless access point based upon the identified frame type for at least one of the data packets; and

assign a confidence value to the identification of the wireless access point.

23. A computer-readable recording medium recorded with a computer program for use by a processor to perform a process of estimating confidence in a status of a wireless device, the process comprising:

obtaining one or more packets of data transmitted from a first wireless device to a second wireless device;

evaluating the one or more transmitted data packets to identify a frame type for each respective data packet;

identifying the first wireless device or the second wireless device as a wireless access point based upon the identified frame type for at least one of the data packets; and

assigning a confidence value to the identification of the wireless access point.

24. An apparatus including a processor operable to estimate confidence in a location of a wireless device, the processor executing a process to:

obtain one or more packets of data transmitted from a first wireless device to a second wireless device;

determine that the first or second wireless device is a wireless access point based upon the transmitted packets;

determine an estimated location of the wireless access point; and

assign a confidence value to the estimated location.

25. A computer-readable recording medium recorded with a computer program for use by a processor to perform a process of estimating confidence in a location of a wireless device, the process comprising:

obtaining one or more packets of data transmitted from a first wireless device to a second wireless device;

determining that the first or second wireless device is a wireless access point based upon the transmitted packets;

determining an estimated location of the wireless access point; and

assigning a confidence value to the estimated location.

26. An apparatus for use in a wireless network, the apparatus comprising:

memory for storing information associated with a plurality of devices in the wireless network;

means for communicating with one or more of the plurality of devices in the wireless network; and

a processor operable to estimate a location of an access point device in the wireless network based upon data packet information sent to or received from the access point device;

wherein the processor is adapted to provide location based service information to one or more client devices associated with the access point device upon estimation of the location.

27. The apparatus of claim 26, wherein the data packet information for a given data packet includes a data rate of the given data packet, the information stored in the memory includes distance estimates associated with different data rates, and the processor determines the location estimate of the access point device by comparing the data rate of the given data packet to the different data rates and distance estimates stored in the memory.

28. The apparatus of claim 26, wherein the processor is operable to estimate the location of the access point device using the data packet information for multiple data packets sent to or received from the access point device, and wherein the processor is further operable to rank the data packet information for each of the multiple data packets to obtain approximate distances based upon each such packet.

29. The apparatus of claim 28, wherein the processor estimates the location using a centroid of the approximate distances.

30. The apparatus of claim 28, wherein the processor is further operable to assign a confidence in the estimated location of the access point device.

31. The apparatus of claim 30, wherein the confidence represents a likelihood that the access point device is within a given area.

32. The apparatus of claim 30, wherein the confidence is based upon at least one of spatial diversity of selected devices associated with the access point device, receiver characteristics of the selected devices, transmitter characteristics of the selected devices, and freshness of information stored in memory or the data packet information sent to or received from the access point device.

33. The apparatus of claim 26, wherein the processor comprises a plurality of processing devices in a distributed architecture and the memory stores the information so that the information is accessible to one or more of the plurality of processing devices.