Abstract:
The increasing complexity of modern networks, particularly in the context of the Internet of Things (IoT), has
necessitated the development of advanced methods to protect these systems against various security problems.
Graph theory has emerged as a powerful tool for modeling and solving network security problems due to its direct
relevance to network structures. A network can be represented as a set of nodes connected by physical or logical
links, and graph parameters such as the dominating set, secure dominating set, and critical node set are critical for
optimizing network protection. The Dominating Set helps in selecting nodes to ensure information transmission
within the network, while the secure dominating set identifies the set of guards that protect the entire network,
playing a crucial role in network security. The Critical node set allows for identifying key nodes whose removal
maximally disconnects the network, enabling targeted defense strategies. Despite their importance, obtaining
optimal values for these graph parameters is a challenging task, as they often involve NP-complete problems that
require approximate solutions. This thesis aims to address this challenge by proposing distributed algorithms that
efficiently approximate these graph parameters, making them suitable for the resource-constrained, and
decentralized nature of IoT networks. By leveraging distributed computing techniques, the research develops
heuristic-based solutions for the secure dominating set, maximal independent set, and critical node set problems,
focusing on IoT networks where traditional sequential methods are inadequate due to their computational
complexity. The proposed algorithms are evaluated through simulations using the CupCarbon IoT simulator,
demonstrating significant improvements in efficiency, scalability, and security. This work contributes both
theoretical insights and practical solutions, enhancing the resilience of IoT networks while addressing the unique
challenges posed by their distributed and dynamic nature.
