（检测技术与自动化装置专业论文）无线传感器网络路由协议优化研究.pdf

无线传感器网络路由协议优化研究 摘要 无线传感器网络因其低廉的价格、便利的部署方式，正得到越来越广泛的研究和 应用。无线传感器网络最大的缺点是节点能量受限，同时存储空间及计算能力等资源 也非常有限。在有限的硬件条件下，大规模数据采集易使网络产生拥塞现象，并造成 节点能耗大幅度增加，严重时会造成网络的瘫痪。以上问题使得在无线传感器网络中 数据传输的可靠性受到很大限制。本文以无线传感器网络路由协议为研究对象，综合 考虑传感器节点能耗、通信可靠性，对路由协议进行优化和改进，以提高网络的有效 工作时间。 本文主要研究工作如下： l 、在对比分析现有无线传感器网络路由协议和算法的基础上，结合网络的特征， 归纳出无线传感器网络路由协议的特点以及设计要求。 2 、在研究a o d v 路由协议和改进算法的基础上，提出适用于无线传感器网络的 a o d v 改进算法e r a o d v 。该算法采用限制泛洪改进机制，解决了a o d v 路由协议报 文的广播风暴问题，节约节点的能量消耗。同时在路由过程中将链路质量、剩余能量 及节点拥塞等多种因素作为确定路由的指标，为数据传输提供高效路由策略，提高了 网络的生命期和数据传输的可靠性。 3 、研究和分析了无线传感器网络分层型路由协议l e a c h ，对l e a c h 协议中的簇 头选举算法进行改进，同时引入蚁群算法，建立簇头间多跳路由，从而平衡传感器节 点的能耗，延长网络的寿命。 4 、对z i g b e e 网络中星型结构、网状结构和簇树结构三种拓扑结构进行研究，并 对相应的路由算法提出改进方案。 在n e t w o r ks i m u l a t o r ( n s 2 ) 仿真环境下对上述改进算法的性能进行研究分析，仿真 结果表明，改进算法均衡了整个网络节点的能量，有效地延长了系统生命周期。 关键词：无线传感器网络；路由算法；a o d v 路由协议；l e a c h 协议：蚁群算法 t h er e s e a r c ho nt h eo p t i m i z a t i o no fr o u t i n gp r o t o c o li n w i r e l e s ss e n s o rn e t w o r a b s t r a c t d u et oi t sl o wp r i c e ，c o n v e n i e n c eo ft h ed e p l o y m e n tm e t h o d s ，w i r e l e s ss e n s o r n e t w o r k sa r eb e i n gi n c r e a s i n g l yw i d e l ys t u d i e da n du s e d t h eb i g g e s td r a w b a c ko fw i r e l e s s s e n s o rn e t w o r ki st h a tn o d e sh a v ev e r yl i m i t e de n e r g y , s t o r a g es p a c ea n dc o m p u t i n ga b i l i t y l a r g e s c a l ed a t aa c q u i s i t i o nm a yb r i n gt h ed a n g e ro fc o n g e s t i o ni nt h ec o n d i t i o no fl i m i t e d h a r d w a r el i m i t s ，c a u s el a r g ec o n s u m p t i o n so fn o d e so re v e nn e t w o r kp a r a l y s i s t h e s e p r o b l e m sm a k et h er e l i a b i l i t yo fd a t at r a n s m i s s i o n si nw i r e l e s ss e n s o rn e t w o r ku n d e rg r e a t r e s t r i c t i o n i nt h i sp a p e r , r o u t i n ga l g o r i t h mi st h er e s e a r c ho b j e c t t o g e t h e rw i t he n e r g y c o n s u m p t i o no fs e n s o rn o d ea n dc o m m u n i c a t i o nr e l i a b i l i t y ，t h et h e m ep a y sa t t e n t i o nt o o p t i m i z ea n di m p r o v ei t ，i no r d e r t oi n c r e a s et h ee f f e c t i v ew o r k i n gt i m en e t w o r k t h em a i nc o n t e n t so ft h et h e s i sa r ea sf o l l o w s ： 1 o nt h eb a s i co ft h ec o m p a r a t i v ea n a l y s i so f e x i s t i n gw i r e l e s ss e n s o rn e t w o r kr o u t i n g p r o t o c o l sa n da l g o r i t h m s ，c o m b i n a t i o no fn e t w o r kc h a r a c t e r i s t i c s ，t h ec h a r a c t e r i s t i c so f r o u t i n gp r o t o c o l sf o rw i r e l e s ss e n s o rn e t w o r ka n dd e s i g nr e q u i r e m e n t sa r es u m m a r i z e d 2 a c c o r d i n gt ot h er e s e a r c ho fa o d vr o u t i n gp r o t o c o la n di m p r o v e da l g o r i t h m sf o r w i r e l e s ss e n s o rn e t w o r k s ，t h i sp a p e rp r o p o s e de n e r g y e f f i c i e n ta n dr e l i a b l er o u t i n g p r o t o c o l b a s e do na o d vf o rw i r e l e s ss e n s o rn e t w o r k s t h ea g r e e m e n ti n t r o d u c e sr e s t r i c t i o n so n b r o a d c a s tm e c h a n i s mt os o l v et h ea o d v r o u t i n gp r o t o c o lb r o a d c a s ts t o r mp r o b l e m ，a n d s a v e st h ee n e r g yc o n s u m p t i o no fn o d e s i m u l t a n e o u s l y , i nt h er o u t i n gp r o c e s s ，l i n kq u a l i t y , r e s i d u a le n e r g y , c o n g e s t i o no fn o d ea r ea l la d o p t e da sr o u t i n gm e a s u r et op r o v i d eah i 曲 e f f i c i e n tr o u t i n gp o l i c y 3 b a s e do nt h er e s e a r c ho fl e a c h r o u t i n gp r o t o c o la n di m p r o v e da l g o r i t h m sf o r w i r e l e s ss e n s o rn e t w o r k s ，t h i sp a p e rp r o p o s e se n e r g yb a l a n c es u b - c l u s t e rr o u t i n gp r o t o c o l f o rw i r e l e s ss e n s o rn e t w o r k sb a s e do na n tc o l o n ya l g o r i t h m t h ea l g o r i t h mi m p r o v e st h e e l e c t i o no fc l u s t e rh e a do fn e t w o r kn o d e s f u r t h e r m o r e ，t h ea n tc o l o n ya l g o r i t h mi s i n t r o d u c e di n t ot h ea l g o r i t h m ，w i t he s t a b l i s h m e n to fm u l t i - h o pr o u t i n gb e t w e e nc l u s t e r h e a d s ，u s i n gm u l t i - h o pc o m m u n i c a t i o n st ot h eb a s es t a t i o nt r a n s m i td a t a t h ea l g o r i t h mc a r l e f f e c t i v e l ye x t e n dt h en e t w o r kl i f e t i m e ，a n ds a v e sn e t w o r ke n e r g yc o n s u m p t i o nt oa c h i e v e n e t w o r kl o a db a l a n c i n g 4 z i g b e er o u t i n gp r o t o c o lf o rw i r e l e s ss e n s o rn e t w o r k si ss t u d i e d o nt h eb a s i co ft h e a n a l y s i so f s t a rs c h e m a ，m e s hs t r u c t u r ea n dc l u s t e rt r e en e t w o r k t o p o l o g y ，t h ep a p e r p r o p o s e si m p r o v e m e n tp r o g r a m t h e n e t w o r ks i m u l a t o ri ss e l e c t e da st oc r e a t es i m u l a t i o ne n v i r o n m e n t t h er e s u l t so f s i m u l a t i o ns h o w st h a tt h ei m p r o v e da l g o r i t h mb a l a n c e st h ee n e r g yo ft h ee n t i r en e t w o r k ， e f f e c t i v e l ye x t e n d st h es y s t e ml i f e 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 ；r o u t i n ga l g o r i t h m ；a o d vr o u t i n gp r o t o c o l ； l e a c h p r o t o c o l ；a n tc o l o n ya l g o r i t h m 插图清单 图2 1 无线传感器网络体系结构图6 图2 2 平面拓扑结构示意图7 图2 - 3 层次拓扑结构示意图7 图2 4 泛洪路由过程图一8 图2 - 5 定向扩散路由过程图8 图2 6p e g a s i s 数据传输流程图9 图3 - 1a o d v 路由过程图1 3 图3 2e r a o d v 算法结构图1 6 图3 - 3 协议初始阶段执行流程图1 7 图3 - 4r r e q 报文接收流程图2 0 图3 5r r e p 报文接收流程图2 1 图3 6 预先路由修复过程图2 2 图3 7e r a o d v 与a o d v 算法仿真存活节点个数对比图2 4 图3 - 8e r - a o d v 与a o d v 算法仿真分组平均投递率对比图2 4 图4 - 1l e a c h 协议分簇示意图2 6 图4 - 2l e a c h 算法流程图2 7 图4 3 簇头选举和簇构成算法流程图3 2 图4 4 簇头间路由建立流程图3 4 图4 - 5a c a - l e a c h 算法的数据传输过程图3 4 图4 - 6a c a - l e a c h 与l e a c h 算法仿真存活节点个数对比图3 5 图4 7a c a - l e a c h 与l e a c h 基站接收数据量对比图3 6 图5 - 1 网络拓扑结构图3 8 图5 - 2z i g b e e 星型路由结构图4 0 图5 - 3z i g b e e 簇树路由结构图4 1 图5 - 4z i g b e e 网状路由结构图4 2 图5 5r r e q 改进报文4 2 插表清单 表2 1 无线传感器网络路由协议的分类比较表1 1 表2 2 无线传感器网络路由协议的特点比较表1 1 表3 一le r a o d v 与a o d v 的网络寿命比较表2 4 表3 2e r a o d v 与a o d v 网络的平均投递率比较表2 5 表4 - 1 节点的邻居表3 l 表4 - 2 节点的簇头列表3 3 表4 3a c a l e a c h 与l e a c h 的网络寿命比较表3 6 表4 4a c a l e a c h 与l e a c h 的接收数据量比较表3 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金鲤王些太堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：叶黼签字日期：沙卜年邻月必日 学位论文版权使用授权书 本学位论文作者完全了解金巴王些太堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权金日巴王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者躲叶袖杯 导师魏 签字日期：洲。年q 月砖日 学位论文作者毕业后去向： 工作单位： 通讯地址： 签字日期：洲。年y 月沿日 电话： 邮编： 致谢 本文是在我的导师朱程辉副教授的悉心指导下完成的。从课题的选题到研 究都倾注了朱老师大量的心血。 朱老师高尚的人格、博大的胸怀、严谨的治学态度、渊博的理论知识和丰 富的实践经验给我留下了深刻而又美好的印象，使我终生难忘，并将是我今后 学习的楷模。在此向朱老师致以最诚挚的感谢! 衷心感谢王建平教授，王老师认真的工作态度、严谨细致的工作作风以及 学习生活上热心的帮助尤为让我感动。在此向王老师表示深深的感谢! 衷心感谢智能传感器网络研究所全体老师，您们的教诲为本文的研究提供 了理论与技术基础。 感谢同窗好友秦朗、王二帅、任冉冉、张大敏、徐奇同学在学习和生活上 的热情关心和无私帮助，感谢师弟、师妹们的关心和帮助，这段与你们一起度 过的学习和生活时光将是我人生的美好回忆。 感谢我的父母，他们给了我无微不至的关爱和全力的支持，在我的求学生 涯里，他们为我倾注了太多的心血，衷心地谢谢你们! 再一次向所有关心、支持和帮助过我的人表示衷心的感谢! 作者：叶福林 2 0 1 0 年4 月 第一章绪论 1 1 引言 无线传感器网络川( w i r e l e s ss e n s o r n e t w o r k ，w s n ) 是一种没有固定拓扑结构的 无线通信网络，通常由位于监测区域内随机布置的大量微型传感器节点构成，网络中 的节点采用多跳通信的方式相互进行通信。这种技术依靠节点间协作完成感知、采集 和处理网络涵盖范围内的对象信息，并发送给观察者。无线传感器网络不需要固定网 络支持，具有快速展开、抗毁性强等特点，存在广阔的应用前景，尤其在环境监测、 军事侦察、健康监测、火灾探测、交通监测、空间探索等领域优势更为明显。无线传 感器网络的研究涉及多学科技术，是一种全新的信息采集和处理技术，己成为当前计 算机信息领域热点研究课题比1 。 虽然无线传感器网络与传统无线网络有相似之处，但差异也尤为明显。传统无线 网络通常处于频繁移动的环境中，在满足服务质量的条件下，通过优化路由和系统资 源管理使带宽利用率最大化，其次才考虑节约能源。而无线传感器网络节点体积微小， 计算能力和存储容量较低，通常携带很有限的能量，且难以再次补充1 ，所以提高能 源的利用效率和设计简洁高效的路由协议是无线传感器网络的首要设计目标。无线传 感器网络设计必须针对特定的应用，其部署方式和拓扑结构根据具体应用的性质会有 所不同。通常情况下，工作环境和节点故障容易造成无线传感器网络拓扑结构的变化， 这些独特的要求和制约因素为无线传感器网络研究提出了新的技术问题。 目前，无线传感器网络的研究还存在很多不足地方，距大规模应用阶段还存在一 定的差距。无线传感器网络的广泛应用将改变人们认识自然界的方式，人们可以用其 为载体直接感觉客观事物的存在和变化，从而扩展现有网络的功能和人类认识世界的 能力。因此，及时开展对无线传感器网络的研究，加快进入实用阶段的进程，对整个 国家的社会、经济将有重大的战略意义。 1 2 无线传感器网络概述 1 2 1 无线传感器网络的发展进程与研究现状 无线传感器网络经历了三个发展阶段，即从智能传感器、无线智能传感器到无线 传感器网络。1 9 9 6 年，现代无线智能传感器概念起源于美国u c l a 大学的w 1 l i 觚j k f i s e r 教授向d a r p a 提交的“低能耗无线集成微型传感器 报告。无线传感器网络的最初 研究来源于美国军方，美国国防先进研究计划局于2 0 0 1 年对加州伯克利大学开发无线 传感器系统给以资助。2 0 0 3 年美国自然科学基金委员会制定了传感器网络研究长期规 划，对该方面的基础研究提供资金支持。从2 0 世纪末以来，美国相继启动分布式传感 器网络( d s n ) 、集成的无线网络传感器( w i n s ) 、智能灰尘( s m a r td u s t ) 、无线嵌入式 系统( w e b s ) 、协同分布式可升级系统结构( s c a d d s ) 、嵌入式网络传感( c e n s ) 和无线传感器网络的一系列重要研究项目h 1 。 我国对无线传感器网络的研究起步较早，1 9 9 9 年中国科学院知识创新工程试点 领域方向研究首先提出w s n 网络研究计划。中国科学院微系统研究与发展中心于 2 0 0 1 年在上海成立，意在整合中科院内部有关资源，共同推动无线传感器网络的研究。 2 0 0 2 年以来，中国国家自然科学基金委员会开始制定传感器网络相关课题的研究计 划。中国工业与信息化部在2 0 0 8 年启动的“新一代宽带移动通信网”国家级重大专 项中，该专项的设立将加快了对w s n 网络技术在应用领域的研究。2 0 0 6 年1 0 月， 中国计算机学会传感器网络专委会在北京正式成立，将中国w s n 技术研究带入了一 个新的发展阶段。 当前，无线传感器网络的研究主要基于在硬件系统和网络层面两大部分。硬件系 统主要关注问题包括微操作系统、微传感器技术、节能与网络生存期控制、数据的有 效采集、能量存储与带宽、无线通信技术、网络部署等；网络层面的研究内容主要涉 及网络自组织、节点间协作与信息处理、通信的安全性、网络拓扑与路由、任务管理 等诸多方面。目前，研究人员提出了诸如s p i n 哺副、d i r e c t e dd i f f u s i o nn 钔、l e a c h 【9 】、 t e e nn 引、p e g a s i sn ”等协议及其改进措施，对降低网络的整体能量消耗起了很大的 作用，同时提高了网络寿命。当前的研究成果推动了无线传感器网络的发展也使其初 步进入实用阶段，但传感器节点能量和通信可靠性问题仍没有一个很好的解决方案。 1 2 2 无线传感器网络关键技术 无线传感器网络作为当前计算机科学研究的新兴领域，研究人员在理论研究和实 际应用技术两个方面提出了许多挑战性课题。现阶段影响无线传感器网络性能的关键 技术包括拓扑控制、路由控制技术、时间同步、数据融合、网络安全技术和嵌入式操 作系统等。 ( 一) 拓扑控制技术 拓扑控制技术对提高无线传感器网络的性能，具有很重要的作用，尤其在提高网 络能耗效率、提高网络的生存期、降低链路碰撞等方面，优点尤其突出。目前网络拓 扑控制以保证工作区域内节点通信可达为出发点，通过调整节点发送功率和主干路径 的节点选择，改变节点的通信半径以除去节点之间不必要的链路，为数据的采集和传 送提供一条高效可靠的渠道n 羽。 拓扑控制通常通过节点功率控制和层次型拓扑构建两种方式来实现n 引。功率控制 技术通过调节传感器节点的发送功率，降低节点的能耗，同时保证网络连通度和均衡 邻居的分布。层次型的拓扑控制以将网络分成不同的簇为出发点，通过簇内节点轮流 充当簇首均衡能量消耗、非簇头节点在空闲情况进入睡眠状态以节省能量等手段，由 簇头节点形成一个高效的处理和转发数据通信路径。 另外，自主睡眠和有事唤醒机制也是拓扑控制的有效手段。这种技术使无事节点 的通信模块设置自动进入睡眠状态，当有事件发生时自动开启通信模块并唤醒相邻节 点，形成数据转发拓扑结构，节约传感器节点的能耗。 ( 二) 路由控制技术 路由协议的任务是在传感器节点和汇聚节点之间提供有效的数据传输路径。由于 2 传感器网络资源严重受限，因此路由协议设计的出发点应以避免节点进行复杂的计 算、维护过多的路由信息。研究人员相继提出了多种路由协议，设计思想大都基于无 线传感器网络的以下特点： ( 1 ) 传感器节点寻址基础是数据属性，而不是全网唯一的地址； ( 2 ) 网络中节点采集数据通常只传输到s i n k 节点，而普通节点间一般不进行数据 交流； ( 3 ) 网络的随机部署导致节点间分布存在较大的冗余性，从而采集的数据存在很 大的相似性。 ( 三) 信息融合技术 在收集信息的过程中采用各个节点单独传送数据到汇聚节点的方法是不合适的， 主要有以下两个原因： ( 1 ) 降低能量的利用效率：无线传感器网络一般具有较高的覆盖度，邻近节点采集 的数据存在很大的重复性，网络中节点各自传输数据会占用较大的通信带宽。同时， 大量数据的传输加速整个网络节点能量过快消耗，缩短网络的生命周期； ( 2 ) 影响系统信息收集的可靠性：网络中可能会出现多个节点同时传输数据的情 况，导致信道的冲突，造成数据的丢失和重传，从而影响了信息收集的可靠性。 为解决上述问题，无线传感器网络利用数据融合技术处理收集的数据，当然这种 处理方式不能破坏数据准确性。数据融合是向s i n k 节点提供更符合需求的数据的过 程，它将多份数据进行统一处理和构造，以提高信息的准确度n 4 1 。 数据融合是一种减少传输数据量，节省能量的策略，在资源受限的无线传感器网 络中应用优点尤其突出。 。 ( 四) 时间同步技术 时问同步是协同传感器节点间工作的重要技术，也是分布式系统都要解决的个 重要问题。虽然现在有许多成熟的方法可以应用解决该问题，但是无法直接应用于无 线传感器网络的时间同步，这是由于无线传感器网络具有其自身的特点，必须考虑以 下因素： ( 1 ) 无线传感器网络时间同步首先要解决数据传输延迟的不确定性的问题； ( 2 ) 无线传感器网络优先考虑功耗问题，时i 刨同步技术必须优先考虑该问题； ( 3 ) 无线传感器网络中，节点的移动、故障及外界环境的变化等多种因素都会导 致无线传感器网络的高度动态性。时间同步协议必须能够对这些情况进行处理，以保 证系统的健壮性。 ( 五) 网络安全技术 由于无线传感器网络工作环境和无线通信的开放性，容易遭受各种外来攻击。无 线传感器网络作为基于特定应用的网络，要完成数据采集、传输和融合、而且还要完 成节点的协同控制等。安全技术保证系统开销在合理范围内为数据传输提供一种更安 全的通信渠道。 传感器节点随机部署、网络拓扑的动态性以及信道的不稳定性，使传统的安全机 制无法直接被应用，因此需要设计新型的网络安全机制符合无线传感器的特点。 ( 六) 嵌入式操作系统 传感器节点具有嵌入式系统的特征，需要操作系统管理其硬件和软件，以支持 多个任务可以并发运行。从目前的发展情况来看，美国加州大学伯克利分校研发的 t i n y o s 操作系统是最成功的w s n 专用操作系统。 1 2 3 无线传感器网络研究的难点 就当前的技术水平来说，无线传感器网络稳定运行并大规模投入使用需要解决以 下难题： ( 1 ) 节点问通信问题。无线传感器网络节点间通信需要一条安全、可靠的渠道， 而由于外界环境的影响恶化通信链路质量的情况经常出现。如何进行安全可靠的通信 是个急需解决的问题。 ( 2 ) 传感器节点能力受限。传感器节点的能量、处理能力、存储能力和通信能力 都十分有限，实现网络协议和应用系统时受到很大的限制。 ( 3 ) 高效的组网模式。组网模式影响无线传感器网络的性能，分为平面模式、基 于分簇的层次模式等。合理的拓扑结构可以充分的利用系统的资源。 1 3 课题研究的目的和意义 无线传感器网络在工业、农业、军事、环境、医疗等传统领域具有巨大的运用价 值，特别在低速的环境监测优越性尤其突出。尽管无线传感器网络前景光明，但仍有 很多问题有待解决，研究的关键问题是网络的能量管理和可靠性设计。无线传感器网 络节点能耗大部分集中在无线通讯模块上n6 1 ，开发能降低传感器节点能耗以延长网络 生存周期的路由技术成为无线传感器网络研究的核心问题，也是当前国内外研究机构 关注的焦点。由于传感器网络节点能量有限，在特殊的部署方式和复杂环境下，使得 能量难以再次补充。当电池电量消耗殆尽后，节点失效并退出网络，严重的影响网络 的拓扑结构。在极其严重的情况下，若关键节点过早地退出网络，可能会直接导致一 条或多条路由的无效，从而造成网络的瘫痪。除此之外，网络拓扑也会对路由协议的 性能产生严重的影响。在节点大规模随机分布的传感器网络中，可能会导致部分区域 节点的密度较为稠密，造成节点的能量不必要的消耗，而且容易因广播风暴造成阻塞 及碰撞。为了最大限度的提高整个网络的生存期和数据传输的可靠性，本文对现有的 a o d v 路由协议、链路拥塞、分簇路由协议等问题进行了研究，提出的改进算法能有 效地解决节点能量损耗不均衡、路由请求过程中报文广播风暴等问题。 1 4 课题研究的主要内容 本文主要研究无线传感器网络的路由技术，在阅读了大量文献的基础上，着重研 究适合无线传感器网络的a o d v 路由协议和分簇路由协议以及改进算法的实现。具体 工作包括以下几个方面： 4 ( 1 ) 研究和分析现有无线传感器网络路由算法，通过对一些典型的路由算法在能 量消耗方面进行分析和比较，归纳出平面路由算法和层次路由算法各自的优点和局限 性，提出路由算法设计的出发点。 ( 2 ) 在研究a o d v 路由协议的基础上，提出适用于无线传感器网络改进算法，称 为e r a o d v 。e r a o d v 算法通过建立全网的方向梯度，在路由中采用受限洪泛 机制、最优路由回复机制建立起源节点到s i n k 节点的最优路径。 ( 3 ) 针对l e a c h 协议中簇头节点与汇聚节点单跳通信带来的问题，提出了无线 传感器网络l e a c h 改进算法，称为a c a l e a c h 。该算法在l e a c h 路由协议的基础 上，在簇头选举过程中引入能量最大优先机制，并在簇问路由建立过程中引入了蚁群 算法，根据能量和距离寻找最优传输路径。 ( 4 ) 研究z i g b e e 网络的路由算法。分析z i g b e e 网络中星型结构、网状结构和簇 树结构三种拓扑结构的路由算法优缺点，提出了相应的改进方案。 第二章无线传感器网络路由协议分析与研究 无线传感器网络系统通常包括三个主要构件n 引：传感器节点( s e n s o rn o d e ) 、汇集 节点( s i n k ) 和观察对象，网络体系结构如图2 - 1 所示。大量传感器节点随机布置在监 测区域内，通过自组织的方式构成网络。每个节点将采集的数据通过多跳的方式传输 到汇聚节点，然后通过其它通信方式传给用户。用户通过汇集节点或者管理节点对传 感器网络进行监控和管理，发布监测指令以及收集监测数据。 i n t e r n e t 或 h 马一 或 c o 印u t e r t广 o lk ，、 任务管理节点( 、一 ： ， 用户 观察对象 图2 1 无线传感器网络体系结构图 传感器节点n 明通常具有数据采集和处理能力的微型嵌入式系统，集成了数据采 集、无线通信和能量供应模块。由于受到成本和能源供给等因素的限制，传感器节点 的处理和存储能力相对薄弱，通常只和自身通信半径内的邻居节点交流数据。要访问 通信半径外的节点，必须借助邻居节点转发报文。无线传感器网络节点的布置要满足 一定的连通性确保监测到的数据能够传送到汇聚节点。每个传感器节点除了完成本地 数据的采集和处理外，同时还要接收和转发邻居节点发送的数据。汇聚节点通常具有 较强的处理和通信能力，具有双重作用。一方面收集监测区域内产生的数据，发布用 户对网络管理和任务的信息：另一方面它连接传感器网络和电脑终端，转发收集到的 数据信息到外部终端上。 2 1 无线传感器网络路由协议概述 路由协议是无线传感器网络层的核心技术，它主要包括两个方面的功能：寻找数 据的传输路径、对路径进行维护。 传统无线网络的设计以提供服务质量和提高带宽利用率为出发点，对终端间的传 送时延有很高的要求。这些网络的路由协议以最少跳数作为主要路由度量指标，同 时提高网络资源的利用率，预防链路冲突及平衡网络流量等，而能量消耗问题是这类 网络次要问题。在无线传感器网络中，一般节点能量受限且难以再次补充，因此能量 消耗是设计需要考虑的首要因素。同时单位区域内无线传感器网络节点数可能几倍于 传统网络，节点难以获取全网的拓扑信息，这就要求路由协议能依据有限的拓扑信息 选择适当的传输路径。由于无线传感器网络的应用环境和数据通信模式不同，设计者 6 需要根据具体应用的需求设计与之适应的特定路由机制。此外，传感器网络的路由机 制往往与数据融合技术联系在一起，通过减少通信量而节省能量。 无线传感器网络路由协议负责在s i n k 节点和其余节点间提供可靠地传输路径，支 持网络节点间的协同工作。无线传感器网络路由协议根据具体应用和拓扑结构存在很 大的差异，根据网络的拓扑结构，路由协议可以分为平面结构路由协议和层次结构路 由协议引。在平面结构路由协议中，所有节点具有数据采集和路由双重功能，且协同 完成数据采集任务，通过局部操作和反馈信息来生成路由，采用多跳的方式传送数据 到汇聚节点。平面路由协议拓扑结构如图2 2 所示。 汇聚节点 图2 2 平面拓扑结构示意图 在层次结构路由协议中，网络通常被划分为多个不同的簇，每个簇由一个簇头节 点和多个簇内成员节点组成。簇内节点等概率充当簇头，均衡节点的能耗。簇成员节 点负责采集本地数据，并将数据转发给簇头，而簇头节点负责簇内数据的融合，并将 数据传送给汇聚节点。层次结构路由拓扑结构如图2 - 3 所示。 图2 3 层次拓扑结构示意图 2 2 典型无线传感器路由协议分析 2 2 1 路由协议介绍 ( 一) 泛洪路由协议n 7 1 泛洪( f l o o d i n g ) 路由是一种传统的网络通信协议。泛洪算法路由过程如图2 4 所 示，当源节点需要传输数据给汇聚节点时，向所有邻居节点广播数据包，中间节点收 到数据包后继续以广播的形式转发数据包，直到数据扩散到目的节点。泛洪路由过程 如图2 - 4 所示。 7 汇率节点 图2 4 泛洪路由过程图 对于自组织的无线传感器网络，泛洪式路由是种较为直接的实现方法。它的优 点是：易实现，不需要进行网络拓扑信息的维护和复杂路由的计算而增大网络的能耗 成本，适用于鲁棒性要求高的情况。泛洪的缺点是： ( 1 ) 存在信息泛滥问题，即出现一个节点可能几乎同时得到多个相同数据的现象： ( 2 ) 出现数据交叠现象，如果处于同一观测环境的几个相邻传感器节点在同一时 间对同一事件回应，这两个数据是同一性质的，当时的邻居节点将获得多份基本相同 的数据； ( 3 ) 节点能耗不均衡，泛洪算法不考虑各节点的能量状态，无法做出适当的路由 选择。 ( 二) 定向扩散路由协议 定向扩散协议( d i r e c t e dd i f f u s i o n ) 是以数据为中心和基于查询驱动的路由机制。 协议采用以数据为中心的思想有利于消除冗余的数据，尽量减少数据发送量，从而节 省网络能源和延长其寿命。汇聚节点向邻居节点广播兴趣报文扩散启动路由建立过 程，兴趣报文包括任务类型、目标区域、数据发送速率、时间戳等参数。邻居节点收 到报文后，建立与发送报文的上一跳节点的梯度关系。兴趣报文广播逐级扩散，最终 遍历全网，建立起符合要求的节点向汇聚节点传输数据路径。算法路由过程如图2 5 所示。通过调整的梯度相关参数，以符合多样的应用需求，一般通过时延和与上个转 发兴趣报文节点的跳数来确定。 符合兴趣报文要求的节点把数据发送到梯度方向的上一跳节点，并根据梯度上的 数据传输速率调节节点采集数据的频率。数据传输可能通过多条路径，而汇聚节点会 根据数据到达的先后选择一条路径进行加强，最终会形成一条“梯度”值最大的路径， 而其他路径可以作为替代路径，以提高网络的可靠性。 = 一篓一j o ooo 蓑i + ( ) + 汇鼍节点卜善+ ( 3 h 汇曩节点 oo “垤黼据oo 3 姗艇 图2 5 定向扩散路由过程图 8 定向扩散协议采用邻居节点间通信的方式来避免维护全局拓扑，采用查询驱动 数据传送模式和本地数据融合而降低网络数据流，因此是种能量高效的协议。 ( 三) 低功耗自适应聚类路由算法( l e a c h ) l e a c h ( l o w e 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 ) 协议由麻省理工学院 h e i n z e l m a n 等人专门针对无线传感器网络设计的低功耗分簇式路由协议，在无线传感 器网络路由协议中发挥重要作用，其它基于分簇的路由协议如t e e n ，a p t e e n ， p e g a s i s 等大都由l e a c h 发展而来。l e a c h 协议运用数据融合技术和等概率簇首节 点轮换机制节约能耗成本，通过簇头节点的数据融合技术去除冗余的数据，同时保证 各节点等概率地担任簇头，均衡节点的能耗，防止簇头节点的过早失效。 鉴于本文在第四章要重点介绍和分析l e a c h 协议，故在这里就不赘述了。 ( 四) p e g a s i s 协议 传感器信息系统中的高能效采集( p o w e re f f i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o n s y s t e m s ，p e g a s i s ) 由l e a c h 发展而来的，是一个以近似最优链为基础的协议。 p e g a s i s 协议采用动态簇头选举原理，建立一条包含所有节点的最短传输途径，称为 “链 ，而不是把网络分成多个不同的簇。链上的每个节点仅与最近的邻居节点通信， 并且链中节点轮流负责与s i n k 节点通信，从而延长网络的生命周期。在p e g a s i s 协议 中节点要找到最近的邻居节点，每个节点使用信号强度以衡量所有邻近节点的距离， 然后调整功率保证一个节点可以接收。 p e g a s i s 协议采用贪婪算法从最远节点开始来构建链，其数据传输流程如图2 6 所示，此时节点3 是簇头。需要传输数据时，先由节点3 沿着链的一端发送报文，节点l 和节点2 收到报文后开始传数据。节点1 先传给节点2 ，节点2 将收到的数据与自身的数 据进行融合，再传给节点3 ，节点3 收到后沿着链的另一端发送报文，通知节点4 和节点 5 可以传输数据，节点4 和节点5 按照同样的方式将数据传给节点3 。在链两端的数据都 收到后，节点3 将它们与自己的数据进行融合，然后再传给汇聚节点。此时，一轮数据 采集过程就完成了。 和一集1 了点 图2 - 6p e g a s i s 数据传输流程图 当链中出现节点死亡时，链将需要重建。当前还没有有效方法寻找包含所有节点 的最短路径，p e g a s i s 协议不适合在大规模网络上使用。此外，p e g a s i s 协议主要依 据链上节点的随机位置获得簇头的随机性，各轮簇头间的负载平衡效果有限。 ( 五) g e a r 路由协议舢 g e a r 路由协议基于数据查询的模式，它假设每个节点知道自己和邻居节点的位 置和能量水平，同时利用节点的位置信息把数据传送到指定的区域，减少传输的距离。 9 g e a r 协议分为目标区域数据传输和域内数据传输两个阶段。在目标区域数据传输阶 段，当节点收到一个数据报文，检查其邻居节点列表中是否有比自己更接近目标区域 的节点，如果有一个以上，到目标地区最近的邻居节点被选定为下一跳。如果不存在 则认为有一个区域空洞。在这种情况下，节点根据最小通信开销的原则选择某个邻居 节点作为下一跳。在域内数据传输阶段，如果数据报文达到该区域，可以通过坐标递 归或限制广播的方式在区域内扩散。g e a r 协议不仅降低了路由的能源消耗，报文传 递的性能优于其他基于位置的路由协议，从而更有效的提高了网络的生命周期。 2 2 2 路由协议分析与评价 平面路由算法易实现、效率较高，要求所有传感器节点都具有数据采集和路由功 能，节点借助中间节点通过多跳的通信模式将数据传送给汇聚节点。但是该算法容易 导致节点能耗的不均衡，造成关键节点可能因能耗迅速而过早失效，影响网络的性能。 层次型路由算法中只有部分节点负责数据的转发，并且簇头节点容易实现对收集的数 据进行数据融合，避免了不必要的通信开销从而延长了节点的生存期。这种路由协议 可以很好的满足传感器网络的可扩展性，适用于大规模的网络。但同样存在些问题： 算法导致数据存在较大的延时；簇头分布的不均匀导致节点能量消耗存在很大的 差异，减少网络的生命周期。 定向扩散、l e a c h 、p e g a s i s 和g e a r 路由协议避免了泛洪协议存在的固有缺陷， 设计以提高能源使用效率为出发点，大幅度提高整个网络生命周期，但都存在由于能 量消耗导致的“热点问题”。 定向扩散协议具有许多优点：它采用多路径，性能稳定；利用数据融合技术去除 冗余数据。协议以提高能源的利用效率为出发点，节点按需传送采集数据，只需维护 局部拓扑的信息。但同时也存在很多缺点：由于协议基于查询驱动的数据传送方式， 所以无法应用到需要周期持续的发送数据的场合；节点和兴趣报文的匹配过程消耗 了节点额外的资源；协议采用的“抑制副本”数据融合方法可能会导致有效数据的 丢失。 l e a c h 算法具有动态集群的优势，均衡传感器节点的能耗，提高网络的正常工作 时间。在l e a c h 算法中，传感器节点间的相互关系明确，只需维护简单的拓扑信息。 l e a c h 的缺点是它采用单跳传输数据的方式，要求节点以较大功率直接与s i m ( 节点 通信，导致其可扩展性差，不适用于大规模得网络；周期性的簇头选举造成大量的 能源消耗。 p e g a s i s 算法避免了周期性选举簇头引起的不必要能耗，通过传感器节