Multi-robot Patrolling in Wireless Sensor Networks using Bounded Cycle Coverage - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Multi-robot Patrolling in Wireless Sensor Networks using Bounded Cycle Coverage

Résumé

Patrolling is mainly used in situations where the need of repeatedly visiting certain places is critical. In this paper, we consider a deployment of a wireless sensor network (WSN) that cannot be fully meshed because of the distance or obstacles. Several robots are then in charge of getting close enough to the nodes in order to connect to them, and perform a patrol to collect all the data in time. We discuss the problem of multi-robot patrolling within the constrained wireless networking settings. We show that this is fundamentally a problem of vertex coverage with bounded simple cycles (CBSC). We offer a formalization of the CBSC problem and prove it is NP-hard and at least as hard as the Traveling Salesman Problem (TSP). Then, we provide and analyze heuristics relying on clusterings and geometric techniques. The performances of our solutions are assessed in regards to robot limitations (storage and energy), networking parameters, but also to random and particular graph models.
Fichier non déposé

Dates et versions

hal-01357866 , version 1 (30-08-2016)

Identifiants

  • HAL Id : hal-01357866 , version 1

Citer

Mihai-Ioan Popescu, Hervé Rivano, Olivier Simonin. Multi-robot Patrolling in Wireless Sensor Networks using Bounded Cycle Coverage. ICTAI 2016 28th International Conference on Tools with Artificial Intelligence, IEEE, Nov 2016, San Jose, United States. ⟨hal-01357866⟩
243 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More