Location inspector in wireless networks

• US 7,835,749 B1
• Filed: 10/03/2006
• Issued: 11/16/2010
• Est. Priority Date: 10/03/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Pandey, Anita, Thomson, Allan, Hart, Brian Donald, Maldonado, Emilio, Doshi, Bhautik, Paranjpe, Milind
• Primary Examiner(s): Pérez-Gutiérrez; Rafael
• Assistant Examiner(s): Kasraian; Allahyar
• Application Number:
  US11/542,720
• Time in Patent Office: 1,505 Days
• Field of Search: 4554561-4566, 455/446, 455/423, 455/67.11, 455/457, 342/450
• US Class Current: 455/446
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/02527 Detecting or resolving anomalies in the radio frequency fingerprints of the radio-map
• CPC Class Codes: H04W 36/385 of the core network

Abstract

In one embodiment, a method includes receiving calibration data, computing one or more attributes of a pathloss model based on the calibration data, computing estimated locations using the received signal strength values of the calibration data points, associating location errors with the one or more calibration data points, and computing a location quality within a region based on the associated location errors.

Claims

1. A storage medium comprising a plurality of programming instructions to be executed by a processor to:

receive calibration data associated with a plurality of calibration data points, wherein;

each calibration data point is at a known location; and

the calibration data comprise a plurality of received signal strength values corresponding to a plurality of radio frequency (RF) signals transmitted from the plurality of calibration data points respectively;

compute one or more attributes of a pathloss model based on the calibration data to obtain the pathloss model that best fits the calibration data;

compute, using the pathloss model, a plurality of estimated locations for the plurality of calibration data points respectively using the plurality of received signal strength values;

associate a plurality of location errors with the plurality of calibration data points respectively, wherein for each calibration data point, its location error is a distance difference between the known location of the calibration data point and the estimated location computed for the calibration data point;

compute a location quality within a region comprising the plurality of calibration data points and one or more other locations between the plurality of calibration data points, comprising;

for each calibration data point in the region, determine a percentage of the location errors associated with two or more calibration data points within a radius of the calibration data point that are within a given error threshold; and

for each other location between the plurality of calibration data points in the region, interpolate the percentages of two or more calibration data points; and

generate a map of location quality based on the percentages of the plurality of calibration data points and the interpolated percentages of the one or more other locations between the plurality of calibration data points.

2. The storage medium of claim 1, wherein for each other location between the plurality of calibration data points in the region, interpolate the percentages of the two or more calibration data points using two-dimensional linear interpolation.

3. The storage medium of claim 1, wherein the plurality of programming instructions is further operable to, for each calibration data point in the region, determine the radius based on an average density of the plurality of calibration data points in the region.

4. The storage medium of claim 1, wherein for each calibration data point in the region, the radius is predefined.

5. The storage medium of claim 1, wherein the map of location quality is color coded to indicate different degrees of error.

6. The storage medium of claim 1, wherein, for each calibration data point in the region, the radius captures twenty or more calibration data points for determining the percentage.

7. The storage medium of claim 1, wherein, to compute the location quality, the plurality of programming instructions is further operable to cause the at least one processor to:

select, for each calibration data point in the region, the radius that captures a desired number of calibration data points;

sort the location errors associated with the captured calibration data points by percentile of location errors; and

interpolate, based on a selected percentile parameter, a distance error versus (x,y) for the one or more other locations between the plurality of calibration data points.

8. The storage medium of claim 1, wherein the given error threshold is based at least in part on one or more of a configurable error threshold and an accuracy percentage.

9. A method comprising:

by one or more computing devices,

receiving calibration data associated with a plurality of calibration data points, wherein;

each calibration data point is at a known location; and

the calibration data comprise a plurality of received signal strength values corresponding to a plurality of radio frequency (RF) signals transmitted from the plurality of calibration data points respectively;

computing one or more attributes of a pathloss model based on the calibration data to obtain the pathloss model that best fits the calibration data;

computing, using the pathloss model, a plurality of estimated locations for the plurality of calibration data points respectively using the plurality of received signal strength values;

associating a plurality of location errors with the plurality of calibration data points respectively, wherein for each calibration data point, its location error is a distance difference between the known location of the calibration data point and the estimated location computed for the calibration data point;

computing a location quality within a region comprising the plurality of calibration data points and one or more other locations between the plurality of calibration data points, comprising;

for each calibration data point in the region, determining a percentage of the location errors associated with two or more calibration data points within a radius of the calibration data point that are within a given error threshold; and

for each other location between the plurality of calibration data points in the region, interpolating the percentages of two or more calibration data points; and

generating a map of location quality based on the percentages of the plurality of calibration data points and the interpolated percentages of the one or more other locations between the plurality of calibration data points.

10. The method of claim 9 wherein the location quality is further based on the given error threshold.

11. The method of claim 9 wherein the map of location quality indicates an accuracy percentage at one or more locations.

12. The method of claim 9 wherein the map of location quality indicates a percentage of locations with errors within a circle having a predefined radius.

13. The method of claim 9 wherein the map of location quality is color coded to indicate different degrees of error.

14. The method of claim 9 wherein, to compute location quality, the method further comprises:

selecting, for all calibration data points, a radius that captures a desired average number of calibration data points;

computing the percentage of calibration data points captured within the radius and within the given error threshold; and

interpolating percentage values for locations between calibration data points.

15. The method of claim 9 wherein, to compute location quality, the method further comprises:

selecting, for each calibration data point, a radius that captures a desired number of calibration data points;

computing location errors for the captured calibration data points captured within the radius;

sort the location error by percentile of location errors; and

interpolating, based on a selected percentile parameter, a distance error versus (x,y) for locations between calibration data points.

16. The method of claim 9, wherein the given error threshold is based at least in part on one or more of a configurable error threshold and an accuracy percentage.

17. A system comprising:

a server comprising a location inspector application stored in a memory, wherein the location inspector application comprises programming instructions operable to cause the server to;

receive calibration data associated with a plurality of calibration data points, wherein;

each calibration data point is at a known location; and

the calibration data comprise a plurality of received signal strength values corresponding to a plurality of radio frequency (RF) signals transmitted from the plurality of calibration data points respectively;

compute one or more attributes of a pathloss model based on the calibration data to obtain the pathloss model that best fits the calibration data;

compute, using the pathloss model, a plurality of estimated locations for the plurality of calibration data points respectively using the plurality of received signal strength values;

associate a plurality of location errors with the plurality of calibration data points respectively, wherein for each calibration data point, its location error is a distance difference between the known location of the calibration data point and the estimated location computed for the calibration data point;

compute a location quality within a region comprising the plurality of calibration data points and one or more other locations between the plurality of calibration data points, comprising;

for each of the calibration data point in the region, determine a percentage of the location errors associated with two or more calibration data points within a radius of the calibration data point that are within a given error threshold; and

for each other location between the plurality of calibration data points in the region, interpolate the percentages of two or more calibration data points; and

generate a map of location quality based on the percentages of the plurality of calibration data points and the interpolated percentages of the one or more other locations between the plurality of calibration data points; and

a wireless access point operable to facilitate collection of the calibration data.

18. The system of claim 17 wherein the location quality is further based on the given error threshold.

19. A method comprising:

by one or more computing devices,

receiving a plurality of received signal strength values each of which corresponding to a radio frequency signal transmitted from one of a plurality of known first locations and received at one of a plurality of known second locations;

determining a pathloss model that best fits the received signal strength values, the pathloss model representing a received signal strength value as a function of location, the function comprising one or more configurable variables;

computing a plurality of estimated first locations each of which corresponding to one of the known first locations and being computed using the best-fit pathloss model based on the received signal strength value corresponding to the radio frequency signal transmitted from the corresponding known first location;

computing a plurality of location errors for the known first locations, each of the location errors being a distance difference between a corresponding pair of known first location and estimated first location;

determining a location quality for a region comprising the known first locations and one or more third locations between the known first locations, comprising;

for each of the known first locations, determining a percentage of the location errors of two or more known first locations within a radius of the known first location that are within a given error threshold; and

for each of the third locations between the known first locations, interpolating the percentages of two or more known first locations; and

constructing a color coded map of the location quality, such that different percentages of different known first locations or third locations are represented using different colors.

20. The method of claim 19, wherein determining the best-fit pathloss model comprises:

applying each of the received signal strength values and the corresponding known first location and known second location to the function; and

adjusting one or more values of the configurable variables.

21. The method of claim 19, wherein computing each of the estimated first locations comprises applying the received signal strength values corresponding to the radio signal transmitted from the corresponding known first location to the best-fit pathloss model with the configurable variables each having a best-fit value.

22. The method of claim 19, wherein for each of the known first locations, the radius captures twenty or more known first locations for determining the percentage.