Method for providing network orchestration for industrial communication system

Abstract

A method for providing network orchestration for industrial communication system with multiple network slices, comprising:—calculating centralities of nodes in the industrial communication system;—grouping nodes with similar centralities of nodes into clusters;—selecting cluster head for each cluster that is responsible for the resources allocation for the members of the cluster; and—calculating centrality metric for cluster centralities, so as to orchestrate the industrial communication system.

Claims

1. A method for providing network orchestration for industrial communication system (ICS) with multiple network slices, comprising: calculating centralities of nodes in the industrial communication system; grouping nodes with similar centralities of nodes into clusters; selecting cluster head for each cluster; and calculating centrality metric for cluster centralities, so as to orchestrate the industrial communication system, wherein the cluster centralities are calculated as: mean of the betweeness centrality of the nodes of cluster; betweeness centrality of the node with the maximum closeness centrality to the nodes of the cluster; betweeness centrality of the cluster head; and/or betweeness centrality of the node connected to the neighboring cluster.

2. The method according to claim 1, wherein it further comprises: allocating resource to the clusters based on the calculated centrality metric; and coordinating transmissions between nodes of each cluster, wherein that the cluster head is responsible for the resources allocation for the members of the cluster.

3. The method according to claim 2, wherein grouping nodes with similar centrality into clusters comprises: using K-means technique to cluster the nodes based on their centralities.

4. The method according to claim 2, wherein the resource comprises: transmission slots for data collection and/or control command transmission; power and frequency resource blocks that corresponds to OFDM systems; antennas that corresponds to space diversity resources; and/or maximum Bakeoff and other parameters of CSMA/CA medium access control such as energy detection ED parameters.

5. The method according to claim 2, wherein allocating resources to the clusters based on the calculated centrality metric comprises: selecting different transmission bands and bandwidths for clusters with different centralities, wherein higher transmission bandwidths for more central nodes in order to mitigate the congestion during the data collection.

6. The method according to claim 2, wherein coordinating transmissions between nodes of each cluster comprises: transmitting coordination information, by the cluster head, to the nodes, and using the coordination information, by the nodes, to coordinate the transmission with the other nodes of the cluster; evaluating local, by the cluster head, in cluster, centrality of each of its nodes and transmit coordination information based on this local centrality to the nodes in order to coordinate their transmission; and obtaining a common coordination parameter, by the nodes within each cluster, and using the common parameter for coordinating the transmission in the cluster.

7. The method according to claim 1, wherein the centralities of nodes are characterized by the betweeness centrality formula: $B (v) = \underset{i, j \neq v}{.Math.} \frac{σ_{i, j} (v)}{σ_{i, j}}$ wherein σ.sub.i,j is defined by the number of shortest paths from the node i to the node j of the industrial communication system, and σ.sub.i,j (v) is defined by the number of shortest paths for which the node v of the industrial communication system is contributing to.

8. The method according to claim 1, wherein the centralities of nodes are characterized by the following closeness centrality formula: $C_{D} (v) = \underset{i \in N (v), i \neq v}{.Math.} \frac{1}{d_{v, i}}$ wherein variable d.sub.v, i is the distance between the node v and the node i from the set N(v), and a node v with high closeness centrality is a node that is not at the border of the set N(v) and that have small distances to every other node in the set N(v).

9. The method according to claim 7, wherein the centrality metric is a product of betweeness and closeness centralities of nodes, characterized by the following formula:
λ(v)=B(v)C.sub.D(v).

10. The method according to claim 1, wherein it further comprises: obtaining the centrality metric that characterizes the centrality of the terminal set P that is the set of the selected cluster heads; selecting Steiner node having a high value of the centrality metric; adding connection with the lowest latency between the Steiner node and the terminal node from the terminal set P to the Steiner tree and adding the Steiner node to the terminal nodes; and testing if the constructed tree is spanning the network.

11. The method according to claim 10, wherein the Steiner node having the high value of the centrality metric contains a high betweeness centrality and is close to all the non terminal nodes, wherein the nodes of the network that are not in the terminal set P.

12. The method according to claim 11, wherein that the betweeness centrality is characterized by the following formula: $B (v) = \underset{w : v \in P_{s} (w)}{.Math.} \frac{σ_{s v}}{σ_{s w}} (1 + δ_{s} (w))$ where the parameter P.sub.s (w) is the set of direct predecessors set of a given node w towards the sink node and it is obtained by graph traversal techniques; and σ.sub.sv and σ.sub.sw are respectively the number of shortest paths from the nodes v and w to the node s of the network, and δ.sub.s(w) is the cumulative centrality metric of the node w on the path from a source, the centrality metric is characterized by the following formula: $λ (v) \approx \underset{\underset{w \in N (v)}{w : v \in P_{s} (w)}}{.Math.} \frac{σ_{s v}}{d (v, w) σ_{s w}} (1 + δ_{s} (w))$ Where d (v, w) is the distance between the nodes v and w in the network.

13. An orchestrator for providing network orchestration for industrial communication system (ICS) with multiple network slices, being configured to: calculate centralities of nodes in the industrial communication system; group nodes with similar centralities of nodes into clusters; select cluster head for each cluster that is responsible for the resources allocation for the members of the cluster; and calculate centrality metric for cluster centralities, so as to orchestrate the industrial communication system, wherein the cluster centralities are calculated as: mean of the betweeness centrality of the nodes of cluster; betweeness centrality of the node with the maximum closeness centrality to the nodes of the cluster; betweeness centrality of the cluster head; and/or betweeness centrality of the node connected to the neighboring cluster.

14. An industrial communication system with multiple network slices, comprising an orchestrator according to claim 13.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 illustrates an industrial control system according to the present invention.

(2) FIG. 2 illustrates an abstraction of the ICS connectivity.

(3) FIG. 3 illustrates clusters grouped from nodes in ICS system.

(4) FIG. 4 is a flowchart of an illustrative method according to the invention.

DESCRIPTION OF EMBODIMENTS

(5) FIG. 1 shows schematically an industrial communication system (ICS) including a number of industrial sensors s1 to s4 and actuator a1 to a4 that can emit or receive wireless data, wherein the sensors s1, s2 and the actuator a1, a2 are installed on machine M1, and the sensor s3, s4 and the actuator a3 and a4 are installed on machine M2, a number of wireless nodes, such as Wi-SUN ws1 to ws8 and WiFi nodes w1 to w8, for example operating under 900 MHz under IEEE 802.15.4 standard or 2.5 GHz under IEEE 802.11 standard, as well as a gateway GW and a controller C. Wherein the wireless nodes can receive the wireless data from the sensor and send it to the gateway GW, and the gateway GW can transmit it to the controller C. On the other hand, the controller C can send command to the gateway, which then transmits it to the wireless nodes, and then the wireless nodes transmit it to the actuator. The wireless data can also be transmitted among the wireless nodes.

(6) In this exemplary ICS system, there is coexistence between two network slices in the ICS system, URLLC (Ultra-reliable low-latency communication) network slice for the transmission of the controller commands and ultra dense IOT for the data collection from the sensors. In fact, this is merely an example, and there could be coexistence between multiple network slices with more than two slices as shown in the present example.

(7) With more and more multiple network slices when the system containing more sensors and actuator, as well as other possible devices in the ICS, an orchestration problem for ICS should be addressed by the present invention, on the one hand, to reduce the collision between the transmission of the packets from the sensors or towards the actuators, and on the other hand, to minimize the delay to the transmission to/from the gateway.

(8) According to the present invention, an exemplary orchestration process is viewed as a combined clustering and backbone network construction and/or adaptation in order to reduce the overall latency and interference in the ICS system. The overall orchestration method according to the invention is now described hereinafter.

(9) Before the orchestration process, each node in the ICS system of FIG. 1 is measuring the signals it receive from the neighboring nodes with specific power/quality or any other metric that characterizes the ability that two nodes are having to communicate. These measurements can be the measurements of the nodes, eventually inter-frequency measurement when multiple technologies are used in the ICS system. These measurements are collected in the abstraction layer of the ICS system and are used to build a representation of the connectivity situation.

(10) As shown in FIG. 2, an abstract model is stored in the abstraction layer/middleware of the ICS and is defined as: a node that represents a specific communication device in the ICS system and edges connecting nodes represents the communication link between the nodes or interference from one node to another.

(11) In case the ICS is having multiple network slices, the abstraction may be either on per slice basis, i.e. an abstraction is built for the communication and/or interference situation in each slice or on a global network basis, i.e. considering the slices that can communicate with each other or that can interfere in building the abstraction. In this last case, the contribution of the node of the ICS to multiple network slices is implicitly included in the centrality calculation in the later orchestration process, especially step S1 as shown in FIG. 4, that will be detailed below.

(12) Several metrics regarding the centrality calculation can be considered in the present invention. For instance, a first exemplary metric is the contribution of each communication device to a path of a data packet in the ICS network. Let us define the number of shortest paths from the node i to the node j of the ICS as σ.sub.i,j. The number of shortest paths for which the node v of the ICS is contributing to is-defined as σ.sub.i,j(v).

(13) The metric that characterizes the contribution of the node to the paths towards the gateway is given by the following betweenness centrality formula:

(14) $B (v) = \underset{i, j \neq v}{.Math.} \frac{σ_{i, j} (v)}{σ_{i, j}}$

(15) Nodes with high betweenness centrality are nodes that are contributing to a high number of paths of low latency in the network.

(16) A second exemplary metric used in the present invention is closeness centrality metric where for the node v the closeness centrality of the node with respect to nodes in a set N(v) around the node v. This closeness centrality is defined as the following:

(17) $C_{D} (v) = \underset{i \in N (v), i \neq v}{.Math.} \frac{1}{d_{v, i}}$

(18) The variable d.sub.v,i, is the distance between the node v and the node i from the set N(v). A node v with high closeness centrality is a node that is not at the border of the set N(v) and that have small distances to every other node in the set N(v).

(19) After obtaining these centralities, orchestration process is proceeded as follows:

(20) First, in step S2, the nodes with similar centralities of nodes are grouped into clusters. In particular, the nodes are clustered into groups that have similar contribution to the path from the sensor towards the gateway, for example, nodes similar betweenness centralities.

(21) FIG. 3 illustrates such a cluster, wherein each node has its own node centrality C and those with similar centrality are grouped together as one cluster.

(22) As an example, K-means technique may be used to cluster the nodes based on their centralities. K-means calculate local mean of the betweenness centralities in the cluster, the node is added to the cluster if its betweenness centrality is close to the local mean centrality of the cluster.

(23) In addition, we may determine from the measurements of the nodes, the clusters and commands the nodes independently to join the clusters.

(24) After the node clustering step, a cluster head is selected for each cluster in step S3. The cluster head is a specific node of the industrial communication system that is usually central in the cluster. For example, the head can be a node that communicates with low latency with the cluster members or it is contributing to communication paths between any pairs of nodes of the cluster.

(25) The cluster head is adapted for transmission coordination in the cluster. For example, the cluster head node is timing reference for time division multiple access transmission (TDMA) between the nodes of the cluster. Another example is that the cluster head performs the coordination between the transmissions in the cluster by sensing the radio channel and sending clear to send (CTS) packets to the nodes of the cluster in carrier sense multiple access CSMA with collision avoidance, CA scheme.

(26) The cluster head is responsible for the later resources allocation for the members of the cluster. This resource allocation scheme is for example, the selection of the slots, the frequencies, the powers or any other radio network resources for the transmission of the nodes of the cluster. Resource allocation is also viewed as a way to provision resources for the transmission of the nodes of the cluster that minimizes the interference.

(27) Afterwards, centrality metric for cluster centralities is calculated in step S4, so as to orchestrate the industrial communication system. As an example, the cluster centrality can be calculated by means of:

(28) The mean of the betweenness centrality of the cluster;

(29) The betweenness centrality of the node with the maximum closeness centrality to the nodes of the cluster,

(30) The betweenness centrality of the cluster head; and/or,

(31) The betweenness centrality of the node connected to the neighboring cluster.

(32) For example, wherein the centrality metric is a product of betweenness and closeness centralities of nodes, characterized by the following formula:
λ(v)=B(v)C.sub.D(v).

(33) If the node v is having high centrality, it will have high value of the parameter λ(v).

(34) On the one hand, in order to mitigate possible congestion during the data collection process/control command transmission process, the following steps are implemented.

(35) In step S5, resources are allocated to the clusters based on cluster centrality such that more resources are allocated to central clusters during the data collection process/control command transmission process. These resources may be for example: Transmission slots for data collection and/or control command transmission; Power and frequency resource blocks that corresponds for example to OFDM systems; Antennas that corresponds to space diversity resources. More antennas can be allocated to nodes with higher betweenness centrality; Maximum Bakeoff and other parameters of CSMA/CA medium access control such as energy detection ED parameters; Different transmission bands and bandwidths can be selected for the clusters with different centrality. It selects higher transmission bandwidths for more central nodes in order to mitigate the congestion during the data collection from the sensors. The transmission bands are selected to minimize the interference of the transmission between the clusters. Different transmission bands are selected for the transmission of the clusters with different centralities.

(36) Accordingly, in step S6, transmission is coordinated between the nodes of each cluster as the following: Cluster head transmit coordination information to the nodes and the nodes use this information to coordinate the transmission with the other nodes of the cluster. The cluster head evaluate local, in cluster, centrality of each of its nodes and transmit coordination information based on this local centrality to the nodes in order to coordinate their transmission. The coordination may be done as: nodes with similar centralities in the cluster transmit in a coordinated way. The nodes within each cluster obtain a common coordination parameter, through consensus averaging and use this common coordination parameter for coordinated transmission in the cluster.

(37) With these arrangements in steps S5 and S6, nodes are clustered so as to reduce the collision between the transmission of the packets from the sensors or towards the actuators.

(38) On the other hand, in order to improve the reactivity of the centrality calculation and improve the monitoring/management latency of the orchestration, the present invention also proposes a method for the inter cluster backbone network.

(39) State of the art backbone network construction is based on Steiner tree problem and algorithms. In its simplest form, the minimum Steiner tree problem may be formulated as: given a set P of n pins or terminal nodes, we would like interconnect these points using a minimum total amount of wire. The minimum Steiner tree problem consists of introducing a set of intermediary points S outside the set P such that the tree spanning the set P u S is a minimum spanning tree, i.e. a tree with minimum sum of metric.

(40) For this reason, Steiner tree is the basic component of the design of the backbone network for ICS. The optimal solution of the Steiner tree problem is non polynomial and hard (NP-hard). An exact algorithm is given by the Dreyfus-Wagner recursion. This algorithm is a dynamic programming algorithm that augments iteratively the Steiner tree by adding the nodes v and u to the terminal nodes P and that minimize the following:
ST(P,v)=min.sub.v∈V(dist(v,u)+min.sub.X.Math.P(ST(X,u)+ST(P\X,u)))

(41) where ST(P,v) is the sum of the metrics of the Steiner tree over the nodes P∪{v}. The set X is a partition of the terminal nodes and P\X is a complementary set of the partition X in the set P. The function dist(v,u) is the latency of the transmission between the node v and u and ST(P,v) is the sum of the latencies in the Steiner tree. The node u is a node that is on the path between the node v and the set of terminals P and with degree above 3.

(42) One of the key drawbacks of this approach in the art is the lack of scalability when the network is large. In this regard, the present invention proposes another approximation, based on the following method that starts from clusters with low centrality and move to clusters with high centrality:

(43) S7: Start from the set of terminals P that is the set of the previously determined cluster heads;

(44) S8: Obtain a metric that characterizes the centrality of the terminal set P. The metric can be for example, the average centrality of the terminal set, the maximum centrality of the terminal set or any other metric that characterizes the contribution of the cluster heads to the paths of the packets in the ICS system;

(45) S9: Select Steiner node that is having a high betweenness centrality and that is close to all the non-terminal nodes (X\P), i.e. nodes with high value of the indicator λ(v)=B(v)C.sub.D(v) and that is neighbour to at least one terminal node. Add the connection with the lowest latency between the Steiner node and the terminal node to the Steiner tree and add the Steiner node to the terminal nodes;

(46) S10: Test if the constructed tree is spanning the network. If not, go to step S8.

(47) The basic advantage of using the metric λ(v) for finding the Steiner nodes of the backbone network is the local dependency of this metric with respect to the case of the network wise betweenness centrality metric B(v).

(48) It is well known by the Brands algorithm that the betweenness centrality is given by the following recursive relation

(49) $B (v) = \underset{w : v \in P_{s} (w)}{.Math.} \frac{σ_{s v}}{σ_{s w}} (1 + δ_{s} (w))$

(50) This metric serves for the addition of the new Steiner nodes for the backbone construction will consider only a local nodes in the neighbourhood of the considered node, instead of all network nodes. This will improve the scalability of orchestration for ultra-dense networks and the latency of the backbone construction.

(51) One of the advantages of the proposed metric is related to the monitoring and management of the centrality metric λ(v). The standard Brands algorithm needs to monitor and propagate the accumulated centrality metrics δ.sub.s(w) to the node v from all the network nodes w such that v∈P.sub.s(w), i.e. v is at the intersection of the shortest paths from some w nodes in the network. The algorithm according to the present invention proposes to reduce the centrality calculation to a neighborhood N(v) around the node v that improves the reactivity of the centrality calculation and improve the monitoring/management latency of the orchestration.

(52) With these arrangements, the backbone network between the clusters is optimized so that the delay to the transmission to/from the gateway is minimized.

(53) According to another aspect of the present invention, it also proposes an orchestrator for providing network orchestration for ICS with multiple network slices by implementing the process mentioned above.

(54) In summary, the key idea of the invention is to propose a single metric for both for the clustering and the backbone optimization that reduces the complexity of the orchestration and improve the overall system performance, so as to achieve latency and jitter optimization, simple management thanks to clustering.

(55) In addition, as is known to those skilled in the art, the aforementioned example architectures described above, according to the present invention, can be implemented in many ways, such as program instructions for execution by a processor, as software modules, microcode, as computer program product on computer readable media, as logic circuits, as application specific integrated circuits, as firmware, etc. The embodiments of the invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

(56) Furthermore, the embodiments of the invention can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer, processing device, or any instruction execution system. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can contain, store, communicate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be electronic, magnetic, optical, or a semiconductor system (or apparatus or device). Examples of a computer-readable medium include, but are not limited to, a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a RAM, a read-only memory (ROM), a rigid magnetic disk, an optical disk, etc. Current examples of optical disks include compact disk-read-only memory (CD-ROM), compact disk-read/write (CD-R/W) and DVD.

Method for providing network orchestration for industrial communication system

Assignee

Inventors

Cpc classification

Classification Explorer

H04W74/0816

ELECTRICITY

Classification Explorer

H04W28/26

ELECTRICITY

Classification Explorer

H04L41/0893

ELECTRICITY

Classification Explorer

H04L41/0897

ELECTRICITY

Classification Explorer

H04W72/0446

ELECTRICITY

Classification Explorer

H04W84/18

ELECTRICITY

International classification

Classification Explorer

G06F15/173

PHYSICS

Classification Explorer

H04L41/0897

ELECTRICITY

Classification Explorer

H04L41/0893

ELECTRICITY

Abstract

Claims

Description