Granted Patent B2

US 12,250,123 · App. 17/502,031 · Granted Mar 11, 2025

Inventors: Tianjiao Wang (Linyi, CN); Zengfu Wang (Xi'an, CN); Moshe Zukerman (Hong Kong, HK); Bill Moran (Balwyn, AU)

Assignee: City University of Hong Kong

H04L41/12H04L12/44H04L45/12

Abstract

Claims (79)

1. A computer-implemented method for method for planning regional connectivity of a cable network on a surface of the earth in a bounded closed region, comprising: modelling the surface of the earth in the bounded closed region as an irregular two-dimensional manifold comprising a plurality of grid nodes in a three-dimensional Euclidean space;

prespecifying a topology for the cable network;

modelling the prespecified topology as a Steiner tree including a plurality of terminal nodes representing a plurality of cable landing stations (CLSs) to be installed respectively in a plurality of destination regions connected by the cable network, a plurality of Steiner nodes presenting a plurality of branching units (BUs) to be installed in the cable network, and a plurality of edges connecting the terminal nodes and Steiner nodes;

finding a Steiner minimal tree (SMT) with the least cost in the Steiner tree;

returning coordinates of Steiner nodes of the SMT as locations of the BUS;

returning coordinates of terminal nodes of the SMT as locations of the CLSs; and

finding geodesics corresponding to edges of the SMT as cable paths between the BUs and CLSs;

wherein the SMT is found by:

defining a subtree consisted of only Steiner nodes and edges connecting the Steiner nodes to each other in the Steiner tree as a skeleton tree;

choosing an arbitrary Steiner node in the skeleton tree as a root node of the skeleton tree;

assigning an orientation to each of the edges toward to the root node; and

arranging the Steiner nodes in a topological order to obtain a sequence of the Steiner nodes so that children Steiner node of a given Steiner node appear in the sequence earlier than the given Steiner node;

associating each of the Steiner nodes with a subset of grid nodes;

constructing a directed acyclic graph (DAG) containing a plurality of directed paths, each consisted of grid nodes associated with different Steiner nodes and ended at a grid node associated with the root node; and

finding an optimal DAG with the least cost and returning the optimal DAG as the SMT; and

wherein the optimal DAG is found by applying a DAG-Least-Cost-System algorithm comprising:

initializing a plurality of minimum cumulative costs (MCCs) corresponding to the grid nodes associated with the Steiner nodes respectively;

updating a plurality of initialized MCCs for the grid nodes associated with the root node;

finding a grid node with the smallest MCC among the grid nodes associated with the root node as an optimal root node; and

returning the DAG containing the optimal root node as the optimal DAG.

2. The computer-implemented method according to claim 1 , wherein each of the plurality of MCCs corresponding the grid nodes associated the Steiner nodes is initialized by:

determining if the Steiner node is a leaf node of the skeleton tree;

if the Steiner node is a leaf node of the skeleton tree, initializing a MCC for the grid node to be a sum of one or more minimum costs from neighboring terminal nodes to the grid node; and

if the Steiner node is not a leaf node of the skeleton tree, initializing a MCC for the grid node to be zero.

3. The computer-implemented method according to claim 2 , wherein each of the minimum costs from neighboring terminal nodes to the grid node is obtained by applying a fast marching method comprising:

generating one or more potential paths from the neighboring terminal to the grid node;

calculating one or more costs for the one or more potential paths based on a cost model; and

returning the smallest cost as the minimum cost for from the neighboring terminal to the grid node; and

wherein the cost model is modelled with a set of cost factors includes cable laying cost, BU construction cost and CLS construction costs.

4. The computer-implemented method according to claim 3 , wherein the plurality of initialized MCCs for the grid nodes associated with the root node are updated by performing a plurality of iteration in the topological order for each of the grid nodes associated with each of the Steiner nodes in the skeleton tree.

5. The computer-implemented method according to claim 4 , wherein each of the iteration comprises:

determining if the Steiner node is a leaf node of the skeleton tree;

if the Steiner node is not a leaf node of the skeleton tree, updating the initialized MCC for the grid node associated with the Steiner node by adding one or more MCC increments, each derived from a grid node associated with a child node of the Steiner node.

6. The computer-implemented method according to claim 5 , wherein each of the one or more MCC increments is derived by:

determining if the child node has the same location as the Steiner node;

if the child node has the same location as the Steiner node, determining the MCC increment to be equal to a MCC for the grid node associated with the child node;

if the child node has a different location from the Steiner node, determining the MCC increment to be equal to a sum of the MCC for the grid node associated with the child node and a BU construction cost at the grid node associated with the Steiner node.

7. The computer-implemented method according to claim 1 , wherein the irregular two-dimensional manifold is a triangulated piecewise-linear two-dimensional manifold.

8. The computer-implemented method according to claim 1 , wherein each Steiner nodes of the SMT have a number of branches equal or greater than three.

9. A non-transitory computer readable medium for storing computer instructions that, when executed by one or more processors, causes the one or more processors to perform a method for planning regional connectivity of a cable network on a surface of the earth in a bounded closed region, the method comprising:

modelling the surface of the earth in the bounded closed region as an irregular two-dimensional manifold comprising a plurality of grid nodes in a three-dimensional Euclidean space;

prespecifying a topology for the cable network;

modelling the prespecified topology as a Steiner tree including a plurality of terminal nodes representing a plurality of cable landing stations (CLSs) to be installed respectively in a plurality of destination regions connected by the cable network, a plurality of Steiner nodes presenting a plurality of branching units (BUs) to be installed in the cable network, and a plurality of edges connecting the terminal nodes and Steiner nodes;

finding a Steiner minimal tree (SMT) with the least cost in the Steiner tree;

returning coordinates of Steiner nodes of the SMT as locations of the BUS;

returning coordinates of terminal nodes of the SMT as locations of the CLSs; and

finding geodesics corresponding to edges of the SMT as cable paths between the BUs and CLSs;

wherein the SMT is found by:

defining a subtree consisted of only Steiner nodes and edges connecting the Steiner nodes to each other in the Steiner tree as a skeleton tree;

choosing an arbitrary Steiner node in the skeleton tree as a root node of the skeleton tree;

assigning an orientation to each of the edges toward to the root node; and

arranging the Steiner nodes in a topological order to obtain a sequence of the Steiner nodes so that children Steiner node of a given Steiner node appear in the sequence earlier than the given Steiner node;

associating each of the Steiner nodes with a subset of grid nodes;

constructing a directed acyclic graph (DAG) containing a plurality of directed paths, each consisted of grid nodes associated with different Steiner nodes and ended at a grid node associated with the root node; and

finding an optimal DAG with the least cost and returning the optimal DAG as the SMT; and

wherein the optimal DAG is found by applying a DAG-Least-Cost-System algorithm comprising:

initializing a plurality of minimum cumulative costs (MCCs) corresponding to the grid nodes associated with the Steiner nodes respectively;

updating a plurality of initialized MCCs for the grid nodes associated with the root node;

finding a grid node with the smallest MCC among the grid nodes associated with the root node as an optimal root node; and

returning the DAG containing the optimal root node as the optimal DAG.

10. The non-transitory computer readable medium according to claim 9 , wherein each of the plurality of MCCs corresponding the grid nodes associated the Steiner nodes is initialized by:

determining if the Steiner node is a leaf node of the skeleton tree;

if the Steiner node is a leaf node of the skeleton tree, initializing a MCC for the grid node to be a sum of one or more minimum costs from neighboring terminal nodes to the grid node; and

if the Steiner node is not a leaf node of the skeleton tree, initializing a MCC for the grid node to be zero.

11. The non-transitory computer readable medium according to claim 10 , wherein each of the minimum costs from neighboring terminal nodes to the grid node is obtained by applying a fast marching method comprising:

generating one or more potential paths from the neighboring terminal to the grid node;

calculating one or more costs for the one or more potential paths based on a cost model; and

returning the smallest cost as the minimum cost for from the neighboring terminal to the grid node; and

wherein the cost model is modelled with a set of cost factors includes cable laying cost, BU construction cost and CLS construction costs.

12. The non-transitory computer readable medium according to claim 11 , wherein the plurality of initialized MCCs for the grid nodes associated with the root node are updated by performing a plurality of iteration in the topological order for each of the grid nodes associated with each of the Steiner nodes in the skeleton tree.

13. The non-transitory computer readable medium according to claim 12 , wherein each of the iteration comprises:

determining if the Steiner node is a leaf node of the skeleton tree;

if the Steiner node is not a leaf node of the skeleton tree, updating the initialized MCC for the grid node associated with the Steiner node by adding one or more MCC increments, each derived from a grid node associated with a child node of the Steiner node.

14. The non-transitory computer readable medium according to claim 13 , wherein each of the one or more MCC increments is derived by:

determining if the child node has the same location as the Steiner node;

if the child node has the same location as the Steiner node, determining the MCC increment to be equal to a MCC for the grid node associated with the child node;

if the child node has a different location from the Steiner node, determining the MCC increment to be equal to a sum of the MCC for the grid node associated with the child node and a BU construction cost at the grid node associated with the Steiner node.

15. The non-transitory computer readable medium according to claim 9 , wherein the irregular two-dimensional manifold is a triangulated piecewise-linear two-dimensional manifold.

16. The non-transitory computer readable medium according to claim 9 , wherein each Steiner nodes of the SMT have a number of branches equal or greater than three.

Assignments (1)

Continuity (1)

References Cited (51)