In this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpiński graph SG n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of “seeing” the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves.

Intruder Capture in Sierpinski Graphs.

LUCCIO, Flaminia
2007-01-01

Abstract

In this paper we consider the problem of capturing an intruder in a networked environment. The intruder is defined as a mobile entity that moves arbitrarily fast inside the network and escapes from a team of software agents. The agents have to collaborate and coordinate their moves in order to isolate the intruder. They move asynchronously and they know the network topology they are in is a particular fractal graph, the Sierpiński graph SG n . We first derive lower bounds on the minimum number of agents, number of moves and time steps required to capture the intruder. We then consider two models: one in which agents have a capability, of “seeing” the state of their neighbors; the second one in which the actions of the agents are leaded by a coordinator. One of our goals is to continue a previous study on what is the impact of visibility on complexity: we have found that in this topology the visibility assumption allows us to reach an optimal bound on the number of agents required for the cleaning strategy. On the other hand, the second strategy relies only on local computations but requires an extra agent and a higher (by a constant) complexity in terms of time and number of moves.
2007
Fun with Algorithms
File in questo prodotto:
File Dimensione Formato  
final.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 195.28 kB
Formato Adobe PDF
195.28 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA 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/10278/32797
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 2
social impact