Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

监测无线传感器网络休眠调度算法

休眠调度设计是无线传感器网络一种重要的通信节能方法。针对监测典型应用,为了实现长时间的监测应用要求,充分利用冗余部署提供的能量资源,提出了一种能量相关的分布式自适应休眠调度算法。算法利用极大独立集构建思想,结合节点层次级别、实时的能量消耗、连通度等信息动态选择连通支配节点集作为网络骨干,使得网络活跃节点数量最小化。仿真试验分析表明,算法能够有效地利用冗余节点提供的能量资源,扩展了网络的生命周期。     

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.     

一种面向无线多媒体传感器网络的分布式图像压缩算法

因为多媒体数据的高带宽要求,要传输传感器节点采集到的原始数据将会消耗大量的资源。文章提出了一种分布式图像压缩算法,该算法通过把压缩任务分配给其他节点来解决在能量受限的节点上处理能力不足的问题。此外,该算法把压缩任务分配给其他空闲节点能很好的延长网络的生存时间。     

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

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

一种基于LEACH的无线传感器网络路由算法及仿真

在低功耗自适应分簇（LEACH,Low Energy Adaptive Clustering Hierarch）算法中,由于每一轮循环都要重新构造簇,距离较远的簇头节点可能会因长距离发送数据而过早耗尽自身能量,能量较低的节点当选为簇头节点时将会加速该节点的死亡,影响整个网络的生命周期。针对LEACH算法分簇机制中存在的不足,提出了一种改进的路由算法。仿真结果表明,改进算法通过考虑节点的剩余能量与固定分簇的方法,有效的改善了网络能量均衡,提高了网络生存时间。     

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

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

基于最小连通支配集的CRL分发系统研究

CRL(certification revocation list,证书撤销列表)分发效率是制约PKI在无线网络中应用的重要因素之一。针对无线网络节点能量有限的不足和CRL分发的实时性要求,提出了基于最小连通支配集的"推"方式分发方法,并设计了CRL广播分发协议,协议的设计包括数据结构和报文格式、广播树构造描述,并在协议基础上设计CRL分发系统,最后利用NS-2仿真平台进行模拟仿真。仿真结果表明,当合理设置定时器等待时间时,该系统不仅能适应节点较多的网络,并可以保证较好的传输率、较低的传输开销及较短的传输时间,具有一定应用价值。     

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

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

时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。     

无线传感器网络LEACH协议的研究

在无线传感器网络中,与平面路由协议相比,分簇路由协议具有一定的优势.它具有拓扑管理方便、能量利用高效.数据融合简单等优点,成为当前路由协议研究的重点.本文以低能量自适应聚类(LEACH)为例,对分簇路由协议进行了分析.在此基础上,提出改进了的LEACH ED_LEACH(Base on Energy and Di Stance factors-Low-Energy Adaptive Clustering Hierarchy),通过使用MATLAB进行了仿真,仿真结果表明ED_LEACH算法能更有效地延长网络寿命.     

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

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

Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set （IS） in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.