基于自动终止准则改进的kd-tree粒子近邻搜索研究

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0)对近邻搜索效率的影响。试验表明,ATC-kd-tree具有更高的近邻搜索效率,相较于不使用自动终止准则的kd-tree搜索效率最高提升46%,且适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过2维阿米巴虫形状的参数优化试验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率比网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。研究结果表明,ATC-kd-tree和GSCD法不仅提高了近邻搜索的效率,也为复杂运动中近邻粒子搜索问题提供了一种更为高效的解决方案,能够显著降低计算资源的消耗,进一步提升模拟的精度和效率。

A Path-Based Approach for Data Aggregation in Grid-Based Wireless Sensor Networks

Sensor nodes in a wireless sensor network （WSN） are typically powered by batteries, thus the energy is constrained. It is our design goal to efficiently utilize the energy of each sensor node to extend its lifetime, so as to prolong the lifetime of the whole WSN. In this paper, we propose a path-based data aggregation scheme （PBDAS） for grid-based wireless sensor networks. In order to extend the lifetime of a WSN, we construct a grid infrastructure by partitioning the whole sensor field into a grid of cells. Each cell has a head responsible for aggregating its own data with the data sensed by the others in the same cell and then transmitting out. In order to efficiently and rapidly transmit the data to the base station （BS）, we link each cell head to form a chain. Each cell head on the chain takes turn becoming the chain leader responsible for transmitting data to the BS. Aggregated data moves from head to head along the chain, and finally the chain leader transmits to the BS. In PBDAS, only the cell heads need to transmit data toward the BS. Therefore, the data transmissions to the BS substantially decrease. Besides, the cell heads and chain leader are designated in turn according to the energy level so that the energy depletion of nodes is evenly distributed. Simulation results show that the proposed PBDAS extends the lifetime of sensor nodes, so as to make the lifetime of the whole network longer.

Malicious Node Detection Using Confidence Level Evaluation in a Grid-Based Wireless Sensor Network

In this paper, we present a malicious node detection scheme using confidence-level evaluation in a grid-based wireless sensor network. The sensor field is divided into square grids, where sensor nodes in each grid form a cluster with a cluster head. Each cluster head maintains the confidence levels of its member nodes based on their readings and reflects them in decision-making. Two thresholds are used to distinguish between false alarms due to malicious nodes and events. In addition, the center of an event region is estimated, if necessary, to enhance the event and malicious node detection accuracy. Experimental results show that the scheme can achieve high malicious node detection accuracy without sacrificing normal sensor nodes.

Using Cellular Automata for Grid-Based Fishery Management

This report introduced new concept and technics for a grid-based fishery management system. The fishing ground was first divided into small grid of equal area, each with predefined longitudes and latitudes (both 0.033 degrees or approximately 2 × 2 nautical miles in this study). All grids were laid and formatted into a Microsoft-Excel spreadsheet system, as defined by the coastline. Individual sheets were also constructed to represent different ecological characters, serving as supporting data of the main grid-map. Including individual fishing record, water depth, wind & current vector, benthic character, etc. Cellular automata (CA) mathematics was applied for simulation studies. They were programmed on the built-in Visual BASIC langrage in EXCEL. In a three-year research project, the author was able to accomplish the following major results: 1) An EXCEL-based spreadsheet system for storage of fishing effort in each grid. Provided that data of fishing yield is also available for each grid, research model for fishery management can be constructed, leading toward solutions for total allowable catch (TAC) as well as maximum economic yield (MEY). 2) A multi-layered, 2-dimentional spread-sheet system demonstrating the distribution of relative intensity for individual grids. The system can be decked up with different ecological data for more advanced studies. 3) Estimation of the nearest distance between two special grids as well as fishing harbors. This would help in more efficient navigation management and allocation of fishing rights for the fishing vessels.

Mixed Communication Method on the Grid-based for Wireless Sensor Networks

When senors transmit their data to the sink via multi-hop communication, the sensors closer to the sink are burdened with heavy relay traffic and tend to die early. On the contrary, if all sensors transmit datas to the sink via single-hop communication, the sensors further from the sink will die much more quickly than those closer to the sink. In this paper, we first develop an analytical model to derive the optimal cluster radius. Then we propose a mixed communication method on grid-based where the sensors can transmit data to the sink in either single-hop or multi-hop. Finally, we conduct extensive experiments and show that our method outperforms LEACH and HEED in terms of network lifetime by balancing energy consumption.

A Void Avoidance Scheme for Grid-Based Multipath Routing in Underwater Wireless Sensor Networks

This work proposes a geographic routing protocol for UWSNs based on the construction of a 3D virtual grid structure, called Void-Avoidance Grid-based Multipath Position-based Routing (VA-GMPR). It consists of two main components, the multipath routing scheme and the grid-based void avoidance (GVA) mechanism for handling routing holes. The multipath routing scheme adopts node-disjoint routes from the source to the sink in order to enhance network reliability and load balancing. While the GVA mechanism handles the problem of holes in 3D virtual grid structure based on three techniques: Hole bypass, path diversion, and path backtracking. The performance evaluation of the VA-GMPR protocol was compared to a recently proposed grid-based routing protocol for UWSNs, called Energy-efficient Multipath Geographic Grid-based Routing (EMGGR). The results showed that the VA-GMPR protocol outperformed the EMGGR protocol in terms of packet delivery ratio, and end-to end-delay. However, the results also showed that the VA-GMPR protocol exhibited higher energy consumption compared to EMGGR.

Multipath Grid-Based Enabled Geographic Routing for Wireless Sensor Networks

This work proposes an efficient disjoint multipath geographic routing algorithm for dense wireless sensor networks (WSN), called Multipath Grid-based Enabled Geographic Routing (MGEGR). The proposed algorithm relies on the construction of a 2-D logical grid in the geographical region of deployment. The objective of the proposed scheme is to determine optimal or near-optimal (within a defined constant) multiple disjoint paths (multipath) from a source node to the sink, in order to enhance the reliability of the network. The determined multiple disjoint paths would be used by the source node in a round-robin way to balance the traffic across the disjoint paths, and to avoid discovered paths with cell holes. The proposed scheme limits the use of broadcasting to the process of gateway election within each cell, and the process of maintaining the table of neighbors of each gateway. Our simulation results show the effectiveness and scalability of our routing scheme with increased network size compared to on-demand routing protocols.

Improved Data Stream Clustering Method: Incorporating KD-Tree for Typicality and Eccentricity-Based Approach

Data stream clustering is integral to contemporary big data applications.However,addressing the ongoing influx of data streams efficiently and accurately remains a primary challenge in current research.This paper aims to elevate the efficiency and precision of data stream clustering,leveraging the TEDA(Typicality and Eccentricity Data Analysis)algorithm as a foundation,we introduce improvements by integrating a nearest neighbor search algorithm to enhance both the efficiency and accuracy of the algorithm.The original TEDA algorithm,grounded in the concept of“Typicality and Eccentricity Data Analytics”,represents an evolving and recursive method that requires no prior knowledge.While the algorithm autonomously creates and merges clusters as new data arrives,its efficiency is significantly hindered by the need to traverse all existing clusters upon the arrival of further data.This work presents the NS-TEDA(Neighbor Search Based Typicality and Eccentricity Data Analysis)algorithm by incorporating a KD-Tree(K-Dimensional Tree)algorithm integrated with the Scapegoat Tree.Upon arrival,this ensures that new data points interact solely with clusters in very close proximity.This significantly enhances algorithm efficiency while preventing a single data point from joining too many clusters and mitigating the merging of clusters with high overlap to some extent.We apply the NS-TEDA algorithm to several well-known datasets,comparing its performance with other data stream clustering algorithms and the original TEDA algorithm.The results demonstrate that the proposed algorithm achieves higher accuracy,and its runtime exhibits almost linear dependence on the volume of data,making it more suitable for large-scale data stream analysis research.

基于KD-Tree与DBSCAN的水电机组状态监测数据清洗方法

针对水电机组状态监测数据量逐步增大,数据质量差的问题,提出了一种基于改进K维树(K-Dimensional Tree,KD-Tree)与基于密度的空间聚类算法(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)的水电机组状态监测数据清洗方法,首先对输入数据建立KD-Tree,再使用DBSCAN在最近邻样本上扫描完成聚类,聚类结束以后会分离出噪声点,将噪声点去除即可完成对水电机组状态监测数据清洗。选取某水电站状态监测系统上导摆度数据1 088条,再以相同时间间隔插入随机数据100条,通过算例与常规DBScan、K-means、OCSVM算法对比聚类性能与时间性能,所提出的方法识别正确率最高,为97.78%,消耗时间最少,为0.007 732 s,数据清洗效果最优,并可以大幅减少计算时间。

Density Clustering Algorithm Based on KD-Tree and Voting Rules

Traditional clustering algorithms often struggle to produce satisfactory results when dealing with datasets withuneven density. Additionally, they incur substantial computational costs when applied to high-dimensional datadue to calculating similarity matrices. To alleviate these issues, we employ the KD-Tree to partition the dataset andcompute the K-nearest neighbors (KNN) density for each point, thereby avoiding the computation of similaritymatrices. Moreover, we apply the rules of voting elections, treating each data point as a voter and casting a votefor the point with the highest density among its KNN. By utilizing the vote counts of each point, we develop thestrategy for classifying noise points and potential cluster centers, allowing the algorithm to identify clusters withuneven density and complex shapes. Additionally, we define the concept of “adhesive points” between two clustersto merge adjacent clusters that have similar densities. This process helps us identify the optimal number of clustersautomatically. Experimental results indicate that our algorithm not only improves the efficiency of clustering butalso increases its accuracy.

用于ICP的近似KD-Tree搜索加速器设计及FPGA实现

为了加速迭代最近点(iterative closest point,ICP)算法中k近邻(k-nearest neighbor,KNN)搜索过程,文章根据近似K维树(K-dimensional tree,KD-Tree)数据结构,基于现场可编程门阵列(field programmable gate array,FPGA)提出一种高性能的KNN搜索加速器;分析近似KD-Tree数据结构的可行性,结果表明该数据结构能够满足ICP算法精度要求,并提高计算的并行度和性能;为了解决近似KD-Tree建树过程耗费时间长的问题,设计基于分治归并排序的具有反馈数据通路的树构建计算模块,该模块可在8.95 ms内计算出256个空间的树节点并完成树构建;为了优化点云暴力搜索过程,设计一种高吞吐率的点云搜索模块,可以在0.49 ms内完成近30000个点的最近点搜索。研究结果表明,与相关的设计相比,该文提出的硬件加速方法可以有效降低KNN搜索时间复杂度,提高算法性能。

虚拟场景的一种快速优化Kd-Tree构造方法

Kd-tree因其具有场景自适应划分、低存储消耗和快速遍历等优势成为使用最为广泛的加速结构.本文提出一种快速优化的kd-tree构造方法,该方法通过分析场景的SAH函数,将模拟退火技术使用到最优分割平面搜索过程中加快搜索过程,从而加速kd-tree的构造过程.实验表明,通过本文的方法可以在保证构造的kd-tree的质量情况下有效加快构造速度.同时,本文实现了该方法的一个多核并行扩展,利用多核CPU的并行处理能力,进一步加快了kd-tree的构造过程.

有序的KD-tree在图像特征匹配上的应用

针对用KD-tree实现高维空间点匹配中存在的错误匹配问题进行讨论,分析其存在的原因;接着,使用PCA,根据各维数之间的协方差,求出它们的主成分奉献率,再按主成分奉献率进行维数优先级排序,并在该基础上增加了KD-tree各节点的权重;最后,将改进前后的KD-tree应用于Sift特征点匹配。实验证明,改进后的KD-tree能在保持实时性的前提下,大大提高匹配的准确率。

结合K均值聚类和KD-Tree搜索的快速分形编码方法

利用部分失真搜索求解传统K均值聚类算法中的最近邻搜索问题,显著地减少了传统算法的乘法次数,从而提高了聚类速度;然后用改进后的聚类算法来加速分形编码:首先将定义域块聚类并为每个类建立一棵KD-Tree,编码时对每个值域块先后用部分失真搜索与近似最近邻搜索得到与其距离最近的若干KD-Tree及其上的若干最近邻,而其最优匹配块即由后者产生.实验结果表明,相对于全局搜索,该方法能大幅度地提高编码速度和较大地提高压缩比,而解码质量只有很小的下降;相对于同类方法,在相同压缩比下有更好的加速效果和解码质量.

基于KD-Tree搜索和SURF特征的图像匹配算法研究

针对图像匹配时进行特征检测和匹配的搜索时间长的问题,文章研究了基于KD-Tree搜索和SURF特征的图像匹配算法。该算法首先提取得到图像的SURF特征并生成特征描述向量,然后为这些特征描述向量建立KD-Tree索引,最后通过计算每个特征点的与其距离最近的若干个KD-Tree上的最近邻点,完成特征匹配工作。实验结果表明,与SIFT算法相比,SURF算法进行特征检测的速度要快2～3倍;与全局最近邻搜索相比,基于KD-Tree索引的近似最近邻搜索大大减少了计算量,较大地提高了SURF算法的匹配速度。

在游戏中利用邻域特性扩展的kd-tree及其查找算法

处理场景中数量庞大的各种对象间的交互是游戏的一类主要计算工作。将kd-tree用于组织场景,提高了这类计算的效率。传统算法采用树的层次遍历方式进行查找,处理跨节点情况时性能下降明显。提出了邻域特性概念以扩展传统kd-tree结构,增添了树节点间的平面邻接关系,且考虑了游戏对kd-tree的一些限定,设计了从起始节点向四周扩展的查找算法。经分析与实验证明,新算法比传统算法有约40%的性能提升且更稳定。

KD-Tree的并行化创建方法分析

针对KD-Tree的串行创建效率不高的问题,文中对KD-Tree创建的并行化方法进行了研究。首先通过分析串行创建的方法;结合GPU的并行特性,改进了原有方法;并对三种不同的并行化方法进行了对比,其中基于GPU构建的并行化方法既保证了稳定性和性能,又具有比较满意的时间复杂度。

基于线索KD-Tree的射线追踪并行计算

针对射线追踪过程中,由于射线数目巨大、部分目标场景复杂,造成计算效率低下的问题,采用线索KD-Tree (K-dimensional tree)空间加速算法,将目标场景进行有序组织,通过对线索KD-Tree进行无堆栈遍历,加快射线与目标场景求交的计算速度。为解决传统方法中,串行计算射线与目标求交过程中造成待遍历射线多的问题,采用图形处理器(graphics processing unit, GPU)在统一计算设备架构(compute unified device architecture, CUDA)平台下并行处理所有射线,加快计算速度。实例仿真计算结果表明,基于线索KD-Tree的射线追踪并行计算相比于串行计算,计算效率提高,获得了很好的加速效果。

kd-tree建树算法改进

kd-tree(k-dimensional tree的简称)是一种分割k维数据空间的数据结构,主要应用于多维空间特征向量的快速搜索。但是kd-tree的重要缺点是建树速度非常慢,提出一种改进的建树算法,可显著提高建树速度。

启发式探查最佳分割平面的快速KD-Tree构建方法

在基于光线跟踪方法的真实感绘制中,kd-tree是一种重要的加速结构.文章对kd-tree的构建方法进行了研究,提出了一种基于分区(binning)算法的快速构建方法.首先,通过分析kd-tree的成本函数,启发式地定位了当前节点的分割平面所在的子区间;其次,对探查到的子区间进行进一步的细化采样(sub-sampling),使得到的分割平面更好地逼近最优分割位置;同时,文章分析了现有方法在处理分割终止时存在的问题,提出了更加合理的分割终止条件.与以往方法相比,新方法用更小的计算成本生成了质量更好的kd-tree,构建过程更加鲁棒.实验数据验证了文中方法的有效性.