移动定位算法（精选11篇）
移动定位算法 篇1
1 概述
无线传感器网络WSN (wireless sensor networks) 由大量成本低廉的, 能够与外界环境交互的传感器节点组成, 它能够运用在人类与环境健康状况的监测, 工业生产控制, 化学物品、生物制剂威胁与泄露的侦查, 自然灾害的营救等多方面。然而, 大多数应用场合, 确定传感器位置才能使感知的数据有实际意义, 传感器节点需要明确自身的位置才能提够实现对目标的跟踪和监测[1]。节点定位技术成为无线传感器网络的关键技术。利用少量已知位置的节点 (采用GPS定位或者预先配置) , 通过定位算法, 来实现对节点的定位。已知位置的节点称作锚节点 (anchor) , 未知位置的节点称作未知节点, 需要被定位。
2 移动定位算法的研究
目前存在的定位算法, 可以分为三类:基于距离的 (range-based) 定位, 距离无关的 (rangefree) 定位, 传感器网络的移动定位算法。基于测距的定位算法能够实现高精度的定位, 但需要额外的硬件设备测量距离或角度, 对大规模配置传感器节点的无线传感器网络是不合适的。距离无关的定位成本低, 但定位精度低, 且存在无法定位的盲点, 很大程度上依赖锚节点的配置状况。如果锚节点或者未知节点处于移动状态, 则无法使用这些方法进行定位, 提出了移动定位技术。
由大量未知节点与少量锚节点组成的传感器网络, 其移动性表现分为三种情形: (1) 未知节点与锚节点都是移动的。自组织网络 (ad-hoc) 就是一个典型的网络; (2) 未知节点静止, 锚节点是移动的。比如:Spotlight System, 未知节点是从飞机上抛洒下来, 随机分布在监测区域。节点配置之后。飞机上安装了一种Spotlight的设备作为锚节点, 飞机从检测区域飞过并产生光事件, 未知节点检测事件, 并将检测的时间返回给Spotlight的设备。Spotlight的设备就可以计算未知节点的位置。 (3) 未知节点移动, 锚节点静止。
2.1 Monte Carlo Localization (MCL) 算法[2]
MCL算法分为三个阶段:第1段基于前一时刻的抽样与未知节点的移动, 使用一个移动模型来预测它当前的可能位置;第2阶段, 未知节点根据从锚节点获得的新信息, 使用一种过滤机制来消除与当前位置不一致的预测位置;第3阶段, 为使抽样数在设定的门限值之上, 需要再进行抽样。
2.1.1 预测阶段。
假设时间被划分为离散的时间单位, 那么节点在一个时间单位移动的距离可用其移动速度来表示。假设未知节点仅知道移动的速度在[0, vmax) 内的任意值, 不能超过最大值vmax, 而不知移动的方向。节点在t-1时刻可能的位置分布为lt-1, 则在t时刻可能分布lt是以lt-1为圆心, vmax为半径的圆形区域内。d (l1, l2) 表示节点l1与l2的Euclidean距离。则当前位置的概率分布为:
也就是说, 当d (lt, lt-1) 小于vmax时, 则当前位置以等概率分布于以lt-1为圆心, vmax为半径的圆形区域内的任意一点;当d (lt, lt-1) 大于vmax时, 则节点移动的速度太快, 前一时刻的位置分布已经没有了参考价值。
2.1.2 过滤阶段。
在这阶段, 基于新的观察结果, 节点会过滤不可能的位置信息。如图1所示, 锚节点时刻0在位置l0, 时刻1移动到位置l1, 对黄色区域I的未知节点来说, 在时刻0能监听到, 时刻1无法监听到, 它是离开的锚节点;对绿色区域II的节点来说, 时刻0无法监听, 时刻1能监听, 它是刚到达的锚节点;对黄绿重叠区域III节点而言, 时刻0和1都能监听到, 它是内部锚节点。刚到达的和离开的锚节点能提供最有用的信息, 因为节点知道自己在当前时刻处于某个锚节点的传输范围内而不处于其它锚节点的范围内。仅仅从锚节点的当前时刻收获的信息是不够的, 还需要获取其它的信息。
图2显示了过滤机制。在锚节点发射距离r范围内的未知节点能够直接监听到它的信息;而在 (r, 2r]范围内的未知节点无法直接监听到锚节点的信息, 但未知节点的某个邻居节点可以监听到锚节点的信息, 这个锚节点为间接锚节点。N为预测阶段获得的某个未知节点可能的位置信息。S为能被N监听到的所有锚节点。T为能被N的邻居节点监听到而自己无法监听到的锚节点。则过滤机制为:
如果filter (l) 的值为假, 即两个无交集, 基于观察的位置概率分布为0;否则可以获得基于观察值的概率分布p (lt|ot) 。因此, 通过观察, 可以消除与预测阶段不一致的位置信息。在过滤阶段之后, 可能的位置信息少于N个, 就需要重复这两个阶段, 直到至少有N个可能位置信息获得。
实验表明锚节点、未知节点的速度越快, 越易达到稳定状态, 因为节点的快速移动, 可以获得更多的锚节点的信息, 过滤掉不准确的信息。因此, 节点的移动提高了定位精度。仿真结果也证实, 它的定位精度比质心算法、Amorphous算法高。
2.2 MSL*的定位算法[3]
这个算法能运用在传感器的移动网络和静态网络中。在MSL*算法中, 为每个节点维持了一个可能的位置集, 即抽样。抽样的质量以加权值 (weights) 来衡量.直观上讲, 一个抽样的加权值就是在邻居节点估计位置给定的情况下, 这个抽样接近未知节点真实位置的可能性近似值。MSL*算法的定位主要有以下几个步骤:
(1) 初始化。在定位的初期, 节点没有关于它位置的任何信息, 每个节点的第一批抽样值是从整个传感器区域内随机选择的;节点仅仅从直接邻居节点的锚节点中获得信息。
(2) 抽样。节点可以使用下面的转换方程产生新的抽样。
vmax是节点移动的最大速度, d (St, St-1) 表示节点在t与t-1时刻的距离。在每个时间单位中, 一个新的抽样是以当前抽样值为圆心, vmax+α为半径的圆形区域内的任意一点。在选择了抽样值之后, 其加权值由邻居节点的信息而决定。假设未知节点p的一个抽样s的加权值为ws (p) , 它的邻居节点为q, q的加权值ws' (q) , 则p的加权值是所有邻居节点的加权值之和。k是节点p的一跳和二跳的所有邻居节点, 即为:
如果节点p的加权值ws (p) 大于设定的门限值, 则此抽样保存下来。
(3) 再抽样。再抽样就是逐渐移出低加权值的抽样点, 而留下高加权值的抽样点。在这个阶段, 每个节点都要从当前抽样集中计算出新的抽样集。抽样数保持固定, 小的加权值的抽样点被再次选中的概率低。大的加权值的抽样点选中的概率高。在新的抽样集中存在许多与前一次相同的抽样点。
仿真结果显示, 节点的移动能够提高定位的精度, 因为移动的节点可以获得更多的锚节点或者邻居节点的信息。但不是越快的速度, 定位精度越高, 因为过快的移动, 前一时刻的位置信息将不再有用, 定位差错就增加。最大速度vmax为半径的0.2倍时, 定位精度最高。
2.3 移动定位算法的比较
以上讨论的四种算法都是分布式的定位算法, 具有良好的扩展性。MSL*算法是MCL算法的基础上延伸的算法, 但又做了些改进, 表现为: (1) 每个节点筛选了获得信息的渠道, 是从具有更好位置估计的邻居节点, 通过节点的加权值来实现。这种改进即使在节点的低速运动或者低锚节点密度的情况下, 也能实现快速收敛, 提高定位的精度; (2) MSL*算法改进了节点的抽样过程, 抽样点的加权值必须高于某个门限值。这就使得定位差错更快的收敛, 有更快的执行时间, 在移动传感器网络获得更好的位置估计。“用移动锚节点进行定位的算法”是“移动锚节点定位算法”的升级版本。前者在继承后者定位算法的基础上, 使用迭代求精, 通过Levenberg-Marquardt数学方法来优化获得的信息, 实现了更精确的定位。MLS*和MCL能够运用未知节点和锚节点都是移动的无线传感器网络中。
3 结论和展望
传感器网络的定位技术在遭遇基于距离的定位技术的高成本, 与距离无关的粗糙定位的瓶颈之后, 人们开始使用新的方法来获得精确的定位, 那就是移动节点定位技术。详细地介绍了几种新型的移动节点定位算法, 分析比较了几种算法的性能。边界锚节点的确定是获得精确定位的关键。因此, 如何准确地确定边界锚节点将是以后研究的关键。在这些定位算法中, 都没考虑定位的安全性, 将这些算法中添加一些密匙之类的安全措施, 实现安全定位也是算法研究的一个重点。
摘要：基于距离和距离无关的两种定位算法, 在无线传感器网络应用中, 有各自的局限性, 而移动节点定位技术较好的弥补这些缺陷。详细阐述了几种新型的移动定位算法的原理和特点, 分析了它们的性能, 并指出了未来研究的重点。
关键词：无线传感器网络,移动定位算法,定位精度
参考文献
[1]任丰原, 黄海宁, 林闯.无线传感器网络[J].软件学报, 2003, 14 (2) :1148-1157.
[2]L.Hu, D.Evans, Localization for mobile sensor networks[J].MobiCom, pages, 2004:45-57.
[3]M.Rudafshani, S.Datta, Localization in wireless sensor networks[C].IPSN'07, USA, 2007.
移动定位算法 篇2
星载测向定位滤波算法研究
为了有效改善运动状态中辐射源测向定位精度,并进行实时定位,根据星载正交干涉仪测向和定位技术原理,对星载测向过程中存在的系统指向误差进行了数学建模.引入了扩展卡尔曼滤波技术,通过最优估计值为标称值对测向系统非线性模型的.线性化处理,采用状态空间递推方法来进行实时估计,从而对测向随机过程进行实时最小方差估计;建立了地理位置推算的扩展卡尔曼滤波具体实现算法.仿真给出了一组典型的系统误差和位置误差滤波推算结果曲线,表明提出的扩展卡尔曼滤波模型和算法的正确性,达到了可纠正系统误差,改善辐射源地理位置估计值的效果.
作 者：李文华 陆安南 LI Wen-hua LU An-nan 作者单位：江南电子通信研究所,浙江,嘉兴,314033刊 名：计算机仿真 ISTIC PKU英文刊名：COMPUTER SIMULATION年，卷(期)：201027(5)分类号：V474.2关键词：正交干涉仪 测向 定位 扩展卡尔曼滤波 仿真
慎用定位服务，注意移动安全 篇3
想必在这之前，很少有人真正正确认识到智能手机上“定位服务”这一功能的威力。定位服务能够通过 GPS 定位您所在的位置。许多可下载的应用要求使用您的“位置”信息来为您提供周边的咖啡馆、餐馆、优惠券信息或让您签到，用户大都是通过这些应用才了解到定位服务的便利。
而这一项功能所带来的便利常常会让人忽略其潜在的风险。在孩子们使用定位服务之前，家长有责任教导他们遵循一些安全做法，避免暴露过多的个人信息，给自己带来安全威胁。以下是安全专家就定位服务提供的一些安全建议：
如果常用的应用不需要使用“定位服务”，请在手机的“设置”选项中彻底关闭该服务。
与孩子们讨论“签到”做法的安全性，以及是否有必要这样“签到”。
与孩子们一起审查隐私设置。彻底检查孩子们的所有移动应用的“设置”选项。有时候，孩子们在下载应用时已经选中了“允许定位服务”，但他们并未意识到这一点。
花一些时间审查一下孩子们的好友列表，并向他们询问是否认识可查看其帖子的所有人。
检查是否有某个公共账户关联到多个社交网络（比如现今微博、豆瓣等多个社交平台都可相互绑定）。审查每一个帐户的隐私设置，是否存在向认识的好友公开的关联帐户。
采取进一步的措施。 确保孩子们的移动设备受到适当的过滤软件的全面保护，这是不影响“定位服务”功能又能确保移动安全的明智做法。
移动定位算法 篇4
近年来,无线传感器网络技术及应用迅速发展,由于其节点成本低、功耗小、系统稳健、组网灵活,得到业界的广泛关注。清华大学提出城域感知与运营网络(Metropolitan Area Sensing and Operating Networks,MASON)概念,面向城市环境信息采集应用,在大空间尺度上部署传感器节点,通过节点移动性和动态组网扩展信息采集范围和传输效率。
在城市无线传感器网络应用中,传感器节点的位置信息十分重要[1,2],在生态环境监测、自然灾害的现场监控等应用中,传感器节点所发回的物理信息数据要有意义,就必须与其地理位置相关联,从而使上层得到信息来源的准确位置,有时甚至需要传感器节点发回单纯的位置信息[3,4],例如,在目标跟踪应用中,传感器节点通过监测所跟踪目标的移动速度,在知道其所在位置的情况下,用特定的分析算法,计算目标当前的运动轨迹并预测未来的移动路线。此外,节点位置信息还可以为其他协议层的设计提供帮助。在应用层,节点位置信息对基于位置的信息服务应用至关重要,同时,位置信息还可以提供整个网络对物理空间覆盖质量的评估;在网络层,位置信息可以帮助路由算法得到更好的性能,提高路由效率,实现网络的负载均衡和网络拓扑的自配置等;在城市环境的无线传感器网络的监测、跟踪、预警等应用中,传感器节点所发回的空气、水体、噪声、天气、交通、安全等意义信息都需要信息来源的准确位置来支持,因此,需要研究高效的定位方法来确定传感器节点的位置信息[2]。
由于传感器节点的位置信息在应用中的重要作用,节点定位成为了无线传感器网络的主要研究方向之一。由于传感器节点通常是用随机的方式部署到监测区域中的,因此预先确定节点的部署位置比较困难,只能在部署完成后,通过一定的技术手段获取节点的绝对地理坐标或相对位置信息。当前,最普遍使用的定位系统是全球定位系统(Global Positioning System,GPS),但是由于其需要单独的定位芯片组,成本开销和功耗较大,只适用于室外开阔地带,不适于低功耗、低成本、大规模的无线传感器网络。在机器人研究领域,目前也有很多关于定位的研究,但是由于该领域算法一般不关心计算复杂度,同时需要有特殊的硬件设备支持,所以在无线传感器网络中也不能方便地应用[5]。
无线传感器网络定位机制根据其应用不同可以分为两类:第一类是针对静态网络拓扑的定位机制,其又可细分为基于距离(Range-Based)的定位算法和距离无关(Range-Free)的定位算法[6,7]。基于距离的典型定位算法有到达时间TOA的定位、到达时间差TDOA的定位、到达角度AOA的定位和接收信号强度指示RSSI的定位。距离无关的典型定位算法有质心算法、距离向量-跳段DV-Hop算法、Amorphous算法和近似三角形内点测试APIT算法;第二类是针对可移动网络拓扑的定位机制。典型的有利用移动GPS和路点(Way Point)的路径预测算法[8]和利用GPS的蒙特卡洛定位(MCL)方法[9,10,11]。这两类定位机制都要求传感器节点之间可以直接通信,即依赖于网络拓扑的密集性。由于无论是静态网络拓扑,还是可移动网络拓扑,其定位机制通常都依赖于3种最基本的方法[1]:三边测量法、三角测量法和极大似然估计法。这3种方法有效的最基本的前提就是传感器节点之间可以直接通信,对于存在移动节点缺乏连续的网络连接性的稀疏、延时容忍网络(Delay Tolerant Networks,DTN),这些基本方法不能够直接使用。
由于城市无线传感器网络的规模大、覆盖面积广、节点间距离较远,一般互相不在彼此的通信半径之内,整网的拓扑是稀疏且短暂互联的,数据传输要依赖于节点的移动性,是一种延时容忍网络,故传统的无线传感器网络定位机制在城市传感器网络中不能够直接使用。另外由于城市无线传感器网络节点的大规模和稀疏性,从成本、可扩展性和易用性的角度考虑,在节点上配备GPS设备、加速度传感器或任意其他跟测量相关的硬件都是不可取的。因而,有必要设计特殊的定位算法,以解决这类网络中的定位问题。
笔者考虑城市无线传感器网络低成本、低能耗、节点数量众多和强延时容忍等特性,提出一种可应用于城市移动无线传感器网络的新定位算法,该算法不需要任何其他附属的硬件设备就能完成定位,分析其收敛条件,通过仿真验证,给出误差分析。
2 系统模型
根据不同类型节点对定位的不同作用,城市无线传感器网络可分为以下3类:
1)信标节点(Anchor)。数量较少,地理位置信息已知,可与接近它的移动节点交换信息,一般在无线传感器网络中负责信息汇集的作用。
2)传感节点(Sensor)。随机布撒,数量非常多,地理位置信息未知但位置保持不变,需要定位,可与接近它的移动节点交换信息。
3)移动节点(Carrier)。被车辆携带,从而在网络中移动,其地理位置信息未知且经常变化,可与路过的临近的信标节点和传感节点交换信息。
在城市无线传感器网络中,由于网络的稀疏性,无法直接通过测距、测角等基本方法来设计定位方法,但可以得到网络节点的其他信息,如移动节点的最大移动速度、信标节点的位置等[8,10],因而可以结合多节点协同[12]的方法来帮助定位。另外由于其延时容忍特性,还可以通过大量的观测得到城市环境下车辆流(Traffic Stream)的运行轨迹和统计学特性的经验统计模型,根据经验统计模型来给移动节点建立概率移动模型,在此基础上,应用统计学的方法,可以实现位置保持不变的传感节点的定位。
文献[13]在分析了车辆运行统计模型的基础之上,提出了曼哈顿格(Manhattan Lattice,ML)模型。ML模型在不失本质和普遍性的前提下模拟了大量车辆同时在城市中运行的统计学规律。笔者在有关Torus环结构的研究成果[14]下把该模型加以改进,并结合城市无线传感器网络的系统,形成了适用于城市无线传感器网络定位算法分析的曼哈顿环(Manhattan Torus,MT)模型。该模型使得针对城市无线传感器网络的理论和仿真分析更加容易,具体表述为:假设移动节点在n×n的MT图的边上自由行走在每个交叉点以一定的概率选择右转、前行和左转中的任意一种,如图1所示,其中图1a表示MT图,在Torus环的基础上加入了网格Lattice,图中两条粗线分别标示区域分块的长度和宽度。图1b表示车辆的行走方式,其在MT图的所有边上都是自由行走的。图1c则表示了移动节点在交叉点处的方向选择。
移动模型的基本假设:
1)所有移动节点的移动在图上满足MT模型,并在每个计时时刻以一定概率选择在下一个时间间隔内右转、前行或左转。每个计时时刻内的移动距离相当于MT图中一个短边的距离,设为1(称为一步)。
2)所有信标节点和传感节点均不重叠地位于各个交叉点上。事实上,如果传感节点与信标节点重叠,显然该传感节点已无需定位。
3)信标节点的数量和位置已知,传感节点则在交叉点上随机布撒。
4)移动节点与信标节点或传感节点的通信只能当它们位于同一个点上的时候才能进行。
3 定位算法
在上述移动模型的基础上,设计了一种基于位置概率分布收敛原理的定位算法,其基本原理为:每一个节点都维护了对自身当前位置的估计,以概率分布的形式表现。当两个节点相遇时,双方通过短距离无线通信信道,交换其对当前位置估计的概率分布,并根据两个概率分布函数计算新概率分布,以更新对当前位置的估计。直观上,由于网络中存在位置已知的固定信标节点和数目众多的移动车辆,这个方法可以通过车辆的移动定位大量随机布撒而位置未知的传感器节点。
在n×n的MT图中,概率分布可以表示为n2维向量的形式。由于移动节点无法直接获知自身移动方向,每移动一步,其概率分布区域随之扩大,由每一个点扩散到MT图中以该点为中心的周围5个点上。两节点相遇时,将双方的概率分布相乘后归一化,得到新的概率分布,完成概率更新。新的概率分布为
式中,pA和pB分别表示概率更新前的A,B节点位置的离散概率分布,是n2维向量。pA′和pB′则分别表示概率更新前的A,B节点位置的离散概率分布,也是n2维向量。pA×pB表示pA和pB对应元素相乘,其结果为n2维向量,分母pA·pB表示pA和pB的内积,是归一化因子。据此提出定位算法,如图2所示。
该算法的收敛性要依赖于信标节点的数量和位置,下面对其进行初步的分析。
由于直接分析二维MT的收敛情况比较困难,先讨论一维和二维ML图的收敛情况,并利用ML图的方法和结论,引出对MT的收敛性的证明。
1)已知节点间距离,对一维ML图定位,需要至少2个信标节点。如果网络中没有信标节点,则只能知道节点的相对位置信息,不能获得节点绝对位置坐标,因而至少需要1个信标节点。又因为若整个图以唯一信标节点为轴心旋转,可以在保持相对位置不变的前提下,改变节点绝对位置,所以至少还需要1个信标节点来消除旋转。事实上,以图中任意两点所成直线为轴的镜像都不能改变绝对位置。
2)至多3个信标节点可以保证一维ML图的收敛。对于一维n格ML图[13],如果n为偶数,则只需要2个信标节点占据一维ML图的两端,就能保证全图收敛;如果n为奇数,采取奇偶分解的方法,将一维ML图分解为n-1格和另外1个格,n-1格为偶数,需要2个信标节点,另外1个格子需要1个,在这种情况下,共需要3个信标节点就能够保证收敛。
3)已知节点间的距离,对二维ML图定位,需要至少3个信标节点。由2)可知,至少需要2个信标节点来消除旋转。又因为整个图是以这2个信标节点为轴的镜像翻转,可以在保持相对位置不变的情况下,改变节点的绝对位置,故还需要1个不在这2个信标节点所成直线上的信标节点来消除镜像。对于二维ML图,至少需要3个信标节点消除旋转和镜像。
4)至多9个信标节点可以保证二维ML图的收敛。对于二维n×m格ML图,如果n与m均为偶数,则由3)可知,只需要在ML图的四角放置4个信标节点就能保证最外围节点的点点收敛,而最外围节点的收敛又保证了中央所有节点的收敛;如果n和m不全为偶数,则仍采取奇偶分解的方法,这里仅以最复杂的n和m均为奇数的情况为例,将ML图分解为1个二维偶-偶ML图(二维(n-1)×(m-1)格ML图,需要4个信标节点)、2个一维偶ML图(一维(n-1)格ML图和一维(m-1)格ML图,均需要2个信标节点)和1个单格,故至多4+2×2+1=9个信标节点就能够保证全图点点收敛。
5)由3)可知,已知节点间的距离,对二维MT图定位,需要至少3个信标节点。
6)至多25个信标节点可以保证二维MT图的收敛。对于二维n×m格MT图,仍然采取4)的方法,保证分出的最大图的长宽分别为不大于n/2和n/2的最大整数,至少可以分解为4个二维偶-偶图、4个一维偶图和1个单个格点,故至多4×4+4×2+1=25个信标节点就能保证收敛。
综上所述,在二维MT图中,按4)和6)给出的方法布置信标节点,可以保证算法的收敛。
4 算法仿真
仿真在Matlab环境下完成,依据MT移动模型,使用20×20的区域(使用长度和宽度均为20的区域分块方式)、8个信标节点、80个传感节点和50个移动节点,这与大城市中的车辆密度基本相符。在100次仿真过程中,信标节点位置不变,传感节点的位置则在每次仿真开始时随机生成且不与信标节点重叠,50个移动节点在仿真过程中的随机时间加入网络开始运动,设定其在每个交叉点的前行概率为0.75,右转概率为0.17,左转概率为0.08,图3和图4显示100次仿真的收敛情况。由于目前还未有专门针对稀疏、容延时网络的定位算法,因而笔者不给出与相关算法的仿真比较。
图3显示100次仿真每次的收敛时间,均值为236,即平均236步就能够使所有传感节点的位置估计收敛到1点。所有100次仿真都在378步之内达到收敛,这与之前的分析一致,验证了该算法的收敛性,并且不会有长的收敛时间。
图4 则按时间显示出收敛的速度。主曲线显示在每一时间达到收敛的传感节点数量的平均值,竖线显示各时间点均值的标准差。可以看出,从统计意义上来讲,每一时间收敛节点的数量的变化不大,这说明节点收敛的速度是可预期的,从而验证了该算法的稳定性。
图5 显示了某次仿真估计位置与传感节点实际位置的对比,可以看出,仿真的估计位置与节点的实际位置相差不大,从而说明使用该算法可以得到较为精确的位置估计。
事实上,在该算法下,估计位置与实际位置的差别取决于区域分块的精细度。显然,对于同一区域来说,分块越精细,仿真结果越接近实际位置,但同时会影响收敛时间,并且算法的计算复杂度会提高;相反,分块越粗糙,仿真结果与实际位置的差别越大,但会节省收敛时间,同时也会降低算法的计算复杂度。因而,对于定位精度有不同需求的系统,可以选择不同精度的区域分块方式。但就方法而言,该定位算法对于不同的分块精度不会有差异。
5 小结
“算法初步”学习的定位与思考 篇5
一、重难点解析与学习定位
本章的重点是程序框图。程序框图往往含有顺序结构、条件结构和循环结构三种基本逻辑结构，其中的难点是对循环结构的理解和应用。正确理解循环结构，首先要确定是当型循环结构还是直到型循环结构，第二要认清表示累计变量的意义，第三要确定在哪一步开始循环。
算法的程序语言，是将算法框图转化为计算机能识别和执行操作的语句，任何一种正确的算法程序，输入到计算机中，通过计算机运行就能输出结果。输入语句、输出语句和赋值语句是任何一个算法中必不可少的语句。在赋值语句中，一定要注意其格式要求，如：“=”的右侧必须是数值表达式，左侧必须是变量，一个语句只能给一个变量赋值，变量的值始终等于最近一次赋给它的值，先前的值将被替换。在一个算法对输入的值进行判断时，就需要条件语句。若一个算法中某些步骤需要反复执行多次，就少不了循环语句。
二、算法的多元表征与案例分析
移动定位算法 篇6
无线传感器网络主要应用于对事件的智能监控, 而事件发生的坐标信息对于监控消息至关重要。由于锚节点移动算法仅使用少量移动的信标节点在待定位区域进行游走定位, 定位成本大大降低, 同时定位精度也较高, 从而得到了国内外学者的广泛重视[1,2], 文献[3]介绍了通过优化锚节点移动路径以降低定位误差的方法;文献[4]介绍了未知节点根据接收到的移动锚节点发射的信号时间差来确定位置坐标的方法。由于锚节点一般采用GPS设备确定坐标, 这难免出现误差, 而以上算法在对未知节点定位时均未考虑到此误差产生的影响, 因此, 算法不够完善。本文充分考虑锚节点误差及成本, 提出了一种采用单个多功率移动锚节点的自适应权重粒子群 (SAPSO-SMPMA) 算法。
1 SAPSO-SMPMA算法
在SAPSO-SMPMA算法中, 设待定位区域为L×L正方形区域, 未知节点随机撒布, 锚节点按照设计的路径进行移动, 在锚节点发射信号的不同位置, 分别用静态的虚拟锚节点进行表示, 如图1中, 移动锚节点从定位区域的一个顶点出发 (图1中黑色实点所示) , 按照箭头方向进行移动直至游走完整个待定位区域。
1.1 计算未知节点与不同位置锚节点的距离
本文设定移动锚节点的移动步长为s=L/5, 锚节点通过功率控制, 每次移动一个步长的距离后, 以一定的时间间隔依次向四周发射4种功率依次增强的功率信号, 信号包含锚节点发射时的坐标A和相应发射功率下锚节点信号的极限传输半径R={ri|i=1, 2, 3, 4且r1<r2<r3<r4}及4种锚节点极限传输半径数据包。一旦锚节点的功率信号被待定位节点接收, 此节点便不再接收锚节点同一位置更高功率的信号。
若待定位节点Q接收到锚节点在坐标A11处第i次发射的功率信号则有||Q-A11||<ri, 同时由于信号是按照功率依次增强的顺序进行发射的, 故有||Q-A11||>ri-1, 即得到未知节点的位置区间为ri-1≤||Q-A11||≤ri, 此时取d= (ri-1+ri) /2作为此时锚节点和未知节点之间的距离估计, 当i=1时, 取ri-1=0。如图2所示, 未知节点位于锚节点的第二次发射信号最大传输半径r2和第三次发射信号的最大传输半径r3之间, 则此时 (r2+r3) /2即为估计距离。
1.2 锚节点误差矢量分析
由于定位过程中信标节点位置信息的核心地位, 所以加入锚节点定位误差进行分析具有重要的意义, 文献[5]提到了一种GPS矢量分析形式, 但是这种表示形式, 仅考虑到了节点定位装置接收GPS信号的误差, 未考虑定位环境差异带来的影响及锚节点移动的误差, 因此本文提出了如式 (1) 所示的锚节点误差分析的矢量坐标表示形式, 其中envir_error表示锚节点的环境误差, gps_error表示因噪声等干扰的信号误差, β表示锚节点移动角度误差。
1.3 估计未知节点的坐标
为了在保证定位精度的前提下, 尽可能延长移动锚节点的生存寿命, 本文设定锚节点传输半径r4位于区间内, 未知节点根据接收到的信标节点的坐标及与相应信标节点坐标对应的距离d, 采用鲁棒性强、实现简单并且收敛快的自适应权重粒子群算法进行处理, 从而得到未知节点的估计坐标。
1.3.1 自适应权重粒子群算法 (SAPSO) 描述
在基本的PSO算法[6]中, 准确适当地平衡算法的局部及全局搜寻能力, 对于求取最优值非常重要, 因此, 如能自主合理地匹配惯性权重则能精准快速地求得最优值。
基于以上思想, Shi和Eberhart[7]提出了SAPSO算法, 算法数学描述如下:在e维搜寻区域有N个潜在问题解的粒子形成的种群, 微粒速度及坐标可分别表示为Vi=[vi, 1, …, vi, e]和Xi=[xi, 1, …, xi, e] (i=1, 2, …, N) 。对各微粒的目标函数分析求出t时刻各微粒的个体及群体的最优值, 再按式 (2) 更迭各微粒的坐标及速度。
其中i=1, 2, …, N;c1、c2为加速常数, 一般设为c1=2, c2=2;r1、r2为0~1之间均匀分布的随机数;Pi及Pg分别为个体和群体最优值;w为惯性权重因子, 按式 (3) 设置。
式中wmax和wmin分别代表w的最大值和最小值, 本算法设wmax=0.42, wmin=0.05;f为粒子当前的目标函数值, favg和fmin分别为微粒的平均和最小目标值。SAPSO算法流程如图3所示。
1.3.2 设置SAPSO参数
本文选取边长为200 m的正方形区域仿真, 待定位节点个数为100, 粒子数为18, 迭代次数为20。
(1) 适应度函数
设每个待定位节点收集到的移动锚节点的信号数量为Mi (i=1, …, N) , (x, y) 为待定位节点位置, 移动锚节点与待定位节点的距离为ci (i=1, 2, …, Mi) , (xi, yi) 为移动锚节点位置, gi为待定位节点与移动锚节点的测距误差, 其计算表达式为:
由于在无线传感器网络中, 测距误差越小, 定位的精确度越高, 因此本文选用每个未知节点测距误差和的绝对值作为适应度函数, 具体计算公式如下:
(2) 性能评价指标
本实验评判指标选取平均定位误差来计算, 如式 (6) 所示:
其中:Ravg表示移动锚节点的平均通信半径, (xk′, yk′) 表示未知节点真实位置, N代表待定位节点总数, (xk, yk) 表示未知节点坐标。
2 SAPSO-SMPMA算法性能仿真
设仿真区域为边界长度为200 m的正方形, 待定位节点数为100。本文设定锚节点误差分析参数为envir_error∈[1, 5], gps_error∈[1, 5], β∈[0, 2π]、β、envir_error、gps_error均为取值区间内的随机数。将r4设为DV-hop算法节点通信半径。为了验证本文算法的性能, 将SAPSO-SMPMA算法与DV-hop[8,9]算法进行对比仿真实验。根据构想搭建的仿真区域节点分布如图4所示, 其中:*表示误差为零的虚拟锚节点坐标, □表示加了定位误差的虚拟锚节点坐标, ○表示待定位节点的坐标。
由图5可知, 随着节点数增多, DV-hop算法的定位误差逐渐降低, 这是由于该算法需要较好的网络连通度来进行定位, 节点越多越密集定位精度越高, 但是其定位误差相对另两种算法仍然较高, 而锚节点按本文虚拟锚节点分布的DV-hop算法和本文算法的定位误差曲线变化比较平稳, 同时本文算法的定位误差明显较低。
图6显示对于DV-hop算法随着锚节点误差的升高定位误差逐渐增大, 锚节点按照本文虚拟锚节点分布的DV-hop算法的定位误差曲线出现了小范围波动但是整体依然平缓, 然而本算法随着移动锚节点定位误差的增大平均定位误差曲线一直比较平稳而且误差值较低, 相比DV-hop算法误差减少了40.1%~43.2%, 相比锚节点按照本文虚拟锚节点分布的DV-hop算法误差减少33.2%~33.7%。
3 结论
SAPSO-SMPMA算法通过锚节点移动并发射多功率信号, 待定位节点通过选择性接收信标信号, 并结合SAPSO算法快速迭代处理来计算自身坐标。实验分析表明, 本文算法在引入锚节点误差分析及不需要硬件测距设备支持的情况下, 能精确地对节点进行定位, 是一种可行的无线定位算法。
摘要：为了降低定位成本及提高定位精度, 提出了一种使用单个锚节点移动进行未知节点坐标计算的SAPSO-SMPMA算法。该算法采用单个移动锚节点游历定位区域, 并通过功率控制发射不同功率的信标信号, 未知节点利用收到的不同位置锚节点信息结合自适应权重粒子群算法计算节点坐标。考虑到实际应用时锚节点可能带有误差, 故加入了锚节点矢量误差分析。仿真表明, 本算法在充分考虑锚节点自身误差及大幅降低定位成本的情况下, 定位精度仍然较高, 是一种实用的定位算法。
关键词：无线传感器网络,移动锚节点,多功率控制,粒子群
参考文献
[1]Ou Chia-ho.A localization scheme for wireless sensor networks using mobile anchors with directional antennas[J].Sens-ors Journal, IEEE, 2011, 11 (7) :1607-1616.
[2]李光辉, 赵军, 王智.基于无线传感器网络的森林火灾监测预警系统[J].传感技术学报, 2006, 19 (6) :2760-2764.
[3]李洪峻, 卜彦龙, 薛晗, 等.面向无线传感器网络节点定位的移动锚节点路径规划[J].计算机研究与发展, 2009, 46 (1) :129-136.
[4]LUO J, SHUKLA H V, HUBAUX J P.Noninteractive location surveying for sensor networks with mobilitydifferen-tiated TOA[A].Proceedings of 25th IEEE Conference on Computer Communication[C].Barcelaona, Spain, 2006:1-12.
[5]李牧东, 熊伟, 郭龙.基于最优跳距处理策略的无线传感器网络智能定位算法[J].计算机应用, 2012, 32 (7) :1836-1839.
[6]KENNEDY J, EBERHART R C, SHI Y.Swarm intelligence[M].San Francisco:Mor-gan Kaufman Publishers, 2001.
[7]SHI Y, EBERHART R C.A modified particle swarm optimizer[C].In:Proc.of the IEEE CEC.1998:69-73.
[8]NICULESCU D, NATH B.Ad hoc positioning system (APS) [C].Proceedings of the 2001 IEEE Global Telecommunications Conference.New York:IEEE Communications Society, 2001:2926-2931.
移动定位算法 篇7
为了减少无线传感器网络的成本，也为了提高定位精度，我们使用一个锚节点部署在移动车辆上构建成一个可移动的锚节点，让它在网络中移动，并发射当前位置的坐标信息。这样既减少了锚节点数量，而且未知节点接收锚节点坐标信息都是在一跳的通信距离内，避免了多跳通信，也减少了信号误差。鉴于以上分析，本文提出了一种基于网格的移动无线传感器网络定位算法(an Lo-calization Algorithm based on Grid for mobile wireless sensor networks,LAG)。
本文的章节安排如下：第1节介绍了相关的一些无线传感器网络路由协议;第2节详细介绍了基于网格的移动无线传感器网络定位算法;第3节是仿真实验和分析;第4节进行总结。
1 相关工作
在无线传感器网络中，传感器节点的定位算法通常可以分为两大类:距离相关(range-based)定位算法和距离无关(range-free)定位算法。主要的距离相关算法有：DV-distance、Euclidean算法、GenericLocalized Algrithms算法、N-HOP multilateration primitive算法等。距离无关定位算法研究比较典型的算法有DV-hop[1],质心算法[2],APIT[3]算法等。文献[4]提出了基于RSSI的改进三边测量法实现节点定位，并结合优选信标节点的方法提高定位精度。文献[5]改进了传统的ACT算法，实验表明，改进策略大幅降低了算法的复杂性，并提高了定位精度。
2 网络模型及问题陈述
本文将整个网络区域分为若干个网格，移动节点依次运动到每个网格的中心点，移动节点到达网格中心点后便根据Random Walk移动模型运动，每次停顿期发射当前的位置坐标给未知节点，使得网格区域的未知节点都接收到锚节点坐标，当移动节点在网格运动一段时间后再移动到下一个网格。未知节点根据TDOA测距方式[6]计算自己同移动节点发射坐标的位置的距离，当接收到4个坐标信息，未知节点根据多边定位法[7]计算自己的坐标位置。网格大小、移动时间等在仿真实验中详细介绍。
2.1 网格的划分
在本算法中，设监测区域为正方形(n×n)，我们划分整个监测区域为9个网格，每个网格边长为n/3，且都有自己唯一的编号，如图1所示。网格依次编号为1、2、3、4、5、6、7、8、9。
2.2 移动节点运动轨迹
移动节点依次运动到每个网格的中心点，移动节点到达网格中心点后便根据Random Walk移动模型[8,9]运动一段时间，然后再移动到下一个网格。
移动节点运动到每个网格的轨迹如图2所示。移动节点的运动方向为虚线箭头所示，依次通过1→2→3→6→9→8→7→4→5，移动节点从网格1的中心处开始，逆时钟螺旋方向运动到其他网格区域，最后一站是5号网格。每个网格的中心点坐标如表1所示。
当移动节点运动到网格的中心区域后，移动节点开始在网格内按照Random Walk移动模型运动，我们设置移动节点每次移动的距离为Ddis，它的取值同n相关，我们在仿真实验中详细讨论Ddis的大小，同样，我们也预先设定移动节点在每个网格内的移动时间，为Tmobile，并在下面的仿真实验中讨论Tmobile的大小。移动节点在网格内的轨迹如图3所示。
图3所示为移动节点在网格内的轨迹，在网格1内，黑色圆点为移动节点的初始点，黑色三角形为移动节点的停止点。移动节点每次选择一个任意的方向，在这个方向上移动距离Ddis，然后停下来，发射当前坐标的信息，当移动节点在同一个网格内运动Tmobile时间后，移动节点停止发射坐标，移动到下一个网格内，如虚线所示移动轨迹从1→2。
2.3 算法描述
步骤1：网格划分;
步骤2：移动节点规划网格移动顺序;
步骤3：在每一个网格内移动节点根据Random Walk移动模型运动，移动距离为Ddis，同时广播自己当前的位置信息;
步骤4：未知节点接受信标坐标，利用TDOA计算自身同信标坐标的距离;
步骤5：未知节点判断虚拟信标坐标是否达到4个，如果达到定位条件则进入下一步，没有达到则继续等待新的信标坐标;
步骤6：未知节点根据多边测量法计算自身的位置;
步骤7：移动节点在网格内运动时间超过Tmobile则进入下一个网格;
步骤8：结束;
2.4 算法流程图
算法流程图如图4所示。
3 仿真实验和性能分析
3.1 仿真环境设置
仿真实验总各项参数如表2所示。
3.2 实验比较和结果分析
实验1：本实验比较Tmobile对定位误差率的影响。参数设置如下，未知节点数为100个，Ddis为20m，定位所需坐标为4个，其他参数设置如表3所示。
表3显示的是Tmobile对定位误差率的影响。很明显随着Tmobile的增加,LAG算法的定位误差率明显减小。这是因为Tmobile比较小时,移动节点在网格内发射的坐标较少,而导致网格内未知节点接收到的定位坐标也较少,达不到定位要求,这样计算出来的未知节点坐标较大的偏离真实的坐标。而增加后,移动节点在网格内发射的坐标增加,这样网格内的未知节点接收到的定位坐标也增加,可以达到定位要求,计算出来的未知节点坐标较为接近真实的坐标。当Tmobile为50s时,LAG定位误差率为53%;而Tmobile为100s时,LAG定位误差率减小，为38%;Tmobile进一步增加到150s时，LAG定位误差率进一步减小，仅为19%;最后，当Tmobile达到200s时，LAG定位误差率达到最小，等于9%左右。
实验2:本实验比较Ddis对定位误差率的影响。参数设置如下,未知节点数为100个,Tmobile为150s,定位所需坐标为4个,其他参数设置如表4所示。
表4显示的是Ddis对定位误差率的影响。随着Ddis从5m增加到30m,LAG定位误差率先是迅速减小,达到一个值之后,LAG定位误差率趋于平稳。这是由于Ddis很小时,导致移动节点每次运动的距离很小,其运动轨迹不能覆盖大部分网格区域,致使网格内的未知节点不能获得可以定位的坐标数,而导致定位误差率较大。Ddis增加后,移动节点的运动轨迹逐渐可以覆盖整个网络,网格内的未知节点也能够获得的定位坐标也接近可以定位的坐标数,从而使得误差减小,当Ddis为20m时,定位误差率达到最小,等于19%,这时,Ddis继续增加,其定位误差率区域平稳。
实验3:本实验比较节点数对定位误差率的影响。参数设置如下,Tmobile为100s,Ddis为20m,其他参数设置如表5所示。
表5显示的是节点数对定位误差的影响。随着节点数的增加,LAG定位误差率缓慢的增加。因为当节点数增加后,移动节点需要发射更多的坐标信息才能提供给未知节点足够的定位坐标。当节点数等于50个时,LAG定位误差率仅仅为11%左右,而当节点数等于150个时,LAG定位误差率达到了26%。
实验4:本实验将提出的算法LAG算法[10]与TPS算法,DV-hop进行比较。参数设置如下,Tmobile为100s,Ddis为20m,节点数等于100个,其他参数设置如表5所示。
图5所示为LAG算法、TPS算法和DV-hop三个算法在不同通信半径下的定位误差比较。通信半径不同,三个算法的误差率也不同,随着通信半径的增加,三个算法定位误差率逐步下降。由于DV-hop算法是非测距的定位算法,所以误差率比其他两个算法都高。而LAG算法和TPS算法都是测距算法,且LAG比TPS误差较低。这也验证了我们提出的算法的有效性。
4 结论
本章提出了基于网格的移动无线传感器网络定位算法。并比较了、、节点数对定位误差率的影响，最后，比较了LAG算法、TPS算法和DV-hop三个算法在不同通信半径下的定位误差，验证了我们提出的算法的有效性。
摘要：节点定位是无线传感器网络重点研究的内容之一,怎样用较少的锚节点达到较高的定位精度,是值得进一步研究的内容。提出了一种基于网格的移动无线传感器网络定位算法,将整个网络区域分为若干个网格,移动节点依次运动到每个网格的中心点,当移动节点到达网格中心点后便按照Random Walk移动模型运动,每次停顿期发射当前的位置坐标给未知节点,使得网格区域内的未知节点都接收到锚节点坐标,当移动节点在网格运动一段时间后再移动到下一个网格。仿真结果表明,该定位算法能够达到较高的定位精度。
关键词：无线传感器网络,网格,移动节点,随机移动模型,定位算法
参考文献
[1]Drago N,Badri N.DV based positioning in Ad hoc networks[J].Telecommunication Systems,2003,22(1):267-280.
[2]Bulusu B,Heidemann J,Estrin D.Density adaptive algorithms for beacon placement in wireless sensor networks[C].In:Proceedings ofIEEE International Conference Computer and Sensor.2001:543-550.
[3]He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C].In:Proceedings of IEEE on Mo-bile Ad Hoc Networking&Computing,2003,81-95.
[4]付波,李斌.基于WSN的定位系统研究[J].电脑知识与技术,2010,6(8):1827-1829.
[5]张杰,邱晓晖.无线传感器网络节点自定位算法研究[J].电脑知识与技术,2009,5(25):7110-7112.
[6]Savvides A,Han C C,Srivastava M B.Dynamic finge-grained localization in ad-hoc networks of sensors.In:Proceedings of 7th Annu-al International Conference on Mobile Computing and Networking.2001,166-179.
[7]孙利明,李建中.无线传感器网络[M].北京:清华大学出版社,2005:9-20.
[8]Sanchez M,Manzoni P.Anejos:a java based simulator for ad-hoc networks[J].Future Generation Computer Systems,2001,17(5):573-583.
[9]Davies V.Evaluating mobility models within an ad hoc network:[Master dissertation].USA:Colorado School of Mines,2000.
移动定位算法 篇8
无线传感器网络由大量部署在监控区域内的传感器节点组成,各节点通过无线通信的方式形成一个多跳自组织网络,协作感知、采集和处理自然界的各种相关的监控信息[1]。在许多情况下,无线传感器网络中的节点需要知道自身的物理位置。比如,在跟踪目标和检测突发事件中。通常无线传感器节点都被随机地布置在不同的区域中,由于传感器节点受成本、能量和体积的限制,随机布放的节点无法预先知道自身的位置,他们只能根据其它已知位置的节点,按照某种定位的机制来确定自身的位置。
针对无线传感器网络节点的定位,很多学者作了深入的研究,提出了许多的定位机制和算法。根据是否需要测距,定位算法可以分为基于测距的和无需测距的[2]。
基于测距的定位算法依赖于硬件条件,在自然环境中,还会受到各种不确定因素的干扰。无需测距的定位算法主要有质心算法、DV-Hop算法、Amorphous算法、APIT算法等。无需测距的定位算法定位误差较测距的算法要大些,但可以满足大多的工程应用需求,是目前大家普遍重点关注的定位机制[3]。同时也有许多学者研究了大量的方法来提高无需测距算法的精度,但也导致了无需测距算法复杂度和能量开销的增大。
针对这种情况,本文提出了一种基于移动信标的传感器网络节点定位算法,减少无线传感器网络定位的成本和复杂度,并且提高了定位精度。
该算法在DV-Hop定位算法的基础上,利用一个带有GPS定位装置的移动信标节点在网络中按预定的路径移动并不断地广播自己的位置信息,形成多个虚拟信标,未知节点记录到每个虚拟信标的跳数,并将移动信标广播的平均跳距离通过加权处理来重新计算适用于其所在区域的网络平均跳距离,再与跳数相乘得出其与各虚拟信标的距离,最后利用改进的三边测量法计算其位置信息,实现节点精确定位。由于只采用一个移动信标,不需要在网络中布置其它的信标节点,降低了定位的成本及组网的复杂度。
最后通过仿真证明此算法可以提高定位精度,减少算法的计算量,提高了定位的效率。
1 DV-Hop定位算法
1.1 DV-Hop算法
Niculescu D等人提出的DV-Hop(Distance Vector-Hop)定位算法不需要直接测量节点间的距离,该算法具有方法简单、定位精度高等优点,它是利用距离矢量路由和GPS定位思想提出的一系列分布式定位方法之一[4]。该算法的基本思想是将未知节点到信标节点之间的距离用网络中节点平均每跳距离和到信标节点间的跳数的乘积来计算,再使用三边测量法来得出节点的位置信息。
DV-Hop定位机制非常类似于传统网络中的距离向量路由机制。距离向量定位机制分为以下三个阶段[3]:
第一阶段:未知节点首先计算与信标节点的最小跳数。信标节点向邻居节点广播自身位置信息的分组,其中包括跳数字段,初始化为1。接收节点记录具有到每个信标节点的最小跳数,忽略来自同一个信标节点的较大跳数的分组。然后将跳数值加1,并转发给邻居节点。通过这个方法,网络中的所有节点能够记录下到每个信标节点的最小跳数。
第二阶段:计算未知节点与信标节点的实际跳段距离。每个信标节点根据第一个阶段中记录的其它信标节点的位置信息和相距跳数,利用式(l)估算平均每跳的实际距离:
其中(xi,yi)、(xj,yj)是信标节点i、j的坐标,hj是信标节点i与j(j≠i)之间的跳段数。然后,信标节点将计算的平均每跳距离用带有生存期字段的分组广播至网络中,未知节点仅记录接收到的第一个平均每跳距离,并转发给邻居节点。未知节点接收到平均每跳距离后,根据记录的跳数,计算到每个信标节点的跳段距离。
第三阶段:未知节点利用第二阶段中记录的到各个信标节点的跳段距离,利用三边测量法或极大似然估计法计算自身坐标。
1.2 DV-Hop定位算法误差分析
1.2.1 DV-Hop定位算法的假设
在DV-Hop定位算法中,未知节点在通信范围内获得的信标节点数量不多,但通过多跳传播可以获得通信范围外的多个信标节点的估计距离,利用大量的信息获得该节点的位置,在网络平均连通度为8,信标比例为10%时,算法的定位误差大约是节点射频通信距离的1/3左右[4]。算法有如下的假设:
1)网络中每个传感器节点都以相同的固定的通信距离r与其邻居节点通信;
2)传感器节点的通信距离r影响定位精度,只有r大小适中才能达到较优的定位精度;
3)监测区域中定位精度依赖于网络连通度和信标节点比例。
对于一些环境下的传感器网络,通过人工部署大量位置已知的信标节点是不实际的,而在网络中布置一定比例的带有GPS的信标节点则会提高网络的定位成本。
1.2.2 DV-Hop定位算法的信标节点比例分析
在传感器网络中,假设某未知节点的坐标记为(xn,yn),实际的坐标记为(Xn,Yn),两个位置的距离为:
平均定位误差的定义与节点的无线传输范围有关[5],为:
建立实验的仿真环境来分析DV-Hop定位算法的性能,主要分析不同的锚节点比例对定位精度的影响。在Matlab平台上建立实验仿真环境,在一个边长为50m的正方形区域中分布有100个未知节点,射频通信距离为10m。分析当网络中信标节点个数从3个到10个时的定位误差,如图2所示。
从图2中可知,信标节点的比例与定位误差成反比,信标节点越多,平均定位误差和均方差越小。所以为了提高定位的准确性,需要增加信标节点。
2 移动信标节点定位算法
从以上分析可知,为了提高定位精度,需要增加信标节点,但信标节点造价高。为了提高定位精度,降低布网复杂度,本文提出一种基于移动信标的定位方法。
带有定位装置的信标节点装载在可移动的平台或移动机器人上,就构造了一个移动信标,移动信标在一定规律的移动过程中,可实时获取自身位置,并周期性地广播自身的位置信息,以帮助未知节点进行定位。
2.1 信标节点的移动模型
移动信标节点采用什么样的方式移动才能尽可能地遍历整个网络,这个本身就是一个研究的热点,网络中传感器节点本身是随机散布的,节点位置本身信息是未知的,为了使这些节点全部进行定位,需要设计出一种运动模型,使移动信标的运动轨迹能在尽可能少的时间内遍历网络,发送足够的定位信息给未知节点以完成定位算法。目前应用于无线传感器网络的移动模型有S型、RWP(Random Way Point)模型和Gauss-Markov模型等。这些模型是自组织网络中广泛应用的模型,RWP模型对信标的硬件要求小,路径的随机性大,并且随着运动速度逐渐减小,运动轨迹出现在网络中心区域的概率偏大。S模型则对硬件的要求相对较高。
为此本文选择Gauss-Markov运动模型,该模型可以覆盖网络的大部分区域,相对于RWP模型,可以避免运动轨迹的突变和边缘地带概率减少的缺点[6],对硬件的要求也不高,其模型表示如下:
其中,vk和dk表示运动时刻k移动信标的速度和方向。a是方向随机调节参数,取值为0到1(0<=a<=1),vmean、dmean为平均速度和平均运动方向,γv、γd代表高斯随机变量。移动的下一时刻的速度和方向从当前的速度和方向求出:
信标节点按照Gauss-Markov模型计算每个时刻的运动速度和方向,并由定位装置获取当前运动位置的坐标信息,将其广播到网络中。因为信标节点要周期性的广播坐标信息,还要接收网络中未知节点广播回来的跳数累加的广播分组,故在GaussMarkov模型中,设置一个计时器,计时周期为信标节点广播坐标的周期,每当计时器时间到,移动暂停,广播当前位置信息,并接收各未知节点返回的跳数广播分组,记录在列表中。再继续移动。
2.2 基于移动信标节点算法的定位过程
信标节点在网络中移动,周期性地将位置信息广播到网络中,广播的信息格式包括当前运动到第几个点、当前位置坐标,网络跳数(初始化为0),在移动信标节点通信范围的未知节点都接收到该位置的信标节点的定位数据包。每个节点接收到定信息后,将其中的跳数值加1后继续广播。每个节点接收到多个邻居节点的广播值都与本身记有的值比较,如果小于自身记有的跳数值,则丢弃这个广播分组。
这一过程与DV-Hop定位算法相似,不同的是,未知节点判断接收到的是第几号位的信标节点广播,如果为第1个就暂不广播,直到接收到第二号位的信标广播时,再把一号位的定位信息包广播出去,并保存接收到的二号位广播,等待下一位的广播后再发送,以此类推。广播定位信息的过程分为以下几步:
1)移动信标在第一个位置取得当前位置信息,封装位置信息广播信息包{LIDi,xi,yi,HOPs},LIDi表示当前是第几号位置的广播包,xi、yi表示当前位置坐标,HOPs为经历的跳数,初始为0;
2)移动信标在第一个位置的通信范围内所有邻居节点接收到定位信息包,接收到信息包的节点将其与本身的数据包进行比较,取跳数较小的一项,并丢弃较大的,将跳数一项加1,记录下这个个跳数值,等待下一个定位信息包;
3)移动信标移动到下一个位置,将位置信息加1并广播这个一新位置的定位信息包,同时接收各节点发回的广播信息,取与前一位置最小跳数的分组,将两位置的距离除以跳数计算出平均每跳距离(Di)并广播到网络中;
4)重复步骤3直到位置号达到预先设定的阈值K,K根据所需的虚拟信标密度而定,如果网络中有N个未知节点,根据精度要求得出虚拟信标比例q,则K=N×q;
5)节点根据接收到的各个虚拟信标的平均跳距离按权值进行校正,并根据记录的跳数计算出到各个虚拟信标的距离,挑选出最优的虚拟信标节点距离信息,按优化的三边测量法计算自己的位置。
2.3 加权值法计算平均跳距离
为了更准确地计算出估计的平均跳距离值,本文引入权值的概念,运用加权值对平均跳距离进行校正是基于网络并非完全的均匀分布,各个节点接收到多个虚拟节点的平均跳距离值,越是靠近未知节点其平均跳距离值更能反映出未知节点所在的网络区域的情况,对其平均跳距离的影响也越大,所以应当占有更大的权值,这样比只计算平均值更接近真实值,计算出来的未知节点位置更精确。
为了方便表达,我们假设网络中的未知节点Nj接收到多个虚拟信标的平均跳距离值,虚拟信标Ai计算的平均跳距离记为Di,节点Nj到信标Ai的跳数为Hi。
加权因子体现的是各个虚拟信标节点计算出来的平均跳距离值对未知节点计算平均跳距离值的影响力。假设未知节点N1接收到三个虚拟信标节点(A1,A2,A3)的平均跳距离值(D1,D2,D3),而该节点查找表中所记的跳数值知道其距离三个虚拟信标的跳数分别为:H1,H2,H3。那么节点计算其平均距离值如下式:
各个平均跳距离的权值相加为1,反映的是各个平均跳距离值对最终计算的跳距离值的影响程度,这样计算节点Nj的平均跳距离值就为:
至此,各未知节点已得到与各个虚拟信标的跳数,并可根据2.3节求出适合自己网络区域内的平均跳距离值,因此可利用三边测量法计算出未知节点Nj的坐标。
3 仿真
为了提出的算法在OMNe T++平台进行仿真,并用MAT-LAB进行实验数据的辅助分析,在OMNe T++平台上,将100个传感器节点随机分布在一个50×50的区域中,节点通信半径为10。网络中还有一个可获得自身位置的移动信标按GaussMarkov模型移动,平均速度为5,初始方向角设为90°,在边缘区域时转变系数,即式(4,5)中α=0.75,移动信标的广播计算器设置为2秒,即移动信标节点每移动2秒后即在网络中进行定位信息的广播。为了使仿真结果更接近实际的情况,仿真结果是经过20次独立仿真结果平均值获得。
3.1 定位精度与定位覆盖率分析
移动信标以预定的运动模型运动,并周期性的广播定位信息包,即虚拟信标的增长速度,虚拟信标越多,定位精度越高,所花的定位时间也越多,他们存在图3中的关系。
图中所示的关系是显然的,随着时间的推移,移动信标在网络中移动的距离越远,广播的定位信息越多,虚拟信标也越多,定位的误差也随之减小。同样的,随着移动信标的轨迹覆盖了越多的地方,越来越多的未知节点获得定位信息包而计算自己的位置,定位的覆盖率也不断增加。
3.2 信标节点广播定位信息周期的影响
当移动信标节点以参数一定的Gauss-Markov模型运动时,广播周期越小,则虚拟信标越密,即单位区域内虚拟信标越多,必然导致节点通信消耗的增大,误差也增大。当周期T增大到一定程序时,再增大,则广播的定位信息大少,用于定位的虚拟信标大少,也会导致定位误差的增大。最优的定位周期的大小由节点由通信半径决定,当通信半径越大时,广播的周期也应相应的增大。在同样的移动模型下,当广播周期T变化时,定位误差与其关系如图4所示。
3.3 定位误差比较
算法的性能主要以定位的误差来评价,移动信标以2秒的周期广播定位信息包,即在网络中构造一个虚拟信标。仿真结果的比较如图5所示。
如图5中,可见,两种定位算法的误差随着信标节点的增加都会减少,在信标节点越多的时候,本文提出的算法误差减少更明显,这是因为采用了加权处理来求各未知节点的平均跳距离,当一个节点获得越多其周围的虚拟信标计算的平均跳距离,加权处理后的平均跳距离就越接近真实的网络情况。
4 总结
基于移动信标的定位方法是无线传感器网络定位的关键技术之一。本文提出的MBWDV-Hop算法在DV-Hop定位算法的基础上引入移动信标,可以减少网络信标节点的数量,并且不需要测距,对硬件要求不高,降低了组网的成本。同时采用加权处理来改进节点的平均跳距离值的计算,求出的值更接近节点所在网络区域的情况,提高定位的精度。由仿真结果可以看到,MAWDV-Hop的定位效果更好,它能提高定位的精度,降低定位的成本,但由于只采用一个移动信标节点,需要在网络中移动过的区域才能对未知节点定位,所以不适用于需要快速定位的网络,如何规划移动信标的移动路径,使其能更快地覆盖网络的区域,减少无法定位的节点也需要进一步研究的问题。
参考文献
[1]Akyildiz L,Su W,Sankarasubramaniam Y,et al.A Survey on SensorNetwork[J].IEEE Communication Magazine2,002(8):102-114.
[2]Stankovic J A,Abdelzaher T F,Lu Chenyang,et al.Real-Time Com-munication and Coordination in Embedded Sensor Networks.Proceed-ings of the IEEE,2003,91(7).
[3]王海东,孙利民.无线传感器网络的定位机制[J].计算机科学,2006,33(4):36-49.
[4]Nicolescu D,Nath B.DV based positioning in ad hoc networks[J].Journal of Telecommunication Systems,20032,2(1/4):267-28.
[5]Min YinJ,ian Shu.The Infltmenee of Beacon On DV-hop in WirelessSensor Networks[C]//Hunan:Proceedings of the Fifth International Conference on Grid and Cooperative Computing Workshops,2006:118-122.
移动定位算法 篇9
1 基于移动锚节点的静态无线传感器网络定位
1.1 静态无线传感器网络节点定位的基本原理
静态锚点主要是通过人工部署或者是配置GPS定位设备等来部署完成并且获得自身的精确位置信息, 在使用的过程中由于自身在无线传感器网络中占用的比例比较小, 但是其部署的目的是为了协助未知节点进行具体的定位的。因此可以总结到移动锚节点就是具备移动能力并且配置自身定位设备的节点。在无线传感器网络的使用中具体的分布在无线传感器网络中的位置节点中, 来提供可靠的辅助信息, 并且按照一定的算法来计算自身的估计位置。
在无线传感器定位系统中, 节点的间距或者是角度的测量技术主要是由:RSSI、TOA、TDOA和AOA组成的。其中在测量技术中, RSSI主要是在已知了发射功率, 在接收节点测量接收功率中, 具体的计算传播损耗, 使用理论或者是经验信号传播模型来将传播损耗转化为传输的距离;TOA是指通过测量信号传播时间来测量具体的网络距离;TDOA被广泛的应用在无线传感器网络的定位方案中, 一般是在节点上安装两种信号收发器。AOA是一种估算邻居节点相对自身防伪信息的技术, 但是最终总结到:RSSI和TDOA是移动锚节点在无线传感器网络定位中最常用的技术。在移动锚节点中定位的计算主要采用的是三边测量法、极大似然估计法以及三角测量法来计算未知节点的位置。
1.2 静态无线传感器网络定位算法分类
静态无线传感器网络定位的算法主要有: (1) 基于测距的定位和无需测距的定位。基于测距的定位算法通常采用的是RSSI、TOA、TDOA、和AOA测量技术, 在测量技术的应用中, 需要将传感器节点上额外的配备测距的装置, 这样就能够增加节点的成本和功耗以及计算量和通信量, 避免了在测量中的误差影响。但是无需测距定位, 在使用中能够减小节点的尺寸, 满足了功耗和成本的限制。 (2) 集中式计算的定位于分布式计算定位, 其中集中式计算的定位是指计算中心收集所有的定位信息, 然后将集中的信息计算完成所有的节点定位方式, 在使用中能够进行大量的计算以及存储, 并且可以获得相对精确的节点位置估算。 (3) 静态网络节点的定位和移动网络节点的定位, 其主要应用的是锚节点移动性来进一步减少所需要的锚节点的数量, 最终降低了硬件成本, 增强了覆盖面积, 提高了定位精度。
2 移动锚节点在静态无线传感器网络定位算法中的分析
通过增加锚节点的数量以及密集的部署锚节点来提高整个网络的定位, 其中在移动锚节点的定位算法中主要是利用1个或者是多个锚节点来在整个网络节点中进行全面的分布, 并且按照规划好的路径进行移动, 在移动的过程中其周期性广播标数据包, 以及信标数据包中的发射该信标的信标点位置的信息就能详细的确定, 在移动锚节点中通信的传感器节点可以接收到信标数据包, 在测量的同时根据节点间的连同信息或者是3个以上的测量距离来估计自身的位置。本文在结合使用RSSI、TOA和AOA测量技术估计节点位置的算法中, 详细的确定了静态无线传感器网络定位算法的构建。最终确定出未知节点通过信标信号内的时间戳计算传输时间差, 然后将传输速度和传输时间差来计算未知节点和信标点之间的距离, 完成了整个过程的位置确定。另外在移动锚节点的路径规划中, 主要是为了促进移动轨迹能够覆盖整个网络中所有的未知节点, 然后再未知节点进行定位完成后提供良好的质量保证信标点。
3 总结
本文在分析了移动锚节点之后将静态无线传感器网络定位算法进行了详细的探究, 对无线传感器网络的特点以及移动锚节点的路径的规划问题, 并且通过分析移动锚节点在静态无线传感器网络定位的算法, 为进一步加强节点定位以及测量技术提供了有效的保障, 提高了节点的定位精度, 为无线传感器网络提供了最小的网络成本, 在耗能最低中实现了最高的定位精度以及定位覆盖率, 延长了整个网络的使用, 提高了我国网络技术的进一步发展趋势。
摘要：随着网络技术在深入的发展, 静态无线传感器网络主要是通过引入网络技术中具有数据采集能力、信息处理能力以及无线通信的能力的传感器节点进行相互交换信息, 并且协调控制有机相结合。该技术的已经被广泛的应用于生活中的各个领域中, 在移动锚节点的使用中, 改变了静态无线传感器网络在发展中遇到了环境恶劣、不可到达区域最终实现了监测和跟踪的任务, 有效的控制了节点位置的具体信息。
关键词：移动锚节点,静态无线传感器,网络定位,算法构建
参考文献
[1]何晓敏, 梁金甲.基于移动锚节点的无线传感器网络定位算法研究[J].仪器仪表学, 2012 (04) .
几种虹膜定位算法的分析与比较 篇10
关键词:虹膜;离散圆形动态轮廓线法;灰度阈值分割法;圆Hough变换;点Hough变换
1 引言
虹膜定位是虹膜识别处理过程中非常重要的环节,它不仅决定了后续过程能否继续,而且决定了提取特征是否有效,并最终决定虹膜识别结果。虹膜包含纹理的部分是内外两个近似圆形边界之间的部分,虹膜内侧与瞳孔相邻,外侧与眼白相邻。但是,这两个圆不是完全同心的[1],需要分别对内外两个边界进行处理。
本文介绍了离散圆形动态轮廓线法、灰度阈值分割法、圆Hough变换和点Hough变换几种虹膜定位算法,并对各种算法进行了分析和比较。
2 离散圆形动态轮廓线法
离散圆形动态轮廓线法(DCAC:Discrete Circular Active Contours),这种算法使用了先验的信息和统计学的知识,找出虹膜边界和评定这种方法的成功和失败。由于瞳孔-虹膜边界是圆形,需要定义一个圆形的动态轮廓线,假定一个开始点,在图像中定位一个圆[2]。
每个顶点用 vi 来表示,内部力Fint,i被定义为:
(2.1)
是该顶点在完美多边形中的位置。有如下公式:
(2.2)
其中Cr表示当前边界的平均半径,C= (Cx,Cy) 是当前的质心,n是节点数,δ是每次迭代中半径的增加值,质心C被定义为:(2.3)
平均半径Cr被定义为:(2.4)
由图像像素的灰度级提供的图像力把顶点向里推,来平衡轮廓线的内部力。每个顶点 vi 的外部图像力的方向定义为:
(2.5)
大小定义为:
(2.6)
I(vi) 是vi最近顶点的灰度值,这样每个顶点的图像力被定义为:(2.7)
如图2所示:
轮廓线的运动由内部力和图像力之和决定,因此从t到t+1次迭代顶点运动表示为:
(2.8)
β是这两种力的权重。这个运动直到内外力平衡或者达到允许误差范围之内停止。如果当前轮廓线的平均半径的中心和m次迭代前的相同,就认为达到了平衡。这样就确保了即使单个顶点发生震荡移动,轮廓线也能够保持稳定。
离散圆形动态轮廓线法原则上是依靠初始配置能够找到瞳孔-虹膜边界或者虹膜-巩膜边界,因为在每个例子中圆形边界内部的区域更加黑。然而,在真实的眼睛图像中这样的方法会带来几个问题:
首先,DCAC算法搜索瞳孔-虹膜边界的时候频繁地受到来自角膜的镜面反射的影响。这个问题可以通过预处理图像把所有灰度值高于128的部分全部设为128来解决。
第二个问题是在真实的眼睛图像中该算法极度地依赖于公式2.2中δ的取值。如果δ的值太大,轮廓线总是会移出图像;反之如果δ值太小,轮廓线或者维持在开始的地方,距离实际的目标增长得非常缓慢,或者收缩到半径为零。不幸的是,没有适用于广泛的眼睛图像的δ值。
3 灰度阈值分割法
灰度阈值分割法是一种基于区域的技术,这种方法是把每个像素的灰度值与阈值T进行比较,根据它是否超过该阈值而将图像中的像素点分成两类。
一般意义下,阈值运算可以看作是图像中某点的灰度函数,或者该点的某种局部特性(该点的平均灰度)及该点在图像中的位置的检验,这种阈值检验函数可记作:
T (x, y, N ( x, y, )g ( x, y) )(3.1)
式中g( x,y ) 是点( x,y )的灰度值,N( x,y )是点( x,y )的局部邻域特性。如果 g( x,y )>T( x, y, N( x,y ), g( x,y )) (3.2)
则点( x,y )记作物体点,反之则为背景点。若设( x,y )表示阈值处理后的图像,则有:
根据瞳孔和眼白、虹膜之间的关系。从图4所显示的虹膜来看,瞳孔的灰度最为趋向一致,也是图像中灰度值最低的部分,虹膜图像的灰度直方图具有明显的多峰特征,灰度值最低的峰值之后所对应的峰谷就是瞳孔与其他部分分割的阈值。
采用如下步骤进行灰度阈值分割[6]:
(1)先计算出整个图像的灰度直方图。灰度直方图是灰度值的函数,描述的是图像中具有该灰度值的像素的个数。其横坐标表示像素的灰度级别,纵坐标表示该灰度出现的频率(像素的个数)。在实际操作中对整个图像的所有像素进行扫描,建立数组int greyCount[256],用以存储各个灰度值出现的次数。
(2)平滑灰度直方图:采用中值滤波和改进的盐和胡椒滤波两种方法对虹膜图像进行噪声处理。
(3)求可能的阈值点:设灰度直方图的包络线为f(x),则阈值点a是满足下列条件的一个点: 其中δ为一微小增量,用差分代替导数求得阈值点,对于数字图像,可以用一阶差分代替一阶微分:
(3.4)
(3.5)
(4)确定阈值点:求其中第一和第二个波峰之间的波谷对应的灰度值T0,在大部分情况下,直接使用T0作为阈值就可以取得很好的效果,但是有的图像中睫毛或眼眉的灰度要低于瞳孔的灰度,这时求得的阈值偏低,瞳孔会被误认为背景,需要进一步判断:计算T0与第一个波峰对应的灰度值之间的差值,如果差值大于3,则T0就可以作为最后的阈值T1;否则继续在直方图中搜索下一个波峰后的波谷,作为二值化的阈值T1。这些规定,是根据所用虹膜库的虹膜图像为320×280,经过实验和先验知识综合确定的。
求得阈值之后,设阈值为a,则可用下述方法将图像二值化:扫描整个图像,若像素点的灰度值大于a,则赋值为255;若其小于a,则赋值为0。
图5展示了图4的灰度直方图,由图可以看出,它应该有两个主要的峰值,其中的第一个峰值,对应的就是瞳孔区域灰度集中的范围,提取瞳孔的二值化阈值应该选在第一个峰值的右侧。图6显示了对该图进行灰度分割(保留阈值<=35的部分)后的结果。
由此可见,阈值分割不失为一种分离瞳孔的途径,但是应当指出,对于聚焦良好,光照均匀的虹膜图像,可以直接采用投影的方式确定瞳孔的半径和圆心,但是,对于光照不均匀的图像,阈值分割之后会出现许多干扰点,图7是一幅光照不均匀情况下的虹膜图像及其阈值变换,可见光照不均匀的情况下阈值变换后的瞳孔边界有棱角,而且周围有很多干扰点,这对确定虹膜的内边缘增加了不少难度。
虽然阈值分割不能一次分离出完整的环形虹膜,但已经使环形虹膜内外边界明显,为下一步的内外边缘的检测提供了更好的条件。
4 圆Hough变换
Hough变换[4]是一种用于区域边界形状描述的方法,经典的Hough变换常常被用于直线段、圆和椭圆的检测。Hough变换的思想是将图像的空间域变换到参数空间,即将原始图像中给定形状的曲线或直线变换成变换空间的一个点,原始图像中曲线或直线上所有点都集中到变换空间的某个点上形成峰点,这样,把原始图像中给定形状的曲线或直线的检测问题,变成寻找变换空间的峰点问题,也即把检测整体特性(给定曲线的点集)变成检测局部特性的问题。
Hough变换可应用于检测图像空间解析曲线(u,v)=0,其中u为解析曲线上的点(二维矢量),v为参数空间上的点(矢量)。由上述原理,可得圆的Hough变换的方法:在x-y平面上,中心在(ac, bc),半径是 的圆周C上每一点 (x, y) 满足
(4.1)
如果将圆心 (a, b) 看作为变量,则在a-b平面上可以画出中心在 (x, y) 、半径rc的圆Ch。在圆C上的每一点 (xi, yi) ,在a-b平面上有中心在 (xi, yi) 、半径为rc的圆Chi与之对应,且这些圆组成了相交于一点 (ac, bc) 的圆群。进一步把圆的半径r作为变量,在a-b平面得到由不同半径的圆Chi构成的圆环。在a-b-r空间中建立三维数组,数组中元素Pai,bi,ri的值代表a-b平面上通过点 (ai, bi)、半径为ri圆的个数,则数组中的最大值所对应的参量(ai, bi, ri),就是图像空间中圆的圆心和半径。
Hough变换虽然使用广泛,但是因为它要在三维空间内搜索,计算量是非常大的。
5 点Hough变换[5,6]
点Hough变换是Hough变换的改进,它是利用圆周上任意两条不平行弦的中垂线相交于圆心的性质。原理如图8所示,设K、L、M为圆周上的三个点,由圆的几何性质可知,KL的中垂线Lkl与LM的中垂线Llm必然相交于圆C的中心O。设K、L、M三点的坐标分别为 (xk, yk) 、 (xi, yi) 、 (xm, ym) ,则 Lkl 和 Lim 的方程分别为:
(5.1)
(5.2)
利用(5.1)和(5.2)式,计算出圆 C 的圆心 (ac, bc) 和半径 rc:
(5.3)
(5.4)
(5.5)
可见,半径为ri、圆心为 (ai, bi) 的圆周上任意不共线的三点(以下称为点组)对应 a-b-r 空间中的一点(ai, bi, ri),所以称之为点Hough变换(Point Hough Transform)。
用向量表示 a-b-r 空间中的点,则图像中圆 (ai, bi, ri) 上的点组对应于a-b-r空间中的向量。在图像中选取N个点组,得到向量 0、1、…N-1,N组来自同一个圆上的点组对应的向量相同。向量组中不同编号的向量可能相同。向量组中出现次数最多的向量就是图像中圆的参量。用数组P[n] (n=0,…N-1) 表示向量组中向量 出现的次数,则有:
确定数组P[n] 后,就可以找出图像中圆的参量值:
(5.7)
实际上,由于数字化误差的原因将式(5.6)中kk=1的条件由 改为,为一微小增量,更为符合实际条件。PHT不需搜索变量空间,只对选取的点组进行统计,计算复杂性仅跟所选择点组的数目有关。可见,选择适当的点组可以大大降低计算复杂度。
6 结束语
综合以上几种方法的优缺点,结合试验结果分析,点Hough变换无须搜索变量空间,只对选取的点组进行计算,复杂性仅跟点组数有关,因此更适合用于虹膜定位。
参考文献
[1] MANN I. The Development of the Human Eye[M]. New York: Grune and Stratton,1950.
[2] RITTER N J, COOPER R. Locating the Iris :A First Step to Registration and Identification[A]. International Conference on Signal and Image Processing[C]. IASTED, Aug.2003:507-512.
[3] 常海军.虹膜识别算法研究与实现[D].杭州:浙江大学,2005.
[4] 夏良正.数字图像处理(修订版)[M].南京:东南大学出版社,1999.
[5] 林金龙,石青云.用点Hough变换实现圆检测的方法[J].计算机工程,2003,29(11):17-18.
移动定位算法 篇11
ZigBee是一种新兴的低成本、短距离、自配置、低速率以及低功耗的无线网络技术,具有比较完善的防碰撞机制、节点管理体系及电源功耗管理功能[1]。选用的无线收发芯片型号是A7105,A7105是一低成本2.4 GHz ISM频段的无线应用射频芯片。A7105 内建接收信号强度指示RSSI和ADC侦测使用电压。
在无线传感器网络中,传感器节点间的测距方法是一些基于测距的定位算法的基础。测量节点间距离或方位时常用的方法有基于到达时间(TOA)、基于到达时间差(TDOA)、基于到达角度(AOA)和基于接收信号强度指示(RSSI)的方法[2],本文采用基于RSSI的测距,因为此方法无须额外的硬件设备,是一种低功率、廉价的测距技术,但是因为无线信号受反射、多径传播、非视距传播等问题影响,使得相同距离产生不同的传播损耗,因此,为了获取更加准确的RSSI,先通过中值过滤器(先把RSSI数据排序,设定阈值,根据阈值来取值),再经过均值过滤器的方法,以去除那些偏差较大的RSSI,提高了RSSI的精度。在定位过程中,本文采用基于极大似然估计法加权取均值的定位优化算法,此种定位方法提高了定位的精度。
上位机利用LabVIEW软件开发,LabVIEW是一种图形化编程语言,采用工程技术人员所熟悉的术语和图形化符号代替常规的文本语言编程,具有界面友好、操作简便、操作周期短等特点[3]。本文上位机的作用是采集RSSI,实现算法及显示。
1 算法描述
1.1 RSSI测距原理及本文获取RSSI算法
1.1.1 RSSI测距原理
基于RSSI(接收信号强度)测距算法:在发射节点的发射功率确定的情况下,可以根据接收节点接收到的功率,利用理论和经验模型,得出能量损耗与距离的关系。
一般采用的RSSI测距原理如式(1)所示
式中:RSSI是接收信号强度;A为常数;d是收发节点之间的距离;n是信号传播因子。常数A和n的值决定了接收信号强度RSSI和传输距离d的关系。A和n的数值易受多种因素影响[4]。此种测距方法需确定A和n两个常数值,实现过程较复杂。
本文采用的RSSI测距原理:由于当发射节点设置不同的发射功率情况下,接收节点收到的RSSI与信号传输距离d的线性范围不一样,因此,在特定的环境中,可以通过改变发射节点的发射功率,来调节RSSI与信号传输距离呈线性关系的范围,根据接收节点接收到的不同距离处的RSSI,拟合出一个适用于此特定环境的函数表达式,可以将接收到的RSSI转化为距离[5]。
1.1.2 本文获取RSSI值算法
假设Mi(i=1,2,…,n)为未知节点,Nj(j=1,2,…,n)为固定节点,为固定节点Nj接收到未知节点Mi的RSSI,针对一个固定节点,一组采集十次,获取10个RSSIij,由小到大排序得到:RSSIij1,RSSIij2,…,RSSIij10,然后求得这组数据的中值mid(RSSIij),为了去除掉那些因环境因素影响严重的RSSI,在这里,取一个门限值β,令
取出落在mid(RSSIij±β)的RSSI,然后求出其均值,即为RSSIij值。
1.2 极大似然估计法定位算法[6]和本文定位优化算法
1.2.1 极大似然估计法定位算法
在无线传感器网络定位算法中,如果知道移动节点与参考节点之间距离个数不小于3个时,可使用极大似然估计法来定位。
极大似然法的原理如图1所示。假设1,2,3,…,n个参考节点的坐标分别为(xi,yi)(i=1,2,…,n),它们到移动节点的距离分别为di(i=1,2,…,n),设移动节点P的坐标为(x,y)。
可得到
依次从第一个方程减去第n个方程得到
则式(4)可以用线性方程AX=b表示,其中
使用最小均方差得节点P的坐标为
1.2.2 本文定位优化算法
假设有m(m≥4)个固定节点,令p=C
式中:k=1,2,…,p;wk愈小,说明第k个定位坐标值愈接近其余(p-1)个定位坐标值;反之,当wk愈大,说明第k个定位坐标值愈远离其余(p-1)个定位坐标值。因此,可以设置一个阈值W,若wk≤W,则保留相对应的定位坐标值Nk;反之,若wk>W,则删除掉相对应的定位坐标值Nk。
假设经过阈值判断,保留了q个坐标值。然后根据这q个坐标的权值,求出其均值,如式(10)所示
式中:坐标
2 利用LabVIEW软件开发的上位机
这部分主要完成数据采集、定位算法和定位结果显示界面。
2.1 程序流程
程序流程图如图2所示,先判断帧头正确之后,接收来自5个基站发送的数据,提取出RSSI。先利用生产者循环存RSSI,然后通过消费者循环读数据并存入数组,数组元素达到50个时,利用抽取数组子程序,得到各个基站发送的10个RSSI,然后,通过中值和均值过滤,获得RSSI,带入拟合公式,再利用本文定位优化算法求出定位坐标并显示。
2.2 前面板部分
前面板如图3所示,需配置基站的坐标值。
3 相关实验、实验结果及误差分析
3.1 相关实验
在实验阶段,首先为了保证试验模块的一致性,减少实验误差。采用的方法是在可视距离内,接收模块固定不变,别的被测模块在4个方向不同距离处,进行多次测量取均值,根据最终测得的RSSI来选择出具有一致性的试验模块。
其次,选择合适的DataRate,全向天线和读取一帧数据的时间等,经过实验测试,设置的DataRate是250 kbit/s,全向天线的增益是0 dBm,读取一帧数据的时间为20 μs。
当这些试验参数都确定的情况下,在室内可视范围内,使用那些具有一致性的无线模块,通过在1～6 m,间隔为0.5 m,每个位置取值10次,在不同发射功率的情况下,利用先排序、滤波再取均值的方法获得RSSI,通过MATLAB把RSSI与距离值进行拟合之后的图像如图4所示。
拟合的一次函数表达式如式(11)所示
定位实验部分:在室内,2 m高的平面内,布置了5个固定节点,5个固定节点的ID号及坐标分别为:01#(2.5,0);02#(0,1);03#(0,4);04#(2.5,5);05#(4.5,2.5),并且固定节点之间可视。
3.2 实验结果
实验结果见图5。
注:①方形表示实际坐标;菱形表示极大似然估计法坐标;星形表示本文算法坐标。
3.3 误差分析
设R为通信半径,经过实验测得R为70 m。误差的计算公式如式(12)所示
定位误差比较结果见表1。
4 结论
本文在获得RSSI时采用先排序、再滤波进而取均值的方法,抑制了那些因多径效应、反射而读到的错误数据,提高了获取RSSI的精度;在5个固定节点获得未知节点的RSSI之后,定位的方法采用了基于极大似然估计法加权取均值的定位优化算法,与极大似然估计算法相比较,提高了定位的精度。但仍然存在一些需要改进的地方,比如可以增加固定节点数目、调整更为理想的参数,使得获取RSSI的速度更快、更准确。另外,上位机部分也需要改进,这些都会在以后的研究中进一步完善。
摘要：基于ZigBee进行室内无线定位系统的开发已经成为热点,这是由于采用无线通信可以节省成本,使用也更加方便。但同时,基于接收信号强度指示(RSSI)的测距和定位易受多种因素的影响,使得测距和定位的误差都比较大。提出了针对室内小环境范围内的定位系统,提出了获取RSSI的方法(中值过滤和均值过滤)和定位的优化算法(基于极大似然估计法加权取均值的定位优化算法),通过两种方法的结合,提高了定位精度。同时,利用LabVIEW软件开发上位机。
关键词：室内无线定位,接收信号强度指示,图形化编程
参考文献
[1]瞿雷.Zigbee技术及应用[M].北京:北京航空航天大学出版社,2007.
[2]孙利民.无线传感器网络[M].北京:清华大学出版社,2005.
[3]雷振山.LabVIEW高级编程与虚拟仪器工程应用[M].北京:中国铁道出版社,2009.
[4]CEYLAN O,TARAKTAS K F,YAGCI H B.Enhancing RSSI technologiesin Wireless sensor networks by using Different frequencies[C]//Proc.the Fifth International Conference on Broadband and Wireless Compu-ting,Communication and Applications,BWCCA 2010.Fukuoka,Japan:Fukuoka Institute of Technology,2010:369-372.
[5]YAN Jiajun.Neighbour discovery for transmit power adjustment in IEEE802.15.4 using RSSI[D].Chengdu:Sichuan University,2011.