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

• US 8,170,579 B2
• Filed: 01/24/2008
• Issued: 05/01/2012
• 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: Alles, Martin, Carlson, John, Maher, George, Mazlum, Selcuk
• Primary Examiner(s): Corsaro, Nick
• Assistant Examiner(s): Lebassi, Amanuel
• Application Number:
  US12/019,509
• Publication Number:
  US 20080188236A1
• Time in Patent Office: 1,559 Days
• Field of Search: 455/456.1, 455/414.2
• US Class Current: 455/456.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. Received signal level measurements reported by a mobile device for which a location estimate is to be determined may be compared with the data associated with the various grid points to estimate the location of the mobile device.

Claims

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

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from one network measurement report as a function of said at least one parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) comparing an ordered list of cells neighboring a cell serving said mobile device in said one network measurement report to an ordered list of neighboring cells in each grid point of said grid, said ordering being a function of at least one parameter of said one 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 grid;

a highest joint probability matching grid point in said grid;

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

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

as a function of estimated locations determined from subsets of said plurality of network measurement reports.

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

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

4. The method of claim 1 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

5. The method of claim 1 wherein the step of determining an estimated location for said mobile device further comprises:

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

6. The method of claim 5 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in, said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

7. The method of claim 1 wherein the step of determining an estimated location for said mobile device further comprises:

(iii) if the ordered list of neighboring cells of said one network measurement report is not contained in the ordered list of neighboring cells for said grid then using a largest subset of ordered neighboring cells in said one network measurement report having either an exact match or contained in the ordered list of neighboring cells in said grid.

8. The method of claim 7 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

9. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from one network measurement report as a function of said at least one parameter,

wherein the step of determining an estimated location for said mobile device Comprises;

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

(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 grid;

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

a weighted sum of clustered locations of a set of matching grid points

in said grid; and

as a function of estimated locations determined from subsets of said plurality of network measurement reports.

10. The method of claim 9 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

11. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from one network measurement report as a function of said at least one parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) evaluating a joint probability of power levels for at least one cell neighboring a cell serving said mobile device in said one network measurement report over a set of available grid points in said grid; 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 grid;

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

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

as a function of estimated locations determined from subsets of said plurality of network measurement reports.

12. The method of claim 11 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

13. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from one network measurement report as a function of said at least one parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) determining a distortion measure between a parameter or a function characterizing a grid point and a corresponding parameter or function in said one 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 grid, 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 grid; and

as a function of estimated locations determined from subsets of said plurality of network measurement reports.

14. The method of claim 13 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

15. The method of claim 13 wherein said distortion measure is a Mahalanobis distance.

16. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of Said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from one network measurement report as a function of said at least one parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) matching cell parameter ordering of cells neighboring a cell serving said mobile device in said one network measurement report to neighboring cell parameter ordering in each of the grid points in said grid; 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 one network measurement report and grid point cell parameter ordering.

17. The method of claim 16 further comprising filtering available grid points as a function of one characteristic selected from the group consisting of:

a matching of serving cell or sector for available grid points in said grid to the serving cell or sector of said one network measurement report;

a timing advance parameter from said one network measurement report;

a round trip time parameter from said one network measurement report;

a mobile device orientation parameter;

a serving cell identifier;

a serving control channel;

a magnitude of a serving cell forward link control channel received signal level;

a predetermined number of cell received signal levels common to said one network measurement report; and

any combination thereof.

18. The method of claim 16 wherein said parameter is selected from the group consisting of:

an ordered list of neighboring cells;

functions defined on the absolute neighboring cell power levels;

functions defined on the relative neighboring cell power differences;

serving cell;

serving sector;

timing advance parameter;

round trip time parameter;

individual probability density function of each neighboring cell power level;

individual probability distribution function of each neighboring cell power level;

joint probability density function of neighboring cell power levels;

joint probability distribution function of neighboring cell power levels;

mean and variance of neighboring cell power levels;

mobile device orientation;

a representation that enables retrieval of calibration data NMR vectors assigned to a respective NUG;

network state as indicated in the calibration data;

a confidence measure indicative of the reliability of the calibration data feeding a respective NUG; and

any combinations thereof.

19. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from a set of said plurality of network measurement reports as a function of said parameter,

wherein the step of determining an estimated location for said mobile device further comprises determining a cluster for each parameter in each network measurement report in said set of network measurement reports as a function of a metric to weight said cluster.

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

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

22. The method of claim 19 wherein said metric is selected from the group consisting of:

Mahalanobis distance, joint probability, probability density function, parameter quality, and any combination thereof.

23. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from a set of said plurality of network measurement reports as a function of said parameter,

wherein the step of determining an estimated location for said mobile device further comprises;

(i) determining a representative value for each parameter or function occurring in said set of network measurement reports; and

(ii) determining a cluster for each representative value as a function of a metric to weight said cluster.

24. The method of claim 23 wherein said representative value is selected from the group consisting of:

power level;

neighboring cell power level;

quality of measurements;

timing advance;

round trip time;

or any combination thereof.

25. The method of claim 23 wherein said representative value is determined as a function of a mean of a set of parameter values.

26. The method of claim 23 wherein said representative value is determined as a function of a median of a set of parameter values.

27. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from a set of said plurality of network measurement reports as a function of said parameter,

wherein the step of determining an estimated location for said mobile device further comprises;

(i) observing a transition in a parameter occurring in one or more network measurement reports within said set of network measurement reports; and

(ii) estimating a location of said mobile device on a boundary defined by a first range represented by said parameter before said transition and by a second range represented by said parameter after said transition.

28. The method of claim 27 wherein said parameter is selected from the group consisting of:

signal power level;

rate of dropping in/out of a neighboring cell signal;

pattern of dropping in/out of a neighboring cell signal;

signal quality;

changes in serving cell;

changes in serving sector;

timing advance;

round trip time; and

combinations thereof.

29. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from a set of said plurality of network measurement reports as a function of said parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) determining a distortion measure between a parameter or function of ones of said grid points and a corresponding parameter or function in each network measurement report in said set; and

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

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

a weighted sum of the locations of a set of matching grid points in said grid, 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 grid; and

as a function of estimated locations determined from subsets of said set of network measurement reports.

30. The method of claim 29 wherein said distortion measure is a Mahalanobis distance.

31. A method of estimating location of a mobile device in a geographic region comprising the steps of:

(a) providing a plurality of grid points in a geographic region, each of said grid points including at least one characterizing parameter and each of said grid points located on a grid defined over said geographic region;

(b) providing a plurality of network measurement reports for a mobile device in said geographic region; and

(c) determining an estimated location for said mobile device from a set of said plurality of network measurement reports as a function of said parameter,

wherein the step of determining an estimated location for said mobile device comprises;

(i) determining one or more representative values for each cell neighboring a serving cell serving said mobile device in said set of network measurement reports;

(ii) determining a distortion measure for each representative value as a function of a comparison between a selected parameter of ones of said grid points and a corresponding parameter for said each representative value; and

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

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

a weighted sum of the locations of a set of matching grid points in said grid, 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 grid; and

as a function of estimated locations determined from subsets of said set of network measurement reports.