Dominating set algorithms for wireless sensor networks

Wireless sensor networks (WSNs) are infrastructureless network of nodes which are capable of sensing and wireless communication. Relaying the packets of applications running on WSN is an important problem. Clustering the network is a solution for this problem. Dominating set construction is a fault tolerant clustering method. If any of two dominators are not neighbors of each other then the set of dominators is called independent set. Construction of an independent set is an important method to elect cluster leaders. Self-stabilization provides a decision making mechanism for a node about its state by just checking its neighbors state. Self-stabilization is a very suitable method for distributed and fault tolerant processing. In this technique, nodes should execute well defined rules. In this thesis, distributed self-stabilizing maximal independent set algorithms are studied. Theoretical and practical evalutions of the previous work are made, an algorithm which is shown to be effective than the previous work, is designed. Proposed algorithm is analyzed theoretically, implemented in the simulation environment and tested on Iris nodes.