（计算机应用技术专业论文）无线传感器网络dvhop定位算法的改进与仿真.pdf

1 进行研究 其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：。l 寿囝0 日期锄f 年易月j f 臼 重庆交通大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权重庆交通大学可以将本学位论文的全部内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中 国科学技术信息研究所将本人学位论文收录到中国学位论文全文数据库，并 进行信息服务( 包括但不限于汇编、复制、发行、信息网络传播等) ，同时本人 保留在其他媒体发表论文的权利。 学位论文作者签名：象t 1 春妨0 日期：加1 年 7 月j6 日 指导教师签名：许整左j 日期：年占月“日 本人同意将本学位论文提交至中国学术期刊( 光盘版) 电子杂志社c n k i 系列数据库中全文发布，并按中国优秀博硕士学位论文全文数据库出版章程 规定享受相关权益。 学位论文作者签名： ；1 春阮 指导教师签名： 许毯d i 摘要 lq l l l l li i i i l lli i i i l l l1 1iil 19 0 2 0 3 4 传感器节点的自定位技术作为无线传感器网络重要支撑技术之一具有重大 的研究价值。在许多实际应用中感知数据只有结合位置信息才具有意义，而使用 g p s 收发器，成本和能耗较高不适用于无线传感器网络，所以必需研究适合无线 传感器网络的自定位算法。此外，准确的定位信息对网络的许多实际应用具有重 要的意义，比如在目标跟踪中准确的定位信息可以使目标跟踪更为准确。 本论文的研究重点是目前应用最为广泛的定位算法之一d v h o p 定位算 法，从原始d v h o p 算法出发，分析了原始算法的各种不足，归纳了现有的该算 法的各种改进。通过对原始d v - h o p 算法的优缺点的分析提出了一种基于d v - h o p 算法的低成本、低误差、可扩展的改进算法，通过使用n s 2 仿真实验验证算法的 有效性，并分析了算法的使用价值。 算法的改进主要是以下三方面：提出一种基于三角形内点测试法的锚节点 选择策略。从原始d v - h o p 算法入手，从锚节点选择策略方面分析了原算法误差 产生的原因。a p t 是一种三角形内点测试法，由于a p i t 算法只能用于单跳的情 况，且要求较高的节点密度保证定位精度，无法用于多跳算法，在本文中提出了 一种不受跳数和节点密度限制的基于锚节点的内点测试法，仿真结果显示基于锚 节点的内点测试法的准确率较a p i t 算法高约2 0 。提出了一种基于局部区域 的d v - h o p 定位算法。原始算法使用全局策略，在节点密度不均匀的网络中平均 跳长误差较大，使得定位精度过低，在本文中使用局部策略，通过确定定位内外 限的方法实现局部定位。局部定位的关键是一种锚节点选择策略，内外限的确定 都是基于该种策略。该策略指选取的锚节点集合中存在这样的三个锚节点，使得 待测点在这三个锚节点构成的三角形内部，并且使用参与定位的节点来计算局部 跳长。外限的确定是将锚节点视为待测节点来估测整个网络局部定位的范围。在 外限的范围内使用锚节点选择策略来确定参与定位的锚节点，从而确定该点定位 的局部范围即内限，使用该内限范围内所有锚节点进行平均跳长的估计与定位。 将覆盖度统计与锚节点布撒算法加入d v h o p 算法。通过对锚节点覆盖度的统 计来估测锚节点的分布，进而通过对锚节点分布不足的局部区域采用添加锚节点 的方法来满足覆盖度的要求，从而使锚节点分布更为合理，保证未知节点定位所 需的锚节点，进而保证定位的准确度。在实际操作中可以根据覆盖度统计结果对 锚节点进行分次播撒，使锚节点分布更为合理，提高锚节点的使用效率来达到使 用较少锚节点保证一定定位精度的目的。仿真结果表明改进算法在原算法的基础 上将定位精度提高了5 0 ，并且改进算法比原算法具有良好的适应性和可扩展性。 厂一 部定位算法；三角形内点测 r a b s t r a c t s e l f - l o c a l i z a t i o nt e c h n o l o g yf o rs e n s o rn o d e sa so n eo ft h em o s ti m p o r t a n t s u p p o r t i n gt e c h n o l o g i e s i so fi m p o r t a n tr e s e a r c hv a l u ei nw s n s e n s o rd a t ah a s m e a n i n go n l yw h e n i tc o m b i n e sw i t hl o c a t i o ni n f o r m a t i o ni nm a n ya p p l i c a t i o n s g p s p o s i t i o n i n g i sd i s a g r e ew i t hw i r e l e s ss e n s o rn e t w o r k ( w s n ) f o ri t sh i g h e n e r g y c o n s u m p t i o na n dh i g h - c o s t s os e l f - l o c a l i z a t i o na l g o r i t h m ss u i t a b l ef o rw s n a r e n e e d e d b e s i d et h e s e ，t h ea c c u r a t el o c a t i o ni n f o r m a t i o np l a y sa ni m p o r t a n tr o l ei n m a n ya p p l i c a t i o n s f o re x a m p l e ，t h ea c c u r a t el o c a t i o ni n f o r m a t i o nc a nm a k et a r g e t t r a c k i n gm o r ea c c u r a t e t h i sp a p e rf o c u s e so nt h er e s e a r c ho fd v o h o pw h i c hi st h em o s tw i d e l yu s e da t p r e s e n t f r o mt h eo r i g i n a ld v o h o pa l g o r i t h m ，d i s a d v a n t a g e so ft h eo r i g i n a la l g o r i t h m w e r ea n a l y z e d ，a n dt h ee x i s t i n gi m p r o v e da l g o r i t h m sw e r es u m m e du p a ni m p r o v e d a l g o r i t h mi sp r o p o s e db ya n a l y z i n gt h eo r i g i n a ld v o h o pa l g o r i t h m sa d v a n t a g e sa n d d i s a d v a n t a g e s ，w h i c hi s l o wc o s t ，l o we r r o r , e x t e n s i b l e t h ee f f i c i e n c yo ft h e a l g o r i t h mi sv e r i f i e db ys i m u l a t i o n si nn s 2 ，a n dt h eu s ev a l u eo ft h ea l g o r i t h mi s a n a l y z e d t h ei m p r o v e da l g o r i t h mi sm a i n l yt h ef o l l o w i n gt h r e ea s p e c t s ：t h ei n t e r i o r p o i n t t e s ti sp r o p o s e db a s e do nt h ea n c h o rn o d e b e c a u s ea p i t a l g o r i t h mc a no n l yb e u s e df o rt h es i t u a t i o no fs i n g l ej u m pa n dh i g h e rn o d ed e n s i t yi sn e e d e d s oi tc a n n o t b eu s e df o rm u l t i p l eh o p sa l g o r i t h m a ni n n e rp o i n tt e s ti sp u tf o r w a r dw h i c hd o e sn o t s u f f e rh o pa n dn o d ed e n s i t yr e s t r i c t i o no fa n c h o rn o d e t h es i m u l a t i o nr e s u l t si n d i c a t e t h a tt h ei n t e r i o rp o i n tt e s t i n gb a s e do na n c h o rn o d eh a sh i g h e ra c c u r a c yt h a na p i t a l g o r i t h mw h i c hi sa b o u t2 0 a ni m p r o v e dd v - h o pa l g o r i t h mb a s e do nl o c a l a r e ai sp r o p o s e d t h eo r i g i n a ld v - h o pu s e sg l o b a ls t r a t e g yw h i c hm a k e sal a r g e r h o p - d i s t a n c ee s t i m a t i o ne r r o ri nr a n d o mw s n s ot h eo r i g i n a ld v - h o ph a sal o w e r l o c a t i o np r e c i s i o n t h r o u g ht h em e t h o do fd e t e r m i n i n gi n t e r n a la n de x t e r n a ll i m i t l o c a lp o s i t i o n i n gi sr e a l i z e d t h ek e yo fl o c a lp o s i t i o n i n gi st h ea n c h o rn o d ec h o o s i n g s t r a t e g y , a n dt h ed e t e r m i n a t i o no fi n t e r n a la n de x t e r n a lr e s t r i c t i o ni sb a s e do nt h e s t r a t e g y t h es t r a t e g yi st h a tt h e r ea r et h r e ea n c h o rn o d e si ns e l e c t e da n c h o rn o d e s w h i c hc a nm a k et h eu n k n o w nn o d ei nt h et r i a n g l e sc o n s t r u c t e db yt h e ma n d u s i n gt h e n o d et oc a l c u l a t el o c a lh o p - d i s t a n c e o u t e rl i m i ti sd e t e r m i n e db yc o n s i d e r i n ga n c h o r n o d ea su n k n o w nn o d et oa s s e s st h el o c a lp o s i t i o n i n gs c o p eo ft h ee n t i r en e t w o r k t h e r a n c h o rn o d e st a k i n gp a r ti np o s i t i o n i n gi no u t e rl i m i tr a n g ei sd e t e r m i n e db yu s i n g a n c h o rn o d e c h o o s i n gs t r a t e g y , t h e nt h e e x t e r n a lr e s t r i c t i o ni s d e t e r m i n e d c o v e r a g es t a t i s t i ca n db a c o nn o d e ss e e d i n ga l g o r i t h ma lea d d e di nt h ei m p r o v e d d v o h o p t h ed i s t r i b u t i o no fa n c h o rn o d e si sa s s e s s e dt h r o u g ht h es t a t i s t i c so fa n c h o r n o d ec o v e r a g e ，t h e na d d i n ga n c h o rn o d e st ot h e s ea r e a sw h i c hi sl a c ko fa n c h o rn o d e t os a t i s f yt h ed e m a n d so fc o v e r a g et om a k em o r er e a s o n a b l ed i s t r i b u t i o no fa n c h o r n o d e s ，a n de n s u r ee n o u g ha n c h o rn o d e sl o c a l i z a t i o nn e e d e dt h e ne n s u r et h e p o s i t i o n i n ga c c u r a c y i np r a c t i c e ，a c c o r d i n gt ot h ec o v e r a g eo fs t a t i s t i c a lr e s u l t s a n c h o rn o d e sc a nb es e e d e db ys e v e r a lt i m e sw h i c hw i l lm a k em o r er e a s o n a b l e d i s t r i b u t i o no fa n c h o rn o d ei m p r o v i n gt h eu t i l i z a t i o ne f f i c i e n c yo fa n c h o rn o d ea n d a c h i e v et h ep u r p o s et h a tu s i n gal e s sa n c h o rn o d eg e tt h el o c a l i z a t i o n a c c u r a c y r e q u i r e d s i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mo nt h eb a s i so ft h e o r i 酉n a la l g o r i t h m l o c a l i z a t i o n a c c u r a c y i n c r e a s e db y5 0 a n dt h e i m p r o v e d a l g o r i t h mh a sf a v o r a b l ea d a p t a b i l i t ya n de x p a n s i b i l i t y k e yw o r d s ：l o c a t i o n a l g o r i t h mi n 。w s n ；g r i ds c a n ；l o c a ll o c a t i o n ； p o i n t - i n _ t r i a n g l e t e s t ；d v - h o p f 1 1 1 5 6 6 第二章无线传感器网络8 2 1 无线传感器网络特点及其性能评价8 2 2 无线传感器网络的关键技术9 2 3 无线传感器网络的仿真技术1 5 2 4 无线传感器网络的定位算法1 6 2 4 1 主动定位与被动定位1 6 2 4 2 计算节点位置的基本方法1 7 2 4 3 主要定位算法2 1 2 5 本章小结2 2 第三章d v h o p 算法及其分析2 3 3 1d v - h o p 算法2 3 3 2 算法分析2 4 3 3 现有的d v h o p 改进算法2 5 3 4 本章小结3 1 第四章改进的d v - h o p 算法3 2 4 1 基于锚节点的内点测试法3 2 4 1 1a p i t 测试3 3 4 1 2 基于锚节点的内点测试法3 5 4 2 基于局部区域的d v - h o p 定位3 7 4 3 基于覆盖度的锚节点布撒算法4 0 4 3 1 基于模板的网格扫描算法4 0 4 3 2 覆盖度补充算法4 4 4 4 基于局部定位的d v h o p 中相对定位误差数学模型4 6 4 4 1 相对定位误差与n 的关系4 6 厂 4 4 2 相对定位误差与k 的关系4 9 4 4 3 相对定位误差与n ，k 的关系5 2 4 5 本章小结5 3 第五章仿真结果及分析5 4 5 1 基于锚节点的内点测试法仿真5 4 5 2 局部区域d v h o p 定位算法仿真分析5 6 5 3 基于覆盖度统计的锚节点播撒算法5 8 5 4 改进算法的综合仿真5 9 5 4 1 改进算法描述5 9 5 4 2 仿真结果与分析6 3 5 5 改进算法的应用分析6 8 5 6 本章小结6 9 第六章总结与展望7 0 6 1 总结7 0 6 2 展望：7 0 致谢7 2 参考文献7 3 攻读硕士学位期间发表的论文7 6 厂 域内部或附 过自组织构 布到监测区 域内，所有节点分布式运行，能够向临节点发送和接收数据，具有发现和维护其 他节点路由的功能。节点以自组织和自管理的形式构成网络，通过多跳中继的方 式将监测到的数据传送到汇聚节点，最后通过i n t e m e t 或其他网络通讯方式将监测 信息传送到管理节点。同样可以通过管理节点来进行命令的发布，指示传感器要 收集的信息。无线传感器网络将信息世界与客观世界融合在一起，改变了人与自 然的交互方式。人类通过传感器网络感知客观世界，随着i n t e m e t 的不断发展和壮 大，无线传感器网络也将为人类提供最直接、有效、真实可靠的信息。 倦雅 图1 1 无线传感器网络基本结构 f i g1 1t h eb a s i cs t r u c t u r eo fw s n 无线传感器网络在军事、农业、环境监测、医疗卫生、工业、智能交通、建 筑物监测、空间探索等领域有着广阔的应用前景和巨大的应用价值。在军事上， 具有可快速部署、可自组织、隐蔽性强和高容错性特点的无线传感器网络非常适 合在军事上应用。利用无线传感器网络能够实现对敌军兵力和装备的监控、战场 的实时监视、目标的定位、战场评估、核攻击和生物化学攻击的监测和搜索等功 能。目前国际许多机构的课题都是以战场需求为背景展开的。例如，美军开展的 如c 4 k i s r 计划、s m a r ts e n s o rw e b 、灵巧传感器网络通信、无人值守地面传感器 群、传感器组网系统、网状传感器系统c e c ，等等。在军事领域应用方面，该项 技术的远景目标是：利用飞机或火炮等发射装置，将大量廉价传感器节点按照一 定的密度布放在待测区域内，对周边的各种参数，如温度、湿度、声音、磁场、 红外线等各种信息进行采集，然后由传感器自身构建的网络，通过网关、互联网、 2 第一章绪论 卫星等信道，传回信息中心。该技术可用于敌我军情监控。在友军人员、装备及 军火上加装传感器节点以供识别，随时掌控自己情况。通过在敌方阵地部署各种 传感器，做到知己知彼，先发制人。另外，该项技术可用于智慧型武器的引导器， 与雷达、卫星等相互配合，利用自身接近环境的特点，可避免盲区，使武器的使 用效果大幅度提升。在农业方面，无线传感器网络有着卓越的技术优势。它可用 于监视农作物灌溉情况、土壤空气变更、牲畜和家禽的环境状况以及大面积的地 表检测。如图1 2 所示，一个典型的系统通常由环境监测节点、基站、通信系统、 互联网以及监控软硬件系统构成。如图所示，根据需要，人们可以在待测区域内 安放不同功能的传感器并组成网络，长期大面积地监测微小的气候变化，包括温 度、湿度、风力、大气、降雨量，收集有关土地的湿度、氮浓缩量和土壤p h 值 等，从而进行科学预测，帮助农民抗灾、减灾，科学种植，获得较高的农作物产 量。在“九五 计划中，“工厂高效农业工程已经把智能传感器和传感器网络化 的研制列为国家重点项目。在医疗监测方面，无线传感器网络在检测人体生理数 据、老年人健康状况、医院药品管理以及远程医疗等方面可以发挥显著的作用。 在病人身上安置体温采集、呼吸、血压等测量传感器，医生可以远程了解病人的 情况。利用传感器网络长时间地收集人体的生理数据，这些数据在研制新药品的 过程中非常有用。如图1 3 ，1 4 所示，研究人员可以利用无线传感器网络来实现 远程医疗监视。在一个公寓内，1 7 个传感器节点分布在各个房间，包括卫生间。 每个传感器节点上包括了温度、湿度、光、红外传感器及声音传感器，部分节点 使用了超声节点。根据这些节点收集到信息，监控界面实时显示人员的活动情况。 根据多传感器的信息融合，可以相当精确地判断出被检测人j 下在进行的行为，例 如：做饭、睡觉、看电视、淋浴等等，从而可以对老年人健康状况，如老年痴呆 症等进行精确检测。因为系统不使用摄像机，比较容易得到病人及其家属的接受。 美国英特尔公司目前正在研制家庭护理的无线传感器网络系统。该系统是美国“应 对老龄化社会技术项目”的一个环节。根据演示，该系统在鞋、家具以及家用电 器等嵌入传感器，帮助老年人及患者、残障人士独立地进行家庭生活，并在必要 时由医务人员、社会工作者进行帮助。在工业领域，煤矿、石化、冶金行业对工 作人员安全、易燃、易爆、有毒物质的监测成本一直居高不下，无线传感器网络 把部分操作人员从高危环境中解脱出来的同时，提高险情的反应精度和速度。图 1 5 是成峰公司与陕西天和集团共同研发矿工井下区段定位系统，各个工作地点放 置一定数量的传感器节点，通过接收矿工随身携带的节点所发射的具有唯一识别 码的无线信号进行人员定位。同时各个传感器节点还可以进行温度、湿度、光、 声音、风速等参量的实时检测，并将结果传输至基站，进而传至管理中心。在环 保监测领域无线传感器网络可以广泛地应用于生念环境监测、生物种群研究、气 3 f 、。* 、 o ：$ ev 蚴 o t t ，珏 图1 2 农业生态环境检测实例结构图 网络，可以让大 安装了传感器网 理部门按照优先 通控制管理、空 f i 9 1 2t h es t r u c t u r eo fa g r o e c o l o g i c a le n v i r o n m e n td e t e c t i o n 客房 囝i 国口0 3 饭厅 i厨房 0 5囝眵囝7 囝9 客厅 固i o9 l l 囝彳 囝8 囝l2 囝l3 囝；国j ， 浴室l 钟7i 囝j 6 l客房 图1 3 公寓内无限传感器节点的分布图 f i 9 1 3t h ed i s t r i b u t i o nm a po fw i r e l e s ss e n s o rn o d e si n d o o r 4 第一章绪论 图1 4 浴室中的节点分布图 f i 9 1 4t h ed i s t r i b u t i o nd a po fb a t h r o o m 蓓硒嚣节点信嬲节点磅撼器节点 倍瑟器节点信黪器够点咒絮节点 。佩戴蕉奉节点的旷工 图1 5 煤矿安全环境监测无线传感器网络的基本结构 f i 9 1 5t h eb a s i cw s ns t r u c t u r eo fm o n it o r i n gm i n i n gs a f e t ys y s t e m 第一章绪论5 2 0 0 2 年1 0 月的美国福布斯杂志报道了加州大学洛杉矶分校的无线传感器 网络的研究项目，指出通过无线传感器网络，我们将实实在在地掌握这个物理世 界。w s n 技术是2 0 0 3 年美国技术评论杂志评出的十种将改变世界的新兴技 术之一，也是美国商业周刊评出的未来将掀起新的产业浪潮的四大高新技术 之一，它引起了军事部门、工业界和学术界越来越多的关注。2 0 0 4 年第7 期的i e e e s p e c t r u m 杂志发表专辑，论述w s n 的发展和潜在的广泛应用。2 0 0 4 年8 月，i e e e c o m p u t e r 杂志也出版了专辑，发表了一些关于无线传感器网络的论文。可以预计， w s n 的发展和广泛应用，将对人们的社会生活和产业变革带来极大的影响和产生 巨大的推动。 相对于人际间信息交流的互联网，物联网是物与物、人与物之间的信息互联 网络。物联网是利用r f i d ( r a d i of r e q u e n c yi d e n t i f i c a t i o n ) 、w s n 、无线数据通信等 技术，构造一个覆盖世界上万事万物的巨大信息网络。具体地说，就是把各种感 应器嵌入和装备到电网、铁路、桥梁、隧道、公路、建筑、供水系统、大坝、油 气管道等各种物体中，形成物与物、人与物相互连接的信息网络，然后将此物联 网与现有的互联网融合起来，让物体自己开口说话，再基于网络中强大的中心 计算机群，实现对人员、机器、设备和基础设施的实时的智慧管理和控制，改善 人与自然间的关系。物联网是继计算机、互联网与移动通信网之后的世界信息产 业第三次浪潮。物联网如何从远景走向现实应用并得到快速发展己成为广受各界 关注的话题，相应的作为物联网基础的w s n 的发展也成为热点，根据易观国际 ( a n a l y s y si n t e r n a t i o n a l ) 最近发布的国内首份物联网全景报告中国物联网白皮书之 一无线传感器网络的机遇与挑战中的数据显示【1 1 ，作为物联网现阶段发展核 心的无线传感器网络产业，其市场规模将在未来两年内增长1 5 倍，达到4 0 亿元。 无线传感器网络的发展，还将带动r f i d 等其他物联网产业的发展，为其提供更明 确的应用方向和更丰富的市场机会。 1 1 2 无线传感器网络定位的必要性 无线传感器网络节点进行自身定位是各种实际应用的重要前提条件之一。定 位信息常用来报告事件发生地点、进行目标跟踪、实时监视目标的行动路线、交 通监控和环境检测等。由于节点工作区域通常是人类不适合进入的或是战时敌对 区域，传感器节点甚至需要通过飞行器抛撒于工作区域，因此节点的位置都是随 机且未知的。即使在人类可以进入的区域，w s n 节点可能是移动的，因此如果 w s n 节点通过定位算法找到自己所在位置，将大大方便施工人员的工作。 实际应用中，无线传感器网络节点所采集到的数据必须结合其位置信息才有 具体意义i2 。像在前面1 1 1 节中提到的矿工井下区段定位系统，在发生事故时并 需要通过传感器了解矿工及其所在环境的情况，定位信息更为重要，因为只有了 6 第一章绪论 解矿工的位置信息才能够安排有效的营救方案。不但如此，在无线传感器网络中 较为精确的定位信息，还有其他若干重要的作用。第一，有助于基于地理位置路 由的设计、实现以及改进。例如典型的基于地理位置的路由算法g e m 3 l ( g r a p h e m b e d d i n g ) ，g p s r 4 l ( g r e e d yp e r i m e t e rs t a t e l e s sr o u t i n g ) 等。第二，精确的定位信 息在数据融合算法的设计、实现、改进过程中也具有重要的促进意义，精确的定 位信息可以进一步提高网络数据传输的可靠性。第三，精确的网络节点定位是目 标跟踪，实时监视目标路线，预测目标前进轨迹等上层应用有效性的前提保证。 此外，可以利用传感器节点传回的位置信息构建网络拓扑图并实时统计网络覆盖 情况，对节点密度低的区域及时采取必要的措施。 综上所述，网络自身节点的定位算法的研究具有重要的意义，目前定位技术 已经作为w s n 关键技术之一得到人们的广泛关注。 其中d v - h o p 算法是目前应 用最广泛的定位算法之一，针对d v - h o p 改进【5 j 【6 j 算法的研究，已成为重要的研 究热点。 1 2 论文的主要研究内容和创新点 本论文的主要工作是通过查阅大量中英文参考资料，归纳并总结了现有无线 传感器网络的各种定位算法，着重研究了适用于节点随机分布的分布式d v - h o p 定位算法。通过对原始d v - h o p 算法的优缺点的分析提出了一种基于d v - h o p 算法 的低成本、低误差、可扩展的与距离无关的改进算法。最后通过使用n s 2 仿真实 验给出了一个量化的比较，并分析了该算法的应用价值。本文的主要成果有： 分析了a p i t 算法的局限性，提出了一种基于锚节点的内点测试法，并通过 仿真比较分析了该算法较a p i t 判定法的有效性。 提出局部区域的d v - h o p 定位算法。通过局部定位两个范围的确定，实现局 部定位的思想。首先在锚节点集合中通过使用三角形内点测试法，确定定位外限， 然后在外限范围内再次通过三角性内点测试法确定参与定位的锚节点。 引入锚节点覆盖度，通过覆盖度来配置网络锚节点环境。通过对锚节点覆 盖度的统计来衡量锚节点密度，进而通过对锚节点分布不足的局部区域添加锚节 点或采用改变该区域内及附近锚节点通信半径的方法来满足覆盖度的要求，从而 达到使用较少锚节点就可以达到要求的定位精度的目的。该点改进使锚节点分布 更为合理，不但提高锚节点的使用效率，而且提高了定位精度。 1 3 论文结构安排 本文各章内容安排如下： 第一章绪论7 第一章，首先介绍了无线传感器网络的研究背景、概念、主要应用及其发展 前景。其次介绍网络节点定位的必要性及意义。 第二章，在讨论了无线传感器网络的特点及性能评价标准之后，分析了无线 传感器网络的关键技术及仿真技术。接着详细介绍了无线传感器网络的定位算法。 第三章，分析了无线传感器网络的一种分布式定位算法d v 二h o p ，总结了 该算法的不足，论述了现有的主要的改进算法。 第四章，根据第三章对原始d v - h o p 算法的分析提出三点改进。改进算法包括 以下三部分涉及覆盖度统计的网格扫描算法与覆盖度补充算法；基于锚节点的内 点测试法；局部定位思想。 第五章，首先对各部分改进算法进行了n s 2 仿真实验的验证，然后将所有改 进点综合在一起进行仿真。最后对仿真结果进行了统计分析，对改进算法的性能 进行了评估。 第六章，总结全文。对本文工作进行了总结，对现有无线传感器网络的定位 存在的问题和需要继续研究的方向做了叙述。 第一二章无线传感器网络 第二章无线传感器网络 第一草尢线1 专愁雷青网鞲 2 1 无线传感器网络特点及其性能评价 无线通信网络技术在过去的几十年间取得了飞速的发展。作为i n t e m e t 在无线 和移动范畴的扩展和延伸，无线自组网络由若干采用无线通信的节点动态地形成 一个多跳的移动性对等网络，从而不依赖于任何基础设施【7 】。无线传感器网络与无 线自组网由很多的相似之处，总的来说包括分布性、自组性、多跳路由等，但无 线传感器网络与无线自组网络( a d h o e ) 8 】有着明显不同的技术要求和应用目标，使 得无线传感器网络具有以下一些区别于无线自组网络的独有特征： 通信能力有限。由于无线信道自身的物理特性，通常使得它所能提供的网 络带宽相对有线信道小的多。而且节点能量的变化、周围自然环境的影响，使得 网络的无线通信性能也会经常变化，有时导致通信的时断时续。因此，在有限的 通信带宽下高质量的完成感知信息的处理与传输，是传感器网络面临的挑战之一。 传感器节点数量大、密度高、分布范围广。为获得尽可能精确、完整的信 息，无线传感器网络通常密集部署在检测区域中。这是因为它是通过大量冗余节 点的协同工作来提高系统的工作质量的。这个特点使得传感器网络的维护十分困 难，因此传感器网络的硬、软件必须具有很强的健壮性和容错性。 电源能量受限。节点的能量约束是阻碍传感器网络应用的最重要的因素之 一。传感器网络的能量问题除了受本身微型化设计的影响，还因为传感器网络节 点分布数量往往很大，甚至在某些情况下节点所在的区域无法更换电池。所以在 无线传感器网络中要最大化地延长网络的生命周期，降低能耗必然是要考虑的。 计算和存储能力有限。由于嵌入式处理器和存储器的容量和能力有限，使 得传感器的计算能力十分有限，所以设计定位系统与定位算法要考虑算法复杂度， 要求算法简单且计算量少。 网络拓扑变化大。w s n 要求网络在使用有限的硬件资源和能量的前提下 完成指定的功能，由于无线信道的不稳定，无线信道间的相互干扰、节点的移动 和失效以及地形等综合因素的影响，w s n 的拓扑结构随时都可能发生变化，而且 变化的趋势具有随机性。也就是说网络中的一条链路在前一秒钟存在，在第二秒 就很可能找不到。这就要求传感器节点能够随着环境的变化而适时的调整自身的 工作状态，所以传感器网络必须具有自组织性和可重构性。 应用相关，且感知数据流巨大。无线传感器网络通过感知客观世界的物理 量来获取外界的信息。由于不同应用关心不同的物理量，因而对网络系统的要求 第二章无线传感器网络 9 也不同，其硬件平台、软件系统和通信协议也必然会有很大的差异。传感器网络 中的每个传感器节点通常都产生较大的流式数据，并具有实时性。需要研究强有 力的分布式数据流管理、查询、分析和挖掘方法。 以数据为中心。在无线传感器网络中，人们通常只关心某个区域内某个观 测指标的数值，而不会去具体关心单个节点的观测数据【9 】。这就是无线传感器网络 以数据为中心的特点，它不同于传统网络的寻址过程，能够快速、有效地组织起 各个节点的信息并融合提取出有用信息直接传送给用户。用户使用传感器网络查 询事件时，直接将所关心的事件通告给网络，而不是通告给某个确定编号的节点。 网络在获得指定事件的信息后汇报给用户。 无线传感器网络主要性能评价【1 0 】有： 能源有效性：传感器网络的能源有效性是指该网络在有限的能源条件下能 够处理的请求数量。 生命周期：传感器网络的生命周期是指从网络启动到不能为观察者提供所 需信息为止所持续的时间。 时间延迟：传感器网络的延迟时间是指当观察者发出请求到其接收到应答 信息所持续的时间。 感知精度：传感器网络的感知精度是指观察者接收到的感知信息的精度。 可扩展性：传感器网络通常工作在恶劣的环境中，经常会有节点失效或者 有新节点加入等情况出现，这些使得无线传感器网络拓扑结构发生变化，因此要 求定位算法具有良好的可扩展性，能够适应网络拓扑结构的动态变化。 容错性：传感器网络中的节点随机部署通过自组织方式形成网络，网络中 节点定位、信息采集以及信息传送的准确性都受到网络生存环境的影响，所以网 络容错性也是一个重要指标。 无线传感器网络的6 个性能指标不仅是评价传感器网络的标准，也是传感器 网络设计的优化目标。为了达到这些目标，有大量的研究工作需要完成。在下面 提出的本文的改进算法将会围绕这几点来评价算法的性能。 2 2 无线传感器网络的关键技术 无线传感器网络作为信息领域的一个新的研究热点，涉及多学科交叉的研究 领域，有非常多的关键技术有待发现和研究，下面分析了网内信息处理、路由协 议、定位技术三项关键技术【1 1 】。 无线传感器网络网内信息处理 无线传感器网络不同于传统网络的特点给它带来了许多新的挑战。例如以数 l o 第二章无线传感器网络 据为中心，要求在路由的同时必须对所传递的数据内容进行处理，而不是像传统 网络那样仅仅转发数据。这要求构造一种以数据为中心的、最大限度节能的、协 作的网内信息处理模式。为此，研究者采取了一系列措施，如在传输过程中进行 数据融合，以计算量的增加来换取数据通信量的降低；节点发送数据前对数据进 行压缩，接收到数据后再进行解压；在节点间建立分布式的协商与合作机制，由 多个节点协作完成网内信息的处理等。 1 ) 数据融合 数据融合( d a t af u s i o no rd a t aa g g r e g a t i o n ) 技术是一项早在2 0 世纪7 0 年代出 现，并于8 0 年代得到发展的专门技术。数据融合的基本思想是：在从各个节点收 集数据的过程中，利用节点本地的计算和存储能力处理数据，去除冗余数据，尽 量减少数据传输量；同时将来自不同节点的多份数据结合起来，提取或综合出较 单个节点数据采集更为有效、准确的数据信息，最终达到精确感知目标信号，降 低能耗，延长网络生命周期的目的【1 2 】。 2 ) 数据压缩 数据融合方法仅对监测目标的统计结果感兴趣，而不关心中间数据记录的应 用场合是否有效。这对需要同时保留中间观测数据的应用就不适用，比如在生物 栖息地监测的应用中，通常需要从长期的历史记录数据中，根据丰富的中问观察 数据统计分析出生物的生活习性。一种可行的方案是，在传感器节点和汇聚节点 处分别采用压缩和解压缩处理。这样虽然加重了c p u 处理的负担，有一些存储空 间和运行时间方面的代价，但只要设计合理，与直接传输原始数据所消耗的巨大 能量相比，这些代价还是值得的。无线传感器网络中数据压缩采用分布式的方式， 实现低复杂度、高压缩效率。还可以将数据融合和数据压缩方法综合起来考虑， 从而满足更广泛的应用对象。 3 ) 协作信号信息处理 协作信号处理致力于节点间的协商和合作，通过选择合适的节点参与协作， 平衡节点个体和网络整体在协作过程中的信息收益和资源代价，节点网络信息处 理中的驱动机制、节点选择、处理地点、时机和算法等问题【1 3 1 。 路由协议 w s n 中节点一般采用电池供电，并且大部分情况下电池不能补充和更换，节 点能量受限。这样要延长网络寿命就必须降低节点工作时的能耗。相对数据采集、 数据计算两项功能而言，节点能量主要消耗在通信模块上。要减少节点能量消耗 必须减少节点的有效传输半径，而有效传输半径的减少降低了单节点的覆盖面积。 为了实现w s n 的大范围覆盖，必须使用多跳中继的方法来传输数据，这需要相应 的路由协议的支持。传统的a dh o c 网络路由协议设计一般将服务质量( q o s ) 高以 第二章无线传感器网络 及带宽有效利用放在第一位，其次才会考虑能量消耗问题。因此，无线传感器网 络所特有的高能量效率的路由协议无法采用传统网络的路由算法。因此，目前研 究人员致力于开发新的能效高的路由协议。 可以将现有路由协议大体上分为两类，平面路由协议和层次化路由协议，下 面就从这两方面介绍各种协议【1 4 1 。 1 ) 平面路由协议 a 泛洪协议 泛洪协议( f l o o d i n g ) 【1 5 1 是最早的路由协议，它的基本思想是：每个节点把接 收到的信息以广播的方式发送出去，如此下去最后将信息发送给目的节点。这种 协议最大的优点就是不需要知道网络拓扑和使用任何算法，实现简单，但协议容 易引起信息的“内爆”和“重叠”，造成资源的浪费。为解决这两个问题又相继 提出了g o s