Apparatus and method for identifying optimal node placement to form redundant paths around critical nodes and critical links in a multi-hop network

摘要

A method includes obtaining information identifying one or more critical nodes and/or one or more critical links in a multi-hop network. Each critical node or critical link represents a node or link whose failure isolates at least part of the network. The method also includes generating a list identifying one or more orphaned nodes that lose connectivity to a gateway when a specified critical node or critical link fails. The list is generated using an Eigenvector of a matrix defining a topology of the network without the specified critical node or critical link. The method further includes identifying, using the list, at least one location where an additional node can be inserted into the network in order to reduce a number of critical nodes and critical links in the network. The gateway and the orphaned node(s) can be associated with different values in the Eigenvector.

主权项

1. A method comprising the steps of:
using one or more processing devices:
obtaining information identifying at least one of: one or more critical nodes and one or more critical links in a multi-hop network, each critical node or critical link representing a node or link whose failure isolates at least part of the network;generating a list identifying one or more orphaned nodes that lose connectivity to a gateway when a specified critical node or critical link fails, the list generated using an Eigenvector of a matrix defining a topology of the network without the specified critical node or critical link; andidentifying, using the list, at least one location where an additional node can be inserted into the network in order to reduce a number of critical nodes and critical links in the network.