Method and apparatus for aggregating terminals into clusters to assist in the construction of a distributed data communication network
First Claim
1. In a communication network having a number of terminals, backbone nodes for routing communication traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said network extending throughout a geographic region, a computer implemented method for aggregating the terminals into clusters comprising steps of:
- a) dividing said geographic region over which the network extends into subregions;
b) defining a number of subregions to be used, the square of the number of subregions being less than or equal to the number of terminals;
c) assigning each terminal to a subregion based on its geographic coordinates;
d) computing the total communication traffic within a backbone in each subregion;
e) computing a center of each subregion based on a weighted average of each terminal assigned to the subregion, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal;
f) retaining subregions with computed traffic greater than a predetermined significant traffic value as candidate clusters;
g) assigning those terminals not associated with a retained subregion to the nearest adjacent retained subregion, or if no such subregion is available placing the terminal in its own subregion;
h) merging the clusters based on user-defined parameters by clustering the smallest subregion with its nearest neighbors;
i) determining a center of the newly merged clusters based on a weighted average of each terminal of the cluster, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal;
j) choosing the location of the terminal closest to the center of each newly merged cluster as the representative location of that cluster; and
k) directing communication traffic from a first of said terminals through said terminal closest to the center of the cluster in which said first terminal is located to a second of said terminals through said terminal closest to the center of the cluster in which said second terminal is located.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for aggregating terminals into clusters that assists in the construction of a distributed data communication network. Terminal locations to be clustered are used as input along with a weight for each one representing the traffic carried by that location. The terminals are placed into boxes based on their geographic coordinates and only boxes with substantial traffic are retained. Any terminals included in a box not retained are assigned to the closest retained box. The retained boxes are merged into clusters so long as the maximum cluster traffic and maximum cluster radius are not exceeded. The center of mass of the resulting clusters are then determined. The representative locations of the resulting clusters are determined as the location of the terminal in the cluster closest to the center of mass.
-
Citations
51 Claims
-
1. In a communication network having a number of terminals, backbone nodes for routing communication traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said network extending throughout a geographic region, a computer implemented method for aggregating the terminals into clusters comprising steps of:
-
a) dividing said geographic region over which the network extends into subregions; b) defining a number of subregions to be used, the square of the number of subregions being less than or equal to the number of terminals; c) assigning each terminal to a subregion based on its geographic coordinates; d) computing the total communication traffic within a backbone in each subregion; e) computing a center of each subregion based on a weighted average of each terminal assigned to the subregion, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal; f) retaining subregions with computed traffic greater than a predetermined significant traffic value as candidate clusters; g) assigning those terminals not associated with a retained subregion to the nearest adjacent retained subregion, or if no such subregion is available placing the terminal in its own subregion; h) merging the clusters based on user-defined parameters by clustering the smallest subregion with its nearest neighbors; i) determining a center of the newly merged clusters based on a weighted average of each terminal of the cluster, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal; j) choosing the location of the terminal closest to the center of each newly merged cluster as the representative location of that cluster; and k) directing communication traffic from a first of said terminals through said terminal closest to the center of the cluster in which said first terminal is located to a second of said terminals through said terminal closest to the center of the cluster in which said second terminal is located. - View Dependent Claims (2, 3)
-
-
4. An apparatus for efficiently connecting a number of terminals through backbone nodes, a backbone, and concentrators including a computer based interactive device for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive device comprising:
-
a) a user input device of said computer receiving inputs including; a first set of data corresponding to terminal locations to be clustered, and a second set of data corresponding to weights corresponding to the traffic carried by each terminal location; and said user input device of said computer receiving specified parameters including; a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed; said user input device selecting a system output mode; b) a processor of said computer creating a number of subdivisions based on said total number of terminal clusters to be formed, wherein a square of the number of subdivisions is less than or equal to the number of terminals; said processor assigning each terminal to one of said group of subdivisions based on its location; said processor determining a total traffic for each of said group of subdivisions based on the weights of the terminals assigned to it by said processor; said processor determining a center of each of said group of subdivisions based on the weights and the locations of the terminals assigned to it by said processor; said processor forming a set of candidate subdivisions based on the total traffic for each of said group of subdivisions; said processor defining a location for each of said group of subdivisions; said processor assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions; said processor merging subdivisions in said set of candidate subdivisions into clusters; said processor updating centers of said clusters of merged subdivisions based on the weights and the locations of terminals of said clusters; and said processor determining the representative locations of said clusters of said merged subdivisions; and said processor directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. An apparatus for effectively connecting a number of terminals through backbone nodes, a backbone, and concentrators, including a computer based interactive device for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive device comprising:
-
a) a user input device of said computer receiving inputs including; a first set of data corresponding to terminal locations to be clustered, and a second set of data corresponding to weights corresponding to the traffic carried by each terminal location; and said user input device of said computer receiving specified parameters including; a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed; said user input device selecting a system output mode; b) a processor of said computer creating a number of subdivisions, wherein the square of the number of subdivisions is less than or equal to the number of terminals; said processor assigning each terminal to one of said number of subdivisions; said processor determining a total traffic for each of said number of subdivisions; said processor determining a center of each of said number of subdivisions; said processor forming a set of candidate subdivisions including some of said number of subdivisions; said processor defining a location for each of said number of subdivisions; said processor assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions; said processor merging subdivisions in said set of candidate subdivisions into clusters; said processor updating centers of said clusters of merged subdivisions; said processor determining the representative locations of said clusters of said merged subdivisions; and said processor directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located. - View Dependent Claims (25, 26, 27)
-
-
28. A method for efficiently connecting a number of terminals through backbone nodes, a backbone, and concentrators including a computer based interactive method for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive method comprising steps of:
-
inputting to said computer a first set of data corresponding to terminal locations to be clustered; inputting to said computer a second set of data corresponding to weights corresponding to the traffic carried by each terminal location; receiving in said computer specified parameters including a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed; selecting a system output mode; creating a number of subdivisions based on said total number of terminal clusters to be formed, wherein the square of the number of subdivisions is less than or equal to the number of terminals; assigning each terminal to one of said subdivisions based on its location; determining a total traffic for each of said subdivisions based on the weights of the terminals assigned to it by said assigning step; determining a center of each of said subdivisions based on the weights and the locations of the terminals assigned to it by said assigning step; forming a set of candidate subdivisions based on the total traffic for each of said subdivisions; defining a location for each of said subdivisions; assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions; merging subdivisions in said set of candidate subdivisions into clusters; updating centers of said clusters of merged subdivisions based on the weights and the locations of terminals of said clusters; determining the representative locations of said clusters of said merged subdivisions; and directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47)
-
-
48. A method for effectively connecting a number of terminals through backbone nodes, a backbone, and concentrators, including a computer implemented interactive method for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer implemented interactive method comprising steps of:
-
inputting to said computer a first set of data corresponding to terminal locations to be clustered; inputting to said computer a second set of data corresponding to weights corresponding to the traffic carried by each terminal location; receiving in said computer specified parameters including a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed; selecting a system output mode; creating a number of subdivisions, wherein the square of the number of subdivisions is less than or equal to the number of terminals; assigning each terminal to one of said subdivisions; determining a total traffic for each of said subdivisions; determining a center of each of said subdivisions; forming a set of candidate subdivisions including some of said subdivisions; defining a location for each of said subdivisions; assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions; merging subdivisions in said set of candidate subdivisions into clusters; updating centers of said clusters of merged subdivisions; determining the representative locations of said clusters of said merged subdivisions; and directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located. - View Dependent Claims (49, 50, 51)
-
Specification