Integration of node deployment and path planning in restoring network connectivity

Truong, Thuy T.; Brown, Kenneth N.; Sreenan, Cormac J.

Integration of node deployment and path planning in restoring network connectivity

Files

2011-Thuy-Plansig2011.pdf(2.24 MB)

Accepted version

Date

2011-12

Authors

Truong, Thuy T.

Brown, Kenneth N.

Sreenan, Cormac J.

Publisher

Association for the Advancement of Artificial Intelligence (AAAI)

Abstract

A wireless sensor network can become partitioned due to node failure, requiring the deployment of additional relay nodes in order to restore network connectivity. This introduces an optimisation problem involving a tradeoff between the number of additional nodes that are required and the costs of moving through the sensor field for the purpose of node placement. This tradeoff is application-dependent, influenced for example by the relative urgency of network restoration. We propose two heuristic algorithms which integrate network design with path planning, recognising the impact of obstacles on mobility and communication. We conduct an empirical evaluation of the two algorithms on random connectivity and mobility graphs, showing their relative performance in terms of node and path costs, and assessing their execution speeds. Finally, we examine how the relative importance of the two objectives influences the choice of algorithm.

Keywords

Wireless sensor networks , WSN , Connectivity , Random connectivity , Network connectivity

Citation

Truong, T., Brown, K. and Sreenan C. J. (2011) 'Integration of Node Deployment and Path Planning in Restoring Network Connectivity', Proceedings of the 29th Workshop of the UK Special Interest Group on Planning and Scheduling: PlanSIG2011, University of Huddersfield, UK, 8-9 December, pp. 77-84.