论文部分内容阅读
摘 要：无线传感器网络（Wireless SensorNetworks，WSN）通过引入网络技术使具有数据采集能力、信息处理能力和无线通信能力的传感器节点不再是单个的感知单元，而是能够交换信息、协调控制的有机结合体。无线传感器网络已成为一种全新的信息获取、处理、传输和控制系统，并在军事、工业、商业、医疗、环境监测等领域有着广阔应用前景。无线传感器网络广泛应用在环境恶劣、不可到达区域，实现监测与跟踪任务。
首先，在查阅大量相关文献的基础上，本文综述了无线传感器网络技术在国内外的研究现状，介绍了无线传感器网络定位计算方法和定位算法分类方法，并详细分析了近年来该领域具有代表性的算法和研究成果。其次，考虑到无线传感器网络中的节点是随机部署在二维空间内的特定应用环境中，移动锚节点利用周围节点信息进行动态路径规划是一个重要研究方向。本文针对静态路径规划缺少灵活性的缺点，提出了一种禁忌搜索动态路径规划方法，通过仿真分析验证了该方法在节点非均匀分布情况下的有效性。然后，研究分析了基于半定规划的定位模型，仿真分析了该研究领域内主要算法的定位性能。针对集中式半定规划定位算法存在计算复杂度大的问题，本文重点探讨了一种基于多功率移动锚节点的分布式半定规划定位算法，仿真结果表明该算法可以大大减小算法的计算复杂度。
1 节点定位的基本原理
无线传感器网络中包含大量传感器节点，通常节点的放置采用随机撤布放置方式，如果依靠人工标定来确定每个节点的位置，其工作量巨大，难以完成。另一种可直接获得节点位置的方法是为每个节点配备全球定位系统（GPS），但由于节点数目众多，考虑到价格、体积、功耗等因素的限制，通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置或为它们配备定位系统（如GPS），这些节点通常称为锚节点。目前节点定位的研究热点集中于如何利用这些锚节点提供的位置信息与节点间的协作，来计算非锚节点的位置。
无线传感器网络定位问题的一般前提假设是：
（1）网络具有较高的密度；
（2）网络内每一个节点具有全网唯一的ID；
（3）在没有特别说明的情况下，所有节点具有相同的最大通信距离；
（4）在定位过程中，假设节点相对位置不变。
2 节点定位的方法
2.1无线信号测量方法
节点定位的计算通常需要一些表征几何特征的原始数据，这些信息可以通过对无线信号的某些特征进行测量来获取。以下介绍几种常用的无线信号
测量方法。
1. 测量信号到达时间（TOA.Time of Arrival）
2. 测量不同信号到达时间差
3. 测量接收信号到达角
4. 测量节点的信号强度
5. 测量节点是否在发射信号的接收范围内
2.2节点定位的计算方法
获得了检测量后，利于如下方法得到节点的定位。
1. 三边（多边）计算法
2. 三角（多角）计算法
3. 利用范围重叠计算
（1）重叠区域质心算法
（2）凸规划算法
（3）跳数距离估算法
（4）变覆盖范围定位算法
（5）模板匹配算法
2.3定位算法的分类
（1）集中式计算与分布式计算
（2）基于测距技术的定位和无需测距技术的定位
（3）绝对定位与相对定位绝对定位的定位结果是一个标准的坐标位置，如经纬度。目前大部分WSN系统采用这种表示方式。相对定位通常以网络中部分节点为参考，建立整个网络的相对坐标系统。典型的相对定位算法有SPAI¨（self-position algorithm）。而MDS.MAP定位算法可以根据网络配置的不同分别实现两种定位。
（4）细粒度定位和粗粒度定位根据接收信号强弱、时间、方向和信号模式匹配等完成定位的称为“细”，根据节点接近度进行定位的称为“粗”。高精度的定位技术往往要求较高的器件水平和能耗，在有些场合下，为了满足传感器网络节点的低成本、低能耗的要求，需要根据任务和需求选择适度“粗”的算法。细粒度的典型算法有质心算法、Active Baage凸规划等。粗粒度的典型算法有跳数距离估算法等。
（5）循环求精和一次计算大部分定位算法都采用一次计算得到节点的位置。循环求精是在起始阶段得到节点位置的粗略估计，在循环阶段每个节点向其邻居节点广播它的位置估计，并根据从邻居节点接收的位置信息和节点间的测距结果重新计算自身位置，直至两次计算得到的位置估值之差小于一定的域值。典型的循环求精算法有Cooperative ranging㈣和Two—Phase Positioning【16】
3 性能方法的评价标准
（1）定位精度：一般用误差值与节点的无线电测距射程的比例表示，例如定位精度为20%表示误差是射程范围的20%。
（2）锚节点的密度：因为锚节点通常依赖人工部署或安装GPS等定位设备，使用成本较高。锚节点的使用数量是限制WSN规模、影响WSN成本的重要指标之一。
（3）功耗：由于传感器节点的能量有限，控制功耗是WSN的一项重要工作。因此定位算法所需要的计算复杂度、时间复杂度、通信开销、存储开销等成为影响功耗的重要因素。
（4）规模：不同的定位系统或算法所能定位目标的数量是一个重要的评价指标。节点数量增加带来了网络通信干扰、结构复杂度和通信复杂度的增加。规模的扩大对算法的适应性提出了考验。
（5）容错性和适应性：实际应用场合存在着多种不确定性，例如多径传播、通信盲点，节点能量耗尽、损坏等。这要求定位系统和算法有较强的容错性和适应能力，能自动调整，减小不确定因素带来的错误和误差。
4 节点定位技术的发展方向
（1）低成本、高能效、高精度的距离或角度测量技术。
（2）为尽量延长网络生存周期的低复杂度、低开销、低能耗的节点定位算法。
（3）适用于大规模或超大规模无线传感器网络的低成本节点定位技术。另外，已提出的节点定位算法研究成果大部分是基于静态网络的，对移动节点定位技术研究相对较少，适用于网络拓扑结构处于动态变化时的节点的定位技术还有待研究。■
首先，在查阅大量相关文献的基础上，本文综述了无线传感器网络技术在国内外的研究现状，介绍了无线传感器网络定位计算方法和定位算法分类方法，并详细分析了近年来该领域具有代表性的算法和研究成果。其次，考虑到无线传感器网络中的节点是随机部署在二维空间内的特定应用环境中，移动锚节点利用周围节点信息进行动态路径规划是一个重要研究方向。本文针对静态路径规划缺少灵活性的缺点，提出了一种禁忌搜索动态路径规划方法，通过仿真分析验证了该方法在节点非均匀分布情况下的有效性。然后，研究分析了基于半定规划的定位模型，仿真分析了该研究领域内主要算法的定位性能。针对集中式半定规划定位算法存在计算复杂度大的问题，本文重点探讨了一种基于多功率移动锚节点的分布式半定规划定位算法，仿真结果表明该算法可以大大减小算法的计算复杂度。
1 节点定位的基本原理
无线传感器网络中包含大量传感器节点，通常节点的放置采用随机撤布放置方式，如果依靠人工标定来确定每个节点的位置，其工作量巨大，难以完成。另一种可直接获得节点位置的方法是为每个节点配备全球定位系统（GPS），但由于节点数目众多，考虑到价格、体积、功耗等因素的限制，通常不采取这种方案。一种较合理的方法是为部分节点事先标定好准确位置或为它们配备定位系统（如GPS），这些节点通常称为锚节点。目前节点定位的研究热点集中于如何利用这些锚节点提供的位置信息与节点间的协作，来计算非锚节点的位置。
无线传感器网络定位问题的一般前提假设是：
（1）网络具有较高的密度；
（2）网络内每一个节点具有全网唯一的ID；
（3）在没有特别说明的情况下，所有节点具有相同的最大通信距离；
（4）在定位过程中，假设节点相对位置不变。
2 节点定位的方法
2.1无线信号测量方法
节点定位的计算通常需要一些表征几何特征的原始数据，这些信息可以通过对无线信号的某些特征进行测量来获取。以下介绍几种常用的无线信号
测量方法。
1. 测量信号到达时间（TOA.Time of Arrival）
2. 测量不同信号到达时间差
3. 测量接收信号到达角
4. 测量节点的信号强度
5. 测量节点是否在发射信号的接收范围内
2.2节点定位的计算方法
获得了检测量后，利于如下方法得到节点的定位。
1. 三边（多边）计算法
2. 三角（多角）计算法
3. 利用范围重叠计算
（1）重叠区域质心算法
（2）凸规划算法
（3）跳数距离估算法
（4）变覆盖范围定位算法
（5）模板匹配算法
2.3定位算法的分类
（1）集中式计算与分布式计算
（2）基于测距技术的定位和无需测距技术的定位
（3）绝对定位与相对定位绝对定位的定位结果是一个标准的坐标位置，如经纬度。目前大部分WSN系统采用这种表示方式。相对定位通常以网络中部分节点为参考，建立整个网络的相对坐标系统。典型的相对定位算法有SPAI¨（self-position algorithm）。而MDS.MAP定位算法可以根据网络配置的不同分别实现两种定位。
（4）细粒度定位和粗粒度定位根据接收信号强弱、时间、方向和信号模式匹配等完成定位的称为“细”，根据节点接近度进行定位的称为“粗”。高精度的定位技术往往要求较高的器件水平和能耗，在有些场合下，为了满足传感器网络节点的低成本、低能耗的要求，需要根据任务和需求选择适度“粗”的算法。细粒度的典型算法有质心算法、Active Baage凸规划等。粗粒度的典型算法有跳数距离估算法等。
（5）循环求精和一次计算大部分定位算法都采用一次计算得到节点的位置。循环求精是在起始阶段得到节点位置的粗略估计，在循环阶段每个节点向其邻居节点广播它的位置估计，并根据从邻居节点接收的位置信息和节点间的测距结果重新计算自身位置，直至两次计算得到的位置估值之差小于一定的域值。典型的循环求精算法有Cooperative ranging㈣和Two—Phase Positioning【16】
3 性能方法的评价标准
（1）定位精度：一般用误差值与节点的无线电测距射程的比例表示，例如定位精度为20%表示误差是射程范围的20%。
（2）锚节点的密度：因为锚节点通常依赖人工部署或安装GPS等定位设备，使用成本较高。锚节点的使用数量是限制WSN规模、影响WSN成本的重要指标之一。
（3）功耗：由于传感器节点的能量有限，控制功耗是WSN的一项重要工作。因此定位算法所需要的计算复杂度、时间复杂度、通信开销、存储开销等成为影响功耗的重要因素。
（4）规模：不同的定位系统或算法所能定位目标的数量是一个重要的评价指标。节点数量增加带来了网络通信干扰、结构复杂度和通信复杂度的增加。规模的扩大对算法的适应性提出了考验。
（5）容错性和适应性：实际应用场合存在着多种不确定性，例如多径传播、通信盲点，节点能量耗尽、损坏等。这要求定位系统和算法有较强的容错性和适应能力，能自动调整，减小不确定因素带来的错误和误差。
4 节点定位技术的发展方向
（1）低成本、高能效、高精度的距离或角度测量技术。
（2）为尽量延长网络生存周期的低复杂度、低开销、低能耗的节点定位算法。
（3）适用于大规模或超大规模无线传感器网络的低成本节点定位技术。另外，已提出的节点定位算法研究成果大部分是基于静态网络的，对移动节点定位技术研究相对较少，适用于网络拓扑结构处于动态变化时的节点的定位技术还有待研究。■