基于Voronoi图的无线传感器网络的节点调度机制

无线传感器网络由大量低能量、短寿命、不可靠的传感器节点组成,最小化能量消耗—延长网络寿命是一个主要的目标。对于大多数传感器应用,通过关掉网络中配置的冗余节点提供对目标区域的完全感知并降低能量消耗是一种有效的方法。据此提出了一种基于Voronoi图的节点调度算法,该算法能在保证网络覆盖范围的情况下,有效地剔除冗余节点,由此延长网络寿命。     

基于加权Voronoi图的分布式无需测距节点定位算法

针对无线传感器网络定位的精度问题,提出一种基于加权Voroni图的无需测距的分布式定位算法(weighted Voronoi diagram based localization algorithm, WVL).对待定位节点接收到的来自锚节点的信号强度(RSSI)进行从大到小的顺序排序,并将这些一跳锚节点的权值赋值为相对应的RSSI值.利用节点的一跳邻居和二跳邻居表将集中式计算转换为分布式计算,分别计算锚节点的W-Voronoi图,求这些图的交集后再取交集的质心,即可得未知节点的位置参数.通过仿真对比基于W-Voronoi图和Voronoi图,以及加权质心定位算法,仿真结果证明基于W-Voronoi图的算法精度更高.     

基于Voronoi图的无需测距的无线传感器网络节点定位算法

将Voronoi图应用于无线传感器网络定位问题中,提出了VBLS(Voronoi diagrams based localization scheme)定位算法.它首先对接收到的anchor节点的接收信号强度(RSSI)从大到小进行排序,然后利用UDG图依次计算每个anchor节点的Voronoi区域,最后将所有Voronoi区域交集的质心输出作为定位结果.通过仿真将VBLS和另外两种无需测距的定位算法(W-Centroid和Centroid)进行了比较.仿真结果表明,对于anchor节点随机摆放的情况,VBLS的定位误差比Centroid和W-Centroid分别降低了18%和13%;对于anchor节点均匀摆放的情况,VBLS的定位误差比Centroid降低了7%,比W-Centroid增加了2%.     

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

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

基于Voronoi多边形的移动目标跟踪算法

分析讨论了Voronoi多边形的特性以及在目标监测与跟踪中的应用,提出了一种基于Voronoi多边形的移动目标跟踪算法。仿真实验结果分析表明,算法的计算和通信开销小,有效地节省监测节点的能量消耗,提高移动目标的监测效能。     

基于Voronoi图的无线传感器网络栅栏覆盖算法设计

针对无线传感器网络中栅栏构建的问题,提出了一种基于监测区域Voronoi图划分的无线节点栅栏构建算法。仿真结果显示,网络中无线节点部署地越多,栅栏形成的可能性和组建栅栏的节点平均数量也会随之增加。该算法能够在无线传感器网络节点覆盖密度较低且不均,已经形成了少量栅栏空洞的情况下快速实现监测区域的栅栏覆盖,但空洞修复还需要进一步研究。     

基于区域分割和Voronoi图的区域覆盖算法

针对无线传感器网络区域已知的区域覆盖问题,提出了一种基于区域分割和Voronoi图的覆盖算法（RSV）。算法首先分析已知区域的地理信息和兴趣点,根据传感器感知能力,构造合适大小的网格将已知区域细化分割。然后基于分割后的各个区域,根据兴趣点的数量划分其为不同权重部分,并初步设计传感器位置。根据初步部署位置和权重,对不同权重位置构造Voronoi图填补覆盖空洞,直至所有空洞被填补完毕,并为了延长运行寿命设计了合适的节点休眠策略。仿真实验显示,基于区域分割和加权Voronoi图的目标区域覆盖算法相较于现有算法,在节点数量增加较少的情况下,延长了网络的运行寿命,同时使节点能量消耗更加平均,在节点数量受限情况下,算法对有效区域的覆盖效果也更佳。     

基于Voronoi图的WSN阶次序列定位算法

针对现有阶次序列定位算法复杂度高的问题,提出一种基于Voronoi图的无线传感器网络阶次序列定位算法。根据Voronoi图对定位空间进行划分,将多边形顶点和边界交汇点作为虚拟信标节点,建立虚拟信标节点到信标节点的阶次序列表。计算未知节点序列与最优序列的Kendall阶次相关系数,通过对系数的归一化处理实现未知节点位置的加权估计。仿真结果表明,与现有序列定位算法相比,该算法在保证较高定位精度的前提下降低了算法复杂度,并且未产生额外的网络成本与能耗。     

基于Voronoi图的移动空划分

随着我国航空母舰的出现,固定空域已不能满足需要,随之产生了移动空域的概念,移动空域具有相对移动性。在对管制员工作负荷和移动空域各类型限制条件研究的基础上,综合使用Voronoi图对移动平台周边的空域进行划分,形成相对于平台划分的空域。根据类型,移动空域可分为禁止区、危险区、限制区和责任区。充分利用Voronoi图的简易性,在此基础上重新构造移动空域划分算法,并给出仿真实验结果,验证了该算法在移动空域划分中的可行性,通过比较给出了传统算法的不足。     

基于Voronoi和空间自相关的离群点检测

为了提高空间数据挖掘的效率和准确度,在分析传统的离群点检测算法优、缺点的基础上,提出一种空间离群点检测算法。用Voronoi来确定空间对象间的邻近关系,在空间邻域内利用空间自相关性来计算局部Moran指数,并将其作为离群因子进而判断离群点。实验结果表明,该算法能够高效、准确地检测出空间离群点,具有对用户依赖性少和可伸缩性强等优点。     

一种基于局部Voronoi图的目标穿越算法

许多传感器节点被布置在感兴趣的区域,以监控任何可能出现的目标;另一方面,智能目标搜索最佳路径穿越监控区域,以免被监测到.关注目标如何穿越被监控区域的问题,建立穿越问题模型,基于局部Voronoi图设计并实现了一系列路径搜索方法,并对其进行了详细分析与比较.其特色在于假设目标仅能探测到部分布置的传感器节点,并基于此局部信息实现穿越,这使得所提出的方法更加有效并符合客观实际.实验结果验证了该方法的可行性和适用性.     

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

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

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

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

传感器网络基于Voronoi 网格的数据压缩算法

提出了一种传感器网络中分布式多分辨率数据压缩算法.在分布式域剖分模型DDPM(distributed domain partition model)基础上,提出了一种多分辨率的数据压缩模型MDCM(multiscale data compress model),DDPM 把传感器网络按域划分来构建连通核,传感节点只需在连通核中寻径,因而能够明显减少寻径时间复杂度并且具有更好的分布性;MDCM 利用Voronoi 网格来对DDPM所形成的域中的节点进行划分,然后采用多分辨率方法构建数据压缩模型.理论分析和实验仿真结果表明,MDCM 具有很好的逼近性能,并且能够对传感器网络中的数据进行有效压缩,可以更大程度地降低传感器网络中的数据传输量.     

道路网络上基于网络Voronoi图的隐私保护算法

基于位置服务(location-based services, LBSs)中的不可信服务提供商不断收集用户个人数据,为用户隐私带来威胁.因此,LBSs中的位置隐私保护研究已在学术界和工业界受到广泛关注.现有道路网络中的位置隐私保护方法大多是基于深度或广度图遍历的算法,需重复扫描道路网络的全局拓扑信息,匿名效率较低.针对这一问题,利用网络Voronoi图(network Voronoi diagram, NVD)将道路网络事先划分为独立的网络Voronoi单元,将传统方法中的多次遍历全局道路网络转化为了访问网络Voronoi单元中的局部路网信息.根据网络Voronoi单元覆盖的移动用户数和路段数,将网络Voronoi单元分为了不安全单元、安全-中单元和安全-大单元3类,提出了适应不同类型网络Voronoi单元特点的高效位置匿名算法.最后,通过在真实数据集上进行大量实验,验证了提出算法在仅比传统算法多牺牲0.01%的查询代价的前提下,保证了100%的匿名成功率和0.34ms的高效匿名时间,在隐私保护强度和算法性能方面取得了较好的平衡.     

基于Voronoi图的异常检测算法

异常检测是数据挖掘的一个重要组成部分,其中基于密度的方法LOF是目前常用的主要方法。然而LOF方法进行检测时需要设定参数k和MinPts,检测结果对参数非常敏感,容易造成检测错误。该文提出了一种基于Voronoi图的异常检测算法VOD,采用Voronoi图来确定对象间的邻近关系,解决了基于密度方法存在的问题,算法的时间复杂性从O(N2)降低到O(NlogN)。