论文摘要
无线传感器网络（Wireless Sensor Network,WSN）是一种全新的信息获取平台,能够利用各种各样的传感器,实时监测和采集网络分布区域内的各种监测对象的信息,并将这些信息通过无线网络发送到任务管理节点,以实现目标对象的监视与跟踪。无线传感器网络具有快速展开、大范围监测和抗毁性强等特点,已经引起了各国政府与研究组织的兴趣,构建虚拟骨干网是无线传感器网络一个热门的研究领域。由于无线传感器网络无基础设施的特点,使得网络管理以及路由等问题凸显,而传感器节点资源又十分有限,因此,有必要构造一个虚拟骨干网充当基础设施,提高资源利用率,优化网络性能。虚拟骨干网的构造在数学上等同于求图的最小连通支配集,最小连通支配集的求取问题已经被证明是NP完全问题,目前通用的方法是采用启发式的方法求取一个最优解。求取连通支配集（Connected Dominating Set,CDS）的算法被分为集中式算法和分布式算法,由于无线传感器网络拓扑的动态性特点,采用集中式算法并不适合,因此多采用分布式的求取算法。本文提出了两个分布式的CDS求取算法:FWCDS（A Forword set Based CDS Distributed Construction Algorithm）算法和LCDS（A Layer Based CDS Construction Alogrithm）算法。FWCDS算法仅利用了1-hop的邻节点信息,在每个节点上分布式的构造一个转发集,然后采用一个广播染色算法,从这些转发集中选择一部分节点作为支配节点,构造一个连通支配集。FWCDS算法改进了OHDC算法。仿真结果表明,FWCDS算法有约等于支配节点数的额外消息数,同时有约等于网络直径的收敛时间,而且得到了一个较小的CDS。小的额外消息数,快速的收敛以及较小的CDS,决定了FWCDS算法非常适合于动态性较强的无线传感器网络。LCDS算法提出了一个分层模型,首先选取一个源节点（sink或簇头节点）,然后以此节点将网络按跳数划分成若干层。分层完成后,各层分布式的计算本层的支配节点集,所有层的支配节点集的并即为网络的连通支配集。LCDS算法的时间复杂度为O （Δ2）,其中Δ表示节点的平均度。仿真结果表明,LCDS算法获得了一个比MTCDS和MISB等算法小的CDS,并且随着网络密度快速增加,LCDS算法获得的CDS尺寸增加很小,在密度很大的无线传感器网络中,LCDS算法仍然能得到一个较小的CDS。