A Self-Stabilizing Distributed Approximation Algorithm for the Minimum Connected Dominating Set
A Self-Stabilizing Distributed Approximation Algorithm for the Minimum Connected Dominating Set
复制标题
DOI：
10.1142/s0129054110007362
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
S. Kamei;H. Kakugawa
中科院分区：
文献类型：
--
作者：
S. Kamei;H. Kakugawa
自稳定是一种非掩蔽容错分布式算法的理论框架。自稳定系统可以容忍任何种类和有限数量的瞬态故障，如消息丢失、内存损坏和拓扑变化。由于此类瞬时故障在移动自组织网络中频繁发生，因此它们上的分布式算法应该能够容忍此类事件。本文提出了一种最小连通支配集的自稳定分布式逼近算法，该算法可用于移动自组网中的虚拟主干网或路由。我们算法的解的大小最多为8 |Dopt | + 1，其中Dopt是最小连通支配集。时间复杂度为O（n2）步。
Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. A self-stabilizing system tolerates any kind and any finite number of transient faults, such as message loss, memory corruption, and topology change. Because such transient faults occur so frequently in mobile ad hoc networks, distributed algorithms on them should tolerate such events. In this paper, we propose a self-stabilizing distributed approximation algorithm for the minimum connected dominating set, which can be used, for example, as a virtual backbone or routing in mobile ad hoc networks. The size of the solution by our algorithm is at most 8 |Dopt | + 1, where Dopt is a minimum connected dominating set. The time complexity is O(n2) steps.