Randomized Robot-Assisted Relocation of Sensors for Coverage Repair in Wireless Sensor Networks

In wireless sensor networks (WSN), stochastic node dropping and unpredictable node failure greatly impair coverage, creating sensing holes, while locally redundant sensors exist. If sensors are all equipped with locomotion, they will be able to relocate themselves to improve coverage. But this approach increases the complexity of hardware design for sensors as well as deployment budget. In this paper, we consider a small group of mobile robots to serve WSN. We propose an algorithm, named Randomized Robot-assisted Relocation of Static Sensors (R3S2), for coverage repair and a grid-based variant, called G-R3S2. By these algorithms, mobile robots move within the network to collect redundant sensors and deliver them to reported sensing hole positions. In R3S2, robots move completely at random and relocate encountered redundant sensors. In G-R3S2, the robots random movement is restricted on a virtual grid, and the robots continually move to the next least recently visited grid point so as to increase the chance of discovering redundant sensors and sensing holes. Through extensive simulation, we show their effectiveness and practicality and evaluate their performance. The simulation results indicate in particular that G-R3S2 outperforms R3S2 across all measured metrics.