基于蜂窝结构的传感器网络覆盖问题求解算法

在无线传感器网络中,求解能够完全覆盖目标区域的最小覆盖集是个NP难问题.在传感器节点数目较多时,目前只能通过近似算法求解.蜂窝结构是覆盖二维平面的最佳拓扑结构,但不能直接用于求解无线传感器网络的覆盖问题.提出了一种基于蜂窝结构的覆盖问题求解算法,在该算法迭代求解过程的每一阶段,选出一个节点加入到初始为空的节点集合中,并使得该节点集合的拓扑结构接近于蜂窝结构,直至该节点集合成为覆盖集.该算法在最坏情况下的时间复杂度为O(n3),这里n为传感器节点总数.实验结果表明该算法可在很短的时间内执行完,在所得覆盖集的大小方面要优于现有的覆盖问题求解算法.     

基于Voronoi图的无线传感器网络K覆盖算法

针对无线传感器网络(WSN)在随机高密度部署节点情况下的多重覆盖问题,提出一个基于Voronoi图的K覆盖算法。该算法利用邻居节点信息计算Voronoi覆盖邻居节点集,构建有向Voronoi覆盖关系图,通过调整关系图中的节点状态实现K覆盖。仿真结果表明,该算法能正确判断网络覆盖率,连通K覆盖的近似最小活动节点集数目少于CCP算法。     

无线传感器网络中的分布式平面t-支撑拓扑控制算法

在确保无线传感器网络连通的前提下,每个节点自适应地调整自己的发射功率,通过最小化节点的能耗和减少节点间的通信干扰,达到延长网络生存时间的目的.基于 Voronoi划分和局部Delaunay三角剖分,提出一种新的几何结构PSLDel图(planar symmetric local Delaunay triangulation)以及其分布式构造算法,为无线传感器网络建立连通、稀疏、平面、t-支撑的底层逻辑拓扑,每个节点将依据最远的逻辑邻居调整到最小发射功率.仿真实验表明,PSLDel图在逻辑邻居、最小发射功率和通信干扰等性能方面接近集中式构造的UDel图,而且PSLDel图的网络延迟稍微优于 UDel图;与分布式构造的AUDel图相比,PSLDel图的通信开销至少可以降低55%,从而有利于提高无线传感器网络的能量使用效率.     

Ad Hoc网络区域最小覆盖方法研究

覆盖控制作为无线传感器网络中的一个基本问题,反映了网络所能提供的“感知”服务质量,可以使无线传感器网络的空间资源得到优化分配,进而更好地完成环境感知、信息获取和有效传输的任务.如何计算同时满足“覆盖要求”（工作节点必须能够完全覆盖目标区域）和“连通性要求”（工作节点组成的通信网络必须是连通的）的最小节点集合,是一个NP难问题.本文设计了一种基于目标区域Voronoi划分的改进集中式近似算法,用于计算完全覆盖目标区域所需要的近似最小节点集.     

基于图论的无线传感器网络自组织性能研究

无线传感器网络自组织问题越来越受到人们的关注,控制方法也大量涌现,但在对自组织性能的评价上,现在大多仍停留在定性分析阶段。本文针对无线传感器网络自组织中连接和覆盖两个重要指标,利用Delaunay三角剖分评价节点实体和他们的关系以及结点之间的信息传递和融合;利用Voronoi图进行评价节点覆盖的区域;同时,对整个自组织过程,引用自组织度的概念对其分布效果进行定量分析。仿真结果表明,我们提出的性能分析方法能够很好地评价无线传感器网络自组织算法的优劣。     

无线传感器网络中基于Voronoi图的覆盖和连通综合配置协议

着重研究无线传感器网络随机部署下的覆盖和连通问题的解决方案,尤其是当无线传感器节点的通信半径Rc与感应半径Rs之比小于2时的解决方案.本文提出了无线传感器网络中一个基于Voronoi图的覆盖和连通的综合配置协议(VIP).该协议采用了一种分布式节点冗余判断算法以判断无线传感器网络中节点的冗余性,并让节点据此来对自身进行相应的职能调度.该协议能够在Rc/Rs为任意值时保证网络的覆盖和连通性能.本文还将该协议进行了推广,使得该协议能够满足覆盖度和连通度动态变化的要求,保证网络的k-度覆盖和k-度连通.     

基于Delaunay三角划分策略的WSN区域覆盖优化研究

针对无线传感器网络在对初次抛洒节点形成的覆盖漏洞进行二次部署的过程中,传统几何学方法难以运用于概率感知模型的问题,提出一种基于Delaunay三角划分策略的无线传感器网络区域覆盖优化算法——DPSO算法。首先对监测区域内随机抛洒的静态节点和监测区域边缘顶点进行Delaunay三角划分,以得到静态节点三角网,结合无线传感器网络节点的概率感知模型证明三角形内部存在完全未覆盖区域即覆盖漏洞;其次将通过筛选得到的三角形形心集合作为粒子群优化算法的初始解集,利用改进的粒子群优化算法完成对移动节点的二次部署,以达到修复覆盖漏洞的目的。实验表明,所提出的基于Delaunay三角划分策略的优化算法能够有效修复覆盖漏洞,使区域覆盖率得到显著提高。     

基于遗传算法的无线传感器网络巡航覆盖最小移动节点数研究

被监测环境的状态可以使用无线传感器网络的有效感知.本文使用无线传感器网络巡航覆盖模型实现了建筑能效监测过程.为降低基于无线传感器网络巡航覆盖模型的数据采集系统构造和维护成本并降低系统复杂度,采用MTSP问题对无线感器网络巡航覆盖最小移动节点数问题建模,提出了无线感器网络巡航覆盖最小移动节点数快速求解算法并使用遗传算法实现了快速求解算法.实验结果表明,本文提出的方法快速有效,而基于遗传算法的快速求解算法的实现可以快速确定无线感器网络巡航覆盖最小移动节点数上界.     

无线传感器网络最小连通覆盖集问题求解算法

降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.     

异构无线传感器网络中异构节点的部署与优化

在无线传感器网络中适当地部署少量的异构传感器节点能够有效地延长网络寿命,提高网络的可靠性.本文主要研究无线传感器网络中异构节点的部署问题,提出了基于选址问题的异构节点部署算法,以优化无线传感器网络中异构节点的数量和位置.与其它算法相比,该算法对无线传感器网络的拓扑结构没有特定的要求,可以支持随机部署或人工部署的各种传感器网络,最后还给出了该算法的仿真测试结果.     

无线传感器网络中基于伸展树的感知节点分布优化

In a sensor network, reasonable distribution of sensor nodes will do much good to the improvement of sensorial ability. In a sensor network constructed by randomly scattering, a better sensing coverage can be achieved by topology adjustment utilizing mobility of some sensor nodes. To solve this problem, we define an extending-tree in the sensor network using Voronoi diagrams and Delaunay network. On this base, a new optimization algorithm of sensor node distribution based on genetic algorithm is designed, which provides a sound effective means to improve the sensorial ability of network. Simulation output shows that this algorithm can achieve an optimizing node distribution in the object area, by which sensorial ability of the whole sensor network can be improved at a relatively low cost.     

Sensor Distribution Optimization Based on Extending-tree in Sensor Network

In a sensor network,reasonable distribution of sensor nodes will do much good to the improvement of sensorial ability.In a sensor network constructed by randomly scattering,a better sensing coverage can be achieved by topology adjustment utilizing mobility of some sensor nodes.To solve this problem,we define an extending-tree in the sensor network using Voronoi diagrams and Delaunay network.On this base,a new optimization algorithm of sensor node distribution based on genetic algorithm is designed,which provides a sound effective means to improve the sensorial ability of network.Simulation output shows that this algorithm can achieve an optimizing node distribution in the object area,by which sensorial ability of the whole sensor network can be improved at a relatively low cost.     

A novel gossip-based sensing coverage algorithm for dense wireless sensor networks

Wireless sensor networks (WSNs) have been widely studied and usefully employed in many applications such as monitoring environments and embedded systems. WSNs consist of many nodes spread randomly over a wide area; therefore, the sensing regions of different nodes may overlap partially. This is called the “sensing coverage problem”. In this paper, we define a maximum sensing coverage region (MSCR) problem and present a novel gossip-based sensing-coverage-aware algorithm to solve the problem. In the algorithm, sensor nodes gossip with their neighbors about their sensing coverage region. In this way, nodes decide locally to forward packets (as an active node) or to disregard packets (as a sleeping or redundant node). Being sensing-coverage-aware, the redundant node can cut back on its activities whenever its sensing region is k-covered by enough neighbors. With the distributed and low-overhead traffic benefits of gossip, we spread energy consumption to different sensor nodes, achieve maximum sensing coverage with minimal energy consumption in each individual sensor node, and prolong the whole network lifetime. We apply our algorithm to improve LEACH, a clustering routing protocol for WSNs, and develop a simulation to evaluate the performance of the algorithm.     

WSN中基于可调感知半径的节点睡眠算法

讨论在无线传感器网络中节点的感知半径可调的情况下,如何合理设计节点的拓扑结构,实现网络的能量负载均衡、延长网络的生存周期。在保证覆盖和连通的前提下,分析当感知半径可调时节点的分布特征和拓扑结构,并对现有的冗余节点移除算法进行改进,提出一种自适应调节感知半径冗余节点睡眠算法(AASRS)。实验结果表明,该算法可以提高网络的能量负载均衡水平,并能最大化节点的感知覆盖区域,且使用的活动节点较少。     

无线传感器网络中能耗均衡的覆盖控制算法

覆盖控制作为无线传感器网络的一个基本问题,对网络的生存时间、部署策略、通信协议和组网等问题的解决具有重要影响。在传感器节点随机冗余部署方式下,传统的方式 是在保证覆盖要求和通信连通的前提下仅将最少量的节点投入活跃工作状态,从而降低网络能耗。但是,若频繁地激活同一批节点,会造成这些节点由于能耗过快而较早失效效,使整个网络的冗余程度降低。然而,冗余度是传感器网络在单个节点性能有限的情况下提高整个网络的可靠性、容错性、精确性等的基础。为此,本文提出了一个能耗均衡ECB的覆盖问题,指出它是NP完全的,并给出了一个集中式近似算法。该算法根据节点的剩余能量赋于每个节点非负权,再基于Voronoi划分和贪心边方法,在保证覆盖要求的同时选择权和最小的节点激活。仿真实验结果表明,ECB算法求得的活跃节点集小,可以达到有效覆盖,并且可以保持网络的冗余度。     

无线传感器网络的任意覆盖率节点配置

研究了任意覆盖率下的无线传感器网络分布式节点自动配置问题. 首先, 针对正六边形拓扑架构下的网络覆盖, 给出了节点密集分布条件下的覆盖率与相邻工作节点间距的解析关系, 从而得到了理想条件下部分覆盖的最优节点配置. 考虑到实际系统中有限的节点密度和节点的随机分布, 进一步提出了一种可以在此条件下实现任意覆盖率的部分覆盖协同优化算法(Optimized collaborative partial coverage, OCPC). OCPC通过节点间的动态协同唤醒最接近于理想配置的工作节点并使其他节点睡眠以节省能量. 以尽可能少的工作节点达到网络的覆盖和连通需求并降低网络的能耗, 进而达到网络的感知任务和能量消耗的有效折衷. 仿真表明, OCPC可以有效地实现任意期望覆盖率下的网络配置并保持网络连通, 同时, 与经典覆盖算法PEAS (Probing environment and adaptive sleeping)和OGDC (Optimal geographic density control)相比, 在网络的节能方面也具有明显的优越性.     

基于斯坦纳树和泰森多边形的连通恢复算法

针对无线传感器网络容易遭受恶劣环境破坏,连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法（CRAST）。首先,将被分割的节点分区抽象为离散点,枚举出离散点区域内的所有非退化四边形,再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。然后,用关键节点构建Delaunay三角网,通过Delaunay三角网构建出整个无线传感器网络的泰森多边形拓扑结构。最后,在泰森多边形所有顶点部署可移动的备用中继节点,在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点,移动备用中继节点替换损坏的关键节点。整个算法能使传感器网络以最少的代价实现连通恢复,并且拥有较强的高效性和健壮性。     

随机异构传感器网络中基于虚拟节点的调度算法

针对随机异构传感器网络节点调度过程中覆盖率和能耗的平衡问题,论文面向具有随机异构属性的无线传感器网络,提出了一种基于虚拟节点的调度算法(SAVSH)。通过部署虚拟节点,与原网络拓扑共同构建Delaunary三角剖分,分配节点受力来源。利用三角形平衡点实现网络整体的覆盖优化;通过三角形关键点完成节点位置的精确定位;引入二进制编码,完成对越界关键点的识别,及其对边界节点的约束受力设计。仿真结果表明,SAVSH在稳定的短移动距离下,能够高效地提高异构网络的覆盖率,且与同类算法相比,SAVSH在收敛速度上表现出一定优势。