Randomized carrier-based sensor relocation in wireless sensor and robot networks

A wireless sensor network (WSN) is an effective surveillance tool for various applications. One of its functional bases is coverage. Stochastic node dropping and node failure greatly impair coverage, creating sensing holes, while redundant sensors may exist in other areas in the network. This problem was not considered before and we propose first solutions to it. We propose a family of localized robot-assisted sensor relocation algorithms including R3S2, G-R3S2, C-R3S2 and C-G-R3S2. Robots move within the network to discover sensing holes and redundant sensors by local communication and transfer the discovered redundant sensors to the encountered sensing hole positions. In R3S2, robots move at random; in G-R3S2, robots random movement is restricted on a virtual grid and biased toward least recently visited grid points. C-R3S2 and C-G-R3S2 are respectively the variants of R3S2 and G-R3S2 where clustering and virtual force techniques are adopted to merge local sensing holes. Through extensive simulation we show the effectiveness and practicality of these algorithms and evaluate their performance. The simulation results indicate that grid-based variants outperforms non-grid counterparts across all measured metrics and cluster-based variants offer noticeable improvement to those that use no clusters.