Optimized repair of a partitioned network topology

We consider the problem of deploying the least count of relay nodes to restore connectivity in a network that got partitioned into multiple disjoint segments. Such a problem has been generally formalized as a Steiner Minimum Tree (SMT) by assuming that each segment is a terminal, e.g., by picking a single node in a segment to serve as an interface point. We argue that such formulation is ineffective since the size and the shape of the segment are not factored in. To overcome this drawback, we propose a novel approach for Boundary-aware optimized Interconnection of Disjoint segments (BIND). BIND opts to restore network connectivity by forming the shortest length topology in the Euclidean plane that interconnects a subset of nodes on the segment boundaries through extra Steiner points so that there is a path between every pair of segments. Since constructing the SMT connecting boundary nodes (terminals) subject to obstacle avoidance is NP-hard, BIND pursues a heuristic based on the generation and concatenation of full Steiner trees (FSTs). As the number of distinct FSTs grows exponentially with the number of terminals, BIND further promotes a new geosteiner technique based on the straight skeleton of the segment boundaries within the deployment area in order to reduce the complexity. The simulation results confirm the effectiveness of BIND and its advantage compared to competing schemes.