An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
复制标题
UDG 中安全收敛的最小 CDS 的异步自稳定近似
DOI：
10.1016/j.tcs.2015.12.001
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Yukiko Yamauchi,
中科院分区：
文献类型：
--
作者：
Sayaka Kamei;Tomoko Izumi;Yukiko Yamauchi,
在无线自组网或传感器网络中，连通支配集(CDS)对于形成虚拟骨干网非常有用，因为这些网络缺乏固定的基础设施和集中管理。自稳定保证了系统可以容忍任何有限数量的瞬时故障，并且不需要任何初始化。安全收敛属性确保系统快速收敛到可行的安全配置，并随后收敛到合法配置而不违反安全性。以前发表的关于最小CDS的安全收敛算法的文章假设了一个相位时钟同步器，这是一个非常强的假设。本文提出了单位圆盘图(UDG)网络中求最小CDS的第一个安全收敛的异步自稳定(6+ϵ)近似算法。我们假设可行的安全配置满足构造支配集的条件。收敛到可行安全构形的时间为一轮，而收敛到构造近似最小CDS的合法构形的时间为O(max{d2，n})轮和O(N 6)步。
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.