Extended clustering for improved positioning

• US 8,208,942 B2
• Filed: 10/30/2006
• Issued: 06/26/2012
• Est. Priority Date: 10/30/2006
• Status: Expired due to Fees

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Wigren, Torbjorn
• Primary Examiner(s): Patel, Nimesh
• Application Number:
  US12/447,841
• Publication Number:
  US 20100062790A1
• Time in Patent Office: 2,066 Days
• Field of Search: 455/440, 455/456.1, 455/433, 455/446, 342/457, 342/465
• US Class Current: 455/456.1
• 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 for different positions of user equipment terminals in communication with the cellular communications network; and

separating out the points that are the results of the high-precision position determinations into at least two subclusters of the points, the respective points of each of the subclusters having a local positional density of points above a predetermined local positional density threshold, where said separating out comprises,

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

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

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

2. Method according to claim 1, 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.

3. Method according to claim 2, 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 positional density of points that is larger than said predetermined local positional 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 positional density of points of said candidate point is larger than said predetermined local positional 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 positional density of points that is larger than said predetermined local positional density threshold and having a distance to said reference point that is smaller than said predetermined distance threshold remain.

4. Method according to claim 3, 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.

5. Method according to claim 1, 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 positional 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 positional density of points that is larger than said predetermined local positional density threshold;

including said closest neighbour point in said first subcluster and selecting said closest neighbour point as new reference point if a local positional density of points of said candidate point is larger than said predetermined local positional 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 positional density of points that is smaller than said predetermined local positional 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, 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.

6. Method according to claim 1, where selecting a point comprises selecting a first point, and where said separating out comprises:

selecting a second point in said main cluster of points having a local positional density of points larger than said predetermined local positional density threshold and not being included in any of the first subcluster to be included in a second subcluster; and

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

7. Method according to claim 6, where said separating out further comprises:

selecting a third point in said main cluster of points having a local positional density of points larger than said predetermined local positional density threshold and not being included in any of the first and second subclusters to be included in a third subcluster; and

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

8. Method according to claim 1, further comprising:

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

9. Method according to claim 1, further comprising:

removing encircling subclusters.

10. Method according to claim 9, where the removing encircling subclusters comprises discarding of said encircling subclusters.

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

12. Method according to claim 9, where the removing encircling subclusters comprises comparing an average of said local positional 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.

13. Method according to claim 9, 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.

14. Method according to claim 1 wherein the high-precision position determinations are configured to provide positioning accuracy of 100 meters at 67% and positioning accuracy of 300 meters at 95%.

15. Method according to claim 1 wherein the high-precision position determinations are made using Global Positioning System (GPS) positioning and/or Uplink Time Difference Of Arrival (UTDOA) positioning.

16. Method according to claim 1 wherein obtaining the main cluster comprises obtaining the main cluster at a clustering section of the communications network and wherein separating out the points comprises separating out the points at the clustering section of the communications network.

17. Method according to claim 1 further comprising:

providing a position determination for a particular user equipment terminal using at least one of the subclusters.

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

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

performing high-precision position determinations for different positions of said user equipment terminals;

repeating said establishing a cell relation configuration and said performing a high-precision position determinations 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 into a plurality of 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;

where said splitting comprises,

determining a local positional density of points for each point in said at least one of said main clusters of points,

selecting a point in said at least one of said main clusters of points having a local positional density of points larger than a predetermined local positional density threshold to be included in a first subcluster, and

including points of said at least one of said main clusters of points in said first subcluster, said points included in said first subcluster having a local positional density of points that is larger than said predetermined local positional density threshold.

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

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.

20. Method according to claim 18 wherein the high-precision position determinations are made using Global Positioning System (GPS) positioning and/or Uplink Time Difference Of Arrival (UTDOA) positioning.

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

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

means for performing high-precision position determinations for different positions of said user equipment terminals in communication with the cellular communications network;

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 of the points, the respective points of each of the subclusters having a local positional density of points above a predetermined local positional 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;

said means for clustering results being further arranged for,

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

selecting a point in said main cluster of points having a local positional density of points larger than said predetermined local positional 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 positional density of points that is larger than said predetermined local positional density threshold.

22. Arrangement according to claim 21 wherein the high-precision position determinations are made using Global Positioning System (GPS) positioning and/or Uplink Time Difference Of Arrival (UTDOA) positioning.

23. Node of a cellular communications network, comprising:

an arrangement comprising;

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

means for performing high-precision position determinations for different positions of said user equipment terminals in communication with the cellular communications network;

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 of the points, the respective points of each of the subclusters having a local positional density of points above a predetermined local positional 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;

where said means for clustering results being further arranged for,

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

selecting a point in said main cluster of points having a local positional density of points larger than said predetermined local positional 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 positional density of points that is larger than said predetermined local positional density threshold.

24. Cellular communications network, comprising:

an arrangement comprising;

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

means for performing high-precision position determinations for different positions of said user equipment terminals in communication with said cellular communications network;

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 of the points, the respective points of each of the subclusters having a local positional density of points above a predetermined local positional 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;

where said means for clustering results being further arranged for,

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

selecting a point in said main cluster of points having a local positional density of points larger than said predetermined local positional 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 positional density of points that is larger than said predetermined local positional density threshold.

25. Non-transitory 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 for different positions of user equipment terminals in communication with the cellular communications network; and

separating out the points that are the results of the high-precision position determinations into at least two subclusters of the points, the respective points of each of the subclusters having a local positional density of points above a predetermined local positional density threshold, where said separating out comprises,

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

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

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

26. Computer readable medium according to claim 25 wherein the computer readable medium comprises a data memory device.