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

(Author names are NOT in an alphabetical order.)

**Journal:** –

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

**Abstract:**

** **

** **

** **

** **

** **

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!**