无线传感器网络中节点定位算法的研究

论文摘要

早在上世纪七十年代末,美国国防部高级研究计划署（DARPA）就提出了无线传感器网络的最初构想。随着近三十年来微电机系统MEMS（micro-electro-mechanical systems）、嵌入式系统、处理器、无线电技术以及存储技术的巨大进步,新一代无线传感器网络应运而生。无线传感器网络通常由大量具有有限的感知、计算、存储和无线通信能力的微小节点构成,当将这些节点以适当的方式组成网络,并将它们的输出有机地关联与融合时,整个网络可提供远高于单个节点的强大功能。无线传感器网络可广泛应用于环境监测、工业过程控制、战场监视、抢险救灾、反恐等多种场合。美国国家研究委员会在一篇报告中指出,“该网络在全社会的普及将使此前信息革命中发生的一切重大事件相形见绌”。无线传感器网络已成为近几年的研究热点,其中网络路由、时间同步、节点定位、拓扑控制及传感器网络应用等成为研究的重点。节点定位是无线传感器网络的一项基本能力。传感器节点从物理环境中采集的数据只有同位置信息联系在一起才是有意义的,同时节点位置还在目标定位/跟踪、提高路由效率等方面发挥着重要的作用。然而,为传感器网络设计和实现一个“最佳”的定位算法是一件非常困难的事情,主要原因在于传感器网络的规模可能很大（成千上百个节点）,而计算、通信、存储能力及能源都非常有限,这使得常见的定位策略（如利用GPS系统、手工配置位置等）无法应用到传感器网络中。目前,学术界已经提出了各种各样的节点定位算法,这些算法大致分为基于测距的定位算法和非基于测距的定位两类。基于测距的定位算法使用某种测量技术得到节点间关于距离或角度的估计值,然后采用三边测量法或三角测量法等几何方法进行定位。非基于测距的定位算法利用接收到的信号强度或节点间的无线连接来判断节点间的远近关系或邻居关系,进而粗略地进行定位。目前最常见的测距方法是利用节点配备的无线电收发器,通过接收到的信号强度并利用信号的传播模型来估计距离,这个模型假定无线电信号的传输是各向同性的。然而,越来越多的研究表明,在无线传感器网络这种由密集的低功率节点组成的环境中,无线信号的传播严重偏离理想模型,接收信号强度严重依赖方向,而且随节点及环境的不同而不同,因而完全没有可能仅根据接收到的信号强度来推断距离。这意味着目前所有依赖于理想信号传播模型的定位算法都需要重新考虑。由于传感器网络通常部署在无人看护的环境,采用无线通信方式,并且节点的能力及资源非常有限,特别容易受到各种安全攻击。针对节点定位的攻击多为位置及距离欺骗攻击,比如假冒合法节点发布虚假的参考位置信息,通过破坏信号的传播时间、强度或角度来误导测量结果等。然而,目前无线传感器网络中大多数的节点定位算法不具有抵抗安全攻击的能力,少数已经提出的安全定位算法或者只适用于特定种类的安全攻击,或者算法的计算及通信开销很大,不适合能源紧缺的无线传感器网络。本文研究无线传感器网络的节点定位问题。本文的第一个工作是利用一个仿真实际信号传播特性的无线电信号不规则模型RIM（Radio IrregularityModel）建立模拟实验环境,通过大量的仿真实验研究了接收信号强度、链路对称性及距离之间的映射关系,在此基础上设计并实现了一个基于链路状态的节点定位算法LSBA（Link-State Based Annulus）,并在仿真实验环境中与其它四个典型的同类算法Centroid、DV-HOP、Amorphous和APIT在定位精度、算法收敛速度、计算复杂度和通信复杂度四个方面进行了全面比较。这也是这四个算法在模拟实验环境中首次进行全面的性能比较。实验结果表明在具有适量参考节点的无线传感器网络中,LSBA具有最佳的综合性能,并且LSBA对节点的不规则分布也有很好的适应性。本文的第二项工作是设计并实现了一个能够抵御各种位置和距离攻击并能适应节点与环境异常的鲁棒的节点定位算法Bilateration。该算法将位置或距离攻击导致的虚假位置或距离看成是有误差的信息,而节点出错或局部环境异常造成的结果也是出现位置或距离误差,为此Bilateration采用统一的方法来处理这三种情况。首先根据正常的位置与距离应有的几何关系区分出可能是正确的和错误的（即误差太大的）信息,然后只利用可能是正确的信息进行节点定位。本文将Bilateration与基于三边测量法的三个典型算法（有过滤能力和没有过滤能力）进行了比较,仿真实验表明在测量噪声受限的传感器网络中,Bilateration具有最好的定位精度和最小的计算复杂度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 无线传感器网络
• 1.2 节点定位问题
• 1.2.1 问题定义
• 1.2.2 算法划分
• 1.2.3 性能指标
• 1.2.4 影响因素
• 1.2.5 安全问题
• 1.3 定位算法面临的问题
• 1.3.1 面临的挑战
• 1.3.2 发展趋势
• 1.4 论文工作
• 1.5 论文结构
• 第2章 定位算法的理论基础
• 2.1 数学基础
• 2.1.1 解方程
• 2.1.2 三角测量法
• 2.1.3 几何约束
• 2.1.4 统筹方法
• 2.2 算法举例
• 2.2.1 基于测距的定位算法
• 2.2.2 非基于测距的定位算法
• 2.3 本章小结
• 第3章 基于链路状况的定位算法:LSBA
• 3.1 无线电的传播
• 3.2 无线电信号传播模型
• 3.2.1 大范围的传播模型
• 3.2.2 中等范围的传播模型
• 3.3 面临的问题
• 3.4 RIM模型
• 3.5 算法描述及实现
• 3.6 性能比较
• 3.6.1 平均连接度对算法性能的影响
• 3.6.2 参考节点平均数目对算法性能的影响
• 3.6.3 DOI对算法性能的影响
• 3.6.4 VSP对算法性能的影响
• 3.6.5 APIT算法的收敛速度
• 3.6.6 算法在C型区域内的性能
• 3.7 本章小结
• 第4章 安全定位算法:Bilateration
• 4.1 启发
• 4.2 问题描述
• 4.3 LS,LMS and LLMS
• 4.3.1 Least Square
• 4.3.2 Least Median Square
• 4.3.3 Linear LMS
• 4.4 Bilateration
• 4.5 模拟
• 4.5.1 门限
• 4.5.2 参考节点平均数目对算法性能的影响
• 4.5.3 破坏节点比例对算法性能的影响
• 4.5.4 最佳合理后备位置对Bilateration性能的改进
• 4.5.5 测距误差对算法性能的影响
• 4.5.6 算法性能和通信复杂度的折中
• 4.5.7 计算复杂度分析
• 4.6 本章小节
• 第5章 总结与展望
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果