| In a mobile agents based network environment, intruders are defined as harmful mobile agents penetrating into the environment. Many graph search algorithms can be related to the intruder capture problem , and some have been developed to capture intruders by using mobile agents, such as capturing intruders in a tree [5] and etc. The efficiency of an intruder capture algorithm is the size of the team deployed to capture the intruders. In this paper, we propose algorithms for capturing intruders in four types of Mesh topologies, namely Mesh, Hexagonal Mesh, Octagonal Mesh, and Toroidal Mesh. First we show that in any m x n-Mesh (m ≤ n), at least m agents are needed to solve the problem. We consider two models for each algorithm, one in which an agent has only local knowledge about the node it resides, and the other in which an agent has visibility to see their neighboring nodes. Then for each type of mesh, we design an algorithm in both models, prove its correctness and analyze its complexity in terms of number of agents, number of moves and time required to capture the intruder. |
