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 (902, 1002, 1104) information identifying one or more critical nodes (102) and/or one or more critical links (104) in a multi-hop network (100). 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 (906, 1006, 1108) 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 (916, 1016, 1118), using the list, at least one location where an additional node (102) 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.