A study on the algorithms for capacitated domination problems

Distributed systems are a collection of autonomous interconnected computing elements that cooperate to achieve common goals which include transparency, openness, reliability, performance, and scalability. A distributed system is self-stabilizing if it converges a legitimate state notwithstanding starting initially from any illegitimate state and stays so without any external intervention. Wireless ad hoc and sensor networks (WASNs) are distributed networks that consist of thousands of wireless self-organized sensor nodes without the aid of predefined infrastructure, and they are used for many real-world applications such as military surveillance, emergency operation, smart city, environmental science, and precision agriculture. Domination problems are widely used to provide energy efficiency and fault tolerance for distributed systems such as WASNs. The capacitated versions which are extensions of them additionally provide load balancing. In this thesis, we propose three distributed self-stabilizing algorithms for capacitated domination problems which are independent set, dominating set, and connected dominating set. All of them are proven in terms of convergence and closure. Moreover, they are implemented on IRIS motes through testbeds and on TOSSIM through simulations.