面向节能和容错的异构WSNs数据收集算法

采用连通支配集作为虚拟骨干可以延长无线传感器网络的生命时间,但是考虑节点容易失效的特性,网络还需要具有一定的容错性。针对k-连通m-支配集的容错方法能耗过大的问题,提出了一种面向节能和容错的分布式数据收集算法。算法首先构建连通支配集,然后选择容错度大的节点作为备份节点,最后在数据收集过程对支配节点的能耗进行均衡。理论分析和仿真实验证实算法不仅以较小的时间和消息开销构建规模较优的连通支配集,而且还保证了容错性并最终延长了网络的生命时间。     

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

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

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

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

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

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

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

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

异构无线传感器网络中基于CDS树的拓扑控制方法

拓扑控制是无线传感器网络中节约能量、延长网络生命的关键技术。针对现有拓扑控制方法主要集中在同构网络中作为拓扑构建或拓扑维护单独研究的问题,提出了包含两个过程的异构网络分布式拓扑控制算法A3M。拓扑构建基于最小连通支配集构建虚拟骨干树,在保证连通性的同时关闭网络冗余节点以降低能耗;拓扑维护对网络性能进行评估,当现有网络性能严重下降时,改变拓扑以保障网络的稳定运行。理论分析和仿真实验证实算法能够以较小的时间和消息代价减少拓扑构建能耗并延长网络时间。     

无线传感器网络(k,m)-容错连通支配集的分布式构建

采用连通支配集作为虚拟骨干可以延长无线传感器网络的生命时间,但是考虑到节点容易失效,虚拟骨干还需要具有一定的容错性。对此,针对任意k和m取值,提出了一种完全分布式的k-连通m-支配集构建算法,其中k-连通保证了网络中支配节点之间的容错性,m-支配则保证了普通节点与支配节点之间的容错性。该算法可以在异构网络中进行扩展,首先构建连通支配集,然后采用最大独立集和贪心的思想将普通节点进行m-支配,最后在局部拓扑中通过公共邻居节点将连通支配集扩展为k-连通。仿真实验证实,该算法可以通过较低的通信开销获得规模较优的k-连通m-支配集。     

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。     

异构Ad hoc网络骨干网络的建立与性能分析

目前针对虚拟骨干网的研究都是基于最小连通支配集(MCDS)的方式,其目的是最小化骨干网中的节点个数,但没有考虑到骨干节点的实际通讯能力。这样,在异构Adhoc网络中一些低性能骨干网节点可能成为整个网络的性能瓶颈。充分考虑到Adhoc网络的节点异构性问题,提出了基于高性能节点的最小连通支配集算法(MCDS-HNP),同时给出了算法的逼近度证明,并通过仿真试验表明在与MCDS算法相似的骨干节点个数的情况下,MCDS-HNP算法能获得更好的骨干网性能。     

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

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

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

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

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

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

Fast distributed dominating set based routing in large scale MANETs

Hierarchical routing techniques have long been known to increase network scalability by constructing a virtual backbone. Even though MANETs have no physical backbone, a virtual backbone can be constructed by finding a connected dominating set (CDS) in the network graph. Many centralized as well as distributed algorithms have been designed to find a CDS in a graph (network). Theoretically, any centralized algorithm can be implemented in a distributed fashion, with the tradeoff of higher protocol overhead. Because centralized approaches do not scale well and because distributed approaches are more practical especially in MANETs, we propose a fast distributed connected dominating set (FDDS) construction in MANETs. FDDS has message and time complexity of O(n) and O(Δ²), where n is the number of nodes in the network and Δ is the maximum node degree. According to our knowledge, FDDS achieves the best message and time complexity combinations among the previously suggested approaches. Moreover, FDDS constructs a reliable virtual backbone that takes into account (1) node’s limited energy, (2) node’s mobility, and (3) node’s traffic pattern. Our simulation study shows that FDDS achieves a very low network stretch. Also, when the network size is large, FDDS constructs a backbone with size smaller than other well known schemes found in the literature.     

无线传感器网络不依赖位置信息的能耗均衡拓扑控制

针对无线传感器网络(WSN)稠密部署的特点,首先提出一种不依赖位置信息的拓扑构建(LTC)算法用于构造连通支配树型结构的虚拟骨干网。在此基础上,深入分析骨干节点的能量消耗以及数据传输时延,引入密度控制与数据传输率控制因子以均衡虚拟骨干网能耗,提出了不依赖位置信息的能耗均衡拓扑控制(LETC)算法。LETC算法依据各个区域不同的数据传输量,调整该区域虚拟骨干节点的布置密度,同时增加低能耗节点的传输速率以减少网络时延。理论分析与仿真表明,经过优化的LETC算法相比LTC能够更有效地均衡能耗,延长网络寿命241%,减少时延28.1%。     

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

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

无线Ad hoc网络中干扰感知的拓扑管理

干扰问题是无线网络中的一个普遍现象。干扰影响网络总能耗、吞吐量、网络寿命等,减少干扰可以优化网络性能。同时利用连通控制集（CDS）作为虚拟骨干网也可以提高网络性能,达到简化路由、节省能量的目的。文中提出了一个干扰感知的基于优先级排序的拓扑管理算法（I-TMPO）,该算法考虑了每个节点的干扰值,同时加入速度因素为每个节点分配一个优先级。通过该算法,每个节点根据它的邻居信息决定其是否在最小控制集（MDS）中,然后将MDS中的节点连通成一个CDS。理论上证明了算法的正确性,仿真结果表明文中的算法具有更好的性能。