（控制理论与控制工程专业论文）基于移动信标优化路径的定位算法研究.pdf

ad i s s e r t a t i o ns u b m i t t e dt og u a n g d o n gu n i v e r s i t yo f t e c h n o l o g yf o r t h ed e g r e eo f m a s t e ro f e n g i n e e r i n gs c i e n c e r e s e a r c ho nl o c a l i z a t i o na l g o r i t h mb a s e do n m o b i l eb e a c o nw i t ho p t i m a lp a t h m a s t e rc a n di d a t e ：x i ex i a o s o n g s u p e r v i s o r ：p r o f c h e n gl i a n g l u n m a y2 0 10 f a c u l t yo fa u t o m a t i o n g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 0 0 6 摘要 摘要 无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器 网络大多数应用的基础。无线传感器网络应用的大多数领域，如：目标监测与跟 踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需要研究更 为有效的定位算法，降低定位成本，提高定位精度。 针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法 进行了研究，该定位算法能够实现节点的高效率定位。文章在d v - h o p 定位算法 中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本 文的主要完成的工作有： l 、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于 信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。 2 、提出基于移动信标改进的d v - h o p 定位算法，该算法在d v - h o p 定位算法 的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自 己的位置信息，形成多个虚拟信标，研究平均跳距离的加权算法和信标节点的动 态选择算法，降低定位的成本和布网的复杂度，提高节点定位的精度和效率。 3 、结合基于移动信标改进的d v - h o p 定位算法，提出了面向无线传感器网 络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网 络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通 信开销，提高算法的效率。 最后在o m n e t h 仿真环境下，仿真基于移动信标的定位算法，建立包括移 动智能节点和普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节 点的位置，仿真表明，基于移动信标优化路径的定位算法既改善了定位的精度， 又减少了定位算法的通信开销，提高无线传感器网络节点定位效率。 关键词：无线传感器网络；移动信标；优化路径：o m n e t + + ；智能节点 a b s t r a c t a bs t r a c t w i r e l e s ss e n s o rn o d el o c a l i z a t i o ni so n eo ft h ek e yt e c h n o l o g i e sf o rw i r e l e s s s e n s o rn e t w o r k s i t st h ef o u n d a t i o no fm o s tw i r e l e s ss e n s o rn e t w o r ka p p l i c a t i o n s ， s u c ha s ：t a r g e ts u r v e i l l a n c ea n dt r a c k i n g ，r o u t i n ga n do t h e rl o c a t i o ni n f o r m a t i o n a c q u i r i n g ，a l lo ft h e s en e e dt ok n o wt h el o c a t i o ni n f o r m a t i o no f t h en o d e s s ow en e e d m o r ee f f e c t i v el o c a l i z a t i o na l g o r i t h mt or e d u c et h ec o s ta n di n c r e a s et h ep r e c i s i o n t nr e s p o n s e ，t h ep a p e rr e s e a r c ht h en o d e sl o c a l i z a t i o na l g o r i t h mf o rw i r e l e s s s e n s o rn e t w o r kb a s eo nm o b i l eb e a c o nw i t ho p t i m a lp a t h t h i sa l g o r i t h mc a na c h i e v e l l i g he f f i c i e n c yo fp o s i t i o n i n gn o d e s w ei n t r o d u c e dm o b i l eb e a c o nn o d ei n t od v - h o p l o c a l i z a t i o na l g o r i t h m ，a n ds t u d yt h ed y n a m i cb e a c o nn o d es e l e c t i o na l g o r i t h ma n d m o v i n gp a t ho p t i m a la l g o r i t h m t h e s em a j o rw o r k sa r e ： 1 s u m m a r i z e sc o m m o nr a n g e f r e el o c a l i z a t i o na l g o r i t h ma n dt h ea l g o r i t h m s b a s eo nb e a c o n , s t u d yt h ep o s i t i o n i n gm e c h a n i s mo fl o c a l i z a t i o na l g o r i t h m sb a s eo n b e a c o n 2 i m p r o v i n gd v - h o pl o c a l i z a t i o na l g o r i t h mb a s e d o nm o b i l eb e a c o n , t h e a l g o r i t h mu s eam o b i l eb e a c o n n o d et o m o v ei n t h en e t w o r ka c c o r d i n gt oa p r e d e t e r m i n e dp a t ha n db r o a d c a s ti t s l o c a t i o ni n f o r m a t i o nt h a tc r e a t ev i r t u a lb e a c o n s w es t u d yt h ew e i g h t e da v e r a g eh o pd i s t a n c ea l g o r i t h ma n dt h ed y n a m i cb e a c o nn o d e s e l e c t i o na l g o r i t h mt or e d u c el o c a l i z a t i o nc o s t sa n dc o m p l e x i t yo fd i s t r i b u t i o n n e t w o r k sa n di m p r o v ea c c u r a c ya n de f f i c i e n c yo f n o d el o c a l i z a t i o n 3 c o m b i n e dw i t ht h ei m p r o v e dd v - h o pl o c a l i z a t i o na l g o r i t h mb a s e do nm o b i l e b e a c o n ，w ep r o p o s e dm o b i l eb e a c o np a t hp l a n n i n gm e t h o df o r w i r e l e s ss e n s o r n e t w o r k s g r a p ht h e o r yi s i n t r o d u c e di n t ot h em o b i l ep a t hp l a n n i n g ；b ya c q u i r i n g c o n n e c t i v i t yc o n d i t i o n so ft h en e t w o r kw eo p t i m i z et h ep a t ho fm o b i l eb e a c o n t h e s e m a k ei n c r e a s eo fp o s i t i o n i n ga c c u r a c yo fp o s i t i o n i n g a l g o r i t h m a n dr e d u c e c o m m u n i c a t i o nc o s t s ，i m p r o v ee f f i c i e n c yo ft h ea l g o r i t h m f i n a l l y , w es i m u l a t em o b i l eb e a c o nb a s el o c a l i z a t i o na l g o r i t h mi no m n e t + + i i i 广东工业大学硕上学位论文 s i m u l a t i o ne n v i r o n m e n tb ym o d e l i n gm o b i l ei n t e l l i g e n tn o d e sa n do r d i n a r yn o d e si n t h en e t w o r k t h en e t w o r kc o m p u t e st h eu n k n o w nn o d e sl o c a t i o nt h r o u g ht h e p o s i t i o n i n gp r o c e s so fc o m m u n i c a t i o na n dd a t ap r o c e s s i n g t h es i m u l a t i o nr e s u l t s s h o wt h a tt h ea l g o r i t h mb a s eo nm o b i l eb e a c o nw i t ho p t i m a lp a t hn o to n l yi m p r o v e s t h ep o s i t i o n i n ga c c u r a c yb u ta l s or e d u c et h ec o m m u n i c a t i o no v e r h e a do fl o c a t i n g m ， t h e s ei m p r o v et h ee f f i c i e n c yo fw i r e l e s ss e n s o rn o d e sl o c a l i z a t i o n k e yw o r d s ：w s n ；m o b i l ea n c h o r ；o p t i m a lp a t h ；o m n e t h ；s m a r tn o d e i v 目录 目录 摘要一i a b s t r a c t i i i 目豸毛v c o n t e n t s v i i 第一章绪论1 1 1 本论文的研究背景及意义1 1 1 1 研究背景与意义1 1 1 2 课题来源j 3 1 2 国内外研究现状3 1 3 本论文的主要研究内容与结构5 第二章传感器网络常用节点定位算法相关研究7 2 1 无线传感器网络基于信标节点的定位算法7 2 1 1 相关工作7 2 1 2 基于信标定位算法的优点9 2 2 无线传感器网络常用的定位方式的实现1 0 2 2 1 极大似然估计法。1 0 2 2 2 三边测量定位法1 l 2 2 3 三角测量定位法1 2 2 - 3 常用的节点定位算法1 3 2 3 1 常用的r a n g e - b a s e 节点定位算法1 3 2 3 2 常用的r a n g e f r e e 节点定位算法1 6 2 4 本章小结18 第三章基于移动信标的节点定位算法1 9 3 1 无线传感器网络基于移动信标改进的d v - h o p 定位算法1 9 3 1 1 d v - h o p 定位算法2 0 3 1 2 移动信标节点定位算法2 3 v 广东t 业大学硕上学位论文 3 1 3 仿真分析2 6 3 2 基于移动信标动态选择改进d v - h o p 定位算法2 8 3 2 1d v - h o p 定位算法平均跳距离计算误差来源分析2 9 3 2 2 基于移动信标动态选择的改进型d v - h o p 定位算法过程3 l 3 2 3 仿真分析。3 4 3 3 本章小结3 5 第四章无线传感器网络移动信标的路径优化3 6 4 1 无线传感器网络移动信标的移动模型分析3 6 4 1 1 随机移动r w p ( r a n d o mw a yp o i n t ) 模型3 6 4 1 2 高斯马尔可夫移动g a u s s m a r k o v 模型3 7 4 1 3 螺线移动模型3 8 4 2 面向无线传感器网络节点定位的移动信标的路径优化3 8 4 2 1 基于图论的信标移动路径规划方法3 9 4 2 2 面向传感器网络的移动信标路径规划的仿真实现4 0 4 3 本章小结4 2 第五章基于移动信标优化路径定位算法的仿真实现4 3 5 1 仿真实验工具和实验方法简述4 3 5 1 1o m n e t + + 仿真实验平台介绍4 3 5 1 2 定位算法性能评价指标及分析方法4 4 5 2 基于移动信标的传感器网络定位算法的设计4 5 5 2 1 无线传感器网络仿真程序模型及程序设计4 6 5 2 2 定位过程仿真程序设计。5l 5 3 基于移动信标优化路径的定位算法性能分析5 2 5 4 本章小结5 5 结论与展望5 6 参考文献5 7 攻读学位期间发表的学术论文6 0 攻读学位期间参加的科研项目6 1 独创性声明6 2 蜀c 射6 3 v i c o n t e n t s c o n t e n t s a b s t r a c t ( c h i n e s e ) i a b s t r a c t ( e n g l i s h ) i i i c o n t e n t s ( c h i n e s e ) v c o n t e n t s ( e n g l i s h ) v i i c h a p t e r1i n t r o d u c t i o n 1 1 1r e s e a r c hb a c k g r o u n da n dm e a n i n go ft l l i ss u b j e c t 1 1 1 1r e s e a r c hb a c k g r o u n da n dm e a n i n g 1 1 1 2s o u r c eo f t l l i ss u b j e c t 3 1 2d o m e s t i ca n df o r e i g nr e s e a r c hs t a t u s 3 1 3m a i nc o n t e n ta n ds t r u c t u r eo f t h j ss u b j e c t 5 c h a p t e r 2c o m m o nn o d e sl o c a l i z a t i o nf o rs e n s o rn e t w o r k 7 2 1l o c a l i z a t i o na l g o r i t h mb a s eo nb e a c o n 7 2 1 1r e a l a t i v ew o r k 7 2 1 2 1 1 1 ea d v a n t a g eo fl o c a l i z a t i o na l g o r i t h mb a s eo nb e a c o n 一9 2 2i m p l e m e n to f c o m m o nl o c a l i z a t i o nw a y s 1 0 2 2 1m a x i m u ml i k e l i h o o de s t i m a t i o n 10 2 2 2t r i l a t e r a t i o nm e t h o dl o c a l i z a t i o n 。l1 2 2 3t r i a n g u l a t i o nm e t h o dl o c a l i z a t i o n 1 2 2 3c o m m o nn o d e sl o c a l i z a t i o na l g o r i t h m 13 2 3 1c o m m o nr a n g e - b a s en o d e sl o c a l i z a t i o na l g o r i t h m 。1 3 2 3 2c o m m o nr a n g e f r e en o d e sl o c a l i z a t i o na l g o r i t h m 16 2 4s u m m a r yo ft h i sc h a p t e r 18 c h a p t e r3l o c a l i z a t i o na l g o r i t h mb a s e do nm o b i l eb e a c o n 1 9 3 1i m p r o v i n gd v - h o pa l g o r i t h mb a s eo nm o b i l eb e a c o n 1 9 3 1 1d v - h o pl o c a l i z a t i o na l g o r i t h m 2 0 3 1 2n o d e sl o c a l i z a t i o n a l g o r i t h mb a s eo nm o b i l eb e a c o n 2 3 3 1 3s i m u l a t i o nr e s u l t 2 6 3 2i m p r o v i n gd v - h o pa l g o r i t h mb a s eo nm o b i l eb e a c o nd y n a m i cs e l e c t i o n 2 8 3 2 1a n a l y s i st h ee r r o rr e s o u r c eo f d v - h o pa v e r a g e rh o pd i s t a n c e 2 9 3 2 2t h ep r o c e s so f t h ei m p r o v i n gl o c a l i z a t i o na l g o r i t h m 31 3 2 3s i m u l a t i o nr e s u i t ：；z i ：；3s u m m a r yo f t h i sc h a p t e r 3 5 v i i 广东丁业大学硕上学位论文 c h a p t e r4m o b i l eb e a c o nm o v i n gp a t ho p t i m i z a t i o n 3 6 4 1a n a l y s i st h em o v i n gm o d e lo fm o b i l eb e a c o n 3 6 4 1 1r w p ( r a n d o mw a yp o i n t ) m o v i n gm o d e l 3 6 4 1 2g a u s s m a r k o vm o v i n gm o d e l 3 7 4 1 3s p i r em o v i n gm o d e l 3 8 4 2m o b i l eb e a c o nm o v i n gp a t ho p t i m i z a t i o nf o rw s n s 3 8 4 2 1m o b i l eb e a c o np a t hp l a n n i n gb a s eo ng r a p ht h e o r y 。3 9 4 2 2s i m u l a t i o no f t h em o b i l eb e a c o np a t hp l a n n i n g 4 0 4 3s u m m a r yo f t l l i sc h a p t e r 4 2 c h a p t e r5s i m u l a t i o no fl o c a l z a i t i o na l g o r i t h mb a s eo nm o b i l eb e a c o n 4 3 1 ；1i n t r o d u c t i o no f s i m u l a t i o nt o o l sa n d e n v i r o n m e n t 4 3 5 1 1i n t r o d u c t i o no f o m n e t + + 4 3 5 1 2l o c a l i z a t i o n a l g o r i t h mp e r f o r m a n c ee v a l u a t i o na n d a n a l y s i s 4 4 1 ；2l o c a l i z a t i o na l g o r i t h md e s i g nb a s eo nm o b i l eb e a c o n 4 5 5 2 1p r o g r a m m i n ga n dm o d e l i n gl o c a l i z a t i o na l g o r i t h m 4 6 5 2 2p r o g r a m m i n gt h ep r o c e s so f t h el o c a l i z a t i o na l g o r i t h m 51 5 3p e r f o r m a n c ee v a l u a t i o na n da n a l y s i so ft h el o c a l i z a t i o na l g r i t h mb a s eo n o p t i m i z ep a t h 5 2 5 4s u m m a r yo f t l l i sc h a p t e r 5 5 i ：o n c l u s i o na n dp r o s p e c t 5 6 r e f e r e n c e s 5 7 p u b l i s h e d p a p e r s 6 0 p a r t i c i p a n tp r o j e c t s 6 1 o r i g i n a lc r e a t i v es t a t e m e n t 6 2 a c k n o w l e d g e m e n t s 6 3 v i i i 第一章绪论 第一章绪论 1 1 本论文的研究背景及意义 1 1 1 研究背景与意义 无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等 技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式 自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息 获取和处理模式【1 1 。 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 是由部署在监测区内大量 的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络 系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传 送给观察者【2 j 。 传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络 应用中，通常将节点撤播在很广的区域里，网络中大部分的节点的位置是未知的， 事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信 息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传 感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据 是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到 的事件及信息发生的具体位置【3 】。节点必须明确自身位置才能详细说明“在什 么位置或区域发生了特定事件 ，实现对外部目标的定位和追踪。此外，在设计 路由协议时利用节点位置信息还可以提高路由效率，为网络提供命名空间，向网 络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置1 4 j 。 因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。 传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用 节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自 主确定位置被认为是其基本能力和系统的基本服务之一。对于w s n 来说，人工 广东工业大学硕士学位论文 部署或为所有网络节点配置g p s 装置都会受到成本、功耗、拓展性等问题的限 制，因此，寻求w s n 自身定位机制成为许多研究机构和学者共同探讨的问题【4 】。 无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机 制分为：基于测距的( r a n g e - b a s e d ) 定位和距离无关的( r a n g e 舶e ) 定位方法【5 1 。前 者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标 节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。r a n g e b a s e d 算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有 t i m eo fa r r i v a l ( t o a ) t 6 1 ，t i m ed i f f e r e n c eo fa r r i v a l ( t d o a ) t 7 1 ，r a d i os i g n a l s t r e n g t h ( r s s i ) 8 】和a n g l eo f a r r i v a l ( a o a ) 9 】等。 r a n g e b a s e d 算法能够实现精确定位，但由于需要在节点中加入g p s 或其它 附加的测距的硬件设备，在实际应用中所需的成本较高。而r a n g e f r e e 定位算法 由于降低了对节点硬件的要求，引起了更多的关注，典型算法有d v - h o p 1 0 】算法， 基于r s s i 的d v - h o p 1 1 】算法，基于连通性的定位算法【1 2 】等。 目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信 标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法， 都需要移动节点至少获得3 个或者3 个以上信标节点提供的坐标和距离1 1 3 。另 一种思想则是使信标或者信标运动起来，通过带有g p s 的已知位置的移动信标 按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节 点获取这些信号来进行定位计算。 动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所 涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法【14 1 ，包括 待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的 成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时 性要求较高，通常的改进方法是加入对节点运动的预测估计【l5 1 ，或是使定位算 法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。 虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精 度，减少定位代价。在b e r g a m o 等的研究中，网络中有2 个固定的信标向全网 传送坐标信息，其余处于运动状态的节点根据接收到的信号强度进行自身定位 b 6 o 国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法 2 第章绪论 【1 7 1 。但这些算法普遍存在以下局限【1 8 】：依赖特殊硬件的支持；需要特殊 的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文 献【1 9 】通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度 分布不均匀的不足。文献【2 0 】提到利用移动参考节点和r s s i ( 接收信号强度指示) 方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件 往往都是变化的，使得r s s i 技术在实际应用中仍然存在困难。尤其是节点对能 耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。 免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络 连通情况或者g p s 定位等思想提出的一种分布式定位方法，无需测距，这无疑 降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差， 当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差， 精度也相应的降低【2 1 1 。因此如何提高这种免测距定位算法的精度也成为了一个 研究的热点方向。 1 1 2 课题来源 本课题来源于国家自然科学基金资助项目( 编号：6 0 6 7 3 1 3 2 ) ；广东省自然 科学基金重点项目( 编号：0 7 1 1 7 4 2 1 ) 。 1 2 国内外研究现状 基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖 于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节 点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的 节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效 率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学者进行了许 多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定 位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规 划。为此，国内外有许多学者把移动信标与经典的质心定位算法、a p i t 定位算 法及d v - h o p 定位算法等相结合来改进这些定位算法。而质心定位算法及 广东工业人学硕l 学位论文 d v - h o p 定位算法因为无需测距有着更多的优势也得到更多的研究。 无需测距( r a n g e f r e e ) 的定位算法不需要直接测量距离信息，而是根据网络 的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等信息 估计每一跳的大致距离，然后估出节点在网络中的位置【2 2 1 。典型的无需测距的 定位算法有d v o h o p 定位算法，a p i t 定位算法、质心定位算法、a m o r p h o u s 定 位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。 通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是 最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的 飞行器上，并且该节点装有g p s 或其他定位装置，这样就构造了移动信标【2 3 1 。 它可以在移动的过程中实时获得其当前的位置信息。 通过移动信标来定位的主要思想是：移动信标在“感兴趣的区域内( r e g i o n o f i n t e r e s t ，简称r o i ) 2 4 1 移动的过程中，不断的广播包含其当前位置信息的分 组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者 三个以上的与其距离为r 的位置信息时，就可以利用三边测量法或极大似然估 计法【1 。7 】计算该未知节点的位置。 国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶 段，相关的文献并不多，提出的算法也不够成熟，文献 2 5 】和 2 6 】提出的定位 方法只需要一个可以移动的信标，其中文献 2 5 】利用t o a 测距技术和质心法来 计算待定位节点位置，文献 2 6 】不需要复杂的测距技术，而是通过信标的不断 运动并利用几何限制关系来计算待定位节点位置。 文献 2 7 】则在d v o h o p 的基础上引入移动的信标形成一种新的 m a d v - h o p 算法，实现在不提高硬件成本的情况下，又能达到同样定位效果的 构想。其定位的主要思想是：当移动信标在定位区域内移动时，移动到若干个新 位置，立即在该位置补充一个普通节点。根据信标的即时位置信息，新位置的普 通节点知道自身的位置。它们就等同于信标。另外，增加普通节点的同时，也提 高了随机网络的连通度。引入移动信标的优势是即使只有一个信标也可以实现对 未知节点的定位。 本论文针对基于信标的定位算法需要较高的信标节点密度导致定位成本提 高的情况，引入移动信标在网络中移动并广播自己的位置分组信息在网络中构成 虚拟信标的方法来定位未知节点，在d v - h o p 定位算法的基础上将移动信标构成 4 第一章绪论 的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化 的路径来提高定位效率。 对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研 究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广 播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究 信标的移动路径规划，使网络中的节点以最小的代价获得足够多用于自身定位的 信息成为一个重要的研究内容。 目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨 迹可以尽量覆盖网络区域。这样的算法显然不能最大限度的节约节点的能耗，对 于严格要求能源的传感器网络节点来说，必然需要更为优化及适用于当前网络的 路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通 信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静 态的路径规划与网络的连通状况无关，根据需要定位的r o i 区域，规划以尽可 能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可 夫移动模型，螺线移动模型和s c a n 移动模型。而国外有根据网络的联通状况 来进行路径规划的动态算法，文献【2 8 】提出几条最优路径的选择原则，本文主 要进行动态路径优化研究。 1 3 本论文的主要研究内容与结构 针对无线传感器网络基于信标节点的无需测距定位算法精度低，定位效率低 的情况，本文提出基于移动信标优化路径的无线传感器网络节点定位算法。研究 的内容主要如下： 1 、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于 信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。 2 、提出基于移动信标改进的d v - h o p 定位算法，该算法在d v - h o p 定位算 法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播 自己的位置信息，形成多个虚拟信标，未知节点采用加权处理的方法计算平均跳 距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实 现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计算精度的 广东t 业大学硕士学位论文 移动信标节点进行定位计算。仿真证明，相对于d v - h o p 算法，基于移动信标改 进的d v - h o p 定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度 和效率。 3 、结合基于移动信标改进的d v - h o p 定位算法，提出