（计算机软件与理论专业论文）无线传感器网络leach算法的研究与改进.pdf

摘要 摘要 无线传感器网络是一种全新的信息获取和处理的网络，它综合了传感器技 术、嵌入式技术、无线网络通讯技术、分布式信息处理技术以及微机电技术等。 是由大量的传感器节点组成，通过无线通信方式形成的一个自组织网络系统。 其目的是感知、采集和处理网络区域中的信息并发送给观察者。无线传感器网 络作为计算技术、通信技术和传感器技术三项技术的相结合的产物，是一种全 新的信息获取和处理技术。本论文在简要介绍无线传感器网络的基础上，分析 了l e a c h 分级路由协议存在的一些问题以及如何解决这些问题。 无线传感器网络已经引起学术界和工业界的高度重视，被称为是2 1 世纪最 具有发展前景的技术之一。目前无线传感器网络将对人们的生活产生深远的影 响，它的应用范围比较的广泛。这种网络系统被广泛地应用于国防军事、大型 工业园区的安全检测、国家安全、交通管理、原始森林的防火和动物活动范围 的情况检测、医疗卫视、抗灾等领域。 无线传感器网络路由协议的首要目标是节能，其次是延长网络生命周期。 本文将着重对l e a c h 路由算法进行研究与改进，具体的研究工作将包含以下几 个方面： 1 大量阅读国内外相关的资料，对传感器网路体系结构进行全面的研究， 对现有的无线传感器的路由协议进行归纳分析。 2 根据无线传感器网络的路由协议的设计要求，对目前一些典型的路由协 议进行分析和对比。通过分析得出l e a c h 路由协议的优点和存在的不足，然后 对其进行改进，通过对改进的路由协议进行仿真实验。 3 在簇首选择阶段，我们考虑以节点的剩余能量多少作为主要依据来选择 簇首，只有那些剩余能量大于所有节点的平均能量的才有可能成为簇首。同时， 对相应的成簇算法也进行改进。 关键词：无线传感器网络；网络层；l e a c h 路由协议；能耗 a b s t r a c t r e c e n t l y , w i r e l e s ss e n s o rn e t w o r k si sr e c e i v i n gm o r ea n d m o r ea t t e n t i o n ，i tl sa r l e wi n f b n n a l i o na c q u i s i t i o na n dp r o c e s s i n gn e t w o r k s ， i ti sa l s oar e s u l to f c o m b i l l a t i o no ft h ec o m p u t e r ，e o m m u n i c a t i o na n d s e n s o rt e c h n o l o g y i tc o n s i s t so fa l o to fs e n s o rn o d e st h a tf o r mas e l f - o r g a n i z i n gn e t w o r ks y s t e mt h r o u g hw i r e l e s s c o n l m u r i i c a t i o n i t sg o a li st op e r c e i v e ，c o l l e c t i v ea n dp r o c e s st h ei n f o r m a t i o ni nt h e n 咖o r k t h i sp a p e rb r i e f l yi n t r o d u c e st h es t r u c t u r eo fw i r e l e s ss e n s o rn e t w o r k s ， a n a l y z es o m ep r o b l e m so ft h el e a c hr o u t i n gp r o t o c o l sa n dh o w t os o l v et h e s e p r o b l e m s w 沁1 e s ss e n s o rn e t w o r kh a sa t t r a c t e dp e o p l e sg r e a ta t t e n t i o n , a n di t h a sb e e n s e e na so n eo ft h em o s tp r o m i s i n gt e c h n o l o g i e so ft h e2 1s tc e n t u r y i tw i l lh a v e e i l o n n o u si m p a c t so np e o p l e sl i v e s ，a n di t sr a n g eo fa p p l i c a t i o n si sv e r yw i d e i ti s w i d e l yu s e di nm i l i t a r y , c o m m e r c e , t r a n s p o r t a t i o nm a n a g e m e n t ，f o r e s tf i r ep r e v e n t l o n a n de n v i r o n m e n t a lm o n i t o r i n ga n ds oo n t h en e t w o r kl a y e rh a sap i v o t a lr o l ei nw i r e l e s ss e n s o rn e t w o r k s ，w h i l et h e n e t w o r kl a y e rr o u t i n gp r o t o c o li st h ek e y i t s m a i nt a r g e ti se n e r g yc o n s e r v a t i o n ， f o l l o w e db ye x t e n s i o no ft h en e t w o r kl i f ec y c l e t h i sa r t i c l ef o c u s e so nt h el e a c h r o u t i n ga l g o r i t h m s ，a n dp u t f o r w a r da ni m p r o v e dm e t h o d ，d e t a i l e ds t u d i e si n c l u d et h e f o l l o w i n ga s p e c t s ： 1 r e a d i n gt h er e l e v a n ti n f o r m a t i o na th o m ea n da b r o a d ，r e s e a r c ht h es e n s o r n e t w or ! k 锄他h i t e c t u r ec o m p r e h e n s i v e l y a n a l y z et h ea d v a n t a g e sa n dd i s a d v a n t a g eo f t h er o u t i n gp r o t o c o l se x i s t i n gi nt h ew i r e l e s ss e n s o rn e t w o r k a c c o r d i n gt o t h e w i r e l e s ss e n s o rn e t w o r kr o u t i n gp r o t o c o ld e s i g nr e q u i r e m e n t s ，a n a l y z ea n dc o m p a r e s o l n et y p i c a lp r o t o c o l so fc u r r e n tr o u t i n gp r o t o c o l s w eo b t a i nt h es h o r t c o m i n g so f t h el e a c hr o u t i n gp r o t o c o lb ya n a l y z i n gi t ，a n dt h e ni m p r o v ei t ，d ot h es i m u l a t i o n e x p e r i m e n to f t h ei m p r o v e dr o u t i n gp r o t o c 0 1 2 i nt h ec l u s t e rh e a ds e l e c t i o np h a s e ，w ec o n s i d e rt h er e m a i n i n ge n e r g i e so f t h e n o d e st os e l e c ta st h em a i nb a s i sf o rt h ef i r s tc l u s t e r , o n l yt h o s ew h o s er e m a i n i n g e n e r g yi sg r e a t e rt h a nt h ea v e r a g ee n e r g yo fa l l n o d e si nt h en o d eb e f o r ei t c a n i i a b s t r a c t b e c o m et h ef i r s tc l u s t e r m e a n w h i l e ，i m p r o v et h ec o r r e s p o n d i n gc l u s t e r i n ga l g o r i t h m 3 i nt h ed a t at r a n s m i s s i o np h a s e ，e a c hn o d ed u et od i f f e r e n td i s t a n c e sf r o mt h e c l u s t e rh e a dn o d ee n e r g yc o n s u m p t i o ni sd i f f e r e n t m e a n w h i l e ，t h ec l u s t e rh e a da l s o l l at h ed i f f e r e n td i s t a n c ef r o mt h eb a s es t a t i o n ，r e s u l t i n gi nt h ee n e r g yc o n s u m p t i o no f c l u s t e rh e a dd i f f e r e n tb e t w e e nt h ep r o p o s e dc l u s t e r - h e a d sa m u l t i - h o pr o u t i n g k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；n e t w o r kl a y e r ；l e a c hg r a d i n gr o u t i n g p r o t o c o l ；s a v ee n e r g y i i l 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得南昌大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作一c 瑚海坪字吼纠钏月9 日 学位论文版权使用授权书 本学位论文作者完全了解童昌太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权直昌太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名( 手写) ：、瓢研导师签名( 手写) 碴屉 签字日期：2 帅7 年j 】月f 口日 签字f tg q ：砂可年iz 月of j 第一章绪论 第一章绪论 本章首先介绍论文的课题来源，然后是选题依据、课题的意义和文章的组 织结构。 1 1 问题的提出 本课题是导师指导下的自选课题。 课题内容是研究分析无线传感器中的路由协议，针对低能量自适应分簇路 由协议( 1 0 we n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ，简称l e a c h ) ，提出了相应的 改进方法。论文在简要介绍无线传感器网络的基础上，分析了l e a c h 路由协议 存在的一些问题。然后提出解决这些问题的方法。 1 2 选题依据 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，简称w s n ) 是功能不同的无线 传感器节点组成的【1 1 。每个传感器节点是由若干某块组成的，这些模块包括数据 采集模块、数据处理模块、通信模块和供电模块等。节点是信息采集和发送者， 采集的数据通过多跳路由到达网关。可以利用飞机飞跃网络上空，通过网关采 集数据。也可以通过i n t e m e t 、移动通信网络、卫星与监控中心进行通信 2 1 。 w s n 中所有的节点地位都是平等的，没有中心节点，各个节点通过分布式 算法来相互协调，形成一个自组织网络。w s n 中节点一般通过电池供电，节点 一般分布在无人看管的环境中，电池不能补充和更换，节点能量受限f 5 】。因此， 延长网络的生命周期就必须降低节点工作能耗，节点的能量主要消耗在通信模 块上。如果想要减少节点的能量消耗就需要减小节点的有效传输半径，但是半 径的减小会降低节点的覆盖面积。为了实现w s n 的大面积的覆盖，必须使用多 跳中继的来传输数据，这就就是路由协议的研究工作。 节点由于受到体积、价格和电源供给等因素的限制，通信距离较短，只能 与自己通信范围的邻居节点交换数据1 6 1 。要访问通信范围以外的节点，必须使 用多跳路由。为了保证网络内大多数节点都可以与网关进行通信，节点的分布 要相当的密集。 第一章绪论 无线传感器网络的特征使得它不能直接使用传统网络的一些协议，例如 i e e e8 0 2 1 1 等。所以国内外的专家针对各个层次进行了不同的研究，目前研究 成果比较少的就是网络层，网络层负责路由的发现与维护，路由协议是无限传 感器网络设计是否成功的关键。 1 3 论文的意义 w s n 的应用范围广阔，但也存在着一些问题。目前，如何减少能量消耗是 w s n 研究的重点问题。大部分的能量消耗在无线通信模块上，延长网络生命周 期就成为w s n 核心技术之一。从路由的角度看，w s n 既不同于传统的i n t e m e t 网络，也不同于移动自组织网络( m o b l i e a dh o cn e t w o r k ，简称a dh o e 网) 。它 的特点是节点能量不可补充，数据冗余等，这些问题在传统网络中都不存在， 所以传统网络路由协议不能应用于w s n t 引。 传统网络的研究重点是通信质量( o o s ) ，而w s n 由于节点能源、带宽资源 有限，路由协议的研究重点就是如何提高能量的效率。路由协议的主要功能是 将数据从源点转发到目标节点，主要是指寻找从源点到目标节点之间的最能节 省能量的路径，将数据沿着这条路径传输到目标节点。但是在无线传感器网络 中，节点的能量有限，不能保证数据能否到达目标节点，因此路由协议需要提 高能量的的利用率。我们必须设计全新的、适合无线传感器网络的路由协议， 目前国外在这方面都有了一定的成果。国外很多著名高校的研究小组都在研究 和从事传感器网络的技术。 路由协议是影响网络性能的一个重要因素，是无线传感器网络正确运行的 关键。平面网络的最大缺点是网络规模受限，每一个节点需要知道到达其它节点 的路径，维护这些动态变化的路由信息需要大量的存储空间。网络规模越大， 路由维护和网络管理的开销越大1 4 j 。 w s n 路由协议在网络中有着相当重要的作用，它与蜂窝网络、无线自组织 网络等存在着差异，其特点是：拥有大量的传感器节点、节点位置分布随机。 网络拓扑结构是动态变化的，电源能量有限。因此，传统网络中的路由协议不 能用在无线传感器网络中，需要重新研究新的路由协议，来满足这种新的网络， 减少无线传感器网络中的能量消耗和延长网络的生命周期。 层次路由协议有利于移动管理、资源分配和提高扩展性。但分簇算法会带 来计算、通信和维护开销，因此，必须设计合理的节能的分簇算法。本文重点 2 第一章绪论 研究无线传感器网络中的低能耗分簇路由协议，分析国内外学者提出的先进路 由协议算法，对l e a c h 算法进行改进【1 0 】。 1 4 文章的组织 第一章首先介绍了本文的选题依据，其次讲述了本论文的研究意义和目的。 第二章具体地介绍了w s n 的基础知识，包括w s n 的体系结构及相关的特 性。同时，讲述了无线传感器网络一些常用的路由协议及它们的特点，重点介 绍了l e a c h 路由协议1 9 】。 第三章详细介绍了主要研究内容l e a c h 路由协议算法，提出改进簇头的选 举和簇形成过程的改进算法。 第四章对改进的路由算法进行仿真实验。 第五章对论文中所做的工作进行总结，给出下一步需要进行的工作。 第二章无线传感网络的综述 第二章无线传感器网络的综述 w s n 是一组传感器节点以自组织方式组成的网络，它的目标是采集网络区 域内的数据【7 1 ，对这些数据进行处理，然后将这些信息传送到网络中需要的用户。 用户通过分析软件来观测网络的运行情况，并且对网络中的节点进行管理和监 控。 传感器网络是由传感器节点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 、和管理 节点组成的系统，它的典型结构如图2 1 所示，大量的传感器节点随机的分布在 检测区域内】。传感器节点是一个嵌入式系统，它的处理、存储和通信能力一 般。汇聚节点负责连接外部网络和传感器网络，实现内外两种网络协议之间的 转换，把采集到数据转发给外部网络中需要数据的人员。管理节点的任务是负 责无线传感器网络的配置和管理，发布网络中节点的任务和采集区域内的数据。 采集到的数据沿着其它传感器节点传输到汇聚节点，最后通过互联网、卫星等 其他通信方式到达管理节点【l 引。 网关 l 监控中心 监测区域 图2 1 无线传感器网络的体系结构 4 第二章无线传感网络的综述 2 1w s n 简述 2 1 1 节点的结构 w s n 是由许多传感器节点组成的网络，在不同的应用中，传感器节点的组成 不同【_ 丌。但是一般的传感器节点都是由传感器模块、数据采集模块、无线通信模 块和供电模块等组成，如图2 2 所示。传感器模块采集区域内的数据，然后对采 集到的数据进行格式的转换，处理器模块控制传感器节点进行的操作，同时还 存储采集到的数据。无线通信模块负责基站和其它传感器节之间进行通信，供 电模块提供无线传感器网络节点之间运行所需要的能量【8 】。 处理器 r 。1r 。1， 传感器ha d d a 卜 存储器 叫! 兰卜叫竺! 卜叫收发器 丁tt i能量供应模块 2 1 2w s n 的体系结构 图2 2 传感器节点结构 w s n 体系结构一般是由网络通信协议、网络管理以及应用支持技术组成 【4 】 o 1 网络通信协议 物理层：负责载波频率的产生、信号的调制和解调等，由于w s n 主要是基 于无线通信，所以，无线频段的调制和扩频技术成为物理层协议的主要技术。 目前，人们对物理层的研究还处于初级阶段，减少系统功耗和降低成本是该层 研究的主要内容f 1 8 】。 第二章无线传感网络的综述 数据链路层：负责介质的接入和差错控制，介质接入协议可以在通信网络 中确保点对点的连接；差错控制保证源节点发出的信息可以完整、无误地到达 目标节点。其中介质访问控制协议关注的是信道的有效利用，设计节能的睡眠 机制等【1 6 】。 网络层：主要负责路由发现与维护，在无线传感器网络中有着举足轻重的 作用，可以说路由协议的设计是无线传感器网络成功与否的关键。随着网络规 模的增大，路由协议的低能耗、可扩展性、动态拓扑性成为人们研究w s n 路由 协议的重点【1 羽。 应用层：与其他传感器节点进行通信的一个应用。 2 几种管理 拓扑控制：通过控制功率，减少节点之间冗余的通信链路，形成一个优化 的网络【1 8 】。 能量管理：传感器节点如何有效地使用能量，各层的协议都需要进行考虑。 传感器节点的能量很多都消耗在节点之间的通信上，所以通信模块的节能是研 究重点。目前，节能策略主要是有数据融合、冲突避免和多跳路由通信等【2 l 】。 安全管理：由于传感器节点的速度和能量容量等因素的限制，传统的网路 的安全机制不能直接应用于w s n ，需要设计新的网络安全机制。 3 支撑技术 节点定位：正确的节点定位是w s n 应用的前提，采用g p s 是得到节点位 置的一种方法，但我们不可能为每个节点都安装高能耗的g p s 设备，需要在路 由算法上进行改进。定位技术是由基于距离的定位和距离无关的定位【2 2 】两种技 术组成，距离无关的定位机制能满足大多数w s n 应用的要求，是目前常用的定 位机制。 2 1 3w s n 的应用 传感器网络在人们的日常生活中有很多的应用，例如军事、城市安全、天 气预报、安全生产、家居安装、城市交通、空间探测等领域。随着传感器网络 的发展，它将逐渐深入到人们的各个生活领域中1 6 】( 9 1 。 ( 1 ) 军事应用 信息技术的快速发展，促进了传感器网络技术的发展。传感器网络具有准 确性和实时性等特点，因此适合军事上的应用。这些特点都能够使人们获得想 6 第二章无线传感网络的综述 要的军事信息【2 。 ( 2 ) 环境监测 随着经济的发展，人们越来越关注我们生存的环境。传感器网络可以监视 空气的湿度、温度、污染物的分布等环境状况，也可以对森林的检测，通过检 测森林中的日常参数确定是否有火灾发生。通常传感器节点随机分布在森林中， 平时定期报告森林的日常数据，当有火灾发生时，传感器节点会及时地将火灾 发生的具体地点、火势的大小等信息发送给相关部门。 ( 3 ) 应急场合 在遭受地震、水灾、强热带风暴等灾难的地区，固定的通信网络设施可能 被破坏或无法正常工作。这时，就需要无线传感器网络这种不依赖固定网络设 施、能快速组网的自组织网络。偏远野外、植被不能破坏的自然保护区和不能 用固定网络设施进行通信的场合，也可以用无线传感器网络来进行信息采集与 处理f 1 0 1 。 ( 4 ) 医疗健康 国外一所大学的研究小组利用无线传感器网络构建了一个医疗检测平台， 平时，病人躺在病床上，身上安装了若干个检测传感器，被连接到病床边的监 测仪器上。这种方式下，病人必须呆在床上，不自由。利用无线传感器网络技 术，病人便可自由活动，医生手持p d a ，可以随时接收报警消息或检查病人的 情况。 ( 5 ) 日常生活 无线传感器节点可以随机地分布在建筑物内，采集区域内的环境参数，为 室内环境控制和危险情况提供重要的参考依据。2 0 0 4 年8 月，一个公司演示了 家庭护理的无线传感器网络系统。这个系统通过在鞋、家具、家用电器等设备 中嵌入半导体传感器，帮助老年人和残疾人的家庭生活，利用无线通信将各个 传感器联网可高效传递信息以便接受护理。 ( 6 ) 宇宙探测 进行宇宙探索天是人们的梦想，我们可以借助飞机在天空中部署传感器网 络节点，传感器节点可以对天空中的天体的表面进行监测，这种方法在理论上 是可行的。 2 1 4w s n 的特征 7 第二章无线传感网络的综述 无线传感器网络除了具有a dh o e 网络和传统网络的特征以外，还具有以下 的特剧7 】【9 】： ( 1 ) 资源有限 无线传感器节点通常采用电池供电，电池的能量有限。这些采用电池供电， 节点分布在人无法接近的区域中，更换电池很困难，所以网络中的节点会能量 受限失效。电源能量有限是阻碍无线传感器网络应用的关键，因此，延长网络 的生命周期是无线传感器网络研究的核心问题之一。 传感器网络的通信带宽一般不是很宽，并且带宽的范围有时候会发生变化， 它的覆盖范围从几十到几百米。因为节点会遭受日晒、建筑物、障碍物等因素 的影响，传感器节点之间的通信经常间断，导致通信失败。 ( 2 ) 节点规模大 为了满足人们获取信息的需要，在传感器网络中通常随机分布许多传感器 节点。这些传感器节点数据一般比较多。这些特点增加了传感器网络的维护的 困难【2 0 j 。 ( 3 ) 自组织成网 在无线传感器网络应用中，传感器节点分布在没有基础硬件设施的地方。 通常，人们通过飞机等设备布置传感器节点到森林，或者随意放到人们不经常 出现的区域。这些环境因素要求传感器节点拥有自组织的功能，能够自己组成 特定的网络。 ( 4 ) 拓扑结构不固定 无线传感器网络是一个动态网络，节点可以移动。一个节点可能会因电池 能量耗尽或其他故障，在网络中实效，成为没有任何功能的节点。无线传感器 网络的拓扑结构发生变化的原因很多，通常，网络中有些节点工作了很长时间， 节点的能量不能及时供应，那么实效的节点在网络中就没有任何的作用，就需 要舍弃这些实效节点，形成新的网络结构。加入新的节点或者节点在网络中移 动都会导致网络的拓扑结构发生变化。 ( 5 ) 以数据为中心 无线传感器网络的主要工作是收集、统计以及处理数据，它的设计重点是 数据管理和处理。主要包括对网络内的数据进行存储、查询、分析、挖掘和对 数据的初期处理进行决策。无线传感器网络中的每个节点都有数据处理能力， 它们会对网络中基站采集的数据进行处理，然后将数据传输给需要这些数据的 8 第二章无线传感网络的综述 人。所有的操作都是围绕数据进行的，所以，无线传感器网络是一个以数据为 中心的网络。 2 2w s n 路由协议的发展 在无线传感器网络中，网络层的路由协议是目前人们研究的重点，传感器 网络由于其自身资源受限的特点，对路由协议的设计要求很高。设计一个能在 各种场合都能使用的路由协议是非常困难的，一般传感器网络的路由协议的设 计都专门针对特定的应用环境。无线传感器网络应用场合单一，适合设计高效 的路由协议。但是，w s n 路由协议设计还是存在着大量的困难，这些问题不但 包括传统的i n t e m e t 路由协议中遇到的问题，还包括由w s n 自身特点引入的问 题。 ( 1 ) 全局最优路由策略 在i n t e m e t 路由协议中，当节点之间链路发生变化的时候，其设计思想是以 最快的速度将该变化通知网络中的其他节点，并重新调整和计算最短路径。链 路变化越快，由此引起的链路开销也就越大。w s n 中不适合应用这种方法，首 先，无线链路的不稳定，节点间链路发生变化的频率高，维护代价大。其次， w s n 中节点的能量有限，处理能力低，无线通信带宽窄，获得整个网络拓扑改 变的信息可能性不大。w s n 不适合采用传统的全局控制方式的路由算法来达到 全局优化，w s n 适合使用基于局部优化的分布式算法。这要求网络中的节点在 只是与区域内的节点进行信息交换的前提下，实现局部优化【1 9 1 。 ( 2 ) 路由算法的q o s 支持 w s n 中的q o s 支持问题是如何动态地配置网络资源使数据传输更有效， w s n 中q o s 路由的工作主要是包括两个方面：是找到满足q o s 需求的路由， 在网络拓扑结构和信道状态频繁变化的情况下维护该路由；二是要尽量提高网 络资源的利用率，在降低能耗和保证网络中q o s 之间找到最佳的平衡点。无线 信道的不稳定性、节点的移动性以及网络资源的有限性，这些都给q o s 路由协 议的设计带来了困难。 ( 3 ) 路由算法的安全性 w s n 通过无线信道来传送数据，无线通信的广播特性使其容易受到窃听、 假冒等攻击【1 9 1 。w s n 中数据通过多跳广播的方式进行传输，没有受到保护的消 9 第二章无线传感网络的综述 息容易遭受攻击，因此，路由算法的安全性也是一个需要考虑的因素。w s n 中 的安全要求和传统的网络一样，包括机密性、完整性、有效性等。w s n 中节点 的地位平等，不存在中心节点，并且网络中的节点是移动的，网络的拓扑结构 经常变化，这些都是传统网络的安全机制不能解决。 ( 4 ) 能源有效性策略 节能是w s n 中的一个重要的话题，w s n 路由协议需要考虑路由算法的能 量效率问题，基本思想是减少网络内的冗余数据，降低传输的次数。采用自适 应设计算法，根据网络状态，动态调整路由协议参数，以达到高效利用能量， 延长网络生命周期的目的。常用的优化能量的方法有数据重命名机制、数据融 合机制和网络自适应机制等。网络自适应机制是指根据节点自己的处理能力、 剩余能量以及网络拓扑等一些因素动态调整路由协议的参数以及节点的功能和 状态【7 1 。 2 3w s n 路由协议的特点和技术 2 3 1 路由协议的特点 因为无线传感器网络与传统网络不同，所以它们的路由协议也存在差异， 无线传感器网络路由协议的特点如下： ( 1 ) 能量消耗不均衡 由于传感器网络中节点的地位不是平等的，存在簇头节点和普通节点。普 通节点进行的工作不多，能量消耗相对较少。簇头节点与网络中的其他节点进 行信息交换，需要消耗大量的能量。所以为了延长网络的生命周期，我们要考 虑节点的能量消耗和能量均衡使用的问题。 ( 2 ) 局部拓扑 w s n 为了节省通信过程中使用的能量，通常采用多跳的方式进行通信。但 是节点的通信能力有限，节点不能保存大量的路由信息，不能进行复杂的路由 选择。节点只能采集到局数据，所以，简单高效的路由协议是我们研究无线传 感器网络的一个重点课题。 ( 3 ) 应用相关性 无线传感器网络的应用场合不同，所以不同的场合的通信方式也是不同的。 1 0 第二章无线传感网络的综述 没有一个路由协议适合所有的传感器的应用场合，所以，我们需要设计不同的 路由协议来满足不同场合的应用需求。 2 3 2 路由协议的技术 w s n 具有广阔的应用前景，但由于存在节点能量有限、存储空间小等问题， 它的大规模应用还存在许多问题，设计一个满足需要的高效的路由协议是目前 面临的一个重要的难题【l o l 。w s n 的基本特点可以概括为：能量受限、网络规模 大、节点移动性差、网络拓扑容易变化、数据冗余等问题。因此，设计一个w s n 路由协议面临的问题很多，目前主要集中表现在以下几个方面。 ( 1 ) 节点能量受限 能力受限包括两个方面的含义，首先是节点的能量储备低，其次是能量不 能被及时地补充。在传感器节点的工作过程中，大部分的能量都消耗在无线传 感器通信部件上。因此，研究能耗低的路由协议就是我们当前的一个重要的任 务。 ( 2 ) 可扩展性差 通常传感器网络包含成千上万个节点，网络规模越大，就意味着路由协议 收敛时间越长，网络的管理越不容易实现。网络拓扑改变的频率更快，网络拓 扑结构保持不变的时间就越短暂，路由的稳定性就越差。 ( 3 ) 拓扑变化性强 在w s n 中，网络拓扑变化主要是指因为无线通信冲突而产生拓扑不稳定、 节点的移动以及节点的失效等。当网络规模很大时，这些因素引起的拓扑结构 变化频繁。通常的i n t e r a c t 路由协议不能适用于这种快速的拓扑变化，这就需要 设计出既能适应快速变化的拓扑，又能不引入过多的开销的路由协议。 ( 4 ) 数据融合 在传统网络中，网络层主要提供点对点的报文转发功能以及实现端到端的 分组传输。而无线传感器网络的目标是获取有效的信息，实际上不需要实现端 到端的分组传输，通信只是一种辅助手段【1 2 1 。在网络运行过程中，通过不断的 加工处理数据，来降低网络开销、节省能量。在w s n 中，感知节点不需要将数 据传送给数据处理中心节点( s i n k ) ，只要有效数据最终汇集到s i n k 节点就可以。 因此，为了减少流量和能耗，转发节点经常将不同的入口报文融合成数目更少 第二章无线传感网络的综述 的出口报文转发给下一跳，这就是数据融合的工作【2 引。 ( 5 ) 数据流量分布不均匀 传感器网络是一个数据采集网络，绝大部分流量是由各个传感器节点流 向s i n k 节点，因此，流量分布不均匀。这种流量分布特点造成了的结果是越靠 近s i n k 节点，链路的流量越高，相应节点的负载也就越重，寿命越短。因此， 流量分布不均匀造成能耗分布不均匀，导致网络生命周期的缩短。 2 3 3 路由协议的设计目标 为了解决路由协议存在这些问题，在改进路由协议时，我们需要考虑以下 的这几个方面： ( 1 ) 能量有效性 由于w s n 中每个节点只是拥有固定的能量，所以路由协议设计需要考虑如 何节省能量，然后考虑服务质量( q o s ) 。 ( 2 ) 单一性。 与传统网络不同，传感器节点的运算和通信能力受到一定的限制。能量有 限的节点负责数据采集和路由器转发，这就要求不能使用传统网络的路由协议， 需要为它设计一种更简单、能量能充分利用的路由协议。 ( 3 ) 可扩展性 w s n 通常工作在恶劣的环境中，各种情况经常会使节点失效，或者有新节 点加入等。这些使w s n 网络拓扑结构发生变化，因此，需要路由协议具有可扩 展性，能够适应网络拓扑结构的动态变化。 ( 4 ) 鲁棒性 鲁棒性就是丕笪的健壮性，它是在异常和危险情况下系统生存的关 键。具体的在无线传感器网络中，能量消耗完毕或其它因素都会造成传感器 节点失效，这些不可靠因素要求w s n 路由机制具有一定的容错能力，具有很好 的鲁棒性。 2 4 路由协议的分类 在无线传感器网络中，路由协议的主要目标是降低节点能量消耗，延长网络 的生命周期。路由协议通常可为平面路由协议和层次路由协议，平面路由协议 1 2 第二章无线传感网络的综述 中包含许多的路由表的信息，这些信息占很大的存储空间。因此不适用于在大 规模的网络中使用，分层路由协议可以在一定程度上解决这个问题【1 3 1 。 2 4 1 平面路由协议 在平面路由协议中，传感器节点的地位是平等的，没有制约网络的关键点。 但还需要有控制信息维护路由，可扩充性差。首先介绍几种平面路由协议，常 见的是洪泛式路由协议( f l o o d i n g ) 、定向扩散路由协议( d i r e c t e dd i f f u s i o n ，d d ) 、 有序分配路由算法( s e q u e n t i a la s s i g n m e n tr o u t i n g ，s a r ) 、基于协商的路由算法 ( s e n s o rp r o t o c l o li n f o r m a t i o nn a g o t i a t i o n ，s p i n ) 等。 ( 1 ) 洪泛式路由协议 洪泛路由协议是一种平面路由协议，在传输数据的时候，不需要维护网络 的拓扑结构和使用路由算法瞄】。在泛红路由协议中，每个节点把接收到数据向 周围的邻居转发，以此类推，直到将数据传输到目标节点为止。 这种路由协议实现简单，不需要知道网络拓结构和路由算法，适用于要求 低的场合。缺点是一个节点可能得到多个节点的数据副本，出现部分重叠 ( o v e r l a p ) 现象。这种路由协议没有考虑节点的能量问题，不能形成自适应的 路由选择算法。因此，洪泛路由协议只适用于结构比较简单网络。 ( 2 ) 基于协商的路由算法s p i n s p i n 路由协议是比较早提出的路由协议，在一定程度上对泛洪路由协议进 行了改进。它是一种是数据为中心的自适应路由协议，考虑到了w s n 中的数据 冗余问题，节点之间通过协商( n e g o t i a t i o n ) 的方式减少网络中传输的数据。节 点只是传输其他节点没有的数据，减少了节点问的数据通信，有效地减少能量 消耗。 在s p i n 路由协议中，引进了元数据的概念，元数据是描述数据的原始状态 的。而且元数据所需要的数据位比原始感知数据的要小，采用这种变相的数据 压缩策略可以进一步减少通信过程中的能量消耗。 s p i n 协议通过协商机制很好的解决了内爆的问题，对于重叠问题也进行了 一定的处理。特别是s p i n 协议支持数据融合，s p i n2 进步引入了能量管理的 概念，一定程度上优化了网络负载，延长了网络的生存时间。 ( 3 ) 有序分配路由协议s a r 在选择路径的时候，有序分配路由算法考虑到了功耗、q o s 和分组优先权 第二章无线传感网络的综述 等要求。采用局部路径恢复和多径路径备份策略，避免节点或链路失败时进行 路由重新计算所需要的计算开销。为了每个节点与s i n k 节点之间生成多条路径， 需要维护多个树结构，每个树落在以s i n k 节点为有效传输半径内的节点为根向外 生长，枝干的选择需要满足定的q o s 要求并要有一定的能量储备。这一处理使 得大多数的传感器节点可能同时属于多个树，可以任意地选择其中的一个将采 集数据回传到s i n k 节点。 ( 4 ) 定向扩散路由协议d d 定向扩散路由协议是一种基于查询的路由方法，s i n k 节点周期性地广播一 种称为“兴趣 的数据包，告诉网络中的节点它需要收集什么样的信息。是由 兴趣扩散、梯度建立以及路径加强三个阶段组成。 o oo oo ooo ooo 川 ooo 图2 3 定向扩散路由机制 在兴趣扩散阶段，s i n k 节点向邻居节点广播兴趣消息。以此类推，逐步遍 历整个网络中的节点。在梯度建立阶段，当节点采集到与兴趣匹配的数据时， 把数据发送到梯度上的邻居节点。由于可能从多个邻居节点收到兴趣消息，源 节点向多个邻居节点发送数据，汇聚节点可能收到从多个路径发来的相同中间 节点收到转发的数据后。首先查询兴趣列表的表项，如果不匹配，就丢弃数据。 若存在相应的兴趣表项，则检查最近是否转发过该数据，若转发过就丢弃该数 据，否则转发该数据。在路径加强阶段，通过正向加速机制来建立优化路径， 根据网络拓扑结构的变化修改数据转发的梯度关系。 该算法引入了网络梯度的概念，可以找到从源节点到目标点的最优路径， 并且使用了本地优化算法，能够很好的满足w s n 对节能、鲁棒性以及可扩展性 的要求。但是由于采用了按需查询驱动的数据模型，不适用于环境监测等要求 1 4 第二章无线传感网络的综述 连续数据的系统，而且选择与查询相匹配的数据会使传感器节点消耗更多的能 量。 2 4 2 层次路由协议 层次结构的路由协议重点是考虑路由算法的可扩展性，其主要特征是将传 感器节点按照特定规则分为多个集群，通过该集群的头结点c h ( c l u s t e rh e a d e r ) 汇集集群内感知数据或者转发其他集群头结点的数据。具体分为两种：单层路 由协议和多层路由协议，其中单层路由协议是指对传感器节点进行一次集群划 分，前提是每个传感器节点能直接与s i n k 节点进行通信。多层路由协议是指对 传感器节点进行多次划分，即集群节点头结点将再次进行划分。 典型的层次路由协议有l e a c h 低能量自适应分簇路由协议( l o w - e n e r g y a d a p t i v ec l u s t e r i n gh i e r r a r c h y ) 、传感器信息系统中高能效采集协议p e g a s i s ( p o w e r - e f f i c i e n tg a t h e r i n gi ns e n s o rn e t w o r kp r o t o c 0 1 ) 、阀值敏感的高效传感器 网络协议t e e n ( t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n ts e n s o rn e t w o r kp r o t o c 0 1 ) 。 ( 1 ) 单层路由协议l e a c h 路由协议 l e a c h 是最早提出的分层路由协议算法，它的思路是考虑到一簇内节点的 能量的消耗问题，目的是为了延长节点的工作时间，并且实现节点的能量平衡。 1 - 基本思想 它是m i t 的人为w s n 设计的，是第一个基于多簇结构的分层路由协议。 基本思想是网络周期性地随机选择选择簇头节点，其他的非簇头节点以就近原 则加入相应的簇头，形成虚拟簇l l 6 1 。 2 实现过程 l e a c h 路由算法的实现过程分为簇的建立阶段和数据传输两部分l e a c h 协 议中引进了“轮 ( r o u n d ) 的概念，它的操作是以轮为单位的，每轮包含簇的建 立和数据传输两个阶段。在簇的建立阶段，通过随机算法产生簇头，相邻节点 动态地形成簇。在数据传输阶段，簇内节点把数据发送给簇头，簇头进行数据 融合并把结果发送给s i n k 节点。簇头需要完成的工作量很大，比如数据融合和 节点进行通信等工作，能量消耗很大。为了节省能量，一般情况下，数据传输 阶段的时间长一点。 l e a c h 路由算法选举簇头的过程：在这个阶段，传感器节点随机的产生o 到l 之间的数，如果这个数小于闭值t ( n ) ，那么就成为是簇头。在每轮中，如果 第二章无线传感网络的综述 某个节点曾经当选过簇头，则t ( n ) 为0 。t ( n ) 的表达式： 王j t ( 1 3 ) = 生一刀g 卜尸木p m o d ( 1 p ) 】 t ( n ) = o 其他 g 是最近1 p 轮循环中还没有选选过簇头的节点集合，p 是簇头占所有节点 的百分比，r 是当前的轮数，r o d 是求余数运算。从t ( n ) 可以看出，当被选为簇 头的节点在接下来的1 p 轮循环中将不能成为簇头时，剩余节点随着t ( n ) 的增大， 节点产生小于t ( n ) 的随机数的概率也增大。 ( 2 ) 二层路由协议门限敏感的节