An Asynchronous Self-stabilizing 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. Safe converging self-stabilization is one extension of self-stabilization, that is, self-stabilization guarantees the system tolerates any kind and any finite number of transient faults and doesn’t need any initialization. The safe convergence property guarantees that the system quickly converges to a safe configuration, and then, the system configuration becomes to an optimal configuration without breaking safety. However, the previous works on safe converging algorithm for the minimum CDS assumed a phase clock synchronizer, this is a very strong assumption. In this paper, we propose the first

asynchronous

self-stabilizing (6 + 

ε

)-approximation algorithm with safe convergence for the minimum CDS in the networks modeled by unit disk graphs. The first convergence time to a safe configuration in which a dominating set is computed is 1 round, and the second convergence time to an optimal configuration in which an approximation of the minimum CDS is constructed is

O

( max {

d

2

,

n

}) rounds,

O

(

n

6

) steps.