共查询到16条相似文献,搜索用时 46 毫秒
1.
2.
能量有效的最小连通支配集近似算法 总被引:3,自引:2,他引:3
针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy-Efficient minimum connected dominating set),路由搜索主要集中在连通支配集内.本文提出一个能量有效的简洁有效的分布式算法,该算法根据各节点所具有的能量不同,优先选择高能量的节点作为连通支配集节点,可以有效地延长网络寿命.实例仿真表明在连通支配集节点数量较少的情况下,高能量的节点在支配集中所占的比例也是较高的. 相似文献
3.
4.
在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网以进行分层路由。在支配集中的节点的耗能相对其它节点要多,虚拟骨干网的生存周期由剩余能量最小的传感器节点决定。提出了一个有能量门限限制的连通支配集分布式构造算法,算法的主要思路是从任一节点开始,采用邻域深度优先搜索,当一个方向搜索结束时再回朔搜索其它方向来形成连通支配集;若某一支配点的邻域中的节点能量小于门限值,则回朔搜索其它方向来形成支配集。 相似文献
5.
在无线传感器网络中,能量效率问题至关重要,构造精简的虚拟骨干网可以节约有限资源,这等同于在图论中求解最小连通支配集(MCDS)问题.由此,提出一种构造MCDS的启发式算法.首先根据均值公式为顶点建立次序表,其次构造极大独立集(MIS),再次连接MIS节点,最后优化.仿真实验表明:该算法能够在短时间内找到规模较小的连通支配集(CDS),并且有效地均衡了各节点能量,延长了网络生命周期. 相似文献
6.
针对AdHoc网络中用洪泛法进行广播易引起广播风暴的问题,提出一个新的分布式最小连通支配集启发式算法HMCDS,其中包括构建极大独立集、引入节点的有效度概念、选择有效度最大的节点作为支配点的贪心策略的方法,实验结果证明,HMCDS算法生成的连通支配集大小为7.60pt+1.4,时间复杂度为O(△^2),消息复杂度为O(n),比同类算法优秀。 相似文献
7.
8.
无线传感器网络中通常利用连通支配集形成虚拟骨干网以进行分层次的路由.现有算法所得到的连通支配集或者只适用于图的连通度比较大的情况,或者没有考虑支配节点的能量等特性.本文设计了一种基于参考能量的连通支配集构造算法,在考虑支配节点的剩余能量的基础上生成连通支配集,使获得的连通支配集不仅适合于各种连通度的拓扑情况,而且具有更好的能量性能. 相似文献
9.
一种最小连通支配集的分布式广播算法 总被引:1,自引:0,他引:1
研究移动自组网络中的广播算法,提出了一种适用于移动自组网络的基于最小连通支配集的分布式广播算法,并证明了新的广播算法与已有算法相比能够更加有效地解决网络采用洪泛(Flooding)方式进行广播时所可能产生的广播风暴问题。同时,算法是基于并行和分布式运行模式的,因此具有很好的扩展性和实用性。 相似文献
10.
一个新的分布式最小连通支配集近似算法 总被引:32,自引:0,他引:32
在计算机网络中广泛使用广播来解决一些网络问题,设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息,可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网,从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明,文中提出的算法求得的连通支配集小,能较好地应用于一般网络以及移动自组网络中。 相似文献
11.
12.
13.
寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果. 相似文献
14.
分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则.规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模.从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性. 相似文献
15.
自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法。 相似文献
16.
一种新的自组网极小连通支配集生成算法 总被引:1,自引:0,他引:1
自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based—Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(A)和O(n△),该性能明显优于已有的算法. 相似文献