Paper Info
Title
An Asynchronous Self-stabilizing Approximation for the Minimum Connected Dominating Set with Safe Convergence in Unit Disk Graphs
Abstract
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.
Year
DOI
Venue
2013
10.1007/978-3-319-03089-0_18
SSS
Field
DocType
Volume
Convergence (routing),Asynchronous communication,Mathematical optimization,Dominating set,Synchronizer,Connected dominating set,Wireless ad hoc network,Initialization,Mathematics,Unit disk graph
Conference
8255
ISSN
Citations 
PageRank 
0302-9743
5
0.43
References 
Authors
11
3
Name
Order
Citations
PageRank
Sayaka Kamei118621.28
Tomoko Izumi214121.33
Yukiko Yamauchi319623.91