（计算机系统结构专业论文）无线传感器网络leach协议的研究与改进.pdfVIP

山东大学硕士学位论文 摘要 无线传感器网络是一种全新的信息获取和处理技术，它综合了传感器技术、 嵌入式计算技术、无线网络通信技术、分布式信息处理技术以及微机电技术等， 能够协作地实时监测、感知和采集各种环境或监测对象的信息，通过嵌入式系统 对信息的处理，以及自组织网络多跳中继方式将信息传送到终端用户，从而实现 “无处不在的计算”理念。可以预计，无线传感器网络的发展和广泛应用，将对 人们的社会生活、产业变革带来极大的影响和产生巨大的推动作用。目前，各国 研究者致力于无线传感器网络的路由协议、m a c 层协议、q o s 、网络拓扑控制、 网络安全等各方面的研究，并取得了一定的研究成果。本文将着重对无线传感器 网络l e a c h 路由协议进行研究。 本文针对l e a c h 路由协议的不足，在以下两方面进行了改进： 1 考虑选择阶段能耗和簇头节点压缩比受限2 方面的问题，我们改进了 l e a c h 路由协议最优簇头数目计算公式，并证明了在新的限定条件下传感器网络 的生存周期最长。仿真结果表明，当且仅当簇头节点接收到的数据正好一次能被 完全压缩并发送到基站时，网络生存周期最长。 2 考虑到节点剩余能量和链路代价2 方面的问题，我们采用划分区域的聚 类方法，引入权重的概念，改进了簇头选择算法，可以使簇头节点均匀分布在网 络中，得到较优化的聚类结构，有效地解决了簇头分布不均匀和簇内节点数差异 过大的问题，减少了簇内通信的能耗；同时，各簇头之间采用多跳的方式，降低 了簇头节点与基站b s 之间长距离通信的能耗。这些措施保证了整个网络的能量 负载能平均分配到每个传感器节点，有效地降低网络能耗、延长网络生存时间。 仿真结果表明，l e a c h - w 算法的网络延时并没有增加多少，簇和死亡节点的分 布更具均衡性，存活节点数明显提高、网络能耗有效降低，这些改进延长了网络 生存周期。 关键字：无线传感器网络：路由协议：l e a c h w ；能耗；网络生存周期 山东大学硕士学位论文 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 s ( w s n ) ，i san e wt e c h n o l o g ya b o u ta c q u i r i n ga n d p r o c e s s i n gi n f o r m a t i o n i ti n c l u d e st h es e n s o rt e c h n o l o g y , e m b e d d e dt e c h n o l o g y , w i r e l e s sn e t w o r k sc o m m u n i c a t i o nt e c h n o l o g y , 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 g t e c h n o l o g ya n dm i c r o - e l e c t - m e c h a n i c a lt e c h n o l o g y , a n dc a l lb ea b l et om o n i t o r , 印- p e r c e i v ea n dc o l l e c tt h ei n f o r m a t i o no ft h ee n v i r o n m e n to rm o n i t o r i n go b je c t s r e a l - t i m e l y t h e nt h ei n f o r m a t i o ni sp r o c e s s e db ye m b e d d e ds y s t e m sa n ds e n tt ot e r - m i n a l sv i as e l f - o r g a n i z e dn e t w o r k sw i t hm u l t i - h o pr e l a y , s o 嬲t oi m p l e m e n tt h e “c o m p u t ee v e r y w h e r e c o n c e p t i o n i tc a nb ef o r e c a s t e dt h a tw i t hi t sd e v e l o p m e n t a n dt h ec o m m o n l ya p p l i c a t i o n ，w s nw i l lb r i n gd e e p l yi n f l u e n c ea n dm a k eag r e a t c o n t r i b u t i o nt op e o p l e sl i f ea n dt h et r a n s f o r m a t i o no fi n d u s t r y a tp r e s e n t ，m a n yr e s e a r c h e r sf o c u so nt h er e s e a r c ho fr o u t i n gp r o t o c o l s ，m a cp r o t o c o l ，q o s ，n e t w o r k t o p o l o g yc o n t r o l ，n e t w o r ks e c u r i t ya n ds oo n i nt h i sp a p e rw ew i l lp a ya t t e n t i o no n l e a c h ( l o 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 ) r o u t i n gp r o t o c o lo fw s n t h i n k i n go ft h ei n s u f f i c i e n ti nt h el e a c hr o u t i n gp r o t o c o l ，t h i sp a p e rp r e s e n t s t w o f o l l o w i n ga s p e c t st oi m p r o v e i t ： 1 c o n s i d e r i n gt h ep r o b l e m so ft h ee n e r g yc o n s u m p t i o nd u r i n gt h ec l u s t e rs e l e c t i o no fl e a c h r o u t i n gp r o t o c o la n di t sl i m i t so nc o m p r e s s i o nr a t i oo fc l u s t e r - h e a d e r n o d e s ，w ei m p r o v et h ef o r m u l ao ft h ec o m p u t i n gf o ro p t i m a ll e a c hc l u s t e r - h e a d e r n u m b e ra n dp r o v et h a tt h en e t w o r kl i f e t i m ei st h el o n g e s to n ei nt h en e wg i v e nc i r - c u m s t a n c e w i t ht h er e s u l t so fs i m u l a t i o ne x p e r i m e n t s ，i ti n d i c a t e st h a tt h en e t w o r k l i f e t i m ei sl o n g e s ti ft h ed a t ar e c e i v e db yc l u s t e r - h e a d e rc a nb et o t a l l yc o m p r e s s e da ta t i m ea n ds e n tt ot h eb a s es t a t i o n 2 c o n s i d e r i n gt h er e s i d u a le n e r g yo ft h en o d e sa n dt h el i n kc o s t ，w ea d o p ta c l u s t e r i n gm e t h o do fp a r t i t i o n i n gv i r t u a la r e aa n di n t r o d u c en o d e sw e i g h tt oi m p r o v e c l u s t e r - h e a d e rs e l e c t i o na l g o r i t h m ，w h i c he n s u r e st h a tt h ec l u s t e r - h e a d e rn o d e sc a nb e d i s t r i b u t e dh o m o g e n e o u s l yi nt h en e t w o r k s s ot h a tam o r eo p t i m a lc l u s t e rs t r u c t u r ei s i i p r o d u c e d ，t h i sc a l la v o i dn o n h o m o g e n e o u sd i s t r i b u t i o no ft h ec l u s t e r - h e a d e r sa n d t h e b i gd i f f e r e n c ea m o n gt h en u m b e ro f e a c hc l u s t e ra n dc a nr e d u c et h ee n e r g yc o n s u m p - t i o no fc o m m u n i c a t i o nw i t h i nc l u s t e r s m e a n w h i l e ，t h ew a yo fm u l t i p l e - h o p sa m o n g c l u s t e r sr e d u c e st h ec o m m u n i c a t i o nc o n s u m p t i o nd u r i n gt h el o n gd i s t a n c eb e t w e e n c l u s t e r - h e a d e rn o d e sa n db a s es t a t i o n t h e ni tm a k e ss u r et h a ta l lt h ee n e r g yl o a d si n t h en e t w o r k sc a nb ed i s t r i b u t e da v e r a g e l yt oe a c hs e n s o rn o d e ，w h i c hc a nr e d u c et h e n e t w o r k se n e r g yc o n s u m p t i o na n dp r o l o n gt h ee x i s t e n c eo ft h en e t w o r k se f f e c t i v e l y w i t ht h er e s u l t so fs i m u l a t i o ne x p e r i m e n t s ，i ti n d i c a t e st h a tt h e r ei sl i t t l ec h a n g eo f n e t w o r kd e l a yw i t h i nt h el e a c h - w a l g o r i t h ma n di ti so fm o r eb a l a n c ef o rt h ec l u s - t e r sa n dd e a dn o d e s a tt h es a m et i m et h en u m b e ro fa l i v en o d e si si n c r e a s i n ga n dt h e n e t w o r ke n e r g yc o n s u m p t i o ni sr e d u c e de f | f e c t i v e l y ，w h i c hi sc o n t r i b u t e dt ot h ep r o l o n g a t i o no ft h en e t w o r kl i f e t i m 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 gp r o t o c o l ；l e a c h - w ；e n e r g y c o n s u m p t i o n ；n e t w o r kl i f e t i m e i l l 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名： 圣李蕴 日 期：2 堕：生理 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：牡导师签名：壅盟日 期： 第一章绪论 本章首先介绍论文选题背景，然后阐述本选题研究的目的和意义，最后介绍 了论文的组织结构。 1 1 选题背景 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，简称w s n ，也叫传感器网络) 是 由联接传感器、激励源和处理器所组成的新型无线自组织网络。随着现代微电子 技术、微机电系统( m s ) 、片上系统( s o c ) 、纳米材料、无线通信技术、信 号处理技术、计算机网络技术等的进步以及i n t e m e t 的迅猛发展，w s n 的研究在 多种应用方面取得了重大进展，各种技术评论杂志也一致看好w s n 蕴藏的巨大 应用潜力和商业价值。2 0 0 3 年2 月，美国m i t 技术评论杂志将w s n 列为未 来改变世界的l o 大新兴技术之首【l 】。2 0 0 3 年8 月出版的美国商业周刊杂志 在其“未来技术专版”中发表文章指出，效用计算、传感器网络、塑料电子学和 仿生人体器官是全球未来的四大高科技产业，它们将掀起新的产业浪潮 2 1 。美国 今日防务杂志更认为w s n 的应用和发展，将引起一场划时代的军事技术革 命和未来战争的变革。可以预见，无线传感器网络将对人们的社会生活、产业变 革带来极大的影响和产生巨大的推动作用。 w s n 作为“无处不在计算”思想衍生的产物，可以被广泛地应用在国防军 事、环境监测、交通管理、医疗卫生、制造业、抗灾抢险等领域，拥有巨大的应 用价值，己经引起了世界许多国家军界、学术界和工业界的高度重视。发达国家 如美国，非常重视w s n 的发展。美国自然科学基金委员会2 0 0 3 年制定了w s n 研究计划，投资巨额资金，支持相关基础理论的研究。美国国防部和各军事部门 都对w s n 给予了高度重视，把w s n 作为一个重要研究领域，设立了一系列的 军事传感器网络研究项目。日本、英国、意大利、巴西等国家也对w s n 表现出 了极大的兴趣，纷纷展开了该领域的研究工作。我国在2 0 0 6 年发布的国家中 长期科学与技术发展规划纲要( 2 0 0 6 2 0 2 0 ) 中指出，信息技术重点研究低成本 的自组织网络，个性化的智能机器人和人机交互系统、高柔性免受攻击的数据网 山东大学硕士学位论文 络和先进的信息安全系统，其中2 个与w s n 的研究直接相关，足见我国对无线 传感器网络的重视程度。尽管i e e e 还没有成立w s n 的标准制定小组，但是i e e e 近几年来也一直在努力推进w s n 的应用和发展，在2 0 0 3 年上半年，各种传感 设备的无线连接接口标准i e e e p l 4 5 1 5 在美国制定【3 1 。b o s t o nu n i v e r s i t y 、b p 、 h o n e y w e l l 、i n e t c os y s t e m s 、i n v e n s y s 等创办了传感器网络协会，期望能促进传 感器联网技术开发。在民用w s n 产品的研制方面，i n e l 、m i c r o s o f t ，m o t o r o l a 、 h o n e y w e l l 等也都推出了自己的系列方案。 目前，国际上w s n 的研究主要集中在节点层面和网络层面两大部分。节点 层面的研究内容主要包括传感器技术，低功耗芯片技术，无线通信技术【4 1 等；网 络层面的研究内容主要包括低能耗路由协议技术，低能耗m a c 协议，协同定位 技术，时钟同步技术【5 1 ，数据融合技术6 1 等。国内w s n 的研究主要集中在穿戴 式计算、上下文感知环境、智能教室等领域方面，而支持w s n 的无线通信网络 技术的研究( 尤其是w s n 路由技术) 尚不多见。尽管研究人员提出了诸如 s p i n 7 引、d i r e c t e dd i f f u s i o n l 9 1 1 1 们、l e a c h 1 1 】【1 2 1 、t e e n 13 1 、p e g a s i s 1 4 1 等协议 及其改进算法，在某些方面降低了w s n 的总体能耗，延长了网络的生存周期。 但，它们还处于实验研究阶段，并不能大规模应用于真实的环境，所以本论文重 点研究w s n 中影响较大的低能耗动态分簇路由协议叫，e a c h 协议。 1 2 研究目的和意义 尽管w s n 前景光明，但人们还需要很多努力。一个关键问题是使传感器的 能源供应能维持数年。这意味着利用太阳能或动能，或者说细调系统，这样它们 就只需要用很少的电池能源。另一个难题是为传感装置的硬件和软件确定行业标 准。由于w s n 节点8 0 的能耗集中在无线通讯模块上，因此，开发能降低传感 器节点能耗，延长网络生存周期的路由技术就成了w s n 研究中的核心问题，也 是当前国内外研究机构关注的焦点。 研究表明【1 5 】【1 6 】：传统的i n t e m e t 技术加上移动自组织网( m o b i l ea d h o e n e t w o r k s ，简称a d h o c 网络) 路由机制并不适用w s n ，两者有着明显不同的技 术要求，传感网络中研究和使用的追求高速率，高服务质量保证( q o s ) 的技术 不能直接应用于w s n ，一些为a d - h o c 网络设计的协议和算法未必适合w s n 的 山东大学硕士学位论文 特点和应用的要求。w s n 中的大部分节点不像传统a d h o e 网络中的节点一样快 速移动，因此没有必要花费很大的代价频繁地更新路由表信息；中间节点上与具 体应用相关的数据处理、融合和缓存也显得很有必要。在密集分布的w s n 中， 相邻节点间的距离非常短，低功耗的多跳通信模式可以降低功耗，同时增加了通 信的隐蔽性，也避免了长距离的无线通信易受外界噪声干扰的影响。这些独特的 要求和制约因素给w s n 的研究提出了新的技术问题如何保证w s n 能耗最 小化、节点生存周期最大化、能量负载均衡化和通信能力最优化等现实要求。 但由于w s n 是一种新的信息获取与信息传送方式的代表，是计算、通信和 传感器三项技术交叉结合的产物，国际上的研究尚处于起步阶段，距离实际需求 还相差甚远。因此，国内与国际水平的差距并不很大，及时开展这项前沿科技研 究的深度和广度，对整个国家的社会、军事和经济的发展都具有重大战略意义。 1 3 论文组织 第一章首先介绍了本文的课题背景，其次阐述了本课题的研究目的和意义。 第二章粗略介绍了w s n 的基础知识及路由协议的特点及设计要求，对经典 的路由协议作了简要介绍和性能比较。 第三章详细介绍了主要研究内容- i ，e a c h 路由协议，对其最优簇头数目 进行了研究，改进了最优簇头数计算公式。同时，通过对l e a c h 协议的算法分 析，提出了l e a c h 协议的改进算法基于区域划分的低能耗加权分簇路由算 法l e a c h - w ，并详细描述了l e a c h - w 算法的簇头选择过程和簇问路由的生成。 第四章对l e a c h w 算法进行了仿真分析。 第五章对课题中所做的工作进行了全面的总结，并给出下一步需要进行的工 作。 山东大学硕士学位论文 第二章无线传感器网络综述 w s n 是由部署在监测区域内大量的廉价、微型传感器节点组成，通过无线 通信方式形成的一个多跳的、自组织的网络系统，其目的是协作地感知、采集和 处理网络覆盖区域中感知对象的信息，并发送给观察者。w s n 典型的结构如图 2 - 1 所示【l6 1 ，通常包括传感器节点、汇聚节点和管理节点。传感器节点通常是一 个微型的嵌入式系统，它的处理能力、存储能力和通信能力相对较弱。每个传感 器节点兼顾传统网络节点的终端和路由器双重功能。汇聚节点的处理能力、存储 能力和通信能力相对较强。它连接传感器网络和外部网络，实现两种协议栈之间 的通信协议转换，同时发布管理节点的监测任务，并把收集到的数据转发到外部 网络上。管理节点主要负责传感器网络配置和管理，发布监测任务以及收集监测 数据。大量传感器节点监测的数据沿着其它传感器节点逐跳进行传输，在传输过 程中监测数据可能被多个节点处理，经过多跳后路由到汇聚节点，最后通过互联 网、卫星或者移动通信网络到达管理节点。用户通过管理节点对传感器网络进行 配置和管理，发布监测任务以及收集监测数据。 2 1w s n 结构 图2 - 1传感器网络结构 2 1 1 节点结构 w s n 是由大量传感器节点组成的。传感器节点通常易于部署、成本低廉、 4 山东大学硕士学位论文 重量轻，同时支持一些基本功能，比如事件检测、分类、追踪以及汇报。在不同 应用中，传感器节点的组成不尽相同，但一般都由传感单元( 由传感器和模数转 换功能模块组成) 、处理单元( 由嵌入式系统构成，包括c p u 、存储器、嵌入式 操作系统等) 、通信单元( 由无线通信模块组成) 、以及电源部分1 刀组成，如图 2 2 所示。此外，可以选择的其它功能单元包括定位系统、移动系统以及电源自 供电系统等。 图2 - 2 传感器节点的组成 传感器网络中的传感器节点主要有两类：普通传感器节点和汇聚节点。汇聚 节点( s i n k ) 为一个特殊节点，它是中心处理节点，也称网关节点。该节点可向区 域内的普通传感器节点发送数据、采集命令，并接收和处理普通传感器节点传送 来的数据等。 2 1 2 网络体系结构 w s n 体系结构一般由网络通信协议、网络管理以及应用支撑技术三部分组 成，如图2 3 所示。这是目前w s n 研究的核心与关键。 1 网络通信协议 物理层：主要负责数据的调制、发送与接收。由于w s n 主要基于无线电通 信，故无线频段的选择、调制技术和扩频技术成为无线通信物理层协议的主要技 术。目前，人们对物理层的研究还处于初始阶段，其中减少系统功耗和降低硬件 成本一直是该研究的主要内容。 数据链路层：主要负责数据成帧、帧检测、介质访问和差错控制。其中介质 山东大学硕士学位论文 访l 口- j 控制( m e d i u ma c c e s sc o n t r o l ，m a c ) 协议更多地关注信道的有效利用，设计 节能的睡眠机制等方面【1 9 1 ，这是该层研究的重点。 图2 3 传感器网络体系结构 网络层：主要负责路由的生成与路由的选择，路由协议设计是该层需要解决 的主要问题。随着网络规模的扩大，路由的低能耗和可扩展性，路由对动态拓扑 的强烈适应性，成为人们研究w s n 路由的重点【2 0 】。 传输层：主要负责数据流的传输控制，在网络层的基础上为应用层提供一个 可靠的、高质量的数据传输服务。 应用层：包括一系列基于监测任务的应用层软件。 2 网络管理 拓扑控制：主要研究的问题是在满足网络覆盖率和连通度的前提下，通过功 率控制和骨干网节点选择，剔除节点之间不必要的通信链路，形成一个数据转发 的优化网络结构。根据拓扑控制的研究方向可以分为两类：节点功率控制和层次 型拓扑组织结构【2 1 】。 能量管理：管理传感器节点如何使用能量，各个协议层都需要考虑节省能量。 由于传感器节点的绝大部分能耗在无线通信模块上，故通信模块节能是研究的重 点。目前，研究人员提出的节能策略主要有休眠机制、数据融合、冲突避免与纠 错及多跳短距离通信等，并将其应用在计算模块和通信模块的各个环节。 安全管理：受限于传感器有限的运算速度、存储器及能量容量，传统网络的 安全机制并不能直接应用于w s n ，需要设计新型的网络安全机制。目前存在两 山东大学硕士学位论文 种思路：一种思路是从维护路由安全的角度出发，寻找尽可能安全的路由以保证 网络的安全；另一种思路是把重点放在安全协议方面。 t 3 支撑技术 节点定位t 节点的准确定位是w s n 应用的重要条件。采用g p s 是获得位置 信息的一种方法，但不适宜为每个节点都装配高能耗的g p s 设备，须在算法上 作出相应的补充。以是否实际测量节点间的距离或角度，定位算法可以分为基于 距离的定位和距离无关的定位2 2 1 。距离无关的定位机制能满足大多数w s n 应用 的要求，是目前重点关注的定位机制。 时间同步：时间同步机制是w s n 的一个关键机制。目前已提出的同步机制 中，r b s 、t i n y m i n i s y n c 和t p s n 被认为是三个基本的w s n 同步机制瞄】。 但由于这些机制往往以提高某些方面的性能为目的，因此，需要进一步地改进或 者设计新的机制来满足w s n 的要求。 2 2w s n 路由协议的特点和设计要求 w s n 路由协议具有以下特剧2 4 】： 1 能量优先 传统路由协议在选择最优路径时，很少考虑节点的能耗问题。而w s n 中节 点的能量有限，延长整个网络的生存周期成为w s n 路由协议设计的首要目标， 需要考虑节点的能耗以及网络能量均衡使用的问题。 2 基于局部拓扑信息 w s n 为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资 源和计算资源，使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。 在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单高效的路由机 制是w s n 的一个基本问题。 3 以数据为中心 传统的路由协议通常以地址作为节点的标识和路由的依据，而w s n 中大量 节点随机部署，所关注的是检测区域的感知数据，而不是具体哪个节点获取的信 息，不依赖于全网唯一的标识。w s n 通常包含多个传感器节点到基站的数据流， 按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发 7 山东大学硕士学位论文 路径。 4 应用相关性 w s n 的应用环境千差万别，数据通信模式不同，没有一个路由机制适合所 有的应用，这是w s n 应用相关性的一个体现。需要针对每一个具体应用的需求， 设计与之适应的特定路由机制。 基于以上特点，具体设计路由协议时，需要满足以下要求【2 4 】： 第一，能量有效性。由于w s n 节点能量有限，所以路由协议设计必须将有 效地利用能量放在第一位，将服务质量( q o s ) 放在第二位考虑，而且要从整个 网络的角度考虑，使整个网络能耗均匀。 第二，简单性。相对于传统网络而言，传感器节点的运算能力和存储能力极 其有限，这种硬件资源有限的节点却承担着数据采集和路由器的双重角色，这就 要求不能照搬传统网络路由协议的设计思想，而是要为这种节点资源有限的特殊 网络“量身定制”一种简单有效的路由协议，要求路由协议的报文和算法简单有 效。 第三，可扩展性。w s n 通常工作在恶劣的环境中，各种情况经常会使得节 点失效，或者有新节点加入等等，这些使得w s n 网络拓扑结构动态发生变化， 因此要求路由协议具有可扩展性，能够适应网络拓扑结构的动态变化。 第四，鲁棒性。能量耗尽或环境因素造成传感器节点的失效，周围环境影响 无线链路的通信质量以及无线链路本身的缺点等，这些不可靠因素要求w s n 路 由机制具有一定的容错能力，具有很好的鲁棒性。 第五，快速收敛性。传感器网络的拓扑结构动态变化，节点能量和通信带宽 等资源有限，因此要求路由机制能够快速收敛，以适应网络拓扑的动态变化，减 少通信协议开销，提高消息传输的效率。 2 3w s n 路由协议简要分析 与传统的无线a d h o c 网络不同，w s n 节点没有统一的标识，多对一通信； 节点数量大，随机分布，密度较大，产生大量的数据冗余；网络拓扑结构随时间 动态变化；节点资源局限强，生存周期短等，这些使得w s n 路由协议的设计极 富挑战性2 5 1 。针对w s n 中数据传送的特点和难题，研究人员提出了许多新的路 山东大学硕士学位论文 由协议，这些路由协议可以大致分为四类：泛洪式路由协议、以数据为中心的路 由协议、层次式路由协议和基于位置信息的路由协议。下面简要介绍现有的w s n 路由协议，并对这些典型路由协议进行分析和比较。 2 3 1 泛洪式路由协议 1 泛洪( f l o o d i n g ) 图2 - 4 泛洪路由机制不恿图 该技术适用于w s n 的最简单直接的路由算法，也是一种古老和传统的路由 技术，无需建立和维护网络的拓扑结构，每个接收到f l o o d i n g 消息的节点都以 广播方式转发该消息，直到数据包到达目的地或者达到预先设定的最大的跳数为 止，如图2 - 4 所示。这种路由算法适用于健壮性要求强的场合，但该算法存在着 “内爆”( i m p l o s i o n ) 、“重叠”( o v e r l a p ) 、“闭塞”( i m p l o s i o n ) 、传播时效性差和 盲目使用资源等缺陷【8 】【2 6 1 。 2 g o s s i p i n g 图2 - 5 闲聊法的数据重发现象示意图 g o s s i p i n g 2 7 1 ( 闲聊法) ，是扩散法的改进版本。闲聊法可节约能量，节点发送 数据，不像扩散法那样给它的每一个邻居节点都发送数据副本，而是随机选择某 一个邻居节点，向它发送一份数据副本。如果某一个邻居节点e ( 如图2 - 5 所示) 已收到它的邻居节点b 的数据副本，若再次收到，那么它将此数据副本发回到 9 山东大学硕士学位论文 它的邻居节点b ，然后再由b 随机选择一个邻居节点转发数据副本，这样就避免 出现信息爆炸的问题。但是仍然无法解决部分重叠现象和盲目使用资源问题，而 且数据传输平均时延拉长，传输速度变慢，增加了网络时延。 2 3 2 以数据为中心的路由协议 1 s p i n 路由协议 s p i n t 7 1 【8 ( s e n s o rp r o t o c o l sf o rl nf o r m a t i o nv i an e g o t i a t i o n ) 是- - 组以数据为 中心的自适应路由协议，通过协商机制来解决泛洪算法中的“内爆”和“重叠” 问题。传感器节点仅广播采集数据的描述信息，当有相应的请求时，才有目的地 发送数据信息，其过程如图2 - 6 所示。s p i n 协议中有3 种类型的消息，即a d v 、 r e q 和d a t a ，节点用a d v 宣布有数据发送，用r e q 请求希望接收数据，用 d a t a 封装数据。 s p i n 协议有4 种不同的形式，即s p i n p p 、s p i n e c 、s p i n b c 和s p i n r l ， 其中s p i n - p p 和s p i n e c 是面向点到点的通信方式的网络；s p i n b c 和s p i n r l 是面向广播通信方式的网络。 一一一 一一一 图2 - 6s p i n 协议示意图 s p i n 协议通过使用节点间的数据协商和资源自适应机制，大大节省了能耗， 延长了网络寿命。同时，由于每个节点只需要知道它的单跳邻居节点信息，网络 拓扑结构改变对它的影响只是局部的。但是，s p i n 的广播机制还存在着一定的 缺陷，不能保证数据包从采集节点经过多跳后完全交付到汇聚节点，可能出现“数 据盲点”，进而影响整个网络的信息收集。该组协议仅适用于规模较小的网络。 山东大学硕士学位论文 2 d d 路由协议 d d 【9 】【1 0 1 ( d i r e c t e d d i f u s i o n ，定向扩散) 是一种基于数据为中心查询的路由机 制。定向扩散路由机制可以分为请求扩散、梯度场建立以及数据传输三个阶段， 如图2 - 7 所示。首先，汇聚节点根据不同应用需求定义不同的“兴趣 消息，采 用泛洪的方法将兴趣广播到整个区域或部分区域内的所有传感器节点。同时，完 成从数据源到汇聚节点的梯度建立。如果数据源节点发现了感兴趣的目标，就沿 梯度方向发送低速率的探测数据，当汇聚节点收到来自于不同路径的探测数据 时，从其中选出一条“高效 的路径加强。最后，数据源将沿着加强路径以高速 率向汇聚节点传输数据。 a ) 请求扩散 b ) 梯度场建立c ) 数据传输 图2 7 定向扩散路由机制示意图 该算法引入了网络梯度的概念，可以找到从源节点到目标点的最优路径，并 使用了本地化算法，能够很好满足w s n 对节能、鲁棒性以及可扩展性的要求。 但由于采用了按需查询驱动的数据模型，不适用于环境监测等要求连续传递数据 的系统，且选择与查询相匹配的数据会使传感器节点消耗更多的能量。 2 3 3 层次式路由协议 1 l e a c h 路由协议 l e a c f i t l l 】【1 2 1 ( 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 ) 协议由m i t 的 h o i n z e l m a n 等人提出的第一个w s n 分簇层次路由协议，在w s n 路由协议中占 有重要地位，其后基于分簇的路由协议如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 山东大学硕士学位论文 协议，故在这里就不赘述了，l e a c h 协议如图2 - 8 所示。 图2 - 8l e a c h 协议 基于l e a c h 协议优良的属性和现有的问题，人们提出了许多的改进方案 【2 8 】【2 9 】【3 0 1 ，下面重点介绍l e a c h c 协议。 l e a c h - c 2 8 1 协议是在l e a c h 的基础上提出来的一种集中式的路由协议， 该协议有效地解决了聚类数目不确定和簇头节点选择最优化的问题。实验证明， 该协议和l e a c h 相比，有效地增加了基站接收到的数据量、延长了节点的生存 时间。 首先，该协议将节点当前能量作为簇头选择的条件。此时所有的节点不再是 等概率担任簇头，而是与当前的能量的多少成正比，当前能量较多的节点当选为 簇头节点的概率也要大一些。第i 个节点在时刻t 作簇头的概率为p 。( f ) ，其计算 等式如下： p i ( t ) = m i n 器鲫 ( 3 一1 ) 其中，k 是每一轮的簇头数，e i ( t ) 是第i 个节点当前的能量，e 洲( t ) 是n 个节点当前的能量之和，即e 删( t ) = e j ( t ) 。 j = l 其次，在每一轮的初始阶段，基站计算全网的平均能量，e e t o t a 1 ( t ) ，所有 j n 当前剩余能量低于这个值的节点不能当选为簇头，然后基站根据模拟退火算法 3 1 ( t h es i m u l a t e da n n e a l i n ga l g o r i t h m ) 在剩余节点中寻找最优分簇方案，最小化 其它节点与簇头的通信能耗。 总的来说，l e a c h c 相比l e a c h 协议，在簇头的选择和簇的形成2 方面 山东大学硕士学位论文 都有所改进，簇结构更合理和优化。但是，这两点改进需要额外的条件，即获得 节点当前剩余能量和全网的拓扑结构，实现这两个条件需要增加通信开销和协议 的复杂度。 2 t e e n 路由协议 t e e n 【l 别( 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 ) 路由协 议采用类似l e a c h 的分簇算法，只是在数据传送阶段使用不同的策略。t e e n 的具体做法是在协议中设置了硬、软两个阈值，以减少发送数据的次数。在每轮 簇头选择的时候将两个阈值广播出去。当监测数据第一次超过设置的硬阈值时， 节点把这次数据设为新的硬阂值，并在接下来的时隙内发送它。之后，只有监测 数据超过硬阈值并且监测数据的变化幅度大于软阈值时，节点才会传送最新的监 测数据，并将它设为新的硬阈值。 通过调节两个阈值的大小，可以在精度要求和系统能耗之间取得合理的平 衡。采用这样的方法，可以监视一些突发事件和热点地区，数据的传送量比主动 网络少，较大地节省能耗，适用于响应型的网络应用。仿真结果表明，t e e n 比 l e a c h 更有效。但t e e n 存在两个缺陷：如果某个节点的检测数据始终达不 到硬阈值，节点不会传送任何数据，也就无法知道这个节点是否失效，因此这个 方法不适用于周期性采样的网络；数据一旦符合阈值要求，节点立即传送，容 易造成信号干扰，如果采用t d m a 方式，则又会造成数据延迟。 3 p e g a s i s p e g a s i s t l 4 1 是l e a c h 的改进，其思想是：为了延长网络的生存周期，节点 只需要和它们最近的邻居节点之间进行通信。节点与汇聚节点间的通信过程是轮 流进行的，当所有节点都与汇聚点通信后，节点间再进行新一回合的轮流工作。 由于这种轮流通信机制使得能耗统一地分布到每个节点上，因此降低了整个传输 所需要的能耗。 不同于l e a c h 的多簇结构，p e g a s i s 协议在传感器节点中采用链式结构 进行链接，p e g a s i s 协议如图2 - 9 所示。运行p e g a s i s 协议时每个节点首先利 用信号的强度来衡量其所有邻居节点距离的远近，在确定其最近邻居的同时调整 发送信号的强度以便只有这个邻居能够接收到信息。其次，链中每个节点向邻居 节点发送接受数据，并且只选择一个节点作为链首向汇聚节点传输数据。采集到 山东大学硕士学位论文 的数据以点对点的方式传递、融合，并最终被送到汇聚节点。 fb si i _ j 图2 - 9p e g a s l s 链式结构示意图 优点：减少了l e a c h 在簇重构开销，并且通过数据融合降低了收发数据 的次数，从而降低了网络能耗。仿真表明：与l e a c h 相比，p e g a s i s 能够提 高网络的生存周期近2 倍。 缺点：协议假定每个传感器节点能够直接与汇聚节点通信，而在实际网络中， 传感器节点一般需要采用多跳方式才能到达汇聚节点；p e g a s i s 假定所有的传 感器节点都具有相同级别的能量，因此节点很可能在同一时间内全部死亡；尽管 协议避免了簇重构开销，但由于传感器节点需要知道邻居的能量状态以便传送数 据，协议仍需要动态调整拓扑结构。对那些利用率高的网络而言，拓扑的调整会 带来更大的开销；协议所构建的接链中，远距离的节点会引起过多的数据延迟， 而且链首节点的唯一性使得链首会成为网络的瓶颈。 2 3 4 基于位置信息的路由协议 o o 一。 o o 、 ：o o m 2 i 二_ o n o d e 图2 - 1 0g e a r 中递归的目标域数据传送 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 2 1 是充分考虑了能量有效性的 基于位置的路由协议。该算法在定向扩散算法的基础上做了一系列改进，也采用 了查询驱动数据传送模式，但g e a r 不像定向扩散算法那样，向整个网络广播 1 4 山东大学硕士学位论文 兴趣，而是利用位置信息，向某一个特定的区域进行兴趣的广播，然后根据位置 信息( 尽可能地选择最短路径) 和节点剩余能量的情况，将数据包发送到汇聚节 点。它传送数据分组到目标域中所有的节点的过程包括两个阶段：目标域数据传 送和域内数据传送，如图2 1 0 所示。 该方法将避免了大规模的扩散传播，减少了中间节点的数量，降低了路由建 立和数