A Localized Algorithm for Restoring Internode Connectivity in Networks of Moveable Sensors

Recent years have witnessed a growing interest in the applications of wireless sensor networks (WSNs). In some of these applications, such as search and rescue and battlefield reconnaissance, a set of mobile nodes is deployed in order to collectively survey an area of interest and/or perform specific surveillance tasks. Such collaboration among the sensors requires internode interaction and thus maintaining network connectivity is critical to the effectiveness of WSNs. While connectivity can be provisioned at startup time and then sustained through careful coordination when nodes move, a sudden failure of a node poses a challenge since the network may get partitioned. This paper presents RIM; a distributed algorithm for Recovery through Inward Motion. RIM strives to efficiently restore the network connectivity after a node failure. Instead of performing a networkwide analysis to assess the impact of the node failure and orchestrate a course of action, RIM triggers a local recovery process by relocating the neighbors of the lost node. In addition to minimizing the messaging overhead, RIM opts to reduce the distance that the individual nodes have to travel during the recovery. The correctness of the RIM algorithm is proven and the incurred overhead is analyzed. The performance of RIM is validated through simulation experiments.