摘要： 为解决连通支配集的最小化问题，提出基于改进的分布式学习自动机的近似算法，在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树，只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明，与现有算法相比，该算法能得到更优的最小连通支配集。
关键词:
最小连通支配集,
学习自动机,
单位圆盘图,
支配树,
深度优先搜索
Abstract: Connected Dominating Set(CDS) has a wide range of applications in wireless networks. For the Minimal Connected Dominating Set(MCDS) problem, an approximation algorithm is presented based on an improved Distributed Learning Automata(DLA). The proposed algorithm considers not only the deeper exploration with random selections, but also the strategy of backtracking. The dominating tree is constructed using only neighborhood information, and some properties of the dominating tree are analyzed on Unit Disk Graph(UDG) to model networks. Experimental results on those graphs show the superiority of the proposed algorithm over the existing algorithms in terms of the MCDS size.
Key words:
Minimum Connected Dominating Set(MCDS),
Learning Automata(LA),
Unit Disk Graph(UDG),
dominating tree,
Depth-First Search(DFS)
中图分类号:
赵学锋, 王秀花, 杨海斌, 张贵仓. 基于学习自动机的最小连通支配集算法[J]. 计算机工程, 2011, 37(10): 149-151.
DIAO Hua-Feng, WANG Xiu-Hua, YANG Hai-Bin, ZHANG Gui-Cang. Minimum Connected Dominating Set Algorithm Based on Learning Automata[J]. Computer Engineering, 2011, 37(10): 149-151.