摘要：Ad hoc网络和无线传感器网络具有广泛的应用,但对于这样自组性的网络须采用分层结构的聚簇来有效管理.通过选择具有支配属性的节点构成虚拟主干以支持路由、广播及覆盖等应用.大部分的研究都集中在高效选择较小的连通支配集.全面阐述了连通支配集构造的研究进展,并依据不同的网络假设、设计目标和性能对超过20种连通支配集的构造算法进行分类和总结.指出这一领域的研究方向.

摘要：无线传感器网络中通常利用连通支配集形成虚拟骨干网以进行分层次的路由。现有算法所得到的连通支配集或者只适用于图的连通度比较大的情况,或者没有考虑支配节点的能量等特性。本文设计了一种基于参考能量的连通支配集构造算法,在考虑支配节点的剩余能量的基础上生成连通支配集,使获得的连通支配集不仅适合于各种连通度的拓扑情况,而且具有更好的能量性能。

摘要：定义了有向图指定源点连通支配集问题。借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集。不同模型随机图上的模拟实验表明这些规则和算法是有效的。

摘要：针对无线网络中的连通支配集(CDS)问题,通过分析得到了CDS的一个重要性质,即简单连通无向图的最小CDS是该图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论,设计了一个新的连通支配集求解算法,实验表明,新算法较前人的算法有更好的性能。

摘要：针对最小连通配集问题设计了一种具有较高能量效率的启发式算法。算法首先把网络中所有的节点作为最小连通支配集的一个初始解,然后利用启发式修剪策略剔除冗余节点从而减小最小连通支配集的大小,直到没有冗余节点存在。文中将算法分成集中式和分布式两种情况进行了详细讨论。仿真结果表明,由于实现简便,该算法与其他已有算法相比较,在算法复杂性和算法稳定运行时间上有一定的优势。

摘要：航空集群作战由于具有规模大、时效性高、作战平台资源有限的特点,现有路由算法不能很好地适应于航空集群作战这种特殊环境。结合连通支配集理论,提出路由约束连通支配集路由算法。算法通过构建节点权值函数,分布式构造基于路由约束的连通支配集形成一个骨干网,在此基础上,设计路由约束连通支配集路由算法,使得数据转发可以高效进行,并基于有向图设计骨干网维护机制。仿真结果和理论分析表明,算法在时延、路由开销、死亡节点数方面的综合表现优于经典路由算法,能够较好地适应于航空集群网络。

摘要：现有构建连通支配集CDS(connected dominating set)算法只强调CDS规模,没有考虑能量水平的支配节点。为此,提出一种基于能量均衡的连通支配集的分布式(energy-balance-based connected dominating set distributed,ECDSD)算法。利用基于权值覆盖成本(weighted coverage cost,WCC)构造CDS,WCC含有感测邻居节点的能量,选择具有高WCC值的节点作为支配节点。仿真结果表明,与现有算法相比,ECDSD算法缩小了CDS规模,延长了CDS生命周期约23%,覆盖率提升了约33%。

摘要：移动Ad hoc网络是一种多跳、自组织网络,在该网络中可以通过构建虚拟骨干网来减少参与路由计算的节点数量,虚拟骨干网可以由近似的最小连接主节点集(MCDS)组成。提出了一种考虑节点权值的分布式近似MCDS查找算法,在网络拓扑结构发生变化时对MCDS进行维护。与几种经典的分布式近似MCDS查找算法相比较,结果表明,该算法具有更好的性能。

摘要：针对传感器网络节点资源有限的特点,结合连通支配集的概念,提出了基于最小连通支配集的路由算法。算法通过高效地构造最小连通支配集形成一个虚拟骨干网,使得数据转发可以高效地进行,而且算法是层次式的,具有良好的可扩展性。模拟实验和理论分析也表明算法具有良好的性能。

摘要：连通支配集是一个著名的NP难解问题,在网络和通信等领域具有重要应用.该文主要研究连通支配集的规约规则设计与实现.对现有规约规则进行改进,同时通过对图中顶点进行着色,提出新的局部规约规则.接着对规约规则则进行实现并测试在模拟无线传感网络中的规约效果.实验结果表明,规约规则在各种不同规模和不同稠密度网络中均能不同程度降抵问题规模.