Self-Stabilizing Algorithm for Dynamically Maintaining Two Disjoint Dominating Sets

摘要

This paper considers dynamically maintaining two disjoint dominating sets for sleep scheduling or cluster head scheduling in sensor networks. We formulate this problem as the local (1, |N_i)-critical section (abbr. CS) problem which is one of the generalizations of the mutual exclusion problem. This is the problem of controlling the system in such a way that, for each process, among its neighbors and itself, at least one process must be in the CS and at least one process must be out of the CS at each time. In this paper, first, we consider an inefficient (costly) self-stabilizing algorithm for the local (1, |N_i)-CS problem. Additionally, this paper shows the necessary and sufficient conditions to solve the problem without any deadlock detection based on the algorithm. After that, an efficient self-stabilizing algorithm for the local (1, |N_i)-CS problem is proposed. The convergence time of the proposed algorithm is O(n) rounds under the weakly fair distributed daemon.