能量有效的最小连通支配集近似算法

针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy-Efficient minimum connected dominating set),路由搜索主要集中在连通支配集内.本文提出一个能量有效的简洁有效的分布式算法,该算法根据各节点所具有的能量不同,优先选择高能量的节点作为连通支配集节点,可以有效地延长网络寿命.实例仿真表明在连通支配集节点数量较少的情况下,高能量的节点在支配集中所占的比例也是较高的.     

一种最小连通支配集的分布式广播算法

研究移动自组网络中的广播算法,提出了一种适用于移动自组网络的基于最小连通支配集的分布式广播算法,并证明了新的广播算法与已有算法相比能够更加有效地解决网络采用洪泛(Flooding)方式进行广播时所可能产生的广播风暴问题。同时,算法是基于并行和分布式运行模式的,因此具有很好的扩展性和实用性。     

高效的分布式最小连通支配集近似算法

在Alzoubi and Wan’s算法的基础上,利用2跳局部网络拓扑信息选择连通点,提出一个高效的分布式最小连通支配集算法EDMCDS。理论分析表明,EDMCDS算法生成的连通支配集大小为(5.8+ln4)opt+1.2,时间复杂度为 ,信息复杂度为 。与TFA和Alzoubi and Wan’s算法相比,该算法生成的连通支配集更小,时间复杂度和信息复杂度也有所降低。     

移动Ad Hoc网络中最小连通支配集的分布式高效近似算法

提出了一种基于局部最大度数与节点标识号相结合的支配点选择斤式,并基于该方式给出了一种计算移动Ad Hoc网络最小连通支配集的分布式近似算法CDSA,实验显示,CDSA算法生成的连通支配集比文献所提出的WL、CBBA及MCDS算法更小另外,CDSA是一种动态的和基于分布式的算法,冈此它不但适用于移动Ad Hoc网络,也适用于一般网络中的最小连通支配集的近似计算问题。     

自组织网络分布式最小连通支配集创建算法*

针对无线自组织分组（Ad hoc）网络中最小连通支配集（MCDS）创建NP难问题,提出了一种分布式的最小连通集创建算法DMCA。DMCA基于最大独立集（MIS）的构建,只需要周围一跳邻居的信息,在不超过三跳距离的一对支配节点之间找出一条最短路径。对DMCA算法的性能分析表明,DMCA具有常数的近似比、线性的时间和消息复杂度。详细的仿真实验以及与其他创建最小连通支配集算法的比较表明,提出的DMCA算法在节点数量与节点传输范围变化时创建的最小连通集更小。     

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。     

基于域的分布式最小连通支配集的启发式算法

在规模较大且移动较频繁的ad hoc网络中,针对构建树形连通支配集缓慢且网络开销大的问题,提出了基于域的分布式最小连通支配集的启发式算法(ZBCDS).ZBCDS在求得极大独立集的基础上,定义了节点阶势和候选节点的概念,通过判断节点的阶势,优化了域的生成和域边界上连接节点的调整,达到CDS重构快速高效地实现的目的.实验...     

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

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

一种参考能量的最小连通支配集近似算法

在无线传感器网络中,能量效率问题至关重要,构造精简的虚拟骨干网可以节约有限资源,这等同于在图论中求解最小连通支配集(MCDS)问题.由此,提出一种构造MCDS的启发式算法.首先根据均值公式为顶点建立次序表,其次构造极大独立集(MIS),再次连接MIS节点,最后优化.仿真实验表明:该算法能够在短时间内找到规模较小的连通支配集(CDS),并且有效地均衡了各节点能量,延长了网络生命周期.     

求解圆盘图中最小连通支配集的近似算法

针对无线传感器网络常用的拓扑模型单位圆盘图,提出了基于分布式贪心策略的近似算法DDT,在算法执行的每一轮中,根据一跳邻域范围内的权值和邻居的状态信息,选举出节点并和已确定的节点连接,逐步构造出网络图中的一个支配树。用概率方法研究了支配树中的节点度的性质,通过对极大独立集和最小连通支配集之间关系的分析,得到单位圆盘图中最小连通支配集问题一个新的近似比。计算结果表明,和相关的分布式算法相比,DDT产生的连通支配集在规模上更优。     

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.     

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法。     

最小连通支配集问题的化简算法

分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则.规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模.从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性.     

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织，构造成一种不需要任何基础设施的新型无线网络，基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足，基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS（Coloring Based—Minimum Connected Dominating Set）。CB-MCDS算法仅需要一跳邻居节点的拓扑信息，就能快速地构造出虚拟主干网，理论分析表明整个算法的时间和消息复杂度分别为O（A）和O（n△），该性能明显优于已有的算法.     

能量限制的连通支配集分布式构造

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网以进行分层路由。在支配集中的节点的耗能相对其它节点要多,虚拟骨干网的生存周期由剩余能量最小的传感器节点决定。提出了一个有能量门限限制的连通支配集分布式构造算法,算法的主要思路是从任一节点开始,采用邻域深度优先搜索,当一个方向搜索结束时再回朔搜索其它方向来形成连通支配集;若某一支配点的邻域中的节点能量小于门限值,则回朔搜索其它方向来形成支配集。     

Ad Hoc 网络和无线传感器网络中连通支配集的分布式构造

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