EXTENDED CLUSTERING FOR IMPROVED POSITIONING

• US 20100062790A1
• Filed: 10/30/2006
• Published: 03/11/2010
• Est. Priority Date: 10/30/2006
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Wigren, Torbjorn
• Granted Patent: US 8,208,942 B2
• Time in Patent Office: Days
• US Class Current: 455/456.100
• CPC Class Codes: G01S 5/0018 Transmission from mobile station to base station
• CPC Class Codes: G01S 5/02 using radio waves using satellite radio beacon systems for determining position G01S19/00
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/02529 not involving signal parameters, i.e. only involving identifiers
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A method for clustering position determinations is used for providing position determination assisting data in a cellular communications network. The method comprises obtaining (209) a main cluster of points, which are results of high-precision position determinations. The method further comprises separating out (220) of at least two subclusters. The points of the subclusters have a local density of points which is above a predetermined local density threshold. A method for providing position determination assisting data in a cellular communications network comprising the clustering of position determinations is also presented as well as an arrangement for providing position determination assisting data in a cellular communications network, a node of a cellular communications network, a cellular communications network and a computer readable medium comprising position determination assisting data are disclosed.

Claims

1. Method for clustering position determinations for providing position determination assisting data in a cellular communications network, the method comprising:

obtaining a main cluster of points being results of high-precision position determinations; and

separating out at least two subclusters, the points of which having a local density of points above a predetermined local density threshold.

2. Method according to claim 1, where said separating out comprises:

determining a local density of points for each point in said main cluster of points.

3. Method according to claim 2, where said separating out further comprises:

selecting a point in said main cluster of points having a local density of points larger than said predetermined local density threshold to be included in a first subcluster;

including points of said main cluster of points in said first subcluster, said points included in said first subcluster having a local density of points that is larger than said predetermined local density threshold.

4. Method according to claim 3, where said points included in said first subcluster having a distance to any other point included in said first subcluster that is smaller than a predetermined distance threshold.

5. Method according to claim 4, where said selecting a point in the main cluster of points comprises selecting said point as a first reference point;

and

said including points comprises;

selecting a candidate point of said main cluster of points not being included in said first subcluster;

checking if said candidate point having a local density of points that is larger than said predetermined local density threshold and having a distance to said reference point that is smaller than said predetermined distance threshold;

including said candidate point in said first subcluster if a local density of points of said candidate point is larger than said predetermined local density threshold and if said candidate point having a distance to said reference point that is smaller than said predetermined distance threshold; and

repeating the selecting a candidate point, the checking, and the including the candidate point until no further points not being included in said first subcluster having a local density of points that is larger than said predetermined local density threshold and having a distance to said reference point that is smaller than said predetermined distance threshold remain.

6. Method according to claim 5, where said including points comprises:

selecting a new reference point among points in said first subcluster not previously being selected as a reference point;

repeating the selecting a candidate point, the checking, the including the candidate point, and the selecting a new reference point until all points in said first subcluster have been utilized as a reference point.

7. Method according to claim 3, where

said selecting a point in the main cluster of points comprises selecting the point in said main cluster of points having a highest local density of points to be included in a first subcluster and being selected as a start point;

and

said including points comprises;

selecting said start point as a reference point;

finding a closest neighbour point of said main cluster of points not being included in said first subcluster and not being utilized as start point;

checking if said closest neighbour point having a local density of points that is larger than said predetermined local density threshold;

including said closest neighbour point in said first subcluster and selecting said closest neighbour point as new reference point if a local density of points of said candidate point is larger than said predetermined local density threshold; and

repeating the finding a closest neighbour point, the checking if the closest neighbour point, and the including the closest neighbour point until said closest neighbour point having a local density of points that is smaller than said predetermined local density threshold;

selecting a point included in said first subcluster not previously being utilized as start point as a new start point; and

repeating the selecting the starting point, the finding a closest neighbour point;

the checking if the closest neighbour point;

the including the closest neighbour point;

the repeating the finding a closest neighbour point, the checking if the closest neighbour point, and the including the closest neighbour point; and

the selecting the point included in the first subcluster until all points included in said first subcluster have been utilized as start points.

8. Method according to claim 3, where said separating out comprises:

selecting a point in said main cluster of points having a local density of points larger than said predetermined local density threshold and not being included in any of the (n−

1) first subclusters to be included in an n;

th subcluster, where n is an integer larger than 1;

including points of said main cluster of points in said n;

th subcluster, said points included in said n;

th subcluster having a local density of points that is larger than said predetermined local density threshold not being included in any of the (n−

1) first subclusters.

9. Method according to claim 8, where

repeating the selecting the point in the main cluster selecting a point in said main cluster of points having a local density of points larger than said predetermined local density threshold and not being included in any of the (n−

1) first subclusters to be included in an n;

th subcluster and the including points of said main cluster of points in said n;

th subcluster starting with n equal to 2 and ending with n equal to N, where N is a maximum number of allowed subclusters.

10. Method according to claim 1, further comprising:

discarding subclusters having less than a predetermined number of included points.

11. Method according to claim 1, further comprising:

removing encircling subclusters.

12. Method according to claim 11, where the removing encircling subclusters comprises discarding of said encircling subclusters.

13. Method according to claim 11, where the removing encircling subclusters comprises splitting of said encircling subclusters in further subclusters.

14. Method according to claim 11, where the removing encircling subclusters comprises comparing an average of said local density of points with a ratio between a total number of points included in said encircling subcluster and an area spanned by said points in said encircling subcluster.

15. Method according to claim 11, where the removing encircling subclusters comprises comparing an average distance between points included in said encircling subcluster and a center of gravity of said points included in said encircling subcluster with a minimum distance between any of said points included in said encircling subcluster and said center of gravity of said points included in said encircling subcluster.

16. Method for providing position determination assisting data in a cellular communications network, the method comprising:

establishing a cell relation configuration for a user equipment;

said cell relation configuration comprising at least cell identities of cells, in which signals to/from said user equipment fulfill at least a specific radio condition criterion when received;

performing a high-precision position determination for said user equipment;

repeating said establishing and said performing a plurality of times;

clustering points being results of said high-precision position determinations belonging to the same cell relation configuration in separate main clusters of points;

splitting at least one of said separate main clusters of points in subclusters;

associating an area definition with at least one of said main clusters of points; and

creating position determination assisting data comprising a relation between said cell relation configurations and said associated area definitions.

17. Method according to claim 16, where the associating an area definition with at least one of said main clusters of points comprises the steps of:

associating a subarea definition with at least two of said subclusters of at least one of said main clusters of points; and

defining said area definition as an aggregate of said subarea definitions.

18. Arrangement for providing position determination assisting data in a cellular communications network, the arrangement comprising:

means for establishing a cell relation configuration for a user equipment;

said cell relation configuration comprising at least cell identities of cells, in which signals to/from said user equipment fulfill at least a specific radio condition criterion when received;

means for performing a high-precision position determination for said user equipment;

means for clustering results of said high-precision position determinations belonging to the same cell relation configuration in separate main clusters of points;

said means for clustering results being further arranged for separating out, from at least one of said separate main clusters of points, at least two subclusters, the points of which having a local density of points above a predetermined local density threshold; and

means for associating an area definition with at least two of said subclusters of said main clusters of points and creating position determination assisting data comprising a relation between said cell relation configurations and said associated area definitions.

19. Arrangement according to claim 18, where said means for clustering results being further arranged for determining a local density of points for each point in said main cluster of points.

20. Arrangement according to claim 19, where said means for clustering results being further arranged for:

selecting a point in said main cluster of points having a local density of points larger than said predetermined local density threshold to be included in a first subcluster; and

including points of said main cluster of points in said first subcluster, said included points having a local density of points that is larger than said predetermined local density threshold.

21. Node of a cellular communications network, comprising:

an arrangement comprising;

means for establishing a cell relation configuration for a user equipment;

said cell relation configuration comprising at least cell identities of cells, in which signals to/from said user equipment fulfill at least a specific radio condition criterion when received;

means for performing a high-precision position determination for said user equipment;

means for clustering results of said high-precision position determinations belonging to the same cell relation configuration in separate main clusters of points;

said means for clustering results being further arranged for separating out, from at least one of said separate main clusters of points, at least two subclusters, the points of which having a local density of points above a predetermined local density threshold; and

means for associating an area definition with at least two of said subclusters of said main clusters of points and creating position determination assisting data comprising a relation between said cell relation configurations and said associated area definitions.

22. Cellular communications network, comprising:

an arrangement comprising;

means for establishing a cell relation configuration for a user equipment;

said cell relation configuration comprising at least cell identities of cells, in which signals to/from said user equipment fulfill at least a specific radio condition criterion when received;

means for performing a high-precision position determination for said user equipment;

means for clustering results of said high-precision position determinations belonging to the same cell relation configuration in separate main clusters of points;

said means for clustering results being further arranged for separating out, from at least one of said separate main clusters of points, at least two subclusters, the points of which having a local density of points above a predetermined local density threshold; and

means for associating an area definition with at least two of said subclusters of said main clusters of points and creating position determination assisting data comprising a relation between said cell relation configurations and said associated area definitions.

23. Computer readable medium that stores instructions that, when executed by a processor, cause the processor to perform a method for clustering position determinations for providing position determination assisting data in a cellular communications network, the method comprising:

obtaining a main cluster of points being results of high-precision position determinations; and

separating out at least two subclusters, the points of which having a local density of points above a predetermined local density threshold.