论文部分内容阅读
摘 要：节点定位技术是无线传感器网络的关键技术之一。文章介绍了无线传感器移动节点定位的原理，讨论了移动节点定位算法的分类，对移动节点定位算法的优点、局限、适用情况做了对比，并对未来移动节点定位算法的发展进行了展望。
关键词：无线传感器网络；移动节点定位；蒙特卡罗定位算法；
Abstract： Localization technique is one of the key technologies of wireless sensor networks.This paper introduces the principle of wireless sensor node localization in mobile，and discusses the classification of mobile node localization algorithm，and compares the mobile node localization algorithm advantages，disadvantages and applicability，and the future of mobile node localization algorithm development was prospected.
Key words：wireless sensor network ，mobile node localization，Monte Carlo localization algorithm
文章编号：1674-3520（2015）-12-00-02
引言
无线传感器网络（WSN）是21世纪最重要的技术之一，它是由一组具有有限计算能力和通讯性能的传感器构成的分布式自组织的无线网络。目前它已经广泛应用在智能家居、医疗护理、智能交通、环境监测等领域。无线传感器节点定位是最关键的技术，因为不包含位置信息的节点是毫无价值的，而且无线传感器中的诸如数据传输与传递的过程是以节点的位置信息为基础的。无线传感器节点定位主要分为静止节点定位与移动节点定位。静止节点定位也称传统节点定位技术。根据是否将定位过程建立在距离或角度信息的基础上主要分为基于测距的定位技术与非测距技术。基于测距的定位技术主要包括TOA、TDOA、AOA、RSSI等；基于非测距技术主要包括质心定位技术、DV-Hop、Amorphous、APIT等。这些算法可以通过经常刷新位置估计来适用于移动网络，但是它们没有考虑到如何可以开发移动性来完成定位。有关静止节点定位技术的综述现在已有很多，故本文不再赘述，本文主要论述移动节点定位技术。
一、移动传感器网络定位算法分类
根据移动无线传感器节点的运动情况的不同可以分为三类：锚节点静止而未知节点运动、锚节点运动而未知节点静止、锚节点和未知节点都运动的情况。锚节点静止而未知节点运动的一个典型例子是未知节点沿着河漂流，锚节点固定在河岸中的某一位置。锚节点运动而未知节点静止的典型例子是一个军事应用，其中未知节点从飞机上下落到土地，士兵或者动物身上附带的发射器被当做移动锚节点。锚节点和未知节点都运动的情形是最通用的，它适用于未知节点和锚节点以ad hoc方式分布，或因为他们所处的环境而移动或因为他们具有促动器而移动的任何应用。在此情况下，主流的定位算法是蒙特卡罗算法及其衍生算法。
（一）蒙特卡罗算法
2005年Lingxuan Hu和David Evans将蒙特卡罗（MCL）定位算法首先应用到了移动传感器网络中，而此前MCL方法一直是应用在机器人定位中[2]。MCL算法的流程是先初始化，然后判断系统是否到达定位时间，如果到达定位时间，就进入预测阶段。在预测阶段，位置节点使用转移方程并根据前一时刻的样本分布来预测它可能的位置和运动情况。如果已知节点的最大运动速度为v，则节点在当前时间段的位置是以前一时间段位置为圆心，v为半径的圆内。所以根据之前位置估计的现有位置的概率以均匀分布的形式给出。接下来进入过滤阶段。在这一阶段，未知节点根据新的观测值滤除不可能存在的位置。滤波条件是保留所有直接被未知节点监听到的锚节点和被未知节点的邻居节点监听到但未被未知节点直接监听到的锚节点的集合。过滤之后剩下的节点数可能少于要求的数目，预测和过滤过程重复进行，加入找到的满足条件的可能节点，直到达到要求或者采样次数达到上限为止。最后将样本点集合中的平均值作为待定位节点在t时刻的估计位置。
（二）MCB算法
在MCL方法中如果采样样本没有达到阈值就不再设置样本集了。在MCL算法基础上，Baggio等人提出了Monte Carlo Localization Boxed（MCB）算法。在MCB算法中，使用监听到的锚节点的信息来限制采样区域，主要通过构建锚盒和采样盒子。一个监听到一跳或二跳锚节点的未知节点构建一个覆盖锚节点广播范围重叠区域的盒子称为锚盒。锚盒的构建过程是一个未知节点构建一个以锚节点位置为中心的边长为2r的正方形，r是廣播范围。采样盒是一个以旧样本点为中心，2vmax为边长的正方形。它限制了对于每个旧样本点，一个未知节点在一个时间间隔内能移动的最大区域。盒子的构建保持一个序列化过程，锚盒首先被建立，独立更新每个旧样本点，建立采样盒子，从中每个新样本点被有效采样。MCB的滤波和重采样过程与MCL相同[3]。
（三）MMCL定位算法
传统的MCL、MCB算法虽然可以减少计算量但是这些算法仍然依赖于一些特定的参数比如固定的广播传输范围，而且主要有两个限制：需要有充分的锚节点和假定固定广播传输范围已知。因此Jiyoung Yi等人根据具有多跳传播的序列蒙特卡罗方法提出了一种新的定位机制，基于多跳的MCL算法MMCL。
MMCL算法主要由两部分组成。第一部分像DV-hop一样给锚节点提供一个平均跳段距离。每个传感器节点从锚节点处获得平均每跳距离并计算它的位置。第二部分是在每个传感器节点运用MCL算法[2]。 （四）对偶MCL算法与混合MCL算法
对偶蒙特卡罗算法的原理就是将传统MCL算法中的预测阶段和过滤阶段进行倒置：以观测方程获得样本点，以转移方程过滤样本点。在混合蒙特卡罗算法中，样本点通过原始MCL算法和对偶MCL算法生成。混合蒙特卡罗算法是以概率1-p使用原始MCL采样算法，以概率p使用对偶MCL算法来生成每个样本点。
（五）MSL和MSL*算法
它是由加拿大York大学的Rudafshani M和Datta S设计提出的，在 MCL算法基础上进行改进，依据样本集的构建过程和采样的共同邻居节点关系将样本粒子的权重进行不同的取值。该算法是利用待定位节点的一阶和二阶邻居节点来改善定位效果。MSL*针对 MCL 算法仅仅依靠信标节点来实现定位进行了改进，提出了两种利用未知节点的邻居节点来提高定位精度的方法，但是该算法也会扩大采样区间，又降低了采样的效率。
二、各算法性能比较
以上介绍的每个算法都有其各自的特点，以下分析每个算法的改进之处、优点、局限和适用情况。
（一）MCB算法特性
MCB算法的优点是不像MCL算法那样定位精度容易受未知节点的最大速度的影响。对于一个类似的定位精度，MCB算法比MCL算法定位更快。在MCB定位算法中，把节点的通信区域看成是一个正规的圆形区域，而在现实的环境中，节点间通信的范围不可能是规则的圆形区域。MCB算法适用于对于MCL算法获得足够多的样本点困难的情形，MCB能得到足够多的样本点。
（二）MMCL算法特性
MMCL算法的改进之处是结合了MCL和DV-Hop两个算法的优势。MMCL算法的优点是不需要提前知道节点传输范围，MMCL相对于MCL算法而言，在信标节点密度较小的时候，由于几乎能用到所有信标节点的位置信息而使其定位精度较高。MMCL算法的局限在于随着信标节点密度的增大，该算法定位精度的提高却很有限，远不及 MCL 算法精度的提高。同时网络中节点间的通信量却迅速增多，浪费了节点的能量。MMCL算法更常适用于大规模且低信标节点密度的网络应用。
（三）对偶MCL算法特性
对偶MCL算法的改进之处是原始蒙特卡罗算法的逻辑颠倒。对偶MCL算法的优点是它克服了依赖样本总个数的缺点。对偶MCL算法的局限是需要更多时间从传感器获得样本。对偶MCL算法的计算量比MCL算法多，定位精度不优于MCL定位精度。对偶MCL算法的适用情况同MCL一样。
（四）混合MCL算法特性
混合蒙特卡罗方法的改进之处是它是原始蒙特卡罗算法和对偶蒙特卡罗算法的结合。混合MCL算法的优点是克服了依赖样本点总个数的缺点。混合MCL算法在计算时间消耗和定位准确性中找到了平衡。混合MCL算法的局限是它的计算量比MCL算法多，定位精度也优于MCL定位精度。混合MCL算法的适用情况同MCL一样。
（五）MSL算法特性
MSL算法的改进之处是通过使用所有邻居节点的位置估计（而不仅仅是锚节点）来提高算法的定位精度。MSL算法的优点是具有良好的衰减性和更低的通信开销。MSL算法的局限是它需要高的未知节点密度和高的锚节点密度来收敛。MSL算法适用于那些可以支持额外通信开销的大型传感器网络。在最后时间单元倒置大多数样本点的特性使得MSL更适用于具有低运动速度的网络。
（六）MSL*算法特性
MSL*算法的改进之处是它能在广播传输范围内处理不均匀性（异质性）。通过使用所有邻居节点的位置估计（而不仅仅是锚节点）来提高算法的定位精度。MSL*算法的优点是误差较小，具有良好的衰减性，采样步骤较快。MSL*算法在很多场景下表现的比MSL要好，但是这导致了更高的通信开销，它还具有比MSL更高的计算开销。MSL*适用于任何数量的传感器节点是静止的或运动的情况下。适用于那些可以支持额外通信开销的大型传感器网络。在最后时间单元倒置大多数样本点的特性使得MSL*更适用于具有低运动速度的网络。
三、总结与展望
本文主要介绍了蒙特卡罗算法及其衍生算法。基于蒙特卡罗算法的跟踪方法，用蒙特卡罗算法预测移动节点定位目标下一时刻的一组状态；然后通过计算得到各预测状态中与参考目标的状态相似度最大的一个，即为移动节点定位目标跟踪的结果。研究结果表明：该方法能实时、准确地跟踪无规律、非线性运动的目标。不同的算法各有优劣与适用情况，在实际科学计算中应按照不同算法各自的特點，选择合适的算法。研究发展方向期待有更多的衍生算法诞生，未来的移动节点定位算法将向着低复杂度、低开销、低能耗的趋势进一步发展，如何进一步优化节点定位算法将成为无线传感器网络定位技术研究的重要方向。期待着未来的WSN定位算法向着智能化、便捷化的方向发展，同时要实现这一目标具有理论上、技术上的难度，需要科研工作者努力研究实现。
参考文献：
[1]罗雯雯.无线传感器网络自主移动节点定位技术研究.浙江理工大学硕士学位论文.2013.03
[2]宋艳.基于Monte Carlo移动无线传感器网络定位算法研究.南京邮电大学硕士学位论文2012.02
[3]王妮.分布式无需测距（range-free）的移动无线传感器网络节点的定位方法.上海交通大学硕士学位论文.2008.11
关键词：无线传感器网络；移动节点定位；蒙特卡罗定位算法；
Abstract： Localization technique is one of the key technologies of wireless sensor networks.This paper introduces the principle of wireless sensor node localization in mobile，and discusses the classification of mobile node localization algorithm，and compares the mobile node localization algorithm advantages，disadvantages and applicability，and the future of mobile node localization algorithm development was prospected.
Key words：wireless sensor network ，mobile node localization，Monte Carlo localization algorithm
文章编号：1674-3520（2015）-12-00-02
引言
无线传感器网络（WSN）是21世纪最重要的技术之一，它是由一组具有有限计算能力和通讯性能的传感器构成的分布式自组织的无线网络。目前它已经广泛应用在智能家居、医疗护理、智能交通、环境监测等领域。无线传感器节点定位是最关键的技术，因为不包含位置信息的节点是毫无价值的，而且无线传感器中的诸如数据传输与传递的过程是以节点的位置信息为基础的。无线传感器节点定位主要分为静止节点定位与移动节点定位。静止节点定位也称传统节点定位技术。根据是否将定位过程建立在距离或角度信息的基础上主要分为基于测距的定位技术与非测距技术。基于测距的定位技术主要包括TOA、TDOA、AOA、RSSI等；基于非测距技术主要包括质心定位技术、DV-Hop、Amorphous、APIT等。这些算法可以通过经常刷新位置估计来适用于移动网络，但是它们没有考虑到如何可以开发移动性来完成定位。有关静止节点定位技术的综述现在已有很多，故本文不再赘述，本文主要论述移动节点定位技术。
一、移动传感器网络定位算法分类
根据移动无线传感器节点的运动情况的不同可以分为三类：锚节点静止而未知节点运动、锚节点运动而未知节点静止、锚节点和未知节点都运动的情况。锚节点静止而未知节点运动的一个典型例子是未知节点沿着河漂流，锚节点固定在河岸中的某一位置。锚节点运动而未知节点静止的典型例子是一个军事应用，其中未知节点从飞机上下落到土地，士兵或者动物身上附带的发射器被当做移动锚节点。锚节点和未知节点都运动的情形是最通用的，它适用于未知节点和锚节点以ad hoc方式分布，或因为他们所处的环境而移动或因为他们具有促动器而移动的任何应用。在此情况下，主流的定位算法是蒙特卡罗算法及其衍生算法。
（一）蒙特卡罗算法
2005年Lingxuan Hu和David Evans将蒙特卡罗（MCL）定位算法首先应用到了移动传感器网络中，而此前MCL方法一直是应用在机器人定位中[2]。MCL算法的流程是先初始化，然后判断系统是否到达定位时间，如果到达定位时间，就进入预测阶段。在预测阶段，位置节点使用转移方程并根据前一时刻的样本分布来预测它可能的位置和运动情况。如果已知节点的最大运动速度为v，则节点在当前时间段的位置是以前一时间段位置为圆心，v为半径的圆内。所以根据之前位置估计的现有位置的概率以均匀分布的形式给出。接下来进入过滤阶段。在这一阶段，未知节点根据新的观测值滤除不可能存在的位置。滤波条件是保留所有直接被未知节点监听到的锚节点和被未知节点的邻居节点监听到但未被未知节点直接监听到的锚节点的集合。过滤之后剩下的节点数可能少于要求的数目，预测和过滤过程重复进行，加入找到的满足条件的可能节点，直到达到要求或者采样次数达到上限为止。最后将样本点集合中的平均值作为待定位节点在t时刻的估计位置。
（二）MCB算法
在MCL方法中如果采样样本没有达到阈值就不再设置样本集了。在MCL算法基础上，Baggio等人提出了Monte Carlo Localization Boxed（MCB）算法。在MCB算法中，使用监听到的锚节点的信息来限制采样区域，主要通过构建锚盒和采样盒子。一个监听到一跳或二跳锚节点的未知节点构建一个覆盖锚节点广播范围重叠区域的盒子称为锚盒。锚盒的构建过程是一个未知节点构建一个以锚节点位置为中心的边长为2r的正方形，r是廣播范围。采样盒是一个以旧样本点为中心，2vmax为边长的正方形。它限制了对于每个旧样本点，一个未知节点在一个时间间隔内能移动的最大区域。盒子的构建保持一个序列化过程，锚盒首先被建立，独立更新每个旧样本点，建立采样盒子，从中每个新样本点被有效采样。MCB的滤波和重采样过程与MCL相同[3]。
（三）MMCL定位算法
传统的MCL、MCB算法虽然可以减少计算量但是这些算法仍然依赖于一些特定的参数比如固定的广播传输范围，而且主要有两个限制：需要有充分的锚节点和假定固定广播传输范围已知。因此Jiyoung Yi等人根据具有多跳传播的序列蒙特卡罗方法提出了一种新的定位机制，基于多跳的MCL算法MMCL。
MMCL算法主要由两部分组成。第一部分像DV-hop一样给锚节点提供一个平均跳段距离。每个传感器节点从锚节点处获得平均每跳距离并计算它的位置。第二部分是在每个传感器节点运用MCL算法[2]。 （四）对偶MCL算法与混合MCL算法
对偶蒙特卡罗算法的原理就是将传统MCL算法中的预测阶段和过滤阶段进行倒置：以观测方程获得样本点，以转移方程过滤样本点。在混合蒙特卡罗算法中，样本点通过原始MCL算法和对偶MCL算法生成。混合蒙特卡罗算法是以概率1-p使用原始MCL采样算法，以概率p使用对偶MCL算法来生成每个样本点。
（五）MSL和MSL*算法
它是由加拿大York大学的Rudafshani M和Datta S设计提出的，在 MCL算法基础上进行改进，依据样本集的构建过程和采样的共同邻居节点关系将样本粒子的权重进行不同的取值。该算法是利用待定位节点的一阶和二阶邻居节点来改善定位效果。MSL*针对 MCL 算法仅仅依靠信标节点来实现定位进行了改进，提出了两种利用未知节点的邻居节点来提高定位精度的方法，但是该算法也会扩大采样区间，又降低了采样的效率。
二、各算法性能比较
以上介绍的每个算法都有其各自的特点，以下分析每个算法的改进之处、优点、局限和适用情况。
（一）MCB算法特性
MCB算法的优点是不像MCL算法那样定位精度容易受未知节点的最大速度的影响。对于一个类似的定位精度，MCB算法比MCL算法定位更快。在MCB定位算法中，把节点的通信区域看成是一个正规的圆形区域，而在现实的环境中，节点间通信的范围不可能是规则的圆形区域。MCB算法适用于对于MCL算法获得足够多的样本点困难的情形，MCB能得到足够多的样本点。
（二）MMCL算法特性
MMCL算法的改进之处是结合了MCL和DV-Hop两个算法的优势。MMCL算法的优点是不需要提前知道节点传输范围，MMCL相对于MCL算法而言，在信标节点密度较小的时候，由于几乎能用到所有信标节点的位置信息而使其定位精度较高。MMCL算法的局限在于随着信标节点密度的增大，该算法定位精度的提高却很有限，远不及 MCL 算法精度的提高。同时网络中节点间的通信量却迅速增多，浪费了节点的能量。MMCL算法更常适用于大规模且低信标节点密度的网络应用。
（三）对偶MCL算法特性
对偶MCL算法的改进之处是原始蒙特卡罗算法的逻辑颠倒。对偶MCL算法的优点是它克服了依赖样本总个数的缺点。对偶MCL算法的局限是需要更多时间从传感器获得样本。对偶MCL算法的计算量比MCL算法多，定位精度不优于MCL定位精度。对偶MCL算法的适用情况同MCL一样。
（四）混合MCL算法特性
混合蒙特卡罗方法的改进之处是它是原始蒙特卡罗算法和对偶蒙特卡罗算法的结合。混合MCL算法的优点是克服了依赖样本点总个数的缺点。混合MCL算法在计算时间消耗和定位准确性中找到了平衡。混合MCL算法的局限是它的计算量比MCL算法多，定位精度也优于MCL定位精度。混合MCL算法的适用情况同MCL一样。
（五）MSL算法特性
MSL算法的改进之处是通过使用所有邻居节点的位置估计（而不仅仅是锚节点）来提高算法的定位精度。MSL算法的优点是具有良好的衰减性和更低的通信开销。MSL算法的局限是它需要高的未知节点密度和高的锚节点密度来收敛。MSL算法适用于那些可以支持额外通信开销的大型传感器网络。在最后时间单元倒置大多数样本点的特性使得MSL更适用于具有低运动速度的网络。
（六）MSL*算法特性
MSL*算法的改进之处是它能在广播传输范围内处理不均匀性（异质性）。通过使用所有邻居节点的位置估计（而不仅仅是锚节点）来提高算法的定位精度。MSL*算法的优点是误差较小，具有良好的衰减性，采样步骤较快。MSL*算法在很多场景下表现的比MSL要好，但是这导致了更高的通信开销，它还具有比MSL更高的计算开销。MSL*适用于任何数量的传感器节点是静止的或运动的情况下。适用于那些可以支持额外通信开销的大型传感器网络。在最后时间单元倒置大多数样本点的特性使得MSL*更适用于具有低运动速度的网络。
三、总结与展望
本文主要介绍了蒙特卡罗算法及其衍生算法。基于蒙特卡罗算法的跟踪方法，用蒙特卡罗算法预测移动节点定位目标下一时刻的一组状态；然后通过计算得到各预测状态中与参考目标的状态相似度最大的一个，即为移动节点定位目标跟踪的结果。研究结果表明：该方法能实时、准确地跟踪无规律、非线性运动的目标。不同的算法各有优劣与适用情况，在实际科学计算中应按照不同算法各自的特點，选择合适的算法。研究发展方向期待有更多的衍生算法诞生，未来的移动节点定位算法将向着低复杂度、低开销、低能耗的趋势进一步发展，如何进一步优化节点定位算法将成为无线传感器网络定位技术研究的重要方向。期待着未来的WSN定位算法向着智能化、便捷化的方向发展，同时要实现这一目标具有理论上、技术上的难度，需要科研工作者努力研究实现。
参考文献：
[1]罗雯雯.无线传感器网络自主移动节点定位技术研究.浙江理工大学硕士学位论文.2013.03
[2]宋艳.基于Monte Carlo移动无线传感器网络定位算法研究.南京邮电大学硕士学位论文2012.02
[3]王妮.分布式无需测距（range-free）的移动无线传感器网络节点的定位方法.上海交通大学硕士学位论文.2008.11