Network Decontamination from Black Viruses

Public Deposited
Resource Type
  • In this thesis, the problem of decontaminating networks from Black Viruses (BVs) using a team of system mobile agents, i.e., the BVD problem, is investigated. The BV is a dynamic harmful process which, like the extensively studied black hole (BH), destroys any agent arriving at the network site where it resides; when that occurs, unlike a black hole which is static by definition, a BV moves, spreading to all the neighbouring sites, thus increasing its presence in the network. The initial location of BV is unknown a priori. The objective is to permanently remove any presence of the BV from the network with minimum number of site infections (and thus casualties) and prevent any previously decontaminated node from becoming infected again.The BVD problem is first studied in the systems with only one BV. Initial investigations are for some common classes of interconnection networks: (multidimensional) grids, tori, and hypercubes. Optimal solutions are proposed and their complexities are analyzed in terms of node infections, agent team size, and movements. After understanding the basic properties of the decontamination process in these special graphs, the BVD problem is studied in arbitrary networks. Finally the research is extended to Multiple BV Decontamination problem (MBVD) both in arbitrary graphs and in special topologies.To help understand the behavior of the protocol developed and support complexity analysis, an experimental study is performed using the simulator for reactive distributed algorithms DisJ. A large number of simulations are carried out on various sizes of graphs with many connectivity densities. The simulation runs show that the propose protocol beats random search; they also disclose many interesting behaviors, and validate the analytical complexity results. The simulation results also provide deep understanding on the influence of graph connectivity density and graph size on complexities, i.e., movement, time, and agent size.Finally conclusion remarks are presented and future researches are proposed.

Thesis Degree Level
Thesis Degree Name
Thesis Degree Discipline
Rights Notes
  • Copyright © 2016 the author(s). Theses may be used for non-commercial research, educational, or related academic purposes only. Such uses include personal study, research, scholarship, and teaching. Theses may only be shared by linking to Carleton University Institutional Repository and no part may be used without proper attribution to the author. No part may be used for commercial purposes directly or indirectly via a for-profit platform; no adaptation or derivative works are permitted without consent from the copyright owner.
Date Created
  • 2016


In Collection: