作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2013, Vol. 39 ›› Issue (2): 99-102.

• 网络与通信 • 上一篇    下一篇

基于GSO算法的最小连通支配集问题求解

赵学锋   

  1. (西北师范大学计算机科学与工程学院,兰州 730070)
  • 收稿日期:2012-03-30 修回日期:2012-05-28 出版日期:2013-02-15 发布日期:2013-02-13
  • 作者简介:赵学锋(1965-),男,副教授、硕士,主研方向:网络优化算法
  • 基金资助:

    国家自然科学基金资助项目(61163037)

Solution of Minimum Connected Dominating Set Problem Based on Glowworm Swarm Optimization Algorithm

ZHAO Xue-feng   

  1. (College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China)
  • Received:2012-03-30 Revised:2012-05-28 Online:2013-02-15 Published:2013-02-13

摘要: 经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。

关键词: 最小连通支配集, 萤火虫优化算法, 萤光素, 节点度, 单位圆盘图

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)

中图分类号: