System and method for determining a location area of a mobile user

• US 8,532,608 B2
• Filed: 10/20/2008
• Issued: 09/10/2013
• Est. Priority Date: 12/13/2007
• Status: Active Grant

• Current Assignee: InterDigital Patent Holdings, Inc. (InterDigital, Inc.)
• Original Assignee: Swisscom AG (Government of Switzerland)
• Inventors: Versteeg, Ernst, Taillard, Eric, Bailly, Patrick, Laurent, Maxence
• Primary Examiner(s): Mehrpour, Melody
• Assistant Examiner(s): STEPHEN, EMEM O
• Application Number:
  US12/254,452
• Publication Number:
  US 20090156231A1
• Time in Patent Office: 1,786 Days
• Field of Search: 455/404.2, 455/422.1, 455/423, 455/425, 455/433, 455/435.1, 455/435.2, 455/435.3, 4554561-4566, 701/214, 701/216, 701200-225, 340/8.1, 340/539.13, 340/539.21, 340/539.23, 340/870.04, 340/870.05, 340/905, 340/935, 340/936, 340/988, 340/989, 340/991, 340/995.18, 340/995, 3423572-358, 342/450, 342/457, 702/85, 702 94- 97, 702/142, 702/150
• US Class Current: 455/404.2
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04B 7/026 Co-operative diversity, e.g. using fixed or mobile stations as relays
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 64/003 locating network equipment

Abstract

A computer system determines location probabilities for defined sub-areas (41, 43) of a geographical area (4), e.g. for squares arranged in a grid (40), based on field strengths expected in the small sub-areas (41, 43) from the antennas (A1, A2 A3, A4), and based on the antenna used by the mobile communication terminal. The location probabilities indicate for a sub-area (41, 43) the probability that the mobile communication terminal is located in the respective sub-area (41, 43). The computer system determines at least one ellipse defining the location area, based on the location probabilities of the sub-areas (41, 43). The location probabilities make it possible to determine elliptical location areas of mobile users much smaller than the area each antenna does cover physically, but without the need for measuring at the mobile communication terminal signal properties such as signal strength or observed time differences.

Claims

1. A computer-implemented method of determining a location area of a user using a mobile communication terminal in a geographical area covered by a mobile radio network, the method comprising:

dividing the geographical area into a plurality of sub-areas;

determining for the sub- areas location probabilities, each location probability indicating the probability that the mobile communication terminal is located in the respective sub-area, based on field strengths expected in the sub-areas for antennas located in the geographical area, and based on the antenna used by the mobile communication terminal; and

determining at least one ellipse defining the location area, based on the location probabilities of the sub-areas wherein determining the at least one ellipse comprises;

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability;

assessing whether the single ellipse defines the location area with a defined minimal density of probable sub-areas; and

determining more than one ellipse for defining the location area, otherwise.

2. The method of claim 1, wherein determining the at least one ellipse comprises:

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability; and

defining the location area by the single ellipse, if the number of the probable sub-areas is lower than a defined maximum number of sub-areas and a density of the probable sub-areas is higher than a defined minimum density, and determining more than one ellipse for defining the location area, otherwise.

3. The method of claim 1, wherein determining more than one ellipse comprises:

determining sub-areas to be considered by selecting from the sub-areas with descending location probability those sub-areas which together make up at least a defined target probability;

grouping the sub-areas to be considered into areas of connected sub-areas; and

determining an ellipse around each of the areas of connected sub-areas to define the location area.

4. The method of claim 3, wherein grouping the sub-areas comprises:

determining an area of connected sub-areas by selecting with descending location probability, from the sub-areas to be considered, sub-areas which share a common border with a sub-area already included in the respective area of connected sub-areas;

removing selected sub-areas from the sub-areas to be considered; and

starting to determine an area of connected sub-areas with the sub-area of the remaining sub-areas to be considered having the highest location probability.

5. The method of claim 3, wherein determining more than one ellipse further comprises:

determining whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increasing the target probability, if the defined maximum number of ellipses is exceeded; and

repeating the determining of more than one ellipse using the increased target probability.

6. The method of claim 1, wherein determining more than one ellipse comprises:

using for enlarging an ellipse those sub-areas closest to the ellipse which have an intermediate area with at least a defined minimum mean location probability;

generating new ellipses at sub-areas where the mean location probability of the intermediate area is below the minimum mean location probability, if a maximum number of ellipses has not been reached.

7. The method of claim 6, wherein the intermediate area is a geometric object, placed between the sub-area in question and the closest ellipse to the sub-area in question.

8. The method of claim 6, wherein determining more than one ellipse further comprises:

lowering the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached; and

repeating the determining of more than one ellipse using the lowered minimum mean location probability.

9. A computer system for determining a location area of a user using a mobile communication terminal in a geographical area covered by a mobile radio network, the system comprising:

a sub-area definition module configured to divide the geographical area into a plurality of sub-areas;

an antenna determination module configured to determine the antenna used by the mobile communication terminal;

means for determining for the sub-areas location probabilities, each location probability indicating the probability that the mobile communication terminal is located in the respective sub-area, based on field strengths expected in the sub-areas for antennas located in the geographical area, and based on the antenna used by the mobile communication terminal; and

a location area determination module configured to determine at least one ellipse defining the location area, based on the location probabilities of the sub-areas by defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability;

assessing whether the number of the probable sub-areas is lower than a defined maximum of sub-areas and the single ellipse defines the location area with a defined minimal density of probable sub-areas; and

determining more than one ellipse for defining the location area, otherwise.

10. The system of claim 9, wherein the location area determination module is configured to determine more than one ellipse by determining sub-areas to be considered by selecting from the sub-areas with descending location probability those sub-areas which together make up at least a defined target probability;

grouping the sub-areas to be considered into areas of connected sub-areas; and

determining an ellipse around each of the areas of connected sub-areas to define the location area.

11. The system of claim 10, wherein the location area determination module is configured to group the sub-areas by determining an area of connected sub-areas by selecting with descending location probability, from the sub-areas to be considered, sub-areas which share a common border with a sub-area already included in the respective area of connected sub-areas;

removing selected sub-areas from the sub-areas to be considered; and

starting to determine an area of connected sub-areas with the sub-area of the remaining sub-areas to be considered having the highest location probability.

12. The system of claim 10, wherein the location area determination module is further configured to determine whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increase the target probability, if the defined maximum number of ellipses is exceeded; and

repeat the determining of more than one ellipse using the increased target probability.

13. The system of claim 9, wherein the location area determination module is configured to determine more than one ellipse by enlarging an ellipse using those sub-areas closest to the ellipse which have an intermediate area with at least a defined minimum mean location probability;

and generating new ellipses at sub-areas where the mean location probability of the intermediate area is below the minimum mean location probability, if a maximum number of ellipses has not been reached.

14. The system of claim 13, wherein the intermediate area is a geometric object placed between the sub-area in question and the closest ellipse to the sub-area in question.

15. The system of claim 13, wherein the location area determination module is further configured to lower the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached;

and repeat the determining of more than one ellipse using the lowered minimum mean location probability.

16. A non-transitory computer program product comprising computer program code means for controlling one or more processors of a computer system, such that the computer system:

stores a plurality of sub-areas for the geographical area;

determines the antenna used by the mobile communication terminal;

determines location probabilities for the sub-areas, each location probability indicating the probability that the mobile communication terminal is located in the respective sub-area, based on field strengths expected in the sub-areas for antennas located in the geographical area, and based on the antenna used by the mobile communication terminal; and

determines at least one ellipse defining the location area, based on the location probabilities of the sub-areas wherein determining the at least one ellipse comprises;

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability;

assessing whether the single ellipse defines the location area with a defined minimal density of probable sub-areas; and

determining more than one ellipse for defining the location area, otherwise.

17. The non-transitory computer program product of claim 16, wherein determining the at least one ellipse comprises:

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability; and

defining the location area by the single ellipse, if the number of the probable sub-areas is lower than a defined maximum number of sub-areas and a density of the probable sub-areas is higher than a defined minimum density, and determining more than one ellipse for defining the location area, otherwise.

18. The non-transitory computer program product of claim 16, wherein determining more than one ellipse comprises:

determining sub-areas to be considered by selecting from the sub-areas with descending location probability those sub-areas which together make up at least a defined target probability;

grouping the sub-areas to be considered into areas of connected sub-areas; and

determining an ellipse around each of the areas of connected sub-areas to define the location area.

19. The non-transitory computer program product of claim 18, wherein grouping the sub-areas comprises:

determining an area of connected sub-areas by selecting with descending location probability, from the sub-areas to be considered, sub-areas which share a common border with a sub-area already included in the respective area of connected sub-areas;

removing selected sub-areas from the sub-areas to be considered; and

starting to determine an area of connected sub-areas with the sub-area of the remaining sub-areas to be considered having the highest location probability.

20. The non-transitory computer program product of claim 18, wherein determining more than one ellipse further comprises:

determining whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increasing the target probability, if the defined maximum number of ellipses is exceeded; and

repeating the determining of more than one ellipse using the increased target probability.

21. The non-transitory computer program product of claim 16, wherein determining more than one ellipse comprises:

using for enlarging an ellipse those sub-areas closest to the ellipse which have an intermediate area with at least a defined minimum mean location probability;

generating new ellipses at sub-areas where the mean location probability of the intermediate area is below the minimum mean location probability, if a maximum number of ellipses has not been reached.

22. The non-transitory computer program product of claim 21, wherein the intermediate area is a geometric object, placed between the sub-area in question and the closest ellipse to the sub-area in question.

23. The non-transitory computer program product of one of claim 21, wherein determining more than one ellipse further comprises:

lowering the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached; and

repeating the determining of more than one ellipse using the lowered minimum mean location probability.

24. The method of claim 4, wherein determining more than one ellipse further comprises:

determining whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increasing the target probability, if the defined maximum number of ellipses is exceeded; and

repeating the determining of more than one ellipse using the increased target probability.

25. The system of claim 11, wherein the location area determination module is further configured to determine whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increasing the target probability, if the defined maximum number of ellipses is exceeded; and

repeating the determining of more than one ellipse using the increased target probability.

26. The system of claim 14, wherein the location area determination module is further configured to lower the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached;

and repeat the determining of more than one ellipse using the lowered minimum mean location probability.

27. A computer-implemented method of determining a location area of a user using a mobile communication terminal in a geographical area covered by a mobile radio network, the method comprising:

dividing the geographical area into a plurality of sub-areas;

determining for the sub- areas location probabilities, each location probability indicating the probability that the mobile communication terminal is located in the respective sub-area, based on field strengths expected in the sub-areas for antennas located in the geographical area, and based on the antenna used by the mobile communication terminal; and

determining at least one ellipse defining the location area, based on the location probabilities of the sub-areas, wherein determining the at least one ellipse comprises;

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability; and

defining the location area by the single ellipse, if the number of the probable sub-areas is lower than a defined maximum number of sub-areas and a density of the probable sub-areas is higher than a defined minimum density, and determining more than one ellipse for defining the location area, otherwise.

28. The method of claim 27, wherein determining the at least one ellipse comprises:

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability;

assessing whether the single ellipse defines the location area with the defined minimal density of probable sub-areas; and

determining more than one ellipse for defining the location area, otherwise.

29. The method of claim 27, wherein determining more than one ellipse comprises:

determining sub-areas to be considered by selecting from the sub-areas with descending location probability those sub-areas which together make up at least a defined target probability;

grouping the sub-areas to be considered into areas of connected sub-areas; and

determining an ellipse around each of the areas of connected sub-areas to define the location area.

30. The method of claim 29, wherein grouping the sub-areas comprises:

determining an area of connected sub-areas by selecting with descending location probability, from the sub-areas to be considered, sub-areas which share a common border with a sub-area already included in the respective area of connected sub-areas;

removing selected sub-areas from the sub-areas to be considered; and

starting to determine an area of connected sub-areas with the sub-area of the remaining sub-areas to be considered having the highest location probability.

31. The method of claim 27, wherein determining more than one ellipse comprises:

using for enlarging an ellipse those sub-areas closest to the ellipse which have an intermediate area with at least a defined minimum mean location probability;

generating new ellipses at sub-areas where the mean location probability of the intermediate area is below the minimum mean location probability, if a maximum number of ellipses has not been reached.

32. The method of claim 31, wherein the intermediate area is a geometric object, placed between the sub-area in question and the closest ellipse to the sub-area in question.

33. The method of claim 31, wherein determining more than one ellipse further comprises:

lowering the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached; and

repeating the determining of more than one ellipse using the lowered minimum mean location probability.

34. A non-transitory computer program product comprising computer program code means for controlling one or more processors of a computer system, such that the computer system:

stores a plurality of sub-areas for the geographical area;

determines the antenna used by the mobile communication terminal;

determines location probabilities for the sub-areas, each location probability indicating the probability that the mobile communication terminal is located in the respective sub-area, based on field strengths expected in the sub-areas for antennas located in the geographical area, and based on the antenna used by the mobile communication terminal; and

determines at least one ellipse defining the location area, based on the location probabilities of the sub-areas, wherein determining the at least one ellipse comprises;

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability; and

defining the location area by the single ellipse, if the number of the probable sub-areas is lower than a defined maximum number of sub-areas and a density of the probable sub-areas is higher than a defined minimum density, and determining more than one ellipse for defining the location area, otherwise.

35. The non-transitory computer program product of claim 34, wherein determining the at least one ellipse comprises:

defining a single ellipse around a polygon enveloping probable sub-areas having at least a defined minimum location probability;

assessing whether the single ellipse defines the location area with the defined minimal density of probable sub-areas; and

determining more than one ellipse for defining the location area, otherwise.

36. The non-transitory computer program product of claim 34, wherein determining more than one ellipse comprises:

determining sub-areas to be considered by selecting from the sub-areas with descending location probability those sub-areas which together make up at least a defined target probability;

grouping the sub-areas to be considered into areas of connected sub-areas; and

determining an ellipse around each of the areas of connected sub-areas to define the location area.

37. The non-transitory computer program product of claim 36, wherein grouping the sub-areas comprises:

determining an area of connected sub-areas by selecting with descending location probability, from the sub-areas to be considered, sub-areas which share a common border with a sub-area already included in the respective area of connected sub-areas;

removing selected sub-areas from the sub-areas to be considered; and

starting to determine an area of connected sub-areas with the sub-area of the remaining sub-areas to be considered having the highest location probability.

38. The non-transitory computer program product of claim 36, wherein determining more than one ellipse further comprises:

determining whether the number of ellipses obtained exceeds a defined maximum number of ellipses;

increasing the target probability, if the defined maximum number of ellipses is exceeded; and

repeating the determining of more than one ellipse using the increased target probability.

39. The non-transitory computer program product of claim 34, wherein determining more than one ellipse comprises:

using for enlarging an ellipse those sub-areas closest to the ellipse which have an intermediate area with at least a defined minimum mean location probability;

generating new ellipses at sub-areas where the mean location probability of the intermediate area is below the minimum mean location probability, if a maximum number of ellipses has not been reached.

40. The non-transitory computer program product of claim 39, wherein the intermediate area is a geometric object, placed between the sub-area in question and the closest ellipse to the sub-area in question.

41. The non-transitory computer program product of one of claim 39, wherein determining more than one ellipse further comprises:

lowering the defined minimum mean location probability of the intermediate area, if a defined target probability has not been reached; and

repeating the determining of more than one ellipse using the lowered minimum mean location probability.