Impressionist hole detection and healing using swarms of agents with quantized perception

Coverage holes are a key problem in wireless sensor networks. Methods that use relative localization techniques to restore the service, or heal the holes, rely on accurate range and bearing measurements. However, high-precision range and bearing sensors are too heavy, expensive, and range-limited for the agents tasked with healing. To overcome these limitations, we propose a novel impressionist algorithm, inspired by a recent swarm-based approach, that works with extremely coarse range and bearing information and at low perception frequency, to detect and heal the holes. In the proposed approach, a swarm of agents uses quantized information to navigate a potential field, generated by network nodes, to reach the nearest hole. The swarm adopts a greedy deployment behavior, preventing concurrent placement in close-by locations. After deployment, agents use their coarse perception to update the potential field, leading the rest of the swarm to unhealed area. Simulation results demonstrate that our algorithm achieves similar or better coverage compared to the state-of-the-art and to a benchmark based on random walk. This is achieved using just three bearing quantization levels and four times lower perception frequency. Overall, our impressionist approach shows faster healing, albeit at the expense of employing slightly more agents.