（通信与信息系统专业论文）无线传感器网络leach路由协议的研究(1).pdf

摘要 无线传感器网络( w s n ) 集成了传感器、嵌入式计算、分布式信息处理和 无线通信四大技术，是一种全新的信息获取、处理和传输技术。它可应用于军事、 环境监测、医疗救护、商业等领域，因而具有十分广阔的应用前景，引起了学术 界和工业界的高度重视。 本文重点研究w s n 路由协议l e a c h ，无线传感器网络节点数量庞大、单 个节点资源极其有限，其路由协议设计的首要目标是提高能量有效性，延长网络 生命周期。本文总结了w s n 的发展历程、概念、结构、特点，分析了w s n 的 关键性技术问题及网络协议；研究了w s n 的网络协议体系和路由协议的分类， 分析和比较了目前国外学者提出的几种有代表性的路由协议及其性能和优缺点： 有针对性的选择了动态聚簇结构的路由协议l e a c h 作为研究重点，分析了其存 在的问题，并针对这些问题在原有算法的基础上提出了改进方案，其中借鉴了 s p i n 、d d 等协议的优秀思想，概括为以下三点：改进了闽值t ( 曲的计算方法， 并用此初步选择簇首，然后进行p s o 优化；簇间采取多跳通信方式，簇首节点 只需将数据发送给邻近的节点而不是相距很远的s i n k 节点，可以减少单个节点 的能耗，实现网络负载平衡：采用了“类型码”的概念，在簇成员节点向簇首发送 数据之前进行了数据融合，然后在簇首进行最优加权法的多传感器数据融合。 肘上述三点改进，本文采用o p n e t 网络仿真工具分别单独进行了仿真和分 析。最后进行了l e a c h 路由协议改进算法整体的仿真，仿真结果表明，改进后 的路由算法比原l e a c h 路由算法：系统整体能耗降低，网络生命周期提高1 0 以上，信道占用率降低并且网络扩展性能更好。 关键词：w s n ，路由协议，l e a c h ，多跳通信，能量有效性，动态聚簇结 构 a b s t r a c t w f l e l e s ss e n s o rn e t w o r k ，w h i c hi sm a d eb yt h ec o n v e r g e n c eo f s e n s o r , e m b e d d e dc o m p u t i n g d i s t r i b u t e di n f o r m a t i o np r o c e s s i n ga n dw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e s ，i san e wi n f o r m a t i o n a c q u i s i t i o n ，p r o c e s s i n ga n dt r a n s m i s s i o nt e c h n o l o g i e s i tc a r lb eu s e di nm i l i t a r y , e n v i r o n m e n t a l m o n i t o r i n g ，m e d i c a la n dc o m m e r c i a l ，e t c i th a saw i d ea p p l i c a t i o nf u t u r e b o t ha c a d e m i aa n d i n d u s t r i e sa r ev e r yi n t e r e s t e di ni t t h es t u d yo fl e a c hr o u t i n gp r o t o c o lf o rw s ni st h em a i np a r to ft h i sd i s s e r t a t i o n t h e n u m b e r so fs e n s o rn o d ei nw s na r en u m e r o u sa n ds i n g l en o d ei se x t r a o r d i n a r i l yl i m i t e di n r e s o u r c et h ea l l i m p o r t a n ta i mo fd e s i g n i n gr o u t i n gp r o t o c o lo fw s ni st or e d u c et h eo v e r a l l e n e r g yd i s s i p a t e di nt h en e t w o r ka n dt om a x i m i z et h en e t w o r kl i f e t i m e w es u m m e du pt h e d e v e l o p m e n th i s t o r y , c o n c e p ls t r u c t u r e ，c h a r a c t e r i s t i c so fw s na n da n a l y z e dt h ek e yt e c h n i c a l i s s u e sa n dn e t w o r kp r o t o c o l so fw s n ；w es t u d i e dt h en e t w o r kp r o t o c o l so fw s na n dr o u t i n g p r o t o c o l so nt h ec l a s s i f i c a t i o ns y s t e m w ea n a l y z e da n dc o m p a r e ds o m er o u t i n gp r o t o c o l sf r o m t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e st h a tp r o p o s e db yo v e r s e ar e s e a r c h e r ；w ec h o o s el e a c h r o u t i n gp r o t o c o l a st h er e s e a r c ht a r g e t w ea n a l y z e di t si n s u f f i c i e n t b a s e do nt h eo r i g i n a l a l g o f i t b z n ，w ep u tf o r w a r dt h e i ri m p r o v e m e n tp r o j e c t s ，w h i c ha s s i m i l a t e de x c e l l e n c ei d e aa m o n g s p i n ，d da n do t h e rp r o t o c o l s t h ei m p r o v e m e n tc a nb el i s t e da sf o l l o w i n g ：w es e l e c ti n i t i a l c l u s t e rh e a d e ra c c o r d i n gt ot h ei m p r o v e dt ( n ) ，t h e no p t i m i z e dc l u s t e rh e a d e r sa d o p t i n gp s o a r i t h m e t i c t h i sm e t h o dc o n s i d e r e dn o to n l yt h ee n e r g yo fc l u s t e rh e a d e r sb u tm s ot h es t a t e i n f o r m a t i o no f t h ec l u s t e rm e m b e r s a m o n gc l u s t e r st a k e sm u l t i h o pc o m m u n i c a t i o n st h ec l u s t e r h e a d e r ss e n dd a t ao n l yt ot h ev i c i n i t yn o d ea n dn o tt ot h es i n kn o d ev e r yf a ra w a yf r o mt h e m t h i s c a nr e d u c et h ee n e r g yc o n s u m p t i o no fi n d i v i d u a ln o d e sa n da c h i e v et h en e t w o r kl o a db a l a n c i n g w ea d o p t e dt h e t y p e s ”i nt h ec o n c e p tt od a t af u s i o ni nt h ec l u s t e rm e m b e r sb e f o r es e n d i n gd a t at o c l u s t e rh e a d e r s ，t h e ni nt h ec l u s t e rh e a d e r sa d o p t e do p t i m a lw e i g h tm e t h o df o rm u l t i - s e n s o r sd a t a f u s i o n u s i n go p n e ts i m u l a t i o nt o o l st os i m u l a t ea n da n a l y z es e p a r a t e l yt h et h r e ei m p r o v e m e n t s f i n a l l y , w es i m u l a t e dt h eo v e r a l la l g o r i t h m ，t h es i m u l a t i o nr e s u l t si n d i c a t et h a ti m p r o v e dr o u t i n g a l g o r i t h mc o m p a r e dw i t hl e a c h ：t h eo v e r a l ll o wc o n s u m p t i o n ，n e t w o r kl i f ec y c l ei n c r e a s e db y m o r et h a n1 0 ，c h a n n e lo c c u p a n c yr a t er e d u c t i o na n db e t t e rn e t w o r ks c a l a b i l i t y k e y w o r d s ：w s n ，r o u t i n gp r o t o c o l ，l e a c h ，m u l t i h o pc o m m u n i c a t i o n s ，e n e r g ye f f i c i e n c y , d y n a m i cc l u s t e r i n gs t r u c t u r e 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：盟叁垫忍回年弓月五日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘 版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用 影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容 相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部 分内容的公布( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ：融叁垫2 唧年弓月2 五日 河海大学工学硕 学位论空第一章绪论 1 1 课题背景 第一章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，简称w s n ) 是新兴的下一代传感 器网络，最早的代表性论述出现在1 9 9 9 年，题为“传感器走向无线时代”。随后 在美国的移动计算和网络国际会议上，提出了w s n 下一个世纪面l 临的发展机遇 f q 2 。2 0 0 3 年，美国技术评论杂志【3 1 在论述未来新兴十大技术时，w s n 名列 第一；同年，美国b u s i n e s sw e e k 预测的未来四大新技术：效用计算、传感器网 络、塑料电子学和仿生人体器官，w s n 也列入其中。2 0 0 4 年( i e e es p e c t r u m ) ) 杂志发表一期专集传感器的国度，论述了w s n 的发展和可能的广泛应用。 可以预计，w s n 的发展和广泛应用，将对人们的社会生活和产业变革带来极大 的影响和产生巨大的推动1 4 】。有专家预计，w s n 的广泛应用是一种必然趋势， 它的出现将会给人类社会带来极大的变革。传感器网络的发展主要经历了4 代： 第一代：上世纪7 0 年代，就出现了具有简单模拟信号传输功能的传统传 感器所组成的点对点输出的测控系统网络。该网络具有简单信息获取能力，只是 初步实现了信息的单向传递，其缺点是布线复杂、抗干扰性差。 第二代：随着相关学科的不断发展和进步，传感器网络具有了获取多种信 息的综合处理能力，并通过采用串并接口与传感控制器的相联，组成了有信息 综合和处理能力的传感器网络。 第三代：2 0 世纪9 0 年代后期，出现了基于现场总线技术的智能传感器网 络。现场总线是连接智能化现场设备和控制室的全数字、开放式的双向通信网络 智能传感器的通信技术进入局域网阶段，其局部测控网络通过网关和路由器可以 实现与i n t e m e t f i n t r a n e t 连接。 第四代：大量多功能传感器被运用，并采用无线通信机制，因此也称为 w s n ，正处于研究和开发阶段。 w s n 是一种无基础设施的网络，由一定数目的传感器节点构成，它综合了 传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能协作地 实时监测、感知和采集节点部署区域的各种环境或监测对象的信息( 如光强、温 度、湿度、噪音和有害气体浓度等物理现象) ，并对这些数据进行处理，获得详 尽而准确的信息，通过无线网络最终发送给观察者。在环境监测、医疗护理、抢 险救灾、智能家居、工业生产控制以及商业等领域具有广阔的应用前景【5 j 【6 j 【7 1 。 w s n 与传统固定网络有很大的不同。在其研究初期，人们认为成熟的i n t e m e t 河海大学工学硕j 学位论文无线传感器网络l e a c h 路由坍议的研究 技术加上a dh o e 路由机制对w s n 的设计是足够充分的，但是深入地研究表明， w s n 有不同于传统无线网络和a dh o c 网络的特点，前者以数据为中心，而后两 者以传输数据为目的。与w s n 最为相似的是移动自组织网络( m o b i l ea dh o c n e t w o r k s ，简称m a n e t ) ，共同点是无线自组织多跳网络，邻居发现和路由发现 都是自动的，不同利5 】1 6 】川【s 1 ：w s n 节点不移动或很少移动，节点可达上千，远 大于m a n e t 的几十个节点，并且m a n e t 节点移动性强、是移动的对等体之间 的数据或语音通信；w s n 的数据包较小，因而数据传输开销更大，并且节点的 计算、存储、通信能力更有限；传感器节点通信高能耗，数据计算低能耗，这种 差异在m a n e t 中并不重要；w s n 一般独立成网，主要用于监测功能，是以数据 为中心的网络，m a n e t 则能为分布式应用提供互联、计算能力：w s n 网络流量 具有多对一和一对多的特点，其节点合作完成监测任务，与应用高度相关，数据 相关性较大，节点一般没有统一编址( 在某些应用中可对节点编址) ，节点标识( 如 地址等) 的作用并不是非常重要，因为应用程序不关心单节点上的信息，中间节 点上与具体应用相关的数据处理、融合和缓存却很有必要。 w s n 的上述特点使得一些为众多传统固定网络与m a n e t 设计的路由协议 和算法不适合w s n 的特点和应用要求【5 1 。在密集型的w s n 中，相邻节点间的距离 较短，低功耗的多跳通信模式可以节省能源，同时增加了通信的隐蔽性，也避免 了长距离的无线通信易受外界噪声干扰的影响。w s n 路由设计的重要目标是降 低节点能量损耗，提高网络生命周期；w s n 中这些独特的要求和制约因素为其 研究提出了新的技术问题。其中，路由协议的研究与设计近年来受到国内外研究 学者的重视，研究人员正在努力研究适合w s n 的路由协议。 本课题主要研究w s n 网络层的核心技7 r 一路由技术。w s n 应达到的要求 使它的路由协议设计面临着节能和提高扩展性两个关键性问题。现有的路由协议 都不能很好地解决这两个问题，因此有必要针对w s n 的特点和需求研究专门的 协议或改进现有的协议。综上所述，w s n 路由技术的研究很有挑战性，是一个 开放性的研究课题。 1 2 国内外技术研究现状 w s n 是目前国内外研究的热点【9 】。美国自然科学基金委员会2 0 0 3 年制定了 w s n 研究计划，投资3 4 0 0 万美元，支持相关基础理论的研究，美国国防部和各 军事部门也对w s n 给予了高度重视，把它作为一个重要研究领域，设立了一系 列的军事传感器网络研究项目。欧洲也在德国首都柏林举行了第一届“无线传感 网络论坛”，有一百二十名微电子、机械电子和信息传输方面的专家出席论坛。 信息工业界巨头英特尔公司、微软公司等也开始了w s n 方面的工作，纷纷设 2 河海大学t 学硕士学位论文 第一章绪论 立或启动相应的行动计划；美国康奈尔大学、麻省理工学院、南加州大学等先后 提出了几类新的路由协议，包括s p i n 、d i r e c t e dd i f f u s i o n 、l e a c h 、t e e n & a p t e e r n 、p e g a s i s 等。 我国在w s n 方面的研究工作刚刚开始，清华大学、电子科技大学、哈尔滨 工业大学等单位已经进行了该领域的研究工作，但目前主要集中在介绍国外的研 究进展，提出新的研究问题，尚未见有新的协议提出。由于w s n 是一门新兴技术， i e e e 尚未成立w s n 的标准制定小组，美国也是在2 0 0 0 年才开始出现一些有关 w s n 研究结果的报道，所以国内与国际水平的差距并不大，电子科技大学计算 机学院正在开展w s n 路由协议的设计和仿真工作，力争在5 年内达到国际水平。 但w s n 尚未达到完全实用阶段，大部分工作仍处在仿真和实验阶段，仿真规模 在数百至数千个节点，实验规模在几十个节点左右。 1 3 课题研究的目的和意义 如| i 所述，w s n 有着广泛而有价值的应用领域，比如水工建筑物安全监测， 大型工程建筑物的运行安全，结合现代监测理论及w s n 技术，布置节点实现无 人值守，为设计施工及时反馈信息，对减轻观测的劳动强度，提高安全监控的技 术水平，具有重大的社会经济效益和应用价值。而在个人通信和接入网等方面的 应用则具有良好的商业前景。因此，对w s n 网络技术的研究既有重要的社会意 义又蕴含着潜在的经济价值。因此它已经引起了世界工业界和学术界的极大关 注，开展这项对人类未来生活影响深远的前沿科技的研究，对整个国家的社会、 经济将有重大的战略意义。而从网络层模型的角度分析，每一层都有需要结合 w s n 的特点进行细致研究的问题，已有的研究主要集中在网络层和链路层。 网络数据传输离不开路由协议，路由协议是其组网的基础。路由技术是w s n 通信层的核心技术。路由选择问题是w s n 网络构建时所要着重考虑的一个问题， 从路由的角度来看，w s n 有其自身的特点，使它既不同于传统网络，又不同于 无线自组网a dh o c 网络。传统的无线a dh o c 网络路由协议不适合用于w s n ，我们 必须设计全新的、适合于w s n 特点的路由协议。 路由协议作为影响网络性能的一个重要因素，是确保w s n 网络正常运行的 关键。虽然已提出了很多的协议，但是到底那一种是最合适的还没有一个定论。 因此研究这些路由协议，比较分析哪一种路由协议是相对合适的显得尤为重要， 也是此论文的意义所在。本课题以提高w s n 网络的性能为目的，对其中的路由 问题进行研究，综合大量路由协议和算法文献的基础上，对现有的w s n 路由协 议进行归纳、对比、分析，从中得出了值得借鉴的优秀思想。有针对性的选择了 动态聚簇结构的路由协议l e a c h 作为研究重点，分析了其存在的问题，并针对 河海人学工学硕士学位论文 无线传感器湖络l e a c h 路由协议的研究 这些问题在原有算法的基础上提出了改进方案。总之，对该领域进行深入而广泛 的研究将为w s n 的应用提供重要的科学依据。 1 4 论文的主要工作 本文主要工作归纳如下： 1 总结了无线传感器网络的发展历程、概念、结构、特点及应用，分析了 w s n 存在的关键性问题及通信协议。 2 深入研究了w s n 的网络协议体系和路由协议，分析和比较了目前国外学 者提出的几种有代表性的针对w s n 的路由协议及它们的优缺点。 3 有针对性的选择了经典的基于聚类的低功耗自适应路由算法l e a c h 作为 研究重点，分析了l e a c h 协议的信道模型、物理基础、设计思想、工作过程及 存在的问题，并在原有算法和借鉴s p i n 、d d 等协议的优秀思想，提出了三方 面的改进方案，最后给出了相应的仿真结果和分析。 4 采用o p n e t 网络仿真工具对l e a c h 算法和改进后的算法进行了仿真实 现，并对仿真结果进行了比较分析，证实改进后的算法在网络生命周期、系统整 体能耗、网络扩展性能、信道占用率上比l e a c h 算法均有了很大的提高。 1 5 论文结构安排 第一章，绪论，首先介绍了课题的研究背景及国内外技术研究现状，然后阐 述了本课题的研究目的、意义以及本文的主要工作。 第二章，详细介绍了无线传感器的概念、体系结构、节点结构、协议栈的分 层模型及应用，并分析了w s n 存在的关键性技术问题及网络通信协议。 第三章，集中在本课题的路由协议这一关键技术上，阐述了w s n 路由协议 的分类，分析和比较了目前国外学者提出的几种有代表性的针对w s n 的路由协 议及它们的优缺点。从中找出了对本课题具有重要意义的相关算法和思路，并深 入分析了经典的基于聚类的低功耗自适应路由算法l e a c h 的设计思想、工作过 程和存在的问题。 第四章，对l e a c h 路由算法的改进机制研究，具体分析了三点改进算法并 仿真分析了每一点算法改进对网络性能的影响。 第五章，是整个系统仿真与性能测试。 第六章，总结与展望，全面总结本文在课题中所做的工作，展望未来的研究 工作。 4 河海大学工学硕上学位论文 第二章w s n 综述 2 1w s n 的概念 第二章w s n 综述 w s n 是由一组无线传感器以自组织方式构成的无线网络，其目的是协作地 感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发送给观察者。可 以看出，无线传感器、感知对象和观察者是w s n 的三个基本要素；无线是传感 器之间、传感器与观察者之间的通信方式，用于在传感器与观察者之问建立通信 路径；协作地感知、采集、处理、发布感知信息是w s n 的基本功能；w s n 中 的部分或全部节点可以移动，在本文中只考虑节点静止的情况，节点间以自组织 方式进行通信，每个节点都可以充当路由器的角色，并且每个节点都具备动态搜 索、定位和恢复连接的能力。 2 2w s n 的结构 2 2 1 通信体系结构 节点通过飞机稚撒、人工布置等方式，大量部署在感知对象内部或者附近 o o 。这些节点自组织地构成网络，以协作的方式感知、采集和处理网络覆盖区 域中任意地点任意时间的特定的信息，通过嵌入式系统对信息进行网内计算和融 合，并通过随机自组织无线通信网络以多跳中继方式将监测数据传至u s i n k 节点， 最终借助长距离或临时建立的s i n k 链路将整个区域内的数据传送到远程中心进 行集中处理。典型的w s n 的体系结构包括分布式传感器节点、s i n k 节点、互联网 和用户界面等巴如图2 1 所示。绝大多数节点有很小的发射范围，而s i n k 节点具 有较多的能量，发射能力较强，能把网络采集到的数据传送给远程控制节点。 图2 1 典型的w s n 体系结构 常见的w s n 的3 种网络拓扑结构：层次、网状、链式结构。 ( 1 ) 基于簇( c l u s t e r ) 的层次结构如图2 - 2 ，每个轮换，按某种算法选择簇里 河海大学工学硕士学位论文 无线传感器州络l e a c h 路由协议的研究 面的节点作为簇首，它就是分布式处理的簇中心，簇中其它节点把数掘传送簇首， 由簇首完成信息的处理和融合，然后由簇首以多跳通信方式或者直接方式传送给 r i n k 节点。 ：盘。2 o ”“ o 菁运节点s i n k 图2 2w s n 的层次结构 图2 3w s n 的网状结构 ( 2 ) 基于网( m e s h ) 的平面结构，在这种结构下w s n 连成一张网如图2 3 ，网 络非常健壮，网络伸缩性好；在个别链路和传感器节点失效时，不会引起网络分 裂。可以同时通过多条信源信宿问路由传输数据，传输可靠性非常高，只要对数 据进行一定的前向纠错编码，基本不需要采用基于端到端应答的重传通信机制。 ( 3 ) 基于链( c h a i n ) 的线结构，在这种结构下传感器节点被串联在一条或多条 链上，链尾与s i n k 节点相连，如图2 - 4 。 图2 _ 4w s n 的链式结构 图2 5 无线传感器节点结构 2 2 2 节点结构 w s n 节点作为一种微型化的嵌入式系统，构成了w s n 的基础层支撑平台。 它的基本组成包括如下几个单元【1 1 】：传感单元( 由传感器和模数转换功能模块 组成) 、处理单元( 由嵌入式系统构成，包括c p u 、存储器、嵌入式操作系统等) 、 通信单元( 由无线通信模块组成) 、以及电源部分，如图2 5 所示。此外，可以 选择的其它功能单元包括：定位系统、移动系统以及电源自供电系统等。 2 2 3 分层结构 w s n 是以节点硬件设计为底层平台、信道接入和网络路由技术为支持、数 6 河海人学工学硕 学位论文 第一二章w s n 综述 据融合与应用为实现目的、具备自组织和多跳特性的无线网络。针对w s n 的动 态拓扑性和有限资源环境等特征，在参考o s i 七层模型和t c p i p 协议簇的基础 上，采取如图2 6 所示的分层结构，自底向上分为：物理层、数据链路层、网络 层和高层的应用。文献【6 1 还建议增加传输层，以确保与其他外部网络的连接。这 是目前w s n 普遍应用的协议栈，是一种约简网络次要功能、具有信息融合功能的 传感器专用的五层体系结构。该分层结构的设计是以节约能耗为前提，并以高冗 余度作为设计策略以保证不可靠环境下的有效特征功能。该体系结构能够支持感 知并适应动态的网络拓扑改变，并在此基础上实现路由协议的自适应性和可扩展 性。 网络层有两个相互关联的问题【1 2 1 ：首先，各节点采用自组织的方式构建网 络并确定网络拓扑结构；其次，在给定的网络拓扑结构下，如何进行路由。 由于w s n 属于多跳通信网络，所以每个传感器节点都可以充当路由器，中 继转发其它节点的数据报文。网络层协议是通信网络协议的核心，它的主要目标 是建立并维护多跳通信中使用的路由表，并根据本地地址信息和路由信息决定是 否转发收到的数据报，同时向上层( 传感与执行器平台中实现的应用层) 提供一个 简单易用的软件接口。实现传感器与传感器、传感器与观察者之间的通信，同时 支持多传感器器协作完成大型感知任务。 操作系统 数据融合 网络路由 无线网络 眦协议 无线终端 硬件平台 传痘器 图2 - 6 w s n 的分层结构 2 3w s n 的关键性技术问题 w s n 涉及的技术很多，全球的研究人员也展开了大量的研究，下面就分析目 前w s n 中的一些关键性技术问题。 1 功耗问题 作为一种微电子设备，无线传感器节点只能配置电池，电池电量一般小于 o 5 a h l l3 1 ，电压为1 2 v - 3 3 v 1 3 】【1 4 1 。在一些具体应用中，电池更换是不现实的。 7 河海大学工学硕上学位论文无线传感器网络l e a c h 路由协议的研究 所以，节点生命期严重依赖于电池供电的持续时间。在w s n 中，每个节点都起 着数据采集器和路由器的双重作用。一些节点的故障会引起拓扑的明显变化，可 能要求重建路由或重组织网络。所以，能量保护和能量管理至关重要。 传感节点的主要功能是感知、处理和数掘传输，其能耗也主要分布在这三个 方面。感知能耗与具体应用环境中携带的不同传感单元有关。通信能耗在节点能 耗中比例最大，需要考虑启动功耗、接收功耗和发送功耗，无线电收发器能耗公 式如下【1 5 】； p c = n t p 1 1 ( t o n + t 砒卜p o u t t o n + n r p r ( r o f f 4 r s t ) 】 式2 1 其中，p c 为无线通信功耗；p t 和p r 分别为无线发送和接收器件的功耗；p o u t 为无线发送器的输出功率；1 k 、r 。1 1 分别为每个单位时间内无线发送器和无线接 收器的打开的时间；t 鞋、r s t 分别为发送和接收的启动时间；n t 、n r 为单位时 间内接收和发送的次数，依赖于任务和采用的媒介访问控制( m a c ) 策略；1 巯 也可写成l r ，l 为数据包大小，r 为数据传输速率，图2 7 为时序关系图。数 据处理功耗比通信功耗要小得多，例如：假定瑞利衰落且能量与距离的4 次方成 正比损耗，实验表明【1 6 1 ，无线传输l k 比特的数据1 0 0 米的能量可以让1 0 0 m i p s w 的处理器处理3 0 0 万条指令。因此尽可能地进行本地数据处理而减少数据的无线 传输是降低w s n 能耗的有效办法之一。 r 1 1 二i 二二：r 一& 叫 e 竺= 土f ! ! 二二；! ! ! i 竺二二习 图2 7 功耗与时间对应关系图 针对数据采集、接收、发送和计算这四者的能耗问题，c u r ts c h u r g c r s 1 刀等 人进行了实验。实验结果【l ? 1 【1 s 1 表明，发送数据( t x ) 的能耗略大于接收数据( 磁两， 二者远大于数据处理( 计算) 和数据采集的能耗，如图2 8 所示。 图2 8 无线传感器节点通信子系统能耗情况 2 节能策略 由于无线通信是w s n 能耗的主要部分，因此对无线收发系统的能耗管理非 常重要，可以采取以下措旌减少通信模块的能量损耗。 ( 1 ) 减少通信流量 河海大学t 学硕十学位论文第二章w s n 综述 减少通信流量的方法有：乱本地计算和数据融合b 减少冲突c 增加错误检测 和校正机制d 减少控制包的开销和包头长度。 ( 2 ) 增加睡眠时间 无线通信模块有发送、接收、空闲和睡眠4 种状态。无线通信模块在空闲状 态一直监听无线信道的使用情况，检查是否有数据发送给自己，而在睡眠状态则 关闭通信模块。从图2 7 中可以看到：无线通信模块在发送状态的能量消耗最大， 而在空闲状态和接收状态的能量消耗接近，略少于发送状态的能量消耗，在睡眠 状态的能量消耗最少。因此不需要通信时，尽快进入睡眠状态是w s n 协议设计 重点考虑的问题。 ( 3 ) 采用多跳短距离无线通信方式 无线通信消耗能量e 与通信距离d 的关系为e = k d n 。其中，参数n 满足关系 2 如 。 t b t i 。 ( a ) 运用贪婪算法构成的链( b ) 数据传输到基站的途径 图3 5p e g a s i s 协议工作流程 虽然性能获得了提升，然而由于传输是异步的，造成报文传输时f b j 过长。 h i e r a r c h i c a l p e g a s i s 3 3 1 进行了进一步改进如图3 - 6 所示，在不相邻的节点间， 算法允许并发传输。 b s t a r i o n c 3 _ 一c 7 c 1 - c 3c 5 - - i - c 7 o o - - i - c l c 2 _ c 3c + c 5c 6 图3 - 6h i e r a r c h i c a l p e g a s i s 协议工作流程 相比l e a c h 算法，这两种算法消除了集群分组的开销，然而在路由选择的 时候，都没有考虑下一跳节点的能量情况，而且也不适合对于较高负载的网络情 况；对于节点数量较多的情况下，其数据传输的延时非常明显。 2 分层模式 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 c l l s o rn e t w o r kp r o t o c 0 1 ) 算法i 圳在 l e a c h 算法的基础上，针对检测突发事件的场景，对传感器节点进行两次集群 分组。算法对第一次集群分组选出的簇首进行了第二次集群分组，并引入绝对门 限和相对门限来检测突发事件。前者是指被检测事件属性符合查询要求，可以激 活传感器节点的门限值；后者是指事件属性超过绝对门限值后，其变化又超过相 对门限，可以使传感器节点产生数据传输的门限值。该算法对于基于周期性事件 报告模型的应用不适用。 3 2 3 基于位置信息的路由协议 g e a r ( g e o g r a p h i ca n de n e r g ya w a r er o u t i n g ) 是充分考虑了能源有效性的基 于位置的路由协议，该算法【3 5 l 在d i r e c t e dd i f f u s i o n 算法的基础上做了一系列改 进，该协议并不采用向整个网络广播兴趣，而是利用位置信息，向某一个特定的 区域进行兴趣的广播，然后利用位置信息( 尽可能地选择最短路径) 和节点能量剩 余的情况，将数据包发送到s i n k 节点，该方法可以极大地节省能源。考虑到传感 器节点的位置信息而将i n t e r e s t 报文添加地址信息字段，并据其将i n t e r e s t 往特定方 向传输以替代原泛洪方式，从而显著节省能量消耗。 1 8 河海大学工学硕 学位论文第三章w s n 路由协议算法分析 g e a r 也采用了查询驱动数据传送模式，它传送数据分组到目标域中所有的 节点的过程包括两个阶段：目标域数据传送和域内数据传送如图3 7 。g e a r 将网 络中扩散的信息局限到适当的位置区域中而不是整个网络，减少了中间节点的数 量，从而降低了路由建立和数据传送的能源开销，从而更有效的提高了网络的生 命周期。缺点是依赖节点的g p s 定位信息，成本较高。 o o 1 o o 尸to i o 、奴l o o 、 一1 o 图3 7g e a r 中递归的目标域数据传送 3 3 协议的性能比较 洪泛式路由协议直接将接收到消息的结点以广播形式转发数据包给所有的 邻结点，f l o o d i n g 协议是最古老而经典的洪泛式路由协议。如何有效解决其消 息的“内爆”和“重叠”以及“资源盲点”的问题是其研究目标 层次式路由协议通过将传感器节点分成不同的子网来高效转发传感数据， l e a c h 是第一个在w s n 中提出的层次式路由协议。 以数据为中心的路由协议中的数据传送基于数据查询并依赖数据命名， d i r e c t e dd i f f u s i o n 是以数据为中心的路由协议发展过程的里程碑。高效标准的数 据命名机制和查询信息的高效传送是未来研究的方向。 基于位置信息的路由协议利用结点的位置信息来进行数据发送，g e a r 是充 分考虑了能源有效性的基于位置的路由协议。如何智能的利用节点的位置信息来 达到能源有效性的目的是研究的考虑要点。 l e a c h ，d i r e c t e dd i f f u s i o n 和g e a r 协议克服了f l o o d i n g 协议的一些固有 缺陷，它们在设计中充分考虑了能源的有效利用，成倍的提高了整个网络的生命 周期。文中所述的各种路由协议都是针对特定的应用环境而设计的，在不同的环 境下表现出各自的特色和优势，因此不能绝对的判断哪种协议最优。当我们需要 持续采集网络中所有区域的信息时，可以采用f l o o d i n g 、g o s s i p i n g 、l e a c h 路由 算法；当只需要采集特定区域的特定数据信息时，可以采用s p i n 、t e e n 、d i r e c t e d d i f f u s i o n 算法。 分析了w s n 各分类中最有代表性的路由协议的特点，对它们的信息处理、 路由优化方式和网络体系结构的不同表现给出了一个综合比较，如表3 1 所示。 1 9 河海人学t 学硕上学位论文无线传感器网络l e a c h 路由协议的研究 表3 iw s n 路由协议性能比较 比较元数 路e 数 路由优网络生命数据路由健资源有 数据查 据描数据发谜 路径 够坦 化能力周期融合壮性效性 询缓存 述符 模式 选择 多 f l o o d i n g无不长 无好 不好 无 无 连续 跳 多 g o s s i p l n g 无 不长 无 好 不好无无连续 跳 d i r e c t e d 有较长有 不好 较好有有 查询多 d i f f u s i o n 驱动跳 查询多 s p i n无长无 较好 较好无有 驱动跳 芭 l e 枷无长有较好 好 有 无连续 跳 多 p e g s i s 有长有 不好 好有无 连续 跳 多 1 e 喇 有 长 有好好无 驱动跳 有 事件 查询多 g e 墟 无长无 较好 好 无 有 驱动 跳 3 4l e a c h 协议的分析与研究 3 4 1 层次路由协议和分簇算法 w s n 无固定通信设施和自组织特点使其具有极大的灵活性，但分布控制、 无中心和动态拓扑等特点限制了系统的可扩展性。为解决移动自组网可扩展性问 题，人们提出了层次化的解决方案。该方案利用分簇算法将w s n 划分成逻辑上 的层次结构，这种层次结构能有效降低路由维护系统开销，提高网络可扩展性， 提高信道的空间重用率，在面向大规模网络的应用系统中具有重要应用价值。 分簇算法的任务是将节点集合划分为相交或不相交的几个更小的集合 簇，簇内和簇间节点形成两层结构；将簇进行更细粒度的划分就形成多层嵌套的 层次结构。多层次结构适用于规模更大的网络，但通常两层结构已可以满足大多 数应用需求，l e a c h 协议及改进算法均采用三= 2 的分层簇类模式。 层次路由协议利用上述这种层次基础结构，具有以下优点：通过减少参与路 由计算的节点数目，减小了路由表的大小，降低了交换路由信息所需的通信开销 和维护路由表所需的内存开销；并且通过基于某种簇形成算法尽量选举产生较为 稳定的子网络，从而减少了拓扑结构变化对路由协议带来的影响：簇首节点对其 簇内的节点进行管理，能方便地向s i n k 节点传达节点的各种信息，例如能量、 安全性、故障等。另外s i n k 节点通过簇首节点可以有效地向网络中其他节点发 送命令，这是平面路由所不能有效实现的。分层模式的数学描述如下： 河海大学t 学硕十学位论文第三章w s n 路由协议算法分析 假设平面w s n 中节点的计算和通信能力完全一致，不存在单向链路。这时 w s n 的拓扑结构可抽象为一个连通无向图g = ( v ，e ) 表示，v 表示网络中节点的 集合，m 为节点数，e 表示两个节点间的双向链路集( 节点间存在直接通信能力 的边的集合) 。对于图c , - - - - ( v ，e ) ，有正整数m ，l v s m 。那么一个l ( l 1 ) 层的网络结构模式是v 的集合，它可以表示为v = p l ，p 2 ，p ， ，p ，表示 ， 第，层节点的集合，显然有v - n 。第f 层节点的集合只= v l ，v 2 ，v x ) ， t = l c f 。 v 。 表示第f 簇中的节点集合，其中表示簇首节点，v i j 表示普通节点，显 然只= c 对于只层中的任意一个簇结构满足以下条件： a ) u ：。c ，= p ，每一个节点分属不同的簇 b ) c 。n c ，= o ，任意两个簇之问没有交集 c ) c ，2 ，任意一个簇中的节点数目大于或等于2 分簇算法是构建层次结构的手段，w s n 中分簇算法必须完成层次结构的生 成和维护两大功能，在逻辑上分为簇生成过程和簇维护过程两个部分，分别对应 簇生成算法和簇维护算法。其目标是构造一个能够覆盖整个网络并较好支持资源 管理和路由的互连的簇集合。为了提高移动自组网的吞吐量，我们总是希望以最 少的簇酋覆盖整个网络，即簇首的集合为最小支配集( m d s ，m i n i m u md o m i n a t i n g s e t ) ，但建立m d s 是一个是n p 完全问题，因此一般采用启发式算法。为减少分 簇开销，分簇算法应简单高效，当只有很少节点移动和拓扑变化较慢时，网络应 尽量保持原有结构，从而减少因重新分簇而引入的开销并提高网络性能。 簇生成算法的任务是在系统初始化过程中快速建立全网范围内的层次结构， 一般包括簇首选择和簇成员加入两个阶段，其一般步骤如图3 8 所示：每个节点 首先计算自己的分