Efficient Topology Optimization for a Wired Networked System by Adding Wireless Communication

Adding wireless communication capabilities to networked systems can effectively improve its connectivity, which in turn improves the robustness of the system under emergency. When the resource is limited, only finite wireless communication capacities can be installed to the existing nodes. It is in general difficult to determine which nodes to install in order to achieve the required connectivity, leaving alone the further task to find the installation with efficiency requirement. We consider this important problem in this paper and make the following major contributions. First, we develop an algorithm to configure the network to achieve biconnectivity through installing the minimal number of wireless communication devices. Second, when there are multiple such installations, we further develop an algorithm to pick the installation that maximizes the efficiency of the network. Both algorithms are polynomial w.r.t. the network size. The performances of both algorithms are demonstrated through numerical examples. We hope this work brings insight to topology optimization in more general situations.