Repairing Wireless Sensor Network Connectivity with Mobility and Hop-Count Constraints

Abstract. Wireless Sensor Networks can become partitioned due to node failure or damage, and must be repaired by deploying new sen-sors, relays or sink nodes to restore some quality of service. We formu-late the task as a multi-objective problem over two graphs. The solution specifies additional nodes to reconnect a connectivity graph subject to network path-length constraints, and a path through a mobility graph to visit those locations. The objectives are to minimise both the cost of the additional nodes and the length of the mobility path. We propose two heuristic algorithms which prioritise the different objectives. We eval-uate the two algorithms on randomly generated graphs, and compare their solutions to the optimal solutions for the individual objectives. Fi-nally, we assess the total restoration time for different classes of agent, i.e. small robots and larger vehicles, which allows us to trade-off longer computation times for shorter mobility paths