非测距移动无线传感器网络定位算法

计算机科学2007V01．34N_o．9(专刊) 非测距移动无线传感器网络定位算法*) Range—FreeLocalizationinMobileWirelessSensorNetworks 魏叶华李仁发陈洪龙 (湖南大学计算机与通信学院 长沙410082) 摘要定位在许多无线传感器网络应用中都至关重要，提出了许多节点定位算法，但大部分算法假定网络是静态 的，移动无线传感器网络的定位研究相对较少。针对定位节点和锚节点随机运动的网络模型，结合无线传感器网络 的特点，提出了一种基于似然的自适应采样蒙特卡罗非测距定位算法，充分利用节点移动性和多跳锚节点信息，减少 抽样次数，提高采样效率。仿真结果表明，提出的算法与其它算法相比定位精度相当，但节点在不同最大运动速度 下，抽样次数相对平稳，同时抽样次数减少70％～90％，定位覆盖率最小提高了7％，最大提高了11％左右。 关键词无线传感器网络，定位，蒙特卡罗，非测距 随着无线通信和感器器技术的发展，产生了无 线传感网络(wirelesssensornetworks，简称 WSN)，作为一种新兴的网络技术，在诸如目标跟 踪、入侵检测、环境监控、军事国防、灾难救援、医疗 等许多领域都具有广泛的应用前景，通过部署大量 传感器节点至目标区域，进行信息的感知、处理与传 输，WSN将改变我们与客观世界的交互方式[1]。 在WSN的应用中，如环境监控、目标跟踪等，节 点位置至关重要，离开位置信息，感知数据是没有意 义的[2]，定位技术是无线传感器网络中关键的基础支 撑技术。此外，基于传感器节点位置信息的路由协议 可以提高路由效率，节约能耗[3]，增强网络安全性[4] 及实现网络拓扑的自配置[51等。而所有网络节点均 安装GPS接收器或者人工配置节点位置会受到成 本、效率等问题的限制，甚至在某些场合可能无法实 现，因此必须采用一定的机制实现WSN的自身定位。 目前面向不同应用，提出了许多测距、非测距的 定位算法，然而现有算法大多数假定节点静止的，既 静态无线传感器网络的定位。对于锚节点(已知位 置节点)、定位节点(未知位置节点)均可随机移动的 移动WSN定位研究较少L16|。由于节点的移动性， 增加了节点定位难度，现有静态网络的定位算法也 无法适应这一动态需求。本文针对移动WSN，根据 网络的连通性，利用多跳锚节点信息，提出了基于似 然的自适应采样蒙特卡罗非测距定位算法?使用指 数退避思想对不同跳数的锚节点集过滤所得的样本 赋予不同的加权值，样本总权值达到设定阈值停止 采样。仿真表明此算法保持一定定位精度前提下， 有效减少了抽样次数，从而可以缩短处理时间，节约 系统能耗。 本文第1节概括了WSN定位的相关研究；第2 节阐述蒙特卡罗定位思想；第3节提出了改进的蒙 特卡罗定位算法；第4节进行仿真分析，并与现有算 法进行比较；最后总结和展望。 1 相关研究 无线传感器网络定位成为了一个研究热点问 题，针对不同约束，提出了各种定位算法，大体分为 基于测距和非测距算法两类。测距算法[7~9]，定位 节点使用一定的测距技术，测量到锚节点距离，通常 至少需要三个测距信息，利用三边测量算法进行位 置计算。常用的测距技术有信号强度(RSSI)、到达 时间差(TOA)等。测距算法定位精度相对较高，但 增加了成本和能耗，对测距误差比较敏感，文[10]提 出了减小测距误差影响的优化算法。 非测距定位则无须距离和角度信息，仅根据网 络连通性等约束实现节点定位[11~13]，减少成本，同 时牺牲了定位精度。较为经典的算法如Belusu和 Heidemann提出的质心算法[12’，根据接收的锚节点 位置信息进行位置计算；DV—Hop[11]方法基于到锚 节点的跳数来计算距离，进行三边测量的位置计算， 文[19]使用RSSI技术增加了DV—Hop定位精度。 通常非测距定位需要较多的参考节点，通信开销也 比较大。 文[14，is]中，移动的锚节点周期性广播自己的 当前位置，定位节点接收到一定锚节点信息后：进行 位置估计。此类算法节约了实际锚节点使用数目， 增加了定位节点获取参考信息的概率，如同增加了 *)国家自然科学基金(No．60673061)：高等学校博士学科点专项科研基金(No．20060532024)。魏叶华博士生．研究方向为无线传感器网 络．嵌入式计算：李仁发教授、博导，研究方向为无线网络、嵌入式计算、数字化试验技术：陈洪龙博士生．研究方向为嵌入式中间件。 · 73· 虚拟锚节点，增加了定位精度。 目前，对于锚节点、定位节点均可移动的WSN 定位研究相对较少。由于节点的移动性，获取信息 容易失效，增加了定位困难，削减了定位精度，提出 了新的挑战。文E16]通过对文[17]研究，提出了基 于序列蒙特卡罗的非测距WSN定位算法，网络的 锚节点和定位节点可以无控制移动，取得了较好的 定位精度。但此方法使用固定数目采样，采样周期 长，开销大。为此本文在文116，18]基础之上，提出 了基于似然的自适应采样的蒙特卡罗定位算法，仿 真表明本文算法在保证一定定位精度的情况下，减 少了抽样次数，从而节约处理时间，减少了系统能 耗。第2节给出了蒙特卡罗定位思想的简要描述。 2蒙特卡罗定位思想 对于动态系统状态的递归估计问题，贝叶斯滤 波给出了一个概率框架模型，主要思想就是使用获 取的感知信息递归的估计动态系统状态空间的后验 概率密度。假定数据由顺序的离散时间索引的观测 值0。和控制测量值税。组成，则t时刻后验分布即信 度Bel(五)表示为[2川： Bel(x,)一声(五IOt，Ut一1，Ot一1，地一2，⋯，00，UO)(1) 依据控制测量值和观测值，递归的使用预测(公 式2)、更新(公式3)两个阶段获取状态的后验密度： BeZ一(z￡)·}JP(z￡132f—l，“￡一1)Bel(xf一1)dz￡一1 (2) Bel(x。)一ap(o。I．22￡)Bel一(zf)(3) 其中a是 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化常量，使得在整个状态空间信度之 和为1，p(x。I．27一，UH)为系统运动模型，表示输入 控制信息“一后状态变化，p(o。Iz。)为感知模型，表 示状态五下观测到0。的概率。 蒙特卡罗定位是基于粒子滤波的一种定位方 法，是贝叶斯滤波框架的实现，粒子过滤器与运动和 感知模型的结合，使用加权粒子集表示可能位置的 后验分布。L。一∽i=1，⋯，N)表示粒子集，在预测 阶段，使用LH，z{一1，地一，对P(z。Iz川，“川)进行 采样，得到新的粒子集L7。。更新阶段：根据新的观 测信息0。，使用感知模型对每个采样计算加权系数： 谢一P(o。∽)，对加权粒子集重新采样得到新集合 L。，以此近似表示t时刻的状态的后验概率分布。 3 自适应采样蒙特卡罗定位算法 此节首先描述使用的网络模型、节点感知和运 动模型，及相关假定，接着详细描述自适应采样的定 位算法。 3．1 系统模型 本文使用的系统模型与相关的假定： ①在WSN中，使用全向的、通信半径为r的理 · 74· 想圆周传输模型； ②锚节点、定位节点遵循Waypoint[191运动模 型，在部署区域内随机运动，最大运动速度为Vma，； ③WSN被构建成一个动态的离散时间系统，t 表示离散时间，l。表示节点在时间t时刻的位置分 布，0。表示在t一1到t时刻之间从锚节点获取的观 测信息； ④移动模型P(z。／zH)表示基于上一时刻位置 信息的节点当前位置的预测，感知模型P(o。／z。)表 示在节点位置为z。时得到观测值0。的似然； ⑤L。一{<∥’，叫。“’>i一1，⋯，N)表示粒子集， Wt“’为相应权值。 3．2算法描述 蒙特卡罗方法中粒子枯竭与计算复杂度是两个 主要问题。通过对文[16]仿真分析发现，文[16]提 出的方法采样效率不高，采样次数较大，容易出现样 本不足(采样次数达到了上限时有效样本数未达到 设定值)，在锚节点信息的使用上具有一定的改进空 间。本文提出了基于似然的自适应采样蒙特卡罗定 位算法，称作AMCI。(文[16]中算法称作MCL)，在 过滤阶段充分利用多跳锚节点信息，由不同跳数的 锚节点信息过滤得到的样本使用不同权值，当样本 总权和达到一定阈值，采样结束，进行加权位置估 计。算法描述见图l。 Initialization：Lo一{lo／ooq’)；／／初始化定位 节点，利用首次观测的锚节点信息 Step：／／使用上一位置集LH和新观测值0：计 算新的位置集合L。 1．Lf一{}；a=O； 2．while(口0)then 6． 口一口+Wt‘‘’； 7．L。一上吖U(1。‘。，姒‘‘’>； 8． endif； 9．forj一1⋯ndo 10． m“’一m“’／口；／／权值标准化，n为实际样本数 11．P。：一E讪“’厶“’；／／位置估计 图1 自适应蒙特卡罗定位算法 3．2．1预测阶段 此过程是对上一时刻的样本集LH中每个样本 lH“’利用运动模型声(z。／o。“!)进行更新。在定位 开始?粒子集为空，为改善在部署区域内进行样本随 机选择的不精确性?选取一锚节点作为参考点进行 初始采样。其它时刻中，因已假定节点作随机运动， 最大运动速度为‰。。，则￡一1时刻的可能位置 ￡川“’在￡时刻时的可能位置位于以￡H“’为圆心 zStv。，为半径的圆内．且当前可能位置的概率服从 如下均匀分布，其中d(1。，o，)表示两点的欧几里德 距离，At表示定位时间间隔： 础∥H，一』LO忑"b ifd(Z：，Z，1) 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 宋琛 移动无线传感器网络蒙特卡罗定位算法研究 2008 移动节点定位是无线传感器网络研究中的热点问题之一，它根据少数锚节点，按照某种定位机制确定移动未知节点自身的位置。现有的无线传感器 网络节点定位算法存在着测距方法受环境影响大、定位精度低和功耗大等问题，不适用于移动节点定位。随着无线传感器网络技术的不断进步和成熟 ，其应用将会越来越广泛，移动节点定位技术的研究对于移动无线传感器网络技术的性能提高和实用性保证有着重要的理论意义和应用价值。 蒙特卡罗定位方法是与机器人感知和运动的概率模型有关的粒子滤波，它能够有效并且鲁棒地解决复杂定位问题。蒙特卡罗定位算法的定位精确性 不受节点移动的影响，反而利用其移动性能提高定位的精度，减小定位的代价，将该方法应用于无线传感器网络中，能够帮助解决移动节点的定位问题 。 由于在后验密度分布取值较大区域中的样本数较少，利用蒙特卡罗定位算法进行定位需要大量的样本才能取得较好的效果。本文提出了一种遗传蒙 特卡罗定位算法，将遗传算法中的交叉和变异两个操作引入到蒙特卡罗定位算法中，对样本进行优化，使样本向后验密度分布取值较大的区域移动，从 而更好地表达系统的后验密度分布。仿真结果表明，遗传蒙特卡罗定位算法可以显著地减少定位所需的样本数，具有更高的定位精度和更好的鲁棒性。 此外，通过引入锚节点影响力概念，本文还提出了一种加权采样蒙特卡罗定位算法。加权采样蒙特卡罗定位算法充分利用节点的移动性和多跳锚节 点信息，用锚节点对未知节点位置的不同影响力来确定样本的权值，以提高定位精度。仿真研究显示，加权采样蒙特卡罗定位算法具有很好的分布性、 可扩展性和鲁棒性，特别是算法在定位覆盖率等方面表现出了很好的性能，适合应用于大规模移动无线传感器网络。 2.期刊论文 宋琛.罗娟.SONG Chen.LUO Juan 无线传感器网络移动节点的定位算法 -计算机工程2008,34(20) 针对无线传感器网络中节点移动性问题提出一种遗传蒙特卡罗定位算法.将进化理论中的交叉操作与变异操作引入到蒙特卡罗定位算法中,对采样进 行优化,使采样向后验密度分布取值较大的区域移动,从而更好地表达后验密度分布.仿真结果表明,该算法可以明显减少所需的采样数,具有更高的定位精 度和鲁棒性. 3.学位论文 孙正章 基于蒙特卡罗的无线传感器网络移动节点定位算法研究 2009 确定事件发生的位置或获取信息的节点的位置是传感器网络最基本的功能之一。随着无线传感器网络研究的深入，其应用愈加广泛，固定的网络结 构已无法满足新增应用的需要，移动节点的引入扩展了无线传感器的应用领域，同时也带来了技术上的挑战。目前，移动节点定位问题已成为无线传感 器网络的热点研究之一。 本论文首先论述无线传感器网络节点定位的基本原理，综述无线传感器网络自身定位算法、性能评价指标和分类方法，并对现有的基于蒙特卡罗定 位思想的移动节点定位算法进行了总结。接下来针对蒙特卡罗定位算法在后验密度分布取值较大区域中的采样数较少，算法需要大量的样本才能取得较 好定位效果的不足，提出了一种基于Voronoi图的蒙特卡罗定位算法(MCVD，monte carlo localization based on Voronoi diagram)。该算法利用两跳 范围内的锚节点集合所覆盖区域的几何中心去逼近待定位节点的当前位置，并对以逼近位置为中心的优化区域进行样本采集，使样本向后验密度分布取 值较大的区域移动，从而更准确地表达系统的后验密度分布。仿真结果表明，基于Voronoi图的蒙特卡罗定位算法能够有效抑制锚节点分布不均匀给定位 带来的负面影响，缩小了目标采样区域，具有更少的抽样次数和更高的定位精度。 本文还深入研究非锚节点特性，提出了一种临时锚节点的蒙特卡罗定位算法(MCBN，monte carlo localization boxed using non-anchor)。该算法 建立在蒙特卡罗定位算法基础之上，利用两跳范围内可信任度权值最小且坐标确定的静态非锚节点，辅助网络中两跳范围内的锚节点构建最小锚盒，同 时利用待定位节点上一时刻的位置信息和临时锚节点的特性增强样本过滤条件，进行快速抽样和样本过滤。仿真结果表明：MCBN同MCL、MCB和MCVD算法 相比，提高了节点定位精度，降低了节点能量损耗。 最后，对全文进行了总结，并对未来的研究工作进行了展望。 4.期刊论文 孙燕.尚军亮.刘三阳.SUN Yan.SHANG Jun-liang.LIU San-yang 基于采样优化的蒙特卡罗移动节点定 位算法 -系统工程与电子技术2010,32(9) 针对无线传感器网络中蒙特卡罗移动节点定位算法的不足,提出了一种采样优化的蒙特卡罗移动节点定位算法.该算法根据运动连续性,利用曲线拟合 方法,得出样本节点位置后验密度分布取值较大的区域,对该区域内样本节点的权值进行优化,从而完成未知节点的定位.仿真结果表明,改进后的算法能够 显著地减少定位所需的样本数,有效提高了无线传感器网络移动节点定位的准确性和鲁棒性. 5.期刊论文 谭红君 应用蒙特卡罗抽样法的无线传感器自定位信息融合技术 -中国新技术新产品2009(18) 我们首先介绍了无线传感器网络,对它的特点进行了分析,明白了网络传感器节点自定位的意义,接着介绍了目标比较常用的几种传感器自定位技术 .在此基础上,文章重点描述了一种基于信标节点的无线传感器自定位的分布式算法.在这个算法中,信标节点广播它的分布状态其中包括本身位置的信息 .邻近的未知位置信息的无线传感器利用传输的信息和接受到的信标信号的特征来估计自己的位置.知道自己的位置后,它也将成为一个新的信标节点.蒙 特卡罗抽样法被用来融合无线传感器的分布和获得无线传感器位置分布后验概率估值.我们也利用贝叶斯克拉马-罗下限来进行无线传感器的自定位和研 究信标预知位置信息和其他系统 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 的影响.我们通过计算机仿真分析我们算法的性能,并且与下限法得到的数据进行了比较. 6.学位论文 彭瑶 无线传感器网络的定位及路由协议研究 2008 近年来随着微电子技术、无线通信和低功耗嵌入式技术的飞速发展,孕育出了具有低功耗、低成本、分布式和自组织等特点的无线传感器网络,带来 了信息感知的一场变革。无线传感器网络的路由 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和传统的无线Ad-hoc网络有着很多不同,它的研究已经成为无线传感器网络研究的热点。此外,正是 由于无线传感器网络存在着与传统无线通讯网络相异的设计目标和网络环境,目前无线传感器网络路由协议的研究重点主要是放在如何提高能量效率上而 不是无线通讯的服务质量(QoS)上,因此如何设计出高效节能而又可靠的路由协议成为无线传感器网络路由协议研究的关键点。 本论文的主要研究对象是无线传感器网络的路由协议设计,目前关于此领域的研究已经提出了不少的算法和相关协议。这些协议彼此之间存在一定的 联系,也各有其优势。本文将研究重点放在了基于分簇的路由协议上,在路由协议中利用分簇技术可以提高无线传感器网络的可扩展性,其本地联合工作的 模式也在一定程度上减少了数据传递过程中的冗余信息和能量损耗。为了能更好的完成簇的划分以及优化簇首的选取,进一步均衡网络中节点的能量负载 ,本文还提出了一种新的基于蒙特卡罗的定位算法,节点利用从定位中所获得的位置信息,能够更好的在协议中实现优化路由的建立,达到平衡节点的能量 损耗进而延长网络生命时间的目的。此外,在本文所提出的分簇路由协议中均引入了簇间多跳和簇内重建模式,其目的是为了进一步的节省能量和提高协 议的可靠性。 本文首先系统阐述了无线传感器网络的结构特点及应用前景,论述了无线传感器网络目前研究的重点及热点问题。然后对无线传感器网络现有的路由 协议做了深入的研究,并重点分析了LEACH等分簇路由协议的原理及特点,提出了眼下无线传感器网络路由协议研究所面临的困难与挑战。最后,在学习和 总结前人研究成果的基础上,本文提出了两种适用于无线传感器网络的分簇路由协议。第一种协议利用节点获得的位置和能量信息,运用权值方式来进行 簇头的选取进而完成簇结构的建立；第二种协议首先运用定位所获得的位置信息来完成簇的划分,之后才由节点在本地簇内依照权值的方式来竞争簇首任 务。经实验结果证明,这两种协议都能够很好的平衡网络中所有簇的负载,并选取足够优化的节点来担任簇首,达到节省能量和提高效率的目的。最后对本 课题作了总结和进一步工作的展望。 7.期刊论文 魏叶华.李仁发.罗娟.陈洪龙.Wei Yehua.Li Renfa.Luo Juan.Chen Honglong 基于动态网格划分的移 动无线传感器网络定位算法 -计算机研究与发展2008,45(11) 定位技术是无线传感器网络中关键的基础支撑技术,目前提出了许多静态网络的节点定位算法,移动无线传感器网络的定位研究相对较少.针对定位节 点和参考节点随机运动的网络模型,提出了一个基于动态网格划分的蒙特卡罗定位算法.算法中当接收的参考节点数超过一定阈值时使用最远距离节点选 择模型,选出部分参考节点参与定位和信息转发,节约能耗.接着基于选择的或所有接收的参考节点构建采样区域,进行网格划分,使用网格单元数计算最大 采样次数,在采样区域内采样并使用误差补偿的运动模型进行过滤,提高了采样效率,减少了计算开销,并保证了较好的定位精度.仿真实验表明算法在定位 精度,计算开销、能耗等方面都具有较好的性能. 8.学位论文 李铁奇 无线传感器网络定位与信息采集技术的研究 2009 无线传感器网络是由部署在监测区域内大量的廉价微型传感器节点通过无线通信方式形成的一个多跳自组织网络。它以其低功耗、低成本、分布式 和自组织的特点，带来了信息感知的一场变革。无线医疗监护定位系统则是借助于无线传感器网络并结合现代计算机技术所进行医疗监测的手段。系统 可以实现对病人各种信息的采集处理。进入21世纪以来，无线传感器网络技术作为通信技术是未来发展的重点之一，以其廉价、便携、通用的特点，在 国计民生各领域中得到越来越多的使用。 本文首先研究了无线传感器网络的各种经典定位算法，分析了对各种算法中的优缺点，指出了这些传统的定位算法不能够很好的实现移动定位。在 此基础上，本文提出了一种基于蒙特卡罗的无线传感器网络移动定位算法。此算法不同于传统的蒙特卡罗方法，它可以在使用很少的锚节点情况下实现 精确的移动定位，而且对于锚节点较密集的情况也同样能够实现精确的定位。实验结果证明该算法在定位精度、定位效率等方面优于传统的蒙特卡罗移 动定位算法，可以较好的实现对患者的行踪进行跟踪定位；其次针对无线医疗监护定位中的信息采集问题，提出了一种高效节能的数据融合算法。算法 采取分布式的数据融合方法，分别对源节点和汇聚节点进行数据融合处理。在源节点采用一种自适应数据融合办法对数据进行处理，然后在汇聚节点进 行节能动态管理。通过实验比较可以得出，此算法对于解决无线传感器网络数据融合中的能量消耗过大的问题具有一定的帮助；最后，本文采用 ZigBee技术实现了一种无线医疗监护定位系统。系统能够实现对患者的移动定位，并且预留了各种检测生理参数的接口，对于解决现代医疗监护的实时 监测问题有一定的借鉴意义。 9.期刊论文 黄中林.邓平.HUANG Zhong-lin.DENG Ping 基于自适应采样的移动WSN定位算法 -通信技术 2010,43(11) 节点自定位是无线传感器网络的关键技术之一.当前对无线传感器网络定位的研究主要集中静态节点定位,移动无线传感器网络定位研究相对较少.研 究了基于序列蒙特卡罗方法的移动无线传感器网络定位.针对蒙特卡罗定位采用固定样本数,计算量大的缺点,根据蒙特卡罗定位盒(MCB)算法的锚盒子大 小动态设置样本数,提出一种自适应采样蒙特卡罗盒定位算法.仿真表明,该算法在保持定位精度的同时有效地减小了采样次数,节约了计算量. 10.期刊论文 邵清亮.张振川.张芝贤.Shao Qingliang.Zhang Zhenchuan.Zhang Zhixian 基于蒙特卡罗算法煤矿井 下人员定位研究 -计算机应用与软件2009,26(4) 对比分析几种常用的无线传感器网络节点定位方法.针对煤矿井下节点移动性可能导致普通的定位算法变得不精确,提出了蒙特卡罗定位(Monte Carlo Localization)算法.该方法利用物体运动的连续性,通过选取合适的模型完成移动节点位置预测与定位.经仿真验证在低密度锚节点环境下,蒙特卡 罗方法位置估计误差明显低于其它方法,提高了移动节点定位算法的准确性. 本文链接：http://d.wanfangdata.com.cn/Conference_6570414.aspx 授权使用：北京邮电大学(byab)，授权号：a6d1472f-60b3-4a1f-a0c9-9ea3010da348 下载时间：2011年3月11日