System and method for generating a location estimate using uniform and non-uniform grid points

• US 8,406,753 B2
• Filed: 02/05/2008
• Issued: 03/26/2013
• Est. Priority Date: 02/05/2007
• Status: Active Grant

• Current Assignee: Geoscope Technologies Pte. Ltd. (Transpacific IP Group Limited)
• Original Assignee: Andrew LLC (CommScope Holding Company, Inc.)
• Inventors: Mazlum, Selcuk, Alles, Martin, Carlson, John, Maher, George
• Primary Examiner(s): Mehrpour, Melody
• Assistant Examiner(s): STEPHEN, EMEM O
• Application Number:
  US12/026,480
• Publication Number:
  US 20080188237A1
• Time in Patent Office: 1,876 Days
• Field of Search: 455/422.1, 455/423, 455/425, 455/433, 455/404.2, 4554561-4563, 4554351-4355, 34087004-87005, 340988-989, 340/991, 340/995.18, 340/995.25, 340/423.19, 3423572-35725, 342/357.62, 702/85, 702 94- 95, 702/150
• US Class Current: 455/422.1
• CPC Class Codes: G01S 5/021 Calibration, monitoring or correction G01S5/0252 takes precedence
• CPC Class Codes: G01S 5/0244 Accuracy or reliability of position solution or of measurements contributing thereto
• CPC Class Codes: G01S 5/02526 using non-dedicated equipment, e.g. user equipment or crowd-sourcing
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

The location of a wireless mobile device may be estimated using, at least in part, one or more pre-existing Network Measurement Reports (“NMRs”) which include calibration data for a number of locations within a geographic region. The calibration data for these locations is gathered and analyzed so that particular grid points within the geographic region can be determined and associated with a particular set or sets of calibration data from, for example, one or more NMRs. Sets of grid points may be evaluated as a function of parameters of the calibration data, and a set of grid points may be selected as a function of a predetermined criteria. The location of a mobile device in the geographic region may then be determined as a function of the predetermined criteria.

Claims

1. A method of determining the location of a mobile device in a geographic region comprising the steps of:

(a) providing calibration data for each of one or more calibration points in a geographic region, said calibration data having one or more characterizing parameters;

(b) generating one or more sets of grid points for said calibration data;

(c) receiving at least one network measurement report from a mobile device at an unknown location in said geographic region;

(d) evaluating said at least one network measurement report with each of said sets of grid points as a function of select ones of said characterizing parameters;

(e) selecting a set of grid points as a function of a predetermined criteria; and

(f) determining the location of a mobile device in said geographic region as a function of said selected set of grid points.

2. The method of claim 1 wherein said at least one network measurement report is a set of network measurement reports.

3. The method of claim 1 wherein said predetermined criteria is selected from the group consisting of:

total probability, cluster radius, Euclidean norm, joint probability, and Mahalanobis distance.

4. The method of claim 1 wherein one of said grid points is located on a predetermined fixed uniform grid defined over said geographic region.

5. The method of claim 4 wherein one of said grid points is randomly located within said geographic region.

6. The method of claim 1 wherein one of said grid points is randomly located within said geographic region.

7. The method of claim 1 wherein said calibration data comprises information from a network measurement report.

8. The method of claim 1 wherein for each of select ones of said grid points the calibration data includes plural data vectors and the evaluating of said sets of grid points comprises a determination of clustering of said plural data vectors.

9. The method of claim 1 wherein said characterizing parameter is selected from the group consisting of:

signal strength for a signal transmitted by a transmitter having a known location as received by a receiver at said grid point;

signal strength of a signal transmitted by a transmitter located at said grid point as received by a receiver at a known location;

round trip time for a signal traveling between said grid point and a known location;

timing advance of a signal received by said mobile device at said grid point;

time difference of arrival of plural signals at said grid point with respect to a pair of known locations as measured by a receiver at said grid point or at said known locations;

the identification of a serving cell or serving sector of said mobile device located at said grid point;

a state of a wireless network serving said mobile device, and combinations thereof.

10. The method of claim 1 wherein the step of evaluating further comprises:

(i) comparing select ones of said sets of grid points to at least one characterizing parameter of said at least one network measurement report;

(ii) generating a first location estimate of the mobile device for each parameter of said network measurement report; and

(iii) determining a second location estimate of the mobile device as a function of at least one of said generated first location estimates.

11. The method of claim 10 further comprising the step of identifying and omitting outlier first location estimates by:

(i) determining a Mahalanobis distance from each first location estimate to the second location estimate;

(ii) determining a distance threshold from a median of the Mahalanobis distances multiplied by a predetermined factor; and

(iii) determining a third location estimate by averaging two or more of said first location estimates,

wherein first location estimates having a Mahalanobis distance to the second location estimate greater than the distance threshold are omitted from said determined third location estimate.

12. The method of claim 10 wherein determining a second location estimate further comprises averaging two or more first location estimates.

13. The method of claim 10 further comprising the step of omitting a first location estimate having an error greater than a predetermined threshold.

14. The method of claim 10 wherein determining a second location estimate further comprises employing a weighted averaging of ones of said first location estimates.

15. The method of claim 10 wherein determining a second location estimate further comprises weighting a first location estimate by an inverse of a distance metric.

16. The method of claim 10 wherein determining a second location estimate further comprises normalizing a first location estimate by a sum of an inverse of a distance metric.

17. The method of claim 10 wherein determining a second location estimate further comprises weighting a first location estimate as a function of the number of reporting neighboring cells to a serving cell serving said mobile device.

18. The method of claim 1 wherein the step of evaluating further comprises:

(i) comparing an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report; and

(ii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

19. The method of claim 1 wherein the step of evaluating further comprises:

(i) comparing an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report;

(ii) if no exact match is made between the ordered list of neighboring cells of said network measurement report and any grid point in said geographic region then forming a largest subset of the ordered list of neighboring cells in said grid points that provide a match; and

(iii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

20. The method of claim 1 wherein the step of evaluating further comprises:

(i) comparing an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report;

(ii) if the ordered list of neighboring cells of said network measurement report is not contained in the ordered list of neighboring cells for said geographic region then using a largest subset of neighboring cells in said network measurement report having either an exact match or is contained in the ordered list of neighboring cells in said geographic region; and

(iii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

21. The method of claim 1 wherein the step of evaluating further comprises:

(i) evaluating a probability density function for each power level of a cell neighboring a cell serving said mobile device in said network measurement report over each grid point in a set of available grid points in said geographic region;

(ii) determining a joint probability as a function of said individual probability density functions; and

(iii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

22. The method of claim 1 wherein the step of evaluating further comprises:

(i) evaluating a joint probability of power levels for at least one cell neighboring a cell serving said mobile device in said network measurement report over a set of available grid points in said geographic region; and

(ii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

23. The method of claim 1 wherein the step of evaluating further comprises:

(i) determining a distortion measure between a parameter of a grid point and a corresponding parameter in said network measurement report; and

(ii) generating an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a location of a grid point having the smallest distortion measure;

a weighted sum of the locations of a set of matching grid points in said geographic region, said weighted sum being a function of said distortion measure;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

24. The method of claim 1 wherein the step of evaluating further comprises:

(i) matching cell power ordering of cells neighboring a cell serving said mobile device in said network measurement report to neighboring cell power ordering of grid points in said geographic region; and

(ii) selecting an estimated location as a function of a quality of said matching,

wherein said quality is a function of a relative shift in an ordering sequence occurring between said network measurement report and grid point cell power ordering.

25. The method of claim 1 wherein the step of evaluating further comprises:

(i) defining a first region within said calibration data as a function of a first characterizing parameter of said at least one network measurement report and a predetermined range of said first parameter;

(ii) defining a second region within said calibration data as a function of another characterizing parameter of said at least one network measurement report and a predetermined range of said another parameter;

(iii) repeating steps (i)-(ii) for each characterizing parameter in said at least one network measurement report;

(iv) determining an intersection of each defined region; and

(v) estimating the location of a mobile device in said geographic region as a function of said intersection.

26. The method of claim 1 wherein the step of evaluating further comprises:

(i) defining a first region within said calibration data as a function of a first characterizing parameter of a network measurement report within a set of network measurement reports and a predetermined range of said first parameter;

(ii) defining a second region within said calibration data as a function of another characterizing parameter of said network measurement report within the set of network measurement reports and a predetermined range of said another parameter;

(iii) repeating steps (i)-(ii) for each characterizing parameter in said set of network measurement reports;

(iv) determining a clustering of data vectors in said set of network measurement reports; and

(v) estimating the location of a mobile device in said geographic region as a function of said clustering.

27. The method of claim 1 wherein the step of evaluating further comprises:

(i) determining a representative value for each available characterizing parameter in a set of network measurement reports as a function of a variation of said available characterizing parameter in each available network measurement report;

(ii) determining one or more representative network measurement reports as a function of said representative value; and

(iii) estimating the location of a mobile device in said geographic region as a function of said one or more representative network measurement reports.

28. The method of claim 27 further comprising the steps of:

(iv) defining a first region as a function of a first representative value for a first characterizing parameter and a predetermined range of said first value;

(v) defining a second region as a function of a second representative value for a second characterizing parameter and a predetermined range of said second value;

(vi) repeating steps (iv)-(v) for each characterizing parameter in said one or more representative network measurement reports;

(vii) determining an intersection of each defined region; and

(viii) estimating the location of a mobile device in said geographic region as a function of said intersection.

29. The method of claim 1 wherein the step of selecting further comprises selecting a set of grid points as a function of a criteria of fit.

30. The method of claim 29 wherein the criteria of fit is selected from the group consisting of:

total probability, cluster radius, Euclidean norm, Mahalanobis distance, distortion measure, confidence measure, and any combination thereof.

31. The method of claim 1 wherein the step of selecting further comprises:

(i) selecting one or more candidate locations from one or more of said sets of grid points; and

(ii) evaluating said selected one or more candidate locations across said one or more sets of grid points,

wherein the determined location of the mobile device is a function of said evaluation of said selected locations.

32. A system for determining the location of a mobile device in a geographic region comprising:

(a) a database; and

(b) a processor for receiving calibration data for each of one or more calibration points in a geographic region and receiving at least one network measurement report from a mobile device at an unknown location in said geographic region, said calibration data and network measurement report having at least one characterizing parameter and said processor is programmed to;

(i) generate one or more sets of grid points for said calibration data,

(ii) evaluate said at least one network measurement report with each of said sets of grid points as a function of select ones of said characterizing parameters,

(iii) select a set of grid points as a function of a predetermined criteria, and

(iv) determine the location of a mobile device in said geographic region as a function of said selected set.

33. The system of claim 32 wherein said at least one network measurement report is a set of network measurement reports.

34. The system of claim 32 wherein said predetermined criteria is selected from the group consisting of:

total probability, cluster radius, Euclidean norm, joint probability, and Mahalanobis distance.

35. The system of claim 32 wherein one of said grid points is located on a predetermined fixed uniform grid defined over said geographic region.

36. The system of claim 35 wherein one of said grid points is randomly located within said geographic region.

37. The system of claim 32 wherein one of said grid points is randomly located within said geographic region.

38. The system of claim 32 wherein said calibration data comprises information from a network measurement report.

39. The system of claim 32 wherein for each of select ones of said grid points the calibration data includes plural data vectors and the evaluating of said grid points comprises a determination of clustering of said plural data vectors.

40. The system of claim 32 wherein said characterizing parameter is selected from the group consisting of:

signal strength for a signal transmitted by a transmitter having a known location as received by a receiver at said grid point;

signal strength of a signal transmitted by a transmitter located at said grid point as received by a receiver at a known location;

round trip time for a signal traveling between said grid point and a known location;

timing advance of a signal received by said mobile device at said grid point;

time difference of arrival of plural signals at said grid point with respect to a pair of known locations as measured by a receiver at said grid point or at said known locations;

the identification of a serving cell or serving sector of said mobile device located at said grid point;

a state of a wireless network serving said mobile device, and combinations thereof.

41. The system of claim 32 wherein the processor is further programmed to:

(v) compare select ones of said sets of grid points to at least one characterizing parameter of said at least one network measurement report;

(vi) generate a first location estimate of the mobile device for each parameter of said network measurement report; and

(vii) determine a second location estimate of the mobile device as a function of at least one of said generated first location estimates.

42. The system of claim 41 wherein the processor is further programmed to identify and omit outlier first location estimates by:

(1) determine a Mahalanobis distance from each first location estimate to the second location estimate;

(2) determine a distance threshold from a median of the Mahalanobis distances multiplied by a predetermined factor; and

(3) determine a third location estimate by averaging two or more of said first location estimates,

wherein first location estimates having a Mahalanobis distance to the second location estimate greater than the distance threshold are omitted from said determined third location estimate.

43. The system of claim 32 wherein the processor is further programmed to:

(v) determine an estimated location for said mobile device from said at least one network measurement report as a function of at least one characterizing parameter.

44. The system of claim 32 wherein the processor is further programmed to:

(v) compare an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report; and

(vi) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

45. The system of claim 32 wherein the processor is further programmed to:

(v) compare an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report;

(vi) if no exact match is made between the ordered list of neighboring cells of said network measurement report and any grid point in said geographic region then form a largest subset of the ordered list of neighboring cells in said grid points that provide a match; and

(vii) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

46. The system of claim 32 wherein the processor is further programmed to:

(v) compare an ordered list of cells neighboring a cell serving said mobile device in said network measurement report to an ordered list of neighboring cells in each grid point of said geographic region, said ordering being a function of any parameter of said network measurement report;

(vi) if the ordered list of neighboring cells of said network measurement report is not contained in the ordered list of neighboring cells for said geographic region then use a largest subset of neighboring cells in said network measurement report having either an exact match or is contained in the ordered list of neighboring cells in said geographic region; and

(vii) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a centroid of a cluster of matching grid points in said geographic region;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

47. The system of claim 32 wherein the processor is further programmed to:

(v) evaluate a probability density function for each power level of a cell neighboring a cell serving said mobile device in said network measurement report over each grid point in a set of available grid points in said geographic region;

(vi) determine a joint probability as a function of said individual probability density functions; and

(vii) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

48. The system of claim 32 wherein the processor is further programmed to:

(v) evaluate a joint probability of power levels for at least one cell neighboring a cell serving said mobile device in said network measurement report over a set of available grid points in said geographic region; and

(vi) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a highest joint probability matching grid point in said geographic region;

a weighted sum of the locations of a set of matching grid points in said geographic region;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

49. The system of claim 32 wherein the processor is further programmed to:

(v) determine a distortion measure between a parameter of a grid point and a corresponding parameter in said network measurement report; and

(vi) generate an estimated location of said mobile device wherein said estimated location is selected from the group consisting of;

a location of a grid point having the smallest distortion measure;

a weighted sum of the locations of a set of matching grid points in said geographic region, said weighted sum being a function of said distortion measure;

a weighted sum of clustered locations of a set of matching grid points in said geographic region; and

as a function of locations determined from subsets of said calibration data.

50. The system of claim 32 wherein the processor is further programmed to:

(v) match cell power ordering of cells neighboring a cell serving said mobile device in said network measurement report to neighboring cell power ordering of grid points in said geographic region; and

(vi) selecting an estimated location as a function of a quality of said matching,

wherein said quality is a function of a relative shift in an ordering sequence occurring between said network measurement report and grid point cell power ordering.

51. The system of claim 32 wherein the processor is further programmed to:

(v) determine a first region within said calibration data as a function of a first characterizing parameter of said at least one network measurement report and a predetermined range of said first parameter and repeat said determination for each characterizing parameter in said at least one network measurement report;

(vi) determine an intersection for each defined region; and

(vii) estimate the location of a mobile device in said geographic region as a function of said intersection.

52. The system of claim 32 wherein the processor is further programmed to:

(v) determine a first region within said calibration data as a function of a first characterizing parameter in a set of network measurement reports and a predetermined range of said first parameter and repeat said determination for each characterizing parameter in said set of network measurement reports;

(vi) determine a clustering of data vectors of said set, by location, in said geographic region; and

(vii) estimate the location of a mobile device in said geographic region as a function of said clustering.

53. The system of claim 32 wherein the processor is further programmed to:

(v) determine a representative value for each available characterizing parameter in a set of network measurement reports as a function of a variation of available characterizing parameters in each available network measurement report;

(vi) determine one or more representative network measurement reports as a function of said representative value; and

(vii) estimate the location of a mobile device in said geographic region as a function of said one or more representative network measurement reports.

54. The system of claim 53 wherein the processor is further programmed to:

(viii) determine a first region as a function of a first representative value for a first characterizing parameter and a predetermined range of said first value and repeat said determination for each characterizing parameter in said one or more representative network measurement reports;

(ix) determine an intersection of each defined region; and

(x) estimate the location of a mobile device in said geographic region as a function of said intersection.

55. The system of claim 32 wherein the processor is further programmed to select a set of grid points as a function of a criteria of fit.

56. The system of claim 55 wherein the criteria of fit is selected from the group consisting of:

total probability, cluster radius, Euclidean norm, Mahalanobis distance, distortion measure, confidence measure, and any combination thereof.

57. The system of claim 32 wherein the processor is further programmed to:

(i) select one or more candidate locations from one or more of said sets of grid points; and

(ii) evaluate said selected one or more candidate locations across said one or more sets of grid points,

wherein the determined location of the mobile device is a function of said evaluated selected locations.