We consider synchronous and mobile entities that have to explore and make safe a network with faulty nodes, called black-holes, that destroy any entering entity. We are interested in the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of hops), and we ask for the minimum number of synchronized steps needed to remove all the black-holes from that network. Clearly, if there are b black-holes in the network, then k ≥ b entities are necessary. First, we show that the problem is NP-hard even for b=k=1; second, we provide an asymptotical optimal solution for the case of r=0 and a general lower bound for the case of r>0; third, we propose two different strategies plus a refined heuristic for the case of r=1, and we prove they are all asymptotically optimal; finally, we provide an experimental study to show the practical performance of the proposed strategies.

Exploring and Making Safe Dangerous Networks using Mobile Entities

D'EMIDIO, MATTIA;FRIGIONI, DANIELE;
2013-01-01

Abstract

We consider synchronous and mobile entities that have to explore and make safe a network with faulty nodes, called black-holes, that destroy any entering entity. We are interested in the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of hops), and we ask for the minimum number of synchronized steps needed to remove all the black-holes from that network. Clearly, if there are b black-holes in the network, then k ≥ b entities are necessary. First, we show that the problem is NP-hard even for b=k=1; second, we provide an asymptotical optimal solution for the case of r=0 and a general lower bound for the case of r>0; third, we propose two different strategies plus a refined heuristic for the case of r=1, and we prove they are all asymptotically optimal; finally, we provide an experimental study to show the practical performance of the proposed strategies.
978-3-642-39246-7
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/89132
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact