无线定位算法研究.doc

无线定位算法研究 ——AC-HOP算法改进 Version?: 1.0.0 2010-07-08 DOCUMENT HISTORY Ed. Version Author Change 1 1.0.0 曹玉斌 Initial E-mail:cyb@mail.ustc.edu.cn  目 录 1 项目概述 3 研究背景 3 定位算法研究意义 3 判断定位算法好坏的标准 3 项目需求规格 4 系统设计描述 5 简介 5 经典算法分析 5 算法改进 7 系统功能测试 9 算法测试计划 9 算法测试环境 9 定位算法测试指标 11 测试报告 11 项目及课程总结 14 参考资料 15 项目概述 研究背景 随着微机电系统，片上系统，无线通信和低功耗嵌入式技术的飞速发展，集成了传感器，微机电系统和网络三大技术而成的无线传感器网络是一种全新的信息获取和处理技术。并以其低功耗，低成本，分布式和自组织的特点带来了信息感知的一场变革。简而言之，无线传感器网络就是由部署在检测区域内大量的廉价微型传感器节点组成，通过无线通信方式组成了一个多跳自组织网络。 无线传感器网络具有非常广阔的应用前景。美国商业周刊和MIT技术评论在预测未来结束发展中，分别将无线传感器网络列为21世纪最具影响力的21项技术和改变世界的十大技术之一。无线传感器网络与塑料电子学，仿生人体器官并称为全球未来的三大高科技产业。 传感器节点定位是无线传感器网络应用研究的一个非常重要的方面。基于传感器节点成本低的要求，GPS信号定位方法则被淘汰掉了。由于无线传感器网络存在网络自组织性，节点分布随机性以及网络拓扑的不确定性等特点，致使定位方法必须在分布性，自适性，可扩展性方面有比较杰出的性能。通过比较目前已经提出的多种定位算法可以发现，基于锚节点位置的节点定位算法在以上均具有明显的优势。根据定位过程中是否对节点相互距离进行测量，定位算法分为非基于测距的定位算法与基于测距的定位算法，二者相互比较，非基于测距的定位算法具有成本低，功耗小，抗测距噪声能力强和硬件设备简单易行等优势，定位精度不及基于测距的定位算法是其劣势，但在当今无线传感器网络大量应用的领域，这个精度足以接受，因此非基于测距的定位算法今年倍受关注。目前已发展的非基于测距的定位算法主要有质心算法，凸规划算法，DV-Hop算法，Amorphous算法，MDS-MAP算法。 定位算法研究意义 须知道节点感知数据的发生位置才有应用价值，这是应用的直接要求。 无线传感器网络的很多通信协议是在已知节点位置的基础上运行的。另外基于节点的已知位置可优化网络运行期间的值守调度机制，使网络中冗余节点不定期地轮休以延长寿命。 判断定位算法好坏的标准 定位精度 节点定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比例表示。用二维网格划分定位区域，精度为网格大小。 规模 不同的节点定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内，一种技术可以定位多少目标也是一个重要的评价指标。 锚节点密度 锚节点的费用会比普通节点高两个数量，关系到系统成本。 节点密度 关系到网络通信质量和系统成本。 容错性和自适应性 线传感网络本身特点决定。 功耗、代价（时、空成本）。 项目需求规格 建立室内环境的感知系统，可以确定室内环境中人的位置。 实现的途径可以通过构建室内无线网络，确定网络中结点的位置，已达到定位的目的。但是室内又有网络规模小，结点密度低，受干扰多，应用场景复杂等特点的影响。 系统设计描述 简介 解决方案：首先调研已有的定位算法，找出与应用需求相近的算法。然后分析算法的优缺点，结合应用环境提出改进。 经典算法分析 调研分析结果是AC-HOP算法最适合此应用场景。以下是DV-Hop 算法介绍： 美国Rutgers University 的Niculescu等人利用距离矢量路由和GPS定位原理提出的一系列分布式定位算法，合称为自组织定位系统。包括六种定位算法：DV-Hop算法，DV-Distance算法,DV-Euclidean算法，DV-Coordinate算法，DV-Bearing算法和DV-Radial算法。六者中应用最成功，使用最广泛的当属DV-Hop定位算法。DV-Hop算法和质心算法一样，整个定位过程不依赖于昂贵的测距，不同的是DV-Hop算法利用了多跳锚节点信息来参与未知节点的定位，其定位覆盖率远远高于质心算法。 DV-Hop算法由三个阶段组成。第一阶段，使用典型的距离矢量交换协议，通过节点间的信息交换，使