Archive for October, 2004

Detecting and cleaning intruders in sensor networks (NCSEC’04)

Author: Poona Yospanya, Bundit Lekhanukit, Danupon Nanongkai, Jittat Fakcharoenpholintruder
(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-first-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 configurable, the number of
agents could be improved significantly if a good sub-
graph can be found. This motivates us to define 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-first-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 configurable, the number of agents could be improved significantly if a good subgraph can be found. This motivates us to define 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!

Advertisements

Leave a Comment