基于学习自动机的最小连通支配集算法

Minimum Connected Dominating Set Algorithm Based on Learning Automata

为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。

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.