无线传感器网络中2-连通k-支配的容错连通支配集构造

无线传感器网络可采用连通支配集的虚拟骨干技术使平面网络层次化,但传感器节点的失效和链路的断裂会导致网络失败,虚拟骨干网最好具有容错性好、可靠性高的特性.对此,提出具有容错性的2-连通 -支配集的构造算法,以节点自身和邻域信息分布式地构造 -支配节点,利用最小生成树和块-割点图将 -支配节点2-连通.理论分析和实验仿真表明此算法具有较好的算法性能比,在中等规模网络中会产生更少的具有容错性的 -支配节点,可节省传感器节点的能量消耗和网络的通信开销.     

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段.由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期.现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点.提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点.仿真结果表明,新算法能以较小消息开销,有效延长网络寿命.     

基于连通支配集的虚拟骨干网构造算法

针对无线传感器网络中缺少骨干网络的问题,提出一种基于连通支配集的虚拟骨干网构造算法。该算法利用图论中的极大独立集和连通支配集构造一个虚拟骨干网络,运用修剪规则去除冗余节点,通过优先选择能量多、距离近的节点使网络寿命更长、延迟更小。实验结果表明,该算法在单位圆图中产生的连通支配集至多为7.6opt+1.4,消息复杂度和时间复杂度为O(n)。     

2-连通2-支配集的集中式构造

在无线传感器网络中,通常采用连通支配集来构成一个虚拟骨干网进行分层路由,对重要的目标或环境需要构造容错性高,可靠性好的虚拟骨干网。提出构造网络2-连通2-支配集的两种集中式算法,分别是先回路后支配和先支配后回路。前一种算法是先形成一个由支配点组成的回路,然后以此回路为基础不断地扩充此回路,直到不在回路中的节点为2-被支配为止;后一种算法是首先保证每个非支配点都要变成2-被支配点,然后再使图中所有支配点构成回路。     

能量均衡的最小2-连通2-支配集的分布式算法

在无线传感器网络中,一般通过构造连通支配集形成虚拟骨干网来分层路由。现有算法通常只考虑如何获得规模较小的支配集,忽略网络自身的不稳定性,使得节点失效或链路失败经常发生。针对连通支配集的容错能力,结合节点度与能量因素,提出一种能量均衡的最小2-连通2-支配集的分布式算法（DA-EBM）。 Omnet仿真实验表明, DA-EBM算法构造的容错连通支配集能有效均衡能量消耗,延长网络生命周期。     

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

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

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

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

基于参考能量的无线传感器网络连通支配集算法研究

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

能量均衡的最小连通支配集分布式算法

在无线传感器网络路由协议中,最小连通支配集构成的虚拟骨干网是缓解广播风暴的有效方法。现有算法在构造连通支配集时,通常只考虑支配集的规模,虽然获得了较小的支配集,但也造成虚拟骨干网生命周期较短等问题。为了有效解决该问题,提出了一种能量均衡的最小连通支配集分布式算法(EB-MCDS)。仿真实验结果表明,与现有算法相比,EB-MCDS算法有效的均衡了网络能量,延长了网络生命周期20%左右。     

传感器网络中基于连通支配集的路由算法

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

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

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

无线传感器网络中一种改进的能效数据收集协议

基于连通支配集的虚拟骨干是减少支配节点数量和限制路由搜索空间的关键技术,对于优化无线传感器网络生命起到重要作用。ViTAMin协议不但能通过关闭一些非必要节点产生虚拟骨干,而且能将采集的数据沿着距离基站能耗最低的路径进行发送,以节省能量。针对ViTAMin可能会产生非连通网络且支配节点能耗不均衡的问题,提出了一种基于虚拟骨干的能效数据收集协议EEVB。理论分析证明,EEVB能够以O(n)的时间与信息复杂度构造连通支配集,仿真实验进一步证实EEVB能够以较小的能耗开销构建规模较小的连通支配集,并有效延长网络的生命时间。     

无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法

在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,Wang Feng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。     

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

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

SEBCDS:无线传感网络的连通支配集算法

由于无线传感网络(WSN,sireless sensor network)节点受到能量和传输距离的约束,有效地构建连通支配集(CDS,connected dominating set)是提高WSN数据传输效率的重要技术手段.然而,现存的多数构建CDS算法只强调CDS规模,没有考虑网络的能量均衡.为此,提出了基于休眠机制和能量均衡的连通支配集(SEBCDS,sleep-and energy-balance-based connected dominating set)算法.SEBCDS算法首先选择剩余能量高和邻居节点多的节点作为支配节点,并为支配节点选择副支配节点,然后采用休眠机制,让一部分支配节点工作,另一部分支配节点休眠,降低网络能量消耗.仿真结果表明,提出的SEB-CDS算法能够降低能量消耗、延长CDS的生命周期.与TCDS算法相比,能量消耗降低了23％,CDS的生命周期提高了约31%.     

基于区域划分的连通支配集协议

针对规模较大、节点分布密集的无线传感器网络容易产生冗余数据包以及信号冲突,导致过多的节点能量消耗,加速死亡过程等问题,在深入研究现有的分布式连通支配集构造算法的基础上,提出基于区域划分的连通支配集协议——RPMPR协议.RPMPR协议中每个节点针对网络拓扑信息,对邻居节点进行区域划分,在各区域内选择中继转发节点集,并以节点的度作为选择支配节点的依据,构建覆盖全网的连通支配集.仿真实验结果表明,RPMPR协议充分考虑网络拓扑信息,显著减小连通支配集规模,同时支配节点分布更为均匀.