（电路与系统专业论文）基于位姿评估的无线传感器网络自主移动节点定位技术研究.pdf

摘要 无线传感器网络作为一种新型的数据采集技术，综合了微电子、无线通信和 无线网络等多门学科，在军事、工业控制、环境监测等领域都有广泛的应用前景。 在大多数应用中，获得传感器节点的物理位置是最基本的要求，然而，由于传感 器定位受到软硬件资源限制，因此研究有效的定位算法来确定节点的位置具有重 要的理论意义与实用价值。 本文首先分析了无线传感器网络的特点和目前已有的各类移动节点定位算 法的基本思想及性能，然后针对自主移动节点的特点提出了一种能够减轻非视距 n l o s 影响的基于位姿评估的无线传感器网络移动节点定位算法。该算法首先利 用移动节点的速度信息，构造相对定位轨迹；然后通过相对定位轨迹和射频定位 的比较实现对位置和方向的估计，获取定位结果；最后估计射频定位精度，设置 合造的判定阈值来区分出失真的射频定位结果，以减小n l o s 的影响。 本文从理论分析和m a t l a b 仿真实验两个方面评估了所提出的定位算法的性 能。验证结果表明，所提出的定位算法具有定位精度高、计算复杂度低的特点。 关键词：无线传感器网络；移动节点定位；位姿评估；非视距 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k s ，an o v e lt e c h n o l o g ya b o u ta c q u i r i n ga n dp r o c e s s i n g i n f o r m a t i o n ，i n t e g r a t e m u l t i f o l d s u b j e c t si n c l u d i n gm i c r o e l e c t r o n i c ，w i r e l e s s c o m m u n i c a t i o na n dw i r e l e s sn e t w o r k ，a n di s w i d e l yu s e di nm i l i t a r y , i n d u s t r i a l c o n t r o l l i n g ，e n v i r o n m e n t a lm o n i t o r i n ga n de t c i nm o s ta p p l i c a t i o n s ，d e t e r m i n i n gt h e p h y s i c a lp o s i t i o n so fs e n s o rn o d e si s t h eb a s i cr e q u i r e m e n t s t h ep r o b l e mo f s e l f - l o c a l i z a t i o n ，t h a ti s ，d e t e r m i n i n gw h e r eag i v e nn o d ei sp h y s i c a l l yo rr e l a t i v e l y l o c a t e di nt h en e t w o r k s ，i sac h a l l e n g i n go n e ，a n dy e te x t r e m e l yc r u c i a lf o rm a n y a p p l i c a t i o n s i nt h i sp a p e r , a ne f f e c t i v el o c a t i o nm e t h o di sp r e s e n tt oo b t a i na c c u r a t ep o s i t i o n e s t i m a t i o nf o rm o b i l en o d e sa n dm i t i g a t et h ei n f l u e n c eo ft h en l o sp r o p a g a t i o n w h e ns e n s o rn o d e st h a tc a na c q u i r et h ev e l o c i t yi n f o r m a t i o n f i r s t l y , t h er e l a t i v e l o c a l i z a t i o nt r a c k ( r l t ) ，w h i c hr e f l e c t st h es h a p eo ft r u et r a c k ，i so b t a i n e du s i n gt h e v e l o c i t yi n f o r m a t i o n t h e nt h ec u m u l a t i v ee r r o ro fr l t i sc o r r e c t e dw h i l et h eg l o b a l o p t i m u ms o l u t i o ni so b t a i n e db ym i n i m i z i n gt h ed i f f e r e n c eb e t w e e nr l ta n dr a d i o l o c a l i z a t i o nt r a c k t h e nat h r e s h o l di ss e tt od i s t i n g u i s ho b v i o u sd e v i a t i o nf r o mr a d i o l o c a l i z a t i o n f i n a l l y , am o r ea c c u r a t el o c a l i z a t i o nr e s u l tp r e s e n t s i t s e l ff r o mt h e c o r r e c t e dr l t s i m u l a t i o nr e s u l t ss h o wt h ep e r f o r m a n c e so fo u rm e t h o d si nt e r mo fa c c u r a c y a n dd e t e r m i n a t et h ep a r a m e t e rt h em o r ea d a p t e dr e l a t e dt ot h en e t w o r kc o n f i g u r a t i o n s k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；m o b i l en o d el o c a l i z a t i o n ；l o c a t i o na n d a t t i t u d ee s t i m a t i o n ( l a e ) ；n o n - l i n e o f - s i g h t ( n l o s ) i i 第一章绪论 本章简单地介绍了无线传感器网络线的定义，应用前景，网络结构以及节点 基本结构，同时本章也概述了全文的主要研究内容。 1 1 背景介绍 无线传感器网络研究始于上世纪8 0 年代【l 】，经过近三十年的努力，伴随着 无线通信技术、电子技术和嵌入式技术等的发展，将信息采集、数据处理和短距 离无线通信等多种功能集成到一个微小的体积内【2 】已经成为现实，这大大推动了 低成本、低功耗、集合多种功能的传感器节点发展。人类通过将大量这种节点分 布到某一监测区域内，然后这些节点可以通过与临近节点的无线通信构成一个协 作完成采集数据、处理数据等功能的自组织多跳无线传感器网络。无线传感器网 络提供了一种新的信息获取、信息传播和信息处理的方式【3 】，通过这种方式，人 们可以更加全面、深入地感知和认识物理世界，其巨大的应用价值引起了世界上 许多国家的军事部门、工业界和学术界的极大关注【4 】。有鉴于此，无线传感器网 络被美国商业周刊和m r r 技术评论杂志评为2 1 世纪最有影响力的十大 新兴技术之一1 5 j ，成为当前r r 领域研究热点之一。 无线传感器网络通常部署在一些不容易管理的区域，如森林、河流、大型建 筑物等【6 8 】。无线传感器网络的应用前景非常广泛，它在军事、环境监测、医疗 扩理、机场以及大型工业园区的安全监测等领域。随着研究的不断深入，传感器 网络将渐渐深入到人类生活的各个领域。 传感器网络具有可快速部署、可自组织、隐蔽性强和高容错性的特点，因此 非常适用于在军事上使用，利用传感器网络能够实现战场监控、目标跟踪【lo 】等 任务【9 j 。美国军方很早就启动了s e n s l t ( s e n s o ri n f o r m a t i o nt e c h n o l o g y ) 计划，该 计划的目的是利用无线传感器网络技术，建立一个廉价的无处不在的网络系统， 用以监测声学、磁场、压力、污染、毒物、温度、加速度、光学等物理量。 在科学、环保等研究领域中无线传感器网络主要起着数据采集的作用【1 1 1 ，比 如环保工作者希望采集河水湖水等的数据，来研究工业废水对附近水域水质的影 响；地质学家为了研究某个地质变化，需要采集有关地区地质情况的各种数据。 例如，美国学者曾在大鸭岛上部署了一个多层次的传感器网络系统，用来监测岛 上海燕的生活习性。 如图1 1 是无线传感器网络的管理系统，它通常包括任务管理节点( t a s k m a n a g e rn o d e ) 、汇聚节点( s i n kn o d e ) 和传感器节点( s e n s o rn o d e ) 口】。管理系统主要 为观察者向传感网络发送各种控制信息，以及查看、分析节点采集到的数据提供 方便。在管理系统中，节点采集到的数据进行初次处理后，可以通过路由协议选 择通信路径，在相临的传感器节点之间传输，数据可能在传输过程中也可能被不 同的节点多次处理。当数据传送到汇聚节点时，这些数据就可以通过与汇聚节点 相连的互联网或卫星等到达任务管理节点。传感器节点除了要完成本地数据采集 和处理外，还要对其它节点发送过来的数据进行存储、融合及转发，并与其它传 感器节点合作，以完成某些复杂的任务【9 】。反之，观察者通过卫星或互联网将控 制信息发送到汇聚节点，然后进一步扩散到每一个节点从而实现对网络的配置与 控制，例如指定某一区域内的节点进入休眠或者变换传感器节点采样频率等。 图1 1 无线传感器网络管理系统结构【2 】 如图1 2 所示，目前普通的传感器节点通常由四部分构成：微控制单元 ( m c u ) 、传感器、射频通信模块和能量供应模块【2 】。微控制单元( m c u ) 负责处理 来自传感器采集的数据或射频通信模块传输的数据，并以此来控制节点的各种行 为，例如休眠等；传感器负责采集所在区域的信息数据，并提交给处理器；射频 通信模块负责与临近节点的无线通信，在节点间收发数据和控制信息；能量供应 模块为传感器节点提供运行所需的能量，通常采用微电池【9 j 。 2 圈1 2 传感器节点结构【9 】 在传感器网络中，传感器节点能量有限、可靠性差、无线模块的通信距离有 限，对定位算法和定位技术提出了很高的要求。因此传感器网络的定位算法逶常 需要具备以下特点【9 l ： ( 圭) 健壮性：传感器节点的硬传配置低、麓量少、可靠性差，测量距离时会 产生误差，算法必需要具有较好的容错性。 ( 2 ) 麓量高效：尽可能地减少算法计算的复杂度，减少节点闻的透信开销， 以尽量延长网络的生存周期。通信开销是传感器网络的主要能量开销。 ( 3 ) 分布式计算：每个节点计算囊身位置，不麓将所有信息传送到某个节点 进行集中计算。传感器网络的节点随机分布，不能依靠全局的基础设施协助定位。 1 2 研究意义 移动节点定位算法的研究对无线传感器网络的应用和发展都具有重要的意 义。移动节点得到了越来越多的应雳，移动节点除了可以用来辅助静态节点定位 1 2 , 1 3 1 ，扩展网络的覆盖范围，提高网络连接度h 4 1 等外，还广泛地威用于工厂物流、 智缝家居以及环境保护等领域。 在无线传感器网络中，不管是静态节点还是动态节点，节点定位算法都是一 个至关重要的问题。首先它是各种应用和服务的基础之一。在无线传感器网络的 各种应用中，采集数据的节点位置是需要知道的最基本的信息之一【l5 1 ，在环境 检测、目标跟踪等应用中如聚不知道采集点的位置，那么所采集的数据将是毫无 意义的【16 】；其次，无线传感器网络的很多关键技术都需要利用节点位置信息。 例如，地理路由协议需要直接利用节点位置信息进行数据传递，以避免信息在整 个网络中的扩散，并可以实现定向的信息查询朝，有些路由协议【孵。9 1 也需要节点 位置信息来提高路由效率；网络拓扑控制机制需要利用节点位置信息构建拓扑结 构图，并评估节点晌分布情况。对于移动节点更是需要时时知道自身的位置。 同时移动节点定位问题也是一个技术难点。对移动节点，明显不可能通过预 置来实现定位；为了尽可能地降低成本，每个节点的处理器性能、存储器容量、 无线收发器的通信距离以及电池能量都是极其有限的，如果让所有节点都安装全 球定位系统( g p s ) 【2 0 】，不仅增加了成本，而且会使节点的能量很快消耗殆尽，并 且所到使用场合的限制，因丽这种方法不适合实际使用。传感器节点能力的限制 也要求定位技术尽可能地降低计算复杂度和节点间的通信开销，以降低功耗，延 长整个网络的生命周期。另外，节点的运动性也增加了节点定位难度。 由此可见，无线传感器网络迫切需要一种复杂度低和容错能力强的定位算法 来得到移动节点的位置，这一方面能够提高无线传感器网络的性能，另一方面也 能降低成本，有利于它的大规模应用。 1 3 研究内容 前面提到移动节点的定位具有重要意义。本课题的研究内容首先是针对自主 移动节点的运动特点，分析利用运动轨迹来辅助提高移动节点定位精度的可行 性，以此为依据提出一种利用射频定位来修正露主移动节点累积误差的位姿评佶 l a e 算法。 在第二章中，我们介绍了无线传感器网络节点定位基本原理以及其数学模 型，并分析当前节点定位技术r s s i 、a o a 、t d o a 、t o a 等的优缺点。 在第三章中，我们对自主移动节点运动分析的基础上，提出一种利用射频定 位结果来修正相对定位累积误差的方法，然后对算法进行改进以适应实际定位中 会遇到的非视距等影响。 在第四章中，我们将本文提出的定位算法分成三部分进行仿真，分别仿真验 证了位姿评估、n 囱适应以及偏差判定的效果。 最后在第五章中，对本文的工作做了一下总结，给出有待解决的问题，指明 迸一步研究的方向。 4 第二章基本定位技术介绍 本章首先介绍了无线传感器网络的基本定位算法技术，以及擞前主要的基本 定位技术。定位算法的基本原理是直接或间接测量移动节点与信标节点之间的距 离、方位或者其它连接性信息，然后再根据这些信息计算移动节点的位置。 2 1 基本定位算法 在无线传感器网络中，节点定位算法可以分为基于距离的定位算法和距离无 关的定短算法。前者需要测量相邻节点闻的距离或者方位，然后剩焉测量距离来 计算未知节点的位置；后者无需测量节点间的距离或者方位，而是利用节点间的 饿计距离计算节点位置。本文将主要考虑基于距离的定位算法。 基于距离的定位机制通常可以分为二个阶段：测距阶段和定位阶段。在测距 阶段期闻翌，未知节点测量鑫身到有效范围内信标节点的距离，既可以测量未知 节点与信标节点的直线距离，也可以使用二者之间的跳段距离作为直线距离的近 似；在定位阶段期间里，未知节点在获取自身与三个或者三个以上信标节点的距 离或者角度后，利用三边测量法等实现定位。 在传感器网络的节点定位中，将可以实时获取自己位置的节点称必信标节 点。信标节点的实现成本较高，并且受到使用限制，因此一般比例e t a , j , ，可以通 过携带g p s 定位设备等手段获得精确位置。除了信标节点外，其他传感器节点 都是未知节点，它们可以通过测量与信标节点的相对位置信息来确定自身位置。 传感器节点定位过程中，未知节点在获得相对于邻近信标节点的距离或相对 角度后，通常使用三边测量法、三角测量法以及极大似然估计法等9 1 计算自己的 位置。 2 1 1 三边测量法 如图2 1 所示，已知a ，b ，c 三个节点的坐标分别是k ，虼) ，k ，) ，阮，咒) 以及它们到未知节点d 的距离分别为d a ，唬，或，假设d 的坐标为轼，yj 那么，存在下列公式： 5 可得节点d 的坐标为： 瓜i 再而= d 。 瓜i 再丽= 吃 妊i 再而= 吃 ( 2 。1 ) 蛩y 虼- 一鼍y c ) ) 7 l i x 2 a 一+ 菇一鬈2 十吱2 一露2 22 ( 2 2 ) 2 ( 虼一鼍列l 一+ 菇一鬈十吱一露j p 一7 ak ，虼) b 如，乃) 图2 1 三边测量法 c ( 乙，咒) 2 1 2 三角测量法 如图2 2 所示，已知a ，b ，c 三个节点的坐标分别为( 茏，咒) ，( x b ，y b ) ，( 苁，y c ) ， 节点d 相对于节点a ，b ，c 的角度分别是：_ a d b ，z a d c ，z b d c ，假设d 的坐标分别为b ，yo 对于节点a ，c 和角z a d c ，如果弧a c 在a a b c 内，那 么能够惟一确定一个弱，对圆心为铗k ，勤，) ，半径为i ，那么 a = - a 0 1 c = f 2 万一2 z a d c ) ，并存在下列公式： 抵哥可i 订= 吒 瓜i 哥可i 可= 尹 ( 2 3 ) k 心) 2 + ( 乩一咒) 2 = 2 ，i 2 2 ，i 2c o s 蠢上式可以确定圆心qx o l ，y 0 1 ) 点的坐标和半径毛。圊理对a ，b ，_ a d b 黍jb ， c ，么肋e 分别确定圆心d 2 k ：，y o ：) ，半径吃，圆心g k ，y o ，) ，半径吩。 6 、1，、l， 一 一 荡 ，j、，l 2 2 p。l = 1 x 、 。l 最后利用三边测量法，由点0 1 ，0 2 ，0 3 确定d 的坐标。 a 图2 。2 三角测量法 e 2 1 3 极大似然估计法 如图2 3 所示，咒个信标节点豹坐标分别为k ，y ，) ，沁，y 2 ) ，( ，y 。) ， 它们到节点d 的距离分别为破，d ：，吱，假设节点d 的坐标为b ，y ) 。那么存在 下列公式： f ( 鼍一善r + 魏一y ) 2 = 砰 ji l ( x n - x ) 2 + ( 羹一y ) 2 ：矗： ( 2 4 ) 使用标准的最小均方差估计方法可以得到节点d 的坐标为：曼：( a r a ) - 1 a r 易 f2 如一蕞) 式中a = i ； 1 2 ( 钿一蕞) 7 2 l ， 弋 一 2 n 2 o h + 东 一 一 砰 噍 q 协 矗 政 9 一，； 一 糖 ( x 1 y 1 ) ( x r t 。y n ) ( x 3 。y 3 ) 图2 3 极大似然估计法 2 2 基于距离的定位技术 在基于距离的定位中，测量节点间距离或者方位时采用的方法有r s s i 2 2 1 ， t o a t 矧，t d o a 矧或者a o a 2 5 1 等。其中r s s i 方式是使用褥最多。 2 2 1 基于r s s i 的定位 在基于接收信号强度指示r s s i 的定位技术中，发射节点的发射信号强度已 知，接收节点测量收到信号的强度，计算信号的传播损耗，然后利用理论或者经 验模型将传输损耗转亿为距离，最后幂| j 用已有的算法计算出节赢的位置。r s s i 方式虽然符合低功率、低成本的要求，但相应精度也较低。 r a d a r 2 2 j 是一个基于r s s i 技术的室内定位系统，用以确定目标节点在楼 层内的位置。在这个系统中，未知节点定期发射信号，发射功率预先知道，基站 接收到信号后测得其接收功率，从而可以计算出信号的传播损耗，然后利用信号 传播模型来计算发射节点的位置。 将射频信号强度转化为距离所用到的信号传播模型有两种：经验模型和理论 模型。经验模型是指建立一个位置和信号功率的关系数据库。其方法是，在室内 选取一定数量的测试点，发射节点在这些点上发射信号，记录下各基站接收到的 信号功率，实际定位的时候将测得的信号功率和数据库中的信号功率进行比较， 以定模式选出匹配程度最好的那个信号功率组对应的位置作为节点位置。理论 模型即信号衰减与传播距离之间的关系式如下： 删，c d b m = p ( d o ) d b m - 1 0 n l o g 时 发群2 旋喜c 仁5 ， 矸矽表示基站接收信号功率，e ( d o ) 表示参考节点发射的信号功率，n 表示路 径长度和路径损耗的比率，如表示参考节点和基站之间的距离，n w 表示节点和 基站之间的墙壁个数，c 表示信号穿过墙壁个数的阂值，w a f 表示信号穿过墙 壁的衰减因子，d 表示未知节点和基站之间的距离。基站在测得接收信号功率后 利用这个模型就可以计算出未知节点和基站的距离，当计算出节点与三个或三个 以上基站的距离后，利用三边测量法计算节点的位置。 利用理论模型计算节点位置的方法精度比前一种方法差，因为在实际环境中 各种因素的不确定性导致了理论模型往往与实际情况相差很远。有很多文献对这 个方面作了研究，文献矧中s p o to n 定位系统利用的信号衰减模型结合了理论 模型( 1 r 2 ) $ t l 实际环境。文献堋中l a n d m a r c 定位系统和文献2 研中提出的f e r r e t 系统则对信号衰减模型进行动态校准，通过这种方法尽管能够提高定位精度，但 需要在网络中布置大量额外的接收节点，增加了网络配置的成本。 2 2 2 基于t o a 的定位 在基于到达时间t o a 的定位机制中，已知信号的传播速度，根据信号的传 播时间来计算节点间的距离，然后利用已有算法计算出节点的位置。例如可以采 用噪声序列产生声波信号，然后利雳声波的传播时间来测量节点闻的距度。与无 线射频信号相比，声波对节点硬件的成本和复杂度的要求都低，但是容易受到大 气条件的影响。 基于t o a 的定位精度高，但需要节点间精确的时间同步，无法用于松散耦 合型定位，因此对传感器节点的硬件和功耗提出了较高的要求。 2 2 3 基于t d o a 的定位 在基于t d o a 的定位机制中，发射节点同时发射两种传播速度不同的无线 信号，例如射频信号与声波信号，接收节点根据这两种信号到达的时间差以及已 知这两种信号的传播速度，计算两个节点之间的距离，然后通过已有的基本定位 算法计算窭节点的位置。 9 例如c r i c k e t e 2 4 1 系统，它用来确定移动或者静止节点在大楼内的具体房间位 置。在c r i c k e t 系统中，每个房间都安装有信标节点，信标节点周期性发射无线 射频信号和超声波信号，无线射频信号中包含有信标节点的位置信息，而超声波 仅仅是单纯脉冲信号，没有任何语义。由于无线射频信号的传播速度要远大于超 声波的传播速度，未知节点在收到无线射频信号时，同时打开超声波接收机，根 据两种信号到达的时间差和各自的传播速度，就可以计算出未知节点到该信标节 点的距离。然后通过比较到各个邻居信标节点的距离，选择出离自己最近的信标 节点，从该信标节点广播的信息取得自身的房间位置。 t d o a 技术受限于超声波传播距离有限( w s n 所使用的超声波信号通常传播 距离仅为2 0 - - - 3 0 英尺，因而网络需要密集部署) 和n l o s 对超声波信号传播的影 响，同时成本和能耗也对该技术在低能耗的传感器网络中使用提出了挑战。但是 t d o a 技术测距误差小，有较高的精度。 2 2 4 基于a o a 的定位 在基于到达角度a o a 的定位机制中，接收节点通过天线阵列或多个超声波 接收机感知发射节点信号的到达方向，计算接收节点与发射节点之间的相对方位 以及角度，再通过三角测量法计算出节点的位置。 a o a 定位不仅能够确定节点的坐标，还能提供节点的方位信息。但a o a 测 距技术易受外界影响，且a o a 需要额外硬件，并不适合于大规模的传感器网络。 2 3 射频定位的镜效应 当节点所附近的信标节点处在一条直线或者接近一条直线时，射频定位算法 就有可能产生如图1 5 所示的镜效应。图1 5 以三个信标节点为例，由于测距的 误差，导致节点位置被定到信标节点的另一侧，此时会产生很大的定位误差。测 距的误差越大，镜效应产生的可能性就越高。 1 0 2 4 小结 二：专 图1 5 射频定位的镜效应 本章首先介绍了无线传感器网络定位算法的基本技术，着重介绍基于测距的 定位算法三个基本原理一一三角测量法、三角测量法以及极大似然估计法；然后 介绍了现有的基本定位技术，举例并分析其优缺点。 第三章基于轨迹的自主移动节点定位算法 自主移动节点指能够控制或者测量自身运动的节点，例如文献“2 。1 4 1 中所要求 的就是这一类节点，它们不仅仅需要知道自身的位置，同时还需要能够运动到合 遣的位置以执行特定的任务，这就要求它们能够控制或者测量自身的运运。本章 将给出利用自主移动节点运动特性实现定位的一种方法。 现有的移动节点定位算法 2 2 - 2 5 , 2 9 - 3 1 1 基本上都属于射频直接定位算法，并非专 门针对自主移动节点，因此这些算法也都没有考虑利用节点的运动特性来改善定 位精度。对自主移动节点而言，如果能够有效地利用节点的运动速度信息，将有 利于提高移动节点的定位精度。 3 。1 自主移动节点相对定位 移动节点如图3 i 所示，在不考虑使用陀螺仪等的情况下，节点一般无法直 接获取全局的方向玟，僵是可以通过其它低成本的方法来获取速度方向的改变角 度0 ，以及运动的距离c 。我们将速度方向改变角度口，以及运动的距离c 合称 为移动节点速度信息。节点利用速度信息可以估计自身的位置以及速度方向信 息，即位姿信息。 图3 1 自主移动节点 1 2 如图3 2 所示，移动节点从点a 运动到点b ，节点跟据上一时刻的位姿状态 卜心舷叫+ 磁嘲m ， 。， j ) = 一1 ) + p ) = ( o ) + o ( i ) 图3 2 移动节点从a 运动到b 我们将这种定位方式称为相对定位方式。如果给定的初始位置以及初始运动 方向是正确的，在没有测量或者控制误差的情况下，相对定位轨迹应该是与真实 运动轨迹一致的。但由于误差是必然存在的，我们假设路程误差n c ，角度误差 n o ，都是均值为0 ，方差为r c o v 的高斯白噪声，那么它实际得到的位姿状态为 噼柑) + 隧跚m ) ( + c ( 砌 kk ) = 一1 ) + p ) + 口 ) = ( o ) + 臼( i ) + n o ( i ) ( 3 2 ) 由式( 3 2 ) 可以看出路程误差、角度误差将逐渐累积起来，最终将使节点丧失 位置以及速度方向信息，如图3 3 所示。但是，我们同时也注意到，虽然节点可 能丧失位置以及速度方向信息，但是其相对定位轨迹的形状( 指某一片断) 仍然可 以反映其真实运动轨迹的形状。 5 0 4 0 1 0 口 d1 02 d3 04 口5 0 图3 3 相对定位轨迹( r c o v = 0 0 3 ) 3 2l a e 位姿评估算法 通过对自主移动节点运动特性的分析可以知道，在能够正确获取初始方向以 及初始位置的情况下，相对定位的精度要比射频定位高出许多。但由于相对定位 使用了之前的定位结果，因此其定位结果具有历史相关性，存在误差累积的缺点， 必须不断地修正这些误差，否则节点最终将丢失方向以及位置信息。相对地，射 频定位利用实时获取到的射频信号特性来完成定位，因此它不存在误差累积的影 响，然而射频信号很容易受到各种各样的干扰，从而导致信号特性的波动较大， 定位精度较低。 要利用相对定位首先就必须消除它的累积误差，如图3 4 所示，依据相对定 位轨迹与实际运动轨迹的局部相似性，通过对它进行一定的平移、旋转等变换， 使得其与射频定位结果的差别最小，然后根据平移量以及旋转量来估计相对定位 的累积误差，进而消除累积误差。 1 4 e 、 砸 u i j d 鼍 距离，m a l 初始分布 距离i | m b ) 变换的优化目标 图3 4 初始分布与优化目标 这是一个非线性优化问题，需要求解的量包括平移量以及旋转量等，这类问 题求解一般采用遗传算法或者模拟退火算法等优化算法来求实现，但是这类算法 不仅仅计算量巨大，更需要较大的存储空间，这里它们并不适用。如果要使其适 用于传感器网络的话，必须有一种能够快速、简单、计算量小的方法来获取一个 可以接受的优化解，当然这个解不一定是最优解。接下来我们将给出一种快速求 解次优解的方法。 3 。2 1l a e 位姿评估算法 u 垣给出了一种计算复杂度低的解决方法，具体说明如下： ( 荀图3 。5 显示了次射频定位以及相对定位结果麓初始分布情况。从图中 也可以看出，此时的相对定位轨迹完全丧失方向以及位置信息。 ! e 、 褪 u i j 口鼍 图3 。5 “垣初始分布 其轨迹表示如下： - i x ，ix ，2 x 掰】( 3 3 ) = 区矗，x 矗：x 脒】 ( 3 4 ) 式中y r ，分别代表由长度为的射频定位结果与相对定位结果组成的轨迹； 潞，x u 分别代表相应轨迹中第i 次定位结果。 ( b ) 如图3 6 所示，平移相对定位结果以及射频定位结果，使二者的中心为 原点。可以得到平移后的射频定位以及相对定位轨迹坐标矩阵分别如下 1 6 c = 妞，。c x ，：c x 州】 = 阻，l c r x ，2 一c r 式中c 州= 丙1 善nx 一，代表射频定位轨迹中心。 c = 陋 lc x 2 c x l l l 】 = x 捌一c h nx 2 一 式中= 丙1 善nx 代表相对定位轨迹中心。 e 、 蟊厦 戡翻 a 鹭 x , n - 】 ( 3 5 ) ( 3 6 ) 图3 6l a e 轨迹平移 ( c ) 如图3 7 ，绕原点旋转相对定位轨迹，使其与射频定位结果的差值最小。 1 7 e 褪 t 工j d 鼍 图3 7l a e 的优化目标 相对定位轨迹绕中心( 原点) 旋转口，得到新的坐标矩阵可表示为 尺c 影w ( 秒) = r c x 。( 口) r c x 。：( 口) r c x 圳( 秒) 】 r 瓯( 班盛- c o s ( 9 8 ) ) - 啷s i n ( 刚( 8 ) 锻撕 此时射频定位与相对定位的差别平方和为 d i f f ( 8 ) = r c y 圳( 8 ) 一c 0 2 那么l 嗵的优化目标就是寻找如下0 秒= m i n d i f f ( 8 1 为了求解p ，首先将式( 3 9 ) 的d i f f ( o ) 展开如下 ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 螂( 口) = l 陋c p ) 一c 0 2 = n 牌锻。黛一n ) 一c x ，( 惫一n + f 鼍2 - 淄s i n 圳( o ) 1 q1 2 = 羔b 未+ c ) ，艇2 + 饿一2 + c ) 7 2 2 黜蹦一c o s p ) 一2 c y c ) ，一c 。s p ) 一2 。c x 埘c y 一- s i n ( o ) + 2 c y c x 一s i n ( a ) ) = 兰k + 锣簸2 + “一2 + 锣：) 一2 a c o s p ) 一2 b n 汐) 绞= c x h l - c x , ；+ c y u ) = c ，c ( 3 。1 1 ) o ( 3 1 5 ) ( 3 1 6 ) ( 3 1 7 ) 通过求解可得处于一个周期 o + 5 n 1 5 1 r ) 内且使磁圆取极( 最) 小值的0 为 1 9 、l，、l，p 吣遗 一p 矧 i i 氏强= o 一0 5 石 0 5 趸 a r gt a n ( b a ) a r g t a nb a ) + ，r 由于d i f f ( o ) 连续可导，且一个周期内只有一个极小值，因此该极小值也就是 函数的最小值。需要注意的是a = o ，b = o 这种情况只有在节点长时间不动的情况 下才会出现。这种情况下，虽然任意的护都熊使d i f f ( o ) 取极( 最) 小值，但本文在 实际运算过程中取其值为o 。 ( d ) 如图3 8 所示，得到n 之后，再次平移相对定位轨迹，使其中心为原 射频定位中心c ，至此完成了平移一旋转一再平移的变换过程。 、 褪 t c u 搿鼍 图3 8 出的最终获取的结果 在计算出。之后，那么可以得到所旋转量为n ，平移量蝴r 为： 阡q 茹黝 渤 假定当前的相对定位结果为鼍，可以获取最终定位结果以及运动方向为 8，l 3 ，t、l，、l-，、t， o 0 = 岛9巷， o o o 0 o l j 一一 = 0如麓亿 蜘 - c s 惫黜：啬缎珊m ) + 2 。， d 一惫) = + 。( 3 2 1 ) 程代表相对定位的方向参数，修正之蜃的方向为原方向再加上对累积误差的 估计。 3 2 2 利用l a e 实现射频定位精度的话计 一般情况下，移动节点无法获得正确节点位置，因而节点没有办法来计算射 频定位精度。另外由于移动节点应用环境可能处于不断变化中，这决定了节点不 可能预先知道射频定位精度。 另一方面，在圈3 8 中可以看出，在得到定位位置的同时，如果用相对定位 结果替换真实位置的话，还可以获取对射频定位精度的估计。为了减小累积误差 的影响，本文选择轨迹中心附近的妫个点来计算精度的估计值如下( n o 取值为 1 0 1 ： ；= 4 d i f f ( o m i n ) n o ( 3 2 2 ) 仍以瑟3 8 为例，实际的射频定位精度为1 9 5 m ；羽用式( 3 。9 ) 可以得到节点 对射频定位精度的估计为2 15 m 。 3 3 改进型l a e 算法 l 能可以有效地估计并修正相对定位的累积误差，但仍然存在以下两个缺 点：l 址是基于非视距的，也就是假定节点与信标节点之间不存在障碍物；l a e 算法中参数是预先设定的，有可熊不是最佳的值。因此为了克服这两个缺 点，利用对射频精度的估计来完成n 自适应调整，通过合理设定判定闽值来区 分出偏差大的射频定位结果以克服非视距等影响。 3 3 。ll a e 的n 值囱适应调整 的取值首先关系到l 掘定位精度直接相关的，如图3 9 及3 1 0 所示，过 大的以及过小的都会对累积误差估计适成不良的影响。只有合适的僮才 能保障最后获取到的定位精度。 2 l 董 砸 u i j 口耸 e 錾匿 缸霜 融 距离椭 a ) 初始分布 距离，m b l 变换的优饨目标 图3 9n 值过小时的l 铖效果( n - - 6 ) 艟 t 列 嗽 、 耀 t i ：i j 口乩 距离加 b ) 变换的优诧露标 图3 。l o 值过大时的“蠖效果( n = 5 0 ) 当n 值过小时，如图3 9 所示，射频定位不足以估计相对定位的累积误差。 反之，当n 值过大的话，如图3 1 0 所示，相对轨迹的形状相对于真实轨迹会有 较大的出入，也得不到较好的结果。 值不能设定为一个定值，当射频定位精度p 越小时，也应该越小，才能 尽可能减小累积误差带来的影响；反之当p 越大时，也应该越大，才能尽可能 减小射频定位误差的影响，获取精度较高的位姿信息。 如图3 1 1 本文中的取值为 端m i n m a x k 石+ 】，】；哪( 3 2 3 ) 其中，a 榉取值为1 3 ，k 取值为l ，晌为l o ，麓瞰为5 0 ，墨】表示对x 取整。 3 2 。2 复杂环境下的l a e 图3 1 1n 的取值曲线 在非视距情况下，节点的射频信号受到极大的干扰，射频定位会出现严重的 偏差。除此之外，射频定位的镜效应也会对射频定位产生很大的影响。由于l a e 是以射频定位结果来校正相对定位累积误差，因此如果将严重偏差的定位结果大 量弓| 入的话，将会对l a e 产生很大影响。如图3 1 2 所示，射频定位本身产生较 大偏差，对相对定位累计误差的估计出现较大偏差，最终导致得到定位结果出现 很大偏差。 距离，m a ) 失真的初始分布 距离，m 失真的优化结果 图3 1 2 射频定位产生较大偏差时的l a e 效果 为了提高移动节点定位精度，就毖须减小镜效应以及菲视距的影响。本文利 用相对定位结果与射频定位结果的偏差来估计射频定位与真实位置的偏差，并且 一个判定阚值r 相比较，著偏差大予r ，则认为射频定位误差过大，不与考虑； 反之若偏差小于7 7 ，则认为射频定位误差落在可以接受的范围里。 r 的取值是区分的关键，如果r 取值过大时，则无法把失真节点选择出来； 如果r 取值过小，则会把正常的射频定位结果淘汰掉。显然阈值r 是与射频定位 精度相关的，当射频定位精度p 越高，阈值刁应该越小；精度p 越低，阈值蹿应 该越大，才能有效地区分失真定位结果。由于射频定位的精度是不可知的，因此 利用式( 3 9 ) 作为对射频定位精度的估计。 除了将偏差大的定位结果区分出来之外，我们还要考虑节点在连续的非视距 误差导致累积误差较大时如何尽快地恢复。如图3 1 3 所示，在连续的非视距下， 由于区分出了偏差大射频定位结果，l a e 无法及时更新累积误差，使得累积误 差重新积累起来，接下即使非视距影响消失，相对定位与射频定位之间的差距仍 可能一直保持在阈值之外，丢失了方向信息。 1 0 4 0 图3 13 射频定位连续较大偏差情况 定义n 圳为从“时刻到k 时刻之间，x ，被判定为失真的次数。为了有利 于消除节点相对定位的累积误差，阂值弩应该随着增加丽变大。 综上所述，阈值，7 的确定应该满足两个条件：首先，能够将严重失真的射频 定位结果区分出来；其次，应该有利于节点从相对定位的累积误差中恢复。 本文采用的阈值如下： 刀= 鬈，柏- 峨n 圳惫 2 2 0 。 c 3 刎 l + 。乏z u 其中a = 1 5 ，b 裟o 。0 1 。 a 的值反映了可接受的射频正常定位偏差，偏差小于平均定位精度a 倍的 射频定位结果处于可接受范围。b 的值反映了连续大偏差下，7 7 的增长速度，表 明阈值扩张速度。它表示非视距下相对定位以及射频定位之间的折衷。图3 1 4 反映了这条曲线。 6 5 4 3 2 8 图3 1 4n 的取值曲线，蟹对p 归一 3 4 完整的基于l a e 的定位算法 前两节我们给出了利用射频定位来修正相对定位累积误差的一种方法，接下 来我们将给出完整的定位算法n a l a e l 。图3 。1 5 是n a l a 阻的流程匿。 2 7 图3 1 5n a l a e l 的流程图 n a l a e l 流程图中需要特别说明的是它的初始化过程：在初始化阶段， 节点为相对定位设定初始位姿状态如下 择黔【o o r ( 3 2 5 ) 1 ( o ) = 0 一7 初始饿姿也可以设定为其他任意值，且不会对最终定位结果产生任何影响。 这是因为n a l 墟乙只利用相对定位结果的轨迹形状，与具体位置无关。 另外考虑到具体应用以及为了方便仿真实验说明l a e 修正累积误差的性 熊，n 值自适应的效果以及偏差判定的效果，给出两耪减弱型算法：l a 飘l 以及 n l a e 乙。 l a e l 的流程图如图3 1 6 所示，与n a - - l a e l 相比，缺少n 值自适应以及 偏差判定。 能。 图3 1 6 队e l 的流程图 n l a e l 的流程图如图3 1 7 所示，与n a - - l a e l 相比，缺少偏差判定功 图3 1 7n 一队e l 的流程图 3 5 小结 本章详细阐述了所提出的基于位姿评彳吉的移动节点定位算法。首先介绍自主 移动节点相对定位的特性，然后给出利用射频定位来修正相对定位累积误差的 l a e 算法，接着结合实际情况，加入偏差判定以克服非视距环境以及射频定位 的镜效应影响，最后，在位姿评估算法以及其改进型的基础上，给出了完整的移 动节点定位算法。 第四章仿真实验与性能分析 本章用m a tl a b7 3 对所提出的基于l a e 的移动节点定位算法n a - l a e l 进行 仿真实验以研究其性能。由于定位问题属于无线传感器网络的应用层，因此为了 简化仿真模型，本文没有仿真传感器节点的底层通信模块，仅仅实现上层的定位 模块，因为这已经满足我们的实验要求了。 4 1 仿囊算法实现 仿真实验过程如图4 1 所示 算法傍真程跨t | 生能谮估程序图澎显示 图4 。1 仿真实验过程 4 1 1 基本网络参数黻及茬麓指标 传感器节点的位置用一个二维坐标表示，并且任何时候都是绝对坐标，如节 点a 1 的位置( 3 1 ，1 4 ) 。 定位精度是评价定位算法性能的重要指标，较小的定位误差说明定位算法的 精确度较高，我们采用如下所示的定位误差计算公式： z 矧hx ：, r 一龙i m e a n e r r o r = j = k 一 r 其中，n 是移动节点总定位次数，屯是由定位算法得到的第i 个未知节点的 坐标，一m 是第f 个未知节点的真实坐标。 4 1 2 选用的射频定位算法 仿真实验选择文献2 9 1 中的d t n ( d y n a m i ct r i a n g u l a ra l g o r i t h m ) 作为射频定 位方式，当然并不限于这种算法。d t n 是基于r