求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。     

一种改进的无线传感器网络EEMCDS算法

针对无线传感器网络中的有效路由,提出了一种改进的,基于最小连通支配集的能量有效算法IEEMCDS(Improved Energy-Efficient Minimum Connected Dominating Set).路由搜索主要集中在连通支配集内,通信量小.该算法是一个能量有效的分布式算法,在维护最小连通支配集时,充分考虑了节点的能量问题,优先选择高能量的节点充当连通支配集节点,提出了支配节点能量最小阈值调整法,可以有效地延长网络寿命.实例仿真表明在改进算法的连通支配集中,高能量的节点在支配集中一直占有较高的比例,从而有效地延长了网络寿命.     

分布式最小连通支配集启发式算法

针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7．60pt＋1．4,时间复杂度为O（△^2）,消息复杂度为O（n）,比同类算法优秀。     

无线传感器网络中的连通支配集求解算法

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。     

一种高效的最小连通支配集贪心算法

连通支配集（CDS）在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS）,依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。     

Ad Hoc网络均匀区域广播算法

综合考虑节点连通度、剩余能量和节点相对距离3个因素，提出一种新的基于权值的均匀区域广播算法。根据节点权值构建独立支配集并确定候选支配节点，选取候选支配节点连通独立支配集，在此基础上对广播算法进行优化，进一步消除冗余转播节点，提高广播算法的性能。理论分析和仿真结果表明，该算法在节点密集和稠密分布不均的情况下能有效降低广播时延。     

基于拓扑特性的分布式虚拟骨干网算法

由于在任意连通网络中搜索最小连通支配集(minimum connected domination set,简称MCDS)是NP完全问题,提出了一种拓扑感知的MCDS启发式算法——TACDS(topology-aware connected domination set),并证明了其正确性.通过利用节点的拓扑特性,减小了支配节点选择的盲目性.该算法能够根据2跳内的局部拓扑信息构造出较小的CDS(connected domination set),从而得到基于该支配集的虚拟骨干网.仿真结果表明,该算法优于其他分布式CDS算法,可以更好地近似MCDS.     

一种基于反向CDS树的异构WSNs拓扑构建方法

在无线传感器网络中,拓扑控制是节约能源、延长生命周期的一项关键技术。现有拓扑控制方法的研究主要集中在同构网络,对此,面向异构网络提出了一种低信息复杂度的基于反向连通支配集树的分布式拓扑构建算法。基于最小连通支配集构建虚拟骨干树,改进了A3G算法中节点的适应度函数和算法流程,优化了产生的连通支配集的规模和通信开销,进一步降低信息复杂度,在保证连通性的同时关闭网络冗余节点以降低能耗。理论分析和仿真实验证明,算法能够以较小的时间和通信代价构建拓扑,延长网络生命周期。     

无线传感器网络极小连通支配集算法的改进

无线传感器网络中,基于极小连通支配集的虚拟骨干网的构建使得路由搜索空间集中在支配节点之间,能够有效节省网络资源,减少冗余转发节点。首先提出连通支配集的数学模型。基于WL算法,提出改进的极小连通支配集分布式算法。仿真结果表明,改进算法求得的连通支配集较小,可为无线传感器网络中的路由协议提供通讯基础。     

连通支配集一种集中式近似算法

简单无向图的最小连通支配集问题是NP完全问题,目前还没有成熟解法。提出了一种用有序表构建独立集求解连通支配集的算法,算法从图中度最大的顶点开始将顶点加入到有序表中,并在加入过程中构建独立集,同时加入其他节点连接独立集使其成为连通集。当图中所有节点处理完成,有序表中标记为独立集的节点和连接节点就形成了一个连通支配集。实验表明算法生成的支配集较小,运行时间复杂度比较低。