Name
Title | ||
|---|---|---|
An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs |
Abstract | ||
|---|---|---|
A connected dominating set (CDS) is useful in forming a virtual backbone in wireless ad hoc or sensor networks because these networks lack a fixed infrastructure and centralized management. Self-stabilization guarantees that the system tolerates any finite number of transient faults and does not need any initialization. The safe convergence property guarantees that the system quickly converges to a feasible safe configuration, and subsequently converges to a legitimate configuration without violating safety. A previous publication on a safely converging algorithm for the minimum CDS assumed a phase clock synchronizer, which 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 networks modeled by unit disk graphs (UDGs). We assume that the feasible safe configuration satisfies the condition that a dominating set is constructed. The convergence time to a feasible safe configuration is one round, and the convergence time to a legitimate configuration in which an approximated minimum CDS is constructed is O ( max ¿ { d 2 , n } ) rounds, and O ( n 6 ) steps. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.12.001 | Theoretical Computer Science |
Keywords | Field | DocType |
unit disk graph,self stabilization | Convergence (routing),Approximation algorithm,Mathematical optimization,Combinatorics,Dominating set,Synchronizer,Self-stabilization,Connected dominating set,Wireless ad hoc network,Mathematics,Unit disk graph | Journal |
Volume | Issue | ISSN |
615 | C | 0304-3975 |
Citations | PageRank | References |
1 | 0.39 | 28 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sayaka Kamei | 1 | 186 | 21.28 |
| Tomoko Izumi | 2 | 141 | 21.33 |
| Yukiko Yamauchi | 3 | 196 | 23.91 |