Interconnecting isolated network segments through intermittent links

Wireless Sensor Network (WSN) deployed within hostile environments may suffer from large scale damage where many sensors fail simultaneously and cause the WSN to split into disconnected segments. Restoring inter-segment connectivity is primordial to the effectiveness of the WSN. When it is not feasible to replace the lost nodes, a set of mobile relays is often employed in order to establish intermittent connectivity between segments. Basically these relays serve as mobile data carriers (MDCs) that tour segments to transport the data. A key objective is to minimize the tour length in order to limit the travel overhead and data latency. Existing solutions have simplified the optimization problem by representing each segment by just one terminal and ignoring the shape and the size of the individual segments. In this paper, we consider the recovery optimization under realistic segment topology and constrained number of MDCs, which make the problem very challenging. We present a two-step heuristic for Connecting Isolated Segments through Intermittent Links (CISIL). CISIL first uses a high order Delaunay triangulation to efficiently determine all efficient tours among segments, and then selects the optimal subset of these tours that matches the MDC count and yields a strongly connected network. The selection optimization is mapped to a k-edge minimum spanning tree problem within a hypergraph. The performance of CISIL is validated through simulation and compared to a prominent competing scheme.