【作者】 邱萌；

【导师】 徐惠民；

【作者基本信息】 北京邮电大学 ， 电路与系统， 2009， 博士

【摘要】 本文研究内容为无线传感器网络的分布式无测距依赖定位算法。无线传感器网络由大量具有感知、计算和无线通信能力的廉价传感器节点以自组织方式构成。网络布线多采用空投抛撒,节点位置未知。但节点观测信息一般要求附带位置参数,因此节点自定位算法是无线传感器网络首先要解决的关键技术之一。分布式无测距依赖算法不需要网络计算中心和节点硬件测距能力,成本低、鲁棒性好、定位精度基本满足需要,更有实用价值。目前代表性算法只有四种,其中DV-Hop算法综合性能最好,它用两次泛洪法通信量达到33%定位精度。本文介绍了研究背景和主流算法；分析了分布式无测距依赖定位算法原理,指出定位误差根本原因是量化误差；提出了四种新算法,理论分析并通过OPNET仿真证实,四种新算法以近一次泛洪法的通信量可以获得高于DV-Hop算法16-20个百分点的定位精度,最高可达13%。本文的主要研究成果如下：1.分析分布式无测距依赖定位算法原理,构建理论模型。推导计算公式：平均连通度与节点数、无线射程平方成正比,和测试区域面积成反比。推导估算公式：通信量和锚节点数、节点数成正比。分析定位精度：跳数是用无线射程对节点间距量化后的量化值,量化误差是以跳数为基础的定位算法产生定位误差的根本原因。2. LSHop算法,综合指标良好,可以全面替代DV-Hop算法。折合跳数降低量化误差,与折合跳距结合,可以提高测距精度。迭代三(多)边法,充分利用冗余信息,提高定位精度。记忆泛洪法,避免转发不参与定位计算的无用消息,减少通信量。仿真证实,可以用DV-Hop算法52.0%通信量,达到15%定位精度。3. Cluster算法,抗不可靠锚节点和路径影响。三边比例法,知道三点之间距离比例值(跳数)和其中两点(锚节点)位置,可计算出第三点(未知节点)一对候选共轭位置。简单密度聚类法,用聚类半径内候选位置数作为密度来确定相似类,用类质心定位,排除不可靠网络参数,提高定位精度。选举泛洪法,利用最短路径生成树获取聚类定位所需信息,减少通信量。仿真证实,聚类半径等于无线射程时算法定位精度最好,建议作为经验值使用。该条件下,可以用DV-Hop算法52.3%通信量,达到17%定位精度。4. HopScale算法,抗节点失效和位移,可以应用于移动锚节点场景。比例定位法,知道节点到锚节点距离比例和锚节点位置,即可实现定位。定义邻域(节点无线覆盖区域)内所有节点到同一锚节点的跳数为邻域值,折半查找法可以用实测获得的邻域值计算出梯度,梯度可以消除量化误差,是更好的距离比例值。邻域泛洪法,基于一次普通泛洪法,不增加通信量即可实测获得邻域值。仿真证实,可以用DV-Hop算法50.0%通信量,达到16%定位精度。5. Fuzzy算法,定位精度高,可以用较小改造代价提高已有算法性能。以已有算法粗测位置作为模糊聚类核心,去共轭干扰并确定候选位置概率分布统计参数。用候选位置正态分布概率密度作为模糊隶属度加权定位,降低不可靠锚节点和路径影响。梯度泛洪法,对已有算法增加附加通信阶段,较小改造即可获得邻域值,拟合曲线可以简化邻域值到梯度的计算。仿真证实,可以用DV-Hop算法54.4%通信量,达到13%定位精度更多还原

【Abstract】 This paper studied the distributed range-free localization algorithms for WSN (Wireless Sensor Networks).WSN is an ad hoc network composed of many cheap nodes with capability of detections, calculations and wireless communications. Nodes’ locations are usually random and unknown. Unfortunately, observation informations without location parameters are mostly useless. Therefore, node self-localization algorithm, especially distributed range-free one leading to low cost and well robustness, is one of WSN’s key techniques. There are four major algorithms. DV-Hop has the best performance with precision 33% and traffic twice floods.This paper discussed the localization principle and quantization error, proposed four new algorithms. Simulations by OPNET showed that the precisions are 16-20 percentages higher than DV-Hop’s and the traffics are near once flood.The main research results are as follows:1. From analysis of distributed range-free localization algorithms’ principle, the paper constructed theoretical models, and derived average connectivity formula and traffic estimate formula.Theoretical research showed that quantization error, which comes from using the radio range to quantize the distance, is the fundamental reason for localization error.2. LSHop has the good integrated performance and may instead of DV-Hop. Equivalent hop counts and AHS (Average Hop Size) can reduce the impact of quantization error. Iterative Positioning strategy promotes precision by redundant informations. Memorial Flood avoids forwarding useless packets. Simulations showed that precision can be increased to approach to 15% and traffic can be decreased to 52.0% of DV-Hop’s.3. Cluster can self-exclude unreliable anchors or paths. Trilateral Proportion strategy calculates a pair of conjugate candidate positions from two points’positions and trilateral proportions. Simple Density Clustering strategy defines the number of candidates located within the clustering radius as density and uses centroid of the densest cluster as the node’s location. Vote Flood avoids twice floods by the shortest path tree. Precision can be increased to close to 17% with 52.3% traffic of DV-Hop’s, from the simulations.4. HopScale has only one communication stage and adapts to the mobile anchors scenarios. Proportion Localization strategy can locate nodes without AHS calculation needed. Neighborhood Flood can keep the same process of a normal flood and obtain the Neighborhood Value. Gradient is a better distance proportion and may be calculated from Neighborhood Value by BinarySearch. Simulation showed that precision can be increased to about 16% with once flood traffic.5. Fuzzy has the highest precision. Using the result of other existing algorithms as the clustering core and the statistics of distribution as the fuzzy membership grades, nodes may localize bypassing clustering. Gradient Flood simplifies the gradient calculation by Fitting Curve and avoids big changes to existing algorithms. Simulation showed that precision can be increased to near 13%, higher than that of all similar algorithms including the others put forward in this paper.更多还原