A self-stabilizing 6-approximation for the minimum connected dominating set with safe convergence in unit disk graphs

In wireless ad hoc or sensor networks, a connected dominating set (CDS) is useful as the virtual backbone because there is no fixed infrastructure or centralized management. Additionally, in such networks, transient faults and topology changes occur frequently. A self-stabilizing system tolerates any kind and any finite number of transient faults, and does not need any initialization. An ordinary self-stabilizing algorithm has no safety guarantee and requires that the network remains static while converging to a legitimate configuration. Safe converging self-stabilization is one extension of self-stabilization. The safe convergence property guarantees that the system quickly converges to a safe configuration, and then, it moves to an optimal configuration without breaking safety. In this paper, we propose a self-stabilizing fully distributed 6-approximation algorithm with safe convergence for the minimum CDS in the networks modeled by unit disk graphs.