（通信与信息系统专业论文）移动无线传感器网络蒙特卡罗定位算法研究.pdf

硕：e 学位论文 摘要 移动节点定位是无线传感器网络研究中的热点问题之一，它根据少数锚节 点，按照某种定位机制确定移动未知节点自身的位置。现有的无线传感器网络节 点定位算法存在着测距方法受环境影响大、定位精度低和功耗大等问题，不适用 于移动节点定位。随着无线传感器网络技术的不断进步和成熟，其应用将会越来 越广泛，移动节点定位技术的研究对于移动无线传感器网络技术的性能提高和实 用性保证有着重要的理论意义和应用价值。 蒙特卡罗定位方法是与机器人感知和运动的概率模型有关的粒子滤波，它能 够有效并且鲁棒地解决复杂定位问题。蒙特卡罗定位算法的定位精确性不受节点 移动的影响，反而利用其移动性能提高定位的精度，减小定位的代价，将该方法 应用于无线传感器网络中，能够帮助解决移动节点的定位问题。 由于在后验密度分布取值较大区域中的样本数较少，利用蒙特卡罗定位算法 进行定位需要大量的样本才能取得较好的效果。本文提出了一种遗传蒙特卡罗定 位算法，将遗传算法中的交叉和变异两个操作引入到蒙特卡罗定位算法中，对样 本进行优化，使样本向后验密度分布取值较大的区域移动，从而更好地表达系统 的后验密度分布。仿真结果表明，遗传蒙特卡罗定位算法可以显著地减少定位所 需的样本数，具有更高的定位精度和更好的鲁棒性。 此外，通过引入锚节点影响力概念，本文还提出了一种加权采样蒙特卡罗定 位算法。加权采样蒙特卡罗定位算法充分利用节点的移动性和多跳锚节点信息， 用锚节点对未知节点位置的不同影响力来确定样本的权值，以提高定位精度。仿 真研究显示，加权采样蒙特卡罗定位算法具有很好的分布性、可扩展性和鲁棒性， 特别是算法在定位覆盖率等方面表现出了很好的性能，适合应用于大规模移动无 线传感器网络。 关键词：无线传感器网络；移动节点；定位；蒙特卡罗；遗传算法 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：宗 糸日期：口i 年，月2 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 宗缘 丐娇 日期： o y 年i 月o 日 日期： i ，宫年r 月乩日 硕士学位论文 第1 章绪论 1 1 课题来源 本研究课题来源于国家自然科学基金项目( 批准号：6 0 6 7 3 0 6 1 ) 一类复杂 环境下的无线传感器网络定位算法研究和湖南省自然科学基金项目( 批准号： 0 6 j j 5 0 1 1 1 ) ：矿井无线传感器网络移动节点定位与动态轨迹跟踪研究。 本研究旨在探讨无线传感网络中，无任何运动规律的移动节点的轨迹跟踪， 研究适合特定环境的移动节点定位算法。 1 2 研究目的和意义 微电子技术、计算技术和无线通信等技术的进步，推动了低功耗多功能传感 器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多 种功能。无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组 成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感 知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。无线传感器 网络中的很多特定应用都依赖于传感器节点的位置信息，不知道传感器节点的位 置而感知的数据是没有意义的。比如在战场中对敌方军事目标的定位和森林火灾 方位的确定。此外，无线传感器网络的网络运行和管理也需要传感器节点位置信 息的辅助，例如基于位置信息的路由、资源的有效配置、对外部目标的跟踪、计 算网络覆盖范围和控制网络的负载均衡等。无线传感器网络中定位问题的研究正 是基于上述广泛的网络管理和应用背景。 移动节点的跟踪、节点的准确定位和节点轨迹的精确描述，是未来移动无线 传感器网络应用研究中的一个重点，它既可以作为单独应用，也可以作为其它常 见应用的一部分。尤其是在矿井复杂环境下的人身安全和紧急救助的应用中，寻 找一种切实可行的定位方法，对位置不固定的矿工进行实时定位，以此来解决矿 井复杂环境下的人员定位问题，为矿井安全提供预警。 无线传感器网络移动节点定位的研究涉及了网络、数字信号处理、嵌入式系 统等多知识的综合，可以广泛应用在家居监控、野生动物跟踪研究、森林火灾检 测与跟踪、灾后救援以及战场敌对车辆、人员的识别与跟踪等方面。尽管针对静 态无线传感器网络的节点定位问题从系统到理论都进行了一定的研究，但由于节 点的移动性，获取的信息容易失效，增加了定位的难度，削减了定位精度，移动 无线传感器网络的节点定位仍然面临着许多技术挑战，因此我们针对无线传感器 移动无线传感器网络蒙特卡罗定位算法研究 网络移动节点定位问题的研究具有现实的理论意义和应用价值。 蒙特卡罗定位( m o n t e c a r l ol o c a l i z a t i o n ) 方法是与机器人感知和运动的概率 模型有关的粒子滤波，它能够有效并且鲁棒地解决复杂定位问题。蒙特卡罗定位 算法的定位精确性不受节点移动的影响，反而利用其移动性能提高定位的精度， 减小定位的代价，将该方法应用于无线传感器网络中，能够帮助解决移动节点的 定位问题。 1 3 研究内容 本文主要研究无线传感器网络中的移动节点定位算法，重点讨论了移动无线 传感器网络中的蒙特卡罗定位算法。 由于在后验密度分布取值较大区域中的样本数较少，利用蒙特卡罗定位算法 进行定位需要大量的采样才能取得较好的效果。对此，本文提出了一种遗传蒙特 卡罗定位算法。其主要原理在于将遗传算法理论中的交叉和变异两个操作引入到 蒙特卡罗定位算法中，对样本进行优化，使样本向后验密度分布取值较大的区域 移动，从而更好地表达后验密度分布。仿真结果显示，遗传蒙特卡罗定位算法可 以显著减少定位所需的样本数，具有更高的定位精度和更好的鲁棒性。 针对利用蒙特卡罗定位算法进行定位没有反映出锚节点对未知节点位置的 影响力的大小的问题，本文提出了一种加权采样蒙特卡罗定位算法。其基本思想 是在过滤阶段充分利用节点的移动性和多跳锚节点信息，由不同跳数的锚节点信 息过滤得到的样本使用不同权值，通过权值来体现锚节点对未知节点位置决定权 的大小，利用权值体现各锚节点对未知节点位置的影响程度，反映它们之间的内 在关系，即距离未知节点越近的锚节点对其位置的影响力越大，反之则越小。通 过这种内在关系的反映，来达到提高定位精度的目的。仿真研究显示，加权采样 蒙特卡罗定位算法具有很好的分布性、可扩展性和鲁棒性，特别是算法在定位覆 盖率等方面表现出了很好的性能，适合应用于大规模移动无线传感器网络。 1 4 论文结构 本文的主要工作是围绕着无线传感器网络移动节点定位算法这一课题进行 的，论文的结构安排如下： 第一章主要介绍了课题的来源，然后概述了课题的研究目的和意义，最后对 本文的研究内容和结构进行了说明。 第二章阐述了无线传感器网络移动节点定位的背景、测距技术、基本原理以 及性能评价指标，并综述了移动无线传感器网络的分类、移动节点定位算法和典 型的移动定位系统，重点综述了现有的蒙特卡罗定位算法。 移动无线传感器网络蒙特卡罗定位算法研究 2 1 引言 第2 章无线传感器网络移动节点定位 无线传感器网络是一个动态的网络，随时都可能有传感器节点因能量耗尽或 者损坏而停止工作，也可能有新的传感器节点进入到已有的无线传感器网络中。 而且传感器节点也可能由于人为的原因或者环境的改变导致其所在位置也随之 而改变，这就需要所设计的算法能够适应多种环境。 虽然有不少节点定位算法( 典型的算法有g p s f r e e 定位算法【、质心定位算 法【2 ，3 】、d v ，h o p 定位算法【4 ，5 l 和a p i t 定位算法】) 可以通过频繁地刷新位置估 计信息来应用于移动网络，但这些设计毕竟对节点的移动性没有任何考虑。在节 点移动的情况下，为了获得足够高的定位精度，需要增加定位计算的频率，将耗 费大量的通信和计算资源，极大地影响了算法的可用性。因此在传感器节点移动 的条件下，如何实现低成本、低功耗和高精度的定位，是面临的技术挑战之一。 2 2 定位背景 2 2 1 定位术语 本文涉及的节点定位术语如下： 1 未知节点：无线传感器网络节点定位技术中，把需要定位的节点称为未 知节点。 2 锚节点：而已经位置，并协助未知节点定位的节点称为锚节点。 3 邻居节点：在一个传感器节点通信半径内，所有可以直接通信的节点称 为该节点的邻居节点。 4 节点连接度：节点可探测发现的邻居节点数目称为节点连接度。 5 网络连通度：所有节点的邻居节点数目的平均值称为网络连通度，它反 映了传感器节点配置的密集程度。 6 跳数：两个节点之间间隔的跳段总数，称为两个节点之间的跳数。 7 跳段距离：两个节点之间间隔的各跳段距离之和，称为两个节点之间的 跳段距离。 2 2 2 定位概念 节点定位是指对于一组未知位置的网络节点，通过估计至邻居节点的距离或 邻居数目，利用节点间交换的信息，确定每个节点位置的机制。节点定位的目的 - 4 硕士学位论文 在于给定所有邻居节点对之间的距离测量值的基础上，计算出每个节点的位爱使 其与测距结果相一致。 每一个节点定位问题对应一个网络图，对于某些网络图，由于存在旋转、平 移和偏转因素，符合测距结果的坐标位置并不能够保证唯一性【扪。如图2 1 所示， 假设各边长即节点之间距离保持不变，如果要确定未知节点位置，则图2 1 a 1 是 全局固定的，图2 1 b ) 是部分固定的，其中有一个三角形可沿着边旋转，而图2 1 c ) 则是不固定的。 弧翰 a ) 全局瑚定的网络图b ) 部分崮定的网络图c ) 不固定的网络圉 图2 1 测距得到的网络形状 由于全局固定的网络图只有一种位置方式，即通过自组织方式，在给定边长 的条件下，得到节点唯一的位置布局。对于全局固定的网络图，要找出所有节点 的精确位置分配则属于n p - h a r d 问题。目前大多数节点定位算法允许定位误差在 一定范围之内，求解过程和结果是基本合理的。但对于图2 1 b ) 、图2 1 c 】两种情 形，目前尚未有成熟的解决方案。 2 3 测距技术 节点定位算法通常预先拥有节点与其邻居节点之间的距离或角度信息，因此 测距或测角是定位算法运行的前提。常用的测距和测角方法如下： 1 接收信号强度指示法 接收信号强度指示法【9 】通过信号在传播中的衰减来估计节点之间的距离。由 于信号在传播过程中信号强度会降低，已知发射节点的发射信号强度，接收节点 根据收到信号的强度，可以估计发射节点与接收节点的距离。 无线信道的数学模型如下： ，j 、 咒( d ) 一忍) 一1 帆l g i 手i 一以 ( 2 1 ) “o ， 式( 2 1 ) 中，d 是发射节点和接收节点之间的距离；也是参考距离；n 是信道 衰减指数，一般取值范围是【2 ，4 】；矗是均值为0 、方差为。的高斯随机噪声变量； 咒( 磊) 是距离发射节点如处的信号强度；脱( d ) 是距离发射节点d 处的信号强 度；脱( d 0 ) 可以通过经验得出，或者从硬件规范定义得到。由式( 2 1 ) 可以通过信 号强度忍( d ) 求出距离d 。 信道由于受到多径衰减和非视距阻挡的影响，具有时变特性，严重偏离上述 移动无线传感器刚络蒙特卡罗定位算法研究 模型，根据接收到的信号强度估计出距离d 会有很大的误差。 通过对的分析建立合适的噪声差模型，可以有效地补偿环境的误差。接 收信号强度指示法都集中在对噪声模型的分析和信号滤波。使用最小二乘法和卡 尔曼滤波器可以较好地滤除信号传播过程中引入的线性噪声，但滤除非线性系统 的噪声还没有统一的方法。 2 到达时间法n 达时间差法，往返传播时间法 在到达时间法【9 】中，已知信号的传播速度，根据信号的传播时间来计算节点 之间的距离。这种方法要求发射节点和接收节点是严格时间同步的。 到达时间法如图2 2 所示，已知毛时刻发射节点发送超声波信号，z 时刻接 收节点接收超声波信号。超声波信号的传播速度为v ，假设发射节点与接收节点 之间的距离为d 。 那么存在下列公式： d ( 五一瓦) y( 2 2 ) 发射节点接收节点发射节点接收节点发射节点接收节点 t 0 t l t 0 t 2 t l b t 0 t 3 t l t 2 图2 2 到达时间法图示图2 3 到达时间差法图示图2 4 往返传播时间法图示 在到达时间差法【9 】中，发射节点同时发射两种不同传播速度的信号，接收节 点根据两种信号到达的时间差以及已知这两种信号的传播速度，计算两个节点之 间的距离。 到达时间差法如图2 3 所示，己知发射节点在瓦时刻发送射频信号，随后在正 时刻发送超声波信号，两个信号向同一个方向发送，接收节点分别在王、e 时刻 接收到射频信号和超声波信号。射频信号的传播速度为咋，超声波信号的传播 速度为k 。，假设发射节点与接收节点之间的距离为d 。 那么存在下列公式： d ( 五一五) 一( l 一瓦) 】! 譬 ( 2 3 ) 时倨 由于发射节点在发送射频信号和超声波信号的时候有处理时间差，需要通过 精确的测量伍一瓦) 来补偿这个时间差，获得精确的距离。 在往返传播时间法【”】中，如果发射节点和接收节点属于不同的时钟域，可 以用计算往返时间、扣除处理延时的方法估计发射节点和接收节点之间的距离。 往返传播时间法如图2 4 所示，已知瓦时刻发射节点发送超声波信号，互时 硕士学位论文 过程，定位过程可分为两个阶段。 ( 1 ) 相邻节点之间方位角的测定 如图2 7 所示，节点a 的两个接收机r 1 、r 2 问的距离是l ，接收机连线中 点的位置代表节点a 的位置。将两个接收机连线的中垂线作为节点a 的轴线， 该轴线作为确定邻居节点方位角度的基准线。 在图2 8 中，节点a 、b 、c 互为邻居节点，节点a 的轴线方向为节点a 处 箭头所示方向，节点b 相对于节点a 的方位角是角z a b ，节点c 相对于节点a 的方位角是角么a c 。 在图2 8 中，节点a 的两个接收机收到节点b 的信号后，利用到达时间法 测量出r 1 、r 2 到节点b 的距离x 1 ，x 2 ，再根据几何关系，计算节点b 到节点 a 的方位角0 ，它对应中的方位角么a b ，实际中利用天线阵列可获得精确的角度 信息。同样在获得方位角么a c ，最后得到么c a b = 么a c 一么a b 。 节点b 围2 7 节点结构图示 ( 2 ) 相对锚节点的方位角测量 在图2 9 中，l 节点是锚节点，a 、 图2 8 方位角图示 b 、c 节点互为邻居节点。利用( 1 ) 计算 出a 、b 、c 三个节点之间的相对方位信息。假定已经测得锚节点l 、节点b 和 节点c 之间的方位信息，现在需要确定锚节点l 相对于节点a 的方位。 如上所述a a b c 、a l b c 的内部角度已经确定，从而能够计算出四边形 a c l b 的角度信息，进而计算出锚节点l 相对于节点a 的方位。通过这种方法， 与锚节点不相邻的未知节点就可以计算出与各锚节点之间的方位信息。 n i c u l e s c ud 等人就采用到达角法来确定传感器节点的位置【12 1 。到达角法易 受外界环境影响，且对硬件的要求较高，每个节点需要安装昂贵的天线阵列或超 声波接收器，不适用于大规模的无线传感器网络。 移动无线传感器网络蒙特卡罗定位算法研究 c 节点，l 与b 、c 不一定 互为邻居节点 图2 9 方位角测量 无线传感器网络中同一节点的感知距离与无线通信距离的范围可能有所不 同，也可能相等，本文讨论中假设两者近似相等。另外根据具体应用场景。同一 网络内的各传感器节点感知范围会稍有不同，而且同一节点随着能量的消耗，感 知距离也会随之减少。这些物理因素的变化以及测距的不精确性，都会影响定位 算法的定位精度。 以上测距和测角方法考虑的是如何得到相邻节点之间的观测物理量，有些定 位算法还需要通过间接计算获得锚节点与其它不相连节点之间的距离。通常此类 定位算法从锚节点开始有节制地发起泛洪，节点间共享距离信息，以较小的计算 量确定各未知节点与锚节点之间的距离。 2 4 定位原理 目前各种节点定位算法基于不同的定位原理，通常是利用节点之间的距离或 角度信息，少数则采用节点连接度信息或干脆不采用测距方法。根据节点之间的 距离或角度定位的方法可分为三类： 1 单边测量法 单边测量法是基于测距( 如接收信号强度指示法、到达时间法到达时间差 法往返传播时间法) 的结果。确定二维坐标至少需要三个未知节点至锚节点的 距离值；确定三维坐标则需要四个此类距离值。根据最小方差估计可求得解，当 矩阵不能求逆运算时，单边测量法则不适用，否则可成功得到未知节点的位置估 计。常见的单边测量法有三边定位法【9 1 和极大似然估计法【引。 二维空间中的三边定位法如图2 1 0 所示，已知a 、b 、c 三个节点的坐标分 别为( ，咒) 、( ，) 、( t ，y c ) ，以及它们到未知节点d 的距离分别为矗、以、吃， 假设节点d 的坐标为( z ，y ) 。 那么存在下列公式： 硕十学位论文 赣 e - i 三：乏；：芰：羹；】- l 薹：薹：薹：萎：墨：荔】 43 ( 2 7 ) ( 2 8 ) 圈2 1 0 三边定位法图示图2 1 1 极大似然估计法图示 二维空间中的极大似然估计法如图2 1 1 所示，己知l 、2 、3 、n 等n 个 节点的坐标分别为“，h ) 、( 屯，儿) 、( 弓，乃) 、( ，) ，) ，它们到未知节点d 的 距离分别为嘎、d 2 、以、以，假设节点d 的坐标为( 五) ，) 。 那么，存在下列公式： “一工) 2 + ( m 一) ) 2 - 砰 ； ( 矗一x ) 2 + ( 一y ) 2 - ( 2 9 ) f 砰一一2 “一) x + 砰一z 一2 ( m 一只) ) ，- 砰一 j ； ( 2 1 0 ) l 矗一一2 ( 靠，一毛) z + ) 0 。一露一2 ( 咒。一h ) _ ) ，一稚。一 a 憾 信号相位差法、 接收信号相位差法【1 0 l 通过测相位差，求出信号往返的传播时间，然后计算 硕l 学位论文 3 多边测量法 单边测量法的浮点运算量大，计算开销大，多边测量法则以新确定的未知节 点位置作为锚节点，再计算其它未知节点的位嚣。它是单边测量法和三角测量法 的扩展。s a v v i d e sa 等人提出一种简单的n 跳多边m i n m a x 算法【1 引，其主要思 想是各锚节点根据位置以及至未知节点的距离值，创建一边届框，所有边届框的 交集形成一个矩形，取此矩形的质心作为未知节点的坐标。 2 5 定位性能评价 无线传感器网络节点定位系统和算法的性能直接影响其可用性，如何评价它 们是一个需要深入研究的问题。下面定性地讨论几个常用的评价标准【1 4 】。 1 定位精度或定位误差 定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比 例表示，也有部分定位系统将二维网络部署区域划分为网格，其定位结果的精度 也就是网格的大小。 2 规模 不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一 个房间内实现定位。另外，给定一定数量的基础设旋或在一段时间内，一种技术 可以定位多少目标也是一个重要的评价指标。 3 锚节点密度 锚节点定位通常依赖人工部署或全球定位系统实现。人工部署锚节点的方式 不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性。而使用全球 定位系统定位，锚节点的费用会比未知节点高两个数量级，这意味着即使仅有 1 0 的节点是锚节点，整个网络的价格也将增加l o 倍。因此，锚节点密度也是 评价定位系统和算法性能的重要指标之一。 4 节点密度 在无线传感器网络中，节点密度增大不仅意味着网络部署费用的增加，而且 会因为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均 连通度来表示。许多定位算法的精度都受节点密度的影响。 5 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设 备。但在真实应用场合中常会有诸如以下的问题：外界环境中存在严重的多径传 播、衰减、非视距、通信盲点等问题；网络节点由于周围环境或自身原因( 如电 池耗尽、物理损伤) 而出现失效的问题；外界影响和节点硬件精度限制造成节点 问点到点的距离或角度测量误差增大的问题。由于环境、能耗和其他原因，物理 地维护或替换传感器节点或使用其他高精度的测量手段常常是十分困难或不可 移动无线传感器网络蒙特卡罗定位算法研究 行的。因此，定位系统和算法的软、硬件必须具有很强的容错性和自适应性，能 够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响。以提高定位 精度。 6 功耗 功耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节 点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的 计算量、通信开销、存储开销和时间复杂度是一组关键性指标。 7 代价 定位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系统的 安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算法所需的 基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一种定位系统或 算法的基础设施、节点设备的总费用。 8 定位覆盖率 定位覆盖率的含义是指网络中可实现定位的未知节点数在未知节点总数中 所占的比例，它是评价定位算法性能的另一个重要指标。尽管密集部署是无线传 感器网络的特点之一，但总会有一些不可到达或者网络连通度极低( 网络连通度 小于3 ) 的未知节点存在，除去这些节点，实现尽可能多的未知节点的精确定位 也是无线传感器网络定位系统和算法的追求目标之一。 9 刷新速度 刷新速度是指提供位置信息的频率。比如全球定位系统每秒钟刷新1 次对于 车辆导航已经足够，感觉上是实时服务。对于移动的传感器节点，位置信息刷新 慢，则会出现严重的位置信息滞后，直观的感觉就是已经前进了很长一段距离， 提供的位置还是以前的位置。因此，刷新速度也影响了节点定位系统或算法实际 工作中提供的精度。刷新速度还影响着位置控制者的现场操作，刷新速度慢，使 得操作者无法实旌实时控制。 上述九个性能指标不仅是评价无线传感器网络节点定位系统和算法的标准， 也是其设计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需 要完成。同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡， 以选择和设计合适的定位技术。 2 6 移动节点定位研究 2 6 1 移动无线传感器网络分类 无线传感器网络因其中节点所处环境不同、分布状态不同，其运动形式也不 同。有的无线传感器网络中的节点始终处于静止状态，有的无线传感器网络中的 硕上学位论文 节点偶尔运动，有的则经常改变自身的位置，还有的网络中的节点从布置开始到 网络生存期结束始终没有固定的位置。这些情况下无线传感器网络所表现出的特 征有许多不同点，针对各种情况而设计的算法也不同。因此，这些无线传感器网 络的存在形式决定了没有任何一种算法可以适用于所有的无线传感器网络的存 在状态。 根据传感器节点的移动情况，移动无线传感器网络可以进行如下分类： 1 个别节点移动 这种情况下无线传感器网络中的绝大部分节点处于静止状态，只有几个节点 移动。比如在监测动物生活规律时，只有布置在动物身上的传感器节点在移动， 其它传感器节点均处于静止状态。 在移动无线传感器网络节点定位问题中又可以细分为： ( 1 ) 仅未知节点移动 ( 2 ) 仅锚节点移动 ( 3 ) 未知节点、锚节点都移动 2 小部分节点移动 这种情况与个别节点移动的情况相似，只是移动节点的数目稍微多些 3 大部分节点移动 这种情况可能是节点都向一个方向移动，也可能是节点向各自的方向移动。 比如在监测轮船时，所有轮船上布置的传感器节点都向同一个方向移动；而在监 测轮船上乘客时，传感器节点则向各自的方向移动。 4 全网性移动 ， 这种情况下整个无线传感器网络中的节点都处于运动状态，直到生存期结 束。比如在监测河流流动时，向河水中洒入若干传感器节点，这些节点自抛洒时 起便一直随着河流运动，直到能量耗尽。 按照哪种类型的传感器节点移动进行分类，移动无线传感器网络又可以分 为： 1 未知节点静止，锚节点移动 这种情况下无线传感器网络中的未知节点始终处于静止状态，只有锚节点按 照自己的路线进行移动，这种移动可能是连续的也可能是不连续的，可能是向某 一方向的移动也可能是方向随机改变的移动。比如，在军事应用中传感器节点从 飞机上洒落到地面，而附加在战士或者动物身上的发射器作为可移动的锚节点 经过一段时间，随着每个未知节点接收到越来越多的锚节点信息，它的位置估计 应该变得越来越准确。 2 未知节点移动，锚节点静止 这种情况是锚节点始终处于静止状态，未知节点可能像1 中所叙述的锚节点 移动无线传感器网络蒙特卡罗定位算法研究 的运动方式那样在整个无线传感器网络覆盖区域内移动。例如，未知节点在一条 河中随着水流漂浮，而锚节点则固定在河岸边。 一个更具体的例子可以看n a s a 的m a r st u m b l e w e e d 项目i ”】。该项目提出 了一种探索火星上大范围区域的低成本方法。带有传感器节点的微尘在火星表面 随着风飘移，它们的运动极少甚至不受任何控制。当然，全球定位系统在火星上 不起任何作用。但它可以有助于建立有固定路标的锚节点，或者从人造卫星获得 位置。对于这类场景，每个未知节点的位置估计将会在当前实际位置周围波动， 随着时间流逝，由于未知节点已经移动，原来的位置信息变得不准确，但是随着 新的锚节点信息被获取，未知节点位置估计也得到了修正。 另外，我们参与的项目一“矿井无线传感器网络移动节点定位与动态轨迹跟 踪研究”的研究步骤为：首先在井下的坑道上布置传感器节点作为锚节点，然后 在井下矿工的矿灯上安装传感器节点作为未知节点，这些固定的锚节点和移动的 未知节点在一起就构成了一个无线传感器网络。当井下矿工携带这种具有传感器 节点的矿灯在井下走动时，通过定位算法，系统将会周期性地对矿工的位置变化 进行计算，将其位置信息通过无线传感器网络汇总到地面的中心处理站。显然， 这一项目的研究背景是属于未知节点移动，锚节点静止的情形。 3 未知节点和锚节点都移动 这是最普通的情况。这种情况相对比较复杂，也是本文所要重点讨论的情况。 它一般应用于这样一个场景：未知节点和锚节点都以a dh o c 的方式配置，或者 因为所处的环境因素( 风、水流等) 而移动，或者因为触发器而移动。 2 6 2 移动节点定位算法 针对移动传感器网络的节点定位算法要适用于所有的上述运动情况，并且兼 顾定位精度、功耗等性能指标是不太现实的，只有在强调某个方面的同时兼顾其 它方面 文献f 1 6 2 1 1 的研究中，仅考虑了单个锚节点的移动性。如图2 1 3 所示，有 一个单独的锚节点在无线传感器网络中运动，其余处于静止状态的未知节点根据 接收到的锚节点信息进行自身定位。 硕士学位论文 锚节点 未知节点 图2 1 3 仅单个锚节点移动示意图 文献【2 2 2 5 】的研究中，只考虑了多个锚节点的移动性。如图2 1 4 所示。有 多个锚节点在无线传感器网络中运动，其余在固定位置上的未知节点在接收到一 定的锚节点信息后进行自身位置估计。 锚节点 未知节点 图2 1 4 仅多个锚节点移动示意围 b e r g a m o p 和m 北z i n ig 的工作【2 6 1 ，仅考虑了未知节点的移动性，如图2 1 5 所示，假设无线传感器网络中有两个锚节点在固定位置且能在整个网络范围内广 播自己的位置信息，其余处于运动状态的未知节点根据接收到的信号强度进行自 身定位。他俩的工作没有利用移动性来改进定位，而是对于移动性对定位难度的 影响作了研究，指出随着未知节点速度的增加误差也相应增大。 锚节点 未知节点 图2 1 5 仅未知节点移动示意图 虽然还有一些算法具有不错的仿真结果，但它们是针对某种特定应用提出来 的，因此也只在这种特殊的应用环境下才有效。比如，l a d dam 等人用机器人 定位方法根据标准以太网卡接收的射频信号强度的变化，获得无线网络的精确定 硕4 l 学位论文 算法【3 4 ，3 卯，该算法通过定义锚节点盒子和样本盒子把采样区域限制在一个样本 盒子里，提高了采样的成功率，从而改善了定位效率和定位精度。但是当观测数 据分布在锚节点盒子的比重很小时，采样的成功率仍然很低。 如果蒙特卡罗定位算法定位过程中的样本数很少，并且没有包括表示正确位 置的样本，未知节点就不能够准确定位。为了克服上述问题，s t e v e n s n a v a r r oe 等人提出了一种对偶蒙特卡罗定位算法和一种混合蒙特卡罗定位算法【3 6 1 。对偶 蒙特卡罗定位算法的采样翻转了蒙特卡罗定位算法的采样过程，即蒙特卡罗定位 算法是先预测一个新位置，然后用观测数据去评估该样本的重要性，而对偶蒙特 卡罗定位算法先用当前观测数据去预测，然后结合以前的置信度去评估该预测， 采样过程正好与蒙特卡罗定位算法相反。混合蒙特卡罗定位算法是将蒙特卡罗定 位算法与对偶蒙特卡罗定位算法综合起来得到的一种更有效的定位方法。它结合 了蒙特卡罗定位算法与对偶蒙特卡罗定位算法各自产生样本的方式。仿真结果显 示，对偶蒙特卡罗定位算法和混合蒙特卡罗定位算法的定位精度都比蒙特卡罗定 位算法要高。 目前的蒙特卡罗定位算法都使用固定的样本 、 室内定位系统cricket系统【44，45】是麻省理工学院的oxygen项目的一部分，用 来确定移动或静止节点在大楼内的具体所在房间位置。该定位系统利用无线射频 信号与超声波信号到达时间间隔和各自的传播速度，计算出未知位置节点到已经 位置节鞘蜚旗弱，筵凌滚氍强舀卑碡编意缎稿两弱囊酷黢；塑嗣奄龋薹譬魏裂釜黧型箨。隰毽违滔硬嚣掣崖凛汤臻倒彳囊毳至画毫耩植茌旨? 罗定位算法中的粒子退化问题。混合蒙特卡罗盒子定位算法通过建立观测数据的 最小近似矩形和运动模型的最大近似矩形提高了采样的成功率，减少了无线传感 器网络节点的定位时 硕士学位论文 a c t i v eb a d g e 系统1 4 6 】给每一个目标安装一个b a d g e 。每个b a d g e 周期的每1 5 秒， 红外线发送大约持续o 1 秒的唯一标识号。已知位置的参考节点收到这些信号， 传送到网络，系统知道当前某个b a d g e 在哪个蜂窝单元附近。a c t i v eb a d g e 系统 的缺点是部署大规模网络困难，同时，红外线容易受到光线的干扰，尤其是在户 外。因此，a c t i v eb a d g e 系统是一个室内的基于蜂窝单元的定位系统。 2 7 小结 根据以上论述可知，每种移动节点定位技术都有各自的特点和适用范围，没 有哪一种是绝对最优的，关键是要满足应用的要求。 仿真显示，许多算法和系统的定位精度都还有很大的提高空间。无线传感器 网络移动节点定位问题的研究在今后的一段时间里仍然是无线传感器网络的一 个技术难点，也是关键点之一因此怎样综合考虑定位的性能指标，尽可能地使 性能指标达到最优是无线传感器网络移动节点定位技术的目标。 移动无线传惑器嘲络紫特卡罗定位算法研究 3 1 引言 第3 章遗传蒙特卡罗定位算法 蒙特卡罗定位算法不需要节点配备特殊的测距硬件，能够在存储非常有限、 锚节点分布密度较低的情况下实现无线传感器网络移动节点的定位，具有较高的 定位精度和运算效率。但缺点是定位需要大量的样本才能获得较好的效果，其主 要原因是蒙特卡罗定位算法中有很多样本落在了状态后验密度取值较小的区域 中，对未知节点状态估计的作用非常小。对此，本章提出了一种遗传蒙特卡罗定 位算法，该算法将遗传算法中的交叉与变异两个操作引入到蒙特卡罗定位算法 中，对样本进行优化，使样本向后验密度分布取值较大的区域移动，更好地表达 未知节点位置的后验密度分布，从而有效地减少了定位所需的样本数。 3 2 遗传算法介绍 遗传算法是近年来迅速发展的一种全新的优化仿生算法f 4 7 】。该算法源于六 十年代m i c h i g a n 大学教授h o l l a n dj 在研究机器学习过程中提出的一种随机搜索 方法。它的主要特点是简单、通用、鲁棒性强，适用于并行分布处理、应用范围 广 遗传算法的基本思想源于达尔文的进化论和孟德尔的遗传学说。它将问题域 中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式， 模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学 的操作( 遗传、交叉和变异) ，根据预定的适应度函数对每个个体进行评价，依据 适者生存、优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方 式来搜索优化群体中的最优个体，求得满足要求的最优解。 在对生物遗传与进化机理的模拟过程中，人们针对不同的问题提出了不同的 编码方法，在具体运行策略上，又开发了许多不同的遗传算子来执行遗传算法。 这些算法虽然在形态上多种多样，但是都具有一些相同的基本特征。把这些共同 的特征抽象出来，将这个具有所有类型遗传算法共性的算法，称之为简单遗传算 法。正如生物的遗传机理所述的那样，简单遗传算法可以看作是一切遗传算法的 父亲，其它各类遗传算法都可以通过简单遗传算法，加以适当的变形、改造而得 到。因此，把简单遗传算法放在这里单独讲述，作为对遗传算法的特征的基本抽 象，将有助于理解遗传算法的操作过程，进而容易实现算法、应用算法。 简单遗传算法的一般过程可以分为初始化、选择、交叉和变异四个阶段，其 硕十学位论文 执行流程图如图3 1 所示： 图3 1 简单遗传算法流程图 3 3 无线传感器网络遗传蒙特卡罗定位算法 否 3 3 1 蒙特卡罗定位算法介绍 蒙特卡罗定位算法的定位过程包括三个环节：初始化、采样环节和输出环节。 采样环节是蒙特卡罗定位算法的核心部分，它包括预测、滤波、重采样以及重要 性采样四个阶段。蒙特卡罗定位算法的流程图如图3 2 所示： 移动无线传感器嘲络蒙特卡罗定位算法研究 否 否 否 图3 2 蒙特卡罗定位算法流程图 实际上蒙特卡罗定位算法是按照提议密度分布采集样本，然后利用权值来补 偿提议密度分布与后验密度分布之间的差距。当后验密度分布与提议密度分布相 差很远时，在后验密度分布取值较大的区域中的样本数较少，需要大量的样本才 能较好地估计后验密度。 3 3 2 遗传蒙特卡罗算法思想 蒙特卡罗定位算法与遗传算法有些相似之处：它们都有一个样本集，每个样 本都代表一个可能解；这些样本都根据一定的规则进行状态转移；它们都对适应 度较高的样本进行复制，蒙特卡罗定位算法中的重采样阶段可以看作是样本的复 制过程。它们的主要区别在于状态转移的方式不同：遗传算法通过模拟生物遗传 进化中交叉与变异的思想实现样本的进化【4 8 l ；而蒙特卡罗定位算法中的样本根 据运动模型进行状态转移。 由于在后验密度分布取值较大的区域中的样本数较少，需要大量的样本才能 硕十学位论文 较好地估计后验密度，本章将遗传算法中的交叉与变异两个操作引入到蒙特卡罗 定位算法中，对样本进行优化，使样本向后验密度取值较大的方向移动，以克服 蒙特卡罗定位算法中存在的定位需要大量的样本才能获得较好效果的问题。我们 把这种改进的算法称为遗传蒙特卡罗定位算法。 3 3 3 遗传蒙特卡罗算法描述 假设时间分为离散的时隙。因为一个未知节点可能离开它原来的位黄，所以 它需要在每个时隙进行重定位。我们更关心的是获得一个未知节点可能位置的概 率分布。因为未知节点保持在无线传感器网络中运动，前一个位置信息己变得不 精确。由于未知节点与锚节点之间的通讯，以及未知节点和锚节点的计算都要花 费一定的时间，每次确定当前时刻未知节点的位置时，该未知节点已经在下一个 位置了。我们永远也无法通过传统的定位算法获得当前时刻未知节点的实际位 置，因此尽量准确地预测下一个或几个时刻未知节点的位置就显得至关重要 在状态空间中考虑未知节点的定位问题。令t 表示离散时间，f 表示节点的 通信半径，v 眦表示未知节点的最大运动速度，则未知节点运动速度随机分布在 【o 】内，表示未知节点在t 时刻的后验分布，d f 表示t 一1 时刻与t 时刻之间未 知节点接收到的来自锚节点的观测数据。转移方程p 化l ，) 描述了未知节点根据 上个时刻t 1 的位置对当前时刻t 的位置的预测，测量方程p “i q ) 描述了给定观 测数据q 后未知节点在位置处的似然度。的分布由样本集表示，中含有露、 矿、n 个元素。w 代表对应的权值， ：由彤表示，彤中含有一、砰、 n 个元素。 在预测阶段，未知节点不知道它的运动方向和运动速度，但是知道其运动速 度不超过某个最大值，因此如果t 。是某个未知节点在上个时刻t 一1 的一个可 能位置，那么该节点在当前时刻t 的可能位置就约束在以i ! _ ：- 。为圆心，v 雎为半径 的一个圆内。定义d ( 掣，如) 为掣和两点之间的欧几里德距离，则当前时刻未知 节点位置的概率可以由一个均匀分布给出： r1，、 p ( i k ) l j 乏d ( f f ，) 一( 3 1 ) l od ( c ，o ) 苫 当然，如果未知节点的运动模式是己知的( 比如，未知节点以某个特定的速 度运动或者沿着某个不变的方向运动) ，那么上述的概率分布就可以进行调整， 从而得到更好的预测结果。 2 5 移动无线传感器州络蒙特卡罗定位算法研究 o oo o o o o oo o o oo 节点的实际位置 o o o o o oo o o o o o o oo o o o o 圈3 3 实际节点与样本点 在滤波阶段，未知节点根据当前时刻接收到的新观测数据排除掉那些不可能 存在的预测位置。具体来说，在当前时刻t 每个处于锚节点通信半径内的预测位 置都能够侦听到来自该锚节点的广播，如果某个预测位置侦听不到广播，则表明 该位置是不可能出现的，因此应该丢掉。 o o o o o o o o 节点的实际位置 o o o o o o o o o o o o o 图3 4 滤波后的样本点 图3 5 显示了一跳和两跳锚节点下的滤波条件，这里两跳是指未知节点本身 不能侦听到某个锚节点，但是它的一个邻居节点可以听到此锚节点。令s 表示 未知节点能直接侦听到的所有锚节点的集合，t 表示未知节点无法直接听到但是 可以通过它的邻居节点听到的所有锚节点的集合，则滤波条件为： 一胁u ) i v s s ，d p ，s ) 量r v s e r ，r d p ，s ) s 2 r( 3 2 ) 如果滤波条件不满足，那么p ( i q ) 为o ，否则为1 。这就排除了那些与观测数据 不一致的预测位置。 o o o o o o o o 硕士学位论文 否 否 图3 6 遗传蒙特卡罗定位算法流程图 否 硕士学位论文 先从已设定的5 0 0 米5 0 0 米的正方形区域内随机选取一个点作为其目的地，然 后从【0 ，】或【0 ，】内随机选取一个值作为其运动速度，节点按此运动速度向 目的地运动，到达目的地之后，节点停留一段时间，然后选择下一个目的地，继 续运动。 3 锚节点密度岛：一跳通信范围内平均锚节点数。 4 节点密度几：一跳通信范围内平均节点数。 5 每次对未知节点进行定位所需的样本数n 。 用定位精度和计算开销来衡量定位算法的性能，其中定位精度用以往定位算 法中广泛使用的平均定位误差来表示。 3 4 3 仿真结果及分析 1 遗传蒙特卡罗定位算法的收敛性 考虑以下两种情况： ( 1 ) 锚节点静止( = o ) 、未知节点移动，= 5 0 米秒，劫= l ，= 1 0 ，n = 5 0 。 ( 2 ) 锚节点和未知节点都移动，= = 5 0 米秒，屯= 1 ，= 1 0 ，n = 5 0 。 图3 7 给出了位置估计误差随时间的变化曲线。由图3 7 可知，在初始阶段， 随着观测数据的不断增加，估计误差急剧下降：随着时间的推移，估计误差减小， 误差的变化逐渐变慢，整个系统基本达到了一个平衡，遗传蒙特卡罗定位算法也 逐渐收敛。从收敛的速度和定位精度来看，锚节点移动的情况要优于锚节点静止 的情况，这是因为锚节点静止的时候，未知节点在每个测量时刻侦听到的锚节点 信息变化不大；锚节点运动后，未知节点反而有可能侦听到更多的锚节点信息， 这意味着划分出的未知节点所在区域变小，定位精度的提高也就是自然的结论 了。 o51 01 52 02 53 0 时间秒 f j 痹稠 k 笪堇壶塾塾l 图3 7 锚节点分别在静止和移动情况下算法的收敛图 - 3 1 - 约 印 加 0 * 榭醛霹 移动无线传感器嘲络蒙特卡罗定位算法研究 2 锚节点密度对定位精度的影响 锚节点的增加使得观测数据增加，从而使未知节点的位置估计更加可靠，这 说明增加锚节点密度能够提高整个无线传感器网络中节点的定位精度。图3 8 为 位置估计误差随锚节点密度的变化曲线。其中，锚节点和未知节点都移动， s 一= v 腿= 1 0 米秒，嘞= 1 0 n = 5 0 。由图3 8 可知，三种定位算法的定位精度都 随着锚节点密度的增加而增加，并且当增加到一定程度后不再增加，达到了平衡。 遗传蒙特卡罗定位算法与其它两种定位算法相比能够快速收敛，并且在锚节点密 度较低时也具有较好的定位精度。 桨 j l | j 媸 露 o 11 12 13 14 1 锚节点密度个 + 遗传蒙特卡罗定 位算法 + 蒙特卡罗定位算 法 一质心定位算法 图3 8 锚节点密度对算法定位精度的影响 3 节点密度对定位精度的影响 图3 9 显示了位置估计误差随节点密度的变化曲线。其中，锚节点和未知节 点都移动，= = 1 0