无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.     

连通支配集算法及其改进

无线传感器网络中通常利用连通支配集以形成虚拟骨干网进行分层次的路由.分析现有的几种去冗余分布式连通支配集构造算法,针对它们冗余度大,计算复杂,提出了一种改进的连通支配集构造算法,利用节点的度以及编号构成的集合取代节点编号作为节点的权值,采用DRN算法的节点覆盖思想,并扩展为当遇到闭合环路的情况下,采用保留闭合环路中权值大的节点去冗余的方法,在保证整个网络连通的情况下减少了连通支配集节点的总数.最后通过Matlab仿真分析,证明了算法的有效性.     

一种改进的基于连通支配集的P2P搜索算法

为了避免由洪泛搜索方法引起的大量网络流量问题．基于连通支配集的广播算法BCDS通过减少转发节点来减少查询消息数。文章对BCDS算法进行改进，选择转发节点时考虑节点间的距离．简化选择转发节点的操作，且不用维持局部两跳拓扑信息。实验结果表明当搜索结果相同时，改进的BCDS算法的消息数量平均仅为洪泛搜索方法的35％。     

基于定向扩散的最小连通支配集构造算法

针对区域覆盖算法未考虑节点的通信梯度问题,利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列,提出了一种基于定向扩散的最小连通支配集构造算法.在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集,然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来,最终得到一个近似的最小连通支配集.理论及仿真实验结果表明,该算法构造的连通支配集最小且计算耗时少,能多重有效覆盖热点区域,从而延长无线传感器网络的寿命.     

WSNs中基于能量代价的最小权和支配集拓扑控制算法

该文针对无线传感器网络中最小连通支配集拓扑并非网络耗能最小拓扑的问题,定义由节点剩余能量,邻居个数和通信代价构建的能量代价函数综合反映支配节点的能量效率以及对降低网络整体能耗的贡献,进而以其作为拓扑权值,提出一种基于能量代价的最小权和连通支配集拓扑控制算法。算法选取局部最小权值节点担负支配任务,搭建整体权和最小的支配集,最小化网络整体能耗。实验结果表明,算法不仅具有节能的特点,还确保了通信链路的可靠性,有效延长了网络生命周期。     

无线传感器网络中最小化能量广播算法

在无线传感器网络广播中,为保证所有节点都接收到广播的数据包并调节节点功率以最小化广播总能耗,在Cartigny等人提出的面向相对邻图的广播算法RBOP(relative neighborhood graph broadcast oriented protocol)的基础上,提出了更为节能的增强的面向相对邻图的广播算法ERBOP(enhanced relative neighborhood graph broadcast oriented protocol)。首先在相对邻图上删除较长边得到相对邻图的子图,该子图是连通稀疏图且包含了原图的最小生成树,然后在该子图上构造1-支配的连通支配集,只有支配点才参与数据包转发。仿真显示ERBOP有效节约了能量。     

一种基于传感器网络的DRN改进算法

介绍了连通支配集的基本概念,提出了一种改进型分布式连通支配集DRN算法。该算法可在一个节点u的N1（u）不能直接连通、但能通过一个编号比节点u大的节点连通时去除节点u的冗余,因而具有保留编号大的节点的支配集性质,可在不增加支配集节点数和通信开销的基础上,减少支配集节点的尺寸并保证网络的连通性。     

基于UCDS的战术网络拓扑构建研究

在战术MANET中,底层通信的拓扑结构是不断变化的。寻找最小连通子图(作为一个网络拓扑结构的主干)是在MANET的MAC层设计中网络拓扑构建的有效方法。在战术网络环境下研究用于广播的连通支配集构建算法,阐述了一种分布式的连通支配集算法(UCDS),该算法采用启发式规则选取支配节点及其连接节点。通过与其他相关研究对比分析,表明UCDS具有实施简单、执行速度快、消息复杂度低的特点,同时具备一定的灵活和抗毁能力,并能够实际应用于路由优化和低速率下节点的移动自适应。     

基于最小连通支配集的无线传感网拓扑构建研究

基于通信虚拟主干网的拓扑构建是关闭冗余节点,节省全网能耗的有效方法。该文将全连通网络环境下寻找最优虚拟主干网问题抽象转化成最小连通支配集求解问题(MCDS),并建立了基于混合整数规划的数学模型(NMIP-MCDS)。NMIP-MCDS在分析MCDS解的基础上,确定以令牌分发数与节点能耗乘积为目标的优化函数,通过令牌分发同时辅以全网能量负载均衡的方式,构建最优MCDS。仿真实验结果验证了NMIP-MCDS的有效性,并可进一步实际应用在中等规模的无线传感网中。     

用马尔科夫模型优化分布式最小连通支配集算法

 为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.     

基于图着色的无线自组网极小连通支配集算法

基于连通支配集算法的虚拟主干网技术对于无线自组网的路由优化、能量保护和资源分配都具有重要的作用。通过引入极大独立集和极小支配集概念,基于图着色思想提出一种新的适合于无线自组网的极小连通支配集算法,从理论上证明了该算法的正确性和高效性,也通过仿真实验分析了该算法在多种情况下的实际性能,仿真结果表明新算法在簇头和主干节点数目方面具有较好的性能,特别在节点密集的网络环境中更加突出。     

基于极大权的最小连通支配集启发式算法

Ad hoc无线网络中基于最小连通支配集(MCDS)的路由是一个引人瞩目的方法,文中提出了一种基于极大权的MCDS的启发式算法,确保了性能强的主机担任网关节点的角色,能更好的协调管理网络中其他的节点,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础.仿真结果表明,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性,因此能有效地用于基于MCDS的路由设计中.     

基于连通支配集的无线传感网Top-k查询最优支撑树研究

构建底层逻辑树能有效降低集中式top-k查询带来的巨大通信开销,针对现有逻辑树都以固定汇聚节点为根节点,导致其附近节点能耗太大、过早死亡的问题,本文在无固定汇聚节点的网络背景下,基于连通支配集,提出一种能耗均衡的top-k查询最优支撑树构建方法,综合节点能量、度数以及与邻节点通信开销,选取能量代价小的作为支配节点负责查询中间数据处理,在每次查询中,节点基于地理位置ID轮流作为根节点,有效均衡节点的能耗.仿真实验表明,与其他逻辑拓扑树相比,基于最优支撑树的top-k查询具有相近的查询时间,但其平均每轮查询能耗更小,多次查询后各节点能耗达到均衡,有效延长了网络生命周期.     

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.     

A distributed battery recovery aware topology control algorithm for wireless sensor networks

Battery recovery effect is a phenomenon that the available capacity of a battery could increase if the battery can sleep for a certain period of time since its last discharging. Accordingly, the battery can work for a longer time when it takes some rests between consecutive discharging processes than when it works all the time. However, this effect has not been considered in the design of energy‐efficient topology control algorithms for wireless sensor networks. In this paper, we propose a distributed battery recovery effect aware connected dominating set constructing algorithm (BRE‐CDS) for wireless sensor networks. In BRE‐CDS, each network node periodically decides to join the connected dominating set or not. Nodes that have slept in the preceding round have priority to join the connected dominating set in the current round while nodes that have worked in the preceding round are encouraged to take sleep in the current round for battery recovery. Detailed algorithm design is presented. The computational complexity of BRE‐CDS is deduced to be O(D²), where D is node degree. Simulation results show that BRE‐CDS can significantly prolong the network lifetime as compared with existing work. Copyright © 2016 John Wiley & Sons, Ltd.     

A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks

Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, we propose a simple and efficient distributed algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by their geographical distances. We also propose an update/recalculation algorithm for the connected dominating set when the topology of the ad hoc wireless network changes dynamically. Our simulation results show that the proposed approach outperforms a classical algorithm in terms of finding a small connected dominating set and doing so quickly. Our approach can be potentially used in designing efficient routing algorithms based on a connected dominating set.     

Weighted Steiner Connected Dominating Set and its Application to Multicast Routing in Wireless MANETs

In this paper, we first propose three centralized learning automata-based heuristic algorithms for approximating a near optimal solution to the minimum weight Steiner connected dominating set (WSCDS) problem. Finding the Steiner connected dominating set of the network graph is a promising approach for multicast routing in wireless ad-hoc networks. Therefore, we present a distributed implementation of the last approximation algorithm proposed in this paper (Algorithm III) for multicast routing in wireless mobile ad-hoc networks. The proposed WSCDS algorithms are compared with the well-known existing algorithms and the obtained results show that Algorithm III outperforms the others both in terms of the dominating set size and running time. Our simulation experiments also show the superiority of the proposed multicast routing algorithm over the best previous methods in terms of the packet delivery ratio, multicast route lifetime, and end-to-end delay.