Apparatus and method for detecting critical nodes and critical links in a multi-hop network

An apparatus comprising:

• at least one processing device configured to:
• during each of multiple iterations of a loop:
• obtain a matrix defining a topology of a multi-hop network associated with a current iteration of the loop, the topology identifying nodes and links between the nodes in the multi-hop network, the matrix for the current iteration of the loop constructed by simulating removal of a different one of the nodes from the multi-hop network compared to other iterations of the loop;
• 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 associated with the current iteration of the loop defines a disconnected network using at least one of:
• the one or more Eigenvalues and the one or more Eigenvectors;
• generate a list of 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;
• identify a set of links to or from the critical nodes in the list;
• and
• iteratively process the links in the set of links to determine whether each link in the set of links is a critical link 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;
• and
• at least one memory device configured to store each matrix and identified critical nodes or critical links;
• wherein the at least one processing device is configured to generate the list of critical nodes in the multi-hop network by, for each iteration of the loop in which a determination is made that the topology of the multi-hop network defines a disconnected network, including the node removed from the multi-hop network during that iteration in the list.

A non-transitory computer readable medium embodying a computer program, the computer program comprising computer readable program code for:

• during each of multiple iterations of a loop:
• obtaining a matrix defining a topology of a multi-hop network associated with a current iteration of the loop, the topology identifying nodes and links between the nodes in the multi-hop network, the matrix for the current iteration of the loop constructed by simulating removal of a different one of the nodes from the multi-hop network compared to other iterations of the loop;
• 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 associated with the current iteration of the loop defines a disconnected network using at least one of:
• the one or more Eigenvalues and the one or more Eigenvectors;
• generating a list of 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;
• identifying a set of links to or from the critical nodes in the list;
• and
• iteratively processing the links in the set of links to determine whether each link in the set of links is a critical link 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;
• wherein the computer readable program code for generating the list of critical nodes in the multi-hop network comprises computer readable program code for including, for each iteration of the loop in which a determination is made that the topology of the multi-hop network defines a disconnected network, the node removed from the multi-hop network during that iteration in the list.