（计算机应用技术专业论文）面向能量优化的无线传感器网络分簇路由协议研究.pdf

济南大学硕 j 学位论文 曼曼曼曼! 曼曼皇皇曼曼! 曼! 曼曼曼皇曼曼皇曼曼曼! 曼! 曼! ! 曼曼曼曼i i i i 一, 曼曼! 曼曼皇! 曼蔓曼曼曼曼曼曼皇曼孽曼兰曼! 曼曼皇曼曼 摘要 无线传感器网络是由大量随机分布在监控区域内的传感器节点通过无线通信方 式形成的多跳自组织网络系统。传感器节点消耗能量的模块包括传感器模块、处理器 模块和无线通信模块。随着集成电路工艺的进步，处理器和传感器模块的功耗变得很 低，绝大部分能量消耗在无线通信模块上。因此如何有效地利用节点能量，延长网络 生命周期是无线传感器网络路由协议设计的首要目标。 本文总结归纳了无线传感器网络的体系结构和特点，综述无线传感器网络中典型 的平面路由协议和分簇路由协议，总结了分簇路由协议的优点。分簇路由协议是本文 研究的重点，研究分析分簇路由协议中最有代表性的l e a c h 协议的详细流程。 在理想网络模型下研究分簇路由协议每轮在不同阶段的能量消耗，分析簇首节点 数量、簇首节点的位置、簇的分布情况等因素对各阶段能量消耗的影响。对l e a c h 协议进行仿真实验并结合影响分簇路由协议能量消耗的相关因素分析l e a c h 协议中 存在簇首节点数量不固定、分簇不均匀、分簇带来的额外开销大、选择簇首时没考虑 节点剩余能量的缺点。在分析分簇路由协议各阶段能量消耗的基础上，针对l e a c h 协议存在的缺点提出了改进的分簇路由协议l e a c h 。f c ( f i xc l u s t e r ) 。与传统的分簇 路由协议动态成簇不同，l e a c h f c 采用固定簇的形式，汇聚节点根据网络中节点 的位置信息使用模拟退火算法优化初始簇首节点集合，并对网络中的节点分簇。此时 的簇结构使网络全局能量消耗最小化，并且分簇相对比较均匀。使用固定簇并且每个 簇中有一个簇首节点，不仅能保证每轮网络中的簇首节点数量是最优簇首数量，还可 以减少分簇带来的额外开销。l e a c h f c 的簇首选择机制分为两个阶段，在第一阶 段，网络中的簇首使用模拟退火算法优化选取的节点直到这些节点的剩余能量少于自 己簇内所有节点剩余能量的平均值，可以减少整个网络的能量消耗。当网络中节点剩 余能量差异较大时进入第二阶段，选取剩余能量最多的节点担任簇首，更注重节点能 量的均衡消耗。 通过n s 2 仿真软件进行仿真实验，仿真结果表明改进的分簇路由协议分簇相对 比较均匀，网络能量消耗、节点死亡率、网络生命周期、第一个死亡节点的存活时间 相关性能评价指标均优于l e a c h 协议，是一种能量高效的分簇路由协议。 关键词：无线传感器网络；路由协议；簇；簇首节点；生命周期 v 济南大学硕f j 学位论文 a bs t r a c t w i r e l e s ss e n s o rn e t w o r ki sam u l t i h o ps e l fo r g a n i z i n gs y s t e mm a d eu po fl a r g e n u m b e r so fs e n s o rn o d e sw h i c ha r er a n d o m l yd i s t r i b u t e di nt h em o n i t o r i n gr e g i o n a li na w i r e l e s sc o m m u n i c a t i o nw a y t h em o d u l e sw h i c h d i s s i p a t ee n e r g yi nas e n s o rn o d ei n c l u d e s e n s i n gu n i t ，p r o c e s s i n gu n i ta n dw i r e l e s sc o m m u n i c a t i o nu n i t a st h ed e v e l o p m e n to f i n t e g r a t e dc i r c u i tt e c h n o l o g y , t h ep o w e ro fp r o c e s s i n gu n i ta n ds e n s i n gu n i tb e c o m e sl o w e r a n dl o w e r , w i r e l e s sc o m m u n i c a t i o nu n i tc o n s u m e s m o s te n e r g yo fas e n s o rn o d e t h e r e f o r e ， h o wt ou s et h ee n e r g yi nn o d e se f f e c t i v e l yt op r o l o n gt h en e t w o r k sl i f e t i m ei st h ep r i m a r y o b j e c ti nt h ed e s i g no fr 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 i nt h i sp a p e r , w ec o n c l u d e dt h ea r c h i t e c t u r ea n dc h a r a c t e r so fw i r e l e s ss e n s o rn e t w o r k ， r e v i e w e df l a tr o u t i n gp r o t o c o la n dc l u s t e r i n gr o u t i n gp r o t o c o lt h e s et w oc l a s s i cr o u t i n g p r o t o c o l sa n dt h e nc o n c l u d e dt h ea d v a n t a g eo fc l u s t e r i n gr o u t i n gp r o t o c 0 1 w ep a i dm u c h a t t e n t i o nt oc l u s t e r i n gr o u t i n gp r o t o c o l ，a n a l y z e dt h ef l o wo fl e a c h p r o t o c 0 1 r e s e a r c h e de n e r g yd i s s i p a t i o no fc l u s t e r i n gr o u t i n gp r o t o c o li ne v e r yr o u n du n d e ra d e s i r e dn e t w o r km o d e l ，a n a l y z e dt h ee n e r g yd i s s i p a t i o ni n e v e r yp h a s ei n f l u e n c e db y n u m b e ra n dp o s i t i o no fc l u s t e r - h e a dn o d e sa n dt h ed i s t r i b u t i o no fc l u s t e r s m a d e s i m u l m i o no nl e a c h p r o t o c o la n da n a l y z e dt h ed i s a d v a n t a g eo fl e a c hp r o t o c o l ，w h i c h i n c l u d e st h en u m b e ro fc l u s t e rh e a d sn o tf i x e d ，c l u s t e r i n gu n e v e n ，e x t r as p e n d i n gl a r g ea n d s e l e c tc l u s t e r - h e a dw i t h o u tc o n s i d e r i n gt h er e s i d u a le n e r g y a f t e ra n a l y z i n gt h ee n e r g y d i s s i p a t i o ni ne v e r ys t a g eo fc l u s t e r i n gr o u t i n gp r o t o c o l ，p u ti na ni m p r o v e dc l u s t e r i n g r o u t i n gp r o t o c o ll e a c h - f c ( f i xc l u s t e r ) l e a c h f c ，w h i c hi sd i f f e r e n tf o r mc l a s s i c c l u s t e r i n gr o u t i n gp r o t o c o l s ，a d o p t sf i xc l u s t e r , s i n kn o d eo p t i m i z ei n i t i a lc l u s t e r - h e ms e t b yu s i n gs i m u l a t e da n n e a l i n ga c c o r d i n gt ol o c a t i o ni n f o r m a t i o no ft h en o d e sa n dc l u s t e r n o d e si nn e t w o r k t h ec l u s t e rs t r u c t u r ea f t e rc l u s t e r i n gw i l lm i n i m i z e e n e r g yd i s s i p a t i o no f t h ew h o l en e t w o r ka n dh a v eau n i f o r m c l u s t e r i n g u s i n gf i xc l u s t e ra n de v e r yc l u s t e rh a sa c l u s t e r - h e mn o to n l ym a k es u r et h a tt h en u m b e ro fc l u s t e r - h e a dp e r - r o u n di st h es a m ea s t h a to fo p t i m a lc l u s t e r - h e m ，b u ta l s od e c r e a s et h eo v e r h e a do fd y n a m i c a lc l u s t e r i n g t h e r e a r et w op h a s e si nc l u s t e r - h e a ds e l e c t i o nm e c h a n i s mo fl e a c h - f c ，i nt h ef i r s tp h a s e ，t h e c l u s t e r - h e a dn o d e sw h i c hw e r es e l e c t e du s i n gs i m u l a t e da n n e a l i n g a l g o r i t h mu n t i lt h en o d e v i i 而向能7 - 优化的无线传感器网络分簇路由协议研究 r e s i d u a le n e r g yi sl e s st h a nt h ea v e r a g er e s i d u a le n e r g yo fa l ln o d e sw i t h i ni t so w n c l u s t e r , w h i c hc a nr e d u c en e t w o r k se n e r g yd i s s i p a t i o n i fn o d e sh a v eb i gd i f f e r e n c ei nr e s i d u a l e n e r g y ，t h es e c o n dp h a s ew i l lb ec a r r i e do u t t h en o d e 、析t hm o s tr e s i d u a le n e r g yi s s e l e c t e da sc l u s t e r - h e a d ，w h i c hc a nr e a l i z et h eb a l a n c eo fe n e r g yc o n s u m p t i o n w em a d es i m u l a t i o nb yu s i n gn s 2 ，s i m u l a t i o nr e s u l ts h o w st h a tl e a c h - f ci sa n e n e r g ye f f i c i e n c y c l u s t e r i n gr o u t i n gp r o t o c o l ，t h ep e r f o r m a n c ee v a l u a t i o n si ne n e r g y d i s s i p a t i o n ，r a t eo fn o d e s ，n e t w o r k sl i f e c y c l ea n ds u r v i v a lt i m eo ft h ef i r s t d e a d n o d ea le b e t t e rt h a nl e a c h p r o t o c 0 1 k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ；r o u t i n gp r o t o c o l ；c l u s t e r ；c l u s t e r - h e a dn o d e ；l i f e t i m e v i i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借鉴；本人授权济南大学可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保 存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：型丝毖导师签名： 第一章绪论 1 1 研究背景 传感器是数据采集、信息处理的关键部件，是新技术革命和信息社会的重要技术 基础。传感器技术与通信技术、计算机技术构成信息产业的三大支柱。随着超大规 模集成电路的飞速发展，现代计算机技术和通信技术的进步，传感器技术正向着集成 化、微型化、智能化、网络化的方向发展。研究表明，只有网络化的智能传感器技术 才能适应各种控制系统对自动化水平、对象复杂性以及环境适应性越来越高的要求。 从而出现无线传感器网络( w s n ，w i r e l e s ss e n s o rn e t w o r k ) 技术和相应的应用。 无线传感器网络是一种特殊的a d h o e 网络，可应用于布线和电源供给困难的区 域、人员不能到达的区域( 如受到污染、环境不能被破坏或敌对区域) 和一些临时场 合( 如发生自然灾害时，固定通信网络被破坏) 等。它不需要固定网络支持，具有快 速展开，抗毁性强等特点，可广泛应用于军事、工业、交通、环保等领域，引起了人 们广泛关注。 传感器节点消耗能量的模块包括传感器模块、处理器模块和无线通信模块。随着 集成电路工艺的进步，处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无 线通信模块上。传感器节点传输信息时要比执行计算时更消耗电能，传输1 比特的信 息1 0 0 m 距离所需要的能量大约相当与执行3 0 0 0 条计算指令消耗的能量1 1 。3 】。因此无 线传感器网络中的路由协议成为一个重要研究方向。 1 2 无线传感器网络概述 无线传感器网络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过 无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处 理网络覆盖区域中感知对象的信息，并发送给观察者。 1 2 1 传感器节点的构成 在不同的应用中，传感器节点的设计也各不相同，但是它们一般都包括四个基本 模块：传感器模块、处理器模块、无线通信模块和能量供应模块。无线传感器网络节 点的结构图如图1 1 所示。传感器模块负责监测区域内信息的采集和数据转换；处理 1 而向能帚优化的无线1 9 感器网络分簇路l 协议研究 器模块负责控制整个传感器节点的操作，存储和处理本身采集的数据以及其它节点发 来的数据；无线通信模块负责与其它传感器节点进行无线通信，交换控制信息和收发 采集数据；能量供应模块为传感器节点提供运行所需的能量，通常采用微型电池。此 外可选择的其他功能单元有定位装置、自动移动装置等。 图1 1 无线传感器节点的结构图 1 2 2 无线传感器网络的体系结构 传感器 监测区 图1 2 无线传感器网络体系结构 无线传感器网络典型工作方式如下：传感器节点进行随机撒放，包括人工、机械、 空投等方法，抛撤到感兴趣区域。撒放后的传感器节点进入到自检启动的唤醒状态， 每个传感器节点会发出信号监控并记录周围传感器节点的工作情况。这些传感器节点 2 济雨大字坝_ | 等：俺论文 根据监控到的周围传感器节点的情况，采用一定的组网算法，形成按一定规律结合成 的网络。组成网络的传感器节点根据一定的路由算法选择合适的路径进行数据通信。 每个传感器节点既是信息的采集者又是信息的发出者，也充当信息的路由者，采集的 数据通过多跳路由到达汇聚节点( s i n kn o d e ，一些文献也称为网关) 。汇聚节点是一 个特殊的节点，可以通过i n t e m e t 、移动通信网络、卫星等与监控中心通信。图1 2 为无线传感器网络的体系结构。 1 2 3 无线传感器网络的特点 目前常见的无线网络包括移动通信网、无线局域网、蓝牙网络、a dh o c 网络等， 与这些网络相比，无线传感器网络具有以下特点【1 4 】： ( 1 ) 硬件资源有限。节点由于受价格、体积和功耗的限制，其计算能力、程序空 间和内存空间比普通的计算机功能要弱很多。这一点决定了在节点操作系统设计中， 协议层次不能太复杂。 ( 2 ) 电源容量有限。传感器节点一般是由电池供电，电池的容量一般不是很大。 其特殊的应用领域决定了在使用过程中，不能给电池充电或更换电池，一旦电池能量 用完，这个节点也就失去了作用( 死亡) 。因此无线传感器网络设计过程中，任何技 术和协议的使用都要以节能为前提。 ( 3 ) 无中心。无线传感器网络中没有严格的控制中心，所有节点地位平等，是一 个对等式网络。节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的 运行，具有很强的抗毁性。 ( 4 ) 自组织。网络的布设和展开无需依赖于任何预设的网络设施，节点通过分层 协议和分布式算法协调各自的行为，节点开机后就可以快速、自动组成一个独立的网 络。 ( 5 ) 多跳路由。网络中节点通信距离有限，一般在几百米范围内，节点只能与它 的邻居直接通信。如果希望与其射频覆盖范围之外的节点进行通信，则需要通过中间 节点进行路由。固定网络的多跳路由使用网关和路由器来实现，而无线传感器网络中 的多跳路由是由普通网络节点完成的，没有专门的路由设备。这样每个节点既可以是 信息的发起者，也是信息的转发者。 ( 6 ) 动态拓扑。无线传感器网络是一个动态的网络，节点可以随处移动；一个节 点可能会因为电池能量耗尽或其他故障，退出网络运行；一个节点也可能由于工作的 3 面向能荦| 1 苊化的_ ) 线传感器网络分簇路i h 协议研究 需要而被添加到网络中。这些都会使网络的拓扑结构随时发生变化，因此网络应该具 有动态拓扑组织功能。 ( 7 ) 节点数量众多，分布密集。为了对一个区域执行监测任务，往往有成千上万 传感器节点空投到该区域。传感器节点分布非常密集，利用节点之间高度连接性来保 证系统的容错性和抗毁性。 ( 8 ) 传感器节点主要采用广播方式通信。由于无线传感器网络中节点数目庞大， 使得其在组网和通信时不可能如a dh o e 网络那样采用点对点的通信，而要采用广播 方式，以加快信息的传递速度和范围。 ( 9 ) 以数据为中心。在无线传感器网络中人们只关一1 1 , 某个区域的某个观测指标的 值，而不会去关一i i , 具体某个节点的观测数据，这就是无线传感器网络以数据为中心的 特点。 1 3 本文的主要工作与组织结构 1 3 1 本文的主要工作 总结归纳无线传感器网络的系统结构和特点，综述无线传感器网络中典型的平面 路由协议和分簇路由协议，总结分簇路由协议的优点。 在理想网络模型下研究分簇路由协议每轮在不同阶段的能量消耗，分析簇首节点 数量、簇首节点的位置、簇的分布情况等因素对各阶段能量消耗的影响。重点研究分 簇路由协议中最有代表性的研究l e a c h 协议的详细流程，对l e a c h 协议进行仿真 实验并结合影响分簇路由协议能量消耗的相关因素分析l e a c h 协议中存在的缺点。 在分析分簇路由协议各阶段能量消耗的基础上，针对l e a c h 协议存在的缺点以 能量优化为目标提出一种改进的分簇路由协议l e a c h f c ，通过仿真实验，使用网 络能量消耗、节点死亡率、网络生命周期、第一个死亡节点的存活时间相关性能指标 评价能量优化的有效性。 1 3 2 本文的组织结构 第一章，介绍无线传感器网络的基础知识，包括传感器节点的构成、无线传感器 网络的体系结构、无线传感器网络的特点。 第二章，根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面 路由协议和分簇路由协议。综述线传感器网络中典型的平面路由协议和层次路由协议 4 济雨火号：硕 ：学何论文 并分析其优缺点，总结分簇路由协议相对平面路由协议的优点。 第三章，在一种理想的网络模型下分析分簇路由协议各个阶段的能量消耗情况以 及簇首节点数量、簇首节点的分布等相关因素对各阶段能量消耗的影响。 第四章，介绍分簇路由协议中最有代表性的研究l e a c h 协议的详细流程，并分 析l e a c h 协议的缺点。 第五章，在分析分簇路由协议各阶段能量消耗的基础上，针对l e a c h 协议存在 的缺点以能量优化为目标提出一种改进的分簇路由协议l e a c h f c 。描述l e a c h f c 中确定最优簇首节点数量的方法、簇的建立方式、簇首选择机制、通信方式。 第六章，通过n s 2 仿真平台对l e a c h f c 进行仿真实验，分析仿真结果验证改 进分簇路由协议的能量优化有效性。 第七章，总结全文并展望未来的研究方向。 济南大学硕f j 学位论史 第二章典型的无线传感器网络路由协议介绍 根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面路由协议 和分簇路由协议。平面路由简单，健壮性好，但建立、维护路由的开销大，数据传输 跳数多，适合小规模网络；分簇路由扩展性好，适合大规模网络，但簇的维护开销大， 且簇首是路由的关键节点，其失效将导致路由失败。 2 1 平面路由协议 2 1 1f l o o d i n g 和g o s s i p i n g f l o o d i n 9 1 5 1 是一种传统泛洪式路由技术，它不需要维护网络拓扑结构和计算路由。 接收到数据包的节点以广播形式转发给所有的邻近节点，重复执行此过程，直到数据包 到达目的地或者达到预先设定的最大跳数。 优点：实现简单；不需要为保持网络拓扑信息和实现复杂的路由发现算法而 消耗计算资源；适用于健壮性要求高的场合。 图2 1 信息爆炸问题 缺点：存在信息爆炸( i m p l o s i o n ) i h 题，即出现一个节点可能得到一个数据多个 副本的现象，如图2 1 所示；出现部分重叠( o v e r l a p ) 现象，如果处于同一观测环境 的两个相邻同类传感器节点同时对一个事件做出反应，二者采集的数据性质相同，数 值相近，那么，这两个节点的邻居节点将收到双份数据副本，如图2 2 所示；盲目 使用资源，即扩散法不考虑各节点能量可用状况因而无法做出相应的自适应路由选 择。 g o s s i p i n g 5 】对f l o o d i n g 进行了改进，接收到数据包的节点随机地选择一个没有发 送数据的邻居节点，把数据包传送过去，通过持续执行这个过程达到传播数据的目的 7 面向能黾：优化的无线传感器m 络分簇路f h 协议研究 闲聊算法通过随机选取节点进行有目的的传播，从而避免了信息爆炸的问题，但是这种 方法延长了信息传播的时间。 图2 2 重叠问题 2 1 2s p i n 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 ) 6 】是一种以数据为中心的自 适应通信路由协议。其目标是通过使用节点间的协商制度和资源自适应机制，解决 f l o o d i n g 存在的不足。 为了避免出现f l o o d i n g 中的信息爆炸问题和部分重叠现象，传感器节点在传送数 据之前彼此进行协商，协商制度可确保传输有用数据。节点间通过发送元数据( 即描 述传感器节点采集的数据属性的数据，m e t a - d a t a ) ，而不是采集的整个数据进行协商。 由于元数据大小小于采集的数据，所以传输元数据消耗的能量相对较少。为避免盲目 使用资源，所有传感器节点必须监控各自的能量变化情况。在传输或接收数据之前， 每个节点都必须检查各自可用的能量状况，如果处于低能量水平，必须中断一些操作， 比如充当路由器的角色，停止对其他节点的一些数据转发操作。 s p i n 有3 种数据包类型，即a d v 、r e q 和d a t a 。 a d v 用与新数据广播。当一个节点有数据可共享时，它可用a d v 数据包( 包含 元数据) 对外广播。 r e q 用与请求发送数据。当一个节点希望接收d a t a 数据包时，发送r e q 数据 包。 d a t a 数据包包含附上元数据头( m e t a - d a t ah e a d e o 的传感器采集到的数据。 s p i n 协议族有四种不同的形式：s p i n p p ( at h r e e s t a g eh a n d s h a k ep r o t o c o lf o r p o i n t - t o - p o i n tm e d i a ) 、s p i n e c ( s p i n p pw i t hal o w e n e r g yt h r e s h o l d ) 、s p i n b c ( a t h r e e s t a g eh a n d s h a k ep r o t o c o l f o rb r o a d c a s tm e d i a ) 、s p i n - r l ( s p i n - b cf o r l o s s y 8 济南大学硕 学位论丈 n e t w o r k s ) 。 s p i n p p 采用点到点的通信模式，并假设两节点问的通信不会受到其它节点的干 扰，分组不会丢失，功率没有任何限制。在发送一个d a t a 数据包之前，一个传感 器节点首先对向邻居节点广播a d v 数据包；如果一个邻居节点在收到a d v 后有意 愿接收该d a t a 数据包，那么它向该节点发送一个r e q 数据包，接着节点向该邻 居节点发送d a t a 数据包。类似地进行下去，d a t a 数据包可被传输到远方汇节点 或基站，如图2 3 所示。图中( 1 ) 节点a 先向b 扩散a d v 包。( 2 ) b 向a 发送r e q 包。( 3 ) a 向b 发送d a t a 数据包。( 4 ) b 向它的邻节点扩散a d v 包。( 5 ) 希望得 到d a t a 数据包的节点向b 返回r e q 包。( 6 ) b 向发送来r e q 包的节点发送d a t a 数据包。 ( 3 ) ( 2 ) ( 4 ) ( 5 ) ( 6 ) 图2 3s p i n p p 协议 s p i n e c 在s p i n p p 的基础上考虑了节点的功耗，只有能够完成所有任务并且 能量不低于设定阈值的节点才可以参与数据交换。 s p i n b c 设计了广播信道，使所有在有效通信范围内的节点可以同时完成数据交 换。发送a d v 包的节点只须要广播一次d a t a 数据包，所有向该节点发送r e q 包 的节点就可以收到数据。为了防止产生重复的r e q 请求，节点在收到a d v 包后， 9 面向能军优化的无线f 感器网络分簇路f f l 协议研究 设置一个随机定时器来控制r e q 请求的发送，当节点侦听到信道中有与自己相同的 r e q 请求时，主动放弃发送r e q 请求，如图2 4 所示。图中( 1 ) 节点a 向它所有 的邻节点广播a d v 包。( 2 ) 节点c 广播r e q 请求，并且抑制节点d 发送r e q 请求， 只有发送a d v 包的源节点a 才接收a e q 请求。( 3 ) a 节点接收到r e q 请求后，广 播d a t a 数据包。( 4 ) 节点e 的请求也被抑制，节点c 、d 、e 向它们的邻节点广播 a d v 包。 ( 3 )( 4 ) 、pp” ( a ) = 没有数据的节点ej = 等待发送r e q 的节点 o = 有数据的节点o = 通信范围 图2 4s p i n b c 协议 s p i n r l 是对s p i n b c 的完善。主要考虑如何恢复无线链路引入的分组差错和 丢失。记录a d v 消息的相关状态，如果在确定时间间隔内接收不到请求数据，则发 送重传请求，重传请求的次数有一定的限制。 s p i n 协议的优点：通过协商机制处理信息冗余，能够节省大量能量，很好的 解决了传统的f l o o d i n g 和g o s s i p i n g 协议所带来的信息爆炸和部分数据重叠的问题； 当拓扑结构和节点位置变化时，节点只需要知道单跳的邻居节点，不需要其它拓扑 信息。 缺点：可靠性差，当产生或收到数据的节点的所有邻节点都不需要该数据时， 将导致数据不能继续转发，以致较远节点无法得到数据；( 室) s i n k 节点周围的节点能量 容易耗尽，缩短了整个网络的生命周期。 1 0 济南大学硕 学位论文 2 1 3d d 定向扩散( d i r e c t e dd i f f u s i o n ) 【7 1 是一个重要的基于数据的、查询驱动的路由协 议。该协议用属性值对命名数据。汇聚节点通过兴趣消息( 实质上是用于表示查询 的任务) 发出查询任务，采用泛洪方式传播兴趣消息到整个区域或部分区域的所有传 感器节点。每个节点在本地保存一个兴趣列表，对于每个兴趣，列表中都有一个表项 记录发来该兴趣消息的邻居节点、数据发送速率和时间戳等任务相关信息。在兴趣消 息传播的过程中，协议逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的 数据传输梯度。传感器节点沿着梯度方向选择一条最优路径将采集到的数据传送到汇 聚节点。 定向扩散路由机制可分为周期性的兴趣扩散、梯度建立以及路径加强三个阶段。 图2 5 显示了这三个阶段的数据传播路径和方向。 2 1 4r u m o r s i n k ( 1 ) 兴趣广播 s s o u r c e o o s i n k ( 2 ) 梯度建立( 3 ) 路径加强 图2 5 定向扩散路由机制 s i n k 定向扩散协议需要经过查询消息的泛洪发送和路径增加机制才能确定一条优化 的数据传输路径，当网络的传输数据量很少时，定向扩散协议的开销显得太大， r u m o r 8 1 协议正是为解决此问题而设计的。该协议借鉴了欧氏平面图上任意两条曲线 交叉几率很大的思想。 r u m o r 协议的基本思想是：当节点监测到事件后将其保存，并创建称为a g e n t 的 生命周期较长的包括事件和源节点信息的数据包，将其按一条或多条随机路径在网络 中转发。同时汇聚节点发出的查询请求也沿着一条随机路径转发，当代理消息和查询 消息的传输路径交叉在一起时，将会形成一条汇聚节点到事件区域的完整路径。如果 1 l 面向能量优化的无线传感器m 络分簇路巾协议研究 查询节点在一段时间没有收到事件消息，就认为查询消息没有到达事件区域，可以选 择重传、放弃或泛洪查询消息的方法。 优点：与定向扩散协议相比，有效减少了路由建立的开销；适合用与查询请 求数目很大，网络事件很小，数据传输量很小的传感器网络。 缺点：由于使用随机方式生成路径，所以数据传输路径不是最优路径，并且可能 存在路由环路问题。 2 1 5 能量感知路由协议 能量感知路由协议【l l 】类似于d d 协议，但它不强迫使用一个最优化路径，可以防 止过分依赖某条路径而导致该路径上的节点能量消耗过大而过早失效。该协议的主要 思想是：使用地理位置和节点类型标识节点，在源节点和目的节点之间建立多条路径， 根据路径上节点的通信能量消耗以及节点的剩余能量情况，给每条路径赋予一定的选 择概率，使得数据传输均衡消耗整个网络的能量，延长整个网络的生存期。 优点：随机选择路由方式平衡了通信量。 缺点：随机选择一条路径导致其可靠性不如定向扩散协议；该路由协议需 要收集位置信息并建立编址机制，增加了路由建立的复杂度。 2 2 分簇路由协议 2 2 1l e a c h l e a c h t l 2 1 是一种自组织自适应分簇路由协议。l e a c h 中定义了“轮”( r o u n d ) 的概念，每轮由簇的建立阶段和稳定的数据通信阶段两个阶段组成。在簇的建立阶段， 相邻节点动态地形成簇，随机产生簇首；在数据通信阶段，簇内节点把数据发送给簇 首节点，簇首节点进行数据融合并把结果发送给汇聚节点。 为了保持网络内节点能量的均衡消耗，簇首周期性按轮随机选举，每轮选举方法 是：节点n 产生一个【0 ，1 】之间的随机数，如果这个数小于阈值t ( n ) ，这个节点将成 为这一轮的簇首。t ( n ) 的计算公式如下： 丁( 刀) ： f 厅g ( 2 1 ) o t h e r w i s e p 为网络中簇首节点数量与总节点数量的百分比，为当前的轮数，g 为最近l 仞 1 2 砑o 济南大学硕 学位论文 轮没有成为过簇首的节点集。 优点：使各节点等概率地担任簇首，保持网络内节点能量的均衡消耗，延长了整 个网络的生命周期。 缺点：0 3 l e a c h 使用单跳路由，要求每个节点都可以与汇聚节点直接通信，不 适合用与大规模的网络，可扩展性差；动态分簇带来了簇头变换和大量广播这样的 额外开销，并且簇首数量不固定分簇不均匀，选择簇首时没有考虑节点剩余能量。 2 2 2p e g a s i s 和h i e r a r c h i c a l p e g a s i s p e g a s i s 1 3 1 协议是对l e a c h 协议的改进。该协议假设传感器网络中所有节点都 知道其它节点的位置信息。为了避免l e a c h 协议的动态分簇带来的开销，传感器 节点利用贪婪算法形成链，每一个节点都通过其邻居节点进行数据的收发，利用令牌 ( t o k e n ) 控制链两端数据沿链传送到链头，在传送过程中可融合数据并且在该链中只有 链头节点与汇聚节点进行通信。链头的选取方法：设网络中n 个节点都用从1 到n 的自然数编号，第j 轮选取的链头是第i 个节点，i = jm o d n 。 优点：采用无通信量的链头选举方法，避免了l e a c h 协议频繁动态的选取簇 首带来的开销；采用链式数据融合，极大地减少了数据传输次数和通信量；节点 采用小功率与最近距离邻节点通信，形成多跳通信方式，有效地利用了能量。 缺点：与汇聚节点通信的链头节点可能会成为网络通信的瓶颈；链中的远距 离节点会带来过多的延迟。 h i e r a r c h i c a l p e g a s i s 是对p e g a s i s 的扩展，其目的是减小数据传输到汇聚节 点过程中带来的延迟，在能量和时延之间找到平衡点。该协议中采用了信息同时传输 的方式。 2 2 3t e e n 和a p t e e n t e e n l l 4 1 和l e a c h 的实现机制非常相似，只是前者是响应型的，而后者属于主 动型。主动型传感器网络持续监测周围的物质现象，并以恒定速率发送监测数据；而 响应型传感器网络只是在被观测变量发生突变时才传送数据。 分簇完成后汇聚节点通过簇首向所有节点通告两个门限值( 分别称为硬门限和软 门限，硬门限是可以激活传感器节点的最小属性值，软门限是感知属性值的变化幅度) 来过滤数据发送。在节点第一次监测到的数据超过硬门限时，节点向簇首上报数据， 并将当前监测数据保存为监测值( s v ) 。此后只有在监测到的数据比硬门限大且其与 1 3 面向能量优化的无线传感器网络分蔟路【t j 协议研究 i s v 之差的绝对值大于软门限时，节点才向簇首上报数据，并将当前监测数据保存为 s v 。 优点：通过设置软硬门限减少了数据的传输量；层次型簇结构不要求节点有 大功率的通信能力。 缺点：不适合周期性上报数据的应用；如果监测值没有超过硬门限，将无法 获得任何数据。 a p t e e n 是对t e e n 协议的扩展，平时采用与t e e n 协议一样的工作方式，但 是如果超过一定的时间，节点没有发送任何数据，则强制要求节点传送一次数据。在 一定程度上克服了t e n n 中监测值不能超过硬门限时无法进行通信的缺陷。 2 2 4h e e d h e e d 1 6 1 假设网络中的节点发送数据时可以选择不同的传输功率。节点的剩余能 量作为主要因素产生一定数量的临时簇首，节点的剩余能量越多，成为临时簇首的初 始概率越大。 c h p r o b = m a x ( 芒叫 包2 ， l 芒矾蛔j q 2 c p r o b 是簇首节点的百分比( 例如5 ) ，e r , 酊是节点的剩余能量，易蛾是节点最大 能量。为了保证算法在o ( 1 ) 次迭代内完成，g 砌不能小于阈值加。 h e e d 算法初始化时，每个节点确定在自己射频覆盖范围内邻节点的集合，计算 并广播本节点到每个邻节点的最小平均可达功率( a m r p ) ，计算自己成为临时簇首的 初始概率c h 。r o b 。然后每个节点通过o ( 1 ) 次迭代确定簇首，节点的剩余能量越多，迭 代次数越少。 迭代过程中，如果节点发现邻节点中有临时簇首，就选择代价最小的作为自己的 临时簇首；如果邻节点中没有临时簇首，就将本节点的6 乘以2 ，并以新的嘶 推荐自己为临时簇首，如果推荐成功，广播一个消息声明自己成为临时簇首。当 c 兄r 口6 的值达到1 时，算法做最后一次迭代，临时簇首宣布自己成为簇首。 如果在节点的射频覆盖范围内有多个簇首，节点并不是选择距离最近的簇首加入 簇，而是根据a m r p 选择簇首加入簇。 优点：h e e d 分簇速度更快，能产生分布均匀的簇首、更合理的网络拓扑。 缺点：h e e d 要求簇首节点可以相互通信，以保证各孤立簇的相互连通，限制了 1 4 济南大学硕 学伊论文 簇的规模。 2 2 5t - a n t t - a n t l l 7 1 将群集智能用于无线传感器网络分簇协议。首先计算出最优簇首的数量 n ，网络初始化时汇聚节点释放聆个蚂蚁( s o c i a la g e n t s ) 。这些蚂蚁不是同时释放的， 汇聚节点释放一个蚂蚁后，等待一段随机的时间后才会释放下一个蚂蚁，直到所有的 蚂蚁被释放完。汇聚节点随机选择一个邻节点，并向这个节点发送一个蚂蚁，接收到 蚂蚁的节点继续将蚂蚁发送到一个随机的邻节点，直到1 v r l ( 根据网络覆盖范围和节 点的射频范围设定) 的值为零。在蚂蚁释放的过程中不会产生信息素，最终拥有蚂蚁 的节点成为簇首。 节点成为簇首后向所有的邻节点广播一个a d v 消息，收到a d v 消息的非簇首 节点选择一个距离自己最近( 根据收到信号的强弱判断) 的簇首，根据本节点的剩余 能量和本节点射频范围内簇首的数量计算信息素水平p ，。非簇首节点向自己 选择的簇首发送一个j o i n 消息( 包含本节点的信息素水平) 申请加入该簇。 b = 等 ( 2 3 ) a p = k 篆虿1 眨4 ) i 为当前轮数，e m a x 为节点电池的最大能量，k 为算法的学习率。 在数据通信阶段，簇首与汇聚节点通信完成后，簇首把蚂蚁发送到信息素水平最 高的邻节点。即每个簇内，信息素水平最高的节点成为下一轮的新簇首。与典型的群 集智能有所不同，t - a n t 中拥有蚂蚁的节点不仅影响本节点的信息素水平，而且影 响邻节点的信息素水平。 t - a n t 协议使簇的分布更为均匀，网络中的节点能量消耗更为均衡。 2 3 分簇路由协议的优点 相比平面路由协议，分簇路由协议具有以下优点： ( 1 ) 分簇路由协议使用数据融合技术，簇首节点融合成员节点的数据之后再进 行转发，减少了数据通信量；非簇首节点只在自己的时隙内通信，其他时间关闭射频 模块进入休眠状态。簇