基于Voronoi覆盖的邻居信息的重建研究

对于随机部署的大规模无线传感器网络,在保证目标区域完全覆盖的情况下,可以使部分冗余节点进入休眠状态,进而降低能耗.首先介绍了一种分布式的基于2-Voronoi图的冗余节点判别方法,并根据冗余依赖图使部分节点进入休眠状态.然后着重对网络正常工作后出现新增节点和部分节点失效的两种情况分别提出了两个相应的算法,以此来完成因新增节点或部分节点失效而受影响的节点的Voronoi邻居信息重建工作,并对这两个算法的有效性就行了分析.     

基于能耗均衡的WSN连通覆盖集构建算法

为提高无线传感器网络的能量利用率,提出一种基于能耗均衡的连通覆盖集构建算法EBACCS。该算法以概率覆盖模型为基础,采用Voronoi图划分目标区域,获得网络冗余节点,根据能量权值函数,从冗余节点中选出必要的连接节点建立一个优化的连通覆盖集。理论分析和仿真实验结果表明,EBACCS能够保证网络的连通性与覆盖性,均衡节点能耗,延长网络寿命。     

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

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

WSNs中基于Voronoi图的分布式覆盖协议

研究网络随机部署情况下的覆盖问题,提出基于Voronoi图的分布式覆盖协议。采用分布式节点冗余判断算法来判断传感器节点自身的冗余性,据此对节点进行相应的职能调度。当网络中节点的通信半径大于或等于其感应半径的2倍时,该协议能达到网络完全覆盖及连通的要求。通过该协议的推广,满足了覆盖度动态变化的要求,保证网络的k-度覆盖。     

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

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

无线传感器网络最小覆盖能量优化算法

在无线传感器网络中,位于基站周围的节点由于负责所有探测数据的转发任务而能量消耗水平较高。为了均衡基站周围节点的能量消耗,提出一种合理有效的节点轮换休眠机制。使得网络中大量冗余节点处于休眠状态,从而减少基站周围重要节点的负载。基于这种想法提出了冗余节点判定定理,基于Voronoi图寻找最大可休眠节点集,设计了最小连通覆盖算法（FBSW）寻找网络中可休眠的冗余节点,有效地延长网络的生命周期。仿真结果证明,该算法的运行复杂度优于贪婪算法,由于冗余节点轮换休眠,整个网络的能量节约了20.01%以上。     

基于Voronoi图的无线传感器网络覆盖空洞检测算法

针对无线传感器网络(WSN)中节点随机部署或部分节点能量耗尽带来的覆盖空洞(CH)问题,提出了一种基于Voronoi图的覆盖空洞检测算法。该算法利用节点的位置信息在覆盖区域范围内构建Voronoi图,通过计算每个Voronoi区域内的节点到该区域的顶点和边的距离来判断是否存在覆盖空洞,标识覆盖空洞的边界节点。仿真实验评估了不同节点分布密度、不同感知半径对空洞平均检测时间、平均能耗的影响,并与路径密度(PD)算法进行比较。实验结果表明所提算法在空洞平均检测时间和节点平均能耗两个方面均有10%左右的提升,对进一步延长网络生存期具有重要价值。     

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

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

基于Voronoi图的蜂群优化算法在WSN覆盖中的应用

包含移动节点的混合网络成为无线传感器网络发展的主流.为了优化混合无线传感器网络的部署质量,提高部署效率,提出一种基于Voronoi图的蜂群优化算法来指导移动节点的部署.通过Voronoi多边形迅速找到固定节点部署的覆盖漏洞,指导引领蜂的生成,利于迅速定位全区域覆盖漏洞;通过评价漏洞大小代替轮盘赌选择方式来实现跟随蜂的开采过程,利于局部优化.仿真结果表明,该算法简便易实现,能够迅速收敛,提高网络覆盖率,达到混合网络的最优覆盖效果.     

无线传感器网络MM模式随机覆盖控制模型研究

在传感器节点随机、高密度部署的环境中,覆盖控制算法可以有效降低能耗和减少冗余数据。无线传感器网络MM（MIN NODES-MAX COVERAGE）模式随机覆盖控制算法采用最少节点最大覆盖率策略,在节点呈泊松分布的网络模型中,根据不同的区域覆盖率,采用区域局部节点覆盖率计算方式,在通信半径和感知半径不同情况下,充分考虑节点复杂重叠对覆盖率的影响,适当允许主动覆盖空洞的出现,使得最少节点仍然可以达到非常接近设置的覆盖率。仿真表明算法可以最大化面积覆盖,有效降低网络能耗。     

Promoting Heterogeneity, Mobility, and Energy-Aware Voronoi Diagram in Wireless Sensor Networks

We prove that the energy sink-hole problem can be solved provided that sensors adjust their communication ranges so they can send data over distances less than the radii of their nominal communication range. This solution, however, imposes a severe restriction on the size of a monitored field. To overcome this limitation, we propose a sensor deployment strategy based on energy heterogeneity with a goal that all sensors deplete their energy simultaneously. Our simulation results show that such a sensor deployment strategy helps all sensors deplete their initial energy at the same time. To solve the energy sink-hole problem for homogeneous WSNs, however, where all sensors have the same initial energy, we propose a localized energy-aware Voronoi diagram-based data forwarding (EVEN) protocol. EVEN combines sink mobility with a new concept, called energy-aware Voronoi diagram whose virtual sites (i.e., virtual sensors' locations) are computed based on the remaining energy of the corresponding sensors. Through simulations, we show that EVEN outperforms similar greedy geographical data forwarding protocols and has performance that is comparable to that of an existing data collection protocol that uses a joint mobility and routing strategy. Precisely, we find that EVEN yields an improvement of more than in terms of network lifetime.     

Hadoop下面元加权Voronoi图并行算法及应用

面元加权Voronoi图是生成元为面元的加权Voronoi图。针对大规模数据情况下面元加权Voronoi图存在的计算效率不高问题,结合面元边界点提取方法,提出一种基于Hadoop云平台的面元加权Voronoi图的并行生成算法,进行了单机和集群实验。实验结果表明,算法能有效处理大规模栅格数据,明显提高面元加权Voronoi图的生成速度。还可应用于城市绿地设计规划,为绿地设计提供决策依据。     

Euclidean Voronoi diagram of 3D balls and its computation via tracing edges

Despite its important applications in various disciplines in science and engineering, the Euclidean Voronoi diagram for spheres, also known as an additively weighted Voronoi diagram, in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute the Euclidean Voronoi diagram for 3D spheres with different radii. The presented algorithm follows Voronoi edges one by one until the construction is completed in O(mn) time in the worst-case, where m is the number of edges in the Voronoi diagram and n is the number of spherical balls. As building blocks, we show that Voronoi edges are conics that can be precisely represented as rational quadratic Bézier curves. We also discuss how to conveniently represent and process Voronoi faces which are hyperboloids of two sheets.     

基于维诺图和二分图的水面移动基站路径规划方法

水面传感器网络（Surface sensor networks,SSNs）具有节点稀疏布置的特点（节点间距离通常大于节点通信半径）,因此难以通过节点间的多跳路由汇聚数据,目前主要采用移动基站（Mobile sink,MS）收集网络中的数据,其中移动基站的路径规划是一个关键问题.该文提出一种基于维诺图和二分图的水面移动基站路径规划方法,首先利用维诺图理论生成数据收集“候选点”;然后以二分图描述候选点对网络中传感器节点的支配关系,并基于支配集理论求解出“最小有效支配集”,即可以收集网络中所有节点数据的最小的候选点集合;最后针对最小有效支配集形成最优路径.大量实验结果表明该方法可以有效地规划出水面传感器网络中移动基站的路径,不仅可以完成全网数据收集任务,而且具有路径长度短、能量效率高和节点能耗均衡的优点.     

Voronoi图在无线传感器网络栅栏覆盖中的应用研究*

Voronoi是计算几何学中的一个重要图结构,将其引入到无线传感器网络的覆盖控制中,特别是栅栏覆盖(barrier coverage)的研究中有着极其重要的指导意义.利用Voronoi图的划分,可快速搜索出传感器网络中的覆盖漏洞,在仅考虑邻近传感器节点影响的宽松覆盖要求下,论证出利用该图生成的最小暴露进攻轨迹逼近于理想情况;但由于Voronoi的划分仅仅是一种粗略的轨迹线段的集合,会造成该方法对网络拓扑情况相当敏感,这将一定程度上限制其应用范围.     

基于Voronoi图的无线传感网休眠算法

针对无线传感网络的节点是高密度随机分布在部署区域可能产生重复覆盖而浪费节点和网络整体能量的问题,改进了一种基于Voronoi图的休眠算法。通过计算节点与其邻居节点和其产生的Voronoi图顶点的距离来判断该休眠节点,减少网络的整体能量消耗。仿真结果表明,所改进的休眠算法节约了网络的整体能量,延长了网络的生命周期。     

Region-expansion for the Voronoi diagram of 3D spheres

Given a set of spheres in 3D, constructing its Voronoi diagram in Euclidean distance metric is not easy at all even though many mathematical properties of its structure are known. This Voronoi diagram has been known for many important applications from science and engineering. In this paper, we characterize the Voronoi diagram of spheres in three-dimensional Euclidean space, which is also known as an additively weighted Voronoi diagram, and propose an algorithm to construct the diagram. Starting with the ordinary Voronoi diagram of the centers of the spheres, the proposed region-expansion algorithm constructs the desired diagram by expanding the Voronoi region of each sphere, one after another. We also show that the whole Voronoi diagram of n spheres can be constructed in O(n³) time in the worst case.     

A provably complete exploration strategy by constructing Voronoi diagrams

We present novel exploration algorithms that enable the construction of Voronoi diagrams over unknown areas using a vehicle equipped with range sensors. The underlying control law uses range measurements to make the vehicle track Voronoi edges between obstacles. The exploration algorithms make decisions at vertices in the Voronoi diagram to expand the explored area until a complete Voronoi diagram is constructed in finite time. Our exploration algorithms are provably complete, and the convergence of the control law is guaranteed. Simulations and experimental results are provided to demonstrate the effectiveness of both the control law and the exploration algorithms.     

带线段障碍的城市Voronoi图生成算法研究

带线段障碍的城市Voronoi图是城市Voronoi图的扩展.在步行或使用一般交通工具的情况下,客观世界中存在着许多不能逾越的障碍,甚至连交通网络也时常被一些障碍隔开.许多障碍可简化为线段障碍来处理.给出带线段障碍的城市Voronoi图的定义、性质,结晶生长算法和实例.算法简单,可扩展性好,具有较高的理论价值和应用价值.     

圆柱面和锥面上数据集的最近邻查询方法

为处理圆柱面和圆锥面上数据集的最近邻查询问题,提出利用Voronoi图进行查询和曲面转换2种解决方法。在圆柱面和锥面上构造Voronoi图,利用Vornoi图进行查询处理。将圆柱面和锥面转换映射为二维有界平面,给出转换规则和查询算法。对2种方法进行实验分析,结果表明,利用Voronoi图的方法适合静态数据集的最近邻查询,曲面转换方法对动态数据集的最近邻查询更有效。