APPARATUS AND METHOD FOR DETECTING CRITICAL NODES AND CRITICAL LINKS IN A MULTI-HOP NETWORK

• US 20130064139A1
• Filed: 09/12/2011
• Published: 03/14/2013
• Est. Priority Date: 09/12/2011
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kolavennu, Soumitri N.
• Granted Patent: US 8,948,053 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

A method includes obtaining a matrix defining a topology of a multi-hop network, where the topology identifies nodes and links between the nodes in the multi-hop network. The method also includes identifying one or more Eigenvalues and/or one or more Eigenvectors of the matrix. The method further includes determining whether the topology of the multi-hop network defines a disconnected network using the one or more Eigenvalues and/or the one or more Eigenvectors. For example, one or more Eigenvalues of the matrix can be identified, and a determination can be made whether a second smallest Eigenvalue equals zero. As another example, Eigenvectors corresponding to two smallest Eigenvalues of the matrix can be identified, and a determination can be made whether the Eigenvectors have opposite zero and non-zero entries such that, for all entries in the Eigenvectors, an i^th entry in one Eigenvector is zero while an i^th entry in another Eigenvector is non-zero.

Claims

1. A method comprising the steps of:

obtaining a matrix defining a topology of a multi-hop network, the topology identifying nodes and links between the nodes in the multi-hop network;

identifying at least one of;

one or more Eigenvalues and one or more Eigenvectors of the matrix; and

determining whether the topology of the multi-hop network defines a disconnected network using at least one of;

the one or more Eigenvalues and the one or more Eigenvectors.

2. The method of claim 1, comprising:

identifying one or more Eigenvalues of the matrix; and

determining whether a second smallest Eigenvalue equals zero.

3. The method of claim 1, comprising:

identifying Eigenvectors corresponding to two smallest Eigenvalues of the matrix; and

determining whether the Eigenvectors have opposite zero and non-zero entries such that, for all entries in the Eigenvectors, an i^th entry in one Eigenvector is zero while an i^th entry in another Eigenvector is non-zero.

4. The method of claim 1, further comprising:

repeating the obtaining, identifying, and determining steps using multiple matrices defining multiple topologies of the multi-hop network; and

identifying any critical nodes in the multi-hop network, each critical node representing one of the nodes in the network whose removal divides the network so that at least one remaining node in the network cannot communicate with at least one other remaining node in the network.

5. The method of claim 4, wherein each of the multiple matrices defining the multiple topologies of the multi-hop network is constructed by simulating removal of a different one of the nodes from the multi-hop network.

6. The method of claim 4, wherein the multi-hop network comprises a dynamic network in which the nodes or links constantly change.

7. The method of claim 1, further comprising:

repeating the obtaining, identifying, and determining steps using multiple matrices defining multiple topologies of the multi-hop network; and

identifying any critical links in the multi-hop network, each critical link representing one of the links in the network whose removal divides the network so that at least one node in the network cannot communicate with at least one other node in the network.

8. The method of claim 1, wherein:

the matrix comprises a Laplacian matrix having rows and columns, each node of the network associated with one of the rows and one of the columns;

an (i,j)^th entry in the matrix indicates whether a link exists between the i^th node and the j^th node; and

an (i,i)^th entry in the matrix identifies a degree of the i^th node.

9. The method of claim 8, wherein obtaining the matrix comprises:

generating an adjacency matrix identifying the links in the multi-hop network;

generating a degree matrix identifying the degree of each node in the multi-hop network; and

subtracting the adjacency matrix from the degree matrix.

10. An apparatus comprising:

at least one memory unit configured to store a matrix defining a topology of a multi-hop network, the topology identifying nodes and links between the nodes in the multi-hop network; and

at least one processing unit configured to;

identify at least one of;

one or more Eigenvalues and one or more Eigenvectors of the matrix; and

determine whether the topology of the multi-hop network defines a disconnected network using at least one of;

the one or more Eigenvalues and the one or more Eigenvectors.

11. The apparatus of claim 10, wherein the at least one processing unit is configured to:

identify one or more Eigenvalues of the matrix; and

determine whether a second smallest Eigenvalue equals zero.

12. The apparatus of claim 10, wherein the at least one processing unit is configured to:

identify Eigenvectors corresponding to two smallest Eigenvalues of the matrix; and

determine whether the Eigenvectors have opposite zero and non-zero entries such that, for all entries in the Eigenvectors, an i^th entry in one Eigenvector is zero while an i^th entry in another Eigenvector is non-zero.

13. The apparatus of claim 10, wherein the at least one processing unit is further configured to:

repeat the obtaining, identifying, and determining operations using multiple matrices defining multiple topologies of the multi-hop network; and

identify any critical nodes in the multi-hop network, each critical node representing one of the nodes in the network whose removal divides the network so that at least one remaining node in the network cannot communicate with at least one other remaining node in the network.

14. The apparatus of claim 13, wherein each of the multiple matrices defining the multiple topologies of the multi-hop network is constructed by simulating removal of a different one of the nodes from the multi-hop network.

15. The apparatus of claim 10, wherein the at least one processing unit is further configured to:

repeat the obtaining, identifying, and determining operations using multiple matrices defining multiple topologies of the multi-hop network; and

identify any critical links in the multi-hop network, each critical link representing one of the links in the network whose removal divides the network so that at least one node in the network cannot communicate with at least one other node in the network.

16. The apparatus of claim 10, wherein:

the matrix comprises a Laplacian matrix having rows and columns, each node of the network associated with one of the rows and one of the columns;

an (i,j)^th entry in the matrix indicates whether a link exists between the i^th node and the j^th node; and

an (i,i)^th entry in the matrix identifies a degree of the i^th node.

17. A computer readable medium embodying a computer program, the computer program comprising computer readable program code for:

obtaining a matrix defining a topology of a multi-hop network, the topology identifying nodes and links between the nodes in the multi-hop network;

identifying at least one of;

one or more Eigenvalues and one or more Eigenvectors of the matrix; and

determining whether the topology of the multi-hop network defines a disconnected network using at least one of;

the one or more Eigenvalues and the one or more Eigenvectors.

18. The computer readable medium of claim 17, wherein the computer program further comprises computer readable program code for:

repeating the obtaining, identifying, and determining operations using multiple matrices defining multiple topologies of the multi-hop network; and

identifying any critical nodes in the multi-hop network, each critical node representing one of the nodes in the network whose removal divides the network so that at least one remaining node in the network cannot communicate with at least one other remaining node in the network.

19. The computer readable medium of claim 18, wherein each of the multiple matrices defining the multiple topologies of the multi-hop network is constructed by simulating removal of a different one of the nodes from the multi-hop network.

20. The computer readable medium of claim 17, wherein the computer program further comprises computer readable program code for:

repeating the obtaining, identifying, and determining operations using multiple matrices defining multiple topologies of the multi-hop network; and

identifying any critical links in the multi-hop network, each critical link representing one of the links in the network whose removal divides the network so that at least one node in the network cannot communicate with at least one other node in the network.