赵学锋

(西北师范大学计算机科学与工程学院，兰州 730070)

1 概述

在连通网络图G(V, E)中，支配集D是V的一个子集，使得V-D中的任一节点和D中的一个节点邻接。当D的导出子图G[D]连通时，称D为图G的连通支配集(Connected Dominating Set, CDS)，当D点数最小时称为最小连通支配集(Minimum Connected Dominating Set,MCDS)。MCDS在无线传感器网络设计中有重要应用，如通过构建以 CDS为原型的虚拟骨干网可改善网络性能，虚拟骨干网络使整个网路的路由搜索空间缩小到一个规模较小且稀疏的子网上，维护网络路由信息的任务仅由支配节点完成，从而减少开销、节省能耗。无线传感器网络的基本模型是单位圆盘图(Unit Disk Graph,UDG)，在这类特殊的拓扑结构上，MCDS的计算依然是NP难的，因此设计在多项式时间内获得更好近似解的算法引人关注。文献[1]由度数大的节点局部自我选举为支配点，形成区域支配集，再用边界点连接成为CDS。文献[2]在初始时将V作为CDS，随后逐步删除冗余节点。这2种算法都是确定性的，基于学习自动机的MCDS算法[3]由单个节点开始扩充成为网络的支配树，在选择支配点时考虑了随机性。文献[4]采用节点的局部转发因子作为选择支配节点的优先级，然后补充连通节点产生CDS，局部转发因子的计算需要2-跳局部信息。

萤火虫优化[5](Glowworm Swarm Optimization, GSO)算法是一类新型的群体智能优化算法，主要有荧光素更新、个体移动和决策域调整3个阶段，萤火虫个体之间通过由荧光素决定的荧光相互影响。萤火虫的亮度与该个体所处位置的目标函数值有关，荧光素越浓则萤光越亮，表明该萤火虫代表更优的目标值，会更吸引周围其他亮度较暗的个体。……