T. Truong, K. Brown, C.J. Sreenan.
Repairing wireless sensor network connectivity with mobility and hop-count constraints.
Proc. of 12th International Conference on Ad Hoc Networks and Wireless (ADHOC-NOW),
July 2013.
Wireless Sensor Networks can become partitioned due to node failure or damage, and must be repaired by deploying new sensors, relays or sink nodes to restore some quality of service. We formulate 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 dfferent classes of agent,
i.e. small robots and larger vehicles, which allows us to trade-off longer
computation times for shorter mobility paths.