。在任意图中求解最小连通支配集是NP难[4]问题，因此常采用启发式算法近似求解，基于网络分层的连通支配集算法#唐勇，张军，汪文勇，向渝，张骏，杨挺*（电子科技大学计算机科学与工程学院，成都611731）51015202530摘要：在无线传感器网络中，构造一个虚拟骨干网是优化网络性能的重要手段。虚拟骨干网的构造在数学上等同于求图的最小连通支配集，最小连通支配集的求取问题已经被证明是NP完全问题，因此采用启发式的方法求取一个最优解。本文提出了LCDS算法(ALayerBasedCDSConstructionAlgorithm)，首先选取一个源节点（sink或簇头节点），然后以此节点将网络按跳数划分成若干层。分层完成后，各层分布式的计算本层的支配节点集，所有层的支配节点集的并即为网络的连通支配集。LCDS算法的时间复杂度为，其中表示节点的平均度。仿真结果表明，LCDS算法获得了一个比MTCDS[6]和MISB[10]等算法小的CDS，并且随着网络密度快速增加，LCDS算法获得的CDS尺寸增加很小，在密度很大的无线传感器网络中，LCDS算法仍然能得到一个较小的CDS。关键词：无线传感器网络；连通支配集；分层中图分类号：TP393ALayerBasedCDSConstructionAlogrithmTangYong,ZhangJun,WangWenyong,Xiangyu,ZhangJun,YangTing(SchoolofComputingScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,ChengDu611731)Abstract:InWirelessSensorNetworks,VirtualBackboneisanimportantmethodtooptimizenetworkperformance.Inmathematics，theconstructionofVirtualBackboneequivalenttoseekingtheMinimumConnectedDominatingSet(MCDS)whichhasbeentoprovedtobeNP-completeproblem.Aheuristicapproachisanapproximatesolution.ThispaperpresentsLCDSalgorithm(ALayerBasedCDSConstructionAlgorithm)proposesalayermodel.First,thisalgorithmselectsasourcenode(sinkorclusterhead),thenitstartsabroadcastfromthisnodetodividenetworksintoseverallayersaccordingtohops.Afterlayerisdivided,eachlayerperformingCDSconstructionalgorithmcomputesdominatingsetseparately,andtheunionofdominatingsetofalllayersactsCDSofnetworks.ThetimecomplexityofLCDSiswhererepresentaveragedegreeofnodes.Simulationresultsshowthat,LCDSalgorithmgetsasmallerCDSthanotheralgorithmswhichincludeMTCDS[6]andMISB[10]algorithmandwiththerapidincreaseofnetworkdensity,theincreaseofCDSisveryslow.WhennodesofWSNhaveaverylargedensity,LCDSalgorithmisstillabletogetasmallerCDS.Keywords:wirelesssensornetworks;CDS;Layer350引言在无基础设施的无线传感器网络中，高效快速的构造一个虚拟骨干网无疑是非常有意义的[1-3]其主要方法有集中式[5]和分布式[6]两种。采用集中式方法虽然能够得到较小的连通支配集，40但求解前需要知道整个图的拓扑信息，这对于动态性强的无线传感器网络并不适用，因此，一般应采用分布式方法。连通支配集的构造作为著名的NP难问题，至今仍然无法证明存在多项式时间内的求解算法。为了提高无线传感器网络的性能，有必要构造一个以连通支配集表示的虚拟骨干网。因此，人们不断的探索各种方法来构造尽可能小的连通支配集，以接近最优求解算法。MTCDS算法[6]及其改进算法[7][8]提出了在每个节点设置反向定时器，从中心基金项目：教育部博士点基金新教师项目（200806141110）作者简介：唐勇，（1973-），男，工学博士，电子科技大学副教授。主要研究方向为无线传感器网络、网络管理.E-mail:worldgulit@uestc.edu.cn-1-UN(u)−N(v)−N455055606570到边缘的广播扩散构造连通支配集的方法，但由于使用反向定时器的原因，算法的延迟太大，对具有一定动态性的无线传感器网络并不适用。本文提出了一种分层CDS构造算法，将网络从一个源(中心)节点按照不同的跳数划分成不同的层。网络的各层分布式的求取支配集，所有层支配集的并即构成了网络的CDS。仿真结果表明本算法在CDS大小上优于其它几个算法。1问题描述本文提出了一个网络分层模型，分层模型将网络划分成n层，每一层是一个闭合的环型区...