System and Method for Mobile Location By Dynamic Clustering

• US 20120208553A1
• Filed: 02/14/2012
• Published: 08/16/2012
• Est. Priority Date: 02/14/2011
• Status: Active Grant

• Current Assignee: CommScope Technologies, LLC (CommScope Holding Company, Inc.)
• Original Assignee: Andrew LLC (CommScope Holding Company, Inc.)
• Inventors: Alles, Martin, Gravely, Thomas B., Al-Mufti, Khalid W.
• Granted Patent: US 8,526,968 B2
• Time in Patent Office: Days
• 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/02521 using a radio-map
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A system and method for determining the location of a mobile device in a communications network. A set of network measurement reports (NMR) may be provided for a region in the network. NMRs in the first set may be clustered as a function of observed measurement information in the NMRs. A candidate NMR for a mobile device may be received, and the candidate NMR may then be associated with a selected cluster of NMRs. The candidate NMR and a second set of NMRs may then be clustered, and a location of the mobile device determined as a function of the clustered candidate NMR and second set of NMRs, where the NMRs in the second set are associated with the selected cluster.

Claims

1. A method of determining the location of a mobile device in a communications network comprising the steps of:

(a) generating a first set of network measurement reports (NMR) for a region in a communications network;

(b) clustering measurement information from the first set of NMRs as a function of a common parameter of the measurement information;

(c) receiving a candidate NMR for a mobile device;

(d) comparing measurement information from the candidate NMR with the clustered measurement information from the first set of NMRs; and

(e) determining a location of the mobile device as a function of the compared measurement information.

2. The method of claim 1 wherein the location is determined as a function of a location corresponding to the compared measurement information.

3. The method of claim 1 wherein the NMR is a collection of measurement parameters observed at a geographic location in the communications network.

4. The method of claim 3 wherein the measurement parameters includes parameters selected from the group consisting of power levels, power differences, functions defined by power levels, functions defined by power differences, serving cell, serving sector, Timing Advance, Timing Advance equivalent, an ordered list of signal sources, round trip time, time difference of arrival, power density function of power levels, joint power density function of power levels, mobile device orientation, network state reported by the network, network state determined by an observing device, and combinations thereof.

5. The method of claim 1 wherein the NMR represents a single vector of observed measurement information, multiple vectors of observed measurement information, or a single vector representing multiple vectors of observed measurement information.

6. The method of claim 1 wherein the common parameter is a measure representing a commonality between measurement information of NMRs in the first set.

7. The method of claim 1 wherein the common parameter is determined as a function of the following relationship:

d_L1²(i,j)=d_O(i,j)*d_NS(i,j)*(d_RCV²(i,j)+d_DIV²(i,j))

where i and j each represent an NMR, d_O(i, j) represents a function comparing the observed measurements for ordered lists, d_NS(i, j) represents a function comparing network states, d_RCV²(i, j) represents a function comparing real continuous variables, and d_DIV²(i, j) represents a function comparing discrete integer variables.

8. The method of claim 1 further comprising the step of collecting calibration data from drive testing to thereby obtain an NMR.

9. The method of claim 1 further comprising the step of collecting calibration data from mobile devices in active communication in the communications network to thereby obtain an NMR.

10. The method of claim 1 wherein the step of clustering further comprises taking available measurement information from the first set of NMRs and providing a set of measurement information clusters based on common parameters in observation space.

11. The method of claim 1 wherein the step of clustering further comprises the steps of:

(i) selecting an arbitrary NMR from the first set of NMRs;

(ii) extracting NMRs from the first set having a common parameter with the arbitrary NMR;

(iii) generating a subset of NMRs including the extracted NMRs and the arbitrary NMR;

(iv) if the subset of NMRs is less than a predetermined threshold, then iterating steps (i)-(iii) until the threshold is met; and

(v) if the subset of NMRs meets the predetermined threshold, then determining a focus of the subset of NMRs in observation space.

12. The method of claim 11 wherein the step of comparing further comprises:

(i) assigning windows for each parameter type in the clustered measurement information;

(ii) comparing measurement information from the candidate NMR with the clustered measurement information from the subset of NMRs using assigned windows of a corresponding parameter type;

(iii) if the compared measurement information from the candidate NMR does not substantially correspond with a respective window, then adjusting the respective window until the compared measurement information from the candidate NMR substantially corresponds and re-clustering measurement information from a second set of NMRs; and

(iv) if the compared measurement information from the candidate NMR substantially corresponds with a respective window, then determining a location of the mobile device as a function of the location corresponding to the compared measurement information.

13. The method of claim 12 wherein the re-clustering further comprises:

(i) extracting measurement information from the second set of NMRs, the second set comprising at least the candidate NMR and NMRs from the subset or first set;

(ii) selecting an arbitrary NMR from the second set of NMRs;

(iii) extracting NMRs from the second set having a common parameter with the arbitrary NMR;

(iv) generating another subset of NMRs including the extracted NMRs and the arbitrary NMR;

(v) if the another subset of NMRs is less than a second threshold, then iterating steps (ii)-(iv) until the second threshold is met; and

(vi) if the subset of NMRs meets the second threshold, then determining a focus of the subset of NMRs in observation space.

14. The method of claim 1 wherein the step of comparing further comprises:

(i) assigning windows for each parameter type in the clustered measurement information;

(ii) comparing measurement information from the candidate NMR with the clustered measurement information from the first set of NMRs using assigned windows of a corresponding parameter type;

(iii) if the compared measurement information from the candidate NMR does not substantially correspond with a respective window, then adjusting the respective window until the compared measurement information from the candidate NMR substantially corresponds and re-clustering measurement information from a second set of NMRs; and

(iv) if the compared measurement information from the candidate NMR substantially corresponds with a respective window, then determining a location of the mobile device as a function of the location corresponding to the compared measurement information.

15. The method of claim 14 wherein the re-clustering further comprises:

(i) extracting measurement information from the second set of NMRs, the second set comprising at least the candidate NMR and NMRs from the first set;

(ii) selecting an arbitrary NMR from the second set of NMRs;

(iii) extracting NMRs from the second set having a common parameter with the arbitrary NMR;

(iv) generating a subset of NMRs including the extracted NMRs and the arbitrary NMR;

(v) if the subset of NMRs is less than a second threshold, then iterating steps (ii)-(iv) until the second threshold is met; and

(vi) if the subset of NMRs meets the second threshold, then determining a focus of the subset of NMRs in observation space.

16. The method of claim 1 wherein the determined location is a location corresponding to a centroid of the clustered measurement information.

17. The method of claim 1 wherein the determined location is a location corresponding of the closest NMR to a centroid of the clustered measurement information.

18. The method of claim 1 further comprising the step of re-clustering the compared measurement information using a second set of NMRs, the second set comprising at least the candidate NMR and NMRs from the first set.

19. A method of determining the location of a mobile device in a communications network comprising the steps of:

(a) collecting calibration data for a region in a communications network;

(b) providing a first set of measurement vectors in observation space using the collected calibration data;

(c) selecting available measurement information from the first set of vectors to create clusters based on a common parameter in observation space;

(d) receiving a candidate measurement vector for a mobile device;

(e) comparing measurement information from the candidate vector with the measurement information from the created clusters; and

(f) determining a location of the mobile device as a function of a location corresponding to the compared measurement information.

20. The method of claim 19 wherein the common parameter is a measure representing a commonality between measurement information of vectors in the set.

21. The method of claim 19 wherein the step of selecting further comprises:

(i) selecting a random vector from the set of vectors;

(ii) extracting vectors from the set having a common parameter with the random vector; and

(iii) generating a cluster of vectors including the extracted vectors and the arbitrary vector.

22. The method of claim 19 wherein the step of comparing further comprises:

(i) associating the candidate vector with a selected cluster of vectors; and

(ii) clustering the candidate vector and a second set of vectors,

wherein the vectors in the second set are associated with the selected cluster.

23. The method of claim 19 wherein the common parameter is determined as a function of the following relationship:

d_L1²(i,j)=d_O(i,j)*d_NS(i,j)*(d_RCV²(i,j)+d_DIV²(i,j))

where i and j each represent an NMR, d_O(i, j) represents a function comparing the observed measurements for ordered lists, d_NS(i, j) represents a function comparing network states, d_RCV²(i, j) represents a function comparing real continuous variables, and d_DIV²(i, j) represents a function comparing discrete integer variables.

24. A method of determining the location of a mobile device in a communications network comprising the steps of:

(a) providing a set of network measurement reports (NMR) for a region in the network;

(b) clustering NMRs in the first set as a function of observed measurement information in the NMRs;

(c) receiving a candidate NMR for a mobile device;

(d) associating the candidate NMR with a selected cluster of NMRs;

(e) clustering the candidate NMR and a second set of NMRs; and

(f) determining a location of the mobile device as a function of the clustered candidate NMR and second set of NMRs,

wherein the NMRs in the second set are associated with the selected cluster.

25. The method of claim 24 wherein the determined location is determined as a function of a centroid of the clustered candidate NMR and second set of NMRs.

26. The method of claim 24 wherein the determined location is the closest NMR to a centroid of the clustered candidate NMR and second set of NMRs.

27. The method of claim 24 wherein the step of clustering NMRs in the first set further comprises:

(i) selecting a random NMR from the first set of NMRs;

(ii) extracting NMRs from the first set having a common parameter with the random NMR; and

(iii) generating a cluster of NMRs including the extracted NMRs and the arbitrary NMR.

28. The method of claim 27 wherein the common parameter is determined as a function of the following relationship:

d_L1²(i,j)=d_O(i,j)*d_NS(i,j)*(d_RCV²(i,j)+d_DIV(i,j))

where i and j each represent an NMR, d_O(i, j) represents a function comparing the observed measurements for ordered lists, d_NS(i, j) represents a function comparing network states, d_RCV²(i, j) represents a function comparing real continuous variables, and d_DIV²(i, j) represents a function comparing discrete integer variables.

29. In a method for determining the location of a mobile device in a communications network comprising collecting calibration data for a region in the network and providing a set of network measurement reports (NMR) using the collected calibration data, each NMR having measurement information, the improvement comprising clustering NMRs in the set without regard to the location where the measurement information was obtained, receiving a candidate NMR for a target mobile device, associating the candidate NMR with a selected cluster of NMRs, combining measurement information from the candidate NMR with a second set of NMRs, and determining a location of the mobile device in the region as a function of a location corresponding to the combined measurement information.

30. The method of claim 29 wherein the determined location is a location corresponding to a centroid of the combined measurement information.

31. The method of claim 29 wherein the determined location is a location corresponding to the closest NMR to a centroid of the combined measurement information.

32. A method of determining the location of a mobile device in a communications network comprising the steps of:

(a) providing calibration data for a region in the network;

(b) clustering the calibration data as a function of observed measurement information in the data in observation space;

(c) receiving a candidate NMR containing for a mobile device;

(d) associating the candidate NMR with a selected cluster of calibration data proximate to the candidate NMR in observation space;

(e) clustering the candidate NMR and the selected cluster of calibration data in observation space; and

(f) determining a location of the mobile device as a function of the clustered candidate NMR and selected cluster of calibration data.

33. The method of claim 32 wherein the determined location is determined as a function of a centroid of the clustered candidate NMR and selected cluster of calibration data.

34. The method of claim 32 wherein the determined location is the closest NMR to a centroid of the clustered candidate NMR and selected cluster of calibration data.