计算机工程2013，Vol.39Issue(2)：99-102,107,5.DOI:10.3969/j.issn.1000-3428.2013.02.020
基于GSO算法的最小连通支配集问题求解
Solution of Minimum Connected Dominating Set Problem Based on Glowworm Swarm Optimization Algorithm
摘要
Abstract
For computing the Minimum Connected Dominating Set(MCDS) in the network, a new algorithm is proposed based on Glowworm Swarm Optimization(GSO) algorithm. Each node of network is considered as individual glowworm emitting luciferin whose intensity is dependent on the degree of the node. By use of the scheme of probabilistic selection and luciferin adjustment, some nodes are attracted toward its neighbors having higher intensity of luciferin, and in this way, a dominated set of the network is constructed which contains the priority individuals. The nodes of the dominating set are connected and a pruning rule is applied to eliminate some redundant nodes for MCDS. Numerical results in Unit Disk Graphs(UDG) modeling wireless networks show the GSO-based algorithm can provide smaller CDS scale, and it is closer to centralized algorithm.关键词
最小连通支配集/萤火虫优化算法/萤光素/节点度/单位圆盘图Key words
Minimum Connected Dominating Set(MCDS)/ Glowworm Swarm Optimization(GSO) algorithm/ luciferin/ node degree/ Unit Disk Graph(UDG)分类
信息技术与安全科学引用本文复制引用
赵学锋..基于GSO算法的最小连通支配集问题求解[J].计算机工程,2013,39(2):99-102,107,5.基金项目
国家自然科学基金资助项目(61163037) （61163037）
