System and method for generating non-uniform grid points from calibration data
View Patent ↗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.
1. A method of assigning geographical coordinates to a grid point located in a geographic region for the location of a mobile device, comprising:
(a) providing calibration data for each of one or more calibration points in the geographic region;
(b) for each of said calibration points:
(i) evaluating the associated calibration data;
(ii) determining if at least one grid point should be defined based on said evaluation; and
(iii) assigning geographical coordinates to said at least one grid point,
(c) determining geographical coordinates for each of a plurality of nodes of a uniform grid spanning said geographic region; and
(d) for each of said at least one grid point:
(i) determining a closest node from said plurality of nodes; and
(ii) assigning characteristic data associated with said grid point to said closest node,
wherein for each of select ones of said calibration points the calibration data includes plural data vectors and the evaluating of said calibration data comprises a determination of clustering of said plural data vectors,
and wherein said characteristic data comprises data selected from the group consisting of: a list of cells neighboring a cell serving said mobile device; a quantity that is a function of a power level of one or more cells neighboring a cell serving said mobile device; an identity of a cell or a sector serving said mobile device; a timing advance parameter; a geographical orientation of said mobile device; a location of said mobile device; network measurement report data vectors; a state of a network serving said mobile device; a confidence measure indicative of a reliability of the calibration data; and combinations thereof.
2. The method of claim 1 wherein one of said calibration points is located on a predetermined fixed uniform grid defined over said region.
3. The method of claim 1 wherein one of said calibration points is randomly located within said region.
4. The method of claim 1 wherein said calibration data comprises information from a network measurement report.
5. The method of claim 1 wherein said calibration data for one of said calibration points is obtained from one or more mobile devices located in close proximity to said one calibration point.
6. The method of claim 1 wherein said calibration data for one of said calibration points is obtained from a signal transmitted from a mobile device in close proximity to said one calibration point and received at a receiver in or in proximity to said region.
7. The method of claim 1 wherein said determining if at least one grid point should be defined based on said evaluation includes:
(A) comparing a first cluster of data vectors from a first one of said select calibration points to a second cluster of data vectors comprising said first cluster of data vectors and data vectors from a second one of said select calibration points; and
(B) if said comparison is within a predetermined tolerance, assigning said data vectors from said first and said second calibration points to the same grid point, otherwise assigning the data vectors from said first calibration point to a first grid point and assigning the data vectors from said second calibration point to a second grid point.
8. The method of claim 7 wherein said determination of clustering of said plural data vectors includes a K-means algorithm analysis and wherein said comparing of a cluster of data vectors includes determining a probability density function of an aspect of said data vectors.
9. The method of claim 1 further comprising determining outlier data vectors and eliminating said outliers from said determination of clustering.
10. The method of claim 1 wherein said determining if at least one grid point should be defined based on said evaluation includes:
(A) comparing a first cluster of data vectors from a first one of said select calibration points to a second cluster of data vectors from said first one of said select calibration points; and
(B) if said comparison is within a predetermined tolerance, assigning said data vectors from said first and said second clusters to the same grid point, otherwise assigning the data vectors from said first cluster to a first grid point and assigning the data vectors from said second cluster to a second grid point.
11. The method of claim 10 wherein the geographical coordinates assigned to said first and second grid points are identical.
12. The method of claim 1 wherein the geographical coordinates assigned to said at least one grid point are different than the geographical coordinates of any of said calibration points.
13. The method of claim 1 wherein the geographical coordinates assigned to said at least one grid point are the same as the geographical coordinates of one of said calibration points.
14. The method of claim 1 wherein only one calibration point is in said geographic region and the geographical coordinates assigned to said at least one grid point result in said at least one grid point being located within a predetermined radius of said one calibration point.
15. The method of claim 1 wherein only one calibration point is in said geographic region and the geographical coordinates assigned to said at least one grid point are identical to geographic coordinates of said one calibration point.
16. The method of claim 1 wherein plural calibration points are in said geographic region and wherein the geographical coordinates assigned to said at least one grid point result in said at least one grid point being located within a predetermined radius of a geographic centroid determined from geographic coordinates of said plural calibration points.
17. The method of claim 1 wherein said calibration data 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 calibration point; signal strength of a signal transmitted by a transmitter located at said calibration point as received by a receiver at a known location; round trip time for a signal traveling between said calibration point and a known location; timing advance of a signal received by said mobile device at said calibration point; time difference of arrival of plural signals at said calibration point with respect to a pair of known locations as measured by a receiver at said calibration point or at said known locations; the identification of a serving cell or serving sector of said mobile device located at said calibration point; a state of a wireless network serving said mobile device, and combinations thereof.
18. The method of claim 1 wherein said evaluating the associated calibration data includes an evaluation selected from the group consisting of: a minimum number of unique neighboring calibration points as determined by calibration data of said neighboring calibration points; a minimum number of data vectors or network measurement reports; a predetermined maximum or minimum radius from said calibration point; a predetermined set of cells neighboring a cell serving said mobile device; and combinations thereof.
19. The method of claim 1 further comprising populating a database with said geographical coordinates.
20. The method of claim 19 further comprising populating said database with information selected from the group consisting of: a list of cells neighboring a cell serving said mobile device; a quantity that is a function of a power level of one or more cells neighboring a cell serving said mobile device; an identity of a cell or a sector serving said mobile device; a timing advance parameter; a geographical orientation of said mobile device; a location of said mobile device; network measurement report data vectors; a state of a network serving said mobile device; a confidence measure indicative of a reliability of the calibration data; and combinations thereof.
21. A method of assigning geographical coordinates to a grid point located in a geographic region for the location of a mobile device, comprising:
(a) providing calibration data for each of one or more calibration points in the geographic region;
(b) for the calibration data associated with each of said calibration points:
(i) evaluating the associated calibration data;
(ii) determining if at least one grid point should be defined based on said evaluation; and
(iii) assigning geographical coordinates to said at least one grid point,
(c) determining geographical coordinates for each of a plurality of nodes of a uniform grid spanning said geographic region; and
(d) for each of said at least one grid point:
(i) determining a closest node from said plurality of nodes; and
(ii) assigning characteristic data associated with said grid point to said closest node,
wherein for each of select ones of said calibration points the calibration data includes plural data vectors and the evaluating of said calibration data comprises a determination of clustering of said plural data vectors,
and wherein said characteristic data comprises data selected from the group consisting of: a list of cells neighboring a cell serving said mobile device; a quantity that is a function of a power level of one or more cells neighboring a cell serving said mobile device; an identity of a cell or a sector serving said mobile device; a timing advance parameter; a geographical orientation of said mobile device; a location of said mobile device; network measurement report data vectors; a state of a network serving said mobile device; a confidence measure indicative of a reliability of the calibration data; and combinations thereof.
22. A system for assigning geographical coordinates to a grid point located in a geographic region, comprising:
a database; and
a processor for receiving calibration data for each of one or more calibration points in said geographic region and for each of said calibration points said processor is programmed to:
evaluate the associated calibration data;
determine if at least one grid point should be defined based on said evaluation;
assign geographical coordinates to said at least one grid point; and
populate said database with said geographical coordinates,
said processor further programmed to:
determine geographical coordinates for each of a plurality of nodes of a uniform grid spanning said geographic region; and
for each of said at least one grid point, determining a closest node from said plurality of nodes; and assigning characteristic data associated with said grid point to said closest node,
wherein for each of select ones of said calibration points the calibration data includes plural data vectors and the evaluating of said calibration data comprises a determination of clustering of said plural data vectors,
and wherein said characteristic data comprises data selected from the group consisting of: a list of cells neighboring a cell serving said mobile device; a quantity that is a function of a power level of one or more cells neighboring a cell serving said mobile device; an identity of a cell or a sector serving said mobile device; a timing advance parameter; a geographical orientation of said mobile device; a location of said mobile device; network measurement resort data vectors; a state of a network serving said mobile device; a confidence measure indicative of a reliability of the calibration data; and combinations thereof.
23. The system of claim 22 wherein one of said calibration points is located on a predetermined fixed uniform grid defined over said region.
24. The system of claim 22 wherein one of said calibration points is randomly located within said region.
25. The system of claim 22 wherein said calibration data comprises information from a network measurement report.
26. The system of claim 22 wherein said calibration data for one of said calibration points is obtained from one or more mobile devices located in close proximity to said one calibration point.
27. The system of claim 22 wherein said calibration data for one of said calibration points is obtained from a signal transmitted from a mobile device in close proximity to said one calibration point and received at a receiver in or in proximity to said region.
28. The system of claim 22 wherein said determining if at least one grid point should be defined based on said evaluation includes:
(A) comparing a first cluster of data vectors from a first one of said select calibration points to a second cluster of data vectors comprising said first cluster of data vectors and data vectors from a second one of said select calibration points; and
(B) if said comparison is within a predetermined tolerance, assigning said data vectors from said first and said second calibration points to the same grid point, otherwise assigning the data vectors from said first calibration point to a first grid point and assigning the data vectors from said second calibration point to a second grid point.
29. The system of claim 28 wherein said determination of clustering of said plural data vectors includes a K-means algorithm analysis and wherein said comparing of a cluster of data vectors includes determining a probability density function of an aspect of said data vectors.
30. The system of claim 22 wherein said processor is further programmed to determine outlier data vectors and eliminating said outliers from said determination of clustering.
31. The system of claim 22 wherein said determining if at least one grid point should be defined based on said evaluation includes:
(A) comparing a first cluster of data vectors from a first one of said select calibration points to a second cluster of data vectors from said first one of said select calibration points; and
(B) if said comparison is within a predetermined tolerance, assigning said data vectors from said first and said second clusters to the same grid point, otherwise assigning the data vectors from said first cluster to a first grid point and assigning the data vectors from said second cluster to a second grid point.
32. The system of claim 31 wherein the geographical coordinates assigned to said first and second grid points are identical.
33. The system of claim 22 wherein the geographical coordinates assigned to said at least one grid point are different than the geographical coordinates of any of said calibration points.
34. The system of claim 22 wherein the geographical coordinates assigned to said at least one grid point are the same as the geographical coordinates of one of said calibration points.
35. The system of claim 22 wherein only one calibration point is in said geographic region and the geographical coordinates assigned to said at least one grid point result in said at least one grid point being located within a predetermined radius of said one calibration point.
36. The system of claim 22 wherein only one calibration point is in said geographic region and the geographical coordinates assigned to said at least one grid point are identical to geographic coordinates of said one calibration point.
37. The system of claim 22 wherein plural calibration points are in said geographic region and wherein the geographical coordinates assigned to said at least one grid point result in said at least one grid point being located within a predetermined radius of a geographic centroid determined from geographic coordinates of said plural calibration points.
38. The system of claim 22 wherein said calibration data 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 calibration point; signal strength of a signal transmitted by a transmitter located at said calibration point as received by a receiver at a known location; round trip time for a signal traveling between said calibration point and a known location; timing advance of a signal received by said mobile device at said calibration point; time difference of arrival of plural signals at said calibration point with respect to a pair of known locations as measured by a receiver at said calibration point or at said known locations; the identification of a serving cell or serving sector of said mobile device located at said calibration point; a state of a wireless network serving said mobile device, and combinations thereof.
39. The system of claim 22 wherein said evaluating the associated calibration data includes an evaluation selected from the group consisting of: a minimum number of unique neighboring calibration points as determined by calibration data of said neighboring calibration points; a minimum number of data vectors or network measurement reports; a predetermined maximum or minimum radius from said calibration point; a predetermined set of cells neighboring a cell serving said mobile device; and combinations thereof.
40. The system of claim 22 wherein said processor is further programmed to populate said database with information selected from the group consisting of: a list of cells neighboring a cell serving said mobile device; a quantity that is a function of a power level of one or more cells neighboring a cell serving said mobile device; an identity of a cell or a sector serving said mobile device; a timing advance parameter; a geographical orientation of said mobile device; a location of said mobile device; network measurement report data vectors; a state of a network serving said mobile device; a confidence measure indicative of a reliability of the calibration data; and combinations thereof.
41. The system of claim 22 further comprising:
circuitry for determining geographical coordinates for each of a plurality of nodes of a uniform grid spanning said geographic region; and
circuitry for determining, for each of said at least one grid point, a closest node from said plurality of nodes and assigning characteristic data associated with said grid point to said closest node.