（计算机系统结构专业论文）能量均衡的无线传感器网络分簇路由协议的研究.pdf

山东大学硕士学位论文 摘要 无线传感器网络是当前在国际上备受关注的、涉及多学科高度交叉、知识高 度集成的前沿热点研究领域。路由协议是无线传感器网络层的核心技术。从路由 的角度看，无线传感器网络有其自身的特点。在无线传感器网络中，节点能量有 限且一般没有能量补充，因此路由协议需要高效利用能量，同时传感器网络节点 数目往往很大，节点只能获取局部拓扑结构信息，路由协议要能在局部网络信息 的基础上选择合适的路径。此外，传感器网络的路由机制还经常与数据融合技术 联系在一起，通过减少通信量而节省能量。因此，传统无线网络的路由协议不适 应于无线传感器网络，无线传感器网络有其自身的特点。 在阅读了大量文献的基础上，本文以能量均衡高效为主线，研究了无线传 感器网络的路由协议。 首先针对经典分簇协议l e a c h 中存在的簇头随机选择和簇间通信代价大的 问题，提出了能量均衡消耗的分簇路由协议。通过简单的定位算法使所有场景中 的传感器节点得知自己的位置信息，节省了资源。在簇头选择方面，在网络初始 化时由基站来指定簇头节点；在簇头节点选择下任节点时，综合考虑能量距离等 因素，选择权重函数值最大的节点作为簇头，解决了簇头能耗不均衡及分布不均 匀的问题。 本文还对多跳路径上节点间的距离分布进行了分析。在通信过程中，每个 节点的能耗不一样，由于中间的节点除发送自己的数据包外，还要中继别节点的 数据包，因此，离基站越近的节点，中继的数据包越多，消耗的能量就越多，该 节点很快因能量耗尽而死去，从而使网络无法完全覆盖引起整个系统寿命很短。 由此可得，离基站越近的节点间隔越小，单跳传输能耗低，从而平衡整个系统的 能耗。本文分析在线性模型下节点个数和通信距离都一定的情况下，节点间距离 的分布问题，如何排列节点距离，使系统能耗最小，并且系统各节点能耗均衡。 最后针对大规模无线传感器网络的特点，提出了一种能量均衡的优化路径 的多跳路由协议e b a b 。该协议在分析了节点距离分布的基础上，将网络划分为若 干个同心圆环，每一层环均由簇头节点和成员节点组成，簇头节点负责采集数据 并向簇头发送，簇头节点负责环间的多跳转发。在簇间路由中引入了蚁群算法， 根据能量和距离寻找最优传输路径 4 1 。并提出了一个简单的拓扑规则使e b a b 更 加灵活且适用更加广泛。最后通过仿真证明，e b a b 协议可有效地降低通信能耗， 延长网络生命周期。 关键字：无线传感器网络；路由协议；能量均衡；蚁群算法：节点距离分布 i l 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 sa r ef o r e f r o n to fh o tr e s e a r c ha r e a si nt h ei n t e r n a t i o n a l c o m m u n i t yo fc u r r e n t l yc o n c e r n e d 、i n v o l v i n ga1 1 i g h l yc r o s s e ds u b je c ta n dh i g h l y i n t e g r a t e dk n o w l e d g e r o u t i n gp r o t o c o li s t h ec o r et e c h n o l o g yo fw s n w i r e l e s s s e n s o rn e t w o r kh a si t so w nc h a r a c t e r i s t i c sf r o mt h ep o i n to fv i e wo fr o u t i n g i n w i r e l e s ss e n s o rn e t w o r k s ，t h ee n e r g yo fn o d ei sl i m i t e da n dg e n e r a l l yc o u l dn o t r e p l e n i s h ，s ot h er o u t i n gp r o t o c o l h a v et ou s ee n e r g ye f f i c i e n t l y , m e a n w h i l et h e n u m b e ro fn o d e si nn e t w o r ka r eo f t e nl a r g e ，s ot h en o d ec a no n l ya c q u i r et h el o c a l t o p o l o g yi n f o r m a t i o nd e p e n dw h i c hr o u t i n gp r o t o c o lh a v et os e l e c ts u i t a b l ep a t h i n a d d i t i o n ，t h er o u t i n gm e c h a n i s mo fw s ni s o f t e na s s o c i a t e dw i t hd a t af u s i o n t e c h n o l o g y ，b yr e d u c i n gt r a f f i cl o a dt os a v ee n e r g y t h e r e f o r e ，t h et r a d i t i o n a lr o u t i n g p r o t o c o lf o rw i r e l e s sn e t w o r k a r en o ts u i t e dt ow s n ，w s nh a si t so w nc h a r a c t e r i s t i c s o nt h eb a s i so fr e a d i n gag r e a td e a lo fl i t e r a t u r e ，i nt h i sp a p e rw es t u d yr o u t i n g p r o t o c o lo f w s na l o n gt h el i n eo fe n e r g ye f f i c i e n t f i r s to fa l l ，i nc o n n e c t i o nw i t ht h ep r o b l e mo fl e a c h , w ep r o p o s eo u rp r o t o c o l ： b a l a n c e dc l u s t e rb a l a n c e de n e r g y ( b c b e ) i nt h i sp r o t o c o lw ep r o p o s eas i m p l e l o c a t i o na l g o r i t h mt om a k ea l lt h en o d e sk n o wt h e i rl o c a t i o ni n f o r m a t i o n i nt h e a s p e c to fc h o o s i n gc l u s t e rh e a d s ，w h e ni n i t i a l i z et h en e t w o r kb sd e s i g n a t ec l u s t e r h e a dn o d e s ；w h e ns e l e c tt h ea n c e s t o r , t h ec l u s t e rh e a d h a v et oc o n s i d e rf a c t o r ss u c ha s r e m n a n te n e r g ya n dd i s t a n c e t h i sm e t h o ds o l v e st h ep r o b l e mo fi m b a l a n c eo fe n e r g y c o n s u m p t i o na n dc l u s t e rh e a dd i s t r i b u t i o n i nt h i sp a p e r , w ea n a l y z et h ed i s t a n c eb e t w e e nn o d e so fm u l t i - h o pp a t h i nt h e c o m m u n i c a t i o np r o c e s s ，t h ee n e r g yc o n s u m p t i o no fe a c hn o d ea r en o tt h es a m e ， i i i 山东大学硕士学位论文 b e c a u s et h er e l a yn o d en o to n l yh a v et os e n di t so w n p a c k e t s ，b u ta l s or e l a yp a c k e t so f o t h e rn o d e s ，s ot h en e a r e rf r o mt h eb a s es t a t i o n ，t h em o r ep a c k e t sh a v et or e l a y ，t h e m o r ee n e r g yh a v et oc o n s u m p t i o n ，n o d e sw i l ld i es o o nd u et oe n e r g yd e p l e t i o n ，r e s u l t i nt h en e t w o r kc a l ln o tf u l l yc o v e rt h ea r e a s oi nt h i sp a p e r , w ea n a l y z et h ed i s t a n c e b e t w e e nn o d e si nt h ec a s eo ff i x e dn o d en u m b e ra n dd i s t a n c e f i n a l l yi nc o n n e c t i o nw i t ht h ec h a r a c t e r i s t i c so fl a r g es c a l ew i r e l e s ss e n s o r n e t w o r k s ，w ep r o p o s ee n e r g yb a l a n c e da n tb a s e dr o u t i n gp r o t o c o le b a b o nt h e g r o u n d so fa n a l y s i st h ed i s t a n c eb e t w e e nn o d e s ，w ed i v i d e dt h en e t w o r ki n t os e v e r a l c o n c e n t r i cr i n g s ，a n dw eg i v et h e i rn a m e “d o m a i n ”，w ed oi n t e r - c l u s t e rr o u t i n g b e t w e e nd o m a i n s i ni n t e r - c l u s t e rr o u t i n gw ei n t r o d u c et h ea n tc o l o n ya l g o r i t h m , a c c o r d i n gt oe n e r g ya n dd i s t a n c et of i n dt h eo p t i m a lt r a n s m i s s i o np a t hd i s t a n c e a t l a s t ，w ep u tf o r w a r das i m p l et o p o l o g yr u l e ，i no r d e rt om a k ee b a bm o r ef l e x i b l ea n d w i d e l ya p p l i e d s i m u l a t i o nr e s u l t ss h o wt h a te b a bc a l le f f e c t i v e l yr e d u c i n ge n e r g y c o n s u m p t i o n ，e x t e n d i n gt h en e t w o r kl i f et 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 ；e n e r g yb a l a n c e d ；a n t c o l o n ya l g o r i t h m ；d i s t a n c eb e t w e e nn o d e s 1 v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：三数 日 期：型q 2 1 生，芏 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 圣达导师签名_ 塑丛堡日期：竺! 呈：! ：之 山东大学硕士学位论文 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 t ) 、纳米材料、无线通信技术、 信号处理技术、计算机网络技术等的进步以及i n t e m e t 的迅猛发展，w s n 的研究 在多种应用方面取得了重大进展，各种技术评论杂志也一致看好w s n 蕴藏的巨 大应用潜力和商业价值。2 0 0 3 年2 月，美国m i t 技术评论杂志将w s n 列为 未来改变世界的1 0 大新兴技术之首 1 。2 0 0 3 年8 月出版的美国商业周干| j 杂志在其“未来技术专版”中发表文章指出，效用计算、传感器网络、塑料电子 学和仿生人体器官是全球未来的四大高科技产业，它们将掀起新的产业浪潮 2 。 美国今日防务杂志更认为w s n 的应用和发展，将引起一场划时代的军事技 术革命和未来战争的变革。可以预见，无线传感器网络将对人们的社会生活、产 业变革带来极大的影响和产生巨大的推动作用 3 4 。 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 在美国制定 5 。 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 t 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 的研究主要集中在节点层面和网络层面两大部分。节点层 面的研究内容主要包括传感器技术，低功耗芯片技术，无线通信技术 6 等；网 络层面的研究内容主要包括低能耗路由协议技术，低能耗m a c 协议，协同定位技 术，时钟同步技术 7 ，数据融合技术 8 等。国内w s n 的研究主要集中在穿戴式 计算、上下文感知环境、智能教室等领域方面，而支持w s n 的无线通信网络技术 的研究( 尤其是w s n 路由技术) 尚不多见。到目前，研究人员提出了诸如 s p i n 9 1 0 、d i 删e dd i f f u s i o n 1 1 1 2 、l e a c h 1 3 、t e e n 1 4 、p e g a s i s 1 5 】 等协议及其改进算法，在某些方面降低了w s n 的总体能耗，延长了网络的生存周 期。 1 2 研究目标和内容 尽管w s n 前景光明，但人们还需要很多努力。一个关键问题是使传感器的能 源供应能维持数年。这意味着利用太阳能或动能，或者说细调系统，这样它们就 只需要用很少的电池能源。由于w s n 节点8 0 的能耗集中在无线通讯模块上，因 此，开发能降低传感器节点能耗，延长网络生存周期的路由技术就成了w s n 研 究中的核心问题，也是当前国内外研究机构关注的焦点。研究表明 1 6 1 7 ：传 统的i n t e m e t 技术加上移动自组织网( m o b i l ea d h o cn 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 中 2 山东大学硕士学位论文 的大部分节点不像传统a d h o c 网络中的节点一样快速移动，因此没有必要花费 很大的代价频繁地更新路由表信息；中间节点上与具体应用相关的数据处理、融 合和缓存也显得很有必要。在密集分布的w s n 中，相邻节点间的距离非常短，低 功耗的多跳通信模式可以降低功耗，同时增加了通信的隐蔽性，也避免了长距离 的无线通信易受外界噪声干扰的影响。这些独特的要求和制约因素给w s n 的研 究提出了新的技术问题一如何保证w s n 能耗最小化、节点生存周期最大化、 能量负载均衡化和通信能力最优化等现实要求。 在阅读了大量文献的基础上，本文以能量有效性为主线，研究了无线传感 器网络的路由协议，本文的主要工作归纳如下： 1 针对分簇协议l e a c h 中存在的簇头随机选择和簇间通信代价大的问题，提出 了能量均衡消耗的分簇路由协议。在簇头选择方面，在网络初始化时由基站 来指定簇头节点；在簇头节点选择下任节点时，综合考虑能量距离等因素， 选择最佳适合系数最大的节点作为簇头，解决了簇头能耗不均衡及分布不均 匀的问题。最后通过仿真证明，b e b c 协议可有效地降低通信能耗，延长网络 生命周期。并通过实验分析其生命周期，能量消耗，接收数据量这三方面， 找到最优簇头数目。 2 简单的节点定位算法。节点的位置信息是无线传感器网络的一个重要条件。 在很多论文中，知道节点的位置信息是前提条件，如p e g a s i s 等。有些论文 中则不需要知道节点的位置信息，如l e a c h ，但是这也给l e a c h 协议带来 了不好的影响一簇头分布不均匀。而l e a c h - c 则是中央控制的l e a c h ，它 利用基站知道节点的位置信息来提高网络效率。所以节点位置信息对网络协 议来说非常重要。但是如果在每个传感器中安装定位系统则使网络运营成本 过高，而在本文中，场景中只需要两个节点安装定位系统，知道位置信息即 可。通过简单的定位算法使所有场景中的传感器节点得知自己的位置信息， 达到整个网络簇的分配均衡。 山东大学硕士学位论文 3 多跳节点间距离分布的分析。无线传感器网络的路由问题可以归结为：寻求 一条将数据从源节点传送到基站的最优路径，这条路径上节点在接收和转发 数据时所花费的能耗最小，同时整个网络的能耗处于一种均衡的状态。在通 信过程中，每个节点的能耗不一样，由于中间的节点除发送自己的数据包外， 还要中继别节点的数据包，因此，离基站越近的节点，中继的数据包越多， 消耗的能量就越多，该节点很快因能量耗尽而死去，从而使网络无法完全覆 盖引起整个系统寿命很短。由此可得，离基站越近的节点间隔越小，单跳传 输能耗低，从而平衡整个系统的能耗。本文分析在线性模型下节点个数和通 信距离都一定的情况下，节点间距离的分布问题，如何排列节点距离，使系 统能耗最小，并且系统各节点能耗均衡。 4 针对大规模无线传感器网络的特点，提出了一种能量均衡的优化路径的多跳 路由协议e b a b 。该协议在分析了节点距离分布的基础上，将网络划分为若 干个同心圆环，每一个环均由簇头节点和成员节点组成，簇头节点负责采集 数据并向簇头发送，簇头节点负责环间的多跳转发。在簇间路由中引入了蚁 群算法，根据能量和距离寻找最优传输路径。最后通过仿真证明，e b a b 协 议可有效地降低通信能耗，延长网络生命周期。 1 3 论文组织 第一章首先介绍了本文的课题背景，其次通过分析无线传感器网络的发展和 现有协议的不足，提出本课题的研究内容。 第二章粗略介绍了w s n 分层路由协议的特点及设计要求，对经典的分层路 由协议作了简要介绍和性能比较。 第三章针对无线传感器网络分簇协议l e a c h 协议的不足“由于簇头是随机 产生的，可能造成簇的分布不均衡从而网络能量消耗不均衡”，引出能量均衡的 4 路由协议一b c b e 。 第四章分析节点间最优距离分布，在这个基础上引入适用于大规模无线传感 器网络的路由协议一- e b a b 。 第五章对全文进行总结，并对今后的工作提出了展望。 山东大学硕士学位论文 第二章无线传感器网络分层路由协议分析 2 1w s n 路由协议概述 路由协议是无线传感器网络层的核心技术。从路由的角度看，无线传感器网 络有其自身的特点，它既不同于传统网络，又不同于移动自组织网络( m o b i l e a d h o cn e t w o r k ，m a n e t ) 。 路由协议是组网的基础，其主要任务就是建立能量高效的优化路径和可靠地 传输传感器节点到基站的数据。路由协议负责将数据分组从源节点通过网络转发 到目的节点，它主要包括两个方面的功能：寻找源节点和目的节点间的优化路径， 将数据分组沿着优化路径正确转发。a dh o e 、无线局域网等传统无线网络的首 要目标是提供高服务质量和公平高效地利用网络带宽，这些网络路由协议的主要 任务是寻找源节点到目的节点间通信延迟小的路径，同时提高整个网络的利用 率，避免产生通信拥塞并均衡网络流量等，而能量消耗问题不是这类网络考虑的 重点。在无线传感器网络中，节点能量有限且一般没有能量补充，因此路由协议 需要高效利用能量，同时传感器网络节点数目往往很大，节点只能获取局部拓扑 结构信息，路由协议要能在局部网络信息的基础上选择合适的路径。传感器网络 具有很强的应用相关性，不同应用中的路由协议可能差别很大，没有一个通用的 路由协议。此外，传感器网络的路由机制还经常与数据融合技术联系在一起，通 过减少通信量而节省能量。因此，传统无线网络的路由协议不适应于无线传感器 网络，无线传感器网络有其自身的特点。 2 2w s n 路由协议的特点和设计要求 与传统网络的路由协议相比，无线传感器网络的路由协议具有一下特点 1 8 ： 6 山东大学硕士学位论文 1 能量优先 传统路由协议在选择最优路径时，很少考虑节点的能耗问题。而w s n 中节 点的能量有限，延长整个网络的生存周期成为w s n 路由协议设计的首要目标， 需要考虑节点的能耗以及网络能量均衡使用的问题。 2 基于局部拓扑信息 w s n 为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资 源和计算资源，使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。 在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单高效的路由机 制是w s n 的一个基本问题。 3 以数据为中心 传统的路由协议通常以地址作为节点的标识和路由的依据，而w s n 中大量 节点随机部署，所关注的是检测区域的感知数据，而不是具体哪个节点获取的信 息，不依赖于全网唯一的标识。w s n 通常包含多个传感器节点到基站的数据流， 按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发 路径。 4 应用相关性 w s n 的应用环境千差万别，数据通信模式不同，没有一个路由机制适合所有 的应用，这是w s n 应用相关性的一个体现。需要针对每一个具体应用的需求，设 计与之适应的特定路由机制。 基于以上特点，具体设计路由协议时，需要满足以下要求1 1 8 ： 1 能量有效性。由于w s n 节点能量有限，所以路由协议设计必须将有效地利用 能量放在第一位，将服务质量( 0 0 s ) 放在第二位考虑，而且要从整个网络 的角度考虑，使整个网络能耗均匀。 2 简单性。相对于传统网络而言，传感器节点的运算能力和存储能力极其有限， 这种硬件资源有限的节点却承担着数据采集和路由器的双重角色，这就要求 山东大学硕士学位论文 不能照搬传统网络路由协议的设计思想，而是要为这种节点资源有限的特殊 网络“量身定制”一种简单有效的路由协议，要求路由协议的报文和算法简 单有效。 3 可扩展性。w s n 通常工作在恶劣的环境中，各种情况经常会使得节点失效， 或者有新节点加入等等，这些使得w s n 网络拓扑结构动态发生变化，因此要 求路由协议具有可扩展性，能够适应网络拓扑结构的动态变化。 4 鲁棒性。能量耗尽或环境因素造成传感器节点的失效，周围环境影响无线链 路的通信质量以及无线链路本身的缺点等，这些不可靠因素要求w s n 路由机 制具有一定的容错能力，具有很好的鲁棒性。 5 快速收敛性。传感器网络的拓扑结构动态变化，节点能量和通信带宽等资源 有限，因此要求路由机制能够快速收敛，以适应网络拓扑的动态变化，减少 通信协议开销，提高消息传输的效率。 2 3w s n 分层路由协议简要分析 针对无线传感器网络不同的应用场景，研究人员提出了各种不同的路由协 议，其中较为常见的主要有：f l o o d i n g 1 9 和g o s s i p i n g 2 0 、d d ( d i r e c t e d d i f f u s i o n ) 1 1 1 2 、s p i n ( s e n s o rp r o t o c o lf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 9 1 0 、r u m o r r o u t i n g 21 、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 ) 13 、 l e a c h - c ( l e a c h - c e n t r a l i z e d ) 2 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 t s e n s o rn e t w o r kp r o t o c 0 1 ) 14 、p e g a g 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 r i n f o r m a t i o ns y s t e m ) 1 5 、g e a r ( g e o g r a p h i c a la n de n e r g ya w a r er o u t i n g ) 2 3 。为 方便本课题的研究，本课题根据路由结构和路由策略分类，可以将上述路由协议 分为平面路由和分层路由两类 2 4 。在平面路由协议中，所有节点的都具有相同 的功能，以对等方式完成路由的建立、维护和数据中继。平面路由适用于规模较 小的网络，协议较为简单，效率较高：但是随着节点数量的增加、网络规模的扩 大，这类协议表现出扩展性差、效率下降的缺陷。这时，使用分层路由协议的效 率较高。在分层路由中，节点按功能被划分为簇成员节点和簇头节点，簇成员节 点负责监测环境，采集数据，并将采集到的信息发送到所在簇的簇头节点。而簇 头节点负责管理本簇的成员节点，给成员节点分配时间槽，收集成员节点的信息 进行融合处理并路由到基站。 w s n 分簇机制具有以下优点： 2 5 1 分簇路由协议使能量消耗均匀分布，能有效的延长网络寿命，平衡网络负载。 2 网络的通信分为簇内通信和簇间通信，簇头将成员节点收集来的信息融合处 理后，转发到基站，降低了发送信息量。 3 簇头分配给成员节点时间槽，成员节点只需在时间槽时打开通信模块，向簇 头传送数据，节省了网络能量。 4 成员节点的功能比较简单，无须维护复杂的路由信息。这大大减少了网络中 路由控制信息的数量，减少了通信开销和维护路由表所需的内存开销。 5 分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化作出快 速反应，具有较好的可扩展性，适合大规模网络。 目前，经典的分层路由协议有：l e a c h , t e e n , p e g a s i s 等。 2 3 1l e a o h l e a c h 1 3 ( 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 e 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 节约能量的主要原因就是它运用了动态分簇路由技术，通过本地 的联合工作来提高网络的可扩展性和鲁棒性，通过数据融合来减少发送的数据 量，通过把节点随机的设置成“簇头节点”来达到在网络内部负载均衡的目的， 防止簇头节点的过快死亡。 山东大学硕士学位论文 该算法将整个网络划分成若干个簇，每个簇由一个簇头节点和若干成员节 点( 非簇头节点) 组成，如图2 - 1 所示。 图2 1l e a c h 协议分簇示意图 l e a c h 协议中定义了“轮”( r o u n d ) 概念，每一轮分为2 个阶段，即：建 立阶段和稳定阶段。在建立阶段，通过选择使某个节点成为簇头节点，成为簇头 的节点向周围节点广播信息，其它节点根据接收到的广播信息的强度来选择它所 要加入的簇，并告知相应的簇头。在稳定阶段，非簇头节点把数据发送给自己的 簇头，簇头进行数据融合并把数据发送给基站。簇头节点工作任务比较繁重，需 要完成数据融合、与基站通信等任务，所以能耗较大。因此，每一轮结束需要重 新选择簇头。 基于l e a c h 协议优良的属性和现有的问题，人们提出了许多的改进方案 2 2 2 6 ，下面重点介绍l e a c h - c 协议。 l e a c h c 2 2 协议是在l e a c h 的基础上提出来的一种集中式的路由协议， 该协议有效地解决了聚类数目不确定和簇头节点选择最优化的问题。实验证明， 该协议和l e a c h 相比，有效地增加了基站接收到的数据量、延长了节点的生存 1 0 l l i 东大学硕士学位论文 时间。 首先，该协议将节点当前能量作为簇头选择的条件。此时所有的节点不再 是等概率担任簇头，而是与当前的能量的多少成正比，当前能量较多的节点当选 为簇头节点的概率也要大一些。第i 个节点在时刻t 作簇头的概率为p a t ) ，其 计算等式如下： p 。( t ) = r a i n 器蜘) ( 2 - 1 ) 其中，k 是每一轮的簇头数，e i ( t ) 是第i 个节点当前的能量，e 删( t ) 是n 个节点当前的能量之和，即e 洲( t ) = e j ( t ) 。 ( 2 - 2 ) 其次，在每一轮的初始阶段，基站计算全网的平均能量，即垦警熊，所有 n 当前剩余能量低于这个值的节点不能当选为簇头，然后基站根据模拟退火算法 2 7 ( 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 3 2t e e n t e e n 14 ( 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 存在两个缺陷：1 、如果某个节点的检测数据始终达 不到硬阈值，节点不会传送任何数据，也就无法知道这个节点是否失效，因此这 个方法不适用于周期性采样的网络：2 、数据一旦符合阈值要求，节点立即传送， 容易造成信号干扰，如果采用t d m a 方式，则又会造成数据延迟。 2 3 3p e g a $ l s p e g a s i s 1 5 是l e a c h 的改进，其思想是t 为了延长网络的生存周期， 节点只需要和它们最近的邻居节点之间进行通信。节点与基站间的通信过程是轮 流进行的，当所有节点都与基站通信后，节点间再进行新一回合的轮流工作。不 同于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 协议时每个节点首先利用信号的强度来衡量 其所有邻居节点距离的远近，在确定其最近邻居的同时调整发送信号的强度以便 只有这个邻居能够接收到信息。 回 图2 2p e g a s l s 链式结构示意图 优点：减少了l e a c h 在簇重构开销，并且通过数据融合降低了收发数据的 山东大学硕士学位论文 暑鼍詈! ! ! 詈詈皇穹皇詈詈鲁曼詈詈皇皇皇皇皇皇! 詈詈詈曼! 曼詈阜m m 2 m _ 鼍詈! 詈鼍詈鼍詈皇詈皇! 喜皇詈鼍! 詈詈! 皇詈詈皇皇詈詈! 暑皇鼍皇曼! 詈詈! ! 曼! 詈暑皇曼詈! 詈 次数，从而降低了网络能耗。仿真表明：与l e a c h 相比，p e g a s i s 能够提高网 络的生存周期近2 倍。 缺点：协议假定每个传感器节点能够直接与基站通信，而在实际网络中， 传感器节点一般需要采用多跳方式才能到达基站；p e g a s i s 假定所有的传感器节 点都具有相同级别的能量，因此节点很可能在同一时间内全部死亡；尽管协议避 免了簇重构开销，但由于传感器节点需要知道邻居的能量状态以便传送数据，协 议仍需要动态调整拓扑结构。对那些利用率高的网络而言，拓扑的调整会带来更 大的开销；协议所构建的接链中，远距离的节点会引起过多的数据延迟，而且链 首节点的唯一性使得链首会成为网络的瓶颈。 2 3 4 各路由协议的性能比较 对上述路由协议，从路由结构、路由策略、节能策略、网络生存时间，数 据融合、健壮性和路径等方面 2 8 总结表2 - 1 所示。 表2 1 各路由协议的性能比较 路由路由 提供网络以数提供 节能生存据为 数据健壮多路最佳 结构策略融合性径路径 q o s 策略时间中心支持 l e a c h层次主动是较好不是有 较好 否不是否 p e g a s i层次 主动是较好不是有较好否不是否 t e e n 层次主动是较好是有较好否不是否 2 4 本章小结 本章简要介绍了w s n 路由协议，并总结归纳了w s n 路由协议的特点及设计 要求，然后分析了w s n 分层路由协议的重要性和优势，分层路由是均衡w s n 能 量消耗的一个很好方法。最后对l e a c h 1 3 、删 1 4 、p e g a s i s 1 5 经典 分簇路由协议作了介绍并进行了性能比较。 山东大学硕士学位论文 第三章无线传感器网络能量均衡的分簇路由协议b c b e 3 1 问题的提出 本文的b c b e ( b a l a n c e dc l u s t e ra n db a l a n c e de n e r g y ) 协议根据l e a c h 协 议提出，避免l e a c h 中存在的缺点和不足。l e a c h 1 3 是通过等概率地随机循环 选择簇头，将整个网络的能量负载平均分配到每个传感器节点，从而达到降低网 络整体能耗、延长网络生命周期的目的。但是l e a c h 协议存在的缺点影响了整个 网络的能量均衡消耗。 通过研究发现l e a c h 选择簇头的方法无论从数量上还是分布的位置上都常 常呈现不稳定状态，即在一次选择中会出现簇头个数远远偏离期望值和簇头分布 位置集中在网络覆盖区域一侧的现象。当簇头个数太少时，失去分层的意义：当 簇头个数太多时，由于簇头节点要直接与远方的基站通信，发射功率较大，会导 致整个网络能耗过大；簇头位置过偏会导致部分节点簇内通信半径过大，能耗不 均匀，都会影响网络寿命，使得网络的负载平衡下降。上述现象的发生源于每次 簇头选择过程完全依赖于各节点产生随机数，随机数产生的不稳定性导致了簇头 状态的不稳定性。 b c b e 路由协议力求解决以下几个问题： 如何选择簇头节点使其在网络中均匀分布。由于簇头节点比成员节点消耗更 多的能量，簇头节点的选择应该是动态的和轮换的：为了保证网络能量消耗 均衡，簇头节点应均匀分布。 简单的节点定位算法。节点位置信息对网络协议来说非常重要。但是如果在 每个传感器中安装定位系统则使网络运营成本过高，如何充分利用最少的资 源使所有场景中的传感器节点得知自己的位置信息。 1 4 当簇头节点能量低于一定值的时候，如何选择下任簇头节点，以保证能量较 低的节点不会提前死掉。 最优簇头的个数，当簇头节点为多少个时，能够使整个网络的综合性能最优。 整个网络中能量是否均衡消耗。 3 2b c b e 网络模型和能量消耗模型 3 2 1 网络模型 本章采用的网络模型有以下特征： 传感器节点是随机分布在方形区域如图3 - 1 所示，1 0 0 个节点均匀分布在1 0 0 x1 0 0 平方米的区域内。 基站在方形区域的中心，基站的能源不限，具有相对较强的计算、存储能力。 所有传感器节点部署后不再移动，并具有相同的初始能量、处理信息能力和 数据融合功能。 其中有两个传感器节点装有定位系统，知道自己的位置信息。 所有传感器节点可以根据接收到信号的强弱计算出与发送信号节点的距离， 也可根据发送信息的远近来相应的调整功率。 。 。0 0 。 。 。0。 o 。 uu ) o u【) u 。 o 。 。00 。 3 三 。 。 。 。 n n 0 000g ，00o0。0 口 o o n0 。0 0 o。 。 。 。0 。0 。 。u0。0 。0o o oo 。n o 。 。 u 。 0 。： 0 o u 广、 。三。0 。：。o 。 v _ 3 2 2 能量消耗模型 图3 1节点分布图 每个无线传感器节点包括四部分：信息测量单元、信息处理单元、信息传输 单元和供电电源，前三部分工作都要消耗能量，但主要能耗在信息传输单元，它 包括信息的接收、发送和启动能量消耗，特别针对传感器网络小数据包短距离多 次传输的情况下，启动能量是主要能量消耗源。 无线通信模型如图3 - 2 所示。 k 比特 图3 2无线能耗模型 能量消耗模型为 1 3 ： 民( k ，d ) 号e 乙l c c ( k ) 也k 。，( k ，d ) 瓯伙) i 已。k ( k )