**Author:** Poona Yospanya, Bundit Lekhanukit, Danupon Nanongkai, Jittat Fakcharoenphol

(Author names are NOT in an alphabetical order.)

**Download:** PDF, PS

**Journal:** –

**Conference: **NCSEC 2004: The 8th National Computer Science and Engineering Conference [link]

**Abstract:**

** **

** **

** **

** **

** **

We view the problem of detecting and cleaning intrud-

ers in sensor networks using mobile agents as a ver-

sion of the graph searching problem. The goal is to

minimize the number of agents running at the same

time. Three scenarios are considered, each differs in

the relative power of the agents and the intruders. Our

main idea is to use breadth-ﬁrst-search (BFS) trees to

organize the search. In the case where the intruder

is most powerful, we search the graph by levels of

the nodes on the BFS tree. However, in the second

case where the network is conﬁgurable, the number of

agents could be improved signiﬁcantly if a good sub-

graph can be found. This motivates us to deﬁne the

Minimum Search Number Spanning Tree problem, of

which we also prove its hardness. We however show

that one can still use a BFS tree to get a good result. In

the last scenario where the intruder has no information

on the status of the agents, random walks are used. In

each case, we prove upper bounds on the number of

agents and provide experiment results.

We view the problem of detecting and cleaning intruders in sensor networks using mobile agents as a version of the graph searching problem. The goal is to minimize the number of agents running at the same time. Three scenarios are considered, each differs in the relative power of the agents and the intruders. Our main idea is to use breadth-ﬁrst-search (BFS) trees to organize the search. In the case where the intruder is most powerful, we search the graph by levels of the nodes on the BFS tree. However, in the second case where the network is conﬁgurable, the number of agents could be improved signiﬁcantly if a good subgraph can be found. This motivates us to deﬁne the Minimum Search Number Spanning Tree problem, of which we also prove its hardness. We however show that one can still use a BFS tree to get a good result. In the last scenario where the intruder has no information on the status of the agents, random walks are used. In each case, we prove upper bounds on the number of agents and provide experiment results.

**Update history:**

**[v1]**** **October 2004

**Comments are welcomed!**

### Like this:

Like Loading...

*Related*

## Leave a Reply