（计算机科学与技术专业论文）基于遗传模拟退火算法的无线传感器网络定位算法的研究.pdf

独创性声明 丫llll1111118111iif7lln19fl；7llllf5liiii6flll i 丫18 7 9 7 5 6 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 签名：独西日期：h i l 。孓。l 三 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规 定，即学校有权保留并向国家有关部门或机构送交论文的复印件 和电子版，允许论文被查阅和借阅。本人授权武汉理工大学可以 将本学位论文的全部内容编入有关数据库进行检索，可以采用影 印、缩印或其他复制手段保存或汇编本学位论文。同时授权经武 汉理工大学认可的国家有关机构或论文数据库使用或收录本学 位论文，并向社会公众提供信息服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：乏磁码 导师( 签名) ：了孳7 云：c 乞 日期：压mx i j 因此，无线传 的通信能力， 对于无线传感 器网络的大多数应用而言，传感器节点的位置是非常重要的，因此定位技术是 无线传感器网络中的一个关键技术，研究无线传感器网络的节点定位也显得十 分有意义并将会得到更多的重视。 在已经提出的节点定位算法中，大致可以被分为基于测距的和基于非测距 的两种定位算法。作为一种典型的基于非测距的定位算法，d v - h o p 定位算法在 硬件成本以及能耗上都优于基于测距的定位算法j 但它的定位精度不高，主要 问题在于在d v - h o p 定位算法中是使用两个节点之间的跳段距离代替了它们实 际的距离，且d v - h o p 算法的平均每跳距离会直接影响到节点定位误差的大小， 因此为了提高该算法的定位误差的精度，本文将如何提高d v - h o p 定位算法的平 均跳段距离作为研究的重点内容。 针对上面提出的d v - h o p 定位算法存在的问题，本文查阅和研究了大量的相 关文献，在本文中也对该算法的理论基础知识作了介绍，同时也对已经存在的 对d v - h o p 定位算法的改进方案做了仔细的研究分析。本文针对d v - h o p 定位算 法中的平均每跳距离代替实际距离可能产生误差进而导致定位误差的问题，并 借鉴几种已有的相关改进算法，提出了一种新的对d v - h o p 算法的改进方案。此 算法的主要思想是将提出的遗传模拟退火算法应用于该算法的平均每跳距离的 求解中，使得在一定程度上能够降低平均每跳距离所带来的定位误差，最终能 提高定位算法的定位精度。 本文最后使用m a t l a b 仿真软件对提出的改进算法进行了仿真实验，仿真 实验结果表明，改进后的算法相比已存在的几种d v - h o p 的改进算法以及原算法 节点的定位精度都有一定的提高。 关键词：无线传感器网络，定位算法，d v - h o p ，平均每跳距离，遗传模拟退火 算法 武汉理工大学硕士学位论文 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 ， 1 san e wk i n do fn e t w o r k , c o m b i n e dal o to fn e w t e c h n o l o g i e s ，t h e r e f o r e , m o r ea n dm o r ep e o p l ep a ya t t e n t i o n st oi ta n di ti sw i d e l y a p p l i e dt ov a r i o u sf i e l d s d u et oi t sv e r ys t r o n gc o m m u n i c a t i o na b i l i t y g e n e r a l l y a p e a k i n g , s e n s o rn o d e s p o s i t i o n sa 1 ov e r yi m p o r t a n tf o rm a n ya p p l i c a t i o n so fw i r e l e s s s e n s o rn e t w o r k , s ol o c a t i o nt e c h n o l o g yh a v ei m p o r t a n tr o l ei nw i r e l e s ss e n s o rn e t w o r k a n di ti sv e r ys i g n i f i c a t i v ea n dm o r ei m p o r t a n c ew i l lb ea t t a c h e dt oi ti nt h er e s e a r c h o fw i r e l e s ss e n s o rn e t w o r k e x i s t i n gl o c a t i o na l g o r i t h m sc a ng e n e r a l l yb ed i v i d e di n t ot w oc a t e g o r i e s ：t h e r n n g e - b a s e dl o c a t i o na l g o r i t h m sa n dt h er a n g e - f l e el o c a t i o na l g o r i t h m s t h ed v - h o p a l g o r i t h r n a sar a m g e f r e ea l g o r i t h mi ss u p e r i o rt o t h er a n g e - b a s e da l g o r i t h mi n h a r d w a r ec o s ta n dp o w e rc o n s u m p t i o n , b u ti t sl o c a t i o na c c u r a c yi sl o w e r t h em a i n p r o b l e mi nd v - h o pa l g o r i t h mi st h a tt h er e a ld i s t a n c eb e t w e e nt h en o d e si sr e p l a c e d w i t ht h eh o p sa n dt h ea v e r a g eh o p si nd v - h o pa l g o r i t h mw i l la f f e c tt h ea c c u r a c yo f l o c a t i o na l g o r i t h md i r e c t l y , s ot h ek e yo ft h i sp a p e ri sh o wt oi m p r o v et h ea c c u r a c yo f t h ea v e r a g eh o p si nd v - h o pa l g o r i t h m t os o l v et h ea b o v ep r o b l e m ，t h i sp a p e ri n t r o d u c e ds o m et h e o r yk n o w l e d g ea b o u t l o c a t i o na l g o r i t h ma n dr e s e a r c h e dt h es o m ee x i s t i n gi m p r o v e dd v - h o pa l g o r i t h m s c a r e f u l l yo nt h eb a s i so fc o n s u l t i n gal a r g en u m b e ro fd o c u m e n t s t h i sp a p e rp r o p o s e d an e wi m p r o v e m e n td v - h o pa l g o r i t h ma c c o r d i n gt ot h ep r o b l e mo ft h ee r r o rc a u s e d b yt h er e a ld i s t a n c ei sr e p l a c e db yt h ea v e r a g eh o p si nd v - h o pa l g o r i t h ma n dt h e i d e a so fs o m ee x i s t i n gi m p r o v e m e n td v - h o pa l g o r i t h m s t h en e wa l g o r i t h mt h a ti s p r o p o s e db yt h i sp a p e ra c q u i r e dt h eo p t i m a ls o l u t i o no ft h ea v e r a g eh o p s 谢m t h e g e n e t i ca l g o r i t h mb a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h ms oa st or e d u c e dt h ee r r o r c a u s e db yt h ea v e r a g e h o p sa n di m p r o v e dt h ea c c u r a c yo f l o c a t i o na l g o r i t h mf i n a l l y t h i sp a p e rs i m u l a t e dt h ea l g o r i t h mt h a ti sp r o p o s e db yt h i sp a p e rw i mm a t l a b s o f t w a r ei nt h ee n d t h es i m u l a t i o nr e s u l t ss h o w e dt h a tt h ea l g o r i t h mt h a ti sp r o p o s e d b yt h i sp a p e rc a nl o c a l i z ea c c u r a t e l yf a s t e rt h el o c a t i o no ft h en o d e st h a ns o m e e x i s t i n gi m p r o v e m e n td v - h o pa l g o r i t h m so ro r i g i n a ld v - h o pa l g o r i t h m 武汉理工大学硕士学位论文 k e yw o r d s ：w s n ，l o c a l t i o na l g o r i t h m ，d v - h o p ，a v e r a g eh o p s ，t h eg e n e t i ca l g o r i t h m b a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h m i i i 1 1 ：! ：； ：； 1 3 2 无线传感器网络的特点5 1 3 3 无线传感器网络的应用领域7 1 3 4 无线传感器网络的关键技术9 1 4 本文的主要工作及章节安排1 1 第2 章 无线传感器网络定位技术的概述一1 3 2 1 无线传感器网络定位的基本概念1 3 2 2 无线传感器网络定位技术的基本术语1 4 2 3 无线传感器网络定位算法的分类1 5 2 4 基于非测距的典型的定位算法1 8 2 5 定位算法的性能评价指标2 0 2 6 本章小结2 2 第3 章遗传模拟退火算法的研究与分析2 3 3 1 遗传算法的研究与分析2 3 3 1 1 遗传算法的构成要素2 3 3 1 2 遗传算法的基本步骤。2 7 3 1 3 遗传算法的应用步骤2 7 3 1 4 遗传算法的特点。3 0 3 2 模拟退火算法的研究与分析3 0 3 2 1 模拟退火算法的构成要素3 0 3 2 2 模拟退火算法的基本步骤。31 3 3 遗传模拟退火算法的提出3 3 3 3 1 遗传算法的局限性3 3 3 3 2 模拟退火算法的局限性3 3 i v 武汉理工大学硕士学位论文 3 3 3 遗传模拟退火算法的研究。3 3 3 4 本章小结3 4 第4 章基于遗传模拟退火算法的无线传感器网络定位算法的设计3 6 4 1d v 二h o p 定位算法的详细阐述3 6 4 2 现有的d v - h 0 p 改进算法3 8 4 3 改进的d v 二h 0 p 定位算法的设计3 9 4 4 本章小结4 2 第5 章算法的仿真与分析4 3 5 1 m a t l a b 简介4 3 5 2 部署的网络环境4 3 5 3 性能评价指标4 6 5 4 仿真结果及其分析4 6 5 5 本章小结5 0 第6 章总结与展望5 2 6 1 论文总结5 2 6 2 展望5 2 至炙谢。5 4 参考文献5 5 攻读硕士期间发表的论文及参研情况5 8 v 的传感器技术、计算机技术以及通信技术等多个学科技术，是由大量的廉价的 无线传感器节点通过无线通信的方式形成的一个多跳、自组织的网络。网络中 的这些传感器节点是具有感知、数据处理和一定的计算和存储等能力的，并且 还能够协作地感知、采集和处理网络覆盖区域内的监测对象的信息，与此同时 节点之间还可以进行无线通信，实现协同监控的目的【。 无线传感器网络是有很广阔的市场及产业前景的，目前在军事、医疗、交 通、国防和环境监测等多个领域都有十分广泛的使用。在无线传感器网络的应 用中，被随机部署的无线传感器节点是无法事先知道其自身的位置信息的，对 大多数的应用而言，传感器节点采集到的数据必须结合它们在测量坐标系内的 位置信息才将可能会有一定的意义，即如果不知道传感器节点位置而采集到的 数据是不可能具有任何意义和利用价值的。传感器节点必须明确了自身位置才 能详细说明“在什么位置或区域发生了特定事件”【2 】，因此传感器节点的位置信 息在无线传感器网络的各种应用中是非常重要的，节点的定位问题已经成为了 无线传感器网络的一个研究热点，受到很多研究人员的关注。 传感器节点的定位可以通过以下几种途径来实现：第一，手工配置，也就 是借助于手工的方式输入节点在网络中的坐标位置信息，但由于传感器节点数 目的较多，比较耗时，因此该方法不可行。第二，使用g p s 接收器，即为每个 节点安置一个g p s 接收器，每个节点通过接收多个卫星的信号来确定各自的位 置。虽然g p s 具有定位精度高、实时性好等一系列优点，但它体积大、能耗高， 价格高且不能直接用于室内，导致该方法也是不可行的。由此，近年来研究人 员提出了许多种类的定位算法，原理是通过g p s 来确定出少量的节点的位置， 然后利用这些少量的已知节点的位置信息以及节点之间的距离信息再借助一定 的手段实现其他未知节点的定位【3 】。定位算法大体可被分为两类，分别是基于测 距的( r a n g e - b a s e d ) 和无需测距的( r a n g e - f r e e ) ，这些算法虽然都各有各的特点和适 用范围，但真正应用的还是比较少，因此需要有更多的人研究并提出更好的定 武汉理工大学硕士学位论文 位方法来实现传感器节点的定位。 综上所述，节点定位是无线传感器网络的一个重要的辅助功能之一，研究 节点定位方法对无线传感器网络的理论和实际应用有重大意义。 1 2国内外研究现状 无线传感器网络( w s n ) 是一种全新的研究技术，它的最初构想是出于国 防需求，并由美国军方提出来的。对无线传感器网络最初的研究是在美国国防 部高级研究计划署( d e f e n s ea d v a n c e dr e s e a r c hp r o j e a sa g e n c y ) 资助的一所卡内 基一梅隆大学内进行的，之后又在美国的一个“移动计算和网格“的国际会议上 被提出是下一世纪所面临的发展机遇。此外，它还被美国商业周刊以及麻省理 工学院( m i t ) 分别列为2 l 世纪最有影响的能改变世界的十大技术之一和全球未 来的三大高科技产业之一【4 】。近年来随着无线通信技术的发展以及应用需求的增 加，无线传感器网络的研究得到了越来越多人的关注，并在国内很多研究所和 高校展开。 定位技术作为无线传感器网络的一个重要基础技术也得到了越来越多的关 注，而作为其核心的定位算法更是国内外的研究重点【5 】，并取得了一定的研究成 果，尤其是近年来，已经提出了不少的有关定位问题的算法和思路，主要被划 分为基于测距的和无需测距的两种 6 1 。基于测距的定位算法主要包括t o a ( 至u 达 时间) 、a o a ( 至i j 达角度) 和r s s i ( 接收信号强度) 等四类算法，这类算法是通过测 量相邻节点之间的实际距离从而确定节点的位置，而无需测距的定位算法主要 包括d v - h o p 定位算法、近似三角形内点测试( a p n o 定位算法、质心定位算法、 和a m o r p h o u s ( 不定型) 定位算法，该类的定位算法是不需要测量节点之间的实际 距离的，而是使用节点之间的估计距离来确定节点的位置的【_ 丌。由于后者不仅不 需要硬件设备而且它的定位精度还能满足大多数的无线传感器网络的应用需 求，所以是比前者受关注的。但由于不同的算法只能用来解决各自相关领域的 问题，没有一种是绝对最优的【引。 总而言之，无线传感器网络的自身定位问题是一门刚刚兴起的研究课题， 虽然已经提出了许多大胆的想法并倾向于和相关领域的一些技术相结合【9 】，但很 多理论都难以真正实现，有待于我们去进一步探索和研究开发。 2 武汉理工大学硕士学位论文 1 3 无线传感器网络概述 在当今的信息时代，传感器技术作为采集信息最重要和最基本的技术，也 取得了非常大的发展。传感器获取信息的技术开始由过去的单一化向集成化、 微型化以及网络的方向发展。无线传感器网络是由大量的体积小、成本低并具 有通信和数据处理能力的节点所组成的，以获取和处理该网络覆盖区域内的目 标对象的数据和信息并发送给观察者为目的，如今，它可以在任何时间、多数 地点和多种环境的条件下获取到大量的更加详尽且可靠的信息，并将获取到的 信息发送给观察者【l o j 。 作为一门新兴的研究技术，无线传感器网络对人们未来的生活有着深远的 影响，是具有很大的科学意义和应用价值的，同时也是国内外的重点研究课题。 1 3 1无线传感器网络的体系结构 无线传感器网络通常是被部署于需要被监测的区域内的，它的典型的结构 主要包括传感器节点、汇聚节点以及管理节点。借助于人工布置、飞行器抛洒 等这样的方法把大量的传感器节点随机地分布在监测区域的内部或者附近，这 些节点之间又通过自组织的方式组成网络【1 1 1 。传感器节点作为整个无线传感器 网络的基本组成单元，通常是一个微型的嵌入式系统，由传感器节点获取的数 据有可能会被其它的多个节点进行处理，并沿着这些传感器节点进行逐跳地传 输，然后通过多跳中继的方式传送给了汇聚节点，最后将数据通过互联网或卫 星等的方式传送到用户所在的管理节点。通过管理节点用户又可以对无线传感 器网络进行管理和配置以及进行监测任务的发布和监测数据的采集等一系列的 操作。 3 图1 1 无线传感器网络结构示意图 图1 1 是一个典型的无线传感器网络的结构。其中传感器节点的体系结构如 图1 2 所示，它们是由四个模块组成的，分别是传感器模块、无线通信模块、处 理器模块以及电源管理模块【眩】。传感器节点的处理能力、通信能力以及存储能 力相对于汇聚节点来说都是比较弱的，并且它们都是通过携带的电池来提供能 量的，所以节点的能量是十分有限的。 图1 2 传感器节点的体系结构 汇聚节点的体系结构如图1 3 所示，相对于传感器节点来说，汇聚节点的处 理能力、通信能力和存储能力都是较强的。它们是由中央处理单元和存储单元 以及射频收发模块和通信模块组成的，汇聚节点可以是一个增强型的传感器节 点，与传感器节点不同的是，这个传感器节点具有足够的能量供给以及更多的 4 武汉理工大学硕士学位论文 内存和计算资源，同时汇聚节点也可以是一个特殊的节点设备，而该设备只是 带有无线通信接口的。汇聚节点通过连接互联网以及w s n 等外部的网络以及协 议转换能够实现两种协议栈管理节点和无线传感器网络互相进行通信，同时它 还能把采集到的数据信息转发到外部网络上并进行管理节点监测任务的发布的 操作。 图1 3 汇聚节点体系结构 1 3 2 无线传感器网络的特点 到目前为止，无线网络的种类有很多种，比较常见的包括无线局域网、无 线自组网、蓝牙网络、移动通信网、蜂窝移动电话网以及a d h o c 网络等。无线 传感器网络与其中的a dh o e 网络是最相似的【”】，它们都是采用分布式的无线通 信方式，能够适应动态的拓扑变化，且没有固定的基础设施的多跳路由，最重 要的是每个节点都是具有自组织能力的，但与传统的a d - h o c 网络相比，无线传 感器网络作为一种新兴的 智能 网络在许多方面都有其独特的特点，主要表 现在以下几个方面： ( 1 ) 更大的规模 在无线传感器网络的很多实际应用中，为了获得准确的信息，需要在一个 监测区域内部署大量的传感器节点来进行监测或跟踪的任务，这些传感器节点 的数量有可能是上万个，甚至是几百万个。无线传感器更大的规模性主要表现 在两个方面【1 4 】，第一个方面是需要被部署的无线传感器节点是在一个很大的区 域范围的；第二个方面是在一个面积不是很大的空间内，部署了大量的无线传 感器网络的节点且分布很密集。这种部署方式不仅能够分布式地处理大量的信 息，还能够提高监测精度并能够通过不同的空间视角来获得信息，具有了更高 的可靠性。 5 武汉理工大学硕士学位论文 ( 2 ) 自组织性 无线传感器网络中的节点通常是通过飞行器抛洒等这样的途径被部署在人 不可能到达或者危险的被监测区域内的，这些节点的部署是不需要为其准备任 何基础设施的，换句话说在需要部署的节点所在的区域内是不存在基础设施的。 此外，这些传感器节点的位置是不可能在事先被精确地设定的，同时也不可能 精确地知道并确定这些节点之间的邻居关系【1 5 1 。为了适应这样的条件和环境， 这些被部署的传感器节点就必须具有自组织的能力，同时也要能够自动地进行 配置和管理，并还需要能够借助于拓扑控制机制和网络协议的基础上自动地形 成一个能够用于转发检测数据的多跳无线网络系统。 通过使用无线传感器网络，可以发现有时会因为耗尽了节点的能量的因素 或其他的一些环境因素而导致节点失效te 1 6 】，而有时为了实现提高监测精度的 目的而增加若干节点到网络中。但是无论是节点的失效而导致的减少节点还是 为了实现目的而采取的增加节点都会导致网络的拓扑结构发生动态的变化，所 以无线传感器网络的自组织性还要能够适应网络拓扑结构的动态变化。 ( 3 ) 以数据为中心的网络 无线传感器网络是一个任务型的网络，离开无线传感器网络来谈论传感器 节点是没有任何意义的。在传感器网络中观察者通常只关注它的一定区域内的 某个观测的指标值，而不关注某个节点具体的信息，即观察者只关心目标出现 的位置，而并不关心是哪个节点监测到了目标，所以无线传感器网络是一个以 数据为中心的网络。 ( 4 ) 能量有限，能力有限 在无线传感器网络中传感器节点的能量是由电池供给的，电池的容量一般 是不会很大的，而由于节点通常是被部署在人不可到达或者条件恶劣的环境中 的，这就导致不可能也不能够及时更换电池或给电池充电，所以传感器节点的 能量是非常有限的。 通常传感器节点可以被看作是一种微型的嵌入式设备，而该系统的主要特 点是价格低廉和功耗较低，所以节点所具有的处理器和存储器的计算能力和存 储能力都将比较小。在执行监测的任务时，为了完成大量的数据采集和转换、 数据处理和管理等一系列的工作，使得如何利用有限的资源来完成协同任务就 成为传感器节点设计的核心问题。 ( 5 ) 可靠性的网络 由于传感器网络一般被部署在人不可到达或者环境危险的地方，导致传感 6 武汉理工大学硕士学位论文 器节点将会长时间工作在露天的环境中，遭受着风吹暴晒，甚至还可能会遭到 人或者动物的破坏。传感器节点通常是通过飞机抛洒等这样的途径被随机分布 在监测区域的，每个节点非常坚固且不容易损坏，再加上节点的数量大、分布 广的因素，维护网络的难度是非常大的，甚至可以说是不可维护的。除此之外， 为了保护监测到的数据以防被盗并能及时阻止伪造的监测信息被获取，将无线 传感器网络的安全性和通信保密性作为网络的十分重要且关键的两个方面给予 重视。由此可知，非常好的鲁棒性和容错性对无线传感器网络的软硬件是必须 具有的两个特点l 1 7 j 。 ( 6 ) 应用相关的网络 存在于客观世界里的物理量是多种多样的，也是不可穷尽的，而传感器网 络是用来感知客观的物理世界并从中获取其信息量的。对不同的传感器网络应 用而言，它们将侧重于不同的物理量，关注的信息也将不同，因此，对传感器 的应用系统也就会有不同的要求，同时它们的硬件平台，软件系统以及网络协 议的差异也会是非常大的。对于无线传感器网络的开发应用而言，更关心的是 无线传感器网络的差异，并针对每一个具体的应用来研究无线传感器技术，这 是无线传感器网络设计不同于传统网络的一个显著特征。 1 3 3 无线传感器网络的应用领域 作为一种源于应用而且服务于应用的现实可行的网络技术，无线传感器网 络的应用前景是非常广阔的。随着它的深入研究和广泛应用，将会逐渐深入到 人类生活的各个领域中。 ( 1 ) 军事领域 由于无线传感器网络有快速部署、隐蔽性强、随机分布和可自组织等方面 的特点，使其很适合应用于恶劣的战场环境中。它能代替边界上的警卫和岗哨 进行防御，使得士兵远离危险地带；为了防范可能的袭击，它还可以用于识别 和定位目标；此外利用传感器网络也能够实现对敌军兵力和装备的监控、协助 智能炸弹对目标的攻击、战场的时实监视、战争破坏情况的评估以及生物化学 攻击的监测和搜索等功能。 ( 2 ) 医疗领域 无线传感器网络在监测人体的各种生理数据、监测和跟踪医院内医生和患 者的健康状况、医院的药品管理以及远程医疗等方面的应用中发挥着非常重要 7 武汉理工大学硕士学位论文 的作用。通过把特殊用途的传感器节点安装在病人的身上的手段，比如心率和 血压监测等设备，医生就可以利用无线传感器网络随时随地地对被监护病人的 病情进行了解，一旦发现到异常时可以进行及时地抢救。此外还可以把一些微 型传感器植入人体器官当中，以便能够实现随时随地监测并发现器官的生理状 况以及功能恶化情况的目的，进而采取必要的治疗措施来挽救病人的生命。总 而言之，无线传感器网络将会为未来的远程医疗提供更加快捷、方便的技术实 现手段。 ( 3 ) 环境监测 随着对环境科学的研究的不断加深，它所涉及的范围将越来越广泛，这使 得使用传统的环境数据进行采集的方式已经很难再适应，而无线传感器网络不 仅能够为获取野外随机性的研究数据提供便利同时还可以避免由于传统数据的 采集方式而给环境造成的侵入式破坏。到目前为止，无线传感器网络在环境领 域的应用主要包括对农作物的灌溉情况的监测、大气和土壤成分的监测、森林 火灾的预报以及通过跟踪候鸟和昆虫的迁移进行种群复杂度研究等方面【l 引。此 外，无线传感器网络还可应用在精细农业上，如农作物中害虫的监测、土壤的 酸碱度以及施肥状况等方面。 ( 4 ) 智能家居 无线传感器网络在家居中的应用是通过将无线传感器网络与因特网( i n t e r n e t ) 连接在一起，以为人们提供更加舒心、便利和人性化的智能家居环境为目的。 另外可以利用远程监控系统实现对家电进行远程遥控的目的，还可以通过温度、 光照等传感器对家庭环境进行自动控制以及通过图像传感设备随时对家庭的安 全情况进行监控。 ( 5 ) 空间探索 探索外部星球一直是作为人类梦寐以求的理想的，而利用航天器布撒的传 感器节点返回的信息可以对星球的表面实现长时间的监测，这是目前为止一种 最经济可行的探测方案。由美国宇航局的j p l ( j c tp r o p u l s i o nl a b o r a t o r y ) 实验室研 制的无线感应网( s e n s o rw e b s ) 就是为将来对火星进行探测而做的技术准备，它已 经在佛罗里达宇航中心周围的环境监测项目中进行了测试和完善。 ( 6 ) 工业和商业控制 对于工业领域来说，借助于安置各种的传感器节点在车间的手段可以实现 监测车间中的各种设备比如运行的机器所处的状态的目的，同时也能够对相关 的特定操作进行控制。 8 武汉理工大学硕士学位论文 对于商业领域而言，传感器网络几乎可以在任何商业的地方实现对灯光、 空调等这些设备的控制，同时它也能在物资跟踪和供应链的管理方面发挥很大 的作用。比如对于一堆分布非常散乱的物品，无线传感器网络就可以帮助从中 找到需要的物品的位置，以使整个的供应链能够高效地运转起来。 ( 7 ) 其他应用 微型化、自组织和对外部世界的感知能力是无线传感器网络的三个特点， 这些特点使得无线传感器网络在更多的领域得到了更加广泛的应用。 在交通领域可以将无线传感器网络作为车辆监控的有力工具，以起到车辆 跟踪、控制以及智能交通控制的作用【1 9 1 。同时也可以将无线传感器网络应用于 保障建筑物安全的领域，借助于声音、图像、温度、气体检测等一系列的传感 器，通过将它们安置在建筑物的内部，以达到及时反馈异常事件的发生等目的。 此外在灾难拯救、公共安全、交互式博物馆、汽车防盗、工业传感、物流 管理以及工业自动化生产线等很多的领域中，无线传感器网络都将会孕育出全 新的设计和应用模式。 1 3 4 无线传感器网络的关键技术 作为当今信息时代的新的研究热点，无线传感器网络涉及到了很多的关键 技术，为了满足网络的各种应用需求和场合我们需要去迸一步地探索与研究这 些关键技术。以下为无线传感器网络的几个主要的关键技术： 1 数据融合 在无线传感器网络中节点的分布很密集，所以采集到的数据信息必定存在 着大量的冗余，虽然这在一定程度上能保证网络的健壮性，但是如果把采集到 的所有数据都传送给用户，就会导致很大的通信量以及消耗过多的能量【2 0 1 。数 据融合技术可以对这些来自多个传感器和信息源的数据信息进行整合、相关以 及判断等处理，最终可以有效地减少网络中的数据冗余，节省了能量。同时， 通过数据融合技术对多份数据进行综合处理，还可以在一定程度上提高数据信 息的精确度。 2 网络协议 部署在无线传感器网络中的传感器节点的通信能力、计算能力、存储能力 和带有的能量都是很有限的，所以每个节点获取的只能是局部网络的拓扑信息， 这就要求在其上运行的网络协议也是不能太过复杂的。同时，由于传感器网络 9 武汉理工大学硕士学位论文 的拓扑结构的动态变化的特征，网络资源也在动态变化着，这些都对网络协议 提出了更高的要求以满足网络的需求。目前无线传感器网络协议的重要研究对 象是网络层协议和数据链路层协议。 3 定位技术 在传感器节点采集的大量数据信息中，位置信息是不可缺少的部分，包含 位置信息的监测信息才将可能会具有一定的意义。确定事件发生的位置或者被 采集的数据的节点位置，是无线传感器网络的最基本功能之一。所以为了能提 供有效的位置信息，如何确定传感器节点的位置就变得尤为重要。虽然g p s 已 经在很多的领域中被使用，但限于它的成本高且对使用环境还有一定的限制， 是不能为网络中的每个节点安装g p s 的，这就需要对定位技术进行进一步的研 究，定位技术作为本文研究的主要内容，将会在后续章节中进行重点且详细地 阐述。 4 网络安全， 由于传感器网络通常被部署在人不可控制和无人维护的环境中，所以它的 网络安全受到了很大的挑战。传感器网络采用的是无线传输信道，很有可能会 遇到窃听、消息修改、消息注入、路由欺骗、拒绝服务、恶意代码等一系列的 安全威胁，尤其在某些特定的应用中，安全问题就显得更加重要了。为了能够 保证采集的数据的可靠性、数据融合的高效性等要求，传感器网络需要有一套 有效的安全机制，用以提高它的网络安全。 5 操作系统 传感器节点通常是一个微型的嵌入式系统，它的特点决定了传统的操作系 统已经不能满足其需要，美国加州大学伯克利分校开发了专门针对于无线传感 器网络的t i n y o s 操作系统，它既能满足无线传感器网络的特殊要求，也能给各 种应用给予最大的支持，虽然它已经得到了广泛的应用，但还存在许多不足之 处。 6 时间同步 对许多的无线传感器网络的应用和协议而言，时间是非常重要的一个方面， 所以实现时间同步是网络系统协同作用的一个很关键的机制。虽然每个节点都 有它们自己的本地时钟，但由于电磁波干扰以及温度变化等方面的因素，使得 即使某一时刻所有的节点的时钟都同步了，随着时间变化也将可能会逐渐出现 偏差【2 。受到能量、功耗、体积以及价格等方面的限制，传统的网络时间协议 以及时间同步算法已经不再能够适用于传感器网络了，需要设计或修改一种新 1 0 线传感器网络目前 的定位算法进行了 研究，在开始的部分介绍了无线传感器网络的研究背景及其选题意义并对无线 传感器网络的结构、特点、应用领域及其关键技术等方面进行了相关的概述。 随后对已经提出的定位算法进行了分类并对一些典型的距离无关的定位算法的 基本原理作了详细的介绍，其中重点对d v - h o p 定位算法的算法思想作了详细 的研究分析并提出了它的不足之处。然后通过研究分析遗传算法和模拟退火算 法的理论的基础上引入了遗传模拟退火算法，并将其应用到d v - h o p 定位算法 中，从而提出了改进算法。最后对提出的改进算法和已有的几种改进算法以及 原d v h o p 定位算法进行了仿真实验。本文的章节安排如下： 第一章首先介绍了无线传感器网络的研究背景及其选题意义和国内外的研 究现状，然后对无线传感器网络的结构、特点、应用领域和关键技术作了详细 的概述，最后对本文的研究内容作了阐述并对章节安排作了说明。 第二章首先对无线传感器网络的定位技术的基本概念及其相关的基本术语 作了详细的介绍，然后通过分析现有的定位算法的特点，将它们进行了分类。 同时对一些典型的距离无关的定位算法的基本原理和计算节点的方法进行了详 细的阐述，最后对作为定位算法的性能评价指标的因素作了简单的介绍。这些 都为后面的研究工作提供了重要的理论基础。 第三章首先介绍且研究分析了遗传算法的基本原理、基本步骤以及相对应 的流程图，然后对模拟退火算法的原理和步骤进行了具体的研究分析，最后在 分析两种算法的优缺点的基础上引入了遗传模拟退火算法，并介绍分析了该算 法的基本步骤和相关的运行参数。这为后续的算法的改进奠定了基础。 第四章首先介绍了距离无关的d v - h o p 定位算法的具体思想及其步骤，并 分析了其不足之处，然后分析了现有的几种改进的d v o h o p 算法的改进思想， 最后将提出的遗传模拟退火算法应用于d v h o p 算法中，并详细阐述了具体的 算法实现。 ， 第五章主要对本文提出的改进算法进行仿真实验，首先介绍了算法仿真的 1 2 研究课 可控制 的，所以网络中大多数节点的位置事先是不能够被确定的，而在无线传感器网 络的很多应用中为了获得监测信息的准确位置，节点的位置信息是非常重要的， 因此确定传感器节点的位置对无线传感器网络的有效性起着决定性的作用，是 无线传感器网络的最重要的功能之一，同时也是本文的研究重点。 2 1 无线传感器网络定位的基本概念 由于能量有限、随机部署、数量较大以及低成本等一系列的特点，g p s 不 适合被安装于传感器网络中的每个节点，这样做会导致它的成本非常地高，所 以只能给一小部分的传感器节点装配g p s 来指定其位置坐标，这类节点就称之 为锚节点，另外的一类不能确定自身位置的节点被称之为未知节点。如下图2 1 所示，u 为未知节点，m 为锚节点。 图2 1 传感器网络中的锚节点和未知节点 在无线传感器网络中，节点定位就是根据少量的锚节点的位置信息，然后 武汉理工大学硕士学位论文 再利用一定的定位算法并按照某种定位机制，从而最终计算出传感器节点在二 维或三维空间分布上的坐标位置信息。 2 2 无线传感器网络定位技术的基本术语 以下为无线传感器网络中常见到的一些基本术语： 1 ) 锚节点( 信标节点) ：指已知自身位置信息的节点，通常被装配有g p s 设 备或者通过人工部署。 2 ) 邻居节点：指处于彼此通信范围内的两个传感器节点，它们之间能够进 行互相的无线通信，这两个节点就被称之为邻居节点。 3 ) 非锚节点：也被称之为未知节点，是指事先不能确定其自身位置的节点， 需要通过锚节点的位置信息来确定其位置的节点。 4 ) 跳距：指网络中两个节点之间相隔的各个跳段距离的和，称之为这两个 节点之间的跳距。 5 ) 跳数：指网络中两个节点之间所相隔的跳段个数总和，称为这两个节点 之间的跳数【2 2 1 。 6 ) 基础设施：指协助传感器节点进行定位的已知其自身位置的固定设备， 如通信卫星等。 7 ) 网络密度：指单个节点通信能够覆盖的区域的传感器节点的平均数目。 8 ) 网络连接度：指传感器网络中所有节点的邻居节点数目的平均值，它能 反映节点配置的密集程度。 9 ) 接收信号强度指示：指网络中节点收到的无线信号的强度大小。 1 0 ) 到达时间：指无线信号从一个传感器节点传播到另外一个传感器节点所 需要花费的时间，称之为该信号的到达时间。 1 1 ) 到达时间差：指两种信号以不同的传播速度从一个传感器节点传播到另 外一个传感器节点所需要花费的时间之差。 1 2 ) 到达角度：指传感器节点接收到的信号相对于自身轴线的角度。它可以 分为两种方式，分别是接收天线的相位响应和接收天线的幅度响应。 1 3 ) 视线关系：指如果网络中的两个节点之间是没有任何障碍物间隔且它们 能够直接地进行通信，则称这两个节点存在着视线关系。 1 4 ) 非视线关系：同视线关系的概念相反，如果网络中的两个节点之间有障 碍物间隔着，那么就称为这两个节点存在着非视线关系。 1 4 武汉理工大学硕士学位论文 2 3 无线传感器网络定位算法的分类 随着应用场合、软硬件资源以及应用需求的不同，研究人员已经提出了很 多种类的无线传感器网络的定位算法，到目前为止，这些定位算法可以被分为 以下几类1 2 列： 1 基于测距与基于非测距的定位算法 根据在节点定位的过程中是否需要物理地测量节点之间的距离，可以将已 有的定位算法分为基于测距的和基于非测距的即距离无关的定位算法这两种。 基于测距的定位算法是通过一定的测距技术来测出节点之间的距离或者角 度等信息，然后再使用特定的坐标计算方法，计算出网络中未知节点的坐标信 息。目前已有的测距技术和计算节点的坐标信息的方法分别如下： 目前已有的测距技术主要有以下几个技术： r s s i ( r c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) ：一般用于无线射频信号的定 位。它的工作原理是将发射节点所发射的信号强度与接收节点收到的信号强度 作一个比较，然后使用理论或者经验的信号传播模型将信号传播过程中的信号 强度损耗转化为距离。未知节点利用计算出的r s s i 值来算出它与发射此信号的 信标节点之间的距离。 基于到达时间t o a ：它的工作原理是通过测量无线信号从信标节点发送后到 未知节点接收到此信号的传输时间来计算节点之间的距离。 基于到达时间差t d o a ：它的工作原理是通过记录两种以不同传播速度同时 从发射节点发送的信号到达的时间差，然后再利用它们的传播速度，计算出两 个节点之间的距离。 基于到达角度a o a - 它是通过阵列天线或者结合多个接收器以得到相邻节点 发送信号的方向，而接收节点根据天线的阵列或者多个