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

作者：Kamei Sayaka^*; Kakugawa Hirotsugu

来源：Theoretical Computer Science, 2012, 428: 80-90.

DOI：10.1016/j.tcs.2011.12.007

• Self-stabilization
• Safe convergence
• The minimum connected dominating set

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.

• 出版日期2012-4-13