。在任意图中求解最小连通支配集是NP难[4]问题，因此常采用启发式算法近似求解，基于转发节点集的连通支配集分布式算法#唐勇，张军，汪文勇，向渝，张骏，杨挺*（电子科技大学计算机科学与工程学院，成都611731）510摘要：在无线传感器网络中，构造一个虚拟骨干网是优化网络性能的重要手段。虚拟骨干网的构造在数学上等同于求图的最小连通支配集，最小连通支配集的求取问题已经被证明是NP完全问题，因此采用启发式的方法求取一个最优解。本文提出了FWCDS算法(AForwardsetBasedCDSDistributedConstructionAlgorithm)，仅利用了1-hop的邻节点信息，在每个节点上分布式的构造一个转发集，然后采用一个广播染色算法，从这些转发集中选择一部分节点作为支配节点，构造一个连通支配集。FWCDS算法改进了OHDC算法[9]。仿真结果表明，FWCDS算法有约等于支配节点数的额外消息数，同时有约等于网络直径的收敛时间，而且得到了一个较小的CDS。关键词：无线传感器网络；连通支配集；分布式算法中图分类号：TP39315ForwardingSetBasedDistributedalgorithmforCDSTangYong,ZhangJun,WangWenyong,XiangYu,ZhangJun,YangTing(SchoolofComputingScienceandEngineering,UniversityofElectronicScienceandTechnologyofChina,ChengDu611731)202530Abstract:InWirelessSensorNetworks,VirtualBackboneisanimportantmethodtooptimizenetworkperformance.Inmathematics，theconstructionofVirtualBackboneequivalenttoseekingtheMinimumConnectedDominatingSet(MCDS)whichhasbeentoprovedtobeNP-completeproblem.Aheuristicapproachisanapproximatesolution.ThispaperpresentsFWCDSalgorithm(AForwardsetBasedCDSDistributedConstructionAlgorithm)usingonly1-hopneighbors’informationofnode,atfirst,constructsaforwardsetdistributedoneachnodeofnetworks.Andsecond,FWCDSstartsabroadcasttoselectdominatingnodesfromtheforwardnodessetofeachnodeofwholenetworks.FWCDSalgorithmisaenhancementofOHDCalgorithm[9].Simulationresultsshowthat,theadditionalnumberofmessagesofFWCDSalgorithmisapproximatelyequalCDSsize,withconvergencetimeapproximatelyequivalenttodiameterofNetworkandasmallerCDS.Keywords:wirelesssensornetworks;CDS;distributedalgorithm0引言在无基础设施的无线传感器网络中，高效快速的构造一个虚拟骨干网无疑是非常有意义35的[1-3]其主要方法有集中式[5]和分布式[6]两种。采用集中式方法虽然能够得到较小的连通支配集，但求解前需要知道整个图的拓扑信息，这对于动态性强的无线传感器网络并不适用，因此，一般应采用分布式方法。在过去的几年中，许多机构和研究组织已经着手这一方面的研究，并且出现了一些喜人的研究成果，其中几个经典的算法有Dai’s算法[7]，MISB算法[8]以及40OHDC算法[9]。本章在OHDC算法的基础上，提出了一个简化的算法，称为FWCDS（AForwardsetBasedCDSDistributedConstructionAlgorithm）算法。同OHDC算法相似，FWCDS算法仍然采用区域覆盖的思想，但与OHDC算法不同，FWCDS算法仅仅判断哪些节点在1-hop邻居所覆盖区域的边缘，然后直接确定这些边缘节点为转发节点。FWCDS算法思想基金项目：教育部博士点基金新教师项目(200806141110)作者简介：唐勇，（1973-），男，工学博士，电子科技大学副教授。主要研究方向为无线传感器网络、网络管理.E-mail:worldgulit@uestc.edu.cn-1-∈N[UA(B(v))，因此，节点V中所UA(B(v))。简单，易于实现，并且改进了CDS尺寸。算法分析与仿真结果表明，算法完成了设计的目45标：良好的CDS尺寸，极少的通信量以及快速的收敛时间。1问题描述1.1网络模型本算法采用Unit-disk图无线传感器网络模型。在Unit-disk模型中，若网络拓扑图表示为G(V,E)，则图的顶点集V表示网络的传感器节点集合，图的边集E表示网络的通信50链路集合。若∃u,v∈V，且uv∈E，则称节点u，v之间有一条通信链路，节点u和v可以互相通信。此时u和v的直线距离小于等于R。假定算法在理想的网络环境中执行，即所有传感器节点同质同材，配有全向天线。...