A SELF-STABILIZING DISTRIBUTED APPROXIMATION ALGORITHM FOR THE MINIMUM CONNECTED DOMINATING SET

被引：8

作者：

Kamei, Sayaka ^{[1
]}

Kakugawa, Hirotsugu ^{[2
]}

机构：

[1] Hiroshima Univ, Dept Informat Engn, Hiroshima 7398527, Japan

[2] Osaka Univ, Dept Comp Sci, Osaka 5608531, Japan

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2010年 / 21卷 / 03期

关键词：

Self-stabilizing algorithm; approximation algorithm; ad hoc network; minimum connected dominating set; fault-tolerant; STEINER TREE; CONSTRUCTION;

D O I：

10.1142/S0129054110007362

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 7.6 vertical bar D-opt vertical bar + 1.4, where D-opt is the minimum connected dominating set. The time complexity is O(k) rounds, where k is the depth of input BFS tree.

引用

页码：459 / 476

页数：18

共 31 条

[1] [Anonymous], 1999, P 3 INT WORKSHOP DIS, DOI DOI 10.1145/313239.33261
[2] Blum J., 2005, HDB COMBINATORIAL OP, P329
[3] Cheng X., 2002, Virtual backbone-based routing in multihop ad hoc wireless networks
[4] UNIT DISK GRAPHS
CLARK, BN
COLBOURN, CJ
JOHNSON, DS
[J]. DISCRETE MATHEMATICS, 1990, 86 (1-3) : 165 - 177
[5] Das B., 1997, ICC 97 1997 IEEE INT, V1, P376
[6] SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL
DIJKSTRA, EW
[J]. COMMUNICATIONS OF THE ACM, 1974, 17 (11) : 643 - 644
[7] Dolev S., 2000, Self-Stabilization
[8] Drabkin V, 2006, LECT NOTES COMPUT SC, V4305, P425
[9] Duchet P., 1982, North-Holland Math. Stud., V62, P71, DOI DOI 10.1016/S0304-0208(08)73549-7
[10] A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks
Gao, B
Yang, YH
Ma, HY
[J]. INTERNATIONAL JOURNAL OF COMMUNICATION SYSTEMS, 2005, 18 (08) : 743 - 762

← 1 2 3 4 →